- 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 in Algebraic Normal Form (ANF). At each depth , the model is given a prefix of previously revealed monomial terms along with a batch of new binary input-output observations (), and must identify the unique -th monomial term .
Critical strengths
- 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 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 scales (proven in Appendix C and validated via Bayesian estimators in Figure 3). This provides a clean testbed for isolating multi-variable state tracking.
- Insightful Mechanistic Ablations ( and Execution Control): Rather than only reporting accuracy drops, the authors map LLM performance to an "effective prefix integration" length using partial-information Estimator (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 despite having the exact working Python script from in context, accuracy immediately collapses to chance (0%–0.4%).
Critical weaknesses
- 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 requires zero novel rule recombination as increases. The same 10-line Python script (looping over the prefix to XOR the mask and intersecting supports where ) solves and . In my view, standalone LLMs collapse at large not because they fail to discover deep concept compositions, but because evaluating 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.
- 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 , 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 () at before suddenly jumping to at , whereas without tools it achieves at . Why does giving tools to 30B-Thinking hurt its performance at shallow depths () and why does its tool-assisted accuracy increase with depth?
Questions for authors
- This is related with weakness #2: Why does 30B-Thinking with tools perform worse than 30B-Thinking without tools at , and why does its accuracy increase dramatically from () to ()? 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?
- 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?
- Since the algorithm to unmask and intersect supports is invariant to , meaning a model with tools only needs to write a single for-loop over the parsed prefix string regardless of whether or , how do you justify framing as "compositional reasoning depth" rather than simply data/loop iteration width? What happens if each step requires synthesizing a structurally different algebraic operation rather than repeating an identical XOR reduction?
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.