RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference

Long-context Large Language Model inference is severely bottlenecked by the massive Key-Value (KV) cache, yet existing sparse attention methods often suffer from static fixed-budget (Top-k) retrieval or rely on proxy scores that are computationally expensive and biased. To address these limitations, we propose RaBitQCache, a novel sparse attention framework that utilizes randomized rotated binary quantization and high-throughput binary-INT4 arithmetic to efficiently estimate attention weights. Our proxy score serves as an unbiased estimator with a proven error bound, enabling adaptive Top-p retrieval that dynamically adjusts the token budget based on actual attention sparsity. We further implement a hardware-aware system with asynchronous pipelining and lazy updates to mask overhead. Evaluations demonstrate that RaBitQCache significantly accelerates inference and reduces memory I/O while preserving generation quality compared to state-of-the-art baselines. Code is available at https://github.com/Sakuraaa0/RaBitQCache.git.

Modern language models can read and write with very long inputs, such as full documents or codebases, but they become slow and expensive because they must repeatedly search a large stored memory called the key-value cache. In practice, only a small fraction of that memory is usually important for choosing the next word. RaBitQCache is a system that helps the model quickly decide which past pieces are worth checking. It compresses each stored piece into a tiny binary fingerprint and compares these fingerprints with the current question using very cheap computer operations. This gives a fast estimate of importance without reading the whole memory in detail. Unlike many previous shortcuts that always keep a fixed number of past pieces, RaBitQCache adapts how much it keeps to each situation and comes with a mathematical guarantee that the estimate is reliable. In experiments on long-document understanding, information retrieval, and reasoning tasks, it kept answers nearly as accurate as the standard method while making generation substantially faster. This can make long-context AI assistants faster, cheaper to run, and more practical for real applications.