Truncation Samplers Are Nested: Comparing Decoding Rules Is a Measurement Problem

Rasul Khanbayov; Hasan Kurban

cs.LGOct 11, 2026

Truncation Samplers Are Nested: Comparing Decoding Rules Is a Measurement Problem

Authors: Rasul Khanbayov, Hasan Kurban

Organizations: College of Science and Engineering, Hamad Bin Khalifa University, Doha, Qatar

Abstract

Settling one comparison between two truncation samplers has cost six thousand A100-hours, and nothing says in advance how far apart two samplers can be. We observe that almost every deployed truncation rule keeps a prefix of the probability-sorted vocabulary, so any two such rules are nested at every decoding step. Nesting yields a closed-form per-step distance and a coupling under which both samplers emit identical text until they first disagree. Accumulated over a generation, this gives a separation certificate that bounds the difference between two samplers on any bounded outcome, is computable from logs a comparison already produces, and equals their sequence-level total variation distance exactly when neither rule ever overtakes the other. Two consequences follow without measurement: exactness is fragile, and certifying a small difference requires the two retained masses to agree to very high precision at every step. On six open-weight models over four math and science benchmarks, the certificate for every hyperparameter grid we tested is at least 0.998, so a bound alone rarely settles a comparison, although two members of one family can be far closer. What remains useful is the coupling, which gives an unbiased paired estimator that cuts variance $1.2$ - $3.8\times$ against prompt-level pairing. Read against benchmark sizes at the default pair's variance and our point estimate of its between-prompt component, resolving a one-point difference needs 8 to 32 samples per prompt on GSM8K, MATH-500 and GPQA-Diamond and about 210 on AIME 2025; at that component's upper confidence bound GPQA-Diamond needs more than 32 and AIME 2025 cannot be resolved at any sample count. Choosing a truncation sampler is a measurement problem at least as much as a design one. The code is available at https://github.com/KurbanIntelligenceLab/truncation-samplers.

Figures & tables

Sampler	Cutoff rule	Prefix	Swept
basic (no truncation)	$K=V$	$\checkmark$	single
top- $k$ ( Fan et al., 2018 )	$K=k$	$\checkmark$	$\bullet$
top- $p$ ( Holtzman et al., 2019 )	smallest $K$ with $Z_{K}\geq p$	$\checkmark$	$\bullet$
$\epsilon$ ( Hewitt et al., 2022 )	keep $p_{(i)}\geq\epsilon$	$\checkmark$	$\bullet$
$\eta$ ( Hewitt et al., 2022 )	keep $p_{(i)}\geq\min\{\epsilon,\sqrt{\epsilon}e^{-H}\}$	$\checkmark$	$\bullet$
min- $p$ ( Nguyen et al., 2025 )	keep $p_{(i)}\geq p_{\mathrm{base}}\,p_{(1)}$	$\checkmark$	$\bullet$

Table 1: Most deployed truncation samplers return a cutoff index in the sorted order, so the retained set is a prefix and any two such rules are nested at every step; Top-W and locally typical sampling, marked below the rule, do not. The nine rows above the gap are the family used in Section 4 : six marked

\bullet

each contribute six hyperparameter values, and three marked single (basic,

p

-less and Top-H, none swept over multiple settings) contribute one member each.

Figure 2: The coupling on one GSM8K prompt (Qwen3-1.7B, min-

p

versus top-

p

T{=}256

). (a) The rules share tokens until step

9

, where the draw lands in the band: top-

p

keeps it, min-

p

redraws, and both continuations later reach the correct answer. (b) The next-token distribution at the fork, with each rule’s cutoff.

