💬 NLP

Joint Optimization for Greedy Longest-match Tokenization

Cet article introduit JOLT, un cadre d'optimisation conjointe qui formule l'apprentissage du vocabulaire comme un programme entier avec des contraintes de cohérence gloutonne pour aligner l'entraînement sur le décodage par plus longue correspondance, atteignant une compression quasi-optimale qui surpasse de manière significative le BPE standard tout en fournissant un certificat de quasi-optimalité.

Auteurs originaux : Adhiraj Singh, Deepanshu Mody, Ghina Al Shdaifat, Hamza Alshamy, Adam Wiemerslage, Varshini Reddy, Craig W. Schmidt

Publié 2026-07-28

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Adhiraj Singh, Deepanshu Mody, Ghina Al Shdaifat, Hamza Alshamy, Adam Wiemerslage, Varshini Reddy, Craig W. Schmidt

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 essayiez de faire tenir une bibliothèque massive de livres dans une seule et petite valise pour un voyage. Vous voulez faire entrer autant de texte que possible dans un espace limité, mais vous ne pouvez pas simplement écraser les pages en une boule ; vous devez les organiser en morceaux nets et maniables. Dans le monde de l'intelligence artificielle, cette « valise » est la mémoire de l'ordinateur, et les « morceaux » sont appelés jetons (tokens). Les modèles d'IA ne lisent pas le texte sous forme de mots entiers, mais sous forme de ces plus petites pièces. La façon dont nous découpons les mots est très importante : si nous les coupons mal, nous utilisons plus d'espace et l'ordinateur doit travailler plus dur pour les lire. Pendant des années, la méthode standard pour découper ces mots a été une méthode appelée Byte Pair Encoding (BPE). Considérez le BPE comme un bibliothécaire très efficace, mais légèrement rigide, qui suit une règle stricte : « Collez toujours les deux morceaux de texte les plus courants ensemble en premier. » C'est une approche rapide et gourmande qui a bien fonctionné, mais c'est essentiellement une heuristique — une bonne supposition basée sur une règle simple, et non une solution mathématique parfaite.

Récemment, des scientifiques ont commencé à poser une grande question : le « bon coup de pouce » de ce bibliothécaire est-il réellement le meilleur que nous puissions faire ? Ou existe-t-il une manière plus intelligente de découper les mots afin de faire tenir encore plus de texte dans la valise ? Ce document explore cette question en examinant une manière spécifique dont l'IA lit le texte, appelée « Greedy Longest-Match » (correspondance la plus longue gourmande). Imaginez lire une phrase et, à chaque étape, saisir le mot le plus long possible que vous connaissez avant de passer à la lettre suivante. Les auteurs voulaient voir s'ils pouvaient concevoir un vocabulaire spécifiquement pour ce style de lecture, plutôt que d'espérer qu'un vocabulaire à usage général fonctionne. Ils ont construit un nouveau système appelé JOLT (Joint Optimization for Greedy Longest-match Tokenization). Au lieu de simplement coller des morceaux ensemble en fonction de leur fréquence, JOLT traite l'ensemble du problème comme un puzzle géant et complexe. Il utilise des mathématiques avancées pour déterminer exactement quels morceaux de mots conserver et comment découper chaque mot des données d'entraînement de sorte que, lorsque l'IA le lit en utilisant la règle du « plus long match », elle utilise le nombre absolu minimum de morceaux possible.

L'article conclut que, bien que l'ancien bibliothécaire (BPE) soit en fait assez bon — se situant déjà à 1 % ou 2 % du meilleur emballage théorique possible — le nouveau système, JOLT, peut en extraire un peu plus d'espace. En résolvant ce puzzle mathématique, JOLT parvient à combler presque tout l'écart restant entre l'ancienne méthode et la limite théorique parfaite. Lors de tests avec différentes tailles de données textuelles, JOLT a réduit le nombre de jetons jusqu'à 0,78 % par rapport à la méthode standard. Bien que ce chiffre paraisse faible, dans le monde de l'IA, économiser même une fraction de pourcentage signifie que le modèle peut lire plus de texte, réfléchir plus vite et coûter moins cher à exploiter. Les auteurs montrent qu'en alignant parfaitement le vocabulaire avec la façon dont l'IA lit réellement, nous pouvons récupérer presque toute la « marge de compression » qui était auparavant laissée sur la table.

L'histoire de JOLT : Résoudre le puzzle des mots

