Faster Superword Tokenization

Titolo: Faster Superword Tokenization (Tokenizzazione Superword più Veloce)

Autore: Craig W. Schmidt, Chris Tanner, Yuval Pinter.
Contesto: Preprint in revisione (Kensho Technologies, Ben-Gurion University).

---

1. Il Problema

L'algoritmo di Byte Pair Encoding (BPE) è lo standard per la tokenizzazione nei moderni modelli linguistici di grandi dimensioni (LLM). Tuttavia, il BPE classico presenta un limite fondamentale: i token non possono attraversare i confini di "pre-token" (segmenti iniziali come parole, punteggiatura o spazi definiti da un'espressione regolare). Questo vincolo impedisce la creazione di token che combinino più parole (es. "to be" come un'unica entità), limitando l'efficienza di compressione e la distribuzione uniforme dei token.

Algoritmi recenti come BoundlessBPE e SuperBPE hanno risolto questo problema introducendo le superword (o "supermerges"), ovvero combinazioni di pre-token adiacenti che formano frasi. Nonostante i vantaggi intrinseci (migliore compressione, efficienza di Rényi e accuratezza nei task downstream), le implementazioni originali di questi algoritmi erano impraticabili per l'addestramento su larga scala:

• BoundlessBPE: Richiedeva 4,7 giorni di CPU per addestrare su soli 1 GB di dati.
• SuperBPE: Richiedeva "alcune ore" su 100 CPU per 10 GB di dati.
• Causa principale: Le implementazioni originali mantenevano in memoria l'intero documento di pre-token per ogni istanza, impedendo l'aggregazione per frequenza e rendendo il tempo di addestramento lineare rispetto al numero totale di occorrenze dei pre-token.

2. Metodologia

Gli autori propongono una riformulazione dell'addestramento che permette l'aggregazione dei candidati di supermerge, simile a quanto avviene nel BPE classico, ottenendo un'accelerazione drastica.

A. Aggregazione dei Candidati di Supermerge

Invece di memorizzare i documenti interi, il nuovo metodo:

1. Pre-tokenizzazione Script-Specifica: Per lingue non separate da spazi (es. cinese, giapponese), divide ogni carattere in un pre-token a parte (usando regex specifiche per script). Questo evita la creazione di token invalidi composti da byte parziali di caratteri diversi (un problema noto nei tokenizer BPE standard) e crea una sequenza di pre-token candidati per le superword.
2. Identificazione dei Candidati: Un pre-token è un candidato valido per una supermerge solo se:
   • Contiene almeno una lettera Unicode (\p{L}).
   • È già tokenizzato come un singolo token (dopo la fase di BPE standard).
3. Aggregazione per Frequenza: I candidati di supermerge (sequenze di 2+ pre-token validi) vengono contati e aggregati per frequenza. Questo riduce drasticamente la quantità di dati da processare nella fase successiva, eliminando la necessità di mantenere i documenti grezzi in memoria.

B. Formulazione a Due Fasi di BoundlessBPE

Gli autori introducono una versione a due fasi di BoundlessBPE che produce risultati identici all'implementazione originale, ma con un'architettura più efficiente:

• Fase 1: Addestramento di un tokenizer BPE standard su pre-token aggregati fino a raggiungere la dimensione desiderata del vocabolario. Questo definisce quali pre-token diventano token singoli.
• Fase 2: Confronto tra le regole di merge standard della Fase 1 e i migliori candidati di supermerge (aggregati). L'algoritmo seleziona dinamicamente se applicare un merge standard o una supermerge basandosi sulla frequenza, senza bisogno di un parametro iperparametrico manuale per decidere quante superword includere.

C. Relazione con SuperBPE

Questa struttura a due fasi allinea BoundlessBPE a SuperBPE. La differenza principale è che in SuperBPE il numero di supermerge ($s$) è un iperparametro fisso, mentre nella nuova formulazione di BoundlessBPE questo numero viene determinato automaticamente nella Fase 2 in base ai dati.

D. Ottimizzazione dell'Inferenza

È stata introdotta un'ottimizzazione per l'inferenza: se un pre-token è già presente nel vocabolario come token singolo, viene lasciato invariato senza applicare le regole di merge. Questo riduce il tempo di inferenza di un fattore 2.8x (Python) e 1.6x (Rust).

3. Contributi Chiave

1. Implementazione Open Source: Rilascio di implementazioni di riferimento in Python e di una versione ad alte prestazioni in Rust per BoundlessBPE e SuperBPE.
2. Accelerazione Computazionale: Riduzione del tempo di addestramento da giorni a minuti mantenendo la stessa qualità del modello.
3. Unificazione Teorica: Dimostrazione che BoundlessBPE e SuperBPE possono essere visti come varianti dello stesso processo a due fasi, con BoundlessBPE che automatizza la scelta del numero di supermerge.
4. Gestione delle Lingue Non Spaziate: Introduzione di una strategia di pre-tokenizzazione specifica per script che previene la creazione di token corrotti (byte parziali) e abilita la formazione di superword anche in lingue come il cinese.

4. Risultati

I risultati sperimentali su un dataset di 1 GB (MiniPile) con un vocabolario di 131.072 token mostrano:

• Velocità di Addestramento:
  • BoundlessBPE: Da 4,7 giorni CPU a 603 secondi (circa 10 minuti).
  • SuperBPE: Da "alcune ore" a 593 secondi.
  • Accelerazione: Un aumento di velocità superiore a 600x rispetto alle implementazioni originali.
• Confronto BPE vs. Superword:
  • L'implementazione Rust è significativamente più veloce di quella Python (circa 3-5x per l'inferenza).
  • La maggior parte del tempo di addestramento è speso nella logica procedurale di merge e aggiornamento dei conteggi, che beneficia enormemente dell'uso di Rust.
• Qualità del Modello: I modelli prodotti dalla nuova implementazione sono identici (stesse regole di merge e vocabolario) a quelli delle versioni originali, garantendo che i benefici prestazionali downstream riportati in letteratura (es. +4% di accuratezza) siano preservati.

5. Significato e Impatto

Questo lavoro rimuove la principale barriera all'adozione delle superword: la lentezza dell'addestramento.

• Scalabilità: Permette di addestrare tokenizer basati su superword su dataset molto più grandi (molti GB o TB) in tempi ragionevoli, cosa che prima era proibitiva.
• Accessibilità: Fornisce strumenti pratici (codice Python e Rust) per la comunità di ricerca e pratica per sperimentare e utilizzare tokenizzazione avanzata senza costi computazionali eccessivi.
• Futuro: Apre la strada a ricerche future sull'impatto delle superword su modelli più grandi e su lingue diverse, sfruttando la velocità ottenuta per esplorare spazi di iperparametri più ampi.

In sintesi, il paper trasforma le superword da un'idea promettente ma computazionalmente costosa in una tecnica praticabile e scalabile per la tokenizzazione di LLM, mantenendo intatta la superiorità teorica rispetto al BPE classico.