Panel of Figure 3 — Figure 3: Measurements against the two structural results. Markers are measured, solid lines are theory. (a) The sufficient budget of Corollary 6 (a) for $\mathrm{Sep}_{T}\leq 0.1$ is flat in $T$ ; measured $\Delta_{T}$ exceeds it $130$ – $261\times$ for the matched pairs of Table A1 (triangles, $T{=}1024$ ) and $163$ – $2431\times$ for the AIME series (circles; gray dashes extend its per-token rate, $0.016\,T$ ). (b) Proposition 5 ’s bound on the no-flip probability for three $\varepsilon$ , against the matched pairs’ measured $1-\Pr[\text{flip}]$ at $T{=}1024$ . Within a family ( $\varepsilon{=}0$ ) exactness holds at every horizon; at $\varepsilon{=}0.05$ the bound is $3.1\times 10^{-23}$ by $T{=}1024$ .

Task	Pair	Reduction	95% CI, significance
GSM8K	min- $p$ (0.05) vs top- $p$ (0.95)	$3.8\times$	$[3.1,4.9]$ , significant after Holm
GSM8K	top- $k$ (10) vs top- $p$ (0.70)	$1.3\times$	$[1.1,1.5]$ , significant after Holm
GSM8K	$\epsilon$ (0.1) vs $\eta$ (0.0003)	$1.3\times$	$[1.2,1.6]$ , significant after Holm
MATH-500	min- $p$ (0.05) vs top- $p$ (0.95)	$1.7\times$	$[1.2,2.4]$ , bootstrap $p=0.023$
GPQA-Diamond	min- $p$ (0.05) vs top- $p$ (0.95)	$18.7\times$	$[8.0,62.1]$ , bootstrap $p=0.16$

Table 2: The coupled estimator’s variance reduction against prompt-level pairing. GSM8K rows are Qwen3-1.7B with five seeds, cluster bootstrap intervals and Holm correction across the three pairs; the MATH-500 and GPQA-Diamond rows replicate the default pair.

Figure 4: Certificates are large, accuracy gaps are small (the eight pairs of Table A3 ). (a) Theorem 3 bounds the expected gap by the certificate (cone). (b) The boxed region with

95\%

CIs. The gray band,

\pm 1.96\sqrt{\mathrm{Sep}_{T}/n}

with

n{=}1{,}000

, is the zero-gap spread implied by Proposition 7 ; it is conservative in using a variance bound and anti-conservative in treating

200

prompts

\times

five seeds as independent. Points near

\mathrm{Sep}_{T}{=}0.99

are offset by

\pm 0.009

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Pair, matched to $\rho=0.95$	$\rho$	$\mathrm{Sep}_{1024}$	$\Delta_{1024}$	$\Pr[\text{flip}]$
	achieved
min- $p$ vs top- $p$	$0.954$	$0.993$	$13.67$	$0.998$
top- $n\sigma$ vs top- $p$	$0.957$	$0.994$	$13.93$	$0.996$
$\eta$ vs top- $p$	$0.978$	$0.998$	$27.55$	$0.374$

Appendix

Table A1 : At a matched operating point the certificate stays large and stops being exact (Qwen3-8B, MATH-500,

T{=}1024

). Rows are ordered by how closely the pair was matched; the flip-rate paragraph above discusses the dose-response reading of the flip-rate column.

$k$	$\tau^{2}=0$ (point estimate)	$\tau^{2}=9.3\times 10^{-4}$ (upper bound)
$1$	$6{,}318$	$6{,}392$
$8$	$790$	$863$
$32$	$197$	$271$
$\approx 210$	within AIME 2025’s $30$ (untested)	$103$
any $k$	no floor	never below about $73$

Appendix

Table A2 : Prompts needed to resolve a one-point difference with

k

coupled samples per prompt (default pair, GSM8K variance decomposition). Benchmark sizes: GSM8K

1{,}319

, MATH-500

500

, GPQA-Diamond

198

, AIME 2025

30

Panel of Figure 8 — Figure A1 : The grid certificate on all nine configurations, as $1-\mathrm{Sep}_{T}(\mathcal{G})$ on a log axis, so a point further right is a looser certificate. Circles are five-seed estimates with $95\%$ CIs, diamonds single-seed estimates. Two values fall below floating-point resolution and are drawn at $10^{-9}$ . Only Qwen3-1.7B/GSM8K ( $0.998064$ ) lies right of the $\mathrm{Sep}_{T}=0.9997$ line.

