💬 NLP

SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora

SoftMatcha 2 est un algorithme de recherche ultra-rapide et flexible qui permet une mise en correspondance de motifs sémantiques en moins de 0,3 seconde sur des corpus à l'échelle du trillion en exploitant des tableaux de suffixes, des représentations de mots vectorielles et un élagage dynamique sensible au corpus pour atténuer l'explosion combinatoire.

Auteurs originaux : Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

Publié 2026-06-11

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

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 possédez une bibliothèque contenant un billion de livres. Ce n'est pas seulement beaucoup de livres ; c'est une bibliothèque si massive que si vous essayiez de lire chaque mot, cela vous prendrait des millions d'années. Maintenant, imaginez que vous vouliez trouver une phrase spécifique dans cette bibliothèque, mais que vous ne vous souvenez pas des mots exacts. Peut-être que vous vous souvenez de l'idée, ou que vous savez que la phrase était légèrement différente (par exemple, vous vous souvenez de « l'importance de la machine » mais le livre dit en réalité « la signification de la machine »).

C'est le problème que SoftMatcha 2 résout. C'est un moteur de recherche super rapide conçu pour trouver du texte dans ces bibliothèques à l'échelle du billion, en moins d'un tiers de seconde, même si votre requête de recherche n'est pas une correspondance exacte.

Voici comment cela fonctionne, décomposé avec des analogies simples :

1. Le Problème : L'« Explosion Combinatoire »

Si vous demandez à un ordinateur de trouver un texte qui est « similaire » à votre requête, il fait face à un scénario de cauchemar.

L'Analogie : Imaginez que vous cherchiez une recette spécifique dans un livre de cuisine. Si vous dites : « Trouve-moi quelque chose comme "gâteau au chocolat" », l'ordinateur doit vérifier toutes les variations possibles : « muffin au chocolat », « gâteau au chocolat noir », « tarte au chocolat », « gâteau au chocolat avec des noix », « gâteau au chocolat sans noix », etc.
Le Problème : À mesure que votre requête s'allonge, le nombre de ses variations possibles explose de manière exponentielle. C'est comme essayer de trouver une aiguille dans une botte de foin, mais la botte de foin devient une montagne à chaque fois que vous regardez. Les outils précédents soit restaient bloqués dans la montagne, soit ne cherchaient que l'aiguille exacte, manquant ainsi les versions similaires.

2. La Solution : Deux Astuces Magiques

SoftMatcha 2 utilise deux astuces ingénieuses pour dompter cette montagne de possibilités :

Astuce A : Le « Filtre Intelligent » (Élagage Dynamique Sensible au Corpus)

Au lieu de vérifier chaque variation possible de votre recherche, le système vérifie d'abord ce qui existe réellement dans la bibliothèque.

L'Analogie : Imaginez que vous cherchez un type de voiture spécifique dans un immense parking. Au lieu de vérifier chaque modèle de voiture qui pourrait exister (comme une « voiture volante » ou une « voiture sous-marine »), vous regardez d'abord le parking et vous dites : « D'accord, je vois qu'il y a des berlines rouges et des camions bleus ici, mais pas de voitures volantes ».
Comment ça marche : Le système construit une liste de mots similaires (comme des synonymes) mais élimine immédiatement toute combinaison qui n'apparaît pas réellement dans la bibliothèque de mille milliards de mots. Il utilise la « forme » statistique du langage (comme le fait que certains mots sont très courants et d'autres rares) pour éliminer les options impossibles avant même de commencer la recherche. Cela empêche l'espace de recherche d'exploser.

Astuce B : La « Carte Sensible au Disque » (Recherche Exacte Rapide)

La bibliothèque est trop grande pour tenir dans la mémoire principale de l'ordinateur (RAM), elle vit donc sur un disque dur (disque). Lire depuis un disque est généralement lent, comme marcher jusqu'à un entrepôt pour récupérer un livre.

L'Analogie : Imaginez une bibliothèque standard où vous devez aller à l'étagère, prendre le livre, revenir, et répéter cela des centaines de fois. SoftMatcha 2 construit une « carte » spéciale (un Suffix Array) qui indique au bibliothécaire exactement où aller.
L'Innovation : La plupart des outils de recherche obligent le bibliothécaire à faire de nombreux voyages à l'entrepôt pour trouver un livre. La nouvelle carte de SoftMatcha 2 est conçue pour que le bibliothécaire n'ait besoin de faire qu'un seul voyage à l'entrepôt pour trouver l'emplacement exact. Cela rend la recherche du texte exact incroyablement rapide, même si la bibliothèque est stockée sur un disque lent.

3. Ce qu'il peut faire (La partie « Soft »)

Parce qu'il combine ces astuces de vitesse avec une compréhension du sens des mots (en utilisant des vecteurs de mots), il peut gérer des recherches « douces » (soft) :

