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

Technische Samenvatting: Top-H Decoding

Probleemstelling
Grote Taalmodellen (LLMs) staan voor een fundamentele uitdaging bij het genereren van open-ended tekst: het vinden van een balans tussen de concurrerende doelstellingen van het bevorderen van diversiteit en creativiteit enerzijds en het behoud van logische coherentie anderzijds. Bestaande afgeknipte steekproeftechnieken, zoals temperatuurschaalverdeling, top-k, top-p (nucleus) en min-p steekproeven, proberen deze afweging te beheersen, maar vertonen aanzienlijke beperkingen. Specifiek vertrouwen methoden zoals min-p op een enkel top-token als heuristiek voor modelvertrouwen. Deze aanpak houdt geen rekening met de algehele vorm van de waarschijnlijkheidsverdeling, wat leidt tot over-afknippen in schaarse (lage-entropie) verdelingen en onder-afknippen in dichte (hoge-entropie) verdelingen. Bijgevolg worstelen deze methoden vaak om coherentie te behouden bij hogere temperaturen waar creativiteit essentieel is.

Methodologie
Het artikel introduceert top-H decoding, een steekproefstrategie die is ontworpen om modelvertrouwen dynamisch te integreren door de volledige waarschijnlijkheidsverdeling te overwegen in plaats van slechts de piek. De methodologie is gebaseerd op een theoretisch kader dat de afweging tussen creativiteit en coherentie formaliseert als een optimalisatieprobleem.

1. Theoretische Grondslag (ECMD & ECMM):
   De auteurs formuleren het probleem als Entropie-Gedwongen Minimum Divergentie (ECMD), dat streeft naar het vinden van een subset van tokens $S$ die de Jensen-Shannon Divergentie (JSD) van de oorspronkelijke verdeling $p$ minimaliseert, terwijl een entropie-beperking $H(q) \leq \alpha H(p)$ wordt voldaan, waarbij $q$ de verdeling over $S$ is en $\alpha \in (0,1)$ een aanpasbare hyperparameter is.
   Het artikel bewijst dat het minimaliseren van JSD onder deze entropiegrens wiskundig equivalent is aan Entropie-Gedwongen Massa-Maximalisatie (ECMM): het maximaliseren van de som van de kansen van de geselecteerde tokens ($\Gamma_S = \sum_{i \in S} p_i$) onderworpen aan dezelfde entropie-beperking.

2. Complexiteitsanalyse:
   De auteurs bewijzen dat het ECMM-probleem NP-moeilijk is via een polynomiale tijdsreductie vanuit het Cardinality-Gedwongen Subset Sum (CCSS)-probleem. Dit vestigt dat het vinden van de exacte optimale subset in het algemene geval computationeel onuitvoerbaar is.

3. Algoritme (Top-H):
   Om de NP-moeilijkheid aan te pakken, stelt het artikel top-H voor, een computationeel efficiënt gulzig algoritme.

   • Procedure: Het algoritme sorteert tokens op dalende waarschijnlijkheid en voegt ze iteratief toe aan de selectieset $S$. Na elke toevoeging berekent het de entropie van de genormaliseerde verdeling $q$ over $S$.
   • Beëindiging: Het proces stopt wanneer het toevoegen van het volgende token zou leiden tot een entropie $H(q)$ die de dynamische drempel $\alpha H(p)$ overschrijdt.
   • Dynamische Aanpassing: In tegenstelling tot statische drempelmethoden past top-H zich aan het variërende vertrouwen van het model aan bij elke generatiestap. Naarmate de entropie van de oorspronkelijke verdeling $H(p)$ verandert, schaalt het toegestane entropie-budget voor de geselecteerde subset dienovereenkomstig.

Belangrijkste Bijdragen

• Theoretische Formulering: Het artikel vestigt een theoretische basis voor entropie-gebaseerd afknippen door het ECMD-probleem te definiëren en de equivalentie ervan met het NP-moeilijke ECMM-probleem te bewijzen.
• Nieuw Algoritme: Het presenteert top-H, een gulzig benaderingsalgoritme dat het ECMM-probleem efficiënt oplost ($O(n \log n)$ complexiteit, gedomineerd door sorteren) terwijl het de entropie van de geselecteerde verdeling strikt begrenst.
• Verdelingsbewustzijn: In tegenstelling tot min-p, dat uitsluitend vertrouwt op de waarschijnlijkheid van het top-1 token, maakt top-H gebruik van de volledige vorm van de verdeling om de grootte van de steekproefpool te bepalen, waardoor de beperkingen van heuristiek-gebaseerd afknippen in zowel schaarse als dichte verdelingen effectief worden aangepakt.

Experimentele Resultaten
Uitgebreide empirische evaluaties werden uitgevoerd over drie instructie-gefine-tuned modellen (LLaMA3.1-8B, Qwen2.5-3B, Phi-3-Mini) en meerdere benchmarks:

• Creatief Schrijven (Alpaca-Eval & MT-Bench): Top-H presteerde beter dan de state-of-the-art min-p steekproeven met tot 25,63% in win-rates en jury-scores. Cruciaal toonde top-H superieure robuustheid tegen temperatuurschaalverdeling; terwijl top-p en min-p aanzienlijke coherentiedegradatie leden bij hoge temperaturen (bijv. $T=2$), behield top-H stabiele prestaties.
• Redeneertaken (GSM8K & GPQA): Top-H behaalde consistent hogere nauwkeurigheid dan min-p en top-p over verschillende temperaturen. Bij $T=2$ toonde top-p een bijna totale ineenstorting in nauwkeurigheid (bijv. een daling van 73,62% voor Phi-3-Mini op GSM8K), terwijl top-H robuustheid behield, met tot 25,63% verbetering ten opzichte van min-p.
• LLM als Jury: Evaluaties met GPT-4o bevestigden dat top-H outputs produceert met hogere creativiteit, originaliteit en coherentie vergeleken met baselines, met name bij verhoogde temperaturen.
• Efficiëntie: De computationele overhead van top-H is verwaarloosbaar (ongeveer 0,8% toename in latentie vergeleken met min-p/top-p), aangezien de complexiteit wordt gedomineerd door de sorteerstap die gemeenschappelijk is voor alle cumulatieve decoding-methoden.

Betekenis en Claims
Het artikel claimt dat top-H de state-of-the-art in open-ended tekstgeneratie vooruitbrengt door een principiële, theoretisch onderbouwde methode te bieden om creativiteit en coherentie in evenwicht te brengen. Door expliciet de entropie van de steekproefverdeling te controleren ten opzichte van de onzekerheid van het model, stelt top-H LLMs in staat om diverse en creatieve inhoud te genereren zonder logische consistentie op te offeren, zelfs in hoge-temperatuurregimes waar traditionele methoden falen. De auteurs positioneren top-H als een directe vervanging voor bestaande steekproefstrategieën die eenvoudig kunnen worden geïntegreerd in toepassingen voor creatief schrijven en andere generatieve taken. De code is publiek beschikbaar gesteld om adoptie te vergemakkelijken.