💬 NLP

Incremental BPE Tokenization

Cet article introduit un nouvel algorithme de tokenisation par encodage de paires de字节 (Byte Pair Encoding - BPE) incrémental qui atteint une complexité temporelle dans le pire des cas de $\mathcal{O}(n \log^2 t)$ , permettant un traitement en flux efficace avec une accélération allant jusqu'à 3x par rapport aux bibliothèques existantes comme les tokenizers de Hugging Face et tiktoken.

Auteurs originaux : Shenghu Jiang, Ruihao Gong

Publié 2026-06-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shenghu Jiang, Ruihao Gong

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 lisez un livre long, mais au lieu de lire mot par mot, vous le lisez « octet par octet » (les plus petites briques numériques du texte). Votre objectif est de regrouper ces octets en morceaux significatifs appelés « tokens ». Ce processus est appelé tokenisation, et la méthode la plus populaire pour le faire est le Byte Pair Encoding (BPE).

Considérez le BPE comme un jeu de Lego. Vous commencez avec des briques individuelles (des octets). Les règles du jeu disent : « Si vous voyez deux briques spécifiques l'une à côté de l'autre souvent, emboitez-les pour créer une brique plus grande et personnalisée. » Vous continuez ainsi, emboîtant des paires, jusqu'à obtenir un mélange de petites briques et de structures plus grandes, construites sur mesure.

Le Problème : Le goulot d'étranglement de l'« attente »

Actuellement, la plupart des programmes informatiques qui jouent à ce jeu de Lego sont hors ligne. Ils exigent la page entière de texte avant de commencer à emboîter les briques ensemble.

L'Analogie : Imaginez que vous construisez un mur en Lego, mais que vous devez attendre que le camion de livraison apporte l'intégralité des briques du mur avant de pouvoir même emboîter les deux premières ensemble. Vous ne pouvez pas commencer à construire tant que toute la cargaison n'est pas arrivée.
La Conséquence : Dans l'IA moderne (comme les chatbots), cela crée un délai. L'ordinateur doit attendre que la phrase entière arrive avant de pouvoir commencer à traiter le premier mot. C'est comme une chaîne de montage d'usine qui s'arrête chaque fois qu'une nouvelle pièce arrive, attendant tout le lot avant de progresser.

La Solution : Le constructeur « Incrémental »

Les auteurs de cet article proposent une nouvelle façon plus intelligente de jouer au jeu de Lego. Ils l'appellent la Tokenisation BPE Incrémentale.

Au lieu d'attendre le camion entier, leur algorithme emboîte les briques dès que chaque nouvel octet arrive.

L'Analogie : Imaginez un maître constructeur capable de regarder une seule nouvelle brique, de savoir instantanément comment elle s'ajuste avec les précédentes, et de l'emboîter immédiatement. Il n'a pas besoin de voir tout le mur pour savoir à quoi ressemble la section actuelle.
Comment ça marche : L'article présente une structure mathématique ingénieuse (une « Successor Forest » et une « Suffix-Successor Tree ») qui agit comme une carte de toutes les combinaisons de Lego possibles. Lorsqu'un nouvel octet arrive, l'algorithme utilise cette carte pour déterminer instantanément la meilleure façon de le regrouper avec le passé, sans avoir à rescanner tout le texte.

Caractéristiques Clés et Avantages

1. Vitesse et Stabilité (La garantie « Sans Fonte »)

L'Affirmation : Les anciennes méthodes deviennent parfois lentes ou plantent si le texte présente des motifs étranges (comme un million de « a » à la suite). La nouvelle méthode est comme un gilet pare-balles ; elle garantit qu'elle ne ralentira jamais, peu importe la bizarrerie du texte.
Le Résultat : Elle est jusqu'à 3 fois plus rapide que la norme actuelle de l'industrie (les tokenizer de Hugging Face) et gère les entrées « pathologiques » (étranges) sans ralentir, contrairement à tiktoken d'OpenAI qui peut s'enliser.

2. Sortie en Flux (Le Chef « Prompt »)

L'Affirmation : Non seulement il traite l'entrée plus rapidement, mais il commence aussi à produire les briques de Lego terminées immédiatement.
L'Analogie : Imaginez un chef qui n'attend pas que tout le repas soit cuit avant de servir. Dès qu'un plat est prêt, il le dresse et vous le tend. C'est ce qu'on appelle la « Sortie Eager » (Eager Output).
Le Bénéfice : Cela permet à l'IA de commencer à « réfléchir » (générer une réponse) pendant qu'elle est encore en train de « lire » votre question, rendant la conversation beaucoup plus fluide et en temps réel.

3. Remplacement Direct (Drop-in Replacement)