Substitution : Vous cherchez « médaille d'or » et il trouve « médaille d'argent » (car ils sont liés).
Insertion/Suppression : Vous cherchez « importance de machine » et il trouve « l'importance de la machine » (ajout d'un mot) ou « l'importance de l'apprentissage automatique » (ajout de mots).
L'Ordre Compte : Contra�à d'autres outils qui regardent simplement un sac de mots, SoftMatcha 2 respecte l'ordre. Il sait que « le chien mord l'homme » est différent de « l'homme mord le chien ».

4. Résultats Réels

Le papier a testé cela sur FineWeb-Edu, un ensemble de données contenant 1,4 billion de mots.

Vitesse : Il a trouvé des résultats en moins de 0,3 seconde.
Comparaison : Il était 33 fois plus rapide que le meilleur outil de recherche exacte précédent (infini-gram) et nettement plus rapide que le précédent outil de recherche « douce » (SoftMatcha), qui ne pouvait pas gérer des bibliothèques de cette taille.
Découverte : Parce qu'il est si bon pour trouver des « quasi-correspondances », les chercheurs l'ont utilisé pour trouver de la contamination dans les données d'entraînement. Ils ont découvert que certaines questions de tests utilisés dans les benchmarks d'IA étaient apparues dans les données d'entraînement sous des formes légèrement différentes (par exemple, les chiffres changés ou les mots échangés), ce que les outils de correspondance exacte précédents avaient manqué. C'est comme trouver un élève qui a mémorisé le corrigé mais qui a légèrement modifié les chiffres pour tricher.

Résumé

SoftMatcha 2 est un bibliothécaire super rapide pour les plus grandes bibliothèques du monde. Il ne se contente pas de chercher des copies exactes de votre requête ; il comprend le sens et trouve des phrases similaires, même si vous oubliez un mot ou remplacez un mot par un synonyme. Il y parvient en ignorant intelligemment les options impossibles et en utilisant une carte hautement efficace pour naviguer dans le stockage de données massif, le tout en un clin d'œil.

Résumé Technique : SoftMatcha 2

Énoncé du Problème

La montée en charge rapide des modèles de langage de grande taille (LLM) a nécessité des corpus d'entraînement atteignant des milliers de billions de tokens (par exemple, FineWeb-Edu avec 1,4 billion de tokens). Les outils existants pour la recherche dans ces corpus font face à trois défis distincts que les méthodes actuelles ne parviennent pas à résoudre simultanément :

Scalabilité : Les méthodes de recherche doivent pouvoir passer à l'échelle sur des jeux de données de l'ordre du billion de tokens sans coûts de latence ou de mémoire prohibitifs.
Flexibilité Sémantique : Les requêtes en langage naturel nécessitent la récupération de textes sémantiquement similaires, acceptant les substitutions, insertions et délétions, plutôt que de se reposer uniquement sur une correspondance exacte de chaînes de caractères.
Sensibilité à l'Ordre : Contrairement aux modèles de sac de mots (ex: TF-IDF, BM25) ou à la recherche vectorielle dense (qui perd souvent l'ordre des mots), la séquence spécifique de mots dans une requête porte un sens et doit être préservée lors de la recherche.

Les approches précédentes, telles qu'infini-gram (correspondance exacte uniquement) et SoftMatcha (sémantique mais limitée par la scalabilité de l'index inversé), ne satisfont pas ces trois exigences. Plus précisément, la dépendance de SoftMatcha à l'égard des index inversés l'empêche de passer à l'échelle sur des corpus de l'ordre du billion, tandis que les moteurs de correspondance exacte manquent des variations sémantiques critiques comme la fuite de modèles (template leakage) ou le paraphrasage mineur.

Méthodologie

SoftMatcha 2 introduit un algorithme de recherche ultra-rapide et flexible qui combine des tableaux de suffixes avec des vecteurs de mots pour permettre une recherche de motifs souple (soft pattern matching) à grande échelle. L'approche repose sur deux innovations algorithmiques primaires pour atténuer l'explosion combinatoire inhérente à la relaxation sémantique :

1. Élagage Dynamique Sensible au Corpus

Pour traiter la croissance exponentielle des motifs candidats lors de l'autorisation de substitutions, d'insertions et de délétions, l'algorithme emploie une stratégie d'élagage itératif (Algorithme 1) :

Élagage Itératif : Au lieu d'énumérer tous les motifs similaires globalement, l'algorithme construit les motifs candidats token par token. À chaque étape $i$ , il génère des candidats similaires au préfixe de la requête $q_1 \dots q_i$ , puis les filtre immédiatement contre le corpus via des recherches exactes. Cela exploite la distribution de loi de puissance des n-grammes dans le langage naturel, réduisant drastiquement l'espace de recherche en écartant tôt les candidats qui n'existent pas dans le corpus.
Élagage par k-grammes : Les 2-grammes et 3-grammes à haute fréquence sont pré-vérifiés et mis en cache en RAM pour éviter l'accès au disque pour les combinaisons courantes.
Élagage par derniers bits (Last-bits Pruning) : Pour les motifs ayant très peu d'occurrences (≤50), l'algorithme énumère directement leurs occurrences dans le corpus plutôt que d'ajouter des suffixes, contourant ainsi le besoin de recherches supplémentaires dans le tableau de suffixes.

