# To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning

arXiv: https://arxiv.org/abs/2504.07052 · HTML: https://mlsanity.com/paper/2504.07052/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 39 of its 46 references that are in the map.
- First posted on arXiv 9 Apr 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 39)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [Training Language Models to Self-Correct via Reinforcement Learning](https://mlsanity.com/paper/2409.12917/) (2024)
- [Self-critiquing models for assisting human evaluators](https://mlsanity.com/paper/2206.05802/) (2022)
- [Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs](https://mlsanity.com/paper/2503.01307/) (2025)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Data](https://mlsanity.com/paper/2405.14333/) (2024)
- [Large Language Model Guided Tree-of-Thought](https://mlsanity.com/paper/2305.08291/) (2023)
- [REFINER: Reasoning Feedback on Intermediate Representations](https://mlsanity.com/paper/2304.01904/) (2023)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [VinePPO: Refining Credit Assignment in RL Training of LLMs](https://mlsanity.com/paper/2410.01679/) (2024)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [Recursive Introspection: Teaching Language Model Agents How to Self-Improve](https://mlsanity.com/paper/2407.18219/) (2024)
- [Platypus: Quick, Cheap, and Powerful Refinement of LLMs](https://mlsanity.com/paper/2308.07317/) (2023)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Retroformer: Retrospective Large Language Agents with Policy Gradient Optimization](https://mlsanity.com/paper/2308.02151/) (2023)
- [Critique-out-Loud Reward Models](https://mlsanity.com/paper/2408.11791/) (2024)
- [RL4F: Generating Natural Language Feedback with Reinforcement Learning for Repairing Model Outputs](https://mlsanity.com/paper/2305.08844/) (2023)
- [GLoRe: When, Where, and How to Improve LLM Reasoning via Global and Local Refinements](https://mlsanity.com/paper/2402.10963/) (2024)

## Built on by (most cited first, 24 of 24)

- [Position: Stop Anthropomorphizing Intermediate Tokens as Reasoning/Thinking Traces!](https://mlsanity.com/paper/2504.09762/) (2025)
- [Scaling Offline RL via Efficient and Expressive Shortcut Models](https://mlsanity.com/paper/2505.22866/) (2025)
- [Cognitive Foundations for Reasoning and Their Manifestation in LLMs](https://mlsanity.com/paper/2511.16660/) (2025)
- [The Geometry of Self-Verification in a Task-Specific Reasoning Model](https://mlsanity.com/paper/2504.14379/) (2025)
- [How Much Backtracking is Enough? Exploring the Interplay of SFT and RL in Enhancing LLM Reasoning](https://mlsanity.com/paper/2505.24273/) (2025)
- [RoT: Enhancing Table Reasoning with Iterative Row-Wise Traversals](https://mlsanity.com/paper/2505.15110/) (2025)
- [Decomposing Elements of Problem Solving: What "Math" Does RL Teach?](https://mlsanity.com/paper/2505.22756/) (2025)
- [Trust but Verify! A Survey on Verification Design for Test-time Scaling](https://mlsanity.com/paper/2508.16665/) (2025)
- [MedReflect: Teaching Medical LLMs to Self-Improve via Reflective Correction](https://mlsanity.com/paper/2510.03687/) (2025)
- [Improving Sampling for Masked Diffusion Models via Information Gain](https://mlsanity.com/paper/2602.18176/) (2026)
- [Towards Stable and Effective Reinforcement Learning for Mixture-of-Experts](https://mlsanity.com/paper/2510.23027/) (2025)
- [RAST: Reasoning Activation in LLMs via Small-model Transfer](https://mlsanity.com/paper/2506.15710/) (2025)
- [Measuring Weak-to-Strong Legibility of Reasoning Models](https://mlsanity.com/paper/2603.20508/) (2026)
- [From Reasoning Traces to Reusable Modules: Understanding Compositional Generalization in Language Model Reasoning](https://mlsanity.com/paper/2606.18089/) (2026)
- [More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD)](https://mlsanity.com/paper/2601.21522/) (2026)
- [DOS: Dependency-Oriented Sampler for Masked Diffusion Language Models](https://mlsanity.com/paper/2603.15340/) (2026)
- [Conformal Certification of Reasoning Trace Prefixes](https://mlsanity.com/paper/2605.30085/) (2026)
- [Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently](https://mlsanity.com/paper/2606.22938/) (2026)
- [Asking the Right Questions: Improving Reasoning with Generated Stepping Stones](https://mlsanity.com/paper/2602.19069/) (2026)
- [Mind the Gap Between Spatial Reasoning and Acting! Step-by-Step Evaluation of Agents With Spatial-Gym](https://mlsanity.com/paper/2604.09338/) (2026)
- [Learning the ARTS of Search for Automated Discovery](https://mlsanity.com/paper/2606.21891/) (2026)
- [Search, Fail, Recover: A Training Framework for Correction-Aware Reasoning](https://mlsanity.com/paper/2607.07492/) (2026)
- [Metacognitive Behavioral Tuning of Large Language Models for Multi-Hop Question Answering](https://mlsanity.com/paper/2602.22508/) (2026)
- [A Taxonomy of Cognitive Capability Gaps in Generative and Agentic AI](https://mlsanity.com/paper/2608.02553/) (2026)

## Abstract (arXiv)

Recent advancements in large language models (LLMs) have significantly improved their reasoning abilities, particularly through techniques involving search and backtracking. Backtracking naturally scales test-time compute by enabling sequential, linearized exploration via long chain-of-thought (CoT) generation. However, this is not the only strategy for scaling test time-compute: parallel sampling with best-of-N selection provides an alternative that generates diverse solutions simultaneously. Despite the growing adoption of sequential search, its advantages over parallel sampling-especially under a fixed compute budget-remain poorly understood. In this paper, we systematically compare these two approaches on two challenging reasoning tasks: CountDown and Sudoku. Surprisingly, we find that sequential search underperforms parallel sampling on CountDown but outperforms it on Sudoku, suggesting that backtracking is not universally beneficial. We identify two factors that can cause backtracking to degrade performance: (1) training on fixed search traces can lock models intro suboptimal strategies, and (2) explicit CoT supervision can discourage implicit (non verbalized) reasoning. Extending our analysis to reinforcement learning (RL), we show that models with backtracking capabilities benefit significantly from RL fine-tuning, while models without backtracking see limited, mixed gains. Together, these findings challenge the assumption that backtracking universally enhances LLM reasoning, instead revealing a complex interaction between task structure, training data, model scale, and learning paradigm.