Pith. sign in

REVIEW 3 major objections 4 minor 29 references

Remembering Distinct Items, Not Tokens: A Learnable Dirichlet-Process Cache Between State-Space Models and Attention

T0 review · 3 major / 4 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A sparse cache that allocates slots only for novel inputs matches full-attention recall while storing the distinct items, not every token.

desk verdict Clean, honestly scoped mechanism study: DP-means as the KV cache itself works in the separation regime they built, with a sharp inductive-bias ablation; language-scale proof is deferred. read the letter →

arxiv 2607.09889 v1 pith:T6Q53TUE submitted 2026-07-10 cs.LG cs.AIcs.CLcs.NE

Siddharth Pal , Viktoria Rojkova This is my paper
classification cs.LGcs.AIcs.CLcs.NE
keywords Dirichletprocesscacheallocate-on-noveltyassociativerecallstate-spacemodelssparsekey-valuememoryDP-meansfixed-budgetevictionsurprise-adaptiveconcentration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Fixed-state sequence models forget once the past outgrows their fixed memory; attention never forgets but pays quadratic cost and a cache that grows with every token. This paper shows a middle path: open a new memory slot only when an input is genuinely novel, otherwise merge it into the nearest existing slot. The rule is the classic DP-means clustering step, used here as the key-value operator of a deep recurrent model rather than as Bayesian inference. On a controlled recall task with deliberate redundancy the cache reaches perfect recall while keeping only the distinct items; it dominates the usual fixed-budget eviction schemes on the accuracy-versus-size curve; and when stacked on a state-space backbone it answers both a recall query and a long-range aggregate at the lowest memory of any model tested. A two-parameter novelty gate trained solely on the task loss recovers the same rule, proving the inductive bias, not gate capacity, is what matters. The same allocation tracks distinct entities on four real streams (movies, system logs, clinical events, insurance claims) with no per-domain retuning.

What carries the argument

The DP-means allocation rule: novelty is 1 minus the maximum cosine similarity of the incoming key to existing slots; if novelty exceeds a concentration threshold a new slot is opened, otherwise the key is merged into the nearest slot. This is the small-variance MAP limit of a Dirichlet-process mixture, repurposed as the online cache operator. A surprise-adaptive variant further modulates the effective budget by the recent allocation rate so capacity expands during novelty bursts and contracts once the stream settles.

What would settle it

Train the cache end-to-end on a real language-model backbone with learned embeddings and measure whether it still reaches near-attention recall accuracy while keeping roughly the number of distinct entities; if no fixed or learned threshold can separate true distinct tokens without massive over- or under-allocation, the claim fails.

Watch

Extended reading notes

Core claim

A Dirichlet-process allocate-on-novelty sparse cache, used as the key-value memory of a deep recurrent backbone, matches full-attention associative recall while storing only on the order of the distinct items rather than the tokens. It dominates fixed-budget eviction caches on the recall-versus-size frontier, composes with a state-space model to perform both recall and long-range integration at lowest memory, and its allocation rule is recovered end-to-end by a minimal two-parameter novelty-threshold gate trained on the task loss alone.

Load-bearing premise

Distinct items must produce keys that stay well separated from one another while repeats remain nearly identical, so a single cosine threshold cleanly decides novelty; heavy overlap among real embeddings would break the clean separation.

Editorial extensions

