Nội dung này phục vụ mục đích giáo dục. Không đưa dữ liệu nhạy cảm hoặc quyền hành động thật vào một cây tìm kiếm chưa được kiểm soát.

Trả lời ngắn: Tree of Thoughts là cách biến bài toán thành cây gồm nhiều trạng thái trung gian, sinh vài phương án ở mỗi nút, đánh giá rồi giữ, cắt hoặc quay lui. Nó phù hợp khi quyết định sớm có thể dẫn vào ngõ cụt, nhưng không bảo đảm đúng nếu evaluator hoặc dữ kiện đầu vào sai.

Đọc xong, bạn sẽ hiểu:

  • Một cây ToT thật cần state, generator, evaluator và search controller nào.
  • Vì sao ToT khác Chain of Thought một đường và Self-Consistency bỏ phiếu ở cuối.
  • Cách đặt node budget, depth cap, stop rule và verifier để cây không phình vô hạn.

1. Tree of Thoughts là gì, và một cây thật cần gì?

a. Từ một đường thành nhiều trạng thái

Giả sử bạn cần xếp ba việc A, B, C với ba điều kiện:

  • A phải nằm cuối.
  • C không được nằm đầu.
  • Mỗi việc chỉ dùng một lần.

Nếu chọn A trước, ta biết ngay nhánh đó sai. Chọn C trước cũng sai. Chọn B trước còn hợp lệ; từ đó có thể thử A hoặc C. Nhánh B→A đi vào ngõ cụt vì A không còn ở cuối, còn B→C→A đạt đủ điều kiện.

Phần ghi “đã xếp gì, còn việc gì, điều kiện nào vẫn phải giữ” gọi là state, hay trạng thái. Một thought ở đây không phải suy nghĩ bí mật trong đầu model; nó là phương án trung gian có ý nghĩa làm state thay đổi, chẳng hạn “đặt B vào vị trí đầu”.

Paper gốc mô tả ToT như khung suy luận mở rộng Chain of Thought bằng cách khám phá các đơn vị văn bản trung gian, đánh giá lựa chọn, nhìn trước và quay lui. Yao và cộng sự, NeurIPS 2023

b. Bốn phần tối thiểu

Một cây có kiểm soát cần:

  1. State representation: cách ghi trạng thái đủ để tiếp tục.
  2. Generator: phần sinh vài phương án từ state hiện tại.
  3. Evaluator: rule, tool, model hoặc người chấm phương án.
  4. Search controller: phần quyết định mở rộng, cắt, quay lui hay dừng.

Chỉ yêu cầu “hãy nghĩ ba cách” rồi in ba bullet chưa phải ToT. Nếu không có state, đánh giá giữa đường và quy tắc tìm kiếm, đó chỉ là brainstorm nhiều phương án.

c. Không cần cây cho mọi câu hỏi

Câu hỏi tra cứu, phép tính đơn giản hoặc task có tool chuyên dụng thường không cần ToT. Cây chỉ đáng tiền khi có nhiều lựa chọn trung gian, sai sớm làm hỏng phần sau và ta có cách chấm nhánh.

2. Một cây Thought được sinh, chấm và quay lui ra sao?

Hình 1 — Cây chỉ mở rộng state còn hợp lệ; ngõ cụt được quay lui thay vì kéo dài bằng mọi giá.

a. Node, edge và candidate

Mỗi node, hay nút, chứa một state. Edge, hay cạnh, là lựa chọn nối state cha với state con.

Tại nút gốc [ ] / còn A,B,C, generator sinh ba phương án:

  • [A] / còn B,C
  • [B] / còn A,C
  • [C] / còn A,B

Evaluator dùng rule đã biết. A bị loại vì phải cuối; C bị loại vì không được đầu; B được giữ.

b. Prune không phải xóa tùy hứng

Prune, hay cắt nhánh, là ngừng mở rộng một node vì nó vi phạm điều kiện, quá kém hoặc vượt budget. Mỗi lần prune cần reason có thể audit.

Từ B, ta thử:

  • B→A: sai vì còn C nhưng A đã không còn ở cuối.
  • B→C: hợp lệ, tiếp tục thành B→C→A.

