🤖 machine learning

LAPLEX: The FFT of Learnable Laplace Kernels

LAPLEX führt eine Klasse exakter, trainierbarer Laplace-Kernel-Operatoren ein, die eine FFT-ähnliche Skalierung erreichen, um datenadaptive globale Interaktionen und die Modellierung hochdimensionaler Kovarianzen ohne die Speicherkosten dichter Matrizen zu ermöglichen und damit Ausdruckskraft effektiv von Speicheranforderungen zu trennen.

Ursprüngliche Autoren: Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

Veröffentlicht 2026-05-26

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

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 versuchen, eine riesige Bibliothek mit Milliarden von Büchern zu organisieren. In der Welt der modernen künstlichen Intelligenz sind „Bücher" lediglich Zahlen (Datenpunkte), und „Organisieren" bedeutet, komplexe Mathematik anzuwenden, um Muster zu finden.

Normalerweise steht die KI, wenn sie dies in großem Maßstab versucht, vor einer frustrierenden Wahl:

Der starre Bibliothekar (Feste Geometrie): Wie ein Standard-Katalog ist er schnell und exakt, doch die Regale sind fest verankert. Sie können ein Buch nicht an einen besseren Ort verschieben, basierend darauf, wonach Sie suchen. (Dies ist vergleichbar mit der FFT oder Fourier-Transformation).
Der flexible, aber schwere Bibliothekar (Dichte Parameter): Dieser Bibliothekar kann die Regale beliebig umstellen, um die Bücher perfekt unterzubringen, benötigt dafür jedoch ein riesiges Lagerhaus, um die Anweisungen für jedes einzelne Buch zu speichern. Wird die Bibliothek zu groß, reicht der Platz im Lagerhaus nicht mehr aus, und das System stürzt ab. (Dies ist eine Standard-Dichte Matrix).
Der approximative Bibliothekar (Niedriger Rang/Sketching): Dieser Bibliothekar versucht, Platz zu sparen, indem er nur die „allgemeine Stimmung" der Bücher in Erinnerung behält oder ein Zufallsspiel nutzt. Er ist schnell und passt ins Lagerhaus, verliert jedoch die genauen Details und kann die beste Anordnung nicht erlernen.

LAPLEX ist eine neue Art von Bibliothekar, der diesen Zielkonflikt durchbricht. Es behauptet, die „Goldlöckchen"-Lösung zu sein: Es ist exakt, es ist trainierbar (es kann die beste Anordnung erlernen) und es ist leichtgewichtig (es benötigt kein riesiges Lagerhaus).

Hier ist die Funktionsweise, erläutert mit einfachen Analogien:

1. Das Geheimnis: Lernen der „Koordinaten" statt der „Karte"

Stellen Sie sich vor, Sie haben eine riesige Stadtkarte mit Millionen von Straßen.

Der alte Weg: Um die Entfernung zwischen jedem Straßenpaar zu kennen, müssten Sie für jedes einzelne Paar eine Zahl aufschreiben. Für eine Stadt mit 1 Million Straßen wären das eine Billion Zahlen. Das kann man nicht speichern.
Der LAPLEX-Weg: Anstatt jede Entfernung aufzuschreiben, notiert LAPLEX lediglich eine Liste von „Ankerpunkten" (wie wichtigen Wahrzeichen). Anschließend verwendet es eine clevere mathematische Regel (den Laplace-Kernel), um die Entfernung zwischen jedem zwei Punkten basierend darauf zu berechnen, wie nah sie an diesen Wahrzeichen liegen.

Da die Regel so einfach ist, muss LAPLEX nicht die Billion Zahlen speichern. Es benötigt nur die Liste der Wahrzeichen. Doch hier liegt der Zauber: Es kann lernen, wo es diese Wahrzeichen platzieren soll. Wenn die Daten nahelegen, dass „Straße A" und „Straße B" oft zusammenhängen, lernt LAPLEX, seine Wahrzeichen so zu verschieben, dass A und B in seiner internen Logik nah beieinander liegen.

2. Der „Scan"-Trick: Mathematik ohne schwere Arbeit

Die Arbeit behauptet, dass LAPLEX, obwohl es wie eine riesige, dichte Karte wirkt, die Mathematik unglaublich schnell durchführen kann.

Stellen Sie sich dies wie ein Fließband in einer Fabrik vor.