If this is right

  • Sequence models can keep attention-level associative recall at a memory cost set by the number of distinct items rather than sequence length.
  • Fixed-budget eviction policies are dominated by novelty allocation on the recall-versus-size frontier whenever redundancy is present.
  • The allocate-on-novelty rule is learnable from task loss alone with a two-parameter gate; extra gate capacity without the novelty bias fails.
  • Composing the cache with a state-space backbone yields models that jointly handle content-addressed recall and long-range aggregation at the lowest memory of either pure approach.
  • The identical rule tracks distinct entities across real heavy-tailed streams and can itself serve as an online log parser.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the separation assumption holds for learned embeddings, the cache could cut long-context KV-cache memory by the redundancy factor without losing rare-fact retrieval.
  • The surprise-adaptive concentration supplies a nonparametric middle ground between static sparse caches and fully learned write gates for non-stationary streams.
  • Online clustering rules of this family could replace fixed-size external memories across both transformers and state-space models.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes a sparse key-value cache for sequence models that allocates a new slot only when an input is novel under the DP-means (Dirichlet-process small-variance) rule, so cache size tracks the number of distinct items rather than tokens. Two variants are developed: a static cache with fixed concentration threshold τ and a surprise-adaptive cache whose effective budget follows an EMA of the recent allocation rate. On a controlled associative-recall probe with redundancy the cache matches full-attention recall at the distinct-item budget, dominates re-implemented fixed-budget eviction policies (H2O-style, StreamingLLM-style, SnapKV, recency) on the recall-versus-size frontier, composes with an SSM backbone for joint recall-plus-integration at lowest memory, and is recovered end-to-end by a two-parameter novelty-threshold gate trained solely on task loss (while an over-parameterized gate fails). The distinct-items property is checked on four real streams; a full language-model validation is deferred to a companion study. Scope is explicitly limited to controlled mechanism studies at modest scale.

Significance. If the mechanism holds under realistic conditions, it supplies a clean, learnable middle ground on the fixed-state / full-attention axis for streams that contain redundancy, with memory cost set by distinct cardinality rather than length. The inductive-bias ablation (two-parameter novelty gate recovers the rule; capacity alone does not), seed-stable tables, multi-machine cross-checks, and public multi-domain streams are genuine strengths. The synthesis of classical DP-means allocation as a deep key-value operator, together with the adaptive-concentration schedule and the honest scoping, is a useful contribution even if the language-scale validation remains future work.

major comments (3)
  1. [§3.1.7, §4, Abstract] The central distinct-items claim and the reported multi-fold savings rest on a clean bimodal similarity regime (near-unit self-similarity of repeats, near-zero cross-similarity of distinct entities) so that a single cosine threshold saturates exactly at true cardinality K. This regime is engineered by construction in the associative-recall probe (identical embeddings for repeats) and, by the authors’ own statement in §3.1.7, for the MovieLens, MIMIC and claims streams (synthetic keys). Only the log-parsing result uses natural keys, and even there grouping accuracy is 0.89 rather than perfect. Section 4 correctly flags that “on real, overlapping data the threshold and the merge step would need care,” yet the abstract and contribution list still present the four-stream confirmation as establishing the property “unchanged.” A load-bearing experiment with learned or naturally overlapping emb
  2. [§3, Tables in 3.1.1–3.1.3] All baselines are re-implemented minimal mechanisms (diagonal SSM, full softmax, recency/H2O/StreamingLLM/SnapKV-style eviction, kNN) rather than the published systems. The paper states this clearly, yet the language of “dominates the deployed fixed-budget eviction caches” and the tables that list “H2O heavy-hitter,” “StreamingLLM,” etc., invite a systems-level reading. Because the comparison is mechanism-level only, any claim that the DP cache is preferable to the actual deployed systems (which include additional engineering, learned components, and different read paths) is not supported by the present evidence and should be qualified more tightly.
  3. [§3.2, Eqs. (4)–(6)] Approach II (surprise-adaptive concentration) is shown to help only under deliberately non-stationary demand and to be neutral under stationary demand; both sides are confirmed on real streams. This is clean, but the adaptive schedule still relies on the same novelty threshold for the underlying allocate/merge decision. When embeddings overlap, the temperature merely modulates budget; it does not correct mis-merges of distinct items or spurious near-duplicates. The non-stationarity experiments therefore inherit the same separation assumption and do not enlarge the regime in which the distinct-items property is guaranteed.
