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_cc_2024_Conference
Published: 2024-05-03 22:24:39

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.

Main paper: 
 introduction: 
 We study the optimal memorization capacity of Kernelized modern Hopfield Models (KHMs) [Wu et al., 2024a] , propose a sublinear-time algorithm to achieve it, and analyze parameter selection for these models. KHMs belong to a class of transformer-compatible Dense Associative Memory [Krotov and Hopfield, 2021, 2016] known as 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-compatible 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., 2023a , 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 is fundamental and of practical importance. One one hand, it prevents MHMs from functioning as full-fledged content-addressable 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 neuroscience and large foundation model research [Bietti et al., 2024 , Krotov, 2023 , Kozachkov et al., 2023 , Cabannes et al., 2023 , Hoover et al., 2023b] . 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 a sublinear-time algorithm to achieve it.Let Ξ := [ξ 1 , • • • , ξ M ] ∈ R d×M be a set of memory patterns where each column (indexed by µ ∈ [M ]) represents a memory ξ µ ∈ R d , and let x ∈ R d 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 x t → x t+1 with its update rule T (x t ), for some t ∈ {0, 1, ...}. This update rule converge to a fixed point x ⋆ , defined by x ⋆ = T (x ⋆ ). x ⋆ is the retrieved pattern2 based on initial query x 0 . Explicitly, iteratively updating x with T is defined as a process of minimization to an energy function E(x). For example, the Modern Hopfield Model [Ramsauer et al., 2020] has the energy function:EQUATIONwhere lse(β, z) := log M µ=1 exp{βz µ } , with some β > 0. With the Concave-Convex Procedure (CCCP) [Yuille and Rangarajan, 2001] , (1.1) is monotonically decreased by an iterative update rulex t+1 ← T (x t ) = Ξ • Softmax(βΞ T x t ).(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] . It also provides a model-based interpretation of the transformer attention mechanism [Wu et al., 2024a ,b, Hu et al., 2024a ,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 µ-th memory (µ ∈ [M ]), the retrieval error of MHM is exponentially suppressed by the pattern separation: ∆ µ := ⟨ξ µ , ξ µ ⟩ -max ν,ν̸ =µ ⟨ξ ν , ξ µ ⟩ ( [Wu et al., 2024a, Eqn. 1.3] or [Hu et al., 2023, Eqn. 2.7] ). This ∆ µ -dependence in MHM retrieval accuracy also manifests the ∆ µ -dependence in memory capacity. To see this, recall that the standard memory capacity is a high-probability bound based on thresholding the separation ∆ µ for each pattern µ ∈ [M ] to determine storage and retrieval (Section 2.1). Explicitly, storing a pattern requires its separation to exceed a threshold that decreases with the minimal separation: ∆ min := min µ∈[M ] ∆ µ . Namely, a larger ∆ min leads to larger capacity (Appendix B.1). Thus, the capacity depends on ∆ min . Yet, ∆ min depends on the stored memories Ξ. This Ξ-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: ∆ Φ µ , where ∆ Φ µ := K (ξ µ , ξ µ ) -max ν,ν̸ =µ K (ξ ν , ξ µ ) .x t+1 ← T Φ (x t ) := Ξ • Softmax (βK(Ξ, x)) , E K (x) = 1 2 K(x,Notably, ∆ Φ min is learnable and parameterized via Φ. Wu et al. [2024a] point out that with Φ(x) = W x, where W ∈ R d×DΦ , finding a suitable Φ that maximizes ∆ Φ min benefits memory storage. This construction of Φ preserves key MHM properties, such as accurate [Wu et al., 2024a, Lemma 2.1] and consistent [Wu et al., 2024a, Thm 2 .1] retrieval. However, direct maximization of ∆ Φ min is challenging due to its max-min nature. To circumvent, Wu et al. [2024a] propose a surrogate loss to maximize ∆ Φ µ 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 ∆ Φ µ on average, rather than ∆ Φ min , raises questions about how their surrogate loss benefits memory storage. Moreover, the impact of ∆ Φ min on memory capacity lacks a clear analytical characterization, and no theoretical analysis confirms whether maximizing ∆ Φ 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 a 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-separation condition [Hu et al., 2023, Thm 3.1] . We term this spherical code as memory code. Surprisingly, this unique connection enables a 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 a 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-Hop+, 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+ significantly reduces metastable states on both MNIST and synthetic datasets, indicating larger memory capacity; (iii) with U-Hop+, the KHMs update rule converges to fixed points faster.Organization. Section 1 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 Φ. Section 3.2 discusses the relationship between Φ and M . Section 4 includes numerical experiments.  
main theory: 
 We provide a 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 a 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:3 Assumption 1. We assume memory patterns ∥ξ µ ∥ = 1 in the rest of our paper.We start by showing the memory capacity of KHM using the standard capacity lower bound introduced by Ramsauer et al. [2020] . This provides a direct comparison between KHMs and previous works.The definition of the generalized fixed point [Sriperumbudur and Lanckriet, 2009] is Generalized Fixed Point [Sriperumbudur and Lanckriet, 2009] ). We say a set S ⊆ R d is a generalized fixed point w.r.t. T if T (y) ∈ S for every y ∈ S.Definition 2.1 (Remark 1. In contrast to Definition 2.1, a fixed point of T is a point y satisfying T (y) = y.Let S Φ µ be a ball with radius R Φ 4 centered at every memory pattern in the feature space Φ(ξ µ ):S Φ µ = {y | ∥Φ(ξ µ ) -y∥ ≤ R Φ }, where R Φ := 1 2 min µ,ν∈[M ] µ̸ =ν ∥Φ(ξ µ ) -Φ(ξ ν )∥. (2.1)Following [Wu et al., 2024a] , we define the memory storage and retrieval as:Definition 2.2 (Pattern Storage and Retrieval). We say a memory pattern ξ µ is stored if S Φ µ is a generalized fixed point of T , and there exists a fixed point x ⋆ µ ∈ S Φ µ . A memory pattern ξ µ gets ϵ-retrieved by T with an input queryx if ∥T (x) -ξ µ ∥ ≤ ϵ.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 of KHM). Let 1 -p be the probability of successfully storing and retrieving a pattern. Assuming the patterns are normalized, the number of patterns M Φ that can be stored and retrieved by the KHM, following the update rule (1.3), is lower-bounded by: Proof. Our proof follows [Hu et al., 2023 , Wu et al., 2024b] . See Appendix C.1 for a proof.M Φ ≥ √ pC (DΦ-1)/4 ,With a fixed D Φ , the highest lower bound of Lemma 2.1 corresponds to specific a Φ that maximizes R Φ . This provides an intuitive insight on the design of separation loss [Wu et al., 2024a, Definition 2.2] for kernel learning in [Wu et al., 2024a, Algorithm 1] . With an additional feature space, KHM has an exponential memory capacity in D Φ that does not depend on d. When D Φ = d, KHMs obtain a tighter lower bound than MHMs if R Φ > R. This bound connects the storage capacities of KHMs and MHMs, showing that their capacities scale exponentially with respect to D Φ and d.There are two aspects the lower bound in Lemma 2.1 does not address: the maximal capacity of KHMs and the flexibility of choosing different Φ in KHMs. Therefore, we present a new framework using spherical codes to 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 S d-1 is a finite set C N = {c 1 , ..., c N } of S d-1 with N points, where c i ∈ R d for i ∈ [N ] and |C N | = N .Definition 2.4 (Minimal Separation). The minimal separation ρ(C N ) of a spherical code C N is the maximal inner product between two distinct points inC N : ρ(C N ) = max ci,cj ∈C N ⟨c i , c j ⟩ , for every i ̸ = j.attention-mechanism and the input query and memory set correspond to Q, K for attention. As LayerNorm is a commonly used strategy in attention layers, this setup can also be seen in real-world scenarios. 4 By definition, neighborhoods do not overlap:S Φ µ ∩ S Φ ν = ∅ for ν ̸ = µ.Definition 2.5 (Optimal Spherical Code). Let C N = {c 1 , . . . , c N } ⊆ S d-1 be a d-dimensional spherical code with N points. An optimal spherical code C ⋆ N minimizes the maximal pairwise inner product, which corresponds to maximizing the minimal separation between points in the code. Formally, the optimal spherical code C ⋆ N is defined as:C ⋆ N = argmin C N ⊂S d-1 max i̸ =j ⟨c i , c j ⟩ , for i, j ∈ [N ].The minimal separation of the optimal spherical code is denoted as ρ ⋆ . a a The optimal arrangement of most spherical codes is unknown, except for specific pairs of (d, N ). A list of known optimal arrangements and minimal separations can be found at http://neilsloane.com/ packings/ and in [Conway and Sloane, 2013] .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 Φ ∈ H, Φ : S d-1 → S DΦ-1 is a linear map defined by a matrix W ∈ R d×DΦ .2. The matrix W has full column rank.3. When applying Φ to different inputs:• For a vector ξ ∈ R d , Φ(ξ) = W T ξ ∈ R DΦ . • For a matrix Ξ ∈ R d×M , Φ(Ξ) = (Φ(ξ 1 ), . . . , Φ(ξ M )) ∈ R DΦ×M . • For a set of vectors V = {v 1 , . . . , v N }, Φ(V) = {Φ(v 1 ), . . . , Φ(v N )} 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 .1] 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 (Kernelized Well-Separation Condition [Wu et al., 2024a ,b, Hu et al., 2023 , Ramsauer et al., 2020] ). Given a set of kernelized memory patterns Φ(Ξ) = {Φ(ξ µ )} M µ=1 ⊆ S DΦ-1 , the kernelized memory pattern Φ(ξ µ ) satisfies the well-separation condition if the following holds:∆ Φ µ ≥ 1 β ln 2(M -1) R Φ , (2.2)where the inverse temperature β is given by (1.3) and R Φ is defined by (2.1).The inequality (2.2) is a necessary condition for the µ-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 ∈ N + , β > 0, D Φ > 1 and Φ ∈ H. For any finite set Φ(Ξ) = {Φ(ξ µ )} M µ=1 ⊆ S DΦ-1 , we say the set Φ(Ξ) is a memory code if all points in Φ(Ξ) satisfies (2.2). Further, we denote Λ DΦ as the set of all memory codes in S DΦ-1 , including all possible Ξ, Φ.Notably, Λ includes all the possible pattern sets {Φ(Ξ)} 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 S DΦ-1 . This leads to our 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 Λ DΦ , i.e., M ⋆ := max Φ(Ξ)∈Λ |Φ(Ξ)| for all possible Ξ, Φ. Definition 2.9 specifies the largest possible memory code in Λ DΦ for a given D Φ . Let Ξ denote the memory set associated with M ⋆ , such that ∥ Ξ∥ = M ⋆ . To store all patterns in Ξ, we need to find a suitable feature map Φ such that Φ( Ξ) is a 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 C opt is in S DΦ-1 and has size M ⋆ , then C opt ∈ Λ DΦ .Proposition 2.1 (Optimal Memory Capacity). Following Lemma 2.2, we haveM ⋆ ≍ c DΦ ,for some c > 1. 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 a increasing function w.r.t. the minimal separation value. For Proposition 2.1, we utilize the upper bound in [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 D Φ . This capacity bound is provably tight and optimal for large feature dimension D Φ . It 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 Ξ of size M , the memory storage problem with KHMs divides into two sub-problems:(P1) Finding a sufficiently large D Φ (in Section 3.2), and (P2) Finding a Φ such that Φ(Ξ) is an optimal spherical code (in Section 3.1).Next, we examine these two sub-problems and present a sub-linear time algorithm to solve them.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 1 was discussed in 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren'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. 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 in [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 or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged 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 proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
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.Here we present an asymptotic result showing that an algorithm exists to find the optimal Φ for maximizing memory storage in dimension D Φ . Building on the results from the previous sections, we consider the following problem:Problem 1 (HardMax Problem). Given a memory set Ξ = {ξ 1 , . . . , ξ M }, and assuming that D Φ is sufficiently large to satisfy (2.2), we define the HardMax problem as finding a Φ such that Φ(Ξ) forms an optimal spherical code:min Φ∈H L HardMax (Φ), where L HardMax (Φ) := max ν,µ∈[M ],ν̸ =µ ⟨Φ(ξ µ ), Φ(ξ ν )⟩ ≥ ρ ⋆ . (3.1)This problem setup involves finding a Φ such that Φ(Ξ) forms an optimal spherical code. Ideally, a more expressive function class H would simplify finding such a Φ; 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 [Hsieh 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 τ > 0, given a set of memory patterns Ξ and a feature map Φ, we define the average separation loss asL(Ξ, τ, Φ) := 1 M M µ=1 ℓ µ (Ξ, Φ, τ ), where ℓ µ (Ξ, Φ, τ ) := log M ν=1 exp ⟨Φ(ξ µ ), Φ(ξ ν )⟩ τ .(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 havelim sup τ →0 argmin Φ∈H L(Ξ, Φ, τ ) ⊆ argmin Φ∈H L HardMax (Φ). Algorithm 1 U-Hop+ Input: Iterations N , feature map Φ(x) := W x, memory set Ξ, learning rate γ ≤ 1/G where G is the Lipschitz constant of L Output: x 1: W 0 ← W 2: for t = 0, ...N -1 do 3: W t+1 ← PGD (W t , γ, Ξ) . 4: end for 5: return W N Proof.we first introduce a helper function L 0 in (C.10). We show that as τ → 0, L 0 converges uniformly to L HardMax . Then, we prove that optimizing L 0 and L yields the same optimal solution. Please see Appendix C.3 for a 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 a theoretical justification for the empirical success of [Wu et al., 2024a] . In particular, the surrogate objective -the maximizing average separation between memories -leads to provably optimal memory capacity in 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 (τ = 1) in [Wu et al., 2024a] is sufficient for a wide range of applications.U-Hop+: Sub-Linear Time Algorithm for Achieving Optimal Memory Capacity. Next, we present Algorithm 1 for finding a Φ 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 an unconstrained one. Several methods satisfy the requirements in Definition 2.6; we discuss them in Appendix B.2. We denote the learning rate as γ, the input matrix of the loss function as X, and the weight matrix as W . We define a single Projected Gradient Descent (PGD) step asW t+1 = PGD(W t , γ, X),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 γ ≤ 1/G, yields a sub-linear convergence rate of O( 1 /N) [Iusem, 2003] . This provides an asymptotic solution to the first sub-problem ((P1)). Next, we examine the relationship between feature dimension D Φ and the number of memories M .This subsection analyzes the minimum D Φ to store a given set of M memories. Based on the wellseparation condition and the derivation in Appendix C.2, the required ∆ Φ min to store M memories scales as O(ln(M )). With this insight, the following proposition shows the scaling behavior of required D Φ with respect to M and ∆ Φ min .Proposition 3.1. Let M ⋆ be the optimal memory capacity in S DΦ and Φ ∈ H. For any optimal code C ⋆ in S DΦ-1 of size M ⋆ , the minimal separation ρ(C ⋆ ) is bounded by:1 2 √ π M ⋆ • Γ DΦ+1 2 Γ DΦ 2 + 1 2 D Φ -1 ≤ max Φ∈H ∆ Φ min ≤ 2 2 √ π M ⋆ • Γ DΦ+1 2 Γ DΦ 2 1 D Φ -1, where Γ(•) is the gamma function.Remark 2. By gamma function asymptotics, Proposition 3.1 is consistent with Proposition 2.1.Proof. Please see Appendix C.4 for a detailed proof. Proposition 3.1 establishes the separation value for memory codes that achieve optimal capacity in D Φ -dimensional space. Using this bound, for a given separation value ∆ Φ min , the minimum D Φ required to store M points scales as log M 2 /∆ Φ min . We conduct an experiment to demonstrate the bound's tightness and provide an example with D Φ = 3 in Figure 3 .Table 1 : Distribution of Metastable State (in %). For MNIST, we use the training set as memories and test set as queries. For synthetic data, we randomly generate the memories and queries. ∥p∥ 0 denotes the size of metastable state , which is the amount of non-zero entries of the probability distribution. For Softmax, we use a threshold of 0.01. For hyperparameter settings, see Table 3 We compare the distribution of metastable state size under standard MHM and KHM update rules.. Synthetic MNIST Softmax 1.5-entmax sparsemax Softmax 1.5-entmax sparsemax ∥p∥ 0 - U-Hop+ - U-Hop+ - U-Hop+ - U-Hop+ - U-Hop+ - U-The results are 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 1, it represents that the retrieved pattern converges near the mean of a subset of memories, violating the requirement of S Φ µ ∩ S Φ µ = ∅. 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, we 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 p = Softmax(βx T Ξ). We determine whether the update rule converges to either a single memory or a mixture of memories by observing the probability distribution p. The quantity ∥p∥ 0 represents the size of the metastable state, which is the number of non-zero entries in the probability distribution. In the case of 1.5-entmax and sparsemax, we calculate ∥p∥ 0 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 0. We conduct experiments using both synthetic and MNIST datasets. For MNIST, we use the training set as memories and the test set as queries. For synthetic datasets, we randomly generate memories and queries with Gaussian initialization. To ensure the convergence to the fixed point, we perform multiple updates on the query. For more details, refer to Appendix D.1.Results. On both synthetic and MNIST datasets, it 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 in dense associative memory models [Krotov and Hopfield, 2016] . For the MNIST dataset, we see MHMs show close performance with KHMs under 1.5-entmax and sparsemax, showing that the methods in [Santos et al., 2024 , Wu et al., 2024b , Hu et 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 1 efficiently utilize feature dimensions for memory storage. 
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 1 . We consider two settings: 2 and 4 memories stored in 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, it leads to memory confusion and the presence of metastable states during energy minimization. For experiment details, refer to Appendix D.2.Results. The first row in Figure 1 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 to further separate one point 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, 2, 5). The visualization shows that Algorithm 1 not only separates the local minima better, but also pushes memories closer to the fixed point.Table 2 : Test AUC of Multiple Instance Learning Datasets. We compare the HopfieldPooling-based model with and without U-Hop+. We use the dense [Ramsauer et al., 2020] and sparse [Hu 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 baselines, 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) in [Hu et al., 2023 , Ramsauer et al., 2020] . We exclude the variance as they are all smaller than 0.07. The result shows that even without HPO, U-Hop+ is still able to obtain a performance gain. . We observe this phenomenon across all settings, especially under the 2-point configuration with Softmax and 1.5-entmax, where the low-energy region is 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 to 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 to faster convergence to fixed points due to larger gradients.Figure 2 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 to a 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 not capable of converging to fixed points in 5 updates. While U-Hop+ dramatically improves such aspect, where most queries are able to converge either one of the memories. Moreover, the increased R Φ also leads to a larger S Φ µ , making more queries to converge to a single memory. Additionally, there is a performance gap between Softmax (α = 1) and other sparse variants, which matches the findings in [Santos et al., 2024 , Hu et al., 2023] .We conduct multiple instance learning (MIL) on 4 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 et al., 2023 ] by using a model with 1 embedding layer, 1 HopfieldPooling layer and a linear readout layer. We first utilize Algorithm 1 to "pretrain" the embedding and HopfieldPooling layer, Square points are memories. White area is where queries are not able to converge to a single memory. Colored area is where queries converges to the corresponding memory. The result indicates that U-Hop+ is capable of converging to fixed point fast and reduce metastable states. 1 and 2-entmax corresponds to Softmax [Ramsauer et al., 2020] and Sparsemax [Hu et al., 2023] . and then fine-tune the whole model on 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-Hop+, indicating our method is also effective in practical scenarios. Further, as demonstrated in Figure 5 , the separation loss converges fast, indicating U-Hop+ is a lightweight method for performance boost.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as 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. • 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 a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 or 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. 
discussion and conclusion: 
 This work complements U-Hop [Wu et al., 2024a ] by establishing the optimal capacity of kernelized modern Hopfield models (KHMs) and providing the first tight, optimal memory capacity bound for transformer-compatible dense associative memories. We start by connecting stored memories in KHMs to spherical codes from information theory. We then prove that maximizing memory storage in KHMs requires arranging memories as an optimal spherical code in 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 et 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 a sub-linear time algorithm to achieve this optimal capacity, U-Hop+ (Algorithm 1). U-Hop+ performs this rearrangement with a convergence rate of O( 1 /N). Additionally, we analyze the minimum dimension D Φ required to store M memories. Numerically, we validate the effectiveness of KHMs and demonstrate how Algorithm 1 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 et al., 2023 , Neelakantan et al., 2022] . The primary strategy is to ensure the embeddings of similar instances share similar directions in Euclidean space. At first glance, the approach of pushing all 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 a semantically coherent manner. A discussion of the separation capability of Φ can be found in Figure 4 .Limitations. One limitation of our work only considers linear affine functions as the feature map Φ ∈ H. Additionally, standard spherical code analysis focuses only on normalized points on a hypersphere, ignoring memories with varying magnitudes. We leave them for future research. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a 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). 
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 no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as 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. • If 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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, or 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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 https://github.com/pytorch/pytorch/blob/ main/LICENSE. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets 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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: 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 Kernelized Hopfield models, potentially benefit the area of computational associative (Hopfield) memory models, transformer networks and large foundation models.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 [Hopfield, , 1982] ] that handle binary patterns and have a (sub-)linear memory capacity of O(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 mostly6 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.Transformer-Compatible Dense Associative Memories: 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., 2024a ,c,b, 2023 , Ramsauer et al., 2020] . Therefore, we also refer to them as transformer-compatible dense associative memories. Notably, the defining characteristic of 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 et al., 2024 , OpenAI, 2024 , Hu et 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 et al., 2022 , Bommasani et al., 2021 , Radford et al., 2019 , Devlin, 2018] .As a result, such a 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 et 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 et 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 outlierremoving, deep learning compatible Hopfield layer for robust large pretrained model quantization. Wu et al. [2024a] propose U-Hop facilitating memory retrieval in a learnable 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., 2023b] , 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 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-efficient transformer backbone for large language models and large foundation models. Ota et al. [2023] embed a partial forgetting functionality in modern Hopfield models to enhance model performance.Kernelized Hopfield Models. Wu et al. [2024a] propose kernelized Hopfield models (KHMs)7 , 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 1 to 4] . By maximizing the average separation between memories, KHMs empirically achieve lower retrieval errors [Wu et al., 2024a, Section 4 ]. 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 a d-dimensional hyper-sphere [Delsarte et al., 1991] . The main problem around spherical codes is to arrange points in a 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 of 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 errors in data transmission and storage.We review the modern Hopfield capacity lower bound in [Ramsauer et al., 2020] .. Let 1 -p be the probability of successfully storing and retrieving a pattern. Assuming patterns are normalized, the amount of patterns randomly sampled from a d-dimensional unit-sphere that the MHM with update rule in (1.2), can store and retrieve is lower-bounded byM ≥ √ pC (d-1)/4 ,where C is the solution to C = b /W0(exp{a+ln b}), with W 0 (•) being the principal branch of Lambert W function, a := ( 4 /d-1) (ln 2 √ p-2 /R + 1) and b := 4β /5(d-1).Observe W 0 is an increasing function in exp{a + ln b}, indicating that C is increasing in R ( C is increasing in a; a is decreasing with fixed R). Finally, we observe that under Assumption 1, we have R = 1 2 √ 2∆ min , implying that the memory capacity of MHM is constrained by large ∆ min .We review ways to do optimization on the surface of an unit-hypersphere (Stiefel manifold).Projected Gradient Descent. Given any loss function L(•), an input matrix X, and learning rate γ, a single gradient descent step at t-th time step is:W t+ 1 /2 = W t -γ t ∇ X L(X). (B.1)Projected gradient descent [Raman and Yang, 2019] then projects W t+ 1 2 onto the feasible set, in this case, the surface of a unit hypersphereW t+1 = W t+ 1 /2 W t+ 1 /2 . (B.2)Combining (B.1) and (B.2), we obtain the projected gradient descent step asW t+1 = PGD(W t , γ, X).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 to the Riemannian setting. In general, with carefully selected step-size, their method achieves O( 1 /N) convergence rate which is the same in the euclidean setting. Overall, there are various of methods for optimization on 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 to satisfy the norm constraint is through L2 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 et al., 2021] . Further, from the analysis on unconstrainted feature models [Zhu et al., 2021] , we can see that with carefully chosen coefficient on the regularization term on W , the optimal solution of (3.2) or cross-entropy loss ended up outputting normalized features.Based on the previous research, we are able to see that the constraint in Definition 2.6 is not difficult to satisfy.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 as 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 we try to optimize the usage of external neurons for memory storage by increasing the separation between memories in such external space (Φ-space).We show that to prevent memory confusion, minimizing separation loss is an effective way to utilize the external space efficiently. The closest work we can find is [Morrison et al., 2017] and [Kozachkov et 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 a transformer. In this context, our work provide an improved connection between brain and transformer models, offering a more learnable and powerful approach to brain-machine interfaces (BMI).We observe that cos(θ min ) connects to the maximal separation loss viacos(θ min ) = L Φ (Ξ) + 2t 2t .Following the proof of [Hu et al., 2023, Lemma 3.1] and by Lemma C.1, it holdsM = √ pC d-1 /4 ,with some real value C ∈ R. Here C is solution to the upper branch of the Lambert W function deduced from (C.2),C = b W 0 (exp{a + ln b}) , (C.3)wherea := 4 d -1 ln 2( √ p -1) R Φ + 1 , and b := 4β 5(d -1) . (C.4)Then, we arrive a lower bound on the exponential storage capacity M:M ≥ √ pC d-1 4 . (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.a := 4 d -1 ln 2( √ p -1) R + 1 , and b = b.And we also have θ min := Min 1≤µ≤ν≤M (1 -cos(θ µν )) ∈ [0, π] be the angle between two raw memory patterns ξ ν , ξ µ .We denote the optimal separation loss be L ⋆ (Ξ), and the loss value at t-th step be L t (Ξ).We denote R ⋆ Φ be the corresponding R Φ when L Φ (Ξ) is at its global minimum. By (3.2), the convexity of L Φ , the optimality of L Φ givesR ⋆ Φ = 1 2 L ⋆ Φ (Ξ) -t ≥ R Φ .Next, we prove that to achieveR Φ ≥ R, we need O 1 -4tR 2 -L ⋆ Φ (Ξ) sub linear time (iterations.). Recall that R := 1 2 Min ν,ν̸ =µ ∥ξ ν -ξ µ ∥. By R Φ = LΦ(Ξ) /-t/2, for R Φ ≥ R, we need 1 2 L Φ (Ξ) -t ≥ 1 2 Min ν,ν̸ =µ ∥ξ ν -ξ µ ∥,which implies, by t > 0,L Φ (Ξ) ≤ -t • (2R) 2 . (C.6)Subtracting -L ⋆ Φ (Ξ) on both sides, we getL Φ (Ξ) -L ⋆ Φ (Ξ) ≤ -t • (2R) 2 -L ⋆ Φ (Ξ) := ϵWhich implies the iteration number needed to achieve improved memory capacity bound is:N = O 1 -4tR 2 -L ⋆ Φ (Ξ), which gives us a sub-linear time complexity.Let  and b :=  4β  5(d -1) .a := 4 d -1 ln 2( √ p -1) R Φ + 1 ,As long as Algorithm 1 runs forO ( 1 /-4tR 2 -L ⋆ Φ (Ξ)) iterations, its output Φ satisfies a ≤ a, (C.7)andC = W 0 exp a + ln b ≤ W 0 (exp{a + ln b}) = C. (C.8)Thus, we have the memory capacity comparison asM = √ pC d-1 4 ≥ √ p C d-1 4 = M .Since the upper branch of Lambert W function is monotonically increasing on its domain, R Φ > R impliesM = √ pC d-1 4 ≥ √ p C d-1 4 = M .Hence we finish the proof.C.2 Proofs of Lemma 2.2 and Proposition 2.1Lemma C.3 (Capacity of Optimal Spherical Code, Lemma 2.2 Restated). Given a fixed D Φ > 1, and its corresponding M ⋆ , if an optimal code C opt is in S DΦ-1 and has size M ⋆ , then C opt ∈ Λ DΦ .Proposition C.1 (Optimal Memory Capacity, Proposition 2.1 Restated). Following Lemma 2.2, we haveM ⋆ ≍ c DΦ ,for some c > 1. Here ≍ indicates matching upper and lower bounds up to constant factors.Proof. By Assumption 1, all memories are normalized. Thus, we haveR Φ = 1 2 2 -2 max µ,ν∈[M ] µ̸ =ν ⟨Φ(ξ µ ), Φ(ξ ν )⟩ By (2.1) = 1 2 ∆ Φ min . (C.9)Recall the storage condition∆ Φ µ ≥ 1 β ln 2(M -1) R Φ .Here we consider the minimal ∆ Φ µ among all possible µ ∈ [M ]. We plug (C.9) into the well-separation condition and change ∆ Φ µ to ∆ Φ min . We arrive∆ Φ min ≥ 1 β ln 2(M -1) ∆ Φ min /2.By rearranging terms, we get∆ Φ min + 1 2β ln 1 2 ∆ Φ min ≥ 1 β ln (2(M -1)) .The derivative w.r.t. ∆ Φ min on the LHS is1 + 1 2β∆ Φ min , indicating that LHS is increasing in ∆ Φmin for all ∆ Φ min > 0. The derivative w.r.t. M on the RHS is1 β(M -1) ,indicating that the RHS is increasing in M for all M > 1. Since we are handling ∆ Φ min , this property holds for all ∆ Φ µ . Let δ be the minimum value for ∆ Φ min that satisfies the storage condition such thatδ + 1 2β ln 1 2 δ ≥ 1 β ln (2(M -1)) .With the definition of optimal spherical code, we have δ ≤ 1 -ρ ⋆ . Thus an optimal spherical code must satisfy this inequality. Now we further analyze the quantity M ⋆ . Let θ = arccos (ρ(C opt )), with θ ∈ (0, π /2), we apply the upper bound in [Kabatiansky and Levenshtein, 1978] , we get e φ(θ)DΦ(1+o( 1)) ≥ M ⋆ .where Φ ∈ H. With the above result, we get M ⋆ = o(c DΦ ) for some c > 1.For the lower bound of M ⋆ , we use the classic sphere code bound in [Chabauty, 1953 , Shannon, 1959 , Wyner, 1965] , and getM ⋆ ≥ 1 √ π Γ( DΦ /2) Γ( DΦ-1 /2) θ 0 sin DΦ-2 (x)dx -1 = (1 + o(1)) 2πD Φ • cos(θ) sin DΦ-1 (θ),where x ∈ S DΦ-1 .Therefore, we havee φ(θ)DΦ(1+o(1)) ≥ M ⋆ ≥ (1 + o(1)) 2πD Φ • cos(θ) sin DΦ-1 (θ),where φ(θ) > -log sin(θ), and o(•) is " strictly slower than" notation as D Φ → ∞.This completes the proof. Tighter bounds can be found in [Jenssen et al., 2018 , Fernández et al., 2021] .We selected bounds that most clearly show the exponential scaling behavior for better intuition.We first restate Theorem 3.1:Theorem C.1 (Theorem 3.1 Restated). For any possible integer M , we havelim sup τ →0 argmin Φ∈H 1 M M µ=1 L Φ (ξ µ , τ ) ⊆ argmin Φ∈H L HardMax (Φ),where all H is the hypothesis space of Φ.Then we introduce a helper lemma.Lemma C.4. Let L 0 (Φ, τ ) beL 0 (Φ, τ ) := τ • log M µ=1 L Φ (ξ µ , τ ).L 0 (Φ, τ ) converges uniformly to L HardMax (Φ) as τ → 0.Proof of Theorem 3.1. We first organize terms in (3.2). We obtain:L Φ (ξ µ , τ ) = -log exp ⟨Φ(ξ µ ), Φ(ξ µ )⟩ τ -log M ν=1 exp ⟨Φ(ξ µ ), Φ(ξ ν )⟩ τ = - 1 τ -log M ν=1 exp ⟨ξ µ , ξ ν ⟩ τ .We define a helper function L 0 , denoted asL 0 (Φ, τ ) := τ • log M µ=1 ℓ µ (Ξ, Φ, τ ). (C.10)We haveL 0 (Φ, τ ) := τ • log M µ=1 L Φ (ξ µ , τ ) = τ log M µ=1 log   1 + M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ   .Due to the fact that x /(1+x) ≤ log(1 + x) ≤ x for all x > -1, we have:M ν∈[M ]\µ exp ⟨Φ(ξν ),Φ(ξµ)⟩-1 τ 1 + M ν ′ ∈[M ]\µ exp ⟨Φ(ξν ),Φ(ξµ)⟩-1 τ ≤ log   1 + M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ   ≤ M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ . (C.11)Given the fact that ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 ≤ 0 for all possible ν, µ. With the monotonicity of the exponential function, we obtain:M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ ≤ M -1.Combining this with LHS of (C.11), we haveM ν∈[M ]\µ exp ⟨Φ(ξν ),Φ(ξµ)⟩-1 τ M ≤ log   1 + M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ   ≤ M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ .Summing over all possible µ ∈ [M ] we haveM µ=1 M ν∈[M ]\µ exp ⟨Φ(ξν ),Φ(ξµ)⟩-1 τ M ≤ M µ=1 log   1 + M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ   ≤ M µ=1 M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ .Using the property of max function, we further getmax µ,ν∈[M ],µ̸ =ν exp ⟨Φ(ξν ),Φ(ξµ)⟩-1 τ M ≤ M µ=1 M ν∈[M ]\µ exp ⟨Φ(ξν ),Φ(ξµ)⟩-1 τ M , ≤ M µ=1 log   1 + M ν∈[M ]\µ exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ   ≤ M • (M -1) • max µ,ν∈[M ],µ̸ =ν exp ⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1 τ .Now by taking logarithmic on both sides and multiplying all three terms by τ we getmax µ,ν∈[M ],µ̸ =ν (⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1) -τ log M ≤ L 0 (Φ, τ ) ≤ τ log (M • (M -1)) + max µ,ν∈[M ],µ̸ =ν (⟨Φ(ξ ν ), Φ(ξ µ )⟩ -1) . By max µ,ν∈[M ],µ̸ =ν (α µ,ν ) = L HardMax (Φ) -1, we have L HardMax (Φ) -τ log M -1 ≤ L 0 (Φ, τ ) ≤ τ log M • (M -1) + L HardMax (Φ) -1.Therefore, for any ϵ > 0, by taking τ 0 = ϵ max (log M,log(M •(M -1))) , we have|L 0 (Φ, τ ) -L HardMax (Φ)| ≤ τ max{log M, log(M • (M -1))} ≤ ϵ,for any τ < τ 0 . That is, L 0 (Φ, τ ) converges uniformly to L HardMax (Φ), leading to Lemma C.4. Now we know L 0 (Φ, τ ) converges uniformly to L HardMax (Φ) as ϵ → 0, by [Rockafellar and Wets, 2009, Proposition 7 .15], we have L 0 (Φ, τ ) Γ-converges to L HardMax (Φ) as well. By [Braides, 2006, Theorem 2 .10], we havelim inf τ →0 argmin Φ∈H L 0 (Φ, τ ) ⊆ argmin Φ∈H L HardMax (Φ).This completes the proof8 .C.4 Proof of Proposition 3.1 Proof. We first define the one-vs-one distance.Definition C.1 (one-vs-one distance). We define the one-vs-one distance of a set of pointsV = {v µ } M µ=1 ⊆ S d-1 , with |V| = M , as ρ one-vs-one (V) := min µ∈[M ] min ν̸ =µ ∥v ν -v µ ∥.The one-vs-one distance is lower bounded as following Lemma C.5. [Jiang et al., 2023, Lemma C.13 ]√ π M Γ d+1 2 Γ d 2 + 1 1 d-1 ≤ max V⊆S d-1ρ one-vs-one (V) .(C.12)Note that by the definition of the one-vs-one distance, we have the equivalent expression such thatρ 2 one-vs-one (V) 2 ≡ min ν,µ∈[M ] ⟨v µ , v µ ⟩ -⟨v µ , v ν ⟩ .Combining the above property, Lemma C.5 and a known upper bound in [Moore, 1974, Theorem 1], we obtain:1 2 √ π M Γ DΦ+1 2 Γ DΦ 2 + 1 2 D Φ -1 ≤ ∆ Φ min ≤ 2 2 √ π M Γ DΦ+1 2 Γ DΦ 2 1 D Φ -1 .The upper bound in [Moore, 1974] is derived by the normalized surface area of a spherical cap of angular radius θ.Computational Environments. All experiments are conducted on the platform with NVIDIA GEFORCE RTX 2080 Ti 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.Hyperparameters. The hyperparameters we used for the metastable state experiment is listed in Table 3 . 3 denotes the batch size we use to train the feature map Φ. 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] .Hyperparameters. The hyperparameters we used for the basins of attraction experiment is listed in Table 5 . 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 we train Φ 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] .Hyperparameters. The hyperparameters we used for the basins of attraction experiment is listed in Table 5 . Implementation Details. We specifically set the update rule iteration to 5 as we see the sharp energy gradient in Figure 1 . Demonstrating that the standard MHM and its variants are not able to converge to fixed points fast.We provide a numerical simulation of our bound with D Φ = 3. We take the known solution of minimal separation published in http://neilsloane.com/packings/ a ground truth. 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 Φ under U-Hop+ with 6 different images sampled from CIFAR10 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 our learned feature map consistently puts similar pairs closer to each other in 7 out of 10 trials. This 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 to each instance. A similar analysis can be found in [Dirksen et al., 2022 , Ghosal et al., 2022] , where they found out that if data has subtle clustered structure, a random neural network is able to make it linearly separable with high probability.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.Here we observe the loss curve of L w.r.t. different memory set size. We aim to verify whether L is able to converge well through proposed algorithm. 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 a new framework to describe the optimal memory capacity of kernelized Hopfield models (KHMs) and modern Hopfield models. We consdier stored memory sets as a special type of spherical code that all points in the set satisfies the well-separation condition. Next, we show there is a sublinear time algorithm to find an 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 contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.x ⋆ corresponds either to one of the memories or to a fuzzy 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 et al., 2024b, Hu et al., 2023].It is a common assumption adopted in[Santos et al., 2024, Wu et al., 2024a]. A justification is the connection to transformer-attention. The modern Hopfield update rule (a.k.a. retrieval dynamics) is constantly compared toNote that, Definition 2.6 is sufficient but not necessary. It is possible to find a different H ′ such that KHMs with Φ ∈ H ′ achieves desiring characteristics as[Wu et al., 2024a, Lemma 2.1] and[Wu et al., 2024a, Thm 2.1].After completion of this work, the authors attended ICML 2024 and learned of an upper bound result reported by[Santos et al., 2024], which also utilizes techniques from spherical codes. The authors regret missing the dinner withSantos 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 low-temperature region (Proposition 2.1).This is different from[Iatropoulos et al., 2022] while they share similar names.In general, L0 converges uniformly to Lhardmax as τ goes to 0 with an error rate of |L0 -Lhardmax| ≤ 2τ log(M ). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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?
2. Definition 2.7 assumes that the patterns are normalized. This assumption is not explicitly stated elsewhere and are not well-justified.
3. 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"? 
4. Is the convergence in Theorem 2.2 pointwise convergence or uniform convergence? For a given $\tau>0,$ what's the error rate?
5. The proposed algorithm learns a linear map, what about non-linear maps?
6. 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.

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
limitations: limitations: The paper is of theoretical nature. A paragraph on limitation is given in the main content.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
While 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]
should have been conducted on these tasks.
questions: 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: limitations: Yes.
paper_summary: paper_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: 
1. How does memory capacity affect the gap between memories?
2. Given a fixed feature dimensionality, how to select an optimal separation function? 
3. Is there a simpler and more efficient algorithm which optimize the kernel?
4. How to connect the gap between memories and the optimal capacity of KHNs theoretically? 

