💬 NLP

Tokenisation via Convex Relaxations

Cet article présente ConvexTok, un algorithme de tokenisation novateur qui formule la construction du vocabulaire comme un programme linéaire résoluble par optimisation convexe, surpassant ainsi les méthodes gloutonnes traditionnelles en matière de métriques intrinsèques et d'efficacité des modèles de langage tout en fournissant une borne certifiée sur sa proximité avec l'optimalité.

Auteurs originaux : Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel

Publié 2026-05-22

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel

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

La Vue d'Ensemble : Ranger une Valise

Imaginez que vous essayez de ranger une immense bibliothèque de livres dans une seule valise (la mémoire de l'ordinateur) pour l'envoyer à un ami. Pour le faire efficacement, vous avez besoin d'un tokeniseur.

Dans le monde de l'IA, un tokeniseur est comme un ensemble de tampons personnalisés. Au lieu d'envoyer chaque lettre de chaque livre (ce qui est lent et encombrant), le tokeniseur regroupe les lettres en « morceaux » ou « tokens » (comme des mots entiers ou des phrases courantes) et envoie ceux-ci à la place. L'objectif est de rendre la valise aussi petite que possible (forte compression) tout en étant capable de reconstruire parfaitement les livres à leur arrivée.

Le Problème : Le Ranger « Avide »

Actuellement, la plupart des modèles d'IA utilisent une méthode appelée BPE (Byte-Pair Encoding). Imaginez le BPE comme un ranger avide.

Comment ça marche : Le ranger examine les livres, trouve les deux lettres les plus courantes qui apparaissent l'une à côté de l'autre (comme « t » et « h »), les colle ensemble pour former un nouveau tampon (« th »), et répète ce processus encore et encore.
Le défaut : Parce que le ranger ne regarde que l'étape immédiatement suivante (optimalité locale), il peut coller deux lettres qui semblent utiles sur le moment mais finissent par créer une forme étrange et inefficace plus tard, qui ne rentre pas bien dans la valise. Il prend une série de petites bonnes décisions qui mènent à un mauvais résultat global. Il ne recule jamais pour voir la « vue d'ensemble ».

La Solution : L'Approche « Architecte » (ConvexTok)

Les auteurs de ce papier, Jan Tempus et ses collègues, ont décidé d'arrêter d'utiliser le ranger avide. Au lieu de cela, ils ont construit un Architecte.

Ils ont réalisé que trouver la manière parfaite de ranger la valise est un problème mathématique si difficile que les ordinateurs abandonnent généralement (c'est « NP-difficile »). Cependant, ils ont trouvé une astuce ingénieuse : la Relaxation Convexe.

L'Analogie : Imaginez essayer de trouver le point le plus bas d'une chaîne de montagnes pour construire une maison. Le ranger avide descend simplement la pente jusqu'à ce qu'il atteigne une petite vallée et s'arrête là, pensant que c'est le fond.
L'Astuce de l'Architecte : Les auteurs ont lissé les montagnes accidentées pour former un bol parfait et lisse (une forme « convexe »). Dans ce bol lisse, il est mathématiquement facile de trouver le point le plus bas absolu.
Le Résultat : Ils ont résolu cette version lisse et facile du problème en utilisant un outil appelé Programme Linéaire (LP). Cela leur a donné un « plan » pour l'emballage parfait.

Le Bémol : Du Plan à la Réalité

Le plan obtenu à partir du bol lisse avait un problème : il suggérait d'utiliser des « demi-tampons ». Par exemple, il pourrait dire : « Utilisez 0,7 du tampon 'th' et 0,3 du tampon 'ing' ». On ne peut pas réellement imprimer un demi-tampon.

Pour régler cela, ils ont inventé trois façons d'arrondir ces nombres à des tampons entiers (comme arrondir 0,7 à 1) :

Déterministe (Det) : Choisissez simplement les $K$ meilleurs tampons avec les scores les plus élevés.
Biaisé (Bias) : Choisissez des tampons qui sont courts et efficaces, même si leur score est légèrement inférieur.
Entier (Int) : Ne choisissez que les tampons dont le plan était sûr à 99 %.

Ce Qu'ils Ont Trouvé (Les Résultats)

L'équipe a testé leur nouvelle méthode ConvexTok contre la méthode BPE avide standard. Voici ce qui s'est passé :

Meilleur Rangement : Les valises ConvexTok étaient systématiquement plus petites (meilleure compression) que les valises BPE. Cela signifie que les modèles d'IA pouvaient lire la même quantité de texte en utilisant moins de « tokens ».
La Garantie « Presque Parfaite » : L'une des choses les plus cool de leur mathématique est qu'elle fournit une « borne inférieure ». Imaginez cela comme un certificat disant : « Nous savons que la taille parfaite de la valise est au moins aussi petite que cela. » Ils ont découvert que leurs valises ConvexTok étaient à moins de 1 % de cette taille théorique parfaite. En d'autres termes, elles sont presque aussi bonnes que mathématiquement possible.
Performance de l'IA : Lorsqu'ils ont entraîné des modèles d'IA en utilisant ces nouvelles valises :
- Les modèles étaient légèrement meilleurs pour comprendre le texte (mesuré par « bits par octet »).
- Sur des tâches de raisonnement complexe (comme répondre à des énigmes logiques), les résultats étaient mitigés. Parfois ConvexTok était meilleur, parfois BPE était meilleur, mais ConvexTok n'a jamais été significativement pire.
Stabilité : La méthode avide BPE est très stable ; si vous lui donnez des livres légèrement différents, elle produit les mêmes tampons. La nouvelle méthode ConvexTok est un peu plus sensible aux livres spécifiques qu'elle voit, ce qui signifie que les tampons peuvent changer légèrement si vous modifiez les données d'entraînement.

Résumé

Le papier soutient que nous utilisons une méthode « avide » pour enseigner à l'IA comment lire depuis trop longtemps. En utilisant des mathématiques avancées (optimisation convexe) pour examiner le problème entier d'un coup, ils ont créé un nouveau tokeniseur appelé ConvexTok.

C'est comme passer d'une personne qui colle aveuglément les lettres les plus courantes ensemble, à un architecte qui conçoit toute la disposition de la valise d'un coup. Le résultat est une manière plus efficace de compresser le texte, nous rapprochant de la limite théorique de la taille minimale que nous pouvons donner à ces « valises » d'IA.

Résumé Technique : Tokenisation par Relaxations Convexes

Énoncé du Problème

La tokenisation est un composant fondamental du pipeline de Traitement Automatique des Langues (TAL), convertissant des chaînes d'octets en séquences de tokens pour les modèles de langage (ML). Bien que des recherches récentes suggèrent une corrélation entre l'efficacité de compression de la tokenisation et les performances des ML en aval, trouver un tokeniseur optimal est un problème NP-difficile. Les méthodes actuelles de l'état de l'art, telles que le Byte-Pair Encoding (BPE) et Unigram, reposent sur des algorithmes gloutons. Ces méthodes prennent des décisions localement optimales (par exemple, fusionner itérativement les paires de tokens les plus fréquentes) sans considérer l'optimalité globale du vocabulaire résultant. Par conséquent, elles peuvent générer des tokens intermédiaires inutiles et échouer à atteindre une compression maximale. Le défi central abordé par cet article est de savoir comment approximer efficacement un tokeniseur globalement optimal, en dépassant les limites des heuristiques gloutonnes.

Méthodologie

Les auteurs proposent ConvexTok, un algorithme de tokenisation novateur qui formule la construction d'un tokeniseur comme un programme linéaire (PL) dérivé d'une relaxation convexe d'un programme en nombres entiers (PNE).

1. Formulation par Graphes

Le problème est d'abord reformulé comme un problème de plus court chemin sur un graphe acyclique orienté (DAG) :

Sommets : Représentent les positions entre les octets dans les chaînes d'octets du jeu de données.
Arêtes :
- Arêtes-octets : Relient les octets adjacents (représentant les caractères individuels).
- Arêtes-token : Relient des sommets non adjacents, représentant des tokens potentiels multi-octets.
Coloration : Les arêtes-token sont colorées en fonction de la séquence d'octets spécifique qu'elles représentent. Une « couleur » correspond à un token unique.
Objectif : Trouver un chemin du début à la fin du graphe qui minimise la longueur totale du chemin (compression) en utilisant un vocabulaire d'au plus $K$ couleurs distinctes (tokens).

2. Programme en Nombres Entiers (PNE)

Le problème de graphe est traduit en un Programme en Nombres Entiers. Les auteurs définissent des matrices d'incidence pour les arêtes libres (arêtes-octets) et les arêtes pondérées (arêtes-token), ainsi qu'une matrice de partition de couleurs. Les variables d'optimisation sont des vecteurs binaires représentant :

Quelles arêtes sont utilisées dans la segmentation ( $f$ pour libre, $p$ pour pondérée).
Quelles couleurs (tokens) sont sélectionnées pour le vocabulaire ( $c$ ).
L'objectif est de minimiser la longueur totale du chemin sous réserve de contraintes de flux (assurant un chemin valide) et d'une contrainte de budget (limitant le nombre de couleurs sélectionnées à $K$ ).

3. Relaxation Convexe (PL)

Puisque la résolution du PNE est NP-difficile, les auteurs relâchent les contraintes discrètes ( $x \in \{0, 1\}$ ) vers des intervalles continus ( $x \in [0, 1]$ ). Cela transforme le problème en un Programme Linéaire (PL), qui peut être résolu efficacement à l'aide de solveurs standards (spécifiquement, la méthode PDLP dans NVIDIA CuOPT).

Le Polytope de Tokenisation : L'espace de solutions de ce PL relâché permet des tokens « partiels » (valeurs fractionnaires), représentant une combinaison convexe de vocabulaires potentiels.

4. Schémas d'Arrondi

Puisque les ML nécessitent des vocabulaires discrets, la solution fractionnaire du PL doit être discrétisée. L'article propose et évalue trois schémas d'arrondi :

Déterministe (Det) : Sélectionne les $K$ couleurs ayant les valeurs PL les plus élevées.
Biaisé (Bias) : Classe les couleurs selon le ratio de leur valeur PL à la longueur du token ( $c / \text{longueur}(c)$ ), favorisant les tokens plus courts lorsque les scores sont comparables.
Entier uniquement (Int) : Sélectionne uniquement les couleurs où la valeur PL est déjà proche de 1 (essentiellement « forcées » par la relaxation), conduisant souvent à un vocabulaire plus petit que le budget $K$ .

Contributions Clés

Formulation : L'article fournit la première formulation de la construction d'un tokeniseur comme un programme linéaire via des techniques polyédriques, reliant explicitement la tokenisation aux problèmes de plus court chemin sur des graphes colorés.
Algorithme (ConvexTok) : Il introduit un nouvel algorithme qui approxime un tokeniseur globalement optimal, évitant les optima locaux inhérents aux approches gloutonnes comme le BPE.
Certification d'Optimalité : La solution PL fournit une borne inférieure prouvable sur la compression réalisable par n'importe quel tokeniseur sur un jeu de données donné. Cela permet aux chercheurs de certifier à quel point un tokeniseur spécifique (par exemple, BPE ou ConvexTok) est proche de l'optimum théorique.
Analyse d'Arrondi : L'article évalue systématiquement trois stratégies d'arrondi distinctes pour convertir les solutions fractionnaires du PL en tokeniseurs fonctionnels.

Résultats Expérimentaux

Les auteurs ont évalué ConvexTok par rapport au BPE sur diverses tailles de vocabulaire (8k à 256k) en utilisant le jeu de données ClimbMix400B et des transformateurs de type GPT avec uniquement des décodeurs.

Qualité de la Solution PL : À mesure que la taille du vocabulaire augmente, la solution PL devient de plus en plus entière (proche de 0 ou 1), suggérant qu'à plus grande échelle, les choix de tokens optimaux sont moins ambigus.
Écart d'Optimalité : La borne inférieure PL révèle que les tokeniseurs existants sont remarquablement proches de l'optimum. Aux tailles de vocabulaire courantes (128k, 256k), tant le BPE que les variantes de ConvexTok sont à moins de 1% de la borne de compression optimale.
Métriques Intrinsèques :
- Le schéma d'arrondi Biaisé (Bias) a systématiquement surpassé le BPE et les autres schémas sur des métriques intrinsèques telles que l'utilisation du vocabulaire, le rapport type-token et le taux de compression.
- Le BPE s'est révélé plus stable que les variantes de ConvexTok lors du réentraînement sur différents sous-ensembles aléatoires de données, probablement en raison de sa nature locale et pilotée par la fréquence.
Performances de Modélisation du Langage :
- Bits par Octet (BpB) : Le schéma d'arrondi Déterministe (Det) a systématiquement obtenu les meilleurs scores BpB, surpassant souvent le BPE, en particulier aux grandes tailles de vocabulaire.
- Tâches en Aval (CORE) : Les résultats sur les benchmarks en aval (raisonnement, choix multiple, bon sens) étaient mitigés. Bien que les variantes de ConvexTok soient compétitives avec le BPE, elles n'ont pas montré d'avantage significatif et cohérent sur toutes les tâches et profondeurs de modèle.
Stabilité : Le BPE a démontré une stabilité supérieure concernant l'échantillonnage des données d'entraînement par rapport à ConvexTok, bien que le schéma d'arrondi Entier uniquement ait montré une stabilité supérieure aux autres variantes de ConvexTok.

Signification et Revendications

L'article revendique que la tokenisation optimisée globalement est une alternative prometteuse aux méthodes de fusion basées sur des heuristiques gloutonnes locales. La signification principale réside dans la capacité à :

Résoudre la Tokenisation Globalement : Démontrer que la tokenisation peut être abordée via l'optimisation convexe plutôt que par des heuristiques gloutonnes.
Certifier les Performances : Fournir une borne inférieure rigoureuse pour mesurer l'écart entre n'importe quel tokeniseur et l'optimum théorique. Les auteurs ont constaté empiriquement qu'aux tailles de vocabulaire standards, les méthodes actuelles sont déjà très proches de cet optimum (à moins de 1%).
Améliorer la Compression : Montrer que, bien que le BPE soit déjà quasi-optimal, des schémas d'arrondi spécifiques (comme le Biais) peuvent produire de meilleures métriques de compression intrinsèque.

Les auteurs restent modestes concernant les améliorations des tâches en aval, notant que si le BpB s'est amélioré de manière cohérente, les gains sur les tâches CORE en aval étaient moins cohérents. Ils concluent que, bien que leur méthode offre un cadre théoriquement supérieur et des bornes certifiables, les gains pratiques par rapport aux méthodes gloutonnes hautement optimisées comme le BPE sont incrémentaux dans le contexte de l'entraînement actuel des grands modèles de langage.