Pour comprendre comment JOLT fonctionne, imaginez que vous êtes un chef de cuisine expert essayant de créer le menu parfait pour un banquet massif. Vous avez une immense liste d'ingrédients (le texte), et vous devez les couper en tailles spécifiques (jetons) pour les servir à vos invités (l'IA). Le hic, c'est que vos invités ont une habitude alimentaire très spécifique : ils saisissent toujours la plus grosse bouchée qu'ils peuvent trouver avant de passer à la suivante. C'est la règle du « Greedy Longest-Match ».

Pendant longtemps, les chefs (chercheurs en IA) ont utilisé une recette standard appelée BPE. Ils regardaient les ingrédients et disaient : « Hé, "th" et "e" apparaissent souvent ensemble, collons-les pour faire "the" ». Ils continuaient ainsi, collant les paires les plus communes, jusqu'à obtenir un menu d'une certaine taille. Cela fonctionnait bien, mais c'était un peu comme construire une maison en empilant simplement des briques sans vérifier si les murs étaient parfaitement droits. C'était une approche « gourmande » (greedy) — faire la chose facile et évidente en premier.

Les auteurs de cet article ont réalisé que si vous voulez que vos invités mangent efficacement, vous ne devriez pas seulement construire un menu basé sur ce qui est commun ; vous devriez construire un menu basé sur la façon dont ils mangent. Ils ont créé JOLT, qui est comme un chef super intelligent qui planifie l'ensemble du menu à la fois, en considérant chaque ingrédient et chaque façon possible de le découper, garantissant que le résultat final est parfaitement optimisé pour l'habitude de la « plus grosse bouchée » des invités.

Le Puzzle Mathématique
Le cœur de JOLT est un problème mathématique massif. Les auteurs devaient décider de deux choses simultanément :

Quels ingrédients conserver : Quels morceaux de mots doivent figurer dans le vocabulaire final ?
Comment découper le texte : Pour chaque mot des données d'entraînement, quels morceaux spécifiques doivent être utilisés pour le construire ?

La partie délicate est que ces deux décisions sont liées. Vous ne pouvez pas décider de découper un mot en « ta » et « ble » à moins d'avoir réellement décidé de garder « ta » et « ble » dans votre vocabulaire. De plus, comme l'IA utilise la règle du « plus long match », vous devez vous assurer que si vous découpez un mot en « ta » et « ble », il n'existe pas un morceau plus long comme « table » dans votre vocabulaire qui viendrait voler la vedette. Si « table » existe, l'IA mangera « table » en entier, et votre plan de servir « ta » et « ble » échouera.

Pour résoudre cela, les auteurs ont utilisé une technique appelée « Programmation en Nombres Entiers » (Integer Programming). Imaginez une grille géante d'interrupteurs. Certains interrupteurs activent un mot (le mettent dans le vocabulaire), et d'autres activent une façon spécifique de découper un mot. Le but est d'actionner les interrupteurs pour obtenir le nombre total de morceaux le plus bas possible. Cependant, résoudre cette grille pour une bibliothèque entière de texte est si vaste que même les ordinateurs les plus rapides mettra l'éternité à le faire.

L'astuce intelligente
Ainsi, les auteurs ont trouvé une astuce ingénieuse. Au lieu d'essayer de résoudre tout le puzzle à la fois, ils ont commencé par une version petite et simple. Ils n'ont considéré que le découpage des mots en un ou deux morceaux. Ils ont résolu le problème mathématique, et si l'ordinateur disait : « Hé, ce mot est trop difficile à découper avec seulement ces morceaux, j'ai besoin de plus d'options », ils ajoutaient des options de découpage plus complexes juste pour ce mot. Ils répétaient ce processus, ajoutant de la complexité uniquement là où c'était nécessaire, jusqu'à ce que la solution se stabilise.

Cette approche leur a permis de trouver une solution incroyablement proche de la limite théorique parfaite. Ils ont découvert que la méthode standard BPE faisait déjà un excellent travail, se situant à 1 % ou 2 % du meilleur résultat possible. Mais JOLT a réussi à combler 89,6 % à 99,4 % de cet écart restant.

Les Résultats
Lorsqu'ils ont testé leur nouveau système sur différentes quantités de données (de 100 000 à 400 000 mots) et différentes tailles de vocabulaire (32 000 et 64 000 mots), les résultats étaient clairs. JOLT utilisait systématiquement moins de jetons que la méthode standard BPE.

Avec un vocabulaire de 32 000 mots, JOLT a réduit le nombre de jetons jusqu'à 0,78 % par rapport à la méthode standard.
Avec un vocabulaire de 64 000 mots, l'amélioration était plus faible mais toujours présente, atteignant jusqu'à 0,31 %.

