Limits of attention mechanisms with correlated repeated data items
Beyond Deduplication: Sharp Retrieval Limits for Attention with Correlated Distractors
Machine Learning
Summary
When computer systems try to find important information in lots of data, repeated or similar items can confuse them in different ways. The authors study a mathematical model showing that simply discounting repeated groups of similar data points is not enough to fix this problem. Instead, averaging the scores before making a decision works better, especially when the similar items are closely related. Their experiments with sentence data confirm these findings and show when each method helps or hurts performance.
What this means in practice
- •For machine learning engineers: Improve attention-based search and retrieval systems by applying score averaging to better handle groups of similar data items.
- •For natural language processing teams: Design better sentence embedding retrieval algorithms that distinguish relevant items among many correlated distractions using insights from this model.
Tested on one dataset.
Authors
Heehyun Park
Abstract
Redundant context affects attention through two distinct mechanisms: repeated items add normalization mass, while score variation within correlated groups can produce extreme individual scores. We separate these effects in a planted retrieval model with exponentially many Gaussian distractors arranged in known, exponentially large clusters. The model is a two-level generalized random energy model, whose classical free energy yields exact retrieval thresholds. Gaussian interpolation further shows that increasing positive correlation at fixed token count lowers the distractor free energy, unlike adding duplicates. Our main result identifies a sharp limitation of subtracting log cluster size from pre-softmax scores: this correction removes multiplicity but retains within-cluster extremes. Even a temperature chosen after observing all scores cannot lower the required signal below $\sqrt{2α_1}$, where $α_1$ is the exponential rate of the number of clusters. Averaging scores before exponentiation instead suppresses these fluctuations and achieves $\sqrt{2ρα_1}$, where $ρ$ is the within-cluster correlation. The gap persists after adding exponentially many singleton distractors, so group size alone does not identify the target, and extends to fixed finite hierarchies of light-tailed independent-increment scores. Finite-sample, stability, and participation results complement the asymptotic analysis. A controlled retrieval experiment with frozen sentence embeddings supports this distinction while delineating its scope: averaging helps when the relevant item is a singleton, but can discard useful evidence when a relevant group contains multiple matching items.