Through 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.
strength_weakness: strength_weakness: 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).
questions: 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?

For 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}$?

Is 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: *	Quality: 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).
*	Quality: 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]. 
*	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.
questions: questions: 1.	How 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.
2.	What is Lambda in Definition 2.8, Theorem 2.1?
3.	Is the lower bound from definition 2.7 tight? Can you establish it is not vacuous?
limitations: 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.

Comments: title: A Gentle Reminder
Response to rebuttal
comment: Thank you for your clarifications. It appears to me that the datasets you have selected for evaluations are those with high sparsity, which makes the two curves overlap. I'm not sure such comparisons are fair. However, I think the current work makes some solid theoretical contributions. Thus, I will keep my score.
Dear Reviewer,

As the discussion period coming to its end, we want to check if our latest response has addressed your concerns.

We have responded to the reviewer’s followup questions and concerns. If resolved, we respectfully ask that you consider increasing your score to reflect your satisfaction.

Please let us know if you have any further questions or need clarification. Thank you!

Best regards,

Authors
Glady!

 > **Q1:** Could you provide any intuition on why the Sparse Hopfield + U-hop+ line is almost overlapped with the Generalized Sparse Hopfield + U-hop+ line?

**Response:** Sparse Hopfield is a special case of Generalized Sparse Hopfield (GSH) with the sparsity parameter $\alpha=2$. Notably, $\alpha=2$ represents the most sparse GSH. Therefore, for datasets with high sparsity, the two may overlap.

 >   **Q2:** In my previous question, I was wondering why Definition/Lemma 2.8 leads to the conclusion that "there is a feature map such that is a memory code". It seems to me that there are some important premises for Memory Code (Definition 2.7). One is the assumption that the patterns are normalized. Another is that the feature map is linear.

