Online Temperature Sampling: A New LLM Decoding Method from an Information-Theoretic Perspective

Large Language Models (LLMs) often fall into repetitive, degenerate patterns when generating text—saying the same thing over and over, or getting stuck in meaningless loops. Standard remedies like temperature sampling, nucleus sampling, and top-k sampling are essentially static heuristics: once hyperparameters are set, they stay fixed regardless of how the context changes. A recent arXiv paper, Information-Theoretic Foundations of Online Temperature Sampling, attempts to reexamine this problem from its information-theoretic roots and proposes an online sampling algorithm that can dynamically adjust temperature.

From Offline Optimality to the Online Challenge

The paper's core insight builds on Kac's lemma and the Asymptotic Equipartition Property (AEP): for a stationary source, the time required to repeat a given block grows exponentially with its entropy. In other words, there is a deep information-theoretic duality between generation diversity and repetition probability. To suppress degenerate generation, the natural approach is to maximize the entropy of the sampling distribution while imposing a cross-entropy budget constraint to ensure the output remains plausible from the model's perspective.

The offline solution to this constrained optimization problem turns out to be exactly temperature sampling—the inverse temperature parameter is precisely the Lagrange multiplier of the budget constraint. This conclusion is not surprising in itself, but it provides a rigorous information-theoretic interpretation of temperature sampling: temperature is no longer a hyperparameter to be tuned manually, but rather the shadow price of the trade-off between model likelihood and output diversity.

The real challenge lies in the online setting. During actual generation, the conditional distributions $p_1, p_2, \dots$ are revealed one by one, and the sampling distribution $q_t$ must be determined causally from the known prefix $p_1, \dots, p_t$, yet the budget constraint couples the entire generation horizon. This means the optimal temperature is a global shadow price that must be estimated from local information.

Kac's Lemma originates from ergodic theory and was originally used to study the statistical properties of return times in dynamical systems. Its core conclusion is that for a stationary ergodic system, the expected return time to a state or block of states is inversely proportional to its measure. In the information-theoretic context, this lemma is generalized as follows: the time required for a stationary source to repeat a block of length n grows exponentially with the block's entropy. Intuitively, the more information a block contains (the higher its entropy), the lower the probability that the source will generate the same sequence again, and the longer the average waiting time. This provides the mathematical foundation for the paper's claim that "there is an information-theoretic duality between generation diversity and repetition probability": the more deterministic the model output (low entropy), the more easily it falls into repetitive loops; the more diverse the output (high entropy), the exponentially longer the time required for repetition.

The Asymptotic Equipartition Property (AEP) is one of the foundational theorems of information theory, proposed by Shannon. It states that for i.i.d. or stationary ergodic sources, as the sequence length n tends to infinity, the probability of almost all typical sequences is approximately 2^{-nH}, where H is the source entropy. AEP directly connects entropy to the number and probability of typical sequences: higher entropy means more typical sequences and lower probability for each individual sequence. This property is a key bridge for understanding the application of Kac's lemma to the source repetition problem, and it also provides theoretical justification for subsequent entropy-based sampling objective functions.

The EOS Algorithm: Estimating Global Temperature from Local Prefixes

To address this online problem, the authors propose the Entropic Online Sampling (EOS) algorithm. The core mechanism of EOS is to re-solve for the temperature parameter at each prefix—essentially approximating that global optimal Lagrange multiplier online.

The theoretical analysis provides clear performance guarantees. EOS's entropy loss relative to the offline optimal solution is $O(R\log n)$, and the budget overshoot is also on the order of $O(R\log n)$, where $R$ is a drift parameter that depends on the specific instance. The authors also propose a budget-tightening variant that strictly satisfies the budget constraint at the same rate.

More crucially, the lower bound result: any online algorithm that strictly satisfies the budget must incur an entropy loss of $\Omega(R)$. This means EOS is already optimal within a $\log n$ factor. When the conditional distributions come from a finite mixture model, $R = \tilde{O}(\sqrt{n})$, yielding a concrete and controllable bound.

The value of this analytical framework lies in elevating temperature sampling from an engineering trick to a theoretically grounded online decision-making problem, and clearly quantifying the unavoidable cost of limited online information.

Lagrange Multipliers and Shadow Prices: In constrained optimization problems, the Lagrange multiplier measures the marginal improvement in the optimal value of the objective function when the constraint is relaxed by one unit. In economics, it is often interpreted as the "shadow price"—the implicit value of the constrained resource. In this paper's framework, the cross-entropy budget constraint requires that the average cross-entropy between the sampling distribution and the model distribution not exceed a certain threshold, and the inverse temperature β is precisely the Lagrange multiplier of this constraint. The larger β is (lower temperature), the closer the sampling distribution is to the model distribution, resulting in lower cross-entropy but also lower entropy; the smaller β is (higher temperature), the higher the entropy but the cross-entropy may exceed the budget. Thus β precisely quantifies the marginal rate of substitution between "plausibility" and "diversity."

