🤖 AI

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

Die Arbeit stellt Qrita vor, einen hochperformanten, deterministischen Top-k- und Top-p-Sampling-Algorithmus für große Vokabulare, der pivotbasierte Trunkierung und Selektion nutzt, um im Vergleich zu bestehenden GPU-Kernen eine bis zu 1,4-fache Steigerung des Durchsatzes und eine 50%ige Reduktion des Speicherverbrauchs zu erreichen, was zu seiner Übernahme als Standard-Sampler in vLLM führte.

Ursprüngliche Autoren: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

Veröffentlicht 2026-05-27

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Koch, der eine riesige Küche (ein Large Language Model) leitet, mit einer Speisekammer, die 100.000 verschiedene Zutaten (das Vokabular) enthält. Jedes Mal, wenn Sie ein Gericht zubereiten müssen (ein Wort generieren), müssen Sie die besten wenigen Zutaten aus dieser riesigen Speisekammer auswählen, um sicherzustellen, dass das Essen gut schmeckt, aber nicht langweilig ist.

In der Welt der KI wird dieser Auswahlprozess Top-k (Auswahl der besten k Zutaten) und Top-p (Auswahl der kleinsten Gruppe von Zutaten, die einen bestimmten „Geschmackswert" ergibt) genannt.

Das Problem: Die langsame, überfüllte Küche

Derzeit bewältigen die meisten Küchen dies, indem sie alle 100.000 Zutaten auf eine riesige Arbeitsfläche kippen, sie nach „Geschmackswert" vom besten zum schlechtesten sortieren und dann die besten herausgreifen.

Das Problem: Das Sortieren von 100.000 Artikeln ist langsam und chaotisch. Es beansprucht enorm viel Arbeitsflächenplatz (Speicher), und die Hände des Kochs werden müde (Rechen-Overhead).
Die Alternative: Einige Köche versuchen, einfach eine zufällige Handvoll Zutaten zu greifen, die vielleicht gut sind. Dies ist jedoch riskant; manchmal verpassen Sie die besten Zutaten, und manchmal schmeckt das Gericht jedes Mal anders, wenn Sie es zubereiten (nicht-deterministisch), was schlecht ist, wenn Sie ein Rezept exakt replizieren müssen.

Die Lösung: Qrita (Der intelligente Sous-Chef)

Die Arbeit stellt Qrita vor, eine neue, hochgeschwindigkeitsfähige Methode zum Auswählen von Zutaten. Betrachten Sie Qrita als einen superschlauen Sous-Chef, der zwei clevere Tricks anwendet, um das chaotische Sortieren vollständig zu umgehen.

Trick 1: Die „Gaussian Sigma-Truncation" (Der Rauschfilter)

Stellen Sie sich vor, in Ihrer 100.000-Zutaten-Speisekammer sind 99.000 davon nur „Rauschen" (wie Salz, Zucker und Mehl, die alle ungefähr den gleichen langweiligen Geschmack haben). Nur ein paar hundert sind die „Star-Zutaten" (wie Trüffel oder Safran).

Anstatt jedes einzelne Glas zu betrachten, führt Qrita einen schnellen Schnüffeltest durch. Es berechnet den durchschnittlichen Geschmack und die „Schärfe" (Standardabweichung) der Speisekammer. Dann zieht es eine Linie: „Alles unter dieser Linie ist nur Rauschen; wir müssen es nicht ansehen."

Das Ergebnis: Es wirft sofort 99 % der Speisekammer weg und lässt nur die etwa 200 interessanten Gläser übrig. Dies geschieht in einem einzigen, blitzschnellen Durchlauf.

Trick 2: Die „Quaternary Pivot Search" (Die Vier-Wege-Aufteilung)

Nun hat der Koch einen kleinen Stapel von 200 interessanten Zutaten. Er muss immer noch die exakten Top 50 finden.

Alter Weg: Einer nach dem anderen prüfen (zu langsam) oder den Stapel in zwei Hälften teilen (binäre Suche).
Qritas Weg: Anstatt den Stapel in zwei Hälften zu teilen, teilt Qrita ihn gleichzeitig in vier Abschnitte auf. Es fragt: „Ist die beste Zutat im ersten Viertel, zweiten, dritten oder vierten?"
Der Bonus: Es hat auch eine spezielle Regel für doppelte Zutaten. Wenn drei Gläser „Safran" exakt denselben Wert haben, weiß Qrita genau, wie viele davon zu behalten sind, um sicherzustellen, dass das Rezept jedes Mal identisch ist (deterministisch). Dies verhindert, dass der Koch in einer Endlosschleife stecken bleibt, während er versucht, zwischen identischen Gläsern zu entscheiden.

Warum dies wichtig ist (Die Ergebnisse)

Die Autoren haben Qrita mit einem spezialisierten Tool namens Triton (eine Sprache zum Programmieren von Grafikkarten/GPUs) entwickelt und gegen die derzeit besten Methoden getestet, die von großen KI-Engines wie vLLM und SGLang verwendet werden.

Geschwindigkeit: Qrita ist in realen Servierszenarien bis zu 1,4-mal schneller und in Rohgeschwindigkeitstests bis zu 2-mal schneller.
Speicher: Es verwendet die Hälfte des Speichers, da es nicht die gesamte sortierte Liste von 100.000 Artikeln speichern muss.
Genauigkeit: Im Gegensatz zu einigen schnellen Methoden, die raten, liefert Qrita exakt dasselbe Ergebnis wie die langsame, perfekte Sortiermethode. Es ändert nicht die Ausgabe; es findet sie nur viel schneller.

Das Fazit

Qrita ist wie der Upgrade von einem Koch, der jedes einzelne Gewürz der Welt manuell sortiert, zu einem intelligenten Assistenten, der sofort die langweiligen Dinge ignoriert, die interessanten Dinge gleichzeitig in vier Stapel aufteilt und Duplikate perfekt handhabt. Es macht die KI-Generierung schneller und effizienter, ohne die Qualität der Antworten zu verändern.

Hinweis: Die Arbeit erwähnt, dass Qrita nun die Standardmethode für den GPU-Pfad in vLLM, einem beliebten Tool zum Ausführen von KI-Modellen, ist, und der Code für andere verfügbar ist.

Technische Zusammenfassung: Qrita – Hochleistungs-Top-k und Top-p mittels pivotbasierter Trunkierung und Selektion

Problemstellung

Die effiziente Implementierung von Top-k- und Top-p-Sampling-Algorithmen für Large Language Models (LLMs) mit großen Vokabularen (oft über 100.000 Tokens) bleibt eine erhebliche Herausforderung auf GPUs. Bestehende Ansätze stehen vor einem Zielkonflikt zwischen Recheneffizienz und Korrektheit der Ausgabe:

Sortierungsbasierte Methoden: Von Engines wie vLLM verwendet, liefern sie exakte, deterministische Ergebnisse, verursachen jedoch hohe Rechen- und Speicherkosten durch Sortierungen des gesamten Vokabulars und gestreute Speicherzugriffe.
Stochastische Methoden: Bibliotheken wie FlashInfer und SGLang nutzen Rejection Sampling, um Sortierungen zu vermeiden und hohen Durchsatz zu bieten. Sie liefern jedoch nur ein einzelnes gesampeltes Token statt des vollständigen Kandidatensatzes, was sie für Aufgaben unbrauchbar macht, die deterministische Kandidatensätze erfordern, wie z. B. die Verifikation beim spekulativen Decoding und beim Reinforcement Learning.
Statistische Cutoff-Methoden: Ansätze wie Top-nσ und Min-p eliminieren Sortierungen durch die Verwendung statistischer Schwellenwerte (z. B. Mittelwert und Standardabweichung). Obwohl sie effizient sind, verändern sie die Sampling-Verteilung und die Ausgabe, was zu Debatten über die Qualität und Kohärenz der Generierung führt.

Es besteht eine kritische Lücke für einen Algorithmus, der Speichereffizienz und striktes deterministisches Verhalten (Rückgabe des vollständigen Kandidatensatzes) liefert, ohne die exakte Semantik von Top-k und Top-p zu beeinträchtigen.

Methodik

Die Autoren schlagen Qrita vor, einen hochperformanten Top-k- und Top-p-Algorithmus für GPUs, der auf pivotbasierter Trunkierung und Selektion beruht. Qrita erweitert die pivotbasierte Strategie von RTop-k (ursprünglich für Graph Neural Networks entwickelt), um große LLM-Vokabulare zu handhaben und dabei Determinismus zu gewährleisten. Die Methode stützt sich auf zwei Schlüsseltechniken:

1. Gausssche $\sigma$ -Trunkierung

In Anerkennung der Tatsache, dass LLM-Logits typischerweise einer quasi-gaußschen Verteilung folgen, bei der hochwahrscheinliche Tokens als Ausreißer gegen einen „rauschenden" Hintergrund auftreten, führt Qrita einen Vorfilter-Schritt durch.

Mechanismus: Der Algorithmus approximiert die Logit-Verteilung als $Z \sim \mathcal{N}(\mu, \sigma^2)$ . Er berechnet den Mittelwert ( $\mu$ ) und die Standardabweichung ( $\sigma$ ) aus einem Sample-Block und berechnet einen Trunkierungsschwellenwert $t = \mu + \delta \cdot \sigma$ .
Nachschlagetabellen: Der Koeffizient $\delta$ wird über vorcomputierte Nachschlagetabellen bestimmt, die aus der Normalquantilfunktion abgeleitet sind und auf die Zielwerte $k$ oder $p$ zugeschnitten sind.
Ergebnis: Dieser Schritt trunkiert den massiven „Rausch"-Bereich des Vokabulars in einem einzigen Durchlauf. Wenn die Größe des getrunkenen Satzes $|Z_t|$ das Ziel $k$ überschreitet (ein „Trunkierungstreffer"), wird die Suche nur auf dieser kleineren Teilmenge fortgesetzt. Andernfalls wird auf den vollständigen Logit-Satz zurückgegriffen. Dies reduziert den Suchraum für die nachfolgende pivotbasierte Suche erheblich.

