JoLT: Near-Lossless KV Cache Compression via Joint Tucker and JL-Residual Allocation

During LLM inference, the KV cache memory grows linearly with batch size, context length, and depth, often becoming the throughput bottleneck beyond model weights. Existing compression methods—low-rank approaches (e.g., SVD) decomposing 2D slices of the cache, and quantization lowering the bit-width of each entry—fail to exploit the natural third-order structure of the cache. This paper proposes JoLT (Joint Tucker and JL-Residual), which treats the KV cache at each layer as a third-order tensor (heads × tokens × features). JoLT applies a partial Tucker decomposition on the token and feature axes while keeping head and layer axes intact, then uses Johnson-Lindenstrauss (JL) rotated low-bit residuals to compensate for truncation loss. A Lagrangian dual optimizer jointly allocates Tucker ranks and residual bit-widths per layer group for keys and values under a single byte budget. Experiments on grouped-query attention (Mistral-7B-v0.3) and multi-head attention (LLaMA-2-13B) show that 2-3x compression yields perplexity, GSM8K accuracy, and RULER retrieval recall within statistical noise of the uncompressed baseline. At 2x compression, relative Frobenius errors are 0.009 (K) and 0.006 (V), roughly an order of magnitude lower than cross-layer SVD and 4-bit quantization. Moreover, the randomized SVD variant FlashJoLT speeds up compression by 5-13x at matched quality, greatly enhancing practicality.