"Regret" in Online Learning and Global Constraints: Online optimization problems typically use "regret" to measure the gap between online decisions and the best possible decisions in hindsight. The special difficulty faced by the EOS algorithm in this paper is that the budget constraint is global—it couples all sampling decisions across the entire generation horizon, while the algorithm can only make decisions causally, prefix by prefix. This is similar to online resource allocation problems: how much budget is consumed at each step is unknown, but there is a cap on the total budget. EOS approximates the globally optimal Lagrange multiplier by re-solving the local optimization at each prefix, and its O(R log n) entropy loss and budget overshoot guarantees are precisely the theoretical cost of this online approximation strategy.

Finite Mixture Model Assumption: The "conditional distributions come from a finite mixture model" mentioned in the paper is a common statistical modeling assumption, meaning that each conditional distribution p_t can be expressed as a convex combination of a finite number of base distributions, i.e., p_t = Σ_k π_k f_k, where π_k are the mixture weights and f_k are the base distributions. This assumption is reasonable for language models: different contexts may activate different semantic patterns or topics, each corresponding to a base distribution. Under the finite mixture model, the drift parameter R can be concretely bounded as Õ(√n), which means that as the sequence length grows, the estimation error of the online temperature grows at a square-root rate rather than linearly. This result turns EOS's performance guarantee from an abstract O(R log n) into a concrete and controllable Õ(√n log n), providing clearer expectations for practical applications.

Experimental Validation and Practical Significance

The experimental section validates the theoretical predictions: EOS can effectively track the trajectory of the offline optimal temperature and outperforms fixed temperature sampling on entropy metrics. This result has two implications.

On the practical side, EOS offers an adaptive temperature strategy for LLM decoding that requires no manual tuning. In traditional methods, engineers must repeatedly experiment with temperature values based on task type and model behavior, whereas EOS can in principle automate this process with information-theoretic performance guarantees.

On the theoretical side, this work establishes a new connection between online learning and information theory. The online version of temperature sampling is essentially an online optimization problem with global constraints, and its analytical tools (Kac's lemma, AEP, Lagrangian duality) come from several classical fields, but their combination is quite novel.

Of course, there is still a gap between theory and large-scale deployment. EOS requires re-solving the optimization problem at each prefix; whether the computational overhead is acceptable and how numerical stability is ensured are issues that need to be considered in practical applications. The experimental scale of the paper is also relatively limited, and performance on larger-scale models and longer generation sequences remains to be verified.

The Theoretical Turn in Decoding Strategies

This work reflects a broader trend: decoding strategies during LLM inference are moving from experience-driven to theory-driven. Over the past few years, from temperature sampling to nucleus sampling to various penalty mechanisms, most have relied on intuition and experimental trial and error. EOS represents a direction of using rigorous information theory and online learning frameworks to re-derive these heuristics and provide provable performance bounds.

For researchers and engineers focused on LLM inference optimization, this paper offers a perspective worth noting: the design of decoding strategies need not remain at the heuristic level; information theory can provide a more solid theoretical foundation and clearer performance bounds.

Nucleus Sampling and Top-k Sampling are currently the two most commonly used heuristic strategies in LLM decoding. Top-k sampling samples only from the k tokens with the highest probabilities at each step, where k is a fixed hyperparameter; nucleus sampling dynamically selects the smallest set of tokens whose cumulative probability reaches a threshold p, then samples from that set. Both aim to truncate low-probability "long-tail" tokens to avoid generating incoherent content. However, their hyperparameters (k or p) are also static and cannot adaptively adjust based on context complexity. The fundamental difference between EOS and these methods is that it does not control quality by truncating the distribution, but rather dynamically adjusts temperature through entropy maximization under information-theoretic constraints, with its adjustment process guaranteed by online learning theory. From a broader perspective, the "constrained optimization + online learning" framework represented by EOS has the potential to unify and reinterpret existing decoding heuristics, transforming decoding strategy design from a parameter tuning problem into an optimization problem with explicit objective functions and constraints.

One-line Summary

The paper reinterprets temperature sampling as the optimal solution under a cross-entropy budget from an information-theoretic perspective, and proposes a theoretically guaranteed online adaptive temperature algorithm, EOS.

Paragraph Summary

This paper reexamines the temperature sampling problem in LLM decoding from its information-theoretic foundations. Based on Kac's lemma and the Asymptotic Equipartition Property, the authors reveal an information-theoretic duality between generation diversity and repetition probability, and prove that offline optimal temperature sampling is equivalent to entropy maximization under a cross-entropy budget constraint, with the inverse temperature being precisely the Lagrange multiplier of the budget. For the online setting where conditional distributions are revealed one by one, the paper proposes the Entropic Online Sampling (EOS) algorithm, which re-solves for the temperature parameter at each prefix to approximate the global optimum. Theoretical analysis shows that EOS's entropy loss and budget overshoot are both O(R log n), and a lower bound proves that any online algorithm strictly satisfying the budget must incur at least Ω(R) entropy loss, indicating that EOS is optimal within a log n factor. Experiments validate that EOS can effectively track the offline optimal temperature and outperforms fixed temperature sampling on entropy metrics.