Riepilogo Tecnico: XGrammar-2

Enunciato del Problema

Gli agenti moderni basati su Large Language Model (LLM) fanno sempre più affidamento sulla generazione strutturata dinamica, in particolare per le chiamate agli strumenti e i protocolli di risposta. A differenza dei tradizionali compiti di generazione strutturata, dove lo schema di output è statico e noto in anticipo, i carichi di lavoro agentici presentano una significativa dinamicità strutturale:

1. Dinamicità Inter-Request: Ogni richiesta può esporre un diverso insieme di strumenti e schemi (spesso con controllo degli accessi per strumento), portando a uno spazio combinatoriamente vasto di possibili grammatiche di output. I motori esistenti che memorizzano nella cache intere grammatiche a livello di richiesta diventano inefficaci, costringendo a costosi pre-processing per richiesta e aumentando il Time-to-First-Token (TTFT).
2. Dinamicità Intra-Request: All'interno di una singola richiesta, il modello deve passare dal testo libero a sotto-grammatiche strutturate in base a trigger (ad esempio, un nome specifico di strumento o un tag di canale). Esprimere queste commutazioni condizionali utilizzando la forma standard Backus-Naur (BNF) o la BNF Estesa (EBNF) è ingombrante, inefficiente e scala male con il numero di strumenti.

I metodi esistenti di decodifica vincolata (ad esempio, XGrammar, Outlines, llguidance) faticano a gestire queste dinamiche. Richiedono o la compilazione completa della grammatica in anticipo (proibitiva per insiemi di strumenti dinamici) o mancano di meccanismi efficienti per gestire l'intercalazione di testo libero e vincoli strutturati all'interno di un singolo flusso di generazione.

Metodologia

XGrammar-2 è un motore di generazione strutturata progettato specificamente per carichi di lavoro agentici dinamici. La sua architettura si fonda su due principi di progettazione fondamentali: supporto di primo livello per la commutazione strutturata attivata da tag e riutilizzo granulare tra richieste con strutture di output diverse.

1. TagDispatch: Semantica di Instradamento Dinamico

Per affrontare la dinamicità intra-request, XGrammar-2 introduce TagDispatch, un intrinseco della grammatica che consente una commutazione efficiente tra testo libero e sotto-grammatiche strutturate.

• Meccanismo: TagDispatch è parametrizzato da una lista di coppie tag-grammatica $(t_i, G_i)$ e da un insieme di stringhe di arresto.
• Operazione: Il motore opera in due modalità:
  • Modalità di Instradamento (Dispatching): Il motore accetta testo ordinario utilizzando un automata Aho–Corasick (AC) per abbinare in modo incrementale i tag registrati al testo generato.
  • Modalità Instradata (Dispatched): Al verificarsi di un match con un tag, il motore passa alla sotto-grammatica corrispondente $G_i$. Una volta completata $G_i$, il controllo ritorna alla modalità di instradamento.
• Vantaggio: Questo evita la necessità di codificare logica condizionale complessa in regole EBNF massive, riducendo significativamente le dimensioni della grammatica e la complessità di compilazione.

2. Cache Cross-Grammatica

Per affrontare la dinamicità inter-request, XGrammar-2 implementa una Cache Cross-Grammatica per riutilizzare le cache di mask dei token tra grammatiche diverse che condividono sotto-strutture comuni.

• Sfida: Determinare se due Macchine a Stati Finiti (FSM) sono equivalenti è difficile quando contengono riferimenti a regole e cicli. Inoltre, le cache di mask dei token dipendono non solo dalla struttura FSM ma anche da come tale FSM è referenziata (espansione del contesto).
• Soluzione: Il sistema utilizza un algoritmo di hashing gerarchico:
  • Costruisce un grafo di riferimento FSM.
  • Per le porzioni acicliche, calcola hash strutturali dal basso verso l'alto, incorporando gli hash delle FSM referenziate.
  • Per i riferimenti ciclici, utilizza hash provvisori seguiti da un affinamento dell'hash del ciclo per garantire identificatori strutturali univoci.
• Strategia di Riutilizzo: Quando viene incontrato un nuovo stato di grammatica, il sistema controlla il pool di cache globale. Se viene trovato un match perfetto (stessa FSM e stesso lookahead), la cache viene riutilizzata. Se esiste solo un match parziale (stessa FSM, lookahead diverso), il sistema ricontrolla i token incerti e aggiorna la cache.

3. Cache di Mask dei Token Adattiva Basata su Earley

Abbandonando gli Automi a Pila (PDA) utilizzati nelle versioni precedenti, XGrammar-2 utilizza un parser Earley per la sua cache di mask dei token adattiva.