Nếu đi sâu vào B→A, search controller phải backtrack, tức quay về nút B để thử nhánh C. Nó giống đi vào ngõ cụt rồi quay lại ngã rẽ gần nhất, không xóa cả bản đồ.

c. Score chỉ là chỉ dẫn

Trong bài demo, có thể dùng:

  • 0: vi phạm điều kiện, prune.
  • 1: chưa vi phạm, còn phải mở rộng.
  • 2: hoàn thành đủ điều kiện, stop.

Điểm này là rule tự xây, không phải xác suất đúng. Với task mở, evaluator LLM có thể chấm sai và cắt mất nhánh tốt. Vì vậy nên lưu state, score, action và reason cho từng node.

3. ToT khác Chain of Thought và Self-Consistency ở đâu?

Hình 2 — ToT khác Self-Consistency ở chỗ chấm và cắt state trung gian trước khi mọi nhánh thành đáp án hoàn chỉnh.

Phương pháp Cấu trúc Chấm lúc nào Quay lại
Chain of Thought Một đường bước trung gian Thường ở cuối Không có search controller
Self-Consistency Nhiều đường hoàn chỉnh độc lập Tổng hợp đáp án cuối Không sửa state giữa đường
Tree of Thoughts Nhiều state trung gian có nhánh Trong lúc search Có prune/backtrack

Chain of Thought khuyến khích tạo các bước trung gian trên một đường. Wei và cộng sự, NeurIPS 2022 Self-Consistency lấy nhiều reasoning path rồi tổng hợp đáp án cuối. Wang và cộng sự, ICLR 2023

ToT giữ nhiều state chưa hoàn chỉnh và chấm trước khi đi hết đường. Đây là khác biệt vận hành, không phải chuyện sơ đồ có hình cây đẹp hơn.

a. BFS và DFS nói dễ hiểu

Breadth-first search (BFS) mở các node theo tầng: thử mỗi ngã rẽ một đoạn rồi mới đi sâu. Nó giữ nhiều state cùng lúc, dễ tốn bộ nhớ và lượt chấm.

Depth-first search (DFS) đi sâu một nhánh trước; gặp ngõ cụt thì backtrack. Nó giữ ít state hơn nhưng có thể lãng phí thời gian ở nhánh dài kém.

Repo chính thức của Princeton cung cấp code và prompt minh họa cách search; đó là tài liệu nghiên cứu, không phải chuẩn production mặc định. Princeton NLP

b. Cây phình nhanh

Branching factor là số nhánh trung bình mỗi node; depth là số tầng lựa chọn.

Nếu mỗi node sinh b = 3 nhánh qua d = 4 tầng, riêng tầng lá có thể là:

3^4 = 81 lá

Một cây đầy đủ còn có 1 + 3 + 9 + 27 + 81 = 121 node. Mỗi node có thể cần một lần generate hoặc evaluate. Vì vậy node budget phải được đặt trước, không chờ hóa đơn token mới nghĩ cách dừng.

4. Sai lầm, rủi ro và Control Card

Hình 3 — Một cây không có node budget và stop rule có thể phình nhanh hơn giá trị mà nó tạo ra.

Trước khi chạy, điền đủ:

  1. Task có thật sự cần search nhiều bước không?
  2. State chứa field nào và bỏ chi tiết nào?
  3. Generator sinh tối đa bao nhiêu candidate?
  4. Evaluator chấm theo rule hoặc bằng chứng nào?
  5. Node budget và depth cap là bao nhiêu?
  6. Khi nào prune; khi nào backtrack?
  7. Tie giữa hai node được xử lý ra sao?
  8. Stop rule nào xác nhận hoàn thành hoặc hết budget?
  9. Verifier nào kiểm nghiệm kết quả ngoài cây?
  10. Nhánh nào bắt buộc human gate?

Ba sai lầm nặng:

  • State mơ hồ: bỏ mất ràng buộc, khiến node sau tưởng nhánh sai là hợp lệ.
  • Evaluator cùng lỗi với generator: model tự sinh rồi tự chấm có thể lặp thiên lệch.
  • Duplicate branch: nhiều câu chữ khác nhau nhưng cùng một state, làm tốn budget giả tạo.

ToT không bảo đảm kết quả đúng. Paper gốc báo kết quả trên Game of 24, Creative Writing và Mini Crosswords; đó là task nghiên cứu cụ thể, không phải bằng chứng mọi workflow sẽ tốt hơn.