Der dichte Weg: Um das Ergebnis für ein einzelnes Item zu berechnen, müssen Sie anhalten, jedes andere Item im Lagerhaus ansehen und eine Berechnung durchführen. Dies wird mit wachsender Größe des Lagerhauses immer langsamer.
Der LAPLEX-Weg: Es sortiert die Items auf dem Fließband zunächst. Dann verwendet es eine „Scan"-Technik. Stellen Sie sich einen Arbeiter vor, der die Reihe entlanggeht und nur die laufende Summe dessen, was er bisher gesehen hat, im Gedächtnis behalten muss. Da die Mathematik des Laplace-Kernels exponentiell ist (Dinge werden sehr schnell kleiner, je weiter man sich entfernt), kann der Arbeiter das Endergebnis für die gesamte Reihe berechnen, indem er nur den „Präfix" (das, was davor kam) und den „Suffix" (das, was danach kommt) betrachtet.

Dies ermöglicht LAPLEX, Dimensionen von bis zu 1 Milliarde (10⁹) auf modernen Computern zu verarbeiten, eine Größe, bei der die „dichte" Methode sofort den Speicher aufbrauchen würde.

3. Was es tatsächlich leistet (Die Experimente)

Die Arbeit testet diesen „Bibliothekar" in drei spezifischen Szenarien, um zu beweisen, dass er funktioniert:

Der „Flachgelegte-Bild"-Test: Sie nahmen hochauflösende Fotos (Millionen von Pixeln), legten sie in eine einzelne lange Zahlenreihe (unter Ignorierung des 2D-Rasters) und versuchten, die Daten zu modellieren.
- Ergebnis: Ein Standard-„Niedrig-Rang"-Modell (der approximative Bibliothekar) versagte darin zu erkennen, dass Pixel, die im Originalfoto nebeneinander liegen, zusammenhängen sollten; es sah lediglich Rauschen. LAPLEX hingegen lernte, seine „Wahrzeichen" so zu platzieren, dass die Formen der Bilder (wie ein Strand oder eine Palme) erhalten blieben, obwohl es das Bild niemals als Raster sah. Es lernte die Geometrie der Daten, ohne ihm mitgeteilt worden zu sein, was ein Raster ist.
Der „Klassifizierungs-Kopf"-Test: Sie versuchten, die letzte Schicht eines neuronalen Netzwerks (der Teil, der entscheidet: „Ist das eine Katze oder ein Hund?") durch LAPLEX zu ersetzen.
- Ergebnis: Mit nur einem winzigen Bruchteil der Parameter (wie 1–5 % der üblichen Größe) schnitt LAPLEX fast genauso gut ab wie das massive, vollwertige Netzwerk. Es lernte, Informationen viel besser zu leiten als Standard-„Niedrig-Rang"-Abkürzungen.
Der „Geschwindigkeits"-Test: Sie verglichen, wie schnell es auf einem Supercomputer (GPU) läuft.
- Ergebnis: LAPLEX ist etwa 65-mal schneller als die Standardmethode für Vorwärtsdurchläufe und 430-mal schneller beim Training (Vorwärts- + Rückwärtsdurchlauf) auf großen Datensätzen. Es verbraucht zudem 100-mal weniger Speicher.

4. Warum dies wichtig ist (In einfachen Worten)

Die Arbeit argumentiert, dass wir lange Zeit glaubten, wir müssten zwischen Geschwindigkeit/Größe und Genauigkeit/Flexibilität wählen.

Wollten Sie Geschwindigkeit, mussten Sie feste Regeln (wie FFT) oder Zufallsraten verwenden.
Wollten Sie die besten Regeln lernen, mussten Sie so viel Speicher verbrauchen, dass Sie es nicht auf großen Daten betreiben konnten.

LAPLEX sagt: „Sie müssen nicht wählen." Indem es die Koordinaten der Daten als lernbare Variablen behandelt und nicht als feste Plätze, schafft es ein System, das:

Exakt ist: Es rät nicht; es berechnet die wahre Mathematik.
Trainierbar ist: Es passt sich den spezifischen Daten an, die es sieht.
Effizient ist: Es passt auf Hardware, die sonst abstürzen würde.

Zusammenfassende Analogie

Stellen Sie sich vor, Sie versuchen, eine riesige Party zu organisieren, bei der Millionen von Gästen ihre Plätze finden müssen.

