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

Thank you reviewer EL6J for your constructive feedback! We are grateful that you found our work includes extensive experiments, careful articulation of the methods and clear and interesting results that lead to future interesting work.

We address your concerns below:

In problems with large depth, it may be hard for parallel sampling to yield sufficient variety and coverage. I also wonder, if this could be shown by varying the number of filled cells in Sudoku and seeing how that impacts the performance in a more gradient fashion (and similarly for CountDown).

• Great suggestion! We address this in our analysis by sorting Sudoku problems by search tree depth and evaluating the effectiveness of parallel sampling at each depth level (i.e., number of unfilled cells). Implemented what you suggested, in this figure, we observe that the performance of parallel sampling degrades as problem depth increases. As a reference baseline, backtracking (i.e., sequential search) performance remains stable even as depth increases. This supports your intuition that deeper problems are harder to solve via parallel sampling.

• We would have liked to conduct the same analysis for Countdown, but in our current setup, each Countdown game uses only 4 candidates, resulting in a fixed tree depth of 3. Extending this analysis would require retraining models on new Countdown with varying depth. We will consider incorporating this additional CountDown analysis in the camera-ready version! That said, the “deep Countdown” experiment we include (Appendix D) already demonstrates the same trend—highlighting tree depth as a key factor in the relative success of backtracking strategies.

I’m struck by the rate of unsolved CountDown boards (noted on line 122). Why is this the case? If the model is approximating DFS, will this make CountDown harder for models (even though you’ve sampled the ones that were solvable, it could be that the approximation is still more prone to being incorrect)

• We were also struck by how difficult Countdown is to solve, and we verified both the correctness of our implementation and the quality of the search strategy used to generate training traces. The DFS-based solver achieves only a 60% success rate because it uses a sum-based heuristic to rank node expansions and prune the search tree. While effective in many cases, this heuristic can occasionally prune the correct path, especially on harder boards.

• We explored alternative strategies—including different heuristics (e.g., multiplicative factor–based) and BFS—and selected the most effective among them (see Fig.8). While we cannot guarantee there is a brilliant search strategy for CountDown out there, we believe this situation reflects a broader reality in real-world reasoning tasks: crafting the optimal strategy is often non-trivial and rarely provable. The best we can do is often generating “reasonably” good solution traces.

• We also shared your concern about whether approximating DFS might make Countdown harder. In fact, in Section 4.3 (Fig. 4b), we address this concern by training on a mix of strategies designed to diversify the solution traces. While this mix-strategy model performs better than the pure DFS-trained model, it still underperforms the direct solution model—suggesting that the difficulty is not just due to approximating DFS, but also stems from intrinsic challenges in the task.

• Finally, we emphasize that the use of DFS allows for a sharp contrast between tasks: while DFS traces are less effective for Countdown, they enable superior performance in Sudoku, further highlighting the role of task structure in determining the utility of backtracking.

Thank you reviewer VtTK for your constructive feedback! We are grateful that you found our work exposes important limitations of backtracking that are often overlooked in literature. We also found your suggestion of making the results more general particularly helpful.

We address your concerns below:

It might be beneficial to consider other types of reasoning tasks beyond these two to show that the phenomenon is more general.

• We agree that making our claims more general will strengthen our paper! Combining comments from reviewer z9oL, we are currently extending our findings to more realistic LLM settings. We are actively working on reproducing our study in math problem-solving tasks. In this setup, we start from a model without backtracking capabilities and, mirroring our toy setting, train both a backtracking model and a direct solution model. We then evaluate their performance under equivalent test-time compute to assess whether our conclusions hold in a more realistic domain.

• We are also thinking about an additional synthetic task (details in the last response item)!

The reliance on DFS-based backtracking traces for training raises concerns. The model's underperformance may stem more from the quality of traces than from backtracking as a strategy per see.

• We agree that the backtracking model’s performance depends in part on the quality of its training traces. However, for many reasoning tasks—even relatively simple ones like Countdown—it is non-trivial to generate optimal solution traces without significant human effort. In practice, many real-world reasoning tasks face the same challenge: high-quality traces are difficult to define and scale.

• In Section 4.3 (Fig. 4b), we explicitly explore this concern through a mix-strategy variant for Countdown. We first carefully analyzed different search strategies (see Fig. 8), and then trained the model on a mix of these strategies to improve training data diversity. Despite these targeted efforts to improve trace quality, the backtracking model still underperforms the direct solution model. This suggests that the limitation is not solely due to trace quality, but reflects deeper, task-specific constraints on backtracking as a viable strategy. Importantly, in the case of Sudoku, models trained on DFS traces outperform the direct solution model, further supporting that the nature of the task plays a critical role.

The analysis on scaling effects is informative but somewhat shallow. For example, while larger backtracking models plateau in CountDown, the paper doesn’t deeply explore why scale fails to help in overcoming trace-induced biases.

• We agree that model scale alone does not overcome trace-induced biases—and this is expected under a supervised learning objective. Since the model is explicitly trained to imitate DFS-generated traces, there is no optimization signal encouraging it to deviate from the search strategy used to generate the training data. This reflects a limitation of SFT, not of scale itself.

• For Countdown, the model scales we work with (specifically, the larger ones) are sufficient to learn and reproduce the DFS strategy almost perfectly—effectively modeling the data generation process. Once this capacity threshold is reached, increasing scale provides no additional benefit, which explains the observed plateau. We will clarify this more explicitly in the camera-ready version.

I will raise the score if the authors could consider adding more tasks beyond these two tasks.

As a first step, we are extending our results to math tasks using general-purpose reasoning LLMs and expect to report these results in the coming days.

We focused on Countdown and Sudoku because they represent two extremes in reasoning complexity: Countdown is broad and shallow, while Sudoku is narrow and deep. We fully agree that exploring tasks that lie between these extremes would provide further insight.

• Deep-narrow Countdown (Appendix D): We have experimented with a variant of Countdown that increases search depth and constrains intermediate steps, pushing it toward a deeper, narrower structure
• N-Queens problem: A classic CSP problem sits between Countdown and Sudoku in both depth and complexity, offering a more balanced test case for backtracking. Game description: The goal is to place N queens on an N × N chessboard such that no two queens threaten each other. Solving the problem requires placing one queen per row, making it a sequential decision process with depth N. At each step, the model must choose a valid column position that avoids conflicts, resulting in moderate branching. This positions N-Queens between Countdown and Sudoku in terms of complexity—neither as shallow and wide as Countdown nor as deep and narrow as Sudoku.

While our immediate priority is adding math benchmarks, we aim to include N-Queens for the camera-ready version.

Thank you reviewer z9oL for your insightful feedback! We are glad that we were able to point out some interesting and fundamental research problems in test-time scaling and even more broadly search strategies in finding the answer in a large space. We found your concerns on not generalizing our findings to real LLMs particularly helpful.

We address your concerns below:

I would like to see some real tasks or real models on these tasks, to get more sense on how the takeaways of this paper could be transferred to LLM tasks and settings.

• We agree that extending our findings to more realistic LLM settings is an important direction. We are actively working on reproducing our study in math problem-solving tasks. In this setup, we start from a model without backtracking capabilities and, as in our toy setting, train both a backtracking model and a direct solution model. We then evaluate their performance under equivalent test-time compute to assess whether our conclusions hold in a more realistic domain.

The methodology part was a little vague to me.

• We will improve the clarity of Section 3 for the camera-ready version. Is there any part (definition, procedure, set-up) that you found particularly confusing?

What’s the search depth of these two problems? Is this the reason why they perform differently on two tasks? It would be good to show some statistics about tree breadth and depth, and more info about that.

• Search tree statistics for CountDown: We play a version of CountDown with N=4 candidate numbers. At each step we reduce one number by performing a math operation (illustrated in Fig. 2a).Therefore, the tree depth is N-1 = 3. The width (branching factor) is $\binom{N}{2} \times 4$, where N represents the number of candidates left. Concretely, the widths for each depth are: 24, 12 and 4. See further details in Appendix B1 Line 578 for detailed analysis.

• Search statistics for Sudoku: We play Sudoku boards that on average have 56 unfilled cells (or 81 - 56 = 26 filled cells). Thus the tree depth is on average 56. At each step, we pick the easiest cell to fill (one with fewest candidate numbers). The tree width is determined by the number of candidate numbers and on average the candidates are between 1 - 5.

• Comparing these two games CountDown has wide but shallow search trees while Sudoku has deep and narrow search trees. We will incorporate these details into the main text in the camera-ready version.

• Characteristics of the search tree is a key factor differentiating the two tasks. In Appendix D, we directly test this hypothesis by introducing a deeper variant of Countdown and a shallower variant of Sudoku. By making those game variants, we control search tree characteristics and show that it directly impacts the effectiveness of backtracking. In short, our experiments confirm both your intuition and ours.

  • For Sudoku, we included an addition analysis where we sort Sudoku problems by searching tree depth and evaluating the effectiveness of parallel sampling at each depth level. In this figure, we observe that the performance of parallel sampling degrades as problem depth increases. As a reference baseline, backtracking (i.e., sequential search) performance remains stable even as depth increases. This supports your intuition that deeper problems are harder to solve via parallel sampling.

I am a little confused about non-backtracking vs direct solution vs parallel sampling. Could you provide more info about what’s the parallel search algorithm here. I think some algorithm tables would be useful to differentiate algorithms here.

• Thank you for pointing this out, and we apologize for the mix of terminology. To clarify: the non-backtracking model and the direct solution model refer to the same thing—we will standardize the terminology to “direct solution model” in the camera-ready version. This direct solution model uses parallel sampling at test time, specifically via a Best-of-N strategy. We agree that a table summarizing the different algorithms would improve clarity and will include one in the revision.

Thank you reviewer GNL9 for your comments and feedback! We are very glad that you found our work really important and contributes greatly to our progress as a field.

We address your concerns below:

Their experiments focus mostly on the SFT setting where the model is trained on a bunch of synthetically generated backtracking trajectories. This differs substantially from how general reasoning LLMs like Deepseek-R1 zero were trained.

• Many papers claim that backtracking is key for enhancing a model's ability for math problem solving [1, 2, 3]. However, many recent follow-up studies [4, 5, 6, 7] show that the only way to teach backtracking behaviors is through pretraining and SFT. In other words, if the backtracking behavior is not present in the base model pre-RL, it cannot emerge through RL. While DeepSeek-R1 zero claims anecdotal evidence regarding the importance of backtracking, we do not know what was in the pretraining data for these models and it is very likely that pretraining data already contains synthetically generated “backtracking” traces.

• The focus of this work is to understand the impact of backtrackinging on solving reasoning tasks in a highly controlled setting. To that end, our training setup mirrors the typical LLM pipeline: a supervised phase followed by reinforcement learning. Specifically, we first train models with supervised learning to solve Countdown and Sudoku with training data containing solution traces (Section 4). This step is analogous to supervised pretraining in LLMs. We then apply RL to these pretrained models (Section 5), reflecting the post-training RL phase used in models like DeepSeek-R1. While our domain and scale are simplified, the training setup is intentionally aligned with that of general reasoning LLMs.

This model instead learns most of their backtracking behaviors from the RL phase, as there is no SFT phase at all for this model. As a result, it is possible that the findings do not transfer to these more general models.

• In general, it is not very lear how to define backtracking of general tasks. First, the anecdotal DeepSeek-R1’s backtracking traces [1, 2, 3] are mostly adding a “wait” token and backtracking to the beginning of reasoning steps. While real backtracking consists of checking the wrong step and correcting it. In addition, we do not know how much of traces with backtracking behaviors are already present in their pretraining data.

• Using synthetic tasks CountDown and Sudoku allows us to first rigorously define backtracking behaviors, and study in a controlled setting. We are the first to study the efficacy of backtracking in the context of test-time compute scaling.

• To ensure our work translates to general reasoning LLMs, we are working on finetuning LLMs on math tasks (MATH/GSM8K) into a backtracking and a direct-solution model. We will then repeat the same analysis as we have done to CountDown and Sudoku. We will report results in the coming days!

They conduct some ablations of this in 4.3, and their results with the mix strategy model suggest that indeed the data is important here.

• We agree that data is super important and a choice of suboptimal data can critically degrade the performance. However, we argue that with “reasonable” data with backtracking or direct solution strategy, the nature of tasks determines the performance. We provide two types of evidences on why tasks is important:

• Evidence 1: For both Sudoku and Countdown, we use the same data generation strategy—DFS-based backtracking traces—as detailed in Sections 3.1.2 and 3.2.2. Despite this controlled setup, the two tasks yield different outcomes, suggesting that task structure plays a critical role in determining the effectiveness of backtracking. While Section 4.3 shows that mixing strategies can improve performance, the backtracking model still underperforms compared to the direct solution model. This supports our claim that while data matters, the task itself remains a key factor.

• Evidence 2: As additional evidence, Appendix D introduces variations of both tasks: a version of Sudoku with decreased search tree depth and a version of Countdown with increased depth. By manipulating tree depth alone, we directly control the effectiveness of backtracking. These results further support that the observed behaviors are not solely due to data construction, but are fundamentally linked to the structure of the task.

In a few places I felt that the writing was overly verbose, such as in Sections 3.1 and 3.2.

• Thank you for the feedback! We agree that for readers who are experts in LLM reasoning, the background in Sections 3.1 and 3.2 may feel overly detailed. Our goal was to ensure accessibility for readers less familiar with Countdown and Sudoku. That said, we will revise these sections in the camera-ready version to make the writing more succinct while retaining the necessary context.