Sample-efficient learning with Dense Associative Memories

Andrew Lucas; Dmitry Krotov

cs.LGOct 19, 2026

Sample-efficient learning with Dense Associative Memories

Authors: Andrew Lucas, Dmitry Krotov

Organizations: Department of Physics and Center for Theory of Quantum Matter, University of Colorado, Boulder, CO 80309, USA · Dynamical Mind, Cambridge, MA 02141, USA

Abstract

We analytically study the evolution of the energy function of Dense Associative Memories (DenseAMs) as they train on randomly sampled codewords of random expander low-density parity-check codes (a.k.a. solutions of random XORSAT problems). We identify two distinct regimes and a transition between them, reminiscent of grokking in neural networks. A regime of small training set size is where the model memorizes a few training examples but cannot discover the underlying rules of the entire codeword dictionary generative process. The opposite regime, corresponding to a larger training set size, is where the model has uncovered the sparse constraints that generated the entire data set after seeing only polynomially many patterns. We also design a novel class of DenseAMs with a thresholding learning rule, and show that any amount of thresholding enables the model to perform simplified sparse Hamiltonian learning, which exponentially reduces the number of training examples needed to learn the true underlying data set. In this regime, the model learns how to discover $\exp[\mathrm{O}(n)]$ solutions from only $\mathrm{O}(\log n)$ training samples, which is asymptotically optimal for any learning algorithm. When training on codewords of certain random codes, the model can even learn the underlying code when a small O(1) fraction of bits are latent variables. These latent variables are not shown to the model during learning, but will be discovered by sparsifying observed higher-order correlations. For certain random codes, we show that a simple and conservative algorithm learns a minimal latent representation for the data set. This provides a transparent, physics-motivated, and analytically tractable toy model for how deep latent representations emerge in an associative memory training.

Figures & tables

Figure 1: Illustration of a local patch of a Tanner graph of a random code with

(\Delta_{\mathrm{B}},\Delta_{\mathrm{C}})=(3,4)

. Bits

i

are depicted as black circles; checks

\alpha

are depicted as orange squares. The number of small cycles in a Tanner graph is extremely small, so the graph will typically look locally tree-like.

Figure 2:

\widehat{k}

as a function of

P

when training the

a\rightarrow 1

TDenseAM on random bitstrings of length

n=100

. The bubble plot depicts the probability of seeing a given value of

\widehat{k}

at each

P

when choosing a random sequence of training data. Left:

m=2

. Right:

m=4

, where ( 21 ) is clearly visible at small

P

Figure 3: The memorization-generalization transition as a function of

P

, after initializing TDenseAM at unseen codewords. The probability distributions of

f_{\text{flip}}

and

f_{\text{new}}

are depicted as bubble plots. Training is done on a (3,4) code (

n=80

k=20

). Left:

a=0.2

. Right:

a\rightarrow 1

Figure 4: Illustration of a local patch of a Tanner graph of a random code with observed (black) and latent (white) bits. The latent TDenseAM learner will detect

h_{1}

since it has an observable 3-shadow. Learning

h_{1}

reveals

h_{2}

, which also subsequently has an observable 3-shadow.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Illustration of

G_{\mathrm{nice}}

in the case

m=5

Figure 6: An illustration of a connected component

A\subset G_{\mathrm{nice}}

; the subset

A

is highlighted in turquoise, and this example has

n_{1}=n_{2}=2

along with

m=5

. The red edges are the deleted edges which must have been removed in ( B.117 ).

Associative Memory

Associative memory studies how systems store patterns or associations and retrieve them from partial, noisy, or context-dependent cues.

See all 120 papers

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

Apr 14, 2026

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

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.

Madhava Gaikwad

Independent Researcher

Associative Memory Neural Network Robustness

Ask PDF

May 11, 2026

Hyperparameter Transfer for Dense Associative Memories

Dense Associative Memory (DenseAM) is a promising family of AI architectures that is represented by a neural network performing temporal dynamics on an energy landscape. While hyperparameter transfer methods are well-studied for feed-forward networks, these methods have not been developed for settings in which weights are shared across layers and within the layer, which is common in DenseAMs. Additionally, DenseAMs utilize rapidly peaking activation functions that are rarely used in feed-forward architectures. The confluence of these aspects makes DenseAM a challenging framework for using existing methods for hyperparameter transfer. Our work initiates the development of hyperparameter transfer methods for this class of models. We derive explicit prescriptions for how the hyperparameters tuned on small models can be transferred to models trained at scale. We demonstrate excellent agreement between these theoretical findings and empirical results.

Roi Holtzman, Dmitry Krotov, Boris Hanin

Rudolf Peierls Centre for Theoretical Physics, University of Oxford, Oxford OX1 3PU, UK · Dynamical Mind, IBM Research · Princeton

Hyperparameter Transfer Associative Memory Hyperparameter Optimization

Ask PDF

Abstract

Associative Memory

Explore similar work

Free energy landscape of Dense Associative Memory

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

Hyperparameter Transfer for Dense Associative Memories