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

Bias-Induced Crossover in Absolute Capacity of Dense Associative Memory
Sep 15, 2026Yuto Sakurai, Takeaki Shimokawa, Kazunori Iwata +1Hopfield Networks Associative Memory
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
Free energy landscape of Dense Associative Memory
Jul 21, 2026Sumedha, Abhishek SinghFree Energy Calculation Neural Network Memorization
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
On associative neural networks for sparse patterns with huge capacities
Mar 27, 2026Matthias Löwe, Franck VermetAssociative Memory Hopfield Networks

Sep 15, 2026J/K move · Enter open · S save

Bias-Induced Crossover in Absolute Capacity of Dense Associative Memory

Yuto Sakurai, Takeaki Shimokawa, Kazunori Iwata, Kazushi Mimura

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Bias-Induced Crossover in Absolute Capacity of Dense Associative Memory

Free energy landscape of Dense Associative Memory

On associative neural networks for sparse patterns with huge capacities