acceptodds
Under review as a conference paper at ICLR 2027

Tool Use Reduces Depth-Induced Collapse in OOD Reasoning

Abstract

Humans can apply ideas learned in one context to substantially different situations. We call this process of searching for and constructing novel recombinations of learned relationships to solve new problems out-of-distribution (OOD) reasoning. The capacity for large language models (LLMs) to support OOD reasoning underpins proposals for generally intelligent systems. However, this property is challenging to measure because most problems admit many decompositions, some involving shallow subproblems and others involving subproblems that may have been memorized from the training data. This makes it difficult to determine how much compositional reasoning a model must actually perform. Uncertainty about training distributions, how to measure a datapoint's distance from a training distribution, and the exponential number of ways to decompose most tasks make it intractable to robustly measure any modern LLM's OOD-reasoning capacity on standard natural-language tasks. In this work, we introduce a benchmark in which a model progressively solves a Boolean circuit over from data. This benchmark is both minimal, isolating OOD reasoning from these confounding factors, and general, as any computable function can be represented as a sufficiently large polynomial. We find that standalone models’ next-step accuracy collapses as depth grows. In contrast, tool use through the synthesis and execution of code prevents this collapse in both small and frontier LLMs. These results indicate that synthesizing tools play a crucial role in supporting OOD reasoning.

Primary area:
foundation or frontier models, including LLMs
Keywords:
OOD, reasoning, llm, tool use, long-horizon reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_gP6rOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how the out-of-distribution (OOD) reasoning capacity of large language models (LLMs) scales with problem complexity. To avoid the ambiguities of natural language tasks such as multiple valid decompositions, varying levels of abstraction, and memorized shortcuts, the authors introduce a controlled, stepwise Boolean circuit reconstruction benchmark over GF(2)GF(2) in Algebraic Normal Form (ANF). At each depth gg, the model is given a prefix PgP_g of gg previously revealed monomial terms along with a batch of K=32K=32 new binary input-output observations (SgS_g), and must identify the unique (g+1)(g+1)-th monomial term tg+1t_{g+1}.

Critical strengths
  1. Rigorous Benchmark Construction: A persistent challenge in evaluating LLM reasoning is that models exploit statistical leakage, memorized subproblems, or shallow heuristics. By formulating a stepwise reconstruction game over GF(2)GF(2) in Algebraic Normal Form (ANF) with fixed-Hamming-weight payloads, the authors guarantee that neither history-only nor row-wise data-only heuristics can succeed as depth gg scales (proven in Appendix C and validated via Bayesian estimators in Figure 3). This provides a clean testbed for isolating multi-variable state tracking.
  2. Insightful Mechanistic Ablations (k∗(g)k^{*}(g) and Execution Control): Rather than only reporting accuracy drops, the authors map LLM performance to an "effective prefix integration" length k∗(g)k^{*}(g) using partial-information Estimator Dk\mathcal{D}_k (Figure 10), quantitatively demonstrating how standalone models fail to integrate growing context. The Execution-Control ablation in Appendix A (Figure 5) cleanly rules out the hypothesis that code generation acts only as a beneficial "structural prior" or self-reflection aid: when execution is disabled at g=32g=32 despite having the exact working Python script from g=31g=31 in context, accuracy immediately collapses to chance (0%–0.4%).
