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 become effective models for this task, but their properties
are still not fully understood. In particular, the largest number of distinct
context sequences that a decoder-only transformer can interpolate next-token
distributions for has not been established. To fill this gap, we prove upper
and lower bounds on this number, which are equal up to a multiplicative
constant. We prove these bounds in the general setting where next-token
distributions can be arbitrary as well as the empirical setting where they are
calculated from a finite number of document sequences. Our lower bounds are for
one-layer transformers and our proofs highlight an important injectivity
property satisfied by self-attention. Furthermore, we provide numerical
evidence that the minimal number of parameters for memorization is sufficient
for being able to train the model to the entropy lower bound.

给定一个令牌序列，如单词，下一个令牌预测的任务是预测下一个令牌的条件概率分布。我们针对仅编码器的 transformer 模型的性质进行了研究，并证明了该模型可以插值下一个令牌分布的最大上下文序列的上下界，其中下界只需最小的参数数量即可实现。