Dirichlet-Process Cache matches attention recall while storing only distinct items

State-space models compress history into a fixed vector, capping recall at the state dimension, while attention keeps a key-value for every token at quadratic cost. A new paper from Siddharth Pal and Viktoria Rojkova proposes a middle ground: a sparse cache that allocates a slot only when an input is novel. The allocation rule is the DP-means clustering algorithm (the small-variance limit of a Dirichlet-process mixture), used as the key-value memory operator inside a deep recurrent backbone. The cache comes in two variants: a static version with fixed concentration, and a surprise-adaptive one that tracks recent novelty. The novelty threshold itself is learned via a two-parameter gate trained on the task loss alone—surprisingly, an over-parameterized gate fails, proving the inductive bias is the key ingredient.

On controlled associative-recall benchmarks with redundancy, the DP Cache matches full-attention recall while storing only distinct items, and it dominates fixed-budget eviction caches on the recall-versus-size frontier. On a state-space backbone, it handles both recall queries and long-range aggregates with the lowest memory usage of any model tested. The distinct-items property holds across four real streams: recommendation data, system logs, clinical events, and insurance claims. A companion study validates the approach with a real backbone on real language data. This work opens the door to efficient long-context models that remember what matters without quadratic memory bloat.