Sintesi Tecnica: Oltre la Predizione: Scheduling Sensibile alla Coda per l'Inferenza di LLM

1. Definizione del Problema

Il servizio di Large Language Models (LLM) affronta una sfida critica nella gestione dell'estrema variabilità della lunghezza delle richieste, in particolare con l'ascesa di modelli aumentati dal ragionamento che esibiscono generazione multi-step, auto-riflessione e terminazione adattiva. Questa variabilità rende fragili le politiche di scheduling basate sulla dimensione (come Shortest Job First - SJF, o Shortest Remaining Processing Time - SRPT).

Gli scheduler allo stato dell'arte attuale si affidano alla predizione della lunghezza dell'output o dei token rimanenti per approssimare SJF/SRPT. Tuttavia, il paper identifica tre problemi fondamentali con questo approccio:

1. Fragilità della Predizione: La predizione della lunghezza dell'output è intrinsecamente difficile a causa dell'alta varianza nella generazione dei token (stocasticità e non determinismo), rendendo le policy fragili sotto cambiamenti di distribuzione e arrivi improvvisi (bursty).
2. Disallineamento delle Metriche: Le policy ottimizzate per la latenza media (es. media di TTFT/TBT) spesso mostrano un comportamento scadente nelle latenze della coda (P90–P99). Nel servizio di LLM, l'esperienza dell'utente è governata dalle latenze della coda (Time-To-Last-Token, TTLT), che sono spesso il vincolo determinante per gli SLO (Service Level Objectives).
3. Dinamiche Accoppiate alla Memoria: A differenza delle code classiche, l'inferenza LLM è stateful. Le richieste accumulano grandi cache KV durante la fase di decoding. La preemption ingenua per dare priorità ai lavori brevi può portare a costose espulsioni della cache, ricalcoli e "thrashing", aumentando potenzialmente la latenza della coda nonostante la riduzione del ritardo di accodamento.

La domanda centrale posta è se gli scheduler abbiano bisogno di predizioni esplicite sulla lunghezza dei job per ottimizzare la latenza della coda. Gli autori sostengono di no, proponendo un approccio basato sulla distribuzione e privo di predizioni.

2. Metodologia: UNIBOOST

Il paper introduce UNIBOOST, un framework di scheduling consapevole della distribuzione e privo di predizioni, che sostituisce la predizione esplicita della lunghezza con un "soft" boosting della priorità guidato da segnali statistici leggeri. Il design è una co-ottimizzazione di scheduling e preemption consapevole della cache, strutturata in quattro fasi:

Fase 1: Strawman (DISTBOOST)

L'approccio iniziale tratta le fasi di prefill e decode come problemi disgiunti. Utilizza una funzione di priorità $\gamma$-Boost (ispirata alla teoria delle code) per le richieste di prefill, ma dà priorità alla coda di decode. Sebbene questo migliori le metriche della coda per il decoding, soffre di Head-of-Line (HoL) blocking dove le richieste di prefill vengono affamate dai job di decode a lunga durata.

Fase 2: Prioritizzazione Unificata (UNIBOOST-BASE)

Per affrontare l'HoL blocking, gli autori unificano le code di prefill e decode in un unico spazio di priorità.

• Punteggio di Priorità: Le richieste sono punteggiate in base a $\phi_i(t) = a_i - b_\gamma(\tilde{w}_i(t))$, dove $a_i$ è il tempo di arrivo e $\tilde{w}_i(t)$ è il lavoro effettivo (il massimo tra il lavoro ottenuto e la lunghezza del prefill).
• Funzione di Boost: $b_\gamma(w) = \frac{1}{\gamma} \log(\frac{1}{1 - e^{-\gamma w}})$. Questa funzione fornisce un boost di priorità "soft" alle richieste con meno servizio ottenuto, evitando la preemption drastica del classico SRPT.
• Meccanismo: Lo scheduler seleziona la richiesta con il punteggio minimo, permettendo la preemption tra le fasi ma controllata da un parametro di isteresi per evitare oscillazioni.

Fase 3: Stabilità tramite MEMGUARD (Isteresi consapevole della KV-cache)

Per mitigare l'alto costo dell'evizione e del ricalcolo della cache KV, gli autori introducono MEMGUARD.

• Priorità Quantizzate: Invece di aggiornare continuamente le priorità, il sistema discretizza la metrica del lavoro ottenuto ($\hat{w}_i$) utilizzando una quantizzazione geometrica (es. soglie a $k, 2k, 4k...$).
• Minimo Run: Una volta che una richiesta viene dispacciata, non può essere evitta finché il suo lavoro ottenuto non supera la soglia di quantizzazione successiva. Questo ammortizza i costi di movimento della KV e limita le opportunità di preemption a un limite logaritmico rispetto alla lunghezza del job.