Dichte Matrix: Sie drucken einen riesigen Sitzplan aus, auf dem jeder Gast neben jedem anderen Gast steht. Es ist perfekt, aber der Papierstapel ist zu schwer, um ihn zu tragen.
Niedriger Rang/Sketching: Sie sagen den Gästen einfach, sie sollen zufällig in „Zone A" oder „Zone B" sitzen. Es ist leicht, aber die Sitzordnung ist chaotisch und ineffizient.
LAPLEX: Sie geben den Gästen ein paar „magnetische Anker" (wie VIP-Tische). Sie lehren die Gäste, sich basierend darauf zu setzen, wie nah sie an diesen Ankern sind. Die Anker bewegen sich während der Party, um die besten Plätze zu finden. Sie benötigen keinen riesigen Plan; Sie brauchen nur die Liste der Anker. Die Gäste finden ihre Plätze sofort, die Anordnung ist perfekt, und Sie können den gesamten Plan in der Tasche tragen.

Die Arbeit kommt zu dem Schluss, dass dieser Ansatz es der KI ermöglicht, „dichte" Interaktionen (wo alles mit allem spricht) in einem Maßstab zu handhaben, der zuvor unmöglich war, ohne die Fähigkeit zu opfern, aus den Daten zu lernen.

Technische Zusammenfassung: LAPLEX – Die FFT lernbarer Laplace-Kerne

1. Problemstellung

Moderne maschinelle Lernsysteme operieren zunehmend in Regimen, in denen die ambienten Dimensionen Millionen oder Milliarden erreichen. In diesen hochdimensionalen Settings ist der Engpass oft die Wanduhrzeit und der Speicherverbrauch linearer Operationen, wie das Anwenden dichter Matrizen, das Berechnen von Gram-Operatoren und das Mischen von Merkmalen.

Bestehende Ansätze zur Skalierung der linearen Algebra opfern typischerweise eine von drei wünschenswerten Eigenschaften: Exaktheit, Lernbarkeit oder nahezu-lineare Skalierung.

Niedrigrangige Methoden (z. B. LoRA) behalten dichte, basisabhängige Interaktionen bei, leiden jedoch unter einem Speicherverbrauch von $O(nk)$, da sie Koeffizienten für die Eingabebasis speichern müssen, selbst wenn der Ausgabesrang komprimiert ist.
Randomisierte Skizzen und Zufallsmerkmale (z. B. CountSketch, Random Fourier Features) bieten Skalierbarkeit, wirken jedoch auf feste Indizierung oder approximieren den Kernel und tauschen Exaktheit gegen Effizienz ein. Sie können nicht anpassen, wie Koordinaten gematcht werden.
Sparse-Methoden können die Hardware-Regelmäßigkeit brechen und sind schwierig end-to-end zu trainieren.
Klassische schnelle Transformationen (z. B. FFT) sind exakt und günstig ( $O(n \log n)$ ), sind jedoch an eine spezifische Gittergeometrie gebunden und können das Koordinatensystem nicht lernen.

Die identifizierte Kernbeschränkung ist die Basisabhängigkeit: Standardoperatoren parametrisieren die Matrixwerte direkt und erfordern einen Speicherbedarf proportional zur Eingabedimension. Die Arbeit plädiert für einen Wechsel zu Index-Level-Operatoren, die die Eingabegeometrie selbst lernen können, ohne eine dichte Matrix zu speichern.

2. Methodik: LAPLEX

Die Autoren stellen LAPLEX vor, eine Klasse exakter, trainierbarer Operatoren basierend auf dem Laplace-Kernel. Eine LAPLEX-Schicht ist implizit durch lernbare Koordinatenanker definiert, nicht durch explizite Matrixgewichte.

2.1 Der Operator

Das grundlegende Element ist die Laplace-Kernel-Matrix, definiert durch zwei Mengen lernbarer Anker, $a \in \mathbb{R}^n$ und $b \in \mathbb{R}^k$ :
$\text{LAPLEX}(a, b)_{ij} = \exp(-|a_i - b_j|)$
In einem natürlichen Grenzregime (Temperatur $t \to 0$ ) kodiert dieser Operator alle Permutationen der Koordinatenmenge. Durch Hinzufügen von Phasenparametern $\phi, \psi$ kann der Operator erweitert werden zu:
$\text{LAPLEX}(a, \phi; b, \psi)_{jk} = \exp(-|a_j - b_k|) \cdot \cos(\phi_j - \psi_k)$
Dies ermöglicht es dem Operator, als dichte, trainierbare Matrix zu fungieren, während er nur $O(n)$ Parameter (die Anker) verwendet.

2.2 Exakte Scan-Algebra

Der wesentliche algorithmische Beitrag ist ein exakter, vollständig paralleler $O(n \log n)$ -Algorithmus für Matrix-Vektor- und Gram-Produkte, der die dichte Matrix niemals materialisiert.

