🤖 machine learning

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

This paper introduces "Fractal KV-Cache Archives," a lossless, linear-time storage format for quantized KV caches that enables O(1) random access and amortized appending while simultaneously functioning as a search index for approximate substring queries, achieving up to 54x compression with minimal perplexity degradation.

Original authors: Vladimir Gusev

Published 2026-07-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vladimir Gusev

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are reading a very long book, and every time you turn a page, you need to remember everything you've read so far to understand the next sentence. For a computer AI (like the one in this paper), this "memory" is called the KV Cache.

As the story gets longer, this memory becomes huge. It's like trying to carry a library in your backpack just to read one more page. Eventually, the backpack gets so heavy (using up all the computer's memory) that you can't read anymore.

This paper proposes a clever two-part solution to make that backpack lighter and easier to use.

Part 1: The "Fractal Map" (The Storage Trick)

Usually, when computers try to save space, they compress data into a big, messy blob. To find a specific sentence later, they have to unpack the whole blob, which is slow.

The authors suggest a different way: The Fractal Map.

Imagine you have a giant, magical map of a city.

The Rule: Every time you add a new word to your memory, you take a tiny step on this map.
The Magic: The map is designed so that if you take a step for the word "Apple," you land in a specific tiny neighborhood. If you then take a step for "Pie," you land in a specific spot inside the "Apple" neighborhood.
The Result: Your entire memory of a story isn't a list of words; it's just one single dot on this map.
- If you want to know the last word, you look at the dot and see which tiny neighborhood it's in.
- If you want the last two words, you look at the dot, figure out the second-to-last neighborhood, and so on.

Why is this cool?

It's Lossless: You can reconstruct the exact original words from that single dot, perfectly.
It's Fast: You can jump to any point in the story instantly (Random Access) without reading the whole map first.
It's Searchable: Because the map is built on geometry, if you are looking for a phrase like "The cat sat," you can find it just by looking for dots that are close to each other in a specific pattern. You don't need to read the text to find the pattern; the shape of the dot is the pattern.

Part 2: The "Smart Shrink" (The Compression Trick)

Before turning the memory into a dot on the map, the AI needs to shrink the data. The paper tested how to shrink the "Key" and "Value" parts of the AI's memory.

Think of the AI's memory as a conversation between two people:

The Keys: These are like "questions" or "labels" that decide what to pay attention to.
The Values: These are like the "answers" or the actual content.

The paper discovered a funny imbalance:

Keys are fragile: If you mess up the "questions" (compress them too much), the AI gets confused about what to look at. It's like giving someone a blurry map; they might look at the wrong street.
Values are tough: If you mess up the "answers" a little bit, the AI can usually still understand the gist. It's like hearing a slightly muffled voice; you can still get the meaning.

The Solution: The authors created a "Hybrid Backpack." They packed the "Questions" (Keys) very carefully (using more space) and the "Answers" (Values) more loosely (using less space). This saved a massive amount of space—36 times smaller than the original—while only making the AI slightly less accurate (about 11% worse at guessing the next word).

The Big Picture

The paper combines these two ideas:

Shrink the data using the "Smart Shrink" method (treating questions and answers differently).
Store the shrunken data on the "Fractal Map."

The Superpower:
Because the data is stored on this Fractal Map, the AI can do something amazing: It can search its own past without "unzipping" the files.

If the AI needs to find a specific sentence it read 500 pages ago, it doesn't need to load the whole book. It just looks at the map, finds the matching dot, and instantly knows where that sentence is. It's like having a library where you can find a specific book just by looking at the color of the dust on the shelf, without ever taking the book off the shelf.

Summary of Claims

Storage: They created a way to store AI memory that is perfectly accurate, very fast to access, and easy to add to.
Compression: They found that compressing "questions" (Keys) is much harder than compressing "answers" (Values), and they used this to save 36x space.
Search: The storage method itself acts as a search engine, allowing the AI to find patterns in its past memory instantly.
Scope: They tested this on a specific, small AI model (GPT-2) with a 1,000-word context. They did not test it on huge models or real-world tasks yet, but the math and the code work perfectly on a standard laptop.

Technical Summary: Fractal KV-Cache Archives

Problem Statement

Serving transformer language models over long contexts has shifted from a compute-bound to a memory-bound challenge. The Key-Value (KV) cache, required for autoregressive attention, grows linearly with context length, often dwarfing model weights and constraining batch sizes. While existing solutions focus on lossy compression (quantization, eviction, offloading), this paper addresses a downstream, often implicit question: Once a KV state has been reduced to a symbol stream via vector quantization, how should that stream be stored?

The authors argue that the storage layer should not be an inert blob but an active component capable of supporting the specific access patterns of a growing cache: O(1) amortized append (as new tokens arrive) and O(1) random access (to retrieve past positions), while potentially offering additional functionality like in-place retrieval.

Methodology

1. The Storage Primitive: Contractive Iterated-Map Codes

The paper proposes using a lossless contractive iterated-map code (specifically, a generalization of the Chaos Game Representation and Universal Sequence Maps) as the serialization layer for quantized KV indices.

