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

The key-value (KV) cache dominates the memory cost of long-contextautoregressive inference, and a growing body of work compresses it throughquantization, eviction, or offloading. We study a complementary question:once a position's KV state has been quantized to codebook indices, howshould the resulting symbol stream be stored, and can the storage layer domore than store? A family of contractive iterated-map codes that serializea symbol sequence into a sequence of low-dimensional real vectors isrevisited, and it is shown that they form a natural archive format for aquantized KV cache with the following features. The method provides exactlythe access pattern a growing cache requires. It is lossless, it runs inlinear time, and supports O(1) random access and O(1) amortized append. Acontrolled study of the quantizer feeding this archive is conducted onGPT-2 with 1024-token contexts. Keeping a small exact window (4 attentionsinks + 32 recent tokens) and archiving the rest, per-head residual vectorquantization reduces the archived cache by 36-54x relative to an fp16 cacheat a perplexity cost of 11-15%, and we quantify a sharp key/value asymmetry-- quantizing keys is roughly 4x more damaging than quantizing values,consistent with prior low-bit KV work -- and use it to allocate bits in ahybrid scheme. Finally, we show the archive is simultaneously a searchindex: approximate substring queries execute directly on the storedvectors, and matched context is decoded from the matched vector withoutever materializing the surrounding text. We release all code; every numberreproduces from a single command on a laptop CPU. Code: https://github.com/eighteight/fractal-kv Note: This is a preprint. The same work is being submitted to arXiv (cs.LG);the two records are identical and will be cross-linked once the arXivversion is assigned an identifier.