minor comments (4)
  1. [Figures 1–2] Figure 1 and Figure 2 captions refer to “log scale” and “recall-versus-size frontier” but do not state the exact redundancy or number of value classes; adding these numbers would make the plots self-contained.
  2. [§2, “A learnable gate”] The novelty feature used by the learnable gate (nov_t = 1 - max_{s<t} sim(k_t, k_s)) is defined over previous tokens rather than over current slots; a one-sentence clarification of why this is equivalent (or preferable) for the soft-mask training would help.
  3. [Header] The arXiv identifier and date line read “2607.09889v1 [cs.LG] 10 Jul 2026”; this is presumably a placeholder and should be corrected before camera-ready.
  4. [§2 / §3.1.9] A short explicit statement of the computational complexity of the nearest-slot search (already measured in Fig. 7) in the main text near Eqs. (1)–(2) would make the build-versus-read trade-off easier to locate.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: DP-means allocation is an independent classical rule; recall and distinct-item tracking are measured outcomes, not definitional tautologies.

full rationale

The paper's central claims are empirical mechanism results, not first-principles derivations that close on themselves. The allocation operator is the classical DP-means / leader rule (Kulis & Jordan; Antoniak), imported as a known clustering primitive and used as a key-value memory; the paper does not redefine novelty or the threshold in terms of the recall metric it later reports. Equations (1)-(2) compute cosine novelty and open/merge slots; equation (3) is ordinary attention over the resulting slots. The learnable-gate study trains a two-parameter novelty-threshold gate solely on task loss (no rule supervision) and recovers the rule, while an over-parameterized gate with the same novelty feature fails - an ablation of inductive bias, not a fit of the target quantity. Real-stream checks report that allocated slots track the number of distinct entities on public datasets; for recommendation/clinical/claims the keys are synthetic (explicitly scoped), and the log-parser result is scored against ground-truth templates. No equation equates the claimed recall advantage to a fitted parameter by construction, and there is no load-bearing self-citation uniqueness theorem. The separation regime that makes a single threshold work is an assumption the paper itself flags in Scope, not a circular step. Score 1 only for the minor, non-load-bearing character of the novelty claim (synthesis of known ingredients).

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The central claim rests on the classical DP-means allocation rule, cosine novelty, a fixed or surprise-driven concentration, and the modeling assumption that distinct items are well-separated in key space. Free parameters are the usual thresholds and EMA rates; no new physical entities are invented. The main load-bearing modeling choice is the well-separated-keys regime that makes a single threshold recover the true distinct count.

free parameters (4)
  • novelty threshold τ (concentration)
    Hand-chosen or swept; the paper shows a plateau of good values [0.5, 0.8] on real streams but the operating point remains a free hyperparameter of the static cache.
  • surprise EMA rate η and budget slope β (Approach II)
    Control how quickly the adaptive concentration tracks allocation rate; chosen for the non-stationary experiments.
  • two-parameter gate scalars a, b
    Learned from task loss; minimal capacity that recovers the threshold rule.
  • target budget M / M0 for soft-mask training and adaptive schedule
    Sets the soft keep-count penalty and the base of the adaptive budget.
assumptions (4)
  • standard math DP-means / leader rule: open a new cluster when nearest distance exceeds threshold, else merge (small-variance MAP limit of a Dirichlet-process mixture).
    Invoked as the allocation operator (Eqs. 1-2); classical result of Kulis & Jordan and earlier online clustering.
  • domain assumption Cosine similarity on keys is a sufficient novelty signal for allocation.
    Used throughout the method section; works when keys of distinct items are well-separated.
  • domain assumption On data drawn from a finite set of item types the online rule saturates at the true number of distinct types rather than growing as α ln N.
    Stated in the method section via Antoniak signature versus finite-type saturation; underpins the 'distinct-items' cost claim.
  • ad hoc to paper Repeats of an item share sufficiently similar embeddings that they merge into the same slot under a fixed threshold.
    Built into the synthetic probe (identical embeddings) and assumed for real streams; Scope section notes that real overlapping embeddings would need care.
