To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning
Authors: Tian Qin
David Alvarez-Melis
Samy Jelassi
Eran Malach
Venue: COLM 2025 (2025)
Keywords: LLM Reasoning
Backtracking
Test-time Computate
TL;DR: A comparative study of backtracking versus parallel search in LLMs, revealing nuanced trade-offs: backtracking can harm reasoning due to constrained search strategies and verbosity, but is particularly suitable for RL.

Abstract: 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.

Published as a conference paper at COLM 2025
To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning
Tian Qin * Harvard University
David Alvarez-Melist
Harvard University, Kempner Institute, MSR
Samy Jelassi
Eran Malachtt
Harvard University, Kempner Institute
Harvard University, Kempner Institute
Abstract
Recent advancements in large language models (LLMs) have significantly improved their reasoning abilities, particularly through techniques in- volving 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-11 selection provides an alternative that generates diverse solutions simultaneously. Despite the growing adoption of sequential search, its advantages over parallel sampling eesiiingespecialllly under fixed compute budget budget-remain poorly un- derstood. In this paper, we systematically compare these two approaches on two challenging reasoning tasks: CountDown and Sudoku. Surpris- ingly, we find that sequential search underperforms parallel sampling on CountDown but outperforms it on Sudoku, suggesting that backtracking not universally beneficial. We identify two factors that can cause backtrack- ing 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 complex interaction between task structure, training data, model scale, and learning paradigm.
Introduction
Recent studies (Kumar al., 2024; Havrilla et al., 2024) propose teaching LLMs to cor- rect mistakes through backtracking, enabling exploration of alternative solutions. Despite growing popularity (DeepSeek-Al) et al., 2025; Muennighoff et al., 2025), it remains unclear whether correcting errors post-hoc via backtracking is ultimately more compute-efficient at test time than directly learning the correct solution. Solving strategic games such as CountDown and Sudoku requires extensive exploration of different solution paths, making them ideal for analyzing the computational trade-offs sequential versus parallel search. In this work, we use these two games to conduct a controlled investigation to determine whether backtracking is an effective way to scale test-time compute.
There are two primary strategies scale LLMs' test-time compute: sequential autoregressive search (explicit backtracking within a chain-of-thought) and parallel sampling (generating multiple independent solutions and selecting the best with best-of-r). While sequential search allows the model to refine reasoning by learning from past mistakes, it comes at a cost: due to the attention mechanism, the FLOPs required to generate CoT grow quadratically
"Correspondence to tqinég. hww.ara.. $ Equal senior contributions. *Currently at Apple.
1

---

Published as a conference paper at COLM 2025
(A)
Countdown
Sudoku
(B) CountDown GRPO
80
60
Direct Solution Model (Scalin g wr best of
Direct Salution
Backtrack (Bofors)
(wibest TV
Afterh
Problem Solved
45
Backtrack Model
(Scaling m/ EoT)
Problem Salved
60
Backtrack
(wl CoTI
Problem Solved
6D
Alter GXTO
Drect sn (Betora)
40
40
30
20
20
15
10:0
FLOPs 10 10a0
10
10:0
10
FLOPs
FLOPs
Figure 1: Backtracking performance varies significantly with task type and the application of post-training reinforcement learning. (A) Training backtracking and direct solution models on CountDown and Sudoku reveals task-dependent performance: under equal test-time compute, backtracking (sequential search) underperforms direct solution with best-of-n generation (parallel search) on CountDown, but outperforms on Sudoku. (B) Fine-tuning with GRPO consistently improves backtracking model performance across compute budgets, but has mixed effects on the direct solution model.
with sequence length. Even when generating the same number of tokens, sequential search incurs more FLOPs than parallel sampling. To compare these two strategies, we train (i) backtracking models that learn from explicit search traces and use sequential search to solve hard problems, and (ii) direct solution (i.e., no backtracking) models that learn solely from correct solutions, using parallel search at test time. Equating test-time compute, we observe contrasting results (Fig. A): in CountDown, the backtracking model consistently underperforms, whereas in Sudoku, it consistently outperforms the direct solution model.
Through controlled experiments, identify two reasons teaching backtracking can inad- vertently degrade performance. First, explicit backtracking reasoning traces bias models toward prescribed search strategies, limiting exploration of potentially superior alternatives. In CountDown, the backtracking model closely mimics training search paths, while the direct solution model independently discovers more efficient strategies (Section 4.2). Second, detailed backtracking traces encourage verbosity (producing lengthy yet ineffective reason- ing chains), while discouraging internal "thinking" (implicit reasoning without outputting CoT, Section 4.3). Beyond these factors, we demonstrate that model size and task-specific characteristics also impact the effectiveness of backtracking (Section 5.1). Crucially, we show that our contrastive observation between Sudoku and Countdown generalizes to real-world tasks: such as math and science problem solving. We show that backtracking is not always the most effective way to scale test-time compute (Appendix A) for general reasoning models.
Extending beyond supervised learning, we evaluate reinforcement learning (RL) with Group Relative Policy Optimization (GRPO) (Shao et al., 2024), uncovering novel interactions be- tween backtracking capabilities and RL. We show that the backtracking model discovers new, effective search strategies through RL, achieving substantial performance im improvements. Conversely, the direct solution model improves one-shot accuracy but loses effectiveness in parallel search, revealing clear trade-off (Fig. B). This finding shifts our understanding of how backtracking influences model's potential to improve under RL, highlighting the unique advantage of teaching backtracking for long-term reasoning capabilities.
Our controlled study on two strategic games provides a nuanced understanding of when backtracking effectively scales test-time compute. Our main contributions are:
We use CountDown and Sudoku as controlled testbeds to examine whether backtrack-
ing enables efficient test-time scaling. Under a fixed compute budget, backtracking outperforms parallel search in Sudoku but underperforms in CountDown (Fig. 1 A).
We identify two key factors affecting backtracking efficacy: (1) Prescribed search bias: Training on detailed backtracking traces can unintentionally constrain models to subopti-
2

---

Published as a conference paper at COLM 2025
(a)
(b)
Countdown
Sudoku
Iapat:
Target: 36
2
4.x 10 40
10-6-8
4
Loft: (40,
13
4
Left [4.0]
Lett: 13
2
1x
4 6 10
13 3
[24]
[30]
(c)
Backtracking model performs sequential search and backtrack:
1--9-4 Loth 18.0
1+6-10
Lett: pa.15
Loft
1.13
Lall: 194]
haderrsiing
Laft: (1..
Lot
Laft: 24]
Direct solution model performs parallel search through temperature sampling:
1S 10
Let: 13.
Left
best-of-n
12 4-0
[8.0.33]
Figure 2: Backtracking and direct solution for two different strategic games. Panel (a, b): Example the search tree for CountDown and Sudoku. Solving both games require extensive search in the solution space. Panel (c): The backtracking model is trained on the search traces generated by Depth-Finst-Search (DFS) algorithm. At test time, the model performs sequential search. The direct solution model trained on the correct solution only. At test time, the model performs parallel search through temperature sampling and takes best-of-n.
mal search strategies. (2) Excessive verbosity: Explicit backtracking traces encourage models to produce lengthy reasoning chains without improving reasoning ability.
We demonstrate that reinforcement learning (GRPO) consistently enhances backtrack- ing models by enabling discovery novel solutions, whereas direct solution models experience mixed outcomes (Fig. 1 B).
Related Work
See Appendix B for an extensive review on related work.
Scaling test-time compute. Prior work has explored scaling language model performance at test time through parallel or sequential search strategies. Parallel methods rely on independent sampling and selection via heuristics reward models (Brown et al., 2024; Irvine et al., 2023; Levi, 2024; Xin et al., 2024), while sequential methods refine reasoning step by step using earlier outputs (Hou al., 2025; Lee al., 2025). Tree-based methods such as MCTS bridge the two and often incorporate process-level reward models to guide reasoning (Wu et al., 2024; Lightman et al., 2023). Our work contributes to this area by comparing sequential (backtracking) and parallel search under fixed compute budgets.
Self-correction and backtracking, Language models can be trained to self-correct through fine-tuning revision data, synthetic augmentations, reward-based learning (Saunders et al., 2022; Qu et al., 2024; Welleck et al., 2022). Some approaches also introduce explicit search separate correction modules to guide revision (Yao et al., 2023b; Havrilla et al.,

---

Published as a conference paper at COLM 2025
2024). We build on this line of work by studying backtracking implicit form of self-correction, analyzing when learning to backtrack helps or hinders reasoning.
Reinforcement learning for LLM reasoning. Reinforcement learning has shown promise in enabling language models to autonomously discover reasoning strategies, including through simplified algorithms like GRPO (Shao et al., 2024; DeepSeek-AI et al., 2025). While prior work has demonstrated strong results, it remains unclear which model properties enable successful RL-based reasoning (Zelikman et al., 2022; Kazemnejad et al., 2024). Our study redsess this gap by comparing how backtracking and no backtracking models respond to RL fine-tuning, revealing asymmetric benefits.
3
Two strategic games: CountDown and Sudoku
3.1
CountDown
3.1.1
Game setup
The Game of CountDown has been frequently used as a testbed to study and evaluate LLM reasoning (Gandhi et al., 2024; 2025; Yao et al., 2023a). In CountDown game, the player is given a set of candidate numbers and a target number (restricted to integers). The goal is to reach the target by applying sequence of arithmetic operations- adautiion-adiiionn, subtraction, multiplication, or division-use using the candidate numbers. Each number must be used exactly once, and intermediate results can be reused in subsequent operations.
To algorithmically solve CountDown, we can represent the problem as a search tree (Fig. 2a). Each node in the search tree corresponds to state defined by the current set of available numbers. At each step, the algorithm selects a pair of numbers from the set and applies one of the four operations, replacing the pair with the resulting value to create new state. This process continues recursively until the target number is reached (correct leaf node) or all combinations are exhausted (wrong leaf node). In this work, we play the CountDown with four candidate numbers, and for each game, there are 1,152 possible search paths.
3.1.2 Data generation
We generate backtracking traces with Depth First Search (DFS) with sum-heuristic (Gandhi et al. (2024), further details in Appendix C.1). We generate a dataset of 500,000 CountDown questions, and the DFS search correctly solves 57% of the questions. The backtracking trace is a serialized version of DFS, listing all the tree nodes visited in the order of DFS traversal. To construct the direct solution training data, we prune the backtracking traces to keep only the correct solution path. With the pruning approach, we remove the exploratory parts of the trace while preserving the answer format and scaffolding used in the backtracking model, to ensure fair comparison. We also ensure that the direct solution model does not see more solved CountDown games, we include only the 285,000 questions (i.e., 500,000 x 0.57) that DFS successfully solves. We provide examples of both training data in Appendix H.
3.2 Sudoku
3.2.1 Game setup
Sudoku is another prototypical strategic game used to study reasoning and search in LLMs (Yao et al., 2023a; Long, 2023). In this work, we focus on hard 9 x 9 Sudoku boards, where only about 20 of the 81 cells are pre-filled, making the search space substantially larger (see Appendix C.1 for a description of Sudoku rules). To algorithmically solve Sudoku, we represent the problem as a search tree (Fig. 2b). Each node corresponds to a partial board state, where some cells have been filled. At each step, the algorithm selects an unfilled cell and fills with candidate digit that satisfies Sudoku constraints in the current state. Each valid assignment creates new child node representing the updated board. The process continues recursively until a complete, valid solution is reached (correct leaf node) or no valid moves remain (wrong leaf node). The depth of the tree corresponds to the number of empty cells, and the branching factor at each node depends on the number of unfilled cells as well how many digits are valid for each unfilled cell.
4

---

Published as a conference paper at COLM 2025
DFS Bxckrodkig Tace Backtracingg Model
Numbar of Misakess
40
Direct Silutinn Model
DFS Bacitoocing Face
Smmledty (lscardd Inddad
Direct Solucion Mode
Backnacking Mudal
0.30
20
0.15
0.00
100
15.0
200
50 2000
150
20 30
Tost Sam pie Indox
Test Sample le Indox
Number of Mistakes
Figure 3: Backtracking and direct solution models implement different search strategies for CountDown. For test questions that model solves correctly, we measure the number of mistakes made (i.e., wrong terminal nodes visited) before finding the correct solution. We sort the test questions by number of mistakes made by DFS. Left: Trained on DFS traces, the number of mistakes made by the backtracking model correlates with the DFS. Middle: In contrast, the direct solution model solves a lot more problems with significantly fewer mis- takes compared to DFS. Right: For a given number of mistakes made, we examine whether two models solve the same set of question as DFS. Direct solution model implements a search strategy significantly different from DFS.
3.2.2 Data generation
We follow the same procedure as CountDown to generate training data for both the back- tracking and direct solution models. We use DFS-based search algorithm, in combination with a Sudoku solver that applies seven common human strategies (e.g., naked singles, hidden pairs and etc, Papadimas. (2023) ) to eliminate candidates for unfilled cells. At each node, we use the 7 strategies to eliminate candidates for unfilled cells, and then DFS chooses an unfilled cell, makes guess and continues solving recursively. This process continues until the board is either solved or reaches dead-end (i.e., an invalid state with no legal moves). We use dataset of 3M Sudoku puzzles from (Radcliffe, 2020), and the combined DFS-solver approach successfully solves 98% of them. Since DFS successfully solves nearly all puzzles, we train both models on 2.8M examples and reserve the last 200K for validation and testing. We provide further details on Sudoku training data generation in Appendix C.1 and data examples in Appendix H.
3.3 Model and training
We use Qwen2.5-style model architectures (Yang et al., 2024) with RoPE positional encoding (Su et al., 2021) and Group Query Attention (GQA) (Ainslie et al., 2023). To maximize parameter efficiency, we design custom tokenizers for both games, significantly reducing the size of the language modeling head. This allows to train smaller models than prior work (Gandhi et al., 2024; Shah et al., 2024) while maintaining comparable performance on both tasks. For CountDown, 4096 tokens; for Sudoku, we use 38M model with the same context length. See Appendix C.3 for model architecture and an exhaustive list of training hyperparameters. We train all models until validation loss converges (see Appendix G.3).
use a 17M parameter model with context length of
4 Empirical trade-offs of backtracking
We first demonstrate that backtracking models do not universally outperform the direct solution models (Section 4.1) because backtracking models are restricted to learn way of search (Section 4.2). We then identify two factors (Sections 4.3) showing how we might improve test- test-time scaling for backtracking models.
a prescribed
4.1 Backtracking is not always beneficial
Evaluation metrics. We evaluate model performances using solving accuracy on 200 unseen problems with binary scores (either correct or incorrect, no partial credits, see appendix C.1). We use FLOPs to compare inference costs (see Appendix D for FLOPs computation). For the backtracking model, we allow models to autoregressively generate and measure how many problems the model finds the correct solution at various CoT lengths (ranging from 1024 to 4096 tokens). For the direct solution model, we generate
5

---

Published as a conference paper at COLM 2025
solutions in parallel through temperature sampling at T = 0.7, and examine whether the model has found the correct solution within и attempts (i.e., best-of-n). Best-of-n is a suitable choice in those two games, a case where solving the task is hard but verification is trivial. In general, our analysis applies to tasks where verification can be easily done with external verifier at test-time. This is definitely not always the case, and we leave the study of problems where test-time verification is not as easy to future work. In those tasks, one might need to consider majority voting or other strategies. See Appendix E for further discussions.
Results. In Fig. A, we observe distinct scaling behaviors for the two models. For both games, the direct solution model's test accuracy scales linearly with increased test-time com- pute (measured on a logarithmic scale). This scaling behavior indicates that through parallel sampling, the backtracking model generates diverse solutions that search through different solution paths. Conversely, the backtracking model exhibits sub-linear scaling: Longer solution traces disproportionately yield smaller accuracy improvements. We attribute the sub-linear scaling to two causes. First, as reasoning chains become longer, the backtracking model might struggle to effectively track visited states and efficiently search through the solution space. Second, when models perform sequential search, the computation cost grows quadratically with CoT length (due to the attention mechanism, see Appendix D), and this further makes backtracking model less effective for scaling up test time compute. Overall, for CountDown, the direct solution model consistently outperforms its backtrack- ing counterpart. However, this trend is reversed in Sudoku, where the backtracking model consistently achieves higher accuracy.
4.2 Backtracking model learns both the good and the bad
When teaching child to correct math mistakes, the child understands that the goal is the correct answer-not making and then fixing errors. Humans have meta-cognitive awareness that models lack. Models trained via next-token prediction simply imitate the traces they see, including making the mistake before fixing it. In CountDown, this poses key limitation: the backtracking model learns to follow the specific search paths seen in training. While some tasks-like shortest path finding-harr have optimal strategies we can supervise directly (e.g., Dijkstra's 's algorithm), most reasoning tasks, including CountDown, lack such guarantees. As a result, the model may be constrained by the inefficiencies in the backtracking data. In contrast, the direct solution model, trained only on correct answers, is free to discover more efficient strategies. In our subsequent analysis, we concretely show how the direct solution model successfully bypasses many inefficient search and backtracking steps learned by the backtracking model.
4.2.1 Backtracking model finds the solution with fewer mistakes
Measuring number of mistakes. We compare the number of mistakes made by: (1) DFS (used to generate backtracking data), (2) the backtracking model, and (3) the direct solution model. For DFS and the backtracking model, mistakes are counted as the number of incorrect terminal nodes explored before finding the correct solution. For the direct solution model, mistakes correspond to how many parallel samples (n in best-of-n) are needed.
Comparing search strategies. We sort the 200 test problems based on mistakes made by DFS and plot mistakes for both models. Fig. 3 left compares DFS search and backtracking model. The number mistakes made by the backtracking model is correlated with the DFS backtracking trace. This observation is not surprising given that the backtracking model is trained on these traces. However, this result is interesting when we compare against the direct solution model (Fig. 3 middle). The direct solution model solves most problems within fewer than 10 attempts--fe far fewer compared to DFS or the backtracking model. Fig. 3 right quantifies these observations. Specifically, for fixed mistake budget, we use Jaccard Index to measure whether the model solves a similar set of problems as DES solves. The backtracking model closely mirrors DFS search (high set similarity), whereas the direct solution model diverges significantly (low set similarity). Together with superior performance of the direct solution model, we conclude that the direct solution model learns more efficient search strategies, avoiding unnecessary explorations of wrong paths.
Mistaaes are counted only for problems solved correctly by the model.

---

Published as a conference paper at COLM 2025
(a)
search path
(b)
70
Baskireck
DPS Trace (Dats Bound)
Direct Soluion
60
Mix Backtracarvariatton 11
Thni-Backtr wra.ttttattteetiiiinnn
60
Unseen Problems
40
Backtrack
30
Think baakkkbbctrckk (Variation 2)
20
10
Direct solution
model searches internally and realizes that the solution is not in this subtree
10aa
104
FLOPs
Figure 4: Two different variations to improve backtracking model. (a). We hypothesize that the backtracking model can think one step ahead without sacrificing its ability to search. Therefore, data variations that improve the backtracking model. Mixed-backtrack model trained on diverse set of search strategies. Think-backtracking model trained shortened DFS trace.
shorten the search trace by skipping the last search step. (b). Two
4.3 Two ways improve backtracking model
Training on diverse set of search strategies. Our analysis suggests a clear direction for improving the backtracking model: using better search strategies to improve backtracking traces. Beyond DFS, we explored alternatives including Breadth-First Search (BFS) and various heuristic methods (see Appendix G.1). Despite these efforts, no single search strategy significantly outperformed DFS. Inspired by Gandhi et al. (2024), we trained variant of the backtracking moxdel-mix-backrree model-usio -usiig a diverse mixture of BFS and DFS strategies (32 in total), aiming to help the model discover more optimal search patterns.
Backtracking model thinks less and talks more. Apart from learning suboptimal search strategies, another inefficiency in the backtracking model is caused by the model learns to be excessively verbose. Specifically, by requiring the model to explicitly output every step of the DFS, we may prevent it from internalizing part of the reasoning process. Concretely, we hypothesize that for CountDown, the model can internally plan least one step ahead, allowing it to shorten its explicit reasoning trace without losing its ability to perform DFS. To test hypothesis, we train variation the backk-backtrack model-on on shortened DFS traces, skipping one intermediate step (Fig. 4, A).
Mix-strategy results. Fig. 4 (B) compares this mixed-strategy model against the original backtracking and direct solution models. We also include a training data upper bound, representing perfect execution of the mixed search strategies. The mixed-strategy model improves the original backtracking model and closely approaches its training- upper bound. However, even with deliberate attempts to optimize search strategies, sur- passing the performance of the direct solution model remains challenging. This experiment underscores the inherent difficulty in identifying superior handcrafted search traces.
Think-backtrack results. Fig. 4 (B) also compares the performance of the think-backtrack model. By encouraging the model to internalize parts of the reasoning process, the think- backtrack model achieves performances comparable to the direct solution model. This result suggests that models with backtracking ability might produce long but ineffective CoT. By training the model to avoid making the mistakes at the first place, we reduce model verbosity without sacrificing its search capability, and in turn improving fest-time-compute scaling. As an additional evidence, in Appendix G.2 we show that the think-backtrack model solves superset of test problems solved by the original backtrack model.
7

---

Published as a conference paper at COLM 2025
CountDown
80
Unseen Problems Solved (9)
(A) Backtracking Models
Direct Solution Backtrack (%6
(C) Performance Gap Between Models
60
Accuracy Gap
17M
80
38M
(B) Direct Solution Models
60
40
20
10
10a
FLOPs
FLOPs
Sudoku
(D) Backtracking Models
Solution - Backtrack (%)
(F) Performance Gap Between Models
Unseen Problems Solved (%)
50
25
Direct Accuracy Gap
17M
-15
38M
75
(E) Direct Solution Models
144M
50
25
10"
1030
10
10
10
10
FLOPs
FLOPs
Figure 5: Different scaling behaviors for backtracking versus direct solution model. CountDown (A). Backtracking model performance does not improve as we scale up model size. (B), The direct solution model improves (C). Direct solution model consistently outper- forms backtracking model. Sudoku (D, E). Both models' performances improve as we scale up model size. (F). Direct solution model consistently underperforms backtracking model.
Model size and tree depth impact the efficacy of backtracking
While we've shown that backtracking might lead to ineffective test-time scaling, other factors also shape its effectiveness. In Section 5.1, show that backtracking and direct solution models scale differently with model sizes. To explain the contrasting outcomes (Fig. 1 A) between CountDown and Sudoku, in Appendix F, we show that task differ- ences- cacnss-prttcullrlly search tree depth-play a key role: deeper tasks like Sudoku benefit more from backtracking.
5.1 Dependence model size
We now investigate how model size impacts the performance of backtracking and direct solution models. We evaluate four model scales- 17M, 38M, and 144M-by propor- tionally increasing the number of attention heads, embedding dimensions, and number of attention layers. Detailed model configurations can be found in Appendix C.2.
CountDown. Scaling up model size improves the performance of the direct solution model (Fig. 5 B) across all test-time-comptte budgets. When trained exclusively on correct solutions, larger models can independently discover highly effective search strategies. In contrast, the backtracking model shows no improvements with increased model sizes (Fig. A). The lack of improvement from model scaling can be explained by training data: The performance of backtracking model is constrained by the quality of the backtracking traces used for training. As previously seen in Fig. 4 (right), the 17M backtracking model is already approaching the performance ceiling that is set by the training data. Training larger models the same backtracking data would not lead to further performance improvements. Due
8

---

Published as a conference paper at COLM 2025
to different scaling behaviors between backtracking and direct solution models, the gap in performances between two types of models widens with increasing model sizes (Fig. 5).
Sudoku. Similar to CountDown, the performances direct solution models improve with increased model sizes (Fig. 5 E). Unlike CountDown, however, the backtracking model also significantly benefits from scaling (Fig. 5 D). This difference can again be explained by exam- ining the backtracking training data. Sudoku inherently more complex than CountDown. The DFS backtracking traces successfully solve 97% of test moards--far exceeding the current performance of all four tested model sizes. Because the backtracking model for Sudoku has not yet reached training data performance ceiling, increased model capacity leads to im- proved results. On the other hand, due the complexity and large search space of the game, the backtracking models' performance gains start to diminish as the search traces become longer. As a result, the backtracking model consistently outperforms the direct solution model across scales, but the advantages diminishes at larger compute budgets (Fig. 5 E).
6 GRPO: Learning beyond the imitation game
So far, we have shown that under supervised learning, backtracking is not always optimal for scaling test-time compute. We now explore how further training both backtracking and direct solution models with reinforcement learning leads to qualitatively different outcomes.
6.1 Continue training models with GRPO
Recently, RL has become popular approach to further enhance LLMs performance on challenging benchmarks such as MATH (Hendrycks et al., 2021) and AIME (AIME, 2024). Here, we study the effects of RL in a controlled setting, focusing on how it impacts model's backtracking behaviors (sequential search) and as well as model's parallel search capability (sampling with best-of-H).. We take the CountDown backtracking and direct solution models, which have been trained to convergence under the supervised learning objective (see Appendix G.3 for training curves). We then continue training each model using GRPO (Shao et al., 2024), following verl's (Sheng et al., 2024) implementation. We perform GRPO on the same training data used for the supervised learning. As before, we evaluate performance across different test-time compute budgets.
6.2 Backtracking model discovers new search strategies
Figure 1 C shows that the backtracking model post GRPO sees an performance boost across all test-compute budgets. The post-GRPO model (dark red) reaches an accuracy comparable to the pre-GRPO direct solution model (light blue). This improvement is surprising for two reasons: (1) at maximum compute (4096 tokens), the model solves nearly 70% of the test set-exceeiing the performance of the DFS strategy used to generate training data (57%); and (2) the model was trained on questions has already seen during supervised learning, with no new problems introduced during GRPO.
These gains suggest that the backtracking model, once freed from the constraints of predict- ing next token on DFS traces, can now discover better search strategies. To concretely show that the backtracking model post-GRPO learns search strategies different from DFS training traces, we revisit the mistake-counting analysis from Section 4.2.1 (Figure 3). For each test problem, we compute the number of mistakes as before (i.e., counting how many incorrect terminal nodes are explored before reaching a correct solution). Using the same set similarity measure as before, we quantify the strategy deviation in Figure 6 (left). The smaller Jaccard index values confirm that through GRPO, the backtracking model has learned new and more effective search behaviors. In Appendix G.4, we also show the per-problem scatter plot as done in Figure 3.
6.3 Direct solution model specializes at pass@1
We now show that compared to backtracking models, GRPO has remarkably different effects on direct solution models. As shown in Figure 1 C, the direct solution model Post-GRPO achieves strong performance at the smallest compute budget (pass@1), solving 42.5% of unseen CountDown puzzles (82 out of 200 test problems). None of the handcrafted search strategies (Appendix G.1) can reach such high accuracy. To understand the impressive gain

---

Published as a conference paper at COLM 2025
0.45
Backtracking Model (Before GRPO)
Simllntty Ijaccard Index)
After GRPO
Direct Solution Model
Sobing drobbbiiity (Possge4)
0.6
0.6
Dinect Solation Model
Post GAPO
0.4
0.15
0.2
5
10
25 Number of Mistakes
15
20
35
40
30
100
150
200
Problem Index
Figure 6: GRPO has different effect on backtracking versus direct solution model Left: After GRPO, the backtracking model's search strategy starts to deviate away from the DFS search. Right: For problems the pre-GRPO direct solution model (blue) have a non-zero pass@k solving probabilities, the post-GRPO direct solution model (red) solves with pass@1.
on 1-shot performance, we examine those 82 problems, and discover that the Pre-GRPO direct solution model was able to find correct solution by sampling best-of-n (with 64). We now examine a model's s solving probabilities (i.e., measuring pass@k rate out of the 64 generations). We compare the pass@k rate for the diret solution model pre and post GRPO, shown in Figure 6, right. We rank the 200 test problems by the pre-GRPO model's solving probabilities. For problems that the Pre-GRPO model has a non-zero pass@k rate, the post-GRPO model can solve most of them with pass@1.
However, this improvement in 1-shot performance comes with a substantial trade-off: the model loses its ability generate diverse solutions. As a result, when we perform parallel search using best-of-n, the direct solution model post-GRPO fail to explore different solution paths, hurting its test-time-scaling effectiveness. Therefore, test-time compute scaling becomes ineffective as we increase compute bugdets, forming sharp contrast to the backtracking model's consistent improvements across the full compute budget.
7 Conclusion and discussions
In this work, we conducted a controlled empirical investigation into the efficacy of teaching backtracking large language models (LLMs) as method for scaling test-time computation. Using two strategic games, CountDown and Sudoku, we demonstrated that backtracking does not universally outperform parallel solution strategies; rather, its effectiveness depends significantly on task characteristics, model scale, and training approach. Appendix A, we show that our resuls in synthetic setting generalize: even in real-world reasoning tasks, backtracking is not always beneficial. Additionally, our reinforcement learning experiments uncovered a unique synergy between backtracking capabilities and RL-based training, enabling models to discover novel strategies.
Limitations and future work. While our experiments relied on two strategic games (Count- Down and Sudoku) and models trained from common practices for controlled studies-an an important avenue for future research is extending our findings to complex, real- world reasoning tasks such as coding and mathematical problem-solving. For future work, developing precise ways to characterize tasks that benefit from backtracking will be valuable for guiding model training. Finally, while we intentionally created a dichotomy between pure backtracking and direct-solution models, real-world applications may require hybrid strategies that dynamically choose between direct generation and explicit search based on problem complexity. Investigating whether LLMs can autonomously optimize their reasoning modes, particularly through reinforcement learning paradigms, is a promising future direction for improving the flexibility and efficiency of model reasoning.
10

---

Published as a conference paper at COLM 2025
Acknowledgments
We thank Core Francisco Park and Bingbin Liu for helpful discussions and feedback through- out the development of this work. TQ and DAM acknowledge support from the Kempner Institute, the Aramont Fellowship Fund, and the FAS Dean's Competitive Fund for Promis- ing Scholarship.
References
AIME. American invitational mathematics examination, 2024. URL https: //mps.//ma.../// org/ ittpa//mmmmriiaaaaiiiiiittttoaoa
Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. GQA: Training generalized multi-query transformer models from multi-head checkpoints. arXiv [cs.Cl.], 2023. URL http://aaxxiv.rgg/bbbs// 13245.
Afra Feyza Akyürek, Ekin Akyürek, Aman Madaan, Ashwin Kalyan, Peter Clark, Derry Wijaya, and Niket Tandon. RL4F: Generating natural language feedback with re- inforcement learning for repairing model outputs. arXiv [cs.CL.], 2023. URL http: 08844.
Zachary Ankner, Mansheej Paul, Brandon Cui, Jonathan D Chang, and Prithviraj Am- manabrolu. Critique-out-ooud reward models. arviv [cs.LG], 2024. URL http://arxiv. org/abs/2408.111 11791.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. Xiv [cs. 2024. URL http://arxivu http://aaxii.orr/ab/////0../ 21777
Sehyun Choi, Tianqing Fang, Zhaowei Wang, and Yangqiu Song. KCTS: Knowledge- constrained tree search decoding with token-level hallucination detection. ar Xrv [cs, CLI, 2023. URL http:///axx: http:///aaxxvv.oo/aabbsssee/ wrg./br/////1///// 24400004444
Song.
DeepSeek-AL, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z.F Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Liang Zhao, Litong Wang, Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang, Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, R Chen, R L Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang. Shuiping Yu, Shunfeng Zhou, Shuting Pan, SS,,, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun, T Wang. Wangding Zeng, Wanjia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W L Liao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X Qi, Xiangyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang, Xinnan Song, Xinyi Zhou, Xianzu Wang, Xinxia Shan, Y Li, Y Q Wang, Y Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang, Yi Yu, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He, Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y X Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z Z Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie,
11

---

Published as a conference paper at COLM 2025
Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. DeepSeek-RL. Incentivizing reasoning capability in LLMs via reinforcement learning. arXio fes. CLI, 2025. URL
2501. 12948.
Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (SoS): Learning to search in language. arXiv [cs.LGI, 2024. URL http://arriv.orr//b//////
03683.
Kanishk Gandhi, Ayush Chakravarthy, Anikait Singh, Nathan Lile, and Noah Good- man. Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective STaRs. Xiv [es.CLI, 2025. URL htttt:/p///riii http:///aaaii..og/b///////////// 01307.
Alex Havrilla, Sharath Raparthy, Christoforus Nalmpantis, Jane Dwivedi-Yu, Maksym Zhuravinskyi, Eric Hambro, and Roberta Raileanu. GLoRe: When, where, and how to improve LLM reasoning via global and local refinements. ar [cs.CL], 2024. URL
http:///rxxiv.rr//bb///// 10963.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. Xiv [cs, 2021. URL http: httprg/ab//220....em
Zhenyu Hou, Xin Lv, Rui Lu, Jiajie Zhang, Yujiang Li, Zijun Yao, Juanzi Li, Jie Tang, and Yuxiao Dong. Advancing language model reasoning through reinforcement learning and inference scaling. ar Xiv [cs.LG], 2025. URL / www.i..orggabb/50000 11651.
Robert Irvine, Douglas Boubert, Vyas Raina, Adian Liusie, Ziyi Zhu, Vineet Mudupalli, Aliaksei Korshuk, Zongyi Liu, Fritz Cremer, Valentin Assassi, Christie-Carol Beauchamp, Xiaoding Lu, Thomas Rialan, and William Beauchamp. Rewarding chatbots for real-world engagement with millions of users. arv [cs.CL], 2023. URL 06135.
Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux. VinePPO: Unlocking RL potential for LLM reasoning through refined credit assignment. arXiv [cs.LG], 2024. URL http://arxiv. org/abs/ 2/100 02110..16699 01679.
Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq Iqbal, Colton Bishop, Rebecca Roelofs, Lei M Zhang, Kay McKinney, Disha Shrivastava, Cosmin Paduraru, George Tucker, Doina Precup, Feryal Behbahani, and Aleksandra Faust. Training language models to self-correct via reinforcement learning. arXiv [cs. 2024. URL http://aaxvvvvvooo /prgg 12917.
Ariel N Lee, Cole J Hunter, and Nataniel Ruiz. Platypus: Quick, cheap, and powerful refinement of LLMs. ar Xiv [cs.CL], 2023. URL httpp://axxvvvooo...oo 2330..////3.7.77... 07317.
Kuang-Huei Lee, lan Fischer, Yueh-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schu- urmans, and Xinyun Chen. Evolving deeper LLM thinking. arxiv [cs.AT], 2025. URL http://arxiv.. argg
Noam Levi. A simple model of inference scaling laws. arv [stat.M)), 2024. URL http: //arxiv. wwwpiii.org////ae abt////s//211 2410. 16377.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. Xiv [cs.LG], 2023. URL
20050.
Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz. Don't throw away your value model! generating more preferable text with value-guided monte-carlo tree search decoding. arXiv [cs.CI.], 2023. URL http://arriv.orr//aa///33 15028.
Jieyi Long. Large language model guided tree-of-thoughh. Xiv [cs.AlI, 2023. URL http: wawaii..org/ab///223.2. 08291.
12

---

Published as a conference paper at COLM 2025
Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Meiqi Guo, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, Jiao Sun, and Abhinav Rastogi. Improve mathematical reasoning in language models by automated process supervision. arXio [cs. [cs.CLI, 2024. /a///bb///66./ 06592.
URL hittp://arxiv
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv [cs. CI.] 2025. URL http:://axiiii http://xxxvi.ogggbbrr///sa www.orrg/bbb//111.11 19393.
Aleksei Maslakov And Papadimas. Sudoku solver with step-by-step guidance, 2023. URL https://githhb... ctwc/cc///////eeeeeeee httm//umade/dooussaaa 2023.
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. REFINER: Reasoning feedback on intermediate representations. arXiv (es. 2023. URL
01904.
Yuxiao Qu, Tianjun Zhang, Naman Garg, and Aviral Kumar. Recursive IntroSpEction: Teaching language model agents how to self-improve. arXiv [cs.LG], 2024. URL http: //arxiv.org org/ /wwp//27... 221./12777111113
David Radcliffe. 3 million sudoku puzzles with ratings. Website, 2020. URL https: www.uuuuuuuuulsssiiittrrttooonn http:///ee..a...eooooooooooooooe //www. wwwww.aggle..o hwwglle.comdaaaaeo
William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. Self-critiquingg models for assisting human evaluators. ar [cs.CL], 2022. URL 05802.
http:://arxiv.org/abtte
Kulin Shah, Nishanth Dikkala, Xin Wang, and Rina Panigrahy. Causal language modeling can elicit search and reasoning capabilities on logic puzzles. arXiv [cs.LG], 2024. URL http://arxiv. atggabss/4400 10502.
Zhihong Shao, Peiyi Wang. Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, Y K Li, Y Wu, and Daya Guo. DeepSeekMath: Pushing the limits of mathematical reasoning in open language models. arviv [Cs, 2024. URL http:://axxii.orrr http://w.wrr//////////////sse/// abs//////2 03300.
Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Lin, and Chuan Wu. HybridFlow: A flexible and efficient RLHF framework. arXiv preprint Xiv: 2409. 19256, 2024.
Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. RoFormer: Enhanced transformer with rotary position embedding. ar Xiv [cs.CL], 2021. URL http: //trxiv.org//aaaaait/ abs 22////21/2 104.00.0 09864.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9026994269999 (00699949,,000 Stroudsburg, PA, USA, 2024. Association for Computational Linguistics. URL http://d/ doi. orw.org////// 18653/v1 /2024 acl-long.
510.
Tianlu Wang, Ping Yu, Xiaoqing Ellen Tan, Sean O'Brien, Ramakanth Pasunuru, Jane Dwivedi-Yu, Olga Golovneva, Luke Zettlemoyer, Maryam Fazel-Zarandii and Asli Ce- likyilmaz. Shepherd: A critic for language model generation. ar Xiv [cs.CL], 2023. URL http://arxiv.orr//bbs 2398.04592.
Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. arXiv [cs. CL.) 2022. URL http://arxxvv.org/aa
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models. ar Xiv [cs.A[], 2024. URL http://arxiv.orr/abb///ae 00724.
13

---

Published as a conference paper at COLM 2025
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min-Yen Kan, Junxian He, and Qizhe Xie. Self-evaluation guided beam search for reasoning. arv [cs.CL], 2023. URL http: //arxiv.org/ httpg//bb/2235.0005555
Huajian Xin, Daya Guo, Zhihong Shao, Zhizhou Ren, Qihao Zhu, Bo Liu, Chong Ruan, Wenda Li, and Xiaodan Liang. DeepSeek-provers Advancing theorem proving in LLMs through large-scale synthetic data. arXiv [cs. 2024. URL http::/aaaxi..org//bb/////// 14333.
An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yugiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report. ar Xiv preprint Xio:2412.. 15115, 2024.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Xrviv [cs.CL], 2023a. URL http:://aatttt www.:/ogg/bbb///eee 10601.
Weiran Yao, Shelby Heinecke, Juan Carlos Niebles, Zhiwei Liu, Yihao Feng, Le Xue, Rithesh Murthy, Zeyuan Chen, Jianguo Zhang, Devansh Arpit, Ran Xu, Phil Mui, Huan Wang, Caiming Xiong, and Silvio Savarese. Retroformer: Retrospective large language agents with policy gradient optimization. arXiv [cs.CL), 2023b. URL http://arxiv org/ //abs/ 2308.022 02151.
Seonghyeon Ye, Yongrae Jo, Doyoung Kim, Sungdong Kim, Hyeonbin Hwang, and Minjoon Seo. SelFee: Iterative self-revising LLM empowered by self-feedback generation. Blog post, 2023. URL https:: tit..b. io/SelFee/.
Eric Zelikman, Yuhuai Jesse Mu, and Noah D Goodman. STaR: Bootstrapping reasoning with reasoning. arXiv [cs.LG], 2022. URL //arxi/ .rgg/ htrg//bb/2222 14465.
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B Tenenbaum, and Chuang Gan. Planning with large language models for code generation. arXiv [cs.LG], 2023. URL http://arxiv. www. htrg/abs//i 2303.33332 05510.
Yunxiang Zhang, Muhammad Khalifa, Lajanugen Logeswaran, Jaekyeom Kim, Moontae Lee, Honglak Lee, and Lu Wang. Small language models need strong verifiers self- correct reasoning. arXiv [cs.CL], 2024. URL http:://axxit org/abs/2404 17140.
Andy Zhou, Kai Yan, Michal Shlapentokt-Rothmann Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. arx Acs.AII, 2023. URL http:http///aeeee wwtp:v...rrr/bb//////// 04406.
14

---

Published as a conference paper at COLM 2025
Math-500 Performance vs. Test Compute
GPQA Performance vs. Test Compute
0.8
Accuracy (96)
Accuracy (%)
0.6
0.4
02
0.2
Parallel Scalling (Best-of-N)
0.1
Parallel Scaling (Blettof--)
Parallel Sca ling (Majority Vetel
Parallel Scaling (Majority Vote) Backtracking (Sequential Scaling)
(Sequential Scaling)
0.0
0.0
500
1K 1K2K 3K
5K
10K
Z0K
50K
500
1
1K22
3K
SK
10K
20K
50K
Test Compute (# Tokens)
Test Compute (# Tokens)
Figure 7: Evaluating backtracking on real LLMs. Left: On MATH-500, we compare the S1 model (fine-tuned on backtracking traces) using sequential decoding with budget forcing, against its base model (0wen2.5-32B-Insttree model underperforms at low compute but narrows the gap at higher budgets. Right: On GPQA, the same backtracking setup outperforms parallel sampling a multiple-cho reasoning setting. This comparison generalizes our conclusion from synthetic settings to real LLMs.
using parallel sampling. The backtracking
A Backtracking Analysis on Math Reasoning with LLMs
A.1 Experimental Setup
To complement our synthetic experiments, conduct evaluation on real-world math problems to examine whether backtracking remains effective under equal test-time com- pute. We compare two approaches:
Backtracking model: fine-tuned on solution traces that include explicit self-correction and step-by-step reflection.
Direct solution model: the base model without backtracking fine-tuning, using parallel sampling (with majority voting for final correct answer) at inference.
To control test-time compute, we use the budget forcing technique introduced in (Muen- nighoff et al., 2025). This enables fair comparison across models with differing reasoning styles.
Backtracking Model. We adopt the S1 checkpoint from Muennighoff et al. (2025), model trained on solution traces distilled from DeepSeekR1, These traces exhibit explicit backtracking weriiiooo--ddetiiiinnnnn and correcting earlier mistakes. We generate outputs with temperature T 0.7 under budget forcing and evaluate on the MATH-500.
Direct Solution Model. For fair comparison, we use the same base model as S1 Qwen2.5- 32B-Instruct-witee without backtracking fine-tuning. We sample N to completions with temperature T = 0.7, and report both Best-of-N and Majority Vote accuracy.
Results and Interpretation
Figure 7 (left) presents accuracy under matched compute budgets. We observe that at low compute budgets the backtracking model underperforms due to its verbose reasoning traces. At higher budgets, backtracking matches and slightly exceeds the performance of parallel sampling. This mirrors trends observed in the CountDown (Section 4.3), and suggests that while backtracking introduces overhead, it yields benefits when sufficient compute is available.
To form a sharp contrast, we reproduce results from (Muennighoff et al., 2025) on GPOA-Diamond (Figure 7, right), which shows that the same backtracking model signifi- cantly outperforms parallel sampling-eve even at lower budgets- in a multiple-choice setting. This contrast highlights that the effectiveness of backtracking is task-dependent.
15

---

Published as a conference paper at COLM 2025
This real-world evaluation supports synthetic findings: backtracking improves perfor- mance under compute constraints, but its advantage depends on the task structure. On open-ended math problems, the benefit is most pronounced at higher budgets. On struc- tured tasks like multiple-choice QA, gains can appear even earlier. Overall, our conclusions generalize beyond synthetic settings.
B Related Work Extended
B.1 Test-time computation scaling
growing body of work has explored how to improve language model performance by scaling test-time computation. These approaches typically fall into two broad categories: parallel and sequential search. Parallel methods sample multiple solutions independently and select the best one using predefined criteria-such as majority voting or external reward models-as as seen in Best-of-N techniques (Brown et al., 2024; Irvine et al., 2023; Levi, 2024). These methods often rely on outcome-based reward models that score complete solutions (Xin et al., 2024; Ankner et al., 2024).
In contrast, sequential methods iteratively refine reasoning by conditioning on previous attempts. This class includes stepwise improvement methods(Ann (Ankoerr et al., 2024; Hou et al., 2025; Lee et al., 2025), where each new trajectory builds on earlier outputs, enabling the model to adapt its reasoning dynamically. Other research works have also explored using the search process itself to improve model reasoning capabilities, either during inference or by integrating the feedback into training(Wang et al., 2024; Luo et al., 2024). While these methods can reduce redundancy, they typically require more compute per sample and may suffer from compounding errors.
Tree-based approaches, such as Monte Carlo Tree Search (MCTS) and guided beam search, represent a hybrid between parallel and sequential strategies 2023; Zhang et al., 2023; Zhou et al., 2023; Choi et al., 2023; Xie et al., 2023). These methods often leverage process reward models, which assign value to intermediate reasoning steps rather than full outputs(Lightman et al., 2023; Wang et al., 2024; Wu et al., 2024). REBASE(WU et al., 2024), for example, uses a process reward model to guide exploration and pruning in tree search, and has been shown to outperform both compling-based methods and traditional MCTS.
al., 2024; Liu al.,
B.2 Self-correction and backtracking
Search and backtracking are inherently tied to self-correction, as they enable models to revisit earlier decisions and recover from errors-a a critical capability for multi-step reason- ing. Teaching language models to self-correct has been approached through fine-tuning on revision demonstrations from humans or stronger (SaulesSaunders et al., 2022; Ye et al., 2023; Qu et al., 2024), as well as through synthetic data generation and handcrafted aug- mentation(Paul et al., 2023; Wang et al., 2023; Lee et al., 2023). Reward- methods provide another avenue, using outcome- process-level signals to differentiate good and bad reasoning trajectories, often framed as implicit policy Mamming(Welledd) et al., 2022; Akyürek et al., 2023; Zhang et al., 2024). Some methods further incorporate search, critique generation, or separate correction modules to enhance reasoning quality(Yao et al., 2023b; Havrilla al., 2024). In contrast, using two structured games, we investigate the tradeoffs of teaching models to backtrack via search traces versus allowing them to learn purely from correct solutions.
B.3 Reinforcement learning for LLM reasoning
Reinforcement learning (RL) has emerged as powerful framework for improving the reasoning abilities of language models. While early work applied off-policy and on-policy RL methods to guide models toward verifiable outcomes(Zelikman et al., 2022; Kazemnejad et al., 2024), recent approaches have shown that even simplified algorithms like GRPO can lead to significant performance gains and the emergence of in-context search behavior (DeepSeek-A) et al., 2025; Shao et al., 2024; DeepSeek-AL et al., 2025). These advances suggest that RL can help models autonomously discover more effective reasoning strategies, even without explicit reward models or structured search. However, not all models benefit
16

---

Published as a conference paper at COLM 2025
equally from RL, and it remains unclear what properties make model amenable to learning through reinforcement. Our work contributes to this question by examining how back- tracking models, when trained with GRPO, can discover novel solution strategies-While no-backtracking models show limited or mixed gains.
C Experiment details
C.1 Additional details on game, data generation
CountDown tree size computation. CountDown has exponentially growing search space with respect to the number of candidate numbers. the current state has available numbers, there are (2)
(N) 4 possible actions (selecting pair and one of four operations),
and the depth of the tree is 1. For games with four candidate numbers, the complete search tree contains 1,152 nodes.
CountDown search. To generate DES search data, we use a sum heuristic to guide the search order and prune nodes. This heuristic measures the distance between the sum of all input numbers and the target number, and prunes node if the absolute distance exceeds the target. This approach is inspired by Gandhi et al. (2024), who also consider alternative- multiply heuristic-which measures the minimum distance between the input set and the factors of the target. However, in experiments, both heuristics yield similar performance: for a fixed number of visited nodes, DFS with either heuristic solves approximately the same number of games.
Sudoku rule. In a Sudoku game, the player is given 9 x grid in which each cell must be filled with a digit from 1 to 9. The puzzle is subject three constraints: each row, each column, and each of the nine x 3 subgrids must contain all digits from 1 to 9 exactly once. Given a partially filled grid, the objective to fill in the remaining cells such that all constraints are satisfied.
Sudoku data and tokenization. To represent the Sudoku board for language models, we encode each cell as a position-value pair: (x,y) V, where (x,y) denotes the grid location and is the cell's value. The model receives the initial board as list of known yx, D pairs and generates the solution by predicting the values for the remaining cells. We generate backtracking traces by serializing the full DFS traversal. For the direct solution model, prune each trace to include only the final solution path.
Scoring. For CountDown, solution correct only if it adheres to game rules and correctly achieves the target number. For Sudoku, correctness requires fully solving the board, with no partial credit given for incomplete but correct boards. Models are tested on 200 unseen problems per game. The same scoring function is used as the reward function in GRPO (Section 6)
C.2 Additional details on model architecture
Model hyperparameters can be found Table
Model Size
Hidden Size
Layers
Attn Heads
Intermediate Size
KV Heads
3M
256
6
4
512
17M
512
8
4
1024
38M
512
10
8
2048
2
144M
1024
12
8
3072
Table 1: Qwen2.5-style architecture configurations for the four model sizes used in our experiments.
C3 Training hyperparameter
Training hyperparameters can be found in Table We train all models on NVIDIA H100 80GB HBM3 GPUs.
17

---

Published as a conference paper at COLM 2025
Hyperparameter
Value
Optimization
Learning rate
1 x 10-5
Weight decay
0.01
Learning Rate Schedule
Scheduler type
Cosine
Warmup steps
1
Training Setup
Epochs
30
Batch size (backtracking model)
32
Batch size (direct solution model)
64
Context length (backtracking model)
4096
Context length (direct solution model) Tokenizer
512
Tokenizer size (CountDown)
74
Tokenizer size (Sudoku)
110
Table 2:
Training hyperparameters used for all experiments. Batch size and context length vary based on model type.
D FLOP computation
To compare backtracking and direct solution models under fixed compute budget, we estimate inference FLOPs based model architecture and generation length T. We simplified transformer FLOP computation that accounts for per-token operations across all layers.
Below is a list of architectural and generation parameters:
model hidden dimension
d key/value dimension
døf intermediate (feedforward) dimension
L: number of layers
T: number of generated tokens (i.e., context length)
N: number of sequences generated (e.g,, in best-of-N sampling)
D.1 Step-by-step FLOPs Calculation
1. Per-layer linear FLOPs per token. We down the linear FLOPs for each transformer layer into attention and MLP components:
Self-attention:
Query projection: dmudel dmodel
Key projection: dmodel X dky
Value projection: dmodel dgy
Output projection: &model X dmodel
This results in total of:
FLOPs attention-linear
2d 2d + 2d gy
MLP (Feedforward);
MLP layers include following components:
Gate projection
-Up projection
Down projection
Each of these MLP layers costs: dmodel dit, giving:
FLOPsmlp 3d
key value dimension is different from hidden dimension because of GQA (Ainslie al., 2023)
18

---

Published as a conference paper at COLM 2025
Combining both components, the total per-token linear cost per layer is:
FLOPStinear = 2d model + model + 3d model
2. Quadratic attention cost. Self-attention involves computing interactions between all token pairs, resulting in a quadratic cost:
T(T+1) +11
FLOP model
2
3. Total generation cost per sequence. Each token attends to all previous tokens across all layers. The generation cost for a single sequence is:
FLOP gen = L (FLOPslinear T PLOOPsatentionn
4. Total inference FLOPs. For sequences (e.g., best-of-N sampling), the total inference cost is:
FLOPS = N N-FLOPSgen
We do not include auxiliary operations such token embedding and softmax, weight norm, as their contribution negligible compared to the transformer layers. All FLOPS reported in experiments use this formula, with model configurations listed in Table 1.
E Majority voting versus best-of-n
In this work, we primarily use the best-of-1 metric to evaluate the direct solution model. This metric is suitable for tasks where verifying the correctness of solution is trivial, whereas solving the task itself is challenging, Many real-world problems, such as coding tasks and combinatorial optimization, fall into this category. Conversely, for problems where verification is difficult, metrics such as majority voting may be more appropriate.
To illustrate this point, we additionally evaluate the CountDown direct solution model using both metrics in Figure 8. For majority voting, we generate solutions per test problem, select the most frequently occurring solution (breaking ties randomly), and evaluate its correctness.
We find that the majority-voting performance closely approximates the direct solution model's one-shot accuracy (i.e., best-of-n with ==1). However, majority voting is less suitable for task for several reasons. First, the CountDown game frequently has multiple correct solutions, so selecting the majority solution path can fail to detect cases where the model generates different but equally valid solutions. Second, while majority voting is as mathematical pasoning-whor where distinct
appropriate in real-world LLM scenarios solution paths converge to the same final boxed answer, in our synthetic setting, where models are trained from scratch, majority voting essentially becomes a noisy proxy for greedy decoding (sampling at temperature T 0). Thus, we expect and observe majority voting accuracy to closely track pass@1 accuracy.
In summary, given the characteristics of our task and the controlled experimental setup, best-of-n remains valid and preferred metric for evaluating direct solution models.
Dependence on depth of the search tree
E1 Search tree depth
Why do backtracking models perform well on Sudoku but underperform on CountDown, even when both are trained on DFS search traces? We argue that task characteristics particularly those beyond our control in real-world settings peetings-play play a key role in determining A major difference between the two
whether backtracking is sos-time--ompute-effii games lies in the depth of their search trees (Figure 2). In hard Sudoku puzzles, only 20 out of 81 cells frellilled, leaving 50 60-60 cells to solve. This results in deep search trees with
19

---

Published as a conference paper at COLM 2025
Direct Solution Model Performance
2est-ckn
majer By nate
%
93
43
30
25
54
n(llgescale)
Figure 8: Majority voting versus best-of-n for CountDown direct solution model. For CountDown, verification is much easier than solving the problem. Therefore, best-of-n as a performance is justified. Additionally, we also examine majority voting performance. However, CountDown solutions not unique, majority voting is not the most suitable way to measure model performances.
15
CountDoars
10
Original
Solitio Backttack (S4
Drect Souaton booktmck (S)
-10
37M
15
Accurary Cap
Accurscy cam
1.0
Original
dked
Figure 9: The efficacy of backtracking depends on search tree depth. Left: We introduce variation of the CountDown game-stackedt CountDown increase the search tree depth. In the original CountDown game (solid bars), the direct solution model consistently outperforms the backtracking model, shown by positive performance gap. In the stacked version (slanted bars), this gap is significantly reduced or even reversed, indicating that backtracking becomes more compute-efficient at greater depths. Right: We introduce variation of Sudoku-easy Sudoku Sudoku-where where the initial board has more pre-filled cells to decrease the search tree depth. In the original setting, the 38M direct solution model (bottom, solid bars) underperforms the backtracking model. In the shallow Sudoku variant (slanted bars), the performance gap narrows across compute budgets. For the 17M models (lop), the results are less conclusive.
extensive trial-and-error, with many backtracking steps. In contrast, CountDown (in our setup) uses 4 candidate numbers, limiting the search tree depth to just 3, We hypothesize that backtracking models excels at tasks with deeper search trees, while shallow trees make parallel strategies (i.e., direct solution model) more effective. To test this, we design a variant of CountDown with increased search depth and variant of Sudoku with reduced depth.
F2 A deeper CountDown
Set up To increase the search tree depth in CountDown, one might naively scale up the number of candidate numbers. However, this approach quickly leads to exponential growth in tree width: with 4 candidates, the tree contains 1,152 nodes; with 5 candidates, it grows to 46,080. To prevent the exponential growth in the number of search paths, design stacked CountDown variant that increases depth while controlling tree width. In this setup, the player is given candidate numbers and final target. The first 4 numbers must be used
20

---

Published as a conference paper at COLM 2025
to reach the 5th number ("a partial goal"), and the remaining numbers must then be used to reach the final target. This effectively stacks two CountDown problems, increasing depth without combinatorial explosion. We generate training data for both backtracking and no-backtracking models following the same procedure as Section 3.1.2, with examples provided in Appendix H (Figure 16). We train 17M well as 38M model until validation loss has converged, and test on 200 unseen problems.
Results In Figure 9 (left), we compare the performance gap between the direct solution model and the backtracking model, measured by the difference in test accuracy. In the original CountDown setting (solid bars), the direct solution model consistently outperforms the backtracking model across all test compute budgets. However, in the stacked Count- Down variant (slanted bars), the performance gap narrows significantly-ande in some cases, reverses. The sign reverse indicates the backtracking model now outperforms the direct so- lution model. These results support our hypothesis: in CountDown, backtracking becomes more compute-efficient as the search tree depth increases. We observe this trend across both 17M and 38M models.
E3 A shallower Sudoku
Set up To reduce the search tree depth in Sudoku, we generate easier boards by increasing the number of initially filled cells. Specifically, we take the original 3M Sudoku dataset Radcliffe (2020) and apply the direct solution model (Section 3.2.2) to correctly fill 10 additional cells. This increases the average number of pre-filled cells from 20 to around 30, effectively decreasing search tree depth. We generate both backtracking and direct solution training data following the same procedure in Section 3.2.2. Models with 17M and 38M parameters are trained to convergence and evaluated on 200 unseen problems.
Results In Figure 9 (right), we show the performance gap between the direct solution and backtracking models, measured by the difference in test accuracy. In the original (hard) Sudoku setting, the 38M direct solution model consistently underperforms the backtracking model, indicated by the negative gaps (solid green bars). In the shallow-Sudoku variant (slanted bars), these gaps are reduced across all test-time compute budgets for the 38M model. The trend is less clear for the 17M model, where the performance difference remains small in both settings. Overall, these results support our hypothesis: in Sudoku, backtracking becomes more test-time-compue--ffiic when the search tree is deeper.
G Additional results
G.1 Exploring different CountDown strategies
We analyze different search strategies for CountDown, including DFS and BFS with varying beam widths. For each strategy, we tokenize the resulting backtracking trace and measure number of tokens used in each search trace. The goal is to identify which strategy that finds correct solutions with the fewest tokens (Figure 10). The results show no clear winner. BFS with smaller beam width produces shorter traces by exploring fewer nodes, but this comes at the cost of missing correct solutions more frequently. Increasing the beam width improves solution coverage but leads to longer traces due to broader exploration.
In contrast, DFS produces more uniformly distributed trace lengths but suffers from specific failure mode: it may prune the correct path early and terminate prematurely. These failures appear as short but incorrect traces, visible as the left-most orange bars in Figure 10 (botlom).
G.2 Compare think-backtrack and backtrack
Table 3 further shows confusion matrix comparing the original and think-backtrack models. The backtracking model solves 102 test problems in total with maximum test-time time compute budget (409 tokens). Out of those 102 problems, the think-backtrack model solves most of them. This evidence further shows that by training on shortened search traces, the model learns to internalize parts of its thinking without sacrificing performances.
21

---

Published as a conference paper at COLM 2025
BFS Beam Width
2K
Correct
1K
BFS Beam Width
2K
Count
1K
BFS Beam Width = 4
2K
1K
DFS
2K
1K
10a
10a
10a
Search Length (log scale)
Figure 10: Examine different search strategies for CountDown. Beyond DFS, we exper- iment with Fread-First-Search (BFS) with different beam widths. We tokenize the search trace and measure the number of tokens as search length. There is not search algorithm that is optimal to generate both short and correct solution traces.
T-B Correct
T-B Incorrect
B Correct
83
B Incorrect
41
57
Table 3: Confusion matrix between Thinnk-Bcktrrcck (T-B) and Backtrack (B) models.
G.3 Supervised learning training curve
During training, set the maximum epochs 30 epochs and allow early stopping. All models converge before 30 epochs and we early stop training when the validation loss has converged on log-log scale. Figure 11, 12 show the training curve for both models and for CountDown and Sudoku.
G.4 Additional GRPO plots
In Figure 3 (Section 4.2.1), we used the number of mistakes as a proxy for comparing search strategies. To further demonstrate that the backtracking model fine-tuned with GRPO discovers new strategies, we repeat the same analysis in Figure 13 (right). Compared to the original backtracking model (Figure 13, left), the post-GRPO model solves many problems with different number of mistakes than the number of mistakes made by DFS. This shift indicates that the model is no longer tightly aligned with the original search trace and has discovered alternative, more diverse solution paths. Figure (left) quantifies the above qualitative observation.
H Data sample
Figure 14 shows an example of CountDown game and the training data. Figure 15 shows an example of Sudoku game and the training data. Figure 16 shows an example of stacked-CountDoww variation and the training data.
22

---

Published as a conference paper at COLM 2025
1.0
Veidation Low Illgoocclll
0.3
0.5
0.3
Stop scale!
Figure 11: CountDown validation loss. Left: Backtracking model. Right: Direct solution model.
Backtracking Model
Direct Solution Model
13
Valsadion Lowe Degeralee
0.9
05
0.5
0.4
0.1
2t
12c
30k:
120k
36
10k
30k
120k
Stop
Stop
Figure 12: Sudoku validation loss. Left: Backtracking model. Right: Direct solution model.
40
Backtacking (Beforu GXP))
40
Backracking (Ater Gitr))
Number Malakes
Number Mistakes
20
10
10
150
150
Sample
Sample
Figure 13: Backtracking model can discover some new search strategies. Post GRPO, the backtracking model discover new strategies: In the right panel, for each problem, the post-GRPO model makes a different number of mistakes compared to DFS trace.
23

---

Published as a conference paper at COLM 2025
Example of CountDown game
Target: 16
Candidates: [96, 11, 78, 22]
DFS Search Trace
Current State: 16: 16:[96, 11, 78, 22], Operations: []
Exploring Operation: 96-78=18, Resulting Numbers: [11, 22, 18]
Generated Node #0,0: 16:[11, 22, 18] Operation: 96-78=18
Moving Node #0,0
Current State: 16:[11, 22, 18], Operations: ['96-78=18')
Exploring Operation: 22-11=11, Resulting Numbers: [18, 11]
Generated Node 40,0,0: 16: 11] Operation: 22-11=11
Moving Node #0,0,0
Current State: 16:[18, 11], Operations: ['96-78=18', '22-11=11']
Exploring Operation: 18-11=7, Resulting Numbers: [7]
7,16 unequal: No Solution
Moving to Node 40,0,0
Current State: 16:[18, 11], Operations: ['96-78=18', '22-11=11']
Exploring Operation: 18+11=29, Resulting Numbers: [29]
29,16 16 unequal: No Solution
Moving to Node #0,0
Current State: 16:[11, 22, 18], Operations: ['96-78-18']
Exploring Operation: 18-11=7, Resulting Numbers: [22,
Generated Node 10,0,1: 16: [22, 7] Operation: 18-11=7
Moving to Node #
Current State: 16:[22, 7], Operations: ['96-78-18', '18-11=7']
Exploring Operation: 22-7=15, Resulting Numbers: [15]
15, unequal: No Solution
Moving to Node 40,0,1
Current State: 16:[22, 7], Operations: ['96-78=18', '18-11=7']
Exploring Operation: 22+7=29, Resulting Numbers: [29]
29,16 unequal: Solution
Moving Node #0,0
Current State: 16:[11, 22, 18], Operations: ['96-78-18'
Exploring Operation: 22/11=2, Resulting Numbers: [18, 2]
Generated Node #0,0,2: 16:[18, 2] Operation: 22/11=2
Moving Node #0,0,2
Current State: 16:[18, 21, Operations: ['96-78-18' '22/11=2']
Exploring Operation: 18-2=16, Resulting Numbers: [16]
16,16 equal: Goal Reached
Direct Solution Trace
Current State: 16:[96, 11, 78, 223, Operations:
Exploring Operation: 96-78=18, Resulting Numbers: [11, 22, 18]
Generated Node #2: [11, 22, 18] from Operation: 96-78=18
Current State: 16:[11, 22, 18], Operations: ['96-78-18']
Exploring Operation: 22/11=2, Resulting Numbers: [18,
Generated Node #3: [18, 2] from Operation: 22/11=2
Current State: 16:[18, 2], Operations: ['96-78-18', 222/11=2']
Exploring Operation: 18-2=16, Resulting Numbers: [16]
16,16 equal:
Goal Reached
Figure 14: Example of training data for CoutnDown. Top: game setup. Middle: full DFS search trace for training backtracking model. Bottom: correct solution path for training direct solution model.
24

---

Published as a conference paper at COLM 2025
2
2
7
2
3
7
1
5
9
Example of Sudoku game
START (0, 0)
(0, 2)
(0, 3)
(0,
(1, 3) (1, 7) 7
(2, 1) 8
(2, 2) 3 (2, 7) (3,
4)
5 (3,
7) = (4, 8) 2 (4, 2)
9
(4
8
7 (5, 3)
= 3 (5, 5) = (6, 2) (6, 4) = (7, 1) = 4 (7, 2) 7 (7 4)
(7, 8)
=
(8, 0) = (8, 3) (8,
4)
(8,
8) solving
DES Search Trace
GJESS (0, 4) [3, 9] 3 (8, 4) GESS: (0, 16, 61 ())
SCL_START (4, 4) = (8, 2)
3) =
= GLESS:
4)
= 5 5) (2, 8) = 13 (4, 5 (.
6) = 8
1) (1211116666211212110103333311113
(2, COCCMDITTTE:: 01
(8, 6) 8 (8,
(4, 5)
1) 3 (5, 2) (6, 110"1111000001000100000000111110
(3,
(3,
(5,
5) 3 (6, 6) =
3 (6, 10 CANDIDATE: NO :
(8, revert:
NG_CANDDDATE CAND (8,
(0, B3, 9]
7 (2, 4)
(3, 5)
0) = (2, 5) (4, 1) (5, 2) (6,
5) (1, 5)
3)
(0, 6) (5, (6.
(1 6) (2,
6)
(2,
(4,
(6.
END
Correct Solution
SCL_START (4, 4) (8,
(8, 5)
2 (3, 3) 9 (3,
5) = (4, 5) = (1
(3 2)
(5,
1)
5
(1, 1)
6 (1 2)
(2, 8) (2, 5)
1)
(1, 5)
(3 1)
8) = (5, 8) (7 5) 3
(1 8)
(3,
6)
3
(5.
8)
(6
5)
9
(6,
8)
(7
8)
(8, 6)
1) (1,
8)
(5, 1)
(8,
(2,
(4, 6)
(4, 7)
(5. 6)
(6.
6 (7,
(8,
6)
SOL
END
Figure 15: Example of training data for Sudoku game. Top: initial puzzle setup. Middle: full search trace with guesses and backtracking (tabs used). Bottom: final correct solution.
25

---

Published as a conference paper at COLM 2025
Example of stacked-CountDown game
Target: 96
Candidates: [22, 77, 24, 48, 31, 12, 36, 35]
DFS Search Trace
Current State: 96: [22, 77, 24, 48, 31, 12, 36, 35], Operations: 0
Exploring Operation: 77-48-29, Resulting Numbers: [22, 24, 29, 31, 12, 36, 35]
Generated Node #0,0: 96: 24, 29, 31, 12, 36, 35] Operation: 77-48-29
Moving Node #0,00
Current State: [6:[22, 24, 29, 31, 12, 36, 35], Operations: ['77-48-29']
Exploring Operation: 22+24=46, Resulting Numbers: [29, 46, 31, 12, 36, 35]
Generated Node #0,0,0: 96: 46, 31, 12, 36, 35] Operation: 22+24=46
Moving to Node #0,0,0
Current State: 96: 46, 31, 12, 36, 35], Operations: ['77-48-29' '22+24=46']
Exploring Operation: 46-29=17, Resulting Numbers: [17, 31, 12, 36, 35]
17,31 unequal
Moving to Node 40,0
Current State: 96: [29, 2, 31, 12, 36, 35], Operations: ['77-48-29', '24-22=2']
Exploring Operation: 29+2=31, Resulting Numbers: [31, 31, 12, 36, 35] 31,31 equal
Current State: [3, 12, 36, 35], Operations: []
Exploring Operation: 36-35=1, Resulting Numbers: [31, 12,
Generated Node #0,0: 96:[31, 12, 1] Operation: 36-35=1
Moving to Node #0,0
Current State: 96:[31, 12, 1J, Operations: ('36-35=1')
Exploring Operation: 31+1=32, Resulting Numbers: [12, 32]
Generated Node 00,0,0: 96: [12 32] Operation: 31+1=32
Moving to Node 40,0,0
Current State: 96:[12, 32], Operations: ['36-35=1' '31+1=32']
Exploring Operation: 12+32=44, Resulting Numbers: [44]
44,96 unequal: No Solution
Exploring Operation: 4*24=96, Resulting Numbers: [96] 96,96 equal: Goal Reached
Direct Solution Trace
Current State: 96: [22, 77, 24, 48, 31, 12, 36, 35], Operations: 0
Exploring Operation: 77-22-55, Resulting Numbers: [55, 24, 48, 31, 12, 36, 35]
Generated Node #2: [55, 24, 48, 31, 12, 36, 35] from Operation: 77-22=55
Current State: 96: [55, 24, 48, 31, 12, 36, 35], Operations: ['77-22=55']
Exploring Operation: 48-24=24, Resulting Numbers: [55, 24, 31, 12, 36, 35]
Generated Node 43: [55, 24, 31, 12, 36, 35] from Operation: 48-24=24
Current State: 96: 24, 31, 12, 36, 35], Operations: ['77-22=55' :48-24-2 148-24=24'J
Exploring Operation: 55-24=31, Resulting Numbers: [31, 31, 12, 36, 35]
31,31 equal
Current State: 96:[31, 12, 36, 35], Operations: []]
Exploring Operation: 35-31=4, Resulting Numbers: [4, 12, 36]
Generated Node #2: [4, 12, 36] from Operation: 35-31=4
Current State: [6:[4, 12, 36], Operations: ['35-31=4']
Exploring Operation: 36-12=24, Resulting Numbers: [24, 4]
Generated Node #3: [24, 4] from Operation: 36-12=24
Current State: 96:[24, 4], Operations: ['35-31=4', '36-12=24']
Exploring Operation: 4+24=96, Resulting Numbers: [96]
96,96 96 equal:
Goal Reached
Figure 16: Example of training data for
(Appendix F). Top: game
setup. Middle: full DFS search trace for training backtracking model. Bottom: correct solution path for training direct solution model.
26


Reviews:
[{"review_id": "xoheWx72Ss", "reviewer": "Reviewer_GNL9", "summary": "They conduct an analysis of how backtracking inside the model's CoT (sequential test-time compute) impacts the performance of LLMs on Countdown and Sudoku, comparing against parallel sampling techniques. They find that on countdown sequential search underperforms parallel, but on sudoku it outperforms, suggesting that which is better depends largely on the task at hand. However, when training with RL models equipped with backtracking learn much more effectively. They also point out. two potential limitations of backtracking: 1) the token inefficiency; and 2) suboptimal data.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The analysis in their paper is well executed. They carefully consider different aspects that can effect backtracking performance including task, model size, and data composition, and they do a good job of teasing each of these attributes apart in their experiments. I think this line of work of trying to better understand the scaling trends of different approaches to test-time scaling is really important and contributes greatly to our progress as a field.", "reasons_to_reject": "* 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. 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.\n* For each task, they generate a dataset for SFT synthetically. It is likely that some of their conclusions are specific to how the data is generated in each case. 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. As a result, their conclusions may be more specific to the data and less-so the task itself as they claim.\n* In a few places I felt that the writing was overly verbose, such as in Sections 3.1 and 3.2.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nplKWx1Sne", "reviewer": "Reviewer_z8oL", "summary": "The paper focuses on comparing backtracking vs direct solution in test-time computation. The paper proposes two dataset/tasks CountDown and Sudoku. Interestingly, sequential search underperforms parallel sampling on CountDown but outperforms on Sudoku. And then the paper extends the analysis to refinrocement learning more specifically GRPO algorithm and find that teaching backtracking universally improves LLM reasoning.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "A very neat idea with clear demonstration on both SFT and RL for comparing backtracking and non-backtracking. The paper points out some interesting and fundamental research problem in test-time scaling and even more broadly search strategies in finding the answer in a large space. I like the easy-to-follow tasks. \n\nThe paper pays some effort in training and comparing algorithms, rather than simple prompt engineering. It provides some concrete analysis and some insights.", "reasons_to_reject": "The task is very limited and it’s not necessarily about LLM. I feel like it’s more about transformers architecture. 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. \n\nClarification of algorithms and terms, complexity analysis and data statistics. The presentation of results in the paper was awesome, but the methodology part was a little vague to me.", "questions_to_authors": "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. \n\n\nI 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 table would be useful to differentiate algorithms here.", "extra_scores": {}}, {"review_id": "4G3fF1QWOU", "reviewer": "Reviewer_VtTK", "summary": "The paper investigates whether training large language models (LLMs) to perform backtracking offers consistent advantages over parallel sampling methods, especially under fixed test-time compute budgets. Using two strategic games, CountDown and Sudoku, as controlled testbeds, the authors compare models trained on explicit backtracking traces to those trained on correct final solutions. Results show that backtracking models outperform direct solution models in Sudoku but underperform in CountDown. The study attributes this divergence to two key issues: (1) backtracking traces impose rigid, potentially suboptimal strategies; (2) verbosity induced by trace-based training reduces reasoning efficiency. Furthermore, reinforcement learning (via GRPO) helps backtracking models discover new, effective strategies and improves test-time performance, while direct solution models show less gain and even reduced diversity after RL. The paper concludes that backtracking is not universally beneficial and must be judiciously applied based on task structure and model constraints.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The use of CountDown and Sudoku as diagnostic tasks is methodologically sound, providing a controlled environment to isolate the effects of backtracking and parallel strategies on LLM performance.\n\n- The paper exposes important limitations of backtracking that are often overlooked in literature emphasizing step-by-step reasoning.\n\n- The study extends its scope by integrating reinforcement learning (GRPO), revealing how backtracking-trained models benefit more from RL fine-tuning than direct solution models", "reasons_to_reject": "- My biggest concern with the paper is the narrow selection of the two tasks. Whether backtracking or not seems to be very task-dependent. For example, CountDown likely has a broad, shallow search space with many possible solutions that are not too far apart. Parallel sampling works well here because generating multiple independent solutions increases the chance of hitting a correct one quickly. Sudoku, by contrast, has a deep, narrow solution space where most paths lead to dead ends, and intermediate steps must be precisely correct. Sequential search with backtracking excels here because correcting errors mid-way (by backtracking) allows recovery from partial failures. From that point of view, it can be expected that countdown tasks with direct sampling may be more effective, while Sudoku benefits more from the backtracking. It might be beneficial to consider other types of reasoning tasks beyond these two to show that the phenomenon is more general instead of being task-specific. \n\n- 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.\n\n- 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.\n\nBesides this, I feel this paper is still very interesting. I will raise the score if the authors could consider adding more tasks beyond these two tasks.", "questions_to_authors": "Is it possible to consider other reasoning tasks beyond Countdown and Sudoku?", "extra_scores": {}}, {"review_id": "ni2C3ztQUz", "reviewer": "Reviewer_EL6J", "summary": "This paper systematically investigates the effectiveness of backtracking (in the context of test-time compute) when compared to parallel sampling for LLMs in reasoning tasks. Through experiments targeting CountDown and Sudoku, the paper finds that backtracking is not “universally beneficial”. Additionally, they find that training on backtracking examples can hinder model performance, that RL finetuning helps models in backtracking, and that aspects of the tasks (tree depth) impact which approach is best. Overall, the paper includes extensive experiments, careful articulation of the methods and clear and interesting results. I recommend that it be accepted.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper is well written, it’s problem clear, the insights interesting, and the experiments thorough. I believe that it will lead to interesting future work.", "reasons_to_reject": "I don’t have any reasons to recommend rejecting the paper.", "questions_to_authors": "-\tI found the results in Appendix D particularly interesting. It is currently framed around what makes backtracking better, but I wonder if instead, the issues are around parallel sampling. 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). \n-\tI’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).", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies if backtracking data is required for reasoning models. Reviewers all agree that the paper introduces findings for the reasoning community.
Decision: Accept