🤖 AI

Qrita: High-performance Top-k and Top-p using Pivot-based Truncation and Selection

Het artikel introduceert Qrita, een hoogpresterend, deterministisch Top-k- en Top-p-samplingalgoritme voor grote vocabulaires dat pivotgebaseerde truncatie en selectie gebruikt om een doorvoerverbetering van tot 1,4x en een geheugenreductie van 50% te bereiken in vergelijking met bestaande GPU-kernels, wat leidde tot de adoptie ervan als de standaard-sampler in vLLM.

Oorspronkelijke auteurs: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

Gepubliceerd 2026-05-27

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een chef bent die een enorme keuken runt (een Large Language Model) met een voorraadkast die 100.000 verschillende ingrediënten bevat (de vocabulaire). Elke keer als je een gerecht moet bereiden (een woord genereren), moet je de beste paar ingrediënten uit die gigantische voorraadkast kiezen om ervoor te zorgen dat het eten lekker smaakt maar niet saai is.

In de wereld van AI heet dit kiesproces Top-k (de top k beste ingrediënten kiezen) en Top-p (de kleinste groep ingrediënten kiezen die samen een bepaalde "smaakscore" opleveren).

Het Probleem: De Trage, Rommelige Keuken

Momenteel hanteren de meeste keukens dit proces door alle 100.000 ingrediënten op een enorm aanrecht te dumpen, ze te sorteren op "smaakscore" van beste naar slechtste, en vervolgens de besten te pakken.

Het Probleem: Het sorteren van 100.000 items is traag en rommelig. Het neemt een enorme hoeveelheid aanrechtplek in (geheugen) en de handen van de chef raken moe (rekenoverhead).
Het Alternatief: Sommige chefs proberen gewoon een willekeurige handvol ingrediënten te grijpen die misschien goed zijn. Maar dit is riskant; soms mis je de beste ingrediënten, en soms valt het gerecht elke keer anders uit als je het kookt (niet-deterministisch), wat slecht is als je een recept exact wilt repliceren.

De Oplossing: Qrita (De Slimme Sous-chef)

Het artikel introduceert Qrita, een nieuwe, supersnelle methode voor het kiezen van ingrediënten. Denk aan Qrita als een super-slimme sous-chef die twee slimme trucs gebruikt om de rommelige sortering volledig over te slaan.

Truc 1: De "Gaussian Sigma-Truncation" (Het Ruisfilter)

Stel je voor dat in je voorraadkast met 100.000 ingrediënten, er 99.000 gewoon "ruis" zijn (zoals zout, suiker en bloem die allemaal ongeveer dezelfde saaie smaak hebben). Slechts een paar honderd zijn de "ster-ingrediënten" (zoals truffels of saffraan).

In plaats van naar elk potje te kijken, doet Qrita een snelle snuffeltest. Het berekent de gemiddelde smaak en de "scherpte" (standaardafwijking) van de voorraadkast. Het trekt vervolgens een lijn: "Alles onder deze lijn is gewoon ruis; daar hoeven we niet naar te kijken."

Het Resultaat: Het gooit direct 99% van de voorraadkast weg, waardoor er slechts zo'n 200 interessante potten overblijven. Dit gebeurt in één enkele, bliksemsnelle doorgang.

Truc 2: De "Quaternary Pivot Search" (De Vierdelige Verdeling)

Nu heeft de chef een kleine stapel van 200 interessante ingrediënten. Ze moeten nog steeds de exacte top 50 vinden.

Oude Manier: Eentje voor eentje controleren (te traag) of de stapel in tweeën splitsen (binair zoeken).
Qrita's Manier: In plaats van de stapel in tweeën te splitsen, splitst Qrita deze in vier secties tegelijk. Het vraagt: "Zit het beste ingrediënt in het eerste kwart, tweede, derde of vierde?"
De Bonus: Het heeft ook een speciale regel voor dubbele ingrediënten. Als drie potten "Saffraan" exact dezelfde score hebben, weet Qrita precies hoeveel er bewaard moeten worden om ervoor te zorgen dat het recept elke keer identiek is (deterministisch). Dit voorkomt dat de chef vast komt te zitten in een eindeloze lus terwijl het probeert te beslissen tussen identieke potten.

Waarom Dit Belangrijk Is (De Resultaten)

