💬 NLP

Tokenisation over Bounded Alphabets is Hard

Questo articolo dimostra che la tokenizzazione su alfabeti limitati, inclusi i casi binario e unario, è fondamentalmente NP-completa e APX-hard, stabilendo che la sua intrattabilità computazionale è una barriera inerente piuttosto che un artefatto di grandi alfabeti di input e spiegando la necessità di approcci euristici negli attuali algoritmi pratici.

Autori originali: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Pubblicato 2026-08-11

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover inviare un messaggio segreto a un amico, ma l'unico modo per farlo è scomporre le tue parole in piccoli pezzi pre-approvati. Se invii "superduper", potresti doverlo dividere in "super" e "duper" invece che nella parola intera, perché il dizionario del tuo amico contiene solo quei due pezzi. Questo è il cuore della tokenizzazione, il primo passo per insegnare ai computer a comprendere il linguaggio umano. Prima che un computer possa leggere una frase, deve frammentarla in questi "token" gestibili (come mattoncini Lego). L'obiettivo è scomporre il testo in modo da utilizzare il minor numero possibile di mattoncini, rendendo il messaggio più breve e veloce da inviare. Questo si chiama compressione. Se riesci a comprimere un libro in meno mattoncini, il computer potrà leggerlo più velocemente e imparare da esso in modo più efficiente. Per anni, gli scienziati hanno costruito algoritmi astuti e avidi — come un bambino che afferra il pezzo Lego più grande che riesce a trovare — per fare questo sminuzzamento automaticamente. Ma una grande domanda è rimasta sospesa: esiste un modo perfetto, matematicamente ottimale, per scomporre qualsiasi testo, o siamo costretti a fare ipotesi "abbastanza buone"?

Questo articolo, intitolato "Tokenisation Over Bounded Alphabets Is Hard", si immerge nelle profondità di questa domanda. Gli autori, un team di ricercatori dell'ETH di Zurigo e dell'Università di Sofia, si sono posti l'obiettivo di dimostrare se trovare quel metodo di scomposizione perfetto sia in realtà un incubo per i computer, anche quando le regole sono semplici. Si concentrano su due modi principali di scomporre: la Tokenizzazione Diretta, dove scegli il miglior set di mattoncini Lego (un vocabolario) tutto in una volta, e la Tokenizzazione Bottom-Up, dove parti da singole lettere e continui a incollare coppie finché non esaurisci la colla (merge). Il grande colpo di scena della loro storia è che testano questi metodi non sull'alfabeto infinito e caotico di tutti i possibili suoni umani, ma sui piccoli set fissi che effettivamente usiamo nei computer: il binario (solo 0 e 1, come un interruttore della luce) e l'unario (un singolo simbolo, come una fila di perline identiche).

La scoperta principale dell'articolo è un risonante "No, non puoi trovare facilmente la soluzione perfetta". Gli autori dimostrano che anche con gli alfabeti più semplici possibili — come un mondo fatto solo di zeri e uno — trovare il modo ottimale di comprimere il testo è NP-completo e APX-hard. In parole povere, questo significa che non importa quanta potenza di calcolo ci si metta, non esiste un algoritmo veloce ed efficiente che possa garantire il miglior risultato possibile. Non è solo che il problema è difficile; è che è fondamentalmente difficile. L'articolo esclude esplicitamente l'idea che la difficoltà derivi dalla complessità del linguaggio umano o da alfabeti enormi. Al contrario, dimostrano che la barriera esiste anche negli scenari più semplici e ristretti. Inoltre, dimostrano che non è nemmeno possibile arrivare "abbastanza vicino" alla risposta perfetta in un tempo ragionevole; non esiste uno schema di approssimazione in tempo polinomiale (PTAS) che possa avvicinarsi arbitrariamente alla soluzione ottimale, a meno che un grande mistero matematico (P = NP) non venga risolto.

I ricercatori affrontano anche il caso unario, dove l'alfabeto ha un solo simbolo (pensa a un messaggio composto interamente dalla lettera "a"). Potresti pensare: "Se ho un solo carattere, quanto può essere difficile?". Sorprendentemente, dimostrano che anche qui, trovare il modo ottimale di scomporre il testo è fortemente NP-completo. Si tratta di un risultato matematico pesante che suggerisce che la difficoltà non è solo un capriccio di grandi set di dati; è impressa nella logologia stessa del tentativo di comprimere il testo in modo ottimale.

Cosa significa tutto questo per il futuro? L'articolo non offre un nuovo algoritmo magico per risolvere il problema. Al contrario, spiega perché gli strumenti che usiamo oggi, come BPE (Byte-Pair Encoding) e UnigramLM, sono costretti a essere euristici — ovvero utilizzano scorciatoie intelligenti e supposizioni piuttosto che calcolare la risposta perfetta. Gli autori sostengono che, poiché la risposta perfetta è computazionalmente impossibile da trovare rapidamente, i ricercatori dovrebbero smettere di inseguire il "sacro Graal" del tokenizer ottimale e concentrarsi invece sulla costruzione di migliori metodologie di approssimazione provabilmente valide. La porta della perfezione è chiusa a chiave e la chiave non esiste; la cosa migliore che possiamo fare è imparare a scegliere il miglior grimaldello a nostra disposizione.

