acceptodds
Under review as a conference paper at ICLR 2027

The Optimal pass@k Decoder is Tilted Temperature

Abstract

It is known that larger sample budgets benefit from higher sampling temperatures in LLMs. However, we lack a formal understanding of the objective that temperature tuning optimizes and how it accomplishes this. We seek to answer these questions: we pose decoding as pass@ 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 tilted temperature . Here, the tilt comes from a verifier potential 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 , the resulting optimal temperature increases with , 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.

Primary area:
learning theory
Keywords:
pass@k, temperature sampling, LLM decoding, constrained optimization

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_kVHTOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper takes a deep dive into the problem of LLM decoding, specifically focused on exploring the optimal temperature needed for pass@k maximization. The authors provide significant theoretical evidence that their tilted temperature proposition is optimal for pass@k optimization subject to constraints that prevent two well-known failure modes in decoding (Dirac sampling on one hand and uniform sampling on the other). The optimal temperature is difficult to estimate so the authors provide two practical implementations in different regimes. Empirical results of deploying this optimal temperature strategy on a coding task show improvement for a few coding LLM variants.

Critical strengths

Strength 1: theoretical backed decoding temperature optimality when the pass@k objective is subject to practical constraints to avoid extreme failure modes.

Strength 2: empirical results that back the theoretical analysis and specifically the practical algorithms proposed for computing the optimal temperature.

Critical weaknesses

The reviewer does not see any major weaknesses in this theoretical paper that support rejection.

Questions for authors
  1. The authors do not provide a computational analysis of the proposed temperature estimation strategy as compared to the non-optimal baselines (e.g. Fixed T and AdaptT). It is important to know what the extra computational cost will be if the optimal temperature is computed regularly. If this step significantly slows down decoding, this will be an issue for practical use.

  2. The authors mention that CTD tracks other temperature strategies; however, the results in Table 1 show that CTD can be much worse even as compared to Fixed T. Can the authors elaborate on why this is?

1 comment

We thank the reviewer for the positive assessment and the two practical questions. We also refer the reviewer to the general response for the corrected Table 1.

Computational cost: Fixed-TT, AdapT and CTD have identical generation cost (one forward pass per token). CTD's calibration is a one-off offline step on the training problems: sampling a small calibration pool, running the verifier, and a scalar OLS fit. TMAD-Gated is more expensive than these baselines. Its overhead comes from the short lookahead, while the continuation head itself is a low-rank bilinear map with negligible cost. The gate confines this overhead to a subset of positions: tokens where the model is uncertain or that are structurally critical, such as the beginning of a new logical statement in code. Elsewhere, decoding uses conservative sampling at the cost of plain temperature sampling. With an active fraction α\alpha of positions, cc refined candidates and lookahead depth LL, this amounts to 1+αcL1+\alpha cL single-token forward passes per generated token (each lookahead step reuses the cached prefix), plus a copy of the KV cache per refined candidate; cc and LL directly trade cost for accuracy.

Why can CTD be worse than Fixed-TT: This is consistent with the theory: Theorem 7 states that CTD should track the best temperature, not beat it, up to the dropped correction term and the calibration error ε\varepsilon. Unlike CTD, Fixed-TT is tuned directly to maximize validation pass@5. CTD instead selects its exponent through entropy matching, using the fitted calibration relationship as a certificate. This entropy-matched exponent need not coincide with the pass@kk-tuned temperature, especially under imperfect calibration or residual continuation effects. Thus Fixed-TT can outperform CTD in some settings. We have clarified this distinction in the revised text.

Reviewer_NNnROpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a theoretical framework for combining temperature sampling with verifier guidance to maximize pass@k under explicit diversity and plausibility constraints. It formulates decoding with an entropy floor to preserve diversity and a cross-entropy ceiling relative to the base model to limit implausible generations, then derives the optimal “tilted temperature” rule, �0�.Here,�1��0�. Here, �1� is a continuation value computed through a backward Bellman recursion that combines terminal verifier rewards with future model likelihood, connecting sequence-level success to token-level decisions. The analysis also identifies calibration and continuation conditions under which ordinary temperature sampling approximates the optimum. Its explanation for using higher temperatures at larger sampling budgets requires an explicit �2��2�-dependent diversity-budget rule; with fixed constraints, the optimizer itself is independent of �3��3�. These results motivate Calibrated Temperature Decoding (CTD), whose temperature-only inference path adds no generation-time overhead, and TMAD-Gated, a practical approximation that uses a learned continuation-success predictor and short lookahead at uncertain or structurally important tokens. On held-out HumanEval and MBPP subsets across three models, TMAD-Gated achieves the highest mean pass@k in 16 of 18 tested model–benchmark–sample-budget settings.