Critical weaknesses
  1. Conflation of Symbolic Execution Load with OOD Compositional Reasoning: The paper's claim is that it measures "OOD reasoning" defined as "searching for and constructing novel recombinations of learned relationships", and that tool synthesis prevents depth-induced collapse in OOD reasoning. However, the task structure across depths g∈{1,…,255}g \in \{1, \dots, 255\} requires zero novel rule recombination as gg increases. The same 10-line Python script (looping over the prefix PgP_g to XOR the mask ⨁j=1gajMj(v)\bigoplus_{j=1}^g a_j M_j(v) and intersecting supports where r(k)=1r^{(k)}=1) solves g=1g=1 and g=255g=255. In my view, standalone LLMs collapse at large gg not because they fail to discover deep concept compositions, but because evaluating 255×32=8,160255 \times 32 = 8,160 monomial evaluations in natural language tokens exceeds transformer working memory. Offloading a known polynomial-time loop to a Python interpreter is externalized arithmetic/symbolic execution, not real OOD compositional synthesis.
  2. Incomplete Experimental Documentation and Unexplained Empirical Anomalies: Reproducibility details promised in the main text are missing from the appendices (e.g., Section 4.3 explicitly refers to Appendix A for full generation, token-budget, and scoring details, which are absent; system/user prompts and tool-use instructions are never shown). Additionally, there are notable anomalies in the results that require explanation: (a). In Figure 4 (Left), 4B-Instruct with tools consistently outperforms 30B-Instruct with tools across all depths (especially at g=31g=31, where 30B drops sharply toward 0.02 while 4B stays above 0.1) (b). In Figure 4 (Center), 30B-Thinking with tools starts with very low accuracy (∼0.1\sim 0.1) at g=1,3,7g=1, 3, 7 before suddenly jumping to ∼0.75\sim 0.75 at g=31g=31, whereas without tools it achieves ∼0.25\sim 0.25 at g=1,3g=1, 3. Why does giving tools to 30B-Thinking hurt its performance at shallow depths (g≤7g \le 7) and why does its tool-assisted accuracy increase with depth?
Questions for authors
  1. This is related with weakness #2: Why does 30B-Thinking with tools perform worse than 30B-Thinking without tools at g=1,3g=1, 3, and why does its accuracy increase dramatically from g=7g=7 (∼0.1\sim 0.1) to g=31g=31 (∼0.75\sim 0.75)? Similarly, why does 4B-Instruct with tools outperform 30B-Instruct with tools across all depths? Is this an artifact of prompt formatting, regex parsing failures, or tool-calling syntax errors in the 30B checkpoints?
  2. This is related with weakness #2: Could you provide the prompt templates (both with and without tools), extraction rules, and the missing generation/token-budget details referenced in Section 4.3?
  3. Since the algorithm to unmask y(k)y^{(k)} and intersect supports supp(v(k))supp(v^{(k)}) is invariant to gg, meaning a model with tools only needs to write a single for-loop over the parsed prefix string regardless of whether g=1g=1 or g=255g=255, how do you justify framing gg as "compositional reasoning depth" rather than simply data/loop iteration width? What happens if each step gg requires synthesizing a structurally different algebraic operation rather than repeating an identical XOR reduction?
Reviewer_D4RWOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces a Boolean reconstruction benchmark with correct intermediate answers supplied to the model. Next-step accuracy deteriorates as the prefix grows, while code execution largely prevents this deterioration. The authors claim that the benchmark isolates compositional depth and demonstrates depth-induced failure in OOD reasoning.

Critical strengths

Correct prefixes separate next-step errors from mistakes accumulated in previous steps.

The execution ablation supports the observed benefit of running generated programs.

Critical weaknesses

Depth is confounded with computational work. Increasing depth also increases prefix length and the number of operations required. The experiments therefore do not isolate reasoning depth as the cause of declining accuracy.

The theory does not establish a sequential lower bound. Showing that a solver needs historical information does not show that it must process that information sequentially. The known terms can be evaluated independently and combined, undermining the claim that no shallower solution exists.

Instance novelty does not establish distribution shift. Random generation makes exact-instance memorization unlikely. It does not establish that the task or its solution algorithm was absent from training, so the claimed OOD interpretation remains unverified.

The execution gain does not establish the claimed new diagnosis. The benefit of executing generated programs is already established. The proposed contribution is to diagnose depth-induced OOD failure; that contribution depends on the depth and OOD claims that the benchmark has not validated.

Questions for authors

What computational model and lower-bound argument establish the claimed unavoidable sequential depth?

How would the results distinguish dependency depth from computational work when input length and operation count are held fixed?

What distribution shift does the benchmark establish beyond sampling new instances?

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

This paper investigates whether large language models can maintain reliable out-of-distribution (OOD) reasoning as compositional depth increases, and whether tool use can mitigate depth-induced performance degradation. The authors introduce a controlled benchmark based on stepwise Boolean circuit reconstruction over GF(2). At each step, the model receives a ground-truth prefix of previously recovered monomials and a set of labeled examples, and must identify the next monomial. The benchmark uses a statistical obfuscation mechanism to discourage shortcut strategies, while providing theoretical guarantees that the next term remains recoverable in polynomial time. Experiments on four Qwen3 models and two frontier models show that next-step accuracy deteriorates significantly as depth increases without tools. In contrast, allowing models to generate and execute code substantially improves performance, particularly for thinking and frontier models. Additional ablations suggest that actual code execution, rather than self-reflection alone, is essential to these improvements.