De auteurs hebben Qrita gebouwd met een gespecialiseerd hulpmiddel genaamd Triton (een taal voor het programmeren van grafische kaarten/GPU's) en het getest tegen de huidige beste methoden die worden gebruikt door grote AI-motoren zoals vLLM en SGLang.

Snelheid: Qrita is tot 1,4 keer sneller in real-world serveerscenario's en tot 2 keer sneller in ruwe snelheidstests.
Geheugen: Het gebruikt de helft minder geheugen omdat het niet de hele gesorteerde lijst van 100.000 items hoeft op te slaan.
Nauwkeurigheid: In tegenstelling tot sommige snelle methoden die gokken, geeft Qrita je exact hetzelfde resultaat als de trage, perfecte sorteermethode. Het verandert de output niet; het vindt het gewoon veel sneller.

De Conclusie

Qrita is als de overstap van een chef die elk specerij in de wereld handmatig sorteert, naar een slimme assistent die direct het saaie materiaal negeert, het interessante materiaal in één keer in vier stapels verdeelt en dubbele exemplaren perfect afhandelt. Het maakt AI-generatie sneller en efficiënter zonder de kwaliteit van de antwoorden te veranderen.

Opmerking: Het artikel vermeldt dat Qrita nu de standaardmethode is voor het GPU-pad in vLLM, een populair hulpmiddel voor het draaien van AI-modellen, en dat de code beschikbaar is voor anderen om te gebruiken.

Technische Samenvatting: Qrita - Hoogpresterende Top-k en Top-p met Pivot-gebaseerde Truncatie en Selectie

Probleemstelling

Een efficiënte implementatie van Top-k en Top-p sampling-algoritmen voor Large Language Models (LLM's) met grote vocabulaires (vaak meer dan 100.000 tokens) blijft een aanzienlijke uitdaging op GPU's. Bestaande benaderingen staan voor een afweging tussen computationele efficiëntie en output-correctheid:

Op sortering gebaseerde methoden: Gebruikt door engines zoals vLLM, bieden deze exacte, deterministische resultaten, maar brengen hoge computationele en geheugenoverhead met zich mee door sortering over het volledige vocabulaire en gestructureerde geheugentoegangen.
Stochastische methoden: Bibliotheken zoals FlashInfer en SGLang gebruiken rejection sampling om sortering te vermijden, wat een hoge doorvoer biedt. Ze retourneren echter slechts één gesamplede token in plaats van de volledige kandidaten-set, waardoor ze incompatibel zijn met taken die deterministische kandidaten-sets vereisen, zoals verificatie bij speculatieve decoding en versterkend leren.
Statistische cutoff-methoden: Benaderingen zoals Top-nσ en Min-p elimineren sortering door statistische drempels (bijv. gemiddelde en standaardafwijking) te gebruiken. Hoewel ze efficiënt zijn, veranderen ze de sampling-verdeling en de output, wat leidt tot debatten over de kwaliteit en coherentie van de generatie.

Er is een kritieke kloof voor een algoritme dat geheugenefficiëntie en strikt deterministisch gedrag (het retourneren van de volledige kandidaten-set) levert zonder de exacte semantiek van Top-k en Top-p op te offeren.

Methodologie

De auteurs stellen Qrita voor, een hoogpresterend Top-k en Top-p algoritme voor GPU's gebaseerd op pivot-gebaseerde truncatie en selectie. Qrita breidt de pivot-gebaseerde strategie van RTop-k (oorspronkelijk ontworpen voor Graph Neural Networks) uit om grote LLM-vocabulaires te hanteren, terwijl determinisme wordt gewaarborgd. De methode steunt op twee kerntechnieken:

1. Op Gaussische verdeling gebaseerde $\sigma$ -Truncatie

Omdat LLM-logits doorgaans een quasi-Gaussische verdeling volgen waarbij high-probability tokens uitbijters vormen tegen een "ruisende" achtergrond, past Qrita een pre-filterstap toe.

Mechanisme: Het algoritme benadert de logit-verdeling als $Z \sim \mathcal{N}(\mu, \sigma^2)$ . Het berekent het gemiddelde ( $\mu$ ) en de standaardafwijking ( $\sigma$ ) uit een sample-blok en berekent een truncatiedrempel $t = \mu + \delta \cdot \sigma$ .
Zoektabellen: De coëfficiënt $\delta$ wordt bepaald via vooraf berekende zoektabellen die zijn afgeleid van de normale kwantiel-functie, afgestemd op de gewenste $k$ - of $p$ -waarden.
Resultaat: Deze stap truncert het enorme "ruis"-gebied van het vocabulaire in één doorgang. Als de grootte van de getruncerde set $|Z_t|$ de doelwaarde $k$ overschrijdt (een "truncation hit"), gaat de zoektocht alleen door op dit kleinere subset. Zo niet, dan wordt er teruggevallen op de volledige logit-set. Dit reduceert de zoekruimte voor de daaropvolgende pivot-zoektocht aanzienlijk.

2. Quaternaire Pivot-zoektocht met Omgaan met Duplicaten

Om de exacte pivot-waarde $\tau$ (waarbij precies $k$ elementen $\ge \tau$ zijn) efficiënt en deterministisch te vinden:

Quaternaire Zoektocht: In plaats van een binaire zoektocht, evalueert Qrita drie pivots (op het 25e, 50e en 75e percentiel van het huidige zoekbereik) in elke iteratie. Dit reduceert het aantal zoekiteraties met de helft ten opzichte van een binaire zoektocht.
Omgaan met Duplicaten: Standaard pivot-zoektochten kunnen falen of niet-deterministisch worden wanneer dubbele logit-waarden voorkomen (wat vaak voorkomt bij lage precisie of langstaartverdelingen). Qrita houdt de minimum logit-waarde die groter is dan de pivot ( $z_{mn}$ ) en het aantal voorkomens ( $N_{zmn}$ ) bij.
Terminatievoorwaarde: De zoektocht stopt wanneer een pivot $\tau_n$ wordt gevonden waarbij het aantal elementen strikt groter dan $\tau_n$ kleiner is dan $k$ , maar het aantal elementen groter dan of gelijk aan de minimum-duplicaatwaarde $z_{mn}$ groter dan of gelijk aan $k$ is. Dit stelt het algoritme in staat om precies te bepalen hoeveel dubbele instanties van de grenswaarde bewaard moeten worden om aan de Top-k-beperking te voldoen, waardoor reproduceerbare, deterministische output wordt gewaarborgd.

Implementatiedetails

Framework: Geïmplementeerd met Triton, een GPU-programmeertaal.
Autotuning: Past een "Tiered Triton Block Size Autotune"-strategie toe. Omdat de vectorgrootte drastisch varieert tussen de volledige logit-set en de getruncerde set, mag de compiler optimale blokgroottes selecteren (bijv. grotere blokken voor volledige sets, kleinere voor getruncerde sets) om hardware-uitbuiting te maximaliseren.
Pijplijn: Het algoritme verwerkt batches parallel, past Gaussische truncatie toe, gevolgd door de quaternaire zoektocht, en tot slot het genereren van een duplicaat-behandelingsmasker om de uiteindelijke output te produceren.

Belangrijkste Bijdragen

Deterministische Hoogpresterende Sampling: Qrita levert de volledige Top-k/Top-p kandidaten-set (in tegenstelling tot FlashInfer/SGLang) terwijl het de exacte semantiek van op sortering gebaseerde algoritmen behoudt, waardoor het geschikt is voor speculatieve decoding en RL.
Reductie van Zoekruimte: Door gebruik te maken van de statistische eigenschappen van logits, reduceert de Gaussische $\sigma$ -truncatie de zoekruimte drastisch en vermijdt het sortering over het volledige vocabulaire.
Robuuste Pivot-zoektocht: De introductie van quaternaire zoektocht gecombineerd met expliciete omgang met duplicaten garandeert deterministisch gedrag en reduceert het aantal iteraties, waardoor de inefficiënties van standaard pivot-gebaseerde methoden op grote vocabulaires worden aangepakt.
Integratie: Qrita is geïmplementeerd als de standaard Top-k en Top-p sampler voor het GPU-uitvoeringspad van vLLM.

Resultaten

De auteurs hebben Qrita geëvalueerd tegenover baselines zoals naïeve PyTorch-sortering, de standaard sampler van vLLM, FlashInfer en SGLang op NVIDIA H100, RTX4090 en AMD MI355X GPU's met diverse modellen (Llama, Qwen, GPT-OSS, Gemma).

Doorvoer: Qrita bereikt tot 1,4 $\times$ verbetering in end-to-end serving doorvoer ten opzichte van de vLLM-baseline op H100, waarbij sommige configuraties tot 2 $\times$ verbetering tonen op RTX4090. Het presteert aanzienlijk beter dan op sortering gebaseerde baselines, terwijl het de output van op sortering gebaseerde algoritmen behoudt.
Geheugengebruik: Qrita vermindert het geheugengebruik met ongeveer 50% ten opzichte van op sortering gebaseerde methoden, voornamelijk door het vermijden van toewijzing van grote tussentijdse buffers die nodig zijn voor sortering.
Ablatiestudies:
- Gaussische Truncatie: Biedt de grootste snelheidswinst en vermindert de latentie met ~74% ten opzichte van het doorzoeken van de volledige logit-set.
- Quaternaire Zoektocht: Hoewel iets trager dan binaire zoektocht in gevallen van "truncation hit" door de verkleinde zoekruimte, biedt het een aanzienlijke reductie in latentie (~2,3 ms) in fallback-cases waarbij het volledige vocabulaire moet worden doorzocht.
- Omgaan met Duplicaten: Voegt minimale overhead toe (~3,5% toename in latentie), maar is cruciaal voor correctheid en determinisme.
- Autotuning: Vermindert de uitvoeringslatentie met bijna 30% ten opzichte van het gebruik van één vaste blokgrootte.

Betekenis en Claims

Het artikel beweert dat Qrita de kloof overbrugt tussen geheugenefficiëntie en strikt deterministisch gedrag voor decoding met grote vocabulaires. Het stelt dat Qrita door het vermijden van sortering over het volledige vocabulaire en het benutten van pivot-gebaseerde selectie met statistische pre-filtering, een hoogpresterende oplossing biedt voor LLM-decoding die compatibel is met geavanceerde taken die volledige kandidaten-sets vereisen (bijv. speculatieve decoding). De auteurs positioneren Qrita niet als een vervanging voor de statistische semantiek van Top-k/Top-p, maar als een efficiënte implementatie die deze exact behoudt, in tegenstelling tot heuristische statistische cutoff-methoden of stochastische single-token samplers. De integratie in vLLM als standaard sampler onderstreept de praktische bruikbaarheid in productieomgevingen.