Tháng trước, tôi build một agent giải bài toán lên lịch cho 12 người, mỗi người có ràng buộc khác nhau về giờ và ngày. ReAct (bài 6) không đi tới đâu: agent loop 25 lần, thử một path, hit contradiction, backtrack bằng… câu prompt mới, hit contradiction lại, rồi trả về một lịch sai hoàn toàn. Tổng cộng $4 và kết quả không dùng được.

Thử lại với Tree of Thoughts. Agent spawn 3 hướng giải khác nhau song song, evaluate từng bước, prune branch nào có vẻ sai sớm, tiếp tục branch tốt nhất. Lần này xong trong 8 phút, tốn $28, ra lịch đúng.

$28 so với $4. ToT đắt hơn 7 lần. Nhưng ReAct không cho ra kết quả dùng được. Câu hỏi không phải “ToT có rẻ hơn không”, mà là “ToT có worth không với task này”. Bài này giải thích khi nào nó worth.

ToT là gì, tại sao khác CoT và ReAct

Chain-of-Thought (bài 10)

CoT là reasoning tuyến tính: một chuỗi thought steps từ A đến Z.

Thought 1 -> Thought 2 -> Thought 3 -> Answer

Đơn giản, hiệu quả với task có đường đi rõ. Không backtrack, không thử nhiều hướng.

ReAct (bài 6)

ReAct xen kẽ thought với action (tool call) và observation:

Thought -> Action -> Observation -> Thought -> Action -> ...

Linh hoạt hơn CoT vì agent tương tác với môi trường. Nhưng vẫn là một path duy nhất. Khi path đó sai, agent phải tự nhận ra rồi từ đầu.

Tree of Thoughts (Yao et al. 2023)

ToT bỏ ý tưởng “một path tuyến tính”. Thay vào đó, reasoning được tổ chức như một cây tìm kiếm:

              [Root]
           /    |    \
        [A1]  [A2]  [A3]
        /  \         |
     [B1] [B2]     [B3]
            |
          [C1]  <- solution

Tại mỗi node, agent có thể:

  • Generate nhiều thought states tiếp theo (branching)
  • Evaluate từng state xem có đáng tiếp tục không (pruning)
  • Search theo BFS hoặc DFS để khám phá cây

Ba thứ đó là 3 component cốt lõi của ToT.

Ba component của ToT

1. Thought generation

Tại mỗi node trong cây, agent được hỏi: “có những bước tiếp theo nào hợp lý?”

Hai cách generate:

Sampling độc lập: gọi LLM k lần với cùng state hiện tại, lấy k thoughts khác nhau (dùng temperature > 0 để đa dạng).

def generate_thoughts(state: str, k: int = 3) -> list[str]:
    thoughts = []
    for _ in range(k):
        response = client.messages.create(
            model="claude-sonnet-4-6",
            max_tokens=512,
            temperature=0.8,
            messages=[{
                "role": "user",
                "content": f"{state}\n\nSuggest one possible next step:"
            }]
        )
        thoughts.append(response.content[0].text)
    return thoughts

Sequential propose: gọi LLM một lần, yêu cầu output k thoughts cùng lúc. Nhanh hơn nhưng thoughts ít đa dạng hơn.

def generate_thoughts_batch(state: str, k: int = 3) -> list[str]:
    response = client.messages.create(
        model="claude-sonnet-4-6",
        max_tokens=1024,
        messages=[{
            "role": "user",
            "content": (
                f"{state}\n\n"
                f"List {k} different possible next steps. "
                "Format: one step per line, numbered."
            )
        }]
    )
    lines = response.content[0].text.strip().split("\n")
    return [l.split(". ", 1)[-1] for l in lines if l.strip()]

2. State evaluation

Đây là phần làm ToT khác biệt và cũng là phần dễ sai nhất. Mỗi node được đánh giá xem có đáng explore tiếp không.

Hai cách evaluate:

Value function: LLM cho điểm từng state (ví dụ 1-10, hoặc sure/likely/impossible).

