Provably Optimal Memory Capacity for  Modern Hopfield Models:   Transformer-Compatible   Dense Associative Memories as Spherical Codes
Authors: Jerry Yao-Chieh Hu
Dennis Wu
Han Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Modern Hopfield Models
Dense Associative Memory
Transformer
Transformer Representation Learning
Memory Capacity
Foundation Model
Primary area: neuroscience_and_cognitive_science
TL;DR: We enhance Modern Hopfield Networks with a kernelized approach to improve memory storage and retrieval, achieving optimal capacity and efficiency in sub-linear time.

Abstract: We study the optimal memorization capacity of modern Hopfield models and Kernelized Hopfield Models (KHMs), a transformer-compatible class of Dense Associative Memories.
We present a tight analysis by establishing a connection between the memory configuration of KHMs and spherical codes from information theory. 
Specifically, we treat the stored memory set as a specialized spherical code.
This enables us to cast the memorization problem in KHMs into a point arrangement problem on a hypersphere.
We show that the optimal capacity of KHMs occurs when the feature space allows memories to form an optimal spherical code.
This unique perspective leads to: 
1. An analysis of how KHMs achieve optimal memory capacity, and identify corresponding necessary conditions. 
Importantly, we establish an upper capacity bound that matches the well-known exponential lower bound in the literature. 
This provides the first tight and optimal asymptotic memory capacity  for modern Hopfield models.
2. A sub-linear time algorithm $\mathtt{U}\text{-}\mathtt{Hop}$+ to reach KHMs' optimal capacity. 
3. An analysis of the scaling behavior of the required feature dimension relative to the number of stored memories.

These efforts improve both the retrieval capability of KHMs and the representation learning of corresponding transformers.
Experimentally, we provide thorough numerical results to back up theoretical findings.

Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatttee Dense Associative Memories as Spherical Codes
Jerry Yao-Chieh Hu*
Dennis Wu*
Han Liu
'Center for Foundation Models and Generative AI, *Department of Computer Science, DDpartment of Statistics and Data Science, Northwestem University, Evanston, IL 60208, USA (jhu, hibb) @u www.wwetteteeeeeeemmm.. edu, hanl hanliughorthhesttem..cmm
Abstract
We study the optimal memorization capacity of modern Hopfield models and Kernelized Hopfield Models (KHMs), a transformer-compan compatible class of Dense Associative Memories. We present tight analysis by establishing a connection between the memory configuration of KHMs and spherical codes from information theory. Specifically, we treat the stored memory set as a specialized spherical code. This enables us to cast the memorization problem in KHMs into point arrange- ment problem on hypersphere. We show that the optimal capacity of KHMs occurs when the feature space allows memories to form optimal spherical code. This unique perspective leads to: (i) An analysis of how KHMs achieve optimal memory capacity, and identify corresponding necessary conditions. Importantly, we establish an upper capacity bound that matches the well-known exponential lower bound in the literature. This provides the first tight and optimal asymptotic memory capacity for modern Hopfield models. (ii) A
time algorithm U-Hop+ to reach KHMs' optimal capacity. (iii) An analysis of the scaling behavior of the required feature dimension relative to the number of stored memories. These efforts improve both the retrieval capability of KHMs and the representation learn- ing of corresponding transformers. Experimentally, we provide thorough numerical results back up theoretical findings.
Introduction
We study the optimal memorization capacity of Kernelized modern Hopfield Models (KHMs) [Wu al., 2024a], propose a sublincar-time algorithm achieve it, and analyze parameter selection for these models. KHMs belong to a class of transformer-comparib Dense Associative Memory [Krotov and Hopfield, 2021, 2016] known Modern Hopfield Models (MHMs) [Wu et al., 2024a,b, Hu et al., 2024a, 2023, Ramsauer et al., 2020]. The defining characteristics of these models include their super-linear memory capacity and strong connection to transformer attention mechanisms [Vaswani et al., 2017]. The former makes them interesting models for associative memory, and the latter makes them versatile transformer-compatibe backbones with diverse empirical successes [Burns, 2024, Burns and Fukai, 2023, Hu et al., 2024a,c, Xu et al., 2024, Wu et al., 2024a,b, Hoover et al., 2024b, Seidl et al., 2022, Fürst et al., 2022]. However, one major limitation of MHMs is their reliance on the quality of memory distribution for effective pattern storage and retrieval [Wu et al., 2024a, Sec. 1].
Studying this limitation in these models fundamental and of practical importance. One one hand, prevents MHMs from functioning as full full-fledged content-addressall memory models. On the other hand, it implies that the representation learning ability of current transformer attention [Vaswani et al., 2017] is suboptimal [Wu et al., 2024a, Thm. 3.1]. Addressing this issue benefits both computational
Equal contribution. Code is available GitHub. Latest version is arXiv.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

