SYNTHESIS NOTE
Topics›Reasoning o1 o3 Search›this note

Why do reasoning LLMs fail at deeper problem solving?

Explores whether current reasoning models systematically search solution spaces or merely wander through them, and how this affects their ability to solve increasingly complex problems.

Synthesis note · 2026-02-22 · sourced from Reasoning o1 o3 Search
How should we spend compute at inference time?

"Reasoning LLMs are Wandering Solution Explorers" provides the most rigorous formalization yet of why reasoning models fail as problem complexity increases. The claim: current RLLMs do not systematically explore solution spaces. They wander.

Systematic exploration requires three properties: (a) validity — the trace follows the reachability structure; (b) effectiveness — the trace contains at least one goal state; (c) necessity — every state in the trace contributes to goal discovery or dead-end elimination. Current models fail all three.

The formalization makes the failure quantifiable. A wandering RLLM performing depth-first search on a binary tree of depth d has a probability pw of omitting one of two child nodes at each decision point. The success probability drops exponentially with depth d. This is not a gradual degradation — it is catastrophic. Problems that appear within reach at depth 5 become virtually impossible at depth 15 not because the model lacks reasoning ability but because it lacks search discipline.

Four failure modes are identified:

The finding directly challenges the "more thinking tokens = better reasoning" narrative. A wandering model given more tokens doesn't explore more systematically — it wanders more extensively. This is the mechanism behind Does more thinking time always improve reasoning accuracy?: additional compute doesn't fix structural search deficiency.

The exponential degradation result connects to Does policy entropy collapse limit reasoning performance in RL?. Entropy collapse reduces exploration diversity during training; wandering reduces exploration discipline during inference. Both are manifestations of the same problem: the model converges on familiar patterns rather than systematically covering the solution space.

Apple's three-regime confirmation. "The Illusion of Thinking" (Apple) provides independent confirmation through controllable puzzle environments with precise complexity manipulation. Three performance regimes emerge: (1) low-complexity — standard models outperform reasoning models with greater token efficiency; (2) medium-complexity — reasoning models gain advantage through extended thinking; (3) high-complexity — both model types collapse to zero. Near the collapse point, reasoning models reduce their reasoning effort despite having ample token budget — a counterintuitive behavioral scaling limit. Even providing explicit optimal algorithms does not prevent collapse, confirming the bottleneck is execution not conceptualization. The three-regime structure refines the wandering explorer thesis: wandering is harmful at low complexity (overthinking easy problems), partially beneficial at medium complexity (exploring toward solutions), and irrelevant at high complexity (no amount of wandering reaches the goal).

Inquiring lines that read this note 107

This note is a source for these research framings, grouped by the broader line of inquiry each explores. Scan the bold lines of inquiry; follow any specific question forward.

What capability tradeoffs emerge when scaling model reasoning abilities? How effectively do deterministic tools improve language model reasoning on formal tasks? Why can LLMs generate ideas better than they evaluate them? How faithfully do LLMs reflect their actual reasoning in outputs and explanations? Why do LLM research ideas score high on novelty yet collapse into low diversity? How does latent reasoning compare to verbalized chain-of-thought? Do base models contain latent reasoning that training can unlock? How do evaluation biases undermine LLM quality assessment systems? Why do reasoning models fail at systematic problem-solving and search? Why does training format shape reasoning strategy more than domain content? How does reasoning graph topology affect breakthrough insights and generalization? How does example difficulty affect learning efficiency in language models? How should iterative research systems allocate reasoning per search step? Do language models perform faithful symbolic reasoning independent of semantic grounding? How do neural networks separate factual knowledge from reasoning abilities? How do knowledge graphs enable efficient multi-hop reasoning over alternatives? Does model scaling alone produce compositional generalization without symbolic mechanisms? Can prompting strategies overcome LLM biases without model fine-tuning? How do language models inherit human biases from training data? When do additional thinking tokens stop improving reasoning performance? Do accurate-looking LLM outputs hide structural failures in learning and reasoning? What critical LLM failures do standard benchmarks hide? Do language models develop causal world models or rely on statistical patterns? Why does self-revision increase model confidence while degrading accuracy? How can models identify insufficient information and respond appropriately without guessing? Why do benchmark improvements fail to reflect actual reasoning quality? What actually drives chain-of-thought reasoning improvements in language models? How do training data properties shape reasoning capability development? How can AI systems learn from failures without cascading errors? What causes silent corruption to amplify through delegated workflows? Does reinforcement learning teach reasoning or just when to reason? Do corrupted reasoning traces serve as effective supervision signals? How do LLMs distinguish causal reasoning from temporal and semantic associations? How do knowledge injection methods compare across cost and effectiveness?

Related concepts in this collection 8

This note in its neighbourhood — explore the map, then jump to a related concept in the list below.

Concept map
19 direct connections · 193 in 2-hop network ·dense cluster Open in graph ↗
Why do reasoning LLMs fail at deeper problem sol… Does more thinking time always improve reasoning a… Does policy entropy collapse limit reasoning perfo… Does self-revision actually improve reasoning in l… Why does parallel reasoning outperform single chai… Does outcome-based RL diversity loss spread across… Can evolutionary search beat sampling and revision… Do reasoning models switch between ideas too frequ… Why do reasoning models fail differently at traini…

Click a node to walk · click center to open · click Open in graph to see this note in the full knowledge graph

your link semantically near linked from elsewhere

Related papers in this collection 8

Papers most semantically related to this note, ranked by cosine similarity in the embedding space.

Search by related questions 4

Suggested questions this note speaks to — click to search the collection, or type your own.

What happens to reasoning accuracy when models use more thinking tokens?Why do reasoning models reduce effort despite having token budget remaining?How does policy entropy during training affect search discipline during inference?Can explicit optimal algorithms prevent reasoning model collapse at high complexity?
Original note title

reasoning llms are wandering explorers not systematic searchers — four failure modes degrade success probability exponentially with problem depth