📊 statistics

Top-H Decoding: Adapting the Creativity and Coherence with Bounded Entropy in Text Generation

This paper introduces Top-H decoding, a novel sampling algorithm based on an entropy-constrained mass maximization framework that effectively balances creativity and coherence in large language models, outperforming state-of-the-art methods like min-p sampling on creative writing benchmarks while maintaining robustness in factual tasks.

Original authors: Erfan Baghaei Potraghloo, Seyedarmin Azizi, Souvik Kundu, Massoud Pedram

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Erfan Baghaei Potraghloo, Seyedarmin Azizi, Souvik Kundu, Massoud Pedram

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are asking a very smart, well-read robot to tell you a story. You want the story to be creative (full of surprising, wild ideas) but also coherent (making logical sense, not gibberish).

The problem is, when you tell the robot to "be creative," it often gets too excited. It starts picking words that are so unlikely that the story falls apart. This is the "Creativity vs. Coherence" struggle.

The Old Ways: The "Top-K" and "Top-P" Filters

Previously, researchers tried to fix this with simple filters:

Top-K: "Only pick from the top 50 most likely words." This is like a strict teacher who only lets you use a small, safe vocabulary. It's coherent, but boring.
Top-P (Nucleus): "Pick from the smallest group of words that adds up to 90% of the probability." This is a bit more flexible, but if the robot is unsure, it might accidentally include some very weird words just to fill the quota, ruining the story.
Min-P: A newer method that says, "If the robot is very confident about the best word, cut off the weird ones aggressively. If it's unsure, be more lenient." This works well, but it has a blind spot: it only looks at the single best word to decide how confident the robot is. It ignores the rest of the crowd.

The New Method: Top-H Decoding

The authors of this paper propose a new method called Top-H. Think of it as a Smart Traffic Controller for words.

Instead of just looking at the "fastest car" (the top word) to decide how much traffic to allow, Top-H looks at the entire traffic jam (the whole probability distribution).

Here is how it works, using a simple analogy:

The "Entropy" Meter (The Measure of Chaos)

Imagine the robot's brain is a room full of people shouting different words.

Low Entropy (Calm): Everyone is shouting the same thing, or just a few people are shouting loudly. The robot is very confident.
High Entropy (Chaos): Hundreds of people are shouting different things at once. The robot is confused and unsure.

Old methods (like Min-P) only check the volume of the loudest person to guess how chaotic the room is. If the loudest person is shouting loudly, Min-P assumes the room is calm and cuts off the others. But what if there are 50 other people shouting just a bit quieter? The room is actually chaotic!

Top-H measures the total noise level (entropy) of the whole room.

If the room is calm (low entropy), Top-H says, "Great, we know what we're doing. Let's only let the top few people speak." (High coherence).
If the room is chaotic (high entropy), Top-H says, "Whoa, there's a lot of uncertainty here. We need to let more people speak to keep the story interesting, but we must set a limit so it doesn't become a screaming match." (High creativity, but controlled).

The "Greedy" Algorithm

The paper proves that finding the perfect group of words to balance this is a mathematically impossible puzzle (called "NP-hard"). It's like trying to find the perfect combination of ingredients for a cake where you have a million options, but you can't test them all.

So, Top-H uses a Greedy Algorithm. Imagine you are building a tower of blocks.

You start with the biggest, most stable block (the most probable word).
You keep adding the next biggest block.
After every block, you check: "Is the tower getting too wobbly?" (Is the entropy too high?)
If the tower is still stable (within the "entropy budget"), you keep adding.
The moment adding one more block would make it wobble too much, you stop.

This ensures you get the most interesting words possible without the story collapsing into nonsense.

What the Paper Found

The authors tested this "Smart Traffic Controller" against the old methods on various tasks:

Creative Writing: Top-H wrote stories that were significantly more creative and coherent than the others, especially when the robot was told to "be wild" (high temperature settings).
Reasoning Tasks: It also did better at math and logic puzzles, proving it doesn't just make things up; it stays grounded.
Speed: It is almost as fast as the other methods, so it doesn't slow down the robot.

The Bottom Line

Top-H is a new way for AI to choose its words. Instead of guessing based on just the "best" option, it measures the overall "confidence" of the AI. If the AI is sure, it sticks to safe words. If the AI is exploring, it allows more variety but keeps a strict leash to prevent the story from falling apart. It's like having a creative director who knows exactly when to let the actors improvise and when to stick to the script.

Technical Summary: Top-H Decoding

