QUARTZ: Dequantization-Free LLM Attention via Lookup Tables

High-throughput serving of large language models (LLMs) is fundamentally memory bound. While existing KV-cache compression techniques reduce storage footprints, most still require compressed keys to be dequantized to full precision before attention is computed. This dequantization keeps the read-path cost at $O(L \cdot d)$ per head ($L$: context length, $d$: head dimension), limiting batch sizes and throughput regardless of the compression ratio achieved. We introduce QUARTZ, a data-oblivious, dequantization-free attention pipeline that removes this bottleneck. QUARTZ exploits the concentration of randomly rotated key coordinates into a predictable Beta distribution to derive a compile-time analytical product quantization (PQ) codebook, eliminating both the calibration data that learned codebooks require (and that edge and privacy-constrained deployments cannot provide) and vector reconstruction on the read path: attention scores are computed directly via integer table lookups. Wrapped in a two-phase serving architecture, this bounds the per-step read-path cost to a constant under a fixed cache budget, independent of context length. Evaluation on Qwen2.5-3B and TinyLlama-1.1B shows 100% passkey retrieval on both models and, on Qwen2.5-3B, an aggregate score on par with FP16 on a RULER-style long-context suite of three task families (0.88 vs. 0.86, a gap within run-to-run noise at ten samples per task), while reducing read-path memory bandwidth by $7.4\times$ relative to an FP16 cache at the headline configuration, with near-lossless perplexity.