Critical strengths
  1. A controlled and theoretically motivated benchmark for investigating reasoning failures.

The proposed GF(2) reconstruction benchmark provides a well-defined setting for studying how model performance changes with increasing reasoning complexity. Its statistical obfuscation mechanism, theoretical recoverability guarantees, and exact-match evaluation make it possible to distinguish failures of the model from insufficient information in the task itself. This controlled formulation is a meaningful contribution because measuring compositional reasoning depth in natural-language benchmarks is inherently difficult.

  1. Strong empirical evidence for the benefits of executable tools.

The experiments demonstrate a substantial and consistent performance gap between tool-enabled and standalone models. For example, at depth 255, the two frontier models achieve 44/46 and 49/50 correct predictions among completed tool-enabled requests, compared with 1/100 and 0/100 without tools. The execution-control ablation further strengthens the finding by showing that retaining previously generated code and allowing additional revisions does not recover performance when execution is disabled. These results provide compelling evidence that externalizing symbolic computation can substantially improve reliability on the proposed benchmark.

Critical weaknesses
  1. The benchmark does not convincingly isolate compositional reasoning depth from increasing computational and contextual demands.

Although the authors interpret the observed performance degradation as depth-induced reasoning collapse, the evaluation provides the model with the correct prefix at every step rather than requiring it to construct the entire reasoning trajectory. Consequently, increasing depth primarily increases the amount of historical information that must be processed and the number of symbolic operations required to remove the prefix-dependent mask.

This raises an important distinction between failures caused by sequential compositional reasoning and failures caused by processing increasingly long inputs or performing more extensive symbolic computations. The benchmark does not include sufficient controls to disentangle these factors. Moreover, because the previous steps are supplied as ground truth, the experiments do not directly measure error accumulation across model-generated reasoning steps.

This limitation is consequential because the paper's central contribution depends on interpreting the observed degradation as evidence of a general depth-induced collapse in OOD reasoning.

  1. The generality and novelty of the conclusions about tool use remain insufficiently established.

The experimental evaluation is concentrated on a single synthetic task family, with the main LLM experiments using a fixed payload dimension, polynomial degree, and number of labeled examples. This task is particularly amenable to code execution because its solution involves deterministic Boolean operations that can be implemented by a relatively simple and reusable algorithm.

While the results convincingly demonstrate that executable code helps on this benchmark, it remains unclear whether the observed effect generalizes to compositional reasoning tasks involving semantic interpretation, uncertain intermediate decisions, or non-algorithmic dependencies.

Furthermore, the central observation that delegating deterministic computation to executable programs improves reasoning performance is closely related to existing work on program-aided reasoning. The paper would benefit from more clearly establishing what new understanding its experiments provide beyond this established principle.

These limitations weaken the broader claim that tool synthesis prevents depth-induced collapse in OOD reasoning generally.

Questions for authors
  1. How do the authors distinguish the effects of compositional reasoning depth from those of increasing prompt length and symbolic computational workload? Could the authors provide length-matched or computation-controlled experiments to demonstrate that the observed degradation is specifically attributable to compositional depth?

  2. Since each evaluation step receives a ground-truth prefix, to what extent do the results characterize failures in genuine multi-step reasoning? Have the authors evaluated complete reconstruction trajectories in which models must generate and maintain their own intermediate solutions? Such results would materially strengthen the connection between the benchmark and the paper's claims about reasoning depth.

  3. How sensitive are the observed trends to variations in payload dimension, monomial degree, and sample count? Additionally, can the authors provide evidence from another compositional task family to establish that the findings are not primarily driven by the particular suitability of GF(2) reconstruction for executable symbolic computation?

Comments on the paper

3 comments

Thank you for your review of our manuscript. We appreciate your identification of editorial issues requiring correction and phenomena warranting further explanation, all of which we would address in a revised manuscript. Given the initial ratings, however, we believe that resolving the more fundamental concerns regarding the rationale for our design choices and the significance of our contributions is the priority. Accordingly, in keeping with ICLR’s guidance on brevity and given the overlap among reviewer comments, we have chosen to focus our response on these central concerns in a summary rebuttal.