Problem Statement
Large Language Models (LLMs) face a fundamental challenge in open-ended text generation: balancing the competing objectives of fostering diversity and creativity while preserving logical coherence. Existing truncated sampling techniques, such as temperature scaling, top-k, top-p (nucleus), and min-p sampling, attempt to manage this trade-off but exhibit significant limitations. Specifically, methods like min-p rely on a single top token as a heuristic for model confidence. This approach fails to account for the overall shape of the probability distribution, leading to over-truncation in sparse (low-entropy) distributions and under-truncation in dense (high-entropy) distributions. Consequently, these methods often struggle to maintain coherence at higher temperatures where creativity is essential.

Methodology
The paper introduces top-H decoding, a sampling strategy designed to dynamically incorporate model confidence by considering the entire probability distribution rather than just its peak. The methodology is grounded in a theoretical framework that formalizes the trade-off between creativity and coherence as an optimization problem.

Theoretical Foundation (ECMD & ECMM):
The authors formulate the problem as Entropy-Constrained Minimum Divergence (ECMD), which seeks to find a subset of tokens $S$ that minimizes the Jensen-Shannon Divergence (JSD) from the original distribution $p$ while satisfying an entropy constraint $H(q) \leq \alpha H(p)$ , where $q$ is the distribution over $S$ and $\alpha \in (0,1)$ is a tunable hyperparameter.
The paper proves that minimizing JSD under this entropy bound is mathematically equivalent to Entropy-Constrained Mass Maximization (ECMM): maximizing the sum of probabilities of the selected tokens ( $\Gamma_S = \sum_{i \in S} p_i$ ) subject to the same entropy constraint.
Complexity Analysis:
The authors prove that the ECMM problem is NP-hard via a polynomial-time reduction from the Cardinality-Constrained Subset Sum (CCSS) problem. This establishes that finding the exact optimal subset is computationally intractable in the general case.
Algorithm (Top-H):
To address the NP-hardness, the paper proposes top-H, a computationally efficient greedy algorithm.
- Procedure: The algorithm sorts tokens by descending probability and iteratively adds them to the selection set $S$ . After each addition, it calculates the entropy of the renormalized distribution $q$ over $S$ .
- Termination: The process stops when adding the next token would cause the entropy $H(q)$ to exceed the dynamic threshold $\alpha H(p)$ .
- Dynamic Adaptation: Unlike static threshold methods, top-H adapts to the model's varying confidence at each generation step. As the entropy of the original distribution $H(p)$ changes, the allowed entropy budget for the selected subset scales accordingly.

Key Contributions

Theoretical Formulation: The paper establishes a theoretical basis for entropy-based truncation by defining the ECMD problem and proving its equivalence to the NP-hard ECMM problem.
Novel Algorithm: It presents top-H, a greedy approximation algorithm that solves the ECMM problem efficiently ( $O(n \log n)$ complexity, dominated by sorting) while strictly bounding the entropy of the selected distribution.
Distribution Awareness: Unlike min-p, which relies solely on the top-1 token probability, top-H utilizes the full distribution shape to determine the sampling pool size, effectively addressing the limitations of heuristic-based truncation in both sparse and dense distributions.

Experimental Results
Extensive empirical evaluations were conducted across three instruction-tuned models (LLaMA3.1-8B, Qwen2.5-3B, Phi-3-Mini) and multiple benchmarks:

Creative Writing (Alpaca-Eval & MT-Bench): Top-H outperformed state-of-the-art min-p sampling by up to 25.63% in win rates and judge scores. Crucially, top-H demonstrated superior robustness to temperature scaling; while top-p and min-p suffered significant coherence degradation at high temperatures (e.g., $T=2$ ), top-H maintained stable performance.
Reasoning Tasks (GSM8K & GPQA): Top-H consistently achieved higher accuracy than min-p and top-p across various temperatures. At $T=2$ , top-p showed near-total collapse in accuracy (e.g., a 73.62% drop for Phi-3-Mini on GSM8K), whereas top-H maintained robustness, showing up to a 25.63% improvement over min-p.
LLM-as-a-Judge: Evaluations using GPT-4o confirmed that top-H produces outputs with higher creativity, originality, and coherence compared to baselines, particularly at elevated temperatures.
Efficiency: The computational overhead of top-H is negligible (approx. 0.8% increase in latency compared to min-p/top-p), as the complexity is dominated by the sorting step common to all cumulative decoding methods.

Significance and Claims
The paper claims that top-H advances the state-of-the-art in open-ended text generation by providing a principled, theoretically grounded method to balance creativity and coherence. By explicitly controlling the entropy of the sampling distribution relative to the model's uncertainty, top-H enables LLMs to generate diverse and creative content without sacrificing logical consistency, even in high-temperature regimes where traditional methods fail. The authors position top-H as a drop-in replacement for existing sampling strategies that can be easily integrated into creative writing applications and other generative tasks. The code is made publicly available to facilitate adoption.