def evaluate_state(problem: str, state: str) -> float:
    response = client.messages.create(
        model="claude-sonnet-4-6",
        max_tokens=256,
        messages=[{
            "role": "user",
            "content": (
                f"Problem: {problem}\n\n"
                f"Current reasoning state:\n{state}\n\n"
                "Rate the likelihood this path leads to a correct solution. "
                "Reply with one of: sure (1.0), likely (0.7), unlikely (0.3), impossible (0.0). "
                "Then explain briefly why."
            )
        }]
    )
    text = response.content[0].text.lower()
    if "sure" in text:
        return 1.0
    elif "likely" in text:
        return 0.7
    elif "unlikely" in text:
        return 0.3
    return 0.0

Voting: generate nhiều thoughts đến cùng goal, vote xem answer nào xuất hiện nhiều nhất. Dùng khi final answer là discrete (đúng/sai, số, lựa chọn).

def vote_on_answers(problem: str, candidates: list[str]) -> str:
    candidates_text = "\n".join(
        f"{i+1}. {c}" for i, c in enumerate(candidates)
    )
    response = client.messages.create(
        model="claude-sonnet-4-6",
        max_tokens=256,
        messages=[{
            "role": "user",
            "content": (
                f"Problem: {problem}\n\n"
                f"Candidate solutions:\n{candidates_text}\n\n"
                "Which solution is most likely correct? "
                "Reply with just the number."
            )
        }]
    )
    vote = response.content[0].text.strip()
    try:
        idx = int(vote) - 1
        return candidates[idx]
    except (ValueError, IndexError):
        return candidates[0]

3. Search algorithm

Với cây đã có generation và evaluation, ToT dùng BFS hoặc DFS để explore.

BFS (Breadth-First Search): khám phá theo từng level, tại mỗi level giữ lại b node tốt nhất (beam search).

from dataclasses import dataclass, field

@dataclass
class ThoughtNode:
    state: str
    score: float = 0.0
    depth: int = 0
    path: list[str] = field(default_factory=list)

def tree_of_thoughts_bfs(
    problem: str,
    initial_state: str,
    max_depth: int = 4,
    breadth: int = 3,
    beam_size: int = 2,
) -> str:
    frontier = [ThoughtNode(state=initial_state, depth=0)]

    for depth in range(max_depth):
        next_frontier = []
        for node in frontier:
            # Generate candidate next steps
            thoughts = generate_thoughts_batch(
                f"Problem: {problem}\n\nProgress so far:\n{node.state}",
                k=breadth,
            )
            for thought in thoughts:
                new_state = node.state + "\n" + thought
                score = evaluate_state(problem, new_state)
                next_frontier.append(ThoughtNode(
                    state=new_state,
                    score=score,
                    depth=depth + 1,
                    path=node.path + [thought],
                ))

        # Prune: keep only beam_size best nodes
        next_frontier.sort(key=lambda n: n.score, reverse=True)
        frontier = next_frontier[:beam_size]

        # Early termination if top node has score 1.0
        if frontier and frontier[0].score >= 1.0:
            break

    return frontier[0].state if frontier else "No solution found"

DFS với backtracking: đi sâu một nhánh, nếu score thấp thì backtrack và thử nhánh khác.

def tree_of_thoughts_dfs(
    problem: str,
    state: str,
    depth: int = 0,
    max_depth: int = 4,
    score_threshold: float = 0.5,
) -> str | None:
    if depth >= max_depth:
        return state

    thoughts = generate_thoughts_batch(
        f"Problem: {problem}\n\nProgress:\n{state}", k=3
    )

    for thought in thoughts:
        new_state = state + "\n" + thought
        score = evaluate_state(problem, new_state)

        if score < score_threshold:
            continue  # prune

        result = tree_of_thoughts_dfs(
            problem, new_state, depth + 1, max_depth, score_threshold
        )
        if result:
            return result

    return None  # backtrack

