Technische Samenvatting: BlendServe

Probleemstelling

Offline batch-inferentie is een kosteneffectieve oplossing geworden voor latency-ongevoelige taken met Large Language Models (LLM's), zoals modelevaluatie en datacuratie. In tegenstelling tot online inferentie, waarbij lage latency prioriteit heeft, streeft offline inferentie naar het maximaliseren van de throughput (tokens per seconde) binnen een ruime tijdvenster.

Bestaande technieken voor throughput-optimalisatie, zoals chunked prefill (Sarathi-Serve) en operator-level overlapping (NanoFlow, Orion), richten zich op het balanceren van reken- en geheugenbronnen binnen een enkele batch. Deze benaderingen kampen echter met afnemende meeropbrengsten naarmate de diversiteit van toepassingen toeneemt. Moderne LLM-workloads vertonen zeer verschillende resource-eisen:

• Compute-intensief: Taken met lange inputsequenties maar korte outputs (bijv. documentsamenvatting, benchmarks zoals MMLU) verzadigen de GPU-rekenunits, terwijl de geheugenbandbreedte onderbenut blijft.
• Geheugen-intensief: Taken met lange outputsequenties (bijv. videogeneratie, redeneren) verzadigen de geheugenbandbreedte tijdens de autoregressieve decode-fase, terwijl de rekenunits onderbenut blijven.

Wanneer een batch voornamelijk uit één type verzoek bestaat, blijven de hardwarebronnen ongebalanceerd, wat de throughput beperkt. Bovendien staat het simpelweg herordenen van verzoeken om resource-overlap te maximaliseren vaak op gespannen voet met prefix sharing, een techniek die verzoeken met gemeenschappelijke prefixes groepeert om redundante berekeningen te vermijden. Een volgorde van verzoeken die prefix sharing maximaliseert (doorgaans Depth-First Search op een prefix-boom) kan resulteren in batches die gedomineerd worden door één enkel type resource, terwijl een volgorde die resource-overlap maximaliseert, de prefix-lokaliteit kan vernietigen.

Methodologie: BlendServe

BlendServe is een servingsysteem dat is ontworpen om resource-bewuste batching en prefix sharing te harmoniseren om de offline inferentie-throughput te maximaliseren. Het kernontwerp bestaat uit drie hoofdcomponenten:

1. Prestatiemodellering en Compute Density

BlendServe introduceert een metriek genaamd compute density ($\rho$), gedefinieerd als de ratio van de compute-gebonden operator-tijd ten opzichte van de memory-gebonden operator-tijd voor een verzoek.

• Verzoekniveau: $\rho(r) = \frac{\text{Comp}(r)}{\text{Mem}(r)}$. Een hoge $\rho$ duidt op compute-intensieve workloads; een lage $\rho$ duidt op memory-intensieve workloads.
• Batchniveau: Het systeem modelleert de totale executietijd $T$ als een functie van de compute-tijd ($T_{comp}$), de memory-tijd ($T_{mem}$) en de prefix sharing ratio ($s$). Het doel is om $T$ te minimaliseren door de overlap van compute- en memory-operaties te maximaliseren en tegelijkertijd redundante berekeningen te minimaliseren.
• Output-schatting: Omdat outputlengtes onbekend zijn tijdens autoregressieve generatie, gebruikt BlendServe een samplingstrategie tijdens een warm-up fase. Het leidt de outputlengteverdelingen af op basis van de semantiek van de prompt en de typen taken, waarbij gesamplede verzoeken worden gebruikt om de dichtheid van niet-gesamplede verzoeken binnen dezelfde prefix-subboom te schatten.

2. Resource-Aware Prefix Tree

Om de afweging tussen prefix sharing en resource-overlap te beheren, construeert BlendServe een resource-aware prefix tree:

• Structuur: Gebaseerd op de Trie-structuur die wordt gebruikt in systemen zoals SGLang, waarbij nodes gedeelde prompt-segmenten vertegenwoordigen.
• Verbetering: Elke node is geannoteerd met de compute density van alle verzoeken in de bijbehorende subtree.
• Sorteren en Splitsen: Het systeem sorteert nodes op elk niveau op basis van hun compute density, waarbij compute-intensieve nodes aan de linkerkant en memory-intensieve nodes aan de rechterkant worden geplaatst. Om uitschieters te behandelen die de globale ordening verstoren, wordt een conditional node splitting techniek gebruikt. Als de dichtheid van een node significant afwijkt van die van zijn buren, wordt de node gesplitst en opnieuw gepositioneerd. Dit brengt een gecontroleerde kostenpost met zich mee van het opnieuw berekenen van een klein prefix-segment om een betere resource-balans te bereiken.

3. Dual Scanning Algoritme

Om de uiteindelijke verzoek-scheduling te genereren, gebruikt BlendServe een dual scanning algoritme:

• Mechanisme: Het algoritme scant de bladeren van de gesorteerde prefix-boom gelijktijdig vanaf de linker (compute-intensieve) en rechter (memory-intensieve) uiteinden.
• Batchvorming: Het algoritme berekent dynamisch de vereiste memory-partitie ($M_L$ en $M_R$) om een doelstelling te bereiken voor de globale compute density ($\rho_{target}$) die overeenkomt met de root van de boom. Verzoeken worden van beide uiteinden geselecteerd om deze partities te vullen, waardoor gegarandeerd een gebalanceerde mix van compute- en memory-intensieve verzoeken in elke batch terechtkomt.
• Resultaat: Deze aanpak behoudt de hiërarchische structuur van de prefix-boom (behoud van hoge prefix sharing) terwijl verzoeken worden door elkaar gehusseld om de hardware-resource-overlap te maximaliseren.

4. Gedistribueerde Implementatie

BlendServe ondersteunt Data Parallelism (DP) en Tensor Parallelism (TP).

• In DP wordt de gecentraliseerde prefix-boom gedecomposeerd in subtrees die aan verschillende ranks worden toegewezen, wat zorgt voor een gebalanceerde workload.
• In TP integreert het systeem met bestaande pipeline-strategieën om de communicatie-overhead te overlappen met de berekening, waardoor compatibiliteit met grootschalige implementaties behouden blijft.

Belangrijkste Bijdragen

1. Analyse van Workload Diversiteit: Een gedetailleerde karakterisering van hoe diverse LLM-toepassingen (chat, coding, videogeneratie) conflicterende resource-eisen (compute vs. memory) creëren die bestaande batching-strategieën beperken.
2. Resource-Aware Prefix Tree: Een nieuwe datastructuur die de resource-eisen (compute density) codeert terwijl de prefix-structuren behouden blijven, waardoor het systeem tegelijkertijd over zowel prefix sharing als resource-overlap kan redeneren.
3. Dual Scanning Algoritme: Een heuristisch scheduling-algoritme dat batches construeert door een gesorteerde prefix-boom van beide kanten te scannen, waardoor verzoekstypen effectief worden gemengd om de resource-overlap te maximaliseren zonder prefix sharing op te offeren.
4. Prototype en Evaluatie: Een volledige implementatie gebouwd op NanoFlow en SGLang, geëvalueerd over meerdere modellen (Llama-3-8B/70B, Qwen-2.5, DeepSeek) en diverse synthetische workloads.

Experimentele Resultaten

De auteurs hebben BlendServe geëvalueerd tegen industriestandaard baselines (vLLM, SGLang) en state-of-the-art throughput-georiënteerde systemen (NanoFlow).

• Throughput Versnelling:
  • Vergeleken met vLLM en SGLang behaalt BlendServe een tot 1,44× hogere throughput.
  • Vergeleken met NanoFlow (de huidige state-of-the-art voor throughput), levert BlendServe gemiddeld 20,84% hogere throughput.
• Optimaliteitsgat: BlendServe bereikt gemiddeld 86,55% van de theoretisch optimale throughput (tot 90% in specifieke configuraties), wat aantoont dat het effectief de limiet benadert van wat haalbaar is met perfecte resource-overlapping en prefix sharing.
• Resource Utilisatie: Visualisaties van compute- en memory-gebruik laten zien dat BlendServe een stabiele, gebalanceerde resource-utilisatie handhaaft tijdens de inference-stappen, terwijl baselines zoals NanoFlow-DFS significante fluctuaties en perioden van resource-onderbenutting vertonen.
• Prefix Sharing: Ondanks het herordenen van verzoeken voor resource-balans, behoudt BlendServe 97% van de maximale prefix sharing ratio die haalbaar is met een standaard DFS-traversal.
• Schaalbaarheid: Het systeem vertoont bijna lineaire schaling met Data Parallelism (DP) en blijft effectief over verschillende modelgroottes (7B tot 72B) en hardwareconfiguraties.

Betekenis en Claims

Het artikel claimt dat BlendServe het eerste serving-systeem is dat specifief is geoptimaliseerd voor offline batch-inferentie en dat er erin slaagt twee traditioneel conflicterende doelstellingen te harmoniseren: resource overlapping en prefix sharing.

De auteurs stellen dat naarmate LLM-applicaties diversifiëren, de aanname van uniforme resource-eisen binnen een batch niet langer geldig is. Door gebruik te maken van de ruime latency-restricties van offline inferentie om verzoeken te herordenen, ontsluit BlendServe aanzienlijke throughput-winsten die eerdere intra-batch optimalisaties niet konden bereiken. Het systeem toont aan dat het mogelijk is om de optimale throughput (90%) te benaderen zonder de efficiëntievoordelen van prefix caching op te offeren, wat een robuuste oplossing biedt voor kosteneffectieve, hoog-throughput LLM-inferentie.