Fase 4: Stima Adattiva dei Parametri ($\gamma$-Ada)

Il parametro di boost $\gamma$ impatta significativamente il comportamento della coda. Un $\gamma$ statico è sub-ottimale sotto carichi variabili.

• Stima Online: Il sistema stima una pendenza effettiva della coda ($\gamma_{eff}$) adattando una pendenza log-lineare alla parte superiore della distribuzione dei tempi di risposta osservati (tra P95 e P99).
• Adattamento: Lo scheduler regola dinamicamente $\gamma$ per interpolare tra FCFS (proteggendo la coda) e LAS (ottimizzando la media), adattandosi ai cambiamenti di workload senza predizioni esplicite.

3. Contributi Chiave

1. Ottimizzazione della Coda Senza Predizione: Dimostra che non è necessaria la predizione esplicita della lunghezza del job per ottimizzare la latenza della coda. Al contrario, segnali statistici leggeri e un boosting soft sono sufficienti.
2. Co-Design di Scheduling ed Evizione: Introduce un framework che ottimizza congiuntamente le decisioni di scheduling con la gestione della cache KV. Accoppiando lo scheduling basato su boost con il controllo di esecuzione consapevole dell'evizione (MEMGUARD), il sistema evita il degrado delle prestazioni causato dal thrashing della cache.
3. Robustezza ai Cambiamenti di Distribuzione: Il metodo proposto si adatta a carichi di lavoro variabili (heavy-tailed vs light-tailed, reasoning vs chat) senza retraining o modelli di predizione complessi.
4. Fondamento Teorico: Adatta la policy $\gamma$-Boost dalla teoria delle code ai vincoli specifici dell'inferenza LLM (statefulness, accoppiamento della memoria).

4. Risultati Sperimentali

Valutato su trace di produzione e open-source (Azure, ShareGPT, S1K) utilizzando modelli come Llama-3-8B, CodeLlama-34B e Qwen-72B su GPU NVIDIA A100:

• Riduzione della Latenza della Coda: UNIBOOST ottiene una P99 TTLT fino al 35–50% inferiore rispetto a SRPT con predizione perfetta della lunghezza (TRAIL+). Riduce anche la P99 TTFT del 34–47% attraverso vari workload.
• Throughput: Il metodo migliora il throughput di 1.01–1.12$\times$ sotto carichi bursty rispetto ai baseline.
• Raggiungimento degli SLO: UNIBOOST permette ai sistemi di tollerare SLO per il TTFT da 2.9 a 8.7 volte più stringenti mantenendo il raggiungimento del 99% rispetto agli approcci basati su SJF.
• Studi di Ablazione:
  • Rimuovere la priorità unificata (Fase 2) porta alla fame (starvation) del prefill.
  • Rimuovere MEMGUARD (Fase 3) causa picchi significativi della latenza della coda a causa del thrashing della KV.
  • Rimuovere l'adattamento di $\gamma$ (Fase 4) riduce la robustezza sotto cambiamenti di carico.
• Confronto: Il metodo supera i baseline allo stato dell'arte inclusi Sarathi di vLLM (chunked prefill), LTR (learning-to-rank SJF) e TRAIL (predizione basata su SRPT), particolarmente nei workload pesanti sul ragionamento dove la qualità della predizione è più inaffidabile.

5. Significato e Affermazioni

Il paper afferma che UNIBOOST fornisce un'alternativa robusta alle policy di scheduling basate sulla predizione per il servizio online di LLM. La sua importanza risiede nel:

• Disaccoppiamento dalla Predizione: Elimina la dipendenza da una predizione accurata della lunghezza, che è un collo di bottiglia maggiore nei workload pesanti sul ragionamento e a lunghezza variabile.
• Ottimizzazione Olistica: Affronta simultaneamente il trade-off "media vs coda" e il trade-off "scheduling vs memoria", offrendo una soluzione efficace anche quando la qualità della predizione degrada.
• Praticità: Il design è semplice da integrare in stack di continuous-batching esistenti (come vLLM e SGLang) e si basa su statistiche di runtime leggere piuttosto che su complessi modelli ML.

Gli autori concludono che uno scheduling consapevole della distribuzione e dell'evizione è essenziale per la prossima generazione di servizio LLM, specialmente man mano che i modelli diventano più capaci di ragionamento a lunghezza variabile.