Geek Out Time: Tree-of-Thought for LLM Reasoning

As LLMs get better at producing structured explanations, it has become increasingly common to describe them as “reasoning models.” The release of OpenAI’s o-series, particularly o1, along with DeepSeek R1 etc, made this framing much more explicit. Unlike earlier models that relied primarily on scaling pre-training data and parameters, the o-series introduced reasoning as a distinct axis of improvement-allocating more compute at inference time to explore intermediate steps before producing a final answer.

With chain-of-thought prompting, models can articulate intermediate reasoning, reflect on assumptions, and arrive at answers that appear logically grounded. But after o1, the idea of a reasoning model became more than just better formatting of explanations. It suggested a different scaling strategy altogether — not just bigger models, but models that deliberately spend more time “thinking.”

That raises an interesting technical question. Under the hood, what does this reasoning actually look like? Is it a single coherent internal process, or is it closer to structured search over multiple candidate paths? And if it is search, how can we make that mechanism visible?

In this Geek Out, let’s play with Tree-of-Thought (ToT) to probe how LLM reasoning can be structured at the system level: how branching, evaluation, and pruning change model behaviour, and why this often leads to more reliable outcomes than a single linear chain-of-thought.

The example is intentionally simple, using a small math word problem involving GST and surcharges, I build a minimal Tree-of-Thought loop around DeepSeek. The goal is not to optimise accuracy, but to make the reasoning process observable.

From chain-of-thought to tree-of-thought

A standard chain-of-thought prompt encourages the model to produce one explicit reasoning path. This helps readability and often improves accuracy, but it remains a single trajectory. Once the model commits to an assumption early on, the rest of the answer tends to follow that path, even if the assumption is wrong.

Tree-of-Thought changes the structure. Instead of asking the model to explain itself once, we ask it to generate multiple candidate solution paths. These candidates are then evaluated, and only the stronger ones are allowed to continue. In effect, we move from “one explanation” to “many competing explanations”.

This is a small architectural change, but it has an outsized impact. The model is no longer forced to be right on the first try. It is allowed to explore alternatives.

What the code does

The setup below uses three components:

• An LLM (DeepSeek) to generate candidate answers
• A Python verifier to independently compute the correct result
• A simple search loop that keeps only the best candidates

Each iteration looks like this:

1. Generate multiple candidate solutions
2. Extract the proposed numeric answers
3. Verify each answer using executable Python
4. Keep only the highest-scoring candidates

This is Tree-of-Thought in its most minimal form.

Full code on Google Colab

The following code runs end-to-end in Colab. Add your DEEPSEEK_API_KEY via Colab secrets before running.

# !pip install openai

import re
import random
from dataclasses import dataclass, field
from collections import Counter
from openai import OpenAI

# --------------------------------------------------------
# Config — loads key from Colab secrets
# --------------------------------------------------------
try:
    from google.colab import userdata
    DEEPSEEK_API_KEY = userdata.get('DEEPSEEK_API_KEY')
except ImportError:
    # fallback for local dev
    import os
    DEEPSEEK_API_KEY = os.environ.get('DEEPSEEK_API_KEY')

if not DEEPSEEK_API_KEY:
    raise ValueError("Missing DEEPSEEK_API_KEY. Add it to Colab secrets.")

client = OpenAI(
    api_key=DEEPSEEK_API_KEY,
    base_url="https://api.deepseek.com"
)

MODEL = "deepseek-chat" 

def llm(prompt: str, temp=0.7, max_tokens=300) -> str:
    resp = client.chat.completions.create(
        model=MODEL,
        messages=[{"role": "user", "content": prompt}],
        temperature=temp,
        max_tokens=max_tokens
    )
    return resp.choices[0].message.content.strip()

# --------------------------------------------------------
# Python Verifier (the real deal)
# --------------------------------------------------------
def extract_code(text: str) -> str | None:
    """Pull python code from markdown fences or raw."""
    match = re.search(r"```python\s*(.*?)```", text, re.DOTALL)
    if match:
        return match.group(1).strip()
    match = re.search(r"```\s*(.*?)```", text, re.DOTALL)
    if match:
        return match.group(1).strip()
    return None

