🤖 machine learning

Fractal KV-Cache Archives: Lossless Symbolic Storage with In-Place Retrieval for Long-Context LLM Inference

Dieses Paper führt „Fractal KV-Cache Archives“ ein, ein verlustfreies Speicherformat in linearer Zeit für quantisierte KV-Caches, das einen O(1)-Random-Access und amortisiertes Anhängen ermöglicht und gleichzeitig als Suchindex für approximative Substring-Abfragen fungiert, wobei es eine bis zu 54-fache Kompression bei minimaler Perplexitätsdegradierung erreicht.

Ursprüngliche Autoren: Vladimir Gusev

Veröffentlicht 2026-07-09

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Vladimir Gusev

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 lesen ein sehr langes Buch, und jedes Mal, wenn Sie eine Seite umblättern, müssen Sie sich an alles erinnern, was Sie bisher gelesen haben, um den nächsten Satz zu verstehen. Für eine Computer-KI (wie die in diesem Paper) wird dieses „Gedächtnis“ als KV-Cache bezeichnet.

Wenn die Geschichte länger wird, wird dieses Gedächtnis riesig. Es ist, als würde man versuchen, eine ganze Bibliothek in seinem Rucksack zu tragen, nur um eine weitere Seite zu lesen. Irgendwann wird der Rucksack so schwer (verbraucht den gesamten Speicher des Computers), dass man nicht mehr weiterlesen kann.

Dieses Paper schlägt eine clevere zweiteilige Lösung vor, um diesen Rucksack leichter und einfacher zu machen.

Teil 1: Die „Fraktale Karte“ (Der Speicher-Trick)

Normalerweise versuchen Computer, Platz zu sparen, indem sie Daten in einen großen, unordentlichen Klumpen komprimieren. Um später einen bestimmten Satz zu finden, müssen sie den gesamten Klumpen wieder entpacken, was langsam ist.

Die Autoren schlagen einen anderen Weg vor: Die Fraktale Karte.

Stellen Sie sich vor, Sie haben eine riesige, magische Karte einer Stadt.

Die Regel: Jedes Mal, wenn Sie ein neues Wort zu Ihrem Gedächtnis hinzufügen, machen Sie einen winzigen Schritt auf dieser Karte.
Die Magie: Die Karte ist so gestaltet, dass Sie, wenn Sie einen Schritt für das Wort „Apfel“ machen, in einem ganz bestimmten kleinen Viertel landen. Wenn Sie dann einen Schritt für „Kuchen“ machen, landen Sie an einem spezifischen Ort innerhalb des „Apfel“-Viertels.
Das Ergebnis: Ihr gesamtes Gedächtnis einer Geschichte ist nicht eine Liste von Wörtern; es ist einfach ein einziger Punkt auf dieser Karte.
- Wenn Sie das letzte Wort wissen wollen, schauen Sie auf den Punkt und sehen, in welchem winzigen Viertel er sich befindet.
- Wenn Sie die letzten zwei Wörter wissen wollen, schauen Sie auf den Punkt, finden das vorletzte Viertel heraus und so weiter.

Warum ist das cool?

Es ist verlustfrei: Sie können die exakten ursprünglichen Wörter perfekt aus diesem einen Punkt rekonstruieren.
Es ist schnell: Sie können sofort zu jedem Punkt der Geschichte springen (Random Access), ohne zuerst die ganze Karte lesen zu müssen.
Es ist durchsuchbar: Da die Karte auf Geometrie basiert, können Sie eine Phrase wie „Die Katze saß“ finden, indem Sie einfach nach Punkten suchen, die in einem bestimmten Muster nah beieinander liegen. Sie müssen nicht den Text lesen, um das Muster zu finden; die Form des Punktes ist das Muster.

Teil 2: Das „Intelligente Schrumpfen“ (Der Komprimierungs-Trick)

Bevor die Daten in einen Punkt auf der Karte verwandelt werden, muss die KI die Daten schrumpfen. Das Paper hat getestet, wie man die „Key“- und „Value“-Teile des KI-Gedächtnisses schrumpft.

Stellen Sie sich das Gedächtnis der KI wie ein Gespräch zwischen zwei Personen vor:

Die Keys (Schlüssel): Dies sind wie „Fragen“ oder „Etiketten“, die entscheiden, worauf man achten soll.
Die Values (Werte): Dies sind wie die „Antworten“ oder der eigentliche Inhalt.

Das Paper entdeckte ein amüsantes Ungleichgewicht:

Keys sind zerbrechlich: Wenn man die „Fragen“ verpatzt (zu stark komprimiert), wird die KI verwirrt darüber, worauf sie achten soll. Es ist, als würde man jemandem eine verschwommene Karte geben; die Person schaut vielleicht auf die falsche Straße.
Values sind robust: Wenn man die „Antworten“ ein wenig verpatzt, kann die KI meistens immer noch den Kern der Sache verstehen. Es ist, als würde man eine etwas gedämpfte Stimme hören; man kann die Bedeutung trotzdem noch erfassen.

Die Lösung: Die Autoren entwickelten einen „Hybrid-Rucksack“. Sie packten die „Fragen“ (Keys) sehr sorgfältig (unter Verwendung von mehr Platz) und die „Antworten“ (Values) lockerer (unter Verwendung von weniger Platz). Das sparte eine enorme Menge an Platz – 36-mal kleiner als das Original – während die KI nur geringfügig weniger genau wurde (etwa 11 % schlechter darin, das nächste Wort vorherzusagen).

Das große Ganze

Dieses Paper kombiniert diese beiden Ideen:

Schrumpfen Sie die Daten mit der Methode des „Intelligenten Schrumpfens“ (indem Fragen und Antworten unterschiedlich behandelt werden).
Speichern Sie die geschrumpften Daten auf der „Fraktalen Karte“.

Die Superkraft:
Da die Daten auf dieser fraktalen Karte gespeichert sind, kann die KI etwas Erstaunliches tun: Sie kann ihre eigene Vergangenheit durchsuchen, ohne die Dateien „entpacken“ zu müssen.

Wenn die KI einen bestimmten Satz finden muss, den sie vor 500 Seiten gelesen hat, muss sie nicht das ganze Buch laden. Sie schaut einfach auf die Karte, findet den passenden Punkt und weiß sofort, wo dieser Satz ist. Es ist, als hätte man eine Bibliothek, in der man ein bestimmtes Buch finden kann, indem man einfach nur auf die Farbe des Staubs im Regal achtet, ohne das Buch jemals aus dem Regal nehmen zu müssen.

Zusammenfassung der Behauptungen

Speicher: Sie haben einen Weg geschaffen, das Gedächtnis einer KI zu speichern, das perfekt genau, sehr schnell abrufbar und leicht erweiterbar ist.
Komprimierung: Sie haben herausgefunden, dass das Komprimieren von „Fragen“ (Keys) viel schwieriger ist als das Komprimieren von „Antworten“ (Values), und sie haben dies genutzt, um 36-mal mehr Platz zu sparen.
Suche: Die Speichermethode selbst fungiert als Suchmaschine, die es der KI ermöglicht, Muster in ihrem vergangenen Gedächtnis sofort zu finden.
Umfang: Sie haben dies an einem spezifischen, kleinen KI-Modell (GPT-2) mit einem Kontext von 1.000 Wörtern getestet. Sie haben es noch nicht an riesigen Modellen oder realen Aufgaben getestet, aber die Mathematik und der Code funktionieren perfekt auf einem Standard-Laptop.

Technisches Resümee: Fraktale KV-Cache-Archive

Problemstellung

Das Servieren von Transformer-Sprachmodellen über lange Kontexte hinweg hat sich von einer berechnungsgebundenen zu einer speichergebundenen Herausforderung entwickelt. Der Key-Value (KV) Cache, der für die autoregressive Attention benötigt wird, wächst linear mit der Kontextlänge und übertrifft oft die Modellgewichte, was die Batch-Größen einschränkt. Während sich bestehende Lösungen auf verlustbehaftete Kompression (Quantisierung, Eviktierung, Offloading) konzentrieren, adressiert dieses Paper eine nachgelagerte, oft implizite Frage: Sobald ein KV-Zustand mittels Vektorquantisierung in einen Symbolstrom reduziert wurde, wie sollte dieser Strom gespeichert werden?

