CS Paper Radar

The Optimal Decoder is Tilted Temperature

Nikolaos Papagiannis, Ananth Grama, Wojciech Szpankowski

cs.LG ·submitted 2026-10-10 16:49 UTC · v1
theory

Abstract

Larger sample budgets benefit from higher sampling temperatures in LLMs, but what temperature tuning optimizes and why it works remain poorly understood. We seek to answer these questions: we pose decoding as pass@$k$ maximization subject to two constraints that encode critical decoding failure modes: an entropy floor preventing diversity collapse, and a cross-entropy ceiling preventing implausibility. We prove that this maximization takes the form of a single closed-form conditional sampling rule, the \emph{tilted temperature} $q^\star \propto \bigl(p e^{ηV}\bigr)^{1/T}$. Here, the tilt comes from a verifier potential $V$ that quantifies how likely a partial generation is to eventually pass. Ordinary temperature sampling, verifier-greedy decoding, and reward-tilted policies represent special cases. We further show that, under a natural rule for scaling the diversity budget with sample size $k$, the resulting optimal temperature increases with $k$, turning empirical choice into a theorem. The optimum still needs the unknown verifier potential, which we estimate using two design approaches. In the online setting, our J-EOS algorithm jointly tracks the two constraint multipliers and learns the verifier potential from binary pass/ fail feedback alone. In the offline setting, we show that when the model is calibrated, its log-probability tracks correctness up to an affine map. Under this condition, the tilt collapses into the exponent and the optimum reduces to ordinary temperature sampling. Calibrated Temperature Decoding (CTD) then fits one scalar offline and samples with zero additional inference-time overhead relative to temperature sampling. Building on these decision rules, we design a practical decoding algorithm for code generation and evaluate it alongside CTD on benchmarks including HumanEval and MBPP, showing improvements over standard and adaptive decoding baselines.

Closest papers

Nearest neighbours by meaning across the whole index.

Information-Theoretic Foundations of Online Temperature Sampling

