💬 NLP

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

SoftMatcha 2 is een ultra-snel, flexibel zoekalgoritme dat semantische patroonmatching in minder dan 0,3 seconden mogelijk maakt over corpora op triljoenenschaal door gebruik te maken van suffix-arrays, vectorgebaseerde woordrepresentaties en dynamische corpusbewuste pruning om combinatorische explosie te mitigeren.

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

Gepubliceerd 2026-06-11

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

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

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een bibliotheek hebt met één biljoen boeken. Dat is niet zomaar veel boeken; het is een bibliotheek die zo enorm is dat als je elk woord zou proberen te lezen, het je miljoenen jaren zou kosten. Stel je nu voor dat je een specifieke zin in die bibliotheek wilt vinden, maar je herinnert je de exacte woorden niet meer. Misschien herinner je je het idee, of weet je dat de zin er net even anders uitzag (bijv. je herinnert je "belang van de machine" maar het boek zegt eigenlijk "betekenis van de machine").

Dit is het probleem dat SoftMatcha 2 oplost. Het is een super-snelle zoekmachine die ontworpen is om tekst te vinden in deze triljoen-schaal bibliotheken in minder dan een derde van een seconde, zelfs wanneer je zoekopdracht geen exacte match is.

Hier is hoe het werkt, uitgelegd met eenvoudige analogieën:

1. Het Probleen: De "Combinatorische Explosie"

Als je een computer vraagt om tekst te vinden die "vergelijkbaar" is met je zoekopdracht, krijgt deze te maken met een nachtmerriescenario.

De Analogie: Stel je voor dat je op zoek bent naar een specifiek recept in een kookboek. Als je zegt: "Zoek iets dat lijkt op 'chocoladekoek'", moet de computer alle mogelijke variaties controleren: "chocolademuffin", "pure chocoladekoek", "chocoladegebak", "chocoladekoek met noten", "chocoladekoek zonder noten", enzovoort.
Het Probleem: Naarmate je zoekopdracht langer wordt, explodeert het aantal mogelijke variaties exponentieel. Het is alsof je een naald in een hooiberg probeert te vinden, maar de hooiberg elke keer dat je kijkt, verandert in een berg. Eerdere tools raakten ofwel vastgelopen in de berg, of ze zochten alleen naar de exacte naald, waardoor ze de vergelijkbare exemplaren misten.

2. De Oplossing: Twee Magische Trucs

SoftMatcha 2 gebruikt twee slimme trucs om deze berg aan mogelijkheden te temmen:

Truc A: De "Slimme Filter" (Dynamic Corpus-Aware Pruning)

In plaats van elke mogelijke variatie van je zoekopdracht te controleren, controleert het systeem eerst wat er daadwerkelijk in de bibliotheek bestaat.

De Analogie: Stel je voor dat je op zoek bent naar een specif kind type auto op een enorme parkeerplaats. In plaats van elke mogelijke auto die zou kunnen bestaan te controleren (zoals een "vliegende auto" of een "onderwaterauto"), kijk je eerst naar de parkeerplaats en zeg je: "Oké, ik zie hier rode sedans en blauwe vrachtwagens, maar geen vliegende auto's."
Hoe het werkt: Het systeem bouwt een lijst van vergelijkbare woorden (zoals synoniemen), maar gooit direct elke combinatie weg die niet daadwerkelijk in de triljoen-woord bibliotheek voorkomt. Het gebruikt de statistische "vorm" van taal (zoals het feit dat sommige woorden zeer gebruikelijk zijn en andere zeldzaam) om de onmogelijke opties uit te sluiten voordat de zoektocht überhaupt begint. Dit voorkomt dat de zoekruimte explodeert.

Truc B: De "Disk-Aware Map" (Fast Exact Lookup)

De bibliotheek is te groot om in het hoofdgeheugen (RAM) van de computer te passen, dus leeft deze op een harde schijf (disk). Lezen van een harde schijf is meestal traag, zoals naar een magazijn lopen om een boek te pakken.