def run_python(code: str, timeout=5) -> tuple[bool, str]:
    """Execute code, return (success, output or error)."""
    import io
    import sys
    import threading

    result = {"ok": False, "output": "timeout"}

    def target():
        old_stdout = sys.stdout
        sys.stdout = io.StringIO()
        try:
            local_ns = {}
            exec(code, {"__builtins__": __builtins__}, local_ns)
            output = sys.stdout.getvalue()

            if "answer" in local_ns:
                result["ok"] = True
                result["output"] = str(local_ns["answer"])
            else:
                result["ok"] = True
                result["output"] = output.strip().split("\n")[-1] if output.strip() else "(no output)"
        except Exception as e:
            result["ok"] = False
            result["output"] = f"error: {type(e).__name__}: {e}"
        finally:
            sys.stdout = old_stdout

    thread = threading.Thread(target=target)
    thread.start()
    thread.join(timeout)

    if thread.is_alive():
        return False, "timeout"

    return result["ok"], result["output"]

def verify_with_python(problem: str, candidate: str) -> tuple[bool, str, str | None]:
    """
    Ask LLM to write code that computes the answer, then compare with candidate.
    """
    prompt = f"""
Solve this math problem with Python. Store the final numeric answer in variable `answer`.

Problem: {problem}

Just code, no explanation.
```python
"""
    resp = llm(prompt, temp=0.2, max_tokens=200)
    code = extract_code(resp) or resp

    ok, result = run_python(code)
    if not ok:
        return False, result, code

    # compare computed answer with candidate
    try:
        computed = float(result)
        proposed = float(candidate)
        passed = abs(computed - proposed) < 0.01
    except:
        passed = result.strip() == candidate.strip()

    return passed, result, code

# --------------------------------------------------------
# Tree-of-Thought
# --------------------------------------------------------
@dataclass
class Node:
    path: str
    answer: str | None = None
    verified: bool = False
    score: float = 0.0
    depth: int = 0

def propose_steps(problem: str, partial: str, k=4) -> list[str]:
    """Generate k candidate next steps."""
    prompt = f"""
Solve this math problem. Show your reasoning.

Problem: {problem}

{"Previous work:" + chr(10) + partial if partial else ""}

Give {k} different solution approaches. For each:
- Brief reasoning (1-2 lines)
- Final numeric answer

Format each as:
[1] reasoning... Answer: <number>
[2] reasoning... Answer: <number>
...
"""
    text = llm(prompt, temp=0.9, max_tokens=400)

    # parse candidates
    candidates = []
    for match in re.finditer(r"\[(\d+)\]\s*(.*?)(?=\[\d+\]|$)", text, re.DOTALL):
        candidates.append(match.group(2).strip())

    # fallback: split by "Answer:"
    if len(candidates) < 2:
        parts = re.split(r"(?=Answer:)", text)
        candidates = [p.strip() for p in parts if "Answer:" in p]

    return candidates[:k]

def extract_answer(text: str) -> str | None:
    """Pull numeric answer from candidate."""
    # try time format first (e.g., 9:01, 10:30)
    match = re.search(r"Answer:\s*(\d{1,2}:\d{2})", text, re.IGNORECASE)
    if match:
        return match.group(1)

    # then try regular number
    match = re.search(r"Answer:\s*(-?[\d,]+(?:\.\d+)?)", text, re.IGNORECASE)
    if match:
        return match.group(1).replace(",", "")

    # fallback: last number in text
    nums = re.findall(r"-?\d+(?:\.\d+)?", text)
    return nums[-1] if nums else None

def tot_solve(problem: str, max_depth=2, branch=4, keep=3, verbose=True) -> Node:
    """
    Tree search with Python verification.
    """
    root = Node(path="", depth=0)
    frontier = [root]

    for d in range(max_depth):
        if verbose:
            print(f"\n--- Depth {d+1} ---")

        candidates = []

        for node in frontier:
            steps = propose_steps(problem, node.path, k=branch)

            for step in steps:
                ans = extract_answer(step)
                new_path = (node.path + "\n\n" + step).strip()

                child = Node(path=new_path, answer=ans, depth=d+1)

                # verify with python
                if ans:
                    passed, result, code = verify_with_python(problem, ans)
                    child.verified = passed
                    child.score = 10.0 if passed else 0.1
                    if verbose:
                        status = "✓" if passed else "✗"
                        print(f"  {status} ans={ans} | {step[:60]}...")
                else:
                    child.score = 0.0

                candidates.append(child)

        # prune: keep top k
        candidates.sort(key=lambda n: (n.verified, n.score), reverse=True)
        frontier = candidates[:keep]

        # early exit if verified
        if frontier and frontier[0].verified:
            if verbose:
                print(f"\n  Found verified answer: {frontier[0].answer}")
            break

    return frontier[0] if frontier else root