We do not know if this task or the algorithm to solve this was present in the training distribution so none of the examples in the benchmark are necessarily “out of distribution.”

While it is possible (though we find it unlikely) that these models included the exact algorithm to solve this task in their training data, it is immaterial to the work because an LLM's familiarity with an algorithm does not imply that all instances of its application are equally in-distribution. What matters is that the LLM has learned to solve small instances of the problem, as validated in Figure 4, and that we can be confident that deeper instances are progressively further out-of-distribution.

This distinction rests on how we interpret the notion of a problem being out-of-distribution. It is impossible to determine exactly how far a given input lies outside the training distribution because we do not know the individual data points used during training. Even if we did, there is no objectively correct way to define the underlying distribution from which those data points were sampled, nor can we establish how representative the observed data are of that distribution. Nevertheless, there is a useful intuition communicated through the phrases in-distribution and out-of-distribution, which we attempt to communicate on lines 131–136 and Figure 4. One cannot expect a model to generalize to a new problem if its training distribution provides neither the requisite knowledge nor a means of inferring it. Generalization therefore entails learning primitive ideas, such as the capitals of countries, and transformations, such as logical deductions, from the training distribution, and developing the capacity to select useful knowledge and transformations in a way that supports correctly to solve novel problems. We thus distinguish in-distribution from out-of-distribution problems based on whether the reasoning process required to reach a solution, including the selection and application of relevant transformations, was sufficiently represented in the training distribution for the model to learn it.

While this still does not allow us to specify exactly how far out of distribution a particular problem is, it provides a useful way to compare how far out of distribution two similar problems are. In particular, a problem becomes increasingly out-of-distribution when it requires combining transformations that rarely occur together in training or increasing the number of transformations needed to reach a solution. The first condition is fairly intuitive if we think of the selection of transformations in a given context as being influenced by a prior over which transformations have been applied in similar contexts during training. The second condition is somewhat less intuitive but equally important. While individual transformations may be simple, selecting and applying them correctly requires tracking the accumulated reasoning state across the full depth. Learning to do so at greater depths therefore requires training examples that capture the full reasoning context, rather than just the individual transformations. However, longer reasoning sequences are composed of shorter subsequences, making deeper problems necessarily less common than their constituent subproblems and therefore less well represented in the training distribution, if at all.

There is, of course, some nuance here: if a model were trained predominantly on long problems and tested on shorter problems requiring different types of transformations, this relationship might not hold. However, our benchmark controls for this by ensuring that all problems require the same types of transformations, applied in the same way, regardless of depth. We are also highly confident that longer instances of these problems were absent from training, as the benchmark was developed after the tested models’ reported knowledge cutoffs. Indeed, even if all 40 trillion training tokens were devoted to this task, the probability of encountering a single instance at even a relatively shallow depth would be comparable to that of being struck by lightning every day for a week and a half.

It is not fair to call execution of an algorithm reasoning, and this metric conflates computational work with reasoning depth.

Reasoning involves evaluating what step to take next based on information from previous steps. Every reasoning process, whether performed by a human or an LLM, relies on some procedure for making this decision. This involves identifying useful heuristics to influence what next steps should be and applying them. Even when we do not know what procedure a human is following, there must be some mechanism guiding each step; otherwise, the process would be random.

Our benchmark differs in that the algorithm is known and must be followed to solve each step. This is an important design choice that allows us to verify intermediate steps in polynomial time. Allowing multiple solution paths or problems without efficient verification procedures would make such analysis combinatorially intractable. The benchmark therefore isolates a minimal component of reasoning: correctly determining the next step from accumulated information using a known algorithm. Failure at this level reveals a reasoning limitation that would be impossible to identify, though still present, in more complex settings.

As defined in the paper, reasoning depth is the number of preceding reasoning steps required to determine a given step (lines 97–107, 247–255). Each successive decision must therefore incorporate information from an increasing number of prior steps (Eq. 3). Processing this additional information necessarily requires computation. Our algorithm ensures that this computational cost grows polynomially rather than exponentially with depth (lines 324–333; Appendix D), but it cannot eliminate the cost altogether. Thus, the computational work in our benchmark is a necessary consequence of reasoning depth, rather than a separate quantity being conflated with it. The ability to perform the required computation reliably is integral to taking a correct reasoning step. We emphasize this distinction throughout the paper (lines 203–215, 414–417, and 455–460).