De Analogie: Stel je een standaard bibliotheek voor waar je eerst naar de plank moet lopen, het boek moet vinden, weer terug moet lopen, en dit honderden keren moet herhalen. SoftMatcha 2 bouwt een speciale "kaart" (een Suffix Array) die de bibliothecaris precies vertelt waar hij heen moet gaan.
De Innovatie: De meeste zoektools vereisen dat de bibliothecaris vele reisjes naar het magazijn maakt om een boek te vinden. De nieuwe kaart van SoftMatcha 2 is zo ontworpen dat de bibliothecaris slechts één enkele reis naar het magazijn hoeft te maken om de exacte locatie te vinden. Dit maakt het vinden van de exacte tekst ongelooflijk snel, ook al is de bibliotheek op een trage harde schijf opgeslagen.

3. Wat het Kan (Het "Soft" Deel)

Omdat het deze snelheidstricks combineert met een begrip van woordbetekenissen (door middel van word vectors), kan het "soft" zoekopdrachten aan:

Substitutie: Je zoekt naar "gouden medaille" en het vindt "zilveren medaille" (omdat ze aan elkaar gerelateerd zijn).
Invoeging/Verwijdering: Je zoekt naar "belang van machine" en het vindt "belang van de machine" (een woord toegevoegd) of "belang van machine learning" (woorden toegevoegd).
Volgorde is Belangrijk: In tegen tegenstelling tot andere tools die alleen naar een "zak met woorden" kijken, respecteert SoftMatcha 2 de volgorde. Het weet dat "hond bijt man" anders is dan "man bijt hond".

4. Resultaten in de Praktijk

Het onderzoeksteam testte dit op FineWeb-Edu, een dataset met 1,4 biljoen woorden.

Snelheid: Het vond resultaten in minder dan 0,3 second seconden.
Vergelijking: Het was 33 keer sneller dan de vorige beste tool voor exacte zoekopdrachten (infini-gram) en aanzienlijk sneller dan de vorige "soft" zoektool (SoftMatcha), die bibliotheken van deze omvang helemaal niet kon verwerken.
Ontdekking: Omdat het zo goed is in het vinden van "bijna matches", hebben de onderzoekers het gebruikt om contaminatie in trainingsdata op te sporen. Ze ontdekten dat sommige testvragen die gebruikt worden in AI-benchmarks in licht gewijzigde vormen in de trainingsdata waren verschenen (bijv. getallen veranderd of woorden omgewisseld), wat eerdere tools voor exacte matches miste. Dit is vergelijkbaar met het vinden van een student die het antwoordblad heeft uit het hoofd geleerd, maar de cijfers net even heeft aangepast om te vals te spelen.

Samenvatting

SoftMatcha 2 is een super-snelle bibliothecaris voor de grootste bibliotheken ter wereld. Het zoekt niet alleen naar exacte kopieën van je verzoek; het begrijpt de betekenis en vindt vergelijkbare zinnen, zelfs als je een woord vergeet of een woord vervangt door een synoniem. Dit doet het door slimweg de onmogelijke opties te negeren en een uiterst efficiënte kaart te gebruiken om door de enorme hoeveelheid opgeslagen data te navigeren, en dat allemaal in een oogwenk.

Technische Samenvatting: SoftMatcha 2

Probleemstelling

De snelle schaling van Large Language Models (LLMs) heeft noodzaardig gemaakt dat trainingscorpora bereiken tot biljoenen tokens (bijv. FineWeb-Edu met 1,4 biljoen tokens). Bestaande hulpmiddelen voor het doorzoeken van deze corpora worden geconfronteerd met drie specifieke uitdagingen die huidige methoden niet gelijktijdig kunnen aanpakken:

Schaalbaarheid: Zoekmethoden moeten schalen naar corpora van biljoenen tokens zonder excessieve latentie of geheugenkosten.
Semantische Flexibiliteit: Natuurlijke taalvragen vereisen de ophaalbaarheid van tekst die semantisch vergelijkbaar is, waarbij rekening wordt gehouden met substituties, inserties en deleties, in plaats van uitsluitend te vertrouwen op exacte string-matching.
Ordegevoeligheid: In tegenstelling tot bag-of-words modellen (bijv. TF-IDF, BM25) of dense vector search (die vaak de woordvolgorde verliezen), draagt de specifieke sequentie van woorden in een query betekenis en moet deze behouden blijven tijdens het zoeken.

Eerdere benaderingen, zoals infini-gram (alleen exacte matches) en SoftMatcha (semantisch maar beperkt door de schaalbaarheid van inverted indices), voldoen niet aan alle drie de vereisten. Specifiek verhindert de afhankelijkheid van SoftMatcha van inverted indices het schalen naar corpora op biljoentenschaal, terwijl exact-match tools kritieke semantische variaties zoals template leakage of lichte parafrasering missen.

Methodologie

SoftMatcha 2 introduceert een ultra-snel, flexibel zoekalgoritme dat suffix arrays combineert met woordvectoren om soft pattern matching op schaal mogelijk te maken. De aanpak is gebouwd op twee primaire algoritmische innovaties om de combinatorische explosie die inherent is aan semantische relaxatie te mitigeren:

1. Dynamische Corpus-bewuste Pruning

Om de exponentiële groei van kandidaat-patronen aan te pakken wanneer substituties, inserties en deleties worden toegestaan, gebruikt het algoritme een iteratieve pruning-strategie (Algoritme 1):

Iteratieve Pruning: In plaats van alle mogelijke vergelijkbare patronen globaal te enumereren, bouwt het algoritme kandidaat-patronen op token-voor-token. In elke stap $i$ genereert het kandidaten die vergelijkbaar zijn met de query-prefix $q_1 \dots q_i$ , en filtert deze vervolgens onmiddellijk tegen de corpus middels exacte lookups. Dit maakt gebruik van de power-law distributie van n-grams in natuurlijke taal, waardoor de zoekruimte drastisch wordt verkleind door kandidaten die niet in de corpus voorkomen vroegtijdig te verwerpen.
k-gram Pruning: Veelvoorkomende 2-grams en 3-grams worden vooraf gecontroleerd en gecached in het RAM-geheugen om disktoegang voor veelvoorkomende combinaties te vermijden.
Last-bits Pruning: Voor patronen met zeer weinig voorkomens (≤50), enumereert het algoritme direct hun voorkomens in de corpus in plaats van suffixes toe te voegen, waardoor verdere suffix array lookups worden omzeild.

2. Disk-bewuste, Gefaseerde Suffix Arrays

Om de enorme indexgrootte (>5 TB) aan te kunnen die vereist is voor corpora van biljoenen tokens, die niet volledig in het RAM-geheugen passen, hebben de auteurs een nieuwe disk-bewuste suffix array ontworpen:

Tweefasige Indexering: Geïnspireerd door BigTable, bestaat de index uit een gesorteerde array $X$ van alle opeenvolgende $L$ -tokens (opgeslagen op disk) en een ijle (sparse) array $Y$ (opgeslagen in RAM) die elk $B$ -de element van $X$ bevat.
Efficiëntie: Om een query te lokaliseren, gebruikt het algoritme eerst $Y$ om het benaderde bereik in $X$ te identificeren (wat één RAM-toegang vereist), en voert vervolgens een enkele binaire zoekopdracht uit binnen dat specifieke bereik op disk. Dit reduceert het aantal willekeurige diskaccessen van $O(\log|C|)$ in standaard suffix arrays naar één willekeurige diskaccess per exacte match lookup.
Compressie: Run-length compressie wordt toegepast op de index, waardoor de disk-voetafdruk van de FineWeb-Edu index van een theoretische 56 TB naar 21,6 TB wordt gereduceerd.

3. Soft Gelijkenismaat