Nên đứng ngoài khi calculator, database hoặc công cụ chuyên giải ràng buộc/lộ trình có thể trả lời trực tiếp. Không để score của evaluator tự cấp quyền gửi email, ghi database, chạy code hay giao dịch. Kết quả có tác động thật cần verifier và người duyệt.

5. Bài tập 15 phút: tìm lịch B–C–A trên giấy

a. Chuẩn bị

Dùng giấy bút hoặc bảng tính miễn phí. Viết ba rule: A cuối, C không đầu, mỗi việc một lần.

  • 3 phút: tạo mẫu state [đã xếp] / [còn lại].
  • 4 phút: sinh A, B, C ở tầng đầu.
  • 3 phút: chấm và prune node sai.
  • 3 phút: mở rộng node B đến nghiệm.
  • 2 phút: ghi node budget, stop rule và lý do dừng.

Không dùng lịch, email hay tool thật; đây chỉ là dữ liệu giả.

b. Mẫu đối chiếu đã điền

Node State Score Action Lý do
1 [A] / còn B,C 0 Prune A phải cuối
2 [B] / còn A,C 1 Expand Chưa vi phạm
3 [C] / còn A,B 0 Prune C không đầu
4 [B,A] / còn C 0 Backtrack A không còn cuối
5 [B,C,A] / còn rỗng 2 Stop Đủ mọi điều kiện

Node budget là 5, depth cap là 3. Verifier đọc lại ba rule và xác nhận B→C→A; lúc đó mới stop.

6. Tổng kết và bài học tiếp theo

a. Năm ý chính

  • Tree of Thoughts là search trên nhiều state trung gian, không phải brainstorm có hình cây.
  • Generator sinh candidate; evaluator chấm; controller prune, backtrack hoặc stop.
  • ToT chấm giữa đường, còn Self-Consistency thường aggregate đáp án hoàn chỉnh ở cuối.
  • Branching factor và depth khiến số node tăng rất nhanh.
  • Node budget, verifier và human gate phải có trước khi tự động hóa.

b. Câu hỏi tự kiểm tra

  • Một cây ToT tối thiểu cần bốn phần nào?
  • Prune khác backtrack ra sao?
  • ToT khác Self-Consistency ở thời điểm đánh giá thế nào?
  • Vì sao b=3, d=4 có thể tạo 81 lá?

c. Gợi ý đáp án

Xem gợi ý câu 1

Cần state representation, generator, evaluator và search controller. → xem mục 1.

Xem gợi ý câu 2

Prune ngừng mở rộng nhánh; backtrack quay về nút trước để thử nhánh khác. → xem mục 2.

Xem gợi ý câu 3

ToT chấm state trung gian; Self-Consistency thường tổng hợp khi các đường đã có final answer. → xem mục 3.

Xem gợi ý câu 4

Mỗi tầng nhân thêm ba lựa chọn, nên số lá là `3 × 3 × 3 × 3 = 81`. → xem mục 3.

d. Thuật ngữ cần nhớ

Thuật ngữ Giải thích ngắn
Tree of Thoughts Search qua nhiều state trung gian có đánh giá.
State Phần đã làm và ràng buộc còn lại.
Thought Phương án trung gian làm state thay đổi.
Generator Phần sinh candidate tiếp theo.
Evaluator Phần chấm candidate theo rule.
Prune Ngừng mở rộng một nhánh.
Backtrack Quay về nút trước để thử nhánh khác.
Branching factor Số nhánh trung bình mỗi node.
Depth Số tầng lựa chọn trong cây.

e. Nguồn tham khảo

f. Học tiếp gì?

Bài trước là Self-Consistency trong LLM là gì? #3, nơi nhiều đường hoàn chỉnh được tổng hợp ở cuối. Bài tiếp theo là Prompt Optimization: Tối ưu prompt có hệ thống #5, nơi ta định nghĩa metric, bộ test và vòng thay đổi prompt có kiểm soát.

Nhắc lại: Nội dung chỉ phục vụ mục đích giáo dục. Cây tìm kiếm không thay thế dữ kiện đúng, tool chuyên dụng, quyền tối thiểu hoặc người duyệt trước hành động bên ngoài.