Transformer-based language models exhibit an astonishing capacity to generalize to longer and more difficult problem instances than those seen in training. However, theoretical understanding of this phenomenon still lags behind. Unlike most machine learning models, the generalisation abilities of transformers inherently require considering two axes. On one hand, one must examine in-distribution statistical generalisation, which concerns the ability of a model to broaden a function from training samples to novel samples of the same distribution. On the other hand, given the sequential nature of language data, one must also consider length generalisation, which reflects whether a model trained on inputs of a given length can extrapolate to longer ones. These two notions have mostly been studied separately, leaving open how they interact. In this work, we give a joint treatment of both axes for fixed-precision transformers. We give generalisation guarantees in terms of the parameter sizes of the involved models, as well as the quantization space and the alphabet size that supply the sequences. Finally, we illustrate how the requirements in the sample count and training length trade off. In particular, we find that increasing training length can be exponentially more efficient than increasing the sample size. Experiments support predictions of the theory.
Figures & tables
Figure 1: Our results predict that increasing the length of the training words can be much more token-efficient than increasing their number; test accuracy for the language A15 (Sec. 5 ) on words five times longer than the training length. We highlight in red the highest-accuracy cell at five different training token budgets.
Figure 2: Examples of poDFAs; the vertices are the states and the arrows are the transition functions δ . Figure (a) represents the transformer that outputs “1” as soon as the input word has entered the language L2:=aΣ∗bΣ∗ with (b) being the associated poDFA. Similarly, (c) depicts the transformer that recognizes the language L3:=aΣ∗bΣ∗aΣ∗ and (d) is its corresponding poDFA. Figure (e) is the poDFA AΔ of the difference function between these two transformers. Any disagreement sends the run to the absorbing final state ⊥ .
Figure 3: Schematic error-budget limit lines with linear axes. At K=C , every budget can be respected with N∼O(sC) training samples. By length K=sC , at least half of the words have reached their terminal absorbing states, so each curve is within a factor 2 of its floor; further length gains saturate.
Figure 4: Left: Impact of teacher’s size on length complexity. Larger teachers require training samples to be longer. The abscissa scale is linear, as suggested by theory. Right: Impact of teacher’s size on data complexity. Larger teachers require more training samples for similar length generalization performance. The abscissa scale is logarithmic, as suggested by theory. On both sides, the plotted tasks are respectively the Alternating L4,L5,L6,L7 , the Alphabet A10,A12,A15,A20 and the Induction Head IH5,IH6,IH7,IH8 .
Figure 5: Tradeoff between the training length and the sample size for one task of each language class: Alternating L6 , Alphabet A15 and Induction Head IH7 . Evaluation at length 5 times the training length. Brown contouring around all cells with accuracy ≥0.75 . Under this condition, the 3 cells with the smallest token-budget are framed.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Impact of teacher’s size on data complexity . Lk probes teacher depth Lt ; Ak jointly varies Ht , Dt , and ∣Σ∣ ; IHk varies alphabet size, width requirements, and output dimension. Student backbones are fixed within each family, while K follows the task-specific coverage criterion.
Figure 7: Impact of teacher’s size on length complexity . Lk probes teacher depth Lt ; Ak jointly varies Ht , Dt , and ∣Σ∣ ; IHk varies alphabet size, width requirements, and output dimension. Tasks are compared at shared values of K , with N and student backbones fixed. For relative evaluations, early accuracy is sometimes high for tasks that are trivial on short words: words of length 3K or 5K might still be short and have a trivial target.
Figure 8: Impact of the student’s depth on length generalization . We vary Ls while holding Ds and Hs fixed.
Figure 9: Impact of the student’s embedding dimension on length generalization . We vary Ds while holding Ls and Hs fixed.
Figure 10: Impact of the student’s head count on length generalization . We vary Hs while holding Ls and Ds fixed.
Figure 11: Tradeoff between training length and data complexity . One task of each family: L6,A15 and IH7 to study the tradeoff between the two quantities.
Figure 12: Control experiment for L6 , A15 , and IH7 , with evaluation at relative test length 5 K . The axis labelled N gives the total token budget of the dataset rather than the number of words.
Figure 13: Tradeoff between training length and data complexity: evaluation on absolute lengths, from length 50 to length 500 with additive incrementation of 50 .
Figure 14: Tradeoff between training length and data complexity: evaluation on relative lengths 1K,2K,3K,4K,5K , with K the training length of the involved cells configuration.
Figure 15: Tradeoff between training length and data complexity: evaluation on absolute lengths, from length 50 to length 500 with additive incrementation of 50 . Red contouring for accuracy ≥0.75 ; highlighted in red are the 3 configurations under this constraint that have the smallest token-budget.
Figure 16: Tradeoff between training length and data complexity: evaluation on relative lengths 1K,2K,3K,4K,5K , with K the training length of the involved cells configuration. Red contouring for accuracy ≥0.75 ; highlighted in red are the 3 configurations under this constraint that have the smallest token-budget.
Figure 17: Tradeoff between training length and data complexity: evaluation on absolute lengths, from length 50 to length 500 with additive incrementation of 50 . For their respective maximum token-budget threshold, highlighted in red are the 3 configurations that achieve the best accuracy.
Figure 18: Tradeoff between training length and data complexity: evaluation on relative lengths 1K,2K,3K,4K,5K , with K the training length of the involved cells configuration. For their respective maximum token-budget threshold, highlighted in red are the 3 configurations that achieve the best accuracy.