Problematica
Recenti lavori teorici hanno stabilito che trovare un tokenizzatore ottimale per un dataset è un problema NP-completo. Tuttavia, questi risultati precedenti si basano sull'assunto che la tokenizzazione operi su alfabeti di dimensioni illimitate. Nella pratica del natural language processing, i tokenizzatori operano su alfabeti di dimensione fissa e limitata (ad esempio, byte con dimensione 256, caratteri Unicode con dimensione ~170.000, o stringhe binarie/di bit con dimensione 2). Rimane una questione aperta se l'intrattabilità computazionale della tokenizzazione persista quando la dimensione dell'alfabeto è limitata da una costante. Questo articolo affronta tale lacuna analizzando la complessità della tokenizzazione su alfabeti limitati, investigando specificamente se i tokenizzatori ottimali possano essere trovati efficientemente per alfabeti binari (dimensione 2) e unari (dimensione 1).

Metodologia
Gli autori definiscono il problema della tokenizzazione $n$ -aria, dove l'alfabeto di input $\Sigma$ ha dimensione $n$ . Analizzano due varianti naturali di tokenizzazione:

Tokenizzazione Diretta: Trovare un vocabolario $S$ di dimensione $K$ che, quando applicato in modo ottimale a un dataset, minimizzi la lunghezza totale compressa.
Tokenizzazione Bottom-up: Trovare una sequenza di $K$ operazioni di fusione (merge) che, quando applicate sequenzialmente a un dataset, minimizzino la lunghezza totale compressa.

La funzione obiettivo utilizzata è la lunghezza compressa (il numero totale di token dopo la codifica), che correla con i costi di addestramento e inferenza dei modelli. Gli autori impiegano tecniche standard di complessità teorica per stabilire l'indurità:

NP-Hardness: Dimostrata tramite riduzioni polinomiali da problemi noti come NP-hard (specificamente 3-OCC-MAX2SAT e Vertex Cover) ai problemi decisionali di tokenizzazione.
APX-Hardness: Dimostrata tramite L-riduzioni (riduzioni che preservano l'approssimazione) da problemi APX-completi. Ciò dimostra che i problemi non appartengono alla classe PTAS (Polynomial-Time Approximation Scheme), il che significa che non possono essere approssimati arbitrariamente bene in tempo polinomiale a meno che P $\neq$ NP.
Problemi Gap: Gli autori definiscono versioni gap dei problemi per derivare costanti esplicite di durezza dell'approssimazione.

Contributi Chiave e Risultati

La Tokenizzazione Binaria è APX-Hard:
Il documento prova che sia la tokenizzazione diretta binaria che la tokenizzazione bottom-up binaria sono APX-hard.

Caso Diretto: Si dimostra che la tokenizzazione diretta binaria non può essere approssimata in tempo polinomiale con un rapporto di approssimazione $\rho < 1.000002$ (a meno che P $\neq$ NP).
Caso Bottom-up: Allo stesso modo, la tokenizzazione bottom-up binaria è APX-hard con una costante di durezza $\rho < 1.0000001$ .
Questi risultati implicano che anche per l'alfabeto non banale più semplice (binario), trovare un tokenizzatore ottimale è computazionalmente intrattabile, e nessun algoritmo in tempo polinomiale può garantire un'approssimazione arbitrariamente vicina all'ottimo.

La Tokenizzazione Unaria è Fortemente NP-Completa:
Gli autori investigano il caso unario (dimensione dell'alfabeto 1), che è teoricamente la variante "più facile".

Dimostrano che la tokenizzazione diretta unaria è fortemente NP-completa. Ciò è ottenuto tramite una riduzione dal problema Vertex Cover. La prova stabilisce che l'indurità è intrinseca alla struttura del problema e non un artefatto della rappresentazione dell'input (stringa rispetto a lunghezza della stringa).
Per la tokenizzazione bottom-up unaria, il documento stabilisce che una variante nota come Optimal Pair Encoding (OPE) è (almeno) debolmente NP-completa, tramite una riduzione dal problema delle catene di addizione (Addition Chain). La complessità della standard tokenizzazione bottom-up unaria rimane una questione aperta in questo lavoro.

Gerarchia di Indurità:
Il documento stabilisce una chiara gerarchia: se la tokenizzazione $n$ -aria è difficile, allora la tokenizzazione $n'$ -aria per ogni $n' > n$ è altrettanto difficile. Di conseguenza, i risultati di indurità per i casi binario e unario si estendono trivialmente a tutti gli altri alfabeti limitati più grandi (inclusi gli alfabeti byte e Unicode).

Significatività e Rivendicazioni
Il documento afferma che questi risultati alterano fondamentalmente la comprensione della complessità della tokenizzazione. Provando che la tokenizzazione rimane difficile anche su alfabeti unari e binari, gli autori dimostrano che l'intrattabilità computazionale non è un artefatto di grandi alfabeti o di complesse operazioni di fusione. Al contrario, è una barriera fondamentale inerente al problema di comprimere i dati tramite tokenizzazione.

Queste scoperte forniscono una giustificazione teorica del perché gli attuali algoritmi pratici, come Byte-Pair Encoding (BPE) e UnigramLM, si affidino a euristiche e strategie greedy piuttosto che all'ottimizzazione esatta. Il documento conclude che la ricerca futura dovrebbe concentrarsi sullo sviluppo di algoritmi di approssimazione provabilmente buoni o sul rilassamento dei vincoli del problema, poiché trovare tokenizzatori ottimali esatti è probabilmente impossibile per qualsiasi dimensione di dataset non banale.

Articoli simili