🤖 machine learning

Discovering Lattice Reduction Strategies via Self-Play

Dieses Paper stellt DeltaStar vor, einen mittels Self-Play trainierten Deep-Reinforcement-Learning-Agenten, der eine überlegene Gitterreduktionsstrategie entdeckt, die weniger Operationen als der klassische LLL-Algorithmus erfordert und eine Zero-Shot-Generalisierung auf höhere Dimensionen sowie ungesehene Moduli demonstriert.

Ursprüngliche Autoren: Mohamed Malhou, Kristin Lauter, Ludovic Perret

Veröffentlicht 2026-06-16

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mohamed Malhou, Kristin Lauter, Ludovic Perret

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 haben einen verhedderten Wollknäuel. Ihr Ziel ist es, den Faden zu entwirren und die Stränge so anzuordnen, dass sie so gerade und kurz wie möglich sind. In der Welt der Mathematik und Kryptographie wird dieser „Faden“ als Gitter (Lattice) bezeichnet, und die „Stränge“ sind Vektoren. Das Finden der kürzesten, geradesten Anordnung ist entscheidend, um digitale Geheimnisse sicher zu halten, aber es ist unglaublich schwierig, dies von Hand zu erledigen, besonders wenn der Wollknäuel riesig wird.

Seit Jahrzehnten ist das Standardwerkzeug zum Entwirren dieses Wollknäuels ein Algorithmus namens LLL. Betrachten Sie LLL als einen sehr strengen, regelbefolgenden Roboter. Er hat zwei einfache Bewegungen:

Größenreduktion (Size Reduction): Er zieht einen Strang fest gegen die vorangehenden Stränge, um die Schlappheit zu entfernen.
Vertauschen (Swapping): Wenn ein Strang aus der Reihe tanzt, vertauscht er ihn mit dem Nachbarn.

Der Roboter entscheidet sich für ein Vertauschen bas-ierend auf einer starren, handschriftlichen Regel (der „Lovász-Bedingung“). Während diese Regel garantiert, dass der Roboter seine Aufgabe in einer angemessenen Zeit erledigt, liefert sie nicht immer das perfekt entwirrte Ergebnis. Es ist, als würde man einer Karte folgen, die einen zwar in die Stadt bringt, man aber dennoch einige unnötige Umwege nimmt.

Die Neuentdeckung: „Delta-Star“

Die Autoren dieser Arbeit stellten eine einfache Frage: Was wäre, wenn wir dem Roboter nicht ein starres Regelbuch gaben, sondern ihm stattdunk, das Spiel des Entwirrens auf eigene Faust zu spielen?

Sie entwickelten einen KI-Agenten namens Delta-Star mittels einer Technik namens Deep Reinforcement Learning. Hier ist die Erklärung, wie sie dies umgesetzt haben, unter Verwendung einiger kreativer Analogien:

1. Das Trainingsgelände (Der „kleine Wollknäuel“)

Sie warfen die KI nicht in einen massiven, unmöglichen Knoten. Stattdessen trainierten sie sie auf kleinen, handhabbaren 8-dimensionalen Gittern (denken Sie an einen kleinen, 8-strängigen Wollknäuel).

Das Spiel: Die KI spielt ein Einzelspielerspiel, bei dem sie nur dieselben zwei Bewegungen ausführen kann (festziehen oder vertauschen).
Das Ziel: Die KI erhält Punkte dafür, dass sie den Faden kürzer und gerader macht. Sie verliert Punkte, wenn sie zu viele Schritte benötigt.
Der Lehrer: Die KI lernt, indem sie Millionen von Malen gegen sich selbst spielt (Self-Play). Sie probiert eine Bewegung aus, sieht, ob sie hilft, und wenn nicht, vergisst sie diese Bewegung beim nächsten Mal.

2. Die „Kristallkugel“-Strategie (Adaptive Horizon MCTS)

Der cleverste Teil ihres Systems ist die Art und Weise, wie die KI vorausdenkt.

