- Eine Sammlung von Quantisierungsalgorithmen, die das Memory-Overhead-Problem hochdimensionaler Vektoren grundlegend löst und sich sowohl auf die Kompression des Key-Value-Caches von LLMs als auch auf die Vektorsuche anwenden lässt
- Eine zweistufige Kompressionsarchitektur: Zunächst werden Daten mit PolarQuant hochwertig komprimiert, anschließend entfernt der QJL-Algorithmus den verbleibenden Fehler mit nur 1 Bit
- Der Key-Value-Cache lässt sich bis auf 3 Bit quantisieren, ohne Training oder Fine-Tuning und ohne Genauigkeitsverlust des Modells; auf H100-GPUs wurde eine Leistungssteigerung von bis zu 8x erreicht
- Auch bei der Vektorsuche werden optimale Recall-Raten erzielt, ohne große Codebooks oder datensatzspezifisches Tuning, und damit bestehende State-of-the-Art-Methoden übertroffen
- Als grundlegender algorithmischer Beitrag mit nachweisbarer Effizienz, die nahe an theoretische Untergrenzen heranreicht, dürfte TurboQuant eine Schlüsselrolle für Modelle wie Gemini und großskalige semantische Suchinfrastrukturen spielen
Hintergrund zu Vektoren und Quantisierung
- Vektoren sind die grundlegende Art und Weise, wie AI-Modelle Informationen verstehen und verarbeiten; hochdimensionale Vektoren repräsentieren komplexe Informationen wie Bildmerkmale, Wortbedeutungen oder Eigenschaften von Datensätzen
- Hochdimensionale Vektoren verbrauchen enorme Mengen an Speicher, was zu Engpässen im Key-Value-Cache führt, einer Art schneller digitaler Referenzliste, die häufig genutzte Informationen unter einfachen Labels speichert und sofort abrufbar macht
- Vektorquantisierung ist eine klassische Datenkompressionstechnik zur Reduktion der Größe hochdimensionaler Vektoren und trägt dazu bei, die Vektorsuche zu beschleunigen und Engpässe im Key-Value-Cache zu beseitigen
- Traditionelle Vektorquantisierung bringt jedoch einen eigenen Memory-Overhead mit sich, weil für jeden kleinen Datenblock Quantisierungskonstanten in voller Präzision berechnet und gespeichert werden müssen; dadurch entstehen Zusatzkosten von 1 bis 2 Bit pro Zahl, was den Zweck der Quantisierung teilweise wieder aufhebt
Funktionsweise von TurboQuant
- TurboQuant ist eine Kompressionsmethode, die ohne Genauigkeitsverlust eine starke Reduktion der Modellgröße erreicht und sowohl die Key-Value-Cache-Kompression als auch die Vektorsuche unterstützt
- Sie besteht aus zwei Kernschritten:
1. Schritt: Hochwertige Kompression (PolarQuant-Methode)
- Datenvektoren werden zufällig rotiert, um die geometrische Struktur der Daten zu vereinfachen; anschließend wird auf jeden Teil des Vektors separat ein standardisierter hochwertiger Quantisierer angewendet
- In diesem Schritt werden die meisten Bits genutzt, um die wesentlichen Konzepte und Intensitäten des ursprünglichen Vektors zu erfassen
2. Schritt: Versteckte Fehler entfernen
- Auf den im ersten Schritt verbleibenden feinen Fehler wird der QJL-Algorithmus mit nur 1 Bit zusätzlicher Restkompression angewendet
- QJL fungiert wie ein mathematischer Fehlerprüfer, entfernt Verzerrungen und erzeugt dadurch präzisere Attention-Scores
QJL: Eine 1-Bit-Methode ohne Overhead
- Nutzt die Johnson-Lindenstrauss-Transformation, um hochdimensionale Daten zu reduzieren und dabei zentrale Distanzen und Beziehungen zwischen Datenpunkten zu bewahren
- Jede Zahl im resultierenden Vektor wird auf ein einzelnes Vorzeichen-Bit (+1 oder -1) reduziert, wodurch der Memory-Overhead auf null sinkt
- Zur Wahrung der Genauigkeit kommt ein spezieller Schätzer zum Einsatz, der hochpräzise Queries und vereinfachte Daten mit niedriger Präzision strategisch ausbalanciert
- So können Attention-Scores, mit denen das Modell bestimmt, welche Teile der Eingabe wichtig sind und welche ignoriert werden können, präzise berechnet werden
PolarQuant: Ein neuer "Winkel" auf Kompression
- Ein Ansatz, der das Memory-Overhead-Problem auf völlig andere Weise löst
- Statt Standardkoordinaten (X, Y, Z) werden Vektoren in Polarkoordinaten umgewandelt — ähnlich wie man „3 Blocks nach Osten, 4 Blocks nach Norden“ durch „5 Blocks in Richtung 37 Grad“ ersetzt
- Das Ergebnis der Umwandlung besteht aus zwei Informationsarten: dem Radius, der die Stärke der Kerndaten beschreibt, und dem Winkel, der Richtung und Bedeutung der Daten repräsentiert
- Da die Muster der Winkel bekannt und stark konzentriert sind, kann man Daten auf ein festes „kreisförmiges“ Gitter mit bereits bekannten Grenzen abbilden, statt auf ein „quadratisches“ Gitter mit ständig wechselnden Grenzen, und so den kostspieligen Schritt der Datennormalisierung überspringen
- In einem d-dimensionalen Vektor werden Koordinatenpaare gruppiert und in ein Polarkoordinatensystem überführt; anschließend werden die Radien paarweise gesammelt und die rekursive Polarkoordinatentransformation wiederholt, bis letztlich ein einzelner Radius und ein Satz beschreibender Winkel übrig bleiben
Experimente und Ergebnisse
Leistung in Long-Context-Benchmarks
- Bewertet mit Open-Source-LLMs (Gemma, Mistral) auf standardisierten Long-Context-Benchmarks wie LongBench, Needle In A Haystack, ZeroSCROLLS, RULER und L-Eval
- TurboQuant erreicht sowohl bei dot product distortion als auch bei Recall optimale Werte und minimiert gleichzeitig den Memory-Footprint des Key-Value-Speichers
- Beim Modell Llama-3.1-8B-Instruct zeigt es robuste Leistung gegenüber der KIVI-Baseline über verschiedenste Tasks hinweg, darunter Frage-Antwort, Code-Generierung und Zusammenfassung
Needle-in-Haystack-Task
- In Tests zum Auffinden spezifischer Informationen in großen Textmengen erzielt TurboQuant über alle Benchmarks hinweg perfekte Downstream-Ergebnisse
- Die Größe des Key-Value-Speichers wird um mindestens das 6-Fache reduziert
- Auch PolarQuant arbeitet bei dieser Aufgabe nahezu verlustfrei
Laufzeitleistung
- Der Key-Value-Cache wird auf 3 Bit quantisiert, ohne Training oder Fine-Tuning und ohne Kompromisse bei der Modellgenauigkeit
- Die Laufzeit ist schneller als beim ursprünglichen LLM; die Implementierung ist äußerst effizient und der Laufzeit-Overhead vernachlässigbar
- 4-Bit-TurboQuant erreicht auf H100-GPUs bei der Berechnung von Attention-Logits gegenüber nicht quantisierten 32-Bit-Keys eine Leistungssteigerung von bis zu 8x, gemessen gegenüber einer JAX-optimierten Baseline
Leistung bei der Vektorsuche
- Verglichen mit modernen Methoden wie PQ und RabbiQ für die Suche in hochdimensionalen Vektoren
- Verwendet wird die 1@k-Recall-Rate, die misst, wie häufig der Algorithmus unter den Top-k-Approximationen tatsächlich das beste Ergebnis nach innerem Produkt erfasst
- Gegenüber Baselines, die auf ineffiziente große Codebooks und datensatzspezifisches Tuning setzen, erzielt TurboQuant durchgehend bessere Recall-Raten
- Auf dem GloVe-Datensatz (d=200) werden im Vergleich zu verschiedenen modernen Quantisierungs-Baselines optimale 1@k-Recall-Raten erreicht
- Als datenunabhängiger (data-oblivious) Ansatz liefert TurboQuant nahezu optimale Verzerrungsraten und erhält mit der Effizienz eines 3-Bit-Systems die Präzision deutlich schwererer Modelle
Ausblick
- TurboQuant, QJL und PolarQuant sind nicht nur praktische Engineering-Lösungen, sondern grundlegende algorithmische Beiträge, die durch starke theoretische Beweise untermauert sind
- Sie besitzen nachweisbare Effizienz und arbeiten nahe an theoretischen Untergrenzen, was sie für großskalige Kernsysteme robust und vertrauenswürdig macht
- Über die Beseitigung von Key-Value-Cache-Engpässen in Modellen wie Gemini hinaus reicht der Einfluss effizienter Online-Vektorquantisierung deutlich weiter
- Da sich moderne Suche von keywordzentrierten Verfahren hin zum Verständnis von Absicht und Bedeutung entwickelt, wird Vektorsuche zum Muss, um in Datenbanken mit Milliarden von Vektoren semantisch ähnlichste Einträge zu finden
- TurboQuant ermöglicht den Aufbau und die Abfrage großskaliger Vektorindizes mit minimalem Speicher, nahezu null Vorverarbeitungszeit und aktueller Spitzenpräzision und macht semantische Suche im Google-Maßstab schneller und effizienter
4 Kommentare
„Rotation ist unendliche Kraft. Glaub daran.“
Respekt.
Wegen dieses Kommentars habe ich mich eingeloggt.
Hacker-News-Kommentare
Die Forschung zur KV-Cache-Kompression ist wirklich eine spannende Entwicklung.
Schade ist allerdings, dass in der zugehörigen Forschung ein Verweis auf den zentralen mathematischen Mechanismus fehlt.
Die Technik, nach Anwendung einer geometrischen Rotation zur Behandlung hochdimensionaler Geometrie eine extreme Quantisierung durchzuführen, wurde zuerst in unserem NeurIPS-2021-Paper „DRIVE“ vorgeschlagen.
Mit diesem rotationsbasierten Ansatz und einem Bias-Korrekturmechanismus wurde eine optimale Schätzung des Verteilungsmittels erreicht.
Ich habe das später auch in einem von Google eingeladenen Seminar vorgestellt, und angesichts der theoretischen Ähnlichkeiten zwischen TurboQuant und PolarQuant hoffe ich, dass in künftigen Versionen ein Verweis auf die Vorarbeiten aufgenommen wird.
Anders gefragt: Wird durch das Speichern einer Diagonalmatrix und einer neuen Basis zusätzlich komprimiert?
Könnte jemand erklären, in welchem Verhältnis diese Arbeit zu MHLA steht?
Solche Ideen werden alle paar Jahre wiederentdeckt; zum Beispiel gab es bereits im Paper von 2017 einen ähnlichen Ansatz.
Es ist aber auch möglich, dass die Forschenden die ähnliche Idee unabhängig entwickelt haben, als ihre Arbeit bereits weit fortgeschritten war.
Gute Ideen liegen oft nahe, wenn man ein Problem tief genug versteht.
Ich verstehe die Erklärung „TurboQuant rotiert die Daten zufällig, um die Geometrie zu vereinfachen“ nicht.
Es ist doch nicht garantiert, dass eine Rotation immer eine einfachere Form erzeugt, oder?
Auch der Teil „reduziert hochdimensionale Daten mit einer Johnson–Lindenstrauss-Transformation und stellt jeden Vektor als Vorzeichen-Bits dar“ überzeugt mich nicht; es ist schwer nachzuvollziehen, wie Beziehungsinformationen mit nur einem Boolean-Wert erhalten bleiben sollen.
In einigen Dimensionen treten Outlier-Aktivierungen auf, und durch die Eigenschaften des Adam-Optimierers wird dieses Phänomen noch verstärkt.
Dazu sind SmoothQuant und Privileged Basis lesenswerte Arbeiten.
Das reduziert das Lernen unnötiger Regeln und stabilisiert die Optimierung.
Anders gesagt: Das Modell soll keine trivialen Regeln lernen wie „Wenn die Ziffer an einer bestimmten Stelle einer bestimmten Dimension 5 ist, dann ist es eine Katze“.
Durch Multiplikation mit einer Rotationsmatrix werden die Daten gleichmäßiger verteilt, was eine effizientere Quantisierung ermöglicht.
Anschließend werden mit dem Lloyd–Max-Algorithmus Grenzen und Rekonstruktionswerte optimiert, und der verbleibende Bias wird mit 1 Bit korrigiert.
So lässt sich auch mit wenigen Bits eine hohe Genauigkeit erhalten.
Zum Beispiel lassen sich Gleitkommawerte leichter komprimieren, wenn man sie in eine andere Einheit umrechnet – etwa von Bel in Dezibel –, weil dann ähnlichere Werte entstehen.
Das heißt, weit entfernte Datenpunkte werden wieder näher an das Zentrum gebracht.
Außerdem wird jede Dimension einzeln codiert, daher wird nicht der gesamte Vektor auf einen einzelnen Boolean reduziert.
Dieser Blogpost ist von schlechter Qualität.
Die Achsen in einem Diagramm sind falsch beschriftet, und die Videovisualisierung vermittelt das Konzept der Polar Quantization überhaupt nicht.
Ein weiteres Diagramm beginnt die Achse bei 48 und übertreibt dadurch den tatsächlichen Unterschied.
Insgesamt leiden Verlässlichkeit der Visualisierungen und Kommunikationsqualität.
Jemand implementiert das bereits in llama.cpp.
Siehe den zugehörigen Commit.
Man hofft, dass das Johnson–Lindenstrauss-Theorem weiterhin gilt und die unabhängige Quantisierung jeder Koordinate theoretisch tragfähig bleibt.
Mir fehlt zwar Domänenwissen, aber die Struktur wirkt klar.
Wahrscheinlich wird das in 4 bis 6 Wochen in den Main-Branch gemergt.
Es gibt eine Animation, die TurboQuant anschaulich erklärt.
Hier eine Zusammenfassung auf Bachelor-Niveau.
Der Kern ist die Quantisierung des KV-Caches bei minimalem Informationsverlust.
Da sich die meisten Vektoren nahe dem Äquator einer hochdimensionalen Kugel befinden, macht eine Rotation die Verteilung gleichmäßiger und erhöht so den Erhalt der Entropie.
PolarQuant versuchte das über eine Polarkoordinatentransformation, TurboQuant vereinfacht dies jedoch und ergänzt eine QJL-Bias-Korrektur.
Im Ergebnis erreicht es mit PolarQuant + QJL + praktischen Korrekturen eine hocheffiziente Kompression.
Der Blogpost enthält viele Fehler und ist verwirrend.
Das hyperpolare Koordinaten-Codebook von PolarQuant ist teilweise auch in TurboQuant erhalten geblieben.
Dieser Text gehört zu den schlechtesten Erklärungen von AI-Komponenten, die ich gesehen habe.
Es fehlt fast völlig an technischem Kontext.
Das Johnson–Lindenstrauss-Theorem wird erwähnt, aber die konkrete Verbindung wird nicht erklärt.
Zum Beispiel wird „3 Blocks nach Osten, 4 Blocks nach Norden“ als „5 Blocks in einem Winkel von 37 Grad“ beschrieben – das wirkt wie eine Analogie auf Mittelschulniveau.
Eine unabhängige PyTorch-Implementierung ist bereits veröffentlicht.
turboquant-pytorch
Der Blog wurde zwar erst vor Kurzem veröffentlicht, aber das Paper wurde bereits vor fast einem Jahr bei arXiv eingereicht.
Ich frage mich, ob das bereits in Modellen wie Gemini eingesetzt wurde, und falls ja, ob dadurch auch die RAM-Kosten für den privaten Einsatz sinken könnten.
Es ist erstaunlich, wie schnell Kompressionsforschung derzeit in praktische Anwendungen übergeht.
So wie bei Bildformaten AVIF und JPEG XL Entwicklungen aus der Videocodec-Forschung aufgegriffen wurden, könnten AI-Quantisierungstechniken bald auch in realen Inferenzumgebungen eingesetzt werden.
Einige Konzepte wie der XYB-Farbraum sind gemeinsam, und ich erwarte, dass auch bei LLMs ähnliches maßgeschneidertes Engineering nötig sein wird.