- 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
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.
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.
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.
Response: The depth-six prediction was fixed before training, and the measured K50=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.
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.
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.
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.
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.