QJL is 1-bit Compressive Sensing: An Equivalence and Its Consequences for KV Cache Compression in LLMs

We establish a formal equivalence between the Quantized Johnson–Lindenstrauss (QJL) trans- form, introduced in the TurboQuant KV cache compression scheme, and the classical 1-bit com- pressive sensing (1-bit CS) measurement model of Boufounos and Baraniuk (2008). The equiv- alence lets us import two decades of 1-bit CS theory into the QJL analysis pipeline. We give the first reconstruction guarantees for QJL side- channel estimates in terms of measurement count m, ambient dimension d, and the Gaussian mean width of the key geometry, transferred from Plan– Vershynin (2013) and Jacques–Laska–Boufounos– Baraniuk (2013), together with a matching m≍ log(n)/γ2 n lower bound via Le Cam / Fano (under the isotropic-keys distributional model). We fur- ther analyze TurboQuant as a two-stage measure- ment operator—rotated scalar quantization com- posed with QJL—and prove a composition error identity characterizing how optimal bit budgets are allocated between the two stages. Building on the composition analysis, we evaluate multi-bit extensions of QJL for residual coding and prove a rate–distortion lower bound identifying the ef- fective rank of the residual covariance as the gov- erning diagnostic. Empirically, on the orthogonal- complement residual of real Llama 3.2 3B post- RoPE keys after removing the top-r0 Karhunen– Lo` eve directions, transform coding at 4 bits per re- tained component reduces residual-reconstruction normalized MSE by 53–74% vs scalar quantiza- tion at matched bit budget—a direct validation of the rate–distortion prediction of Theorem 13 at the reconstruction-error level. Across six LLMs, a QJL-style 1-bit residual correction stacked on a learned low-rank projection adds ≤0.4 perplex- ity points, confirming the composition bound’s saturation prediction end-to-end.