BRACE: Differential Privacy for Dense Associative Memory with LSR Energy

1 Introduction

• Privacy for DAM retrieval dynamics remains largely unexplored, despite DAM’s connections to attention and memory-augmented AI.The paper highlights sensitive-memory applications such as medical record retrieval and personalized AI systems.Source: §1 · p. 2
• LSR-DAM’s compact support localizes retrieval but creates hard-boundary membership switches that can cause discontinuous, cumulative errors under privacy perturbations.The paper argues that smooth-perturbation DP approaches cannot be directly applied to this setting.Source: §1 · p. 3
• BRACE identifies memories whose membership changes under noisy retrieval and adaptively corrects them before calibrated DP noise is added.The method is presented as the first DP framework specifically designed for LSR-DAM.Source: §1 · p. 3
• The paper establishes privacy and minimax-optimal retrieval error guarantees, and develops CLT-based uncertainty quantification for private retrieval.The framework characterizes privacy-induced uncertainty in energy-based AI systems.Source: §1 · pp. 3–4
• The authors position private LSR-DAM as a step toward secure memory-augmented AI for sensitive and personalized information.The claimed application scope includes memory-augmented architectures.Source: §1 · p. 4

2 Preliminaries and Problem Setup

• DAM retrieves patterns through an energy-based iterative update, with LSE energy providing a smooth, globally weighted formulation.LSE-DAM is described as the dominant formulation and as closely connected to Transformer attention.Source: §2 · p. 4
• LSR replaces exponential interactions with compactly supported ones, averaging only memories within radius r.This local retrieval has bounded movement and finite fixed-center sensitivity, but its boundary discontinuity motivates BRACE.Source: §2 · pp. 4–5
• The central DP setting releases the mechanism’s retrieval trajectory while assessing privacy under neighboring memory banks.The mechanism accesses the full bank and releases only its output trajectory.Source: §2 · p. 5

3.1 Retrieval Setup

• Each clean retrieval step moves at most r, so after t steps the trajectory remains within distance tr of its initial query.The clean trajectory iterates the bank-dependent retrieval map from the initial query.Source: §3.1 · p. 6

3.2 Privacy-Induced Boundary Instability

• A small state change can alter the active memory set and cause an order-r retrieval jump, creating cumulative error under the naive private recursion.Privacy calibration of the noise alone does not control the boundary-induced term, which can remain nonzero for arbitrarily small preceding state error.Source: §3.2 · p. 6
• At a unique boundary record, an arbitrarily small state perturbation can remove that record from the active set, making the retrieval map non-locally Lipschitz.The proposition’s boundary-jump argument shows that the update difference can converge to a nonzero value even as the state perturbation vanishes.Source: §3.2 · pp. 6–7

4 Proposed Method: BRACE

• The method constructs a sensitivity upper bound by recursively propagating replacement-bank membership, activation, and projection branches, retaining feasible branches.The bound is used to calibrate the retrieval query’s privacy noise.Source: §4 · pp. 8–9
• BRACE forms a correction from the clean and released-query updates, activates it when its norm exceeds a threshold, and projects the corrected query before noise addition.The selected algorithm computes a smooth sensitivity certificate, adds calibrated noise, and releases the resulting iterate.Source: §4 · pp. 7–10
• A larger activation threshold κ means fewer corrections and lower search complexity, but permits larger residual error.The selected correction rule also bounds cumulative correction displacement in terms of κ, T, and r.Source: §4 · pp. 9–10
• The smooth upper bound on local sensitivity yields an effective sensitivity count bmt = 2r/∆t, which is not the active-set size.The effective count summarizes BRACE’s sensitivity scale.Source: §4 · p. 10

5.1 DP Guarantee of BRACE

• A valid per-step noise calibration together with a composition accountant yields an (ε, δ)-DP BRACE trajectory.The guarantee is conditional on each fixed released history.Source: §5.1 · p. 11

5.2 Terminal and Maximum-Path Minimax Risk

• For fixed T, BRACE attains the optimal r^2 worst-case rate for terminal and full-trajectory error; in the long-chain regime, its horizon dependence is also optimal at T^2r^2.The output projection gives a bound uniform in memory size and dimension.Source: §5.2 · pp. 11–12

5.3 Trajectory Central Limit Theorems for BRACE

• The trajectory CLT gives a joint limit across iterations, capturing dependence among retrieval errors, while the minimax result controls finite-sample error magnitude.Together, these results characterize both error magnitude and asymptotic uncertainty.Source: §5.3 · pp. 13–14
• Privacy noise contributes to the first-order trajectory distribution in the transition regime where the effective count bmn,t is of order √n.The CLT conditions are local asymptotic conditions and do not require global smoothness of the retrieval map.Source: §5.3 · pp. 13–15

