p-less Sampling: A Robust Hyperparameter-Free Approach for LLM Decoding

1. Problem Statement

Large Language Models (LLMs) rely on sampling-based decoding strategies to generate diverse and coherent text. While methods like Top-k, Top-p (nucleus), $\epsilon$-sampling, Mirostat, and Min-p have improved upon deterministic greedy decoding, they suffer from significant limitations:

• Hyperparameter Sensitivity: These methods require tuning specific hyperparameters (e.g., $k$, $p$, $\epsilon$, target surprisal) that are highly sensitive to the generation task and the sampling temperature ($\tau$).
• Temperature Instability: As temperature increases (to encourage diversity), existing methods often fail to adapt their truncation thresholds effectively. This leads to the admission of too many low-probability tokens, causing text degeneration (hallucinations, incoherence, and gibberish).
• Lack of Information-Theoretic Grounding: Many methods rely on fixed thresholds or single-statistic heuristics (e.g., the mode probability in Min-p) rather than utilizing the full information of the token probability distribution.

2. Methodology: p-less Sampling

The authors propose p-less sampling, a parameter-free, information-theoretic approach that dynamically determines a truncation threshold based on the entire token probability distribution at each decoding step.

Core Concept

The method defines a threshold probability, $L[P]$, representing the likelihood of a correct random guess given the current token distribution. Tokens are admitted to the sampling pool only if their probability is at least as high as this threshold.

Mathematical Formulation:
Let $P_\theta(v | x_{1:t-1})$ be the predicted probability of token $v$ given the context. The threshold $L[P]$ is calculated as the sum of squared probabilities (the second moment of the distribution):
$$L[P] = \sum_{v \in V} P_\theta(v | x_{1:t-1})^2$$

The sampling set $V_{p-less}$ is constructed as:
$$V_{p-less} = \{ v \in V : P_\theta(v | x_{1:t-1}) \ge L[P] \}$$

The next token is sampled from $V_{p-less}$ using the normalized probabilities.

Key Properties

1. Dynamic Adaptation: The threshold $L[P]$ changes at every step based on the current distribution's entropy.
   • Low Entropy (High Confidence): $L[P]$ is high, admitting only a few high-probability tokens.
   • High Entropy (High Uncertainty): $L[P]$ drops, admitting a broader range of tokens (including long-tail tokens) to maintain diversity without collapsing into randomness.
2. Connection to Rényi Entropy: The threshold $L[P]$ is mathematically equivalent to the exponential of the negative Rényi entropy of order 2 (Collision Entropy):
   $$L[P] = e^{-H_2(P)}$$
   This provides a principled information-theoretic justification for the method.
3. Hyperparameter-Free: No external parameters (like $p$ or $k$) need to be tuned.
4. p-lessnorm Variant: A relaxed version ($\bar{L}[P]$) is proposed for scenarios where diversity is prioritized over coherence, effectively lowering the threshold by subtracting the likelihood of an incorrect random guess.

Efficiency Advantages

Unlike Top-p (which requires sorting probabilities) or Min-p (which requires finding the mode), p-less operates directly on the empirical distribution.

• Complexity: Reduces time complexity from $O(|V| \log |V|)$ to $O(|V|)$.
• No Sorting: Eliminates the need to sort the vocabulary, significantly speeding up inference.

3. Key Contributions

1. Introduction of p-less: A robust, hyperparameter-free sampling strategy grounded in information theory (Rényi entropy).
2. Theoretical Grounding: Established the link between the sampling threshold and the second moment of the probability distribution, proving it acts as an unbiased estimator of the probability of a correct random guess.
3. Comprehensive Evaluation: Validated across three LLMs (Llama-2-7B, Mistral-7B, Llama-3-70B) and five datasets covering math, logical reasoning (GPQA, GSM8K, QASC, CSQA), and creative writing (Writing Prompts).
4. Efficiency Analysis: Demonstrated superior inference-time efficiency (faster sampling speed and shorter generation lengths) compared to baselines.

4. Experimental Results

Performance on Math & Logical Reasoning

• Metric: Area Under the Accuracy-Temperature Curve (AUC).
• Findings: p-less and p-lessnorm consistently outperformed Top-p, Min-p, $\epsilon$-sampling, $\eta$-sampling, and Mirostat across all models and datasets.
• Temperature Robustness: While other methods showed significant accuracy degradation as temperature increased (e.g., Top-p and $\epsilon$-sampling often dropped to near-zero accuracy at $\tau=2.0$), p-less maintained high accuracy even at high temperatures.
  • Example: On GSM8K with Llama-2-7B, p-less achieved an AUC of 0.267, significantly outperforming Min-p (0.256) and Top-p (0.210).

Performance on Creative Writing

• Metric: Length-controlled win rate (vs. default sampling).
• Findings: p-less achieved the best performance at temperatures $> 1.0$. Other methods suffered severe quality degradation at high temperatures, whereas p-less produced coherent and diverse stories.
• Human Evaluation: In a study with human annotators, stories generated by p-less were preferred over default sampling and other methods, with a win rate of 58.8% (rising to 72.7% for unanimous agreements).

Efficiency and Diversity

• Inference Speed: p-less was the fastest method, achieving a 22% reduction in average sampling time per token compared to Min-p. This is attributed to the lack of sorting operations.
• Generation Length: p-less produced shorter generations on average compared to Top-p and Min-p, especially at high temperatures, without sacrificing accuracy. This indicates better control over verbosity.
• Diversity-Accuracy Trade-off: p-less achieved a Pareto-optimal frontier, offering higher accuracy for a given level of diversity compared to other methods.

5. Significance and Conclusion

The paper demonstrates that p-less sampling offers a superior alternative to existing truncation-based decoding methods by:

1. Eliminating the need for hyperparameter tuning, making it universally applicable across different tasks and models.
2. Providing robustness against high-temperature settings, preventing the text degeneration common in other methods.
3. Improving computational efficiency through a simpler, non-sorting algorithmic approach.

By grounding the decoding process in information theory (specifically Rényi entropy), p-less provides a principled mechanism to balance coherence and diversity dynamically. The results suggest that LLM decoding can be significantly improved by leveraging the full statistical properties of the output distribution rather than relying on heuristic thresholds.

Code Availability: The authors state that the code will be made publicly available to facilitate reproducibility.