• Razionale: Gli stati PDA possono crescere esponenzialmente in grammatiche non deterministiche. Il parser Earley mantiene un insieme di stati di parsing parziali (frontiera) più efficiente per grammatiche libere dal contesto complesse.
• Implementazione: La cache è costruita solo per stati scansionabili (dove il simbolo successivo è un terminale). Gli stati non scansionabili vengono espansi tramite operazioni di previsione e completamento a runtime. I token sono categorizzati come accettati, rifiutati o dipendenti dal contesto, con quest'ultimi che richiedono controlli del contesto a runtime.

4. Compilazione Just-In-Time (JIT)

Per mitigare l'alto costo di compilazione di grammatiche grandi e dinamiche:

• Strategia: Invece di materializzare l'intera cache di mask dei token in anticipo, XGrammar-2 impiega un sistema JIT configurabile.
• Esecuzione: Durante la fase di prefilling, il sistema stima il costo di generazione delle cache per stati specifici. Prioritizza la compilazione degli stati $K$ più dispendiosi in termini di tempo durante il prefilling, sovrapponendo la compilazione al prefilling. Gli stati rimanenti vengono compilati su richiesta durante la fase di decodifica, sovrapponendo la generazione della mask alla decodifica. Questo mira a nascondere la latenza di compilazione.

5. Compressione dello Stato di Ripetizione

Per gestire le strutture di ripetizione comuni negli schemi JSON (ad esempio, MinLength, MaxItems):

• Problema: L'espansione ingenua delle regole di ripetizione porta a un aumento lineare degli stati della grammatica rispetto alla quantità di ripetizioni.
• Soluzione: Il motore comprime gli stati di ripetizione. Per ampi intervalli di ripetizione, trasforma la struttura in una sequenza di una regola base ripetuta $t$ volte, seguita da uno stato compresso che rappresenta l'intervallo residuo. Questo limita il numero di stati a una costante indipendentemente dal limite di ripetizione, riducendo significativamente le dimensioni della cache e l'incertezza.

Risultati Chiave

Gli esperimenti sono stati condotti utilizzando dataset come BFCL-v3 e JSONSchemaBench, confrontando XGrammar-2 con motori all'avanguardia (XGrammar, llguidance, Outlines) su vari modelli (Qwen, serie Llama).

• Velocità di Compilazione: XGrammar-2 raggiunge una compilazione oltre 6 volte più veloce rispetto ai precedenti motori di generazione strutturata in contesti dinamici. Ad esempio, mentre XGrammar richiedeva >1000ms per compilare grammatiche dinamiche, XGrammar-2 ha raggiunto ~10ms.
• Overhead End-to-End: Il sistema comporta un overhead end-to-end quasi nullo nei moderni sistemi di servizio LLM. Negli scenari di chiamata di funzioni, il divario di latenza tra generazione vincolata (XGrammar-2) e generazione non vincolata è stato inferiore al 6%.
• Throughput: XGrammar-2 ha dimostrato un throughput di token superiore rispetto a XGrammar attraverso diverse dimensioni di batch e scale di modelli (ad esempio, un miglioramento del throughput di 2,5 volte su Llama-3.2-1B con batch size 16).
• Scalabilità: L'overhead di memoria della cache cross-grammatica rimane basso e scala con il numero totale di strumenti unici utilizzati piuttosto che con il numero di richieste, prevenendo l'esplosione della memoria in ambienti dinamici.
• Ablazione: La rimozione di JIT ha aumentato il tempo di pre-processing di 8,1 volte; la rimozione della Cache Cross-Grammatica ha aumentato significativamente il tempo di generazione della mask; la Compressione dello Stato di Ripetizione ha ridotto il tempo di pre-processing di 99,6 volte per i casi di ripetizione a coda lunga.

Significato e Affermazioni

Il documento afferma che XGrammar-2 fornisce un'evoluzione necessaria per i sistemi di servizio LLM per supportare applicazioni agentiche. Disaccoppiando la gestione di insiemi di strumenti dinamici dalla compilazione di grammatiche statiche, abilita:

1. Affidabilità: Applicazione rigorosa della validità strutturale (ad esempio, formato di risposta OpenAI Harmony, schemi di chiamata degli strumenti) senza fare affidamento su correzioni post-hoc.
2. Efficienza: La capacità di servire carichi di lavoro dinamici con costi di compilazione e runtime paragonabili a quelli dei carichi di lavoro statici.
3. Adozione: Il motore è stato integrato in framework open-source come SGLang e vLLM, dimostrandone la fattibilità pratica in sistemi di inferenza di livello produzione.

Gli autori posizionano XGrammar-2 non come sostituto delle tecniche di addestramento del modello, ma come un motore di inferenza complementare che può essere combinato con strategie esistenti di fine-tuning o prompting per garantire un output strutturato e robusto in scenari agentici complessi.