LEAD: Breaking the No-Recovery Bottleneck in Long-Horizon Reasoning

Denys Pushkin; Emmanuel Abbe

cs.AIMar 6, 2026

LEAD: Breaking the No-Recovery Bottleneck in Long-Horizon Reasoning

Authors: Denys Pushkin, Emmanuel Abbe

Organizations: EPFL, Apple

Abstract

Long-horizon execution in Large Language Models (LLMs) remains unstable even when high-level strategies are provided. Evaluating on controlled algorithmic puzzles, we demonstrate that while decomposition is essential for stability, extreme decomposition creates a "no-recovery bottleneck". We show that this bottleneck becomes critical due to highly non-uniform error distribution, where consistent errors on a few "hard" steps become irreversible. To address this, we propose Lookahead-Enhanced Atomic Decomposition (LEAD). By incorporating short-horizon future validation and aggregating overlapping rollouts, LEAD provides enough isolation to maintain stability while retaining enough local context to correct errors. This enables the o4-mini model to solve Checkers Jumping up to complexity $n=13$ , whereas extreme decomposition fails beyond $n=11$ .

Figures & tables

Panel of Figure 1 — Figure 1: Comparison of baseline methods across two puzzles.

Panel of Figure 2 — Figure 2: Non-uniform error distributions in Checkers Jumping. (a) Per-step error histograms for o4-mini and GPT-5.2 ( $n=15$ ) show that failures are concentrated on specific “hard steps.” (b) Pairwise Total Variation (TV) distance heatmap ( $n=13$ ) between error distributions of different models. High off-diagonal values indicate that hard steps vary significantly across architectures, while low diagonal values confirm the robustness of our estimates.

Panel of Figure 3 — Figure 3: Lookahead improves robustness on hard steps. Rank-ordered step accuracies for Atomic decomposition vs. Lookahead ( $k=8$ ) show that while Lookahead introduces a slight overhead on “easy” steps for the o4-mini model, it consistently boosts performance on the hardest moves (the right tail) for both tested models. The step accuracies were estimated by sampling 50 solutions for each step in Checkers Jumping ( $n=13$ ).

Panel of Figure 4 — Figure 4: Conditional accuracy of length-8 rollouts for Checkers Jumping ( $n=13$ ). The plot demonstrates how lookahead rollout accuracy evolves when conditioned on the correctness of the first predicted step. Data is aggregated from 50 samples per step across the entire horizon (excluding the last 7 positions).

	o4-mini ( $N$ )			GPT-5.2 ( $N$ )					Qwen ( $N$ )
Method	11	12	13	13	14	15	16	17	14	15	16
AD	14	0	0	0	36	0	4	0	0	0	0
AD + Voting	76	16	0	20	100	0	96	0	100	94	0
LEAD	100	56	76	100	100	100	100	80	84	96	60

Table 1: LEAD scales reasoning performance across architectures. Success rates (%) on Checkers Jumping comparing Atomic Decomposition (AD), AD with first-to-ahead-by-3 voting, and LEAD (with parameters

k=8,h=2,t=3

). Bold indicates best performance per horizon.

Panel of Figure 5 — Figure 5: Computational cost of robust execution. Average number of tokens per solution for Atomic Decomposition (AD), AD with first-to-ahead-by-3 voting, and LEAD (parameters as in Table 1 ). While LEAD increases token consumption, it enables the model to surpass the no-recovery bottleneck that typically limits extreme decomposition techniques. Notably, simply scaling the budget for AD + Voting is unlikely to yield similar gains, as errors on “hard steps” are often systematic rather than stochastic, rendering simple majority voting ineffective.

$h=3$
Lookahead	Filtering	Aggregation	o4-mini ( $N$ )			GPT-5.2 ( $N$ )
			11	12	13	13	14	15
✓	✓	✓	96	56	84	100	100	100
✗	✓	✓	100	36	24	100	100	100
✓	✗	✓	96	52	80	100	100	92
✓	✓	✗	96	4	0	72	92	60

Table 2: Ablation study of LEAD components. Success rates (%) for o4-mini and GPT-5.2 on Checkers Jumping across varying horizons

N

. We evaluate the contribution of Lookahead rollouts, Consistency Filtering, and Overlapping Aggregation (with window size

h

). Results show that removing any component leads to performance degradation, and Aggregation is the most critical component for maintaining performance. Parameters

k=8,t=3

are held constant, and we set

v=N

to adapt to task complexity. Note that the “no-aggregation” results are identical across both

h

blocks as that parameter becomes irrelevant.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Error count histogram of o4-mini model for Tower of Hanoi. The error counts were estimated by sampling 25 independent solutions for each step.

Figure 7: Error count histogram of o4-mini model for Checkers Jumping. The error counts were estimated by sampling 50 independent solutions for each step.

Figure 8: Error count histogram of GPT-5.2 model for Checkers Jumping. The error counts were estimated by sampling 50 independent solutions for each step.

Figure 9: Error count histogram of Qwen model for Checkers Jumping. The error counts were estimated by sampling 50 independent solutions for each step.

Panel of Figure 10 — Figure 10: Distribution of error types for o4-mini model. Each plot shows the average number of each type errors per one solution. The main source of errors for Checkers Jumping is move execution, while for Tower of Hanoi - finding the correct move.

