Min-$k$ Sampling: Decoupling Truncation from Temperature Scaling via Relative Logit Dynamics

1. Problem Statement

Large Language Models (LLMs) rely on decoding sampling strategies to generate text. While mainstream methods like Top-k, Top-p (Nucleus), and Min-p effectively balance diversity and accuracy by truncating the probability space, they share a critical flaw: extreme sensitivity to the temperature parameter ($T$).

• The Issue: As temperature increases, probability distributions flatten. Probability-based methods struggle to distinguish between high-confidence tokens and low-quality "long-tail" noise. This leads to the inclusion of semantically irrelevant tokens, causing "semantic collapse" (where generated text becomes incoherent or repetitive) at high temperatures ($T > 2.0$).
• Limitations of Existing Solutions: Recent logit-space approaches like Top-n$\sigma$ achieve temperature invariance by using global statistics (mean and standard deviation of logits). However, they are susceptible to interference from background noise in the long tail and fail to capture fine-grained "semantic cliffs" (sharp transitions between confident and uncertain tokens) among top candidates. They also remain sensitive to their own hyperparameters.

2. Methodology: Min-k Sampling

The authors propose Min-k Sampling, a dynamic truncation strategy that operates in the logit space to identify the optimal truncation point based on the local geometric structure of the logit distribution, independent of temperature scaling.

Core Mechanism

The method analyzes the sorted logit vector to detect a "semantic cliff"—a sharp drop in logit values indicating the boundary between high-confidence core tokens and uncertain long-tail noise.

1. Sorting and Normalization:

   • Logits ($l$) are sorted in descending order: $l_1 \ge l_2 \ge \dots \ge l_{|V|}$.
   • A dynamic range $R_l = l_1 - l_{|V|}$ is computed to normalize the values, ensuring invariance to linear transformations (like temperature scaling).

2. Weighted Relative Decay:

   • Instead of using global statistics, Min-k computes a position-weighted relative decay rate ($w_i$) for each step in the sorted sequence:
     $$w_i = \frac{l_i - l_{i+1}}{R_l} \cdot \frac{1}{i}$$
   • The term $\frac{1}{i}$ acts as a positional weight, emphasizing changes near the "head" of the distribution (high-confidence tokens) and suppressing noise from the tail.

3. Cliff Detection:

   • The truncation point $k_{cliff}$ is determined by finding the index $i$ with the maximum weighted decay:
     $$k_{cliff} = \arg\max_i w_i$$
   • This identifies the most pronounced semantic boundary.

4. Dynamic Fallback Mechanism:

   • In cases of extreme uncertainty where logits are nearly flat (no clear cliff), the algorithm risks selecting $k=1$. To prevent this, a fallback size $k_{fallback}$ is calculated based on the inverse of the dynamic range ($R_l^{-1}$).
   • The final candidate size is $k = \max(k_{cliff}, k_{fallback})$.

5. Sampling:

   • The top-$k$ logits are retained; the rest are set to $-\infty$.
   • The truncated logits are then scaled by temperature $T$ and passed through Softmax.

Theoretical Guarantee: Temperature Invariance

The paper formally proves that Min-k is strictly temperature-invariant.

• Proof Logic: When logits are scaled by temperature $T$ ($l' = l/T$), the dynamic range scales by $1/T$, and the logit differences scale by $1/T$. These factors cancel out in the relative decay calculation ($d'_i = d_i$). Consequently, the position of the maximum decay ($i^*$) and the resulting truncation size $k$ remain identical regardless of the temperature value.

3. Key Contributions

1. Novel Truncation Strategy: Introduction of Min-k, which dynamically locates "semantic cliffs" using local logit shape analysis rather than global statistics or fixed probability thresholds.
2. Temperature Invariance: Formal proof and empirical demonstration that Min-k maintains consistent truncation boundaries across all temperature settings, decoupling diversity control from noise admission.
3. Robustness: The method exhibits low sensitivity to hyperparameters (specifically the fallback constant $\tau$), making it easier to deploy than Top-n$\sigma$ or probability-based methods.
4. Comprehensive Evaluation: Extensive testing across mathematical reasoning, creative writing, and human evaluation benchmarks.

4. Experimental Results

The authors evaluated Min-k against Top-k, Top-p, Min-p, Mirostat, $\eta$-sampling, and Top-n$\sigma$ using LLaMA-3 (8B, 70B) and Qwen3 (4B, 30B) models.

• Mathematical Reasoning (AQuA, GSM8K, GPQA, MATH500):

  • High-Temperature Resilience: Traditional methods (Top-p, Min-p) suffer near-total accuracy collapse (approaching 0%) at $T=10.0$. Min-k maintains high accuracy (e.g., ~74-79% on GSM8K) even at $T=10.0$.
  • Superiority: Min-k consistently outperforms Top-n$\sigma$ and other baselines across diverse models and datasets.

• Creative Writing (AlpacaEval 2.0):

  • Min-k achieves the highest win rates against greedy decoding. At $T=3.0$ and $T=10.0$, it significantly outperforms Top-n$\sigma$ and probability-based methods, which degrade to near-zero win rates.

• Semantic Noise Analysis:

  • Quantitative analysis shows that while Top-p and Min-p reach ~100% semantic noise rates at $T \ge 2.0$, Min-k maintains a negligible noise rate (<10%) even at $T=10.0$, effectively filtering long-tail noise.

• Human Evaluation:

  • In a pairwise comparison of 200 samples, Min-k was preferred over Top-n$\sigma$ in 37.5% of cases (vs. 33.5% for Top-n$\sigma$), with the remaining being ties.

• Efficiency:

  • Min-k introduces a minimal computational overhead (~3.73% slowdown compared to greedy decoding), comparable to Top-p and Top-n$\sigma$, making it suitable for real-time deployment.

5. Significance

Min-k Sampling represents a paradigm shift in LLM decoding by addressing the fundamental limitation of temperature sensitivity in truncation strategies.

• Decoupling: It successfully decouples the control of diversity (via temperature) from the control of noise admission (via dynamic logit truncation).
• Reliability: It acts as a "safety rail" for high-temperature generation, enabling models to explore creative spaces without sacrificing logical coherence or semantic integrity.
• Generalizability: The method is scale-invariant, performing robustly on both small (4B/8B) and large (30B/70B) models, suggesting it is a fundamental improvement to the decoding process for large language models.

In conclusion, Min-k offers a theoretically grounded, empirically superior, and practically efficient solution for generating high-quality text from LLMs, particularly in scenarios requiring high creativity or operating under extreme temperature settings.