🔢 mathematics

Online Linear Programming for Multi-Objective Routing in LLM Serving

Questo articolo propone un framework di programmazione lineare online basato sulla scienza con controllo del prezzo del bid e aggiornamenti duali con warm-start per ottimizzare il routing multi-obiettivo nel serving di LLM, dimostrando prestazioni di latenza e throughput superiori rispetto ai tradizionali approcci euristici.

Autori originali: Zixi Chen, Yinyu Ye, Zijie Zhou

Pubblicato 2026-07-07

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Zixi Chen, Yinyu Ye, Zijie Zhou

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di gestire la cucina di un ristorante di alto livello molto trafficato. Questa cucina ha diverse postazioni di cottura parallele (le GPU), e i clienti (le richieste AI) arrivano uno alla volta.

In una cucina normale, potresti semplicemente inviare l'ordine successivo al primo chef libero. Ma in questa specifica "ristorante AI", le cose sono complicate:

Gli ordini sono strani: Alcuni ordini sono antipasti veloci (testo breve), mentre altri sono pasti massicci e complessi che richiedono molto tempo per essere cucinati (generazione di testo lungo). Non sai esattamente quanto tempo impiegherà un ordine finché non è già in fase di cottura.
Lo spazio è limitato: Ogni chef ha un banco da lavoro limitato (memoria) e può tenere solo un certo numero di piatti sul suo fornello alla volta (batch size). Se metti troppi piatti su un unico fornello, l'intera postazione va in crash.
I clienti sono esigenti: Alcuni clienti vogliono il loro cibo immediatamente (bassa latenza), mentre altri vogliono solo sapere che la cucina è impegnata ed efficiente (alto throughput). A volte, devi scegliere: servire un cliente super velocemente o servirne dieci un po' più lentamente?

Il problema con i vecchi metodi
La maggior parte delle cucine oggi usa regole semplici, come "invia l'ordine allo chef con la fila più corta" o "invia l'ordine a chi è attualmente libero". Il documento sostiene che queste regole sono come usare un martello per riparare un orologio. Non comprendono il valore dell'ordine o il costo dello spazio che occupa. Non riescono facilmente a bilanciare la necessità di velocità rispetto alla necessità di mantenere la cucina in funzione in modo fluido.

La nuova soluzione: Il sistema del "Prezzo Intelligente"
Gli autori propongono un nuovo modo di gestire la cucina utilizzando un concetto chiamato Programmazione Lineare Online. Immagina questo come un sistema di "Prezzi Intelligenti" per ogni centimetro di banco da lavoro e per ogni minuto del tempo di uno chef.

Ecco come funziona, passo dopo passo:

1. Il Prezzo Ombra (Il "Costo Opportunità")

Immagina che ogni spazio sul fornello di uno chef abbia un "prezzo" nascosto attaccato. Questo non è denaro; è un Prezzo Ombra (Shadow Price).

Se un fornello è affollato e sta finendo lo spazio, il prezzo sale. Questo dice al router: "Fai attenzione! Usare questo spazio ora potrebbe significare che non potremo cucinare un pasto enorme e importante più tardi."
Se un fornello è vuoto, il prezzo è basso. È economico da usare in questo momento.

2. La Decisione (Beneficio vs. Costo)

Quando arriva un nuovo ordine del cliente, il router non si limita a guardare chi è libero. Fa un rapido controllo matematico:

Il Beneficio: Quanto sarà felice questo cliente? (Riceverà il suo cibo velocemente? Aiuterà l'efficienza complessiva della cucina?)
Il Costo: Qual è la somma dei "Prezzi Ombra" dello spazio che questo ordine richiede?

La Regola: Se il Benefio è superiore al Costo, il router dice: "Sì, cucina questo!". Se il Costo è troppo alto (il fornello è troppo costoso in questo momento), il router potrebbe dire: "Aspetta in fila", oppure inviarlo a un fornello diverso e più economico.

3. Imparare al volo (Il "Warm Start")

La cucina è caotica. I "prezzi" cambiano ogni secondo man mano che arrivano nuovi ordini e ne finiscono altri.

I vecchi metodi cercherebbero di ricalcolare il piano perfetto da zero ogni volta che arriva un nuovo ordine. Questo richiede troppo tempo (come cercare di risolvere un enorme puzzle mentre il cibo brucia).
Questo nuovo metodo utilizza un Aggiornamento Intelligente. Ricorda i prezzi dell'ultimo secondo e apporta un piccolo, rapido aggiustamento (un "warm start") basato su ciò che è appena accaduto. È come uno chef che conosce il ritmo generale della cucina e deve solo affinare leggermente i suoi movimenti per il nuovo ordine, invece di dover imparare a cucinare di nuovo ogni volta.

4. Il Menù Multi-Obiettivo

La parte migliore è che il manager della cucina può cambiare il "menù" degli obiettivi istantaneamente senza ricostruire la cucina.

Serve velocità? Il manager alza il "prezzo" del tempo di attesa. Il router darà priorità all'uscita veloce del cibo, anche se la cucina si affolla un po'.
Serve efficienza? Il manager alza il "prezzo" dello spazio sprecato. Il router impacchetterà gli ordini strettamente per fare più cose, anche se alcuni clienti dovranno aspettare un po' di più.
Bisogna sistemare i clienti più lenti? Il manager può dire al sistema di proteggere specificamente la "coda" (l'1% degli ordini più lenti) in modo che nessuno venga lasciato indietro.

I Risultati

Gli autori hanno testato questo sistema di "Prezzo Intelligente" in una simulazione di una massiccia cucina AI. Hanno confrontato il sistema con le vecchie regole della "fila più corta".

Il Risultato: Il nuovo sistema è stato molto più bravo a bilanciare i compromessi. Poteva rendere la cucina più veloce o più efficiente a seconda di ciò che il manager desiderava, senza rompere il sistema.
Il Quadro Generale: Il documento sostiene che l'uso di questo approccio matematico "basato sulla scienza" è superiore alle euristiche basate su "tentativi ed errori" attualmente utilizzate nella maggior parte dei sistemi AI. Fornisce al sistema un cervello che comprende il vero costo delle risorse, piuttosto che limitarsi a seguire una semplice regola.

In breve: Invece di inviare ciecamente gli ordini al primo chef disponibile, questo sistema agisce come un manager intelligente che sa esattamente quanto vale ogni secondo di tempo e ogni centimetro di spazio sul banco, assicurando che la cucina funzioni perfettamente indipendentemente da quanto possa diventare frenetica l'ora di punta.

Sintesi Tecnica: Programmazione Lineare Online per il Routing Multi-Obiettivo nel Servicing di LLM

1. Definizione del Problema

Il documento affronta la sfida del routing delle richieste online nei sistemi di serving di Large Language Models (LLM). In questi sistemi, le richieste in arrivo devono essere smistate a worker di decodifica parallela sotto vincoli rigorosi:

Vincoli Accoppiati nel Tempo: Le richieste consumano risorse (slot di batch e memoria della KV-cache) continuamente durante l'intera durata della decodifica. Una richiesta ammessa al tempo $t$ occupa capacità fino al suo completamento, creando un problema di allocazione delle risorse complesso e dipendente dal tempo.
Compromessi Multi-Obiettivo: I sistemi devono bilanciare obiettivi di livello di servizio (SLO) contrastanti, tra cui throughput, latenza end-to-end (EEL), time-to-first-token (TTFT) e latenza di coda (ad esempio, il 99° percentile). Questi obiettivi sono spesso in tensione; ad esempio, massimizzare il throughput tramite un batching aggressivo spesso degrada la latenza.
Limitazioni degli Euristici Correnti: I sistemi di produzione esistenti (ad esempio, vLLM) e i simulatori (ad esempio, Vidur) si affidano a euristici come Round-Robin, Join-Shortest-Queue (LOR) o scelte Power-of- $d$ . Questi metodi mancano di obiettivi di ottimizzazione espliciti, offrono un controllo limitato sui trade-off degli SLO e non tengono conto della natura eterogenea e incerta delle lunghezze di decodifica degli LLM.

2. Metodologia

Gli autori propongono un framework che formula il routing degli LLM come un problema di Programmazione Lineare Online (OLP), sfruttando tecniche di ricerca operativa per derivare una politica di controllo computazionalmente efficiente.

A. Formulazione Matematica

Modello: Il sistema è modellato su un orizzonte temporale discreto con dispositivi di decodifica parallela. Le richieste arrivano sequenzialmente con footprint di prefill noti e lunghezze di decodifica previste (ma potenzialmente imprecise).
Vincoli: La formulazione impone due vincoli critici per ogni dispositivo per ogni istante temporale:
1. Dimensione del Batch: Un numero massimo di richieste attive ( $B$ ).
2. Capacità della KV-Cache: Un budget di memoria massimo ( $M$ ) per le richieste attive.
Funzione Obiettivo: Gli autori definiscono una funzione di ricompensa lineare per ogni decisione di routing $(j, g, k)$ $(j, g, k)$ (assegnazione della richiesta $j$ $j$ al dispositivo $g$ $g$ al tempo $k$ $k$ ). Questa ricompensa è una somma pesata di:
- Throughput (token elaborati).
- Latenza negativa (minimizzazione di EEL e TTFT).
- Queries Per Second (QPS).
- Metriche di coda (modellate tramite ricompense indicatori per le richieste che soddisfano specifici limiti di latenza).
- Insight Chiave: Le metriche aggregate come la latenza di coda sono decomposte in incentivi per singola richiesta utilizzando funzioni indicatrici, permettendo loro di essere ottimizzate all'interno di un framework lineare.

B. Design dell'Algoritmo: Controllo del Prezzo d'Asta (Bid-Price Control)

Risolvere l'OLP completo ad ogni millisecondo è computazionalmente impraticabile. Invezione, gli autori derivano una politica di Controllo del Prezzo d'Asta basata sulla dualità della LP:

Variabili Duali (Prezzi Ombra): Le variabili duali $p_i$ rappresentano il "prezzo ombra" o il costo opportunità delle risorse (slot di batch e KV-cache) in momenti e dispositivi specifici. Un alto prezzo ombra indica una congestione anticipata.
Regola Decisionale: Una richiesta viene ammessa se il suo beneficio pesato rispetto agli SLO supera il suo costo delle risorse imputato (calcolato come il prodotto scalare del vettore di utilizzo delle risorse e gli attuali prezzi ombra).
Apprendimento Online (SAA): Per gestire la natura stocastica degli arrivi e delle previsioni, i prezzi ombra sono appresi online utilizzando un approccio di Approssimazione Media Campionaria (SAA). L'obiettivo duale viene minimizzato su una cronologia di azioni osservate.
Aggiornamenti Efficienti: Per soddisfare le latenze decisionali nell'ordine dei millisecondi, gli autori impiegano un gradiente a mini-batch proiettato con warm-start. Invece di risolvere il problema duale da zero, l'algoritmo aggiorna il vettore dei prezzi incrementalmente sulla base di un piccolo batch di dati storici. Ciò garantisce un tempo di esecuzione prevedibile (1–2 ms per periodo su una CPU).

3. Contributi Chiave

Framework di Ottimizzazione Multi-Obiettivo: Il primo framework che formula il routing degli LLM come un OLP con vincoli di batch e KV-cache esplicitamente accoppiati nel tempo. Esso decompone gli SLO aggregati (inclusa la latenza di coda) in ricompense per singola richiesta adatte all'ottimizzazione online.
Algoritmo Bid-Price Efficiente: Una politica computazionalmente trattabile che traccia l'evoluzione dei prezzi ombra duali online senza dover risolvere una LP completa ad ogni step, soddisfacendo i rigorosi requisiti di latenza del serving degli LLM.
Controllo Interpretabile dei Trade-off: Il framework fornisce agli operatori "manopole" trasparenti (pesi dell'obiettivo) per spostare sistematicamente le prestazioni lungo la frontiera di Pareto. I prezzi ombra servono anche come strumenti diagnostici per identificare se gli slot di batch o la KV-cache siano l'attuale collo di bottiglia.

4. Risultati Sperimentali

Gli autori hanno integrato il loro router nel simulatore Vidur e lo hanno valutato contro i baseline standard (Round-Robin, LOR, Random, Power-of-2) sotto vari carichi di lavoro (dati reali LMSYS-Chat-1M e rapporti P/D sintetici).

Guadagni di Prestazione: Il metodo proposto ha dimostrato miglioramenti sostanziali rispetto ai baseline in molteplici regimi di SLO.
- In scenari di previsione rumorosi (errore del 20%), l'algoritmo ha ottenuto una riduzione del 45,75% nella EEL media e una riduzione del 42,49% nella P95 EEL rispetto a Round-Robin.
- Ha superato significativamente gli euristici nelle metriche di latenza di coda (P99 EEL e TTFT).
Robustezza: La politica è rimasta efficace anche con previsioni della lunghezza di decodifica imperfette, poiché gli aggiornamenti online dei prezzi si adattano agli errori di stima.
Adattabilità: Nei carichi di lavoro non stazionari (picchi improvvisi di carico), il router si è adattato rapidamente utilizzando un meccanismo di finestra scorrevole per gli aggiornamenti della cronologia, mantenendo prestazioni superiori.
Tuning dei Pesi: Gli esperimenti hanno confermato che l'aggiustamento dei pesi dell'obiettivo consente agli operatori di dare priorità a metriche specifiche (ad esempio, minimizzare la latenza media rispetto al controllo rigoroso della latenza di coda) con risultati prevedibili.

5. Significato e Rivendicazioni

Il documento afferma che un approccio di ottimizzazione basato sulla scienza supera il routing basato su euristici nel serving degli LLM.

Unione di Comunità: Stabilisce un ponte principale tra la comunità della ricerca operativa (allocazione delle risorse online, controllo del prezzo d'asta) e la comunità dei sistemi LLM.
Insight sul Design dei Sistemi: Il framework rivela intuizioni strutturali, come l'uso dei prezzi ombra per diagnosticare i colli di bottiglia delle risorse (batch vs. memoria) e consentire il controllo dell'ammissione consapevole degli SLO durante il sovraccarico.
Applicabilità Pratica: Sebbene l'integrazione completa in produzione sia indicata come lavoro futuro, i risultati dimostrano che il routing basato sull'ottimizzazione è fattibile su scala millisecondo e fornisce una base per il design sistematico delle policy piuttosto che per un tuning ad hoc.

Gli autori rimangono modesti riguardo all'immediata implementazione in produzione, riconoscendo le sfide legate all'integrazione con i motori di serving (ad esempio, vLLM), alla gestione della preemption e alla coordinazione in ambienti distribuiti. Tuttavia, sostengono che il framework fornisca una base necessaria per la ricerca futura all'intersezione tra ricerca operativa e sistemi di machine learning.