In-context learning and Occam's razor
Authors: name: Eric Elmoznino, name: Tom Marty, name: Tejas Kasetty, name: Leo Gagnon, name: Sarthak Mittal, name: Mahan Fathi, name: Dhanya Sridhar, name: Guillaume Lajoie

The goal of machine learning is generalization. While the No Free Lunch
Theorem states that we cannot obtain theoretical guarantees for generalization
without further assumptions, in practice we observe that simple models which
explain the training data generalize best: a principle called Occam's razor.
Despite the need for simple models, most current approaches in machine learning
only minimize the training error, and at best indirectly promote simplicity
through regularization or architecture design. Here, we draw a connection
between Occam's razor and in-context learning: an emergent ability of certain
sequence models like Transformers to learn at inference time from past
observations in a sequence. In particular, we show that the next-token
prediction loss used to train in-context learners is directly equivalent to a
data compression technique called prequential coding, and that minimizing this
loss amounts to jointly minimizing both the training error and the complexity
of the model that was implicitly learned from context. Our theory and the
empirical experiments we use to support it not only provide a normative account
of in-context learning, but also elucidate the shortcomings of current
in-context learning methods, suggesting ways in which they can be improved. We
make our code available at https://github.com/3rdCore/PrequentialCode.