Algorithmic Depth Predicts the Sample Complexity of Generalization

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.