2. Quaternäre Pivot-Suche mit Duplikatsbehandlung

Um den exakten Pivot-Wert $\tau$ (bei dem genau $k$ Elemente $\ge \tau$ sind) effizient und deterministisch zu finden:

Quaternäre Suche: Anstelle einer binären Suche evaluiert Qrita in jedem Iterationsschritt drei Pivots (bei den 25., 50. und 75. Perzentilen des aktuellen Suchbereichs). Dies reduziert die Anzahl der Suchiterationen im Vergleich zur binären Suche um die Hälfte.
Duplikatsbehandlung: Standard-Pivot-Suchen können versagen oder nicht-deterministisch werden, wenn duplizierte Logit-Werte existieren (häufig bei niedriger Präzision oder langschwänzigen Verteilungen). Qrita verfolgt den minimalen Logit-Wert, der größer als der Pivot ist ( $z_{mn}$ ), und dessen Vorkommensanzahl ( $N_{zmn}$ ).
Abbruchbedingung: Die Suche endet, wenn ein Pivot $\tau_n$ gefunden wird, bei dem die Anzahl der Elemente, die strikt größer als $\tau_n$ sind, kleiner als $k$ ist, die Anzahl der Elemente, die größer oder gleich dem minimalen Duplikatwert $z_{mn}$ sind, jedoch größer oder gleich $k$ ist. Dies ermöglicht dem Algorithmus, genau zu bestimmen, wie viele Duplikateinstanzen des Grenzwerts beibehalten werden müssen, um die Top-k-Bedingung zu erfüllen, und stellt reproduzierbare, deterministische Ausgaben sicher.