Symmetrischer Fall ( $a=b$ ): Nach dem Sortieren der Anker zerfällt die Kernel-Matrix in untere und obere Dreiecksteile. Jeder Teil kann über eine Prefix-Scan- und Suffix-Scan-Rekursion berechnet werden. Beispielsweise erfüllt das untere Dreiecksprodukt $y_i = \sum_{j \le i} \exp(a_j - a_i)x_j$ eine Rekursion $y_{i+1} = x_{i+1} + \exp(a_i - a_{i+1})y_i$ , die mit $O(n)$ Arbeit und $O(\log n)$ paralleler Tiefe ausgewertet wird.
Allgemeiner Fall ( $a \neq b$ ): Der Algorithmus aggregiert Beiträge von $b$ -Ankern in Intervalle, die durch sortierte $a$ -Anker definiert sind. Lokale Beiträge werden zu Vektoren $u$ und $v$ zusammengefasst, die dann unter Verwendung des symmetrischen Scan-Primitivs global propagiert werden.
Gram-Operatoren: Die gleiche Ordnungsstruktur ermöglicht die exakte Berechnung gewichteter Gram-Matrizen $M = A \text{diag}(D) A^\top$ in $O(n^2 + k \log n)$ Zeit und vermeidet die naive $O(n^2 k)$ -Kosten. Dies ist entscheidend für Optimierung zweiter Ordnung und Kernel-Methoden.

2.3 Ausdruckskraft und Grenzen

Die Arbeit zeigt, dass LAPLEX eine kontinuierliche Familie ist, die zwischen verschiedenen Operatorklassen interpoliert:

Grenzfall Nulltemperatur: Wenn sich der Temperaturparameter Null nähert, konvergiert der glatte Kernel zu einer diskreten Gleichheits-Routing-Matrix und stellt CountSketch und beliebige Permutationen wieder her.
Universalität: Mit diagonalen Skalierungen und sparsamer Replikation ist die Familie universell für beliebige rechteckige dichte Matrizen.
Beziehung zur FFT: Wenn Anker auf ein gleichmäßiges Gitter eingefroren werden, wird LAPLEX zu einer Toeplitz-Matrix, und der Algorithmus reduziert sich auf Toeplitz-FFT. Wenn der Kernel durch eine endliche spektrale Expansion ersetzt wird, wird er zu Random Fourier Features (RFF). LAPLEX behält Exaktheit und Differenzierbarkeit bezüglich der Anker bei, im Gegensatz zu RFF, das aufgrund der schwerfälligen Cauchy-spektralen Dichte des Laplace-Kernels unter unbeschränkter Gradientenvarianz leidet.

3. Hauptbeiträge

Identifikation der Basisabhängigkeit: Die Arbeit motiviert Index-Level-, Permutations-bewusste Operatoren als prinzipielle Alternative zu niedrigrangigen Methoden, die den Speicherverbrauch von $O(nk)$ nicht umgehen können, da sie die Eingabebasis nicht komprimieren.
Lernbare Geometrie: Sie zeigt, dass die Laplace-Kernel-Matrix in einem natürlichen Grenzregime alle Koordinatenpermutationen kodiert, während sie nur $O(n)$ Parameter verwendet.
Exakte, skalierbare Algorithmen: Die Autoren stellen einen exakten, vollständig parallelen $O(n \log n)$ -Algorithmus für Matrix-Vektor- und Gram-Produkte unter Verwendung von $O(n)$ Speicher bereit. Dies ermöglicht Dimensionen bis zu $10^9$ auf modernen GPUs ohne Materialisierung der Matrix.
Empirische Validierung: Die Arbeit zeigt, dass LAPLEX die Skalierung der FFT-Klasse erreicht, während es effizient als einsetzbare strukturierte Schicht fungiert. Es übertrifft dichte Baselines in Speicher und Geschwindigkeit und übersteigt niedrigrangige und Zufallsmerkmal-Baselines in Genauigkeit und Gradientenstabilität.

4. Experimentelle Ergebnisse

4.1 Skalierung und Leistung

GPU-Skalierung: Auf NVIDIA H100 und RTX 2080 skaliert LAPLEX nahtlos bis $n = 2^{20}$ (ca. 1 Million Elemente), während dichte Baselines bei $n = 2^{14}$ den Speicher erschöpfen (OOM).
Geschwindigkeit: Bei der größten Größe, bei der beide Methoden laufen ( $n=2^{14}$ ), ist LAPLEX im Vorwärtsdurchlauf $\sim 65\times$ schneller und im Vorwärts- plus Rückwärtsdurchlauf $\sim 430\times$ schneller als dichte Matmul.
Speicher: LAPLEX verwendet $\sim 100\times$ weniger Spitzen-Speicher als die dichte Baseline.
Numerische Genauigkeit: Trotz Ausführung in Float32 zeigt LAPLEX einen geringeren relativen Fehler gegenüber einer Float64-Referenz als sowohl dichte Float32-Matmul als auch Toeplitz-FFT. Dies wird der Fähigkeit des Scan-Algorithmus zugeschrieben, exponentielle Skalierungsfaktoren getrennt von Mantissen zu halten und so die $O(n \epsilon)$ -Fehlerakkumulation dichter Summation zu vermeiden.

