A New Type of Associative Memory Network with Exponential Storage Capacity

1. The critical contribution of Bovier (1999) is the proof of an upper bound on the capacity, showing that the lower bound cited by the authors (which appears in earlier work, for instance Petritis (1996) "Thermodynamic Formalism of Neural Computing") is in fact sharp. The authors prove only lower bounds, which follow from a relatively straightforward Chernoff bound (as in Bovier or in Demircigil's study of polynomial networks). The proof of the upper bound is considerably more technically challenging, requiring a somewhat clever conditional negative dependence argument, and to my knowledge has not been extended beyond the standard Hopfield model. The authors should make this clear when they reference Bovier, and also cite the earlier work of Petritis. It would also be useful to offer some speculation regarding the possibility of proving an upper bound.

2. The empirical test of the predicted capacity in Figure 1 is uncompelling, as the authors test only a single network size. They should probe multiple network sizes, and also provide evidence for the claimed exponential scaling.

3. A key claim of this work is that the proposed model simultaneously enjoys superior biological plausibility compared to previously-proposed associative memory models and has a huge storage capacity. However, I have some concerns regarding their claims. First, they decompose the required $k$-fold multiplication into a sequence of $k$ pairwise multiplications, each of which is claimed to be realized by a neuron. Is their evidence for the existence of this highly structured motif in neural connectivity data? Second, to support the claim that a single neuron can compute a pairwise product, they cite work by Groschner et al. on the fly visual motion detection circuit. Despite the title, what Groschner et al. show is more precisely a form of amplification by disinhibition, which in certain limits closely approximates multiplication (this idea goes back at least to work by Torre and Poggio in 1978, which is the basis for this family of biophysically-inspired motion detection models). How sensitive is their model to departures from perfect multiplication? I can only imagine that the errors would compound over the $k$ approximate multiplications required. This is potentially a severe limitation, as the authors require $k$ to grow with $N$ in order to achieve the promised quasi-exponential capacity.

4. The authors should remind the reader of their notational conventions in Appendix B, particularly the use of set-indexed variables to represent products. In this vein, why do they switch from using $\sigma$ as the index to using $s$?

5. To guide the reader, it would be useful to explicitly compare the argument used here to bound the capacity for polynomial networks to the proof by Demircigil et al. Having a concrete example would in particular make it easier to check each step of the proof quickly.

6. A point of curiosity: Can this framework be easily extended to the hetero-associative memory setting? Several recent works have considered extending Dense Associative Memories to the sequence storage settings, including https://arxiv.org/abs/2306.04532 and https://arxiv.org/abs/2212.05563.

7. It would be useful to mention at least briefly the framework of Millidge et al. (2022), "Universal Hopfield Networks: A General Framework for Single-Shot Associative Memory Models," and contrast it with the framework proposed in the present work.

• Can you demonstrate in simulations the similarities and differences between your model and previous ones with respect to "robust storage capacity"?
• Can you show in a table or in a figure the number of interactions between neurons as a function of k for the new model vs polynomial one vs Simplical one? For example, in the conditions used in simulations.
• For the biological plausibility part, can you explicitly write what would be the computations of the k neurons? What would be the connectivity between the N neurons and the k neurons? Would you have recurrent connections among the k neurons? Why did you call it O(k) neurons? Those are not at all clear from equation (8)!
• Figure 2 legend have 10 data items, but only ~5 of them are visible in each panel. Can you use dashed lines or add an indicative data arrow to make it easier to follow?

1. Could the authors please write down explicitly the energy function and update rule for this model with 5+4 neuron model that they discuss in Appendix A3?

2. It seems that the conclusion from Fig 2 is that the behavior of PSHN and Poly HN are roughly similar when deg=k. Is this accurate? If so, might be worth emphasizing this in the text. Also, although it is possible to parse the legend as is, it would be easier for the reader if the items in the legend were grouped in the order they appear in the plot (left to right), e.g. Classical, PSHN=7, PolyHN=7, PSHN=16, etc.

1. $x_\sigma$ is not defined before Eq (1)?
2. Can you please explain how the AHN explained in this paper can be written in the language of the "separation function" described in Millidge et al.'s "Universal Hopfield Networks"?
3. Why are continuous states not studied in this writeup?

Several blatant typos exist in this writeup.:

1. Intro first paragraph: "...attractive to biologist..."
2. pg 1 last paragraph: "...of of subsets..."
3. pg 1 last paragraph: "...correspond specific choices..."

Many more exist, but I stopped recording at this point.