# DP-Means Distinct-Item Memory

- ID: 657
- Canonical URL: https://synthcore.org/idea/657/dp-means-distinct-item-memory
- API JSON: https://synthcore.org/api/idea/657.json
- API Markdown: https://synthcore.org/api/idea/657.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.09889](https://arxiv.org/abs/2607.09889)
- Category: memory
- Solves: memory, scalability, accuracy
- ML areas: ssm, attention, kv-cache, memory
- Math tags: probability, optimization, geometry, metric-geometry
- Ratings: usefulness 8/10; difficulty 4/10; novelty 6/10

## Idea description

Replace token-by-token KV storage after an SSM or recurrent encoder with an online allocate-on-novelty cache. A new slot is created only when the incoming key is sufficiently dissimilar from every stored key; otherwise the incoming value is merged into its nearest slot, so repeated or redundant content does not grow the cache.

## Mathematical statement

The novelty statistic is $\mathrm{nov}_t=1-\max_{i\in\mathrm{slots}}\mathrm{sim}(k_t,\kappa_i)$, where $k_t\in\mathbb{R}^d$ is the incoming key, $\kappa_i\in\mathbb{R}^d$ is the key prototype in occupied slot $i$, and $\mathrm{sim}(a,b)=a^\top b/(\|a\|_2\|b\|_2)$ is cosine similarity. The DP-means allocation rule creates a slot if $\mathrm{nov}_t>\tau$; otherwise it assigns the item to $j_t=\arg\max_i\mathrm{sim}(k_t,\kappa_i)$ and merges it into slot $j_t$. Here $v_t\in\mathbb{R}^{d_v}$ is the value and $\tau\in[0,2]$ is the novelty threshold: larger $\tau$ produces fewer, coarser clusters. A directly implementable merge is the count-weighted update $n_j\leftarrow n_j+1$, $\kappa_j\leftarrow((n_j-1)\kappa_j+k_t)/n_j$, and $u_j\leftarrow((n_j-1)u_j+v_t)/n_j$, where $n_j$ is slot usage and $u_j$ is its stored value. The count-weighted value merge is an adaptation; the paper's essential mathematical contribution is the DP-means novelty/allocation rule.

## Key formulas

- $$\mathrm{nov}_{t}=1-\max_{i\in\mathrm{slots}}\mathrm{sim}(k_t,\kappa_i),\qquad \mathrm{sim}(a,b)=\frac{a^{\top}b}{\|a\|_2\|b\|_2}.$$
- $$\text{if }\mathrm{nov}_{t}>\tau:\ \text{append }(k_t,v_t)\text{ as a new slot};\qquad\text{else }j_t=\arg\max_{i}\mathrm{sim}(k_t,\kappa_i)\text{ and merge into slot }j_t.$$
- $$n_{j_t}\leftarrow n_{j_t}+1,\qquad \kappa_{j_t}\leftarrow\frac{(n_{j_t}-1)\kappa_{j_t}+k_t}{n_{j_t}},\qquad u_{j_t}\leftarrow\frac{(n_{j_t}-1)u_{j_t}+v_t}{n_{j_t}}.$$
- $$r(q)=\operatorname{softmax}_{i\in\mathrm{slots}}\left(\frac{q^{\top}\kappa_i}{\sqrt d}\right),\qquad \operatorname{read}(q)=\sum_{i\in\mathrm{slots}}r_i(q)u_i.$$

## Implementation notes

Integrate the operator at the write side of a recurrent or SSM language model, immediately after the backbone produces per-token key and value tensors. For each sequence, maintain arrays `Kappa[M,d]`, `U[M,dv]`, `Counts[M]`, and an occupancy count; M is only a safety cap. Pseudocode: `for t in range(T): k,v = project(backbone_state[t]); k = k/(norm(k)+eps); if used == 0: allocate(k,v,1); else: sims = Kappa[:used] @ k; j = argmax(sims); novelty = 1-sims[j]; if novelty > tau and used < M: Kappa[used]=k; U[used]=v; Counts[used]=1; used += 1; else: Counts[j]+=1; Kappa[j]=((Counts[j]-1)*Kappa[j]+k)/Counts[j]; U[j]=((Counts[j]-1)*U[j]+v)/Counts[j]`. At query positions, produce q from the current hidden state and read the sparse cache using `softmax(q @ Kappa[:used].T / sqrt(d)) @ U[:used]`; add this vector to the SSM output through a learned residual gate. The paper directly supplies cosine novelty, nearest-slot assignment, and threshold allocation. The count-weighted merge and softmax read are adaptations and should be compared with EMA value updates and hard nearest-slot reads. Log occupied slots, allocation rate, within-slot cosine variance, read latency, and retrieval accuracy. First use a small GRU or diagonal SSM on an associative-recall dataset with fourfold repeated key-value items. Compare full attention, FIFO/LRU fixed-budget eviction, and this cache at equal hidden size and cache-byte budgets. Success means full-attention-level recall with roughly fourfold fewer entries on fourfold-redundant streams, lower peak memory, and cache growth tracking distinct items rather than token count. Follow with a language-model perplexity test on text containing repeated entities.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a readable DP-Means cosine-novelty cache with count-weighted key/value merging and a deterministic associative-recall test. The mechanism predictions were confirmed: the allocation boundary matched acos(1−tau) within 1 degree, orthogonal distinct-item counts matched exactly across thresholds, and merge MSE followed sigma^2/n with normalized factors 0.977–1.036. On the toy repeated-item stream, the cache achieved 4x compression with the same 1.00 recall as token memory; this is a promising mechanism result, not evidence of language-model improvement.

### Mechanism check

- Verdict: Built a readable DP-Means cosine-novelty cache with count-weighted key/value merging and a deterministic associative-recall test. The mechanism predictions were confirmed: the allocation boundary matched acos(1−tau) within 1 degree, orthogonal distinct-item counts matched exactly across thresholds, and merge MSE followed sigma^2/n with normalized factors 0.977–1.036. On the toy repeated-item stream, the cache achieved 4x compression with the same 1.00 recall as token memory; this is a promising mechanism result, not evidence of language-model improvement.
- Confidence: 9/10
- Limitations: Only a synthetic associative-recall workload was tested; no trained GRU/SSM, language-model perplexity, softmax cache read, GPU benchmark, noisy-key clustering stress test, or FIFO/LRU eviction comparison was evaluated.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.16175
- Paired wins: 3/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_dp_means.py](https://synthcore.org/code/122/bench_dp_means.py)
- [bench_dp_means_fast.py](https://synthcore.org/code/122/bench_dp_means_fast.py)
- [bench_report.json](https://synthcore.org/code/122/bench_report.json)
- [dp_means_experiment.py](https://synthcore.org/code/122/dp_means_experiment.py)
- [report.md](https://synthcore.org/code/122/report.md)
- [report_bench_2026-08-30T162506.md](https://synthcore.org/code/122/report_bench_2026-08-30T162506.md)
- [results.json](https://synthcore.org/code/122/results.json)
- [Download all files as ZIP](https://synthcore.org/download/122)

## Disclaimer

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