acceptodds
Under review as a conference paper at ICLR 2027

Is In-Context Search Worth Its Compute?

Abstract

Training language models on search tasks can be substantially improved by providing supervision via search-augmented (SA) intermediate traces that imitate sequential search. Yet, this requires processing longer sequences than solution-only (SO) training, and prior results leave it unclear when this additional supervision is compute-efficient. We therefore ask: when is learning to imitate search more compute-efficient than learning solutions directly? We study this question on maze navigation and Countdown by systematically varying three factors: training scale, the structure of the underlying search problem, and the structure of the intermediate supervision. We identify two different scaling regimes. On maze navigation, SO supervision reaches low error with less training compute than search imitation; we term this a search-optional regime. On regular Countdown, SA supervision with depth-first search traces is substantially more compute-efficient than SO across the training budgets we evaluate; we term this a search-efficient regime. The advantage of search traces increases on modular Countdown, where the magnitude-based heuristics perform at chance level. Finally, training on incomplete search records reduces the efficiency advantage of SA learning, while semantically unrelated traces behave differently across tasks. These results show that the relative efficiency of SA and SO supervision depends jointly on training scale, problem structure, and supervision quality. Exploiting this insight, we show that selective SA supervision achieves low error with less training compute in joint training on both tasks than uniformly applying either SA or SO supervision.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
search, scaling, transformers

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_L5RzOpenReview ↗
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
  1. 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?
  2. 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?
  3. 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

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).

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.

Reviewer_kXoLOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper compares search-trace imitation with training on successful solution steps, varying model size and training data. Complete DFS traces remain compute-efficient on Countdown, while solution-only training becomes cheaper on mazes. The authors investigate these differences through modified puzzles, alternative traces, and joint training.

Critical strengths

The compute comparisons account for the cost of longer search traces and strengthen the solution-only baselines.

Five-seed experiments support the main performance findings, including the persistent DFS advantage on Countdown within the tested budgets.

Critical weaknesses

The paper measures an existing trade-off more thoroughly, but does not establish a new training principle. Training on search traces, scaling solution-only training, and finding task-dependent advantages are already established. This paper adds larger experiments and compute comparisons. Those measurements are useful, but the broader contribution depends on explaining why the rankings change and what another researcher should do differently because of that explanation.

The proposed regimes do not tell when to use search supervision. Calling a task “search-optional” or “search-efficient” records which format won the experiments. The paper does not establish a problem property that predicts that outcome. A researcher facing a new task must still construct the traces and train both alternatives. The categories therefore summarize the results without supplying a reusable rule for designing training.

The paper does not establish whether the models learn different reasoning algorithms. A model trained to output successful solution steps may still perform search internally. Its accuracy does not establish that it relies on shortcuts, just as poor accuracy does not establish that it cannot learn search. The experiments compare training formats; they do not establish the claimed distinction between learning shortcuts and learning to search.

Questions for authors

What evidence distinguishes internal search from shortcut learning in the solution-only models?

What property of a problem predicts which supervision format will be more compute-efficient?

1 comment

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.

[Q1/W3] “What evidence distinguishes internal search from shortcut learning in the solution-only models?”

We do not claim that SO models cannot in principle learn to search internally. In fact, our evidence on mazes suggests that they can search over an in-context graph since they generalise in-distribution. Prior work on graphs suggests SO models learn to search in parallel across vertices to solve graph connectivity problems and generalise to new graph configurations (Saparov et al., 2025). However, our suggestion about SO model learning shortcuts on Gandhi et al. (2024) Countdown is based on the fact that it requires 200x more data to generalise in-distribution. We then ask if such inefficiency can be attributed to SO models attempting to memorise heuristics of every state and digit instead of relying on an algorithmic solution. We support our view with the efficiency of SA, which learns an algorithmic solution explicitly by behaviour cloning, and does not require so much data to generalise.

We then provide evidence for our hypothesis that SO relies on heuristics and shortcuts in Gandhi’s Countdown by showing that if certain heuristics are removed (moving from Gandhi to our modular variant), SO efficiency degrades dramatically, while SA efficiency does not change. If both SO and SA relied on heuristics, their efficiency would suffer in tandem; conversely, if SO did not rely on heuristics, its efficiency would not change between the variants, since the structure of the problem does not change.

[Q2/W2] “What property of a problem predicts which supervision format will be more compute-efficient?”

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 on the efficiency regime.

