🤖 machine learning

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

Dieser Beitrag stellt Feather vor, einen auf Reinforcement Learning basierenden, prefixbewussten Scheduler, der den Trade-off zwischen Batch-Größe und Prefix-Homogenität mithilfe eines leichtgewichtigen Chunked Hash Tree optimiert und damit im Vergleich zu bestehenden State-of-the-Art-Schedulern eine 2- bis 10-fach höhere LLM-Inferenz-Durchsatzrate durch Reduzierung des KV-Cache-Zugriffs-Overheads erreicht.

Ursprüngliche Autoren: Saksham Rathi, Preeti, Mythili Vutukuru

Veröffentlicht 2026-05-08

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Saksham Rathi, Preeti, Mythili Vutukuru

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 betreiben eine sehr belebte, hochgeschwindigkeitsfähige Bibliothek, in der eine einzelne Bibliotheksangestellte (die GPU) versucht, Tausende von Fragen verschiedener Personen (Anfragen) gleichzeitig zu beantworten.

In der Welt der Large Language Models (LLMs) muss die Bibliotheksangestellte für jedes einzelne Wort, das sie generiert, ein massives Buch mit „Kontext" (den Key-Value-Cache) lesen. Die Arbeit besagt, dass die derzeitige Art und Weise, diese Fragen zu organisieren, ineffizient ist, da sie sich zu sehr darauf konzentriert, wie viele Fragen die Bibliotheksangestellte gleichzeitig beantwortet, anstatt darauf, wie ähnlich diese Fragen sind.

Hier ist die Geschichte ihrer Lösung, Feather, aufgeschlüsselt in einfache Konzepte:

1. Das Problem: Der „überfüllte Bus" versus die „Familiengruppe"

