💬 NLP

Tokenization with Split Trees

Ce papier présente ToaST, une nouvelle méthode de tokenisation de sous-mots qui utilise des arbres de division et la programmation en nombres entiers pour optimiser la sélection de vocabulaire afin de minimiser le nombre de tokens, réalisant ainsi des améliorations significatives en matière d'efficacité de compression et de performance des modèles de langage par rapport aux bases de référence existantes telles que BPE et WordPiece.

Auteurs originaux : Craig W. Schmidt, Michael Krumdick, Adam Wiemerslage, Seth Ebner, Varshini Reddy, Yuval Pinter, Chris Tanner

Publié 2026-05-22

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Craig W. Schmidt, Michael Krumdick, Adam Wiemerslage, Seth Ebner, Varshini Reddy, Yuval Pinter, Chris Tanner

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'envoyer une bibliothèque massive de livres à travers Internet, mais que votre connexion Internet est lente. Pour accélérer le transfert, vous souhaitez compresser les livres en le plus petit nombre possible de « morceaux » (tokens) sans perdre aucun sens.

Pendant longtemps, la méthode standard pour y parvenir était celle d'un constructeur de Lego qui commence par de tout petits briques individuelles (lettres) et les colle ensemble une par une, uniquement lorsqu'il voit deux briques collées ensemble fréquemment. Cette méthode, appelée BPE, est rapide et gourmande, mais elle n'est pas toujours la plus efficace. Elle pourrait coller deux briques ensemble qui n'appartiennent pas vraiment l'une à l'autre, ou manquer une occasion de coller un mot entier ensemble parce qu'elle s'est bloquée sur un plus petit morceau en premier.

L'article présente une nouvelle méthode appelée ToaST (Tokenization with Split Trees). Voici comment elle fonctionne, en utilisant quelques analogies simples :

1. L'« Arbre des Possibilités » (Split Trees)

Au lieu de coller les choses ensemble, ToaST commence par un mot entier (comme « Kentucky ») et se demande : « Si je devais couper ce mot en deux, où serait le meilleur endroit pour le faire ? »

Il examine une base de données massive sur la fréquence d'apparition de différentes parties de mots dans le monde réel. Il choisit la coupe qui divise le mot en deux pièces qui sont toutes deux très courantes. Ensuite, il prend ces deux pièces et pose la même question à nouveau. Il continue ainsi jusqu'à atteindre des lettres uniques.

L'Analogie : Imaginez que vous avez un énorme pain non coupé. Au lieu de le trancher au hasard, vous consultez une carte indiquant où les gens mangent habituellement du pain. Vous trouvez l'endroit parfait pour le trancher afin que les deux moitiés soient de tailles populaires. Ensuite, vous prenez ces moitiés et les tranchez à nouveau aux endroits les plus populaires. Vous vous retrouvez avec un arbre généalogique de chaque façon possible de couper ce mot, du pain entier jusqu'aux miettes individuelles.

2. Le « Menu Intelligent » (Sélection de Vocabulaire)

Maintenant, vous avez un arbre de millions de coupes possibles. Vous ne pouvez pas les utiliser toutes ; vous n'avez de la place que pour un nombre spécifique d'« articles de menu » (une taille de vocabulaire, disons 40 000).

Les anciennes méthodes choisissaient simplement les coupes les plus populaires. ToaST utilise un optimiseur mathématique (un programme à nombres entiers) pour jouer à un jeu de « Et si ? » :

Si je choisis ce gros morceau de « Kentucky » comme un seul token, combien de morceaux au total économise-t-on ?
Si je choisis « Kent » et « ucky » séparément, cela économise-t-il plus d'espace ailleurs ?

Il calcule la combinaison parfaite de coupes qui aboutit au nombre total de morceaux le plus faible nécessaire pour écrire toute la bibliothèque. C'est comme un chef planifiant un menu non pas uniquement sur la base de ce qui est populaire, mais sur la façon de servir le plus de clients avec le moins de plats au total.

