Dense Associative Memory Through the Lens of Random Features
Authors: Benjamin Hoover
Duen Horng Chau
Hendrik Strobelt
Parikshit Ram
Dmitry Krotov
Venue: NeurIPS 2024 poster (2024)
Keywords: Associative Memory
Kernels
Random Features
Hopfield Network
Primary area: deep_learning_architectures
TL;DR: We can approximate Dense Associative Memory energies and dynamics using random features from kernel methods, making it possible to introduce new memories without increasing the number of weights.

Abstract: Dense Associative Memories are high storage capacity variants of the Hopfield networks that are capable of storing a large number of memory patterns in the weights of the network of a given size. Their common formulations typically require storing each pattern in a separate set of synaptic weights, which leads to the increase of the number of synaptic weights when new patterns are introduced. In this work we propose an alternative formulation of this class of models using random features, commonly used in kernel methods. In this formulation the number of network's parameters remains fixed. At the same time, new memories can be added to the network by modifying existing weights. We show that this novel network closely approximates the energy function and dynamics of conventional Dense Associative Memories and shares their desirable computational properties.

Dense Associative Memory Through the Lens of Random Features
Benjamin Hoover IBM Research & Georgia Tech benj jain www.ohooveriioo com
Duen Horng Chau Georgia Tech polo@gatech edu
Hendrik Strobelt IBM Research & MIT-IBM hendrik. strobelt@imm.com com
Parikshit Ram
Dmitry Krotov
IBM Research parikshit, t. ramši bm com
IBM Research krotov@ibm, com
Abstract
Dense Associative Memories are high storage capacity variants of the Hopfield networks that are capable of storing large number of memory patterns in the weights of the network of given size. Their common formulations typically require storing each pattern in a separate set of synaptic weights, which leads to the increase the number synaptic weights when new patterns are introduced. In this work we propose an alternative formulation of this class of models using random features, commonly used kernel methods. In this formulation the number of network's 's parameters remains fixed. At the same time, new memories added to the network by modifying existing weights. We show that this novel network closely approximates the energy function and dynamics of conventional Dense Associative Memories and shares their desirable computational properties.
be
Introduction
Hopfield network of associative memory is an elegant mathematical model that makes it possible to store memory patterns in the synaptic weights of the neural network [1]. For a given prompt at = 0), which serves as the initial state of that network, the neural update equations drive the dynamical flow towards one of the stored memories. For system of K memory patterns in the D- dimensional binary space the network's dynamics can be described by the temporal trajectory (t) which descends the energy function
2
ck 0
Here e (index μ = 1...K, and index i = 1...)) represent memory vectors. The neural dynamical equations describe the energy descent on this landscape. In this formulation, which we call the memory representation, the geometry of the energy landscape is encoded in the weights of the network ş which coincide with the memorised patterns. Thus, situations when the set of the memories needs to be expanded by introducing new patterns one must introduce additional weights.
Alternatvely, one could rewrite the above energy in a different form, which is more commonly used in the literature. Specifically, the sum over the memories can be computed upfront and the energy can be written
D
K
=
Tyooo where
(2)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

