SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity

Il paper presenta SageSched, un efficiente scheduler per l'inferenza di LLM che affronta l'incertezza della domanda e l'ibridità computazionale-memoria attraverso la previsione della lunghezza dell'output e una politica di scheduling consapevole dell'incertezza, ottenendo un miglioramento dell'efficienza superiore al 28,7%.

L'essenziale

Immagina di essere il responsabile di un ristorante molto alla moda che serve piatti preparati da uno chef geniale, ma un po' imprevedibile: l'Intelligenza Artificiale (LLM).

Il problema è questo: i clienti (le richieste) arrivano tutti insieme, ma nessuno sa esattamente quanto tempo impiegherà lo chef a cucinare il loro piatto.

1. L'incertezza: A volte lo chef scrive solo due righe, altre volte ne scrive cento. Non lo sai finché non ha finito.
2. La complessità: Alcuni piatti richiedono solo un po' di fuoco (calcolo), altri richiedono un'enorme quantità di ingredienti e spazio sul bancone (memoria).

I sistemi di scheduling attuali sono come camerieri un po' stupidi:

• Metodo "Chi arriva prima, serve prima" (FCFS): Se arriva un cliente che ordina un pasto gigantesco, tutti gli altri devono aspettare, anche se hanno ordinato solo un caffè. È un disastro.
• Metodo "Indovina la lunghezza": Alcuni camerieri provano a indovinare quanto sarà lungo il piatto usando un modello complesso. Ma spesso sbagliano, e il modello stesso è lento da addestrare.

La soluzione: SageSched (Il Cameriere "Saggio")

Gli autori di questo articolo hanno creato SageSched, un sistema di gestione intelligente che risolve questi problemi con tre trucchi geniali, spiegati con analogie semplici:

1. Il "Libro delle Ricette Passate" (Predizione Intelligente)

Invece di usare un modello AI pesante e lento per indovinare quanto sarà lungo il piatto, SageSched guarda il libro degli ordini recenti.

• L'analogia: Se un cliente chiede "Scrivimi una storia su un gatto", il cameriere saggio guarda: "L'ultima volta che qualcuno ha chiesto una storia su un gatto, era lunga 500 parole".
• Il vantaggio: Non deve "indovinare" o "ricucinare" mentalmente il piatto. Basta guardare cosa è successo prima con richieste simili. È veloce, leggero e molto preciso. Invece di dire "Sarà lungo 500 parole", dice: "C'è il 70% di probabilità che sia tra 400 e 600 parole".

2. La "Bilancia Doppia" (Modellazione dei Costi)

I vecchi sistemi guardavano solo quanto tempo ci voleva per cucinare (calcolo). SageSched guarda anche quanto spazio occupa sul bancone (memoria).

• L'analogia: Immagina che il bancone del ristorante sia piccolo. Se un cliente ordina un piatto che richiede un'enorme pila di ingredienti (KV Cache), occupa tutto lo spazio, bloccando gli altri, anche se la cottura è veloce.
• Il vantaggio: SageSched calcola il "costo reale" combinando tempo e spazio. Se un piatto è corto ma occupa tutto il bancone, lo mette in coda. Se è lungo ma occupa poco spazio, lo fa passare.

3. La "Regola d'Oro dell'Attesa" (Scheduling con Gittins)

Questo è il cuore magico. Una volta che il cameriere sa che un piatto potrebbe essere lungo o corto, come decide chi servire?

• Il problema: Se aspetti solo la media, potresti sbagliare.
• La soluzione (Gittins Index): Immagina di avere una scommessa. Il sistema calcola un "punteggio di speranza". Non guarda solo la media, ma guarda la probabilità che il piatto finisca subito.
• L'analogia: Se hai due clienti:
  • Cliente A: Probabilmente ordinerà un panino (breve), ma c'è una piccola chance che voglia un banchetto.
  • Cliente B: Probabilmente ordinerà un banchetto, ma c'è una piccola chance che voglia un panino.
  • SageSched serve prima il Cliente A, perché ha una probabilità più alta di finire ora e liberare il tavolo. Se il Cliente A inizia a ordinare il banchetto, il sistema lo ricalcola e lo rimette in coda. È come un gioco di carte dove si punta sempre sulla carta che ha più probabilità di vincere immediatamente.

