BRACE gives LSR dense associative memory differentially private retrieval, cutting MNIST prediction error from 0.061 to 0.011

The paper formulates the first differential privacy framework for LSR-DAM and identifies boundary instability as its central difficulty: the LSR update averages only memories within a radius, and the hard boundary lets a small state perturbation switch the active set, producing an order-of-radius jump that accumulates over iterations. Prior differential privacy work largely targets sample means or smooth perturbation analysis for LSE energy, whereas the LSR update map is not locally Lipschitz at the boundary, so those approaches do not directly apply; Proposition 1 formalizes this jump. Proposition 1 gives a limit expression for the boundary jump showing the update map is not locally Lipschitz at the boundary; the synthetic experiment shows the first perturbation has small norm yet at update 2 changes 11 gate memberships (six leave, five enter) while the gate size changes only slightly.

BRACE separates privacy perturbation from retrieval instability by correcting before noising: it computes a correction via a publicly specified measurable rule, activates it by a threshold, projects the corrected query, then adds calibrated noise and releases. This preserves the compact-support dynamics of LSR-DAM while providing a data-dependent sensitivity certificate through a smooth sensitivity upper bound and a CorrectedCountSearch branch search, rather than using the active-set count directly. The algorithm specifies six steps and a sensitivity construction; Appendix B proves the branch-search supremum equals the complete-query local sensitivity and shows branch complexity grows with the number of activated corrections rather than branching over the full bank at every iteration.

The paper proves BRACE is centrally differentially private and achieves minimax-optimal terminal and full-trajectory retrieval error rates in both fixed and growing horizons, with dimension-independent rates and optimal dependence on inverse temperature and, in the growing-horizon regime, the retrieval horizon. The results cover both terminal risk and the stronger maximum-path risk, showing that releasing and controlling the whole path does not worsen the minimax order; in the growing-horizon regime matching upper and lower bounds give optimal dependence on the retrieval horizon. Theorem 2 shows any conditionally calibrated noise law with a valid composition accountant yields an -DP BRACE trajectory; Theorem 3 gives matching upper and lower bounds for fixed horizon and for the growing-horizon region (condition 3), with comparison constants possibly depending on inverse temperature but independent of dimension.

The paper establishes trajectory central limit theorems that characterize the asymptotic distribution of private retrieval and the additional variability introduced by privacy, and determines at what order of the effective count privacy noise contributes at the first-order scale. The limit is a joint distribution for the entire released trajectory rather than only the terminal state, so it captures dependence of retrieval errors across iterations; the error is decomposed into a residual correction term and a privacy-noise term. Theorem 4 gives the joint limit under first-order BRACE conditions; Theorem 5 shows that an effective count of a certain order is the transition regime where privacy noise moves from asymptotically negligible to first-order contribution at the root- scale, and gives the non-tight case.

The framework targets iterative retrieval in LSR-DAM under the setting where the initial query, retrieval radius, and horizon are public, the mechanism accesses the full memory bank, and only the trajectory is released. It enables provable privacy and error guarantees for private retrieval in sensitive-memory settings such as medical record retrieval, personalized LLM memory modules, and user-specific assistants, and lets practitioners use the central limit theorems to quantify privacy-induced variability. The synthetic experiment illustrates boundary instability and the need for correction, while the MNIST experiment evaluates retrieval accuracy on two PCA coordinates of a frozen VAE and provides reproducible code, data splits, and noise-repetition settings.

How to choose the activation threshold and smoothing parameters across different data geometries remains an open question for practitioners to weigh; the paper notes sensitivity estimation adds computation and that future work may improve computational efficiency and adaptive choice of the retrieval scale. The MNIST experiment shows low feature-space MSE does not necessarily imply recovery of the original individual digit, so the relation between reconstruction quality and retrieval accuracy deserves further observation. In addition, experiments use two PCA coordinates of a frozen VAE, so transfer to higher-dimensional or sparser-neighborhood settings needs more evidence.