2. Tableaux de Suffixes par Étages et Sensibles au Disque

Pour gérer la taille massive de l'index (> 5 To) requis pour les corpus de billions de tokens, qui ne peut tenir entièrement en RAM, les auteurs ont conçu un nouveau tableau de suffixes sensible au disque :

Indexation en deux étapes : Inspiré de BigTable, l'index consiste en un tableau trié $X$ de tous les $L$ -tokens contigus (stocké sur disque) et un tableau creux $Y$ (stocké en RAM) contenant chaque $B$ -ième élément de $X$ .
Efficacité : Pour localiser une requête, l'algorithme utilise d'abord $Y$ pour identifier la plage approximative dans $X$ (nécessitant un accès RAM), puis effectue une recherche binaire unique dans cette plage spécifique sur le disque. Cela réduit le nombre d'accès aléatoires au disque de $O(\log|C|)$ dans les tableaux de suffixes standards à un seul accès aléatoire au disque par recherche de correspondance exacte.
Compression : Une compression par longueur de course (run-length compression) est appliquée à l'index, réduisant l'empreinte disque de l'index FineWeb-Edu de 56 To théoriques à 21,6 To.

3. Mesure de Similarité Souple

Le système définit une nouvelle fonction de similarité $sim(\bar{q}, \bar{p})$ qui intègre :

Minimum Lissé (Smooth Minimum) : Un minimum lissé paramétré des similarités cosinus entre les vecteurs de mots, évitant les pièges du minimum pur (qui ignore les scores non minimaux) et de la simple sommation (qui pénalise trop lourdement les multiples discordances).
Pénalités Basées sur la Norme : Les insertions et délétions sont pénalisées en fonction de la norme du vecteur du token inséré/supprimé (après blanchiment Zipfien), garantissant que les mots à faible information (ex: "le", "la") entraînent des pénalités plus faibles que les mots à haute information.
Seuillage Adaptatif : Le système ajuste dynamiquement le seuil de similarité $\alpha$ pour garantir le retour d'un nombre cible de résultats ( $K$ ), évitant ainsi des ensembles de résultats vides pour les requêtes difficiles.

Contributions Clés

Proposition d'Algorithme : SoftMatcha 2 est la première méthode à atteindre une recherche souple (lexicale-sémantique) avec préservation de l'ordre des mots sur des corpus de l'ordre du billion, combinant l'élagage dynamique avec des tableaux de suffixes sensibles au disque.
Analyse Théorique : L'article fournit une preuve théorique que le nombre attendu de recherches exactes est sous-linéaire par rapport à la taille du corpus ( $O(|C|^{1/\delta})$ ) sous la loi de Zipf, démontant que la stratégie d'élagage atténue efficacement la croissance exponentielle de l'espace de recherche.
Performance Empirique :
- Latence : Sur FineWeb-Edu (1,4 billion de tokens), SoftMatcha 2 atteint un 95e percentile de latence de 278,17 ms pour la recherche souple et de 0,34 ms pour la recherche exacte.
- Comparaison : Il est 33 fois plus rapide qu'infini-gram pour la recherche exacte et surpasse significativement SoftMatcha (qui expire ou atteint ses limites de mémoire sur de grands corpus).
- Multilinguisme : La méthode passe à l'échelle efficacement pour le chinois (38,3 milliards de tokens) et le japonais (169 milliards de tokens) avec des latences inférieures à 400 ms.
Applications Pratiques : Les auteurs démontrent l'utilité de l'outil dans :
- Détection de Contamination : Identifier la "contamination sémantique" et la "fuite de modèles" (ex: substitutions numériques dans les problèmes mathématiques) dans les corpus d'entraînement que les outils de correspondance exacte manquent.
- Recherche d'Information et Détection de Paraphrase : Surpasser les bases de référence comme BM25, infini-gram et SoftMatcha dans les tâches de récupération et de détection de paraphrase.

Signification et Revendications

Les auteurs positionnent SoftMatcha 2 comme un outil d'infrastructure critique pour la communauté de recherche en LLM. Sa principale importance réside dans la capacité à permettre une inspection exhaustive et sémantiquement consciente des données d'entraînement à une échelle auparavant impossible. En révélant des formes subtiles de contamination de benchmarks (similarité sémantique et fuite de modèles) que les outils de correspondance exacte ignorent, la méthode offre un moyen plus rigoureux d'évaluer l'hygiène des données et le comportement des modèles.

L'article note modestement des limitations : la méthode opère au niveau du mot et ne peut capturer les variations sémantiques multi-mots (ex: "U.S." vs "États-Unis") sans augmenter les candidats de substitution à un degré qui compromettrait la latence. De plus, le système nécessite des ressources disque et mémoire importantes proportionnelles à la taille du corpus. Cependant, les auteurs soutiennent que la capacité d'effectuer une recherche souple en moins de 0,3 seconde sur des jeux de données de billions de tokens représente un bond en avant substantiel pour l'analyse de corpus, la recherche d'information et la détection de fuites de données dans les pipelines d'entraînement de l'IA.