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.