BFS tốt hơn khi muốn nhiều option ở mỗi level và tài nguyên cho phép. DFS tốt hơn khi muốn tìm answer nhanh và solution space hẹp.

Ví dụ đầy đủ: scheduling problem

import anthropic

client = anthropic.Anthropic()

PROBLEM = """
Lên lịch họp 1 tiếng cho 3 người:
- Alice: rảnh 9h-12h, 14h-17h thứ 2
- Bob: rảnh 10h-12h, 15h-17h thứ 2
- Carol: rảnh 9h-11h, 14h-16h thứ 2
Tìm khung giờ tất cả đều rảnh.
"""

def solve_scheduling():
    initial_state = (
        "Bắt đầu phân tích lịch rảnh của từng người."
    )
    result = tree_of_thoughts_bfs(
        problem=PROBLEM,
        initial_state=initial_state,
        max_depth=3,
        breadth=3,
        beam_size=2,
    )
    print("Solution path:")
    print(result)

solve_scheduling()

ToT so với CoT và ReAct

Tiêu chíCoTReActToT
Số path explore11nhiều (b x depth)
BacktrackingKhôngGiới hạnCó (DFS)
Tương tác toolKhôngCóCó thể tích hợp
Token usageThấpTrung bìnhCao (5-10x CoT)
Tốt choReasoning tuyến tínhTask cần toolPlanning, search, multi-constraint
Pitfall chínhKhông backtrackPath sai khó recoverEval function sai

Compute cost thực tế

ToT đắt theo cấp số nhân. Với BFS depth=4, breadth=3, beam=2:

  • Level 0: 1 node generate 3 thoughts, evaluate 3 states = 6 calls
  • Level 1: 2 nodes x 3 thoughts + 6 evaluations = 12 calls
  • Level 2: 2 nodes x 3 thoughts + 6 evaluations = 12 calls
  • Level 3: 2 nodes x 3 thoughts + 6 evaluations = 12 calls
  • Tổng: ~42 LLM calls so với ~5-8 calls của một ReAct thành công

Với Claude Sonnet 4.6 ở $3/MTok input và $15/MTok output, 42 calls × ~500 token mỗi call = khoảng $2-5 cho một ToT nhỏ. Scale lên depth=6, breadth=5 là $15-30 dễ dàng.

Khi nào worth compute

Dùng ToT khi:

  • Task có nhiều ràng buộc phải thỏa mãn đồng thời (scheduling, constraint satisfaction)
  • Không gian solution có nhiều dead-end và cần backtracking thật sự
  • Một path sai đầu sẽ dẫn đến toàn bộ solution sai (cascading errors)
  • Budget tính theo task (không phải per-call), accuracy quan trọng hơn cost
  • Task toán học có nhiều bước trung gian

Không dùng ToT khi:

  • ReAct hoặc CoT đã đủ tốt (đa số task đơn giản)
  • Task cần real-time response (ToT chậm)
  • Budget giới hạn và task không đủ complexity để justify
  • Task là Q&A, summarization, translation: tuyến tính là đủ
  • Không có cách evaluate state tốt (evaluation là điều kiện cần, không có là dùng ToT vô ích)

Pitfall: evaluation function sai là thảm họa

Đây là fail mode đau nhất tôi từng gặp với ToT.

Trong project scheduling, tôi viết evaluation function đại loại: “rate how promising this scheduling approach is”. LLM, do bias trong training data, có xu hướng đánh giá cao những path bắt đầu bằng Alice rồi Bob rồi Carol (thứ tự alphabet).

Kết quả: cây explore sâu theo hướng đó, prune hết các path bắt đầu từ constraint khó nhất (Carol ít rảnh nhất). Cuối depth=4, không tìm được solution. Agent báo “no feasible schedule”, trong khi answer là 10h-11h thứ 2.

Chi phí: $30, thời gian: 15 phút, kết quả: sai.

Bài học:

Evaluation function phải:

  1. Đặc thù cho problem: không phải “how promising does this look” mà là “how many constraints are already satisfied / violated?”

  2. Measurable, không phải vibes: thay vì nhờ LLM cảm nhận, tính toán constraint satisfaction numerically khi có thể.

  3. Đối xứng với goal: nếu goal là “find slot all 3 can attend”, evaluate phải penalize path nào đang bỏ sót người.

def evaluate_scheduling_state(problem: str, state: str) -> float:
    # Tốt hơn: extract concrete constraints đã thỏa
    response = client.messages.create(
        model="claude-sonnet-4-6",
        max_tokens=256,
        messages=[{
            "role": "user",
            "content": (
                f"Problem: {problem}\n\nCurrent state:\n{state}\n\n"
                "Count: (1) how many people's availability has been checked, "
                "(2) how many conflicts found so far. "
                "Reply in format: checked=N conflicts=M"
            )
        }]
    )
    text = response.content[0].text
    # Parse và tính score dựa trên concrete numbers
    # ...
    return score
  1. Test evaluation trước khi chạy full tree: chạy evaluation function trên 5-10 state examples bạn biết tốt/xấu, xem nó cho điểm đúng không. Nếu evaluation function sai, toàn bộ tree search sai theo.

Tích hợp ToT với tool use

ToT không nhất thiết phải thuần LLM. Thoughts có thể kèm theo tool calls:

def generate_thought_with_tool(state: str, available_tools: list) -> dict:
    response = client.messages.create(
        model="claude-sonnet-4-6",
        max_tokens=512,
        tools=available_tools,
        messages=[{
            "role": "user",
            "content": f"{state}\n\nWhat is one possible next step?"
        }]
    )
    if response.stop_reason == "tool_use":
        # Execute tool, get result, fold into state
        tool_result = execute_tools(response.content)
        new_state = state + f"\n[Tool result: {tool_result}]"
        return {"state": new_state, "type": "tool"}
    return {"state": state + "\n" + response.content[0].text, "type": "thought"}

Nhưng cẩn thận: mỗi node có tool call = tốn cả API call cho tool bên ngoài. Với 42 ToT nodes, 42 API calls là có thể. Cost và latency tăng tuyến tính với số nodes.

Cheatsheet

Khái niệmÝ nghĩa
Thought generationTạo k candidate next steps từ một state
State evaluationScore một state xem có đáng explore tiếp không
BFS / beam searchExplore theo level, giữ b node tốt nhất mỗi level
DFS với backtrackingĐi sâu một path, backtrack khi score thấp
PruningBỏ qua node có score thấp hơn threshold
VotingDùng khi final answer là discrete, nhiều path vote cho answer
Tham sốẢnh hưởng
breadth (b)Số thoughts generate tại mỗi node. Tăng = nhiều option hơn, đắt hơn
beam_sizeSố nodes giữ lại sau mỗi level (BFS). Tăng = rộng hơn, đắt hơn
max_depthSố level tối đa. Tăng = sâu hơn, đắt hơn theo cấp số nhân
score_thresholdNgưỡng prune (DFS). Thấp = giữ nhiều branch, đắt. Cao = prune nhiều, nhanh nhưng có thể bỏ solution

Lời kết

ToT là công cụ mạnh, nhưng không phải mặc định. Đa số task agent làm hàng ngày, ReAct hoặc CoT là đủ. ToT cần thiết khi task có cấu trúc tree thật sự: nhiều ràng buộc chồng chéo, cần backtracking, và quan trọng nhất là bạn có thể viết được một evaluation function đáng tin cậy.

Evaluation function là điều kiện cần. Không có nó, ToT chỉ là một cách tốn tiền để ra kết quả ngẫu nhiên.

Bài tiếp theo, Self-reflection: critic, verifier, retry pattern, sẽ đi theo hướng khác: thay vì explore nhiều path song song, agent tự nhìn lại output của mình và sửa. Nhẹ hơn ToT về compute, nhưng hiệu quả với một lớp lỗi khác hoàn toàn.

Đọc thêm trong series: