- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper investigates the relative efficiency of search-augmented (SA) and solution-only (SO) supervision on Maze Navigation and two variants of Countdown along three axes: training scale, the structure of the underlying search problem, and the structure of intermediate supervision. The experiments show that SO achieves low error with less training compute on Maze Navigation, while SA with DFS traces maintains a compute-efficiency advantage on Countdown.
Critical strengths
1. An interesting and important research question.
The paper investigates the benefits of learning to imitate search trajectories from the perspective of training compute efficiency. I find this a meaningful question for understanding the practical benefits of search-augmented reasoning.
2. Systematic experiments aligned with the research question.
The authors examine different dataset sizes, model sizes, and search traces, analyzing scaling behavior in terms of training compute.
Critical weaknesses
1. Some interpretations of the experimental results and their generalizability would benefit from further validation.
The paper attributes the differences in efficiency between SA and SO to problem structure and the usefulness of search heuristics. However, several factors vary simultaneously, making it difficult to isolate their individual effects. For example, Maze Navigation and Countdown differ in search algorithms and trace representations, while regular and modular Countdown differ in numerical ranges and solution lengths. Moreover, the experiments focus on relatively small Transformer models trained from scratch, making it unclear whether similar scaling behavior would emerge in more capable pretrained LLMs. While the observations are interesting, additional controlled experiments and a clearer discussion of the scope and limitations of the findings would help strengthen the conclusions.
2. The trade-off between search trace length and compute efficiency is not sufficiently explored.
SA models must learn both to generate correct search traces and to derive final solutions from them. Therefore, longer search traces may not necessarily improve performance or compute efficiency, and an optimal search budget may exist. Although the paper discusses the importance of trace length to some extent, it does not systematically examine how varying search trace length within the same problem affects performance and compute efficiency. Further analysis would help clarify how much this factor influences the relative efficiency of SA and SO.
Questions for authors
- How does search trace length affect the compute efficiency of SA? Since SA models must learn both (1) to generate search traces and (2) to derive solutions from them, I suspect there may be an optimal trade-off in trace length. Could varying the search budget within the same problem change the relative efficiency of SA and SO, or affect the main conclusions?
- Could the relatively weak performance of SO in Figure 3 be related to limited model capacity? Would the authors expect similar scaling behavior in stronger pretrained models or recent LLMs with more advanced reasoning capabilities?
- Could the authors clarify the choice of DFS and SoS as the main comparison methods for Countdown? I would appreciate further discussion of how differences in search success rates and solution supervision affect the results. To what extent can the effect of search trace quality be isolated from these other factors?
7 comments
Thank you for the detailed response and additional experiments. I appreciate the authors' efforts to address my concerns. While the new results are helpful, I believe my main concerns about the interpretation and generalizability of the findings remain. I therefore maintain my original score.
Thank you for the feedback. We kindly ask if you could elaborate more on what concerns about the interpretation and generalizability still remain? From our perspective, our response and new experiment results should clarify and address many of your concerns, so we would appreciate to know what is missing so that we can improve further.
On "Interpretation"
Reviewer comment: "The paper attributes the differences in efficiency between SA and SO to problem structure and the usefulness of search heuristics."
Our response:
- This is inaccurate, since we specifically discuss that efficiency might be affected by (1) problem structure, of which search heuristic is a part, not a separate factor, and (2) trace structure, in which trace length is the main factor we highlight. These were part of the research questions in the original paper, and we further highlighted and clarified this taxonomy in our update to the paper, incorporating the comments of all 3 reviewers. Therefore, the comment inaccurately characterises what we attribute the differences in performance to.
- Our additional controlled experiments which ablated the influence of the factors in the problem structure (adding heuristics, adding states in context, and simplifying transition function) show that harmonising them with maze navigation is not enough to change the efficiency regime to search-optional. Therefore, the trace structure, of which length difference between Countdown and maze traces is the most quantifiable one, accounts for the rest of the efficiency advantage of search in the easiest variant of Countdown.
On "Generalizability"
Reviewer comment: "Moreover, the experiments focus on relatively small Transformer models trained from scratch, making it unclear whether similar scaling behavior would emerge in more capable pretrained LLMs."
Our response: We believe we addressed this (and only) issue about generalizability raised by the reviewer by adding Llama-3.2-1B-Instruct finetuning experiments, which showed the same trends and reached the same conclusions as our experiments with GPT2 models trained from scratch.
Given that the reviewer is not completely satisfied with our response and additional experiment, we kindly ask for more details about what is still missing from our study which could potentially overturn our results and conclusions, so that we can concentrate on rectifying these. Thank you.
We thank the reviewer for valuable feedback and appreciate thought-provoking comments and questions. Below we address the concerns raised in your review. Please let us know if you have any further concerns or questions. Otherwise, we would appreciate it if you would reconsider your score in light of our replies.
[W1/W2/Q1] “How does search trace length affect the compute efficiency of SA?”
This is a great question. We address this question in our Official Comment, please see above.
In summary, we have amended Introduction, Section 4, and Conclusion to clarify this, and added new experiments to fill the gaps in our ablations of the influence of task structure vs the length of the search trace on the efficiency regime.
[W1] “regular and modular Countdown differ in numerical ranges and solution lengths”
We note that if either the numerical range or solution length were a factor between regular and modular Countdown, we would expect degradation in efficiency for both SO and SA when moving from regular to modular Countdown, since both have to learn the same modular arithmetic and the same solution lengths, so both will be affected by the changes. However, our evidence shows SA efficiency across regular and modular stays nearly the same, while SO efficiency dramatically worsens. Thus, we believe this evidence suggests that changing the arithmetic or solution length is not a factor.
[Q2/W2] “Could the relatively weak performance of SO in Figure 3 be related to limited model capacity?“
To explore this question, we ran additional experiments using a Llama-3.2-1B-Instruct model as the underlying model. We updated Section 4 of the paper with the new results, highlighting them in the new Figure 4 under Llama 3.2 1B plots.
Our results show that, overall, SO maintains poor sample and compute efficiency compared to SA. Pretrained Llama with SO supervision does not generalise even after seeing 20M Countdown puzzles, similar to GPT2. Simplifying the task does improve its sample efficiency; however SA improves too, maintaining the efficiency gap between SO and SA. This suggests that extra capacity and pretraining cannot improve learnability if the task representation does not guide gradient descent towards an algorithmic solution. Simplifying the task, or adding algorithmic traces under SA supervision, seems to be a better way to achieve learnability and efficiency on Countdown.
[Q3] “Could the authors clarify the choice of DFS and SoS as the main comparison methods for Countdown? [...] To what extent can the effect of search trace quality be isolated from these other factors?”
We chose both DFS for Countdown and A* for mazes because they are the most or nearly most optimal search algorithms in their respective domains, measured by the number of node expansions. For example, we see that: On mazes, A* averages 408 steps, while DFS averages 476 and BFS 540 On Countdown, DFS averages 15 steps on modular (depth 2) and 25 steps on Gandhi (depth 3), while best-first with tuned heuristics averages to 17.6 steps and BFS to 25.6 steps.
We include SoS trace since Gandhi et al. (2024) introduced it as a search trace for Countdown, which since then was used in follow-up works as a baseline (Qin et al., 2025); thus, we treat it as a baseline trace from the prior work, and include it in order to compare and contrast our results to it.
References
Gandhi, Kanishk, et al. "Stream of search (sos): Learning to search in language." COLM (2024).
Qin, Tian, et al. "To backtrack or not to backtrack: When sequential search limits model reasoning." COLM (2025).