neuroscience and large foundation model research [Bietti et al., 2024, Krotov, 2023, Kozachkov et al., 2023, Cabannes et al., 2023, Hoover et al., 2023]. Kernelized modern Hopfield Models (KHMs) [Wu et al., 2024a] alleviate this issue by storing memories in the kernelized feature space. A key advantage of KHMs is their ability to reposition memories in the feature space, resulting in larger storage capacity. However, despite strong empirical performance, their capacity still lacks an optimal guarantee [Wu et al., 2024a, Sec. 5]. In this work, we close this gap by establishing the optimality of KHMs' memory capacity and presenting sublinear-time algorithm to achieve it.
Let E == [E.. Ear] E RdxAAl be a set of memory patterns where each column (indexed by y (M) represents memory En E Rd and let IRd be the input query. The Hopfield models (Hopfield, 1982] are energy-based associative memory models, which store memories on the local minima of their energy functions. They retrieve a pattern by iteratively updating the query xf - x'+1 with its update rule Txx),, for some & E {0, I,... This update rule converge to a fixed point xt, defined by x¹ T(x*). x² is the retrieved pattern" based on initial query z..
Explicitly, iteratively updating x with T is defined as a process of minimization to an energy function E(r). For example, the Modern Hopfield Model [Ramsauer et al., 2020] has the energy function:
1
E(x)= =
2 (zz x) + Ise (3, (3,Exx)
(1.1)
where (3) == log E expl { (CCCP) [Yuille and Rangarajan, 2001], (1.1) is monotonically decreased by an iterative update rule
})) with some B > 0. With the Concave-Conwe Procedure
+ T(a)) = E Softmax x²)
(1.2)
This design boosts MHMs to store exponentially (in pattern dimension d) many memories compared to the linear capacity of the classic Hopfield model [Hopfield, 1982]. also provides a model-based interpretation of the transformer attention mechanism [Wu et al., 2024a,b, Hu et al., b024a,b, 2023, Ramsauer et al., 2020]. However, their retrieval accuracy and memory capacity hinge on the quality of the stored memory set [Wu et al., 2024a, Sec. 1], and hence are suboptimal in most scenarios.
To be concrete, for retrieving the y-th memory (μ4 E [M), the retrieval error of MHM exponentially suppressed by the pattern separation: Aμ == (En, Eu) maxe,ra (E.., Ep.) ([Wu et al., 2024a, Eqn. 1.3] or [Hu et al., 2023, Eqn. 2.7I). This Ay-dependence in MHM retrieval accuracy also manifests the A,,depeedennce in memory capacity. To see this, recall that the standard memory capacity is a high-probability bound based on thresholding the separation A, for each pattern [M] to determine storage and retrieval (Section 2). Explicitly, storing pattern requires its separation to exceed a threshold that decreases with the minimal separation: Amin == min [M] Ap- Namely, larger Amin leads to larger capacity (Appendix B. Thus, the capacity depends on Amin- Yet, Amin depends on the stored memories E. This E-dependence makes the capacity suboptimal.
Wu et al. [2024a] relax such limitation by introducing a kernel as a learnable similarity measure, using stored memory patterns as training data to enhance memory capacity. Specifically, they propose the Kernelized Modern Hopfield Model (KHM) defined by following update rule and energy function:
r To = E Softmax x)),
Ex(xx) =
1 - x) Ise (8, x)),
(1.3)
where the kernel IC(,,)) = (9()) (()) Rdd x Rd + R is associated with a learnable feature map & Rd + Rs, Here, IC(:-) acts column- on matrix: K(EE = [(K(EE x) = (E())),), (x)) M E M Importantly, KHMs shift the dependency on Amin to A 9 min with
A min [E[M]]
min 4 where A KC (EnsER) v,
max K. (Ev,
Notably, A is learnable and parameterized via L. Wu al. [2024a] point out that with (zz) Wx, where W Be finding suitable & that maximizes Amin benefits memory storage. This construction of & preserves key MHM properties, such as accurate [Wu et al., 2024a, Lemma 2. I] and consistent [Wu al., 2024a, Thm 2.1] retrieval. However, direct maximization of A is
2x= corresponds either to one of the memories or to a fuezy combination of them. Please see [Ramsauer et al., 2020, Sec. A.1.5] for an informal discussion, [Wu et al., 2024a, Sec. 1] for further discussion, and [Santos et al., 2024, Wu et al., 2024a] for conditions of exact retrieval through sparsity [Wu al., 2024b, Hu et al., 2023].

---

challenging due to its max-min nature. To circumvent, Wu et al. [2024a] propose a surrogate loss to maximize A on average [Wu et al., 2024a, Def. 2.2]. As a result, their approach achieves strong empirical results in memory retrieval for MHMs and supervised learning for transformer models.
Nevertheless, maximizing A on average, rather than A min' raises questions about how their surrogate loss benefits memory storage. Moreover, the impact of A min on memory capacity lacks a clear analytical characterization, and no theoretical analysis confirms whether maximizing A min leads to optimal memorization capacity.
In this paper, we address these questions from the perspective of (optimal) spherical codes from information thoery [Delsarte et al., 1991]. A spherical code is a set of points (vectors) distributed on the surface of hypersphere, and an optimal spherical code is when the minimum angular distance between any two points is maximized. In other words, optimal spherical codes aim to spread the points as evenly as possible over the surface of the sphere. This aligns with the intuition behind KHM increasing average separation between stored memories improves memory capacity. Therefore, we treat the stored memory pattern set as a spherical code (Definition 2.3). and require this spherical code to satisfy the well-separatin condition [Hu et al., 2023, Thm 3.1]. We term this spherical code as memory code. Surprisingly, this unique connection enables tight analysis on KHMs' capacity.
Contributions. Through the memory code perspective, this work makes three main contributions:
Provably Optimal Capacity. We study the optimal memory capacity of KHMs and identify the conditions necessary to achieve it. Specifically, we derive provably tight and optimal capacity by matching the well-known exponential lower bound for the memory capacity of MHMs [Wu et al., 2024a,b, Hu et al., 2023, Ramsauer et al., 2020] with an upper bound in the low-temperature region. Notably, we establish this tight bound by showing that KHMs store the most memories when the memory set forms an optimal spherical code (Lemma 2.2). This result suggests a tight exponential scaling of memory capacity with the pattern dimension D& (Proposition 2.1).
Fast Algorithm. We introduce an algorithm. U-Hopt, that achieves the optimal capacity of KHM in sublinear time. Theoretically, we show that, as temperature approaches zero, U-Hop+ finds the optimal feature map for maximal KHM capacity (Theorem 3.1). This result bridges our theoretical findings with practical applications and explains the empirical successes of [Wu et al., 2024a].
Numerical Validation. Our experiments validate our theoretical analysis. We observe that (i) U-Hop+ creates distinct low-energy regions for each memory pattern, addressing the memory confusion problem in MHMs [Wu et al., 2024a, Krotov and Hopfield, 2016]; (ii) U-Hop+ signifi- cantly reduces metastable states on both MNIST and synthetic datasets, indicating larger memory capacity; (iii) with U-Hopt, the KHMs update rule converges to fixed points faster.
Organization. Section presents a brief review of MHMs and KHMs. Appendix A includes related work discussions. Section 2 presents our main results. Specifically, Section 2.1 presents a memory capacity lower bound for KHMs, Section 2.2 presents the optimal capacity bound based on the notation of memory code. Section 3.1 presents a sublinear time algorithm to search for the optimal 4 Section 3.2 discusses the relationship between & and M. Section 4 includes numerical experiments.
Notations. Lower case letters denote (column) vectors and upper case letters denote matrices. We write (a, b) == a as the inner product for vectors a, E IR.. The index set (1,..., /} is denoted by [T], where 7 E N+ The spectral norm is denoted by |1-1|, which is equivalent to the fo-m when applied to a vector. We denote the memory patterns (keys) by & E Id and the query pattern by x E Rd, and E= = [..,
E RdxM as shorthand for stored memory patterns (Eu ae[Md] Throughout this work, we use E\r interchangeably to refer to either d x M matrix or a set of M d-dimensional memory pattern vectors.
2
Main Theory
We provide theoretical analysis on the optimal memory capacity of KHMs. First, we begin by comparing the memory capacity between MHM and KHM using the standard high-probability lower bound [Hu et al., 2023, Ramsauer et al., 2020]. Then, we present a spherical code perspective as framework for depicting the optimal memory capacity of both MHMs and KHMs. In our analysis, we make the following pattern normalization assumption on memory patterns:
'It is a common assumption adopted in [Santos et al., 2024, Wu et al., 2024a]. A justification is the connection saasformer-attentio The modern Hopfield update rule (a.k.a. retrieval dynamics) is constantly compared to
3

---

Assumption 1. We assume memory patterns ||5μ|| = 1 in the rest of our paper.
2.1 Higgh-rrbabbility Capacity Lower Bound
We start by showing the memory capacity of KHM using the standard capacity lower bound introduced by Ramsauer et al. [2020]. This provides direct comparison between KHMs and previous works. The definition of the generalized fixed point [Sriperumbudur and Lanckriet, 2009] is
Definition 2.1 (Generalized Fixed Point (Sriperumbudur and Lanckriet, 2009]). We say set RR generalized fixed point w.r.t T if (1) E S for every y E S.
Remark 1. In contrast to Definition 1, fixed point of a point y satisfying T(y) = y. Let 8h be ball with radius Rs centered at every memory pattern in the feature space (L,x):
$ ((((e)) - yll < Rp where
Rs = min (E,,) (
(2.1)
2 [
Following [Wu et al., 2024a], we define the memory storage and retrieval
Definition 2.2 (Pattern Storage and Retrieval). We say memory pattern En is stored if 5% is generalized fixed point of T, and there exists a fixed point x E Sp. A memory pattern Ep gets c-retrieved by T with an input query x if [[T(x) Eull S c.
This definition is compatible with both KHMs and MHMs (with identity feature map). Under Definition 2.2, KHM's memory capacity is lower bounded by the following lemma.
Lemma 2.1 (Memory Capacity KHM). Let 1 p be the probability of successfully storing and retrieving pattern. Assuming the patterns are normalized, the number of patterns Ma that can be stored and retrieved by the KHM, following the update rule (1.3), lower-bounded by:
Mp 2 (pC(De-1)) 11//4
where C' is the solution to C' = (e 611,, with Wo(+) being the principal branch of Lambert W function, (1) (In( (In((R-7-2)/ Ra) + 1) and b = 48/(5(D=-1)) For comparison, Ms reduces to MHM's capacity lower bound by setting = Id. with D = d.
Proof. Our proof follows [Hu et al., 2023, Wu et al., 2024b]. See Appendix C.I for a proof.
With a fixed Dą. the highest lower bound of Lemma 2.1 corresponds to specific & that maximizes Ra. This provides an intuitive insight the design of separation loss [Wu et al., 2024a, Defini- tion 2.2] for kernel learning in [Wu et al., 2024a, Algorithm 1]. With an additional feature space, KHM has an exponential memory capacity in De that does not depend on d. When Ds d, KHMs obtain a tighter lower bound than MHMs if R&g > R. This bound connects the storage capacities of KHMs and MHMs, showing that their capacities scale exponentially with respect to D4 and d.
2.2 Memory Code: Memories as Spherical Code
There are aspects the lower bound in Lemma 2.1 does not address: the maximal capacity of KHMs and the flexibility of choosing different &b in KHMs. Therefore, we present a new framework using spherical codes take the above perspectives into consideration for further analysis. We begin by introducing the concepts of spherical code and optimal spherical code.
Definition 2.3 (Spherical Code). A d-dimensional spherical code on the unit sphere gd-1 is finite set CNv {c1. ..., CN } of gd-1 with N points, where e, E Rd for i [N] and [Cx] N.
Definition 2.4 (Minimal Separation). The minimal separation p(CN) of spherical code Cn is the maximal inner product between two distinct points in Cy: p(CN) = max (Ci, (z) for every + c.,c,ECN
attention-mechaniin mechanism and the input query and memory set correspond to Q. attention. As LayerNorm commonly used strategy attention layers, this setup can also he seen in real-world scenarios. By definition, neighborhoods do not overlap: St n S @ for μ.

---

Definition 2.5 (Optimal Spherical Code). Let Cv = {cl...., eN S g be d-dimensional spherical code with N points. An optimal spherical code CN minimizes the maximal pairwise inner product, which corresponds maximizing the minimal separation between points in the code. Formally, the optimal spherical code Cj is defined as:
CN argmin max (ct, Cy), for E [N].
Cx Cs if)
The minimal separation of the optimal spherical code is denoted as p²
"The optimal arrangement of most spherical codes is unknown, except for specific pairs of N), list of known optimal arrangements and minimal separations can be found at packings/ / and in [Conway and Sloane, 2013].
slcanne.......e www.ann.....m com/
Next, we recall the function class H. of the linear feature map introduced by Wu et al. [2024a]:
Definition 2.6. The function class H consists of linear maps that satisfy the following properties:
1. For all & E H. $ gd-1 P is linear map defined by matrix W RdxDe
2. The matrix W has full column rank.
3. When applying d to different inputs:
For vector & [R (E) W E Do
For a matrix R (() = (+(E)):.... ...,, ((EM)) E D&xM
For a set of vectors V (u,...., D(V) = (0(v))...... ((w))) with [+(V) = N.
Definition 2.6 ensures KHMs with feature map Φ(.) H satisfying the defining characteristics of MHMs: accurate [Wu et al., 2024a, Lemma 2. and consistent [Wu et al., 2024a, Thm 2.1] retrieval according to Definition 2.2.5 $ Now, we combine the concept of spherical code and memory storage.
Definition 2.7 (Kemellized Well Well-Separation Condition [Wu et al., b024a,b, Hu et al., 2023, Ramsauer et al., 2020]). Given a set of kerneiized memory patterns ((=) = { p=1 C SDe-1 the kernelized memory pattern (Ex)) satisfies the well-separation condition if the following holds:
1
2(M 2
1
In
(2.2)
B
R4
where the inverse temperature 3 is given by (1.3) and Rs is defined by (2.1).
The incquality (2.2) is a necessary condition for the y-th memory to have a well-defined attractor basin. Hence, the more memories satisfying (2.2) the greater the memory capacity of the model.
Definition 2.8 (Memory Code). Let M E N4, 3 > O, D& 1 and & E H. For any finite set (E)) = { p== S SDs -1 we say the set ((E) is a memory code if all points (( satisfies (2.2). Further, we denote AD. as the set of all memory codes in gDs including all possible E, Φ.
Notably, A includes all the possible pattern sets {E) that are able to be stored and retrieved by kernelized Hopfield models and modern Hopfield models. Naturally, the optimal memory capacity is the size of the largest memory code in @D This leads to next definition:
Definition 2.9 (Optimal Memory Capacity). For D& > 1 and & H. the optimal capacity M* is the cardinality of the largest memory code in A AD i.e., M = max [+) for all possible E, t.
Definition 2.9 specifies the largest possible memory code in AD, for a given Dz. Let E denote the memory set associated with M such that ||||| = M To store all patterns in E. we need to find suitable feature map & such that (()) is valid memory code.
Following this definition, we present the next lemma and proposition on optimal memory capacity.
Lemma 2.2 (Capacity of Optimal Spherical Code). Given a fixed D& > 1, and its corresponding M if an optimal code Copt is in 8 and has size M then Copt E AD
Note that, Definition 2.6 is sufficient but not necessary. is possible to find different Ht' such that KHMs with de E H' achieves desiring characteristics as [Wu et al., 2024a, Lemma 2.1] and [Wu et al., 2024a, Thm 2.
5

---

Proposition 2.1 (Optimal Memory Capacity). Following Lemma 2.2, we have
M x x
for some > Here = indicates matching upper and lower bounds up to constant factors.
Proof Sketch. We proof Lemma 2.2 by showing that the model capacity is increasing function w.r.t. the minimal separation value. For Proposition 2.1, we utilize the upper bound [Kabatiansky and Levenshtein, 1978] and lower bound in [Wyner, 1965, Shannon, 1959, Chabauty, 1953] to bound the quantity. Please see Appendix C.2 for a detailed proof.
Proposition 2.1 indicates that the optimal capacity of MHMs and KHMs scales exponentially with Da. This capacity bound is provably tight and optimal for large feature dimension Dz. echos the exponential capacity lower bound in Lemma 2.1 and in prior works [Wu et al., 2024a,b, Hu et al., 2024a,b,c, 2023, Ramsauer et al., 2020]. Moreover, Lemma 2.2 shows that achieving the maximal capacity in any D& is equivalent to achieving optimal codes. Thus, for a given memory set 3gt of size M, the memory storage problem with KHMs divides into two sub-problems:
(P1) Finding a sufficiently large De (in Section 3.2), and
(P2) Finding & such that Φ (=) is an optimal spherical code (in Section 3.1).
Next, examine these two sub uub-problems and present sub-linear time algorithm to solve them.
Sub-Linear Time Algorithm for Optimal Memory Capacity
In this section, we present an sub-linear time algorithm that achieves optimal capacity. Then, we analyze the scaling behavior of D& for KHMs to store any desired amount of memories.
3.1 Learning Achieve Optimal Memory Code
Here present asymptotic result showing that algorithm exists to find the optimal & for maximizing memory storage in dimension Da. Building on the results from the previous sections, consider the following problem:
Problem 1 (HardMax Problem). Given memory E ....... {M}. and assuming that Da sufficiently large to satisfy (2.2), we define the HardMax problem as finding a $ such that (E) forms an optimal spherical code:
min CHarMMax (Ø), where ΦEH
LHardMax (
(CS,), p".
(3.1)
M.MEMMPPP
This problem setup involves finding & such that (E forms an optimal spherical code. Ideally, more expressive function class H would simplify finding such a 4; exploring explicit forms of more powerful mappings is left for future work. Note that (3.1) represents a min-max optimization problem. Achieving the global optimum is notoriously challenging [Hsich et al., 2021. Daskalakis et al., 2021, Shen et al., 2020]. Thus, we introduce a surrogate objective to solve (3.1):
Definition 3.1 (Average Separation Loss). For r > given a set of memory patterns E and a feature map Φ, we define the average separation loss
($,)), (
C(E, ②)
Σ (,, where (3, log
exp
M
T
(3.2)
The primary difference between (3.1) and (3.2) is that (3.2) calculates average separation, whereas (3.1) focuses on the maximum separation between a single pair. This surrogate loss alleviates the challenging optimization, as (3.2) is convex. Therefore, with vanishing temperature т. the next theorem shows that (3.2) converges to the HardMax problem asymptotically.
Theorem 3.1. For any possible integer M, we have
lim sup argmin L(E R,r)) +-+
argmin LiannMaa (T). NEW
OEH

---

Algorithm U-Hop+
Input: Iterations N, feature map ((x) := Wx, memory set E, learning rate 7 S 1/G where G is the Lipschitz constant of L
Output:
1: Wo f- W
2: for t = .... do
3: W441 + PGD 7,
4: end for
5: return WN
Proof. we first introduce a helper function Lu in (C.10). We show that as + O, Lu converges uniformly to HaadMax Then, we prove that optimizing Lo and L yields the same optimal solution. Please see Appendix C.3 for detailed proof.
Theorem 3.1 indicates that, with vanishing temperature, the minimiozation of (3.2) converges to the HardMax problem, i.e., their share the same optimal solution. This provide theoretical justi- fication for the empirical success of [Wu et al., 2024a]. In particular, the surrogate objective the maximizing average separation between memories low-temperature region (i.e., + 0). Lastly, we remark that that this analysis provides theoretical insights rather than practical guidance. To achieve high retrieval accuracy, the setting (r in [Wu et al., 2024a] is sufficient for a wide range of applications.
leads provably optimal memory capacity in
U-Hop+: Sub-Linear Time Algorithm for Achieving Optimal Memory Capacity. Next, we present Algorithm 1 for finding & such that ((=) forms an optimal spherical code. To meet the conditions in Definition 2.6, we use projected gradient descent to convert this constrained optimization problem into unconstrained onc. Several methods satisfy the requirements in Definition 2.6; discuss them in Appendix B.2. We denote the learning rate as y, the input matrix of the loss function as X, and the weight matrix as W. We define single Projected Gradient Descent (PGD) step
W++ PGD(We, 7: XX),
We defer the detailed formulation to Appendix B.2. Since the separation loss is convex and smooth, using projected gradient descent with a learning rate S 1/G, yields sub-linear convergence rate of O(/NN) [lusem, 2003]. This provides an asymptotic solution the first sub-proli sub-problem (P1). Next, we examine the relationship between feature dimension Da and the number of memories M.
3.2 Impact of D+
This subsection analyzes the minimum D& to store given set of M memories. Based on the well- separation condition and the derivation in Appendix C.2, the required A to store M memories scales as (ln(M)). With this insight, the following proposition shows the scaling behavior of required Da with respect to M and A min
Proposition 3.1. Let M be the optimal memory capacity in SD and & E H. For any optimal code C* D of size M*, the minimal separation p(C*) bounded by:
1 V r (Putt)
7--
r 2 M
D---T
2 M
De T ( +1)
max GEH
r
De
where T(-) is the gamma function.
Remark 2. By gamma function asymptotics, Proposition 3.1 is consistent with Proposition 2.
Proof. Please see Appendix C.4 for a detailed proof.
Proposition 3.1 establishes the separation value for memory codes that achieve optimal capacity
Do Da-dimensional space. Using this bound, for a given separation value A A the minimum D required to store M points scales as log M2 ( We conduct an experiment to demonstrate the bound's tightness and provide example with D4 in Figure
7

---

Table 1: Distribution of Metastable State (in %). For MNIST, we use the training set as memories and test set queries. For synthetic data, randomly generate the memories and queries. l|pllo denotes the size of metastable state, which the amount of non-zero entries of the probability distribution. For Softmax, threshold of 0.01. For hyperparameter settings, see Table
Synthetic
MNIST
Softmax
1.5 1.--entmax
sparsemax
Softmax
1.6-entmax
sparsemax
lll
U-Hop+
U-Hop+
U-Hop+
U-Hop+
U-Hop+
U-Hop+
0.0
90.0
0.0
100.0
100.0
3.48
100.0
69.2
100.0
88.
100.0
0.0
8.0
0.0
0.0
20.0
8.6
0.0
5.2
0.0
0.0
0.0
0.0
0.0
30.0
1.57
3.9
0.0
2.6
0.0
0.0
2.0
0.0
0.0
50.0
0.0
1.23
0.0
2.3
0.0
1.6
0.0
6.0
0.0
0.0
0.0
0.0
0.0
1.2
0.0
1.6
0.0
1.1
0.0
10.0
0.0
25.0
0.0
0.0
0.0
0.95
0.0
0.9
0.0
0.8
0.0
20.0
0.0
25.0
0.0
0.0
0.0
1.04
0.0
0.6
0.0
0.4
0.0
16.0
0.0
0.0
0.0
0.0
0.0
0.0
0.6
0.0
0.1
0.0
20.0
0.0
22.5
0.0
0.0
0.0
1.03
0.0
0.3
0.0
0.0
0.0
10
28.0
0.0
27.5
0.0
0.0
0.0
86.5
0.0
12.0
0.0
0.1
0.0
4
Experimental Studies
4.1
U-Hop+ Reduces Metastable States
We compare the distribution metastable state size under standard MHM and KHM update rules. The results in Table 1. In general, with more metastable state having the size of 1, meaning the Hopfield model stores more memories as the query converges to a single memory. For metastable state size larger than represents that the retrieved pattern converges the mean of subset of memories, violating the requirement of 5 ns
Baselines. We compare different variants of MHMs and KHMs. Santos et al. [2024], Wu et al. [2024b] provide comprehensive analyses of modern Hopfield models with various normalization functions. Here, consider softmax, 1.5-entmax, and sparsemax for normalization. We equip these three baselines with U-Hop to compare against standard MHMs.
Settings and Metrics. Let Softmax T.). We determine whether the update rule converges either single memory or mixture of memories by observing the probability distribution p. The quantity l!pll, represents the size of the metastable state, which is the number of non-zero entries in the probability distribution. the case of 1.5-entmax and sparsemax, we calculate l|rlo directly. For softmax, since it only generates non-zero entries, we use a threshold of 0.01 and consider the entries under the threshold as We conduct experiments using both synthetic and MNIST datasets. For MNIST, we use the training set memories and the test set as queries. For synthetic datasets, randomly generate memories and queries with Gaussian initialization. To ensure the convergence to the fixed point, perform multiple updates on the query. For more details, refer to Appendix D.
Results. On both synthetic and MNIST datasets, is evident that under separation maximization, the size of the metastable state dramatically decreases within just 20 iterations of Algorithm 1. This result demonstrates that, with Algorithm 1, KHMs are capable of storing patterns that MHMs cannot store. The significant percentage of size 1 metastable states in KHMs indicates that they circumvent the memory confusion problem dense associative memory models [Krotov and Hopfield, 2016]. For the MNIST dataset, we see MHMs show close performance with KHMs under 1 1.5-entmax and sparsemax, showing that the methods in [Santos et al., 2024, Wu et al., 2024b, Hu al., 2023] also circumvent the memory confusion problem. Notably, KHMs require only one-fourth of the dimensions to store memories while perfectly storing 60,000 MNIST patterns. These results suggest that KHMs with Algorithm I efficiently utilize feature dimensions for memory storage.
4.2 Energy Landscape under U-Hop+ Stores More Memories
Settings and Metrics. We visualize the energy landscape of KHMs at different stages of Algorithm 1 using contour plots. The results are presented in Figure We consider two settings: 2 and memories stored in a a 2-dimensional space. Ideally, the energy landscape should position memories in multiple separated low-energy regions (valley), with each region isolated from others by high-energy regions. If multiple memories share the same valley, leads to memory confusion and the presence of metastable states during energy minimization. For experiment details, refer to Appendix D.2.
The first row in Figure shows the raw energy landscape without KHM and Algorithm 1, corresponding to the modern Hopfield energy landscape, On the right side of Figure 1, we observe that MHMs are only able to store 2 out of 4 points, but KHMs are able further separate point
Results.

---

R=1
Figure Energy Landscape under Different Iterations Algorithm Left:
Right:
Lighter color represents higher energy. The first row represents the raw energy landscape without applying U-Hop+. The second to last row represents the energy landscape when N = (1, 5). The visualization shows that Algorithm 1 not only separates the local minima better, but also pushes memorics closer the fixed point.
Test AUC of Multiple Instance Learning Datasets. We compare the HopfieldPooliin model with without U-Hopt. We use the dense [Ramsauer et al., 2020] and sparse [Huu et al., 2023] modern Hopfield models as baselines. We use K-fold cross validation on all 4 datasets, with K = 10. The reported AUC is the average AUC score across 10 folds. For the basclines, we use the results reported in [Hu et al., 2023]. For our method, we directly use the default hyperparameter without grid search instead of using hyperparameter optimization (HPO)
Table 2:
based
al., 2023, Ramsauer et al., 2020). We exclude variance they all smaller than 0.07. The result shows that even without HPO, U-Hopp is still able to obtain performance gain.
Method
Tiger
Elephant
Fox
UCSB
Modern Hopfield
0.871
0.876
0.637
0.828
Modern Hopfield + U-Hopt
0.881
0.921
0.648
0.831
Sparse Hopfield
0.884
0.914
0.610
0.796
Sparse Hopfield U-Hop+
0.887
0.921
0.638
0.805
from the others, resulting in memorizing one extra pattern. Lemma 2.2 and Theorem 3.1 indicate that U-Hop+ pushes memories away from each other, providing more isolated S for μ E [M]. We observe this phenomenon across all settings, especially under the 2-point configuration with Softmax and 1.5-entmax, where the low-energy region split into two distinct valleys as N increases. This process shows how U-Hop* is able to store memories that MHMs cannot. With energy minimization, the query converges either one of the minima instead of the mixture thereof (also showed in Figure 2). Additionally, we also notice that the contour lines exhibit steep slopes between different local minima in the 2-point setting under 1.5-entmax and sparsemax. This implies that U-Hop+ pushes local minima further away from each other and deepens each one of them. Such sharp changes in energies lead faster convergence fixed points due to larger gradients.
Basins of Attraction. Figure shows the basins of attraction of queries w.r.t. MHM and KHM under the scenario of storing 5 patterns. We randomly initialize 5 patterns with normal distribution. We run the update rule for 5 iterations and see whether each query converges to a single memory (colored) or metastable state (white). Following the above setting, we track the attraction basins throughout each iteration of Algorithm 1. We defer more details to Appendix D.3. Specifically, most MHM variants are capable of converging to fixed points in updates. While U-Hop+ dramatically improves such aspect, where most queries are able to converge either one of the memories. Moreover, the increased Rs also leads to a larger 5tt making more queries to converge to a single memory. Additionally, there is a performance gap between Softmax (a 1) and other sparse variants, which matches the findings in [Santos al., 2024, Hu al., 2023].
4.3 Multiple Instance Learning
conduct multiple instance learning (MIL) on real-world datasets using Hopfied-based models with and without our U-Hop+ algorithm. We follow the setup in [Santos et al., 2024, Wu et al., 2024a, Hu al., 2023] by using model with embedding layer, HopfieldPool/ cipoolinggg layer and linear readout layer. We first utilize Algorithm to "pretrain" the embedding and HopfieldPoo layer,

---

1-entmax 15-entmax
2-entmax
O
N
Figure 2: Basins of Attraction Comparison of Algorithm The first row represents the raw Basins of Attraction without applying U-Hop+ or KHM. The second to last row shows the basins when N = (1, 2, 5). Square points memories. White area is where queries converges
where queries not able converge converging to fixed point fast and corresponding memory. The result indicates that U-Hop+ capable of et al., 2020] and Sparsemax [Hu et al., 2023].
single memory. Colored
metastable states.
2-entmax corresponds Softmax [Ramsauer
and then fine-tune the whole model the MIL task. The results are in Table 2. We observe that both dense and sparse Hopfield- based models obtain performance boost when equipped with U-Hopt, indicating method is also effective in practical scenarios. Further, as demonstrated in Figure the separation loss converges fast, indicating U-Hop+ is lightweight method for performance boost.
5 Discussion and Conclusion
This work complements U-Hop [Wu al., 2024a] by establishing the optimal capacity of kernelized modern Hopfield models (KHMs) and providing the first tight, optimal memory capacity bound for waasformer-compptbble dense associative memories. We start by connecting stored memories in KHMs to spherical codes from information theory. We then prove that maximizing memory storage KHMs requires arranging memories as an optimal spherical code feature space. This allows us to matches the well-known exponential lower bound [Wu et al., 2024a,b, Hu et al., 2024a,b,c, 2023, Ramsauer al., 2020] with an upper bound. This achievement is notable, as deriving such a tight bound is challenging due to the max-min structure of maximal separation among stored memories [Wu et al., 2024a, Section 5]. Moreover, we introduce sub-linear time algorithm achieve this optimal capacity, U-Hop+ (Algorithm 1). U-Hop+ performs this rearrangement with convergence rate Ot/N). Additionally, we analyze the minimum dimension D& required to store M memories. Numerically, we validate the effectiveness of KHMs and demonstrate how Algorithm enhances memory storage in both KHM retrieval tasks and transformer representation learning tasks.
Can U-Hop+ Preserve Semantic Meanings? In representation learning. it is crucial to preserve relationships in the feature space after encoding data [Wang al., 2023, Neelakantan al., 2022]. The primary strategy is to ensure the embeddings of similar instances share similar directions in Fuclidean space. At first glance, the approach of pushing memories away from each other in Equation (3.2) may seem counterintuitive. However, as detailed in Appendix D.5, we find that the learned feature map still encodes similar instances closely together (Figure 4), even without semantic information involved. This result indicates that U-Hop+ stores memories in semantically coherent manner. A discussion the separation capability can be found in Figure
Limitations. One limitation of our work only considers linear affine functions as the feature map E H. Additionally, standard spherical code analysis focuses only on normalized points on hypersphere, ignoring memories with varying magnitudes. We leave them for future research.
10

---

Broader Impact
We expect no negative social impacts as this work mostly present theoretical results and numerical simulations. As discussed in our introduction, this paper develops a theoretical framework to study Kemeliizdd Hopfield models, potentially benefit the area of computational associative (Hopfield) memory models, transformer networks and large foundation models.
Acknowledgements
JH thanks Thomas Burns, Dmitry Krotov, Mimi Gallagher, Sara Sanchez, Dino Feng. and Andrew Chen for enlightening discussions; Robin Luo, Jiahao Yu. Weimin Wu, and Teng-Yu Yun Hsiao for collaboration on related topics; the Red Maple Family for their support; and Jiayi Wang for facilitating experimental deployments. The authors also thank the anonymous reviewers and program chairs for their constructive comments.
JH is partially supported by the Walter P. Murphy Fellowship. DW is supported by NIH R01LM1372201. HL partially supported by NIH ROILMI AbbVie and Dolby. This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility at Northwestern University which is jointly sup- ported by the Office of the Provost, the Office for Research, and Northwestern University Information Technology. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint 23X3:22003.87774 2023.
Andreas Auer, Martin Gauch, Daniel Klotz, and Sepp Hochreiter. Conformal prediction for time series with modern hopfield networks. Advances in Neural Information Processing Systems, 36: 56027-56074, 2023.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. arXiv preprint arXiv:2306.04637 2023.
Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of transformer: A memory viewpoint. Advances in Neural Information Processing Systems, 36, 2024.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx. Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportuni- ties and risks of foundation models. arXiv preprint 108.:2008.00255.. 2021.
Andrea Braides. A handbook of 7-convergence. In Handbook of Differential Equations: stationary partial differential equations, volume 3, pages 101-213. Elsevier, 2006.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12711 2023.
Thomas F Burns. Semantically-coorelattee memories in dense associative model. arXiv preprint arXiv:2404.07/ 2024.
Thomas F Burns and Tomoki Fukai. Simplicial hopfield networks. arXiv preprint arXiv:2305.05179. 2023.
Vivien Cabannes, Elvis Dohmatob, and Alberto Bietti. Scaling laws for associative memories. arXiv preprint WXXi:2331000298. 2023.
Claude Chabauty. Resultats sur lempilement de calottes egales sur une perisphere de m correction un travail anterieur. COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE I. ACADEMIE DES SCIENCES, 1462-)44442146656 1953.

---

John Horton Conway and Neil James Alexander Sloane. Sphere packings, lattices and groups, volume 290. Springer Science & Business Media, 2013.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-1478, 2021.
Philippe Delsarte, Marie Goethals, and Johan Jacob Seidel. Spherical codes and designs. In Geomerry and Combinatorics, pages 68-93. Elsevier, 1991.
Mete Demircigil, Judith Heusel, Matthias Löwe, Sven Upgang, and Franck Vermet. On model of associative memory with huge storage capacity. Journal of Statistical Physics, 168:288-299, 2017.
Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding, arXiv preprint arXiv:1810.04888 04805, 2018.
Sjoerd Dirksen, Martin Genzel, Laurent Jacques, and Alexander Stollenwerk. The separation capacity of random neural networks. Journal of Machine Learning Research, 23(309):1 477, 2022.
Irene Gil Fernández, Jaehoon Kim, Hong Liu, and Oleg Pikhurko. New lower bounds on kissing numbers and spherical codes in high dimensions. arXiv preprint arXiv:2111.01255 2021.
Andreas Fürst, Elisabeth Rumetshofer, Johannes Lehner, Viet Tran, Fei Tang. Hubert Ramsauer, David Kreil, Michael Kopp. Günter Klambauer, Angela Bitto, et al. Cloob: Modern hopfield networks with infoloob outperform clip. Advances neural information processing systems (NeurIPS), 35:20450- 2022.
Promit Ghosal, Srinath Mahankali, and Yihang Sun. Randomly initialized one-layer neural networks make data linearly separable. arXiv preprint arXiv:2205. 2022.
Florian Graf, Christoph Hofer, Mare Niethammer, and Roland Kwitt. Dissecting supervised con- trastive learning. In International Conference on Machine Learning, pages 3821-3830. PMLR, 2021.
Zexue He, Leonid Karlinsky, Donghyun Kim, Julian McAuley, Dmitry Krotov, and Rogerio Feris. Camelot: Towards large language models with training-free consolidated associative memory. arXiv preprint arXiv:2402.1 3349, 2024.
Claus Hofmmann, Simon Schmid, Bernhard Lehner, Daniel Klotz, and Sepp Hochreiter. Energy-based hopfield boosting for out-of-distribution detection. arXiv preprint arXiv:2405.08766 2024.
Benjamin Hoover, Hendrik Strobelt, Dmitry Krotov, Judy Hoffman, Zsolt Kira, and Duen Horng Chau. Memory in plain sight: A survey of the uncanny resemblances between diffusion models and associative memories. arXiv preprint arXiv:2309.1677 2023.
Benjamin Hoover, Duen Horng Chau, Hendrik Strobelt, Parikshit Ram, and Dmitry Krotov. Dense as- sociative memory through the lens of random features. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a. URL https: http::::////ppeevieeee/e net forum? hid-144nnssyji
Benjamin Hoover, Yuchen Liang, Bao Pham, Rameswar Panda, Hendrik Strobelt, Duen Horng Chau, Mohammed Zaki, and Dmitry Krotov. Energy transformer. Advances in Neural Information Processing Systems, 36, 2024b.
John Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8):2554-2558, 1982.
John J Hopfield. Neurons with graded response have collective computational properties like those of two-state neurons. Proceedings of the national academy of sciences, 81 (100:30088-300 -302,, 1984.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning, pages 4337-4348. PMLR, 2021.
12

---

Wei- Yen Hsu. Application of competitive hopfield neural network to brain-computer interface systems. International journal of neural systems, 22(01):51-62, 2012.
Jerry Yao-Chieh Hu, Donglin Yang, Dennis Wu, Chenwei Xu, Bo- Chen, and Han Liu. On sparse modern hopfield model. In seiett- Conference Neural Information Processing Systems (NeurIPS), 2023.
Jerry Yao- Cho-hh Hu, Pei-Hsuan Chang, Haozheng Luo, Hong- Yu Chen, Weijian Li, Wei-Po Wang, and Han Liu. Outlier-efficien hopfield layers for large transformer-basee models. In Forty-first International Conference Machine Learning (ICML), 2024a.
Jerry Yao-Chieh Hu, Bo-Yu Yu Chen, Dennis Wu, Feng Ruan, and Han Liu. Nonparametric modern hopfield models. arXiv preprint arXiv:2404.03906 2024b.
Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, and Han Liu. On computational limits of modern hopfield models: fine-gra fine-grained complexity analysis. In Forty-first International Conference on Machine Learning (ICML), 2024c.
Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, and Han Liu. On statistical rates and provably efficient criteria of latent diffusion transformers (dits). In Thirty-eighth Conference Neural Information Processing Systems (NeurIPS), 2024d.
Georgios Iatropoulos, Johanni Brea, and Wulfram Gerstner. Kernel memory networks: unifying framework for memory modeling, Advances in Neural Information Processing Systems, 35: 35326-35338, 2022.
Alfredo N lusem. On the convergence properties of the projected gradient method for convex optimization. Computational & Applied Mathematics, 22:37-52, 2003.
Matthew Jenssen, Felix Joos, and Will Perkins. On kissing numbers and spherical codes in high dimensions. Advances in Mathematics, 335:307-321, 2018
Yanrong Ji, Zhihan Zhou, Han Liu, and Ramana V Davuluri. Dnabert: pre-trained bidirectional encoder representations from transformers model for ima-language in genome. Bioinformatics, 37 (15):2112-2120,, 2021.
Jiachen Jiang, Jinxin Zhou, Peng Wang, Qing Qu, Dustin Mixon, Chong You, and Zhihui Zhu. Generalized neural collapse for a large number of classes. arXiv preprint arXiv:2310.0535/ 2023.
Grigorii Anatol evich Kabatiansky and Vladimir losifovich Levenshtein. On bounds for packings a sphere and in space. Problemy peredachi informatsit, 14(1):3-25, 1978.
Pentti Kanerva. Sparse distributed memory. MIT press, 1988.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35: 22199-222133 2022.
Leo Kozachkov, Ksenia V Kastanenka, and Dmitry Krotov. Building transformers from neurons and astrocytes. Proceedings of the National Academy of Sciences, 120(34):c221150013 2023.
Dmitry Krotov. A new frontier for hopfield networks. Nature Reviews Physics, 5(7):366-367) 2023.
Dmitry Krotov and John J Hopfield. Dense associative memory for pattern recognition. Advances in neural information processing systems, 29, 2016.
Dmitry Krotov and John J. Hopfield. Large associative memory problem in neurobiology and machine learning. International Conference on Learning Representations (ICLR), 2021.
Mikhail A Lebedev and Miguel AL Nicolelis. Brain- interfaces: past, present and future. TRENDS in Neurosciences, 29(9)536-544, 2006.
Anatole Lécuyer, Fabien Lotte, Richard Reilly, Robert Leeb, Michitaka Hirose, and Mel Slater. Brain-computer interfaces, virtual reality, and vidcogames. Computer, 41(10))66-72, 2008.
13

---

Debra A Lelewer and Daniel S Hirschberg. Data compression. ACM Computing Surveys (CSUR), 19 (3):261-296, 1987.
Xilin Liu, Milin Zhang, Basheer Subei, Andrew G Richardson, Timothy Lucas, and Jan Van der Spiegel. The pennbmbi: Design of general purpose wireless brain-mas muahine-brain interface system. IEEE transactions on biomedical circuits and systems, 9(2):248-2) 258, 2015.
Carlo Lucibello and Mare Mézard. Exponential capacity of dense associative memories. Physical Review Letters, 132(7)077301,, 2024.
Andre Martins, Vlad Niculae, and Daniel C McNamee. Sparse modern hopfield networks. In Associative Memory & Hopfield Networks in 2023, 2023.
Michael H Moore. Vector packing in finite dimensional vector spaces. Linear Algebra and its Applications, 833)211-224, 1974.
Megan Morrison, Pedro D Maia, Nathan Kutz, et al. Preventing neurodegenerative memory loss in hopfield neuronal networks using cerebral organoids or external microelectromics. Computational and Mathematical Methods in Medicine, 2017, 2017.
Arvind Neelakantan, Tao Xu, Raul Puri, Alec Radford, Jesse Michael Han, Jerry Tworek, Qiming Yuan, Nikolas Tezak, Jong Wook Kim, Chris Hallacy, et al. Text and code embeddings by contrastive pre-training. arXiv preprint arXiv:2201.10000 2022.
OpenAl. Sora: A video generative model based on transformer diffusion. OpenAl Research, 2024.
Accessed: 08/16/2024.
Toshihiro Ota, Ikuro Sato, Rei Kawakami, Masayuki Tanaka, and Nakamasa Inoue. Learning with partial forgetting in modern hopfield networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 6661-6673. PMLR, 2023.
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 24652-24663, 2020.
William Peebles and Saining Xie. Scalable diffusion models with transformers. Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 4205, 2023.
Ben Peters, Vlad Niculac, and André FT Martins. Sparse sequence-to-sequenee models. arXiv preprint arXiv:1905.052: 05702, 2019.
William Wesley Peterson and Edward Weldon. Error-correcting codes. MIT press, 1972.
Adam Polyak, Amit Zohar, Andrew Brown, Andros Tjandra, Animesh Sinha, Ann Lee, Apoorv Vyas, Bowen Shi, Chih- Yao Ma, Ching Yao Chuang, et al. Movie gen: A cast of media foundation models. arXiv preprint arXiv:2410.13722 2024.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838-88) 885,, 1992.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Parameswaran Raman and Jiasen Yang. Optimization on the surface of the (hyper)-sphere. arXiv preprint XXX::1999.00466 06463, 2019.
Ander Maros--urguialdayy Doris Broetz, Massimiliano Rea, Leonhard Läer, Özge Yilmaz, Fabricio L Brasil, Giulia Liberati, Marco Curado, Eliana Garcia-Cossio, Alexandros Vyziotis, et al. Brain- machine interface chronic stroke rehabilitation: controlled study. Annals of neurology, 74(1): 100-108, 2013.
Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Thomas Adler, Lukas Gruber, Markus Holzleitner, Milena Pavlović, Geir Kjetil Sandve, al. Hopfield networks is all you need. arXiv preprint 27X1v:2008.02217,.20 2020.
14

---

R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Bishwajit Saha, Dmitry Krotov, Mohammed J Zaki, and Parikshit Ram. End-to-end differentiable clustering with associative memories. In International Conference on Machine Learning, pages 19649-29677 PMLR, 2023.
Saul Santos, Vlad Niculae, Daniel McNamee, and Andre FT Martins. Sparse and structured hopfield networks. arXiv preprint 1rXi: 2024,
Philipp
Seidl, Philipp Renz, Natalia Dyubankova, Paulo Neves, Jonas Verhoeven, Jorg K Wegner, Marwin Segler, Sepp Hochreiter, and Gunter Klambauer. Improving few-and zero-shot reac- tion template prediction using modern hopfield networks. Journal of chemical information and modeling, 62(9):2111-212) 2022.
Maryam M Shanechi. maiiine interfaces from motor to mood. Nature neuroscience, 22(10):
1554-1564, 2019.
Claude E Shannon. Probability of error for optimal codes in a gaussian channel. Bell System Technical Journal, 38(3):61 1--666,,11,,, 1959.
Jiayi Shen, Xiaohan Chen, Howard Heaton, Tianlong Chen, Jialin Liu, Wotao Yin, and Zhangyang Wang. Learning a minimax optimizer: pilot study, In International Conference on Learning Representations, 2020..
Bharath K Sriperumbudur and Gert RG Lanckriet. On the convergence of the concave-convex procedure. In Advances in neural information processing systems, volume 9, pages 1759-1767, 2009.
Thomas Strohmer and Robert W Heath Jr. Grassmannian frames with applications to coding and communication. Applied and computational harmonic analysis, 14(3):257-275, 2003.
Hugo Touvron, Thibaut Lavril, Gautier Izacard. Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael I Jordan. Averaging stochastic gradient descent on riemannian manifolds. In Conference On Learning Theory, pages 650-687.
PMLR. 2018
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Jeffrey Wang. Finding and investigating exact spherical codes. Experimental Mathematics, 18(2): 249-256, 2009.
Liang Wang, Nan Yang, Xiaolong Huang, Linjun Yang, Rangan Majumder, and Furu Wei. Improving embeddiigg with large language models. arXiv preprint 2xXV::2401.00366 2023.
Michael Widrich, Bernhard Schäfl, Milena Pavlović, Hubert Ramsauer, Lukas Gruber, Markus Holzleitner, Johannes Brandstetter, Geir Kjetil Sandve, Victor Greiff, Sepp Hochreiter, et al. Modern hopfield networks and attention for immune repertoire classification. Advances in Neural Information Processing Systems, 33: 8832-18845, 2020.
David J Willshaw, Peter Buneman, and Hugh Christopher Longuet- Non-holographic associative memory. Nature, (22 962, 1969.
Dennis Wu, Jerry Yao-Chich Hu, Teng- Teng-Yun Hsiao, and Han Liu. Uniform memory retrieval with larger capacity for modern hopfield models. In Forty-first International Conference on Machine Learning (ICML), 2024a.
Dennis Wu, Jerry Mho-Chieh Hu, Weijian Li, Bo- Yu Chen, and Han Liu. Stanhop: Sparse tandem hop- field model for memory-enhanced time series prediction. The Twelfth International Conference on Learning Representations (ICLR), 2024b.
15

---

Aaron D Wyner. Capabilities of bounded diserepancy decoding. Bell System Technical Journal, 44 (6):1011-1122, 1965.
Chenwei Xu, Yu-Chao Huang, Jerry Yao-Chich Hu, Weijian Li, Ammar Gilani, Hsi-Sheng Goan, and Bi-directional cellular learning for tabular data with generalized sparse modern hopfield model. arXiv preprint 2tt1:220440083300 2024.
Han Liu. Bishop:
Alan L Yuille and Anand Rangarajan. The concave-convex procedure (ccop). Advances in neural information processing systems, 14, 2001.
Zhihan Zhou, Yanrong Ji, Weijian Li, Pratik Dutta, Ramana Davuluri, and Han Liu. Dnabert-2: Effi- cient foundation model and benchmark for multi-species genome. arXiv preprint arXiv:2306. 15006, 2023.
Zhihan Zhou, Winmin Wu, Harrison Ho, Jiayi Wang, Lizhen Shi, Ramana V Davuluri, Zhong Wang. and Han Liu. Dnabert-s: Learning species-aware dna embedding with genome foundation models. arXiv preprint (exXx::2402.0777 2024.
Zhihui Zhu, Tiayyu Ding. Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu A geometric analysis of neural collapse with unconstrained features. Advances in Neural Information Processing Systems, 34:29820-2900 29834, 2021.
16

---

Appendix
A Related Works
18
More Discussions
B.1
MHM Capacity
19
B.2
Learning on Stiefel Manifolds
19
B.3
KHMs Brain-Machine Interface
20
Proofs of Main Text
21
C.1 Proof of Lemma 2.1 ................................
21
C22 Proofs of Lemma 2.2 and Proposition 2.1
24
C.3 Proof of Theorem 3.1
26
C.4 Proof of Proposition 3.1
28
Experimental Details
29
D.I Metastable States
29
D.2 Energy Landscape
29
D.3 Basins of Attraction
30
D.4 Simulation of Proposition 3.1
30
D.5 Assignment Problems
30
D.6
Additional Experiments
31
17

---

A Related Works
Hopfield and Dense Associative Memory Models. Associative memory models [Kanerva, 1988, Willshaw et al., 1969] are extensively studied in neuroscience and machine learning due to their biologically plausible designs. These models aim to store a set of memories and accurately retrieve each one given an input query. Hopfield models [Hopfield, 1982] are a class of energy-based associative memory models, beginning with classical versions [Hopfield, 1984, 1982] that handle binary patterns and have a (sub-)linear memory capacity of ((d) for a pattern dimension d. Dense associative memory models [Krotov and Hopfield, 2021, 2016, Ramsauer et al., 2020, Demircigil et al., 2017] are later proposed with superlinear memory capacity enabled by sharper energy functions (e.g.. polynomial and exponential). Notably, the latest advancement in these dense models is their exponential-in-d capacity [Lucibello and Mézard, 2024, Santos et al., 2024, Wu et al., 2024b, Hu et al., 2024a,c.b, 2023, Ramsauer et al., 2020]. However, the current literature reports are mostly lower bound results for this exponential memory capacity. This work matches these lower bounds with an upper bound, making the capacity both tight and provably optimal.
Modern Hopfield Models. Recently, a special class of dense associative memory models, modern Hopfield models (MHMs), has gained increasing interest in deep learning due to their connection to the attention mechanism in transformers [Wu et al., 2024a,b, Hu et al., 20,4a,c,b, 2023, Ramsauer et al., 2020]. Therefore, we also refer to dense associative memories. Notably, the defining characteristic of
Transformer- Compatiibll Dense Associative Memories:
them as transformer-compatiine MHMs is that their single-step update is equivalent to the attention mechanism (Vaswani et al., 2017]. This striking feature makes them interesting given the prevalence and dominance of transformer architectures in the era of large foundation models [Polyak al., 2024, OpenAI, 2024, Hu al., 2024d, Peebles and Xie, 2023, Bubeck et al., 2023, Bai et al., 2023, Achiam et al., 2023, Zhou et al., 2024, 2023, Ji et al., 2021, Touvron et al., 2023, Kojima al., 2022, Bommasani et al., 2021, Radford et al., 2019, Devlin, 2018].
As result, such connection facilitates the integration of associative memory models into modern deep learning and large foundation models [Burns, 2024, Xu et al., 2024, Hu et al., 2024a,b, Hofmann et al., 2024, Wu al., 2024b, Auer et al., 2023, Burns and Fukai, 2023, Fürst et al., 2022, Krotov and Hopfield, 2016]. Moreover, recent studies introduce several modern Hopfield model variants. Hu al. [2023] propose the sparse modern Hopfield model, a sparse counterpart to MHM with larger capacity and lower retrieval error. Wu et al. [2024b], Santos et al. [2024], Martins et al. [2023] introduce generalized sparse Hopfield models that unify all MHMS with different degrees of sparsity. Hu et al. [2024b] present a nonparametric construction for deep learning compatible Hopfield layers and several efficient modern Hopfield variants. Hu et al. [2024a] introduce OutEffHop. an outlier- removing, deep learning compatible Hopfield layer for robust large pretrained model quantization. Wu et al. [2024a] propose U-Hop facilitating memory retrieval in Iearnable feature space (see introduce for a review). Empirically, U-Hop improves the memory confusion problem [Krotov and Hopfield, 2021] by a significant margin.
Applications of Modern Hopfield Models in Modern Machine Learning. Recently, modern Hopfield models also achieve empirical success across various deep learning tasks [Krotov, 2023). Starting with [Krotov and Hopfield, 2016), the polynomial Hopfield model is proposed for image classification tasks (e.g., MNIST). Later, Ramsauer et al. [2020] introduce modern Hopfield layers compatible with deep learning architectures. Since then, various modern Hopfield layers [Hu et al., 2024a, Wu et al., 2024b, Hu et al., 2023] have been applied in many deep learning tasks, such as language modeling [He et al., 2024], multiple instance learning [Ramsauer et al., 2020], immune repertoire classification [Widrich et al., 2020], multivariate time series prediction [Wu et al., 2024b], image generation [Hoover et al., 2023], tabular learning [Xu et al., 2024], unsupervised clustering [Saha et al., 2023], and image captioning [Fürst et al., 2022].
Additionally, modern Hopfield layers introduce new operations in large foundation models to improve performance. For example, Wu et al. [2024b] leverage the retrieval dynamics of modern Hopfield models to enable an external memory plugin in time series prediction, and Xu et al. [2024] apply a
6 After completion of this work, the authors attended ICML 2024 and learned of upper bound result reported by [Santos al., 2024]. which also utilizes techniques from spherical codes. The authors regret missing the dinner with Santos et al. [2024] at Vienna due to a tight schedule. The difference between this work and [Santos et al., 2024] lies not only in scope but also in that our upper bound matches the lower bound in the now-temperature region (Proposition 2.1).
18

---

similar approach to tabular data. In image captioning, Fürst et al. [2022] address issues with covariance structure using modern Hopfield models. Hu et al. [2024a] propose an outlier-free Hopfield layer as a quantization-strong and resource-effiient transformer backbone for large language models and large foundation models. Ota et [2023] embed a partial forgetting functionality in modern Hopfilld models to enhance model performance.
Kernelized Hopfield Models. Wu al. [2024a] propose kernelized Hopfield models (KHMs)², which have the capability to store memories in a learnable feature space. KHMs offer the flexibility to relocate memories while maintaining several defining properties of modern Hopfield models [Ramsauer et al., 2020, Theorems I to 4). By maximizing the average separation between memories, KHMS empirically achieve lower retrieval errors [Wu et al., 2024a, Section 4J. However, the theoretical understanding of KHMs is larking due to their new flexibility in rearranging memories. This work aims to fill this gap by analyzing the capacity limits and theoretical justifications for KHMs.
Spherical Code. Spherical codes are mathematical constructions describing the arrangement of M points on the surface of d-dimensional hyper-sphere [Delsarte et al., 1991]. The main problem around spherical codes to arrange points way such that the minimum distance between any two points are maximized. This arrangement is called the optimal spherical code. It is crucial for minimizing errors and maximizing efficiency in signal transmission and data storage. In general, the value of max minimal separation and arrangement of points is unsolved except for certain pairs of (d, M) [Wang, 2009]. Various fields such as communications [Strohmer and Heath Jr, 2003] and data compression [Lelewer and Hirschberg, 1987]. Moreover, spherical codes are related to the area of error-correcting codes [Peterson and Weldon, 1972], which are used to detect and correct crrors in data transmission and storage.
B
More Discussions
B.1 MHM Capacity
We review the modern Hopfield capacity lower bound in [Ramsauer et al., 2020].
Lemma B.1 (Memory Capacity of MHM). Let 1 - p be the probability of successfully storing and retrieving a pattern. Assuming patterns are normalized, the amount of patterns randomly sampled from d-dimensional unit-sphere that the MHM with update rule in (1.2), can store and retrieve is lower-bounded by
M > VDC(1-1)44 1)/4
where C' is the solution to C = w/wp 8)), with (-(-) being the principal branch of Lambert W function, a (4/a-1) (In 2/F-2/R 1) and b == 48/5td-1).
Observe Wo is an increasing function in exp(a + In b}. indicating that C' is increasing in R ( C is increasing a; a decreasing with fixed R). Finally, we observe that under Assumption 1, we have R = 24 implying that the memory capacity of MHM is constrained by large Amiu-
B.2 Learning on Stiefel Manifolds
We review ways to do optimization on the surface of an unit-hypersphere (Stiefel manifold).
Projected Gradient Descent. Given any loss function C(-), an input matrix X, and learning rate 7, a single gradient descent step at f-th time step is:
W W. 72 C(X)
(B.1)
Projected gradient descent [Raman and Yang, 2019] then projects W onto the feasible set, in this case, the surface of unit hypersphere
W We+1/
W
(B.2)
"This different from [latropoulos al., 2022] while they share similar names. As an independent yet related effort, Hoover et al. [2024a] propose the DrDAM (Distributed Representation for Dense Associative Memory) as a kernel approximation of the standard dense associative memory models based on random feature decomposition.
19

---

Combining (B.1) and (B.2), we obtain the projected gradient descent step as
W41 = PGD Y.
Riemannian Optimization. [Tripuraneni et al., 2018] construct and analyze an approach on optimization on Riemannian manifolds from a geometric perspective. Their adapt the Polyak-Ruppert [Polyak and Juditsky, 1992] iterate averaging technique the Riemannian setting. In general, with carefully selected step-size, their method achieves (L/NN) convergence rate which is the same in the euclidean setting. Overall, there are various of methods for optimization Riemannian manifolds with comparable convergence rate to Euclidean space. Thus, giving the advancement of Riemannian optimization, our assumption in Definition 2.6 is reasonably mild.
L2 Regularization. A simple alternative satisfy the constraint is through 1.2 regularization. From the aspect of neural collapse [Papyan et al., 2020], learning under (3.2) is similar to learning under cross-entropy loss or supervised contrastive learning without positive samples [Graf al., 2021J. Further, from the analysis on unconstrainted feature models [Zhu et al., 2021], we can see that with carefully chosen coefficient on the regularization term W, the optimal solution of (3.2) or cross-entropy loss ended up outputting normalized features.
Based on the previous research, are able to see that the constraint in Definition 2.6 is not difficult to satisfy.
B.3 KHMs as Brain-Machine Interface
The ultimate goal in the field of Brain-Machine Interface (BMI) [Lebedev and Nicolelis, 2006] is to design communication between human brains and external devices. It has potential in various real-world applications such medical treatment (Ramos-Murguialday et al., 2013, Shanechi, 2019], virtual reality [Lécuyer et al., 2008], etc. While Hopfield models serve as computational models for simulating human brains and their memory recall system [Liu et al., 2015, Hsu, 2012], KHMs correspond to external devices (storage space) to assist/enhance the process of memory recall.
In this paper, we study the scenario where try optimize the usage of external neurons for memory storage by increasing the separation between memories in such external space (f-space). We show that prevent memory confusion, minimizing separation loss is an effective way utilize the external space efficiently. The closest work we can find is [Morrison et al., 2017] and [Kozachkov al., 2023]. In particular, they use Hopfield (and modern Hopfield or dense associative memory) models as the computational model for human brain. Specifically, Morrison et al. [2017] study the case of memory loss caused by disease or injuries. Their proposed framework is able to consider the level of memory damage and then estimate the required dimension to fully or partially recover memories. Kozachkov et al. [2023] explore the potential of building biological computers through links between transformers and modern Hopfield models. They show that neuron-astrocyte networks can perform the core computations of transformer. In this context, our work provide an improved connection between brain and transformer models, offering more learnable and powerful approach main-e interfaces (BMI).
20

---

C Proofs of Main Text
C.1 Proof of Lemma 2.1
We first introduce helper lemma:
Lemma C.1 ([Ramsauer al., 2020, Hu et al., 2023]). Given real numbers, a, E R. If the equation
ac + clnc b 0,
holds, then the solution is
b Wexexp + Inb))
By [Hu et al., 2023, Corollary 3. we state the well-separation condition of dense modern Hopfield model [Ramsauer et al., 2020].
Lemma C.2 (Well Separation Condition of Dense Modern Hopfield Model [Ramsauer et al., 2020]) Following Definition 2.2, suppose the memory patterns {En]ue[M] are located within the sphere S, = [=|||> E s R}. Then, assuming normalized memory patterns, the retrieval dynamics TMHM maps the sphere S, onto itself under the following conditions:
1. The initial query x is located within the sphere Sp. i.e. x E Sy.
2. The well-separation condition is satisfied, which is given by:
2(M 1) 2R. h
R
This specifies the necessary condition for a pattern En to be stored in E and be able to retrieved by T.
Proof of Lemma 2.1. Let min Min Ag and uun be the angle between two patterns ((Ex)
and (E,)). Note that Oz E [0, m].
By Definition 2.7, we have
2((M 11)
min 2 In
+ 2R..
B
Rs
and
A min
Min (1 - cos( [1iccs(0min)) ISHSUSM
where 6mn = MinigususM (1 cos(Bo,au)) E 10, m].
Then, it holds
1 2 In 2(( 1)
- cas (oos(mmma))
+ +22
(C.1)
3
Next, Let 1 p be the success storage and retrieval probability under Definition 2.7. We have
1 In
2(M
1
P
A +
+ 2R
1 p.
3
Rs
By (C.1), we have
P(1 cos(Ommn)
2 1 In
2(M - 22M-11)
P
2Rg
1ppp
(C.2)
3
Ra.
21

---

We observe that cos(f connects to the maximal separation loss via
C
2
com()
2t
Following the proof of [Hu et al., 2023, Lemma 3.1] and by Lemma C.I, it holds
M = VpC 1/4
with some real value C' IR Here C is solution to the upper branch of the Lambert W function deduced from (C.2),
C Wolexpla+Inie +
(C.3)
where
2( 2(vP
1)
+ +1]
4,3
a =
In
and
(C.4)
d
Rg.
5(d - 1)
Then, arrive lower bound on the exponential storage capacity M:
M 2 +
(C.5)
To compare the the results from [Ramsauer et al., 2020, Theorem 3] (with the assumption of pattern normalization), we denote the results from [Ramsauer et al., 2020] with notation, i.e.
ā = d
4
In
V
+ +1
and b= 6.
R
And we also have Onin MinigusesM (1 cos(( [0, x be the angle between two raw memory patterns &v, Eu.
We denote the optimal separation loss be (E),,, and the loss value t-th step be (3)
We denote Rt be the corresponding R4 when L+ its global minimum.
By (3.2), the convexity of La, the optimality of La gives
R% 2V
Ra.
Next, we prove that to achieve R4 2 R, we need O
1 (3 sub linear time (iterations.).
Recall that :== Mine.ey 1e5w Eull- By Rs
/Do(3)/-1/2, for R& 2 R. we need
(x)
1 Min ||E5 Enll.
2 perzu
which implies, by t > 0,
(x < - (2R)
(C.6)
Subtracting (E) on both sides, we get
(3) C3) (2R) C3 =
22

---

Which implies the iteration number needed to achieve improved memory capacity bound is:
N = -1122
(411182 - (3)
which gives us a sub-linear time complexity.
Let
2(vD 1)
+1]. and b 43 5 1)
In
Rs
As long Algorithm
runs for O -1/11R2-2200 (2) iterations, its output Ob satisfies
ā S a,
(C.7)
and
Č = Wo (exp ā Inb]) S Wo (exp(a+Inob) C.
(C.8)
Thus, we have the memory capacity comparison as
M vpc VDO M.
Since the upper branch of Lambert W function monotonically increasing on its domain, Rg. > R implies
M = voct 2 -/O=== = M.
Hence we finish the proof.
23

---

C.2 Proofs of Lemma 2.2 and Proposition 2.1
Lemma C.3 (Capacity of Optimal Spherical Code, Lemma 2.2 Restated), Given fixed D > 1, and its corresponding M if an optimal code Copt is in S and has size M then Copt E A D
Proposition C.1 (Optimal Memory Capacity, Proposition 2.1 Restated), Following Lemma 2.2, we have
M x cD,
for some c > Here x indicates matching upper and lower bounds up to constant factors.
Proof.
By Assumption 1, all memories are normalized. Thus, have
Rs
2
max M.ElM
(D(Sx), ((E))
(By (2.1))
1 +
(C.9)
V 2
Recall the storage condition
1
2(M 1)
A
In
B
R
Here consider the minimal A among all possible μr [M]. We plug (C.9) into the well-separation
condition and change 3 A min' We arrive
2(M - 1)
A
+ min
In
3
min /2
By rearranging terms, we get
1
2 1
A
+
In
Amin
In (2(M - 1)).
23
The derivative w.r.t. 4 min on the LHS
23 4 min
indicating that LHS is increasing in A min for all A 2
> 0. The derivative w.r.t M on the RHS is
min
3(M - 1)'
indicating that the RHS is increasing in M for all > 1. Since we are handling A this property holds for all A
+ Let the minimum value for min that satisfies the storage condition such that
8
23 In
(2(M - 1)) 5 z B
2
With the definition of optimal spherical code, we have 8 < - p². Thus an optimal spherical code must satisfy this inequality.
24

---

Now we further analyze the quantity M Let 0 = arecos (p(Copt)). with @ E (0, %/2). we apply the upper bound in [Kabatiansky and Levenshtein, 1978], we get
((0) 2 M
where & E H. With the above result, we get M = o(c ) for some <>> 1.
For the lower bound of M*, the classic sphere code bound in [Chabauty, 1953, Shannon, 1959, Wyner, 1965], and get
1 T(Do/2) M
TT(DD--11 1/2) /-" sin Do (
cos sin 12 (0)
(1+ V
where I E P
Therefore, we have
cos
(o(tto)))) 2 M 2 (1 (1+) (21)))22DDD
2x
sim De
(0)
where :00) > log sin(().. (0). and o(-) is "strictly slower than" notation as De + 00.
This completes the proof. Tighter bounds can be found in [Jenssen et al., 2018, Fernández al., 2021]. We selected bounds that most clearly show the exponential scaling behavior for better intuition. O
25

---

C.3 Proof of Theorem 3.1
We first restate Theorem 3.1:
Theorem C.1 (Theorem 3.1 Restated), For any possible integer M, we have
M Σ ==1
lim sup 7-0
argmin *EH
Lo (Sa,
f argmin LiladMMa (f),
M
DEW
where all H is the hypothesis space of Φ.
Then introduce helper lemma.
Lemma C.4. Let 7) be
M
Co T. loo Σ
Lo (Sn T).
p=1
r) converges uniformly LHardMax ( + O.
Proof of Theorem 3.1. We first organize terms in (3.2). We obtain:
(E()))
(e(su))) 1) -1og log
M
(I(E)) 2((EW)) }
(p(Epr T) = log
exp
Σ
exp
T
T
M
(5 Ev) }}
log
Σ expo
A=1
We define a helper function Co. denoted as
M Lo (., = .og
Σ 1=1
(2, $
(C.10)
We have
Co (2,
log
Lo (E
M
M
(E(E)) ((
}}
= T log
log
1+
Σ
exp
==1
ME(M]V
Due to the fact that m/(1+a) log(1 2.) < for all x 1, have:
Eve[M]N exp
M
(O(E))
1 1 E EV'E/MIVP exp
(((
M
(O(E)), ((E))) -1
log
1+ Σ
exp
PE(M]
($(E), ((E,))
exp
(C.11)
"E(Md]a
26

---

Given the fact that (E))), ((Ew)) exponential function, we obtain:
v for all possible v. p. With the monotonicity of the
M
(P(E,,, ((E))) - 1 S M
exp
7
"E[M M
Combining this with LHS of (C.11), we have
E Eve(MiRa exp
M
(D(E)), ((E))) (((E)))((()))1 -11
log
1
Σ exp
7
ME(M
M
(+(E), ((Eu))
exp
5
Summing over all possible
[M] we have
M
M
exp
(O(E))
M
M
(o(E)), ((EW)) 11)
log
1+
Σ
exp
T
p=1
DE[M]Na
M
M
(D(E)), ((E))) 1
Σ
exp
T
#=1
==1
DE[M]
Using the property of max function, we further get
((.
exp
M.PE E. MEF
M
M
Eve(MIN exp
(O(EW),((E.)))
M
==1
M
M
(E(E)) ((EW))
log
1+
Σ >E[M]\a
exp
(D(E)), ((Gx))
< M (M (M -)
max [.M
exp
Now by taking logarithmic on both sides and multiplying all three terms by 7 we get
max M.PEMM).NA
(()(),), (E,))) 1) T log . < Lo(2, 7) S 7 log (M (M 1))
max
(19(EL). ((E.)) -1).
u.ME M.M((M],nn Mijatt
27

---

By max ( poy (Ap,v) = LaaddMax (Φ) 1, we have
HardMMa (1) Flog M 1 Co @ r) - 7 log M (M 1) HardMaax (1) 1. Therefore, for any > 0, by taking TO
max (log MM (MMllooMMMMMM--M (M-) we have
[Co(#, HardMar i max M, log(l (M- se,
for any 70- That is, Lo(D, 7) converges uniformly to LaanMaa ( leading to Lemma C.4.
Now know Lo( 7) converges uniformly HardMaa (+) 0, by [Rockafellar and Wets, 2009, Proposition 7.15], we have L,( r-converges to HardMaax ()) as well. By [Braides, 2006, Theorem 2.10], we have
lim inf argmin Co T) argmin CaardMax (.). DEH
4CH
This completes the proof
C.4 Proof of Proposition 3.1
Proof. We first define the one-vs-one distance.
Definition C.1 (one-vs ve-one distance). We define the one-vs-one distance of set of points (yp)== C Sd-11 with [ = M, as
Pone-vs-one
(V) = min minl Up
The one-vs-one distance is lower bounded as following Lemma C.5. [Jiang et al., 2023, Lemma C.13]
VT r d+l M
2
Pone one (V).
(C.12)
T +1)
VCSd
Note that by the definition of the one-vs-one distance, we have the equivalent expression such that
Ponc-vs-onc (V)
min (Up: mp)) - (Kipy Up)
2
v.PE[M]
Combining the above property, Lemma C.5 and a known upper bound in [Moore, 1974, Theorem 1]. obtain:
1 V r Da+1
D
2 T
Dat1) D
2
2
2
M r ( +1
min
M
r
The upper bound in [Moore, 1974] is derived by the normalized surface area of a spherical cap of angular radius 6.
"In general, Co converges uniformly to Chadmax as 7 goes to O with an error rate of Lo Lnartmax S 2r (Mg(
28

---

D Experimental Details
Computational Environments. All experiments are conducted on the platform with NVIDIA GEFORCE RTX 2080 and INTEL XEON SILVER 4214 2.20GHz. We use PyTorch 1.8.0 for all experiments. The experiments are relatively lightweight which can also be ran on CPU-only environments.
D.1 Metastable States
Hyperparameters. Table 3.
The hyperparameters used for the metastable state experiment is listed in
Table 3: Hyperparameter used Metastable State Experiment.
parameter
Synthetic
MNIST
Optimizer
Adam
Adam
Learning Iteration N
20
20
Batch Size
10
16
Update Rule Iteration
20
Learning Rate
0.1
0.1
Memory set size M
10
60000
Pattern Dimension d
5
784
Feature Dimension D+p
200
4
0.1
threshold for
0.01
0.01
Implementation Details. The batch size in Table denotes the batch size we use train the feature map T. For the synthetic dataset, we directly train & on the whole memory set. For the softmax threshold, we follow the settings used in [Santos et al., 2024].
D.2 Energy Landscape
Hyperparameters. The hyperparameters we used for the basins of attraction experiment is listed
T.
Table 4: Hyperparameter used in the energy landscape experiment.
parameter
2-Points
4-Points
Optimizer
SGD
SGD
Learning Iteration N
Learning Rate
0.1
0.1
Memory set size M
Pattern Dimension d
2
Feature Dimension D4
20
0.9
query grid resolution
40
40 hot
40 40
color map
hot
Implementation Details. We first prepare a set of randomly generated patterns as memories. Next we record its energy landscape with respect to different query (the coordinate in the figure). Next train d for 5 iterations and record its resulting energy landscape with N 1, 2. 5. We use the entmax and sparsemax package used in [Peters et al., 2019].
29

---

D.3 Basins of Attraction
Hyperparameters. in Table 5.
The hyperparameters we used for the basins of attraction experiment listed
Table 5: Hyperparameter used in the basins of attraction experiment.
parameter
Synthetic
Optimizer
Adam
Learning Iteration N
5
Update Rule Iteration
5
Learning Rate
0.1
Memory set size M
5
Pattern Dimension d
5
Feature Dimension D
5
3
20
query grid resolution
100 x 100
Implementation Details. energy gradient in Figure 1. Demonstrating that the standard MHM and its variants are not able to converge to fixed points fast.
We specifically set the update rule iteration as we see the sharp
D.4 Simulation of Proposition 3.1
We provide numerical simulation of our bound with De 3. We take the known solution of minimal separation published ht attpp:/ tpt http:///nilllaaneee com/ hwtpa//cckigs///// a ground truth.
Separation Bound (d=3)
2.00
Ground Truth
upper bound
1.75
lower bound
1.50
Amin
1.00
0.75
0.50
0.25
0.00
100
120
M
Figure 3: Separation Bound Numerical Simulation We visualize the bound presented in Proposi-
tion 3.1 in 3-D dimension. The bound goes tighter as the number of points increases.
D.5 Assignment Problems
Here we conduct the point assignment problem in 2D space. In 2D space, the optimal arrangement of six points is well-established: they equally divide the unit circle, with each point neighboring two others.
We consider the case where we try to learn a feature map O under U-Hop+ with 6 different images sampled from CIFARIO We sample each image from cat, dog, car, truck, deer and horse class. Intuitively, cat has closer semantic relationship with dog, car is more similar to truck and deer has closer semantic relationship with horse [Jiang et al., 2023, Neelakantan et al., 2022]. We show that learned feature map consistently puts similar pairs closer to each other in out of 10 trials. This
30

---

implies that while our method does not force or even considers the underlying semantic meanings behind each memories, our feature map is still able to present such relationship. The result is in Figure 4.
Discussion.
The separation loss encourages the feature map to make the whole dataset the most linearly separable each instance. similar analysis can be found in [Dirksen al., 2022, Ghosal et al., 2022]. where they found out that if data has subtle clustered structure, random neural network able to make linearly separable with high probability.
0.75
0.50
cat
dog
car
0.00
truck
-0.25
deer
horse
-0.50
-0.75
-1.00
-1.0
-0.5
0.0
0.5
1.0
Figure 4: Assignment Problem in 2D. We observe that the learned feature map consistently put similar pairs closer to each other, leading to preserving some level of semantic information.
D.6 Additional Experiments
Here observe the loss curve of L w.r.t. different memory set size. We aim verify whether C is able to converge well through proposed algorithm.
Training Average Separation Maximization
0.0035
N- 100
0.0085
0.0075
0.0070
Epoch
Figure Loss Curve of L w.r.t. different memory size. We run separation maximization for 100 epochs on MNIST under settings, M = 100/200. We set = 0.1, learning rate le-3, Dx 100. The result shows L converges fast, which echoes our sub-linear time complexity.
31

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope?
Answer: [Yes]
Justification: In our abstract. we claim we propose new framework to describe the optimal memory capacity of kemeliieed Hopfield models (KHMs) and modern Hopfield models. We consdier stored memory sets as special type of spherical code that all points in the set satisfies the well-separation condition. Next, we show there sublinear time algorithm find optimal feature map for KHMs to achieve maximal memory capacity. The main claims are detailed described in the following sections
Optimal memory capacity for KHMs and MHMs: Section 2, Lemma 2.2.
Memory code: Section 2.2, Definition 2.8.
Optimal capacity algorithm: Section 3.1, Algorithm 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No NA answer 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 other settings.
It fine include aspirational goals as motivation long it clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discussed our limitations in the last section, the limitations paragraph. The time complexity of Algorithm was discussed Section 3.1.
Guidelines:
The answer NA means that the paper has no 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 approximations 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 a 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 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 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 grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't 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 to not penalize honesty concerning limitations.
32

---

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]
Justification: We have several thcoretical results:
(a) Lemma 2.1: Proof in Appendix C.1.
(b) Lemma 2.2: Proof in Appendix C.2.
(c) Theorem 3.1: Proof in Appendix C.3.
(d) Proposition 3.1: Proof in Appendix C.4.
The main assumption we made is normalized memory patterns, which is described in Lemma 2.1 and Lemma 2.2. Similar assumption was also made [Santos et al., 2024, Wu et al., 2024a].
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' 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 reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our experimental results are in Section 4. We describe our experimental details in both Section 4 and Appendix D.
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.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution 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, provide access to the model. general. releasing code and data is often one good way to accomplish also be provided via detailed instructions for how replicate the
this, but reproducibility results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, other means that appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions 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 is new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (c.g., with an open- dataset or instructions for how to construct the dataset).
33

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. closed-source models, it may be that access to the model is limited in some way (e.g.- to registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
the case of
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide the code in our supplementary materials. As for data, we mainly use synthetic data and MNIST in all experiments. We also describe the data generation and download in our code and experimental details.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: /tapps//nnipi http://iisssc..o cc/ ss ssmmiissiinnn sisoPolicccy 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 a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:/ /nipssips//...///// cc/ s Peoiooooollo oolicy for more details.
public/ public/quides gww.geieeeggggg /eudddeee/ooeeeeeeeeeeee
The authors should provide instructions on 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 reproducible, they should state which ones are 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 the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyperparameters, how they chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The details are fully described in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a 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, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report enror bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: The results over at least 5 runs with different random seeds.
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.
34

---

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).
The method for calculating the error bars should be explained (closed form formula, call to 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 the standard error of the mean.
It is OK to report 1-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 of Normality of errors is 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).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
We describe our computational environment in the first paragraph of Appendix D.
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 experi- mental 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 failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, every respect, with the NeurlPS Code of Ethics https:/ /al:://neeue wttppb/lcc/tttcceeeeiiieee
Answer: [Yes]
Justification:
The authors have read and agreed to every aspect of the NeurIPS Code of Ethics.
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 a special consideration 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: [Yes]
Justification:
The broader impacts can be found in the section right after conclusions.
Guidelines:
The answer NA means that there is 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 societal impact.
35

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment 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 par- ticular applications, let alone deployments. However, if there is 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: 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, scraped datasets)?
Answer: [NA]
Justification: The experiments conducted are mostly numerical simulations which does not serve practical usage.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 usage guidelines or restrictions access the model 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 (e.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: For our experiments, we only use datasets provided or generated by PyTorch. PyTorch's licenses can be found in ttttps://githie com wwwpootccpyoorotettttepeppp ma i In/LICENSE
Guidelines:
The answer NA means that the paper does not 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 a 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 package should be provided. For popular datasets, paperswi thcode. cww.co//oooooooo ccom/dtasse datasets s has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
36

---

For existing datasets that are re pe-pakagee, both the original license and the license of the derived asset (if it has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not provide new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their sub- missions 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 anonymize your assets (if applicable). You can either create an anonymized URL or 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, well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowdsourcing our human subjects experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, 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/revieww based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve any crowdsoureing our human subjects experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 applica- ble), such as the institution conducting the review.
37


Reviews:
[{"review_id": "yF5xtfrcot", "reviewer": "Reviewer_UbwM", "summary": "Modern Hopfield Networks (MHNs) are limited because they require sufficient minimal separation $\\Delta_{\\min}$ for theoretical guarantee. Kernelized Hopfield Models (KHNs) mitigate this limitation by storing the memories in the feature space. In particular, theoretical analysis in [Wu et al., 2024a] uses a linear kernel. The current paper proposes an algorithm to find the \"optimal\" feature map using spherical coding. By solving a surrogate optimization problem whose solution converges to the HardMax problem asymptotically with vanishing temperature, the algorithm improves the memory capacity.", "questions": "1. Since MHN is a special case of KHN, how do the current results reduce to the MHN results in [Ramsauer et al., 2020]? Are there any improvements?\n2. Definition 2.7 assumes that the patterns are normalized. This assumption is not explicitly stated elsewhere and are not well-justified.\n3. Definition 2.8 is more like a statement rather than a definition. Why should the definition lead to the conclusion that \"there is a feature map $\\Phi$ such that $\\Phi(V)$ is a memory code\"? \n4. Is the convergence in Theorem 2.2 pointwise convergence or uniform convergence? For a given $\\tau>0,$ what's the error rate?\n5. The proposed algorithm learns a linear map, what about non-linear maps?\n6. In line 597, since you are referring to a known upper bound in a book, it would be better to provide more details for the reader to find the result.\n\nThere are some typos:\nLine 48: does -> is\nLine 105: lower bounded by what? \nDefinition 2.5: It seems that there should be an arg in front of minmax\nDefinition 2.7: satisfies -> satisfy", "limitations": "The paper is of theoretical nature. A paragraph on limitation is given in the main content.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "MHNs emerge as a powerful tool for theoretical understanding of neural networks such as Transformers. The current paper builds upon KHNs and gives analysis of necessary conditions for KHNs to achieve optimal memory capacity. Further, a sub-linear time algorithm is proposed to optimize the feature map.", "weaknesses": "Prior work on KHNs already has analysis using linear kernel. It would be helpful to showcase the improvement brought by the current algorithm to improve clarity and contextualization relative to prior work. Moreover, the experiments only demonstrate the convergence property of the iterations. It would be nice to have more practical experiments on tasks such as multiple instance learning and retrieval. I could improve my evaluation if the authors would address the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **W1:** Prior work on KHNs already has analysis using linear kernels. It would be helpful to showcase the improvement brought by the current algorithm to improve clarity and contextualization relative to prior work. \n\n**Response:** \n\nThe prior work in KHN mainly explains how separation maximization helps capacity but lacks theoretical justification for why their algorithm improves capacity.\nTo fill this gap, this work provides a rigorous theoretical analysis of why and how separation maximization improves KHN memory capacity. Additionally, we introduce the notion of optimal capacity and prove the asymptotic conditions for achieving it.\n\nWe acknowledge that the current draft does not emphasize these points enough. We will update the final version accordingly.\n\n> **W2:** Moreover, the experiments only demonstrate the convergence property of the iterations. It would be nice to have more practical experiments on tasks such as multiple instance learning and retrieval. I could improve my evaluation if the authors would address the questions below.\n\n**Response:**  In response to more experiments, **we have added new MIL results and retrieval results** in Table 2 and Figure 3 of the attached pdf. \n\nThese additional experiments demonstrate clear improvements over standard MHN.\n\n\n> **Q1:** Since MHN is a special case of KHN, how do the current results reduce to the MHN results in [Ramsauer et al., 2020]? Are there any improvements?\n\n**Response:** \n\n**The main difference of reducing to MHN is that MHN does not guarantee the well-separation condition will hold for all memories. Thus, not necessarily to store *all* the given points.**\n\nSecond, MHN does not have an extra feature space to store memories. If the data dimension is too small, it is possible that the well-separation condition is impossible to achieve.\nFor KHNs, since learning iteration of Algorithm 1 and $D_\\Phi$ has no restrictions, one is able to select sufficiently large values of these two, to ensure the well-separation condition holds for all memories. We can also compare KHNs and MHNs with Lemma 2.1. With sufficiently large $D_\\Phi$ and $N$, $R_\\Phi$ will eventually surpass $R$, and thus obtain a higher lower bound.\n\nEmpirically, we conducted additional exps (in Table 2, Figure 3 of the attached pdf) showing improvements of UHop+ over MHN.\n\n> **Q2:** Definition 2.7 assumes that the patterns are normalized. This assumption is not explicitly stated elsewhere and is not well-justified.\n\n**Response:** \n\n**We would like to highlight that this is a commonly used assumption in the analysis of [1, 2] and in experiments in [1, 2, 3].**\n\nA justification for this setup is its connection to transformer attention. The modern Hopfield update rule/retrieval dynamics are often compared to the attention mechanism, where the input query and memory set correspond to Q and K in attention. Since LayerNorm is commonly used in attention layers, this setup reflects real-world scenarios.\n\nAnalyzing non-normalized patterns is left for future work. \n\nLastly, we have added a highlight block for this assumption in `line 92` of the final version.\n\n> **Q3:** Definition 2.8 is more like a statement rather than a definition. Why should the definition lead to the conclusion that \"there is a feature map such that is a memory code\"?\n\n**Response:** Thanks for pointing this out. We recognize this potential confusion and have changed the definition to a Lemma, as it is a derived result from Definitions 2.2 and 2.7.\n\n\n> **Q4:** Is the convergence in Theorem 2.2 pointwise convergence or uniform convergence? For a given what's the error rate?\n\n**Response:** \nThe main purpose of Theorem 2.2 is to show one optimization problem converges to another. The convergence between two functions here is not our main focus. That being said, the convergence between $\\mathcal{L}_0$ and HardMax loss is uniform convergence as $\\tau$ goes to 0. We have made it clear in our manuscript by adding the following in line 589.\n\n>> Given a $\\tau > 0$, for the error rate $\\epsilon$  between the convergence of $\\mathcal{L}_0$ and HardMax Loss, we have $ \\epsilon \\leq 2 \\tau \\log(M)$.\n\n\n> **Q5:** The proposed algorithm learns a linear map, what about non-linear maps?\n\n**Response:** \nYes, Algorithm 1 also works for non-linear maps. \n\nWe would like to highlight that only linear feature maps have been discovered for KHNs. The explicit form of non-linear maps is not yet known. The desired (retrieval dynamics with) non-linear map should satisfy fixed-point convergence and monotonic energy minimization to be well-defined under the KHN framework. Discovering its explicit form is left for future work.\n\n> **Q6:** In line 597, since you are referring to a known upper bound in a book, it would be better to provide more details for the reader to find the result.\n\n**Response:** Thank you for pointing this out. We have modified the citation to [Thm 1, Moore 1974].\n\n> **Q7:** There are some typos: Line 48: does -> is Line 105: lower bounded by what? Definition 2.5: It seems that there should be an arg in front of minmax Definition 2.7: satisfies -> satisfy\n\n**Response:** \nThank you very much for pointing these out!\nFor Line 105, we change it to: “lower bounded by the following lemma:”\nFor other typos, we have conducted another round of proofreading and fixed all typos.\n\n===\n\n* [1] Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models. ICLR 2024\n* [2] Sparse and Structured Hopfield Networks. ICLR 2024\n* [3] Universal Hopfield Networks: A General Framework for Single-Shot Associative Memory Models\n* [4] Trivializations for gradient-based optimization on manifolds. NIPS 2019\n* [5] Vector Packing in Finite Dimensional Vector Spaces. 1974\n* [6] On kissing numbers and spherical codes in high dimensions. 2018\n* [7] New lower bounds on kissing numbers and spherical codes in high dimensions. 2023\n\n---\nWe hope these responses have addressed your concerns. Thank you!", "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": "5juncjxOrk", "reviewer": "Reviewer_U6Ut", "summary": "The paper is a theoretical analysis of the memory capacity of MHMs and KHMs. It establishes a connection between memory capacity and spherical codes. A method for approximating optimal memory capacity is introduced. Experiments are conducted to validate the theoretical findings.", "questions": "How do you make sure that in Algorithm 1 the weight matrix W keeps the full column rank property from Definition 2.7?", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and easy to follow.\nThe memory capacity is an important problem that can have a significant impact on SOTA architectures like Transformers.\nThe paper is an interesting theoretical discussion and shows a connection between memory and spherical codes in an original manner.\nThe theoretical framework and parts of the proofs are based on [Ramsauer et al., 2020] with adaptions to KHMs.\nThese previous concepts are extended to get results for optimal memory capacity and to introduce an objective for optimal memory capacity.\nThis objective is relaxed by an \"average separation loss\" introduced in [Wu et al, 2024a].", "weaknesses": "The optimization procedure of U-Hop is similar U-Hop+ i.e., Gradient Descent is replaced by PGD.\nDue to this similarity U-Hop should have been added as baseline.\nSince in the standard case MHMs use learnable weight matrices (as can be seen in Eq. 10 of [Ramsauer et al., 2020] and other publications using MHMs) there should have been\na comparison to these MHMs using gradient descent based on the average separation loss.\nWhile memory capacity is an important property it is not immediately clear how much it helps for learning tasks. Therefore, experiments in similar vein to [Wu et al, 2024a]\nshould have been conducted on these tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **W1:** The optimization procedure of U-Hop is similar U-Hop+ i.e., Gradient Descent is replaced by PGD. Due to this similarity U-Hop should have been added as baseline. Since in the standard case MHMs use learnable weight matrices (as can be seen in Eq. 10 of [Ramsauer et al., 2020] and other publications using MHMs) there should have been a comparison to these MHMs using gradient descent based on the average separation loss. \n\n**Response:**\nThank you for pointing that out. The short answer to this is — **Equation 10 in [Ramsauer et al., 2020] does not ensure a well-defined retrieval update of an associative memory model.** \n\nFor reasons:\n* Equation 10 will only be a legal update rule for auto-associative memory if $W_V$ is excluded, with $W_K Y, W_Q R$ being memory and query, instead of $Y, R$. The consideration of hetero-associative memory is beyond the scope of this paper.\n* Equation 10 without $W_V$ minimizes the energy function of $W_K Y$ and $W_Q R$, instead of real data $Y$, $R$. The retrieved pattern will be in $W_K Y$ space instead of $Y$ space. Thus, under MHM construction, we are not able to separate $W_K$ and $Y$.\n\n> **W2:** While memory capacity is an important property it is not immediately clear how much it helps for learning tasks. Therefore, experiments in a similar vein to [Wu et al, 2024a] should have been conducted on these tasks.\n\n**Response:**\nWe recognize that many reviewers have identified the same problem of lacking experiments. In response, **we have added memory retrieval and multiple instance learning experiments to support our main results.** \n\nIn our experimental result, U-Hop and U-Hop+ show similar results, but the theoretical justification of algorithm 1 makes this paper theoretically grounded. \n\nFor more experimental proofs, we have added the multiple instance learning results and retrieval results in Table 2 and Figure 3 of the attached pdf. \n\n\n> **Q1:** How do you make sure that in Algorithm 1 the weight matrix W keeps the full column rank property from Definition 2.7?\n\n**Response:**\n\nIn our algorithm, we do not force W to be full-rank. Existing methods such as [1, 2] are able to satisfy this property in practice. We choose to only analyze the simple PGD case to keep the convergence analysis simple. **Since $\\mathbf{W}$ is in a high-dimensional space, it is almost surely full-rank** (The probability of a randomly initialized matrix having full column-rank is 1). [Remark 2.1, Wu et al 2024] also explains this implication in detail. Thus we choose to not explicitly force this property in practice.\n\n[1] McTorch, a manifold optimization library for deep learning\n[2] Trivializations for Gradient-Based Optimization on Manifolds (NIPS)\n\n===\n\nThank you for your time and feedback! We look forward to further discussions!", "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": "rz7pECcloX", "reviewer": "Reviewer_LSVx", "summary": "This work provides a theoretical analysis of the optimal capacity on both Modern Hopfield Networks (MHNs) and Kernelized Hopfield Networks (KHNs). Specifically, it seeks to answer four fundamental problems: \n1. How does memory capacity affect the gap between memories?\n2. Given a fixed feature dimensionality, how to select an optimal separation function? \n3. Is there a simpler and more efficient algorithm which optimize the kernel?\n4. How to connect the gap between memories and the optimal capacity of KHNs theoretically? \n\nThrough the viewing of the memory set as a spherical code, the work establishes the problem of storing memories as a hard-max problem of maximizing the number of patterns stored, while ensuring that the angle between them is at least a certain constant (which the work does show). Consequently, this portrayal of the problem enables a simpler algorithm to optimize the kernel in contrast to the previous work UHop. Furthermore, the work illustrates that the optimal memory capacity is strongly dependent on the projection function $\\phi$, such that its optimality maximizes the gap (or angle) between each pair of memories.", "questions": "For figure 4, what is the gray dot in the center of the circle? Is it an image (of a class) in CIFAR or just a point indicating the center?\n\nFor the derivative of the RHS of the bound, $\\nabla^\\phi_\\text{min} + \\frac{1}{2\\beta} \\ln (\\frac{1}{2} \\nabla^\\phi_\\text{min}) \\geq \\frac{1}{\\beta} \\ln (2 (M - 1))$, is it not $\\frac{1}{\\beta (M - 1)}$ instead of $\\frac{1}{2\\beta M}$?\n\nIs it possible to see the loss curve for MNIST when optimizing $\\mathbf{W}$? It would be great to see the stability of the new $\\mathcal{L}$ just to get a sense of $O(\\frac{1}{-4tR^2 - \\mathcal{L}^*_\\phi(\\Theta)})$.", "limitations": "There is a significant lack of experimentation (or comparisons) in this work. Other types of MHN might require modifications or a different framework to analyze their optimal capacity and compatibility with KHNs. The feature map is rather simple --- it is a linear affine function. Lastly, the spherical code framework only considers normalized points on the hypersphere.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The formulation of the problem presented in the work is great while the proofs are easy to follow. Moreover, the work achieves its goals in answering its four fundamental questions while providing a nice associative memory framework, which could possibly also be applied to other MHNs.", "weaknesses": "There is a lack of experimentation in this work. It would be great for the work to have comparisons, similar to those detailed in [Uhop](https://arxiv.org/pdf/2404.03827).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **W1:**  There is a lack of experimentation in this work. It would be great for the work to have comparisons, similar to those detailed in Uhop.\n\n**Response:**\n\nThank you for pointing that out. We recognize that many reviewers have identified the same problem of lacking experiments. **We have added additional memory retrieval and multiple instance learning experiments to support our main result.**\n\nThe new multiple instance learning results and retrieval results are in Table 2 and Figure 3 of the attached pdf. \n\n\n> **Q1:** For figure 4, what is the gray dot in the center of the circle? Is it an image (of a class) in CIFAR or just a point indicating the center?\n\n**Response:**\n\nYes, sorry for the confusion. And thanks for your attention in details! We meant to use the dot to indicate the center of the circle, it is not an image in CIFAR. We will remove it in our final version.\n\n> **Q2:** For the derivative of the RHS of the bound, …\n\n**Response:**\nYes, you are correct. Again, thanks for your attention in details!  We have modified our proof accordingly. \n\nMeanwhile, this correction does not affect our conclusion that the RHS is increasing in M. \n\n> **Q3:** Is it possible to see the loss curve for MNIST when $W$ optimizing? It would be great to see the stability of the new $\\mathcal{L}$ just to get a sense of ...?\n\n**Response:**\nYes. Thanks for the suggestion. We provide the visualization of the loss curve for MNIST in Figure 4 of the attached pdf.\n\n===\n\nThank you for your suggestions and attention to details! \n\nWe hope that our responses adequately address the reviewer's concerns, and we look forward to any further feedback.\n\nThank you for your time and consideration!", "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": "nalCJeyMO0", "reviewer": "Reviewer_vthX", "summary": "Suggest a method to optimize kernel versions of Modern Hopfield Models by mapping memories onto well-separated values on a sphere in feature space. Shows that the spherical arrangement of memories is optimal for retrieval (e.g., maximize capacity) and thus can improve upon the linear kernel [Wu et al. 2024a], which optimises memory separation.", "questions": "1.\tHow does the lower bound on memory capacity (lemma 2.1) contribute to the derived algorithm? It’s dependance on R and D of the embedding, but those are not optimized for in the algorithm. Furthermore, it doesn’t depend on the minimal memory separation.\n2.\tWhat is Lambda in Definition 2.8, Theorem 2.1?\n3.\tIs the lower bound from definition 2.7 tight? Can you establish it is not vacuous?", "limitations": "The authors have presented a theoretical approach based on a lower bound for capacity, which may not directly translate to improvement in task performance and has not shown such improvements through experiments.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "*\tOriginality: the idea presented is quite simple and intuitive, but the perfected procedure is non-trivial and can potentially improve memory performance across a large family of relevant MNM-s. \n*\tClarity: the submission is clearly written and well organized.", "weaknesses": "*\tQuality: the algorithm's main justification is a lower bound that is not shown to be tight, so optimizing the minimal overlap between memories is not well supported (here).\n*\tQuality: if the main claim of the paper is improving the capacity to store memories, I would expect a numerical validation that the algorithm improves the number of memories that may be stored or increases the amount of noise that may be tolerated. The included results (sections 3.1 and 3.2) are only qualitative and are achieved on toy problems. Such a comparison can be done relative to plain-vanilla dense MHM or to [Wu et al. 2024a]. \n*\tSignificance: the results are mostly of practical importance for practitioners who wish to implement MHM with an optimal kernel. For that crowd, it is not that important if the algorithm is based on a novel lower bound but that the algorithm works, which needs to be better established.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Weakness\n\n> **W1:** the algorithm's main justification is a lower bound that is not shown to be tight, so optimizing the minimal overlap between memories is not well supported (here)....:\n\n**Response:** \nSorry for the confusion caused. We want to emphasize that the inequality in Def. 2.7 is a condition instead of a lower bound. We understand the submitted draft is a bit ambiguous about this. We have made the following modifications to clarify.\n\n\nWe decompose Def.2.7 into two separate definitions:\n* >**Definition 1 (Well-Separation Condition).** \t\nGiven a set of memory patterns\n`$\\Phi(\\mathcal{V}) = \\{ \\Phi(v_\\mu)\\}_{\\mu=1}^M \\subseteq \\mathbb{S}^{D_\\Phi-1}$`, we say the memory pattern $\\Phi(v_\\mu)$ satisfies the well-separation condition is the following holds:\n$$\n\t\\Delta_{\\mu}^\\Phi \\geq \\frac{1}{\\beta} \\ln\\( \\frac{  2(M-1)}{R_\\Phi}\\).\n$$\n\n* > **Definition 2. (Memory Code).** Given a finite set of points `$\\Phi(\\mathcal{V}) = \\{ \\Phi(v_\\mu)\\}_{\\mu=1}^M \\subseteq \\mathbb{S}^{D_\\Phi-1}$`, and $\\beta > 0$.\nWe say $\\Phi(\\mathcal{V})$\nis a memory code if all points in $\\mathcal{V}$ satisfies the *well-separation* condition, i.e.\n$$\n\t\\Delta_{\\mu}^\\Phi \\geq \\frac{1}{\\beta} \\ln\\( \\frac{  2(M-1)}{R_\\Phi}\\),\n\t\\quad\\forall \\mu \\in [M].\n$$\nFurther, we denote $\\Lambda$ as the set of all memory codes in $\\mathbb{S}^{D_\\Phi - 1}$, such that\n$$\n\t\\Lambda := \\[ \\Phi(\\mathcal{V}) \\quad| \\quad \\Phi(\\mathcal{V})\\quad \\text{is a memory code} \\].\n$$\n \nWe also added intuitive explanations:\n* > Note that this inequality is a desired property of the code/data which benefits memory storage. In the following section, we demonstrate methods to achieve such property for all different $\\mathcal{V}$.\n\n**Moreover, our Algorithm 1 is actually built on an upper bound, given at the inequality in `line 585`.**\n\n\nWe hope these clarifications have addressed your concern.\n\n> **W2:** If the main claim of the paper is improving the capacity to store memories, I would expect a numerical validatio...\n\n**Response:** \nThank you for pointing that out. We recognize that many reviewers have identified the same problem of lacking experiments. **In response, we have added and *multiple instance learning* and *memory retrieval*  experiments to support our main result.**\nPlease see Table 2 and Figure 3 of the attached pdf. \n\nImportantly, these new experimental results indicate\n* KHMs improves the retrieval outcome by a large margin.\n* U-Hop+ improves the MHM based model in multiple instance learning tasks.\n\n> **W3:** Significance: the results are mostly of practical importance for practitioners who wish to implement MHM with an optimal kernel. For that crowd, it is not that important if the algorithm is based on a novel lower bound but that the algorithm works, which needs to be better established.\n\n**Response:** \nThe main purpose of this paper is to \n1. Identify the quantity of optimal memory capacity \n2. Justify a theoretical grounded algorithm to achieve optimal capacity. \n\nWe want to emphasize that, for practical usage, **the method provides empirical improvement with or without our justification.** We will better establish this in our experiment section. Please see attached pdf for more validations.\n\n### Questions\n\n> **Q1:** How does the lower bound on memory capacity (lemma 2.1) contribute to ...\n\n**Response:**  \nTwo main reasons for us to demonstrate Lemma 2.1:\n* Showing the traditional approach in hopfield is all you need does not work under the flexibility provided by KHMs.\n* Demonstrating the exponential scaling behavior in $D_\\Phi$, which corresponds to the quantity $M^\\star$. To emphasize this relationship, we added the following proposition and description.\n\n>> **Proposition.** Following Theorem 2.1, let\n  $\\theta \\in \\( 0, \\frac{\\pi}{2} \\)$, we have\n  $$\t\n    \te^{ \\varphi( \\theta ) D_\\Phi (1 + o(1)) } \\\n    \t\\geq\n    \tM^\\star\n    \t\\geq\n    \t(1 + o(1)) \\sqrt{2 \\pi D_\\Phi} \\cdot\n    \t\\frac{ \\cos{\\theta} }{ \\sin^{D_\\Phi-1}{ \\theta} },\n  $$\n   where $\\theta =  \\arccos\\(\\rho( C_{opt} )\\)$, and $\\varphi(\\theta) = -\\log \\sin{\\theta}$.\n\nAnd a remark\n\n>> **Remark.** We have $M^\\star = O(c^{D_\\Phi})$, for some $c > 1$. This property echoes the exponential capacity lower bound in Lemma 2.1.\n\n---\n\n> **Q2:** What is Lambda in Definition 2.8, Theorem 2.1?\n\n**Response:** Lambda is defined in the last line of our Definition 2.7. It refers to the set containing all memory codes.\n\n> **Q3:** Is the lower bound from definition 2.7 tight? Can you establish it is not vacuous?\n\n**Response:** \nThe inequality in Definition 2.7 does not serve as a lower bound. Instead, it is a condition of data that we want to achieve with Algorithm 1 because the existence of this condition benefits memory storage. The goal of algorithm 1 is to make this condition hold for all memories in feature space.\n\nWe would also like to highlight that this is a commonly used storage condition in [1, 2, 3, 4], showing that it is a well established/recognized condition.\n\n* [1] Hopfield Netorks is all you need. ICLR 2021\n* [2] On Sparse Modern Hopfield model. NeurIPS 2023\n* [3] Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models ICML 2024.\n* [4] Outlier-Efficient Hopfield Layers for Large Transformer-Based Models\n\n===\n\nThank you for your suggestions and attention to details!\n\nWe hope that our responses adequately address your concerns, and we look forward to any further feedback.\n\nThank you again for your time and consideration!", "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:
## General Response/Rebuttal Summary

Dear Reviewers, 

We thank the reviewers for the insightful questions and reviews.

We have answered all the questions and addressed all the problems in detail in rebuttal and revision.

In response to the reviewers' suggestions, these revisions include additional explanations, refined definitions, paragraphs, and tables to help readers understand this paper. Most importantly, 3 new experimental studies have been added to further clarify U-Hop+'s superiority, including **Multiple Instance Learning (MIL)**, **Memory Retrieval Task** and **Loss Curve w.r.t. Different Memory Size.** 

---

### **Revision Details**

**Major Revisions Include:**

* **3 Additional Experiments with Uniformly Positive Results:** [`UbwM`,`U6Ut`, `LSVx`,`vthX`]
  * **Multiple Instance Learning (MIL)**: We compare the performance of modern Hopfield and Sparse modern Hopfield with and without U-Hop+. The results show U-Hop+ constantly improves models performance in MIL tasks. [`Table 2 of Attached PDF` ]
  * **Memory Retrieval Task**: We conduct memory retrieval experiments with respect to memory size change and different noise perturbation on queries. We use MNIST and CIFAR10 as datasets. The results show with U-Hop+, retrieval dynamics enjoy lower retrieval error. [`Figure 3 of Attached PDF` ]
  * **Loss Curve w.r.t. Different Memory Size:** We plot the loss curve of Algorithm 1 on MNIST, to demonstrate the sub-linear time convergence of $\mathcal{L}_0$. [`Figure 4 of Attached PDF`] 

* **Clarify Assumption of Normalized Patterns** [`UbwM, LSVx`]
  * We specify the “patterns are normalized” as a separated definition in `line 92`

* **Refined Definition 2.7:** [`UbwM`,`U6Ut`,`vthX`]
  * For clarity, we divide the original Def. 2.7 into 2 separated definitions: A & B
  * A: Well-separation condition (A condition for KHMs to storage a given memory pattern)
  * B: Memory Code (spherical codes with all points satisfy the well-separation condition)

* **A Paragraph of Comparison with Prior Works (UHop or KHN)** [`U6Ut`]
  * Prior KHN lacks theoretical justification for how separation maximization helps capacity
  * To fill this gap, this work provides a rigorous theoretical analysis of why and how separation maximization improves KHN memory capacity
  * Additionally, we introduce the notion of optimal capacity and prove the asymptotic conditions for achieving it.

* **Change Definition 2.8 to Proposition 2.1** [`UbwM`]
	* We modify Definition 2.8 into a Proposition since it is a derived result from the previous definition and theorem.

**Minor Revisions Include:**

* Proofread the manuscript and fixed all identified typos and grammatical errors by reviewers and authors.
* Added explanation for the upper bound used in `line 597` 
* Added explanation for the uniform convergence between $\mathcal{L}_0$ and the HardMax loss.
* Changed `line 590` from $1/2\beta M$ to $1/ (\beta(M-1)$ 


We hope these revisions address the reviewers' concerns and improve the overall quality of our paper.

Thank you again for your review!

Best regards,

Authors

Meta-review: There is general agreement between the reviewers that this submission is worth being accepted for its theoretical contributions. There was some debate whether empirical validations would be necessary. The authors added them during the rebuttal and they were judged diversely by the reviewers, with some being convinced, others not. Overall, I recommend acceptance as a poster and urge the authors to take extra care to incorporate the changes promised in the rebuttal when preparing the final version.
Decision: Accept (poster)