Deep Dive: Tree-of-Thought / Graph-of-Thought
Tổng quan Search
ToT/GoT là bước chuyển từ linear reasoning sang search-based reasoning. Khi không có một đường suy luận duy nhất đủ tốt, việc thử nhiều nhánh rồi prune/backtrack thường mạnh hơn CoT thuần.
Tree-of-Thought cho model đề xuất nhiều thought branches, đánh giá chúng, rồi mở rộng nhánh tiềm năng. Graph-of-Thought đi xa hơn: các thoughts trở thành vertex trong một graph, cho phép hợp nhất, chia tách và feedback loop phức tạp hơn.
Điểm cốt lõi của cả hai là ta không còn coi reasoning là một dòng text đơn tuyến. Ta bắt đầu coi nó như một không gian tìm kiếm có scoring function.
| Aspect | Ý nghĩa | Trade-off |
|---|---|---|
| Branching | Sinh nhiều đường suy luận | Tốn token hơn |
| Evaluation | Chấm thought trước khi đi tiếp | Cần scorer tốt |
| Backtracking | Quay lại khi nhánh xấu | Controller phức tạp hơn |
Cơ chế Mechanics
Controller thường làm 3 việc: generate thoughts, evaluate thoughts, expand/prune thoughts. Với GoT, controller còn phải xử lý merge và cross-edge dependencies.
Nếu scorer yếu, ToT biến thành random branching. Nếu scorer tốt, nó có thể tìm được phương án toàn cục mà CoT tuyến tính bỏ sót.
Search loop sketch
generate_k_thoughts()
score_each_thought()
prune_low_scores()
expand_high_scores()
repeat_until_goal()Khi dùng Fit
ToT/GoT hợp với planning, puzzle solving, creative search, combinatorial tasks và bất kỳ bài toán nào mà “đi theo câu đầu tiên” dễ bị kẹt.
Nếu bạn đã có một evaluator mạnh, branching search có thể đáng giá rất nhanh. Nếu không, các nhánh chỉ làm tăng chi phí mà không tạo signal chất lượng.
Ưu điểm
- Tăng xác suất tìm được đường tốt hơn
- Hợp với search/planning khó
- Cho phép pruning và backtracking rõ ràng
Nhược điểm
- Controller và scorer phức tạp
- Token cost cao
- Overkill với task chỉ cần một câu trả lời ngắn
Failure modes Risk
Rủi ro thực tế
- Scoring function phản ánh sai objective thật.
- Branch explosion làm chi phí tăng phi lý.
- Graph merge logic làm mất tín hiệu quan trọng.
- Controller overfit vào benchmark cụ thể.
So sánh Compare
| Technique | Khác biệt chính | Chọn khi |
|---|---|---|
| CoT | Một đường reasoning | Task nhỏ, cần rẻ và nhanh |
| Self-consistency | Nhiều đường nhưng vote cuối | Answer ổn định hơn path |
| Prompt chaining | Nhiều call tuần tự, ít search | Muốn inspect từng bước rõ |