Critical strengths

The paper’s critical strength is its explicit mathematical connection between sequence-level task success and token-level decoding. By formulating diversity and plausibility as separate constraints, it derives a sampling rule that combines temperature scaling with a verifier-informed continuation value, clarifying how local token choices can account for eventual completion quality. Particularly valuable is its distinction between the exact sequence-level optimum and practical token-level approximations: the calibration analysis identifies conditions under which ordinary temperature sampling is adequate and bounds the effects of calibration error and omitted continuation information. The end to end theoretical formulation is sound.

Critical weaknesses

One potential weakness of the paper is the gap between its exact optimality theory and the decoders performance evaluated in practice. The theoretically optimal rule requires a Bellman continuation potential that combines future model likelihoods with terminal verifier rewards, however, at least from the paper I did not see the theoretical establishment of the decoders satisfying the original diversity and plausibility constraints. I hope the authors can clarify that in the rebuttal.

Questions for authors

Do you think TMAD-Gated can achieve good results in more complicated benchmarks such as SWE-bench?

2 comments

We thank the reviewer for the positive assessment and for the precise observations. We also refer the reviewer to the general response for the corrected Table 1.

Constraint satisfaction: We thank the reviewer for this distinction. The exact optimum of Theorem 1 satisfies both constraints by construction, but its Bellman recursion is intractable for realistic LLMs; Theorems 2--3 bound how far the online approximation deviates from it. The practical decoders of Section 4 are designed to respect the constraints approximately rather than enforce them exactly: CTD selects its exponent through entropy matching, using the fitted calibration relationship as a certificate, while TMAD-Gated selects among a finite grid of tilted-temperature regimes with a plausibility term in the regime score. Both are theory-guided approximations of the optimal rule, and we have made this distinction explicit in the revision.

SWE-bench: We thank the reviewer for this suggestion. Our theoretical framework requires only a binary terminal verifier, which SWE-bench provides through its test suites. However, SWE-bench involves repository-level patch generation, often within an agentic workflow, whereas our current implementation targets single-shot code generation. Extending TMAD-Gated would require adapting its continuation-success predictor to substantially longer and more complex trajectories, with additional lookahead costs. We consider integrating verifier-guided decoding into such workflows an interesting direction for future work.

Thanks authors for the detailed rebuttal and further clarification. I think the explanation makes sense to some extent, however, I still do not get exactly how the practical decoders in Section 4 work. The authors mentioned that the design is the theory-guided approximations of the optimal rule, how does the approximation guide the decoding in the right direction? Overall I want to remain my score, but I think it would be helpful if the authors can further strengthen the theoretical explanation particularly for the practical decoders.

Reviewer_PBpWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper poses decoding as pass@k maximization under an entropy floor and a per-token cross-entropy ceiling, and shows that the optimum is a tilted temperature, qt⋆∝(pteηVt)1/Tq_t^\star \propto (p_t e^{\eta V_t})^{1/T}, where VtV_t is a soft-Bellman continuation potential (Theorem 1). A budget-selection rule makes the induced temperature rise with kk (Prop. 3). J-EOS tracks the two dual prices online for a fixed potential estimate, and CTD reduces to temperature sampling when verdicts are affine in mean log-probability. Experiments compare CTD and a heuristic decoder, TMAD-Gated, with fixed-temperature and AdapT sampling on 64-problem HumanEval and MBPP splits for three models.

Critical strengths

The proofs are correct. The main result (Theorem 1) is shown via the principle of optimality and occupancy-measure duality, the entropy-constrained cross-entropy minimality of tempering, and the binary-verifier value.

