Provable Long-Range Benefits of Next-Token Prediction
This provides a theoretical foundation for understanding long-range benefits in language models, addressing a core issue in AI and machine learning, though it is incremental in offering formal proofs for existing empirical observations.
The paper tackles the problem of explaining why next-token prediction in language models leads to long-range coherence, proving that optimizing this objective with RNNs yields models that approximate the training distribution such that no bounded algorithm can distinguish generated tokens from real ones over any k tokens, with polynomial bounds on model size.
Why do modern language models, trained to do well on next-word prediction, appear to generate coherent documents and capture long-range structure? Here we show that next-token prediction is provably powerful for learning longer-range structure, even with common neural network architectures. Specifically, we prove that optimizing next-token prediction over a Recurrent Neural Network (RNN) yields a model that closely approximates the training distribution: for held-out documents sampled from the training distribution, no algorithm of bounded description length limited to examining the next $k$ tokens, for any $k$, can distinguish between $k$ consecutive tokens of such documents and $k$ tokens generated by the learned language model following the same prefix. We provide polynomial bounds (in $k$, independent of the document length) on the model size needed to achieve such $k$-token indistinguishability, offering a complexity-theoretic explanation for the long-range coherence observed in practice.