# On Next-Token Prediction in LLMs: How End Goals Determine the Consistency of Decoding Algorithms

arXiv: https://arxiv.org/abs/2505.11183 · HTML: https://mlsanity.com/paper/2505.11183/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 16 May 2025.

## Builds on (most cited first, 21 of 21)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Language Models as Knowledge Bases?](https://mlsanity.com/paper/1909.01066/) (2019)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [A Thorough Examination of Decoding Methods in the Era of LLMs](https://mlsanity.com/paper/2402.06925/) (2024)
- [On Decoding Strategies for Neural Text Generators](https://mlsanity.com/paper/2203.15721/) (2022)
- [A Mathematical Exploration of Why Language Models Help Solve Downstream Tasks](https://mlsanity.com/paper/2010.03648/) (2020)
- [Hot or Cold? Adaptive Temperature Sampling for Code Generation with Large Language Models](https://mlsanity.com/paper/2309.02772/) (2023)
- [Mechanics of Next Token Prediction with Self-Attention](https://mlsanity.com/paper/2403.08081/) (2024)
- [Convex Calibration Dimension for Multiclass Loss Matrices](https://mlsanity.com/paper/1408.2764/) (2014)
- [Improving Open-Ended Text Generation via Adaptive Decoding](https://mlsanity.com/paper/2402.18223/) (2024)
- [Multi-label classification: do Hamming loss and subset accuracy really conflict with each other?](https://mlsanity.com/paper/2011.07805/) (2020)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Adaptive Decoding via Latent Preference Optimization](https://mlsanity.com/paper/2411.09661/) (2024)
- [Foundation Models for Natural Language Processing -- Pre-trained Language Models Integrating Media](https://mlsanity.com/paper/2302.08575/) (2023)
- [Reasoning Bias of Next Token Prediction Training](https://mlsanity.com/paper/2502.02007/) (2025)

## Built on by (most cited first, 1 of 1)

- [Learning Representations through Token Prediction: Geometry, Approximation, and Downstream Guarantees](https://mlsanity.com/paper/2608.30072/) (2026)

## Abstract (arXiv)

Probabilistic next-token prediction trained using cross-entropy loss is the basis of most large language models. Given a sequence of previous values, next-token prediction assigns a probability to each possible next value in the vocabulary. There are many ways to use next-token prediction to output token sequences. This paper examines a few of these algorithms (greedy, lookahead, random sampling, and temperature-scaled random sampling) and studies their consistency with respect to various goals encoded as loss functions. Although consistency of surrogate losses with respect to a target loss function is a well researched topic, we are the first to study it in the context of LLMs (to the best of our knowledge). We find that, so long as next-token prediction converges to its true probability distribution, random sampling is consistent with outputting sequences that mimic sampling from the true probability distribution. For the other goals, such as minimizing the 0-1 loss on the entire sequence, we show no polynomial-time algorithm is optimal for all probability distributions and all decoding algorithms studied are only optimal for a subset of probability distributions. When analyzing these results, we see that there is a dichotomy created between the goals of information retrieval and creative generation for the decoding algorithms. This shows that choosing the correct decoding algorithm based on the desired goal is extremely important and many of the ones used are lacking theoretical grounding in numerous scenarios.