Critical weaknesses
  1. kk is not used in the optimization. Theorem 1 is the standard soft-Bellman solution of entropy-regularized control, and since pass@k increases with single-sample success, its optimum is the same for every kk. A natural source of kk-dependence is never modeled.
  2. The experiments do not isolate the tilt. TMAD-Gated combines conservative sampling, structural gating, lookahead, and a learned tilt together. So gains cannot be attributed to the potential alone.
  3. Baselines are below published results: Code Llama 7B reports 59.6% HumanEval and 66.7% MBPP pass@10, against 34-36% and 40-44% here, and Qwen2.5-Coder-1.5B reports 59-69% MBPP pass@1, against 37-42% baseline pass@5 in the MBPP row where TMAD-Gated gains most (9-13 points).
Questions for authors

Sima et al. (2026) already derive temperature sampling as the entropy-maximizing decoder under a cross-entropy budget, track it online by re-solving on each prefix, and prove an Ω(R)\Omega(R) lower bound. What do Theorems 2, 3, and 5 add beyond a second price and the verifier term?

1 comment

We thank the reviewer for checking the proofs and for the sharp questions. We take each point in turn.

Dependence on kk: We agree that for fixed budgets (β,γ)(\beta,\gamma), the optimizer is independent of kk, as already noted on page 2. The kk-dependence arises through the selection of the diversity budget β∗(k)\beta^*(k). Proposition 1 (revised manuscript; formerly Proposition 3 in Appendix F) proves that, under the stated assumptions, the induced optimal temperature is non-decreasing in kk in the high-coverage regime. Figure 2 illustrates this trend theoretically and empirically. We have used the additional page permitted during the revision period to explain the budget-selection mechanism and Proposition 1 explicitly in the main text.

Isolating the verifier tilt: We agree that TMAD-Gated combines several components and that the current experiments do not isolate their individual contributions. Conservative sampling and selective intervention are motivated by prior work, including AdapT (Zhu et al., 2024) and AdaDec (He et al., 2026), which identify uncertain and structurally critical positions as particularly important for code generation. Our gating mechanism applies the more expensive verifier-guided decoding only at these positions, while using conservative sampling elsewhere.

To isolate the tilt, we ran an ablation that sets η=0\eta=0 while keeping everything else fixed: the same gate, conservative temperature, candidate set, lookahead, continuation head, temperature T⋆T^\star, test split, and number of samples. The only change is that sampling uses q∝p1/Tq \propto p^{1/T} instead of q∝(peηS^)1/Tq \propto (p e^{\eta \hat S})^{1/T} (Qwen2.5-Coder-1.5B, HumanEval, 64 held-out problems, 15 samples per problem):

Methodpass@1pass@5pass@10pass@15
Fixed-TT (T∗=0.8T^*=0.8)34.262.473.979.7
TMAD-Gated, η=0\eta=035.264.375.681.2
TMAD-Gated39.065.575.682.4
TMAD-Gated −- (η=0\eta=0)+3.8+1.20.0+1.2

The tilt yields its largest gain at pass@1 (+3.8 percentage points); the gain is +1.2 points at pass@5 and pass@15, while pass@10 is unchanged. This supports a benefit from verifier guidance beyond the gating mechanism, although the improvement is not uniform across kk. This ablation uses the corrected pipeline on the same 64-problem held-out subset.

Baselines below published results: We thank the reviewer; this comment led us to identify and correct three shared evaluation issues involving stop-sequence handling, prompt--completion whitespace, and premature truncation on MBPP (see the general response for details). After correcting these issues and re-running all methods, the reported gaps substantially narrowed, as shown in Table 1. The published CodeLlama results cited by the reviewer refer to CodeLlama-7B, whereas our experiments use the Python-specialized CodeLlama-7B-Python checkpoint.

Importantly, our evaluation uses only 64 held-out problems per benchmark, not the entire test sets; the other problems are used for tuning and training the continuation head. Differences of a few percentage points from full-benchmark published results are therefore plausible and should not be interpreted as exact reproduction.

Relation to Sima et al. (2026): We acknowledge that Sima et al. establish the foundations of temperature sampling and online price tracking. However, their objective maximizes diversity under a plausibility constraint, without directly optimizing downstream task success. This distinction is critical: generating diverse, plausible responses does not necessarily imply generating correct ones.

