acceptodds
Under review as a conference paper at ICLR 2027

Algorithmic Depth Predicts the Sample Complexity of Generalization

Abstract

How much training data does a model need before it generalizes? We hypothesize that the answer depends on how difficult the task is, and test this hypothesis on compositional tasks, where task difficulty is the complexity of the algorithm that generates the data. Across thousands of trained models, sample complexity grows exponentially with algorithmic depth, the number of sequentially dependent steps, following a trend that predicts deeper tasks before training. However, depth describes the algorithm, not the learning problem. Supervising intermediate steps during training, while the model must still generate them at test time, reduces sample complexity by orders of magnitude for the same algorithm. We find that sample complexity is set by the unobserved algorithmic depth, the longest run of steps without supervision, so where supervision is placed matters more than how much is provided. The same holds for pretrained language models on English versions of our tasks, real programs, and GSM8K math word problems. Our results show that training data has a computational structure as well as a size, and point to a less discussed advantage of chain-of-thought training, which lowers sample complexity by shortening the reasoning a model must learn on its own.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Sample Complexity, Generalization, Grokking

Reviews

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

The paper studies how the structure of a task and its training supervision affect the amount of data a model needs to generalise. The authors find that data requirements grow approximately exponentially with the number of sequential steps when only the final answer is supervised (finding obtained by using compositional tasks with known sequences of operations). And that providing intermediate results during training reduces these requirements, even though the model must generate those results itself at test time. The authors propose the longest run of operations between supervised outputs as a key predictor of sample complexity, showing that the placement of intermediate supervision can matter more than the number of supervised steps. The central claim is that training examples derive their value not only from their number, but also from how they break a computation into learnable steps.

Critical strengths
  • The paper’s strongest experiment compares models learning the same task with the same number of supervised outputs, but with those outputs placed at different steps. One arrangement needs around five to six times more training data than another, showing that the point where intermediate answers are provided can make a large difference even when their number stays the same.

  • The paper provides a useful way to understand the above mentioned difference: look at the longest sequence of steps the model must learn without an intermediate answer. While this doesn't explain every result, it suggests that training examples may be more helpful when they break long computations into shorter parts, rather than simply include more steps.

  • The results also suggest that chain of thought training can help models learn from fewer examples, beyond giving them more computation at inference time. Since models generating the same number of intermediate outputs still need different amounts of training data, the benefit cannot be explained by extra generated tokens alone.

Critical weaknesses
  • I think that the evidence for an exponential relationship is convincing within the tested tasks, but its broader meaning is a bit unclear. Increasing algorithmic depth also increases the number of possible compositions, so it's difficult to separate the effects of these two changes. The depth-six experiment looks less strong than the main paper suggests: the appendix reports that the authors changed the learning rate schedule and that only 8 of 86 runs met the training-fit criterion. As the authors acknowledge, this result supports the observed trend but it doesn't really provide a clean independent test of it.

  • Unobserved algorithmic depth explains much of the variation in sample complexity, but I thik it doesn't explain all of it. The appendix shows that models can need different amounts of data even when the longest unobserved run is the same. For example, it matters whether that run starts from the input or from an answer the model has generated, where earlier errors can affect later steps. In the Python experiments, leaving an additional step unsupervised increases data requirements by about 3 times without changing the longest run. These results suggest that unobserved depth is an important predictor, but I think that the claim that it “sets sample complexity” gives too little weight to other features of the learning problem.

  • The paper shows that the place where to add the supervision matters, but it doesn't establish that placement is generally more important than quantity. The comparisons between schemes with the same number of supervised outputs are a strong part of the study: changing where those outputs appear produces large differences in data requirements. But the Python experiments also show that adding supervision can substantially improve learning without shortening the longest unobserved run. Maybe a possible more accurate conclusion would be that the placement of supervision matters in addition to its amount, and that their relative importance depends on the task.

  • The experiments don't really separate the reasons why intermediate supervision helps. The fact that almost all models fit their training data rules out a simple failure to learn the training examples, but it doesn't rule out a possible role for optimisation, for example. Intermediate supervision could guide training toward a solution that generalises better, even when a model trained only on final answers reaches the same training accuracy. In a similar way, comparing schemes with the same number of outputs shows that extra generated tokens can't explain the placement effect, but it doesn't measure how much extra test-time computation contributes to the overall benefit of full supervision.

Questions for authors

The appendix shows that schemes with the same unobserved algorithmic depth can still require substantially different amounts of data, particularly in the Python experiments. Could you clarify under what conditions the longest unobserved run is sufficient to predict sample complexity, and when other factors, like the number of unsupervised steps or error propagation, also need to be considered?

3 comments
AuthorsOpenReview ↗

Author Response (1/2)

