Next-token prediction capacity: general upper bounds and a lower bound for transformers

Liam Madden, Curtis Fox, Christos Thrampoulidis

Given a sequence of tokens, such as words, the task of next-token prediction is to predict the next-token conditional probability distribution. Decoder-only transformers have becom…