TANSAR: Editable and Attributable Correlation Matrix Memories under Correlated Keys, with Rule-Constrained Multi-Hop Knowledge Editing
Authors: Abdulhady Abas Abdulla, Jiyan Salim Mahmud, Fatemeh Daneshfar, Hussein Mohammed Ali, Mourad Oussalah, Muhammad Bilal
Organizations: University of Kurdistan Hewlêr, Erbil, Kurdistan Region, Iraq · Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary · Department of Computer Engineering, University of Kurdistan, Sanandaj, Iran · Cybersecurity Department, Tishk International University, Erbil, Kurdistan Region, Iraq · University of Oulu, Oulu, Finland · Lancaster University, Lancaster, United Kingdom
Correlation Matrix Memories (CMMs) store associations as sums of rank-one outer products, providing closed-form addressability, exact deletion, and linear attribution. While classical analyses assume random, orthogonal keys, semantic encoders produce correlated representations. We analyse CMMs under correlated keys using frame-theoretic coherence: (i) capacity bounds yielding an encoder-independent limit n≤d(1+ε2) for mean squared crosstalk ε2; (ii) an exact characterisation of the collateral effect of deleting an association, guaranteeing that deletion never invalidates certified associations; and (iii) a geometric transparency bound demonstrating why attribution requires candidate sets of centred keys. On this basis, we introduce Topology-Aware Neuro-Symbolic Associative Retrieval (TANSAR). TANSAR traverses a directed acyclic association graph, prunes invalid paths via sound ground Horn constraints, and injects a representation derived strictly from the verified path into the residual stream of a frozen language model, guarded by a Clopper--Pearson selective-risk gate. Controlled experiments confirm all theoretical bounds. In multi-hop knowledge editing, Horn pruning reduces answer contradictions from 25.1% to 0.5%, whereas Hopfield retrieval incurs 24% contradictions when stale associations remain stored (and 0% if stale associations are removed). An end-to-end edit transaction requires 13.6 ms on a standard CPU and 2.37 ms on GPU. The symbolic component matches gold labels across all 600 ProofWriter theories and achieves 94.0% agreement on FOLIO, demonstrating sound and efficient multi-hop associative retrieval with exact unlearning.
Figures & tables
Method
GF
Del
Add
Con
ROME / MEMIT
×
×
×
×
GRACE
×
✓
∘
×
WISE
×
×
×
×
SERAC
✓
✓
×
×
MeLLo / PokeMQA
✓
✓
×
∘
DeepEdit
✓
✓
×
∘
Table 1: Design-level comparison with operational definitions. GF : inserting an edit requires no gradient step. Del : removing an edit restores the pre-edit state of the edit store exactly. Add : the representation passed to the model decomposes exactly into one additive term per stored edit. Con : candidate edits are checked against explicitly represented constraints before use. ✓ = satisfied by construction; ∘ = partially (see text); × = not satisfied.
Figure 1: Overview of TANSAR. The language-model state is mapped by the learned alignment A to a query q that addresses the explicit associative memory: a CMM of rank-one associations ( C=∑uβukuzu⊤ ) organised as a directed acyclic graph with a ground-rule store R . The retrieval engine diffuses over the active subgraph, prunes paths that violate R , and selects P∗ (Section 3.4 ). Only the sub-memory on P∗ is read out and injected (Eq. ( 8 )), and only when the calibrated transparency gate accepts. Offline edits and deletions (top right) change the memory without modifying model parameters.
Figure 2: How keys, values and queries are built. Keys (SKE): the text that addresses an association is embedded by a frozen sentence encoder, mean-centred, mapped to Rd by a fixed matrix R and normalised. Values : the scaled unembedding row of the edited target, a vector in the residual space of the language model. Queries : the normalised hidden state of the language model, mapped into the key space by the learned alignment A (Section 3.3 ). Keys and values enter the memory as rank-one terms; queries address it through q⊤ku .
Keys
n
μ
μ2
ΛK
mean ∥e∥2
pred. (b)
max ∥e∥
bound (a)
recall@1
isotropic
256
.136
.0312
2.2
0.25
0.25
0.58
0.84
1.000
1024
.148
.0312
3.9
1.00
1.00
1.10
2.13
1.000
4096
.172
.0313
8.9
4.00
4.00
2.19
6.20
1.000
semantic
256
.412
.0661
12.5
1.13
1.11
1.31
1.94
1.000
1024
.430
.0661
48.1
4.20
4.46
2.50
5.15
1.000
4096
.450
.0655
185.1
17.30
17.57
5.13
15.50
0.995
Table 2: Theorem 1 on correlated keys ( d=1024 , random unit values, β≡1 ). Mean ∥e∥2 : measured over all stored indices vs. the prediction (n−1)μ22 of Theorem 1 (b); the universal lower bound (d) is max(n/d−1,0) . Max ∥e∥ is compared with the largest value of the bound in (a). n0.5 is the capacity of Corollary 1 (ii) at ε=0.5 .
Figure 3: Mean squared crosstalk versus memory load for the three key models ( d=1024 ). Markers: measured; lines: the prediction (n−1)μ22 of Theorem 1 (b); dashed: the universal lower bound n/d−1 of Theorem 1 (d).
Query map
s=0
s=0.25
s=0.5
s=1.0
s=1.5
Random orthogonal projection
0.05 / 0.27
0.03 / 0.20
0.05 / 0.27
0.07 / 0.25
0.05 / 0.23
Self-keys (model states) + random projection
74.4 / 90.9
17.7 / 35.3
1.1 / 3.2
0.13 / 0.67
0.05 / 0.45
Learned InfoNCE map A (ours)
100 / 100
100 / 100
100 / 100
100 / 100
99.98 / 100
Entries are top-1 / top-5.
Table 3: Query–key retrieval accuracy (%) on held-out paraphrases across representation spaces in controlled isolation (E4). s : scale of the style/paraphrase nuisance component. Chance top-1 is 0.05% .
Accuracy ↑
Contradiction ↓
System
all
edited
all
edited
Abstention
Greedy-full (no graph, full readout)
1.3 ± 0.5
1.0 ± 0.7
2.9 ± 0.2
6.5 ± 0.9
0.0
Greedy-top k (no graph)
44.5 ± 2.6
25.5 ± 4.1
21.1 ± 0.9
48.1 ± 1.1
0.0
Validated + full injection
1.4 ± 0.7
1.0 ± 1.1
2.8 ± 0.3
6.5 ± 0.9
0.0
TANSAR, path injection
99.5 ± 0.1
98.8 ± 0.3
0.5 ± 0.1
1.2 ± 0.3
0.7 ± 0.0
TANSAR, hop injection
99.4 ± 0.2
98.6 ± 0.6
0.6 ± 0.2
1.4 ± 0.6
0.7 ± 0.1
Table 4: Multi-hop knowledge editing benchmark on structured fact graphs (E6; %, mean ± std over 3 seeds, 450 questions each). Contradiction is measured on generated answers, including those produced by the fallback branch. The TANSAR rows use λ=0.5 .
System
rent=0.5
0.7
0.85
0.95
Greedy-top k (no graph)
44.5 / 20.7
25.3 / 16.7
12.5 / 12.1
3.3 / 7.1
TANSAR, path injection ( λ=0.5 )
99.3 / 0.7
98.7 / 1.3
98.4 / 1.6
98.2 / 1.8
no diffusion
99.4 / 0.6
98.8 / 1.2
98.5 / 1.5
98.4 / 1.6
no constraint pruning
72.8 / 27.2
72.7 / 27.3
72.4 / 27.6
72.4 / 27.6
λ=0
100.0 / 0.0
99.5 / 0.5
98.8 / 1.2
98.4 / 1.6
λ=1
97.0 / 3.0
97.5 / 2.5
97.5 / 2.5
97.6 / 2.4
Table 5: E6 under increasing entity clustering rent (accuracy / contradiction in generated answers, %; mean over 3 seeds, 450 questions each; σq=0.6 ). The column rent=0.5 is the E6 setting re-run with independent query noise.
Accuracy ↑
Contradiction ↓
Protocol
Memory
all
edited
all
edited
stale kept
Hopfield, βhop=1
0.1 ± 0.1
0.0 ± 0.0
0.0 ± 0.0
0.0 ± 0.0
Hopfield, βhop=8
76.1 ± 1.1
45.0 ± 1.2
24.1 ± 0.9
55.6 ± 1.4
Hopfield, βhop=32
76.1 ± 1.9
45.2 ± 2.3
24.3 ± 2.3
55.8 ± 2.9
Hopfield, βhop=128
78.2 ± 2.3
50.0 ± 3.1
22.2 ± 2.4
51.0 ± 3.4
CMM, full readout
1.9 ± 1.0
1.0 ± 1.1
2.8 ± 0.5
6.5 ± 1.5
Table 6: Modern Hopfield retrieval on the E6 benchmark (E8; %, mean ± std over the 3 seeds of Table 4 , 450 questions each). No system in this table abstains.
Figure 4: Risk–coverage of the transparency gate (E5). Solid: selective risk on the test set; dashed: the Clopper–Pearson certificate computed on the calibration set; dotted: target risk αrisk=0.05 . The selected threshold is marked.
How many key-value associations can a d×d linear memory store? We show that the answer depends not only on the d2 degrees of freedom in the memory matrix, but also on the retrieval criterion. In an isotropic Gaussian model for the stored pairs, we show that top-1 retrieval, where every signal must beat its largest distractor, requires the logarithmic model-size scale d2≍nlogn. We prove that the correlation matrix memory construction, which stores associations by superposing key-target outer products, achieves this scale through a sharp phase transition, and that the same scaling is necessary for any linear memory. Thus the logarithm is the intrinsic extreme-value price of winner-take-all decoding. We next consider listwise retrieval, where the correct target need not be the unique top-scoring item but should remain among the strongest candidates. To formalize this regime, we propose the Tail-Average Margin (TAM), a convex upper-tail criterion that certifies inclusion of the correct target in a controlled candidate list. Under this listwise retrieval criterion, the capacity follows the quadratic scale d2≍n. At load n/d2→α, we develop an exact asymptotic theory for the TAM empirical-risk minimizer through a two-parameter scalar variational principle. The theory has a rich phenomenology: in the ridgeless limit it yields a closed-form critical load separating satisfiable and unsatisfiable phases, and it predicts the limiting laws of true scores, competitor scores, margins, and percentile profiles. Finally, a small-tail extrapolation further leads to the conjectural sharp top-1 threshold d2∼2nlogn.
Nicholas Barnfield, Juno Kim, Eshaan Nichani +2
Harvard University · University of California, Berkeley · Princeton University
Long chain-of-thought reasoning and agentic tool-calling produce traces spanning tens of thousands of tokens, yet Transformer KV caches grow linearly with sequence length, creating a memory bottleneck on commodity hardware. State-space models offer constant-memory recurrence but suffer a memory cliff: retrieval accuracy collapses once the gap between a stored fact and its query exceeds the effective horizon of the recurrent state. We introduce Echo, a KV-cache-free associative recall architecture built around Spectral Koopman Attention (SKA); a drop-in replacement for attention layers that augments SSM blocks with a closed-form dynamical operator whose sufficient statistics are accumulated in constant memory with no KV cache. Echo fits a spectral linear system to the key and value history via kernel ridge regression and retrieves through a learned power-iterated filter, all from O(r2) streaming state where r is a small projection rank. On the Multi-Query Associative Recall benchmark, a pure Mamba-2 SSM fails to exceed chance accuracy (∼3%) across all gap lengths and KV-pair counts, while at the 50M parameter scale SKA-augmented models achieve 100% retrieval accuracy on every configuration tested, including distractor gaps of 4,096 tokens with 32 KV pairs. Across five additional transfer benchmarks including needle-in-a-haystack, tool-trace, and multi-hop retrieval, SKA consistently outperforms both pure SSM and SSM+Attention hybrids while maintaining constant inference memory. Ablations confirm that the spectral operator, not the prefix masking strategy, drives the retrieval gain.
Anupama Sridhar, Alexander Johansen
California, USA · Stanford University Computer Science California, USA
We develop a geometry-based capacity theory for exact-key retrieval in compressed finite-feature Hebbian associative memory. For random or approximately isotropic values, retrieval interference separates into finite-feature noise, which decreases with feature dimension, and structural interference, which is determined by squared kernel overlap among stored keys and persists in the infinite-feature limit. This yields a fit-free prediction of retrieval quality, reveals a geometry-dependent capacity ceiling, and predicts the feature budget required for a target retrieval quality. When stored values are correlated, we show that retrieval depends jointly on the key kernel and value Gram matrix, and derive finite-feature approximations that account for this interaction. We validate the theory on synthetic, visual, and medical-image representations. Overall, the framework links representation geometry directly to memory capacity and distinguishes when performance can be improved by increasing the feature budget and when the representation itself must be changed. Across these settings, the predicted retrieval curves closely match empirical behavior and correctly identify changes in the preferred memory design.
Department of Biomedical Engineering, Schulich School of Engineering, University of Calgary, and the Ron and Rene Ward Centre for Healthy Brain Aging Research, Hotchkiss Brain Institute, University of Calgary