Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness
Madhava Gaikwad · 2026
Read Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness by Madhava Gaikwad (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12811.txt.
Introduction
Madhava Gaikwad gives finite-size guarantees for dense associative memory retrieval. Dense associative memory extends Hopfield nets with higher-order interactions. Past work studies infinite size with random patterns, giving no finite rates. Under separation and bounded interference at high load, retrieval converges fast. Convergence time is logarithmic once the path enters the basin. Attack bounds state how many corrupted bits each sweep tolerates. Capacity scales like N to the n minus one, up to polylog factors, with pure Nash equilibria from a potential-game view.
Catalog record
| CREATOR | Madhava Gaikwad |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57544 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.12811
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness Madhava Gaikwad Abstract Dense Associative Memory (DAM) generalizes Hopfield networks through higher-order interactions and achieves storage capacity that scales as O ( N n − 1 ) O(N^{n-1}) under suitable pattern separation conditions. Existing dynamical analyses primarily study the thermodynamic limit N → ∞ N\to\infty with randomly sampled patterns and therefore do not provide finite-size guarantees or explicit convergence rates. We develop an algorithmic analysis of DAM retrieval dynamics that yields finite- N N guarantees under explicit, verifiable pattern conditions. Under a separation assumption and a bounded-interference condition at high loading, we prove geometric convergence of asynchronous retrieval dynamics, which implies O ( log N ) O(\log N) convergence time once the trajectory enters the basin of attraction. We further establish adversarial robustness bounds expressed through an explicit margin condition that quantifies the number of corrupted bits tolerable per sweep, and derive capacity guarantees that scale as Θ ( N n − 1 ) \Theta(N^{n-1}) up to polylogarithmic factors in the worst case, while recovering the classical Θ ( N n − 1 ) \Theta(N^{n-1}) scaling for random pattern ensembles. Finally, we show that DAM retrieval dynamics admit a potential-game interpretation that ensures convergence to pure Nash equilibria under asynchronous updates. Complete proofs are provided in the appendices, together with preliminary experiments that illustrate the predicted convergence, robustness, and capacity scaling behavior. 1 Introduction Dense Associative Memory (DAM) stores p binary patterns \{\bm{\xi}^{\mu}\}_{\mu=1}^{p}\subset\{-1,+1\}^{N} in an N -neuron network through higher-order interactions Krotov & Hopfield 2016 . For interaction order n\geq 2 , the energy function is E(\bm{x})=-\frac{1}{N^{n-1}}\sum_{\mu=1}^{p}\left(\sum_{i=1}^{N}\xi_{i}^{\mu}x_{i}\right)^{n}, (1) with local field h_{i}(\bm{x})=\partial(-E)/\partial x_{i} and asynchronous update rule x_{i}\leftarrow\operatorname{sign}(h_{i}(\bm{x})). Classical statistical-physics analyses of associative memory models focus primarily on asymptotic behavior in the thermodynamic limit and typically assume randomly sampled patterns. Recent work by Mimura et al. Mimura et al. 2025 provides an asymptotically exact dynamical analysis of DAM using generating functional analysis (GFA). Their results apply to the regime N\to\infty with random i.i.d. patterns and show that for interaction orders n\geq 3 the effective noise variance becomes independent of the overlap, which mitigates a key instability present in classical Hopfield networks ( n=2 ). However, this framework does not provide explicit finite- N convergence guarantees, does not address adversarial or structured pattern sets, and does not yield explicit retrieval-time bounds. This work develops an algorithmic analysis that complements the statistical-physics perspective by focusing on finite systems and explicit performance guarantees. We introduce explicit separation and bounded-interference assumptions on the stored patterns that can be verified directly or shown to hold with high probability for random ensembles. Under these conditions we obtain finite-size convergence guarantees, robustness bounds under adversarial corruption, and explicit capacity guarantees that recover the classical N^{n-1} scaling up to polylogarithmic factors in the worst case. Appendix A contains complete proofs of the main results, including the strengthened interference condition required near capacity loading, the potential-game characterization of retrieval dynamics, and verification that random pattern ensembles satisfy the assumptions with high probability. Appendix B reports preliminary experiments on a cubic ( n=3 ) DAM that illustrate convergence behavior, basin-of-attraction structure, adversarial robustness thresholds, capacity scaling, comparisons between synchronous and asynchronous updates, and retrieval performance on binarized MNIST and CIFAR-10 data. 2 Related Work The foundational work of Hopfield 1982 established recurrent neural networks as physical systems with emergent computational abilities, a perspective deeply analyzed using spin-glass theory Amit et al. 1985 , Amit 1989 . The theoretical storage capacity of these classical models was rigorously quantified in seminal works Newman 1988 , Gardner 1987 , McEliece et al. 1987 , Abbott & Arian 1987 . A major leap forward was the introduction of Dense Associative Memory (DAM) models Krotov & Hopfield 2016 , which achieve exponential storage capacity Lucibello & Mézard 2024 and have been shown to be practically powerful in deep learning architectures Ramsauer et al. 2021 , Hoover et al. 2023 . Recent theoretical advances have further explored the dynamical properties Mimura et al. 2025 , saddle point hierarchies Thériault & Tantari 2026 , and biological plausibility of these modern networks Kafraj et al. 2026 . This resurgence has also led to novel applications in analog circuits Bacvanski et al. 2025 , optical computing Musa et al. 2026 , and as a framework for understanding Transformer architectures Masumura & Taki 2025 . The field’s enduring relevance is underscored by recent surveys and tutorials at major AI conferences Krotov et al. 2025 , Kempe et al. 2024 and its connection to broader topics in optimization Boyd & Vandenberghe 2004 , Shalev-Shwartz & Ben-David 2014 , Goles & Martínez 1985 , game theory Monderer & Shapley 1996 , Hart & Mas-Colell 2003 , and robust machine learning Cohen et al. 2019 , Ge et al. 2015 , Du et al. 2019 . 3 Problem Formulation 3.1 Model and Updates We analyze asynchronous updates , where at each iteration a single neuron is selected uniformly at random and updated according to x_{i}^{(t+1)}=\operatorname{sign}\!\left(h_{i}(\bm{x}^{(t)})\right)\quad\text{for randomly selected }i. (2) Asynchronous updates ensure monotone improvement of the energy function and avoid oscillatory behaviors that may arise under synchronous updates in Hopfield-type networks Goles & Martínez 1985 . We measure time in full sweeps , where one sweep corresponds to N consecutive asynchronous updates so that, in expectation, each neuron is updated once. For a stored pattern \bm{\xi}^{\nu} , the overlap of a state \bm{x} with the target pattern is m^{\nu}(\bm{x})=\frac{1}{N}\sum_{i=1}^{N}\xi_{i}^{\nu}x_{i}. 3.2 Pattern Separation To obtain finite-size guarantees, we impose a separation condition that characterizes the basin of attraction of a stored pattern. Assumption 1 (Pattern Separation) . Fix a target pattern \nu . There exist constants \gamma>0 and \beta<\gamma such that for all states \bm{x} satisfying m^{\nu}(\bm{x})\geq\gamma, the interference from all non-target patterns is bounded as \max_{\mu\neq\nu}\left|\frac{1}{N}\sum_{i=1}^{N}\xi_{i}^{\mu}x_{i}\right|\leq\beta. This condition requires that once the trajectory enters a basin of attraction characterized by overlap at least \gamma , the contribution of every competing pattern remains strictly smaller than that of the target pattern. For random i.i.d. patterns, the condition holds with high probability when the loading satisfies p=o(N^{n-1}) , while the subsequent analysis applies to any deterministic pattern set that satisfies the assumption. 4 Main Results Theorem 2 (Convergence Rate) . Suppose the stored patterns satisfy Assumption 1 with \gamma>\beta , and let the loading satisfy p\leq\frac{N^{n-1}}{2n(n-1)} . Then asynchronous DAM retrieval initialized at any state with m^{\nu}(\bm{x}^{(0)})\geq\gamma converges to the target pattern in T=O\!\left(\frac{1}{\alpha}\log N\right) full sweeps, where \alpha=\frac{1}{n}-\frac{2(n-1)p}{N^{n-1}}>0. Theorem 3 (Adversarial Robustness) . Under the conditions of Theorem 2 , retrieval succeeds despite adversarial corruption of up to \rho N bits per full sweep provided \rho<\frac{\alpha}{2}. In particular, using the explicit expression for \alpha yields the bound \rho<\frac{1}{2}\left(\frac{1}{n}-\frac{2(n-1)p}{N^{n-1}}\right). Theorem 4 (Capacity Scaling) . Assume the pattern set satisfies Assumption 1 . Then DAM retrieval guarantees hold for at least p\geq\frac{N^{n-1}}{4n^{2}(n-1)^{2}} stored patterns, while retrieval may fail when the loading becomes p=\Omega(N^{n-1}) . Thus the achievable storage capacity scales as \Theta(N^{n-1}) up to constant or polylogarithmic factors depending on the pattern ensemble. Theorem 5 (Game-Theoretic Characterization) . DAM asynchronous dynamics coincide with best-response dynamics in an exact potential game with • players: neurons i=1,\ldots,N , • actions: x_{i}\in\{-1,+1\} ,