You are not well controlling for reasoning depth, the model can solve the problem without reasoning as deeply as you claim.

We admit, we are fairly confused by this point. The benchmark was carefully constructed so that we’d be able to show this. We have noticed that this criticism that LLM’s seem to often bring up when reviewing the paper, and to seems to be a very strong bias they have against it, but we don’t think this perspective has much merit.

We designed the benchmark to enforce sequential reasoning steps through one-time-pad-style masking, drawing on the only encryption mechanism known to achieve information-theoretic perfect secrecy [Shannon, 1949]. Our setup differs from Shannon’s original formulation in a small number of ways, most notably in reusing the same mask across multiple inputs. However, the number of observations is sufficiently small relative to the dimensionality of the problem that the resulting mutual information remains negligible. We establish the relevant guarantees mathematically (Eqs. 3–4, Lemma 3.1, Lemma C.2, Corollary C.3, and Appendix D) and validate through simulations that correlations across observations provide negligible practical advantage as reasoning depth increases (Figures 3, 8, and 9). It’s possible we’ve missed something, and would really appreciate it if you could suggest what specific evidence we are missing and how to fix it, but we feel this point is very well supported by existing work. It’s possible this prior is from LLMs mixing up how information within a step combined from past steps vs. the process of actually getting to that step? But it actually doesn’t matter what order the information is used within the step, since in order to get to that step, all prior terms must have already been uncovered according to our benchmark design.

We are particularly puzzled by reviewer D4RW’s comment that “The theory does not establish a sequential lower bound. Showing that a solver needs historical information does not show that it must process that information sequentially. The known terms can be evaluated independently and combined, undermining the claim that no shallower solution exists.” We suspect this concern may reflect a confusion between how information is processed within a step and the sequential process required to reach that step. Our construction does not constrain how a solver combines information once it is available; rather, the masking ensures that the information required at each step cannot be recovered without first uncovering the preceding terms.

We are also unsure whether the reference to a “sequential lower bound” concerns our decision to evaluate individual steps rather than the probability of solving an entire sequence. This distinction is central to our benchmark design. By supplying the correct preceding steps, we measure the probability of successfully completing the next step as a function of reasoning depth, independently of accumulated errors. This is a strictly easier task than solving the entire sequence: even if the probability of success at each step remains constant, the probability of completing the full sequence without error decreases multiplicatively with depth. Evaluating complete sequences would therefore conflate error accumulation with a deterioration in per-step performance at greater depths. Our evaluation isolates the latter, which is a theoretically important and distinct property, including in the analysis of the Diligent Learner.

This paper is not novel because we already know LLMs are better with tools.

We do not claim to have discovered that tools improve LLM performance. This is well established, and we cite much of the relevant literature (lines 183–199). Our contribution is theoretical: we develop a method to measure whether the probability of successfully completing the next reasoning step catastrophically degrades as reasoning depth increases (lines 77–107, 203–215). The assumption that this probability remains bounded above a non-trivial constant underlies the efficiency guarantees of scalable reasoning frameworks such as the Diligent Learner, yet had not been empirically validated for LLMs.

Importantly, this is distinct from the observation that solving longer problems becomes less likely as the number of steps increases. If stepwise success probability remains bounded above a non-trivial constant, verifiers can identify incorrect partial solutions and enable efficient search over increasingly deep reasoning paths. We show that standalone LLMs fail to maintain this property on our benchmark, even when provided with the correct preceding steps, while tool execution substantially mitigates the collapse over the depths tested. Our findings therefore identify a fundamental limitation of standalone LLMs that challenges an assumption underlying proposals for scalable reasoning, and demonstrate how tool augmentation can address it.

Although code execution is well suited to our benchmark, other problems may benefit from different tools. This suggests that the capacity to autonomously construct, select, and reuse appropriate tools may be important for building systems capable of sustaining reasoning over increasingly complex problems. Existing coding agents demonstrate aspects of this capacity, but persistent tool reuse and integration remain important challenges.

Regards,

The authors.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.