🤖 AI

Extracting Search Trees from LLM Reasoning Traces Reveals Myopic Planning

This paper reveals that while large language models generate extensive reasoning traces containing deep lookahead, their actual move decisions are driven by shallow, myopic search rather than the deep planning observed in human experts, a finding established through extracting and analyzing search trees from the game of four-in-a-row.

Original authors: Sixing Chen, Ji-An Li, Saner Cakir, Sinan Akcali, Kayla Lee, Marcelo G. Mattar

Published 2026-05-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sixing Chen, Ji-An Li, Saner Cakir, Sinan Akcali, Kayla Lee, Marcelo G. Mattar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching two different types of chess players: a human grandmaster and a very advanced AI that talks to itself while it thinks.

This paper investigates how these AI models (Large Language Models, or LLMs) actually plan their moves in a game called "Four-in-a-Row." The researchers wanted to know: When the AI writes out a long, detailed thought process, is it actually doing deep, strategic planning like a human, or is it just pretending?

Here is the breakdown of their findings using simple analogies:

1. The Setup: The "Talking" Game

The researchers set up a tournament where 27 different AI models played "Four-in-a-Row" against each other. This is a simple game where you drop colored discs into a grid, trying to get four in a row (horizontally, vertically, or diagonally).

Before making a move, the AI models were asked to "think out loud" (a process called Chain-of-Thought). They would generate long paragraphs of text, simulating future moves like: "If I play here, the opponent will play there, then I will play here..."

2. The Investigation: Reading the "Thought Map"

The researchers took these long, messy paragraphs of text and turned them into clean, structured search trees (like a family tree, but for game moves).

Root: The current board.
Branches: The moves the AI considered.
Leaves: The future scenarios the AI imagined.

They then compared these AI "thought maps" to how human experts play the same game.

3. The Big Discovery: The "Shallow" Thinker

The researchers found a surprising disconnect between what the AI says it is doing and what it actually does.

The Human Way: Human experts are like deep divers. They look far ahead. If they see a move, they simulate 5 or 6 steps into the future to see if it leads to a win. Their performance gets better the deeper they look.
The AI Way: The AI models are like superficial tourists.
- The Illusion: The AI writes out a very long, detailed story about looking 10 steps ahead. It looks like a deep dive.
- The Reality: When the AI actually picks a move, it ignores almost all of that deep thinking. It acts like a myopic (short-sighted) player. It only cares about the immediate next step.

The Analogy: Imagine a student writing a 10-page essay about how they will solve a math problem. They write out complex formulas for chapters 2 through 10. But when they actually write the final answer, they just look at the first sentence of the problem and guess. The long essay was just "decoration," not the actual engine driving the answer.

4. What Actually Makes the AI Win?

The researchers tested what drives the AI's success:

Depth (How far ahead they look): This didn't matter. Even if the AI wrote about looking 10 steps ahead, it didn't help them win.
Breadth (How many options they check): This was the key. The AI models that won were the ones that looked at more different first moves (like checking 20 different doors) rather than looking deeper into just one door.

It's as if the AI wins by casting a wide net, not by diving deep.

5. The "Surgery" Experiment

To prove that the AI wasn't actually using its deep thoughts, the researchers performed a "surgical" experiment.

They took the AI's long reasoning text and deleted the parts where it talked about looking far into the future (the "deep" parts).
They kept only the parts where it talked about the immediate next move.
The Result: The AI made the exact same moves as before.

This proved that the deep thinking was essentially "noise." The AI didn't need it to make its decision. The decision was driven entirely by the shallow, immediate thoughts.

6. The Conclusion

The paper concludes that there is a fundamental difference between human and AI planning:

Humans get smarter by thinking deeper.
AI gets smarter by thinking wider, but it doesn't actually use the deep thoughts it generates to make decisions.

The AI is good at simulating the appearance of deep planning, but it doesn't act on it. This suggests that simply making AI models write longer, more complex reasoning traces won't necessarily make them better planners; we need to teach them to actually use the deep thoughts they generate.

Technical Summary: Extracting Search Trees from LLM Reasoning Traces Reveals Myopic Planning

Problem Statement

Large Language Models (LLMs), particularly reasoning models, generate extended chain-of-thought (CoT) traces that appear to simulate future outcomes, resembling human planning. However, it remains unclear whether these traces constitute genuine systematic search or merely pattern completion. Existing behavioral benchmarks often fail to distinguish between models that successfully solve tasks via deep planning versus those that rely on shallow heuristics or memorization. Furthermore, even if LLMs generate search-like structures, it is unknown whether these structures causally drive decision-making or if the models act on different, unobserved mechanisms. This paper addresses the gap between the surface structure of LLM reasoning and the underlying algorithmic process driving move selection.

