Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness

Madhava Gaikwad

cs.LGApr 14, 2026

Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness

Authors: Madhava Gaikwad

Organizations: Independent Researcher

Abstract

Dense Associative Memory (DAM) generalizes Hopfield networks through higher-order interactions and achieves storage capacity that scales as $O(N^{n-1})$ under suitable pattern separation conditions. Existing dynamical analyses primarily study the thermodynamic limit $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$ 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)$ 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})$ up to polylogarithmic factors in the worst case, while recovering the classical $Θ(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.

Figures & tables

Property	Mimura et al. (2025)	This work
System size	$N\to\infty$ (thermodynamic limit)	Finite $N$
Pattern distribution	Random i.i.d.	Arbitrary (worst-case)
Convergence guarantee	Asymptotic dynamics	$O(\log N)$ full sweeps (basin regime)
Robustness analysis	Typical noise variance	Explicit adversarial tolerance $\rho^{*}$
Capacity result	Ensemble-averaged threshold ( $\alpha^{\prime}_{c,3}\approx 0.266$ )	Finite-size scaling bounds with constants
Finite-size effects	Qualitative discussion	Explicit quantitative bounds

Table 1: Statistical-physics vs. algorithmic analysis of DAM

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

$\alpha$	$N$	$p$	$\beta$	Sweeps	95% CI	Succ.
0.03	200	1200	0.360	1.0	[1.0, 1.1]	100%
0.03	300	2700	0.307	1.0	[1.0, 1.1]	100%
0.03	400	4800	0.290	1.0	[1.0, 1.0]	100%
0.03	500	7500	0.244	1.0	[1.0, 1.0]	100%
0.03	700	14700	0.237	1.0	[1.0, 1.0]	100%
0.05	200	2000	0.350	1.6	[1.4, 1.7]	100%

Appendix

Table 2: Convergence at 15% corruption (

m_{0}=0.70

). Sweeps and 95% bootstrap CI over 60 trials.

$\alpha$	$N$	$p$	$\beta$	Sweeps	95% CI	Succ.
0.01	200	400	0.320	3.4	[1.4, 6.4]	97%
0.01	300	900	0.260	1.3	[1.2, 1.4]	100%
0.01	400	1600	0.255	1.4	[1.3, 1.5]	100%
0.01	600	3600	0.227	1.3	[1.2, 1.4]	100%
0.01	800	6400	0.195	1.2	[1.1, 1.4]	100%
0.02	200	800	0.310	10.0	[5.3, 15.0]	87%

Appendix

Table 3: Convergence at 30% corruption (

m_{0}=0.40

Corruption	$m_{0}$	$\alpha=0.005$	$\alpha=0.01$	$\alpha=0.02$
33%	$+0.34$	99%	98%	68%
34%	$+0.32$	99%	92%	56%
35%	$+0.30$	94%	86%	49%
36%	$+0.28$	94%	81%	28%
37%	$+0.26$	88%	68%	21%
38%	$+0.24$	81%	48%	11%

Appendix

Table 4: Basin of attraction boundary. Each cell shows the average success rate across

N\in\{200,400,600\}

with 60 trials per configuration. The boundary (bold) marks where success drops below 50%. Directly comparable to the theoretical basin in Mimura et al. (2025) , Fig. 2.

$N$	$p$	$\beta$	$\rho^{*}_{\mathrm{asymp}}$	$\rho^{*}_{\beta}$	$\hat{\rho}^{*}_{\mathrm{strong}}$	$\hat{\rho}^{*}_{\mathrm{weak}}$
500	1250	0.224	0.285	0.076	0.160	0.160
500	2500	0.228	0.270	0.072	0.140	0.140
500	5000	0.236	0.240	0.064	0.100	0.100
1000	5000	0.168	0.285	0.132	0.180	0.180

Appendix

Table 5: Adversarial threshold: predicted vs. empirical.

\hat{\rho}^{*}

is the empirical threshold at 50% success (80 trials per

\rho

value).

$\rho$	Strong Adv.	Weak Adv.
0.13	1.00	0.96
0.14	0.89	0.96
0.15	0.84	0.71
0.16	0.42	0.45
0.17	0.11	0.19
0.18	0.05	0.01

Appendix

Table 6: Full adversarial

\rho

-curve for

N=500

p=1250

\alpha=0.005

\gamma=0.6

. Only the transition region is shown; success is 100% for

\rho\leq 0.12

and 0% for

\rho\geq 0.19

$N$	$p_{\max}$	$N^{n-1}$	$\alpha_{\mathrm{eff}}$
100	450	10 000	0.045
150	1 200	22 500	0.053
200	2 163	40 000	0.054
300	5 140	90 000	0.057
400	10 369	160 000	0.065
500	16 915	250 000	0.068

Appendix

Table 7: Capacity scaling.

p_{\max}

is determined by binary search at 95% success threshold with 40 trials.

$\alpha^{\prime}_{3}$	$m_{0}$	$p$	Async	$T_{a}$	Par.	$T_{p}$
0.10	0.3	8333	0.04	7.5	0.00	–
0.10	0.5	8333	1.00	2.1	1.00	3.6
0.10	0.7	8333	1.00	1.0	1.00	1.8
0.15	0.3	12499	0.02	16.0	0.00	–
0.15	0.5	12499	0.74	5.4	0.32	8.4
0.15	0.7	12499	1.00	1.5	1.00	2.2

Appendix

Table 8: Parallel vs. asynchronous updates at

N=500

. “Async” and “Par.” denote success rates;

T_{a}

T_{p}

denote mean sweeps to convergence (successful trials only; “–” if no successes).

$\alpha$	$p$	$\beta_{\mathrm{rand}}$	Rate rand	$\beta_{\mathrm{adv}}$	Rate adv	Gap
0.002	500	0.216	1.00	0.376	0.98	0.02
0.004	1000	0.220	1.00	0.352	0.74	0.26
0.006	1500	0.256	1.00	0.364	0.60	0.40
0.008	2000	0.232	1.00	0.368	0.02	0.98
0.010	2500	0.240	1.00	0.364	0.00	1.00
0.015	3750	0.248	1.00	0.392	0.00	1.00

Appendix

Table 9: Random vs. adversarial (correlated) patterns at

N=500

, 20% initial corruption. “Rate” is the fraction of 50 trials converging within 60 sweeps; “Gap” = Rate rand

-

Rate adv .

			Success rate at corruption level
Dataset	$p$	$\beta$	10%	20%	30%	35%	40%	45%
MNIST	10	1.000	1.00	1.00	1.00	1.00	1.00	1.00
MNIST	50	1.000	1.00	1.00	1.00	1.00	1.00	1.00
MNIST	100	1.000	1.00	1.00	1.00	1.00	1.00	1.00
MNIST	200	1.000	1.00	1.00	1.00	1.00	1.00	1.00
MNIST	500	1.000	1.00	1.00	1.00	1.00	1.00	1.00

Appendix

Table 10: Retrieval on binarized MNIST and CIFAR-10. Success rate over 40 trials at selected noise levels. Patterns are selected with diversity across classes.

\beta

is the measured maximum inter-pattern overlap.

Explore similar work

Sep 15, 2026

Bias-Induced Crossover in Absolute Capacity of Dense Associative Memory

The absolute capacity of dense associative memory has mainly been analyzed for unbiased patterns. Here we examine the effect of bias in centered binary patterns under the Krotov-Hopfield single-site criterion

P_{\mathrm{error}}=1/N

, where

P_{\mathrm{error}}

is the probability that a single-site flip lowers the energy of a stored pattern and

N

is the number of neurons. Each pattern component takes

1-q

with probability

q

and

-q

otherwise, where

0<q\le1/2

. For polynomial interactions of order

n

, a signal-to-noise analysis gives an absolute capacity of order

N^{n-1}/\ln N

q=1/2

. For fixed

q<1/2

, however, the capacity is

O(N^{n/2})

for even

n\ge4

and

O(N^{(n+1)/2})

for odd

n\ge5

. For

n=3

, both the unbiased and fixed-bias capacities remain

O(N^2/\ln N)

. For

n\ge4

, these different asymptotic forms imply a nonuniform large-

N

limit near

q=1/2

. Asymptotic matching predicts a bias-induced crossover in the region

1-2q=O(\ln N/N^{\lfloor n/2\rfloor-1})

. The crossover originates from a bias-dependent crosstalk mean that reduces the stability of sites carrying the more frequent value

-q

. Computer simulations are compared with the finite-size conditioned-Gaussian predictions. An activity-dependent control potential that cancels the conditional crosstalk mean restores the

N^{n-1}/\ln N

capacity for fixed

0<q<1/2

within the conditioned-Gaussian approximation.

Yuto Sakurai, Takeaki Shimokawa, Kazunori Iwata +1

Graduate School of Information Sciences, Hiroshima City University, 3-4-1 Ohtsuka-higashi, Asaminami-ku, Hiroshima 731-3194, Japan · RIKEN Center for Advanced Intelligence Project and The University of Tokyo

Hopfield Networks Associative Memory

Ask PDF

Jul 21, 2026

Free energy landscape of Dense Associative Memory

Using large deviations theory, we solve and obtain a general expression for the free energy functional for a broad class of associative memories, including dense associative memories. We illustrate the method by reproducing classical results for the Hopfield model. For a finite number of patterns, we derive the temperature-dependent free energy functional for dense associative memories featuring polynomial interactions and Log-Sum-Exponential (LSE) activation. We also evaluate the disorder-averaged ground-state energy of these systems in the extensive limit. Our analytical framework reveals how memory retrieval depends on the initial state in higher-order dense networks, and gives the exact full-retrieval threshold for the LSE model. This method provides a systematic procedure for analyzing diverse, complex architectures in associative memory.

Sumedha, Abhishek Singh

School of Physical Sciences, National Institute of Science Education and Research, Bhubaneswar, P.O. Jatni, 752050, India · 2Homi Bhabha National Institute, Training School Complex, Anushakti Nagar 400094, India

Free Energy Calculation Neural Network Memorization Hopfield Networks Associative Memory

Ask PDF

Mar 27, 2026

On associative neural networks for sparse patterns with huge capacities

Generalized Hopfield models with higher-order or exponential interaction terms are known to have substantially larger storage capacities than the classical quadratic model. On the other hand, associative memories for sparse patterns, such as the Willshaw and Amari models, already exhibit enhanced storage capacities in the sparse regime. In this paper we combine these two mechanisms. We introduce higher-order versions of sparse associative memory models and study their storage capacities in the sense of fixed-pattern stability. For the Amari and Willshaw models with fixed interaction order

n

, we obtain storage scales of order

\frac{N^n}{(\log N)^n}

. When the interaction order grows logarithmically with the number of neurons, the resulting storage scale becomes super-polynomial. We also study higher-order interactions in the block-structured Gripon--Berrou architecture, where the natural storage scale is of order

c^n

. Our results show that the capacity increase caused by higher-order interactions persists in the sparse setting, while the precise storage scale depends on the underlying architecture.

Matthias Löwe, Franck Vermet

Associative Memory Hopfield Networks

Ask PDF