Riepilogo Tecnico: Tokenizzazione con Alberi di Divisione (ToaST)

Enunciato del Problema

La tokenizzazione è un passaggio fondamentale nell'elaborazione del linguaggio naturale, tuttavia i metodi esistenti spesso si basano su euristiche greedy che potrebbero non ottimizzare la compressione o le prestazioni a valle. Sebbene la Byte Pair Encoding (BPE) minimizzi il numero di token tramite una strategia di fusione greedy, essa rappresenta un'approssimazione euristica. Lavori precedenti hanno stabilito che trovare un tokenizzatore che massimizzi la compressione è NP-completo, anche su alfabeti limitati. Inoltre, la relazione tra compressione e prestazioni nei compiti a valle rimane dibattuta; mentre alcuni studi suggeriscono una correlazione, altri sostengono che la compressione da sola non è sufficiente a spiegare la qualità della tokenizzazione. Le alternative esistenti, come UnigramLM o PathPiece, utilizzano procedure di inferenza diverse (ad esempio, inferenza top-down ablativa o inferenza del percorso più breve) ma affrontano comunque sfide nell'ottimizzazione globale e nella scalabilità computazionale.

Metodologia

Gli autori introducono la Tokenizzazione con Alberi di Divisione (ToaST), un metodo di tokenizzazione a parole che disaccoppia la costruzione dei token candidati dalla selezione del vocabolario finale. L'approccio consta di tre fasi principali:

1. Costruzione dell'Albero di Divisione

A differenza della BPE, che costruisce i token dal basso verso l'alto, o di UnigramLM, che apprende le probabilità dall'alto verso il basso, ToaST costruisce un albero binario completo per ogni pre-token unico nel corpus di addestramento, indipendentemente da qualsiasi vocabolario.

• Preprocessing: I dati di addestramento vengono suddivisi in pre-token utilizzando un'espressione regolare.
• Logica di Divisione: Per un dato pre-token, l'algoritmo lo divide ricorsivamente in due parti non vuote. Il punto di divisione è scelto in modo deterministico per massimizzare il conteggio minimo dei byte n-gram risultanti a sinistra e a destra ($\max \min(c_p, c_{p'})$) basandosi su statistiche n-gram precalcolate dal corpus.
• Struttura: Questo processo continua fino a quando le foglie sono byte singoli. I nodi di questi alberi formano l'insieme di tutti i token candidati. Questa costruzione è indipendente dal vocabolario finale e non richiede un addestramento iterativo.

2. Inferenza Ricorsiva

Dato un vocabolario $V$, la tokenizzazione viene eseguita tramite una discesa ricorsiva nell'albero di divisione:

• Partendo dalla radice (l'intero pre-token), l'algoritmo verifica se il nodo corrente è in $V$.
• Se il nodo è in $V$, viene emesso come token.
• Se non lo è, l'algoritmo elabora ricorsivamente i due figli.
• Proprietà: Questa procedura garantisce che qualsiasi vocabolario contenente tutti i byte singoli necessari produca una tokenizzazione valida. Rimuovere un token dal vocabolario forza semplicemente l'inferenza a scendere ulteriormente nell'albero, senza effetti a cascata sugli altri token, a differenza dei metodi basati sulla fusione.

3. Selezione del Vocabolario tramite Programmazione Interi

L'innovazione centrale consiste nel formulare la selezione del vocabolario come un Programma Interi (IP) per minimizzare il conteggio totale dei token sul corpus di addestramento.

• Variabili: Variabili binarie $x_i$ indicano se il token candidato $i$ è nel vocabolario. Variabili binarie $z_{jk}$ indicano se il nodo $k$ nell'albero di divisione $j$ viene emesso durante l'inferenza.
• Obiettivo: Minimizzare il conteggio totale ponderato dei token emessi: $\min \sum_{j} c_j \sum_{k} z_{jk}$.
• Vincoli:
  • Dimensione del Vocabolario: La somma dei token selezionati deve essere uguale alla dimensione target $m$.
  • Copertura: Per ogni percorso da una foglia alla radice, deve essere selezionato esattamente un nodo (garantendo che l'intero pre-token sia coperto).
  • Coerenza: Un nodo può essere emesso ($z_{jk}=1$) solo se è nel vocabolario ($x_i=1$) e nessuno dei suoi antenati lo è.
• Risoluzione: L'IP viene rilassato a un Programma Lineare (LP). In pratica, il rilassamento LP è "quasi-integrale", il che significa che la soluzione contiene pochissimi valori frazionari. Viene applicata una semplice euristiche di arrotondamento per ottenere una soluzione intera che è provatamente quasi-ottimale (entro una frazione trascurabile dell'ottimo globale).

Contributi Chiave

1. Nuovo Framework di Tokenizzazione: ToaST introduce un approccio basato su alberi di divisione che evita le approssimazioni greedy della BPE e i vincoli specifici di inferenza di UnigramLM.
2. Ottimizzazione Globale: Formulando la selezione del vocabolario come un IP con un rilassamento LP stretto, ToaST trova un vocabolario che minimizza globalmente il conteggio dei token per un dato insieme di alberi di divisione, invece di affidarsi a decisioni greedy locali.
3. Scalabilità: Il metodo scala quadraticamente con il numero di alberi di divisione, consentendo l'elaborazione di grandi corpus (coprendo il 99% dei conteggi di pre-token) entro tempi di addestramento fattibili.
4. Design Disaccoppiato: La separazione tra la costruzione dell'albero (basata sulle statistiche del corpus) e la selezione del vocabolario (basata sull'ottimizzazione) permette estensioni flessibili, come l'incorporazione di preferenze morfologiche o a livello di carattere senza riaddestrare il modello di ottimizzazione.