We thank the reviewer for the thoughtful review and constructive comments. We appreciate that the reviewer recognizes the importance of our supervision-placement experiments, the predictive role of unobserved depth, and the distinction between the learning benefits of CoT and additional test-time computation. We address the concerns below.

Increasing depth also increases the number of possible compositions, making their effects difficult to separate.

Response: We explicitly investigate this distinction in Appendices B.5–B.7. First, varying the number of operations at fixed depth, our scaling law predicts sample complexity within 30% (B=8–32). Second, holding the number of possible compositions fixed while changing depth produces up to 2.3× differences. Third, chained and parallel compositions with identical operations, inputs, and numbers of possible compositions exhibit substantially different generalization behavior.

These experiments establish that the number of possible compositions matters, but computational structure also influences sample complexity. Our scaling law captures their relationship quantitatively rather than attributing generalization difficulty to depth alone.

The depth-six experiment is less convincing because the learning-rate schedule changed and only 8 of 86 runs fit their training set.

Response: The depth-six prediction was fixed before training, and the measured K50K_{50}=55,337 falls within the confidence interval of the predicted 71,332. We acknowledge the optimization difficulties and treat this as supporting evidence. Importantly, our central conclusion does not depend on depth six: the exponential relationship is established across depths 2–5 and independently supported across four operation types, with growth rates of approximately 5.3–6.7× per step.

Unobserved depth does not explain everything; error propagation and the number of unsupervised steps also matter.

Response: We agree that these factors contribute, and we explicitly study them in Appendix C.5 and Section 6.2. Our central finding is that unobserved depth is the dominant predictor in controlled compositional tasks, rather than the only factor affecting sample complexity.

To quantify this, our additional analysis across 20 supervision schemes (D=3–7, B{8,12}) shows that the scaling law fitted only on outcome-supervised tasks predicts all 20 schemes within 2×, with a typical error of just 1.30×, without refitting. In contrast, predictors based on total depth, supervision quantity, or average unobserved length have typical errors of 2.5–3.5×, even when fitted to these schemes. Adding further structural features improves predictions only marginally.

Thus, despite the additional factors, one simple quantity provides remarkably accurate predictions across supervision schemes without additional fitting. We will clarify the scope of this finding.

The paper does not establish that placement is generally more important than quantity.

Response: Our controlled experiments directly separate these effects. As the reviewer also highlights, changing only the placement of supervised steps can substantially change sample complexity, even when the task and supervision quantity remain identical.

TaskSupervised stepsDunobsD_{unobs}K50
Depth 5{1, 3, 5}255
Depth 5{1, 2, 5}3361
Depth 4{2, 4}274
Depth 4{1, 2, 4}268

Table R1: Effect of supervision placement and quantity. Changing the placement of the same number of supervised steps increases sample complexity by 6.6×, whereas adding a supervised step without shortening unobserved depth improves it by only 1.1×.

These results establish that placement can matter substantially more than quantity in our controlled setting. We agree that their relative importance can depend on the task, and will make this scope explicit.

Training fit does not rule out optimization effects, and matching generated outputs does not isolate all benefits of test-time computation.

Response: Our experiments establish two specific observations. First, 499 of 501 runs fit their training compositions (Appendix A.4), ruling out differences in training fit as the explanation for the observed sample-complexity differences. Second, schemes generating the same number of intermediate outputs at test time still differ by up to 6.6× in sample complexity, so additional generated tokens alone cannot explain the placement effect.

We do not exclude optimization or test-time computation as contributing factors. Rather, our results demonstrate that how supervision divides the computation matters beyond training fit and the number of generated outputs.

AuthorsOpenReview ↗

Author Response (2/2)

When is unobserved depth sufficient to predict sample complexity

Response: The key condition is whether intermediate computations share reusable structure. In our controlled tasks, operations come from the same small set, so learning the longest unobserved computation allows reuse across shorter ones. This explains the accurate predictions across 20 schemes.

In heterogeneous tasks such as Python programs, different steps require different computations, making the number of unsupervised runs relevant as well. Error propagation introduces further variation when computations begin from model-generated outputs.

Thus, unobserved depth captures the dominant difficulty when computations share reusable structure, while additional factors become relevant when that structure is less shared. We will clarify these conditions in the revised paper.

Q1. Under what conditions is the longest unobserved run sufficient to predict sample complexity, and when do other factors matter?

Response: As discussed above, the key distinction is whether intermediate computations share reusable structure. In our controlled tasks, all steps compose operations from the same small set, so learning the longest unobserved run allows the model to reuse what it learns across shorter runs. Consequently, unobserved depth predicts all 20 supervision schemes within 2×, with a typical error of just 1.30×, without refitting.

In more heterogeneous tasks, such as Python programs, different steps involve different computations, making the number of unsupervised runs relevant as well. Error propagation also introduces variation when a computation starts from a model-generated output (Appendix C.5).