[W1] “Training on search traces, scaling solution-only training, and finding task-dependent advantages are already established.”

We agree with the reviewer that these questions have been investigated in prior works that established certain advantages and disadvantages of SO and SA supervision. However, prior works do not provide a coherent picture, and multiple works contradict each other;. Thus, our goals are to (1) clarify the claims of prior works by showing them in the context of a unified and controlled scaling experiment, which should resolve the ambiguities about the utility of search traces, and (2) suggest how different factors in problem structure and representation can affect the results.

For example, behaviour cloning of A* in mazes was introduced by Lehnert et al. (2024) with a claim that search traces improve performance and efficiency; Su et al. (2025) then showed that the models can switch between SO and SA without loss in performance; Valmeekam et al. (2026) contradicted both by showing that traces do not have to be semantically relevant. Without our study, a researcher approaching this setup does not find an answer in the literature about what search traces actually do in this setup, and whether they are required. We answer this by showing the search traces are not required, and so the answer to whether SO or SA is better is sensitive to training configuration.

This work also addresses a gap in the literature around comparisons between SA and SO models across different environments from the perspective of sample and compute efficiency, which has not been addressed before, and attempts to show how changing different factors affect the learning regime. Although this work represents an initial first step in properly understanding sample and compute efficiency of SA, it nevertheless provides the first evidence and opens new questions about how researchers should train and evaluate search-augmented models on synthetic planning problems.

References

Saparov, Abulhair, et al. "Transformers struggle to learn to search." ICLR 2025.

Gandhi, Kanishk, et al. "Stream of search (sos): Learning to search in language." COLM 2024.

Lehnert, Lucas, et al. "Beyond a*: Better planning with transformers via search dynamics bootstrapping." COLM 2024.

Su, Andy DiJia, et al. "Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces." ICLR 2025.

Valmeekam, Karthik, et al. "Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokens." TMLR, 2026.

Reviewer_1nrvOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the scaling behavior for training with search-augmented traces overs solution only traces, for synthetic benchmarks with varying level of in-context state graph information, solvability by heuristics rather than learning. Through controlled evaluation, the paper observes three separate regimes from search-optional to search-efficient.

  1. Maze navigation, where both in context graph information and heuristics are available, is search-optional: Solution-only traces dominate search-augmented traces both in training efficiency and in samples needed to reach perfect performance, but for undertrained setting with imperfect performance, solution-only has worse sample complexity than search-augmented traces
  2. Countdown, where in-context graph is not available but heuristics are effective, is more search-efficient: search-augmented traces become beneficial in both training efficiency and in samples needed to reach perfect performance, but for heavily undertrained setting with close-to-zero performance, solution-only has better training efficiency than search-augmented traces.
  3. Finally, their proposed modular countdown, which is a strictest setting with no in-context graph information nor usable heuristics, is the most search-efficient: search-augmented traces become beneficial in both training efficiency and in samples needed at all performances.

On top of these results, the authors additionally investigate the effect of quality of traces by adding a mixture of suboptimal traces with swapped search from other problems. This by definition are random irrelevant traces that does not help solving the current question.

  1. They observe that suboptimal traces can only reach perfect performance in search-optional regimes, i.e., in maze navigation. This is intuitively because the model learned to ignore the irrelevant traces.
  2. By contrast, in search-efficient regimes, including suboptimal traces significantly harms the converged performance, and degrades both training efficiency and sample complexity compared to search-augmented training, even making countdown and modular countdown search-optional.
  3. Another surprising observation is that, for search-efficient regimes, including suboptimal traces can boost performance compared to solution-only training. This intuitively says trajectories that contain useful logical skills for solving the task, despite being irrelevant to the question at hand, can improve reasoning.

These results shed light on the mystery in prior works on the benefits of irrelevant traces, and point towards separating search-optional and search-optimal regimens, and comparing at training FLOPs parity rather than at fixed sample size or training FLOPS.

Finally, the authors also construct an informed data mixture with optionally expanded search trajectory, intuitively including search for search-efficient tasks, and using solution-only for search-optional tasks. They observe that such data mixture consistently achieves better training efficiency and uses fewer samples across different performance levels.

Critical strengths
  • I find the paper very well-written and the in-depth analysis enlightening.
  • The benchmark designs and data mixture variations elegantly controlled the availability of in-context graph and availability of heuristics.
  • I especially enjoyed reading about the new design of modular countdown to reduce effectiveness of heuristics, and about the suboptimal traces experiments that confirmed prior observations, cleared doubts in prior works, and offered intuitively convincing explanations and ways to separate regimes to aid inclusion choice of search trajectories.
