Riepilogo Tecnico: BlendServe

Problematica

L'inferenza batch offline è emersa come una soluzione conveniente per i compiti di Large Language Model (LLM) a bassa latenza, come la valutazione dei modelli e la cura dei dati. A differenza dell'inferenza online, che privilegia la bassa latenza, l'inferenza offline mira a massimizzare il throughput (token al secondo) entro una finestra temporale rilassata.

Le tecniche di ottimizzazione del throughput esistenti, come il chunked prefill (Sarathi-Serve) e l'overlapping a livello di operatore (NanoFlow, Orion), si concentrano sul bilanciamento delle risorse computazionali e di memoria all'interno di un singolo batch. Tuttavia, questi approcci affrontano rendimenti decrescenti man mano che la diversità delle applicazioni aumenta. I moderni carichi di lavoro LLM presentano richieste di risorse molto diverse:

• Compute-intensive (Intensive di calcolo): Compiti con sequenze di input lunghe ma output brevi (es. riassunto di documenti, benchmark come MMLU) saturano le unità di calcolo della GPU lasciando sottoutilizzata la larghezza di banda della memoria.
• Memory-intensive (Intensive di memoria): Compiti con sequenze di output lunghe (es. generazione di video, ragionamento) saturano la larghezza di banda della memoria durante la fase autoregressiva di decoding, lasciando sottoutilizzate le unità di calcolo.

Quando un batch consiste prevalentemente di un unico tipo di richiesta, le risorse hardware rimangono sbilanciate, limitando il throughput. Inoltre, il semplice riordinamento delle richieste per massimizzare la sovrapposizione delle risorse spesso entra in conflitto con il prefix sharing (condivisione dei prefissi), una tecnica che raggruppa le richieste con prefissi comuni per evitare calcoli ridondanti. Un ordine di richieste che massimizza la condivisione dei prefissi (tipicamente la ricerca in profondità o DFS su un albero dei prefissi) può generare batch dominati da un singolo tipo di risorsa, mentre un ordine che massimizza la sovrapposizione delle risorse può distruggere la località del prefisso.

Metodologia: BlendServe

BlendServe è un sistema di serving progettato per armonizzare il batching consapevole delle risorse (resource-aware batching) e il prefix sharing per massimizzare il throughput dell'inferenza offline. Il suo design principale prevede tre componenti principali:

1. Modellazione delle Prestazioni e Densità di Calcolo

BlendServe introduce una metrica chiamata densità di calcolo ($\rho$), definita come il rapporto tra il tempo dell'operatore limitato dal calcolo (compute-bound) e il tempo dell'operatore limitato dalla memoria (memory-bound) per una richiesta.

• Livello di Richiesta: $\rho(r) = \frac{\text{Comp}(r)}{\text{Mem}(r)}$. Un $\rho$ elevato indica carichi di lavoro intensivi di calcolo; un $\rho$ basso indica carichi di lavoro intensivi di memoria.
• Livello di Batch: Il sistema modella il tempo di esecuzione totale $T$ come funzione del tempo di calcolo ($T_{comp}$), del tempo di memoria ($T_{mem}$) e del rapporto di condivisione del prefisso ($s$). L'obiettivo è minimizzare $T$ massimizzando la sovrapposizione delle operazioni di calcolo e memoria e minimizzando il calcolo ridondante.
• Stima dell'Output: Poiché le lunghezze di output sono sconosciute nella generazione autoregressiva, BlendServe impiega una strategia di campionamento durante una fase di warm-up. Inferisce le distribuzioni della lunghezza dell'output in base alla semantica del prompt e ai tipi di task, utilizzando richieste campionate per stimare la densità delle richieste non campionate all'interno dello stesso sottoalbero del prefisso.

2. Albero dei Prefissi Consapevole delle Risorse

Per gestire il compromesso tra condivisione dei prefissi e sovrapposizione delle risorse, BlendServe costruisce un albero dei prefissi consapevole delle risorse:

• Struttura: Basata sulla struttura Trie utilizzata in sistemi come SGLang, dove i nodi rappresentano segmenti di prompt condivisi.
• Potenziamento: Ogni nodo è annotato con la densità di calcolo di tutte le richieste nel suo sottoalbero.
• Ordinamento e Suddivisione: Il sistema ordina i nodi a ogni livello in base alla loro densità di calcolo, posizionando i nodi compute-intensive a sinistra e quelli memory-intensive a destra. Per gestire gli outlier che interrompono questo ordinamento globale, viene utilizzata una tecnica di suddivisione condizionale dei nodi (conditional node splitting). Se la densità di un nodo devia significativamente dai suoi vicini, esso viene diviso e riposizionato. Ciò comporta un costo controllato di ricalcolo di un piccolo segmento di prefisso per ottenere un migliore bilanciamento delle risorse.

3. Algoritmo di Scansione Duale

Per generare lo scheduling finale delle richieste, BlendServe impiega un algoritmo di scansione duale:

• Meccanismo: L'algoritmo scansiona le foglie dell'albero dei prefissi ordinato simultaneamente dalle estremità sinistra (compute-intensive) e destra (memory-intensive).
• Formazione del Batch: Calcola dinamicamente la partizione di memoria necessaria ($M_L$ e $M_R$) per raggiungere una densità di calcolo globale target ($\rho_{target}$) che corrisponda alla radice dell'albero. Le richieste vengono selezionate da entrambe le estremità per riempire queste partizioni, garantendo che ogni batch contenga un mix bilanciato di richieste compute-intensive e memory-intensive.
• Risultato: Questo approccio preserva la struttura gerarchica dell'albero dei prefissi (mantenendo un'alta condivisione dei prefissi) pur intercalando le richieste per massimizzare la sovrapposizione delle risorse hardware.

4. Distribuzione Distribuita

BlendServe supporta il Parallelismo dei Dati (DP) e il Parallelismo dei Tensori (TP).

• In DP, l'albero dei prefissi centralizzato viene decomposto in sottoalberi assegnati a diversi rank, garantendo carichi di lavoro bilanciati.
• In TP, il sistema si integra con le strategie di pipeline esistenti per sovrapporre l'overhead di comunicazione con il calcolo, mantenendo la compatibilità con implementazioni su larga scala.

Contributi Chiave

1. Analisi della Diversità dei Carichi di Lavoro: Una caratterizzazione dettagliata di come i diversi carichi di lavoro LLM (chat, coding, generazione di video) creino richieste di risorse contrastanti (calcolo vs memoria) che limitano le strategie di batching esistenti.
2. Albero dei Prefissi Consapevole delle Risorse: Una nuova struttura dati che codifica le richieste di risorse (densità di calcolo) preservando al contempo le strutture dei prefissi, consentendo al sistema di ragionare simultaneamente sulla condivisione dei prefissi e sulla sovrapposizione delle risorse.
3. Algoritmo di Scansione Duale: Un algoritmo di scheduling euristico che costruisce i batch scansionando un albero dei prefissi ordinato da entrambe le estremità, mescolando efficacemente i tipi di richieste per massimizzare la sovrapposizione delle risorse senza sacrificare la condivisione dei prefissi.
4. Prototipo e Valutazione: Un'implementazione completa costruita sopra NanoFlow e SGLang, valutata su molteplici modelli (Llama-3-8B/70B, Qwen-2.5, DeepSeek) e diversi carichi di lavoro sintetici.

Risultati Sperimentali

Gli autori hanno valutato BlendServe contro baseline standard del settore (vLLM, SGLang) e sistemi orientati al throughput all'avanguardia (NanoFlow).

• Accelerazione del Throughput:
  • Rispetto a vLLM e SGLang, BlendServe ottiene un'accelerazione del throughput fino a 1.44×.
  • Rispetto a NanoFlow (l'attuale stato dell'arte per il throughput), BlendServe offre un throughput medio superiore del 20.84%.
• Gap di Ottimalità: BlendServe raggiunge in media l'86.55% del throughput teorico ottimale (fino al 90% in configurazioni specifiche), dimostrando che si avvicina efficacementamente al limite di ciò che è ottenibile con una perfetta sovrapposizione delle risorse e condivisione dei prefissi.
• Utilizzo delle Risorse: Le visualizzazioni dell'uso di calcolo e memoria mostrano che BlendServe mantiene un utilizzo delle risorse stabile e bilanciato durante i passaggi di inferenza, mentre le baseline come NanoFlow-DFS mostrano fluttuazioni significative e periodi di sotto-utilizzo delle risorse.
• Condivisione dei Prefissi: Nonostante il riordinamento delle richieste per il bilanciamento delle risorse, BlendServe mantiene il 97% del rapporto massimo di condivisione dei prefissi ottenibile con una normale scansione DFS.
• Scalabilità: Il sistema dimostra una scalabilità quasi lineare con il Parallelismo dei Dati (DP) e rimane efficace attraverso diverse dimensioni dei modelli (da 7B a 72B) e configurazioni hardware.

Significato e Rivendicazioni

Il paper afferma che BlendServe è il primo sistema di serving specificamente ottimizzato per l'inferenza batch offline che riesce ad armonizzare due obiettivi tradizionalmente contrastanti: la sovrapposizione delle risorse (resource overlapping) e la condivisione dei prefissi (prefix sharing).

Gli autori sostengono che, con la diversificazione delle applicazioni LLM, l'assunzione di richieste di risorse uniformi all'interno di un batch non è più valida. Sfruttando i vincoli di latenza rilassati dell'inferenza offline per riordinare le richieste, BlendServe sblocca guadagni significativi di throughput che le precedenti ottimizzazioni intra-batch non potevano raggiungere. Il sistema dimostra che è possibile avvicinarsi al throughput ottimale (90%) senza sacrificare i vantaggi dell'efficienza del caching dei prefissi, fornendo una soluzione robusta per l'inferenza LLM ad alto throughput e conveniente.