Risultati Sperimentali

Gli autori hanno valutato ToaST su testo inglese utilizzando il dataset CulturaX e lo hanno confrontato con BPE, WordPiece e UnigramLM.

• Compressione: A dimensioni del vocabolario di 40.960 e superiori, ToaST riduce il numero di token di oltre l'11% rispetto a tutte le baseline. Questo è misurato in byte per token.
• Distribuzione dei Token: ToaST riduce significativamente la frequenza dei token "Foglia" (fallback a byte singolo) di 14–19 volte rispetto alle baseline a una dimensione del vocabolario di 65.536. Al contrario, produce sostanzialmente più token "Radice" (pre-token completi), indicando una migliore ritenzione delle unità semantiche.
• Efficienza di Rényi: ToaST raggiunge una maggiore efficienza di Rényi (con $\alpha=2.5$), indicando una distribuzione dei token più uniforme e meno token ad alta frequenza, il che è spesso correlato a migliori prestazioni a valle.
• Prestazioni a Valle: Negli esperimenti di addestramento di modelli linguistici da 1,5 miliardi di parametri (nanochat), ToaST ha ottenuto il punteggio CORE più alto (una media di 22 benchmark), superando le baseline dal 2,6% al 7,6%. Ha superato significativamente BPE e UnigramLM, ed è stato il miglior esecutore su 13 dei 22 compiti individuali.
• Qualità dell'Ottimizzazione: Il rilassamento LP è risultato eccezionalmente stretto. Su 128 istanze del problema, il massimo gap relativo tra la soluzione intera arrotondata e il limite LP è stato di $5.76 \times 10^{-7}$, con molte istanze completamente intere.

Significato e Affermazioni

Il documento afferma che ToaST dimostra il valore dell'ottimizzazione diretta della tokenizzazione per la compressione utilizzando un framework di ottimizzazione globale piuttosto che affidarsi a euristiche greedy. Gli autori sostengono che la compressione superiore porta a una finestra di contesto effettiva più ampia e, di conseguenza, a prestazioni a valle migliorate.

Il significato del lavoro risiede in:

• Praticità: Nonostante la complessità NP teorica della tokenizzazione ottimale, il rilassamento LP rende l'approccio computazionalmente fattibile e pratico per l'addestramento su larga scala.
• Prestazioni: I risultati empirici suggeriscono che la riduzione dell'11% nel numero di token si traduce in guadagni misurabili nelle prestazioni dei modelli linguistici (punteggio CORE), supportando l'ipotesi che una migliore compressione correla con una migliore utilità del modello.
• Flessibilità: L'architettura permette future estensioni, come la gestione di caratteri multi-byte o divisioni morfologiche, modificando la gerarchia di costruzione dell'albero senza alterare la logica di ottimizzazione del vocabolario.

Gli autori notano delle limitazioni, specificamente che gli esperimenti sono stati condotti esclusivamente su testo inglese e che l'efficacia dell'addestramento sui pre-token aggregati superiori potrebbe variare per lingue non delimitate da spazi. Dichiarano inoltre l'utilizzo di LLM per l'implementazione del codice e la generazione delle figure.