Panel of Figure 9 — Figure A2 : Prompts needed to resolve a one-point difference with $k$ coupled samples per prompt (default pair, GSM8K variance; Table A2 ). The solid line is the point estimate $\tau^{2}=0$ ; the band reaches the upper bound of $\tau^{2}$ , where the requirement never falls below about $73$ . Markers show where each curve meets a benchmark’s size (dashed). The model is fitted on five samples per prompt, so everything beyond $k=5$ is extrapolated, with GSM8K’s $\tau^{2}$ used for every benchmark.

Pair	Family	$\mathrm{Sep}_{T}$	gap	gap 95% CI
min- $p$ (0.05) vs top- $p$ (0.95)	cross	$0.710$	$0.017$	$[0.000,0.034]$
top- $k$ (10) vs top- $p$ (0.70)	cross	$0.992$	$-0.023$	$[-0.052,0.006]$
$\epsilon$ (0.1) vs $\eta$ (0.0003)	cross	$0.989$	$0.013$	$[-0.015,0.041]$
top- $p$ (0.98) vs top- $p$ (0.99)	within	$0.437$	$-0.002$	$[-0.014,0.010]$
top- $k$ (10) vs top- $k$ (320)	within	$0.541$	$0.003$	$[-0.009,0.015]$
top- $k$ (10) vs top- $k$ (80)	within	$0.517$	$0.003$	$[-0.008,0.014]$

Appendix

Table A3 : The eight pairs behind the predictiveness check (Qwen3-1.7B, GSM8K,

T{=}256

, five seeds). Family marks whether the pair compares two different truncation rule types (cross) or the same rule at two hyperparameter settings (within), including the negative control.

Language Model Generation Evaluation

Language model generation evaluation measures the quality, reliability, diversity, and task fit of outputs produced by language models.

See all 396 papers

Temperature Fragility and the Conditional Benefits of Truncation Sampling
Sep 14, 2026Francesco La RosaLLM Evaluation Language Model Decoding
University of Edinburgh
Adaptive Nucleus Truncation for Long-Form Reasoning
Jun 12, 2026Ousmane Amadou DiaLanguage Model Decoding Adaptive Sampling
Revisiting Lossy Verification in Speculative Decoding: Mechanisms, Trade-offs, and Failure Modes
Jul 29, 2026Tianyu Wang, Yuxuan Zhou, Wenbin Wang +3Speculative Decoding LLM Inference Acceleration
1Independent Researcher · 2Baidu Inc. · 3Zhejiang University

Sep 14, 2026J/K move · Enter open · S save

Temperature Fragility and the Conditional Benefits of Truncation Sampling

Francesco La Rosa

University of Edinburgh

LLM Evaluation Language Model Decoding

Open paper AskPDF arXiv

Large language models generate text by sampling each token from a predicted distribution, and a temperature parameter sets how far the draw strays from the most probable tokens. Truncation samplers such as top-p and min-p discard the least probable tokens before the draw, so that sampling at high temperature stays coherent. Their reported accuracy gains come from temperatures of 1.5 to 3, while the defaults of deployed systems cluster between 0.6 and 1.0. Whether they change accuracy at those defaults, and for which models, has not been measured. We test thirteen open-weight models on GSM8K and MMLU-Pro at temperatures 0.7, 1.0, and 1.3 in one controlled pipeline, ten of them under eight decoding configurations. Six of the thirteen models lose 17 to 38 accuracy points on MMLU-Pro between 0.7 and 1.3, and the other seven lose at most 10. The lost accuracy comes from generations that run to the token limit or never state an answer. These results suggest that truncation samplers improve accuracy primarily when higher temperatures substantially degrade model performance. Where accuracy remains stable across temperatures, none of the tested truncation samplers improves on plain temperature sampling.

Abstract

Language Model Generation Evaluation

Explore similar work

Temperature Fragility and the Conditional Benefits of Truncation Sampling

Adaptive Nucleus Truncation for Long-Form Reasoning

Revisiting Lossy Verification in Speculative Decoding: Mechanisms, Trade-offs, and Failure Modes