While our analysis builds on similar arguments, Theorem 2 extends price tracking to two coupled constraints, Theorem 3 establishes sequence-distribution and pass@k stability guarantees, and Theorem 5 characterizes when verifier guidance becomes unnecessary: under perfect calibration, the task-optimal distribution reduces to sequence-level tempering, with the entropy floor determining its exponent. Thus, unlike the diversity-oriented guarantees of Sima et al., our results characterize and provide guarantees for decoding explicitly optimized for downstream task success.

Reviewer_r9bkOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper seeks to formulate the problem of optimally sampling sequences from LLMs such that at least of one of k independently drawn sequences successfully solves the task as scored by a verifier. It formulates this as a problem of optimizing pass@k subject to an entropy floor to maintain diversity and a ceiling on the cross-entropy between the base and decoding distributions. To solve this problem where reward is delayed (only observed at the end of the sequence from the verifier), they introduce a verifier potential and show that the exact DP solution to the problem is in the form a “tilted temperature distribution”. They then go on to propose several ways to utilize this in solving for the optimal decoding including - (a) an approach to track the dual prices needed for the solution (assuming fixed verifier potential) (b) a calibration based approach to remove the dependence on the verifier potential and (c) a practical algorithm inspired by the results. Brief empirical results are presented on 2 benchmarks (HumanEval and MBPP).

Critical strengths

The paper is well-written and contributes a meaningful framework for analyzing the problem of optimal decoding under the pass@k criterion. The formulation and derivation of the optimal policy in the context of inference-time LLM decoding, the online price tracking analysis and the calibration reduction seem to be novel.

Critical weaknesses

There are several works in the RL literature that are similar to the formulation and tilted temperature result in the paper - Model-Based Relative Entropy Stochastic Search, Abdolmaleki et al.,2015, Model-Free Trajectory Optimization for Reinforcement Learning, Akrour et al., 2016; , SAC with automatic temperature, Haarnoja et al., 2018. The authors would do well to acknowledge these and delineate their contributions more precisely in the context of LLM decoding.

The empirical evaluation could be strengthened with comparison to more decoding algorithms and better tuning of baselines (e.g. unclear why Fixed-T temperature is only tuned to maximize pass@5 and reused). As such, the empirical results with the error bands don't seem significant.

Questions for authors

None

1 comment

We thank the reviewer for the careful reading and for recognizing the formulation, the online price-tracking analysis and the calibration reduction as novel. We address the two weaknesses below.

Relation to RL literature. We thank the reviewer for these references and have added them to the revised related-work discussion. MORE (Abdolmaleki et al., 2015) and MOTO (Akrour et al., 2016) are closely related to our work: they combine a KL bound with an entropy bound and obtain a closed-form update of the same geometric form as ours. SAC (Haarnoja et al., 2018) is also relevant, as it adapts the temperature as the dual variable of an entropy constraint, analogous to our entropy floor and its dual price. Our contributions lie in the decoding setting: the pass@kk objective under a sparse, delayed verifier reward, its reduction to a soft-Bellman verifier potential over the token tree, constraints defined relative to a fixed base model at inference time, and the resulting calibration and online-tracking analyses. We have revised the related-work section and the statement of contributions accordingly.

Baselines and significance. Please see the general response for the corrected Table 1. Following the reviewer's suggestion, we have included min-p sampling (Nguyen et al., 2025) as an additional decoding baseline. The table reports means and standard deviations on held-out 64-problem subsets for each benchmark; we do not claim statistical significance from these run-to-run summaries. Regarding Fixed-TT: each method is evaluated with a single configuration, from which all pass@kk values are computed on the same sample pool, and the temperature T⋆T^\star selected at pass@5 is shared by all methods that use one. We agree that selecting the temperature separately for each kk would strengthen the baselines. However, a fair comparison would require retuning every method per kk, which for TMAD-Gated means a separate full evaluation run for each kk; we therefore kept a single shared configuration across all methods in this paper.

Comments on the paper

1 comment

We thank the reviewers for their careful and constructive reviews. We summarize the main changes here and refer to this comment from the individual responses. Proposition and theorem numbers below refer to the revised manuscript.