Implementierungsdetails

Framework: Implementiert mit Triton, einer GPU-Programmiersprache.
Autotuning: Anwendung einer „Tiered Triton Block Size Autotune"-Strategie. Da die Vektorgröße zwischen dem vollständigen Logit-Satz und dem getrunkenen Satz stark variiert, darf der Compiler optimale Blockgrößen auswählen (z. B. größere Blöcke für vollständige Sätze, kleinere für getrunken Sätze), um die Hardwareauslastung zu maximieren.
Pipeline: Der Algorithmus verarbeitet Batches parallel, wendet eine gaußsche Trunkierung an, gefolgt von der quaternären Suche, und generiert schließlich eine Duplikatsbehandlungsmaske, um die endgültige Ausgabe zu produzieren.

Hauptbeiträge

Deterministisches Hochleistungssampling: Qrita liefert den vollständigen Top-k/Top-p-Kandidatensatz (im Gegensatz zu FlashInfer/SGLang) und bewahrt gleichzeitig die exakte Semantik sortierungsbasierter Algorithmen, was ihn für spekulatives Decoding und RL geeignet macht.
Reduktion des Suchraums: Durch die Ausnutzung der statistischen Eigenschaften von Logits reduziert die gaußsche $\sigma$ -Trunkierung den Suchraum drastisch und vermeidet Sortierungen des gesamten Vokabulars.
Robuste Pivot-Suche: Die Einführung der quaternären Suche in Kombination mit einer expliziten Duplikatsbehandlung garantiert deterministisches Verhalten und reduziert die Iterationsanzahl, wodurch die Ineffizienzen standardmäßiger pivotbasierter Methoden bei großen Vokabularen adressiert werden.
Integration: Qrita ist als standardmäßiger Top-k- und Top-p-Sampler für den GPU-Ausführungspfad von vLLM implementiert.

