# Equal-Variation KV Cache

- ID: 664
- Canonical URL: https://synthcore.org/idea/664/equal-variation-kv-cache
- API JSON: https://synthcore.org/api/idea/664.json
- API Markdown: https://synthcore.org/api/idea/664.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.09974](https://arxiv.org/abs/2607.09974)
- Category: memory
- Solves: memory, accuracy, scalability
- ML areas: attention, kv-cache, memory
- Math tags: metric-geometry, approximation-theory, measure-theory
- Ratings: usefulness 8/10; difficulty 5/10; novelty 6/10

## Idea description

Compress a causal sequence by retaining history positions at equal increments of cumulative representation variation instead of at uniform time intervals. Use the resulting N representatives in a decoder that reconstructs piecewise-constant keys and values; the paper's minimax result predicts a worst-case reconstruction error of total variation divided by 2N, independent of where rapid changes occur.

## Mathematical statement

For an absolutely continuous history \(\pi:[0,T]\to E\), define cumulative variation \(V_\pi(t)=\int_0^t\|\dot\pi(s)\|_E\,ds\) and total variation \({\rm Var}(\pi)=V_\pi(T)\). The equal-variation encoder chooses breakpoints \(0=t_0<\cdots<t_N=T\) satisfying \(V_\pi(t_j)=j\,{\rm Var}(\pi)/N\), using a first-hitting-time convention when \(V_\pi\) has flat intervals. Its right-continuous step reconstruction \(\pi_N(t)=\pi(t_j)\) for \(t\in[t_j,t_{j+1})\) has sharp normalized minimax error \(1/(2N)\) under the paper's assumptions. The norm \(\|\cdot\|_E\) can be replaced by a learned feature-space norm; for transformer compression, \(\pi(t)\) is a projected key-value trajectory and variation is estimated by finite differences.

## Key formulas

- $$\|\epsilon\|_{E}=\sqrt{\mathbb{C}\epsilon\cdot\epsilon},\qquad \|\sigma\|_{F}=\sqrt{\mathbb{C}^{-1}\sigma\cdot\sigma}.$$
- $$V_{\pi}(t)=\int_{0}^{t}\|\dot{\pi}(s)\|_{E}\,ds,\qquad {\rm Var}(\pi)=V_{\pi}(T).$$
- $$V_{\pi}(t_j)=\frac{j}{N}{\rm Var}(\pi),\quad j=0,\ldots,N,\qquad \pi_N(t)=\pi(t_j)\ \text{for }t\in[t_j,t_{j+1}).$$
- $$\inf_{\mathcal E_N}\sup_{\pi}\frac{\|\pi-\mathcal D(\mathcal E_N(\pi))\|_{L^\infty}}{{\rm Var}(\pi)}=\frac{1}{2N}.$$

## Implementation notes

Integrate this at the long-context attention memory layer, before the attention kernel consumes the KV cache. For each incoming token t, form a low-dimensional feature z_t=P[h_t;k_t;v_t], where P is a fixed random projection or a small learned projection, and estimate local variation d_t=||z_t-z_{t-1}||_2. Maintain cumulative variation c_t=sum_{r=1}^t d_r. In an offline or chunked implementation, define thresholds q_j=j c_T/N and choose each segment boundary as the first token whose cumulative variation crosses the next threshold. Store a representative key and value for each segment, using variation-weighted averages kbar_j=sum_{r in S_j} d_r k_r/(sum_{r in S_j} d_r) and the analogous value average. Retain a recent uncompressed window to preserve local token identity. In streaming inference, use reservoir splitting: when a segment exceeds its variation budget, split it at the first threshold crossing and merge adjacent low-variation segments when necessary. The paper supplies the equal-variation allocation and 1/N scaling; P, the representative statistic, and the online policy are empirical choices. First test a small Transformer-XL or 1B decoder on PG19 and LongBench against uniform eviction, recent-window caching, and H2O at equal KV memory. Measure perplexity, retrieval accuracy, attention FLOPs, and reconstruction error versus N. Success is lower perplexity at fixed cache size and an empirical error curve close to 1/N, especially on sequences with bursts of rapid feature change.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built an equal-variation KV compression MVP with first-hitting cumulative-variation boundaries, representative averaging, trajectory-error checks, and a synthetic attention comparison. The sharp scalar prediction matched 1/(2N) exactly through N=32; burst-path errors decayed with fitted slope -1.12 and remained below the 1/N bound, while equal-variation location sensitivity was substantially lower than uniform timing. However, attention-output MSE generally favored uniform compression, so the mathematical mechanism manifested but an end-to-end accuracy win was not demonstrated.

### Mechanism check

- Verdict: Built an equal-variation KV compression MVP with first-hitting cumulative-variation boundaries, representative averaging, trajectory-error checks, and a synthetic attention comparison. The sharp scalar prediction matched 1/(2N) exactly through N=32; burst-path errors decayed with fitted slope -1.12 and remained below the 1/N bound, while equal-variation location sensitivity was substantially lower than uniform timing. However, attention-output MSE generally favored uniform compression, so the mathematical mechanism manifested but an end-to-end accuracy win was not demonstrated.
- Confidence: 8/10
- Limitations: No real Transformer, language-model perplexity, PG19/LongBench, H2O comparison, learned projection, streaming reservoir policy, or GPU benchmark was tested. The attention experiment is a small synthetic proxy and uses offline segment means rather than a production KV-cache kernel.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/125/bench_report.json)
- [bench_run.py](https://synthcore.org/code/125/bench_run.py)
- [experiment.py](https://synthcore.org/code/125/experiment.py)
- [report.md](https://synthcore.org/code/125/report.md)
- [report_bench_2026-08-30T153322.md](https://synthcore.org/code/125/report_bench_2026-08-30T153322.md)
- [results.json](https://synthcore.org/code/125/results.json)
- [Download all files as ZIP](https://synthcore.org/download/125)

## Disclaimer

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