# Entropy-Budgeted Contiguous KV Pooling

- ID: 177
- Canonical URL: https://synthcore.org/idea/177/entropy-budgeted-contiguous-kv-pooling
- API JSON: https://synthcore.org/api/idea/177.json
- API Markdown: https://synthcore.org/api/idea/177.md
- Verification status: audited
- Source: [arXiv:2608.25533](https://arxiv.org/abs/2608.25533)
- Category: architecture
- Solves: memory, speedup, accuracy
- ML areas: attention, kv-cache, transformer, inference-speedup
- Math tags: information-theory, combinatorics, optimization, probability
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Use the attention probability distribution over an ordered context to choose contiguous token groups whose pooled attention masses have entropy as close as possible to a prescribed upper budget R. Replace the corresponding key/value vectors by one weighted representative per group, preserving token order and reducing the KV-cache length from n to m. Unlike unconstrained token merging, the entropy constraint gives a direct control knob over how concentrated or diffuse the retained attention allocation may be.

## Mathematical statement

The paper defines a probability vector p=(p_1,...,p_n), where p_i>=0 and sum_i p_i=1, and a contiguous aggregation q=(q_1,...,q_m) induced by boundaries 0=b_0<b_1<...<b_m=n: q_k=sum_{i=b_{k-1}+1}^{b_k}p_i. Its optimization problem is max_{q in CA(p)} H(q) subject to H(q)<=R, with Shannon entropy H(q)=-sum_{k=1}^m q_k log_2(q_k), using 0 log 0=0. A merge of adjacent masses a and b changes entropy by Delta(a,b)=h(a)+h(b)-h(a+b), where h(x)=-x log_2 x; because merging categories cannot increase entropy, each contiguous merge has Delta(a,b)>=0. The paper reports that one efficient approximation has objective error at most h(p^downarrow_{floor(2^R)+1}), where p^downarrow_j is the j-th largest entry of p and h is binary entropy. We use this bound as a conservative diagnostic when the attention distribution has a small tail beyond the effective budget 2^R.

## Key formulas

- $$\max_{q\in CA(p)} H(q)\quad\text{subject to}\quad H(q)\le R.$$
- $$q_k=\sum_{i=b_{k-1}+1}^{b_k}p_i,\qquad 0=b_0<b_1<\cdots<b_m=n.$$
- $$H(q)=-\sum_{k=1}^{m}q_k\log_2 q_k,$$
- $$\Delta(a,b)=h(a)+h(b)-h(a+b),\qquad h(x)=-x\log_2 x,\qquad H(\text{after merge})=H(\text{before merge})-\Delta(a,b).$$

## Implementation notes

Integrate this at transformer inference between attention-score computation and KV-cache insertion. For a query or a small group of queries, compute attention probabilities p over the n context positions. Choose a target number of retained groups m and an entropy ceiling R. Each group is a contiguous interval; replace its keys and values by K'_k=(sum_{i in group k} p_i K_i)/(q_k+epsilon) and V'_k=(sum_{i in group k} p_i V_i)/(q_k+epsilon), while storing q_k and the interval boundaries. For an exact small-model prototype, enumerate all boundary tuples b_1,...,b_{m-1}, compute q and H(q), discard partitions with H(q)>R, and select the feasible partition with largest H(q). This costs O(C(n-1,m-1)nm) and is suitable for n<=32. For the scalable version, initialize singleton blocks and perform n-m adjacent merges. At each step calculate Delta for every neighboring pair, tentatively apply each candidate, and retain the merge producing the largest final entropy among candidates satisfying H<=R; use a two-step lookahead when the immediate merge overshoots the budget. Cache partitions at chunk boundaries or compute them from averaged attention over heads to amortize overhead. The formulas above are computed exactly; the only empirical choices are m, R, whether p is per-head or averaged, and whether K/V pooling uses attention weights or uniform weights. First test on a 1-2B decoder on WikiText-103 or C4 with context length 2048, comparing full KV attention, uniform contiguous pooling, and a standard heuristic such as importance-based eviction. Sweep m in {256,512,1024} and R in {log2(m)/2, log2(m)*0.75, log2(m)}. Measure perplexity at equal retained-cache size, attention-output cosine error, decode throughput, and peak KV memory. Success is at least 1.5x decode speed or 2x lower KV memory at a fixed perplexity degradation, with the entropy-bound diagnostic correlating with the observed error.

## Verification

- Status: audited
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built an exact contiguous entropy-constrained KV pooling prototype with attention-mass-weighted K/V representatives and stored log-mass priors. The merge identity held to 4.9e-17 numerical error, all 40 tail-bound diagnostics passed, and entropy pooling reduced mean cosine error from 0.2024 to 0.0723 versus uniform pooling at the same 16-to-6 cache reduction. This is a promising accuracy signal, but exact partition search is too slow for deployment and throughput was not directly measured.

### Mechanism check

- Verdict: Built an exact contiguous entropy-constrained KV pooling prototype with attention-mass-weighted K/V representatives and stored log-mass priors. The merge identity held to 4.9e-17 numerical error, all 40 tail-bound diagnostics passed, and entropy pooling reduced mean cosine error from 0.2024 to 0.0723 versus uniform pooling at the same 16-to-6 cache reduction. This is a promising accuracy signal, but exact partition search is too slow for deployment and throughput was not directly measured.
- Confidence: 7/10
- Limitations: Only synthetic single-query attention was tested with n=16, d=24, m=6 and 30 trials. No real transformer, language-model perplexity, multi-head attention, long-context setting, memory measurement, or end-to-end decode throughput was measured; exact enumeration is exponential and unsuitable beyond small n, although a basic greedy merge implementation is included.

## Artifacts

- [entropy_kv_pooling.py](https://synthcore.org/code/20/entropy_kv_pooling.py)
- [report.md](https://synthcore.org/code/20/report.md)
- [report_super_2026-08-30T101744.md](https://synthcore.org/code/20/report_super_2026-08-30T101744.md)
- [results.json](https://synthcore.org/code/20/results.json)
- [super_results.json](https://synthcore.org/code/20/super_results.json)
- [supercheck.py](https://synthcore.org/code/20/supercheck.py)
- [supercheck_report.md](https://synthcore.org/code/20/supercheck_report.md)
- [Download all files as ZIP](https://synthcore.org/download/20)

## Disclaimer

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