L'Affirmation : Ce nouvel algorithme est conçu pour être une mise à niveau « plug-and-play ». Vous n'avez pas besoin de reconstruire tout votre système d'IA ; vous remplacez simplement l'ancien outil de tokenisation par ce nouveau, et il fonctionne exactement de la même manière, mais beaucoup plus vite.

Résumé

En termes simples, cet article présente un constructeur de Lego ultra-efficace et en temps réel pour le traitement de texte par l'IA.

Ancienne Méthode : Attendre tout le texte, puis tout construire d'un coup. (Lent, sujet aux délais).
Nouvelle Méthode : Construire un petit peu à chaque fois qu'une seule lettre arrive. (Rapide, stable, et permet à l'IA de répondre pendant que vous tapez encore).

Les auteurs ont prouvé mathématiquement que cette méthode est rapide, fiable et fonctionne parfaitement avec les règles existantes de la compréhension du texte par l'IA, offrant un gain de vitesse significatif pour les modèles de langage modernes.

Résumé technique : Tokenisation BPE incrémentale

Énoncé du problème

Les pipelines des modèles de langage de grande taille (LLM) modernes reposent largement sur le codage par paires de octets (BPE) pour la tokenisation. Cependant, les implémentations de pointe actuelles (par exemple, tokenizers de Hugging Face et tiktoken d'OpenAI) sont principalement conçues comme des processus hors ligne. Elles nécessitent que l'intégralité de la séquence d'entrée ou un segment pré-découpé soit entièrement observée avant de produire une tokenisation canonique. Cette limitation architecturale force la tokenisation et le pré-remplissage (pre-filling) du modèle à s'exécuter de manière séquentielle plutôt que concurrente, introduisant de la latence dans les scénarios de streaming et d'inférence à contexte long.

De plus, les implémentations existantes reposent souvent sur des files de priorité basées sur le tas (heap-based priority queues) pour sélectionner les fusions sur l'ensemble de l'entrée, ce qui donne des formulations qui sont intrinsèquement globales et difficiles à adapter à des mises à jour octet par octet. Bien que certains outils utilisent une pré-segmentation par expressions régulières pour limiter les coûts de fusion, cette approche peut être fragile, entraînant une dégradation des performances ou une épuisement de la pile sur des entrées pathologiques (par exemple, des répétitions de caractères étendues), où certains outils présentent un comportement en $O(n^2)$ .

Méthodologie

Les auteurs proposent un nouvel algorithme pour la tokenisation BPE incrémentale qui maintient les résultats de la tokenisation BPE pour chaque préfixe du texte en temps réel. L'approche est fondée sur les propriétés structurelles du BPE et introduit plusieurs innovations algorithmiques clés :

1. Fondations structurelles

Cohérence des préfixes : En tirant parti de la propriété selon laquelle une tokenisation BPE valide peut être librement tronquée, l'algorithme modélise la tokenisation d'une chaîne croissante comme une extension de la tokenisation valide précédente d'un préfixe plus court, plutôt que comme un nouveau calcul.
Dernier jeton ( $\theta(s)$ ) : L'algorithme se concentre sur le maintien du « Dernier Jeton » (Last Token) de la chaîne $s$ actuelle. La tokenisation complète est implicitement encodée par la séquence des derniers jetons, récupérable via un retour en arrière (backtracking).
Forêt de successeurs & Arbre Suffixe-Successeur : Le vocabulaire est normalisé en jetons canoniques, formant une structure topologique appelée Forêt de Successeurs. Pour toute entrée, l'espace de recherche pour le nouveau dernier jeton est confiné à un Arbre Suffixe-Successeur, qui organise tous les jetons de suffixe potentiels.

2. La propriété de chemin monotone

Une contribution théorique centrale est la Propriété de Chemin Monotone, qui établit que pour toute chaîne d'entrée, l'ensemble des jetons de suffixe capables de servir de dernier jeton forme un chemin unique et continu au sein de l'Arbre Suffixe-Successeur. Ce chemin est ancré à la racine (le jeton atomique) et s'étend jusqu'au véritable dernier jeton $\theta(s)$ . Cette propriété réduit l'espace de recherche de l'arbre entier à un seul chemin, permettant une vérification efficace.

3. Implémentation algorithmique

Le processus de mise à jour incrémentale implique deux étapes principales :

Identification de l'espace de recherche : En utilisant un automate d'Aho–Corasick augmenté d'un pavage par racine carrée persistant, l'algorithme identifie le jeton de suffixe le plus long $\tau(sc)$ en $O(1)$ , définissant l'Arbre Suffixe-Successeur délimitant.
Recherche d'extension de chemin : Pour trouver le nœud le plus profond du chemin monotone, l'algorithme emploie la Décomposition en Centroïdes. Il parcourt un Arbre de Recherche de Centroïdes (CST) précalculé de hauteur $O(\log |\tau|)$ . À chaque étape, il vérifie la Condition du Dernier Jeton de Préfixe (vérification de la joignabilité et de la dominance de priorité) en utilisant des intervalles de linéarisation DFS. Cela permet à l'algorithme de déterminer la direction du chemin valide en $O(\log |\tau})$ .

4. Mécanisme de sortie immédiate (Eager Output)

Pour supporter un véritable streaming, les auteurs introduisent un algorithme de sortie immédiate (eager output). Il identifie le « Frontière Active » de l'arbre de tokenisation — la plage de préfixes qui pourraient potentiellement devenir des parents de futurs jetons. En maintenant un sous-graphe dynamique de ces candidats, le système peut émettre des jetons dès que leurs frontières deviennent invariantes (c'est-à-dire quand tous les chemins actifs convergent vers un seul enfant de la racine virtuelle), permettant un pipeline complet avec l'inférence du modèle.

