Next-Token Prediction and Regret Minimization

We study the robustification of next-token prediction models in adversarial online decision-making environments. Suppose a next-token predictor is trained on a distribution over sequences of opponent actions, and a decision maker acts by approximately best responding to the model’s predictions. If this induced decision-making algorithm achieves low adversarial regret, we call such distributions low-regret distributions. For models with unbounded context, we show that every distribution is exponentially close in total variation distance to a low-regret distribution. Thus, sublinear regret can always be achieved while changing the original next-token prediction distribution by only a negligible amount. By contrast, for models with bounded context windows, as in standard transformer architectures, we prove an impossibility result: some distributions are $\Theta(1)$-far from every low-regret distribution. We complement these results with two positive findings. First, allowing a modest increase in context length restores robustification with near-optimal regret guarantees. Second, the unbounded-context robustification procedure can be implemented by adding a constant number of layers to a standard transformer architecture. Finally, we provide empirical evidence that small transformer models can be efficiently trained to represent these robustified low-regret distributions.

Next-token predictors are trained to predict the next item in a sequence, such as the next word in a sentence or the next event in a stream of data. These predictions are increasingly used to support decisions, but a model that predicts well on typical data may behave poorly when the environment is adversarial or strategically chosen. This paper asks whether next-token prediction models can be modified so that decision makers using their predictions also perform well in adversarial online settings. We show that, when the model can use the full past history, any next-token predictor can be changed by only a negligible amount so that it leads to low-regret decisions. However, when the model has a limited context window, as many transformer-based models do, such a modification is sometimes impossible without increasing the context length. We also show that the proposed modification can be implemented by standard transformer layers and that small transformers can learn these robustified behaviors in experiments. Overall, the paper clarifies when predictive AI models can be safely used for sequential decision making in adversarial environments.