Riepilogo Tecnico: Algoritmi di Scheduling Ottimali per il Throughput nell'Inferenza di LLM e negli Agenti AI

Enunciato del Problema

Con la crescente domanda di Modelli Linguistici su Larga Scala (LLM) e agenti AI, l'ottimizzazione dei sistemi di inferenza per l'efficienza è fondamentale. Sebbene significativi sforzi ingegneristici si siano concentrati su miglioramenti a livello di sistema, manca un quadro matematico coerente e un modello teorico delle code per valutare gli algoritmi di scheduling. Nello specifico, il documento affronta la domanda fondamentale: Qual è il tasso di throughput massimo per un sistema di inferenza LLM e quali classi di algoritmi di scheduling possono raggiungere questo limite?

L'inferenza LLM presenta sfide uniche rispetto ai sistemi di code classici:

1. Elaborazione a Due Fasi: Le richieste subiscono una fase di prefill limitata dal calcolo (elaborazione dei token di input per costruire la cache KV) seguita da una fase di decode limitata dall'I/O della memoria (generazione autoregressiva dei token).
2. Vincoli di Batching: Per massimizzare l'utilizzo della GPU, le richieste vengono raggruppate in batch. Tuttavia, la miscelazione di token di prefill e decode crea interferenze, e l'hardware impone un budget di token ($b_{max}$) e spesso un vincolo di dimensione del batch ($k_{max}$).
3. Carichi di Lavoro degli Agenti AI: Le applicazioni moderne coinvolgono reti di server LLM che elaborano compiti complessi di agenti, i quali possono seguire topologie a Grafo Aciclico Diretto (DAG), pattern fork-join o contenere instradamenti ciclici.

I sistemi esistenti impiegano strategie diverse (ad es. FasterTransformer, vLLM, Orca, Sarathi-Serve) con priorità variabili (prefill-first vs decode-first) e capacità di batching (misto vs separato). I professionisti attualmente si affidano a costosi benchmark specifici per il carico di lavoro per scegliere i sistemi, mancando di una garanzia teorica di stabilità o ottimalità del throughput.

Metodologia

Gli autori sviluppano un rigoroso quadro teorico delle code per modellare i sistemi di inferenza LLM.

1. Modellazione Stocastica

• Modello di Base: Il sistema è modellato come una catena di Markov a tempo discreto (DTMC) che rappresenta una coda di servizio in batch a due classi.
  • Classi: Le richieste esistono in una coda di prefill o in una coda di decode.
  • Batching: Il server elabora un batch di token da entrambe le code simultaneamente, soggetto a un budget di token $b_{max}$.
  • Asimmetria: I token di prefill di una singola richiesta possono essere elaborati in blocco, mentre i token di decode sono strettamente sequenziali (uno per richiesta per batch).
• Modello dei Tempi di Elaborazione: Sfruttando tracce empiriche, il tempo di elaborazione del batch $t_b$ è approssimato da una funzione a tratti costante dipendente dal carico di token $b$:
  $$t_b = c + a \cdot \lceil b/b_0 \rceil$$
  dove $c$ è il costo base, $a$ è il costo marginale per blocco di $b_0$ token. Questo modello cattura il dominio dei calcoli degli strati lineari nell'inferenza LLM.

2. Quadro Analitico

• Tecnica del Limite Fluido: Gli autori impiegano il quadro del limite fluido (Dai 1995, Stolyar 1995) per analizzare la stabilità. Dimostrano che, sotto condizioni specifiche, il processo stocastico scalato converge a un modello fluido deterministico.
• Definizione di Stabilità: Un sistema è stabile (ricorrente positivo) se il numero totale di token non elaborati non diverge all'infinito.
• Classe di Scheduling: L'analisi si concentra sugli algoritmi conservativi del lavoro (quelli che riempiono il batch alla capacità $b_{max}$ ogni volta che è possibile) e introduce la condizione K-FCFS (First-Come-First-Served con sorpasso limitato) per gestire le complessità del batching misto.

3. Estensioni

Il quadro è esteso a:

• Server Paralleli: Sistemi con bilanciamento del carico (Random o Join-the-Shortest-Queue).
• Reti Multi-Classe: Singoli server che gestiscono multiple classi di richieste (ad es. diversi passaggi di agenti).
• Topologie di Rete: Reti multi-server con instradamento DAG e sincronizzazione fork-join.
• Instradamento Ciclico: Analisi di reti con cicli di feedback (tipo Rybko–Stolyar).
• Vincoli di Dimensione del Batch: Analisi di sistemi vincolati sia dal budget di token ($b_{max}$) che dalla dimensione massima del batch ($k_{max}$).

Contributi e Risultati Chiave

1. Ottimalità del Throughput degli Scheduling Conservativi del Lavoro

Il documento stabilisce un principio di progettazione fondamentale: gli algoritmi di scheduling conservativi del lavoro raggiungono il throughput massimo per l'inferenza LLM su singolo server e per reti con topologie DAG o fork-join.