invented entities (1)
  • Dirichlet-process cache (static and surprise-adaptive) as key-value memory operator
    purpose: Serves as the sparse middle-ground memory between fixed-state SSMs and full attention.
    Not a new mathematical object; a new architectural use of an existing clustering rule. independent_evidence is false because the entity is defined by its use inside this paper's experiments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Remembering Distinct Items, Not Tokens: A Learnable Dirichlet-Process Cache Between State-Space Models and Attention." pith.science (2026). https://pith.science/paper/T6Q53TUE

@misc{pith2026260709889,
  author       = {Pith},
  title        = {Pith review of: Remembering Distinct Items, Not Tokens: A Learnable Dirichlet-Process Cache Between State-Space Models and Attention},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T6Q53TUE}},
  note         = {Machine review of arXiv:2607.09889}
}
read the original abstract

Fixed-state sequence models compress an unbounded past into a bounded state, which caps their associative recall at roughly the state dimension; attention escapes the cap by keeping a key-value entry for every token, at quadratic compute and a cache that grows with the sequence. We study the middle ground: a sparse cache that allocates a slot only when an input is novel, so its size tracks the number of distinct items rather than the number of tokens. The allocation rule is the DP-means clustering rule, the small-variance limit of a Dirichlet-process mixture, used not as latent-variable inference but as the key-value memory operator for a deep recurrent backbone. We develop it in two forms, a static cache with a fixed concentration and a surprise-adaptive variant whose concentration follows the recent novelty rate. On a controlled associative-recall benchmark with redundancy we show that the cache matches full-attention recall while storing only the distinct items, that it dominates a fixed-budget eviction cache on the recall-versus-size frontier, and that on a state-space backbone it answers both a recall query and a long-range aggregate at the lowest memory of any model tested. The allocation is learnable end to end: a two-parameter novelty-threshold gate trained on the task loss alone recovers the rule exactly, whereas an over-parameterized gate fails, so the operative ingredient is the inductive bias rather than capacity. The evidence is a family of controlled mechanism studies at modest scale, with the distinct-items property confirmed on four real streams (recommendation, systems logs, clinical events, and insurance claims); a real-backbone, real-corpus language validation is pursued in a companion study.

Figures

Figures reproduced from arXiv: 2607.09889 by the authors.