Figure 11: Atomic Decomposition with voting approaches the atomic competence barrier on Checkers Jumping, where the limiting factor is atomic move execution. The plot compares accuracy of full-step execution (selecting and executing a move) and isolated move selection or move execution as a function of problem size

n

. Results are shown for the o4-mini model using majority voting over 32 independently sampled solutions at each step.

	Lookahead Accuracy by Position
Step Idx	$+1$	$+2$	$+3$	$+4$	$+5$	$+6$	$+7$	$+8$
60	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0
61	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0
62	0.74	0.74	0.74	0.74	0.74	0.74	0.73	0.73
63	0.5	0.5	0.5	0.5	0.5	0.5	0.5	0.5
64	0.94	0.94	0.94	0.94	0.94	0.94	0.94	0.94

Appendix

Table 3: Lookahead prediction accuracy for GPT-5.2 on Checkers Jumping (

n=15

), shown for the hardest step (step index 63) and its neighboring steps. Columns correspond to the position within the Lookahead rollout. Bold entries indicate predictions for the hardest step obtained from different Lookahead starting points. Although the hardest step is not consistently correct at its native position, it is predicted correctly when inferred from earlier Lookahead rollouts, motivating the inclusion of recent Lookahead predictions in the voting procedure used by LEAD.

Panel of Figure 12 — Figure 12: Comparing Lookahead with Atomic Decomposition strategies for two models on the most difficult step for that model for Checkers Jumping puzzle (the puzzle complexity is $n=13$ for o4-mini and $n=15$ for GPT-5.2 model).

	Complexity $n$
Method	11	12	13
AD	3.15 $\pm$ 0.04	3.84 $\pm$ 0.05	4.60 $\pm$ 0.05
AD + voting	9.70 $\pm$ 0.19	12.70 $\pm$ 0.34	14.98 $\pm$ 0.31
LEAD	37.73 $\pm$ 0.99	55.96 $\pm$ 1.44	69.84 $\pm$ 1.42

Appendix

Table 4: Estimated tokens per solution (

\times 10^{5}

) for o4-mini

	Complexity $n$
Method	13	14	15	16	17
AD	3.18 $\pm$ 0.04	3.64 $\pm$ 0.03	4.40 $\pm$ 0.04	5.16 $\pm$ 0.04	5.91 $\pm$ 0.07
AD + voting	10.11 $\pm$ 0.20	11.07 $\pm$ 0.07	13.95 $\pm$ 0.29	15.86 $\pm$ 0.18	20.73 $\pm$ 0.51
LEAD	51.99 $\pm$ 1.55	53.63 $\pm$ 0.48	78.42 $\pm$ 2.80	88.83 $\pm$ 3.10	435.04 $\pm$ 1.23

Appendix

Table 5: Estimated tokens per solution (

\times 10^{5}

) for GPT-5.2 model

Long-Horizon LLM Reasoning

See all 17 papers

Learning to Refine Hidden States for Reliable LLM Reasoning
Jun 16, 2026Chia-Hsuan Hsu, Jui-Ming YaoRL for Language Model Reasoning Efficient Language Model Reasoning
Explore-Execute Chain: Towards an Efficient Structured Reasoning Paradigm
Sep 28, 2025Kaisen Yang, Tinghe Zhang, Rushi Shah +4LLM Reasoning Structured Reasoning
1Qizhi Institute · 2Dept. of Computer Science, Tsinghua University · College of AI, Tsinghua University +4
PoTRE: Test-Time Reasoning inspired by Cognitive Heterogeneity
Jul 22, 2026Anmol Kankariya, Sercan Ö. ArıkTest-Time Scaling Language Model Ensembles
Applied AI, Google Cloud

Jun 16, 2026J/K move · Enter open · S save

Learning to Refine Hidden States for Reliable LLM Reasoning

Chia-Hsuan Hsu, Jui-Ming Yao

RL for Language Model Reasoning Efficient Language Model Reasoning LLM Reliability Implicit Reasoning in Language Models Adaptive Computation Latent Reasoning

Open paper AskPDF arXiv

Large language models show strong reasoning ability, but their internal reasoning process can remain unstable in complex multi-step settings, where early hidden-state errors may propagate to incorrect predictions. We propose ReLAR, a reinforcement-guided latent refinement framework that iteratively updates hidden representations before decoding. ReLAR maintains a compact latent reasoning state and uses learned depth and action controllers to adaptively determine both the number and direction of refinement steps. The controllers are trained with a policy gradient objective based on step-wise likelihood improvement, enabling efficient input-dependent reasoning without explicit chain-of-thought generation. Experiments on medical, mathematical, multi-hop reasoning, and open-ended generation benchmarks show that ReLAR improves accuracy, generation quality, and reasoning stability with substantially lower inference overhead than explicit reasoning baselines.

Abstract

Long-Horizon LLM Reasoning

Explore similar work

Learning to Refine Hidden States for Reliable LLM Reasoning

Explore-Execute Chain: Towards an Efficient Structured Reasoning Paradigm

PoTRE: Test-Time Reasoning inspired by Cognitive Heterogeneity