Top-H Decoding: Adapting the Creativity and Coherence with Bounded Entropy in Text Generation
Authors: Erfan Baghaei Potraghloo
Seyedarmin Azizi
Souvik Kundu
Massoud Pedram
Venue: NeurIPS 2025 poster ()
Keywords: LLMs
Truncated sampling
Decoding Strategies
Primary area: deep_learning

Abstract: Large language models (LLMs), despite their impressive performance across a wide range of tasks, often struggle to balance two competing objectives in open-ended text generation: fostering diversity and creativity while preserving logical coherence. Existing truncated sampling techniques, including temperature scaling, top-*p* (nucleus) sampling, and min-*p* sampling, aim to manage this trade-off. However, they exhibit limitations, particularly in the effective incorporation of the confidence of the model into the corresponding sampling strategy. For example, min-*p* sampling relies on a single top token as a heuristic for confidence, eventually underutilizing the information of the probability distribution.  To effectively incorporate the model confidence, this paper presents **_top-H_ decoding**. We first establish the theoretical foundation of the interplay between creativity and coherence in truncated sampling by formulating an **entropy-constrained minimum divergence** problem. We then prove this minimization problem to be equivalent to an **entropy-constrained mass maximization (ECMM)** problem, which is NP-hard. Finally, we present top-H decoding, a computationally efficient greedy algorithm to solve the ECMM problem.  Extensive empirical evaluations demonstrate that top-H outperforms the state-of-the-art (SoTA) alternative of min-*p* sampling by up to **25.63%** on creative writing benchmarks, while maintaining robustness on question-answering datasets such as GPQA, GSM8K, and MT-Bench. Additionally, an *LLM-as-judge* evaluation confirms that top-H indeed produces coherent outputs even at higher temperatures, where creativity is especially critical. In summary, top-H advances SoTA in open-ended text generation and can be *easily integrated* into creative writing applications. The code is available at [https://github.com/ErfanBaghaei/Top-H-Decoding](https://github.com/ErfanBaghaei/Top-H-Decoding).

Top-H Decoding: Adapting the Creativity and Coherence with Bounded Entropy in Text Generation
Erfan Baghaei Potraghloo* Seyedarmin Azizi" Souvik Kundu', and Massoud Pedram" "
" Uniivesitty of Southern California, Los Angeles, USA 'Intel AI, USA
i Equal contribution authors
(baghaeip, seyedarm, pedram] @usc. edu, souvikk kundu@intel.com com
Abstract
Large language models (LLMs), despite their impressive performance across a wide range of tasks, often struggle to balance two competing objectives in open- ended text generation: fostering diversity and creativity while preserving logical coherence. Existing truncated sampling techniques, including temperature scal- ing, top-p (nucleus) sampling, and min-p sampling, aim to manage this trade-off. However, they exhibit limitations, particularly in the effective incorporation the confidence of the model into the corresponding sampling strategy. For ex- ample, min-p sampling relies on a single top token as a heuristic for confidence, eventually underutilizing the information of the probability distribution. To ef- fectively incorporate the model confidence, this paper presents top-H decoding. We first establish the theoretical foundation of the interplay between creativity and coherence in truncated sampling by formulating an intropy-constrained minimum divergence problem. We then prove this minimization problem be equivalent to an entropy-com conttpy-onnttriieed mass maximization (ECMM) problem, which NP-hard. Finally, we present top-H decoding, computationally efficient greedy algorithm to solve the ECMM problem. Extensive empirical evaluations demonstrate that top-H outperforms the state-of-the-art (SoTA) alternative of min-p sampling by up to 25.63% 63% on creative writing benchmarks, while maintaining robustness on question- question-answering answering datasets such GPQA, GSM8K, and JTT-Bench. Additionally, an LLM-a as-judge evaluation confirms that top-H indeed produces coherent outputs even at higher temperatures, where creativity is especially crit- ical. In summary, top-H advances So'A in open-ended text generation and can be easily integrated into creative writing applications. The code available
Introduction
Large language models (LLMs) have exhibited impressive abilities in open-ended generation tasks, including creative writing and multi-turn dialogue (Lee al. 2022). However, these models often need to deal with the challenge of balancing creativity and coherence, accepting less likely and more imaginative token choices while avoiding incoherent or nonsensical output. This trade-off is complex. as indiscriminate broadening of the sampling pool can lead to fragmented or disjoint text (Holtzman al. 2019).
To navigate this balance, various sampling strategies have emerged, including temperature scal- ing (Ackley al. 1985), top-k (Fan et al. 2018), top-p (nucleus) (Holtzman al.) 2019). 7 (Hewitt) al. [002)) and min-p sampling (Nguyen et al. (2024). They generally apply heuristies to control diversity and risk. Specifically, min-p sampling (Nguyen et al. 2024 stands out for its dynamic
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

truncation of low-pre cow-robabillity tokens using threshold tied to the probability of the top token. Al- though this method performs well high temperatures (T'). its exclusive reliance on the maximum probability token to estimate confidence disregards the potential distribution of the probability mass over the remaining vocabulary. As a result, min-p remains vulnerable to over-truncation in sparse (low-entropy) distributions and under-truncation in dense (high-entropy) distributions.
The above limitation motivates the need for more methodical confidence-aware sampling framework that accounts for the overall shape of the distribution, rather than only its peak. In addition, the proliferation of heuristic methods highlights a deeper issue, namely the lack of a theory-based foundation to analyze the interplay between creativity and coherence in autoregressive generation.
Our Contributions. Towards effective incorporation of the confidence of the model, in this work, present top-H decoding. In particular, top-H maintains the creativity and coherence balance guided by bounded entropy in text generation. Unlike most earlier approaches that rely on fixed threshold, top-H dynamically selects a subset of tokens such that the resulting truncated distribution over the selected subset has an upper-bounded uncertainty while maintaining minimal divergence from the original distribution predicted by the model.
To formally ground top-H, we first introduce constrained optimization problem that characterizes the off between creativity and coherence in language generation, namely, entropy-constrainee min- imum divergence (ECMD). We show that this minimization is equivalent to entropy- mass maximization (ECMM) problem. We then prove that ECMM is NP-hard. Thus, in top-H, we offer a greedy solution that is both efficient and practically effective in approximating the solution of the ECMM while bounding the entropy of the selected distribution. During autoregressive generation, the token distribution evolves at each step, top-H adjusts its entropy threshold based on the entropy of the token distribution, thereby dynamically adapting to the model's varying confidence over time.
We validate the effectiveness of top-H through extensive experiments in diverse set of tasks, including creative writing (Alpaca-Eval (Li et al. 2023) and MT-Bench (Zheng et al., 2023)), reasoning (GSM8k (Cobbe et al. [202]) and GPQA (Rein et (0244), and human- aligned evaluations using LLM as judge framework. Specifically, top-H consistently outperforms existing sampling methods in accuracy while maintaining robust balance between expressiveness and fluency. For example, compared to min-p, top-H demonstrates an accuracy improvement of up to 25.63%.
2 Related Work
2.1 Stochastic Sampling Strategies for Autoregressive Models
Temperature scaling (Ackley et al.
1985) multiplies the logits by a scalar, encouraging the exploration of less likely tokens. However, can get too indiscriminate at high T's, generating incoherent or contradictory texts. Top-k (Fan et al. 2018) includes only the k highest probability tokens. Although simple, this hard cutoff' is insensitive to context, sometimes excluding large swaths of moderately plausible tokens. Top-p (nucleus) sampling (Holtzman et al., 2019) chooses the smallest subset of tokens whose cumulative probability exceeds p. This alleviates some of the rigidity of top-k. Unfortunately, at high T", the distribution can be so flat that the top-p may inadvertently include very low lww-rrobability tokens, harming coherence. This incoherence in top-p sampling is demonstrated in the experimental results T where the coherence score on text drops significantly at higher T.
Min-p (Nguyen et al. 2024) sampling dynamically scales a base probability score threshold Phase by the probability of the top-I token. This effectively restricts the sample space more aggressively when the model is confident. Min-p has been shown to outperform top-p in tasks requiring both diversity and correctness at higher temperatures. However, its reliance on only the highest-probabiliyy token can overlook broader features of the distribution. Two different probability mass functions might share a t token probability; however, they differ widely in their overall confidence.
2.2 Entropy-Based Sampling Strategies for Autoregressive Models
Several methods attempt to exploit entropy or related uncertainty measures when sampling. 77- sampling (Hewitt et al. 2022) dynamically adjusts the sampling threshold based on the entropy of the distribution of the next token. However, this method often requires carefully tuned hyperparameters and can introduce significant runtime overhead at higher T's. Mirostat (Basu et al. 2020 aims to

---

maintain target perplexity (related to entropy) via feedback control. Although it can yield steady perplexities, it adds complexity to parameter tuning and integration into generation pipelines.
Despite their entropy-aware intentions, these approaches do not strictly limit the randomness of the sampling distribution; instead, they often aim to achieve perplexity target modify the sampling heuristics in real-time. As result, controlling the maximum allowed randomness in the final distribution, thus ensuring both coherence and flexibility, can be challenging.
3 Motivational Case Study
This section presents key motivation to develop a new sampling method, despite the widespread use of nucleus and min-p sampling within the com- munity. Specifically, we try to pose the following question.
Distribution
Distribution B
0.4
Probability
0.3
0.2
0.1
out-off threshold
minp cur threshold
0.0
20
40
20
Why do we need a more distribution-aware sampling technique if min-p already associated min-p threshold.
Token Index
Taken Index
Figure Probability distribution of two different types with
considers the model's confidence?
Min-p employs a dynamic truncation threshold by modulating the maximum probability of the next token probability distribution with base factor. Although this approach accounts for the confidence of the model to some extent, it insufficient to select an optimal sampling pool.
Consider one scenario where min-p may yield low efficacy as illustrated in Fig. [ Distributions A and B represent two token probability distributions over the vocabulary, where tokens are sorted by their probability values, and tokens not shown have probability of zero. Since both distributions have the same maximum probability, min-p applies a similar cut-off threshold. However, the two distributions are distinct in terms of confidence. Distribution A exhibits greater randomness, as contains numerous low-probability tokens, while distribution includes some high-probability tokens discarded due min-p's ss truncation threshold. This example demonstrates that the min-p approach does not accurately capture the underlying distributional characteristics. Consequently, motivated adopt sampling method that considers the overall shape of the probability distribution rather than solely relying on a maximum probability threshold. In Appendix (C.4. we demonstrate how our proposed sampling strategy, top-H, addresses this issue using the exact same example.
Theoretical Foundation for Entropy-Based Truncation Sampling
This section establishes the theoretical foundations of top-H sampling. Given language model M and preceding context window T1æ-1, the probability distribution over the vocabulary V for the next token 2, can be written as,
p(x;) = =M(aaa-1).
Our objective is determine subset C V from which the next token will be sampled, ensur- ing that the resulting probability distribution over the subset S, denoted q(xx). S - [0, 1] with Exes ((xx) satisfies the following desired characteristics:
1. Minimum divergence from the original probability mass function: The subset S should be constructed such that the distribution over the tokens in the subset, g(xx), has minimal divergence from the original distribution p(zx), thereby "maximally matches" p(x.).
2. Reduced randomness for enhanced coherence: The probability mass function ((x.) should exhibit lower randomness compared to p(xx) in the sense that H(g) S H(p) where (.) denotes the Shannon entropy, effectively upper-bounding uncertainty.
3

---

These criteria form the basis of top-H, which seeks to construct S and calculate q so that maximally matches p while exhibiting lower randomness compared to i To regulate diversity in a controllable manner, we introduce parametric randomness bound, parameterized by a (see Eq. 2 We formalize this objective as minimization of the Jensen-Shannon Shannon divergence (ISD) between p and g under the parametric entropy constraint. Formally, we intend to solve the following.
min JSD (p)) subject to (()) S a (p),,
where a E (0, is a tunable hyperparameter. We refer to this problem as entropy-constrained minimum divergence (ECMD). By upper-bounding (q) in proportion H (p). ECMD encourages the sampling of more tokens in the case of higher uncertainty (higher (p)) and the less token the case of lower uncertainty (lower (p)). This approach preserves coherent tokens in contexts where the model "knows" likely the next token, yet encourages exploration when multiple candidates plausibly fit the context, precisely where creativity is more beneficial. Therefore, with an appropriate choice of a, solving the ECMD problem can ideally balance creativity and coherence in autoregressive text generation. In the rest of this section, prove the following statements. I) Minimizing JSD under an entropy bound is equivalent to maximizing the sum of probabilities of the tokens in S (subject to (g)) (p)). II) The ECMD problem is, in general, NP-hard.
4.1 Formulation of the JSD Minimization Problem
We first start by defining the values of each element in the probability distribution of p and q- respectively. Assuming denotes the 7th token in the dictionary V/ the conditional probability of selecting v as the 1th generated token given F1 is,
P Prob x = 0a 11)=)=11) for i= 1,2....,
where | |-| identifies the cardinality of set. Similarly, the conditional probability qa of selecting 2 the 8th generated token given F1:-1 is
PL.
1/ E S
Pgg
where
Ds - Ps=Epo (v
otherwise.
Having defined the distributions, the (SD())lg) = = (p)l +
divergence between p and q is calculated
1 PKL(Il where M = - (p g)
Next, without loss of generality, we use the properties of JSD and re-formulate the ECMD problem maximization problem of the probability mass function for ease of analysis.
4.2 Equivalence to Consoay-Constrained Mass Maximization
The ECMD problem in Equation is is challenging analyze directly due to the complexity associated with the expansion of JSD. We thus reformulate the problem using the Is metric to facilitate analysis and interpretation. The following theorem formalizes the necessary condition for achieving the optimal solution to the original optimization problem in terms of s's.
Theorem 1.
The lensen-Shannon divergence between the distributions p and q only dependent on the s and can be minimized by maximizing l's.
Proof. Refer Appendix A.I for the proof.
As result, ECMD can be rewritten as the following,
max Ig sd. H(4)= S aH(p) + max Σ Ps 1l (m.e)) s.t. H(g) S all
(5)
From now on, we will use and g refer the distributions of the next token defined over the original set (V) and the selected subset (S) of tokens.

---

We name the above formulation as entropy-constrained mass maximication (ECMM). This refor- mulated version of the problem is easier to reason about. Next, we prove that given < < the problem remains NP-hard. Finally, we propose greedy approach as solution to this. Unless otherwise specified, we empirically set a 0.4 and use it throughout our analysis.
4.3
NP-Hardness Proof of the ECMM Problem
Theorem 2.
The entropy-constrainee mass maximization problem is NP-hard.
Proof. In Appendix A.2 we present a detailed polynomial-tina reduction from the well-known cendimality-constaainn subset-sum (CCSS) problem (Garey & Johnson 1979). As CCSS is popular NP-complete problem, our formulation establishes the NP-hardness of ECMM.
Hop-H Decoding Method
Having established the NP-hardness of the ECMM problem, we recognize that it cannot solved efficiently in the general cases. Thus, to produce a practical, efficient, and yet competitive solution, we now present a greedy approximation algorithm, namely top-H. Top-H incrementally maximizes the objective of Eq. 5 while adhering to the imposed entropy constraint.
Algorithm 1 To proposed greedy token selection algorithm
Require: Probability mass function p = (Pt, P2,.P2... P2........ ................................ entropy threshold coefficient a E (0,
Ensure: Selected token set S
1: Sort tokens descending order of probability: pi 2 p2 2 2 Pa
2: Initialize S +- (q) <-
3: for each token / sorted order do
4: Add token to S
5: Compute updated distribution over S
6: Compute entropy (g)
7:
if' 1 (q) > a H then
8:
Remove token from S
9: break
end if
11: end for return
Algorithm ootlines the token selection strategy of top-H. The objective is to maximize the probability mass of the tokens Σ; Pt Il (v,es), where the tokens v; are selected into the sampling set S. To achieve this, the algorithm begins by sorting all candidate tokens in the descending order of their probabilities. then iteratively adds tokens to the sampling set this order. After each addition, a distribution q is constructed over the selected tokens, and its entropy calculated. Top-H continues this process until the entropy of & reaches the dynamid dynamic@thresholo threshold a (p), ensuring that the selected subset respects the global entropy constraint.
Unlike prior truncation based sampling methods, top-H explicitly controls the randomness of the distribution it samples from, [(g), by adapting it to the entropy of the original next token probability distribution H (p). As a result, the allowed randomness dynamically adjusts throughout the steps of autoregressive generation
evolves. In Section 6.2] provide empirical evidence the competitiveness of the top-H's greedy approach in solving the ECMM.
We now present theorem that guarantees the termination of the algorithm, with an early convergence governed by the entropy scaling coefficient a.
Termination Guarantee. Entropy is non-linear and non-monotonic function. Thus, the entropy of the distribution g over a set S' is not predictable as tokens are added. Specifically, adding a token
2 At each step of auto-regressive token generation, the model produces new probability distribution causing the entropy threshold ald (p) vary dynamically across generation steps.
5

---

to S can increase or decrease the entropy, depending on the underlying probabilities. However, under a greedy selection strategy, it can be shown that each additional token strictly increases the entropy of q. Consequently, the entropy constraint is not a vacuous bound, and the growth of S is inherently bounded; the set cannot expand indefinitely without eventually violating the entropy constraint. This intuition is formalized in the following theorem.
Theorem 3. Consider greedy algorithm that selects tokens in descending order of their probabilities Let q be the probability mass function over the selected tokens. Then, the entropy of q increases strictly at each selection step and is maximized only when all tokens are selected. Therefore, if the entropy threshold coefficient chosen such that 0 < a < 1, the algorithm is guaranteed to terminate before all tokens are selected.
Proof. Refer Appendix A.3 for the proof.
The termination guarantee uses the monotonic growth of entropy under the greedy selection procedure. Each token added to the contributes positively the entropy. regardless of its probability, thus ensuring that the entropy H (q) approaches the threshold (p). The algorithm stops adding tokens to the set This ensures that the ECMM objective avoids the trivial solution of selecting all tokens while still satisfying the entropy constraint.
the moment when any further addition of tokens would violate the constraint.
Experiments
6.1 Experimental Setup
Models, sampling methods, and datasets. We evaluate top-H on three recent instruction-tume language models, namely, LLaMA3.1 1-MM..11-8BB Instructt (Grattafiori et al. (222)), Qwen2.5-3B (Yang) et al. 2024), and Phi-3-Mini-4K-Inm Instrrcct (Abdin et al. 2024). As baselines, we compare with several widely used truncation-based sampling methods, namely, top-k, top-p (nucleus sampling), min-p, and iy-sampling. Our evaluations span multiple benchmarks designed to test creative generation, reasoning ability, and evaluative judgment. Specifically, we also used the Alpaca-Eval dataset (Li iet al.] 2023), GSM8K (Cobbe et al. 2021). GPQA (Rein et al. 2024), MT-Bench (Zheng et al. 2023 and an LLM-as-a-judge evaluation setting.
Experimental settings. For decoding hyperparameters, we follow the configuration in (Nguyen et al., 2024), using min_p= 0.1, top_p= 0.9, and 17 0.0002 for min-p, top-p. and s-sampling methods, respectively. We choose the best result out of the = 10, 20, and 50 for top-k method. Regarding the evaluation, accuracy with the flexible extract filter on the GPQA and GSMSK datasets, length-controlled win rate Alpaca-Eval, and judge scores (on scale from 1 to 10) on MT-Bench. For Alpaca-Eval and MT--Becch, we used GPT-4o (OpenAl 2024) as the judge LLM. All experiments were conducted on a single NVIDIA A6000 GPU, and algorithms were implemented using PyTorch version ++cu124 and the Hugging Face Transformers library version 4. 4.50.1. 1.
the nn-evaa-harrne
framework (EleutherAl 2023) and report exact match
6.1.1 Performance on Creative Writing: Alpaca-Eval and MT-Bench
Fig. presents compelling evidence for the superiority of top-H sampling compared to alternative SoTA approaches. In Fig. [[a-c) (Alpaca-Eval), top-H shows remarkable improvements over the state-of-the-art min-p method, and also conventional sampling methods. For example, for LLaMA3.1- 8B across different T., top-H demonstrates an win-rate (%) improvement of up to 17.11% compared to SoTA min-p sampling. A critical finding from Fig. 2ls the resilience of top-H to temperature scaling. While traditional sampling methods exhibit severe performance degradation at higher T, top-H preserves much of its effectiveness. For instance, for LLaMA3.1-888 1-B 1-ntttruutt in Fig. 2(a), top-p sampling shows a catastrophic 34.06% decline in win rate from T=1 to T=2. In contrast, Hop-H experiences only 3.78% reduction over the same temperature range. This robustness is particularly significant given that higher T settings are essential for generating diverse, creative texts. The MT-Bench results (Fig. d--)) further validate the capability of top-H. For example, for I.LAM33. 1-88, similar to that on Alpaca-Eval. the advantage becomes more pronounced at higher T,
with Hop-H achieving higher score value of up to 3.78.

---

n-sampling
top-p
top-
min-p
(ours)
LLaMA5 1-36
Owen2 5-38
Ph3-Mi-
Win odt (6)
Wi Wiirott (K)
20
5.10
(A)
(b)
(6)
7-1.
7-1.0
T-15
Temperature
Temperature())
3.5
59
Audge score (1-10)
(3-10)
(d)
2-23
(
T-10
T-1.5
T-2.0
7-10
T-1.5
7-2.0
T-10
T-1.5
T-20
Temperature (T)
Temperature (T)
Temperature (T)
Figure 2: (a)-(c): Length-controlled win rates (%) comparison of different SoTA sampling with top-H
on Alpaca-Eva Eval benchmark. (d)-(f): Judge scores (on scale to 10) on MTT-eecch.
6.1.2 Performance on Reasoning and CoT Tasks
Following the setup in (Nguyen et al. 2024) we use the gsm_cot (8-shot) and srge_maainngeerativeee n_shot (8-shot) tasks for GSM8K and GPQA, respectively.
The experimental results in Tables and 2 demonstrate the effectiveness of top-H compared to min-p and top-p sampling across language models and temperature settings. Temperature a key hyperparameter in generation, striking balance between creativity and factual accuracy.
top-H consistently outperforms the alternatives. At Tt=,, leads for all the models, outperforming both min-p and top-p by significant margin. Top-H H maintains strong accuracy as temperature increases, while the baselines degrade significantly. At T=2, the contrast becomes
On the GSM8K benchmark (Table D.
pronounced, with top-p showing near-total collapse (declining by up to 73.62% (Phi-3-Mini) in accuracy), while top-H H experiences a very modest degradation, showing an accuracy improvement of up 25.63% compared to min-p (on L.AMA3.1-88))
similar trend observed in GPQA benchmark (Table Pp. At T=1, top-H remains competitive, outperforming both top-p and min-p Qwen2.5 and Phi-3-Mini. At T==2, it exhibits notable robustness, maintaining performance levels substantially higher than those of top-p, which experiences significant deterioration. Compared to min-p, top-H an accuracy improvement of up to 3.12%. 2.67%, and 7.36% on Qwen2.5, LLaMA3.1 1, and Phi-3-Mini, respectively. summary, top-H demonstrates competitive performance even at low temperatures and significantly superior performance at higher temperatures, marking it as a reliable sampling strategy for diverse generation needs.
Qwen2.5 3B
-LaMA3,1-BB-Instt
Phi-3-Mini
Temperature
Min-p
Top-p
Top-11
Min-p
Top-p
Top-11
Min-p
Top-p
Top-H
72.40
67.93
76.35
81.96
81.35
1.5
66.79
55,57
72.55
58.00
23.81
70.51
77.10
67.25
77.86
2.0
49.43
9.10
55.57
13.72
2.65
39.35
60.88
7.73
60.20
Table 1: Accuracy (%) for top-H, min-p, and top-p on GSM8K.
Qwen2.5 3B
1
Phi-3-Mini
Temperature
Min-p
Top-p
Top-H
Min-p
Top-p
Top-H
Min-p
Top-P
Top-H
1.0
28.35
27.68
28.79
26.34
32.81
29.24
31.92
30.58
32.37
1.5
30.13
27.23
27.90
28.35
28.57
30.58
29.91
28.57
30.80
28.79
18.53
Table 2: Accuracy (%) for top-H, min-p, p. and top-p GPQA.
6.1.3 Performance Analysis with LLM-as-a-Judde
In this section, we employ the L.M--asa-JJude framework to directly evaluate the creativity and coherence of texts generated using min-p, top-p, and top-H sampling strategies. Following the
7

---

evaluation setup proposed in (Nguyen et al. 2024). we use three open-ended prompts designed to elicit creative storytelling on diverse topics. We generate responses using three different models: LLaMA3.1 1 IBIItutt Qwen2.5-3B, and Phi3-Mini-4k-Instrud each evaluated across three differ- ent temperature settings. The top-p and min-p sampling methods serve as baselines for comparison. The prompts used are closely aligned with those in (Nguyen et al. 2024) and are listed in Appendix [R] We use GPT-4o (OpenAI] 2024) as the judge model to assess the outputs, which scores the responses based on creativity and coherence using the evaluation prompt detailed in Appendix B
For each evaluation, the outputs of the three sampling strategies are randomly shuffled mitigate positional bias. The scores are then extracted from the GPT-4o evaluation responses. To reduce the impact of randomness and noise, each experimental configuration, defined by model, temperature. prompt, and sampling strategy, is repeated five times, and the average score is reported. The results for L.LaM33. 1 1-8B--Instrue are presented in Table 3 The results in At lower temperatures, top-H produces outputs with significantly higher creativity, originality, and coherence compared to min-p and top-p sampling methods in all three prompts. As I'increases, the top-p sampling suffers marked decline in coherence, often generating fragmented and incoherent text. This degradation stems from top-p's 's lack of awareness of the model's confidence, as it truncates the distribution based purely on cumulative probability without accounting for distributional entropy,
reveal a consistent trend:
In contrast, min-p p and top-H maintain stronger coherence at higher temperatures by adaptively limiting their sampling pools based on model confidence. Among the two, top-H consistently outperforms min-p in both creativity and coherence. This is attributed to top-H's direct control over the entropy of the selected token set, allowing it to modulate randomness in alignment with the model's s uncertainty. Additional a-u---- results supporting these conclusions are provided in Table in in the Appendix, which covers the evaluations on the Qwen2.5 and Phi-3-Mini models.
Temperature
Promut
Sampling
M1
M2
M3
M4
M5
Average
Top p Min-p Top-11
7.45 4:0.20
6.35 22
8.75
1:0.26
6.60 0:030
7.55 +:0.15
7.45 4:0.30
Prompt
8.25 1:0.2
7.60
1:0 26
8:25 1:0.15
7.65
2:0 20
7.60 1:0.15
7,85 1:0.6
8,80 15.15
8.65 20.20
84001:0.2 10022
8,05 20.
8.55 10.22
8,45 10226
Top
7.85 4-0.15
7.20 #:0.5
8,35 +:0.22
7,05 #: 35
7.50 +:0.15
7,50 +:0.30
1.0
Prompt
Min-p
7.25 1:0.24
7,20 150.5
800 1:0.26
7.55 1:0.0 20
6.75 1:0.35
7.40 1:0.22
Top-H
8.10 0:0.2
8.10 +:0.3
40.15
40022
8.25 +:0.3
Top-p
6,50 2.226
6.10
10.22
20.20
7.65 20035
7:20 10015 15
Pronree
Minep
6:7 40.20
25
+0026
6.77 =0.
7:00 +0.20
6:90 +:0.30
Top-H
8.15 #:026
8.05 0.22
8:00 150.15
8.30
0.031
8,25 4:0.20
8,05 +:0.3
Top-p
7.45 1.51
7.10 26
8:00 100-1:0.00 22
7.55
=0.30 30
7:35 +0.22
7.55 10031
Procsge 1
Min-p Top-II
7,95 #0.22
7.55 20.35
8:25 40020
7.55 =00 26
7:60 2:0.2 /2
7,80 +: 26
8.75 2.
9.05 2:0. 26
8:50 1:
8,40
1:
8.50 1:0.20
8,80 1:0.2
Top-p Min
7,50 0.030
7.75 20 22
N.65 1:0.35
7.00 2:0. 22
7:65 :20 26
7:75 0:0.2
1.5
Prompt
7,30 1:0.20
7.10 2:031
7.87 1:0.30
6,80 2:0.6
6.75 1:0.26
7,10 1:0.15
Top-11 11
10 20
8.10 1:0.22
7,40 4:0.20
6.85 #:0. 28
1,30 4:0.11
7.20 +:0.
8:35 +-0.31
7.45 +-0.30
Prompt 3
p
1:0.20
7.20 1:0.2
1:0.
Top-H
8.35 +:030
7.80 #0.31
7,80 4:0.20
8.05 1: 222
8.10 +0:30
8,05 +:0.26 2G
Top-p p
7,00
+0030
40026
40.24
5,95 4-0.22
Procsge 1
Min-p Top-H
8.8 +0.31
8.35 20.31
7.8 4:0.24
7.15 22
7.65 20.31
7:70 +0020
8,50 :0022
9.05 20.24
8.75 +0.20
8.70 15
8300 #:0.2
8.85 +:0.0
Top-p Minep
8.25 20.20
7.65 =0.30
3,85 1:0.20
5.20 2:0. 24
6.30 2:0 22
6.25 +:0 15
2.0
Pioengt 2
7.50 10.15
7.45 20.
7:15 +0031
7.55 20.20
7:40 2:0.3
7,40 40026
Top-11
1:0.20
20031
1:0.2
10030
1::00:000 2.2
8,60 0:0.2
To--p
7.15 2.025
8.15 =0
4.20 1:0.20 24
5.65 = 20
7,50 1:0.1
6.55 +0030
3rompt
6.80 4:0.3
0:0.1
1:0.00
1:0.
Top-11
8.0 10:31
7.1 20.22
9.0 1:011
8.05 0002
7.05 1:0.20
7.65 0:0.24
Table 3: Evaluation metrics and the judge scores (on scale of 1.0 to 10.0) for different temperatures, prompts, and sampling methods on LLaMA3.1-8B-Instruu M1-M5 denote creativity, originality, narrative flow, imagery, and vitality, respectively.
In Appendix[C C we present additional results and discussions on top-H, including evaluations with larger 70B model, human evaluation of creativity and coherence across different sampling techniques, and comparison of top-H to Mirostat method.
6.1.4 Computational Overhead and Timing Comparisons
We compare per-token decode latency (ms/token) of top-H against top-p and min-p on three models: LLaMA3.1-8B ----------IInnrret.. Phi-3-Mini-3.-8 and M-0MAMA.--70---nttrre in the Table For each
8

---

configuration, we evaluate on 100 prompts from AlpacaEval, generating 128 tokens per prompt, and report the mean ms/token over prompts. Specifically, we observe negligible overhead of as low as 0.8 % compared to min-p and top-p.
Computational complexity. Let n. denote the vocabulary size, and let p1 2 P2 2 .... Pr. be the sorted probabilities. Sorting the logits dominates the computational cost for all cumulative decoding methods, requiring (n log r) time. Subsequent operations such as partial selection or cumulative thresholding in top-p and min-p decoding only involve single linear pass, adding (n) additional work but not changing the overall asymptotic complexity.
For top-H decoding, define the partial entropy h Ei=1 Pt logp; ps According to the proof of Theorem A.3 the entropy of the distribution q¹ is given by
h H('') = logT, r
where the cumulative mass satisfies r ,- = - + Py. and the partial entropy follows h, h Py log Po. These recurrences enable incremenial entropy accumulation (Alg. 2 which updates ((')) O(1) time per step, or O(n) in total given sorted inputs. Therefore, the overall complexity of top-H decoding is also bounded by the sorting step, i.e. O(n log n.). In practice, log Pj values are directly available from the model's pog-probabilitie.
Algorithm 2 Incremental entropy accumulation
1: Initialize r +- 0, h < 0, H +- 0
2: for each step j do
3: I - r + Pj
4: h + Py log
h
5:
+ + T
6: end for
LLaMAA31-8B-Instreee
Phi-3-Mini
LLaMA3.3-088-nesrrutt
Temperature
Top-H
Min-p
Top-p
Top-H
Min.p
Top-p
Top-11
Min-p
Top-p
1.0
28.3951
27.3396
27.4275
24.3847
23.6499
23.7809
219.3837
219.1391
218.4900
2.0
28.4671
27.3840
27.4389
24.5929
23.9397
23.5844
219.3428
218.3609
217.7083
Table 4: Average runtime per token (ms/token) across sampling strategies and models.
6.2 Discussions and Ablations
Sensitivity of the text to the temperature scaling. this section, we present a quantitative analysis of how the coherence of generated text varies with changes sampling temperature. We conducted experiments using the Qwen2.5-3B and LLaMA3.1 1-8--Instrut models on prompts from the Alpaca-Eval dataset. To operationalize coherence, we use the total log-probability (log-likelihood) of the generated sequence as proxy: higher total log-
bogprabability
QwenZ.5 top
Qwen2.5 min-p
Duen2.5 top-11
LaMA3.1
probability suggests that the model is more confident in the output, which we interpret
LLMMA3.1 min.p
signal of greater coherence.
LaMAS tog-t
Specifically, we compute the log-likelihood of each gener- ated token during autoregressive generation, average these values across the entire sequence. This process repeated in multiple temperature settings 0077, 1.2, 1.6, 2.0, and
0.75
1.00
1.25
1.50
3.75
2.00
2.25
2.50
Temperature (T)
Figure 3: Effect of T scaling genera- tion coherence in min-p, top-p vs top-H.
2.5 and for three different sampling strategies: top-p, min-p, and top-H. The result is portrayed in Fig. 3 As the temperature increases, the log-likelihood of the text generated under min-p and top-p sampling declines sharply. This suggests that the coherence of these methods is highly sensitive to temperature and that at higher temperatures, where increased creativity is encouraged, the generated

---

text tends to become less coherent. In contrast, top-H adjusts adaptively to the entropy of the distri- bution of the next token H(p). effectively constraining randomness. As a result, maintains more consistent and coherent output even in high-temperature settings.
Impact of parameter. The only hyperparameter in top-H sampling is a, which directly controls the maximum allowable entropy for the distribution q. As such, a careful tuning of a is essential. To determine an appropriate value, we randomly select 50 development samples from the Alpaca-Eval dataset and use LLaMAS.I-SB-nnstre to generate responses. We explore values of a in the range [0.1, 0.9], with increments of 0.05. For each candidate value, we run the model on the development set and evaluate the ouiputs using our LLM-as aas----uugdee prompt (the same as in Section 6.1.3) to assess both creativity and coherence. The optimal value of is selected based on its ability to best balance these two objectives. The results of the creativity and coherence evaluation, averaged over 50 development samples, are presented in Figure T| As a increases, the entropy threshold becomes more permissive, allowing greater randomness in token selection. Consequently, creativity tends to increase, while coherence tends to decline. The optimal value of a is the point which these two metrics are best balanced. Based on the figure, observe that = 0.4 produces the highest average in the creativity and coherence scores, indicating it as the most suitable choice, Additional quantitative results are provided in Appendix C.S
Empirical optimality of the top-H decoding strategy. We now empirically evaluate the competitiveness of the greedy algorithm of the top-H relative the optimal solution of the ECMM problem, found by exhaustive search. We randomly sample 20 prompts from the Alpaca-Eval dataset and generate responses using the top-H method. At each generation step, the candidate set of tokens is restricted to the top-15 tokens of the probability distribution predicted by the model. To obtain the optimal solution, we exhaustively enumerate all possible 215 subsets of the feasible token set and identify the subset S that maximizes the objective s's., subject to the entropy constraint H (9) I 0.4 H (p), with q denoting the distribution over selected subset.
fuerage
0.1 0.2
0.3
0.4
0.5
0.6
0.7
0.8 0.9
Figure 4: Effecct of the parameter on creativity and coherence.
For comparison, also compute the greedy solution $ using Algorithm At each generation step, we calculate the ratio ss= / s-, and report the mean and variance of this ratio (across different generation steps) for 20 dif- ferent evaluation prompts, as visualized in Figure 5 As shown in the figure, the mean of the ratio remains con- sistently close 1.0 across randomly sampled instances from the dataset, with only minor variance. Although deriving a formal approximation guarantee is beyond the scope of this work, our empirical results indicate that the solution obtained by top-H for the ECMM problem closely approximates the optimal solution in practice.
D
110 (supoed 1.0)
Mocan
2000
Normafized
094
tr sroinn Selte
Figure 5: Empirical evaluation of top-H performance relative to the optimal solu- tion of the ECMM problem.
While the primary goal of this work is to empirically demonstrate the efficacy of top-H decoding in addressing the ECMM, we defer a detailed theoretical analysis of the associated error bounds to future research. Nevertheless, in Appendix A.44 we provide a preliminary worst-case error bound for the greedy top-H solution under a specific assumption about the next-token probability distribution.
7 Conclusions
This paper addresses the challenge of balancing creativity and coherence in LLMs, particularly under high-temperattre settings, where coherence often deteriorates. We introduce the entropy-constraime mass maximization (ECMM) problem, which formalizes the objective of balancing creativity and coherence by imposing an entropy constraint on the distribution of tokens in the sampling set. After proving the NP- harrdees of ECMM, we propose top-H. computationally efficient greedy algorithm that effectively approximates the solution of ECMM problem. Extensive empirical evaluation across various tasks demonstrates that top-H consistently outperforms established sampling strategies such as top-p and min-p. achieving up to 25.6% higher accuracy. These results establish top-H as new Maate-ff-the-ar method for creative writing in LLMs.
10

---

Acknowledgments
This work was partially supported by a grant from the Directorate for Computer and Information Science and Engineering (CISE) of the National Science Foundation.
References
Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, et al. Phi-3 technical report: A highly capable language model locally your phone. arXiv preprint WrXiv:2404.142/11 2024.
David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A learning algorithm for boltzmann machines. Cognitive science, 91):1477-66, 1985.
Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R Varshney. Mirostat: A neural text decoding algorithm that directly controls perplexity. arXiv preprint vrXiv:2007.14900 2020.
Richard P Brent and Paul Zimmermann. Modern computer arithmetic, volume 18. Cambridge University Press, 2010.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14,668,, 2021.
EleutherAI. Lm evaluation harness, 2023.
URL https://github..co/fllluuut
-m- ---evvllatioonn-ae
Version 0.4.5.
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. arXiv preprint arXiv:1805.04833 04833, 2018.
Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of up-completeness. In W.H. Freeman. W. H. Freeman and Company, 1979. Problem SP13: Cardinality-Constriiee Subset Sum is NP-complete.
Martin Gerlach and Eduardo G Altmann. Stochastic model for the vocabulary growth in natural languages. Physical Review X, 3(2)0020006, 2013.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama herd of models. arXiv preprint arXhv:2407.2178. 2024.
John Hewitt, Christopher D Manning, and Percy Liang. Truncation sampling as language model desmoothing. arXiv preprint 2rX1v:2210.15111, 2022.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. arXiv preprint arXiv: 1904.0975/, 2019.
Mina Lee, Percy Liang, and Qian Yang. Coauthor: Designing human-ai collaborative writing dataset for exploring language model capabilities. In Proceedings of the 2022 CHI conference on human factors in computing systems. pp. 1-19, 2022.
Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Alpacaeval: An automatic evaluator of -oolroutionnfolllovinng models. https:://ii thub. wwwpttttttttteee lab/ hataaaabappaaaaaaaaaaaaaa 5 2023.
Minh Nguyen, Andrew Baker, Clement Neo, Allen Roush, Andreas Kirsch, and Ravid Shwartz- Ziv. Turning up the heat: Min-p sampling for creative and coherent Ilm outputs. arXiv preprint arXiv:2407.01082, 2024.
OpenAl. Gpt-4o system card. arXiv preprint arXiv:2410.21276, 2024. URL https: http:::/axxxvvvroe

---

Christos H. Papadimitriou. Computational Complexity. Addison- Addison-Wesley, Reading, Massachusetts, 1994. ISBN 978-0-201-53082-7.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. Gpqa: A graduate-level google-proof q&a benchmark. In First Conference on Language Modeling, 2024.
An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115, 2024.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging Ilm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36:46595 46623, 2023.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We provide discussion of the limitations Appendix D
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

The full set of assumptions and complete proof' are provided in Appendix A The main intuitions for the results are provided in the main paper and complete proofs are provided in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the necessary information required to reproduce the experiments are discussed in section 6 in combination with the actual implementation in
Guidelines:
The answer NA means that the paper does include experiments.
the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Implementation of this work, including the full code repository is available httpgghuwwb.ooo/ttaaaaaaaaaaaaaa -eDcciinn
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ httppp.ccppubcccguuuceeee Codeeubmii ssi criionPooiccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This work does not involve model training; however, evaluation and imple- mentation details are provided in Section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We conduct all experiments multiple times (e.g.. five runs in Section 6.1.3 and report the average performance across runs. The standard deviation of the error is also reported when relevant, in Figure 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This information is provided in section 6.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This paper conforms, in every aspect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
This is provided in the Appendix
E
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The assets used in this paper are properly cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
No new assets are created.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpp/////euups..... wwwparippsscccoooeeeeeee cc/Conferencess///////e for what should or should be described.
19

---

A Proofs of Theorems
Unless otherwise specified, all logarithms natural log.
A.1 Proof of Theorem 1
Proof of Theorem L The probability of the selected tokens needs be divided by their sum, make
sure that the sum of the distribution is 1. Given:
Em= m =1 = Σ (
(uee)) =
Ts
(6)
According to
12.
i S
M
Pt
i> m
2
(xL(Pl = 'ee log
Pi
+
Σ
Pi log
Pi =
Σ
log
2
+
Σ
log
1/2
(pe + Ps)
2P:
1 I's
2m1
i m++1
im
im m-+11
2T
loog
Σ
Ps + log (2)
Σ Pi
I+Is
i=
1mm-+1
Using 3
and
6
21 y
Is
ss log
(ogg(2)1 [s) =
log
+ +log(2)
+ +log(2)(1 - rss)
1 [s
I+Tss)
Is
Tss
=ss log
+ log(()) + +og(2) - log(2)l = -s log
+ +log(2)
(7)
1+
1 1+
DKr(al]M) = Σ
log
I's
ps log
2
1
log
2
Ts
(pi +
P1
Ts
1 [
[s
1
[s
1=1
Ts7
1=1
f=1
Using 3
2
log
(log(2) -log(1 + (s)
(8)
1 Tss
Rewriting Aansen-Shannon Divergence using and (8):
1 [+ )) + (log(2) log(1 + [ss)
I's
JSD(plla) log(2) + I' log
1 (2log(2) I's (Tg(Ts) Ds log(1 [ +Ts)
1
[s)) -log(1 +
log(2) (T's log()) (1 I's) log(1 + Iss)
Therefore, JSD is only dependent on ss Now we want to show that the distance between the distributions is decreasing with respect to I's:
d JSD()l
1
(Iog(T's) +1- log(1 + +Ts)
d'' s
(log(Ts) - log(1 + [s))
Always negative.
Therefore, (SD()) decreasing with respect to I' and minimize JSD(pllg), one needs to maximize l's.
D
20

---

A.2 NP-Hardness of Entropy-Constrained Mass Maximization
All logarithms are natural (In). Arithmetic is performed on a unitcost RAM with binary encodings; an integer æ 2 occupies [log2 ø] + bits.
A.2.1
Problem definition
For probability vector p (p1,..., Pn) with EiP:
define
n
H(p) = Σ
Pi Inp,
1=1
The fixed-budget maximization problem ECMM is
max
I >>>
s.t. H(S) S 0.4 H(p),
(ECMM)
SCIn
:ES
where H(S) denotes the entropy of the renormalized vector (pi)ses.
The corresponding decision version, ECME, is:
Input: A probability vector p (Pi...., . ..). a mass target 3 3. and the fixed budget = 0.4 Hp). Question: Does there exist 5 C [n] such that
Σ
3 and H(S) a
ES
We show that the decision variant NP complee;; the optimization variant is NP-hard.
A.2.2 Source problem: Cardinalit-Constraindd Subset Sum
Definition (CCSS). Given positive integers Wi....y Wms a target т, and an integer K with 3 S K m, decide whether some subset of exactly K weights sums т.
CCSS is No-copele reduce from the classic SUBSET- SUM; see, e.g., Papadimitriou Papadim Exercise 8.14).
itriou 1994
Our reduction from CCSS to (ECMM) needs the following narrow-range condition. Assumption (Narrow range).
W4
(1sism)
K
+
K
The next lemma shows that we may enforce Assumption I by polynomial-time padding step. Lemma 1 (Padding to narrow range). There a polynomial-tima transformation that maps an arbitrary CCSS instance (wi...,, Wmis K) to equivalent instance (wi,..., (....... W'ni T'; K) that satisfies Assumption The new weights and target have binary lengths polynomial in the original instance size.
Proof. Set
M (K + 1)T,
w := w. + M,
+ K M.
Because the same constant is added to every weight, a subset of exactly items sums to 7 iff sums to r/:
Σ iES
w -
Σ w =
ES
Lower bound.
Each new weight satisfies i > M. Moreover
T'
+ K(K + 1
KT +
K+1 < KT+T= M,
K+1
K+1
so w. + + 1).
21

---

Upper bound.
We have w S Wmax + +M - + (K + 1)T = (K + 2)r. On the other hand,
K (K(K + +)T
+ K - T.
K
Since (K+2) = Therefore Assumption holld for the padded instance.
--2 +2+K+11 for every K 2 3. follows that w < (1/(/K11))
Encoding size. at most log, (K + 1) bits, and the same holds for r'. Hence the transformation is polynomial in the input length.
The multiplier M (K + 1)7 increases the bit bit-length of the largest weight by
Henceforth assume without loss of generality that every CCSS instance meets Assumption it does not, we first apply the padding from Lemmal T
We also stipulate K 2 20 (duplicate the instance below if necessary).
Scaling step (making K 20 while keeping the narrow range). If the given instance has K < 20, put
d 2)//K].
duplicate every weight d times and set
Ki : dK,
:= dr.
Then
3 C [m] |S| K,
Σ w =T
3S S [m] |S| K1, Σ wi = TI
so feasibility is preserved and K1 > 20.
The plain duplication, however, may violate Assumption 1 because the new lower bound 71 [ KKK+11 1) can exceed some of the duplicated weights. To restore the assumption we now re-apply the padding of Lemma to the instance (W....., Wms 71; K1). This yields an equivalent instance
(w) w'i T²; K1)
that satisfies Assumption annd still has K₁ 2 20.
All numbers grow by most [log2 d] Ollog K) bits, so the whole transformation remains polynomial-time.
Henceforth we may and do assume that K 2 20 and that the narrow-range condition holds.
A.2.3 Reduction to ECME
Let (Wi,..., Wm: Ti K) be CCSS instance that already satisfies Assumption !
Define
1
50k
0.0384 7K
0K
8g
EK
16K
2K2
In K'
In
0.7733
SK + ŌK
A(K)= =
:: = [K>(K))
0.133
W/ : 2B'
Th Buy 2
W W
Set
P = (15i5 m), pb
W
3B
The resulting FCME instance contains n = m + B items. The numbers above are representable with Oloog K') bits, hence the reduction runs in polynomial time.
22

---

т A.2.4 Entropy budget window
Lemma 2 (Budget window), For the constructed instance,
In K - 7K < 0.0. < <nn(K
Proof. Split (p)) Hn + Hb, where
Wi H 3 (H( + + 5)), qi
H (In3 X(K) In K).
By Assumption 1 and second Taylor bound, ((q) In K 0x with 0 < 0x < 2k² Substitution gives
0.4 (p) = Ex) + 0.0384 0.2667 0g + 0.133 0g In K In - + 0.0666 8k. and since 0 < 0.0666 0K In(1 1/K) for K 2 20, the window follows.
A.2.5 Structural lemmas
Lemma (Booster blow-up). Let be any subset with I's = B. If contains at least one booster item, then HSS) > 0.4 (p))
Proof. Write S H U B where H (resp. B) is the set of heavy (resp. booster) indices selected. Let b = B 2 and : |
Step how many boosters are needed. Each booster weighs w/ T/BBB) whereas every heavy weight is at least W'min =K/(K + by Assumption 1. Total weight has to be exactly т, so each heavy item that is removed must be replaced by at least
Wmin
7/(K+)
2B
2B
Wbb
T/(BB)
K+1
boosters. Therefore S K and
2B K
1
8
(9)
2B
K
(The quantity equals the total probability mass of the boosters after renormalisation because each has probability wa/T = 1 (2B).
Step a lower bound on the entropy of S. The booster probabilities are 1/(2B). so their contribution is l2BB). For the heavy part we use the crude bound In(K - 1) S In K 1/K together with the fact that the L heavy probabilities add up to 8:
HSS) (1 8) In(K 1) (2BB) > In 1
+((((( 1) In 2n
K
because In(2B) = In 2 + X(K) In by definition of B. With 4 this gives
H(S) 2 I + (A(K) 1) In K In
K
Since X(K)² 2 2 for every K 2 20, the numerator is positive and we conclude
H(S) > In K.
(10)
Step 3 compare with the budget. proves (S) 0.4 (p),, required.
Lemma states 0.4H(() < K. Combining this with (TO)
Lemma 4 (Cardinality lock). If contains no boosters and T = 3 2/3, then |S| = K and Eies
23

---

Proof. Since S has no boosters, its total weight is
Σ
= -
ES
Let [S] = L. By the narrow -ange assumption,
L
U. = K-1
K+1
iES
Dividing through by gives
L <
L
K+1
K-1
which simplifies to K 1 K + 1. Since L is an integer, L = K. Having [S] K and total weight 7 establishes the claim.
Lemma (Entropy gap for a K-heavy subset). Every K-element subset S of heavy items summing satisfies
H()) & In - 7K-
Proof. After selecting K heavy items summing т, their renormalised probabilities are r W./T. By the narrow-range assumption,
1 K +1 < Pi --1 + Fi In K + + = In K -
we may write x with |aral K[K-I]
and E, I; 0.
Then
K
K Σ im
K
H(S) = Σ raln, =
Σ + zz In(1 + Kxx).
K
Using the Taylor approximation In(1 + u) 2 u
2²
for |u|| < 1,
I
( + x4 In(1 + Kx;)) 2 ( + x:i)
Kr; (Kz,)²² = +
Ku²
K22212
2
Summing over i and using E; 0 and
|جا||
< 1/(K(K - 1)) gives
K
K
K
K2
K
K K
Σ t.; In(1+Ka)) 2
24
2
2(K 1)2 2(K 1)3
2(K - 1)3"
1=1
1=1
For K 2 20, one checks
K 2
1
>
= --K-
2(K - 1)3
16K
Hence
H(S) = In Σ K +
In(1 + Kxx) & InKK - -KK,
as claimed.
A.2.6 Equivalence theorem
Theorem 4. The constructed FCME instance admits subset of mass B3 iff the original CCSS instance is a YES instance.
Proof. (+) Any feasible must exclude boosters by Lemma so Lemma gives a K-subset
summing to T. (+) Conversely, let be any K-element subset summing to r. By Lemma 5 H(S) S K- and by Lemma in K 7K < (.4 Hence HS)) < 0.4 H (p) and I's B, S is feasible. D

---

A.2.7 Complexity consequence
Theorem 5. The decision variant ECME is NP-complete, and the corresponding optimization problem ECMM is NP-hard.
Proof. Membership in NP Given candidate subset S, we can verify both constraints in polynomial time. For the mass we simply add the s. For the entropy, we approximate each In to (log K) bits;
the required precision is well below the separating gap 7 0.0666 0x O(K ((K,)),, 2), so rounding
cannot flip the inequality. Classical results on transcendental evaluation on a unit-cost RAM (Brent
& Zimmermann 2010) show that such an approximation takes O(llog K) input size. Hence the verifier runs in polynomial time.
time time- poaee-oolyomiall in the
NP-hardness of the decision problem. Apply the polynomial-time padding from Lemma T and then the reduction of Section A.2.3] By Theorem the resulting instance is YES instance of ECME iff the original CCSS instance a YES instance. Therefore the decision problem NP-hard.
Optimization hardness. Assume, for contradiction, that we had polynomial- time algorithm that returns
max Ts H(S) 0.4 H(p).
SC(n]
On the same input we could decide the ECME instance by single comparison of that maximum with the fixed target value 3 = 3. This would solve an NP-complete problem in polynomial time, contradicting P NP. Hence the optimization version is NP-hard.
A.3
Proof of Early Termination
Proof of Theorem
3
Assume that the distribution of the selected tokens after steps is g², therefore:
=
2
Pi
log
Pi
ps log P
log(T, 3- 1)
Σ Pes
where r
E Pi
i-1
F
i=1
Since E/=1 Ps = 1-
j-1 pi log P:
H(q"-1) = (og((((1))
1- 1=1
p. log p; ( - log 1-)))
(1I)
Now, calculating H²q)):
H(q')= -- Σ 1=1
Pt
log
Pi
log Ps
Ps
log(T,-1+7))
1 1 +
Pj
T Pj
T Pj
1 1-1 Pj
1=1
log(T Ogg(T-115 + pj)
log +
Pi
T- + Pj
r3 + Pj
1=1
1=1
Since El-1P Eー=1 P: + P3 = -
H(q²) = -og([r-+-p)
pi log log(T)-1
Ps log P: - Py logp;
D +
T + P.j
25

---

Using 11
1og(T]-1 + +2))
- 1 - P3 logp;)
T--1 +p
AH - H(
1
-- + pp) +
(T (T - Pj log H(0
T Pjjitpj
1
-og(T)-1+Pp) +
(T (T + P/) Lo - Pj log(p;))
1 + PP
= -
( (o) po
+ -
The probabilities are sorted in descending order, therefore:
j-1
J-
Vi sj S
Pj
P: (j 1)ps -
pj
i=
t=1
T 3-11
H(p-11 < log(j 1) < log
Pj
Pj log
D--1
- log(T;,
j-1) j
+ Pj log(p,)
AH 2 (T pi)
83
r + PPj
ド + Pj
1
log([ j-1 + P,)
[p, log(T Pj log(p;) + + j- j-1) + P3 log(p;)]
- + Pj
1
= =log(Tū-1 + P()
(p) log (og(T;-1) + T log(T;-1))
Tj-1 +
loog(T]-1 + p2) - (og(()-11) log
Tÿ-1 +
log
1
Pj
Tj-1
T5-1
AH log
(+
1+
Pj Ty-ı
> AHl 0
A.4 Formal approximation bound for the top-H
Zipf model.
Fix vocabulary of size n and exponent 1. We assume the sorted next-token probabilities obey the classical Zipf / regularly varying law:
i-
ps
H
j
(12)
H
Empirically, language-model logits are well approximated by 8 E [1.05, 1.20) (Gerlach & Altmann
2013]; hence the assumption captures current practice.
The Zipf assumption matters, because ECMM is NP-hard (Theorem 2p. exact polynomial-time solutions are unlikely. In the absence of structural assumptions, a constant-factor approximation guarantee for ECMM is highly unlikely unless = NP, as our NP-hardness proof relies on a Subset Sum. This structure is known to
gap-preserving reduction from be fundamentally difficult to approximate, a standard result in computational complexity theory (Papadimitrioul 1994).. However, LLM logits consistently follow heavy-tailed (Zipf regularly- varying) laws, so analysing this regime yields practically relevant bounds.
Notation. We write M(k) = Eisk Ps for the prefix mass, T(k) 1 - M(k) for the tail mass, and (k) for the entropy of the normalised prefix distribution g (k).
26

---

Preliminaries
Lemma 6 (Monotonicity of prefix entropy). For 1 - k < n. one has H(k) < H(k + 1). Moreover, for any subset of size H(gs) H()).
Proof. The first claim is classical: adding the (k + 1)-st symbol strictly increases entropy because
Ph++1 < Pk and entropy Schur-concave. For the second claim we note that (P1....: Pks) majorises any other k-subset of the sorted vector; Schur-concavity again yields the desired inequality.
L
Lemma (Tail mass bound). For h < n,
(k 1) In S (k)) 1
kl-s
(s 1)H
(s H)H
When n >> k, the numerator difference is o(k²=*), so the upper bound is asymptotically tight.
Proof. Apply upper and lower Riemann sums to f" x dæ.
Lemma (Prefix entropy asymptotics). There exist constants Cs. C2 > O such that
C2 log( S (())) - C. log k: for all k 2 2.
Proof. Combine Lemma 7 with integral bounds for Σ i log
Depth of the greedy prefix
Lemmal@imminnn iimplies Kg is well defined. Lemma (Growth rate of kg)) There exist constants 0sy by > such that
Let ky := max(k: (k) S an)) Lemma
agn" S kg I ban".
Proof. Insert Lemma into the defining inequality and solve for lgg
Mass captured by top-II
Write r M (kg). This is the mass captured by the greedy solution. By construction, this solution is valid as it satisfies the entropy constraint H (K:)) S (n).
Tight upper bound for ECMM
Let S* be any subset satisfying the entropy constraint, and set 1 Eies. Pi. We want to bound the maximum possible value r"
The greedy algorithm selects the prefix [ky] and captures mass of M(kgg) = 1 - T(kg). The total mass of all tokens not in the greedy solution is, by definition, the tail mass T(k;g).
Any other valid solution S* can, at best, capture the mass of the greedy solution plus some portion of the remaining tail mass. The absolute maximum mass any solution capture is 1 (the entire vocabulary). Therefore. the maximum possible improvement any optimal solution I* can have over the greedy solution I, is bounded by the tail mass that the greedy algorithm left behind:
- rg < 1 - H 1 M(g)) T(kg).
(13)
This gives us direct upper bound on the additive gap between the optimal and greedy solutions. Theorem (Distribution -ependeen additive guarantee). Under equation 72 for every n 2 4,
k
F r < (ki < 1)H1n,a
g
OOn
Proof. From 13 we have the additive gap I Ig S T(kkg = Tn (kg). Lemma bounds (kg) by 11 1--4
(e-1) Finally, lemma 9 gives kg (nn"). ) so the gap decays O(n a(s- m(s-1)).
27

---

Discussion on the effectiveness of greedy
We understand that the approach of dropping high-probability tokens could in principle beat the greedy prefix by allowing more low-mass tokens from the tail. However, this problem (ECMM) is NP hard, and we approximate the solution via a practically feasible greedy approach. Notably, we empirically demonstrate the effectiveness of this greedy based top-H approach to be superior to the existing SoTA. Additionally. under the constrained distribution of the Zipfian regime, the greedy prefix is constructed to generally maximize mass under minimal entropy growth. Because entropy increases monotonically with each added token, and the most probable tokens usually contribute less to entropy per unit mass, the greedy approach reaches the entropy threshold more efficiently than any alternative.
B LLM-as-a-Juudg Evaluation Prompts
Following (Nguyen et al. 2024), we adopt the following judge evaluation prompt and three open- ended prompts designed to elicit creative responses and facilitate creativity-coherence trade-off analysis:
Judge Evaluation Prompt
You are an expert judge evaluating Al-generated creative writing. am testing the diversity and coherent writing capabilities of three different models, I will paste three different responses that were generated here.
Rate responses based the following metrics:
Diversity: Novelty and uniqueness idcas Originality: Innovative approach the prompt
Narrative Flow: Coherence the text 4. Emotional Impact: Ability to evoke feelings 5. Imagery:
Vividness of descriptions.
Rate each metric from to 10. Also, suggest the overall winner: the response that best maintains high coherence while demonstrating high diversity.
Prompt
Write story about an alien civilization's contact with Earth from their perspective.
Prompt 2
Write story about world where time suddenly starts moving backwards.
Prompt 3
Write story about mysterious door that appears in unexpected place.
C More Results
this section we provide more experimental evaluations and analysis on top-H sampling.
C.1 LLM-as-a-Judge for creativity and coherence evaluation
Table presents creativity and coherence evaluations under the I.LMMas-a-Judde setup for the Qwen2.5-33 and Phi-3-Miini4K--Insmmcc models. The observed trends are consistent with those of -LLLMAA.J-BB-Inste
as the decoding temperature increases, coherence degrades notably for both min-p and top-p sampling methods. In contrast, top-H effectively maintains coherence while producing more creative outputs.
C.2 Validation with large model
We replicated the MT-Bench (Table 6) and GPQA (Table experiments using LLaMA3.3-703 Instruct with the setup of Section the paper. Specifically, top-H outperforms min-p by up to 6.0% and 6.47% on MT-Bench and GPQA, respectively.
28

---

LLM
Temperature
Prompt
Sampling
M1
M2
M3
M4
M5
Top-p Min-p
7.4
7.4
8.0
8.0
7.2
Prompt
6.6
6.5
7.8
6.7
Top-H
8.4
8.4
8.0
8.1
1.0
Top p
7.2
7.0
8.4
6.6
7.4
Prompt 2
Min-p
6.8
7.0
7.6
7.2
6.4
Top-H
7.4
8.0
Top-p
7.0
6.4
8.0
7.6
8.0
Prompt 3
Min-p Top-H
6.4
5.5
8.0
6.2
7.2
9.0
Top.p
8.0
7.5
9.0
7.6
8.4
Prompt
Min
7.9
7.8
8.4
7.5
8.4
Top-H
8.5
8.3
8.8
8.4
Phi-3-Mini
1.5
Top-p
7.2
6.8
7.2
6.6
Prompt 2
Min-p
7.4
7.4
8.2
7.8
8.0
Top-H
8.2
8.0
7.4
7.6
7.8
Top-p
7.4
7.1
8.4
7.1
Prompt 3
Min-p
6.9
6.6
7.7
7.2
7.2
Top-H
8.2
8.0
8.0
8.0
8.3
Top-p
7.2
7.0
5.6
Prompt
Min-p
7.6
7.8
8.6
8.6
Top-H
7.6
7.8
8.6
8.0
8.6
Top-p
8.6
8.8
5.5
7.0
8.7
Prompt
Min
7.4
8.8
7.8
Top-H
8.6
8.2
8.4
8.3
8.3
Top-p
7.4
7.6
5.0
5.8
7.4
Prompt
Min
8.0
Top-H
7.4
7.8
8.4
7.6
8.2
Top-p
5.0
4.8
7.2
5.4
5.2
Prompt
Min-p
4.8
4.0
6.2
4.2
4.2
Top-H
8.2
7.8
7.2
7.6
1.0
Top-p
7.4
6.8
8.0
6.8
7.1
Prompt 2
Min-p
6.4
6.4
7.0
6.2
6.4
Top
7.6
7.6
7.2
7.6
Top-p
6.0
5.3
8.4
6.4
6.8
Prompt 3
Min-p
6.4
6.0
7.0
5.8
6.6
Top
7.9
7.6
8.0
7.3
Top-p Minep Top-H
6.0
5.3
7.8
5.6
Prompt
6.1
5.4
6.0
5.1
4.9
7.9
8.0
8.1
7.3
7.8
Qwen2.5
Top p
6.8
7.6
6.8
Prompt 2
Min-p Top H
6.8
6.2
7.4
6.8
6.8
8.2
8.2
8.0
8.0
8.6
Top-p Min-p
7.2
6.9
7.3
6.2
Prompt
6.7
6.5
7.2
7.1
Top-H
7.6
7.5
7.6
7.2
8.1
Top
6.0
5.4
3.8
3.6
Prompt
Min-p
7.0
Top H
7.4
7.4
8.0
6.8
7.2
Top-p Min-p Top-H
7.6
8.0
4.6
5.8
7.0
Prompt 2
6.2
6.3
7.8
5.8
7.5
7.8
8.1
7.0
Top P
7.4
7.1
4.3
5.5
6.3
Prompt
Min-p
6.6
6.5
5.5
6.4
Top-H
7.3
7.4
Table 5: Evaluation metrics and the judge scores (on scale of 1.0 10.0) for different LLMs, temperatures, prompts, and sampling methods. M1-M5 denote creativity, originality, narrative flow, imagery, and vitality, respectively.
29

---

Method
Temperature = 1.0
Temperature = 1.5
Temperature = 2.0
Top-p
7.06
6.75
3.86
Min-p
7.08
7.11
6.44
Top-H
7.08
7.14
7.04
Table 6: MT-BBench results with LLLaMA333-70B-Insttte
Method
Temperature = 1.0
Temperature = 1.5
Temperature = 2.0
Top-p
43.75
41.74
34.15
Min-p
45.76
42.41
39.29
Top-H
51.12
48.88
45.31
Table 7: GPQA results with LLaMAB.3-70B-Instre.
Additionally, with the large model, we produced results with the LLM-as-judge setup described in This demonstrates top-H's consistent improvement trend over
Section 6.1.3, reported in Table 8 alternatives.
Temperature
Sampling Method
M1
M2
M3
M4
M5
Top-p
6.05 0.24
6.10 0.22
8.80 + 0.20
7.15 + 0.26
6.95 + 0.22
1.0
Min-p
0.22
7.10
8.85
7.95 0.15
8.00 = 0.26
Top-H
8.10 = 0.26
8.85 0.22
8.05 4: 0.22
7.60 + 0.20
8.10 = 0.24
Top-p
6.95 0.22
7.80 0.20
8.65 + 0.15
8.35 1: 0.22
8.40 ::: 0.20
1.5
Min-p
7.10 0.30
7.15 0.22
8.05 0.15
7.25 + 0.26
7.15 + 0.22
Top-H
8.95 0.20
8,90 + 0.15
8.10 +10++00 0.20
9.00 + 0.22
8.95 + 0.22
Top-p
7.75 0.22
8.15 0.26
5.55 + 0.22
7.60 + 0.20
7.25 + 0.26
2.0
Min-p
8.15 0.20
7.30 0.35
6.25 0.22
8.05 + 0.24
6.80 + 0.22
Top-H
8.80 0.20
8,20 0.30
7.10 + 0.26
8.00 + 0.15
7.85 + 0.20
Table 8: LLM-as-judge results with LLaMA3.3-70B-Instre
C.3
Human Eval
We have conducted Human Evaluation of LLLM-generated texts using setup similar to that of min-p. and compared with top-p and min-p. We recruited 14 PhD students for this. We used LLaMA3.1 8B-Instruct with texts generated using prompt adapted from the min-p framework: "Write me creative story." For each configuration, we generated three outputs, capped at 512 tokens. Participants asked to evaluate them along quality and diversity with rating on scale of 1-10. Results are shown in Table
Sampling Method
Creativity (T=0.))
Coherence (T=0.7)
Creativity (T=1.)
Coherence (T=1.0)
Creativity (T=2.0)
Coherence (T=2.0)
Top-p
7.57
Min-p
Top-It
7.35 1 0.71
5/42 1 0.62
1. 0.90
6.42 1. 0.91
6.42 1: 0.62
7.07 4: 0,70
Table 9: Human evaluation results on creativity and coherence ratings.
C.4 Top-H truncation threshold
In this section, we demonstrate how top-H H addresses the limitations of min-p sampling, illustrated Fig. [ which served as our motivational case study. Comparing the two distributions, we observe that distribution A exhibits greater randomness, with higher proportion of low-probability tokens relative to distribution This observation supported by their entropy values: distribution A has an entropy of 4.28, while distribution B has lower entropy of 3.71. Consequently, optimal
30

---

Distribution A
Distribution B
0.4
Top-H cut-off threshold
Top-H cut-off threshold
Probability
0.2
0.0
20
40
0
10
20
Token Index
Token Index
Figure 6: Probability distribution of two different types with associated top-H thresholds.
decoding strategy would be expected to allocate a larger sampling pool in scenario A, reflecting model'ss lower confidence. This is precisely how the top-H decoding method operates. When applied with a = 0.4, the resulting entropy thresholds are shown in Fig. [6 As illustrated, top-H assigns a significantly larger token set to distribution A to accommodate its higher uncertainty- adjustment that min-p fails to make. Moreover, in scenario B, top-H retains several high-probability tokens that min-p erroneously excludes. Therefore, top-H effectively addresses both key shortcomings of min-p sampling in such settings.
C.5 Impact the a Parameter
Table 10 reports GPQA accuracy and the average sampling pool size across different values. The experiment is done using the LLaMA3. 1-88---imnn -B-Instruct model with temperature T 1.5. These results show that:
1. Larger values slightly reduce accuracy, which aligns with the nature of GPQA's graduate- level questions that benefit from more confident (less diverse) answers.
2. Sampling pool size inereases with a, providing more generative options and supporting the creativity aspect observed in Figure
Accuary GIPQA
0.3085
0.988
0.305
0.3085
0.3155
0.303
03388
0.3050
0.7899
0.2917
0.387
0.279
0.2688
0.287M
0.2613
0.2656
0.2701
Average sampling pook size
1.01
1.05
1.20
1.48
1.90
2.3
3.48
4.94
6.94
9.11
11.79
15.77
21.38
27.99
36.28
47.06
59.28
Table 10: GPQA accuracy and average sampling pool size across different
C.6 Comparison of top-H to Mirostat method
In addition to the results obtained with sammpling. we include further comparisons with Mirostat (Basu et al. 2020) Table for MTBench and Table [2] GPQA, serving additional entropy- aware baseline. Unless otherwise specified, all decoding and evaluation configurations follow those in the paper. For Mirostat,
the target entropy parameter
B.AMA3.1-8-IInstree
Phi-3-Mini
Qwen2.5 3B
Temperature
Top-H
Mirostat
Top-H
Mirostat
Top-H
Mirostat
1.0
6.788
6.375
6.819
6.600
5.956
5.369
1.5
6.819
5,594
6.556
5,500
5.513
4.469
2.0
6.438
5,519
6.056
5.269
4.519
4.256
Table 11: MTBench results comparing Top-H and Mirostat. Top-H wins in all 9 settings. Averaged over all models and temperatures, Top-H achieves 6.3 vs. Mirostat 5,439 (+0.724 absolute, +13.3%).
D Limitations
In this paper, we introduced a novel sampling tophod-top-H-ag greedy solution to the NP- hard contray-e mass maximization (ECMM) problem. While top-H demonstrates strong
31

---

LLaMAA31-8BInstee
Phi-3-Mini
Qwen2.5 3B
Temperature
Top-H
Mirostat
Top-H
Mirostat
Top-H
Mirostat
1.0
29.24
30.36
32.37
30.13
28.79
28.35
1.5
30.58
25.67
30.80
29.02
27.90
26.34
2.0
28.79
28.79
30.80
29.91
28.12
27.79
Table 12:
GPQA results comparing Top-H and Mirostat. Top-H outperforms Mirostat in 7 of settings, with one Mirostat win at LLaMA-8B (T 1.0). Averaged over all models and temperatures, Top-H achieves 29.71 vs. Mirostat 28.48 (+1.23 absolute, +4.3%).
empirical performance, it does not provide general competitive guarantees that apply across broad range of distributions. Moreover, the hyperparameter was tuned manually, even though the method exhibits robustness to its variation. Designing an algorithm that offers a provable approximation ratio and can dynamically adapt the entropy threshold remains important direction for future work.
E
Broader Impact
Top-H sampling enhances the coherence and creativity of text generated by large language models, especially high temperatures. This can positively impact applications such as creative writing, education, and human-Al interaction by making outputs more diverse and engaging. Its efficiency and ease integration also support broader accessibility open-source settings. However, the same improvements in fluency could be misused to generate more persuasive disinformation evade content moderation. While top-H
ceneral-purport sampling method, we recommend pairing with safety mechanisms and monitoring in sensitive deployments. Open-sourcing our implementation and providing clear usage guidelines will support responsible adoption and further research.
32


Reviews:
[{"review_id": "JrwZYjCNxS", "reviewer": "Reviewer_ELnF", "summary": "This paper introduces top-H decoding, a novel sampling strategy for LLMs that aims to balance creativity and coherence in text generation. The authors formulate this challenge as an entropy-constrained minimum divergence (ECMD) problem, which they prove equivalent to an entropy-constrained mass maximization (ECMM) problem. After showing ECMM is NP-hard, they propose a practical greedy algorithm that dynamically selects tokens based on entropy constraints. The method outperforms existing approaches, such as min-p and top-p sampling, achieving improvements in accuracy on creative writing benchmarks and maintaining robustness on reasoning tasks.", "questions": "1. **Theoretical justification for constraint form**: Why is the entropy constraint α·H(p) the most appropriate form? Have you considered alternative constraint formulations that might be more theoretically principled?  \n\n2. **Approximation guarantees**: Given the careful theoretical setup, can you provide any approximation bounds for the greedy algorithm, even in special cases? This would significantly strengthen the theoretical contribution.  \n\n3. **Computational analysis**: How does the computational overhead of top-H compare quantitatively to simpler methods like top-p and min-p? Can you provide timing comparisons and analysis of the trade-off between performance and efficiency? \n\n4. **Human evaluation validation**: The heavy reliance on LLM-as-judge evaluation is concerning. Can you provide human evaluation studies to validate that the improvements measured by GPT-4o actually correspond to human preferences?  \n\n5. **Hyperparameter robustness**: How sensitive is performance to the choice of α across different models, tasks, and domains? Can you provide guidance for setting α beyond empirical grid search?", "limitations": "The authors acknowledge the limitation regarding lack of formal approximation guarantees in Appendix E. However, they could better address several other limitations: (1) the heavy reliance on automated evaluation without human validation, (2) the limited theoretical analysis of why the specific entropy constraint form is optimal, (3) incomplete analysis of computational overhead, and (4) potential sensitivity to hyperparameter choices across different domains.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**  \n1. **Strong theoretical foundation**: The paper provides a principled mathematical framework for the creativity-coherence tradeoff by formulating it as an optimization problem with entropy constraints.\n\n2. **Comprehensive experimental evaluation**: Extensive experiments across multiple models (LLaMA3.1, Qwen2.5, Phi-3), benchmarks (Alpaca-Eval, MT-Bench, GSM8K, GPQA), and temperature settings demonstrate consistent improvements over baselines.  \n\n3. **Simple algorithm with strong empirical performance**: The greedy algorithm is simple to implement and shows robust performance, particularly at higher temperatures.\n\n4. **Thorough analysis of design choices**: Good ablation studies on the α parameter and empirical validation that the greedy solution approximates the optimal solution.\n\n5. **Temperature robustness**: Top-H maintains performance much better than alternatives as temperature increases, which is crucial for creative applications.  \n\n**Weaknesses:**  \n1. **Limited theoretical novelty**: While the formulation is sound, entropy-based sampling has been explored before (η-sampling). The main theoretical contribution is the specific ECMD formulation and NP-hardness proof, which are somewhat incremental.  \n\n2. **No approximation guarantees**: Despite the careful theoretical setup, the proposed greedy algorithm comes with no formal approximation bounds or worst-case performance guarantees, limiting the theoretical value.  \n\n3. **Questionable evaluation methodology**: Heavy reliance on LLM-as-judge evaluation without human validation raises concerns about evaluation validity. It can be good to make human evaluation similar to the min-p paper. \n\n4. **Hyperparameter sensitivity**: The α parameter requires careful tuning, and while the paper shows α=0.4 works well empirically, there's limited theoretical guidance for choosing this value or adapting it across different contexts.", "was_revised": true, "final_justification": "I think the paper is good for publication at NeurIPS despite these weaknesses, which were mentioned by Reviewer 2JSm. I don't find the overcomplicated theory a problem, but I agree that better human evaluation can make the paper stronger.", "rebuttal": "We thank the reviewer  ELnF for the insightful feedback and clarify their concerns below.\n\n>**Justification for constraint form:**\n\nThe choice of the entropy constraint form, $H(q) \\le \\alpha H(p)$, is central to our method's theoretical foundation and is chosen for its ability to dynamically balance creativity and coherence. We aim to develop a sampling framework explicitly aware of the model's confidence, not just based on the single highest-probability token, but on the overall shape of the probability distribution. Shannon entropy $H(p)$, is a measure for the uncertainty of the entire distribution $p$.\nAdditionally, the formulation establishes an **adaptive upper bound on the randomness** of the selected token distribution, $q$. This way the generation can retain the following:\n\n*Adapts to Model Confidence:* The constraint is proportional to the entropy of the model's original prediction, instead of a fixed value. Thus, when the model is uncertain (the distribution is flat, with a high $H(p)$), it allows the sampling distribution $q$ to have a higher entropy,  encouraging  exploration and creativity when multiple tokens are plausible candidates. Alternately, when the model is confident (distribution with sharp peaks, with a low $H(p)$), it forces  the sampling distribution $q$ to have a lower entropy, preserving  coherence by restricting the sampling pool to high-probability tokens.\n\n*Provides Control:* The hyperparameter $\\alpha \\in$ (0,1) acts as a knob to control the trade-off between creativity and coherence. \n\n>**Exploration of alternative formulations:** \n\nWe considered approaches including Mirostat [1],min-p [2], and top-p [3]. However, these approaches either fail to adapt to the model's confidence or lack a direct theoretical link to the distribution's overall uncertainty.\n\n\n>**Incremental contribution over $\\eta$‑sampling** \n\nDespite both works control randomness via entropy, following are key differences:\n $\\eta$‑sampling specifies a *rule* (“clip until entropy < $\\eta$”) without any optimization to balance between creativity and coherence while ECMD starts from first principles, *minimize divergence from the model distribution subject to an entropy cap*. We further demonstrate the divergence-mass equivalence for the first time with an information-theoretic justification.\nWe analyze the *unrestricted subset selection* problem (no contiguity imposed on the order of token selection) and show it is NP-hard. This explains *why* a naive global optimizer is impractical motivating our greedy restriction. We further prove **monotone entropy growth** (Thm. 3) within probability-ordered prefixes giving a unique stopping point and justifying Top‑H. $\\eta$‑sampling offers neither hardness results nor structural theorems.\nECMD provide a **single objective** that subsumes and relates diverse decoding heuristics (T, nucleus, top‑k) under clear trade-off parameters $\\alpha$. We quantify how close the greedy solution is to the true optimum (Fig. 5: conservative mean − $\\sigma$ mass ratio ≥ 96%), while prior work lack these approximation results.\n\n>**Approximation guarantee:**\n\nPlease refer to the **Discussion on formal approximation bound for the Top-H** response to reviewer bsFC on this. \n\n>**Computational overhead  and timing comparisons:** \n\nTable R1T1 provides the comparison of the average runtime per token (ms/token) of Top-H with Top-p and Min-p. We used LLaMA3.1-8B-Instruct, LLaMA3.3-70B-Instruct, and Phi-3-Mini-3.8B. For each setting, we averaged results over 100 prompts from the AlpacaEval, generating 128 tokens per prompt. \n### R1T1\n|  **Temp** | **LLaMA-8B** | **LLaMA-8B**| **LLaMA-8B**| **Phi-3** | **Phi-3**  | **Phi-3**  | **LLaMA-70B** | **LLaMA-70B** |**LLaMA-70B**  |\n|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|\n|     | Top-H | Min-p | Top-p | Top-H | Min-p | Top-p | Top-H | Min-p | Top-p |\n| **1.0** | 28.3951 | 27.3396 | 27.4275 | 24.3847 | 23.6499 | 23.7809 | 219.3837 | 219.1391 | 218.4900 |\n| **2.0** | 28.4671 | 27.3840 | 27.4389 | 24.5929 | 23.9397 | 23.5844 | 219.3428 | 218.3609 | 217.7083 |\n\nSpecifically, we observe a negligible overhead of as low as 0.8%.\n\nComplexity analysis: All methods begin with a sorting step, typically $\\mathcal{O}(n ~ log ~ n)$.\nTop-p and Min-p performing CUMSUM and thresholding, respectively, both having a complexity of $\\mathcal{O}(n)$. Below, we explain the incremental entropy accumulation of Top-H to be $\\mathcal{O}(n)$.\nThe Theorem 3 of the paper leads to the following algorithm for computing entropy incrementally:  \nLet us define $\\(h_{j-1} = \\sum_{i=1}^{j-1} p_i \\log p_i \\)$, so the expression becomes:\n$H(q^{j-1}) = \\log (\\Gamma_{j-1}) - \\frac{h_{j-1}}{\\Gamma_{j-1}}$  \nNow, incremental entropy accumulation pseudocode:\n```\nInitialize Γ ← 0,  h ← 0,  H ← 0\nfor each step j:\n    Γ ← Γ + p_j\n    h ← h + p_j log p_j\n    H ← log(Γ) - h / Γ\n```\nThis runs in $\\mathcal{O}(n)$ time.\n\n>**Need for Human Eval:** \n\nWe have now conducted Human Eval of LLM-generated texts using a setup similar to that of min-p, and compared with Top-p and Min-p. We recruited 14 PhD students for this. We used LLaMA3.1-8B-Instruct with texts generated using a prompt adapted from the min-p framework: “Write me a creative story.”  For each configuration, we generated three outputs, capped at 512 tokens. Participants were asked to evaluate them along quality and diversity with rating on a scale of 1-10. Results are shown in R1T2.\n\n### R1T2\n| Sampling Method | Creativity (T = 0.7) | Coherence (T = 0.7) | Creativity (T = 1.0) | Coherence (T = 1.0) | Creativity (T = 2.0) | Coherence (T = 2.0) |\n|:--:|:--:|:--:|:--:|:--:|:--:|:--:|\n| Top-p        |      7.57 $\\pm$ 0.72               |    4.78 $\\pm$ 0.93                |         6.28 $\\pm$ 0.69             |     5.78 $\\pm$ 0.79                |        3.57 $\\pm$ 0.72              |         7.57 $\\pm$ 0.62            |\n| Min-p        |      6.92 $\\pm$ 0.59                |    5.28 $\\pm$ 1.03                 |       6.21 $\\pm$ 0.77               |      5.92 $\\pm$ 0.79               |     6.00 $\\pm$ 0.75                 |   6.57 $\\pm$ 0.72                  |\n| Top-H        |       7.35 $\\pm$ 0.71               |      5.42 $\\pm$ 0.62               |      6.57 $\\pm$ 0.90                |         6.42 $\\pm$ 0.91            |       6.42 $\\pm$ 0.62               |   7.07 $\\pm$ 0.70                  |\n\n> **Hyperparameter robustness:**\n\nPlease note that Figure 4 of the draft shows the creativity-coherence trade-off across a range of $\\alpha$ values. Specifically, the changes in coherence and creativity metrics are gradual with changes in $\\alpha$, indicating it to not be overly sensitive to small adjustments. Intuitively, $\\alpha$ controls the balance between confidence and diversity in the decoding, with small $\\alpha$ encouraging more deterministic outputs while its large value increasing the randomness and thus encouraging creativity.\nThis controllability gives users practical guidance: moderate $\\alpha$ values (around 0.4) offer a balanced trade-off, and users can adapt $\\alpha$ based on their preference for coherence versus creativity. \nAdditionally, the following table R1T3 reports GPQA accuracy and the average sampling pool size across different $\\alpha$ values. The experiment is done using LLaMA3.1-8B-Instruct model with temperature T = 1.5. These results show that: 1. Larger $\\alpha$ values slightly reduce accuracy, which aligns with the nature of GPQA’s graduate-level questions that benefit from more confident (less diverse) answers. 2. Sampling pool size increases with $\\alpha$, providing more generative options and supporting the creativity aspect observed in Figure 4.\n### R1T3\n|$~~~~~~~~~~~~~~~~~~~~~~~\\alpha$|0.10|0.15|0.20|0.25|0.30|0.35|0.40|0.45|0.50|0.55|0.60|0.65|0.70|0.75|0.80|0.85|0.90|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|Accuracy on GPQA(%)|0.3085|0.3085|0.3095|0.3085|0.3125|0.3103|0.3058|0.305|0.2869| 0.2937|0.2879|0.279|0.2655|0.2879|0.2612|0.2656|0.2701|\n|Average sampling pool size|1.01|1.03|1.20|1.48|1.90|2.53|3.48|4.74|6.94|9.11|11.79|15.77|21.35|27.99|36.28 |47.06|59.28|\n\nImportantly, both accuracy and sampling pool size show smooth and consistent trends, reinforcing the method’s robust behavior. For moderate $\\alpha$, accuracy changes smoothly; the small fluctuations at higher $\\alpha$ are expected, as higher $\\alpha$ increases the sampling pool and thus randomness.\n\n---\n## References\n\n[1] Mirostat: A neural text decoding algorithm that directly controls perplexity, arXiv.\n\n[2] Turning up the heat: Min-p sampling for creative and coherent llm outputs, arXiv .\n\n[3] The curious case of neural text degeneration, arXiv ."}, {"review_id": "MiihslHosP", "reviewer": "Reviewer_2JSm", "summary": "The paper introduces Top-H, a truncated LLM sampling approach, which greedily selects the most-confident tokens up to a fraction of the original entropy for sampling. Empirical evaluation using various models (LLaMA3.1, Qwen2.5, Phi-3) on several tasks (creative writing, reasoning, QA, that is on Alpha-Eval & MT-bench, GSM8K CoT, and GPQA) shows better performance vs baselines such as top-p, top-k, min-p, and eta-sampling.", "questions": "1. **Fundamental theoretical validity**: Given that reasonable truncated sampling should never drop higher-confidence tokens for lower-confidence ones, why formulate ECMD to allow such counterintuitive solutions? Isn't the \"greedy approximation\" actually the correct algorithm, making the NP-hardness analysis irrelevant? Can you construct a case, where we would want to drop the maximum confidence token, or generally tokens with higher confidence in favor of tokens with lower confidence?\n2. **Alternative theoretical foundation**: Can you reformulate the approach based on maximum entropy principles over confidence-ordered contiguous token sets? This seems like a more natural and theoretically sound foundation than the current ECMD formulation.  \n3. **Statistical significance**: Can you provide confidence intervals or statistical significance tests for your results? The current reporting of only means over 5 runs is insufficient to establish that improvements are statistically meaningful.  \n4. **Scalability validation**: How does top-H perform on larger models (70B+) where baseline methods have been tested? The current evaluation on only small models limits the generalizability of claims.  \n5. **Judge reliability**: Given the heavy reliance on GPT-4o evaluation, can you validate judge reliability through inter-annotator agreement with human evaluators or comparison with multiple judge models?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n1. **Comprehensive empirical evaluation**: The experiments span multiple small state-of-the-art models (\\<=8B params), diverse task types, and include both automatic metrics and LLM-as-judge evaluations. The results show improvements, especially in high-temperature settings..  \n2. **Clear motivation and practical relevance**: The motivational example conceptually shows limitations of existing methods, i.e. min-p sampling, and the proposed solution integrates seamlessly into existing generation pipelines.  \n3. **Well-written and accessible**: The paper is clearly structured with good intuitive explanations alongside technical details.\n\n**Weaknesses:**\n\n1. **Inadequate statistical reporting**: The paper reports only means over 5 runs without confidence intervals, making it impossible to assess statistical significance of the reported improvements.  \n2. **Limited experimental scope**: Only small models are evaluated (largest is 8B), while e.g. min-p  baseline studies, whose evaluations this paper seems to copy, included Llama 70B. No human evaluation is conducted, and heavy reliance on GPT-4o as judge introduces potential systematic biases without validation of judge reliability.  \n3. **Fundamental theoretical flaws**: The core theoretical contribution is undermined by several critical issues:  \n   * **Misguided problem formulation**: Any reasonable truncated sampling should never drop a token with higher confidence in favor of one with lower confidence. This principle immediately constrains truncated sampling to contiguous sets of tokens sorted by confidence.  \n   * **Theory contradicts intuition**: If the optimal solution to ECMD discards high-confidence tokens in favor of lower-confidence ones, then ECMD is the wrong objective function. The greedy algorithm isn't approximating an NP-hard problem: it's actually solving the correct problem that ECMD fails to capture (otherwise it wouldn’t be NP-hard).  \n   * **Redundant complexity**: Top-H follows naturally from the principle of maximum entropy within confidence-ordered contiguous sets (maximum uninformativeness principle) for a given dynamic entropy threshold, rendering the complex ECMD formulation unnecessary.  \n   * **Unjustified design choices**: The choice of Jensen-Shannon divergence lacks strong theoretical motivation (and the α parameter appears empirically driven rather than principled).  \n4. **Vacuous theoretical results**: Theorem 3 (termination guarantee) is essentially meaningless since any algorithm operating on finite vocabulary with per-token decisions is trivially guaranteed to terminate. The result provides no useful insight.\n5. **Exaggerated claim(s)**: \"solving the ECMD problem can ideally balance creativity and coherence\" is an unnecessarily strong and broad claim that is not evidenced by the paper.", "was_revised": true, "final_justification": "The human eval has flaws (sadly, so does min-p in my opinion). But this one has even fewer participants (14). \n\nI'm also still not convinced by the necessity for all the theoretical complexity when the same greedy algorithm can be explained and motivated differently as well, following existing literature. There is no need to field NP-hard problems and then simplify them to a greedy algorithm in line with other popular sampling methods. The authors have agreed \"that a maximum‑entropy (ME) view over confidence‑ordered prefixes is intuitive and top‑H can be stated that way\". In my opinion, the simpler motivations should win, and the current theory-heavy setup distracts from the actual algorithm and its empirical examination.\n\nThere is also another discrepancy in the appendix D in the given implementation for top-H that also seems to use top-K by default, which has not been mentioned anywhere else in the paper.\n\nOverall, I think keeping my current score is warranted.", "rebuttal": "We thank the reviewer  2JSm for the insightful feedback and clarify their concerns below.\n\n> **Inadequate statistical reporting:** \n\nWe have performed 10 runs and computed standard deviation across all runs for each config. We see the max std dev to be $\\pm 0.35$; we commit to update Table 3 with the detailed results.\n\n>**Validation with large model:** \n\nWe replicated the MT-Bench (R2T1) and GPQA (R2T2) experiments using **LLaMA3.3-70B-Instruct** with the setup of section 6.1 in the paper. Specifically, top-H outperforms min-p by up to 6.0% and 6.47% on MT-Bench  and GPQA, respectively. \n### R2T1\n| Method  | T = 1.0 | T = 1.5 | T = 2.0 |\n|:--:|:--:|:---:|:--:|\n| top-p   | 7.06        |  6.75       |  3.86       |\n| min-p   |      7.08   |   7.11      |   6.44      |\n| top-H   |   **7.08**      |    **7.14**     |    **7.04**     |\n\n### R2T2\n| Method  | T = 1.0 | T = 1.5 | T = 2.0 |\n|:--:|:--:|:--:|:--:|\n| top-p   | 43.75        |  41.74      |  34.15       |\n| min-p   |      45.76   |   42.41      |   39.29      |\n| top-H   |   **51.12**      |    **48.88**     |    **45.31**     |\n\nAdditionally, with the large model, we produced results with LLM-as-judge setup described in Section 6.1.3, and is reported in Table R2T3. This demonstrates top-H’s consistent improvement trend over alternatives.\n\n### R2T3\n\n| Temperature | Method |  $~~~~~~$ M1   | $~~~~~~$ M2   |  $~~~~~~$ M3   | $~~~~~~$ M4   | $~~~~~~$ M5   |\n|:-----------:|:----------------:|:------:|:------:|:------:|:------:|:------:|\n| T = 1.0     | top-p           | 6.05 $\\pm$ 0.24 | 6.10 $\\pm$ 0.22 | 8.80 $\\pm$ 0.20 | 7.15 $\\pm$ 0.26 | 6.95 $\\pm$ 0.22 |\n|             | min-p           | 7.05 $\\pm$ 0.22 | 7.10 $\\pm$ 0.22 | **8.85** $\\pm$ 0.20 | **7.95** $\\pm$ 0.15 | 8.00 $\\pm$ 0.26 |\n|             | top-h           | **8.10** $\\pm$ 0.26 | **8.85** $\\pm$ 0.22 | 8.05 $\\pm$ 0.22 | 7.60 $\\pm$ 0.20 | **8.90** $\\pm$ 0.20 |\n| T = 1.5     | top-p           | 6.95 $\\pm$ 0.22 | 7.80 $\\pm$ 0.2 | **8.65** $\\pm$ 0.15 | 8.35 $\\pm$ 0.22 | 8.40 $\\pm$ 0.20 |\n|             | min-p           | 7.10 $\\pm$ 0.30 | 7.15 $\\pm$ 0.22 | 8.05 $\\pm$ 0.15 | 7.25 $\\pm$ 0.26 | 7.15 $\\pm$ 0.22 |\n|             | top-h           | **8.95** $\\pm$ 0.20 | **8.90** $\\pm$ 0.15 | 8.10 $\\pm$ 0.2 | **9.00** $\\pm$ 0.22 | **8.95** $\\pm$ 0.22 |\n| T = 2.0     | top-p           | 7.75 $\\pm$ 0.22 | 8.15 $\\pm$ 0.26 | 5.55 $\\pm$ 0.22 | 7.60 $\\pm$ 0.20 | 7.25 $\\pm$ 0.26 |\n|             | min-p           | 8.15 $\\pm$ 0.20 | 7.30 $\\pm$ 0.35 | 6.25 $\\pm$ 0.22 | 8.05 $\\pm$ 0.24 | 6.80 $\\pm$ 0.22 |\n|             | top-h           | **8.80** $\\pm$ 0.20 | **8.20** $\\pm$ 0.30 | **7.10** $\\pm$ 0.26 | **8.00** $\\pm$ 0.15 | **7.85** $\\pm$ 0.20 |\n\n\n>**Human evaluation results:** \n\nPlease refer to the table R1T2 of the rebuttal response for reviewer ELnF.\n\n>**On misguided problem formulation-explanation of greedy solution to not be optimal:** \n\nWhile the reviewer’s intuition largely holds in practice, there are certain situations where the **greedy solution wouldn’t be optimal** and there are some nuances only ECMM captures. We explain it below.\n\n*Case for a lower-p token might be preferred over a higher one:* Entropy responds in a highly non-linear way after renormalization. When the entropy cap is tight and we have multiple high-probability (dominant) tokens, the distribution can be so flat that adding *any* extra token violates $H(q)\\\\le \\\\alpha H(p)$. Dropping one of the dominant tokens sharpens $q$, letting us include several medium-probability tokens whose **combined** mass exceeds what was lost, thereby increasing $\\\\Gamma\\_S$. We present an example of such in sorted order, resembling an hypothetical set of probabilities generated by an LLM.\n```\n[4.438e-01, 4.006e-01, 1.027e-01, 3.320e-02,\n 8.733e-03, 5.801e-03, 2.413e-03, 1.468e-03,\n 4.460e-04, 4.286e-04, 1.804e-04, 5.383e-06,\n 5.205e-07, 3.760e-08, 1.521e-12]\n```\nLet the entropy threshold with $\\alpha=0.4$ be $0.6796$. The greedy solution takes only the first token with a probability of 4.438e-01 and stops, due to threshold exceeding issue. However, the optimal solution $\\\\Gamma\\_S$ would be subset `[4.438e-01, 1.027e-01, 3.320e-02, 1.804e-04, 5.383e-06, 5.2056e-07, 3.760e-08, 1.521e-12]` with an entropy of 0.6777 and a retained mass of 0.580 \\> 0.4438 (greedy solution). Thus, there are special cases where the optimal solution to ECMM would prefer a token with a lower probability over a token with a higher probability. \n\n>**Exaggerated claim(s): \"solving the ECMD problem can ideally balance creativity and coherence\"**\n\nBased on the above example, we argue that *solving the ECMM problem can yield solutions better than the greedy algorithm, particularly for corner cases.* This rationale also helps ECMM maintain a significantly better creativity-coherence trade-off over the SoTA: maximizing $\\\\Gamma\\_S$ enforces coherence, while the entropy cap gates creativity and prevents coherence degradation. Top-H implements this balance greedily: it locks in the most probable tokens first, then expands until the entropy budget is about to be exceeded.\n\n>**The Choice of JSD:** \n\nWe chose JSD because it is a standard, bounded, and symmetric measure of divergence. Crucially, as we prove in Theorem 1, minimizing the JSD between our distributions is mathematically equivalent to maximizing the retained probability mass ($\\\\Gamma\\_S$​). This is a powerful and intuitive result: our theoretically grounded objective of minimizing divergence simplifies to the very practical goal of keeping the most probable tokens, which directly addresses the coherence objective.\n\n>**Vacuous theoretical results (Theorem 3):** \n\nWe agree that *mere* termination on a finite vocabulary is trivial. Theorem 3 is not about finiteness, rather establishes a **strict monotonicity property of entropy under probability‑ordered inclusion**. Thus, there is a single crossing point of the constraint $\\(H(q_k)\\le \\alpha H(p)\\)$ that greedy algorithm finds. This ensures: 1. Strict monotonicity guaranteeing a *unique* stopping index. Without it, we could overshoot/undershoot the entropy cap. 2. The theorem is the **formal link** between the entropy constraint and the greedy prefix growth, making it an inevitable consequence—not just a heuristic. 3. The ordering assumption is what turns an NP‑hard subset problem into a linear‑time scan.\n\n>**Alternative theoretical foundation:** \n\nWe agree that a maximum‑entropy (ME) view over confidence‑ordered prefixes is intuitive and top‑H can be stated that way. However, ECMM formulation is strictly more general (it does **not** assume contiguity), yields the divergence–mass equivalence (Thm. 1), and provides the optimality/complexity guarantees that the ME‑prefix view alone cannot.\n\n#### 1. Maximum-Entropy restatement of Top-H (under prefix restriction)\n\nLet $p$ be sorted by probability: $p_{(1)} \\ge p_{(2)} \\ge \\dots$.\nFor the prefix $S_k = \\{1,\\dots,k\\}$, define\n$q_k(i) = \\frac{p_{(i)}}{\\sum_{j \\le k} p_{(j)}} \\quad (i \\le k).$\n\nIf we **restrict ourselves to such prefixes**, then choosing “the most uninformed (highest entropy) distribution that still respects the entropy cap” reduces to:\n\n$k^\\star = \\max\\{k \\mid H(q_k) \\le \\alpha H(p)\\}.$\n\nSince $H(q_k)$ increases monotonically with $k$ when tokens are added in descending $p_{(i)}$ (Theorem 3), this rule is identical to Top-H that adding tokens until the entropy cap would be violated. Thus, under prefix restriction, the top-H is equivalent to the maximum-entropy set (subject to the $\\alpha H(p)$ threshold) over the confidence-ordered prefix.\n\n#### 2. Relation to ECMD/ECMM\n\nECMD objective starts from minimizing divergence of $p$ (fidelity) while bounding randomness. We show that minimizing JSD under the same entropy cap is equivalent to maximizing retained probability mass $\\Gamma_S = \\sum_{i \\in S} p_i$ (ECMM). Over ordered prefixes, $\\Gamma_{S_k}$ is monotone in $k$, so the ECMM optimum picks the same $k^\\star$.\n\nThus, the ME-prefix view *rephrases* the same greedy rule—but only after imposing the prefix constraint.\n\n>**Why retain ECMD as the main formulation?**\n\n1. *No prefix assumption:* ECMD does not assume contiguity. The fact that greedy prefixes are (near-)optimal is **derived**, not assumed.  \n2. *Theoretical guarantees:* ECMD/ECMM yields (i) the divergence–mass equivalence (Theorem. 1) and (ii) NP‑hardness of the unrestricted problem—explaining why a greedy approximation is appropriate.  \n3. *Interpretability & control:* The entropy ratio $\\(\\alpha\\)$ gives a clear knob linking creativity (entropy) to fidelity (mass), independent of the prefix framing.  \n4. *Unification:* The ECMD lens naturally relates Top‑H to other decoding schemes (temperature, nucleus) within one objective-driven framework."}, {"review_id": "PDZgbqpokM", "reviewer": "Reviewer_bsFC", "summary": "This paper presents top-H decoding, a truncated sampling strategy that aims to balance creativity and coherence.\nThe paper first identifies the limitations in existing truncation-based sampling methods like min-p sampling, which relies solely on the top token probability as a confidence heuristic. \nThey formulate the problem as an entropy-constrained minimum divergence (ECMD) optimization, prove its equivalence to an entropy-constrained mass maximization (ECMM) problem, and show that ECMM is NP-hard. Top-H provides a greedy approximation that dynamically selects tokens to bound the entropy of the truncated distribution while minimizing divergence from the original distribution. \nExperimental results show that top-H Decoding is competitive across creative writing and reasoning tasks on various benchmarks.", "questions": "Please refer to the weakness section", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper provides a rigorous mathematical framework by formulating the creativity-coherence trade-off as an optimization problem. The mathematical proofs are well-presented.\n\n- The paper conducts extensive experiments across diverse benchmarks, including creative writing, reasoning tasks (GSM8K, GPQA), and LLM-as-a-judge evaluations to demonstrate the efficacy of the method.\n\n- The proposed method is computationally efficient and can be applied easily.\n\n**Weaknesses:**\n\n- While the paper proves NP-hardness and provides a greedy solution, it lacks formal approximation bounds for the proposed algorithm. The empirical evaluation in Figure 5 suggests good performance relative to the optimal solution, but without theoretical guarantees, the worst-case behavior remains unclear. This is a significant limitation for a method with strong theoretical motivations.\nThe algorithm doesn't consider alternative orderings or lookahead strategies. For instance, temporarily skipping a token that causes large entropy increases might allow inclusion of multiple smaller probability tokens that together contribute more mass while better respecting the entropy constraint.\n\n- The paper positioned itself as an entropy-aware approach, but the experiments are more about comparing it with sampling-based methods, given that only the $\\eta$-sampling is presented for entropy approaches. More comprehensive comparisons with existing entropy-based methods would provide better context for the contributions.\n\n- While the paper claims the algorithm is computationally efficient, there is insufficient analysis of the actual computational cost compared to simpler baselines. The entropy calculation and iterative token selection process likely introduces overhead that should be quantified.\n\n- The paper only provides quantitative evaluations of the results. Further qualitative studies (e.g., human evaluations) are expected to demonstrate the balance of randomness and coherence of the generated content.", "was_revised": true, "final_justification": "The authors have addressed my concerns", "rebuttal": "We thank the reviewer  bsFC for the insightful feedback and clarify their concerns below.\n\n>**Discussion on formal approximation bound for the Top-H** \n\nWhile the primary objective of our work was to empirically demonstrate the efficacy of the top-H decoding, we largely intend to keep the detailed theoretical underpinning of the error bound analysis as a part of future research. Nevertheless, we now attempt to demonstrate a worst-case bound for top-H under the specific assumption of a probability distribution. \n\n**Zipf model.** Fix a vocabulary of size $n$ and exponent $s>1$. We assume the sorted next-token probabilities obey the classical Zipf / regularly varying law: \n\n$\np_i := \\frac{i^{-s}}{H_{n,s}},\\qquad\nH_{n,s}=\\sum_{j=1}^{n}j^{-s}.\n\\quad (1)\n$\n\nEmpirically, language-model logits are well approximated by $s\\in[1.05,1.20]$ [1]; hence the assumption captures current practice.\n\n**Why a Zipf assumption matters.**\nBecause ECMM is NP‑hard (Appendix C), exact polynomial‑time solutions are unlikely. In the absence of structural assumptions, a constant-factor approximation guarantee for ECMM is highly unlikely unless P=NP, as our NP-hardness proof relies on a gap-preserving reduction from Cardinality-Constrained Subset Sum. This structure is known to be fundamentally difficult to approximate, a standard result in computational complexity theory [2]. However, LLM logits consistently follow heavy‑tailed (Zipf / regularly‑varying) laws, so analysing this regime yields practically relevant bounds.\n\n**Notation.** We write $M(k)=\\sum_{i\\le k}p_i$ for the prefix mass, $T(k)=1-M(k)$ for the tail mass, and $H(k)$ for the entropy of the normalized prefix distribution $q^{(k)}_i=p_i/M(k)$.\n\n---\n\n### Preliminaries\n\n**Lemma 1 (Monotonicity of prefix entropy).**\nFor $1 \\leq k < n$, $H(k) < H(k+1)$.\n\n***Proof.***\nPlease refer to the proof for Theorem 3 of the main manuscript.\n\n**Lemma 2 (Tail mass bound).**\nFor $k<n$,\n\n$\\frac{(k+1)^{1-s}-n^{1-s}}{(s-1)H_{n,s}} \\le T_{n}(k)\\le\\frac{k^{1-s}}{(s-1)H_{n,s}}.$\n\nWhen $n\\gg k$, the numerator difference is $o(k^{1-s})$, so the upper bound is asymptotically tight.\n\n***Proof.***\nApply upper and lower Riemann sums to $\\int_{k}^{n}x^{-s}\\,dx$.\n\n**Lemma 3 (Prefix entropy asymptotics).**\nThere exist constants $c_s,C_s>0$ such that\n\n$c_s+\\frac{s}{s-1}\\log\\left(\\frac{k}{2}\\right)\\le H(k)\\le C_s+\\frac{s}{s-1}\\log k \\quad \\text{for all } k\\ge 2.$\n\n***Proof.***\nCombine Lemma 2 with integral bounds for $\\sum i^{-s}\\log i$.\n\n---\n\n### Depth of the greedy prefix\n\nLet $k_g:=\\max\\{k:H(k)\\le \\alpha H(n)\\}$. Lemma 1 implies $k_g$ is well defined.\n\n**Lemma 4 (Growth rate of $k_g$).**\nThere exist constants $a_s,b_s>0$ such that $a_s n^{\\alpha}\\le k_g\\le b_s n^{\\alpha}$.\n\n***Proof.***\nInsert Lemma 3 into the defining inequality and solve for $k_g$.\n\n---\n\n### Mass captured by **Top-H**\n\nWrite $\\Gamma_g=M(k_g)$. This is the mass captured by the greedy solution. By construction, this solution is valid as it satisfies the entropy constraint $H(k_g) \\le \\alpha H(n)$.\n\n### Tight upper bound for ECMM\n\nLet $S^\\star$ be *any* subset satisfying the entropy constraint, and set $\\Gamma_\\star=\\sum_{i\\in S^\\star}p_i$. We want to bound the maximum possible value of $\\Gamma_\\star$.\n\nThe greedy algorithm selects the prefix $[k_g]$ and captures a mass of $\\Gamma_g = M(k_g) = 1 - T(k_g)$. The total mass of all tokens *not* in the greedy solution is, by definition, the tail mass $T(k_g)$.\n\nAny other valid solution $S^\\star$ can, at best, capture the mass of the greedy solution *plus* some portion of the remaining tail mass. The absolute maximum mass any solution can capture is 1 (the entire vocabulary). Therefore, the maximum possible improvement any optimal solution $\\Gamma_\\star$ can have over the greedy solution $\\Gamma_g$ is bounded by the tail mass that the greedy algorithm left behind:\n\n$\\Gamma_\\star - \\Gamma_g \\le 1 - \\Gamma_g = 1 - M(k_g) = T(k_g). \\quad (\\dagger)$\n\nThis gives us a direct upper bound on the additive gap between the optimal and greedy solutions.\n\n---\n\n**Theorem 1 (Distribution-dependent additive guarantee).**\nUnder equation (1), for every $n\\ge 4$,\n\n$\\Gamma_\\star - \\Gamma_g \\le T_{n}(k_g) \\le \\frac{k_g^{1-s}}{(s-1)H_{n,s}} = \\mathcal{O}(n^{-\\alpha(s-1)}).$\n\n***Proof.***\nFrom ($\\dagger$) we have the additive gap $\\Gamma_\\star-\\Gamma_g\\le T(k_g)=T_{n}(k_g)$. Lemma 2 bounds $T_{n}(k_g)$ by $\\frac{k_g^{1-s}}{(s-1)H_{n,s}}$. Finally, Lemma 4 gives $k_g=\\Theta(n^{\\alpha})$, so the gap decays as $\\mathcal{O}(n^{-\\alpha(s-1)})$.\n\n\n>**Discussion on the effectiveness of greedy:** \n\nWe understand that the approach of dropping high-probability tokens could in principle beat the greedy prefix by allowing more low-mass tokens from the tail. However, as discussed in the paper, this problem (ECMM) is NP hard, and we approximate the solution via a practically feasible greedy approach. Notably, we empirically demonstrate the effectiveness of this greedy based top-H approach to be superior to the existing SoTA. \nAdditionally, under the constrained distribution of the Zipfian regime, the greedy prefix is constructed to generally maximize mass under minimal entropy growth. Because entropy increases monotonically with each added token, and the most probable tokens usually contribute less to entropy per unit mass, the greedy approach reaches the entropy threshold more efficiently than any alternative.\n\n\n\n\n\n\n>**Comparison of top-H to other entropy-based sampling method:** \n\nThe manuscript has results with $\\eta$-sampling. We now present more comparison with\nMirostat [3] on MTBench (R3T1), and GPQA (R3T2) as an additional entropy‑aware baseline. Unless otherwise noted, all decoding/eval settings match the main paper; we set $\\tau$ = 3 for Mirostat.\n\n### R3T1 \n|                | **LLaMA-8B** | **LLaMA-8B**| **Phi-3**    | **Phi-3**  | **Qwen-2.5 3B** |**Qwen-2.5 3B**  |\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|**Temp** | Top-H               | Mirostat          | Top-H        | Mirostat    | Top-H                 | Mirostat|\n| 1.0         | **6.788**          | 6.375              | **6.819**   | 6.600        | **5.956**            |5.369  |\n| 1.5         | **6.819**          | 5.594              | **6.556**   | 5.500        |**5.513**             |4.469  |\n| 2.0         | **6.438**          | 5.519              | **6.056**   | 5.269        | **4.519**            |4.256 |\n\nTop‑H wins in 9/9 settings. Averaged over all models and temperatures, Top‑H = 6.163 vs. Mirostat = 5.439 (+0.724 absolute, +13.3%).\n\n\n### R3T2\n\n|                | **LLaMA-8B** | **LLaMA-8B**| **Phi-3**    | **Phi-3**  | **Qwen-2.5 3B** |**Qwen-2.5 3B**  |\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|**Temp** | Top-H               | Mirostat          | Top-H        | Mirostat    | Top-H                 | Mirostat|\n| 1.0         | 29.24                | **30.36**        | **32.37**   | 30.13        | **28.79**            |28.35  |\n| 1.5         | **30.58**          | 25.67              | **30.80**   | 29.02        |**27.90**             |26.34  |\n| 2.0         | **28.79**          | 28.79              | **30.80**   | 29.91        | **28.12**            |27.79  |\n\nGPQA: Top‑H wins 7/9 settings (1 Mirostat win at LLaMA‑8B, T=1.0). Averages: Top‑H = 29.71 vs. Mirostat = 28.48 (+1.23 absolute, +4.3%).\n\n>**Computational cost of top-H**\nPlease refer to the table  R1T1 and corresponding response to reviewer ELnF . \n\n\n >**Human Evaluation results**\nPlease refer to the table R1T2 and corresponding response to reviewer ELnF .\n\n---\n## References\n[1] Gerlach, Martin, and Eduardo G. Altmann. \"Stochastic model for the vocabulary growth in natural languages.\" Physical Review X 3.2 (2013): 021006. \n\n[2] Papadimitriou, Christos H. \"Computational complexity.\" Encyclopedia of computer science. 2003. 260-265.\n\n[3] Mirostat: A neural text decoding algorithm that directly controls perplexity, arXiv."}]

Author rebuttal:

Meta-review: This paper proposes a new sampling strategy for LLMs, named top-H decoding, which aims to balance creativity and coherence in text generation. The authors prove that the underlying problem is NP-hard and derive a greedy algorithm as a practical solution.

The main concerns raised by the reviewers, including the lack of approximation guarantees, absence of human evaluation, and limited analysis on hyper-parameter sensitivity, were addressed in detail in the author rebuttal.

Reviewer opinions diverged significantly: two reviewers were satisfied with the rebuttal and expressed support for acceptance, while one reviewer maintained strong reservations, arguing that the method should have been described in a simpler way. The authors acknowledged that a simpler presentation is possible but emphasized the importance of providing the full theoretical background, a position with which the area chair agrees.

Taking these points into account, the area chair recommends acceptance of the submission. The additional experimental results and clarifications provided in the rebuttal should be incorporated into the final version.
Decision: Accept (poster)