Corrected evaluation pipeline. Prompted by Reviewer PBpW, we audited our evaluation pipeline and found three implementation issues, shared by all methods: (i) the matched stop sequence (e.g. \nif __name__) was kept before truncation, turning otherwise correct completions into syntax errors; (ii) for Code Llama's tokenizer, decoding the completion separately from the prompt dropped a leading space, breaking indentation on HumanEval; (iii) on MBPP, a stop sequence could fire before the function was written, leaving an empty completion. We fixed all three and re-ran every method. The corrected pass rates are substantially higher, largely resolving the discrepancies with published Code Llama results noted by the reviewer (see response to PBpW). Table 1 reports the corrected results, including the completed min-p baseline, on 64 held-out problems from each benchmark, rather than the full benchmark; the remaining problems are used for tuning and training the continuation head. The smaller evaluation subsets can account for residual differences from published benchmark-wide results.

Table 1. Pass@kk (%) with the corrected evaluation pipeline; mean ± standard deviation; evaluation on 64 held-out problems per benchmark with 15 samples per problem. The columns show HumanEval and MBPP side by side.

Qwen2.5-Coder-1.5B

MethodHumanEvalMBPP
Metricpass@5pass@10pass@15pass@5pass@10pass@15
Fixed-TT62.4 ± 3.173.9 ± 4.079.7 ± 4.159.9 ± 2.172.0 ± 1.878.1 ± 2.2
CTD61.9 ± 4.175.1 ± 3.581.2 ± 3.758.6 ± 0.768.1 ± 1.671.9 ± 1.5
AdapT62.1 ± 1.772.3 ± 2.776.6 ± 2.767.8 ± 1.078.2 ± 1.182.8 ± 0.8
min-p64.0 ± 2.373.7 ± 2.176.6 ± 2.464.9 ± 2.374.8 ± 2.079.7 ± 2.3
TMAD-Gated65.5 ± 3.575.6 ± 5.382.4 ± 2.870.9 ± 1.077.4 ± 1.482.8 ± 1.2

Qwen3-4B-Base

MethodHumanEvalMBPP
Metricpass@5pass@10pass@15pass@5pass@10pass@15
Fixed-TT72.4 ± 2.282.6 ± 1.885.9 ± 1.579.2 ± 0.988.1 ± 1.190.6 ± 0.9
CTD72.4 ± 2.581.7 ± 2.084.4 ± 2.275.5 ± 1.381.1 ± 1.182.8 ± 1.1
AdapT75.1 ± 1.582.2 ± 1.385.9 ± 1.581.9 ± 1.689.3 ± 1.290.6 ± 1.7
min-p76.4 ± 1.085.4 ± 1.789.1 ± 1.877.8 ± 0.685.9 ± 0.690.6 ± 1.0
TMAD-Gated78.3 ± 3.184.5 ± 3.187.5 ± 2.482.2 ± 0.687.6 ± 0.792.2 ± 1.0

CodeLlama-7B-Python

MethodHumanEvalMBPP
Metricpass@5pass@10pass@15pass@5pass@10pass@15
Fixed-TT56.3 ± 3.068.4 ± 3.275.0 ± 4.164.9 ± 1.270.7 ± 1.573.4 ± 1.2
CTD59.4 ± 3.370.2 ± 3.075.0 ± 3.064.9 ± 0.668.8 ± 0.870.3 ± 1.5
AdapT60.4 ± 1.870.4 ± 1.376.6 ± 1.360.8 ± 1.166.3 ± 1.268.8 ± 1.4
min-p60.3 ± 1.769.7 ± 1.273.4 ± 1.660.7 ± 1.566.1 ± 1.568.8 ± 1.5
TMAD-Gated61.3 ± 3.071.0 ± 1.975.4 ± 2.764.9 ± 1.366.7 ± 1.269.2 ± 1.3

Additional clarifications and related work. We have expanded the related-work discussion to address the connections to MORE, MOTO, and SAC. In the revised manuscript, we have moved the TMAD-Gated algorithm from the appendix into the main text and updated the experimental discussion to reflect the corrected results and held-out subset protocol. We have also moved the budget-selection result from Appendix F into the main text (now Proposition 1, formerly Proposition 3), clarifying how kk enters through the choice of diversity budget rather than through the optimizer at fixed budgets. The individual responses also provide an ablation isolating the verifier tilt (η=0\eta=0), clarify constraint satisfaction, and discuss the computational cost of TMAD-Gated.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.