L'article a également vérifié la proximité de leur solution avec la limite mathématique absolue. Ils ont trouvé que leur solution arrondie finale se situait à 0,008 % à 0,176 % de la limite théorique. Cela signifie que le processus de « l'arrondi » (transformer la solution mathématique en un vocabulaire réel et utilisable) n'a pas perdu beaucoup d'efficacité. Les petits gains réalisés par JOLT par rapport à BPE n'étaient pas un coup de chance ; c'étaient des améliorations structurelles réelles.

Pourquoi cela importe
Les auteurs ont également examiné d'autres méthodes. Ils ont découvert qu'une méthode populaire appelée WordPiece, conçue pour le même style de lecture par « plus long match », était en réalité moins performante que BPE lorsqu'elle était testée. C'était parce que WordPiece était entraînée pour maximiser un objectif différent (prédire le mot suivant) plutôt que pour minimiser le nombre de morceaux. Cela prouve que vous ne pouvez pas simplement utiliser un vocabulaire conçu pour un usage et vous attendre à ce qu'il fonctionne parfaitement pour un autre. Vous devez entraîner le vocabulaire spécifiquement pour la façon dont l'IA lit.

En résumé, cet article montre que si l'ancien bibliothécaire « gourmand » (BPE) faisait un travail étonnamment bon, il reste encore un tout petit peu d'espace à exploiter. En utilisant une nouvelle approche mathématiquement rigoureuse qui aligne parfaitement le vocabulaire avec le style de lecture de l'IA, JOLT récupère presque tout cet espace perdu. C'est un rappel que dans le monde de l'IA, même de petites améliorations d'efficacité peuvent conduire à des modèles plus rapides, moins chers et plus capables. Les auteurs n'ont pas seulement deviné ; ils ont prouvé mathématiquement que leur méthode nous rapproche de la perfection de l'empaquetage plus que jamais auparavant.

Résumé Technique : Optimisation Conjointe pour la Tokenisation par Correspondance de Longueur Maximale Gloutonne (JOLT)

Énoncé du Problème
La tokenisation par sous-mots est une étape de prétraitement critique en TAL (Traitement du Langage Naturel), où la conversion du texte en jetons (tokens) affecte la capacité de la fenêtre de contexte et les coûts d'inférence. Bien que le BPE (Byte Pair Encoding) soit l'heuristique dominante, des travaux récents (ex. : ToaST, ConvexTok) ont démontré que l'apprentissage du vocabulaire peut être formulé comme un problème d'optimisation visant à minimiser directement le nombre de jetons pour des règles d'inférence spécifiques. Cependant, les approches d'optimisation existantes ciblent des règles d'inférence de type arbre de division (split-tree) ou de chemin le plus court (shortest-path). Il existe un manque de techniques de construction de vocabulaire spécifiquement conçues pour la règle d'inférence de décodage par correspondance de longueur maximale gloutonne de gauche à droite (Greedy Left-to-Right - GL2R), qui est la règle d'inférence standard utilisée par WordPiece. Le défi consiste à formuler la sélection du vocabulaire de telle sorte que le nombre de jetons résultant corresponde exactement à ce que l'algorithme GL2R produit lors du déploiement, une contrainte qui couple la sélection du vocabulaire avec les choix de segmentation de manière non triviale.

Méthodologie
Les auteurs proposent JOLT (Joint Optimization for Greedy Longest-match Tokenization), qui formule l'apprentissage du vocabulaire comme un programme entier (Integer Program - IP) et le résout via une relaxation de programmation linéaire (LP).

Formulation : Le modèle optimise conjointement deux ensembles de variables binaires :
1. Variables de sélection du vocabulaire ( $x_t$ ) : Déterminent quels jetons candidats entrent dans le vocabulaire.
2. Variables de choix de segmentation ( $z_{p,s}$ ) : Déterminent quelle segmentation $s$ est sélectionnée pour chaque pré-jeton $p$ .
Contraintes de Cohérence Gloutonne (Greedy-Consistency) : L'innovation centrale est un ensemble de contraintes garantissant qu'une segmentation sélectionnée est exactement celle que l'algorithme GL2R produirait compte tenu du vocabulaire sélectionné. Pour qu'une segmentation soit valide sous GL2R, aucun jeton de vocabulaire plus long ne peut exister en chevauchant le début de n'importe quel segment de cette segmentation. Ces contraintes forcent l'optimisation à prendre explicitement en compte le comportement de « correspondance la plus longue ».
Escalade Itérative : Puisque le nombre de segmentations possibles croît exponentiellement avec la longueur du pré-jeton, JOLT ne crée pas initialement toutes les instances. Il commence par des segmentations d'ordre faible (jusqu'à l'ordre 2) et une option de « repli » (fallback). Si le solveur sélectionne l'option de repli pour un pré-jeton, le système augmente l'ordre maximal de segmentation pour ce pré-jeton lors du tour suivant, ajoutant ainsi des candidats d'ordre supérieur. Cela permet de maintenir la taille de la LP gérable.
Relaxation LP et Arrondi : L'IP est relaxé en une LP (permettant des valeurs fractionnaires pour $x_t$ et $z_{p,s}$ ) et résolu à l'aide de Gurobi. Un schéma d'arrondi pondéré basé sur la contribution extrait un vocabulaire discret de la solution fractionnaire. L'arrondi donne la priorité aux jetons qui contribuent le plus à la compression des pré-jetons à haute fréquence.

