What makes deterministic recursive reasoning models underperform on multi-solution tasks?
This explores why recursive reasoning models that update their internal state deterministically — producing one fixed trajectory per problem — struggle when a task has several valid answers or strategies, and what the corpus suggests is actually breaking.
This reads the question as being about a specific architectural limit: when a recursive reasoner updates its latent state deterministically, it commits to a single path through the solution space, and that's exactly the wrong shape for a problem that admits many answers. The clearest statement of this comes from GRAM, which argues that deterministic latent updates can only ever represent one prediction, so the model literally has no way to encode a distribution over valid strategies. Swapping in stochastic latent transitions lets the same architecture hold uncertainty and sample alternatives — turning a model that picks one road into one that can entertain several Can stochastic latent reasoning help models explore multiple solutions?. The follow-on insight is that this isn't just about quality but about how you scale: sampling parallel latent trajectories lets reasoning grow in *width* rather than only depth, exploring multiple solutions at once instead of grinding deeper on a single guess Can reasoning systems scale wider instead of only deeper?.
But determinism is only half the story. A second cluster of work shows that even models which do explore behave less like scientists and more like tourists — they wander down invalid branches and then abandon promising ones before finishing. This 'underthinking' is premature path-switching, and strikingly it can be fixed at decoding time with a penalty on thought-transition tokens, no retraining required Do reasoning models switch between ideas too frequently? Why do reasoning models abandon promising solution paths?. The deeper diagnosis is that current reasoners lack the three properties of systematic search — validity, effectiveness, and necessity — so their success probability drops exponentially as problems deepen Why do reasoning LLMs fail at deeper problem solving?. On multi-solution tasks this compounds: a model that can't represent multiple paths *and* can't search the ones it has is doubly handicapped.
What's worth knowing is that several papers push back on calling any of this a 'reasoning' failure at all. When frontier models hit a 20–23% ceiling on constraint-satisfaction problems that demand genuine backtracking, the bottleneck looks less like missing intelligence and more like an inability to sustain reflective search over unfamiliar instances Can reasoning models actually sustain long-chain reflection?. Relatedly, collapses often turn out to be *execution* failures — models that know the algorithm still can't run it step-by-step at scale, and tool-enabled versions sail past the supposed cliff Are reasoning model collapses really failures of reasoning?. And failures track instance-level novelty, not task complexity: models fit patterns from training instances rather than learning a general procedure, so anything off the familiar manifold breaks regardless of difficulty Do language models fail at reasoning due to complexity or novelty?.
The surprising corner of the corpus is that chain-of-thought reasoning can actively *hurt* on certain multi-answer tasks. On exception-based inductive rule inference, reasoning models scored below 25% while plain non-reasoning models hit 55–65% — the extended thinking introduced overgeneralization, math overuse, and hallucinated constraints that drowned out the negative evidence needed to recognize exceptions Why do reasoning models fail at exception-based rule inference?. Reasoning models also fail to systematically beat standard ones on numerical optimization, because longer chains produce more text rather than more iterative computation Do reasoning models actually beat standard models on optimization?. The throughline: committing hard to one elaborated line of thought is precisely what a problem with many valid solutions punishes.
If you want the opposing design direction, the Hierarchical Reasoning Model is the interesting counterweight — it gets near-perfect on Sudoku and mazes (classic multi-path search problems) by coupling slow planning with fast computation across two timescales, escaping the fixed-depth ceiling that constrains ordinary transformers Can recurrent hierarchies achieve reasoning that transformers cannot?. Read together, the corpus suggests the cure for deterministic underperformance isn't 'think longer' but 'think wider and more systematically' — represent uncertainty, sample alternatives, and structure the search rather than committing to one trajectory and hoping it's the right one.
Sources 11 notes
GRAM replaces deterministic latent updates with stochastic sampling, enabling models to represent distributions over solutions rather than single predictions. This allows handling of ambiguous problems and multiple valid strategies that deterministic designs cannot represent.
GRAM shows that stochastic latent transitions enabling parallel trajectory sampling sidestep the serial latency cost of depth-only scaling. Width matches token-level parallelism benefits: independent paths sample the solution space without variance inflation.
o1-like models frequently abandon reasoning paths mid-exploration, wasting tokens on incomplete approaches. A decoding-only penalty on thought-transition tokens (TIP strategy) discourages switching, improving accuracy on challenging math without model fine-tuning.
Reasoning LLMs exhibit two reinforcing failures: wandering (invalid exploration) and underthinking (premature path-switching). Decoding-level interventions like thought-switching penalties improve accuracy without fine-tuning, suggesting viable solutions exist but are abandoned prematurely.
Current reasoning models lack the three properties of systematic exploration: validity, effectiveness, and necessity. This causes success probability to drop exponentially with problem depth, making medium problems solvable but deep problems catastrophically harder.
DeepSeek-R1 and o1-preview achieve only 20-23.6% exact match on 850 constraint satisfaction problems requiring genuine backtracking. This ceiling reveals that reflective reasoning fluency does not translate to actual problem-solving competence on unfamiliar instance structures.
Models confined to text-only generation cannot execute multi-step procedures at scale, even when they know the underlying algorithm. Tool-enabled models solve problems beyond the supposed reasoning cliff, suggesting the bottleneck is procedural execution bandwidth.
LRMs don't break at complexity thresholds but at instance-novelty boundaries. Models fit instance-based patterns rather than generalizable algorithms, so any reasoning chain succeeds if trained on similar instances, regardless of length.
Across four game-based tasks, reasoning models scored below 25% on exception rules versus 55–65% for non-reasoning models. Chain-of-thought introduces math overuse, overgeneralization, and hallucinated constraints that amplify errors in negative evidence recognition.
Reasoning variants with extended CoT show no consistent advantage over standard models on constraint-bound numerical tasks like optimal power flow. Extended thinking produces more text, not more iterative computation, suggesting the bottleneck is numeric procedure rather than reasoning steps.
The Hierarchical Reasoning Model couples slow abstract planning with fast detailed computation across two timescales, achieving near-perfect performance on Sudoku and mazes where chain-of-thought methods fail completely. With only 27M parameters and 1,000 samples, HRM escapes the AC0/TC0 complexity ceiling that constrains fixed-depth transformers.