Ergebnisse

Die Autoren bewerteten Qrita gegen Baselines, darunter naive PyTorch-Sortierung, den Standard-Sampler von vLLM, FlashInfer und SGLang, auf NVIDIA H100, RTX4090 und AMD MI355X GPUs unter Verwendung verschiedener Modelle (Llama, Qwen, GPT-OSS, Gemma).

Durchsatz: Qrita erzielt auf H100 eine End-to-End-Serving-Durchsatzverbesserung von bis zu 1,4 $\times$ gegenüber der vLLM-Baseline, wobei einige Konfigurationen auf der RTX4090 Verbesserungen von bis zu 2 $\times$ zeigen. Es übertrifft sortierungsbasierte Baselines signifikant, während es die Ausgabe sortierungsbasierter Algorithmen erreicht.
Speichernutzung: Qrita reduziert den Speicherverbrauch um etwa 50% im Vergleich zu sortierungsbasierten Methoden, hauptsächlich durch die Vermeidung der Zuweisung großer Zwischenspeicherpuffer, die für Sortierungen erforderlich sind.
Ablationsstudien:
- Gaußsche Trunkierung: Bietet die größte Beschleunigung und reduziert die Latenz um ca. 74% im Vergleich zur Suche im vollständigen Logit-Satz.
- Quaternäre Suche: Obwohl sie in Fällen mit „Trunkierungstreffer" aufgrund des reduzierten Suchraums etwas langsamer ist als die binäre Suche, bietet sie eine signifikante Latenzreduktion (ca. 2,3 ms) in Fallback-Fällen, bei denen das gesamte Vokabular durchsucht werden muss.
- Duplikatsbehandlung: Fügt nur einen minimalen Overhead hinzu (ca. 3,5% Latenzerhöhung), ist jedoch entscheidend für Korrektheit und Determinismus.
- Autotuning: Reduziert die Ausführungslatenz um fast 30% im Vergleich zur Verwendung einer einzigen festen Blockgröße.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass Qrita die Lücke zwischen Speichereffizienz und striktem deterministischem Verhalten für das Decoding mit großen Vokabularen schließt. Sie führt aus, dass Qrita durch die Vermeidung von Sortierungen des gesamten Vokabulars und die Nutzung pivotbasierter Selektion mit statistischem Vorfiltern eine hochperformante Lösung für das LLM-Decoding bietet, die mit fortgeschrittenen Aufgaben kompatibel ist, die vollständige Kandidatensätze erfordern (z. B. spekulatives Decoding). Die Autoren positionieren Qrita nicht als Ersatz für die statistische Semantik von Top-k/Top-p, sondern als eine effiziente Implementierung, die diese exakt bewahrt, im Gegensatz zu heuristischen statistischen Cutoff-Methoden oder stochastischen Single-Token-Samplern. Die Integration in vLLM als Standard-Sampler unterstreicht ihren praktischen Nutzen in Produktionsumgebungen.