cs.LG ·2026-10-10 ·Jin Sima, Nikolaos Papagiannis, Ananth Grama, Wojciech Szpankowski
theory similarity 0.69
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 $Ω(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.

0.29

XTC: Head-Aware Sampling by Excluding Top Choices

cs.CL cs.AIcs.LG ·2026-08-24 ·Philipp Emanuel Weidmann, Allen Roush, Judah Goldfeder, Sanjay Basu, Ravid Shwartz-Ziv
similarity 0.61
Abstract

Standard decoding rules for autoregressive language models promote diversity by rescaling the full next-token distribution or truncating its low-probability tail. These strategies overlook a common regime of open-ended generation in which several continuations are plausible but too much probability mass remains concentrated on the most generic choice. We introduce XTC (Exclude Top Choices), a lightweight head-aware decoding operator that targets this regime directly. XTC identifies tokens whose probabilities exceed an absolute plausibility threshold $τ$: when at least two qualify, it removes the dominant eligible choices with probability $ρ$ and retains only the weakest plausible alternative before renormalization. Across 60 experiments on Gemma 3 27B Q4, Gemma 3 12B Q6, and DeepSeek R1 14B Q6, with scaling validation on Llama 3.3 70B Q4, XTC improves the diversity-repetition Pareto frontier. On creative generation, Distinct-2 increases by 11--15% and repeat trigrams decrease by 27--47% across the four models. Combined with temperature scaling, gains reach 38% in Distinct-2 and 71% in repeat-trigram reduction over baseline. A blinded Amazon Mechanical Turk study with 150 Master raters yields a 62.3% creativity preference for XTC ($p<10^{-4}$) without reduced fluency, while a GPT-4o control judge reproduces the Anthropic-judge direction on every measure. On IFEval with Llama 3.3 70B Q4, XTC preserves prompt-level strict accuracy within 1.7 percentage points of baseline while recovering most of the diversity gain; a temperature setting matched on Distinct-2 reduces IFEval by 8.8 points. The effect is additive with temperature and repetition penalties, robust across quantization levels and model families, and consistent across twelve prompt genres. XTC has been adopted by llama.cpp, ExLlamaV2, and text-generation-webui.

0.55

One Temperature to Rule Them All?

cs.LG cs.AIcs.CL ·2026-11-09 ·Aviv Orly, Ori Shem-Ur, Yaron Oz
top venuecode/data similarity 0.61
Abstract · Accepted at NeurIPS 2026. 82 pages, 45 figures, 6 tables. Code: https://github.com/avivorly/one-temperature

Inference-time sampling is a central mechanism for improving large language models, with temperature controlling the tradeoff between reliability and diversity. While recent work suggests that varying temperature across samples can improve multi-sample inference, simple fixed-temperature schemes remain the standard in practice. We investigate this discrepancy in the canonical pass@K setting, asking when temperature diversity is useful, and when a single tuned temperature suffices. To this end, we analyze per-question success probabilities across multiple models and datasets, tracking how they vary with sampling temperature. We identify several consistent properties of these profiles, including that harder questions are less likely to share efficient sampling temperatures, although this trend is only logarithmic in hardness. We then derive an efficient method for evaluating the theoretically optimal multi-temperature allocation scheme, and show that although such a scheme improves performance, its gains over single-temperature baselines are typically modest when temperature is tuned as a function of the sampling budget K. We explain this phenomenon through mathematical mechanisms that we call dulling effects, and show how they ensure the robustness of temperature choices across different question distributions. Our results clarify when multi-temperature sampling is useful, and how temperatures should ideally be chosen.

0.51

The Price of Not Planning: Parallel Sampling Depth Peaks at the Reconstruction Threshold

cs.LG ·2026-11-16 ·Chuling Wen, Weijie Liang, Jian Lu
similarity 0.61
Abstract

Masked diffusion models sample the tokens of one round independently. Planned decoders first generate a coarse plan, then fill in the tokens in parallel. We ask when a plan saves rounds, how many it saves, and how fine it must be. We study this on broadcast trees: the leaves are the tokens, the internal nodes are the plan, and the edge correlation $θ$ sets how strongly tokens depend on the plan. Errors are measured by the forward Kullback-Leibler divergence $\varepsilon$, and the lower bounds hold for every deterministic value-adaptive rule, also with learned conditionals. We show that a decoder without the plan needs of order $\min\{n,(n/\varepsilon)^α\}$ rounds below the reconstruction threshold, where $α=\log b/(4\log(1/θ))$ rises to $1/2$ at the threshold, and that the exponent stays below $1/2$ above it (binary channel: $0.02\leθ\le0.98$). With the plan, $\log_b n+1$ rounds suffice. In the binary model below the threshold, a plan with units of $m$ tokens needs of order $\log_b(n/m)+\min\{m,(n/\varepsilon)^α\}$ rounds, so it gives logarithmic depth exactly when $m$ is logarithmic. A plan therefore helps most near the threshold, and only if its units are small. Exact divergence computations in the Gaussian model with up to $2^{20}$ leaves confirm these exponents below the threshold.

0.08

A Sign Law for Entropy Drift under Sampler Mismatch in RLVR

cs.LG cs.AI ·2026-10-25 ·Zhiyuan Wang, Jacob Steeves, Chang Liu
theory similarity 0.58
Abstract

In reinforcement learning with verifiable rewards (RLVR), whether entropy rises or falls can depend on choices that matter little under exact sampling, such as whether over-length responses are masked or counted as failures. We trace this to sampler mismatch: rollouts are drawn with top-k/top-p truncation or at a temperature the learner does not apply. We prove that a constant advantage shift then changes the entropy of a softmax policy, at first order and in expectation, with a sign fixed by the sampler. Positive shifts sharpen the policy under any sampler whose likelihood ratio to the policy increases with token probability, including top-k, top-p, min-p, and temperatures below one, and flatten it under flatter samplers. In group-based RLVR with token-level losses, the baseline-dependent part of this drift is set by the token-weighted net advantage, which masking and failing can push to opposite signs. The rest comes from a covariance between advantages and the sampler's sharpness gap and feeds back on itself: in a two-level model, a push away from a sharper sampler takes off in finite time, while a pull toward it saturates. On a 2B model, the entropy slope is linear in shifts of the net advantage under truncated sampling and indistinguishable from flat under exact sampling. Token-level importance ratios leave 98% of the drift, and four clipped minibatch updates per batch amplify it sevenfold. In 100-step runs, a net-zero baseline only delays an entropy explosion, and entropy raised at the start keeps rising only under truncation; cancelling the first-order drift at every step keeps entropy bounded without changing the learner. On a 9B reasoning model forked from an uncorrected run, zeroing the net advantage or renormalizing the learner raises held-out accuracy after ten steps by 8.2 and 8.8 points over the uncorrected rule, with no difference under exact sampling.

0.35

Regev's Reduction Reaches Reconstruction

cs.DS quant-phcond-mat.dis-nn ·2026-11-06 ·Stephen P. Jordan, Quynh T. Nguyen, Leo Zhou
similarity 0.57
Abstract · 30 pages, 4 figures

Regev's reduction uses a quantum Fourier transform to carry out reductions between various problems related to lattices and codes. We apply it to the problem of sampling from Gibbs distributions of certain classical spin glass Hamiltonians, which can equivalently be thought of as cost functions for average-case instances of an optimization problem called $D$-regular max-$k$-LINSAT. This problem becomes hard at low temperature. Here, we use a quantum decoding algorithm called Belief Propagation with Quantum Messages (BPQM) to solve the decoding problem arising from Regev's reduction. Our main contribution is a proof that the minimum temperature reachable using Regev+BPQM is exactly equal to the reconstruction threshold temperature for noisy channels transmitting signals on a tree network. This equality can be understood via Renes' duality between classical and quantum channels, which we use to show that quantum decoding is possible exactly when classical reconstruction on the dual problem is impossible. M{é}zard and Montanari identified this reconstruction temperature with a dynamical glass transition predicted by the one-step replica-symmetry breaking (1RSB) cavity equation. It is conjectured that local samplers such as Metropolis Monte Carlo and Glauber dynamics cannot equilibrate efficiently below this reconstruction temperature but may do so above it; our large numerical experiments show close agreement with this prediction across hundreds of different problem parameters. Therefore, our results rigorously show that Regev+BPQM reaches a temperature for which, to our knowledge, there is no matching classical guarantee, and brings Regev+BPQM to the conjectured limit of efficient Gibbs sampling by classical local dynamics.

0.18

A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding

cs.IT ·2026-10-28 ·Daniella Bar-Lev, Ohad Elishco, Ryan Gabrys
theory similarity 0.57
Abstract

We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least $π/4$ under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately $0.793933445$, which explicit constructions attain asymptotically over every fixed finite field.

0.47

Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime

cs.LG stat.ML ·2026-10-05 ·Yujie Liu, Vincent Y. F. Tan, Yunbei Xu
theory similarity 0.57
Abstract

We study the sampling allocation of LinUCB in the small-gap regime, where the reward gaps are of order at most $n^{-1/2}$ over the decision horizon $n$. This scaling captures the hard instances underlying worst-case regret lower bounds, for which LinUCB is known to be near optimal up to logarithmic factors in $n$. Using a mean-field perspective, we characterize this allocation through the empirical sampling distribution, a macroscopic object that averages the effect of adaptive decisions over the horizon, and identify its limit as $n\to\infty$. We establish that in this regime, the empirical sampling distribution induced by LinUCB converges to the set of D-optimal designs. This central result reveals that, in the small-gap regime, LinUCB not only achieves near optimal minimax regret but also allocates samples in a way that is asymptotically efficient for learning the reward parameter, thereby connecting regret-driven online learning with information-efficient experimental design. Building on the optimal design limit, we obtain two useful consequences. First, we refine the asymptotic regret analysis of LinUCB in the small-gap regime by characterizing its leading-order constant in the limit. Second, we show that, despite LinUCB's adaptive sampling strategy, the regularized least-squares estimator satisfies a central-limit-type theorem in the small-gap regime, thereby enabling valid statistical inference for the reward parameter.

0.27