Decoding di LLM e Grammatiche Vincolate: Un'Analisi Approfondita

Un nuovo studio esplora il processo di decoding di modelli linguistici di grandi dimensioni (LLM) quando questo è vincolato da grammatiche formali. La ricerca si concentra sull'interazione tra la distribuzione autoregressiva dei token successivi e un oracolo di raggiungibilità basato su un sistema pushdown compilato da una grammatica context-free (CFG).

Invarianza dell'Oracolo e Costi di Ambiguità

I ricercatori dimostrano un teorema di invarianza dell'oracolo: grammatiche equivalenti dal punto di vista del linguaggio inducono insiemi identici di token successivi ammissibili per ogni prefisso, e quindi maschere logit identiche. Tuttavia, queste grammatiche possono portare a spazi di stato compilati e costi di ambiguità online significativamente diversi. Viene introdotto un costo di ambiguità strutturale (SAC) left-to-right che misura la crescita incrementale della packed-parse-forest per token.

Limiti Inferiori e Ottimizzazione della Grammatica

Lo studio stabilisce limiti inferiori indipendenti dall'engine: qualsiasi engine di masking online sound, retrieval-efficient e parse-preserving deve sostenere un lavoro di Ω(t^2) per token su una specifica famiglia CFG di dimensione costante. Vengono definite classi di equivalenza di costo di decoding delle grammatiche e viene dimostrata l'esistenza di rappresentanti minimal-SAC all'interno di famiglie di rewrite limitate.

Integrazione con Architetture Moderne

I risultati vengono integrati con architetture Transformer e Mixture-of-Experts, derivando inviluppi di latenza in termini di dimensione del vocabolario, insiemi di stati attivi e ampiezza del beam. Il SAC viene collegato a modelli predittivi di performance basati su strumentazione e all'ottimizzazione automatizzata della grammatica.

Per chi valuta deployment on-premise, esistono trade-off da considerare. AI-RADAR offre framework analitici su /llm-onpremise per valutare questi aspetti.