4.2 Hochdimensionale Dichtemodellierung

Die Autoren trainierten ein Gaußsches Dichtemodell auf flachgelegten DIV2K-Bildern (Dimension $3 \cdot 10^6$ ) unter Verwendung eines exakten Gram-Operators.

Setup: Vergleich eines LAPLEX-Faktors (Rang 1000, $\sim 14$ M Parameter) mit einer dichten niedrigrangigen Baseline (Rang 4, $\sim 15$ M Parameter).
Ergebnis: Die dichte Baseline kollabierte zu uniformem Rauschen aufgrund unzureichenden Ranges. Das LAPLEX-Modell lernte kohärente räumliche Farbstrukturen (zusammenhängende Regionen, Silhouetten), obwohl es auf flachgelegten Vektoren ohne konvolutionale Verzerrung operierte. Die Test-Log-Likelihood war $4,5\times$ höher als bei der dichten Baseline.

4.3 Strukturierte Projektionen und Klassifikation

ImageNet10-Projektionen: In einem eingefrorenen Projektionssetting (flachgelegte 150.528-dimensionale Bilder auf $m \in \{25, \dots, 1000\}$ ) war LAPLEX stabiler als CountSketch und Random Projections und wurde bei größerem $m$ zum besten Performer.
Trainierbare Köpfe: Wenn als Klassifikationskopf für Swin-T und MaxViT-T verwendet, erreichte oder übertraf LAPLEX die Genauigkeit unbeschränkter dichter Projektionen bei gleicher Ausgabedimension, unter Verwendung von $\Theta(m+d)$ Parametern statt $\Theta(md)$ . Bei niedrigen Rängen übertraf LAPLEX die niedrigrangige Faktorisierung (LoRA-artig) signifikant.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, dass LAPLEX Ausdruckskraft von Speicherkosten trennt. Es verhält sich wie eine dichte trainierbare Matrix, wird aber durch eine kleine strukturierte Menge von Parametern (Anker) repräsentiert und angewendet.

Trennung von Ausdruckskraft und Speicherung: Dichte Geometrie kann gelernt werden, ohne eine dichte Matrix zu speichern. Dies ermöglicht datenadaptive globale Interaktionen in Regimen, in denen gewöhnliche dichte Schichten nicht machbar sind.
Exaktheit vs. Approximation: Im Gegensatz zu Random Fourier Features oder Nyström-Methoden bietet LAPLEX eine exakte Kernel-Anwendung und Gram-Berechnung. Es vermeidet die Wert-/Gradienten-Trade-offs von Zufallsmerkmalen, insbesondere die unbeschränkte Varianz in Ankergradienten, die durch die Cauchy-spektrale Dichte verursacht wird.
Lernbare schnelle Transformationen: Die Arbeit zeigt, dass schnelle Transformationen nicht auf festen Koordinatensystemen leben müssen. Durch Parametrisierung eines dichten Operators durch lernbare Laplace-Anker wird die Geometrie selbst zu einem differenzierbaren Parameter.

6. Einschränkungen

Die Autoren erkennen folgende Einschränkungen an:

Dimensionalität: Der aktuelle Aufbau verwendet eindimensionale Laplace-Anker und sortierungsbasierte Algorithmen. Die Erweiterung dieser Exaktheit auf höherdimensionale Ankergeometrien und reichhaltigere Kernel ist eine offene mathematische Richtung.
Systemreife: Die Implementierung demonstriert das algorithmische Regime, aber großskalige Attention-Blöcke, Optimierer und generative Modelle werden spezialisierte Kernel und sorgfältiges Architekturentwurf erfordern.
Umfang: Die Methode ist derzeit auf den Laplace-Kernel und seine spezifische scan-basierte Zerlegung beschränkt.

Zusammenfassend bietet LAPLEX eine prinzipielle Alternative zu niedrigrangigen und randomisierten Methoden und ermöglicht exakte, lernbare und skalierbare lineare Algebra in hochdimensionalen Regimen, indem von der Parametrisierung von Matrizen zur Parametrisierung von Index-Interaktionen gewechselt wird.