Standardmäßiges Denken: Normalerweise schaut eine KI einen Schritt nach vorne, dann den nächsten, dann den nächsten. Das ist langsam und rechenintensiv.
Delta-Stars Denken: Die KI besitzt eine „Kristallkugel“, die die nächsten an mehreren Schritten gleichzeitig vorhersagt.
- Wenn die Kristallkugel sagt: „Die nächsten 10 Schritte sind offensichtlich und automatisch“, überspringt die KI diese sofort.
- Wenn die Kristallkugel sagt: „Halt, der nächste Schritt ist eine schwierige Entscheidung mit vielen Möglichkeiten“, hält die KI inne und denkt tief über genau diesen Moment nach.
Die Analogie: Stellen Sie sich vor, Sie fahren ein Auto. Auf einer geraden, leeren Autobahn müssen Sie nicht über jeden Zentimeter der Straße nachdenken; Sie gleiten einfach dahin. Aber wenn Sie eine komplexe Kreuzung erreichen, werden Sie langsamer und konzentrieren sich. Delta-Star macht dies automatisch: Es spart Energie bei den langweiligen Teilen und konzentriert sich auf die schwierigen Entscheidungen.

3. Der magische Trick: Zero-Shot Generalisierung

Dies ist das überraschendste Ergebnis. Die KI wurde nur auf kleine 8-strängige Wollknäuel trainiert. Sie hat während des Trainings nie einen größeren Wollknäuel gesehen.

Der Test: Die Forscher überreichten der KI einen riesigen 32-strängigen Wollknäuel (eine Dimension, die sie zuvor noch nie gesehen hatte).
Das Ergebnis: Die KI war nicht verwirrt. Sie konnte den riesigen Wollknäuel sofort besser entwirren, als es der alte LLL-Roboter je könnte.
Die Metapher: Es ist, als würde man einem Kind beibringen, seine Schuhe an einem Paar winziger Babyschuhe zu binden, und ihm dann ein Paar Erwachsenenstiefel geben. Das Kind braucht keine neue Lektion; es wendet einfach dieselbe Logik an und macht dabei einen besseren Job als der Erwachsene, der jahrelang Schuhe gebunden hat.

Warum ist das wichtig?

Die Arbeit behauptet, dass Delta-Star ein „saubereres“ entwirrtes Gitter erzeugt als der klassische LLL-Algorithmus.

Bessere Qualität: Die endgültige Anordnung des Fadens ist kürzer und effizienter.
Weniger Schritte: Es sind weniger „Züge und Tauschaktionen“ nötig, um dorthin zu gelangen.
Kein Nachtrainieren: Es funktioniert bei Größen, die es zuvor noch nie gesehen hat.

Der Haken

Das Papier ist sich über eine Einschränkung sehr bewusst: die Geschwindigkeit.
Obwohl Delta-Star eine bessere Lösung mit weniger mathematischen Schritten findet, ist die KI selbst derzeit langsamer im Betrieb als der alte Roboter. Das liegt daran, dass die KI ein komplexes neuronales Netzwerk (ein riesiges digitales Gehirn) ausführen muss, um jede einzelne Entscheidung zu treffen. Der alte Roboter ist ein einfacher Taschenrechner; die KI ist ein Supercomputer.

Die Autoren sagen nicht, dass diese KI heute bereit ist, den alten Roboter in Ihrem Telefon zu ersetzen. Stattdessen sagen sie: „Wir haben einen besseren Weg gefunden, den Wollknäuel zu entwirren. Jetzt müssen wir herausfinden, wie wir die Regeln, die diese KI entdeckt hat, aufschreiben können, damit wir einen einfachen, schnellen Roboter bauen können, der dasselbe tut.“

Kurz gesagt: Sie haben eine superintelligente KI genutzt, um eine bessere Strategie für ein mathematisches Problem zu entdecken, und diese Strategie funktioniert sogar bei Problemen, für die die KI nie explizit trainiert wurde.

Technisches Resümee: Entdeckung von Strategien zur Gitterreduktion mittels Self-Play

Problemstellung

Die Gitterreduktion (Lattice Reduction) ist ein fundamentales Problem der computergestützten Mathematik und Kryptographie, das die Sicherheit post-quanten-kryptographischer Verfahren untermauert. Der LLL-Algorithmus (Lenstra-Lenstra-Lovász) ist die Standardmethode für die polynomielle Gitterbasisreduktion. Obwohl LLL eine spezifische Laufzeit und Schranken für die Vektorlängen garantiert, sind die Ergebnisse in der Praxis oft suboptimal, insbesondere wenn die Dimension des Gitters zunimmt. Der Algorithmus stützt sich auf eine handgefertigte Heuristik, die Lovász-Bedingung, um zu entscheiden, wann Basiselemente vertauscht werden sollen. Diese Bedingung stellt zwar eine monotone Abnahme einer Potenzialfunktion sicher, ist jedoch nicht notwendigerweise optimal, um die stärkstmögliche Reduktion zu erreichen.