Methodology

The authors introduce a framework to extract, quantify, and model search trees from LLM reasoning traces within the domain of the board game "four-in-a-row" (a 4×9 grid).

Experimental Setup: A round-robin tournament was conducted involving 27 LLMs (both proprietary and open-weight) playing 1,404 games. Only models with fully accessible reasoning traces (14 models) were included in the analysis, yielding 9,696 reasoning traces.
Search Tree Extraction: An LLM judge (GPT-5) was employed to parse unstructured CoT traces into formal search trees. The judge identified explicitly deliberated moves, distinguishing between the model's candidate moves (depth-1 nodes) and simulated opponent replies (depth-2 nodes and beyond), outputting a nested list structure.
Computational Modeling: To determine how LLMs utilize these extracted trees, the authors fitted computational cognitive models adapted from human planning literature (Van Opheusden et al., 2023). Four model variants were tested:
- Full-tree: Uses minimax backup to propagate heuristic values from leaf nodes up to the root.
- Myopic: Evaluates only the immediate state resulting from a first-ply move, ignoring all deeper nodes.
- Discount: Interpolates between full-tree and myopic using a discount factor $\gamma$ .
- No-tree: Ignores the extracted search tree entirely, scoring moves based solely on a heuristic function of the current board state.
Causal Intervention: To test if reasoning traces causally drive decisions, the authors performed a surgical pruning study. They removed specific paragraphs from the CoT (e.g., final decisions, entire branches, or specific depth levels) and re-ran the model to observe changes in move selection.

Key Results

1. Search Effort and Performance

There is a positive correlation between search effort (total tree size) and winning rate. Models that generate larger search trees perform better. This relationship holds within model families and is causally supported by the observation that increasing reasoning effort (token budget) in the same model (GPT-OSS-120B) leads to larger trees and higher win rates.

2. Shallow Search and Breadth vs. Depth

LLMs exhibit significantly shallower search than human experts. The average maximum search depth across models ranged from 1.00 to 3.48 plies, whereas human experts in similar games typically search 4–6 plies. Crucially, performance is predicted by search breadth (the number of candidate moves considered at the root) rather than search depth. Controlling for breadth, search depth explains no additional variance in winning rates.

3. Myopic Decision-Making

Despite generating deep nodes in their traces, LLM move choices are best explained by a myopic model.

The myopic model (ignoring deep nodes) consistently outperformed the full-tree model in predicting LLM moves across all architectures.
The "depth harm" metric (the performance drop of the full-tree model relative to the myopic model) was positive for all models and increased with search depth, indicating that backing up values from deeper nodes actively impairs prediction accuracy.
The discount factor $\gamma$ in the discount model converged to near zero, confirming that LLMs assign negligible weight to deep lookahead when making decisions.

4. Causal Role of Reasoning Depth

The causal intervention study revealed that move selection is driven predominantly by shallow nodes:

Removing the final decision paragraph caused minimal change (2.1%).
Removing the entire branch corresponding to the chosen move caused a 32.0% change rate.
However, when progressively adding back paragraphs by depth, restoring only depth-1 paragraphs (immediate consequences) reduced the change rate to near baseline (4.1%). Adding deeper paragraphs (depth-2 and beyond) provided no further reduction in change rate.
This indicates that while LLMs write about deep lookahead, their decisions are causally determined by the immediate evaluation of candidate moves, not the deep search content.

Significance and Claims

The paper claims to reveal a fundamental dissociation between LLM and human planning:

Human Expertise: Driven by deeper search; performance scales with the ability to simulate further into the future.
LLM Planning: Generates the surface structure of tree search but acts on a myopic mechanism. The deep nodes in CoT traces are not utilized to guide the final decision.

The authors argue that the central question regarding LLM planning should be reframed from "Can they plan?" to "What kind of planning algorithm do their decisions reflect?" They suggest that current methods relying on increased test-time compute or longer reasoning traces may be insufficient if the model cannot effectively propagate value information from deep nodes to the root. The findings highlight a limitation in current LLM architectures (potentially related to attention mechanisms or uncertainty at depth) where deep lookahead is generated but not integrated into the decision policy. This work provides a generalizable framework for interpreting the structure of LLM planning and cautions against treating reasoning traces as transparent records of deliberation.