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

Probleemstelling

Het genereren van hoogwaardige output van Large Language Models (LLMs) vereist vaak een sampling-strategie om het volgende token probabilistisch te kiezen. Bestaande methoden, zoals top-p (nucleus sampling), top-k, min-p, en ϵ-sampling, zijn effectief maar hebben een cruciaal nadeel: ze zijn afhankelijk van hyperparameters (zoals de truncatiedrempel $p$, $k$, of $\epsilon$).
De optimale waarden voor deze hyperparameters variëren sterk afhankelijk van de taak (bijv. wiskunde versus creatief schrijven) en de ingestelde temperatuur. Bij hoge temperaturen, die diversiteit bevorderen, falen veel bestaande methoden vaak omdat ze te veel tokens met lage waarschijnlijkheid toelaten, wat leidt tot tekstdegeneratie (onzin of hallucinaties). Er is behoefte aan een robuuste, hyperparameter-vrije methode die dynamisch kan aanpassen aan de entropie van de token-verdeling zonder handmatige tuning.

Methodologie: p-less Sampling

De auteurs introduceren p-less sampling, een op informatie-theorie gebaseerde aanpak die geen hyperparameters vereist. De kern van de methode is het dynamisch bepalen van een truncatiedrempel op basis van de volledige token-probabiliteitsverdeling.

Kernconcepten:

1. Definitie van de drempel: De drempel $L[P]$ wordt gedefinieerd als de waarschijnlijkheid van een "juiste gok" (correct random guess) gegeven de huidige voorspelde verdeling. Formeel is dit de som van de kwadraten van de token-probabiliteiten:
   $$L[P] = \sum_{v \in V} P_\theta(v | x_{1:t-1})^2$$
   Dit komt overeen met de verwachte kans dat een willekeurig getrokken token overeenkomt met het "ground truth" token, onder de aanname dat de modelvoorspelling de beste schatting is van de waarheid.

2. Selectieproces:

   • Bereken $L[P]$ voor de huidige verdeling.
   • Construeer een sampling-set $V_{p-less}$ die alleen tokens bevat waarvan de waarschijnlijkheid $P_\theta(v)$ groter dan of gelijk is aan $L[P]$.
   • Normaliseer de kansen binnen deze set en steek het volgende token.

3. Variatie (p-lessnorm): Er is ook een variant genaamd p-lessnorm die de drempel iets verlaagt door de kans op een incorrecte gok af te trekken. Dit maakt de methode iets minder streng en bevordert meer diversiteit, wat nuttig is voor creatieve taken.

4. Theoretische Grondslag:

   • Rényi Entropie: De drempel $L[P]$ is gerelateerd aan de Rényi-entropie van orde 2 (ook wel collision entropy). Omdat $L[P] = \exp(-H_2(p))$, neemt de drempel af naarmate de entropie (onzekerheid) toeneemt. Dit betekent dat bij hoge entropie automatisch meer tokens (inclusief de lange staart) worden toegelaten, terwijl bij lage entropie (hoge zekerheid) de set strakker wordt.
   • Statistische Momenten: $L[P]$ is een onbevooroordeelde schatter van het tweede moment van de kansdichtheidsfunctie, geschaald met de vocabulairegrootte.

Voordelen t.o.v. bestaande methoden:

• Dynamisch: Past zich per stap aan aan de volledige verdeling, in tegenstelling tot methoden die op een enkel token (min-p) of een vaste drempel (top-p) vertrouwen.
• Hyperparameter-vrij: Geen tuning nodig voor verschillende taken of temperaturen.
• Robuustheid: Garandeert een niet-lege kandidaatset en voorkomt degeneratie bij hoge temperaturen door de entropie van de verdeling te "reguleren".

Belangrijkste Bijdragen

1. Introductie van p-less: Een nieuwe, hyperparameter-vrije sampling-strategie gebaseerd op informatie-theorie.
2. Uitgebreide Validatie: Experimenten uitgevoerd op drie LLM's (Llama-2-7B, Mistral-7B, Llama-3-70B) over vijf datasets, variërend van wiskunde en logisch redeneren (GPQA, GSM8K, QASC, CSQA) tot creatief schrijven (Writing Prompts).
3. Efficiëntie: Aantonen dat p-less sneller is in inferentie (minder CPU-tijd en RAM) en kortere generaties produceert zonder in te boeten op nauwkeurigheid.
4. Analyse: Kwalitatieve en kwantitatieve analyses die laten zien dat p-less superieur presteert bij hoge temperaturen waar andere methoden falen.

Resultaten

De experimenten tonen overtuigende resultaten aan:

• Wiskunde en Logisch Redeneren:

  • p-less en p-lessnorm behalen consistent de hoogste of tweede hoogste AUC (Area Under Curve) over een breed temperatuurbereik (0.5 tot 2.0).
  • Terwijl methoden zoals top-p en min-p bij hoge temperaturen (bijv. 2.0) een drastische daling in nauwkeurigheid vertonen, blijft p-less robuust. Bijvoorbeeld, op het GSM8K-dataset met Llama-3-70B behaalde p-less een nauwkeurigheid van 93.2% bij temperatuur 2.0, terwijl top-p daalde tot 87.0% en andere methoden nog lager.
  • p-less presteert zelfs beter dan greedy decoding en beam search op sommige taken, zonder de complexiteit van beam search.

• Creatief Schrijven:

  • Op het Writing Prompts-dataset behaalde p-less de hoogste "length-controlled win rate" bij temperaturen boven de 1.0.
  • Menselijke evaluaties bevestigden dat annotatoren verhalen gegenereerd door p-less (bij temperatuur 2.0) verkiesten boven die van standaard sampling of andere methoden, voornamelijk vanwege betere coherentie en minder hallucinaties.

• Efficiëntie:

  • p-less is statistisch significant sneller dan min-p (ongeveer 22% snellere sampling per token).
  • Het vereist geen sorteren van de vocabulaire (complexiteit $O(|V|)$ in plaats van $O(|V| \log |V|)$) en heeft geen fallback-mechanisme nodig voor lege sets.
  • Het produceert kortere generaties bij vergelijkbare of betere nauwkeurigheid, wat wijst op minder "verbaal gedoe" (verbosity).

• Diversiteit:

  • Bij hoge temperaturen behoudt p-less een evenwicht tussen diversiteit en nauwkeurigheid. Andere methoden vertonen vaak een "diversiteitsspike" die ten koste gaat van de taak-specifieke prestaties (degeneratie). p-less volgt een meer gestructureerde toename in diversiteit.

Betekenis en Conclusie

Dit paper introduceert een fundamentele verschuiving in hoe we token-sampling benaderen. Door de truncatiedrempel te koppelen aan de entropie van de verdeling (via Rényi-entropie) in plaats van statische hyperparameters, biedt p-less een principiële, model-agnostische oplossing.

De betekenis ligt in drie gebieden:

1. Gebruiksgemak: Gebruikers hoeven geen hyperparameters meer te tunen voor verschillende taken of temperaturen.
2. Robuustheid: Het lost het probleem op van tekstdegeneratie bij hoge temperaturen, wat essentieel is voor creatieve toepassingen en diverse generaties.
3. Efficiëntie: Het verbetert de inferentie-snelheid en reduceert computerkosten, wat schaalbaarheid bevordert.

Kortom, p-less sampling bewijst dat het grondvesten van decoding op informatie-theorie leidt tot een methode die zowel intuïtief als empirisch superieur is aan de huidige state-of-the-art.