Chain of Thought, Tree of Thoughts, MCTS, and Reflexion — the four algorithms shaping how every AI agent thinks before it acts.
01 · Core Concept
Why Agents Need Planning Algorithms — And How They Actually Work
When you ask a person to solve a hard math problem, they don't just say the first thing that comes to mind. They try an approach, get stuck, back up, try another angle, check their work. This deliberate, exploratory style of reasoning is what separates a thoughtful expert from a hasty guesser.
Early LLMs were "hasty guessers." They generated the most probable next token, one at a time, left to right — no backing up, no exploring alternatives, no self-checking. This works for simple tasks. For hard multi-step reasoning — math, code, planning a research project — it fails badly.
The four algorithms covered today are the field's answer to this: each one forces the LLM to slow down and think more carefully, in a different way. They sit at the boundary between prompting (asking the model differently) and search (using the model repeatedly to explore a space of reasoning paths).
Here's how the four algorithms relate to each other:
| Algorithm |
Core Metaphor |
Search Structure |
Self-Correction? |
Best For |
| Chain of Thought |
Show your work |
Linear (one path) |
❌ No |
Math, logic |
| Self-Consistency |
Ask multiple people, vote |
Parallel paths, majority vote |
❌ No |
Factual Q&A |
| Tree of Thoughts |
Chess player planning ahead |
Tree (branching + pruning) |
✅ Via backtracking |
Complex planning |
| MCTS |
AlphaGo, but for language |
Tree with statistical rollouts |
✅ Via simulation |
Math olympiad, code |
| Reflexion |
Learning from your own mistakes |
Sequential trials + memory |
✅ Core mechanism |
Agents, coding |
01a · Algorithm 1
Chain of Thought (CoT) — The Foundation
Analogy first: If you ask a student "what is 17 × 24?" they're more likely to get it right if you say "show your work" versus "just give the answer." Chain of Thought is the LLM equivalent of "show your work."
Precise technical definition: CoT is a prompting strategy introduced by Wei et al. at Google Brain in 2022. Instead of showing the model input-output examples, you show it examples of input → reasoning steps → output. The key finding: this dramatically improves performance on multi-step reasoning tasks, and the effect becomes significant only in models with ≥ 100B parameters (an emergent capability).
💭
How CoT Works Mechanically
The model generates tokens one by one, left to right. With CoT, those intermediate tokens aren't wasted — they become "working memory" the model can condition on when generating the final answer. Each reasoning step constrains the probability distribution for the next step, making the final answer more accurate.
In the few-shot version, you prepend 3–8 examples of (problem, reasoning-chain, answer) before the actual question. In the zero-shot version (introduced in a follow-up by Kojima et al.), you simply add the instruction "Let's think step by step." — a four-word phrase that became famous for its outsized effect.
The "Let's think step by step" finding was so striking it generated its own paper (Kojima et al., 2022, "Large Language Models are Zero-Shot Reasoners"). It works because it shifts the model's prior toward a reasoning-before-answering distribution during pretraining.
⚡
Self-Consistency: The Cheap Upgrade to CoT
Wang et al. (2022, arXiv:2203.11171) added a clever extension: instead of taking the single greedy output, sample multiple diverse reasoning chains from the model, then take a majority vote on the final answers. This consistently outperforms single-chain CoT by 5–15% on benchmarks.
Why it works: different reasoning paths can reach the same correct answer. If 7 out of 10 independent chains converge on the same answer, it's likely right. The diversity of paths captures more of the solution space than one greedy decode.
Self-consistency trades API cost (you call the model N times instead of once) for accuracy. For many production use-cases, calling a model 5 times is cheaper than fine-tuning or using a bigger model — and often just as good.
01b · Algorithm 2
Tree of Thoughts (ToT) — Deliberate Search
Analogy first: A chess grandmaster doesn't just play the first move that comes to mind. They visualize multiple candidate moves, mentally simulate the opponent's response to each, and prune lines that look bad before deciding. Tree of Thoughts gives an LLM this same deliberate, look-ahead capability.
Precise technical definition: ToT (Yao et al., NeurIPS 2023, arXiv:2305.10601) frames problem solving as search over a tree of reasoning states. Each node is a partial solution (a "thought"), each edge is one reasoning step. The LLM plays two roles: proposer (generates candidate next thoughts) and evaluator (scores how promising each partial solution looks). A search algorithm — BFS or DFS — explores the tree.
↓ LLM proposes 3 candidate next thoughts
Approach A
Approach B ★
Approach C ✗
↓ Evaluator scores each (C is pruned)
A → Step 1
A → Step 2 ✗
B → Step 1 ★
B → Step 2
↓ Backtrack from A when stuck, continue on B
Final Answer (via B → Step 1)
Simplified Tree of Thoughts execution. Green = selected path. Gray = pruned. The model can backtrack — unlike linear CoT.
🎯
Why ToT Beats CoT on Hard Problems
CoT commits to a single reasoning path — if step 2 is wrong, every subsequent step is likely wrong too, with no recovery. ToT maintains multiple partial solutions simultaneously and can backtrack. In the "Game of 24" benchmark (given 4 numbers, combine with arithmetic to reach 24), GPT-4 with CoT solved only 4% of problems. GPT-4 with ToT solved 74%.
The reason for this dramatic gap: Game of 24 requires systematic search over a combinatorially large space. No single lucky reasoning path gets you there reliably. ToT's tree search handles this naturally.
ToT's weakness: it's expensive. Generating 3–5 candidate thoughts at each of N depth levels requires N × 5 LLM calls just for proposals, plus evaluation calls. For tasks where simple CoT works, ToT is massive overkill. Engineers choose between them based on task complexity.
01c · Algorithm 3
Monte Carlo Tree Search (MCTS) — Statistical Lookahead
Analogy first: MCTS is the algorithm that made AlphaGo defeat Go world champions. It explores a game tree by running thousands of random "simulations" (playouts) from each position, then uses the statistical outcomes to estimate which moves are best. Applied to LLMs: instead of game moves, you have reasoning steps; instead of win/loss, you have answer quality.
Precise technical definition: MCTS for LLMs runs four phases in a loop until a budget is exhausted:
🗺️
SELECT
UCT formula picks most promising node
→
🌿
EXPAND
LLM generates new child thoughts
→
🎲
SIMULATE
Roll out to completion, get score
→
📊
BACKPROP
Update ancestor node values
↺
🔢
The UCT Formula — What Makes MCTS Smart
The UCT (Upper Confidence bound for Trees) formula governs which node to expand next:
UCT(node) = Q(node)/N(node) + C × √(ln N(parent) / N(node))
The first term is the exploitation term: how good has this node been so far (average reward)? The second term is the exploration term: how underexplored is this node? The constant C balances exploration vs. exploitation. This elegantly ensures the algorithm doesn't get stuck always refining one good-looking path, but also doesn't waste time on clearly bad paths.
In Go, the LLM is replaced by a value network. In LLM agents, the LLM serves as both the policy (what thought to generate next) and part of the value function (how promising does this partial solution look?). The rStar paper (Microsoft, 2024) showed a 7B model could beat OpenAI o1-preview on math benchmarks using this approach.
🚀
rStar: MCTS + LLMs at Scale (2024)
Microsoft Research's rStar framework (ICLR 2025) combined MCTS with a mutual reasoning mechanism: two LLMs — a "policy model" that proposes reasoning steps and a "process reward model" (PRM) that scores each step's quality — work together during tree search. The action space was expanded to include: proposing single steps, generating sub-questions, rephrasing the problem, and re-answering sub-questions.
Result: LLaMA-2-7B went from 12% to 64% accuracy on a math benchmark. A 7B model achieved 90% on MATH, outperforming OpenAI o1-preview (85.5%). This demonstrated that small models + smart search can beat large models + greedy decode — a finding with major implications for cost-efficient deployment.
01d · Algorithm 4
Reflexion — Verbal Reinforcement Learning
Analogy first: Traditional reinforcement learning (RL) is like training a dog with treats — the model learns from rewards by adjusting millions of parameters. This is slow, expensive, and requires many trials. Reflexion is like training a human intern: after each failed attempt, they write down what went wrong and why, then try again with that self-critique in their working memory. No weight update required.
Precise technical definition: Reflexion (Shinn et al., NeurIPS 2023, arXiv:2303.11366) is an agent framework with three key components:
🔄
The Three-Module Architecture
Actor: The LLM that takes actions and generates text. This is the main model trying to solve the task — same as in ReAct.
Evaluator: Scores the Actor's output. Can be a rule-based check (did the code pass tests?), a trained reward model, or even another LLM judging quality. This replaces the environment's reward signal.
Self-Reflection Model: Takes the (trajectory, outcome, evaluator score) as input and generates a verbal reflection — a natural language summary of what went wrong and what should be tried differently. This reflection is stored in an episodic memory buffer and prepended to future attempts.
The insight is that LLMs are already trained on enormous amounts of human self-correction and debugging. When you ask a model "you tried this, it failed because X — what would you do differently?" it draws on that learned expertise rather than updating weights from scratch.
🎬
TRY
Actor attempts task
→
⚖️
EVALUATE
Score outcome
→
✍️
REFLECT
Write verbal critique
→
📚
REMEMBER
Store reflection in memory
→
🔁
RETRY
New attempt with memory
📈
Benchmark Results
On AlfWorld (sequential text-based household tasks): ReAct alone completed 73% of tasks. ReAct + Reflexion completed 97% — solving 130 out of 134 tasks after 12 consecutive trials. The agent learned to stop taking inefficient detours and to avoid the specific hallucinations it had identified in previous attempts.
The paper also showed strong results on coding (HumanEval) and question answering. Critically, these gains came without any model fine-tuning — just prompt engineering and an episodic memory buffer.
Reflexion's limitation: it depends on the model's self-assessment being accurate. If the model misdiagnoses why it failed, it generates a misleading reflection that can actually hurt subsequent performance. This is the "sycophancy risk" — the model reflects what sounds plausible, not necessarily what is true.
02 · Papers to Know
The Four Papers That Defined This Field
Seminal
Google Brain 2022
Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Le, Denny Zhou · arXiv:2201.11903
The paper demonstrated that providing step-by-step worked examples as few-shot prompts dramatically improves multi-step reasoning in large language models. Tested on arithmetic, commonsense, and symbolic reasoning benchmarks, CoT prompting with GPT-3 (540B parameters) surpassed fine-tuned state-of-the-art models at the time. Crucially, the effect only appeared in models above ~100B parameters — below that, intermediate reasoning tokens hurt rather than helped.
Why it changed the field: This paper shifted the paradigm from "bigger model = better" to "better prompting = better, and cheaper." It spawned an enormous literature on prompt engineering and revealed reasoning as an emergent capability — a concept that became central to debates about what LLMs are actually doing.
→ arXiv:2201.11903
Seminal
NeurIPS 2023
Tree of Thoughts: Deliberate Problem Solving with Large Language Models
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan · arXiv:2305.10601
ToT generalized CoT from a single reasoning path to a tree of partial solutions, enabling backtracking and look-ahead. The model both generates candidate "thoughts" and evaluates their promise, with BFS or DFS search over the resulting tree. On the Game of 24 benchmark, GPT-4 with CoT solved 4% of problems; with ToT it solved 74% — a 20× improvement. Creative writing and Mini Crossword tasks showed similar dramatic gains.
Why it changed the field: ToT formalized the connection between LLM inference and classical search algorithms — a bridge many researchers had intuited but hadn't formally built. It opened the door to applying decades of AI planning research (A*, BFS, DFS, MCTS) directly to language model inference.
→ arXiv:2305.10601
Seminal
NeurIPS 2023
Reflexion: Language Agents with Verbal Reinforcement Learning
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, Shunyu Yao · arXiv:2303.11366
Reflexion introduced a training-free alternative to reinforcement learning for agents: instead of updating model weights based on reward signals, it stores verbal self-reflections in an episodic memory buffer that gets prepended to future prompts. A simple evaluator signals success/failure; a reflection module generates natural-language critiques that guide the agent's next attempt. The framework achieved state-of-the-art results on sequential decision-making (AlfWorld), coding (HumanEval), and reasoning tasks without any gradient updates.
Why it changed the field: Reflexion proved that you could get learning-like behavior from LLM agents without the enormous cost of RL fine-tuning. It became a blueprint for "inference-time improvement loops" — a category of techniques that now underpins most production agent frameworks.
→ arXiv:2303.11366
Recent · ICLR 2025
Microsoft Research
Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers (rStar)
Zhiyuan Li, Shuaiyi Li, Zeqi Lin, et al. · Microsoft Research Asia / Harvard · 2024
rStar combined MCTS with mutual reasoning between two models: a policy LLM proposes reasoning actions across a rich action space (step proposals, sub-question generation, problem rephrasing), while a process reward model (PRM) scores each step's correctness. The two models must "agree" on the solution path for high confidence. LLaMA-2-7B under rStar went from 12% to 64% on a math benchmark; a 7B model outperformed OpenAI o1-preview (90% vs. 85.5%) on the MATH dataset. The model solved 53.3% of USA Math Olympiad problems.
Why it changed the field: rStar showed definitively that small models + smart inference-time search can beat large models + greedy decoding — upending the assumption that capability always requires scale. It gave enterprises a path to high-quality reasoning without frontier-model costs.
→ Related: MCTS Boosts Reasoning via Iterative Preference Learning
04 · What the Community Is Saying
Debates, Insights, and Emerging Consensus
"The loopy era of AI: agents running continuous self-improvement loops on code and research. We ran 700 experiments in 2 days and discovered 20 optimizations — including novel architecture tweaks — on a single GPU. The Reflexion loop, now applied to the scientific method itself."
Karpathy's autoresearch repo directly implements Reflexion-style thinking for ML research. Each "experiment" is a complete ReAct loop: the agent reads the training code, hypothesizes an improvement, modifies the code, runs the experiment, observes the result, and decides whether to keep or discard. The result turned heads across the field because it suggests that reasoning algorithms compound — CoT inside a Reflexion loop is more powerful than either alone.
"Chain-of-thought prompting is not reasoning. It's glorified pattern matching. True reasoning requires world models, persistent representations, and the ability to simulate — things autoregressive LLMs fundamentally lack by design."
LeCun is the most prominent critic of the CoT / test-time compute paradigm. He argues these approaches hit a ceiling because the underlying architecture (next-token prediction) doesn't support the kind of grounded, compositional reasoning needed for general intelligence. His proposed alternative: Joint Embedding Predictive Architectures (JEPA). This is a genuine open debate in the field — not settled.
"Test-time compute scaling works. The question is no longer whether you should use inference-time reasoning — you should — but how to route intelligently between fast (CoT) and slow (MCTS/tree search) reasoning based on task difficulty."
Weng (now co-founder of Thinking Machines) published a landmark post reviewing the state of test-time compute. Her key insight: the field is converging on a "routing" model — simple queries get fast CoT, complex queries trigger tree search or multi-trial Reflexion. This matches how OpenAI structures the o1 vs o3-mini vs o3 pricing tiers.
"The most underappreciated shift in 2025: multi-step planning went from a research curiosity to a daily engineering decision. Do I use extended thinking here? Do I let the agent reflect? These choices now affect product quality and API bills simultaneously."
Willison tracked how "agentic engineering patterns" became the core skill of practitioners in 2025–2026. Practitioners now routinely benchmark CoT vs. MCTS vs. Reflexion on their specific tasks because the cost-performance tradeoff differs dramatically by use case — there's no universally best algorithm.
07 · Questions You Can Now Ask
5 Questions That Signal Deep Understanding
1
When you're choosing between CoT, self-consistency, and MCTS for a production task, what signals in the task structure tell you which to reach for? Specifically, how do you think about the verifiability of intermediate steps as a deciding factor?
2
Reflexion's verbal reinforcement improves performance without weight updates — but the self-critiques are generated by the same model that made the mistake. How do you prevent the reflection from being confidently wrong, and does this limitation fundamentally cap what Reflexion can fix?
3
rStar showed a 7B model beating o1-preview with MCTS + a process reward model. What's your read on whether that gap survives as the base models get stronger — is MCTS a permanent advantage or does it amortize out as CoT improves inside RL-trained models?
4
OpenAI hides the reasoning chain; Anthropic exposes it. From a safety and reliability standpoint, what are the concrete engineering differences in how you'd debug a failure or audit a decision in each system?
5
RLVR caused chain-of-thought to emerge spontaneously in o1 and DeepSeek-R1. Does that mean the CoT patterns we see are genuinely functional reasoning, or are they post-hoc rationalizations the model learned correlated with correct answers — and does that distinction matter for how we should trust the output?