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

Sep 14, 2026

Temperature Fragility and the Conditional Benefits of Truncation Sampling

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.

Francesco La Rosa

University of Edinburgh

LLM Evaluation Language Model Decoding

Ask PDF

Jun 12, 2026

Adaptive Nucleus Truncation for Long-Form Reasoning

Sampling plays an important role in long-form language-model reasoning. Over thousands of decoding steps, small changes in the candidate token set can compound into different reasoning trajectories, stability profiles, and final answers. Existing truncation methods such as top-

p

, min-

p

, and fixed top-

nσ

sampling improve over unrestricted sampling, but they rely on fixed thresholds that cannot adapt to changes in entropy, task difficulty, training stage, or generation budget. We introduce Adaptive Nucleus Truncation Sampling (ANTS), which extends top-

nσ

sampling from a fixed decoding rule into an adaptive rollout-control mechanism for long-form generation. ANTS selects standardized neighborhoods around the maximum logit before temperature scaling, adapts the truncation width using an entropy-conditioned controller, and retains a no-truncation fallback arm to stabilize training when truncation becomes unsafe. On a 33B-total / 4B-active sparse Mixture-of-Experts reasoning model, ANTS improves average performance over percentage-based benchmarks by +1.9, +3.8, and +5.2 points at 8K, 16K, and 32K generation budgets, respectively. The strongest gains appear on instruction following and mathematical reasoning, with IFBench improving by more than 10 points at 32K and AIME 2025 improving by 7 points. Code generation reveals an important budget interaction. On Codeforces, ANTS trails the baseline at 8K, but reverses this gap and substantially improves ELO at 16K and 32K. These results suggest that sampler design should be treated not just as a decoding hyperparameter, but as part of how we stabilize and scale long-budget reasoning.

Ousmane Amadou Dia

Language Model Decoding Adaptive Sampling LLM Reasoning Large Reasoning Models

Ask PDF

Jul 29, 2026

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

Speculative Decoding (SD) accelerates large language model inference by allowing a lightweight draft model to propose tokens that are subsequently verified in parallel by a larger target model. Recent approaches introduce lossy verification schemes to further improve efficiency by relaxing strict distributional matching. Yet such relaxation silently rewrites the decoding distribution, and the resulting acceleration can come at the cost of unstable, sometimes severely degraded generation quality. In this work, we present a principled analysis of the distributions induced by lossy verification methods. We show that many seemingly distinct approaches differ only superficially and can be classified into two categories: truncation-based verification and collaborative verification. We further construct a diagnostic evaluation framework across curated benchmarks. For truncation-based methods, we identify a fundamental pitfall: performance can degrade significantly compared to the true truncation sampling baseline due to distributional distortion. For collaborative verification, we uncover a key principles: controlling the overshoot of draft probabilities relative to target probabilities is essential to prevent low-quality outputs. Our code is available at https://github.com/ZhouYuxuanYX/Fast-HSD.

Tianyu Wang, Yuxuan Zhou, Wenbin Wang +3

1Independent Researcher · 2Baidu Inc. · 3Zhejiang University

Speculative Decoding LLM Inference Acceleration

Ask PDF

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