Critical weaknesses
  • The paper investigates regime separation for search-efficiency, yet there is only one problem instance for each regime. Therefore it is it is hard to assess whether the conclusions for one regime generalize to beyond the single tested problem.
  • Although the controlled maze to countdown benchmark designs intuitively separate availability of in-context graph, it also introduces many confounds such as change of tasks. Therefore, this transition is less natural compared to say, the controlled variation of heuristics by changing from countdown to modular countdown. To this end, it would be significantly more convincing to see results for a variation that does not change the task. For example, maze navigation without in-context graph, but just uses a fixed hidden maze and traces generated on top, related to what is investigated in prior papers [a] and [b]. This may also partially address weakness 1 as it adds one additional benchmark for one regime.
  • Additionally, their differences between problem instances in different regimes are largely argued intuitively or qualitatively rather than quantitatively. So it is unclear how to infer the regime that a given problem lies in, or to understand whether a given problem may not lie cleanly in one regime and instead be a mixture of both regimes. This is especially relevant for practical reasoning tasks.

Nevertheless, I understand that addressing weakness 1 and 2 may require heavy training budget, I do not anticipate them fully addressed in the rebuttal period but would appreciate discussions from the authors.

References:

  • [a] Tong, Yao, et al. "Generalization in LLM Problem Solving: The Case of the Shortest Path." ICLR 2026.
  • [b] Noroozizadeh, Shahriar, et al. (2026). Deep Sequence Models Tend to Memorize Geometrically; It Is Unclear Why. ICML 2026.
Questions for authors
  1. How to quantitatively characterize the properties of different regimes? That is, availability of in-context graph and availability of heuristics? Is it possible to assess this for more practical reasoning benchmarks, such as GSM8K or other agentic tool-calling benchmarks? Do the authors believe the results may transfer?

  2. Training configurations: I have a hard time understanding the epoch choices in benchmarks (4 epochs in line 210, 1 epoch in line 269, 10 epochs in line 292), and how they interact with dataset size. Given that the designed benchmarks are largely synthetic, what is the rationale for repeating data relative to say training one single-epoch freshly generated data to avoid the repetition confounding factor?

1 comment

We thank the reviewer for a thorough, careful read of the paper and for the insightful comments. We are glad you found the paper interesting and gained a deeper understanding of the problem, which is the result we were hoping for. 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.

[Q1/W2/W3] “How to quantitatively characterize the properties of different regimes?”

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 on the efficiency regime.

[Q1] “Is it possible to assess this for more practical reasoning benchmarks, such as GSM8K or other agentic tool-calling benchmarks?”

We agree with the spirit of the request and recognise this as a limitation. However, we deliberately decided to focus on synthetic environments in order to have precise control over the problem parameters, such as difficulty and size, and minimise interference from other factors unrelated to search. Additionally, it is challenging to find practical tasks that also are solved with search at the moment. GSM8K does not require search, as the solution involves only one valid action at each reasoning step.

Tool calling benchmarks are much better suited for this investigation; however, they do not come with search traces. Due to the vast combinatorial search space, generating a tractable tree for these tasks is not trivial and is a research project on its own. We therefore add this as a limitation to the paper to the discussion in Conclusion and propose a tool-calling benchmark as future work.

[Q2] “What is the rationale for repeating data relative to say training one single-epoch freshly generated data to avoid the repetition confounding factor?”

We apologise for the confusion caused by this.

For maze: we generated 3M unique puzzles for training, which took 38GB on disk. After training for 1 epoch, all models remained undertrained. To save storage and avoid lengthy regeneration of a larger dataset, we trained our models for 4 epochs on each dataset fraction of the 3M dataset, to quadruple the number of training steps. This method follows Muennighoff et al. (2023), who showed that repeating data in language models up to 4 epochs results in approximately the same validation loss as training on unique data.

For Countdown: we generated 20M unique puzzles for training, which took less time than 3M mazes, and cost only 14GB of storage. Thus, we decided to not repeat data for Countdown training and instead train all dataset fractions for 1 epoch. However, many SO models did not converge on Countdown even after seeing 20M samples. We then repeated 20M samples 5 and 10 times (epochs) to test the impact of more training steps. The goal was to determine how much more data beyond the given training budget SO models require to generalise.