Contributions Clés

Optimisation Spécifique à GL2R : JOLment est la première méthode qui formule l'apprentissage du vocabulaire spécifiquement pour l'inférence GL2R, garantissant que le nombre de jetons optimisé égale le nombre réalisé lors du déploiement.
Contraintes de Cohérence Gloutonne : L'article introduit un ensemble de contraintes novateur qui impose mathématiquement la propriété de correspondance la plus longue de GL2R au sein du cadre d'optimisation, couplant la sélection du vocabulaire et la segmentation.
Stratégie de Résolution Évolutive : Les auteurs développent un mécanisme d'escalade piloté par le repli qui évite l'explosion exponentielle des variables en n'instanciant les segmentations d'ordre supérieur que lorsque cela est nécessaire.
Bornes Proches de l'Optimalité : La relaxation LP fournit une borne inférieure valide sur le nombre de jetons réalisable. Les auteurs démontrent que les solutions arrondies sont à 0,008–0,176 % de cette borne inférieure de la LP, certifiant une compression quasi-optimale.

Résultats
Des expériences ont été menées sur le jeu de données MiniPile avec des portées d'entraînement ( $N$ ) de 100k, 200k, 300k et 400k pré-jetons, et des tailles de vocabulaire ( $|V|$ ) de 32k et 64k.

Gains de Compression : Sur les données de validation hors échantillon, JOLT réduit le nombre de jetons par rapport au décodage natif de BPE jusqu'à 0,78 % (à $N=400k, |V|=32k$ ). Les gains augmentent généralement avec la portée de l'entraînement.
Réduction de l'Écart : La borne inférieure de la LP révèle que les heuristiques standards de BPE sont déjà proches de l'optimalité pour GL2R, se situant à 1–2 % de la borne théorique. JOLT comble 89,6–99,4 % de l'écart restant entre BPE et la borne LP.
Efficacité de l'Arrondi : L'écart entre la relaxation LP et le vocabulaire arrondi final est négligeable (0,008–0,176 %), indiquant que le processus d'arrondi ne perd presque aucun potentiel de compression.
Comparaison avec les Références :
- BPE-greedy : Appliquer le décodage GL2R à un vocabulaire entraîné par BPE ne produit qu'une amélioration marginale (0,08 %) par rapport au mode natif de BPE, confirmant que l'heuristique de fusion de BPE est structurellement alignée avec GL2R.
- UnigramLM-greedy : Malgré l'utilisation de l'inférence GL2R, UnigramLM est nettement moins performant (28–30 % de jetons en plus) car son objectif d'entraînement (maximisation de la vraisemblance) diverge de l'objectif de minimisation du nombre de jetons.

Signification et Revendications
L'article affirme que la principale source d'inefficacité de compression dans les tokeniseurs actuels n'est pas la règle d'inférence elle-même, mais le désalignement entre l'heuristique de construction du vocabulaire et la règle d'inférence spécifique. Bien que le BPE soit déjà proche de l'optimalité pour GL2R, JOLT démontre que la « marge de progression » (l'écart entre BPE et l'optimum théorique) peut être largement récupérée grâce à une optimisation de vocabulaire alignée sur l'inférence. Les résultats suggèrent que la majeure partie de la compression réalisable pour l'inférence GL2R est récupérable, JOLT récupérant 89,6–99,4 % du gain théorique. L'article ne prétend pas que JOLT surpasse radicalement BPE en termes absolus (les gains sont <1 %), mais plutôt qu'il fournit une approche fondée sur l'optimisation et certifie la quasi-optimalité, tout en récupérant le potentiel de compression limité restant dans les heuristiques standards.

L'histoire de JOLT : Résoudre le puzzle des mots

Articles similaires