Die Autoren argumentieren, dass die Speicherschicht keine inerte Blob sein sollte, sondern eine aktive Komponente, die in der Lage ist, die spezifischen Zugriffsmuster eines wachsenden Caches zu unterstützen: O(1) amortisiertes Anhängen (wenn neue Token eintreffen) und O(1) Random Access (um vergangene Positionen abzurufen), während sie potenziell zusätzliche Funktionalitäten wie In-Place-Retrieval bietet.

Methodik

1. Das Speicherprimitiv: Kontraktive iterierte Map-Codes

Das Paper schlägt vor, einen verlustfreien kontraktiven iterierten Map-Code (speziell eine Verallgemeinerung der Chaos Game Representation und Universal Sequence Maps) als Serialisierungsschicht für quantisierte KV-Indizes zu verwenden.

Mechanismus: Eine Symbolsequenz über einem Alphabet der Größe $N$ wird auf eine Trajektorie von Punkten in einer 2D-Ebene abgebildet. Ein reguläres $N$ -Eck mit einem Vertex pro Symbol wird fixiert. Jedes Symbol $c_k$ bildet den aktuellen Punkt $p_{k-1}$ auf einen neuen Punkt $p_k$ über die Kontraktion $p_k = V(c_k) + r(p_{k-1} - V(c_k))$ ab, wobei $r$ ein Kontraktionsverhältnis ist.
Eigenschaften:
- Verlustfrei: Die Abbildung ist invertierbar, sofern das Kontraktionsverhältnis $r$ klein genug ist, um disjunkte „Zellen“ für jedes Symbol zu gewährleisten.
- Effizienz: Die Kodierung erfolgt in linearer Zeit. Die Dekodierung ermöglicht den Random Access zu jeder Position, indem lediglich der notwendige Bereich ab dem nächsten gespeicherten Ankerpunkt rekonstruiert wird.
- Selbstähnlichkeit: Die Menge der erreichbaren Punkte bildet einen fraktalen Attraktor (z. B. ein Sierpinski-Dreieck für $N=3$ ).
Implementierung: Um die Verstärkung von Fließkommafehlern während der Invertierung zu mildern, speichert der Codec einen Punkt pro fest definierter Spanne und rekonstruiert Spannen über eine verankerte Rückwärtssuche.

2. Quantisierungsstrategie

Die Autoren führen eine kontrollierte Studie an GPT-2 (124M) mit 1024-Token-Kontexten durch, um das optimale Quantisierungsschema zu bestimmen, das diesen Archiv speist:

Exaktes Fenster: Um die Performance aufrechtzuerhalten, wird ein kleines exaktes Fenster beibehalten (4 „Attention Sink“-Token + 32 aktuelle Token). Der restliche Kontext wird archiviert.
Quantisierungs-Varianten:
- Pooled vs. Per-Head: Vergleich eines einzelnen Codebuchs, das über alle Attention-Heads geteilt wird, gegenüber individuellen Codebüchern pro Head.
- Residual Vector Quantization (RVQ): Speicherung von Vektoren als Summe von $s$ Indizes aus Codebüchern.
- Key/Value-Asymmetrie: Untersuchung der differenziellen Auswirkungen der Quantisierung von Keys (K) gegenüber Values (V).

3. In-Place Retrieval

Das Paper nutzt eine geometrische Eigenschaft des iterierten Map-Codes: Punkte, die einen gemeinsamen Suffix der Länge $s$ teilen, liegen räumlich nah beieinander (Distanz $\approx 2r^s$ ). Dies ermöglicht es, approximative Substring-Abfragen direkt auf den gespeicherten 2D-Vektoren via Nearest-Neighbor-Suche auszuführen, ohne den umgebenden Text dekodieren zu müssen.

Kernergebnisse

1. Codec-Performance

Der fraktale Codec fungt als hochperformantes Speicherprimitiv, das unabhängig vom Modell arbeitet:

Kodierung: 0,68 µs/Zeichen (lineare Zeit).
Random Access: 311 µs/Lookup für ein 1M-Zeichen-Dokument.
Anhängen: 175 µs/Token (amortisiert).

2. Quantisierungsbefunde (GPT-2, 1024 Tokens)