Therefore, to summarise:

  • Repeating maze for 4 epochs produces approximately the same validation loss as training for 1 epoch on 4x more data, so the trends in validation loss and error rates between maze task and Countdown task can be compared directly.
  • The additional training with 20M Countdown puzzles for 5 and 10 epochs beyond the 1-epoch main training budget was to test how much data may actually be required for SO models to generalise. We shade these experiments with a grey background where they are present on a plot.

[Update, 14/11]: Following the reviewer's feedback about unclear motivation for different training epochs between tasks, we amend the Section 4.1 of the paper with clarification about our choice to train on maze navigation for 4 epochs.

References

Muennighoff, Niklas, et al. "Scaling data-constrained language models." Advances in Neural Information Processing Systems 36 (2023): 50358-50376.

Comments on the paper

1 comment
AuthorsOpenReview ↗

A comment on the factors in the task structure that predict the efficiency regime

Dear reviewers,

We recognise that the original submission has not been clear enough about which factors affect the efficiency regimes, and how. This is evident from the questions raised by all the reviewers, and which we took extra time to address thoroughly. We also recognise that we were missing a more granular ablation of factors between maze navigation and the regular Countdown, and only included a systematic ablation of a single factor, namely the presence of heuristics. Hence, the effects of other factors (the presence of the graph in context, complexity and locality of the transition function) were not sufficiently isolated in the paper.

To study this more carefully, we conducted additional ablation experiments on Countdown where we vary the difficulty of the task by (1) adding states into the context, to mirror in-context state representation of the maze (walls), and (2) simplifying the state transition function to use only addition and subtraction (i.e., no multiplication and division), to mirror the increment/decrement transition function of the maze. We also repeated these ablations with Llama-3.2-1B-Instruct to test if the search-efficient regime holds for the Countdown task with a larger pretrained model. We include the new results as a new subsection in Section 4, and show them in a new Figure 4.

Our results show that training SO supervision becomes more efficient for both GPT2 59M and Llama 3.2 1B, as the Countdown representation and structure are progressively simplified and moved closer to the maze’s. GPT2 with SO also closes the efficiency gap to SA under progressive simplifications. (To remind: we classify a task as search-efficient if search-augmented supervision (SA) outperforms solution-only supervision (SO) at any scale.) On the simplest Countdown - the Gandhi Countdown where the task representation is augmented with intermediate states and operations are restricted only to addition/subtraction, making it the closest variant to the maze - we find almost no gap in efficiency between SO and SA. However, switching to Llama 3.2 shows that the gap persists, as SA with Llama 3.2 also gains efficiency as the task is simplified. Surprisingly, the 1B-parameter Llama 3.2 with SA supervision becomes more FLOP-efficient than GPT2 with 59M parameters on the simplest variant, thanks to its extreme sample efficiency on that task (which is OOD for Llama). This demonstrates that the task remains search-efficient despite simplifying interventions that intuitively ought to benefit SO more than SA.

Our explanation for persistence of search-efficient regime in Countdown is that task difficulty, which is determined by the presence of intermediate states in context, complexity of the transition function, and the presence of heuristics, is not the only factor that determines the efficiency regime. The other factor, which is implicitly varied between maze and Countdown, and which we briefly discuss in Conclusion, is the length of the search traces: the longer the trace, the more FLOPs the model will use, and the more data it might need to generalise. Maze traces are on average much longer than the traces of the simplest Countdown variant (2048 vs 93 tokens). Taking task difficulty and trace/solution length as two axes, our central hypothesis can be re-stated as follows: there is a set of simple but long tasks (e.g., maze navigation) for which search traces are unnecessary for efficient learning but require a substantial compute budget, thus making such tasks search-optional since SO can learn to solve these tasks more efficiently. All other types of tasks - easy tasks with short traces (e.g., Gandhi Countdown with in-context states and restricted ops), difficult tasks with short traces (e.g., modular Countdown with 3 inputs), or difficult tasks with long traces (e.g., modular Countdown with 4+ inputs) - will be search-efficient.

We appreciate that this might not have come across clearly in the paper. 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 on the efficiency regime. All additions and edits are highlighted in blue.

[UPDATE, 17/11]: we updated the Appendix with the data from new experiments, and aligned its formatting with the main text.

[UPDATE, 18/11]: added "4.5 Limitations" subsection to the "4 Experiments" section, per advice of the reviewer 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.