Thus, unobserved depth is the dominant predictor when computations share reusable structure, while additional factors become important when that structure is less shared. We will clarify these conditions in the revised paper.

We hope these responses have addressed your concerns and clarified the contributions of our work. If so, we would be grateful if you would consider strengthening your support for the paper. We would also be happy to address any further concerns you may have. Thank you very much for your consideration!

Thank you for your rebuttal. Your explanation that unobserved depth is the main predictor in the controlled tasks (instead of the only factor that matters) I think helps clarify the scope of the paper.

I still have some concerns about the depth-six experiment, since most runs didn't fit their training sets. I agree that it can support the observed trend, but it shouldn't really be presented as a clean independent test. The explanation based on reusable structure is also plausible, but I would separate it from a condition that the experiments have directly established.

Overall I think I will keep my score.

Reviewer_XFaNOpenReview ↗
Rating
1(−1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents an empirical study of how algorithmic depth and intermediate supervision affect sample complexity of a reasoning task. However, the main conceptual claims seem to overlap with prior work. While the empirical observations offer some novelty, I find the overall contribution a bit incremental.

Critical strengths
  1. The paper presents extensive empirical experiments across depth, operation, and supervision formats.

  2. The proposed scaling law from outcome-only supervision predicts the effect of intermediate supervision, validating intuition.

  3. The paper presents a controlled study on the placement of the intermediate supervision.

Critical weaknesses
  1. (Major) My main concern is that the core findings seem to overlap with existing literature, and several closely related works are not sufficiently acknowledged.
  • The finding that sample complexity depends exponentially to compositional depth is not new. [1, 2] both show that in synthetic multihop / compositional tasks, the difficulty of learning scales exponentially with the algorithmic depth.

  • The finding that when intermediate supervision is present, the sample complexity depends exponentially to unobserved algorithmic depth (the length of the longest unsupervised chain) is not new. [3] shows that with CoT, the difficulty of the task depends on the hardest subtask. Since the longest unsupervised chain is obviously the hardest subtask, the intuition follows.

  • While the settings of the above theoretical works may differ from the setting of this paper, the main takeaways of this paper have been largely established.

  1. (Minor) Weak evidence of generalization to real-world settings
  • On GSM8K, the experiments are limited to cases where total depth is 3, and the unobserved depth varies between 1 and 2 (since outcome-only supervision never even reaches the target accuracy). These data points are not sufficient to draw a scaling law plot.

[1] Wang et al., “Learning Compositional Functions with Transformers from Easy-to-Hard Data,” COLT 2025.

[2] Zhu et al., “On the Power of Context-Enhanced Learning in LLMs,” ICML 2025.

[3] Yang et al., “Chain-of-Thought Provably Enables Learning the (Otherwise) Unlearnable,” ICLR 2025.

Questions for authors
  1. Can the authors clarify on the novelty of the findings of the paper?

  2. Does the scaling law generalize to longer reasoning depths on real-world tasks like GSM8K?

6 comments
AuthorsOpenReview ↗

Author Response (1/2)

We thank the reviewer for the thorough review and insightful comments. We appreciate that the reviewer recognizes our extensive empirical evaluation, the predictive ability of the scaling law across supervision schemes, and the controlled study of intermediate supervision placement. We address the concerns and questions below.

The finding that sample complexity depends exponentially on compositional depth is not new. [1, 2] both show that learning difficulty scales exponentially with algorithmic depth.

Response: We agree that prior theoretical work has established important connections between compositional depth and learning difficulty. However, our contribution goes beyond establishing that the dependence is exponential. Wang et al. [1] prove an exponential statistical-query lower bound for a particular compositional learning problem, while Zhu et al. [2] establish an exponential sample-efficiency advantage of context-enhanced learning. Neither provides an empirical scaling relationship that predicts how much training data a transformer needs to generalize as task depth and supervision change.

In our work, we quantify this relationship rather than only establishing its exponential nature. We find that sample complexity increases by approximately 6× more training data per additional step for our primary task. We further show that the growth rate depends on the operations being composed, and that the relationship predicts deeper tasks and changes in the number of operations without refitting.

Thus, our contribution is not simply that deeper tasks require exponentially more data, but that the rate can be measured and used to predict sample complexity before training.

With CoT, learning difficulty depends on the hardest subtask [3]. Since the longest unsupervised chain is obviously the hardest subtask, the intuition follows.

Response: We agree that Yang et al. [3] establish an important theoretical connection between CoT and the difficulty of its hardest subtask. However, this does not directly establish how the sample complexity of trained transformers changes when only selected intermediate steps are supervised, nor does it provide a quantitative prediction for different supervision placements. This is precisely what we study in Section 5. We first fit the scaling relationship using only outcome-supervised tasks. Remarkably, the same relationship predicts sample complexity across 20 intermediate-supervision schemes, spanning depths 3–7 and different numbers of operations, without refitting.

Moreover, we show that two schemes supervising the same number of intermediate steps can differ by up to 6.6× in sample complexity, solely because of where supervision is placed. We believe these results provide an important distinction: prior theory motivates why intermediate supervision can help, while our work quantitatively predicts how much it helps and how its placement changes the data required for generalization. We will expand the related-work section to acknowledge these theoretical contributions more explicitly and make this distinction clearer.

On GSM8K, experiments are limited to depth three, and the available data points are insufficient to establish a scaling law.

Response: We agree that measuring a precise scaling law on real-world reasoning tasks is challenging. Our central question concerns how sample complexity changes with algorithmic complexity, which requires controlling task difficulty independently of other factors. This motivates our controlled compositional setting, consistent with the approach taken by related theoretical and empirical studies. The purpose of Section 6 is therefore not to claim that the exact fitted exponent transfers to real-world tasks, but to examine whether the dependence on unobserved depth persists beyond the controlled setting.

For GSM8K specifically, reliable sample-complexity estimation at larger depths is limited by the available data. Our parsed training set contains 1,892 depth-three problems but only 627 depth-four problems, making it difficult to estimate generalization thresholds across multiple supervision schemes at larger depths.

Nevertheless, the consistent findings across these three settings support the broader observation that leaving longer computations unobserved makes generalization more data-intensive, even when the model and task representation change.

AuthorsOpenReview ↗

Author Response (2/2)

Q1. Can the authors clarify the novelty of the findings?

Response: Our contribution is not simply establishing that sample complexity grows exponentially with depth or that intermediate supervision helps. Rather, we quantify this relationship and show that it can predict the sample complexity of different supervision schemes without refitting.

Importantly, a scaling law fitted only on outcome-supervised tasks predicts all 20 intermediate-supervision schemes within 2×, with a typical error of just 1.30×. We also show that changing only the placement of supervised steps can change sample complexity by up to 6.6×. These quantitative predictions and controlled placement comparisons go beyond the theoretical insights established in [1–3].

Q2. Does the scaling law generalize to longer reasoning depths on real-world tasks like GSM8K?

Response: As discussed above, our most precise scaling-law measurements come from controlled tasks, where algorithmic depth can be varied independently. GSM8K contains only 627 depth-four training problems in our parsed split, limiting reliable sample-complexity estimation at greater depths.

Nevertheless, the dependence on unobserved depth persists beyond synthetic tasks. On English compositional tasks with pretrained Pythia-70M, each additional unobserved step increases sample complexity by approximately 4–5× across depths 3–5. On Python programs with Qwen2.5-1.5B, the same qualitative effect holds for computations up to eight steps.

Thus, while we do not claim that the exact exponent transfers to GSM8K, our experiments support the broader finding that leaving longer computations unobserved substantially increases the data required for generalization.

We will further clarify this distinction between the quantitatively measured scaling law in controlled tasks and its supporting evidence in real-world reasoning settings.

We hope these responses have addressed your concerns and clarified the validity and contributions of our work. If so, we respectfully ask that you reconsider and increase your score. We would also be happy to address any further concerns you may have. Thank you very much for your consideration.

References

[1] Wang et al. (2025). Learning Compositional Functions with Transformers from Easy-to-Hard Data. COLT 2025.

[2] Zhu et al. (2025). On the Power of Context-Enhanced Learning in LLMs. ICML 2025.

[3] Yang et al. (2025). Chain-of-Thought Provably Enables Learning the (Otherwise) Unlearnable. ICLR 2025.

I thank the authors for the detailed response and the additional experiments. The clarifications help, but several concerns remain.

  1. (Major) Novelty and the main contribution of the paper still not clear

the rate can be measured and used to predict sample complexity before training (Author response (1/2))

I’m not sure if I agree with this point. As the authors already mention, the rate is dependent on the task (e.g., “at a rate the task determines” line 241). Among synthetic tasks, the rate ranges between 5.28 and 6.71 (Figure 2 middle); on English tasks, the rate is 4-5 (line 92); on GSM8K, the rate is 3.5 (line 91). So there is no way to predict the exact sample complexity without running some calibration runs to check what the rate is for a given task. However, this is the same procedure that would need to be performed given just the theoretical results that the sample complexity of a reasoning task is exponential with respect to reasoning depth.

As a minor note, the ablation on model size (Appendix B.8) is insufficient. Even though the evaluation tasks range up to 7 steps of reasoning, it does not test beyond 2 layers of transformers and primarily ablates width. It is widely known that the reasoning depth of a model is generally correlated more with the number of layers.

  1. (Major) The GSM8K results (including the new results) need more explanation

In Table R.1 (in the response to Reviewer Lyj6), the authors present a new result where the GSM8K experiments were repeated with standard CoT. Now, every finetuned model underperforms the untrained baseline, and training with more data performs worse in all cases except the “Final answer only” case. Therefore, this experiment is a regime where further training is hurting the model and does not seem to go well with the authors’ narrative that the paper predicts how much data is needed to generalize.

If in the main paper, the trained models were also performing below the untrained baseline, it is unclear exactly what the training was doing to the model. Is the model learning reasoning? Formatting? Generalization? Implicit calculation?

Also, if there is a lack of data beyond depth 3 in GSM8K, did the authors look into GSM-Infinity [1]?

[1] Yang Zhou et al., “GSM-Infinite: How Do Your LLMs Behave over Infinitely Increasing Context Length and Reasoning Complexity?” ICML 2025.

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

This paper investigates how the computational depth of compositional tasks relates to the amount of training data required for generalization. The authors empirically show that, under outcome-only supervision, sample complexity grows exponentially with algorithmic depth in controlled synthetic tasks. They further introduce unobserved algorithmic depth, defined as the longest sequence of operations between consecutive supervised outputs (including the input as step zero), and show that it predicts sample complexity across different intermediate supervision schemes. They provide additional supporting experiments with pretrained language models on English compositional tasks, generated Python programs, and GSM8K.

Critical strengths
  1. Interesting research question: I find the question of how many intermediate steps we need to supervise, and where to place this supervision, interesting. While full CoT supervision is a natural way, obtaining supervision for every intermediate step can be expensive. Understanding how to reduce this supervision while retaining its benefits is a worthwhile direction.

  2. Clean synthetic setting: I like the controlled synthetic setting, where each operation and its intermediate outputs are clearly defined. This allows the authors to systematically study the effect of computational depth and intermediate supervision on sample complexity, while controlling for other factors.

Critical weaknesses

1. Limited and somewhat unconvincing evaluation on realistic datasets.

I find the experiments on realistic datasets less convincing. First, the reported GSM8K accuracy is surprisingly low (17.4% with full intermediate supervision). Qwen2.5-3B achieves around 79% on standard GSM8K evaluation [4]. Although the authors acknowledge that their constrained output format differs from standard evaluation, it is unclear how much of the low accuracy is due to this restriction. I would like to see a comparison with standard CoT evaluation on the same subset of problems to better understand whether the findings hold under more realistic conditions.

Second, on MuSiQue, outcome-only supervision actually outperforms intermediate supervision. While the authors provide a possible explanation involving intermediate information already available in the input, these results raise questions about how broadly the proposed findings generalize beyond controlled synthetic tasks.

Overall, I find the research question interesting, but I remain unconvinced of its practical impact without stronger evidence on realistic reasoning tasks. In particular, it would be valuable to demonstrate that selectively supervising fewer intermediate steps can achieve a meaningful reduction in supervision or inference cost while maintaining performance close to full CoT on benchmarks such as GSM8K. Without such evidence, it is unclear how the proposed insights translate into practical benefits for training reasoning models.

2. Novelty and missing related work.

Several closely related papers are missing from the discussion, particularly Abedsoltan et al. (ICML 2025) [1], Joshi et al. (COLT 2025) [2], and Yao et al. (ICLR 2026) [3]. These works have already studied important connections between CoT supervision, compositional generalization, and sample complexity, including theoretical results. While the characterization of partial supervision through unobserved algorithmic depth is interesting, the authors should more clearly distinguish their contribution from these prior results and explain what additional insights their empirical scaling law provides.

References

[1] Abedsoltan, A., Zhang, H., Wen, K., Lin, H., Zhang, J., & Belkin, M. (2025). Task Generalization with Autoregressive Compositional Structure: Can Learning from D Tasks Generalize to D^T Tasks? Proceedings of the 42nd International Conference on Machine Learning (ICML), PMLR 267, 154–173.
https://proceedings.mlr.press/v267/abedsoltan25a.html

[2] Joshi, N., Vardi, G., Block, A., Goel, S., Li, Z., Misiakiewicz, T., & Srebro, N. (2025). A Theory of Learning with Autoregressive Chain of Thought. Proceedings of the 38th Conference on Learning Theory (COLT), PMLR 291, 3161–3212.
https://proceedings.mlr.press/v291/joshi25a.html

[3] Yao, X., Ren, R., Liao, Y., Ding, L., & Liu, Y. (2026). Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoning. International Conference on Learning Representations (ICLR).
https://proceedings.iclr.cc/paper_files/paper/2026/hash/9990a18179e862042c18dfc856b0e53f-Abstract-Conference.html

[4] Qwen Team. (2024). Qwen2.5-LLM: Extending the Boundary of LLMs. Official Qwen technical blog. Reports 79.1% GSM8K accuracy for Qwen2.5-3B under standard evaluation.
https://qwenlm.github.io/blog/qwen2.5-llm/

Questions for authors
  1. GSM8K evaluation (Clarification): Could the authors clarify which Qwen2.5-3B checkpoint (base or instruction-tuned) and decoding strategy were used? Was it greedy? how about ave@k, pass@k performances?

  2. GSM8K evaluation (Clarification and additional experiment): The constrained output format appears to simplify the required output by removing natural language reasoning and retaining only intermediate numerical values. However, the reported accuracy drops substantially compared to standard GSM8K performance (17.4% versus approximately 79% for Qwen2.5-3B). Why does this seemingly simpler output format lead to such low accuracy? Is the model struggling with the arithmetic itself, or does the constrained format interfere with its pretrained reasoning capabilities? Could the authors compare against standard CoT generation on the same subset of GSM8K problems to better understand this discrepancy?

  3. Generalization beyond synthetic tasks (Clarification): On MuSiQue, outcome-only supervision outperforms intermediate supervision. How should this result be reconciled with the main hypothesis? Under what conditions do the authors expect unobserved algorithmic depth to be predictive of sample complexity?

  4. Partial CoT supervision on larger datasets (Additional experiment): I understand that in real-world reasoning tasks, intermediate steps are not always clearly defined or easily controlled. However, could the authors evaluate their hypothesis on a larger reasoning dataset with available step-by-step solutions? For example, starting with full CoT supervision and progressively removing intermediate steps, while comparing different removal strategies (e.g., random versus evenly spaced) at the same supervision budget. Potential datasets include OpenMathInstruct-2, NuminaMath-CoT, and MathQA. This would help determine whether unobserved algorithmic depth remains a useful predictor of sample complexity beyond synthetic tasks.

5 comments
AuthorsOpenReview ↗

Author Response (1/2)

We thank the reviewer for the thorough review and insightful comments. We appreciate that the reviewer finds our research question interesting and values the clean, controlled experimental setting. We address the concerns below.

The experiments on realistic datasets are less convincing.

Response: Our starting question is simple: How does the amount of training data needed for generalization change with the algorithmic complexity of a task? Studying this directly on real-world tasks is difficult because task difficulty, prior knowledge, and other factors cannot be controlled independently. We therefore start with compositional tasks, where algorithmic depth can be varied while keeping other factors fixed. This is a standard approach in the literature, including related work on compositional generalization [1–3].

However, an important question is whether the findings carry over to realistic reasoning tasks. This motivated our experiments in Section 6, and we have conducted additional experiments to address the reviewer's concerns.

The reported GSM8K accuracy is surprisingly low (17.4%), compared to around 79% for Qwen2.5-3B under standard evaluation.

Response: We agree that the 17.4% accuracy in Section 6.3 is much lower than standard GSM8K performance. This experiment deliberately required the model to output only intermediate numerical values rather than natural-language reasoning, making its absolute accuracy incomparable to standard CoT evaluation.

To address this, we repeated the experiment using standard human-written CoT solutions, with free-form generation, on the same 320 depth-three GSM8K test problems.

Training targetDunobsAccuracy (800 examples)Accuracy (1,565 examples)
8-shot CoT (no fine-tuning)–70.9%70.9%
Full CoT157.8 ± 1.5%57.7 ± 0.6%
CoT, step 1 removed242.5 ± 0.8%40.5 ± 1.6%
CoT, step 2 removed242.5 ± 0.5%38.8 ± 0.0%
Final answer only37.7 ± 1.4%8.8 ± 0.0%

Table R1: GSM8K with standard CoT. Qwen2.5-3B fine-tuned on human-written CoT solutions (3 epochs), evaluated on 320 depth-three GSM8K problems. Results are mean ± standard deviation over 3 seeds (800 examples) and 2 seeds (1,565 examples).

It is unclear whether the findings hold under more realistic conditions, and whether selectively supervising fewer intermediate steps provides meaningful benefits.

Response: The additional results show that the same ordering holds with standard CoT. At 800 training examples, removing one intermediate step reduces accuracy by 15.3 points, while training on final answers alone reduces accuracy to 7.7%. Both ways of removing a single step give nearly identical accuracy, consistent with their identical unobserved depth.

Interestingly, removing one step reduces the generated tokens by approximately 18–20%, but costs around 15 points in accuracy. This highlights a trade-off between shorter reasoning and the amount of computation left unobserved.

These results support our main finding beyond the controlled setting: leaving more of the reasoning unobserved makes generalization harder, even when the model is pretrained and generates natural-language reasoning.

On MuSiQue, outcome-only supervision actually outperforms intermediate supervision, raising questions about how broadly the findings generalize.

Response: We agree that MuSiQue provides an important boundary condition. Unlike GSM8K, MuSiQue provides supporting passages in the input. In our setup, the first bridge entity already appears in the opening paragraph for 94% of training questions. Thus, the model often does not need to compute the intermediate result from earlier steps, which explains why explicitly supervising it provides little benefit.

Our hypothesis concerns computation that the model must learn to perform, rather than intermediate information already available in the input. When the intermediate facts are directly accessible, leaving them unsupervised does not necessarily increase the difficulty of the task. We will clarify this distinction and the conditions under which unobserved algorithmic depth is expected to predict sample complexity.

AuthorsOpenReview ↗

Author Response (2/2)

Novelty and missing related work.

Response: We thank the reviewer for highlighting these relevant works and will expand the related-work discussion. Abedsoltan et al. (2025) study generalization across autoregressively composed tasks, Joshi et al. (2025) provide theoretical results for learning with observed versus latent CoT, and Yao et al. (2026) explain how CoT enables compositional generalization through learned skills.

Our contribution is complementary but distinct. We characterize how the sample complexity changes when the same computation is supervised at different intermediate positions, and show that this change can be predicted quantitatively. Importantly, the scaling relationship fitted only on outcome-supervised tasks in Section 4 predicts the sample complexity of 20 different intermediate-supervision schemes, without refitting. In additional analysis

Thus, beyond establishing that intermediate supervision helps, our results provide a way to predict how much data different supervision schemes require and why the placement of intermediate supervision matters.

We hope these additional results and clarifications address the reviewer's concerns. We will make these changes in the paper.

Q1. Which Qwen2.5-3B checkpoint and decoding strategy were used? What about ave@k and pass@k?

Response: We use Qwen2.5-3B base model with greedy decoding. The results in Section 6.3 report final-answer accuracy, rather than multi-sample ave@k or pass@k. Our primary focus is how training data requirements change with supervision, rather than the effects of sampling multiple solutions. We will clarify the checkpoint and decoding details in the paper.

Q2. Why is the GSM8K accuracy much lower than standard evaluation? Does the constrained format interfere with pretrained reasoning capabilities?

Response: We address this directly with additional experiments in Table 1, using standard CoT on the same 320 GSM8K problems. The untrained model achieves 70.9% with 8-shot CoT, while full-CoT fine-tuning reaches 57.8%, compared to 17.4% in the original values-only setting. This confirms that the model can solve substantially more of these problems when natural-language reasoning is allowed, although the different fine-tuning setups prevent attributing the entire difference to output format alone.

Importantly, the ordering across supervision schemes remains consistent with our hypothesis, as shown in Table 1.

Q3. How can the MuSiQue results be reconciled with the main hypothesis? When is unobserved depth predictive?

Response: As discussed in the response, MuSiQue provides an important boundary condition. In our setting, the first intermediate answer already appears in the opening paragraph for 94% of training questions, so the model often does not need to compute it. Our hypothesis concerns intermediate computations the model must learn, rather than information already available in the input. We will make this distinction clearer.

Q4. Could the hypothesis be evaluated on larger reasoning datasets with partial CoT supervision and different removal strategies?

Response: This is an interesting direction. Our controlled experiments already compare different supervision placements at the same budget, showing up to 6.6× differences in sample complexity. Extending this comparison to larger reasoning datasets would be valuable, although reliably identifying intermediate dependencies and controlling task difficulty becomes considerably harder.

Our GSM8K experiments use human-written solutions, but only 1,892 depth-three and 627 depth-four training problems are available in our parsed splits, limiting reliable scaling-law estimation at greater depths. Nevertheless, the additional standard-CoT results (Table), together with the English compositional and Python experiments in Section 6, provide evidence that the dependence on unobserved computation extends beyond our primary synthetic setting.

We hope these responses have addressed your concerns and clarified the validity and contributions of our work. If so, we respectfully ask that you reconsider and increase your score. We would also be happy to address any further concerns you may have. Thank you very much for your consideration.

References

Abedsoltan, A., et al. (2025). Task Generalization with Autoregressive Compositional Structure: Can Learning from D Tasks Generalize to D^T Tasks? ICML 2025.

Joshi, N., et al. (2025). A Theory of Learning with Autoregressive Chain of Thought. COLT 2025.

Yao, X., et al. (2026). Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoning. ICLR 2026.

We thank the reviewer again for the thoughtful feedback. We have conducted additional experiments directly addressing your concerns, including a standard-CoT evaluation on GSM8K, a quantitative comparison of alternative sample-complexity predictors, and further clarification of the novelty and limitations of our findings. We have also incorporated these results and the additional related work into the revised manuscript.

We would greatly appreciate it if you could revisit our rebuttal and updated paper. We believe the new evidence substantially strengthens the paper and addresses the main concerns raised in your review. If you find these concerns adequately addressed, we would be grateful if you would reconsider your assessment and increase your score.

Thank you again for your time and consideration!

Comments on the paper

2 comments

Dear Reviewers,

We are now halfway through the discussion phase. The authors have provided their responses to your reviews. If their responses have not adequately addressed your concerns, please take this opportunity to raise any remaining questions or concerns.

I encourage you to engage with the authors as soon as possible to ensure a productive discussion.

Many thanks,
AC

AuthorsOpenReview ↗

Summary of Rebuttal and Reviewer Feedback

We thank reviewers Lyj6, XFaN, and VBEC for their thoughtful feedback and constructive discussion. We appreciate their recognition of our research question and controlled setting (Lyj6), extensive empirical evaluation and predictive scaling law (XFaN), and particularly the supervision-placement experiments demonstrating large differences in sample complexity at a fixed supervision budget (VBEC). Below, we summarize the additional evidence and manuscript revisions addressing their concerns.

Concern C1 (XFaN, Lyj6): Novelty and predictive contribution beyond prior theory.

Our contribution goes beyond observing exponential growth: we identify unobserved algorithmic depth as a quantitative predictor of sample complexity under partial supervision.

Our new analysis covers 20 supervision schemes (463 runs). A law fitted only on outcome supervision predicts all 20 within 2×, with a typical error of 1.30×, without refitting. Alternative predictors based on total depth, supervision quantity, or average unobserved length have errors of 2.5–3.5×, even when fitted on these schemes. Thus, knowing that complexity grows exponentially is not enough; identifying which computational quantity governs the growth enables quantitative prediction.

Paper changes: Expanded related work (§2) and added the predictor comparison (Appendix C.6, Table 21).

Concern C2 (VBEC, XFaN): Depth, composition count, and supervision placement.

Our controlled experiments separate these factors. Holding the number of compositions fixed while varying depth changes sample complexity by up to 2.3× (Appendix B.6), and chained versus parallel compositions exhibit different generalization behavior (Appendix B.7).

Importantly, changing only the placement of the same number of supervised steps changes sample complexity by up to 6.6×, whereas adding supervision without shortening the longest unobserved run improves it by only 1.1×.

These results establish that computational structure and supervision placement matter beyond composition count and supervision quantity.

Concern C3 (Lyj6, XFaN): GSM8K evaluation and pretrained reasoning.

Our original evaluation deliberately uses numerical-only outputs. Under this matched format, accuracy improves from 2.8% (untrained, four-shot) to 17.4% with full-supervision fine-tuning. Hiding one intermediate step requires 3.5× more examples to reach the same 9% accuracy; outcome supervision never reaches this threshold.

We additionally evaluated standard natural-language CoT on the same 320 problems. The untrained model achieves 70.9%, explaining the discrepancy with standard GSM8K performance. Since fine-tuning in this setting reduces pretrained accuracy, we treat it as a format diagnostic, not an independent sample-complexity measurement. The ordering across supervision schemes nevertheless persists.

Paper changes: Added standard-CoT experiments (Appendix D.2, Table 27) and clarified the evaluation protocol.

Concern C4 (Lyj6, XFaN): Generalization beyond synthetic tasks.

Our findings extend to pretrained models on English compositions (4–5× more data per additional unobserved step), Python programs (up to eight steps), and GSM8K.

Following XFaN's suggestion, we also evaluated GSM-Infinite. At depth six, all schemes fit their training sets but achieve only 4.6–8.6% test accuracy, preventing reliable sample-complexity estimation. At depth four, outcome supervision again performs worst (27.6% versus 32.8–35.1%), although limited runs prevent stronger conclusions.

We distinguish the precise scaling law established in controlled tasks from the supporting qualitative evidence on realistic tasks.

Concern C5 (VBEC, XFaN, Lyj6): Scope and limitations.

We clarified three important points:

  • MuSiQue: Intermediate facts already appear in the opening paragraph for 94% of training questions, making additional supervision less useful (Appendix D.4).
  • Depth six: The prediction preceded training, but optimization difficulties make it supporting evidence rather than an independent validation (Appendix B.3).
  • Other factors: Unobserved depth is the dominant predictor in controlled tasks, while error propagation, additional unsupervised runs, and optimization can also matter (Appendices C.5, D.3).

Overall, our new experiments strengthen the central contribution: a scaling law calibrated without intermediate supervision quantitatively predicts how supervision placement changes sample complexity, without refitting.

We sincerely appreciate the reviewers' continued engagement. We believe the additional evidence and manuscript revisions directly address the central concerns and substantially strengthen our contribution. We respectfully encourage the reviewers to reconsider their assessments and increase their scores where permitted. We would be happy to address any remaining questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.