# --------------------------------------------------------
# Baselines
# --------------------------------------------------------
def single_shot(problem: str) -> str | None:
    prompt = f"Solve this and give only the numeric answer.\n\nProblem: {problem}\n\nAnswer:"
    resp = llm(prompt, temp=0.3, max_tokens=100)
    return extract_answer(resp)

def self_consistency(problem: str, n=10) -> tuple[str | None, Counter]:
    answers = []
    for _ in range(n):
        ans = single_shot(problem)
        if ans:
            answers.append(ans)
    if not answers:
        return None, Counter()
    cnt = Counter(answers)
    return cnt.most_common(1)[0][0], cnt

# --------------------------------------------------------
# Test Problem
# --------------------------------------------------------
PROBLEMS = [
    {
        "id": "grab_ride",
        "q": "A Grab ride from Changi Airport to Orchard costs $28. There is a $5 airport surcharge and 9% GST on the total. If you give a $5 tip (no GST on tip), how much do you pay?",
        "expected": "40.97"
    },
]

def run_eval():
    print("=" * 50)
    print("EVALUATION")
    print("=" * 50)

    results = []

    for p in PROBLEMS:
        print(f"\n>> {p['id']}: {p['q']}")

        # single shot
        s_ans = single_shot(p["q"])
        s_ok = s_ans == p["expected"]

        # self-consistency
        sc_ans, sc_dist = self_consistency(p["q"], n=8)
        sc_ok = sc_ans == p["expected"]

        # ToT
        best = tot_solve(p["q"], max_depth=2, branch=4, keep=3, verbose=False)
        tot_ans = best.answer
        tot_ok = tot_ans == p["expected"]

        results.append({
            "id": p["id"],
            "expected": p["expected"],
            "single": (s_ans, s_ok),
            "sc": (sc_ans, sc_ok, sc_dist.most_common(3)),
            "tot": (tot_ans, tot_ok, best.verified)
        })

        print(f"   expected={p['expected']}")
        print(f"   single={s_ans} ({'ok' if s_ok else 'wrong'})")
        print(f"   SC={sc_ans} ({'ok' if sc_ok else 'wrong'}) dist={sc_dist.most_common(3)}")
        print(f"   ToT={tot_ans} ({'ok' if tot_ok else 'wrong'}) verified={best.verified}")

    # summary
    print("\n" + "=" * 50)
    print("SUMMARY")
    print("=" * 50)
    n = len(results)
    print(f"Single-shot: {sum(r['single'][1] for r in results)}/{n}")
    print(f"Self-consistency: {sum(r['sc'][1] for r in results)}/{n}")
    print(f"ToT+Verifier: {sum(r['tot'][1] for r in results)}/{n}")

# --------------------------------------------------------
# Run both problems
# --------------------------------------------------------
if __name__ == "__main__":
    for p in PROBLEMS:
        print("=" * 50)
        print(f"Problem: {p['id']}")
        print(f"Q: {p['q']}")
        print(f"Expected: {p['expected']}")
        print("=" * 50)

        result = tot_solve(p["q"], max_depth=2, branch=4, keep=3, verbose=True)

        print("\nBEST PATH:")
        print(result.path)
        print(f"\nAnswer: {result.answer}")
        print(f"Verified: {result.verified}")
        print(f"Correct: {result.answer == p['expected']}")
        print("\n")

Output

==================================================
Problem: grab_ride
Q: A Grab ride from Changi Airport to Orchard costs $28. There is a $5 airport surcharge and 9% GST on the total. If you give a $5 tip (no GST on tip), how much do you pay?
Expected: 40.97
==================================================