Figure 1
Figure 1. Mechanism comparison (K=64 distinct in L=256 tokens). Left: recall — the DP cache and attention solve the task, the fixed-state SSM and recency eviction fall short. Right: stored slots (log scale, the cost) — the DP cache uses one slot per distinct item where attention and the kNN cache store every token. 3.1.2 The concentration knob dominates eviction Sweeping the novelty threshold traces a recall-versus-size front… view at source ↗
Figure 2
Figure 2. Recall versus cache size against the deployed fixed-budget baselines. The heavy-hitter [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Real recall task (MovieLens genre recall), matched budget. The heavy-hitter (H2O), [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: State-space backbone with the sparse cache. Left: the hybrid matches attention on [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Threshold sensitivity on the real streams. Left: recall is flat at the ceiling across [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Online allocate-on-novelty versus offline [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Cost versus stream length N at a fixed number of distinct items. Left: the DP read stays flat (O(K)) while attention’s read grows (O(N)). Right: the slot count stays bounded near K while the DP build cost grows linearly (O(N |slots|)) — the trade is a heavier one-time …
Figure 8
Figure 8. Figure 8: Adaptive concentration on non-stationary demand. Left: the budget (slots per phase) [PITH_FULL_IMAGE:figures/full_fig_p013_8.png]
Figure 9
Figure 9. Figure 9: The surprise-adaptive concentration on two real streams. Top (MovieLens): the per [PITH_FULL_IMAGE:figures/full_fig_p014_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 21 linked inside Pith

  1. [1]

    [Antoniak(1974)] C. E. Antoniak. Mixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems.The Annals of Statistics, 2(6):1152–1174,

    1974

  2. [2]

    Arora, S

    [Arora et al.(2023)] S. Arora, S. Eyuboglu, A. Timalsina, I. Johnson, M. Poli, J. Zou, A. Rudra, and C. R´ e. Zoology: Measuring and Improving Recall in Efficient Language Models

    2023

  3. [3]

    [Beal et al.(2002)] M

    arXiv:2312.04927. [Beal et al.(2002)] M. J. Beal, Z. Ghahramani, and C. E. Rasmussen. The Infinite Hidden Markov Model.NeurIPS,

    arXiv 2002

  4. [4]

    Behrouz, P

    [Behrouz et al.(2024)] A. Behrouz, P. Zhong, and V. Mirrokni. Titans: Learning to Memorize at Test Time

    2024

  5. [5]

    [Du & Li(2016)] M

    arXiv:2501.00663. [Du & Li(2016)] M. Du and F. Li. Spell: Streaming Parsing of System Event Logs.ICDM,

    arXiv 2016

  6. [6]

    Fountas et al

    [Fountas et al.(2025)] Z. Fountas et al. Human-inspired Episodic Memory for Infinite Context LLMs (EM-LLM).ICLR,

    2025

  7. [7]

    [Fox et al.(2011)] E

    arXiv:2407.09450. [Fox et al.(2011)] E. B. Fox, E. B. Sudderth, M. I. Jordan, and A. S. Willsky. Bayesian Nonpara- metric Inference of Switching Linear Dynamical Systems.IEEE Transactions on Signal Processing, 59(4):1569–1585,

    arXiv 2011

  8. [8]

    Geadah, International Brain Laboratory, and J

    [Geadah et al.(2024)] V. Geadah, International Brain Laboratory, and J. W. Pillow. Parsing Neural Dynamics with Infinite Recurrent Switching Linear Dynamical Systems.ICLR,

    2024

Show all 29 references
  1. [9]

    [Gu et al.(2022b)] A

    arXiv:2111.00396. [Gu et al.(2022b)] A. Gu, A. Gupta, K. Goel, and C. R´ e. On the Parameterization and Initializa- tion of Diagonal State Space Models (S4D).NeurIPS,

    arXiv

  2. [10]

    [Gu & Dao(2023)] A

    arXiv:2206.11893. [Gu & Dao(2023)] A. Gu and T. Dao. Mamba: Linear-Time Sequence Modeling with Selective State Spaces

    2023 arXiv

  3. [11]

    [He et al.(2017)] P

    arXiv:2312.00752. [He et al.(2017)] P. He, J. Zhu, Z. Zheng, and M. R. Lyu. Drain: An Online Log Parsing Ap- proach with Fixed Depth Tree.ICWS,

    2017 arXiv

  4. [12]

    Jelassi, D

    [Jelassi et al.(2024)] S. Jelassi, D. Brandfonbrener, S. M. Kakade, and E. Malach. Repeat After Me: Transformers are Better than State Space Models at Copying.ICML,

    2024

  5. [13]

    [Khandelwal et al.(2020)] U

    arXiv:2402.01032. [Khandelwal et al.(2020)] U. Khandelwal, O. Levy, D. Jurafsky, L. Zettlemoyer, and M. Lewis. Gener- alization through Memorization: Nearest Neighbor Language Models.ICLR,

    2020 arXiv

  6. [14]

    [Kitaev et al.(2020)] N

    arXiv:1911.00172. [Kitaev et al.(2020)] N. Kitaev, L. Kaiser, and A. Levskaya. Reformer: The Efficient Transformer. ICLR,

    1911 arXiv

  7. [15]

    [Kulis & Jordan(2012)] B

    arXiv:2001.04451. [Kulis & Jordan(2012)] B. Kulis and M. I. Jordan. Revisiting k-means: New Algorithms via Bayesian Nonparametrics.ICML,

    2001 arXiv

  8. [16]

    [Lample et al.(2019)] G

    arXiv:1111.0352. [Lample et al.(2019)] G. Lample, A. Sablayrolles, M. Ranzato, L. Denoyer, and H. J´ egou. Large Memory Layers with Product Keys.NeurIPS,

    2019 arXiv

  9. [17]

    [Li et al.(2024)] Y

    arXiv:1907.05242. [Li et al.(2024)] Y. Li, Y. Huang, B. Yang, B. Venkitesh, A. Locatelli, H. Ye, T. Cai, P. Lewis, and D. Chen. SnapKV: LLM Knows What You are Looking for Before Gener- ation.NeurIPS,

    1907 arXiv

  10. [18]

    [Martins et al.(2022)] P

    arXiv:2404.14469. [Martins et al.(2022)] P. H. Martins, Z. Marinho, and A. F. T. Martins.∞-former: Infinite Memory Transformer.ACL,

    2022 arXiv

  11. [19]

    [Mohtashami & Jaggi(2023)] A

    arXiv:2109.00301. [Mohtashami & Jaggi(2023)] A. Mohtashami and M. Jaggi. Landmark Attention: Random-Access Infinite Context Length for Transformers.NeurIPS,

    2023 arXiv

  12. [20]

    [Pritzel et al.(2017)] A

    arXiv:2305.16300. [Pritzel et al.(2017)] A. Pritzel, B. Uria, S. Srinivasan, A. Puigdom` enech, O. Vinyals, D. Hass- abis, D. Wierstra, and C. Blundell. Neural Episodic Control.ICML,

    2017 arXiv

  13. [21]

    [Ramsauer et al.(2021)] H

    arXiv:1703.01988. [Ramsauer et al.(2021)] H. Ramsauer et al. Hopfield Networks is All You Need.ICLR,

    2021 arXiv

  14. [22]

    [Roy et al.(2021)] A

    arXiv:2008.02217. [Roy et al.(2021)] A. Roy, M. Saffar, A. Vaswani, and D. Grangier. Efficient Content-Based Sparse Attention with Routing Transformers.TACL,

    2008 arXiv

  15. [23]

    [Teh et al.(2006)] Y

    arXiv:2003.05997. [Teh et al.(2006)] Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei. Hierarchical Dirichlet Processes.Journal of the American Statistical Association, 101(476):1566–1581,

    2003 arXiv

  16. [24]

    [Vyas et al.(2020)] A. Vyas, A. Katharopoulos, and F. Fleuret. Fast Transformers with Clustered Attention.NeurIPS,

    2020

  17. [25]

    [Wu et al.(2018)] Y

    arXiv:2007.04825. [Wu et al.(2018)] Y. Wu, G. Wayne, A. Graves, and T. Lillicrap. The Kanerva Machine: A Generative Distributed Memory.ICLR,

    2007 arXiv

  18. [26]

    [Wu et al.(2022)] Y

    arXiv:1804.01756. [Wu et al.(2022)] Y. Wu, M. N. Rabe, D. Hutchins, and C. Szegedy. Memorizing Transformers. ICLR,

    2022 arXiv

  19. [27]

    [Xiao et al.(2024)] G

    arXiv:2203.08913. [Xiao et al.(2024)] G. Xiao, Y. Tian, B. Chen, S. Han, and M. Lewis. Efficient Streaming Language Models with Attention Sinks (StreamingLLM).ICLR,

    2024 arXiv

  20. [28]

    15 [Zhang et al.(2023)] Z

    arXiv:2309.17453. 15 [Zhang et al.(2023)] Z. Zhang et al. H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models.NeurIPS,

    2023 arXiv

  21. [29]

    arXiv:2306.14048. 16

    arXiv

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.