**Response:** Thanks for pointing this out. We notice our expression causes confusion. We have changed the paragraph into the following:

"From this definition, with a fixed $D_\Phi$, for some set of patterns $\mathcal{V}$ that has size $M^*$, there might exist a function $\tilde{\Phi} : \mathbb{R}^d \rightarrow \mathbb{R}^{D_\Phi}$, such that it pushes memories further from each other to the level where $\tilde{\Phi} ( \mathcal{V} )$ is a memory code.
In other words, if one hopes to store all points in $\mathcal{V}$ with KHNs, the objective is to find an appropriate $\tilde{\Phi}$."

**This paragraph is meant to be an intuitive explanation rather than a theoretical result. Thank you again for pointing this out, we have revised our manuscript accordingly.**
Thank you for the response. However, I think there are still some misunderstandings.

Q1: Could you provide any intuition on why the Sparse Hopfield + U-hop+ line is almost overlapped with the Generalized Sparse Hopfield + U-hop+ line?

Q2: In my previous question, I was wondering why Definition/Lemma 2.8 leads to the conclusion that "there is a feature map such that is a memory code". It seems to me that there are some important premises for Memory Code (Definition 2.7). One is the assumption that the patterns are normalized. Another is that the feature map $\Phi\in \mathcal{H}$ is linear.
Thank you!
Thank you very much for the response.