Die zentrale Herausforderung, die in dieser Arbeit adressiert wird, ist die Frage, ob ein datengesteuerter Ansatz eine Sequenzierungsstrategie für die primitiven Operationen von LLL (Größenreduktion und benachbarte Vertauschungen) entdecken kann, die eine streng überlegene Reduktionsqualität gegenüber dem klassischen Algorithmus liefert, ohne den Aktionsraum durch komplexere Orakel (wie exakte Löser für das kürzeste Vektorproblem) zu erweitern.

Methodik: Delta-Star

Die Autoren formulieren die Gitterreduktion als ein Single-Player Markov-Entscheidungsproblem (MDP) und verwenden einen Deep-Reinforcement-Learning-Rahmen (DRL), der durch Monte Carlo Tree Search (MCTS) ergänzt wird.

1. MDP-Formulierung

Zustandsraum: Der Zustand umfasst die aktuelle Basismatrix $B$ , deren Gram-Schmidt-Orthogonalisierung (GSO) Vektoren und Koeffizienten, die Cursor-Position $k$ (die angibt, welche Zeile gerade verarbeitet wird) und die verbleibenden Schritte.
Aktionsraum: Der Agent ist auf die exakten primitiven Aktionen des LLL-Algorithmus beschränkt, um einen fairen Vergleich zu gewährleisten:
- MOVEUP/MOVEDOWN: Anpassung der Cursor-Position.
- SWAP: Vertauschen benachbarter Basiszeilen $b_k$ und $b_{k-1}$ .
- SIZEREDUCE: Subtraktion ganzzahliger Vielfacher vorheriger Zeilen, um die Größenreduktionsbedingung ( $|\mu_{j,k}| \le 1/2$ ) zu erfüllen.
Belohnungsfunktion: Eine normalisierte Belohnung wird basierend auf der relativen Reduktion des Log-Metrik der Qualitätsmaße (Orthogonalitätsdefekt $\delta$ und LLL-Potenzial $\Phi$ ) definiert. Eine hybride Belohnung interpoliert zwischen diesen beiden Zielen.

2. Adaptive-Horizon MCTS

Die Autoren führen einen neuartigen Adaptive-Horizon MCTS-Mechanismus ein, um die Effizienz der Suche zu verbessern:

Mehrstufige Vorhersage: Das neuronale Netz sagt gleichzeitig eine Policy und einen Wert für einen Horizont von $H$ zukünftigen Schritten voraus.
Entropie-gesteuerte Expansion: Anstatt den Baum einen Knoten nach dem anderen zu expandieren, durchläuft der Algorithmus den vom Netzwerk vorhergesagten „gierigen“ Pfad. An jedem Schritt $k$ $k$ berechnet der Algorithmus die Shannon-Entropie $H[p(k)]$ $H [p (k)]$ der vorhergesagten Policy.
- Wenn die Entropie niedrig ist (hohe Konfidenz), durchläuft der Algorithmus den Schritt automatisch ohne Verzweigung, was die Inferenzkosten amortisiert.
- Wenn die Entropie den Schwellenwert $\tau$ überschreitet (was auf einen echten Entscheidungspunkt hindeutet), stoppt die Expansion und der Baum verzweigt sich an diesem Knoten.
Dieser Mechanismus ermöglicht es der Suche, deterministische Sequenzen zu überspringen und die Rechenressourcen auf unsichere Entscheidungspunkte zu konzentrieren.

3. Neuronale Netzarchitektur

Backbone: Ein tiefes Residual Network (ResNet) mit einem Lookback-Fenster, um die zeitliche Historie zu erfassen.
Beobachtungstensor: Kodiert die Basis, GSO, Koeffizienten, die verbleibende Zeit und die Cursor-Position in einen 5-Kanal-Tensor.
Heads: Das Netzwerk gibt einen Policy-Head (Wahrscheinlichkeiten für $H$ Schritte) und einen Value-Head (erwartete Erträge für $H$ Schritte) aus.
Training: Das Modell wird mittels AlphaZero-artigem Self-Play trainiert, wobei die Kreuzentropie zwischen der vorhergesagten Policy und den MCTS-Besuchszahlen sowie der mittlere quadratische Fehler zwischen den vorhergesagten Werten und den Episoderückläufen minimiert wird.

4. Trainings-Setup