Mechanism: A symbol sequence over an alphabet of size $N$ is mapped to a trajectory of points in a 2D plane. A regular $N$ -gon is fixed with one vertex per symbol. Each symbol $c_k$ maps the current point $p_{k-1}$ to a new point $p_k$ via the contraction $p_k = V(c_k) + r(p_{k-1} - V(c_k))$ , where $r$ is a contraction ratio.
Properties:
- Lossless: The map is invertible provided the contraction ratio $r$ is small enough to ensure disjoint "cells" for each symbol.
- Efficiency: Encoding is linear time. Decoding allows for random access to any position by reconstructing only the necessary span from the nearest stored anchor point.
- Self-Similarity: The set of reachable points forms a fractal attractor (e.g., a Sierpinski gasket for $N=3$ ).
Implementation: To mitigate floating-point error amplification during inversion, the codec stores one point per fixed-length span and reconstructs spans via anchored backward search.

2. Quantization Strategy

The authors conduct a controlled study on GPT-2 (124M) with 1024-token contexts to determine the optimal quantization scheme feeding this archive:

Exact Window: To maintain performance, a small exact window is kept (4 "attention sink" tokens + 32 recent tokens). The remainder of the context is archived.
Quantization Variants:
- Pooled vs. Per-Head: Comparing a single codebook shared across all attention heads versus individual codebooks per head.
- Residual Vector Quantization (RVQ): Storing vectors as a sum of $s$ indices from codebooks.
- Key/Value Asymmetry: Investigating the differential impact of quantizing Keys (K) versus Values (V).

3. In-Place Retrieval

The paper exploits a geometric property of the iterated-map code: points sharing a common suffix of length $s$ are spatially close (distance $\approx 2r^s$ ). This allows approximate substring queries to be executed directly on the stored 2D vectors via nearest-neighbor search, without decompressing the surrounding text.

Key Results

1. Codec Performance

The fractal codec acts as a high-performance storage primitive independent of the model:

Encoding: 0.68 µs/char (linear time).
Random Access: 311 µs/lookup for a 1M-character document.
Append: 175 µs/token (amortized).

2. Quantization Findings (GPT-2, 1024 tokens)

Per-Head Superiority: Per-head codebooks significantly outperform pooled codebooks at equal bit budgets. A per-head RVQ (depth 2) reduces perplexity increase to +15.0% compared to +29.2% for a pooled RVQ.
Key/Value Asymmetry: Quantizing Keys is roughly 4× more damaging to perplexity than quantizing Values.
- Values only (Keys exact): +4.0% perplexity.
- Keys only (Values exact): +14.5% perplexity.
- This confirms that Keys determine attention routing (high sensitivity), while Values are averaged (error attenuation).
Optimal Hybrid Scheme: Allocating more bits to Keys (4 RVQ stages) and fewer to Values (2 stages) yields the best trade-off:
- Compression: 36× reduction relative to an fp16 cache.
- Perplexity Cost: +11.2% (specifically +16.6% in the "second half" of the context where the archive dominates).
- Storage: 1025 bytes/token.

3. Retrieval Capabilities

Exact Recall: Thresholding the distance between stored points retrieves all positions with a matching suffix of length $\ell$ with 1.00 recall.
Precision: Controlled by numerical precision. Double-precision indices achieve 0.89–1.00 precision; single precision serves as a coarse filter.
Efficiency: Brute-force nearest-neighbor search over 100K positions in 2D space takes ~0.9 ms/query.
Decoding: Matched context is decoded backward from the matched vector without accessing external text.

Significance and Claims

The paper claims three primary contributions, distinguishing itself from concurrent work (e.g., FibQuant, RetroInfer) which focuses on codebook geometry or vector storage engines:

A Unified Archive Format: It frames the contractive iterated-map code as a practical KV archive that is simultaneously a lossless store, a random-access decoder, and an in-place search index. This unification of storage and retrieval in a single representation is presented as the novel contribution.
Quantization Insights: It quantifies the Key/Value asymmetry as a specific perplexity budget, demonstrating that a bit-asymmetric hybrid scheme (4x bits for Keys, 2x for Values) is the optimal operating point for long-context compression.
Searchable Memory: It demonstrates that the archive supports suffix matching directly on the compressed representation, enabling retrieval-augmented decoding where the model can locate relevant past contexts without materializing the full cache.

Limitations Acknowledged by the Authors

Scale: Experiments are limited to GPT-2 (124M) and a single 1024-token context. Results on larger models are untested (though likely more tolerant of quantization).
Codebook Training: Codebooks are trained per corpus, not amortized across data.
Retrieval Scope: The retrieval is strictly sequence-structure matching (suffixes), not semantic retrieval over embeddings.
Compression Ratio: The fractal codec's raw compression ratio is comparable to standard byte-packers; its advantage lies in the access pattern (random access/search) rather than raw size reduction.
Benchmarking: The paper does not benchmark against the specific codebook designs of concurrent works like FibQuant, acknowledging that combining their quantizers with this storage format is future work.