> **Q1:** In Fig. 3 of the attached...

**Response:** It is almost overlapped with the Generalized Sparse Hopfield + U-hop+ line.

> **Q2:** Could you elaborate on how it is derived from Definitions 2.2 and 2.7?

**Response:** We apologize for the confusion. The logic behind this is that Def 2.2 leads to Def 2.7, and then Def 2.7 leads to the maximal capacity as we refer to the solution of the $\max_{ \Phi(V) } | \Phi(V) |$, and $\tilde{\Phi}$ is the solution of $\argmax_{ \Phi } \max_{ \Phi(V) } | \Phi(V) |$.

> **Q3:** I don't think my question Q4 is addressed.

**Response:** With the same $\Xi$ and $\Phi$, $\mathcal{L}_0$ converges uniformly to the HardMax loss with same error rate of $\epsilon = O(\tau \log M)$. However, since Thm 2.2 considers two optimization problems, it is indeed $\Gamma$-convergence between these two minimization problems (convergence for functionals). With the property of $\Gamma$-convergence, the minimizers of one minimization problem will also converges to another. We will address that in the proof of our manuscript.

____
Thanks again for the response and your insightful review, we hope our responses address your concerns.
Thanks to the authors for the clarifications. Thus, I will keep my score.
Thank you for the detailed rebuttal.

- In Fig. 3 of the attached pdf. It seems the results for "Sparse Hopfield + U-hop+" is missing.

- 
> "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."

Could you elaborate on how it is derived from Definitions 2.2 and 2.7?

- I don't think my question Q4 is addressed.
Thank you again for your constructive comments. We truly appreciate your thorough review!

We will take the aesthetic suggestion into consideration. Thank you!
Thank you to the authors for their detailed response and hard work. Based on the provided the results, I am happy enough to raise my score to 7. 

Side comments: 
Yes, indeed the slight in error in RHS of the bound does not change the main statement. 

The error bars of each line in the plots provided in the response are based on standard error? If not, see if plotting the error bars as standard error could help aesthetically. 

Cheers.
Dear Reviewer vthX,

We are happy to hear that our revisions have addressed your concerns.

Thank you again for your constructive comments, which are pivotal in improving our draft and presenting a clearer view of this work We truly appreciate your thorough review.

Best,

Authors
I appreciate the author's improvements in the manuscript and believe my main concerns have been addressed. I'm especially impressed by the added experiments, which, to me, provide important empirical support to the mathematical justification. I will raise my score accordingly.