# Joint Tucker-rank and residual-bit KV allocator

- ID: 813
- Canonical URL: https://synthcore.org/idea/813/joint-tucker-rank-and-residual-bit-kv-allocator
- API JSON: https://synthcore.org/api/idea/813.json
- API Markdown: https://synthcore.org/api/idea/813.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.12550](https://arxiv.org/abs/2607.12550)
- Category: memory
- Solves: memory, accuracy, scalability
- ML areas: transformer, kv-cache, attention, inference-speedup
- Math tags: tensor-decomposition, optimization, linear-algebra, quantization
- Ratings: usefulness 8/10; difficulty 6/10; novelty 6/10

## Idea description

Compress each layer's KV tensor with a partial Tucker approximation over token and feature axes, then encode the truncation residual with a rotated uniform quantizer. Select token rank, feature rank, and residual bit-width jointly under a global byte budget, allowing values with flat spectra to receive residual bits while keys may receive more low-rank capacity.

## Mathematical statement

For a cache tensor X in R^{L x H x T x D}, L is the number of layers, H is the number of heads or KV heads, T is the cached-token count, and D is the head-feature width. Group layers and retain the layer and head axes explicitly while approximating each group by a partial Tucker reconstruction     ilde{X}(r_T,r_d), where r_T and r_d are the token- and feature-axis ranks. The truncation residual is R=X-    ilde{X}(r_T,r_d). Let Q be an orthogonal rotation satisfying Q^TQ=I, and let Q_b denote entrywise uniform quantization at b bits; the decoded cache is \hat{X}=    ilde{X}+Q^TQ_b(QR). For layer group g and cache type c in {K,V}, choose z=(r_T,r_d,b) with byte cost C_{g,c}(z) and normalized distortion D_{g,c}(z). The joint Lagrangian is L(z,lambda)=sum_{g,c}D_{g,c}(z_{g,c})+lambda(sum_{g,c}C_{g,c}(z_{g,c})-B), where B is the total byte budget and lambda>=0 is the byte price. For fixed lambda, each group independently chooses argmin_z[D_{g,c}(z)+lambda C_{g,c}(z)]; binary search on lambda finds a budget-feasible allocation.

## Key formulas

- $$R=X-\tilde{X}(r_T,r_d),\qquad \widehat{X}=\tilde{X}(r_T,r_d)+Q^{\mathsf T}Q_b(QR),\qquad Q^{\mathsf T}Q=I.$$
- $$D_{g,c}(r_T,r_d,b)=\frac{\left\|X_{g,c}-\left[\tilde{X}_{g,c}(r_T,r_d)+Q_{g,c}^{\mathsf T}Q_b\!\left(Q_{g,c}R_{g,c}\right)\right]\right\|_F^2}{\left\|X_{g,c}\right\|_F^2},\qquad R_{g,c}=X_{g,c}-\tilde{X}_{g,c}(r_T,r_d).$$
- $$\mathcal{L}(z,\lambda)=\sum_{g,c}D_{g,c}(z_{g,c})+\lambda\left(\sum_{g,c}C_{g,c}(z_{g,c})-B\right),\qquad z_{g,c}^{\star}(\lambda)=\arg\min_{z\in\mathcal{Z}}\left[D_{g,c}(z)+\lambda C_{g,c}(z)\right].$$
- $$C_{g,c}(r_T,r_d,b)\approx sH_g\left(r_TT_g+r_dr_T+r_dD_g\right)+\frac{b}{8}H_gT_gD_g+\text{metadata bytes},$$

## Implementation notes

Integrate this at KV-cache admission time, before storing K and V tensors for each layer. Divide layers into groups, for example four consecutive layers, and maintain separate candidate tables for K and V. From a calibration run, collect each group tensor X with shape [heads, tokens, features]. Enumerate r_T in {4, 8, 16, 32, T}, r_d in {4, 8, 16, 32, D}, and b in {0, 2, 4, 8}. Compute a partial Tucker approximation using sequential SVD or randomized SVD on the token and feature unfoldings, reconstruct X_tilde, and set R=X-X_tilde. Apply a fixed orthogonal transform, quantize the residual, and measure normalized Frobenius distortion. Calculate actual storage including Tucker factors, core tensors, residual codes, scales, transform metadata, and alignment padding; do not rely only on the asymptotic cost expression. Store candidate pairs (D,C). For a trial lambda, choose the candidate minimizing D+lambda*C independently for every group and cache type. Binary-search lambda until total storage is within one alignment block of budget B, then optionally improve the result by swapping candidates with the best distortion reduction per added byte. At inference, reconstruct the low-rank part and residual immediately before attention, preferably in a fused kernel. First test Mistral-7B at 8k and 32k context against FP16 KV, global-rank Tucker, and uniform 4-bit KV at equal 2x and 3x memory reduction. Record perplexity, needle retrieval accuracy, peak KV bytes, decode tokens/sec, and decompression bandwidth. Success is near-baseline quality with lower memory and better distortion than fixed-rank or fixed-bit baselines.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built and ran a NumPy MVP for partial Tucker reconstruction, rotated residual quantization, explicit storage costs, and joint budget allocation. Orthogonal rotation preserved residual norm exactly, Tucker distortion decreased monotonically with rank, and quantization MSE decreased 16.25–25.65x per two added bits versus the high-rate 16x prediction. At a 4,000-byte budget, joint allocation reached distortion 0.030199 versus 0.032503 for fixed 4-bit allocation, a modest 7.1% improvement; the mechanism shows a real toy-scale signal.

### Mechanism check

- Verdict: Built and ran a NumPy MVP for partial Tucker reconstruction, rotated residual quantization, explicit storage costs, and joint budget allocation. Orthogonal rotation preserved residual norm exactly, Tucker distortion decreased monotonically with rank, and quantization MSE decreased 16.25–25.65x per two added bits versus the high-rate 16x prediction. At a 4,000-byte budget, joint allocation reached distortion 0.030199 versus 0.032503 for fixed 4-bit allocation, a modest 7.1% improvement; the mechanism shows a real toy-scale signal.
- Confidence: 7/10
- Limitations: This is a synthetic four-group NumPy experiment, not a transformer KV-cache evaluation. It does not test perplexity, needle retrieval, decode speed, GPU memory, fused reconstruction, real layer grouping, alignment padding, per-channel scales, or Mistral contexts. The dense random orthogonal transform is used only for mathematical verification, not efficient inference.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/153/bench_report.json)
- [joint_tucker_kv.py](https://synthcore.org/code/153/joint_tucker_kv.py)
- [report.md](https://synthcore.org/code/153/report.md)
- [report_bench_2026-08-30T174447.md](https://synthcore.org/code/153/report_bench_2026-08-30T174447.md)
- [results.json](https://synthcore.org/code/153/results.json)
- [run_bench.py](https://synthcore.org/code/153/run_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/153)

## Disclaimer

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