--- Depth 1 ---
  ✓ ans=40.97 | ** Step-by-step addition with GST on fare + surcharge only. ...
  ✓ ans=40.97 | ** Compute GST first: \( 33 \times 1.09 = 35.97 \), then add...
  ✓ ans=40.97 | ** Treat tip separately from taxable amount: Total = \( (28 ...
  ✓ ans=40.97 | ** Alternative check: GST = \( 0.09 \times 33 = 2.97 \), so ...

  Found verified answer: 40.97

BEST PATH:
** Step-by-step addition with GST on fare + surcharge only.  
Answer: **40.97**

**

Answer: 40.97
Verified: True
Correct: True

What this shows about LLM reasoning

What’s interesting here is not that the model gets the answer right. It’s that the correctness comes from structure, not from asking the model to “think harder”. At the first depth, the model produces several plausible solutions. From a language perspective, they are all coherent. The difference only becomes visible when we evaluate them against an external constraint. Tree-of-Thought gives the model room to explore, and verification gives the system a way to select.

In other words, reasoning here is not a single internal process. It is the outcome of generation plus search.

This distinction becomes especially clear in domains like mathematics and science. In these tasks, there is typically a well-defined objective signal: an equation balances, a numeric value matches, a proof step is valid, or a program compiles. That objective constraint makes Tree-of-Thought particularly powerful, because incorrect branches can be pruned decisively. The search space may be large, but it is anchored by something checkable.

For more subjective or open-ended questions, the dynamic changes. If the task is to compare two business strategies, evaluate ethical trade-offs, or draft a policy recommendation, there may not be a single ground-truth answer. In those cases, Tree-of-Thought does not converge toward a mathematically verified solution, but toward internally consistent or better-structured arguments. The evaluation step becomes heuristic rather than exact, and pruning depends on scoring rather than proof.

The mechanism is the same, generation plus search, but the strength of the external constraint determines how sharp the selection process can be. In math and science, verification is crisp. In subjective domains, it is graded. Tree-of-Thought still helps explore alternatives, but the reliability ceiling is shaped by how well the task can be externally evaluated.

Why Tree-of-Thought is useful

Tree-of-Thought is valuable not because it makes models smarter, but because it makes failures less brittle. By allowing multiple paths to exist in parallel, the system is less sensitive to early mistakes. This pattern shows up repeatedly in agent frameworks, tool-using systems, and planning-based approaches.

Once you view LLM reasoning through this lens, it becomes clear why combining models with tools, verifiers, and planners is so effective. The model supplies possibilities. The system decides which ones matter.

Thoughts

Tree-of-Thought is not a replacement for chain-of-thought, but a generalisation of it. Where chain-of-thought exposes one path, Tree-of-Thought explores many. For tasks that require precision or robustness, that difference matters.

This experiment helped clarify what people often mean by “LLM reasoning” in practice. It’s less about introspective thinking, and more about how we structure generation, evaluation, and control around the model.

Zooming out, what’s actually happening here is a shift in how we spend our ‘compute budget.’ Standard LLM calls are basically a ‘shoot from the hip’ approach; we trade speed for a one-shot, good-enough guess. But by moving to a branching structure, we’re intentionally burning more tokens and latency to buy ourselves some reliability. It effectively turns the LLM from a predictive text engine into a search engine for logic. In other words, reasoning becomes partially a function of how much search you allow at inference time.

But once you frame it this way, another question naturally appears. If reasoning quality improves with more inference-time compute, is there a point where the model “overthinks”? Is more internal search always better? Or does performance plateau — or even degrade — when the search becomes too deep or too unconstrained?

From a systems perspective, this becomes a trade-off problem. More search increases the probability of discovering a correct path. But it also increases the chance of exploring irrelevant branches, reinforcing early mistakes, or drifting into internally consistent but incorrect trajectories. In other words, more compute does not automatically imply better reasoning. It implies a larger search space.

This is why Tree-of-Thought is interesting. It externalises what might otherwise be implicit. Instead of letting the model internally expand reasoning tokens in a single hidden trajectory, we explicitly branch candidate paths, score them, and prune aggressively. That makes the reasoning process observable, controllable, and measurable.

And this is where the “overthinking” analogy becomes useful — not in a human sense, but in a computational one. Search depth must be balanced against evaluation quality. If the verifier is weak, deeper search simply amplifies noise. If the verifier is strong, deeper search can significantly improve reliability. So the real question becomes less about whether a model can reason, and more about how reasoning emerges from the interaction between generation, search, and verification…

Happy experimenting and hv fun !