🤖 machine learning

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

Dit artikel introduceert Feather, een op versterkingslering gebaseerde prefix-bewuste planner die de afweging tussen batchgrootte en prefix-homogeniteit optimaliseert met behulp van een lichtgewicht Chunked Hash Tree, en zo een 2–10× hogere doorvoer bij LLM-inferentie bereikt door de overhead van KV-cache-toegang te verminderen in vergelijking met bestaande state-of-the-art planners.

Oorspronkelijke auteurs: Saksham Rathi, Preeti, Mythili Vutukuru

Gepubliceerd 2026-05-08

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Saksham Rathi, Preeti, Mythili Vutukuru

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 zeer drukke, supersnelle bibliotheek runt waar een enkele bibliothecaris (de GPU) probeert om tegelijkertijd duizenden vragen van verschillende mensen (verzoeken) te beantwoorden.

In de wereld van Large Language Models (LLM's) moet de bibliothecaris voor elk woord dat hij genereert, een enorm boek met "context" (de Key-Value cache) lezen. Het artikel stelt dat de huidige manier waarop deze vragen worden georganiseerd, inefficiënt is omdat het te veel nadruk legt op hoeveel vragen de bibliothecaris tegelijk beantwoordt, in plaats van op hoe vergelijkbaar die vragen zijn.

Hier is het verhaal van hun oplossing, Feather, opgesplitst in eenvoudige concepten:

1. Het Probleem: De "Drukte Bus" versus de "Familiegroep"

Momenteel proberen de meeste systemen zo veel mogelijk mensen op een bus (een "batch") te proppen om de reis efficiënt te maken. Ze gebruiken een "Eerst komen, eerst bediend"-regel.

Het Probleem: Als je 500 vreemden op een bus zet, willen ze allemaal naar 500 verschillende bestemmingen. De chauffeur moet bij 500 verschillende haltes stoppen en voortdurend van richting veranderen. Dit is chaotisch en traag.
De Ontdekking: De auteurs ontdekten dat als je een kleinere groep van 100 mensen neemt die allemaal op dezelfde straat wonen (een "prefix" delen), de chauffeur rechtstreeks die straat af kan rijden zonder te stoppen. Hoewel de bus niet vol zit, is de reis veel sneller omdat de chauffeur niet blijft sturen.

Het Kerninzicht: Het is beter om een kleinere groep mensen te hebben die naar dezelfde plaats gaan dan een enorme groep mensen die naar verschillende plaatsen gaan. Dit heet Prefix Homogeniteit.

2. De Oude Manier: De "Boomklimmer"

Bestaande systemen (zoals SGLang) proberen deze groepen te vinden door te kijken naar een enorme, complexe stamboom (een Radix Tree) om te zien wie dezelfde voorouders deelt.

Het Probleem: Het beklimmen van deze boom om overeenkomsten te vinden kost veel tijd en energie aan het "brein" van de computer (de CPU). Sterker nog, de tijd die werd besteed aan het beklimmen van de boom was soms bijna net zo lang als de tijd die de bibliothecaris daadwerkelijk besteedde aan het beantwoorden van de vragen! Het was alsof je 10 minuten besteedde aan het organiseren van de passagiers om vervolgens slechts 10 minuten te rijden.

3. De Oplossing: "Feather"

De auteurs bouwden een nieuwe planner genaamd Feather die beide problemen oplost.

Deel A: De "Chunked Hash Tree" (CHT) – De Slimme Checklist

In plaats van de enorme stamboom te beklimmen, gebruikt Feather een slimme afkorting.

De Analogie: Stel je voor dat je in plaats van elke enkele letter van de naam van een persoon te controleren, je gewoon de eerste paar "stukken" (chunks) van hun adres controleert.
Hoe het werkt: Feather breekt de lange tekst op in kleine blokken (chunks) en geeft elk blok een unieke "vingerafdruk" (een hash). Het houdt een eenvoudige lijst bij van welke vingerafdrukken momenteel in gebruik zijn.
Het Voordeel: Het kan direct zien: "Oh, dit nieuwe verzoek heeft dezelfde vingerafdrukken als de groep die al in de bus zit." Het doet dit zo snel dat het "CPU-brein" amper zweet. Het is alsof je een barcode-scanner gebruikt in plaats van een heel boek te lezen om een kaartje te controleren.

Deel B: "Versterkend Leren" (RL) – De Slimme Disponent

Feather zoekt niet alleen naar vergelijkbare groepen; het leert wanneer te stoppen met het toevoegen van mensen aan de bus.

Het Dilemma: Als je blijft mensen aan de bus toevoegen, moet je uiteindelijk misschien iemand toevoegen die op een andere straat woont. Als je die toevoegt, wordt de hele groep rommelig en daalt de snelheid.
Het Leren: Feather fungeert als een slimme disponent die door middel van trial and error heeft geleerd: "Als ik nog één persoon toevoeg, verliezen we misschien onze snelheid. Laten we deze bus nu sturen terwijl hij nog snel is, en wachten op de volgende groep."
Het Resultaat: Het bepaalt dynamisch het perfecte moment om de batch te lanceren, en balanceert hierbij tussen een volle bus hebben en ervoor zorgen dat iedereen op dezelfde straat blijft.

4. De Resultaten: De Bibliotheek Versnellen

Toen de auteurs Feather testten:

Snelheid: Het maakte het systeem 2 tot 10 keer sneller dan de huidige beste methoden wanneer mensen vergelijkbare vragen stelden.
Veiligheid: Als de vragen allemaal totaal verschillend waren (geen gedeelde straten), raakte Feather niet in de war; het presteerde gewoon net zo goed als de oude methoden.
Efficiëntie: Het verminderde de "verkeersopstoppingen" in het geheugen van de computer, wat betekent dat de bibliothecaris niet zo vaak heen en weer hoefde te rennen om de boekpagina's op te halen.

Samenvatting

Feather is een nieuwe manier om AI-verzoeken te organiseren. In plaats van zo veel mogelijk verzoeken in één enkele batch te proppen, groepeert het vergelijkbare verzoeken samen (zoals een familie die naar dezelfde bestemming gaat) en gebruikt het een supersnelle, energiezuinige methode om die groepen te vinden. Het leert precies wanneer het stoppen moet met het toevoegen van mensen aan de groep om de reis soepel en snel te houden.

Het artikel beweert dat deze aanpak de responstijden van AI aanzienlijk versnelt zonder dure nieuwe hardware nodig te hebben, simpelweg door het "verkeer" slimmer te organiseren.

Technische Samenvatting: Requests of a Feather Must Flock Together

Probleemstelling

Inferentie met Large Language Models (LLM) is fundamenteel geheugenbeperkt tijdens de auto-regressieve decode-fase. Elke gegenereerde token vereist aandacht voor de Key-Value (KV) cache van alle voorgaande tokens, wat een volledige scan van de KV-cache in het GPU-geheugen voor elke stap noodzakelijk maakt. Hoewel eerder werk zich heeft gericht op het maximaliseren van de batchgrootte om GPU-gebruik te verbeteren, identificeert dit artikel een kritieke, over het hoofd geziene afweging: prefix-homogeniteit.

In real-world workloads (bijv. few-shot prompting, systeemprompts, RAG) delen verzoeken vaak aanzienlijke prefixes. Bestaande inferentie-engines (zoals vLLM en SGLang) gebruiken radiaxbomen of hash-structuren om deze gedeelde prefixes te detecteren en KV-caches te hergebruiken, voornamelijk om het geheugenvoetafdruk te verkleinen. Echter, huidige planners prioriteren het maximaliseren van de batchgrootte of het minimaliseren van geheugenverwijderingen zonder rekening te houden met de impact van prefix-heterogeniteit op geheugentoegangspatronen.

De auteurs tonen aan dat heterogene batches (bevat verzoeken met verschillende prefixes) ruimtelijke en temporele localiteit in GPU-DRAM-toegang verstoren, wat leidt tot een slechte bandbreedtebenutting en verminderde doorvoer. Daarentegen stellen prefix-homogene batches (waarbij alle verzoeken een gemeenschappelijke prefix delen) efficiënte hardware prefetching en cache-hergebruik in de hand. Het artikel betoogt dat bestaande planners niet onderkennen dat een matig kleine, homogene batch een grotere, heterogene batch kan overtreffen. Bovendien zijn de mechanismen die worden gebruikt om prefix-deling te detecteren (bijv. radiaxbomen-traversals) belast met prohibitieve CPU-overhead, vaak vergelijkbaar met of zelfs groter dan de GPU-uitvoeringstijd.

Methodologie

Het artikel introduceert Feather, een prefix-bewuste planner ontworpen om de afweging tussen batchgrootte en prefix-homogeniteit te optimaliseren. Feather integreert twee hoofdcomponenten:

1. Chunked Hash Tree (CHT)

Om de hoge CPU-overhead van traditionele radiaxbomen-traversals aan te pakken, maakt Feather gebruik van een lichtgewicht datastructuur genaamd de Chunked Hash Tree.

Mechanisme: In plaats van token-voor-token vergelijkingen, worden verzoeken weergegeven als vectoren van cumulatieve hashes over vaste token-chunks.
Efficiëntie: CHT onderhoudt een "working set" van hashes voor de actieve batch en een min-heap van wachtende verzoeken, gesorteerd op hun "missing count" (het aantal chunks dat nog niet wordt gedekt door de actieve batch).
Complexiteit: Dit stelt de planner in staat om het beste kandidaat-verzoek om aan een batch toe te voegen te identificeren in $O(\log W)$ tijd (waarbij $W$ het aantal wachtende verzoeken is), een aanzienlijke verbetering ten opzichte van de $O(W \times T)$ of $O(E)$ complexiteit van diepte-eerst radiaxbomen-traversals.
Operaties: CHT ondersteunt efficiënt invoegen, het vinden van het beste verzoek, het toevoegen van een verzoek aan de actieve batch en het verwijderen van voltooide verzoeken, met gebruikmaking van lazy heap-updates en incrementele tip-onderhoud om overhead te minimaliseren.

2. Reinforcement Learning (RL) Batching Policy

Feather gebruikt een op RL gebaseerd beleid om het optimale stoppunt voor batchvorming te bepalen.

De Afweging: Het toevoegen van meer verzoeken verhoogt het GPU-gebruik (grotere batchgrootte), maar kan de prefix-homogeniteit verdunnen (vermindering van geheugenlocaliteit).
State & Action: De planner observeert de huidige batchgrootte, het verlies in gedeelde prefixdiepte ( $\Delta$ ) en het aantal wachtende verzoeken dat de nieuwe prefixdiepte deelt ( $w$ ). Het besluit of er een ander verzoek moet worden Toegevoegd of dat er moet worden Gestopt en de batch moet worden verzonden.
Beleidslijnen: De auteurs evalueren drie beleidslijnen: een statische heuristiek, een Contextual Bandit (UCB) en Q-Learning. Het doel is het maximaliseren van de beloning, gedefinieerd als decode-doorvoer.
Aanpasbaarheid: Het RL-beleid leert batches te vormen die "precies goed" zijn: groot genoeg om de GPU te benutten, maar homogeen genoeg om geheugenlocaliteit te maximaliseren. Het past zich dynamisch aan aan workload-intensiteit en patronen van prefix-deling.

Belangrijkste Bijdragen

Identificatie van een Kritieke Afweging: Het artikel stelt vast dat prefix-homogeniteit een sterkere determinant is van decode-doorvoer dan batchgrootte alleen. Het toont aan dat zelfs één afwijkend verzoek in een batch de localiteit kan verstoren en de doorvoer met bijna 2x kan verminderen.
Kwantificering van CPU-Overhead: De auteurs onthullen dat state-of-the-art prefix-detectiemechanismen (zoals radiaxbomen-traversals in SGLang) CPU-overhead met zich meebrengen die 50–90% van de totale latentie kan bereiken, wat de voordelen van prefix-hergebruik effectief tenietdoet.
Feather Planner: Het ontwerp en de implementatie van Feather, dat de CHT-datastructuur integreert met een op RL gebaseerd batching-beleid. Feather is geïntegreerd in zowel vLLM als SGLang.
Hardware-onafhankelijkheid: In tegenstelling tot prefix-bewuste attention-kernels die specifieke hardware-tuning vereisen, werkt Feather op het planningsniveau, waardoor het compatibel is met bestaande attention-kernels en hardware-configuraties.

Resultaten

De evaluatie werd uitgevoerd op NVIDIA RTX 6000 Ada en A100 GPU's met modellen zoals Llama 3 8B, Qwen en LongChat 13B over diverse workloads (L-Eval, LongBench).

Doorvoerwinsten: Feather bereikt 2–10× hogere end-to-end doorvoer in vergelijking met bestaande planners (vLLM's FCFS, SGLang's LPM/DFS-W) in workloads met gedeelde prefixes variërend van 1K tot 10K tokens.
Prefix-gevoeligheid: In experimenten met 800 verzoeken verdeeld over 8 prefix-groepen, leverde het verwerken ervan in 8 homogene batches van 100 verzoeken bijna 2× hogere doorvoer op dan het verwerken ervan in grotere, heterogene batches.
Overheadreductie: De CHT van Feather verlaagt de prefix-detectie-overhead met tot 1000× in vergelijking met DFS-gebaseerde benaderingen voor lange sequenties. De plannings-overhead blijft onder de 1% van de GPU-uitvoeringstijd, terwijl baseline-benaderingen de GPU-uitvoeringstijd kunnen overschrijden.
Robuustheid: Feather presteert op gelijke voet met de status quo (FCFS) wanneer workloads geen prefix-deling vertonen, waardoor geen prestatiedegradatie optreedt in niet-gedeelde scenario's.
Vergelijking met Kernels: Feather presteert beter dan of gelijk aan gespecialiseerde prefix-bewuste attention-kernels (zoals PAT), ondanks dat de kernel zelf niet wordt gewijzigd, wat bewijst dat optimalisaties op planningsniveau even effectief kunnen zijn als die op kernel-niveau.

Betekenis

Het artikel beweert dat het maximaliseren van de batchgrootte niet langer voldoende is voor efficiënte LLM-serving. De primaire bottleneck in moderne decode-fases is geheugenbandbreedte, die sterk wordt beïnvloed door toeganglocaliteit. Door de focus te verschuiven van "maximaliseren van batchgrootte" naar "optimaliseren van prefix-homogeniteit", ontsluit Feather aanzienlijke prestatiewinsten zonder dat hardware-specifieke kernel-aanpassingen nodig zijn.

Het werk benadrukt dat de kosten van het vinden van gedeelde prefixes (CPU-overhead) een verborgen bottleneck in huidige systemen is geweest. De lichtgewicht CHT van Feather en het adaptieve RL-beleid tonen aan dat het mogelijk is om rekengebruik en geheugenlocaliteit dynamisch in evenwicht te brengen, wat leidt tot aanzienlijke verbeteringen in zowel doorvoer als latentie voor real-world LLM-inferentieworkloads. De auteurs plannen om Feather open-source te maken door het bij te dragen aan de vLLM- en SGLang-repositories.