A) Distributed Representation (DIDAM)
B) DrDAM Reconstructions Closely Match MrDAM's
Energy approximated using dot product in feature space
Featerized Qvery
Featurized Memory
0.05
Energies MrDAM Energies
Energy
0.04
Sumt
Energy
0.00
Dancil
Query Memory Matilc
New Pottore
Memory Representation (MrDAM)
Query DrDAM MrDAM
Time Each Iine the energy descent of are image completion
Energy computed from similarity between query and stored patterns
Figure 1: The Distributed Representation for Dense Associative Memory (DrDAM) approximates both the energy and fixed-point dynamics of the traditional Memory Representation for Dense Assoiiative Memory (MrDAM) while having a parameter space of constant size. A) Diagram of DrDAM using basis function parameterized by random features (e.g., see eq. (8)). In the distributed representation, adding new memories does not change the size of the memory tensor. B) Comparing energy descent dynamics between DrDAM and MrDAM on 3x64x64 images from Tiny Imagenet [11]. Both models are initialized on queries where the bottom two-thirds of pixels are occluded with zeros; dynamics are run while clamping the visible pixels and their collective energy traces shown. DrDAM achieves the same fixed points as MrDAM, and these final fixed points have the same energy. The energy decreases with time for both MrDAM and DrDAM, although the dependence of the energy relaxation towards the fixed point is sometimes different between the two representations. Experimental setup is described in appendix D.
In this form one think about weights of the network being the symmetric tensor Tú instead of "." One advantage of formulating the model this way is that the tensor Tiş does not require adding additional parameters when new memories are introduced. Additional memories are stored in the already existing set of weights by redistributing the information about new memories across the already existing network parameters. We refer to this formulation as distributed representation.
A known problem of the network (eqs. (1) and (2)) is that it has a small memory storage capacity, which scales at best linearly as the size of the network D is increased [1]. This limitation has been resolved with the introduction of Dense Associative Memories (DenscAMs), also known as Modern Hopfield Networks [2]. This is achieved by strengthening the non-linearities (interpreted as neural activation functions) in eq. (1), which can lead to the super-linear and even exponentially large memory storage capacity [2, 3]. Using continuous variables x E R,, the energy is defined as'
K == -Q-Q/ J (F(s(t.g(x)) #=1
(3)
where the function g. RPD - RD is a vector function (c.g., a sigmoid, a linear function, or a layernorm), the function F(-) is rapidly growing separation function (c.g.. power F(-) = (-)" or exponent), S[x, x'] is a similarity function (e.g.. a dot product or a Euclidean distance), and Q is a scalar monotone function (e.g., linear logarithm). For instance, in order to describe the classical Hopfield network with binary variables (eq. (1)) one could take: linear Q, quadratic F(.) - (.), dot product S, and sign function for 9. sign(x;) og There many possible combinations of various functions g, ((,))) that lead to different models from the DenseAM family [2-7]; many of the resulting models have proven useful for various problems in AI and neuroscience [8].
Diffusion models have been linked to even more sophisticated forms of the energy landscape [9, 10].
From the perspective of the information storage capacity DenseAMs are significantly superior compared to the classical Hopfield networks. At the same time, most? of the models from the DenseAM family are typically formulated using the memory representation, and for this reason
'Throughout the paper we use bold symbols for denoting vectors and tensors, e.g., e is a D-dimensional vector in the space of neurons for each value of index μ. Individual elements of those vectors and tensors are denoted with the same symbol, but with plain font. In the example above, these individual elements have an explicit vector index, e.g.. E Same applies to vectors in the feature space introduced later.
"This is true for all DenseAMs with the exception of the power model of Krotov and Hopfield [2]. which can be written using n-index tensors Ta damnoh t in analogy with the 2-tensor Ti as in eq. (2).

---

Query
DrDAM
MrDAM
MrDAM, successfully storing 20 different 64x64x3 images from Tinylmagenet [11] and retrieving them when occluding the lower 40% each query. The memory matrix of MrDAM is of shape (20, 12288) while the memory tensor of DrDAM is of shape Y = 2 100, a ~20% reduction in the number of parameters compared to MrDAM; all other configurations for this experiment match those in appendix D. Further compression can be achieved with higher tolerance for DrDAM's ' retrieval error, smaller 3, and fewer occluded pixels, see $ 4. Top: Occluded query images. Middle: Fixed-point retrievals from DrDAM. Bottom: (ground truth) Fixed-point retrievals of MrDAM.
Figure 2: DrDAM achieves parameter compression
require introduction of new weights when additional memory patterns are added to the network. The main question that we ask in our paper is: how can we combine superior memory storage properties of DenseAMs with the distrihuted (across synaptic weights) formulation of these models in the spirit of classical Hopfield networks (eq. (2))? If such a formulation is found, it would allow us to add memories to the existing network by simply recomputing already existing synaptic weights, without adding new parameters.
A possible answer to this question is offered by the theory of random features and kernel machines. Given an input domain X. kernel machines leverage positive definite Mereer kernel function k: X' x X' + R+ that measures the similarity between pairs of inputs. The renowned "kemel trick" allows one to compute the inner-product
k(x,x') x') (x((x). p(x'))
Σ pa (x(
between two inputs x, x' E X' in a rich feature space defined by the feature map (o(x) without ever explicitly realizing the feature map (xx). Various machine learning models (such as support vector machines [12], logistic regression, and various others [13, 14J) can be learned with just access to pairwise inner-products, and thus, the kernel trick allows one to learn such models an extremely expressive feature space. Kernel functions have been developed for various input domains beyond the Euclidean space such as images, documents, strings (such as protein sequences [15]), graphs (molecules [16], brain neuron activation paths) and time series (music, financial data) [17]. Common kernels for Euclidean data are the radial basis function or RBF kernel k(x, x') exp(->lix x'1l2) and the polynomial kernel k(x, x') = ((x, x") + bjP. To appreciate the expressivity of these kernel machines, note that, for input domain R.D. the RBF kernel corresponds to an infinite dimensional feature space (Y = oc) and the polynomial kernel to O(D)) dimensional feature space.
Interpreting the composition of the separation and similarity functions in eq. (3) as the left hand side of the kernel trick eq. (4) we can map the energy into the feature space, using appropriately chosen feature maps. Subsequently, the order of the summations over memories and features can be swapped, and the sum over memories can be computed explicitly. This makes it possible to encode all the memories in tensor Ta. which we introduce in section $ 3, that contains all the necessary information about the memories. The energy function then becomes defined in terms of this tensor only, as opposed to individual memories. This functionality is summarized in fig. 1. Additionally, we show examples of retrieved Tiny ImageNet images that have been memorised using the original DenseAM model, which we call MrDAM, and the "featurized" version of the same model, which we call DrDAM (please see the explanations of these names in the caption to fig. 1). These examples visually illustrate that mapping the problem into the feature space preserves most the desirable computational properties of DenseAMs, which normally are defined in the "kernel space".
Contributions:
We propose novel approximation of DenseAM network utilizing random features commonly used in kernel machines. This novel architecture does not require the storage of the original memories, and can incorporate new memories without increasing the size of the network.
3

---

We precisely characterize the approximation introduced in the energy descent dynamics by this architecture, highlighting the different critical factors that drive the difference between the exact energy descent and the proposed approximate one.
We validate our theoretical guarantee with empirical evaluations.
In the past, kernel trick has been used for optimizing complexity of the attention mechanism in Transformers [18], and those results have been recently applied to associative memory [19], given the various connections between Transformers and DenseAMs [4, 20J. Existing studies [18, 19] focus on
settings when attention operation or associative memory retrieval is done in a single step update. This is different from our goals here, which is to study the recurrent dynamics of the associative memory updates and convergence of that dynamics to the attractor fixed points. latropoulos al. [21] propose kernel memory networks which are recurrent form of a kernel support vector machine, and highlight that De networks are special cases of these kernel memory networks. Making connection between nonparametric kernel regression and associative memory, Hu et al. [22] propose family of provably efficient sparse Hopfield networks [23, 24], where the dynamics of any given input are explicitly driven by subset of the memories due to various entropic regularizations on the energy. As have been also used for sequences [25, 26, 24]. To reduce the complexity of computing all the pairs of F(S|ç, [5. x]) for given set of memories and queries, Hu et al. [27] leverage low-rank approximation of this separation-simile also recently been used to increase separation between memories (with an additional learning stage to learn the kernel,, thereby improving memory capacity [28]. There are also very recent thcoretical analysis of the random feature Hopfield networks [29, 30], where their focus in the construction of memories using random features. Kernels are also related to density estimation [31]. and recent works have leveraged connection between mixtures of Gaussians and DenseAMs for clustering [32, 33). Lastly, random features have been used for biological implementations of both Transformers and AMsseAMs [34, 35].
matrix using polynomial expansions. The kernel trick has
To the best of our knowledge there is no rigorous theoretical and empirical comparison of Dense and their distributed (featurized) variants in recurrent memory storage and retrieval settings, as well as results pertaining to the recovery of the fixed points of the energy descent dynamics. This is the main focus of our work.
Technical background
Given the energy function in eq. (3), variable is updated in the forward pass through the "layers" of this recurrent model such that its energy decreases with each update. If the energy is bounded from below, this ensures that the input will (approximately) converge achieved by performing a "gradient descent" in the energy landscape. Considering the continuous dynamics, updating the input x over time with dx/dt, dt, we need to ensure that dE/ddt. 0. This can be achieved by setting dx/ dt x Xx..
local minimum. This can be
Discretizing the above dynamics, the update of an input x at the 1-th recurrent layer is given by:
- (t-1) - ExE-(1
(5)
where (0()) is (step dependent) step-size for the energy gradient descent, E()) the energy of the input after the t-th layer, and the input to the first layer ()) +- x. The final output of the associative memory network after L layers is (L).
DenseAMs significantly improve the memory capacity of the associative memory network by utiliz-
ing rapidly growing nonlinearity-based -eppaaaation-iiilaritt compositions such as F(S(x, {*1) = ex (")) or F(S[x, (* = cxp(-*/2||x (=1l or F(S[x, E*1) = ((x, )²))² . > 2, among other choices, with | > 0 corresponding the inverse temperature that controls how rapidly the separation-similaatt function grows. However, these reparation-similane
compositions do not allow for the straightforward simplifications in eq. (2), except for the power composition. For general similarity function, the update based on gradient descent over the energy in eq. (3) is given by:
V-E= - dQ(v)
dF(s) ds Se= g(x)
dS(g", 2)
dg(x) ===g(x) dx
(6)
dy
dz
b=Σ, F(S(e*.(()))
4

---

For example, with Q(-) (1/3) log(-), F()) exp( S(s". xx]= = (5",x) and g(x) x
the energy function and the corresponding update* are:
K
exp(3 (5" g(x))), VxE(x) En= exp(8 (5 g(x))) Σp= exp( (E" g(x))) dx
dg(x) (7)
log E(x) = 3
This form does not directly admit itself to distributed storage of memories as in eq. (2), and thus, in order to perform the gradient descent on the energy, it is necessary to keep the memories in their original form. We will try to address this issue by taking inspiration from the area of kernel machines [36].
2.1 Random Features for Kernel Machines
The expressivity of kernel learning usually comes with increased computational complexity both dur- ing training and inference, taking time quadratic and linear in the size of the training respectively, The groundbreaking work of Rahimi and Recht [37] introduced random features to generate explicit feature maps 6p F + R² for the RBF and other shift-invariant kernels* that approximate the true kernel function that is (x)x), (x(')) x ((x,x)). Various such random maps have been developed for shift-invariant kernels [18, 19, 38] and polynomials kernels [39-41]
For the RBF kernel and the exponentiated dot-product or EDP kernel k((,, x') = exp( x)), there usually two classes of random features trigonometric features and exponential features. For the RBF kernel ((x, x') ) exp(-I|x x x112/ 22), the trigonometric features [37] are given on the left and
the exponential features [18] are the right:
cos( (wl
exp(+ (w x)) w xx)
1 xx(x)= = VY
sin(
( ,
exp( exp(-||x13)
exp(
<0(x)
(8)
cosl (w
xx)
V2Y
exp(+ + exp(
sin sin((w)
where S N(O, VD E (1,....Y) Y) are the random projection vectors." A random feature map io for the RBF kernel can be used for the EDP kernel by scaling co(x) with exp( [|x While the trigonometric features ensure that k(x, x) = (x(x), (o(x)) = 1, the exponential features ensure that (x() E IR?Y. which is essential in certain applications as in transformers [18, 19J. Furthermore, while the random samples w N NO, ID) are supposed to be independent, Choromanski al. [42] show that the {w>, ...., wx) can be entangled to be exactly orthogonal to further reduce the variance of the approximation while maintaining unbiasedness. In general, the approximation of the random feature map is O( O(VD/Y). implying that a feature space with Y O(D/e)) random features will ensure, with high probability, for any x R.,. [&(x,, x') (xp(x), (x(')) I Scaling in the kernel functions such as exp(- (Bl-- x' x112/22 /) or exp(8 (x, x)) can be handled with Po the aforementioned random feature maps &p by applying them to /3x with (xth <op(-8l[x x x21l2/2).
DrDAM with Random Features
Revisting the general energy function in eq. (3), if we have available an explicit mapping & R + R such that (p($"),s((x) R F(S(e", x)), then we can simplify the general energy function in eq. (3) to
Σ (s( (((E)),((((x))) - = ((((())))(
F(x) F(x)=
(9)
We are eliding the /dxxx)/xx (1/[|x[[2)[[D> (1/1|x 3/2))xx term for the of exposition.
Kernel functions that only depend on (x - x') and not individually on x and x'.
A technical detail here is that while are using Y random samples, we actually developing 2Y-
dimensional feature map yp: D R2Y" we can get Y dimensional feature map by dropping the sin(-)
terms in the trigonometric features (and add a random rotation term 6 a E [[]] to the cos( (ws((w" x) + 6*)
term), and the exp(-.) term in the exponential features. This modification (using 2Y features instead of Y) reduces the variance of the kernel function approximation [18, Lemma 1, 2].
5

---

Denoting T= En (f("), we can write simplified general update step for any input x as:
VxÊ= = dQ(s)
(0(z) dz
dg(()
T
(10)
ds (==(p((()))
dx
x=
where dxx R YxDDij is the gradient of the feature map with respect its input. In the presence of such an explicit map yp we can distribute the memory in a MrDAM into the single Y -ddimensional vector T, and be able to apply the update in eq. (10). We can then use the random feature based energy gradient V Ex) instead of the true energy gradient Ex) in the energy gradient descent step in eq. (5). We name this scheme "Distributed representation for Dense Associative Memory" or DrDAM, and compare the computational costs of DrDAM with the "Memory representation of
Dense Associative Memory" or MrDAM in the following:
With access to the K memories {E" E RD, , E [K]], MrDAM takes OLLDD) time and D) peak memory for I energy gradient descent steps (or layers) as defined in eq. (5) with the true energy gradient Ex)..
Proposition 1.
Naively, the random feature based DrDAM would require O(DY) memory to store the random vectors and the Vxp(xx) matrix. However, we can show that we can generate the random vectors on demand to reduce the overall peak memory to just O(Y). The various proce- dures in DrDAM are detailed in Algorithm 1. The RF subroutine generates the random feature for any memory or input. The ProcMems subroutine consolidates all the memories into a single E R. vector. The GradComp subroutine compute the gradient VxE. The following the computational complexities of these procedures:
Algorithm Procedures for DrDAM with random features.
RF(Seed v, Memory E) Initialize p 4- by Set RNG R sood to for 1.... Y do
Sample random leature from I
Pu Pa (E)
return p
ProcMems(Seed r, Mems (e", 1 (1,..., K})
Initialize T + Oy For p 1....,
1. T + T+RREr.&"
return T
The RF subroutine in Algorithm 1 takes O(DY) time and O + Y) peak memory. Proposition 3. ProcMems in Algorithm 1 takes O(DYK) time and O(D + Y) peak memory.
Proposition 2.
GradComp(SSed Distributed T, Input + RF(r, RF(r. g(x))
Op
1/ Compute Vyp(yy TT in O(Y) men for 1, 12
Compute u 4- (dply)/dsily=ett)
Proposition 4. GradComp in Algorithm 1 takes
{u, T)
O(D(Y + D)) time and O(D Y) peak memory.
Initialize x' 0p // Compute =V=g(x) in O(D) men For Compute y <- dg( dxx;
Thus, the computational complexities of DrDAM neural dynamies are (see appendix F.1 for proof and discus- sions):
do
o - (y.x)
Compute 9 + -0((())
Theorem 1. With a random feature map utiliz- ing Y random projections {:aa, a {1....,Y" Y}}
return qz'
and K memories (g" E TR.D . E (1....,K) K}}, the random-feature based DrDAM takes O ( + L(Y + D))) time and DDY peak memory for L. energy gradient descent steps (or layers) as defined in eq. (5) with the random feature based approximation gradient VxE(x) de- fined in eq. (10).
However, note that the memory encoding only needs to be done once, while the same T can be utilized for I. steps of energy gradient steps for multiple input, and the cost of ProcMems is amortized over these multiple inputs. We also show that the computational costs of the inclusion of a new memories & Proposition 5. The inclusion of a new memory & E TR& to DrDAM with K memories distributed in T E TRY takes ODDY time and O(D + Y) peak memory.
The above result shows that inclusion of new memories correspond to constant time and memory irrespective of the number of memories in the current DenseAM. Next, we study the divergence between the output of a L-layered MrDAM using the energy descent in eq. (5) with the true gradient eq. (6) and that of DrDAM using the random feature based gradient in eq. (10).
'If Q(-) - log(-) in eq. (9), note that the inner product between unconstrained choices of &p can be negative but the argument to log must not be; thus, clip the value to the log to some small > 0.

---

Theorem 2. Consider the following energy function with K memories {E" E ERD, . Et,,... and inverse temperature O:
K
E(x) = log Σ
exp(-8/2/15" - x x1
(11)
We further make the following assumptions: (AI) All memories E" and inputs x lie in X' = [0, 1/DDj (A2) Using a random feature map sp DRD + Ry using random feature maps, for any x, x' E Rd there is a constant C1 such that [exp[[x= - x x112/2 ((((x), (((x))(((x))) S Ci CiVP/y. Given an input x E X, let x be the output of the MrDAM defined by the energy function in eq. (11) using the true energy gradient in eq. (6) and (( be the output of DrDAM with approximate gradient in eq. (10) using the random feature map up using constant step-size of 1j > 0 in (5). Then
1- (n 2K ( 11-n +
||x(0) -5--2 x1011, K2 BEIx) DD/ ||x())
(12)
2K n
(e0/2)
Assumption (A1) just ensures that all the memories and inputs have bounded norm, and can be achieved via translating and scaling the memories and inputs. Assumption (A2) pertains to the approximation introduced in the kernel function evaluation with the random feature map, and is satisfied (with high probability) based on results such as Rahimi and Recht [37, Claim 1] and Choromanski et al. [18, Theorem 4]. The above result precisely characterizes the effect
the divergence ||x(L) [ of the (i) initial energy of the input E(x) lower is better, (ii) the inverse temperature 3 lower better, (iii) the number of memories K lower better, (iv) the ambient data dimensionality D- lower is better, (v) the number of random features Y higher is better, and (vi) the number layers L lower is better. The proof and further discussion are provided in appendix F.2. Note that theorem analyzes the discretized system, but as the step-size - O, we approach the fully contracting continuous model. An appropriate choice the energy descent step- size 1) simplifies the above result, bounding the divergence to O D(DD)Y):
Corollary 1. Under the conditions and definitions of theorem 2, if we set the step size nj M142KBB2F77 with C2 < 1, the divergence bounded as:
C2
[x()) - x(10111 ((C3) D/V..
(13)
B(1 C2)
These above results can be extended to the EDP based energy function E(x) -1/3 log exp(3 (g", + 1/2/xx12 using the same proof technique.
Empirical evaluation
To be an accurate approximation of the traditional MrDAM, DrDAM must empirically satisfy the following desiderata for all possible queries and at all configurations for inverse temperature & and pattern dimension D;
(D1) for the same query, DrDAM must predict similar energies and energy gradients as MrDAM; and (D2) for the same initial query, DrDAM must retrieve similar fixed points MrDAM.
However, in our experiments observed that the approximation quality of DrDAM is strongly affected by the choice of ,3 and that the approximation quality decreases the further the query patterns from the stored memory patterns, predicted by theorem 2. We characterize this behavior in the following experiments using the trigonometric "SinCos" basis function, which performed best in ablation experiments (see appendix C), but note that the choice of the random features do play significant role in the interpretations of these results.
4.1 (D1) How accurate are the energies and gradients of DrDAM?
Figure 3 evaluates how well DrDAM, configured at different feature sizes Y. approximates the energy and energy gradients of MrDAM configured with different inverse temperatures / and storing random binary patterns of dimension D. The experimental setup is described below.
7

---

Approximation error of energy when queries are...
Approx error of energy gradients when queries are...
stored paneenss
near stored patioms
random
stored patterns
near stored pattems
1a15omly guessed
D-50
MAE
D=30
5611
p-30
3-
D=100
MAE
D=1000
Figure 3: DrDAM produces better approximations to the energies and gradients of MrDAM when the queries are closer to the stored patterns. Approximation quality improves with larger feature dimension Y, but decreases with higher 3 and higher pattern dimension D. Approximation eπror is computed on 500 stored binary patterns normalized between {0, V/ }. The Mean Approximation
Errors (MAE, eq. (14)) is taken over 500 queries initialized: at stored patterns (i.e., queries equal the stored patterns), near stored patterns (i.e., queries equal the stored patterns where 10% of the bits have been flipped), and randomly (i.e., queries are random and far from stored patterns). Error bars represent the standard error of the mean but visible only poor approximations. Red horizontal lines represent the expected error of random energies and gradients. The theoretical error upper bounds of eq. (13) (dark curves on the gradient errors in the right plot only) show tight fit to empirical results at low 3 and D and are only shown if predictions are "better than random".. The shaded area shows the difference between the thcoretical bound and the empirical results.
We generated 2K- = 1000 unique, binary patterns (where each value normalized to {0, v and stored K 500 of them into the memory matrix E of MrDAM. We denote these stored patterns as 5 e {0, v/D 1D_ E [K], where D is hyperparameter controlled by the experiment. For given 3, the memory matrix is converted into the fcaturized memory vector To Pa (E")) from eq. (9), where iPa
[_Y]] The remaining patterns are treated as the "random queries" x b [K] (i.e., queries that are far from the stored patterns). Finally, in addition to evaluating the energy at these random queries and at the stored patterns, we also want to evaluate the energy at queries x² that are "near" the stored patterns; thus, take each stored pattern E" and perform bit-flips on 0.1D of its entries.
For each set of queries x" E { x X } b [K]] and choice of B, Y, and D, we compute the Mean Approximation Error (MAE) between MrDAM's energy E, := E(x"; B, E) (whose gradient matrix is denoted V Eb) and DrDAM's energy Es E(x"; B, T) (whose gradient denoted V Ex).)
MAEgnergy
ED Eb/. and MAE GrEdendt [E[K]
1 K
Σ V2 BE]K]
-
(14)
We found it useful to visualize the results using log-scale and to compare the errors against the expected error of a "random guess" of the energy/gradients (horizontal red dashed line in each plot of fig. 3). The "random guess error" was empirically computed by sampling a new set of random queries x g b [K] (independent of the reference queries) and computing the MAE between the standard energy on the reference queries vs. the approximate energies on the random queries. This across all [3s is plotted.
was averaged across Y for each 3; the highest average
Observation 1: DrDAM approximations are best for queries near stored patterns DrDAM approximations for both the energy and energy gradients are better the closer the query patterns are to the stored patterns. In this regime, approximation accuracy predictably improves when increasing

---

Hamming Errort of retrievals when queries are...
B)
Corrupt Query
Larger Better Approximation
Ground Truth
sooedd
sandom
30
B-40
6-60
Larger needs
D-100
arger
p=70
p:75
D=1000
5:800
100k
"Hamming CIToE 12 squared Liooroo on binary doo2
Figure 4: A) Retrieval errors predictably follow the approximation quality of fig. 3. Error is lowest at/near stored patterns but completely random when energy and gradient approximations are poor, i.e., at high values of B and D. Note that error improves across Y but follows different (and noisier) trace than the corresponding approximations for energy and gradient in fig. due to error accumulating over multiple update steps. B) DrDAM's approximation quality improves Y increases (visible at low 3), but larger Y's are needed for good approximations to the DAM's fixed points at higher I's. (Left) The same corrupted query from CIFAR- 10 where bottom 50% is masked is presented to DAM's s with different B's. (Middle) The fixed points of DrDAM for each / at different sizes Y of the feature space. (Right) The "ground truth" fixed point of MrDAM. The top 50% of pixels are clamped throughout the dynamics.
the value for Y within "reasonable" values (i.e., values corresponding into sizes of featurized queries and memories that can operate within 46GB of GPU memory).
Observation 2: DrDAM approximations worsen as inverse temperature increases Across nearly all experiments, DrDAM approximations worsen as 3 increases. At queries near the stored patterns, 5 = 50 has an energy error approximately 10x that of 3 = 30 and 100x that of 3 = 10 across all Y. At high D and when queries are far from the patterns, the error of 50 approaches 1000 the error of 3 = 10. This observation similarly holds for the errors of corresponding gradients, corroborating the statement of theorem 2.
Observation 3: DrDAM approximations break at sufficiently high values of D and |3 In general, DrDAM's approximation eтrors remain the same across choices for D, especially when the queries are near the stored patterns. However, when both 8 and D are sufficiently large (c.g.. B 2 40 and D Z 100 in fig. 3), increasing the value of does not improve the approximation quality: DrDAM continues to return almost random gradients and energies. We explore this phenomenon more in $ 4.2 in the context of the retrievability of stored patterns.
4.2 (D2) How accurate are the memory retrievals using DrDAM?
Memory retrieval is the process by which an initial query (0) descends the energy function and is transformed into a fixed point of the energy dynamics. This process can be described by the discrete update rule in eq. (5), where can represent either MrDAM's energy or the approximate energy of DrDAM. A memory said be "retrieved" when |Exx(1) E(x(1-11)
for some small > which point (L-11) (L) =: x* is declared be the retrieved memory after L iterations because x* lives at a local minimum of the energy function E.
Quantifying retrieval error Given the same initial queries ()) E {0, V )D, we want to quantify
the difference between the fixed points x* retrieved by descending DrDAM's approximate energy and the fixed points x" retrieved by descending the energy of MrDAM. We follow the experimental setup of $ 4, only this time run full memory retrieval dynamics until convergence.

---

Note that since energy uses an L2-similarity kernel, memory retrieval is not guaranteed to return binary values. Thus, we binarize x" by assigning each entry to its nearest binary value before computing the normalized Hamming approximation error An, i.e.,
1
[
VD 0,
2vD and
AH
Σ SEIDI
-
[x:
(15)
VD
otherwise
The choice of normalized Hamming approximation error A i our binary data is equivalent the squared 1.2 error on the left side of our bound in eq. (13) (up to a linear scaling of 1
Figure 4A shows the results of this experiment. Many observations from $ 4.1 translate to these experiments: we notice that retrieval random high 3 and D, and that retrievals are of generally higher accuracy nearer the stored patterns. However, we notice that high 3 values can retrieve better approximations than lower values of 3 when the queries are or near stored patterns. Additionally, for sufficiently high 3 (c.g., see D = 1000, 3 = 50 near stored patterns), this accompanies an interesting "thresholding" behavior for Y where retrieval error starts to improve rapidly once Y reaches minimal threshold. This behavior is corroborated in the high D regime in fig. 4B.
Visualizing retrieval error Figure 4B shows what retrieval errors look like qualitatively. We stored K = 10 random images from CIFARIO [43] into the memory matrix of MrDAM, resulting in patterns of size D 32 32 3072, and compared retrievals using 3s that produced meaningful image results with MrDAM. To keep 3 values consistent with our previous experiments, each pixel was normalized the continuous range between and vD s.t. 4 [0, ) with μ E [K] and E [D].
From $ 4.1 and fig. 4A, we know that approximate retrievals are inaccurate high B and high the query is far from the stored patterns. However, this is exactly the regime test when retrieving images in fig. 4B. The visible pixels (top half of the image) are clamped while running the dynamics until convergence. Retrieved memories at different configurations for DrDAM are plotted against their corresponding MrDAM retrievals in fig. 4B.
As 3 increases, insufficiently large values of Y fail to retrieve meaningful approximations to the dynamics of MrDAM. We observe that image completions generally become but with diminishing improvement in perceptible quality after some threshold where DrDAM goes from predicting noise to predicting meaningful image completions.
less noisy as Y increases,
Conclusion
Our study is explicitly designed characterize where DrDAM is good approximation to the energies and dynamics MrDAM. In pushing the limits of the distributed representation, we discovered that DrDAM most accurate when: (1) query patterns nearer to the stored patterns; (2) is lower; and (3) Y is large. Error bounds for these situations are explicitly derived in theorem and empirically tested in $ 4.
We have explored the use of distributed representations via random feature maps in DenseAMs. We have demonstrated how this can be done efficiently, and we precisely characterized how it performs the neural dynamics relative to the memory representation DenseAMs. Our theoretical results highlight the factors playing role in the approximation introduced by the distributed representations, and our experiments validate these theoretical insights. As future work, we intend to explore how such distributed representations can be leveraged in hierarchical associative memory networks [44, 45], which can have useful inductive biases (e.g., convolutions, attention), and allow extensions with multiple hidden layers.
10

---

References
[1] John Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8):2554-2558 1982.
[2] Dmitry Krotov and John J Hopfield. Dense associative memory for pattern recognition. Advances in neural information processing systems, 29, 2016.
[3] Mete Demircigil, Judith Heusel, Matthias Löwe, Sven Upgang, and Franck Vermet. On a model of associative memory with huge storage capacity. Journal of Statistical Physics, 168(2):288
299, 2017.
[4] Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gruber, Markus Holzleitner, Thomas Adler, David Kreil, Michael K Kopp. Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. Hopfield networks is you need. International Conference on Learning Representations, 2021. URL httpt:////e//o wttp://///p/eeee/e/eeeeeeeeeeeee wtwpeeviwwwwwwwefrroeeeeee net/forum? id=tL89RnzIicd.
[5] Dmitry Krotov and John J Hopfield. Large associative memory problem in neurobiology and machine learning. In International Conference on Learning Representations, 2021.
[6] Beren Millidge, Tommaso Salvatori, Yuhang Song. Thomas Lukasiewicz, and Rafal Bogacz. Universal hopfield networks: general framework for single-shot associative memory models. In International Conference on Machine Learning, pages 15561-15583. PMLR, 2022.
[7] Thomas F Burns and Tomoki Fukai. Simplicial hopfield networks. In The Fleventh International Conference Learning Representations, 2022.
[8] Dmitry Krotov. A new frontier for hopfield networks. Nature Reviews Physics, 5(7):366-367, 2023.
[9] Benjamin Hoover, Hendrik Strobelt, Dmitry Krotov, Judy Hoffman, Zsolt Kira, and Duen Horng Chau. Memory in Plain Sight: Surveying the Uncanny Resemblances of Associative Memories and Diffusion Models, 2023. URL https: / //txx/xxvvv/////////////////aav/ http//aaiv..gaabbbaaaa/ httrrg/abs223000 16750.
[10] Luca Ambrogioni. In Search of Dispersed Memories: Generative Diffusion Models Are Associative Memory Networks. Entropy, 26(5), 2024. ISSN 1099-4300. doi: 10.3390/
c26050381. URL attpss// h/ww:://wwwwwwww mdpi. com 1ttp//1999-430000
001999440002265//880
[11] Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge. 2015. URL https:
/ //api. waappi.semmanicscholl.ee oww. http//oppu1DD:11664771
[12] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20:273-297, 1995. URL https: //link///nnnnnn springeerr.rrrrrrr.....ee. com/ /tt.ttttt/pp//1..10/////////////
pdf.
[13] Ryan Curtin, Parikshit Ram, and Alexander G Gray. Fast exact max-kernel search. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 1-9. SIAM, 2013. URL https: wttp://oii.ooo org http://01.1133111111111111/11011 97611619778822.111
[14] Ryan R Curtin and Parikshit Ram. Dual-tree fast exact max-keree search. Statistical Analysis and Data Mining: The ASA Data Science Journal, 7(4):229-253, 2014. URL https://doi. org/10. 1002/sann sam. 11218.
[15] Christina Leslie, Eleazar Eskin, and William Stafford Noble. The spectrum kemnl: A string kernel for svm protein classification. In Biocomputing 2002, pages 564-575, World Scientific, 2001. URL https: http://wwwwwwldsccccccoooo www.wwwwewwdniiiiicocoo.o wttp:/ti....oooo///////ot/////// aotooi/abs/1ie 1ttp///1..114///788877799968 0053.
[16] Karsten Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioin- formatics, 1x:4upp__ 2005. URL https: acm. httgg/do/abb////e
bioinformatiica/bi10007

---

[17] K-R Müller, Alexander J Smola, Gunnar Rätsch, Bernhard Schölkopf, Jens Kohlmorgen, and Vladimir Vapnik. Predicting time series with support vector machines. In International conference artificial neural networks, pages 999-1004. Springer, 1997. URI. https: com/ chwpter/10 100/00000220.0. cat.///aaaarrr/00010////000000
[18] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. Proceedings of ICLR, 2020. https:// wwwp:iiv..g//p/./////ee /2009 14794. pdf.
[19] Deepali Jain, Krzysztof Marcin Choromanski, Kumar Avinava Dubey, Sumeet Singh, Vikas Sindhwani, Tingnan Zhang, and Jie Tan. Mnemosyne: Learning to train transformers with transformers. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
URL
[20] Benjamin Hoover, Yuchen Liang. Bao Pham, Rameswar Panda, Hendrik Strobelt, Duen Horng Chau, Mohammed Zaki, and Dmitry Krotov. Energy transformer. Advances in Neural Infor- mation Processing Systems, 36, 2024, URL wttppttptt/// nww.ips............ cc/ cc/paper_ fit.:ppppre222fftfffeeeo77776662 pdf.
Conference.
[21] Georgios latropoulos. Johanni Brea, and Wulfram Gerstner. Kernel memory networks: A unifying framework for memory modeling. Advances in neural information processing systems, 35:35326-35338, 2022. https: h httpttpeps///poooeeeiinggsg neurips cc/ hacppppp__ft www.es/ppapaeeeee es/aaper/ ht0p://1122550001222000711112222
Paper- Conf fonference. pdf.
[22] Jerry Yao-Chieh Hu, Bo- Yu Chen, Dennis Wu, Feng Ruan, and Han Liu. Nonparametric modern hopfield models. arXiv preprint wwXiv:2404.039000 2024. URL https: /tatps://ariv... ortp/d///or//// 2404.03900 .df.
[23] Jerry Yao-Chieh Hu, Donglin Yang, Dennis Wu, Chenwei Xu, Bo- Chen, and Han Liu. On sparse modern hopfield model. Advances in Neural Information Processing Systems, 36, 2023. URL
meweriiniinnnnnnnssneeeeeeeenirr ct/ccccppaaoa cecppaper_fiiii 177cca552266220111444444eeeeee22 Patpaa/r/ccccettaaaaaaaeooo-eree Comper-Coneeeeneeee
.df..
[24] Saul José Rodrigues Dos Santos, Vlad Niculae, Daniel C Mcnamee, and Andre Martins. Sparse and structured hopfield networks. Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 43368-43335 PMLR, 21-27 Jul 2024. URL https: btttps://pront h/proceedingg...... mlr. press/v235/ aantos24a.hhmll.
[25] Hamza Chaudhry, Jacob Zavatone-Veth, Dmitry Krotov, and Cengiz Pehlevan. Long sequence hopfield memory. Advances Neural Information Processing Systems. 36. 2024. URL
www.eediiinnnnn.iisseeeeeee nwwrinuuriioom cct ppaapr_filee wtt.f//sappeeee///////////////// pppppppppp////ilee/ Ponerrreeeeeeeeeeeeeeeeeee pdf..
[26] Dennis Wu, Jerry Yao-Chieh Hu, Weijian Li, Bo-Yu Chen, and Han Liu. STanhop: Sparse tan- dem hopfield model for memory-enhance time series prediction. In The Twelfth International Conference on Learning Representations, 2024. URL id=6ixg437CZs.
net/forum?
[27] Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, and Han Liu. On computational limits of modern hopfield models: A fine-gre fine-grained complexity analysis. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 19327-19343. PMLR, 21-27 Jul 2024. URL https: / prwceedinggg....m mlr, press/ v235/hu24) html.
[28] Dennis Wu, Jerry Yao-Chieh Hu, Teng-Yun Hsiao, and Han Liu. Uniform memory retrieval with larger capacity for modern hopfield models. arXiv preprint arXiv:2404.03900 2024. URL org. wwt/pof//////ooooooooo/ooo /404. 03827. pdf.
https://arxiv:
[29] Matteo Negri, Clarissa Lauditi, Gabriele Perugini, Carlo Lucibello, and Enrico Maria Malatesta. Random feature hopfield networks generalize retrieval to previously unseen examples. In Associative Memory& & Hopfield Networks in 2023, 2023.
12

---

[30] Matteo Negri, Clarissa Lauditi, Gabriele Perugini, Carlo Lucibello, and Enrico Malatesta. Storage and learning phase transitions in the random-feature hopfield model. Physical Review Letters, (31()5)255730, 2023.
[31] Bernard W Silverman. Density estimation for statistics and data analysis. Chapman & Hall/CRC, 1998.
[32] Bishwajit Saha, Dmitry Krotov, Mohammed J Zaki, and Parikshit Ram. End-to-end differen- tiable clustering with associative memories. In Proceedings of the 40th International Confer- ence on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 99649-296700 PMLR, 23-29 Jul 2023. URL htttps://ppott //poceeddsss mlr. press/v202 saha23a. html.
[33] Rylan Schaeffer, Nika Zahedi, Mikail Khona, Dhruv Pai, Sang Truong, Yilun Du, Mitchell Ostrow, Sarthak Chandra, Andres Carranza, Ila Rani Fiete, Andrey Gromov, and Sanmi Koyejo. Bridging associative memory and probabilistic modeling, 2024. URL petttps://arx// org/ abs/2402. 10202.
[34] Leo Kozachkov, Ksenia V Kastanenka, and Dmitry Krotov. Building transformers from neurons and astrocytes. Proceedings of the National Academy of Sciences, 120(34):e219150022 2023.
[35] Leo Kozachkov, Jean-Jacques Slotine, and Dmitry Krotov. Neuron-astrocyte associative memory. arXiv preprint arXiv:2311.08133 2023.
[36] Léon Bottou. Large-scale kernel machines. MIT press, 2007.
[37] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 2007. URL https:// h/poce/ee////////peeeeee neurips cc/
www.r.pppprr.ee .df..
[38] Valerii Likhosherstov, Krzysztof Marcin Choromanski, Kumar Avinava Dubey, Frederick Liu, Tamas Sarlos, and Adrian Weller. Dense-exponential random features: Sharp positive estimators of the gaussian kemne.. In Thirty Conference on Neural Information Processing Systems, 2023. URL https:t//// opwnrevieeeeeeeeeeeeeeee/ee net sett/forrmnddd=SxxFea
[39] Purushottam Kar and Harish Karnick. Random feature maps for dot product kernels. In Artificial intelligence and statistics, pages 583-591. PMLR, 2012. URL press/v22/kart 1artar/2/aaaarrr pdf.
mlr.
[40] Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kemnels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 239-247, 2013. URL https: //dl. acm. org/ /ttf//d//// 1145/ 2487575 2987591.
[41] Raffay Hamid, Ying Xiao, Alex Gittens, and Dennis DeCoste. Compact random feature maps. In International conference on machine learning, pages 19-27, PMLR, 2014. URL
sttpss//prooceedings. mlr. www.s/rresseveee. http://aamd1...... .df.
[42] Krzysztof M Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effec- tiveness of structured random orthogonal embeddings. Advances neural information pro- cessing systems, 30, 2017. URL https: pesttts:/pproceeee www.iinnnnnnuuis...uu cttpiipss.ccpppp///11////// Paper. .dff.
[43] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[44] Dmitry Krotov. Hierarchical associative memory, 2021. URL https::://aaxi..rrreeeeeee abs/ 2107.06444
[45] Benjamin Hoover, Duen Horng Chau, Hendrik Strobelt, and Dmitry Krotov. A universal ab- straction for hierarchical hopfield networks. The Symbiosis of Deep Learning and Differential Equations II, 2022. URL https::/ wttp:/orrmm.dd--Ssaaaaaaaa
13

---

[46] Peter W Frey and David Slate. Letter recognition using holland-style adaptive classifiers. Machine learning. 6:161-182, 1991.
[47] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milnee and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL com/ google/
http://giin
[48] Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Trans- formers as algorithms: Generalization and stability in in-context learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 19565-19594, PMLR, 23-29 Jul 2023. URL https: /pwpc//d/noccsgssss mlr, wal.r.pees//vee ppwps/v202 /ress//202/11231 11231 html.
14

---

A Limitations
In this paper, we have explored the use of distributed representations via random feature maps in DenseAMs. However, we are only scratching the surface of opportunities that such distributed representations bring to DenseAMs. There are various aspects we do not cover: (i) We do not cover the ability of these distributed representations to provide (probably lossy) compression. (ii) We do not study the properties of DrDAM relative to MrDAM when DrDAM is allowed to have different step sizes and number layers than MrDAM. A further limitation of our work is the limited number of datasets on which we have characterized the performance of DrDAM.
B Approximation error when increasing the number of stored patterns in DrDAM
S 4.1 validated eq. (13), confirming that approximation error decreases the number of random features Y increases under constant number of stored patterns K. We can also consider a related but different question: under constant number of random features Y, how does approximation error behave when increasing the number of stored patterns K Intuitively, DrDAM's approximation should be good when small number of patterns are stored in the network, and this approximation should worsen as we increase the number stored patterns.
Figure validates this intuition empirically, with the caveat that random queries generally improve in accuracy because the probability of being near stored patterns (a regime that generally leads to higher accuracy of retrievals, see Š 4) increases
store more patterns into the network, For this experiment, 2e5 was held constant across experiments and each plotted approximation error is averaged over number of queries equal to the number of stored patterns K. The experimental design otherwise exactly replicates that of fig.
Approximation error of energy when queries are...
Approx error of energy gradients when queries are...
stored patterns
stored panterns
stored stored patterns
random
Eroo andomly guessed
0-50
17
12
Q-40
B-40
D-30
P-30 Bandd"
+030
+0+10+
12
D=100
12
D=1000
K
Figure 5: Mean Approximation Error (MAE, eq. (14)) increases as the number of stored patterns K increases (except random starting positions, where more stored patterns increases the probability that a random query is closer to memory, a regime that leads to higher accuracy of the retrievals, see fig. 3), keeping Y 2e5 constant across all experiments.
C Ablation study: Comparing choices for basis function
Different basis functions can be used to approximate the RBF kernel used in the energy of the memory representation of the DAM in eq. (7). We considered the following kernels ("Cos", "SinCos", "Exp", "ExpExp"), rewritten here as
15

---

cos( w x + b1)
2
cos w x + b2)
PCoo (x)
Y
cos( w x) + by)
cos( (w x)
sin w x
cos w x)
PsinCoos (x) =
sin w x))
vY
cos w xx)
sin
expl
xx
+ b1)
exp( x
x) + (2)
PExp (x)
xx) + by)
exp(1
exp ,x)
exp(-1|x13
exp(
PxxpExp (x)
exp( (w x))
V2Y
exp( +
exp(
where w ~ (O, ID), E [Y] are the random projection vectors and 1 ~ U(0, 2x) are random "biases" or shifts in the basis function.
Figure shows how well the above basis functions approximated the true energy and energy gradient different values for I and size of feature dimension Y. Specifically, given the Letter dataset [46] which consists of 16-dimensional continuous vectors whose values were normalized to be between [0, I we randomly selected 900 unique data points, storing 500 patterns into the memory and choosing the remaining 400 to serve as new patterns. We then compared how well the energy and energy gradients of the chosen basis function approximates the predictions of the original DAM.
We observe that the trigonometric basis funetions (i.e., either Cos or SinCos) provide the most accurate approximations for the energy and gradients of the standard MrDAM, especially in the regime of high which is required for the high memory storage capacity of DenseAMs. Surprisingly, the Positive Random Features (PRFs) of [18] do not perform well in the dense (high 3) regime; in general, trigonometric features always provide better approximations than the PRFs.
We conclude that the SinCos basis function is the best approximation for use in the experiments reported in the main paper, as this choice consistently produces the best approximations for the energy gradients across all values of B.
D TinyImagenet Experimental Details
In performing the qualitative reconstructions shown in fig. 1, we used a standard MrDAM energy
(eq. (7)) configured with inverse temperature 8 60. We approximated this energy in a DrDAM using the trigonometric "SinCos" basis function shown in eq. (8) configured with feature dimension Y = 1.8e5. The four images shown were selected from the Tiny Imagenet [11] dataset, rasterized into a vector, and stored in the memory matrix a MrDAM, resulting in a memory of shape (4, 12288). Energy descent for both MrDAM and DrDAM used standard gradient descent a step size 0. until the dynamics of all images converged (for fig. after 300 steps, see energy traces). Visible pixels are "clamped" throughout the duration of the dynamics by zeroing out the energy gradients on the visible top one-third of the image.
16

---

Error of Energy
Error of Gradients
at stored patterns
new data
at stored patterns
at new data
10n1
10"5
10%
20-5
10
MAF
B=1
MAE
20"4
10a4
10"5
10"2
10.0
MAE
B= 10
MAE
10
10
10
10
10
B = 30
MAE
20"2
10
10"4
20'4
1.0
10"1
10
10
10
10-2
MAE
60
MAE
10-3
20
10-3
226
1301
100
2004
1000
380
1001
200
Figure 6: Trigonometric basis functions significantly outperform Positive Random Features, especially in the regime large 3. We end up choosing the SinCos function analyze in the main paper, as this choice of basis function always produced the best approximations to the energy gradient. Experiments performed on the 16-dimensional Letters dataset [46].
In MrDAM, the memory matrix necessarily grows linearly when storing patterns e However, the distributed memory tensor T of DrDAM does not grow when new pattems are stored. This means it is possible to compress the memories into smaller tensor T where Y NumPixels, provided that we operate in a regime that allows larger approximation errors in the retrieval and smaller initial occlusions. Figure 2 shows variation of the setting of fig. where stored patterns are actually compressed into DrDAM's memory tensor, successfully storing 20 12288 pixels from a distributed tensor of size ~20% reduction in the number of parameters compared to MrDAM. All other hyperparameters are the same as was used to generate fig. 1, and convergence on all images occurs after 1000 steps.
2e5 and retrieving the memories with 40% initial occlusion of the queries,
E Details on Computational Environment for the Experiments
All experiments are performed on single L40s GPU equipped with 46GB VRAM. Experiments were written and performed using the JAX [47] library for tensor manipulations. Unless otherwise noted, gradient computation performed using JAX's powerful autograd mechanism. Experimen- tal code with instructions to replicate the results in this paper are made available this GitHub repos- itory (https: //github. coding environment and run all experiments.
DAM), complete with instructions to setup the
17

---

F Detailed Proofs and Discussions
F. Details for theorem 1
F111 Proof of theorem 1
Proof of theorem I. The proof above involves noting that, first we need encode all the memories with ProcMems, which takes O K) time and O(Y + D) peak memory using proposition 3.
Then compute L gradients with GradComp for L iterations of energy gradient descent, taking O(LD(Y + D)) time and O(D + Y) peak memory using proposition 4.
Putting the runtimes together, and using the maximum of the peak memories gives us the statement of the theorem.
E.1.2 Comparing computational complexities of MrDAM and DrDAM
Note that, comparing the computational complexities of MrDAM in proposition to that of DrDAM in theorem 1 does not directly provide any computational improvements it would depend on the choices of D, K, L, L. The main point of these results is to highlight, that once the memories are processed via ProcMems, the energy descent with DrDAM requires computation and memory that only depends on D and Y. And together with theorem 2 and corollary I, we characterize situations where the energy descent divergence between MrDAM and DrDAM can be bounded with choice of Y that only depends on (and other parameters in the energy function) but not K.
While we do not claim or highlight computational gains over MrDAM, note that the peak memory complexity of MrDAM is O) compared to O(Y + D) for DrDAM. Given that in the interesting regime of Y ~ O(D/e²) which upperbounds the energy descent divergence between DrDAM and MrDAM in corollary 1 to at most some e > O, DrDAM more memory efficient than MrDAM the number of memories K > C/e² for some sufficiently large positive constant C. Ignoring the time required to encode the memories into the distributed representation in DrDAM using ProcMems, the runtime complexities are OL for MrDAM compared to O(LD(Y D)) for DrDAM. Again, considering the interesting regime of ~ e DrDAM will be computationally more efficient than MrDAM if the number of memories K >> CD/2² for some sufficiently large positive constant Č.
F.2
Details for theorem 2
F.2.1 Proof of theorem 2
Here will make of the following result from Li et al. [48]:
Lemma (adapted from Li et al. [48] Lemma B. For x, 2 E RR with (xx S 8 and maxx, (z. 23) S 8, we have the following:
e
S 6d
(xoftmax(x)]lo s
|softmaxxxx softmax(z))
K ||x 2/11-
(16)
K'
We now develop the following results:
Lemma 2. Under the conditions and notation of theorem for x,z E X. we have
<xx((x) VxE(z)I S
21+ (1
z||-
(17)
Proof.
Given the energy function in eq. (11), we can write the energy gradient ExE as:
Exx = sof tmax (enfftaax33111 -3/21lx - (x - 3) x - (33/2||
- = 12) E (18)
where [s] _,l,...,_" cK], ||x 3 denotes x g² 12
xx _5113] and (x =) denotes
[x { ..., (x {.
Then have
18

---

Vx ExE(2)
(19)
x -oftmax(-B// -//2 = + softmax( 3//2|z E =
(20)
x z|| (/softmax(-8/22 = =1 soft
(-3/212 =
(21)
x z|| +|((ootmax (-3/2/|
= = sof softmax
(-3/2 =1 |||
(22)
8/2
- x z||
K 12 || - = - ||x - =
(23)
where applied lemma 1 to the softmax term in the right hand side of eq. (22) with 5 3/2 since all pairwise distances in A' are in [0, 1].
Now we have
8 K
||/2([|z -E1 -
||z 1n ||x- 1
(24)
2
K
(z + x x)
x + x -2)
(25)
9 K
2
||z
||| z + x|| 2
S
2
Σ 4 A|
x||,
(26)
μ=1
μ=
since || < 1 and ||x z/| < ||||| + |||||
< 2. Putting eq. (26) in eq. (23), and using the fact that
| S K, we have
8/2
K
Vx - VxE(z)]2 z||+
K23
Σ #=1
z
x = =11+ 2 - -2), (27)
K
giving eq. (16) in the statement of the lemma.
Given the structure of the energy gradient in eq. (18) of the energy function in eq. (11), we consider a specific energy gradient for this specific energy function instead of the generic energy gradient in eq. (10). We can rewrite the exact energy gradient as
13/21x/21|x 11 K vx x -n'=1 exxp-B/221xx 5t 113
(28)
Using random feature maps, we can write the approximate gradient as
vx = x (((v3x)) 5"
(29)
E (P(VBx).
ER (VVBX) (0((BE)) E (p(V3x), Ex= 60 (((33")) )) p(V[Tx) IK le( (V(BE))) EHT
(30)
where T Σ (VVBBeL)
(31)
(x(V3x), T)
= xx(3x) R (p(VBxx, T)
K
where R
Σ
(32)
where we again just need store T and as defined above and not need to maintain the original memory matrix =.
19

---

Lemma 3. Under the conditions and notation of theorem 2, and assuming that (9((x; sp(x)) 2
xvx,'' E X. for the approximate gradient (x) in eq. (32), we have
D Y
[ - vxE(x)]I S 20, KE
(33)
Proof.
We can expand out the left-hand side of eq. (33) as follows:
Ex= exp( /xp((-//2|x 1=
ΣØ
e" ΣØ (((3e)))
[[x - Vxx(x)]1
- Eeー -
(34)
by reversing the simplifying steps made above to arrive at eq. (32).
Let use denote e == Ci D/Y the approximation in the kernel value induced by the random feature map sp. Then considering the terms in the denominator above, we have
(0(( ( (P(VEx), Ev((v (0((3em) )
(1/K)
Σ exp( 1/p/- x 5²1]²)
(35)
= (1/K)
Σ
(exp(=8/2lxx =2113)- - (p(v3x)) 50( ( /BE4))
(36)
s (1/K) Σ - - (p(VBxx, - (((x)))))(((()))) (1/K) Σe=e. c. (37)
Considering the terms in the numerators, we have
(1/K)
Σ
2xp(-~/2/1x-ee
(o(Vxx,, E ( (B()) E" )("
(38)
= (1/K)
Σ
exp((8/2/lx 5-133) - (10(VXx)) s0( (BE4)) g"
(39)
< (1/K) Ell
(xp(-9/2|lx - 5-113) - (pl (p(v3x). sp( /B g")
(40)
(1/K) Σ [(( (exp(-*/2ll= 3n113) (x(1/x),, s0( v (B()))
||
(41)
s (1/K) Σ |||5"|| = 1 S1 1.
(42)
Let us define the following terms for convenience:
1/K E,, exp(-#/2||x 1²
1/K Σ, exp(-8/2l|x 5
à 1/K Σ, (p(v3 gd
b = 1/K En (I(V/xx) (x (BEE))
Then, based on our previous bounds, we know that
||a - a|l Se, 1b b- [[VxE(x) - Vx =
(43)
20

---

[[x - vxE(x)]I
a
a
WA
2
1
(44)
6
b
6
b
à
1
1a
all +
b
(45)
6
6
b
P
1 +
(46)
Note that (a/b) is in the convex hull of the memories since this is a weighted sum of the memories where the weights are positíve and add up to 1. Thus within (ā/b) E 1//1/ thus |ā/b|| s 1. Now = (1/K) exp(-3E(x)). Thus
D Vx vx Ex)Il s 2 exp(3E(x)) 20 (xxx(((((E)
(47)
y
giving us the right-hand side of eq. (33).
Proof of theorem 2. Expanding out the divergence (LL) after energy descent steps, and using the fact that ()) = (0)) x, we have
D(L) A (z( x111
(48)
(0)
Σ tE[l]]
1/ x ((x((-11)
(x00) Σ n/ =x(((1((
x((0) 100)
(49)
1E|M
Σ 1E/4
1 (vxb(x((-1)) - V (((((((11)))
(50)
Σ [xF((((-1)) Vx (x
(51)
[E[L]
< Σ || (V=F(x((-))) (x te[T]
(52)
Let us denote the individual terms above as d(t) with D = Enery d(t), Also, let us denote by = 2C, K (Ex) /D/ and by B = (1 + 2K B2)) Then writing out the 1-th term
d(0 17 (x - V VxL(x((-11)
(53)
(VxE(x((-1)) - VxE((((11)
+ || (Vx
Vx
(54)
I (BI[x((-1) 11 + nd,
(55)
where the first term is bounded using lemma 2 and the definition of B, and the second term is bounded using lemma and the definition of A.
Note that this gives us the recursion d( < nA nBD(t-1), and thus. D(L) s Eeary n(A (t-(-))).
21

---

Writing out the recursion using induction, we can show that
D
AA
Σ 1+
Σ tE[L]
t(nB)
Σ
Σ t1
+
Σ
Σ
t2(nB)s
rE[T]
1E[L] (IE teffc]
+..
Σ
Σ
l (n_I(1))
(56)
rE[T] [E[4]
16f2 2]
$ A + L(nLL) L(mBL)² (nnBL)
(57)
nAL 1- (nBL)*
(58)
1- BBBL
Replacing the values of A and B above gives us the statement of the theorem.
F.2.2 Dependence on the initial energy Exx of the input.
The divergence upper bound in eq. (12) (in theorem 2) depends on the term exp(3E(x)) However, note that, for the energy function defined in eq. (11), assuming that all memories and the initial queries are in ball of diameter 1 (which is the assumption A1 in theorem 2), E(x) s 2 log K implying that exp(3F(xx) S exp(3/2)/ K, and we can replace this in the upper bound and remove the dependence on Exx).
However, an important aspect of our analysis that the bound is input specific, and depends on the initial energy Exx). As discussed above, this can be upper bounded uniformly, but our bound is more adaptive the input x.
For example, the input is initialized near one of the memories, while being sufficiently far from the remaining (K 1) memories, then exp(3E(x)) term can be relatively small. More preciscly, with all memories and queries lying in ball of diameter 1, let the query be at a distance r < 1 to its closest memories, and as far possible from the remaining (K -1) memories. In this case, the implying that
initial energy (xx) = (1/8)
+ (K
(2)(3r
exp(3F(xx)) ~ (1 + exp(- r)/2) S exx(3rr2).
(59)
For sufficiently small r < 1, the above quantity can relatively small. If, for example, r ~ Ollg K), then exp(3E(x)) ~ O(K)), while r + gives us exp(3E(x)) - O(1). This highlights the adaptive input-dependent nature of our analysis.
22

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We lay out clearly our contribution of novel approximation of the dynamical process for Dense Associative Memory that uses random features.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made
the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are characterized theoretically in $ 3, empirically in $ 4, and summarized in appendix A.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approxinations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
Assumptions, propositions, and theorems are given in $ 3, with additional
proofs in appendix F.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proofs provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Extensive descriptions of the main experimental results are provided in 4; experimental details that were not appropriate for the main paper are explained in appendix I) and appendix E. Our proposed method itself is explained in detail in Algorithm 1.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility. which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
24

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code and instructions to run all experiments this paper is provided at this anonymous GitHub repository (https:/ ttttps://anonymuus anonymous. .open waleencer//draane which is included in appendix E of our paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/ guides/ /ooes//oeeeSussiiiiic.eea ssionooicyy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
//nips. httpp/ubllgggiccoc dee/CooeSuumii sssssssissii aasionnoiccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones omitted from the script and why. At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details are provided alongside the results reported in $ 4. Computational environment for the experiments is described in appendix E.
Guidelines:
The answer NA means that the paper does not include experiments. The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them. The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Error bars representing the "standard error of the mean" (SEM) are shown on all quantitative plots (i.e., figs. and 6). We evaluated on large sample sizes s.t. the SEM is small, but still visible when the predictions have high variability.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
25

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors). It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI. if the hypothesis
Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported tables or plots, The authors should explain in the text how they calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We use the same computational environment for all experiments, which is described in appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn' t make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: attpps:/neeus http///nurrrp.ppee heabllii//thissuudeeellleel
Answer: [Yes]
Justification: Our work does not require human subjects. Datasets used are public and the nature of the evaluation is not dependent on any inherent biases. The work does not have unexpected anticipated societal harms or other harmful consequences requiring mitigation.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics. If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special considera- tion due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We do not anticipate any additional societal harms or other harmful conse- quences requiring mitigation beyond the well-known risks.
Guidelines:
The answer NA means that there is no societal impact of the work performed. If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address socictal impact.
26

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimesss considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No proprietary datasets were used. The models developed are anticipated to have a high risk potential for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All owners of assets used in this paper are properly cited. No licensed work used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paper swi thcode. com/ mmmddataees has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification: This paper mainly contributes new algorithm for approximating Dense Associative Memories. This is documented throughout the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL, include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our research makes no use of crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if main contribution the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our research makes of crowdsourcing human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "usfhZ7fixf", "reviewer": "Reviewer_xsUY", "summary": "The paper proposes to interpret the energy function of Dense Associative Memory as relying on a kernel that can be approximated by kernel-specific random feature maps. \nThe approximation allows to condensate the stored patterns into a tensor whose size is independent of the number of patterns stored, similarly to what can be done in classical and polynomial Hopfield networks. \nNew patterns can then be incorporated without changing the dimensionality of the parameter space. \nThey provide bounds for the approximation error of the iterates in the gradient descent procedure that uses their energy approximation.", "questions": "- Can the author show a plot similar to Fig. 2 but now showing the theoretichal prediction from eq. 12 (say for L=1 and alpha=1) compared to the actual error?\nProbably this information could just be plotted in Fig. 2B. \n\n- It would be nice to make a plot similar to Fig. 2 but now as a function of K.\n\n- In order to help the reader and improve consistency, p in Algorithm 1 and at the beginning of Section 3 could denote the same thing.\n\n- Assuming that the random feature version is considered as DAM per se instead of an approximation to another DAM, could the author comment on its capacity in presence of random memories? It is linear in Y?\n\n- line 215. Usually, the EDP model also contains an x^2 term outside the logarithm.", "limitations": "The authors could discuss more the limitations of their work. In particular, the fact that the approximation requires a very large feature size Y in order to be accurate. This could limit the practical use of the method.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- I appreciated the idea of trying to use the kernel approximation in order to overcome the computational limits of DAMs. \n- The paper is well written and the idea is clearly explained.", "weaknesses": "- The main limitation of the work in my opinion is that one has to go to very  large values of the feature size Y in order to have a good approximation.  In fact, looking at the error bound in eq. (12), it seems that Y has to be taken of the order of O(K^2*D) in order to have a good approximation, which is much larger than the size of the memory matrix (K*D). This not taking into account the exp(beta*E) term in the bound, which could penalize high-energy configurations a lot.\n\n- Numerical Experiments are limited and not fully convincing. For instance, in Fig. 1 the 4x12288=49152 memory matrix has to be replaced by a several times larger Y-sized vector in order to obtain a good approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy to hear that the main message of the paper got across well, and thank the reviewer for their insightful comments and feedback. Below we answer individual questions raised.\n\n> … looking at the error bound in eq. (12), it seems that $Y$ has to be taken of the order of $O(K^2 D)$…\n> \n\nIt is true that if we ignore all the terms on the right hand side of equation (12) except for the $K \\sqrt{D/Y}$ term, it appears that $Y \\sim O(K^2 D)$. However, it is important to note that the remainder terms in the upper bound on the right hand side of (12) also include the step-size $\\alpha$ and $K$ itself. Ignoring the effect of $\\alpha$ and $K$ in the remainder terms can give a wrong impression regarding the bound. For that very reason, we explicitly study a special case in Corollary 1, in which the update rate $\\alpha$ is scaled in a $K, L$, and $\\beta$ dependent manner. An important aspect of our analysis is that the bound is query specific, and depends on the initial energy $E(\\mathbf{x})$. For example, if the query is initialized near one of the memories, while being sufficiently far from the remaining $(K-1)$ memories, then $\\exp (\\beta E(\\mathbf{x}))$ term can be relatively small. More precisely, with all memories and queries lying in a ball of diameter $1$, let the query be at a distance $r < 1$ to its closest memory, and as far as possible from the remaining $(K-1)$ memories. In this case, the initial energy $E(\\mathbf{x}) \\approx -(1/\\beta) \\log [\\exp(-\\beta r / 2) + (K-1) \\exp(-\\beta/2)]$, implying that\n\n$$\n \\exp(\\beta E(\\mathbf{x})) \\approx \\frac{\\exp(\\beta r / 2)}{\\Big[1 + (K-1)\\exp(-\\beta(1 - r)/2)\\Big]} \\leq \\exp(\\beta r / 2)\n$$\n\nThus, the exponential factor in our bound is not a problem. Overall, the divergence is bounded by $O(\\sqrt{D / Y})$, at constant $\\beta$, implying the need for $Y \\sim O(D / \\epsilon^2)$ for at most $\\epsilon$ divergence. Please note, that this estimate is independent of $K$, which is the essence of our proposal.\n\n> Numerical Experiments are limited… in Fig. 1 the 4x12288=49152 memory matrix has to be replaced by a several times larger Y-sized vector…\n> \n\nThe configuration shown in Fig.1 was chosen to illustrate the main idea of the method. $Y$ does not have to be larger than the number of parameters required to describe the memory vectors. To explicitly demonstrate this point we have repeated the experiments shown in Fig.1 with 20 memories; please see Fig (a) in the 1 page PDF rebuttal. Now we have 20x64x64x3=246k parameters in the memory vectors encoded in the 200k-dimensional vector $T$. The method works well and all the conclusions presented in the paper remain valid.   \n\n> Can the author show a plot similar to Fig. 2 but now showing the theoretical prediction from eq. 12…?\n> \n\nWe thank the reviewer for this great suggestion, which would highlight the tightness of our proposed upper bound. We have done it in Fig (c) of the 1 page PDF rebuttal. It is important to note that the upper bound also involves a quantity (precisely the quantity $C_1$ defined in assumption A2 in Theorem 2) which bounds the approximation introduced by the random feature maps (such as Rahimi and Recht (2007)), and this does not have an easily computable analytical form. For this reason, it is challenging to precisely compute this bound. However, it is possible to check the predicted scaling relationships. Specifically, the theoretically predicted $Y^{-1/2}$ dependence in the upper bound for a fixed $D$ appears in most of the results, please see Fig (c) in the 1 page PDF. This shows that the upper bound  in equation (12) from Theorem 2 fairly characterizes the dependence on $Y$. Fig (c) from the PDF will be used to update Fig 2 (right side) in the current submission. \n\n> It would be nice to make a plot similar to Fig. 2 but now as a function of K.\n> \n\nThanks for the suggestion. We have generated this plot per your request and included it in Fig (b) of the 1 page PDF. The results are consistent with the theory developed in our paper. \n\n> … $\\mathbf{p}$ in Algorithm 1 and at the beginning of Section 3 could denote the same thing.\n> \n\nThe reviewer is correct that we overload the variable $\\mathbf{p}$ both as $\\mathbf{p} = \\mathbf{g}(\\mathbf{x})$ and $\\mathbf{p} = RF(\\tau, \\mathbf{g}(\\mathbf{x}))$. We will fix the notation, and use a different term to denote $\\mathbf{g}(\\mathbf{x})$.  \n\n> line 215. Usually, the EDP model also contains an $x^2$ term…\n> \n\nThe reviewer is correct, the complete EDP energy is\n\n$$\nE(\\mathbf{x}) = -\\frac{1}{\\beta} \\log \\sum_\\mu \\exp(\\beta \\langle \\boldsymbol{\\xi}\\mu , \\mathbf{x} \\rangle) + \\frac{1}{2} \\| \\mathbf{x} \\|^2.\n$$\n\nWe were referring to the part of the energy which is relevant for the argument in line 215. We will write the complete energy. Our claim of validity of the proof technique of Theorem 2 still applies, since we just need to approximate the $\\exp(\\beta\\langle \\boldsymbol{\\xi}_\\mu, \\mathbf{x} \\rangle)$ term with the random features.\n\n> Assuming that the random feature version is considered as DAM… could the author comment on its capacity in presence of random memories?\n> \n\nThis is an interesting question, which may be investigated in the future. However, it remains beyond the scope of our current project. Our goal here is to answer the following question: how well the random feature description can represent the dynamics of DAM?\n\n**General Comment**\n\nOnce again, we greatly appreciate your insightful comments and suggestions. We would be grateful if you could consider increasing the score for our work towards an accept.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sFqqPjfQwz", "reviewer": "Reviewer_B4qp", "summary": "This paper studies a method to modify associative memory network weights when introducing new memories. The proposed uses random features and is shown to approximate the energy function of the conventional ones.", "questions": "Please refer to weaknesses.", "limitations": "This paper addresses its limitations in the appendix.", "rating": 7, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method and results are novel to me, understanding associative memories (AMs) through random feature seems to be a great connection between AMs and random feature transformers.\n2. The paper is well written and easy to follow.", "weaknesses": "1. Why using hamming distance when calculating retrieval error when the theoretical results use L2?\n2. To my understanding, the proposed method is an approximation to DAM. Thus the paper should at least compare the proposed method to DAM in thr experimental section.\n3. The field of associative memories, Hopfield networks are getting increased attention recently, I think a related work section would benefit this paper a lot.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Why using hamming distance when calculating retrieval error when the theoretical results use L2?\n> \n\nWe consider Hamming error since we are storing and retrieving binary memories, e.g. in Fig.3. Our theoretical results operate in the more general continuous $\\mathbb{R}^d$ space, and thus bounds the L2 error. However, please note that, with binary vectors, Hamming error and L2 error are related by the square root operation. For this reason, our theoretical bound (proven for L2 error) is equal to the square root of the numerical evaluations with Hamming distance. \n\n> To my understanding, the proposed method is an approximation to DAM. Thus the paper should at least compare the proposed method to DAM in the experimental section.\n> \n\nYou are correct -- our proposed \"distributed representation\" for DenseAMs, which we call DrDAM, are approximations to the original DAM (what we refer to as the \"memory representation\" or MrDAM in our paper). The experiments in our paper are explicitly designed to compare against the original DAM a.k.a. MrDAM. E.g., Figs 2 and 3A plot DrDAM's approximation error when compared to the original DAM. Fig 3B shows how well, qualitatively, DrDAM approximates the original DAM (what we call the \"Ground Truth\" in that figure).\n\n> The field of associative memories, Hopfield networks are getting increased attention recently, I think a related work section would benefit this paper a lot.\n> \n\nThank you for your suggestion. This sentiment was echoed by other reviewers and we will update the paper with a pertinent related works section.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ffQfGeCwM1", "reviewer": "Reviewer_wQ3r", "summary": "The paper offers a kernel-based approximation of Dense Associative Memory that allows for Hebbian encoding in a space of randomized basis functions. The main advantage when compared with the exact approach is that information concerning all patterns is shared in a single weight tensor, without requiring additional weights for each new pattern.\n\nThe authors provide some complexity results and bounds on the Euclidean deviation from the exact retrieved pattern in the case of exponential Dense Associative Networks (i.e. modern Hopfield networks). In a series of numerical experiments, the author show that the approximation breaks down for low values of the inverse temperature and for large number of patterns when compared with the number of basis functions.", "questions": "1) I find intuitively strange that the bound in Eq.13 depends on the absolute value of the energy instead of on a relative energy. Can you provide some intuition for this result?", "limitations": "The limitations of the proposed approximate method are adequately discussed.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) The paper addresses perhaps the greatest limitation of Dense Associative Memories with non-quadratic energy, namely the fact that they cannot compress the patterns into a single shared weight matrix. This has potentially great practical relevance for the implementation of these models in practical applications. Furthermore, it connects the theory of non-quadratic Dense Associative Memories with a very large body of theoretical research on Hebbian learning and classical Hopfield models.\n\n2) The proposed approximate algorithm is theoretically sound as it connects with important known results on kernel machines and feature expansions.\n\n3) The exposition is clear and it is relatively easy to follow even for non-specialists. \n\n4) The numerical analysis of the error profile of the approximation error is thorough and insightful, especially when interpreted in combination with the theoretical results.", "weaknesses": "1) The embedding of this paper in the existing literature is limited. Feature expansion methods have been studied for classical Hopfield and generalized models [1,2,3], and there are uncited existing papers connecting Dense Associative Memories and kernel methods [4]. It would also be useful to discuss the recent results connecting exponential Dense Associative Memories (i.e. modern Hopfield networks) with generative diffusion models [5], since as pointed out in the paper the connection provides an alternative way to learn the same energy function in a fixed synaptic structure. It could also be useful to discuss more theoretical results involving random features, for example [6] and [7].\nIt would be good to have this treatment organized in a proper Related Work section. \n\n2) While the approximation is based on a sound idea, its derivation is very informal. It would be very useful to derive the formula using variational techniques or other known systematic methods for deriving approximations. It could also be interesting to connect it with similar approximations in Gaussian Processes, since kernel feature expansions are commonly used for GPs.\n\n3) I am not convinced about the usefulness of the bound in Eq.12 in non-trivial regimes due to the exponential dependence on the energy. \n\n4) Given the simplicity of the proposed method and its similarities with known approaches such as [TODO], I am not convicted that the contribution is relevant enough for this conference.\n\nReferences:\n[1] Liwanag, Arnold, and Suzanna Becker. \"Improving associative memory capacity: one-shot learning in multilayer Hopfield networks.\" Proceedings of the 19th Annual Conference of the Cognitive Science Society. Vol. 442. 1997.\n[2] Barra, Adriano, Matteo Beccaria, and Alberto Fachechi. \"A new mechanical approach to handle generalized Hopfield neural networks.\" Neural Networks 106 (2018): 205-222.\n[3] Yilmaz, Ozgur. \"Machine Learning Using Cellular Automata Based Feature Expansion and Reservoir Computing.\" Journal of Cellular Automata 10 (2015).\n[4] Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models\n[5] Ambrogioni, Luca. \"In search of dispersed memories: Generative diffusion models are associative memory networks.\" arXiv preprint arXiv:2309.17290 (2023).\n[6] Negri, Matteo, et al. \"Random Feature Hopfield Networks generalize retrieval to previously unseen examples.\" Associative Memory {\\&} Hopfield Networks in 2023. 2023.\n[7] Negri, Matteo, et al. \"Storage and learning phase transitions in the random-features hopfield model.\" Physical Review Letters 131.25 (2023): 257301.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Improve embedding of this paper into existing literature\n\nThank you for your suggestions, we will update the paper with the Related Work section and will include the discussion of all the papers that you have suggested. As a side note, the reference [4] actually is cited in our submission, please see Ref [16]. Connection with diffusion, Ref [5] is a beautiful work, which we will be delighted to highlight. As well as the theoretical work on random features Refs [6], [7].\n\n> It would be very useful to derive the formula using variational techniques… It could also be interesting to connect it with similar approximations in Gaussian Processes…\n> \n\nWe thank the reviewer for these interesting suggestions and connections.\n\nOur presentation of the approximation was motivated by the simplicity of the derivation that highlights how the energy can be approximated with random features in a cleanly straightforward manner; we were hoping to highlight how easily this distributed representation of memories simplifies the energy function. However, after the derivation, we formally and precisely present how the energy descent can be performed with these random features in Algorithm 1, carefully controlling the peak memory usage and computation. Naively, the peak memory usage would have been $O(YD)$, while our carefully crafted algorithm only requires $O(Y+D)$ peak memory with the same outcome.\n\nHowever, we do think it is important to derive this approximation via other techniques, potentially highlighting other avenues for improvement.\n\nWe thank the reviewer for connecting our work to Gaussian processes. It is true that random features have been used for approximating Gaussian Processes, but the form of usage is targeted to a different application. Gaussian Processes are often used for supervising learning (either directly, or as part of a black-box derivative-free optimization), and the main bottleneck is the need to compute and invert the kernel gram matrix of the training points for any inference. With random features, we can instead perform Bayesian linear learning in the expanded feature space, obviating the kernel gram matrix computation and inversion.\n\nDenseAMs are often utilized for memory retrieval, which is  different than supervised learning (the main application of Gaussian Processes). However, this suggested connection by the reviewer can lead to interesting cross-contribution between the fields of Gaussian Processes and DenseAMs. This is very much in line with our goal in this paper to view DenseAMs through a lens of random features and kernel machines, bringing together two fields.\n\n> I am not convinced about the usefulness of the bound in Eq.12 in non-trivial regimes due to the exponential dependence on the energy.\n> \n\nIt is true that the divergence upper bound depends on the term $\\exp(\\beta E(\\mathbf{x}))$. However, note that, for the energy function defined in Eq (11), assuming that all memories and the initial queries are in a ball of diameter $1$, $E(\\mathbf{x}) \\leq \\frac{1}{2} - \\frac{\\log K}{\\beta}$, implies that $\\exp(\\beta E(\\mathbf{x})) \\leq \\exp(\\beta/2) / K$.\n\nAn important aspect of our analysis is that the bound is query specific, and depends on the initial energy $E(\\mathbf{x})$. As discussed above, this can be upper bounded uniformly, but our bound is more adaptive to the query $\\mathbf{x}$.\n\nFor example, if the query is initialized near one of the memories, while being sufficiently far from the remaining $(K-1)$ memories, then $\\exp (\\beta E(\\mathbf{x}))$ term can be relatively small.\n\nMore precisely, with all memories and queries lying in a ball of diameter $1$, let the query be at a distance $r < 1$ to its closest memories, and as far as possible from the remaining $(K-1)$ memories. In this case, the initial energy $E(\\mathbf{x}) \\approx -(1/\\beta) \\log [\\exp(-\\beta r / 2) + (K-1) \\exp(-\\beta/2)]$, implying that\n\n$$\n\\exp(\\beta E(\\mathbf{x})) \\approx \\frac{\\exp(\\beta r / 2)}{\\Big[1 + (K-1)\\exp(-\\beta(1 - r)/2)\\Big]} \\leq \\exp(\\beta r / 2)\n$$\n\nFor sufficiently small $r < 1$, the above quantity can be relatively small. If, for example, $r \\sim O(\\log K)$, then $\\exp(\\beta E(\\mathbf{x})) \\sim O(K^{\\beta/2})$, while $r \\to 0$ gives us $\\exp(\\beta E(\\mathbf{x})) \\to O(1)$. This highlights the adaptive query-dependent nature of our analysis.\n\nSo it is not directly clear why this is not a “non-trivial regime”. We believe that this form of analysis is novel, and highlights the effect of the different quantities of interest in this formulation (such as the effect of the number of memories, energy descent steps, random features, initial particle energy). We accept that this upper bound might not be the tightest. However, that limitation does not necessarily make the analysis “trivial”.\n\n> Given the simplicity of the proposed method and its similarities with known approaches such as [TODO]…\n> \n\nWe would be happy to elaborate on this comment if the reviewer kindly specifies the “[TODO]” approaches. We do believe, however, that our approach is novel and that our contribution is relevant to this conference. We will add a Related Work section to better differentiate it from existing prior work.\n\n> I find intuitively strange that the bound in Eq.13 depends on the absolute value of the energy instead of on a relative energy. Can you provide some intuition for this result?\n> \n\nThis result uses the form of the energy, given by Eq (11), which assumes that the zero-energy state is chosen such that the sum of the exponents under the logarithm is equal to 1. Only the difference of the energies appears in Eqs (12,13), but this difference is implicit, given the (arbitrary) choice of the reference point made in Eq (11).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JefUAe9HkR", "reviewer": "Reviewer_9NBh", "summary": "This paper introduce an iterative random feature Dense Associative Memory Model (DenseAM).\nIt is a kernel approximation of the standard DenseAMs using random feature decomposition and approximation. \nThe authors term this approach to DenseAMs as distributed representation/formulation of memory (DrDAM).\n\nTheoretically, they analyze the time complexity of the proposed method (Thm1) and the approximation error (Thm2), both benchmarked against the standard DenseAM (MrDAM). \nExperimentally, they evaluate the approximation accuracy of DrDAM's energies and gradients, defined as the MAE difference between DrDAM and MrDAM, and the retrieval accuracy of DrDAM. \nImportantly, their analysis of DrDAM considers its iterative nature, distinguishing their contribution from prior works.\n\nIn sum, they address important research questions and their approach is natural and intuitive based on recent advances in the random feature kernel trick.", "questions": "* ```line109```: why you call the number of updates as *layers*? Are you recurrently passing the output as input to the same network or the network really has many layers? For example, recurrent layer is RNN sense is the later. \n\n\n* ```Proposition 1,2,3```: what is peak memory? why we should care about it?\n\n* ```Time Complexity```: I appreciate the analysis of the computational complexity of the proposed method. From my view, this proposal is a special case of [Hu2024] with $L=1$ (where $L$ is the sequence length in their analysis). [Hu2024] provides a characterization of all sub-quadratic (efficient) variants of the modern Hopfield model. Essentially, your proposal is an efficient approximation to the softmax DenseAMs. Hence, the relevance holds. Can you discuss how your proposal fits into the results of [Hu2024]?\n  \n  * [Hu2024] Hu, J.Y.C., Lin, T., Song, Z. and Liu, H., 2024. On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis. arXiv preprint arXiv:2402.04520.\n\n\n* ```line255, Exp Observation 2```: This observation is a bit counterintuitive. Normally, large $\\beta$ means low-temperature region and leads to more stable/accurate retrieval, e.g., infinity $\\beta$ leads to argmax-retrieval. Why random DrDAM shows otherwise?  \n\n\n\n* ```Fig3```: Intuitively, why larger $\\beta$ needs larger $Y$?\n\n* ```line303```: What's the point of approximating energies and update dynamics? Shouldn't the significance lie in the approximation error of retrieval?\n\n* I am wondering if you have explored the learning aspect of the proposed method. It is known that many DenseAMs are connected to transformer attention and can be used as a learning model or layer. Can you explore this part a bit as in [17]? If not, please explain why.\n\n* Can you kindly remind me which part of this work supports the claim \"making it possible to introduce new memories without increasing the number of weights\"?", "limitations": "There is a limitation section but no broader impact or impact statement expect in the checklist.\n\n\nAppendix A of the draft acknowledges that the experimental explorations are limited. However, it would benefit from discussing comparisons with baselines and including some vital ablations. This would help clarify the contribution and soundness of the proposed method. See above for other limitations.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* **Originality**: This paper expands our understanding of Dense Associative Memory Models (DenseAMs) by presenting a random feature DenseAM, termed DrDAM. The idea of DrDAM is novel and beneficial to the ML and associative memory community.\n\n* **Significance**: While the idea of random feature DenseAM is not entirely new, this work delves deeper than most prior studies. For example, to the best of my knowledge, there is nothing as concrete as the iterative Algorithm 1 presented in prior works. This represents a significant and solid step forward for the community, and I appreciate the effort.\n\n* **Theoretical Contribution**: This paper provides an efficiency and approximation analysis of DrDAM.\n\n* **Experimental Contribution**: They explore some aspects of DrDAM, including the approximation of energies and gradients and the approximation ability of DrDAM. Reproducible code is also provided.", "weaknesses": "## Summary of Weaknesses\n\nOverall, this paper presents a good idea, but it seems rushed, which affects the contribution of an otherwise very interesting work. Regardless of the final decision, I hope the authors find my comments helpful in further refining their draft.\n\nThere are a few areas that could benefit from further improvement and clarity:\n\n* **Experiments:** The current experimental results would be strengthened by including comparisons with established baselines and more ablation studies.\n* **Clarity:** Some of the theoretical results are difficult to interpret due to minor typos and a need for increased mathematical clarity.\n* **Motivation:** The motivation and problem statement could be articulated more convincingly. Even after multiple readings of the intro, it remains unclear if distributed representation is truly parameter-efficient beyond the nonparametric sense.\n* **Related Works:** Additionally, while not critical, the idea of Random Feature DenseAM (and Kernel DenseAM) has been discussed in prior works. The related discussion in this paper could be expanded to better position the contribution within the existing literature. For examples:\n  * ```Random Feature DenseAM``` Random Feature Hopfield Networks generalize retrieval to previously unseen examples https://openreview.net/forum?id=bv2szxARh2)\n  * ```Random Feature DenseAM``` Nonparametric Modern Hopfield Models https://arxiv.org/abs/2404.03900\n  * ```Kernel DenseAM``` Kernel Memory Networks: A Unifying Framework for Memory Modeling  https://arxiv.org/abs/2208.09416\n  * ```Kernel DenseAM``` Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models  https://arxiv.org/abs/2404.03827\n  * ```Kernel DenseAM``` Bridging Associative Memory and Probabilistic Modeling https://arxiv.org/abs/2402.10202\n\n\n\n**Note:** I have tried my best to evaluate this paper. I spent much more time on this review than on my previous ones because I like this paper. Still, I might have missed something. Please correct me if I am wrong with fair justifications. I am open to changing my opinion and raising the score.\n\n---\n\n## Major: My main concern with this paper is its soundness and inadequate experimental evidence\n\n### General\n\n\n* ```line23:``` \"Memory representation\" is a strange term for me. If you are referring to the way of encoding memory patterns onto the energy landscape, isn't it \"memory encoding\"? Representation generally involves learning, and to my understanding, there is no learning here.\n\n  >Thus, in situations when the set of the memories needs to be expanded by introducing new patterns one must introduce additional weights.\n\n  A side comment: this statement implies nonparametric, as suggested in [17].\n\n* ```distributed representation```: I find the description of distributed representation vague. With more memories, $K$ increases, resulting in more degrees of freedom in $\\mathbf{T}$. You can say the total number of entries in $\\mathbf{T}$ is fixed, but not the number of parameters, unless you clearly define \"parameters\" differently. The current draft makes it difficult to parse the soundness.  I believe the idea of distributed representation deserves more elaboration. The current draft seems nonparametric to me.\n\n  In my current review, I assume what is stated in lines 29-30 is correct.\n\n* ```Sec3```: Section 3 is hard to follow due to typos and the lack of clarity.\n\n* ```Missing Broader Impacts```: The authors didn't discuss both potential positive and negative societal impacts except in the checklist. My understanding is that this discussion needs to be included in the main text or the appendix, as the checklist is not considered part of the paper.\n\n---\n\n### Theory\n\n\n* ```line92```: Eqn. (6) is hard to follow without clearly defined $S,s$. \n\n  I suppose $S:\\mathbb{R}^d\\times \\mathbb{R}^d\\to \\mathbb{R}$ which makes $s\\in\\mathbb{R}$ a scalar realization of $S$?\n\n\n* ```No fixed point convergence results```: Per my understanding, DenseAMs are energy models with memories stored in their local minima. Memory retrieval is conducted through energy minimization. This setting requires convergence between local minima and fixed points of retrieval updates, such as the convergence results of [Ramsauer2020,Hu2023]. Otherwise, there may be unbounded retrieval error due to the mismatch between local minima and fixed points of retrieval updates. Specifically, I believe lines 106-110 are at best ambiguous.\n\n  * [Ramsauer2020] Hopfield Networks is All You Need. Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G.K., and Greiff, V., 2020. arXiv preprint arXiv:2008.02217.\n  \n  * [Hu2023] On Sparse Modern Hopfield Model. Hu, J.Y.C., Yang, D., Wu, D., Xu, C., Chen, B.Y., and Liu, H., 2023. Advances in Neural Information Processing Systems, 36.\n\n* ```Theorem 1```: I feel Thm1 may be incorrect. Could you elaborate more on this?\n\n  * **My understanding:** Let $L$ be the number of updates, $K$ be the number of stored memories, $D$ be the memory dimension, and $Y$ be the feature space dimension. DrDAM improves time complexity from $O(LKD)$ to $O(D(Y K + L(Y + D))$, and improves peak memory from $O(KD)$ to $O(Y+D)$.\n  * **Comment1:** $O(D(Y K + L(Y + D))$ is clearly a typo and makes the result hard to parse.\n  * **Comment2:** Without specifying the relationships between $L$, $K$, $D$, and $Y$, it's hard to tell if this is truly an improvement. I can easily think of counterexamples.\n\n  Given these, can you kindly elaborate more on the significance of thm1?\n\n\n* ```Theorem 2```: Eqn. (12) is strange. Is there any guarantee ensuring $\\alpha L(1+2K\\beta e^{\\beta/2}) < 1$? If not, it doesn't make sense that more updates would result in larger error. Perhaps this is related to the missing fixed point convergence?\n\n---\n\n### Experiments\n\n* ```No Comparison to existing works:``` there is no baseline compared. \n\n* ```No efficiency evaluation1:``` Please include ablation studies on changing $L,K,D,Y$ to verify Thm1. \n\n* ```No efficiency evaluation2:``` Please also compare the efficiency with other methods, including linear, top-K, random feature, and random masked from [17], as well as dense [Ramsauer2020], sparse [Hu2023], and generalized sparse [Wu2023] MHNs. For example, the current draft needs some figures similar to Fig. 4 of [17] to justify the efficiency. Please do whatever makes sense to you. For instance, you can pick just two out of [Ramsauer2020, Hu2023, Wu2023] since they share similar structures.\n\n  * [Ramsauer2020] Hopfield Networks is All You Need. Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G.K., and Greiff, V., 2020. arXiv preprint arXiv:2008.02217.\n  \n  * [Millidge2022] Universal Hopfield Networks: A General Framework for Single-Shot Associative Memory Models. Millidge, B., Salvatori, T., Song, Y., Lukasiewicz, T., and Bogacz, R., 2022, June. In International Conference on Machine Learning (pp. 15561-15583). PMLR.\n  \n  * [Wu2023] Stanhop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Prediction. Wu, D., Hu, J.Y.C., Li, W., Chen, B.Y., and Liu, H., 2023. arXiv preprint arXiv:2312.17346.\n  \n  * [Hu2023] On Sparse Modern Hopfield Model. Hu, J.Y.C., Yang, D., Wu, D., Xu, C., Chen, B.Y., and Liu, H., 2023. Advances in Neural Information Processing Systems, 36.\n\n\n\n* ```Compare with existing kernel DenseAMs.``` Also, a direct comparison with existing kernel methods is also necessary. For example,\n  * Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models. Wu, D., Hu, J.Y.C., Hsiao, T.Y., and Liu, H., 2024. arXiv preprint arXiv:2404.03827.\n  \n  * Kernel Memory Networks: A Unifying Framework for Memory Modeling. Iatropoulos, G., Brea, J., & Gerstner, W., 2022. Advances in Neural Information Processing Systems, 35, 35326-35338.\n  \n  * Bridging Associative Memory and Probabilistic Modeling. Schaeffer, R., Zahedi, N., Khona, M., Pai, D., Truong, S., Du, Y., Ostrow, M., Chandra, S., Carranza, A., Fiete, I.R., and Gromov, A., 2024. arXiv preprint arXiv:2402.10202.\n\n---\n\n## Minor\n\n* ```Inadequate Related Work Discussion```: A paragraph discussing related works is given at the end of the introduction. However, I feel it could be made more comprehensive to provide more background on the evolution of ideas and existing works in this field. At least, I feel the current draft is hard for a non-expert in DenseAMs to follow. Please see the following points.\n\n* ```line38:``` I believe here can be benefited by including more comprehensive references. There are other recent works showing exponentially large memory storage capacity in various settings and dense associative memory (or modern Hopfield) networks/models. For examples: (I am not sure of their exact relevance, so I will leave it to the authors to decide whether they should be included and discussed.)\n\n   * Hopfield Networks is All You Need. Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G.K., and Greiff, V., 2020. arXiv preprint arXiv:2008.02217.\n  * Kernel Memory Networks: A Unifying Framework for Memory Modeling. Iatropoulos, G., Brea, J., & Gerstner, W., 2022. Advances in Neural Information Processing Systems, 35, 35326-35338.\n  * On Sparse Modern Hopfield Model. Hu, J.Y.C., Yang, D., Wu, D., Xu, C., Chen, B.Y., and Liu, H., 2023. Advances in Neural Information Processing Systems, 36.\n  * Stanhop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Prediction. Wu, D., Hu, J.Y.C., Li, W., Chen, B.Y., and Liu, H., 2023. arXiv preprint arXiv:2312.17346.\n  * Bridging Associative Memory and Probabilistic Modeling. Schaeffer, R., Zahedi, N., Khona, M., Pai, D., Truong, S., Du, Y., Ostrow, M., Chandra, S., Carranza, A., Fiete, I.R., and Gromov, A., 2024. arXiv preprint arXiv:2402.10202.\n  * Sparse and Structured Hopfield Networks. Santos, S., Niculae, V., McNamee, D., and Martins, A.F., 2024. arXiv preprint arXiv:2402.13725.\n  * On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis. Hu, J.Y.C., Lin, T., Song, Z., and Liu, H., 2024. arXiv preprint arXiv:2402.04520.\n  * Outlier-Efficient Hopfield Layers for Large Transformer-Based Models. Hu, J.Y.C., Chang, P.H., Luo, R., Chen, H.Y., Li, W., Wang, W.P., and Liu, H., 2024. arXiv preprint arXiv:2404.03828.\n\n\n* ```line46:``` Similarly, here can be benefited by including more recent references\n  > DenseAM family [...] \n\n* ```line51```: A similar motivating question is asked and explored in [17] from a kernel regression perspective. I agree this paper contributes something different and even beyond [17]. However, given the similarity of aims between the two, the current draft should:\n  1. State the overlaps between the two works (both use a kernel approach to DenseAMs, and...).\n  2. State the clear distinctions between the two works (both use a kernel approach to DenseAMs, but...).\n\n  Such discussion will help readers parse the contributions of this work, which is currently lacking.\n\n  [17] Jerry Yao-Chieh Hu, Bo-Yu Chen, Dennis Wu, Feng Ruan, and Han Liu. Nonparametric modern hopfield models. arXiv preprint arXiv:2404.03900, 2024. URL https://arxiv.org/pdf/2404.03900.pdf.\n \n\n* ```line92```: \n  > those results have been recently applied to associative memory [15].\n\n  I might have missed something, but it would be better to make the discussion of prior work more complete if it's presented in its current form (e.g., a paragraph highlighting the novelty and contributions benchmarked against existing works). The application of the kernel trick to associative memory is not new. While [16,17] are discussed right after [15], I feel it's better to cite them together as [15,16,17]. Additionally, there are two papers related to the kernel trick in associative memory, which I have attached below. Again, I am not sure of their exact relevance, so I will leave it to the authors to decide whether they should be included and discussed.\n\n  - Iatropoulos, G., Brea, J., & Gerstner, W. (2022). Kernel memory networks: A unifying framework for memory modeling. Advances in neural information processing systems, 35, 35326-35338.\n  \n  -  Schaeffer, R., Zahedi, N., Khona, M., Pai, D., Truong, S., Du, Y., Ostrow, M., Chandra, S., Carranza, A., Fiete, I.R. and Gromov, A., 2024. Bridging Associative Memory and Probabilistic Modeling. arXiv preprint arXiv:2402.10202.\n\n* ```line97```: \n  > Another paper [17] uses kernels for studying the sparse modern Hopfield network. \n\n  This is incorrect. \n\n  As stated in their abstract, [17] presents a general framework (referred to as nonparametric) to analyze and design modern Hopfield networks. The sparse network is just a special case of their framework. Additionally, [17] has already introduced the construction of random feature HMNs. While this construction lacks detailed analysis, which is a limitation they acknowledged, it would be more accurate to say that the submitted draft serves as a strong companion to [17] with rigorous theoretical and empirical results. I understand that the authors are not obliged to treat arXiv preprints (unpublished papers) too seriously, but it is better to give accurate credit to existing works when possible. To clarify, I am very happy to see this draft improves the results/proposal of [17] with detailed analysis, including multiple retrieval updates.\n\n* I did not check the proofs line by line. However, I had a quick skim through them and found some typos and areas for improvement. Please do another round of proofreading if possible.\n\n\n---\n\n### Update 2024/08/07: raise score from 4 -> 5 -> 6 -> 7", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough and insightful evaluation of our work. We are glad you found it interesting and beneficial to the ML community! \n\nWe will add a Related Work section in which we will review the results of\n\n- Hu et al., Nonparametric Modern Hopfield Models\n- Wu et al., Uniform Memory Retrieval\n\nwhich are already referenced in our paper, in addition to\n\n- Negri et al., Random Feature Hopfield Networks generalize…\n- Hu et al., On Sparse Modern Hopfield Model\n- Wu et al., Stanhop\n- Iatropoulos et al., Kernel Memory Networks\n\nand other suggested papers. We will also include a Broader Impact statement. Below, we do our best to address your comments within the character constraints of the rebuttal.\n\n> …results would be strengthened by including comparisons with established baselines and more ablation studies.\n> \n\nWe conducted numerical experiments to validate our theorems (see 1-page pdf). Note that our main goal is to approximate the energy and trajectory of a standard DenseAM (MrDAM) using Random Features. Thus, MrDAM is the “baseline” for our method.\n\n> \"Memory representation\" is a strange term for me…\n> \n\nWe use the word representation in a more colloquial sense - the description in terms of something. Similarly to Fourier representation, momentum representation in physics, etc.\n\n> You can say the total number of entries in $T$ is fixed, but not the number of parameters, unless you clearly define \"parameters\" differently…\n> \n\nWe define the number of parameters as the number of entries in $T$. We will include additional elaboration on these aspects in the revised paper.\n\n> I feel Thm1 may be incorrect\n> \n\n(Re: Comment 1) We apologize for the typo. The bound should be $O(D(YK + L(Y+D)))$; the version in the paper is missing a closing bracket around $O(\\cdot)$. Other than that, the bound is as stated, with the $DYK$ term coming from the `ProcMems` subroutine and the $LD(Y+D)$ term coming from the $L$ `GradComp` invocations. See the proof of Thm 1 in App E1.\n\n(Re: Comment 2) Thm 1 quantifies the complexity of procedures in Alg 1. We do not claim improvement over standard MrDAM for the precise reason stated by the reviewer regarding the choices of $D, Y, K, L$.\n\nThese results highlight that energy descent with DrDAM requires computation and memory that only depends on $D$ and $Y$. Together with Thm 2 and Cor 1, we characterize where the energy descent divergence between MrDAM and DrDAM can be bounded with a choice of $Y$ that only depends on $D$ (and other parameters in the energy) but not $K$.\n\n> Is there any guarantee ensuring $\\alpha L (1 + 2K \\beta e^{\\beta/2}) < 1$?\n> \n\nThere is no guarantee, as stated in Thm 2. Denoting this term with $\\delta = \\alpha L(1 + 2K \\beta e^{\\beta/2})$, the upper bound contains a term of the form $\\left(\\frac{1 - \\delta^L}{1 - \\delta}\\right)$. If $\\delta < 1$, it is clear that the numerator grows with $L$, providing a worse upper bound. However, if $\\delta > 1$, $\\frac{1 - \\delta^L}{1 - \\delta}$ can be equivalently written as $\\frac{\\delta^L - 1}{\\delta - 1}$, where the $\\delta^L$ term grows with $L$, still having the same effect of larger divergence upper bound with larger $L$.\n\n> **Re: proof for “fixed point convergence results”**\n> \n\nThe proof is standard in DenseAM literature (see appendices in [paper1](https://arxiv.org/abs/2008.06996) or [paper2](https://arxiv.org/abs/2107.06446)). Consider our Eq (11) for the energy as an example, whose dynamics is described by the following eqs ($i=1...D$)\n\n$$\n\\tau \\frac{dx_i}{dt} = - \\frac{\\partial E}{\\partial x_i}.\n$$\n\nFor this reason, the energy monotonically decreases on the dynamical trajectory\n\n$$\n\\frac{dE}{dt} = \\sum\\limits_{i=1}^D \\frac{\\partial E}{\\partial x_i} \\frac{dx_i}{dt} = -\\tau \\sum\\limits_{i=1}^D \\Big( \\frac{dx_i}{dt}\\Big)^2\\leq 0.\n$$\n\nThe energy in Eq (11) is bounded from below, by $-\\log(K)/\\beta$, since the argument of the logarithm is bounded from above by $K$. Thus the energy descent dynamics has to stop sooner or later when $\\frac{dx_i}{dt}=0$, which defines the fixed points. Thus, local minima of the energy correspond to the fixed points of the dynamics.\n\n> …include ablation studies on changing $L,K,D,Y$ to verify Thm1.\n> \n\nThis is a great suggestion. However, note that Thm 1 is a tight analysis of Alg 1, counting the $D$- and $Y$-dimensional vector initializations, additions, and dot-products. So we did not think such an ablation study would provide additional insight.\n\n> Why larger $\\beta$ needs larger $Y$?\n> \n\nThe reviewer is correct that large $\\beta$ (low-temperature) leads to more stable and accurate retrieval  by approaching the argmax-retrieval in standard DenseAMs. However, this regime is specifically difficult for random features. Consider the L2 distance based energy in Eq (11):\n\n$$\nE(\\mathbf{x}) = -\\frac{1}{\\beta} \\log \\sum_{\\mu} \\exp\\left(-\\frac{\\beta}{2} \\| \\boldsymbol{\\xi}_\\mu - \\mathbf{x} \\|^2 \\right). \n$$\n\nAs $\\beta$ increases, the $\\exp(\\cdot)$ term, which we approximate with random features, gets skewed to the extremes across the $K$ memories, with the $\\exp(\\cdot) \\to 0$ for all but the closest memory. This makes the RF approximation harder, requiring larger $Y$ for better approximation.\n\n> which part of this work supports the claim that \"making it possible to introduce new memories without increasing the number of weights\"?\n> \n\nProp. 5 shows how to update weights $\\mathbf{T}$ with a new memory $\\boldsymbol{\\xi}$ without increasing the number of weights:\n\n$$\n\\mathbf{T} \\gets \\mathbf{T} + RF(\\tau, \\boldsymbol{\\xi}), \n$$\n\ntaking $O(DY)$ time and $O(D+Y)$ memory.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all reviewers for their thoughtful feedback. We are honored that our work has been recognized as addressing “the greatest limitation of Dense Associative Memories with non-quadratic energy” [wQ3r] and as making a “significant and solid step forward for the community” [9NBh]. We are also grateful that reviewers have acknowledged the clarity and accessibility of our paper [xsUY, B4qp, wQ3r].

Reviewers have identified several areas in our presentation that need improvement:

1. **A more complete list of related works** [wQ3r, 9NBh, B4qp]**.**  We appreciate the reviewers’ suggestions for additional relevant works. We have reviewed the related work suggested by reviewers and find them all relevant, and will enhance the “Related Works” section accordingly to more thoroughly embed our work into the context of existing studies.
2. **Improve the motivation for the method** [xsUY, 9NBh]. We understand that reviewers are looking for compelling empirical reasons to use the distributed representation for DenseAMs over the traditional memory representation, particularly in terms of parameter efficiency or time complexity. We hope that our additional experiments show that information compression is indeed possible using DrDAM; however, we want to emphasize that the main message of our paper is to show and characterize how we can uncouple the actual memory patterns from the definitions of (1) the energy and (2) the full memory-retrieval dynamics of DenseAMs. 
3. **Additional experiments** [xsUY, 9NBh, B4qp] We have run additional experiments and included them in the attached 1-page PDF, further validating the theory and practicality of our method:
    - Fig (a): We designed Fig 1 of the original submission as an illustration of the method, but Reviewer xsUY astutely pointed out that in this experiment our distributed representation method (DrDAM) used more parameters than the memory representation for DenseAMs (MrDAM). We have thus updated that experiment to store and retireve 20 images from TinyImagenet into both DrDAM and MrDAM configured at the same $\beta$, showing that DrDAM can successfully compress information in the stored patterns. Full details are provided in the caption and app. C of the orig. submission
    - Fig (b): In Fig 2 of the original submission we analyzed the error between DrDAM and MrDAM as a function of $Y$ (the size of the distributed tensor $\mathbf{T}$), $D$ (the size of queries and stored patterns), and $\beta$ (the inverse temperature). We additionally performed this error analysis as a function of how many patterns $K$ are stored in the memory. See more details in the caption.
    - Fig (c): Here we verify the tightness of the error bound (a function of $\frac{1}{\sqrt{Y}}$ ) in Thm. 2 on top of the empirical curves of Fig 2. We will update the right part of Fig 2 of the original submission with this version upon acceptance.

We have addressed each reviewer’s individual questions and concerns below. We respectfully ask each reviewer to consider increasing their score if concerns have been satisfactorily addressed.

Meta-review: The present study proposes a kernel approximation of the dense associative memory. Connecting the random feature approximation and the dense associative memory is novel. After comprehensive author-reviewer discussions, reviewers have carefully checked the mathematical derivations in the paper and the authors' replies have addressed most of the concerns. Therefore I recommend accepting the present paper. Meanwhile, reviewers pointed out the original manuscript hasn't systematically compared with related work and fully discussed its limitations. Please revise the manuscript based on the reviewers' comments.
Decision: Accept (poster)