# Orthogonally mixed 3-bit KV cache

- ID: 1973
- Canonical URL: https://synthcore.org/idea/1973/orthogonally-mixed-3-bit-kv-cache
- API JSON: https://synthcore.org/api/idea/1973.json
- API Markdown: https://synthcore.org/api/idea/1973.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.08081](https://arxiv.org/abs/2608.08081)
- Category: memory
- Solves: memory, inference-speedup, accuracy
- ML areas: attention, kv-cache, quantization, inference-speedup
- Math tags: linear-algebra, harmonic-analysis, geometry, optimization
- Ratings: usefulness 7/10; difficulty 6/10; novelty 6/10

## Idea description

Replace ordinary per-channel or per-token KV quantization with a structured orthogonal transform followed by blockwise 3-bit quantization. Use a normalized Walsh-Hadamard transform and small SO(4) rotations to spread outliers across coordinates, quantize the transformed vectors, and exploit orthogonality to rotate queries and attention outputs so unquantized attention remains mathematically equivalent.

## Mathematical statement

The paper composes compression as $M_{\mathrm{total}}=O_E\circ C_{KV}\circ Q_W$, where $Q_W$ is weight quantization, $C_{KV}$ is KV-cache compression, and $O_E$ is expert offloading; this identifies $C_{KV}$ as an independent module applicable to ordinary dense attention. Let $d$ be the head dimension, assumed divisible by $4$. Let $H_d$ be the normalized Walsh-Hadamard matrix satisfying $H_d^\top H_d=I_d$. Let $R_i\in SO(4)$ be four-dimensional rotations satisfying $R_i^\top R_i=I_4$ and $\det(R_i)=1$, and define $B=\operatorname{diag}(R_1,\ldots,R_{d/4})$ and $U=BH_d$. Then $U^\top U=I_d$. For query and key vectors $q,k\in\mathbb{R}^d$, orthogonality gives $(Uq)^\top(Uk)=q^\top k$, so both can be transformed without changing unquantized attention logits. For values $v$, transformed values $v'=Uv$ can be converted back after attention using $U^\top$. The scalar quantizer for a block $x\in\mathbb{R}^m$ uses scale $s=(\max_j|x_j|+\epsilon)/(2^{b-1}-1)$ and reconstruction $\hat{x}=s\operatorname{clip}(\operatorname{round}(x/s),-2^{b-1}+1,2^{b-1}-1)$, with $b=3$. The transform is valuable when it reduces block maxima or tail magnitudes, thereby reducing quantization error at fixed bit width.

## Key formulas

- $$M_{\mathrm{total}}=O_E\circ C_{KV}\circ Q_W$$
- $$H_d^\top H_d=I_d,\qquad B=\operatorname{diag}(R_1,\ldots,R_{d/4}),\qquad R_i^\top R_i=I_4,\ \det(R_i)=1,\qquad U=BH_d$$
- $$q^\top k=(Uq)^\top(Uk),\qquad \operatorname{Attn}(Q,K,V)=\operatorname{softmax}\!\left(\frac{QK^\top}{\sqrt d}\right)V$$
- $$s=\frac{\max_j|x_j|+\epsilon}{2^{b-1}-1},\qquad \hat{x}=s\,\operatorname{clip}\!\left(\operatorname{round}(x/s),-2^{b-1}+1,2^{b-1}-1\right),\quad b=3$$

## Implementation notes

Integrate this at the decoder self-attention KV-cache write and read paths. For each attention head with dimension d divisible by four, implement a normalized fast Walsh-Hadamard transform using the recursive butterfly algorithm, then apply a block-diagonal collection of SO(4) matrices. Start with fixed random rotations, and calibrate them on a few thousand representative sequences by minimizing reconstruction MSE after 3-bit quantization; parameterize each SO(4) block with a normalized quaternion or use fixed rotations for the first MVP. On every new token, compute `k1 = U(k)` and `v1 = U(v)`, partition them into quantization blocks, calculate one scale per block, round to signed 3-bit integers, and pack the codes into bytes. Store only packed codes and scales. At read time compute `q1 = U(q)`, unpack and scale keys inside the attention dot-product kernel, calculate logits from `q1` and reconstructed transformed keys, apply softmax, multiply by reconstructed transformed values, and rotate the output back with `U.T`. Pseudocode: `U=block_SO4(FWHT); k1=U(k); v1=U(v); sk=maxabs(k1,blocks)/(2**2-1); sv=maxabs(v1,blocks)/(2**2-1); Kcache.append(pack3(round(k1/sk)),sk); Vcache.append(pack3(round(v1/sv)),sv); q1=U(q); logits=q1@dequant_fused(Kcache); y1=softmax(logits)@dequant_fused(Vcache); y=U.T@y1`. Fuse unpacking, scale multiplication, and dot-product accumulation so full FP16 K/V tensors are never materialized. Orthogonality and the dot-product identity are exact mathematical properties; rotation selection, block size, and scales are estimated empirically. First test a 1B-3B decoder on WikiText-2 or C4 at 4K and 32K context against FP16 KV, standard per-token 3-bit KV, Hadamard-only 3-bit KV, and Hadamard-plus-SO(4) 3-bit KV. Success means at least 4x KV-memory reduction, perplexity degradation below 0.1, and reduced attention memory bandwidth; a stronger result is near-baseline perplexity with improved decode tokens per second.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built a NumPy MVP implementing normalized FWHT, block-diagonal SO(4) mixing, blockwise signed 3-bit quantization, dequantized attention, and 3-bit packing. The math checks passed: SO(4) Gram error was 8.9e-16, transformed dot-product error 7.1e-15, inverse error 1.6e-15, and MSE divided by amplitude squared varied by only 5.4e-12, confirming orthogonal invariance and quadratic error scaling. Mixing reduced the worst block maximum from 6.0 to 2.67 with Hadamard and 3.05 with Hadamard+SO(4), while SO(4) attention relative RMSE improved from 0.2030 to 0.1772; however, raw outlier reconstruction MSE worsened and storage reduction was only 1.45x versus FP16 with fp32 scales.

### Mechanism check

- Verdict: Built a NumPy MVP implementing normalized FWHT, block-diagonal SO(4) mixing, blockwise signed 3-bit quantization, dequantized attention, and 3-bit packing. The math checks passed: SO(4) Gram error was 8.9e-16, transformed dot-product error 7.1e-15, inverse error 1.6e-15, and MSE divided by amplitude squared varied by only 5.4e-12, confirming orthogonal invariance and quadratic error scaling. Mixing reduced the worst block maximum from 6.0 to 2.67 with Hadamard and 3.05 with Hadamard+SO(4), while SO(4) attention relative RMSE improved from 0.2030 to 0.1772; however, raw outlier reconstruction MSE worsened and storage reduction was only 1.45x versus FP16 with fp32 scales.
- Confidence: 8/10
- Limitations: Only toy NumPy experiments were performed. No real decoder, WikiText-2 or C4 perplexity, long-context cache benchmark, CUDA fused kernel, rotation calibration, throughput measurement, or lower-precision scale accounting was tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.8602
- Paired wins: 3/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_kv.py](https://synthcore.org/code/752/bench_kv.py)
- [bench_report.json](https://synthcore.org/code/752/bench_report.json)
- [experiment.py](https://synthcore.org/code/752/experiment.py)
- [report.md](https://synthcore.org/code/752/report.md)
- [report_bench_2026-09-01T022943.md](https://synthcore.org/code/752/report_bench_2026-09-01T022943.md)
- [results.json](https://synthcore.org/code/752/results.json)
- [Download all files as ZIP](https://synthcore.org/download/752)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.