Der Agent, genannt Delta-Star, wird ausschließlich auf kleinen $q$ -ären Gittern mit der Basisdimension $n=8$ und dem Modulus $q=251$ trainiert. Das Training nutzt eine verteilte Pipeline mit Self-Play-Workern, Inferenz-Servern und einem zentralen Learner.

Hauptergebnisse

1. Überlegene Reduktionsqualität

Delta-Star erreicht einen signifikant besseren Hermite-Faktor ( $\delta_0$ ) und Orthogonalitätsdefekt als der klassische LLL-Algorithmus über verschiedene Dimensionen hinweg.

Bei der Trainingsdimension ( $n=8$ ) konvergiert Delta-Star zu einem etwas niedrigeren $\delta_0$ ( $\approx 1.00657$ ) im Vergleich zu LLL ($1.00660$).
Entscheidend ist, dass sich die Leistungsdifferenz mit zunehmender Dimension vergrößert. Bei $n=32$ erreicht Delta-Star $\delta_0 = 1.0149$ , was LLL ($1.0171$) übertrifft und sich der Qualität von BKZ- $\beta$ ($1.0125$) annähert, obwohl es nie auf Dimensionen größer als 8 trainiert wurde.

2. Zero-Shot-Generalisierung

Das Modell zeigt eine robuste Zero-Shot-Generalisierung:

Dimension: Es generalisiert auf ungesehene Dimensionen bis zu $n=32$ .
Modulus: Es generalisiert auf ungesehene Moduli $q$ im Bereich von $\sim 20$ bis $5000$.
Dies wird durch die Verwendung von $q$ -normalisierten Beobachtungstensoren und adaptiver Pooling-Verfahren in der Netzwerkarchitektur erreicht.

3. Algorithmische Effizienz

Delta-Star benötigt weniger primitive Zeilenoperationen als LLL, um eine vergleichbare oder bessere Reduktionsqualität zu erreichen.

Bei $n=8$ nutzt es nur 55 % der von LLL erforderlichen Zeilenoperationen.
Bei höheren Dimensionen ( $n=26, 32$ ) behält es über den gesamten Reduktionsprozess hinweg eine streng bessere Trajektorie bei, konvergiert schneller und zu einem besseren Endzustand.
Die Autoren stellen fest, dass die Inferenz des neuronalen Netzes in der Wandzeit (Wall-Clock Time) langsamer ist als eine klassische Implementierung, aber die Reduktion der elementaren Operationen auf eine effizientere zugrunde liegende Strategie hindeutet.

Bedeutung und Ansprüche

Die Arbeit behauptet zu demonstrieren, dass Deep Reinforcement Learning in der Lage ist, strikt überlegene, generalisierbare Reduktionsstrategien zu entdecken, indem es mit dem primitiven Aktionsraum von LLL interagiert.

Jenseits handgefertigter Heuristiken: Die Arbeit zeigt, dass die starre Lovász-Bedingung nicht optimal ist und dass eine gelernte Policy den Zustandsraum effektiver navigieren kann.
Skalierbarkeit: Der Ansatz stellt die Vorstellung infrage, dass Gitterreduktionsstrategien für verschiedene Dimensionen neu entwickelt werden müssen, indem er zeigt, dass ein Modell, das auf kleinen Instanzen trainiert wurde, auf deutlich größere, ungesehene Dimensionen skalieren kann.
Algorithmen-Entdeckung: Die Autoren positionieren diese Arbeit innerhalb des Paradigmas der KI-gestützten Algorithmenentdeckung (ähnlich wie AlphaTensor und AlphaDev) und legen nahe, dass fundamentale, heuristikgesteuerte Algorithmen durch die Entdeckung optimaler Entscheidungspfade mittels RL optimiert werden können.
Zukünftige Richtungen: Die Arbeit schließt damit ab, dass die gelernten Policy-Gewichte einen deterministischen, effizienten Algorithmus kodieren. Ein primäres Ziel für die Zukunft ist es, diesen klassischen Algorithmus aus dem neuronalen Netz zu extrahieren und zu formalisieren. Zudem könnte die Methodik genutzt werden, um blockbasierte Algorithmen wie BKZ zu verbessern.

Die Autoren bleiben bescheiden hinsichtlich der aktuellen Implementierung, räumen ein, dass das neuronale Netz pro Operation langsamer ist als klassischer Code, und betonen, dass der Wert der Arbeit darin liegt, die Struktur einer effizienteren Reduktionsstrategie zu charakterisieren, statt in der unmittelbaren Laufzeitleistung.