Contributions clés

Complexité algorithmique : L'algorithme proposé traite chaque octet d'entrée avec une complexité temporelle de pire cas stricte de $O(\log_2 t)$ , où $t$ est la longueur maximale du jeton. Cela donne une complexité globale de $O(n \log_2 t)$ pour une entrée de longueur $n$ .
Capacité de streaming : La méthode fonctionne comme un remplacement direct (drop-in replacement) pour les étapes BPE standards, permettant une tokenisation partielle efficace dans les contextes de streaming sans modifier la correction des étapes de prétraitement environnantes.
Sortie immédiate : L'introduction d'un mécanisme de sortie immédiate permet un streaming et un pipelining en temps réel avec l'inférence du modèle, émettant les jetons dès la résolution des frontières.
Robustesse : Contrairement aux outils existants qui peuvent se dégrader en $O(n^2)$ sur des entrées pathologiques, cette approche maintient des garanties de performance stables.
Support de préfixe complet : L'algorithme supporte naturellement les scénarios nécessitant l'accès aux tokenisations de tous les préfixes (par exemple, les tâches de type « fill-in-the-middle » ou de correction de jetons) sans recours à une troncature heuristique ou un nouveau calcul.

Résultats

Les auteurs ont implémenté l'algorithme en Rust et l'ont comparé aux tokenizers de Hugging Face et tiktoken d'OpenAI.

Débit : L'approche incrémentale atteint une accélération de bout en bout allant jusqu'à $\sim 3\times$ par rapport aux tokenizers de Hugging Face, particulièrement dans les scénarios dépourvus de pré-tokenisation par expression régulière (par exemple, CodeLlama).
Latence sur les entrées pathologiques : Sur des entrées comportant des répétitions étendues, tiktoken présente une chute de débit cohérente avec une complexité $O(n^2)$ . En revanche, la méthode proposée maintient un débit stable, démontant des réductions de latence significatives sur ces cas pathologiques.
Surcharge de la sortie immédiate : Le mécanisme de sortie immédiate introduit une surcharge d'environ 10 % du débit de bout en bout par rapport à la version incrémentale non immédiate, un coût que les auteurs notent comme pouvant être amorti dans les systèmes où la tokenisation est pipelinée avec les E/S ou l'inférence.

Signification et affirmations

L'article démontre que la tokenisation BPE peut être effectuée de manière incrémentale avec des garanties de pire cas strictes tout en maintenant une compatibilité sémantique exacte avec le BPE standard.

Les auteurs affirment que leur travail comble le fossé entre les formalismes théoriques (qui suggèrent la stabilité des préfixes) et l'ingénierie pratique (qui a reposé sur un traitement global et hors ligne). En fournissant un algorithme de complexité $O(n \log_2 t)$ , ce travail permet :

Réduction de la latence : En permettant une tokenisation entièrement pipelinée avec l'inférence du modèle, supprimant le goulot d'étranglement séquentiel dans l'inférence en streaming.
Robustesse du système : En atténuant le risque d'attaques par complexité algorithmique (par exemple, déni de service via des entrées conçues) qui exploitent les vulnérabilités $O(n^2)$ des tokenizers actuels.
Optimisation du pipeline : En rendant certaines étapes de pré-segmentation (conçues uniquement pour limiter les coûts globaux de BPE) algorithmiquement redondantes, permettant des conceptions de pipelines plus propres et plus efficaces.

Les auteurs concluent que leur approche ouvre la voie à des pipelines de LLM plus robustes, réactifs et économes en énergie en traduisant des garanties algorithmiques strictes en bénéfices de latence pratiques.