Überlegenheit von Per-Head: Per-Head-Codebücher schneiden bei gleichem Bit-Budget signifikant besser ab als gepoolte Codebücher. Ein Per-Head-RVQ (Tiefe 2) reduziert die Perplexity-Steigerung auf +15,0 % im Vergleich zu +29,2 % bei einem gepoolten RVQ.
Key/Value-Asymmetrie: Die Quantisierung von Keys ist etwa 4-mal schädlicher für die Perplexity als die Quantisierung von Values.
- Nur Values (Keys exakt): +4,0 % Perplexity.
- Nur Keys (Values exakt): +14,5 % Perplexity.
- Dies bestätigt, dass Keys die Attention-Routing bestimmen (hohe Sensitivität), während Values gemittelt werden (Fehlerabschwächung).
Optimales Hybrides Schema: Die Zuweisung von mehr Bits an Keys (4 RVQ-Stufen) und weniger an Values (2 Stufen) liefert das beste Ergebnis:
- Kompression: 36-fache Reduktion relativ zu einem fp16-Cache.
- Perplexity-Kosten: +11,2 % (speziell +16,6 % in der „zweiten Hälfte“ des Kontextes, in der das Archiv dominiert).
- Speicher: 1025 Bytes/Token.

3. Retrieval-Fähigkeiten

Exakter Recall: Schwellenwertbildung der Distanz zwischen gespeicherten Punkten ermöglicht den Abruf aller Positionen mit einem passenden Suffix der Länge $\ell$ mit einem Recall von 1,00.
Präzision: Wird durch die numerische Präzision gesteuert. Double-Precision-Indizes erreichen eine Präzision von 0,89–1,00; Single-Precision dient als grober Filter.
Effizienz: Eine Brute-Force-Nearest-Neighbor-Suche über 100K Positionen im 2D-Raum dauert ~0,9 ms/Query.
Dekodierung: Gematchter Kontext wird rückwärts vom gematchten Vektor her dekodiert, ohne auf externen Text zuzugreifen.

Signifikanz und Ansprüche

Das Paper beansprucht drei primäre Beiträge, die es von gleichzeitiger Arbeiten (z. B. FibQuant, RetroInfer) unterscheidet, welche sich auf die Geometrie der Codebücher oder die Engine für die Vektorspeicherung konzentrieren:

Ein vereinheitlichtes Archivformat: Es rahmt den kontraktiven iterierten Map-Code als ein praktisches KV-Archiv, das gleichzeitig ein verlustfreier Speicher, ein Random-Access-Decoder und ein In-Place-Suchindex ist. Diese Vereinigung von Speicherung und Abruf in einer einzigen Repräsentation wird als der neuartige Beitrag präsentiert.
Quantisierungs-Erkenntnisse: Es quantifiziert die Key/Value-Asymmetrie als spezifisches Perplexity-Budget und demonstriert, dass ein bit-asymmetrisches hybrides Schema (4x mehr Bits für Keys, 2x für Values) der optimale Betriebspunkt für die Langkontext-Kompression ist.
Durchsuchbarer Speicher: Es zeigt, dass das Archiv Suffix-Matching direkt auf der komprimierten Repräsentation unterstützt, was ein Retrieval-Augmented Decoding ermöglicht, bei dem das Modell relevante vergangene Kontexte lokalisieren kann, ohne den vollen Cache materialisieren zu müssen.

Eingeständliche Limitationen der Autoren

Skalierung: Die Experimente sind auf GPT-2 (124M) und einen einzelnen 1024-Token-Kontext beschränkt. Ergebnisse für größere Modelle sind ungetestet (wären aber wahrscheinlich toleranter gegenüber Quantisierung).
Codebuch-Training: Codebücher werden pro Korpus trainiert, nicht über Daten hinweg amortisiert.
Retrieval-Umfang: Das Retrieval ist strikt auf das Sequenzstruktur-Matching (Suffixe) beschränkt, nicht auf semantisches Retrieval über Embeddings.
Kompressionsrate: Die Rohkompressionsrate des fraktalen Codecs ist vergleichbar mit Standard-Byte-Packern; sein Vorteil liegt im Zugriffsmuster (Random Access/Suche) und nicht in der reinen Größenreduktion.
Benchmarking: Das Paper benchmarkt nicht gegen die spezifischen Codebuch-Designs gleichzeitiger Arbeiten, was anerkennt, dass die Kombination ihrer Quantisierer mit diesem Speicherformat zukünftige Arbeit ist.