Il Risultato

Grazie a questi tre trucchi, SageSched riesce a gestire il caos del ristorante molto meglio degli altri.

• Risultato: I clienti aspettano meno tempo per ricevere l'ultimo pezzo del loro piatto (chiamato Time-to-Last-Token).
• Efficienza: Il paper dimostra che SageSched è oltre il 28% più veloce dei sistemi attuali, anche quando il ristorante è strapieno e gli ordini sono imprevedibili.

In sintesi: SageSched è come un cameriere che non si fida delle previsioni astratte, ma guarda la storia recente, controlla quanto spazio occupa ogni ordine sul bancone, e serve sempre chi ha più probabilità di finire subito, tenendo tutto il ristorante in movimento fluido.

Sommario tecnico

Ecco un riassunto tecnico dettagliato del documento "SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity" in italiano.

Panoramica del Problema

L'inferenza dei Large Language Models (LLM) presenta due caratteristiche fondamentali che rendono difficile la pianificazione (scheduling) efficiente delle risorse:

1. Incertezza della domanda (Demand Uncertainty): A causa della natura auto-regressiva degli LLM, la lunghezza dell'output (numero di token generati) non è deterministica e non può essere conosciuta a priori. Questo contrasta con i carichi di lavoro tradizionali (come i sistemi operativi o i big data) che hanno richieste di risorse stabili.
2. Ibridità della domanda (Demand Hybridity): Le inferenze degli LLM sono sia intensive dal punto di vista computazionale (calcolo) che della memoria (utilizzo massiccio della KVCache per evitare la ricomputazione). A differenza dei scheduler OS tradizionali che si concentrano principalmente sul costo computazionale, gli scheduler per LLM devono gestire simultaneamente la contesa di risorse di calcolo e memoria.

Gli scheduler esistenti (come FCFS in vLLM o approcci basati su modelli di previsione come SSJF e TRAIL) falliscono nell'ottimizzare le prestazioni perché:

• Si basano su euristiche semplici (es. First-Come-First-Served) che causano blocchi in testa alla coda (head-of-line-blocking).
• Utilizzano modelli di previsione pesanti e imprecisi che restituiscono un singolo valore invece di una distribuzione di probabilità.
• Ignorano l'ibridità, considerando solo la lunghezza dell'output come costo, trascurando l'impatto della memoria KVCache.

Metodologia: SageSched

SageSched è un nuovo scheduler progettato per gestire l'incertezza e l'ibridità attraverso tre tecniche chiave integrate in un flusso di lavoro unificato:

1. Predittore Storico Consapevole della Semantica (Semantic-aware History-based Predictor)

Invece di addestrare modelli pesanti per prevedere la lunghezza esatta dell'output (che è intrinsecamente incerta), SageSched sfrutta la correlazione tra la similarità semantica dei prompt e la distribuzione della lunghezza dell'output.

• Funzionamento: Per ogni richiesta in arrivo, il sistema cerca nelle richieste storiche recenti quelle con prompt semanticamente simili (calcolando la similarità coseno degli embedding).
• Output: Utilizza la distribuzione delle lunghezze degli output delle richieste storiche simili come previsione per la nuova richiesta.
• Vantaggi: È un metodo "training-free" (non richiede addestramento), leggero (latenza di previsione < 0.5 ms) e fornisce una distribuzione di probabilità anziché un singolo valore, catturando meglio l'incertezza.

2. Modellazione dei Costi Basata sui Vincoli delle Risorse (Resource-bound-based Cost Modeling)

