💬 NLP

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

SoftMatcha 2 ist ein ultraschneller, flexibler Suchalgorithmus, der durch die Nutzung von Suffix-Arrays, vektorbasierten Wortrepräsentationen und dynamischer korpusbewusster Pruning-Verfahren zur Minderung kombinatorischer Explosionen eine semantische Mustererkennung über Trillionen-Skala-Korpora in unter 0,3 Sekunden ermöglicht.

Ursprüngliche Autoren: Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

Veröffentlicht 2026-06-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie besitzen eine Bibliothek mit einer Billion Büchern. Das ist nicht nur eine große Menge an Büchern; es ist eine Bibliothek, die so gewaltig ist, dass Sie Millionen von Jahren bräuchten, um jedes einzelne Wort zu lesen. Nun stellen Sie sich vor, Sie möchten einen bestimmten Satz in dieser Bibliothek finden, aber Sie erinnern sich nicht exakt an die Worte. Vielleicht erinnern Sie sich an die Idee oder Sie wissen, dass der Satz etwas anders lautete (z. B. erinnern Sie sich an „Bedeutung der Maschine“, aber das Buch sagt eigentlich „Signifikanz der Maschine“).

Dies ist das Problem, das SoftMatcha 2 löst. Es ist eine superschnelle Suchmaschine, die darauf ausgelegt ist, Text in solchen Bibliotheken im Billionen-Maßstab in weniger als einem Drittel einer Sekunde zu finden, selbst wenn Ihre Suchanfrage keine exakte Übereinstimmung ist.

So funktioniert es, aufgeschlüsselt mit einfachen Analogien:

1. Das Problem: Die „kombinatorische Explosion“

Wenn Sie einen Computer bitten, Text zu finden, der Ihrer Suchanfrage „ähnlich“ ist, steht er vor einem Albtraumszenario.

Die Analogie: Stellen Sie sich vor, Sie suchen ein bestimmtes Rezept in einem Kochbuch. Wenn Sie sagen: „Finde mir etwas wie ‚Schokoladenkuchen‘“, muss der Computer jede mögliche Variation prüfen: „Schokoladenmuffin“, „dunkler Schokoladenkuchen“, „Schokoladenkuchen mit Nüssen“, „Schokoladenkuchen ohne Nüsse“ usw.
Das Problem: Wenn Ihre Suchanfrage länger wird, explodiert die Anzahl der möglichen Variationen exponentiell. Es ist, als würde man versuchen, eine Nadel im Heuhaufen zu finden, aber der Heuhaufen wächst bei jedem Blick zu einem Berg an. Frühere Werkzeuge blieben entweder im Berg stecken oder suchten nur nach der exakten Nadel und übersahen die ähnlichen Exemplare.

2. Die Lösung: Zwei magische Tricks

SoftMatcha 2 nutzt zwei kluge Tricks, um diesen Berg an Möglichkeiten zu bändigen:

Trick A: Der „Intelligente Filter“ (Dynamic Corpus-Aware Pruning)

Anstatt jede mögliche Variation Ihrer Suche zu prüfen, schaut das System zuerst nach, was tatsächlich in der Bibliothek existiert.

Die Analogie: Stellen Sie sich vor, Sie suchen ein bestimmtes Automodell auf einem riesigen Parkplatz. Anstatt jedes mögliche Automodell zu prüfen, das existieren könnte (wie ein „Flugauto“ oder ein „Unterwasserauto“), schauen Sie zuerst auf den Parkplatz und sagen: „Okay, ich sehe hier rote Limousinen und blaße LKWs, aber keine Flugautos.“
Wie es funktioniert: Das System erstellt eine Liste ähnlicher Wörter (wie Synonyme), wirft aber sofort jede Kombination weg, die nicht tatsächlich in der Billion-Wörter-Bibliothek vorkommt. Es nutzt die statistische „Form“ der Sprache (wie zum Beispiel, dass manche Wörter sehr häufig und andere sehr selten sind), um die unmöglichen Optionen auszuschließen, noch bevor es überhaupt mit der Suche beginnt. Dies verhindert, dass sich der Suchraum aufbläht.

Trick B: Die „Disk-bewusste Karte“ (Fast Exact Lookup)

Die Bibliothek ist zu groß, um in den Hauptspeicher (RAM) des Computers zu passen, also lebt sie auf einer Festplatte (Disk). Das Lesen von einer Festplatte ist normalerweise langsam, wie ein Gang zum Lagerhaus, um ein Buch zu holen.