3. Le « Tour de Magie » (L'Inférence)

Une fois le menu défini, la lecture du texte est rapide. Lorsque l'ordinateur voit « Kentucky », il regarde le sommet de l'arbre.

« Kentucky » est-il sur le menu ? Oui ? Super, envoyez-le comme un seul token.
« Kentucky » est-il sur le menu ? Non ? Alors regardez au niveau suivant. « Kent » est-il sur le menu ? Oui ? Envoyez « Kent », puis regardez de l'autre côté pour « ucky ».

Parce que l'arbre a été construit avant que le menu ne soit choisi, le chemin est toujours clair. Il n'y a pas de règles confuses ni de scénarios du type « que se passe-t-il si je change cela ? ».

Pourquoi est-ce mieux ?

L'article affirme que pour de grandes bibliothèques (tailles de vocabulaire de 40 000+), ToaST est nettement supérieur aux anciennes méthodes :

Compression : Il réduit le nombre de morceaux nécessaires de plus de 11 %. Pensez-y comme à la réduction d'un document de 100 pages à 89 pages sans perdre un seul mot.
Efficacité : Il utilise moins de tokens « lettre unique » (comme envoyer uniquement la lettre 'y' ou 'u'). Cela rend le flux de données plus fluide et plus efficace.
Performance : Lorsqu'ils ont entraîné un modèle de langage (un cerveau qui apprend à parler) en utilisant cette nouvelle méthode, le modèle a mieux performé lors des tests. Il a obtenu des scores plus élevés sur des tâches de raisonnement et de logique par rapport aux modèles entraînés avec les anciennes méthodes.

La Conclusion

ToaST est une nouvelle façon de décomposer le texte. Au lieu de coller aveuglément des morceaux ensemble, il cartographie chaque façon possible de couper un mot, puis utilise un puissant solveur mathématique pour choisir l'ensemble absolu de coupes le meilleur afin de minimiser la quantité totale de données. Le résultat est une façon plus efficace, plus rapide et plus intelligente pour les ordinateurs de lire et d'écrire le langage.

Note : L'article a uniquement testé cela sur du texte anglais. Il ne prétend pas que ces résultats s'appliquent à d'autres langues pour l'instant, ni ne discute des utilisations médicales ou cliniques. Les améliorations concernent strictement l'efficacité du traitement du texte et la performance des modèles de langage sur des benchmarks standard.

Résumé technique : Tokenisation avec des arbres de division (ToaST)

Énoncé du problème

La tokenisation est une étape fondamentale du traitement du langage naturel, pourtant les méthodes existantes reposent souvent sur des heuristiques gloutonnes qui peuvent ne pas optimiser la compression ou les performances en aval. Bien que le codage par paires d'octets (BPE) minimise le nombre de tokens via une stratégie de fusion gloutonne, il s'agit d'une approximation heuristique. Des travaux antérieurs ont établi que trouver un tokeniseur maximisant la compression est un problème NP-complet, même sur des alphabets bornés. De plus, la relation entre compression et performances des tâches en aval reste débattue ; si certaines études suggèrent une corrélation, d'autres affirment que la compression seule est insuffisante pour expliquer la qualité de la tokenisation. Les alternatives existantes, telles que UnigramLM ou PathPiece, utilisent des procédures d'inférence différentes (par exemple, inférence descendante ablative ou inférence par chemin le plus court) mais continuent de faire face à des défis d'optimisation globale et de mise à l'échelle computationnelle.

Méthodologie

Les auteurs introduisent la Tokenisation avec des Arbres de Division (ToaST), une méthode de tokenisation de sous-mots qui découple la construction des tokens candidats de la sélection du vocabulaire final. L'approche se compose de trois étapes principales :

1. Construction de l'arbre de division

Contrairement au BPE, qui construit les tokens de bas en haut, ou à UnigramLM, qui apprend les probabilités de haut en bas, ToaST construit un arbre binaire complet pour chaque prétoken unique du corpus d'entraînement, indépendamment de tout vocabulaire.

Prétraitement : Les données d'entraînement sont divisées en prétokens à l'aide d'une expression régulière.
Logique de division : Pour un prétoken donné, l'algorithme le divise récursivement en deux parties non vides. Le point de division est choisi de manière déterministe pour maximiser le nombre minimum des n-grammes d'octets résultants à gauche et à droite ( $\max \min(c_p, c_{p'})$ ) sur la base de statistiques d'octets n-grammes précalculées issues du corpus.
Structure : Ce processus se poursuit jusqu'à ce que les feuilles soient des octets uniques. Les nœuds de ces arbres forment l'ensemble de tous les tokens candidats. Cette construction est indépendante du vocabulaire final et ne nécessite aucun entraînement itératif.

2. Inférence récursive

Étant donné un vocabulaire $V$ , la tokenisation est effectuée par une descente récursive dans l'arbre de division :

En partant de la racine (le prétoken complet), l'algorithme vérifie si le nœud actuel se trouve dans $V$ .
Si le nœud est dans $V$ , il est émis comme un token.
Sinon, l'algorithme traite récursivement les deux enfants.
Propriétés : Cette procédure garantit que tout vocabulaire contenant tous les octets uniques nécessaires produit une tokenisation valide. La suppression d'un token du vocabulaire force simplement l'inférence à descendre plus profondément dans l'arbre, sans effets en cascade sur les autres tokens, contrairement aux méthodes basées sur la fusion.

3. Sélection du vocabulaire par programmation en nombres entiers

L'innovation centrale consiste à formuler la sélection du vocabulaire comme un Programme en Nombres Entiers (IP) afin de minimiser le nombre total de tokens sur le corpus d'entraînement.

Variables : Des variables binaires $x_i$ indiquent si le token candidat $i$ est dans le vocabulaire. Des variables binaires $z_{jk}$ indiquent si le nœud $k$ dans l'arbre de division $j$ est émis lors de l'inférence.
Objectif : Minimiser le nombre pondéré total de tokens émis : $\min \sum_{j} c_j \sum_{k} z_{jk}$ .
Contraintes :
- Taille du vocabulaire : La somme des tokens sélectionnés doit être égale à la taille cible $m$ .
- Couverture : Pour chaque chemin d'une feuille à la racine, exactement un nœud doit être sélectionné (assurant que l'intégralité du prétoken est couverte).
- Cohérence : Un nœud ne peut être émis ( $z_{jk}=1$ ) que s'il est dans le vocabulaire ( $x_i=1$ ) et que aucun de ses ancêtres ne l'est.
Résolution : L'IP est relâché en un Programme Linéaire (LP). En pratique, le relâchement LP est « quasi-entier », ce qui signifie que la solution contient très peu de valeurs fractionnaires. Une heuristique d'arrondi simple est appliquée pour obtenir une solution entière qui est prouvée comme étant quasi-optimale (dans une fraction négligeable de l'optimum global).

Contributions clés

Nouveau cadre de tokenisation : ToaST introduite une approche basée sur les arbres de division qui évite les approximations gloutonnes du BPE et les contraintes d'inférence spécifiques d'UnigramLM.
Optimisation globale : En formulant la sélection du vocabulaire comme un IP avec un relâchement LP serré, ToaST trouve un vocabulaire qui minimise globalement le nombre de tokens pour un ensemble donné d'arbres de division, plutôt que de s'appuyer sur des décisions locales gloutonnes.
Évolutivité : La méthode s'échelonne de manière quadratique avec le nombre d'arbres de division, permettant le traitement de grands corpus (couvrant 99 % des comptes de prétokens) dans des temps d'entraînement réalisables.
Conception découplée : La séparation de la construction de l'arbre (basée sur les statistiques du corpus) et de la sélection du vocabulaire (basée sur l'optimisation) permet des extensions flexibles, telles que l'intégration de préférences morphologiques ou au niveau des caractères sans réentraîner le modèle d'optimisation.

Résultats expérimentaux

Les auteurs ont évalué ToaST sur du texte anglais en utilisant le jeu de données CulturaX et l'ont comparé au BPE, au WordPiece et à UnigramLM.

Compression : Pour des tailles de vocabulaire de 40 960 et plus, ToaST réduit le nombre de tokens de plus de 11 % par rapport à toutes les lignes de base. Cela est mesuré en octets par token.
Distribution des tokens : ToaST réduit considérablement la fréquence des tokens « Feuilles » (remplacements par un seul octet) de 14 à 19 fois par rapport aux lignes de base pour une taille de vocabulaire de 65 536. Inversement, elle produit beaucoup plus de tokens « Racine » (prétokens complets), indiquant une meilleure rétention des unités sémantiques.
Efficacité de Rényi : ToaST atteint une efficacité de Rényi plus élevée (avec $\alpha=2.5$ ), indiquant une distribution de tokens plus uniforme et moins de tokens à haute fréquence, ce qui est souvent corrélé à de meilleures performances en aval.
Performances en aval : Dans des expériences d'entraînement de modèles de langage de 1,5 milliard de paramètres (nanochat), ToaST a obtenu le score CORE le plus élevé (une moyenne de 22 benchmarks), surpassant les lignes de base de 2,6 % à 7,6 %. Il a nettement surpassé le BPE et UnigramLM, et a été le meilleur performant sur 13 des 22 tâches individuelles.
Qualité de l'optimisation : Le relâchement LP s'est révélé exceptionnellement serré. Sur 128 instances de problèmes, l'écart relatif maximum entre la solution entière arrondie et la borne LP était de $5,76 \times 10^{-7}$ , de nombreuses instances étant entièrement entières.

Importance et affirmations

L'article affirme que ToaST démontre la valeur de l'optimisation directe de la tokenisation pour la compression en utilisant un cadre d'optimisation globale plutôt que de s'appuyer sur des heuristiques gloutonnes. Les auteurs soutiennent que la compression supérieure conduit à une fenêtre de contexte effective plus large et, par conséquent, à une amélioration des performances en aval.

L'importance du travail réside dans :

Praticité : Malgré la NP-complétude théorique de la tokenisation optimale, le relâchement LP rend l'approche computationnellement réalisable et pratique pour un entraînement à grande échelle.
Performance : Les résultats empiriques suggèrent que la réduction de 11 % du nombre de tokens se traduit par des gains mesurables dans les performances des modèles de langage (score CORE), soutenant l'hypothèse qu'une meilleure compression est corrélée à une meilleure utilité du modèle.
Flexibilité : L'architecture permet des extensions futures, telles que la gestion de caractères multi-octets ou de divisions morphologiques, en modifiant la hiérarchie de construction de l'arbre sans altérer la logique d'optimisation du vocabulaire.

Les auteurs notent des limites, spécifiquement que les expériences ont été menées exclusivement sur du texte anglais, et que l'efficacité de l'entraînement sur les prétokens agrégés supérieurs peut varier pour les langues non délimitées par des espaces. Ils divulguent également l'utilisation de LLM pour l'implémentation du code et la génération de figures.