Information-Theoretic Foundations of Online Temperature Sampling

arXiv:2610.15043v1 Announce Type: new 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. Our contribution is the online problem: the conditionals p_1, p_2, ots are revealed one at a time, and the sampling distribution q_t must be chosen causally from p_1, ots, 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(Rlog n) entropy against the offline optimum while overshooting the budget by O(Rlog 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=ilde{O}(sqrt{n}). Experiments confirm that EOS tracks the offline temperature and beats fixed-temperature sampling in entropy.

Related

• Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling
• TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation
• Sample Count Is Not Enough: Candidate-Generation Strategy Shapes the Energy and Performance of LLM Test-Time Scaling

Source: arXiv cs.LG | 2026-10-14