Derzeit versuchen die meisten Systeme, so viele Personen wie möglich in einen Bus (einen „Batch") zu packen, um die Fahrt effizient zu gestalten. Sie verwenden eine „Wer zuerst kommt, mahlt zuerst"-Regel.

Das Problem: Wenn Sie 500 Fremde in einen Bus setzen, wollen alle 500 an 500 verschiedene Orte. Der Fahrer muss an 500 verschiedenen Haltestellen halten und ständig die Richtung wechseln. Das ist chaotisch und langsam.
Die Entdeckung: Die Autoren stellten fest, dass, wenn Sie eine kleinere Gruppe von 100 Personen nehmen, die alle auf derselben Straße wohnen (einen gemeinsamen „Präfix" teilen), der Fahrer die Straße geradeaus entlangfahren kann, ohne anzuhalten. Obwohl der Bus nicht voll ist, ist die Fahrt viel schneller, weil der Fahrer nicht ständig das Lenkrad drehen muss.

Die zentrale Erkenntnis: Es ist besser, eine kleinere Gruppe von Personen zu haben, die zum selben Ort gehen, als eine riesige Gruppe von Personen, die zu verschiedenen Orten gehen. Dies wird als Präfix-Homogenität bezeichnet.

2. Der alte Weg: Der „Baumkletterer"

Bestehende Systeme (wie SGLang) versuchen, diese Gruppen zu finden, indem sie einen riesigen, komplexen Stammbaum (einen Radix-Baum) durchsuchen, um zu sehen, wer dieselben Vorfahren teilt.

Das Problem: Das Klettern auf diesem Baum, um Übereinstimmungen zu finden, kostet viel Zeit und Energie im „Gehirn" des Computers (der CPU). Tatsächlich war die Zeit, die für das Klettern auf dem Baum aufgewendet wurde, manchmal fast so lang wie die Zeit, die die Bibliotheksangestellte tatsächlich für das Beantworten der Fragen benötigte! Es war, als würde man 10 Minuten damit verbringen, die Fahrgäste zu organisieren, nur um dann 10 Minuten zu fahren.

3. Die Lösung: „Feather"

Die Autoren entwickelten einen neuen Scheduler namens Feather, der beide Probleme löst.

Teil A: Der „Chunked Hash Tree" (CHT) – Die intelligente Checkliste

Anstatt den riesigen Stammbaum zu erklimmen, verwendet Feather einen cleveren Abkürzungsweg.

Die Analogie: Stellen Sie sich vor, anstatt jeden einzelnen Buchstaben des Namens einer Person zu überprüfen, prüfen Sie nur die ersten paar „Chunks" ihrer Adresse.
Wie es funktioniert: Feather teilt den langen Text in kleine Blöcke (Chunks) auf und gibt jedem Block einen einzigartigen „Fingerabdruck" (einen Hash). Es führt eine einfache Liste darüber, welche Fingerabdrücke derzeit verwendet werden.
Der Vorteil: Es kann sofort erkennen: „Ah, diese neue Anfrage hat dieselben Fingerabdrücke wie die Gruppe, die bereits im Bus ist." Es macht dies so schnell, dass das „CPU-Gehirn" kaum ins Schwitzen gerät. Es ist wie die Verwendung eines Barcode-Scanners anstatt eines ganzen Buches zu lesen, um ein Ticket zu überprüfen.

Teil B: Das „Reinforcement Learning" (RL) – Der intelligente Disponent

Feather findet nicht nur ähnliche Gruppen; es lernt wann es aufhören soll, Personen zum Bus hinzuzufügen.

Das Dilemma: Wenn Sie weiterhin Personen zum Bus hinzufügen, müssen Sie möglicherweise irgendwann jemanden hinzufügen, der auf einer anderen Straße wohnt. Wenn Sie ihn hinzufügen, wird die gesamte Gruppe unübersichtlich, und die Geschwindigkeit sinkt.
Das Lernen: Feather agiert wie ein intelligenter Disponent, der durch Versuch und Irrtum gelernt hat: „Wenn ich noch eine Person hinzufüge, könnten wir unsere Geschwindigkeit verlieren. Lassen Sie uns diesen Bus jetzt senden, solange er noch schnell ist, und auf die nächste Gruppe warten."
Das Ergebnis: Es entscheidet dynamisch den perfekten Moment, um den Batch zu starten, und balanciert dabei zwischen einem vollen Bus und dem Erhalt der Tatsache, dass sich alle auf derselben Straße befinden.

4. Die Ergebnisse: Die Bibliothek beschleunigen

Als die Autoren Feather testeten:

Geschwindigkeit: Es machte das System 2- bis 10-mal schneller als die derzeit besten Methoden, wenn Personen ähnliche Fragen stellten.
Sicherheit: Wenn die Fragen alle völlig unterschiedlich waren (keine gemeinsamen Straßen), geriet Feather nicht in Verwirrung; es funktionierte einfach genauso gut wie die alten Methoden.
Effizienz: Es reduzierte die „Staus" im Arbeitsspeicher des Computers, was bedeutete, dass die Bibliotheksangestellte nicht mehr so oft hin und her laufen musste, um die Buchseiten zu holen.

Zusammenfassung

Feather ist eine neue Art, AI-Anfragen zu organisieren. Anstatt so viele Anfragen wie möglich in einen einzigen Batch zu stopfen, gruppiert es ähnliche Anfragen zusammen (wie eine Familie, die zum selben Ziel geht) und verwendet eine superschnelle, energiearme Methode, um diese Gruppen zu finden. Es lernt genau, wann es aufhören soll, Personen zur Gruppe hinzuzufügen, um die Fahrt smooth und schnell zu halten.

Die Arbeit behauptet, dass dieser Ansatz die Antwortzeiten von KI erheblich beschleunigt, ohne dass teure neue Hardware benötigt wird, sondern einfach durch intelligentere Organisation des „Verkehrs".

Technische Zusammenfassung: Requests of a Feather Must Flock Together

Problemstellung

Die Inferenz von Large Language Models (LLM) ist während der auto-regressiven Dekodierungsphase grundlegend durch den Speicherbandbreitenbedarf begrenzt. Für jedes generierte Token muss auf den Key-Value (KV)-Cache aller vorherigen Token zugegriffen werden, was für jeden Schritt eine vollständige Durchsuchung des KV-Caches im GPU-Speicher erfordert. Während sich frühere Arbeiten darauf konzentrierten, die Batch-Größe zu maximieren, um die GPU-Auslastung zu verbessern, identifiziert diese Arbeit einen kritischen, übersehenen Zielkonflikt: Prefix-Homogenität.

In realen Workloads (z. B. Few-Shot-Prompting, System-Prompts, RAG) teilen Anfragen oft signifikante Präfixe. Bestehende Inferenz-Engines (wie vLLM und SGLang) nutzen Radix-Bäume oder Hash-Strukturen, um diese gemeinsamen Präfixe zu erkennen und KV-Caches wiederzuverwenden, primär um den Speicherbedarf zu reduzieren. Aktuelle Scheduler priorisieren jedoch die Maximierung der Batch-Größe oder die Minimierung von Speicherverdrängungen, ohne die Auswirkungen von Prefix-Heterogenität auf Speicherzugriffsmuster zu berücksichtigen.

Die Autoren zeigen, dass heterogene Batches (Anfragen mit unterschiedlichen Präfixen) die räumliche und zeitliche Lokalität bei GPU-DRAM-Zugriffen stören, was zu einer schlechten Bandbreitennutzung und reduzierter Durchsatzleistung führt. Im Gegensatz dazu ermöglichen prefix-homogene Batches (bei denen alle Anfragen ein gemeinsames Präfix teilen) eine effiziente Hardware-Vorabladung und Cache-Wiederverwendung. Die Arbeit argumentiert, dass bestehende Scheduler nicht erkennen, dass ein moderat kleiner, homogener Batch einen größeren, heterogenen übertreffen kann. Darüber hinaus verursachen die Mechanismen zur Erkennung von Präfix-Teilung (z. B. Radix-Baum-Durchläufe) prohibitiven CPU-Overhead, der oft mit der GPU-Ausführungszeit vergleichbar ist oder diese übersteigt.

Methodik

Die Arbeit stellt Feather vor, einen prefix-bewussten Scheduler, der den Zielkonflikt zwischen Batch-Größe und Prefix-Homogenität optimiert. Feather integriert zwei Hauptkomponenten:

1. Chunked Hash Tree (CHT)

Um den hohen CPU-Overhead traditioneller Radix-Baum-Durchläufe zu adressieren, verwendet Feather eine leichte Datenstruktur namens Chunked Hash Tree.

Mechanismus: Anstatt Token-für-Token-Vergleiche durchzuführen, werden Anfragen als Vektoren kumulativer Hashes über feste Token-Chunks dargestellt.
Effizienz: Der CHT verwaltet einen „Working Set" von Hashes für den aktiven Batch und einen Min-Heap wartender Anfragen, sortiert nach ihrer „Missing Count" (Anzahl der Chunks, die noch nicht vom aktiven Batch abgedeckt sind).
Komplexität: Dies ermöglicht dem Scheduler, den besten Kandidaten für die Hinzufügung zu einem Batch in $O(\log W)$ Zeit zu identifizieren (wobei $W$ die Anzahl der wartenden Anfragen ist), was eine signifikante Verbesserung gegenüber der $O(W \times T)$ - oder $O(E)$ -Komplexität von Tiefensuche-Radix-Baum-Durchläufen darstellt.
Operationen: Der CHT unterstützt effizientes Einfügen, Finden der besten Anfrage, Hinzufügen einer Anfrage zum aktiven Batch und Entfernen abgeschlossener Anfragen unter Verwendung von verzögerten Heap-Aktualisierungen und inkrementeller Spitzenwartung, um Overhead zu minimieren.

2. Reinforcement Learning (RL) Batching Policy

Feather verwendet eine RL-basierte Policy, um den optimalen Stoppzeitpunkt für die Batch-Bildung zu bestimmen.

Der Zielkonflikt: Das Hinzufügen weiterer Anfragen erhöht die GPU-Auslastung (größere Batch-Größe), kann jedoch die Prefix-Homogenität verwässern (reduzierte Speicherlokalität).
Zustand & Aktion: Der Scheduler beobachtet die aktuelle Batch-Größe, den Verlust an gemeinsamer Präfix-Tiefe ( $\Delta$ ) und die Anzahl der wartenden Anfragen, die die neue Präfix-Tiefe teilen ( $w$ ). Er entscheidet, ob eine weitere Anfrage hinzugefügt oder der Batch gestoppt und ausgeliefert wird.
Policies: Die Autoren evaluieren drei Policies: einen statischen Heuristik-Ansatz, einen Contextual Bandit (UCB) und Q-Learning. Das Ziel ist die Maximierung der Belohnung, definiert als Dekodierungs-Durchsatz.
Anpassungsfähigkeit: Die RL-Policy lernt, Batches zu bilden, die „genau richtig" sind – groß genug, um die GPU auszulasten, aber homogen genug, um die Speicherlokalität zu maximieren. Sie passt sich dynamisch der Workload-Intensität und Mustern der Präfix-Teilung an.

Hauptbeiträge

Identifikation eines kritischen Zielkonflikts: Die Arbeit stellt fest, dass Prefix-Homogenität ein stärkerer Bestimmungsfaktor für den Dekodierungs-Durchsatz ist als die Batch-Größe allein. Sie zeigt, dass bereits eine einzelne abweichende Anfrage in einem Batch die Lokalität stören und den Durchsatz um fast das Zweifache reduzieren kann.
Quantifizierung des CPU-Overheads: Die Autoren offenbaren, dass state-of-the-art Mechanismen zur Präfix-Erkennung (wie Radix-Baum-Durchläufe in SGLang) CPU-Overheads verursachen, die 50–90 % der gesamten Latenz erreichen können, wodurch die Vorteile der Präfix-Wiederverwendung effektiv zunichte gemacht werden.
Feather Scheduler: Das Design und die Implementierung von Feather, das die CHT-Datenstruktur mit einer RL-basierten Batching-Policy integriert. Feather ist sowohl in vLLM als auch in SGLang integriert.
Hardware-Agnostizismus: Im Gegensatz zu prefix-bewussten Attention-Kernels, die eine spezifische Hardware-Optimierung erfordern, operiert Feather auf der Scheduling-Ebene, was ihn mit bestehenden Attention-Kernels und Hardware-Konfigurationen kompatibel macht.

Ergebnisse

Die Evaluierung wurde auf NVIDIA RTX 6000 Ada- und A100-GPUs mit Modellen wie Llama 3 8B, Qwen und LongChat 13B über diverse Workloads (L-Eval, LongBench) durchgeführt.

Durchsatzsteigerung: Feather erzielt im Vergleich zu bestehenden Schedulern (vLLMs FCFS, SGLangs LPM/DFS-W) in Workloads mit gemeinsamen Präfixen im Bereich von 1K bis 10K Tokens einen 2–10× höheren End-to-End-Durchsatz.
Präfix-Sensitivität: In Experimenten mit 800 Anfragen, aufgeteilt in 8 Präfix-Gruppen, ergab die Verarbeitung in 8 homogenen Batches mit jeweils 100 Anfragen einen fast doppelt so hohen Durchsatz wie die Verarbeitung in größeren, heterogenen Batches.
Overhead-Reduktion: Der CHT von Feather reduziert den Overhead der Präfix-Erkennung um bis zu 1000× im Vergleich zu DFS-basierten Ansätzen für lange Sequenzen. Der Scheduling-Overhead bleibt unter 1 % der GPU-Ausführungszeit, während Basisansätze die GPU-Ausführungszeit überschreiten können.
Robustheit: Feather schneidet bei Workloads ohne Präfix-Teilung gleich gut ab wie der Status quo (FCFS) und stellt sicher, dass es in nicht-geteilten Szenarien zu keiner Leistungsverschlechterung kommt.
Vergleich mit Kernels: Feather übertrifft oder gleicht spezialisierte prefix-bewusste Attention-Kernels (wie PAT) aus, obwohl der Kernel selbst nicht modifiziert wird, und beweist, dass Optimierungen auf Scheduling-Ebene ebenso effektiv sein können wie solche auf Kernel-Ebene.

Bedeutung

Die Arbeit behauptet, dass die Maximierung der Batch-Größe für ein effizientes LLM-Serving nicht mehr ausreicht. Die primäre Engpassstelle in modernen Dekodierungsphasen ist die Speicherbandbreite, die stark von der Zugriffslokalität beeinflusst wird. Durch die Verschiebung des Fokus von „Maximierung der Batch-Größe" zu „Optimierung der Prefix-Homogenität" ermöglicht Feather erhebliche Leistungssteigerungen ohne hardware-spezifische Kernel-Modifikationen.

Die Arbeit hebt hervor, dass die Kosten für das Finden gemeinsamer Präfixe (CPU-Overhead) ein versteckter Engpass in aktuellen Systemen war. Feather's leichter CHT und adaptive RL-Policy zeigen, dass es möglich ist, Rechenauslastung und Speicherlokalität dynamisch auszubalancieren, was zu erheblichen Verbesserungen sowohl im Durchsatz als auch in der Latenz für reale LLM-Inferenz-Workloads führt. Die Autoren planen, Feather durch Beitrag zu den vLLM- und SGLang-Repositories open-source zu machen.