• Teorema 2: Per un singolo server, se il carico in arrivo $\lambda(m_p + m_d)$ è inferiore al tasso di elaborazione massimo $b_{max}/t_{b_{max}}$, qualsiasi algoritmo K-FCFS conservativo del lavoro stabilizza il sistema. Al contrario, se il carico supera questa soglia, il sistema è instabile sotto qualsiasi algoritmo.
• Implicazione: Ciò fornisce un limite superiore teorico ($b_{max}/t_{b_{max}}$) e convalida il passaggio nell'industria verso scheduler conservativi del lavoro.

2. Valutazione dei Sistemi Esistenti

L'applicazione del quadro teorico agli algoritmi reali produce classificazioni chiare:

• Ottimali per il Throughput (Conservativi del Lavoro):
  • Orca: Supporta batching misto (prefill + decode) con priorità al prefill.
  • Sarathi-Serve: Supporta prefill a blocchi con priorità al decode e batching misto.
  • vLLM più recente (con prefill a blocchi): Conservativo del lavoro.
• Subottimali/Instabili (Non Conservativi del Lavoro):
  • FasterTransformer: Priorizza il decode ma vieta il batching misto. Lascia la GPU inattiva quando le richieste di decode non sono sufficienti a riempire un batch, anche se ci sono richieste di prefill in attesa.
  • vLLM Vanilla: Priorizza il prefill ma vieta il batching misto. Lascia le richieste di decode in attesa mentre elabora batch solo di prefill.
• Validazione Sperimentale: Tracce reali confermano che gli algoritmi non conservativi del lavoro (FasterTransformer, vLLM vanilla) diventano instabili (esplosione della coda) sotto carichi moderati, dove gli algoritmi conservativi del lavoro (Sarathi-Serve, Orca) rimangono stabili.

3. Carichi di Lavoro degli Agenti AI e Topologie di Rete

• DAG e Fork-Join: Il documento dimostra che lo scheduling conservativo del lavoro rimane ottimale per il throughput per reti di server LLM disposte in DAG o topologie fork-join, a condizione che la condizione di carico valga per ogni server.
• Instradamento Ciclico (Controesempio di Rybko–Stolyar): Gli autori dimostrano che lo scheduling conservativo del lavoro non è sufficiente per reti con instradamento ciclico. Costruiscono una rete a due server in cui assegnazioni di priorità specifiche sotto una politica conservativa del lavoro portano all'instabilità, anche quando il carico totale è inferiore alla capacità. Ciò evidenzia la necessità di una progettazione attenta delle priorità o di politiche non conservatrici del lavoro (ad es. back-pressure) nelle topologie cicliche.

4. Impatto dei Vincoli di Dimensione del Batch

Quando viene imposto un vincolo di dimensione massima del batch ($k_{max}$) insieme al budget di token ($b_{max}$):

• La regione di stabilità diventa un inviluppo convesso bidimensionale nel piano $(\lambda_{prefill}, \lambda_{decode})$, piuttosto che una semplice soglia scalare.
• Riscontro Controintuitivo: In certi regimi (specificamente vicino a un vertice della regione di stabilità che coinvolge batch misti), algoritmi strettamente conservativi del lavoro che riempiono sempre fino a $b_{max}$ possono non stabilizzare il sistema. La stabilità ottimale può richiedere di operare a un carico di token inferiore (ad es. $b_0$) per bilanciare i tassi di elaborazione dei token di prefill e decode. Ciò suggerisce che, sotto vincoli stretti di dimensione del batch, sono necessarie strategie di scheduling adattive.

Significato e Affermazioni

Il documento afferma di fornire la prima fondazione rigorosa della teoria delle code per lo scheduling dell'inferenza LLM. Il suo significato risiede in:

1. Principio di Progettazione: Identifica il "conservativo del lavoro" come un principio chiave per i professionisti, offrendo la garanzia teorica che algoritmi come Sarathi-Serve e Orca sono ottimali per il throughput, mentre avverte contro approcci di batching non misto come FasterTransformer e vLLM vanilla.
2. Collegamento delle Comunità: Abbassa la barriera per la comunità della teoria delle code di contribuire ai sistemi LLM fornendo un modello formale che cattura le caratteristiche uniche a due fasi e di batching degli LLM.
3. Guida per gli Agenti AI: Estende l'analisi di stabilità ai carichi di lavoro degli agenti AI, rivelando che mentre le topologie DAG sono robuste, le topologie cicliche richiedono uno scheduling più sofisticato rispetto alle semplici politiche conservatrici del lavoro.
4. Vincoli Sottili: Rivela che vincoli pratici come i limiti di dimensione del batch possono alterare fondamentalmente le regioni di stabilità, sfidando l'assunzione che "riempire il batch" sia sempre ottimale.

Gli autori concludono che, sebbene il loro lavoro stabilisca una base per l'ottimalità del throughput, il lavoro futuro dovrà affrontare l'ottimizzazione della latenza, modelli di tempo di elaborazione più ricchi (incorporando gli strati di attenzione) e la progettazione di algoritmi adattivi per vincoli complessi e topologie di rete.