提出一种可原位检索的无损符号化存储方案，显著压缩长文本推理的键值缓存。
Fractal KV-Cache Archives: Lossless Symbolic Storage with In-Place Retrieval for Long-Context LLM Inference
- 将量化后的键值序列编码为低维向量流，实现无损存储与快速访问。
- 在GPT-2上压缩率达36-54倍，困惑度仅上升11-15%，且支持常数时间随机访问。
- 存储结构同时充当搜索索引，可直接在向量上执行近似子串查询。
键值（KV）缓存主导了长上下文自回归推理的内存开销。本文研究一个互补问题：当位置的KV状态被量化为码本索引后，如何存储这些符号流？能否让存储层做更多事？我们重新审视一类收缩迭代映射编码方法，发现其能自然构成量化KV缓存的档案格式。该方法具备精确的访问模式、无损性、线性时间复杂度，并支持O(1)随机访问和O(1)均摊追加。在1024词元上下文的GPT-2上，保留小范围精确窗口（4个注意力汇点+32个最近令牌），对每头残差向量量化，使归档缓存相比fp16缓存缩小36-54倍，困惑度仅增加11-15%。我们量化出明显的键/值不对称性——量化键比量化值约差4倍，据此设计混合比特分配策略。进一步表明，该档案同时是搜索索引：可在存储向量上直接执行近似子串查询，匹配上下文可从匹配向量中解码，无需生成全文。我们还刻画了档案的操作范围：截断存储点进入有损阶段，其失真可定位；概率加权映射可恢复算术编码，揭示速率效率、随机访问与内存间的权衡。所有代码均已发布，每个数据可在笔记本CPU上复现。
原文摘要 · Abstract (English)
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 plus 32 recent tokens) and archiving the rest, per-head residual vector quantization reduces the archived cache by 36-54x relative to an fp16 cache at 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 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 further characterize the archive's operating range: truncating stored points yields a lossy regime whose distortion we localize, and probability-weighting the maps recovers arithmetic coding, exposing a trade-off between rate efficiency, random access, and memory. We release all code; every number reproduces on a laptop CPU.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。