SageSched riconosce che il costo di servizio di una richiesta dipende da quale risorsa è il collo di bottiglia (calcolo o memoria) in quel momento.

• Analisi: Il sistema modella il costo sia in scenari memory-bound (dove l'occupazione della KVCache è critica) sia in scenari compute-bound (dove il tempo di calcolo è dominante).
• Formula Unificata: È stato scoperto che entrambi i costi seguono lo stesso paradigma matematico. Il costo totale $C$ è modellato come:
  $$C = \frac{O^2}{2} + I \cdot O$$
  Dove $I$ è la lunghezza del prompt (input) e $O$ è la lunghezza dell'output. Questa formula cattura correttamente l'accumulo di risorse necessarie durante i passaggi di decodifica, superando le approssimazioni lineari usate in precedenza.

3. Politiche di Scheduling Consapevoli dell'Incertezza (Uncertainty-aware Scheduling)

Poiché il costo di una richiesta è rappresentato da una distribuzione di probabilità e non da un valore fisso, l'ordinamento basato sulla media (valore atteso) non è ottimale.

• Indice di Gittins: SageSched utilizza la politica dell'Indice di Gittins, nota per essere ottimale nei problemi di "multi-armed bandit" con distribuzioni di ricompensa note ma durate incerte.
• Funzionamento: Calcola l'indice di Gittins per ogni richiesta in coda basandosi sulla sua distribuzione di costo. Le richieste con un indice più basso (che indicano un costo atteso di completamento più rapido o una maggiore probabilità di completamento a breve termine) vengono priorizzate.
• Aggiornamento Dinamico: L'indice di Gittins viene ricalcolato periodicamente (ai confini di "bucket" di costo) man mano che l'inferenza procede, per mantenere la pianificazione aggiornata senza generare un overhead eccessivo di preemption.

Risultati Sperimentali

Gli autori hanno valutato SageSched su un banco di prova reale (utilizzando modelli Llama3.1-8B e Qwen3-32B su GPU A40 e H800) e attraverso simulazioni su larga scala (fino a 64 nodi).

• Miglioramento delle Prestazioni: SageSched supera gli scheduler più avanzati (come TRAIL, SSJF, FastServe) riducendo il Time-to-Last-Token (TTLT) medio di oltre il 28.7% in scenari ad alta concorrenza.
• Robustezza: Il sistema mantiene prestazioni superiori anche quando le previsioni delle distribuzioni non sono perfettamente accurate, dimostrando resilienza.
• Overhead: L'overhead di scheduling e previsione è trascurabile (circa 100 ms aggiuntivi per richiesta anche su cluster di 64 nodi), rendendo la soluzione scalabile.
• Analisi dei Componenti: Gli esperimenti "microscopici" confermano che ciascuna delle tre componenti (predittore, modellazione del costo, politica di scheduling) contribuisce significativamente al miglioramento complessivo rispetto alle varianti che ne rimuovono una.

Significato e Contributi

Questo lavoro rappresenta un passo avanti significativo nell'ottimizzazione dei sistemi di inferenza LLM:

1. Identificazione del Problema: Dimostra chiaramente che l'approccio tradizionale basato su valori medi e solo sul calcolo è insufficiente per gli LLM a causa dell'incertezza intrinseca e dell'ibridità delle risorse.
2. Innovazione Metodologica: Introduce un approccio ibrido che combina l'analisi storica semantica per la previsione delle distribuzioni e la teoria dell'ottimizzazione stocastica (Indice di Gittins) per la gestione della coda.
3. Impatto Pratico: Offre una soluzione implementabile (già integrata su vLLM) che migliora direttamente l'esperienza utente finale riducendo la latenza totale, un fattore critico per applicazioni come agenti AI e sistemi interattivi.

In sintesi, SageSched trasforma la gestione delle richieste LLM da un approccio deterministico e statico a uno probabilistico e dinamico, adattandosi alle reali caratteristiche di incertezza e consumo misto di risorse dei modelli di linguaggio moderni.