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

"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 121

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 causes foundation models to develop task heuristics instead of understanding? What explains the gap between LLM semantic understanding and production? Why doesn't LLM knowledge translate to improved reasoning outputs? How does explicit structure improve LLM reasoning on complex tasks? What actually drives chain-of-thought performance gains in reasoning tasks? Do base models contain latent reasoning capabilities that training can activate? What makes reasoning models struggle with ill-posed and unfamiliar problems? What determines whether visible reasoning traces improve task performance? Does training data format shape reasoning more than domain content? Why do multiple language models independently generate similar outputs? Does reasoning architecture matter more than model scale? How do different post-training structures affect learning outcomes? How do pretraining data composition and task diversity shape reasoning? How can knowledge graph structure improve reasoning and retrieval? Can scaling alone produce compositional generalization in neural networks? What can prompting techniques actually accomplish in language models? Does reasoning fine-tuning trade off other critical model abilities? Does parallel reasoning outperform sequential approaches in reasoning efficiency? Why does self-revision increase model confidence despite degraded accuracy? What systematic biases do LLM judges exhibit in evaluation? How should test-time compute be allocated adaptively across task difficulties? How does transparency of agent reasoning affect effective oversight? Do AI safety evaluations reliably detect unsafe model behavior? Does reinforcement learning create new reasoning capabilities or refine existing ones? Does architectural recurrence enable computational capabilities that fixed-depth models cannot achieve? Does chain-of-thought reasoning faithfully reflect actual model reasoning processes? Do reasoning traces accurately represent what models actually compute? What training data structures and signals produce robust learning across distributions? What improves LLM forecasting accuracy beyond base model capability? How do different reward signals affect model reasoning and calibration differently? How does verifier integration affect the generation-verification gap? Why does increased reasoning effort fail to improve theory of mind performance? Do AI explanations represent actual model reasoning or constructed post-hoc narratives? Can formal verification substitute for human understanding of AI proofs? Why does separating planning from execution enhance reasoning performance?

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 · 207 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