6.1 Synthetic Data: Boundary-Induced Mode Switching

• A perturbation of norm 0.01443 changes 11 gate memberships at update 2, and Naive DAM's per-coordinate squared error reaches 1.00503 at update 5 versus BRACE's final error of 0.01222.Figure 1 shows the retrieval trajectories and per-coordinate squared error relative to noiseless DAM.Source: §6.1 · p. 16, Figure 1 · p. 16

6.2 MNIST retrieval with strong query corruption

• 1.582963 is BRACE's minimum prediction MSE at β = 0.025119, T = 3, and ε = 64, versus 8.759678 for the corrupted input and 1.582947 for noiseless DAM.This is an 81.9% reduction from the initial prediction error; Naive DAM attains the same measured minimum.Source: Figure 2 · p. 17, §6.2 · p. 18
• At small β the gate can contain most or all memories, while at large β it is often empty; intermediate β can produce nonmonotone fidelity as smaller active counts increase sensitivity.The handwritten reconstructions show that low feature-space MSE does not necessarily recover the original individual digit.Source: §6.2 · p. 19

7 Conclusion and Limitation

• The paper establishes formal privacy guarantees, utility bounds, and minimax optimality results for privacy-preserving LSR-DAM retrieval, and reports better prediction performance than competing approaches.The conclusion says the experiments support the theoretical findings and the practical benefits of local retrieval.Source: §7 · p. 19
• Retrieval benefits may diminish when local neighborhoods are intrinsically sparse, and sensitivity estimation adds computation when obtaining tighter data-dependent privacy guarantees.The paper identifies data geometry and retrieval-scale choice as determinants of practical performance.Source: §7 · p. 19

AI use statement

• The authors report using generative AI for proof writing, code debugging, literature search, and language editing, with authors reviewing the assisted work.They report that two authors verified and tested LLM-generated code and that authors checked LLM-assisted proofs line by line.Source: AI use statement · pp. 20–21

C Proof of Theorem 2

• Conditional differential privacy for each step yields a privacy guarantee for the released trajectory through backward integration over the transcript.The proof applies conditional DP to the preimage under public projection and treats all ordered neighboring datasets.Source: C Proof of Theorem 2 · pp. 31–32

C.1 Exact deficit for the released trajectory

• The mechanism is (ε, δ)-DP exactly when the hockey-stick deficit of the transcript is at most δ, with the reference measure accounting for projection-boundary mass.The proof forms transcript densities and takes their positive set to obtain the criterion.Source: §C.1 · pp. 32–33

C.2 Gaussian calibration in Step 6

• Projection preserves the divergence bound because the projected likelihood ratio is a conditional mean of the input ratio, to which Jensen’s inequality applies.The proof then uses composition and backward integration to bound transcript divergence.Source: §C.2 · pp. 33, 35

• When background records lie outside the initial gate, retrieval stays at q without a trigger, and the movement bound excludes the remote point through time T.This construction separates the no-trigger trajectory from the remote point used in the lower-bound argument.Source: D Proof of Theorem 3 · p. 38
• The rare-record construction conditions on one trigger and tracks iterates between successive points on an event E, using induction for later steps.The proof notes that the second-line condition requires T ≥ 3.Source: D Proof of Theorem 3 · pp. 38–39
• The lower-bound conclusion has constants independent of n, d, and r, and the proof states that a terminal-loss lower bound also applies to maximum-path loss.The proof derives this conclusion by combining its referenced bounds.Source: D Proof of Theorem 3 · pp. 37, 41

E Proof of Theorem 4

• Under the stated assumption and fixed T, Slutsky’s theorem gives the same limit for the full trajectory Y_n,1:T.Source: E Proof of Theorem 4 · pp. 41–42

F Proof of Theorem 5

• In the proof, Yn,<t denotes (q, Yn,1, …, Yn,t−1), and the stated Step 6 relation is Δn,t = 2r/bmn,t.Source: F Proof of Theorem 5 · p. 42
• When ℓ_t = 0, the scaled privacy perturbation √n ξ_n,t converges in probability to zero; the proof also invokes Lévy’s theorem after taking expectations.Source: F Proof of Theorem 5 · p. 42

G Proof of Corollary 1

• Gate differences are confined to annular shells whose volumes are controlled by bounded density near compact boundary spheres; bounded VC-type classes provide uniform empirical control.Source: G Proof of Corollary 1 · pp. 43–44
• For fixed T, induction keeps the centers in Us with probability tending to one, and convergence follows from the fixed-horizon argument.Source: G Proof of Corollary 1 · pp. 45, 47
• The boundary correction satisfies ξn,t = OP(n^-1); with probability tending to one, Hn,t = 0 and Qn,t = ΦDn(Yn,t−1).Source: G Proof of Corollary 1 · p. 46