Information-Theoretic Foundations of Online Temperature Sampling

Abstract:Repetitive, degenerate generation is a persistent failure of LLM decoding, and the standard remedies (temperature, nucleus, and top-$k$ sampling) are static heuristics. By Kac's lemma and the AEP, a stationary source takes time exponential in its entropy to repeat a block. We therefore maximize the entropy of the sampling distributions under one cross-entropy budget that keeps the output plausible under the model. Offline, the solution is temperature sampling, with the inverse temperature as the budget's Lagrange multiplier. \emph{Our contribution is the online problem}: the conditionals $p_1, p_2, \dots$ are revealed one at a time, and the sampling distribution $q_t$ must be chosen causally from $p_1, \dots, p_t$ while the budget couples the entire horizon. The optimal temperature is thus a global shadow price that must be estimated from a prefix. We propose Entropic Online Sampling (EOS), which re-solves for the temperature on each prefix. We prove it loses $O(R\log n)$ entropy against the offline optimum while overshooting the budget by $O(R\log n)$, with $R$ an instance-dependent drift parameter. A budget-tightened variant is exactly feasible at the same rate. Conversely, every exactly feasible online algorithm must lose $\Omega(R)$, so EOS is optimal up to a $\log n$ factor. When the conditionals are drawn from a finite mixture, $R=\tilde{O}(\sqrt{n})$. Experiments confirm that EOS tracks the offline temperature and beats fixed-temperature sampling in entropy.

Machine Learning (cs.LG)

arXiv:2610.15043 [cs.LG]

(or arXiv:2610.15043v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.15043 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.