Die Analogie: Stellen Sie sich eine Standardbibliothek vor, in der Sie zum Regal gehen müssen, das Buch finden, zurückgehen und dies hunderte Male wiederholen müssen. SoftMatcha 2 erstellt eine spezielle „Karte“ (ein Suffix Array), die dem Bibliothekar genau sagt, wohin er gehen muss.
Die Innovation: Die meisten Suchwerkzeuge erfordern, dass der Bibliothekar viele Wege zum Lagerhaus macht, um ein Buch zu finden. Die neue Karte von SoftMatcha 2 ist so konzipiert, dass der Bibliothekar nur einen einzigen Weg zum Lagerhaus machen muss, um den exakten Ort zu finden. Dies macht das Finden des exakten Textes unglaublich schnell, obwohl die Bibliothek auf einem langsamen Datenträger gespeichert ist.

3. Was es kann (Der „Soft“-Teil)

Da es diese Geschwindigkeitstricks mit einem Verständnis für Wortbedeutungen (unter Verwendung von Wortvektoren) kombiniert, kann es „weiche“ Suchen bewältigen:

Substitution: Sie suchen nach „Goldmedaille“ und es findet „Silbermedaille“ (da sie verwandt sind).
Einfügung/Löschung: Sie suchen nach „Bedeutung der Maschine“ und es findet „Bedeutung der Maschine“ (Hinzufügen eines Wortes) oder „Bedeutung von maschinellem Lernen“ (Hinzufügen mehrerer Wörter).
Reihenfolge spielt eine Rolle: Im Gegensatz zu anderen Tools, die nur nach einem „Sack voller Wörter“ suchen, achtet SoftMatcha 2 auf die Reihenfolge. Es weiß, dass „Hund beißt Mann“ etwas anderes ist als „Mann beißt Hund“.

4. Reale Ergebnisse

Das Paper testete dies auf FineWeb-Edu, einem Datensatz mit 1,4 Billion Wörtern.

Geschwindigkeit: Es fand Ergebnisse in unter 0,3 Sekunden.
Vergleich: Es war 33-mal schneller als das bisher beste Werkzeug für die exakte Suche (infini-gram) und signifikant schneller als das bisherige „Soft“-Suchwerkzeug (SoftMatcha), das Bibliotheken dieser Größe gar nicht erst bewältigen konnte.
Entdeckung: Da es so gut darin ist, „fast exakte Treffer“ zu finden, nutzten die Forscher es, um Kontaminationen in Trainingsdaten aufzuspüren. Sie fanden heraus, dass einige Testfragen, die in KI-Benchmarks verwendet wurden, in leicht veränderter Form (z. B. Zahlen geändert oder Wörter vertauscht) bereits in den Trainingsdaten vorkamen, was bisherige Exakt-Match-Tools übersehen hatten. Dies ist vergleichbar mit dem Aufspüren eines Schülers, der die Antwortschlüssel auswendig gelernt hat, aber die Zahlen leicht verändert hat, um zu schummeln.

Zusammenfassung

SoftMatcha 2 ist ein superschneller Bibliothekar für die größten Bibliotheken der Welt. Es sucht nicht nur nach exakten Kopien Ihrer Anfrage; es versteht die Bedeutung und findet ähnliche Sätze, selbst wenn Sie ein Wort vergessen oder ein Wort durch ein Synonym ersetzen. Dies erreicht es, indem es intelligente Optionen ignoriert und eine hocheffiziente Karte nutzt, um durch die massiven Datenspeicher zu navigieren – und das alles in einem Wimpernschlag.

Technisches Resümee: SoftMatcha 2

Problemstellung

Die schnelle Skalierung von Large Language Models (LLMs) hat dazu geführt, dass Trainingskorpora Trillionen von Token erreichen müssen (z. B. FineWeb-Edu mit 1,4 T Trillionen Tokens). Bestehende Werkzeuge für die Suche in diesen Korpora stehen vor drei distinkten Herausforderungen, die aktuelle Methoden nicht gleichzeitig adressieren können:

Skalierbarkeit: Suchmethoden müssen auf Trillionen-Token-Datensätze skalieren können, ohne prohibitive Latenz- oder Speicherkosten zu verursachen.
Semantische Flexibilität: Natürliche Sprachabfragen erfordern den Abruf von Texten, die semantisch ähnlich sind, wobei Substitutionen, Einfügungen und Löschungen berücksichtigt werden müssen, anstatt sich rein auf das exakte String-Matching zu verlassen.
Ordnungssensitivität: Im Gegensatz zu Bag-of-Words-Modellen (z. B. TF-IDF, BM25) oder Dense-Vektor-Suche (die oft die Wortreihenfolge verlieren) trägt die spezifische Sequenz von Wörtern in einer Abfrage Bedeutung und muss während der Abfrage bewahrt werden.

Vorherige Ansätze wie infini-gram (nur exakter Treffer) und SoftMatcha (semantisch, aber begrenzt durch die Skalierbarkeit inverser Indizes) erfüllen nicht alle drei Anforderungen. Insbesondere die Abhängigkeit von SoftMatcha von inversen Indizes verhindert, dass es auf Trillionen-Skala skalierbar ist, während exakte Matcher kritische semantische Variationen wie Template-Leakage oder geringfügiges Paraphrasieren übersehen.

Methodik

SoftMatcha 2 führt einen ultraschnellen, flexiblen Suchalgorithmus ein, der Suffix-Arrays mit Wortvektoren kombطiniert, um eine weiche Mustererkennung (Soft Pattern Matching) in großem Maßstab zu ermöglichen. Der Ansatz basiert auf zwei primären algorithmischen Innovationen, um die kombinatorische Explosion zu mildern, die mit semantischer Relaxation einhergeht:

1. Dynamische korpusbewusste Pruning-Verfahren (Pruning)

Um das exponentielle Wachstum von Kandidatenmustern bei Erlaubnis von Substitutionen, Einfügungen und Löschungen zu adressieren, verwendet der Algorithmus eine iterative Pruning-Strategie (Algorithmus 1):

Iteratives Pruning: Anstatt alle ähnlichen Muster global zu enumerieren, baut der Algorithmus Kandidatenmuster Token für Token auf. In jedem Schritt $i$ generiert er Kandidaten, die ähnlich zum Query-Präfix $q_1 \dots q_i$ sind, und filtert diese dann unmittelbar gegen das Korpus mittels exakter Lookups. Dies nutzt die Potenzgesetzverteilung von n-Grammen in der natürlichen Sprache aus, indem der Suchraum drastisch reduziert wird, indem Kandidaten, die nicht im Korpus existieren, frühzeitig verworfen werden.
k-Gram Pruning: Hochfrequente 2-Gramme und 3-Gramme werden vorab geprüft und im RAM zwischengespeichert, um den Festplattenzugriff für häufige Kombinationen zu vermeiden.
Last-bits Pruning: Für Muster mit sehr wenigen Vorkommen (≤50) enumeriert der Algorithmus deren Vorkommen direkt im Korpus, anstatt Suffixe anzuhängen, wodurch die Notwendigkeit weiterer Suffix-Array-Lookups umgangen wird.

2. Disk-bewusste, gestufte Suffix-Arrays

Um das massive Indexvolumen (>5 TB) zu bewältigen, das für Trillionen-Token-Korpora erforderlich ist und nicht vollständig in den RAM passt, haben die Autoren ein neues disk-bewusstes Suffix-Array entwickelt:

Zweistufige Indizierung: Inspiriert von BigTable besteht der Index aus einem sortierten Array $X$ aller zusammenhängenden $L$ -Tokens (auf der Festplatte gespeichert) und einem dünnbesetzten Array $Y$ (im RAM gespeichert), das jedes $B$ -te Element von $X$ enthält.
Effizienz: Um eine Abfrage zu lokalisieren, verwendet der Algorithmus zuerst $Y$ , um den ungefähren Bereich in $X$ zu identifizieren (was einen RAM-Zugriff erfordert), und führt dann eine einzige Binärsuche innerhalb dieses spezifischen Bereichs auf der Festplatte durch. Dies reduziert die Anzahl der zufälligen Festplattenzugriffe von $O(\log|C|)$ bei Standard-Suffix-Arrays auf einen einzigen zufälligen Festplattenzugriff pro exaktem Match-Lookup.
Kompression: Auf den Index wird eine Run-Length-Kompression angewendet, die den Festplatten-Footprint des FineWeb-Edu-Index von theoretisch 56 TB auf 21,6 TB reduziert.

3. Weiches Ähnlichkeitsmaß

Das System definiert eine neuartige Ähnlichkeitsfunktion $sim(\bar{q}, \bar{p})$ , die Folgendes integriert:

Smooth Minimum: Ein parametrisiertes Smooth Minimum der Kosinus-Ähnlichkeiten zwischen Wortvektoren, das die Fallstricke des einfachen Minimums (das nicht-minimale Scores ignoriert) und der einfachen Summation (die mehrere Mismatch-Fehler übermäßig bestraft) vermeidet.
Norm-basierte Strafen: Einfügungen und Löschungen werden basierend auf der Norm des eingefügten/gelöschten Token-Vektors (nach Zipfianischer Weißung) bestraft, wodurch sichergestellt wird, dass Wörter mit geringem Informationsgehalt (z. B. "der", "die", "das") geringere Strafen erhalten als hochinformative Wörter.
Adaptive Schwellenwertbildung: Das System passt den Ähnlichkeitsschwellenwert $\alpha$ dynamisch an, um eine Zielanzahl von Ergebnissen ( $K$ ) zu gewährleisten und leere Ergebnismengen bei schwierigen Abfragen zu verhindern.

Kernbeiträge

Algorithmus-Vorschlag: SoftMatcha 2 ist die erste Methode, die eine weiche (lexikalisch-semantische) Suche mit Wahrung der Wortreihenfolge auf Trillionen-Skala erreicht, indem sie dynamisches Pruning mit disk-bewussten Suffix-Arrays kombiniert.
Theoretische Analyse: Die Arbeit liefert einen theoretischen Beweis, dass die erwartete Anzahl der exakten Lookups unter dem Zipf-Gesetz sublinear zur Korpusgröße ist ( $O(|C|^{1/\delta})$ ), was zeigt, dass die Pruning-Strategie das exponentielle Wachstum des Suchraums effektiv mildert.
Empirische Leistung:
- Latenz: Auf FineWeb-Edu (1,4 T Tokens) erreicht SoftMatcha 2 eine 95. Perzentil-Latenz von 278,17 ms für die weiche Suche und 0,34 ms für die exakte Suche.
- Vergleich: Es ist 33 Mal schneller als infini-gram bei der exakten Suche und übertrifft SoftMatcha signifikant (welches bei großen Korpora Zeitüberschreitungen aufweist oder an Speicherlimits stößt).
- Mehrsprachigkeit: Die Methode skaliert effektiv auf Chinesisch (38,3 B Tokens) und Japanisch (169 B Tokens) mit Latenzen unter 400 ms.
Praktische Anwendungen: Die Autoren demonstrieren den Nutzen des Werkzeugs in:
- Kontaminationserkennung: Identifizierung von "semantischer Kontamination" und "Template-Leakage" (z. B. numerische Substitutionen in Mathematikaufgaben) in Trainingskorpora, die von exakten Match-Tools übersehen werden.
- Informationsabfrage & Paraphrase-Erkennung: Übertreffen von Baselines wie BM25, infini-gram und SoftMatcha in Aufgaben zur Informationsabfrage und Paraphrase-Erkennung.

Bedeutung und Ansprüche

Die Autoren positionieren SoftMatcha 2 als kritisches Infrastrukturwerkzeug für die LLM-Forschungsgemeinschaft. Seine primäre Bedeutung liegt in der Ermöglichung einer erschöpfenden, semantisch bewussten Inspektion von Trainingsdaten in einem Ausmaß, das zuvor unmöglich war. Indem es subtile Formen der Benchmark-Kontamination (semantische Ähnlichkeit und Template-Leakage) aufdeckt, die exakte Match-Tools übersehen, bietet die Methode eine rigorosere Art, Datenhygiene und Modellverhalten zu evaluieren.

Das Paper weist bescheiden auf Limitationen hin: Die Methode operiert auf Wortebene und kann keine mehrwortigen semantischen Variationen (z. B. "U.S." vs. "United States") erfassen, ohne die Anzahl der Substitutionskandidaten so stark zu erhöhen, dass die Latenz gefährdet wird. Zudem benötigt das System erhebliche Festplatten- und Speicherressourcen proportional zur Korpusgröße. Die Autoren argumentieren jedoch, dass die Fähigkeit, eine weiche Suche in unter 0,3 Sekunden auf Trillionen-Token-Datensätzen durchzuführen, einen bedeutenden Fortschritt für die Korpusanalyse, Informationsabfrage und die Erkennung von Data Leakage in KI-Trainingspipelines darstellt.