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

Jul 16, 2026

Upload by Quinn

The KV cache is the dominant memory cost in long-context autoregressive inference, motivating compression via quantization, eviction, or offloading. This work studies how, after KV states are quantized into codebook indices, the resulting symbol stream should be stored and whether the storage layer can also support retrieval. It reuses contractive iterated-map codes to build a lossless, linear-time archive enabling O(1) random access, O(1) amortized append, and direct substring search on stored vectors without reconstructing surrounding text.

LanguageEnglish

CategoryTechnology

FormatPDF

Pages8

Reading Time20 min

Introduction

The Code (Contractive Iterated-Map / Fractal Archive)

Contributions

arXiv :2607 .07 144v 1 [ cs .LG] 8 Jul 2026 Fractal KV-Cache Archives: Lossless Symbolic Storage with In-Place Retrieval for Long-Context LLM Inference Vladimir Gusev Independent Researcher [vladimir@scriptum.ru](vladimir@scriptum.ru) [ORCID: 0009-0006-4236-9190](ORCID: 0009-0006-4236-9190) July 9, 2026 Abstract The key–value (KV) cache dominates the memory cost of long-context autoregressive inference, and a growing body of work compresses it through quantization, eviction, or offloading. We study a complementary question: once a position’s KV state has been quantized to codebook indices, how should the resulting symbol stream be stored, and can the storage layer do more than store? A family of contractive iterated-map codes that serialize a symbol sequence into a sequence of low-dimensional real vectors is revisited, and it is shown that they form a natural archive format for a quantized KV cache with the following features. The method provides exactly the access pattern a growing cache requires. It is lossless, it runs in linear time, and supports O(1) random access and O(1) amortized append. A controlled study of the quantizer feeding this archive is conducted on GPT-2 with 1024-token contexts. Keeping a small exact window (4 attention sinks + 32 recent tokens) and archiving the rest, per-head residual vector quantization reduces the archived cache by 36–54× relative to an fp16 cache at a perplexity cost of 11–15%, and we quantify a sharp key/value asymmetry—quantizing keys is roughly 4× more damaging than quantizing values, consistent with prior low-bit KV work—and use it to allocate bits in a hybrid scheme. Finally, we show the archive is simultaneously a search index: approximate substring queries execute directly on the stored vectors, and matched context is decoded from the matched vector without ever materializing the surrounding text. We release all code; every number reproduces from a single command on a laptop CPU. 1 Introduction Serving a transformer language model over a long context is increasingly a memory problem rather than a compute problem. To generate each new token the model attends to cached key and value vectors for every previous position in every layer; for GPT-2 this KV cache is 2×12×12×64 = 18,432 scalars per token, and for production-scale models it reaches hundreds of kilobytes per token, so that for long documents the cache dwarfs the model weights and becomes the binding constraint on batch size and context length. The dominant responses are lossy: low-bit quantization of the cached tensors, eviction of “unimportant” positions, and offloading of cold cache to slower memory [1, 2 , 3 , 4] . This paper isolates a question that sits downstream of the lossy step and is usually left implicit. Suppose a position’s KV state has already been reduced to a handful of codebook indices by vector quantization. Those indices are a symbol stream. How should the stream be stored, and–more interestingly–can the storage layer serve retrieval and random access rather than being an inert blob? We show that a lossless contractive iterated-map code answers both. Concretely, we test three claims: (i) the code is a lossless, linear-time store with sub-millisecond random access and append; (ii) with a small exact window, per-head residual VQ archives the remaining cache atmore than 30× compression versus an fp16 cache for a bounded, measured perplexity cost; and (iii) substring queries resolve directly on the stored vectors at full recall. The success criterion for each is stated with its experiment. The code. We use a contractive iterated-map code that reads a symbol sequence over an alphabet of size N and produces a trajectory of points in the plane: a regular N-gon is fixed, one vertex per symbol, and each symbol ck maps the running point by pk = V (ck) + r (pk−1 − V (ck)) for a contraction ratio r. These N contractions form an iterated function system, and the set of points it can reac

FAQs

What problem does the KV-archive method target in long-context LLM inference?

It targets the high memory cost of the KV cache, which grows with context length and can constrain batch size and achievable context length. The approach compresses and organizes the cached KV information while preserving efficient access.

How does the archive support O(1) random access and O(1) amortized append?

The method encodes the quantized symbol stream using a contractive iterated-map code and allows decoding via an anchored backward search over fixed-length spans. This design yields O(1) random access to any past position and O(1) amortized append for growing caches.

How are substring queries handled without materializing surrounding text?

Approximate substring queries are executed directly on the stored vectors in the archive. When a match is found, the matched context is decoded from the matched vector without ever reconstructing the surrounding text.

Jul 16, 2026

Upload by Quinn