Het systeem definieert een nieuwe gelijkenisfunctie $sim(\bar{q}, \bar{p})$ die het volgende integreert:

Smooth Minimum: Een geparametriseerd smooth minimum van cosine similarities tussen woordvectoren, wat de valkuilen van het gewone minimum (dat niet-minimale scores negeert) en eenvoudige sommatie (die meerdere mismatches te zwaar bestraft) vermijdt.
Norm-gebaseerde Straffen: Inserties en deleties worden gestraft op basis van de norm van de vector van het geïnjecteerde/gedeleteerde token (na Zipfiaanse whitening), wat ervoor zorgt dat woorden met een lage informatiedichtheid (bijv. "de", "het") minder straf krijgen dan woorden met een hoge informatiedichtheid.
Adaptieve Drempelwaarde: Het systeem past de gelijkenisdrempel $\alpha$ dynamisch aan om een doel aantal resultaten ( $K$ ) te garanderen, wat lege resultaatsets voor moeilijke queries voorkomt.

Belangrijkste Bijdragen

Algoritme Voorstel: SoftMatcha 2 is de eerste methode die soft (lexicaal-semantische) zoekopdrachten met behoud van woordvolgorde bereikt op corpora van biljoenen tokens, door dynamische pruning te combineren met disk-bewuste suffix arrays.
Theoretische Analyse: Het paper levert een theoretisch bewijs dat het verwachte aantal exacte lookups sublineair is ten opzichte van de corpusgrootte ( $O(|C|^{1/\delta})$ ) onder de wet van Zipf, wat aantoont dat de pruning-strategie de exponentiële groei van de zoekruimte effectief mitigeert.
Empirische Prestaties:
- Latentie: Op FineWeb-Edu (1,4 biljoen tokens) bereikt SoftMatcha 2 een 95e percentiel latentie van 278,17 ms voor soft search en 0,34 ms voor exact search.
- Vergelijking: Het is 33 keer sneller dan infini-gram voor exact search en presteert aanzienlijk beter dan SoftMatcha (dat time-outs ervaart of de geheugenlimieten bereikt op grote corpora).
- Meertaligheid: De methode schaalt effectief naar Chinees (38,3 miljard tokens) en Japans (169 miljard tokens) met latenties onder de 400 ms.
Praktische Toepassingen: De auteurs demonstreren het nut van het hulpmiddel bij:
- Contaminatie Detectie: Het identificeren van "semantische contaminatie" en "template leakage" (bijv. numerieke substituties in wiskundige problemen) in trainingscorpora die exact-match tools missen.
- Informatie Retrieval & Parafrase Detectie: Het overtreft baselines zoals BM25, infini-gram en SoftMatcha in retrieval en parafrase detectie taken.

Betekenis en Claims

De auteurs positioneren SoftMatcha 2 als een cruciaal infrastructuurhulpmiddel voor de LLM-research community. De primaire betekenis ligt in het mogelijk maken van een uitputtende, semantisch bewuste inspectie van trainingsdata op een schaal die voorheen onmogelijk was. Door subtiele vormen van benchmark-contaminatie (semantische gelijkenis en template leakage) bloot te leggen die exact-match tools over het hoofd zien, biedt de methode een rigoureuzere manier om datahygiëne en modelgedrag te evalueren.

Het paper merkt bescheiden beperkingen op: de methode opereert op woordniveau en kan geen multi-word semantische variaties vangen (bijv. "U.S." versus "United States") zonder de substitutie-kandidaten zodanig te verhogen dat de latentie in het gedrang komt. Daarnaast vereist het systeem aanzienlijke disk- en geheugenbronnen proportioneel aan de corpusgrootte. De auteurs argumenteren echter dat het vermogen om een soft search uit te voeren in minder dan 0,3 seconden op corpora van biljoenen tokens een substantiële sprong voorwaarts vertegenwoordigt voor corpusanalyse, informatie retrieval en de detectie van data leakage in AI-trainingspipelines.