Long Sequence Hopfield Memory
Authors: Hamza Tahir Chaudhry
Jacob A Zavatone-Veth
Dmitry Krotov
Cengiz Pehlevan
Venue: NeurIPS 2023 poster (2023)
Keywords: Sequence Recall
Dense Associative Memory
Memory Capacity
Hopfield Networks
Biological Motor Control
TL;DR: Hopfield Networks are extended to store sequences of memories that are polynomially or even exponentially long relative to network size.

Abstract: Sequence memory is an essential attribute of natural and artificial intelligence that enables agents to encode, store, and retrieve complex sequences of stimuli and actions. Computational models of sequence memory have been proposed where recurrent Hopfield-like neural networks are trained with temporally asymmetric Hebbian rules. However, these networks suffer from limited sequence capacity (maximal length of the stored sequence) due to interference between the memories. Inspired by recent work on Dense Associative Memories, we expand the sequence capacity of these models by introducing a nonlinear interaction term, enhancing separation between the patterns. We derive novel scaling laws for sequence capacity with respect to network size, significantly outperforming existing scaling laws for models based on traditional Hopfield networks, and verify these theoretical results with numerical simulation. Moreover, we introduce a generalized pseudoinverse rule to recall sequences of highly correlated patterns. Finally, we extend this model to store sequences with variable timing between states' transitions and describe a biologically-plausible implementation, with connections to motor neuroscience.

Long Sequence Hopfield Memory
Hamza Tahir Chaudhry!? 12,
Jacob A. Zavatone-Vetts
Dmitry Krotov Cengiz Pehlevan 12,4
'John A. Paulson School of Engineering and Applied Sciences,
CCnter for Brain Science, DDpaarmentt of Physics,
Kempper Institute for the Study of Natural and Artificial Intelligence, Harvard University
Cambridge. MA 02138
MIT-IBM Watson Al Lab, IBM Research,
Cambridge, MA 02142
hchaudhry@g harvard edu, jwwvattneeeeeehggg....oo. hwwpeeetthhhhh.arrdaaaaaaa harvard edu,
krotoveibm. com, epehlevan@seas www.arr. edu
Abstract
Sequence memory an essential attribute of natural and artificial intelligence that enables agents encode, store, and retrieve complex sequences of stimuli and actions. Computational models of sequence memory have been proposed where recurrent Hopfield-like neural networks are trained with temporally asymmetric Hebbian rules. However, these networks suffer from limited sequence capacity (maximal length of the stored sequence) due interference between the memories. Inspired by recent work on Dense Associative Memories, we expand the sequence capacity of these models by introducing a nonlinear interaction term, enhancing separation between the patterns. We derive novel scaling laws for sequence capacity with respect network size, significantly outperforming existing scaling laws for models based on traditional Hopfield networks, and verify these theoretical results with numerical simulation. Moreover, we introduce a generalized pseudoinverse rule to recall sequences of highly correlated patterns. Finally, we extend this model to store sequences with variable timing between states' transitions and describe a iatogicclll-plaussbbe implementation, with connections to motor neuroscience.
1 Introduction
Memory an essential ability of intelligent agents that allows them to encode, store, and retrieve information and behaviors they have learned throughout their lives. In particular, the ability to recall sequences of memories is necessary for a large number of cognitive tasks with temporal or causal structure, including navigation, reasoning, and motor control [1-9].
Computational models with varying degrees of biological plausibility have been proposed for how neural networks can encode sequence memory [1-3, 10-22]. Many of these are based on the concept of associative memory, also known as aontent-addressablee memory, which refers the ability of system to recall a set of objects or ideas when prompted by distortion or subset of them. Modeling associative memory has been an extremely active area of research computational neuroscience and deep learning for many years, with the Hopfield network becoming the canonical model [23-25].
Unfortunately, major limitation of the traditional Hopfield Network and related associative memory models is its capacity: the number of memories it can store and reliably retrieve scales linearly with the number of neurons in the network. This limitation is due interference between different memories during recall, also known as crosstalk, which decreases the signal-to-noie ratio. Large amounts of crosstalk results in the recall of undesired attractor states of the network [26-29].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

SeqNet
Polynomial DenseNet
-0
0.0
0.8
-00
Overlap (m
0.8
0.6
-60
Overlap
40
0.2
02
-00
-0
-02
10
30
40
50
60
70
83
90
100
10 20
30
40
50
60
70
90
80
100
Time Step
Time Step
Figure 1: SeqNet and Polynomial DenseNet (d = 2) are simulated with N = 300 neurons and P = 100 patterns. One hundred curves plotted as function of time, each representing the overlap of the network state at time with one of the patterss, m (1/N) Σ S,. The curves are ordered using the color code described on the right (patterns in the beginning and end of the sequence are shaded in yellow and red respectively). A. SeqNet quickly loses the correct sequence, indicated by the lack of alignment of the network state with the correct pattern in the sequence (m/ < 1). B. The Polynomial DenseNet faithfully recalls the entire sequence and maintains alignment with one of the patterns at any moment in time, m 82 1.
Recent modifications of the Hopfield Network, known Dense Associative Memories or Modern Hopfield Networks (MHNs), overcome this limitation by introducing a strong nonlinearity when computing the overlap between the state of the network and memory patterns stored in the network [30, 31]. This leads to greater separation between partially overlapping memories, thereby reducing crosstalk, increasing the signal-to-noies ratio, and increasing the probability of successful recall [32].
Most models based on the Hopfield Network are autoassocative, meaning they are designed for the robust storage and recall of individual memories. Thus, they are incapable of storing sequences of memories. In order to adapt these models to store sequences, one must utilize asymmetric weights in order to drive the network from one activity pattern to the next. Many such models use temporally asymmetric Hebbian learning rules to strengthen synaptic connections between neural activity at one time state and the next time state, thereby learning temporal association between patterns in sequence [1, 3, 10, 11, 16, 17, 22].
In this paper, we extend Dense Associative Memories to the setting of asymmetric weights in order store and recall long sequences of memories. We work directly with the update rule for the state of the network, allowing us to provide an analytical derivation for the sequence capacity of our proposed network. We find close match between theoretical calculation and numerical simulation, and further establish the ability of this model to store and recall sequences of correlated patterns. Additionally, we examine the dynamics of model containing both symmetric and asymmetric terms. Finally, we describe applications of our network model of biological motor control.
2 DenseNets for Sequence Storage
Traditional Hopfield Networks and MHNs, as described in Appendix B, are capable of storing individual memories. What about storing sequences? Assume that want store sequence of P patterns, 5 + -2 - ..... + EP, where g/t E {+1} is the jth neuron of the f pattern and the network will transition from pattern & to gu+1, Let N be the number of neurons in the network and S(I) E (-1, +1, be the state the network at time I. We want to design network with dynamics such that when the network is initialized in pattern g² it will traverse the entire sequence." ! We define a network, SeqNet, which follows a discrete-ting time synchronous update rule?:
P Σ 1==1
TSN (S); = sgn
Σ J jzt
sgn
+
m
m
Σ SS it
(I)
(N
'We impose periodic boundary conditions and define g++ e Boundary terms a sub-leading contribution the crosstalk, so a model with open boundary conditions will have the same scaling of capacity. "One can also consider asynchronous update rule in which neuron is updated time [23, 26].

---

is an asymmetric matrix connecting pattern <" gu+1, Note that are excluding self-interaction terms = j. We also rewrote the dynamics in terms of in the overlap of the network state S with pattern 5 When the network is aligned most closely with pattern ç the overlap my the largest contribution in the sum and pushes the network to pattern gu+z When multiple patterns have similar overlaps, meaning they are correlated, then there will be low sigmal-to-me -ooiise ratio. This correlation between patterns limits the capacity of the network, limiting the SeqNet's 's capacity to scale linearly relative to network size.
where S(t 1) TeN(() and J, - E
To overcome the capacity limitations of the SeqNet, Memories [30] to define the Denselet update rule:
inspiration from Dense Associative
TDN (S); sgm
Σ sttt f (mn)))
(2)
where f is nonlinear monotonically increasing interaction function. Similar to MHNs, reduces the crosstalk between patterns and, as we will analyze in detail, leads to improved capacity. Figure demonstrates this improvement for f(x) = x²
2.1 Sequence capacity
To derive analytical results for the capacity, we must choose a distribution to generate the patterns. As is standard in studies of the classic HN and MHNS [26-31, 33-36], we choose this to be the Rademacher distribution, where 5 E [-1,+1] with equal probability for all neurons j in all patterns 2. and calculate the capacity for different update rules. If one is allowed specially engineer the patterns, even the SeqNetcan store sequence of length 2 [37]. but this construction is not relevant to associative recall of realistic sequences. Rademacher patterns are a more appropriate model for generic patterns while remaining theoretically tractable.
We consider both the robustness of single transition, and the robustness of propagation through the full sequence. For a fixed network size N E {2, .,... and an error tolerance c E [0, 1), we define the single-transition and sequence capacities by
Pr(N.c) = max ( (PE (2.... .2.....21.1 P (TTN(())) = =E"] 2 1 cc
(3)
and
Ps(N,c) max (PE 2.......,,, (DN]))) = 21-c],
(4)
respectively, where the probability is taken over the random patterns. Note that for the single- transition capacity we could focus on any pair of subsequent patterns due to translation invariance arising from periodic boundary conditions. Also note that the full sequence capacity is defined by demanding that all transitions are correct. For perfect recall, we want to take the threshold e 4 Ó. In the thermodynamic limit in which N, P - 0o, expect for there to exist sharp transition in the recall probabilitics as a function of P, with almost-surely perfect recall below the threshold value and vanishing probability of recall above [26-29, 31, 33-36]. Thus, expect the capacity to become insensitive to the value of in the thermodynamic limit; this is known rigorously for the classic Hopfield network from the work of Bovier [34].
As we detail in Appendix C, all our theoretical results are obtained under two approximations. We will validate the accuracy of the resulting capacity predictions through comparison with numerical experiments. First, following Petritis [33]'s analysis of the classic Hopfield network, we use union bounds to control the single-transitic
and full-sequence capacities in terms of the single-bitflin error probability ([T ) & E. Using the fact that the patterns are i.. this gives P[T Dn (E") = (T
{"+1] > I-NPPTTD (E )1 # Edl and Pin (TDN (E+) + H > 1 - N PP[T (E + E2) respectively, resulting in the lower bounds
Pr(N,)) c) Z max {P E (2..... 2N NP (5 + s
(5)
Ps(N, c) Z max {P e (2....,,NN) .2.
NPP + c).
(6)
From studies of the classic Hopfield network, we expect for these bounds to be tight in the thermody- namic limit (NV - oo), but we will not attempt to prove that this is [33, 34]. Second, our theoretical
3

---

results are obtained under the approximation of P[THN * Ei in the regime N, > 1 by Gaussian tail probability. Concretely, we write the single- bittlip probability as
P(TDN(E + eी] = P/C < f(1]
(7)
in terms of the crosstalk
C= Gist / - 5c. 1==
(8)
1=2
which represents interference between patterns that can lead to a bitflip. Then, as the crosstalk the sum of P -1 1 i.i.d. random variables, we approximate its distribution as Gaussian. We then extract the capacity by determining how should scale with N such that the error probability tends to zero as N + 0o, corresponding to taking 4 0 with increasing N. Within the Gaussian approximation, we can also estimate the capacity at fixed e by using the asymptotics of the inverse Gaussian tail distribution function to determine how P should scale with N such that the error probability is asymptotically bounded by c as N + cc. This predicts that the effect of non-negligible c should vanish as N 00.
For P large but finite, this Gaussian approximation amounts to retaining only the leading term in the Edgeworth expansion of the tail distribution function [38-41] We will not endeavour to rigorously control the error of this approximation in the regime of interest in which N is also large. To convert our heuristic results into fully rigorous asymptotics, one would want to construct an Edgeworth-type series expansion for the tail probability P(C < - [1)] that is valid in the joint limit with rigorously- controlled asymptotic error, accounting for the fact that the crosstalk is sum of discrete random variables [38-41]. As a simple probe of Gaussianity, we will consider the excess kurtosis of the crosstalk distribution, which determines the leading correction to the Gaussian approximation in the Edgeworth expansion, and describes whether its tails are heavier or narrower than Gaussian [38-41].
2.2 Polynomial DenseNet
Consider the DenseNet with polynomial interaction function, f(x) = x4, which we will call the Polynomial DenseNet. In Appendix C. we argue that the leading asymptotics of the transition and sequence capacities for perfect recall are given by
Nd
Nd
Pr 2(2d - 1)!! log Ps 1)(2d 1)!! lo)
(9)
Note that this polynomial scaling of the single-transition capacity with network size coincides with the capacity scaling of the symmetric MHN [30]. Indeed, as we have excluded self-interaction terms in the update rule, the single- bittllp probabilities for these two models coincide exactly for unbiased Radamacher patterns (Appendix C.I). This allows us to adapt arguments from Demircigil et al. [31] to show that (9) is in fact a rigorous asymptotic lower bound on the capacity (Appendix D). We compare our results for the single- single-transition and sequence capacities to numerical simulation in Figure
2. The simulation matches theoretical prediction for large network size N. For smaller N, there finite-size effects that result in deviation from theoretical prediction. The crosstalk has non-negligible kurtosis in finite size networks which leads to deviation from the Gaussian approximation.
Furthermore, we point out that for fixed N, the network capacity does not monotonically increase in the degree d. Since the factorial function grows faster than the exponential function, every finite network of size N has a polynomial degree dmaa after which the capacity will actually decrease. This is also true for the standard MHN. We demonstrate this numerically in Figure 2B, again noting mild deviations between theory and simulation due to finite-size effects.
2.3 Exponential DenseNett
We have shown the DenseNet's capacity can scale polynomially with network size. Can it scale exponentially? Consider the DenseNet with exponential interaction function, f(x) = (N=1))==1) which we call the Exponential Denselett. This function reduces crosstalk dramatically: fm" 1 when m (S) = and is otherwise sent to zero exponentially fast. In Appendix C.2, we show that under the abovementioned approximations one has the leading asymptotics
3N-1
3N
where B exp(2) ~ 1.964...
Pr 2 2 N
and Ps 2 No
(10)
cosh(2)

---

A
7
Theay Roy (1m1)
Sim Pay 1511
6
Theoy: Foy (2n0)
Sim Paay 1512)
Theoy: Poy (2nd)
Sim Payy 15n5)
Theoyy Fo (Bn))
Sin Puy 1814
Theary Pip
Sin Pop
4
1093
2
10
30
N
B
C
20
Theory M-
10²
Ni
18
10a
Excess Kurtosis
10"
17
1P
Variance
10
10'
-15 2
-13
10
10"
-11
10 20
10"
1
10"
10"
18
10"
Figure 2: Testing the transition and sequence capacities of DenseNets with polynomial and ex- ponential nonlinearities. A. Scaling of transition capacity (logıo (Pr), left) and sequence capacity (logio(Ps) right) with network size. As network size increases, the variance of the crosstalk de- creases and the theoretical approximations become more accurate, resulting in tight match between theory (solid lines) and simulation (points with error bars). The theory curves are given by Equations 9 and 10. Error bars computed across realizations of the random patterns (see Appendix G). There is significant deviation between theory and simulation for the sequence capacity of the Exponential DenseNet. We show that this is due to finite-size effects in Section 2.3. B. Transition capacity of Polynomial DenseNets as function of degree. For any finite network size N, there is degree d that maximizes the transition capacity. The same would be true for the sequence capacity. C. Crosstalk variance (left) and excess kurtosis (right) for the Exponential DenseNet Variance proportional P and inversely proportional N, while the opposite true for excess kurtosis. See Appendix G for details of our numerical methods.
function of P and N.
In Figure 2, numerical simulations confirm this model scales significantly better than the Polynomial DenseNet and enables to store exponentially long sequences relative to network size. While the ratio between transition and sequence capacities remains bounded for the Polynomial DenseNet, where Pr/Ps- d 1, the gap for the Exponential DenseNet diverges with network size.
However, we can see in Figure 2A that the empirically measured capacity-of the Exponential Denselit deviates substantially from the predictions of our approxi- mate Gaussian theory. Due to computational constraints, our numerical simulations are limited to small network sizes (Appendix G). Computing the excess kurtosis of the crosstalk distribution with number patterns comparable the capacity predicted by the Gaussian theory reveals that, for range of system sizes we can simulate, the distribution should deviate strongly from Gaussian. In particular, take P 3N (aNN for some constant factor a, then the excess kurtosis increases with network size up to around N 56 (Appendix C.2). Increasing the size of an Exponential DenseNet therefore has competing effects: for a fixed sequence length P, increasing network size N decreases the crosstalk variance, which should reduce the bitflip probability, but also increases the excess kurtosis, which reflects a fattening the crosstalk distribution tails that should increase the bitflip probability. This is illustrated in Figure 2C.
the sequence
The competition between increasing P and N for the Exponential DenseNet is easy to understand intuitively. For fixed N, increasing P means that the crosstalk is equal in distribution to the sum of an increasingly large number of i.i.d. random variables, and thus by the central limit theorem should become increasingly Gaussian. Conversely, for fixed P, increasing N means that each of the
5

---

A
Fig Moving 200000 Image Sequence
B4
Poy: Gct Poly
Payy
Poly 6F)
3
Payy
R
0.0 0.1 0.2
0.3
0.4
0.5
0.6
0.7
0.8 0.9
24
Figure 3: A. Recall of a sequence of 200000 correlated images from the MovingMNIST dataset using DenseNets of size N = 784. We showcase 10 image subsequence. The top row depicts the true sequence, the second row depicts SeqNet's 's performance, the next rows depict the Polynomial DenseNets' performance which increases with degree d, and the final row depicts the Exponen- tial DenseNet's performance which yields perfect recall. B. Transition capacity of Polynomial DenseNets of size N 100 relative pattern bias e. Increasing monotonically decreases capacity. Networks with stronger nonlinearities maintain high capacity for large correlation strength. Imple- menting the generalized pseudoinverse rule decorrelates these patterns and maintains high sequence capacity for much larger correlation. See Appendix G for details of numerical methods.
P-1 contributions to the crosstalk is equal in distribution to the product of an increasing number of i.i.d. random variables-as as [( ( 25 = II; exp($) )-) and thus by the multiplicative central limit theorem each term should tend to lognormal distribution. In this regime, then, the crosstalk is roughly a mixture of lognormals, which is decidedly non- non-Gaussian. In contrast, for Polynomial DenseNet, memorization is easy in the limit where N tends to infinity for fixed P, as almost surely.
the crosstalk should tend almost surely to zero each term f( NN Σ5 (
2.4 Recalling Sequences of Correlated Patterns
The full-sequence capacity scaling laws for these models were derived under the assumption of ii.d Rademacher random patterns. While theoretically convenient, this is unrealistic for real-world data. We therefore test these networks in more realistic settings by storing correlated sequences of patterns, which will lead greater erosstalk in each transition and thus smaller single-transition and full-sequence capacities relative to network size [26, 36]. However, the nonlinear interaction functions should still assist in separating correlated patterns enable successful sequence recall.
For demonstration, we store a sequence 200000 highly-eorrelated images from the MoVIng dataset and attempt to recall this sequence using DenseNets with different nonlinearities [42]. The entire sequence is composed subsequence is composed of 20 images of two hand-written digits slowly moving through one another. This means there is significant correlation between patterns which will result in large amounts of crosstalk. The results of the DenseNets shown in Figure 3A, where increasing the nonlinearity of the Polynomial DenseNets slowly improves recall but not entirely, while the exponential network achieves perfect recall. The SeqNet and DenseNets, up until approximately d = 50, entirely unable to recall any part of any image, despite the DenseNets being well within the capacity limits predicted by theoretical calculations on uncorrelated patterns.
10000 unique subsequences concatenated together, where each
2.5 Generalized pseudoinverse rule
Can we overcome the DenseNet's limited ability to store correlated patterns? Drawing inspiration from the pseudoinverse learning rule introduced by Kanter and Sompolinsky [43] for the classic Hopfield network, we propose a generalized pseudoinverse (GPI) transition rule
TSP)(S); sgn Σ cu+1
Σ Cotttm
Our
1
Σ
(I)

---

where the overlap matrix Oud is positiv--smiidefnite, we can define its pseudoinverse O+ by inverting the non-zero eigenvalues. With f(x) = z. this reduces to the pseudoinverse rule of [43].
If the patterns are linearly independent, such that O is full-rank, we can see that this rule can perfectly recall the full sequence (Appendix E). This matches the classic pseudoinverse rule's ability to perfectly store any set of linearly independent patterns; this is why we choose to sum over // inside the separation function in (11). For i.i.d. Rademacher patterns, linear independence holds almost surely in the thermodynamic limit provided that P < N.
In Figure 3B, we demonstrate the effect of correlation the Polynomial DenseNet through studying the recall of biased patterns ę with P(ç""" = =1) = [1 [1 <) for e E 1). We see that the Polynomial DenseNet has better recall at all levels of bias expect there to be a maximum degree as described before. However, at large correlation values, they all have low recall, suggesting the need for alternative methods to decorrelate these patterns. This failure is easy to understand theoretically, following van Hemmen and Kühn [44]'s analysis of the classic Hopfield model: for patterns with bias e, the Polynomial DenseNet update rule expands as
degree d increases, although we still
TDN (5"); = sgn(s] [g|
+ (P-11) 1) 1) 2d+1 + ((VV)/N)
(12)
Therefore, even if N is large, for + there must be some value of P for which the constant bias overwhelms the signal. If N + do for any fixed P. then we must have P < (22++] + 1 for the signal to dominate. In Figure 3B, we show the generalized pseudoinverse update rule is more robust to large correlations than the Polynomial DenseNet. While this rule can also be applied to the Exponential DenseNet, simulations fail due to numerical instability coming from small values in the pseudoinverse.
3 MixedNets for variable timing
Thus far, we have considered sequence recall in purely asymmetric networks. These networks transition the next pattern in the sequence every timestep, preventing the network from storing sequences with longer timing between elements. In this section, we aim to construct a model where the network stays in a pattern for steps. Our starting model will be associative memory model for storing sequences known as the Temporal Association Network (TAN) [1, 10], defined as:
P
AS): = sgn
Σ
S m! + Aer mg)
m = N
Σ S j
(13)
where m represents the normalized overlap of each pattern E" with a weighted time-average of the network over the past timesteps. S,(t) Ep= w(p)S, p). The weight function, w(t), is generally taken to be low-pass convolutional filter (e.g. Heaviside step function, exponential decay).
This network combines a symmetric and asymmetric term for robust recall of multiple sequences. The symmetric term containing m (t), also referred to as "fast" synapse, stabilizes the network in pattern n for a desired amount of time. The asymmetric term containing m (t), also referred to as a "slow" synapse, drives the network transition to pattern gu+ The À parameter controls the strength of the transition signal. If À is too small, no transitions will occur since the symmetric term will overpower it. If X is too large, transitions will occur too quickly for the network to stabilize in desired pattern and the sequence will quickly destabilize.
For TAN, Sompolinsky and Kanter [10] used numerical simulations to estimate the capacity as approximately PTAN O.IN, defining capacity as the ability to recall the sequence in correct order with high overlap (meaning that a small propotion of incorrect bits are allowed in each transition). Note that this model can fail in two ways: (i) it can fail to recall the correct sequence of patterns, or (ii) it can fail to stay in each state for the desired amount of time.
To address these issues, consider the following dynamics:
TMN (S); sgn Σ fs (m+) + Net Sa (m!))
(14)
At the patterns will be deterministic with 5:¹ = +1.
7

---

A
Temporal Association Network
Polynomial MixedNet (d,=d,=2)
Polynomial MixedNet (dg=d,=10)
Overlap (m+)
1.0
40
Patter (E.)
0.5
0.0
100 Timestep (t)
200
10D Timestep
200
100 Timestep (t)
200
dg=
d =
ds=
log 10
3
2
Theory (6,- 21
Theory (6.=
Theery (dx-
Sin 10. 3)
Id,
(d, 2)
10g
2
lo
3
2
10
20
30
40
50
60
70
80 90 100
10
20
30
40
50 60
70 80
90
100
10
20
30
40
50
60
70
80 90
100
N
N
N
dg=
dg =
ds
5
10gro(Ps)
Theory (dx-1)
3
Theory (dx=
Theory (da 3j
Skn 10. 3)
1d, 3)
3
log
3
2
2
2
10
20
30
40
50
80
70
80 90 100
10
20
30
40
50
80
70
80
90
100
10
20
30
40
50
80
70
80 90 100
N
N
N
Figure 4: Capacity of the Polynomial MixedNet. A. We simulate MixedNets with N = 100, 7 5. and attempt to store P = 40 patterns. The Temporal Association Network (left), corresponding to a linear MixedNet with dg = 1 = d,.. fails to recover the sequence. Increasing the nonlinearities to ds = 2 = d (center) recovers the correct sequence order, but not the timing. Increasing the nonlinearities to dş 10 d (right) recovers the correct sequence order and timing. B. Transition capacity (Pr) of the Polynomial MixedNet as a function of network size. Each panel has a fixed symmetric nonlinearity fs(x) zd indicated by the panel's title. As network size increases, crosstalk variance decreases and theoretical approximations in Equation 3 become more accurate to tightly match the simulations. Note that as expected, the capacity scales according to the minimum of dg and d C. As in B, but for the sequence capacity 1og10 (Ps).
We call this model the MixedNet, and seek to analyze the relationship between the symmetric and asymmetric terms in driving network dynamics and their impact on sequence capacity. As before, the asymmetric term will try to push the network to the next state at every timestep, while the symmetric term tries to maintain
its current state for timesteps. We will allow different nonlinearities for Is and fA. and analyze their effect on transition and sequence capacity.
We demonstrate the effectiveness of the Polynomial MixedNet, where for simplicity we set fs(z) fx ndd in Figure 4AA. While TAN fails completely, polynomial nonlinearity of d = 2 enables recall of pattern order but the network does not stay in each pattern for r = timesteps. Further increasing the nonlinearity to d 10 recovers the desired sequence with correct order and timing.
Theoretical analysis of the capacity of the MixedNet (14) for general memory length 7 is challenging due to the extended temporal interactions. We therefore consider single-step memory (7 = 1). and show that even in this relatively tractable special case new complications arise relative to our analysis of the DenseNet. Alternatively, DenseNet. If one imagines the network learns its weights through a temporally asymmetric Hebbian rule with an extended plasticity kernel, and its state is not perfectly clamped to the desired transition, the coupling from g" to gu+1 could be corrupted by coupling go to itself [22].
can interpret the Mixedlet with 1 as imperfectly-
We first consider the setting where both interaction functions are polynomial, fs(x) = =s and fx(z) = _dd and refer to this network as the Polynomial MixedNet. This model is analyzed in detail Appendix F.1. Interestingly, this model's crosstalk variance forms a bimodal distribution, as shown in Figure F. This complicates the analysis, but once bimodality is accounted for one can approximate the capacity using a similar argument that of the DenseNet. We find that
Pr (A- 1)2 Nmiu(ds,da) 2nds.da
1)2 Ps ~ 2(min dA) + 1) 1)dds,da log N
Nmiu(ds,da)
(15)
log N
8

---

where ,do,da is a multiplicative factor defined as
(2ds - 1 (1² + 12dds - 1)!! 2X[(ds 1)ds even]
if ds < dA if ds dA if ds dA.
Ids,ds
(16)
1 12ddA-11)
In Figure 4B-C, we show that simulations match the theory curves well as N increases. We demon- strate theoretical and simulations results for the Exponential MixedNet in Appendix F.2.
Biologically-Plausbn Implementation
Since biological neural networks must store sequence memories [2, 5-8], one naturally asks if these results can be generalized to biologically-plasshnn
neural networks. A straightforward biological interpretation of the DenseNet is problematic, as a network with polynomial interaction function of degree d is equivalent to having a neural network with many-body synapses between d + 1 neurons. This can be seen by expanding the Polynomial DenseNet in terms of weight tensor of d neurons:
P
1 N
St sgn
S,, (0)........ Σ fiondd
Jejr
Σ
S/ (17)
Sii
This is biologically unrealistic as synaptic connections usually occur between two neurons [45]. In the case of the Exponential DenseNet, one can interpret its interaction function via a Taylor series expansion, implying synaptic connections between infinitely many neurons which is even more problematic. Similar difficulties arise models with sum of terms with different powers [46].
To address this issue, we again take inspiration from earlier work in MHNs. Krotov and Hop- field [47] addressed this concern for symmet- ric MHNs by reformulating the network using two-body synapses, where the network was par- titioned into a bipartite graph with visible and hidden neurons (see [48] for an extension of this idea to deeper networks). The visible neurons correspond to the neurons in our network dynam- ics, Sj. while the hidden neurons correspond to the individual memories stored within the net- work. They are connected through a weight matrix. Since we working with an asym- metric network, we modify their approach and define two sets of synaptic weights: Wj con- nects visible neuron Uj to hidden neuron hn.
ha((1) = Σ Wiee(()
,
W3 = N
cl'
Myj = 5
oftl +
sgu
Σ Manlintt
Figure 5: Biologically-plausbb implementation of DenseNet with two-body synapses.
Maj connects hidden neuron h, to visible neuron uy. This yields the same dynamics exhibited in Equation (2), absorbing the nonlinearity into the hidden neurons' dynamics.
For the DenseNet, we define the weights as Wjn- == 55 and Maj := = For the MixedNet, we redefine the weight matrix Maj E/ xex The update rules for the neurons follows:
hy((1)= = Σ
(.:0)=/[[wwnen (0)
0y(1+ + 1) = sgn Σ M1)))n(()
(18)
Note that these networks" transition and sequence capacities, Pr and Ps, now scale linearly with respect to the total number of neurons in this model, N visible neurons and P hidden neurons. However, the network capacity still scales nonlinearly with respect to the number of visible neurons.
Finally, we remark that this network is reminiscent of recent computational models for motor action selection and control via the cortico-basal taglli--halamoocortiaa loop, in which the basal ganglia inhibits thalamic neurons that are bidirectionally connected to a recurrent cortical network [5, 49, 50]. This relates to our model as follows: the motor cortex (visible neurons) executes an action, each

---

thalamic unit (hidden neurons) encodes motor motif, and the basal ganglia silences thalamic neurons (external network modulating context). In particular, the role of the basal ganglia in this network suggests a novel mechanism of context-dependent gating within Hopfield Networks [51]. Rather than modulating synapses or feature neurons a network, one can directly inhibit (activate) memory neurons in order to decrease (increase) the likelihood of transitioning to the associated state. Similarly, thalamocortical loops have been found to be important to song generation in zebra finches [52]. Thus, the biological implementation of the DenseNet can provide insight into how biological agents reliably store and generate complex sequences.
Discussion and Future Directions
We introduced the DenseNet for the reliable storage and recall of long sequences of patterns, derived the scaling of its single-transition and full-sequence capacity, and verified these results in numerical simulation. We found that depending on the choice of nonlinear interaction function, the DenseNet could scale polynomially or exponentially. We tested the ability of these models to recall sequences of correlated patterns, by comparing the recall of sequence of MovingMNIST images with different nonlincarities. As expected, the network's 's reconstruction capabilities increased with the nonlinearity power d, with perfect recall achieved by the exponential nonlinearity. To further increase the capacity, we introduced the generalized pseudoinverse rule and demonstrated in simulation its ability to maintain high capacity for highly correlated patterns. We also introduced and analyzed the MixedNet to maintain patterns within sequences for longer periods of time. Finally, we described a biologically plausible implementation of the models with connections to motor control.
There has recently been a renewed interest in storing sequences of memories. Steinberg and Som- polinsky [53] store sequences in Hopfield networks by using a vector-symbolic architecture bind each pattern to its temporal order in the sequence, thus storing the entire sequence as a single attractor. However, this model suffers from the same capacity limitations as the Hopfield Network. Whittington et al. [54] suggest a mechanism to control sequence retrieval via an external controller. analogous to the role we ascribe the basal ganglia for depeedetde gating. Herron al. [55] investigate mechanism for robust sequence recall within complex systems more broadly, reducing crosstalk by directly modulating interactions between neurons rather than the inputs into neurons. Tang et [56] propose model for sequential recall akin to SeqNet with an implicit statistical whitening process. Karuvally et al. [57] introduce a model closely related to the cetoooccally-llussbbte implementation of our MixedNet and analyze it in the setting of continuous-time dynamics, allowing for intralayer synapses within the hidden layer and different timescales between the hidden and feature layers.
While we have focused on a generalization of the fixed-point capacity for sequence memory, this is the only notion of capacity one could consider. In other studies of MHNs, instead of considering stability as the probability of staying at fixed point, researchers quantify the probability that the network will reach a fixed point within single transition [31, 58, 59]. This approach allows one and the size of each memory's 's basin of attraction [35]. More broadly,
to quantify noise-robustred one could consider other definitions of associative memory capacity not addressed here, including those that depend only on network architecture and not on the assumption of a particular learning rule (60, 61]. However, as compared to the relatively simple analysis that possible for the fixed-point capacity of a Hopfield network using Hebbian learning rule, analyzing these alternative notions of capacity in nonlincar networks can pose significant technical challenges [61-63].
In this work, we limited ourselves to theoretical analysis of discrete-time networks storing binary patterns. An important direction for future research would be to go beyond the Gaussian theory in order to develop accurate predictions of the Exponential DenseNet capacity. There are also many potential avenues for extending these models and methods to continuous-tima networks, continuous- valued patterns, computing capacity for correlated patterns, testing different weight functions, and examining different network topologies. Finally, we hope to take inspiration from the recent resurgence of RNNs in long sequence modeling to use this model for real-world tasks [64, 65).
10

---

Acknowledgments and Disclosure of Funding
We thank Matthew Farrell, Shanshan Qin, and Sabarish Sainathan for useful discussions and com- ments on earlier versions of our manuscript. HC was supported by the GFSD Fellowship, Harvard GSAS Prize Fellowship. and Harvard James Mills Peirce Fellowship. JAZ-V and CP were supported by NSF Award DMS-213411
and NSF CAREER Award IIS-2239780. CP received additional support from Sloan Research Fellowship. This work has been made possible in part by gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence. The computations in this paper were run on the FASRC Cannon cluster supported by the FAS Division of Science Research Computing Group at Harvard University.
References
[1] Kleinfeld and Sompolinsky. Associative neural network model for the generation of temporal patterns. theory and application to central pattern generators. Biophysical Journal, 54 (6):1039-105,, 1988.
[2] Michael A. Long, Dezhe Jin, and Michale S. Fee. Support for a synaptic chain model of neuronal sequence generation. Nature, 468(7322) Nov 2010. ISSN 1476-4687. doi: 10. 1038/nature095 14. URL
[3] Maxwell Gillett, Ulises Pereira, and Nicolas Brunel. Characteristics of sequential activity in networks with temporally asymmetric Hebbian learning. Proceedings of the National Academy of Sciences, 117(47):29948 29958, November 2020. 1oi:10.1073/pnas.. 1916771177.
[4] Stefano Recanatesi, Ulises Obilini-Oiili,oviic, Masayoshi Murakami, Zachary Mainen, and Luca Mazzucato. Metastable attractors explain the variable timing of stable behavioral action sequences. Neuron, 110(1):139-153, 2022.
[5] Luca Mazzucato. Neural mechanisms underlying the temporal organization of naturalistic animal behavior. eLife, 11:776577, 2022.
[6] Edmund T Rolls and Patrick Mills. The generation of time in the hippocampal memory system. Cell Reports, 28()):1449-1658, 2019.
[7] Alexander B. Wiltschko, Matthew J. Johnson, Giuliano Iurilli, Ralph E. Peterson, Jesse M. Katon, Stan L. Pashkovski, Victoria E. Abraira, Ryan P. Adams, and Sandeep Robert Datta. Mapping sub-second structure in mouse behavior. Neuron, 88(6):121-11135 2015. ISSN 0896- 6273, doi.huts:://oi.org//// 101 new.:...nnoooo....1... 1.301. Utt.sttss:// http:///wwwww.weeeee......e www.ss.ieieedrrrt.... httpeeeeeaaareeeeeeeeeeeeeeeeeee /1//////60/0000001010005
[8] Jeffrey E. Markowitz, Winthrop F. Gillis, Maya Jay, Jeffrey Wood, Ryley W. Harris, Robert Cieszkowski, Rebecca Scott, David Brann, Dorothy Koveal, Tomasz Kula, Caleb Weinreb, Mohammed Abdal Monium Osman, Sandra Romero Pinto, Naoshige Uchida, Scott W. Lin- derman, Bernardo L. Sabatini. and Sandeep Robert Datta. Spontancous behaviour is struc- tured by reinforcement without explicit reward. Nature, 614(7946):08--117, Feb 2023. ISSN 1476-4687. doi: s4 (41586-002-00661-2
URL https://aoi.ooooo http::////oooo//1.1.10111 1038/
[9] Cengiz Pehlevan, Farhan Ali, and Bence P Ölveczky. Flexibility in motor timing constrains the topology and dynamics of pattern generator circuits. Nature communications, 2018 doi.htts::/doi.orr// 10. (0388/44147--018-00331
[10] H. Sompolinsky and I. Kanter. Temporal Association in Asymmetric Neural Networks. Physical Review Letters, 57(22):2861 December 1986. 1o 10..1
[11] Zijian Jiang. Ziming Chen, Tianqi Hou, and Haiping Huang. Spectrum of non- Hermitian deep-Hebbian neural networks. Physical Review Research, 5:013090, Feb 2023. 1o Reee:PhyyReeeesearc...0000111 PhysRevResearch.. w.t.ih....0333. 013090.
URL https://link: aps. org//oi/10/o/ooooo// 1103/
[12] Ulises Pereira and Nicolas Brunel. Unsupervised learning of persistent and sequential activity. Frontiers in Computational Neuroscience, 13:97, 2020.

---

[13] Christian Leibold and Richard Kempter. Memory capacity for sequences in recurrent network with biological constraints. Neural Computation, 18(4):904-94 941, 2006.
[14] Jeff Hawkins, Dileep George, and Jamie Niemasik. Sequence memory for prediction, inference and behaviour. Philosophical Transactions of the Royal Society B: Biological Sciences, 364 (I521):1203-122) 2009.
[15] Jeff Hawkins and Subutai Ahmad. Why neurons have thousands of synapses, theory of sequence memory in neocortex. Frontiers in Neural Circuits, page 23, 2016.
[16] Daniel Amit. Neural networks counting chimes. Proceedings of the National Academy of Sciences, 85(7):2141-2145, 1988.
[17] H. Gutfreund and M. Mezard. Processing of temporal sequences in neural networks. Phys. Rev. Lett., 61:235-238. 238, Jul 1988. doi:10. hwt.///ysseeeeee.....m 61.2 URL https://linkk aps.
org/doi/10 11/o//10.10 ww11/////////eee...e 235.
[18) Kanaka Rajan, Christopher D. Harvey, and David W. Tank. Recurrent network models of sequence generation and memory. Neuron, 90(1):128-142, 2016. ISSN 0896-6273.
fttt:::/www..cieneeerre... com/
[19] Markus Diesmann, Marc-Oliver Gewaltig, and Ad Aertsen. Stable propagation of synchronous spiking in cortical neural networks. Nature, 402(6761):522-5333 Dec 1999. ISSN 1476-4687. 1oi:10.1038/999
URL https: www.///g//..//..
0r0../.000..0111109999000001 1991/9900
[20] Nicholas F Hardy and Dean V Buonomano. Neurocompuuational models of interval and pattern timing. Current Opinion in Behavioral Sciences, 8:250-257, 2016. ISSN 2352-1546. doi.https://doi.org//W 10..
URL https: //www. sciencedirect. com/ Time in perception and action.
[21] Dina Obeid, Jacob Zavatone Veth, and Cengiz Pehlevan. Statistical structure of the trial-to-trial timing variability in synfire chains. Phys. Rev. E, 102:052406, Nov 2020. doi: 111.///yyeeE..12222222222. PhysRevE. 102. 052406.
URL atttps://inm aps. ortp/oi//////////// 1103/
[22] Matthew Farrell and Cengiz Pehlevan. Recall tempo of Hebbian sequences depends on the inter- play of Hebbian kernel with tutor signal timing. bioRxiv, 2023. doi: 10. 10.100...01//022...0.......6 URL https:tt///// //tp::///www biorxiv. org/ content/early/20222
[23] John J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, 7955)22554- 1982.
[24] John J Hopfield. Neurons with graded response have collective computational properties like those of two-state neurons. Proceedings of the national academy of sciences, ((100)3088-309) 1984.
[25] S-I Amari. Learning patterns and pattern sequences by self ooff--ongnzzing nets of threshold elements. IEEE Transactions on computers, (00(11):1197-4)
1972.
[26] John Hertz, Anders Krogh, and Richard Palmer. Introduction the theory of neural computation. CRC Press, 2018.
[27] Daniel J Amit, Hanoch Gutfreund, and Haim Sompolinsky. Spin-glass models of neural networks. Physical Review A, 3202) 1985.
[28] Daniel J. Amit, Hanoch Gutfreund, and H. Sompolinsky. Storing infinite numbers of patterns in a spin-glass model of neural networks. Phys. Rev. Lett., 55:1530-1533, Sep 1985. doi: 11.11....1111 10..103//hyseeeettt.555. PhysRevLett. 55. 1530.
URL https://link..n org//oi///..ooo 1103/
[29] Daniel Amit, Hanoch Gutfreund, and H Sompolinsky. Statistical mechanics of neu- ral networks near saturation. Annals of Physics, 173(1):30-67, 1987. ISSN 0003-4916. dww.nggs///aaooog////////0000000 com
URL. https: : ://www sciencedirect.
12

---

[30] Dmitry Krotov and John J. Hopfield. Dense associative memory for pattern recognition. Advances Neural Information Processing Systems, 29, 2016.
[31] Mete Demircigil, Judith Heusel, Matthias Löwe, Sven Upgang, and Franck Vermet. On a model of associative memory with huge storage capacity. Journal of Statistical Physics, 168(2): 288-201 288-299, July 2017. ISSN 0022-4715, 1572-9613.
[32] Dmitry Krotov, A new frontier for hopfield networks. Nature Reviews Physics, pages 1-2, 2023.
[33] Dimitri Petritis. Thermodynamic formalism of neural computing. In Eric Goles and Servet Martínez, editors, Dynamics of Complex Interacting Systems, pages 81-146. Springer Nether- lands, Dordrecht, 1996. doi:10. 1007/977 94-017-1323-8 1007/978- -0--94--222 017 1323-8_32... 8_3.
URL https:/ 10./10.
[34] Anton Bovier. Sharp upper bounds perfect retrieval in the Hopfield model. Journal of Applied Probability, 36(3):941-99)) -500, 1999. doi:10. 12399//a/110333744477
[35] R. McEliece, E. Posner, E. Rodemich, and S. Venkatesh. The capacity of the Hopfield associative memory. IEEE Transactions on Information Theory, 33(4):461 482, July 1987. ISSN 0018- 9448. 1..
[36] G. Weisbuch and F. Fogelman- Scaling laws for the attractors Hopfield networks.
J. Physique Lett., 46(14))623-630, 1985, 10. https:/ orto:io.rrg///00 10. 1wt1//ppysleeee.eeeepeee ht1pspppppplle111111110100000100
URL
[37] Samuel Muscinelli, Wulfram Gerstner, and Johanni Brea. Exponentially Long Orbits in Hopfield Neural Networks. Neural Computation, 29(2):458-484 02 2017. ISSN 0899-76677 doi: 111.1..11//NEC... a__0099..
[38] V. V. Petrov. Sums of Independent Random Variables. De Gruyter, Berlin, Boston, 1975. ISBN 97831 12573006.
Trans. A. A. Brown.
[39] John E. Kolassa Series Approximation Methods in Statistics. Springer New York, 1997. URt.htts:://ae http:://dooiooo////// wttp//..100//97....0 077-44777777777
[40] John E. Kolassa and Peter McCullagh. Edgeworth Series for Lattice Distributions. The Annals of Statistics, 18(2):981 985, 1990. doi: 46t:10..214/40//11764477666
URL https:
//doi.org//l
[41] Dmitry Dolgopyat and Kasun Fernando. An Error Term in the Central Limit Theorem for Sums of Discrete Random Variables. International Mathematics Research Notices, 05 2023. ISSN 1073-7928. doi:10. 10.1109//m///maoo/ URL https: //doi. org/ 10. 10t10099/mmmm htt/s/mmmm///eee/ee http///immm/raadeee rnad088. mad088.
[42] Nitish Srivastava, Elman Mansimov, and Ruslan Salakhudinov. Unsupervised learning of video representations using Istms. In International conference on machine learning, pages 843-852. PMLR, 2015.
[43] I. Kanter and H. Sompolinsky. Associative recall of memory without enrors. Phys. Rev. A, 35: 380-392, Jan 1987. doi: 10.1 10..110////yyyys........000 URL https:////lnk aps org//oi/10.. 1103/PhysRevA. 35.355..8 380.
[44] Leo van Hemmen and Reimer Kühn. Collective phenomena in neural networks. In Eytan Domany, J. Leo van Hemmen, and Klaus Schulten, editors, Models of Neural Net- works pages 1-113, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg. ISBN 978- 3-642-79814-6. do 101.10077778733442799888 978-3-642-79814-622
URL https::/ddn htt////...r/111.100001100
[45] Eric R Kandel, James H Schwartz, Thomas M. Jessell, Steven Siegelbaum, A James Hudspeth, Sarah Mack, al. Principles of neural science. McGraw-hill New York, 6 edition, 2021.
[46] Thomas F Burns and Tomoki Fukai. Simplicial Hopfield networks. In The Eleyenth International Conference Learning Representations, 2023.
13

---

[47] Dmitry Krotov and John J. Hopfield. Large associative memory problem in neurobiology and machine learning. International Conference on Learning Representations. 2021. URL https://openreviier wtw..eeeeoormmm//xxxy1000000
[48] Dmitry Krotov. Hierarchical associative memory. arXiv preprint arXiv:2107.06+440 2021.
[49] Ta-Chu Kao, Mahdieh S Sadabadi, and Guillaume Hennequin. Optimal anticipatory control as a theory of motor preparation: A thalamo-cortical circuit model. Neuron, 109(9):1567-1581, 2021.
[50] Laureline Logiaco, LF Abbott, and Sean Escola. Thalamic control of cortical dynamics in model of flexible motor sequencing. Cell Reports, 35(9):10909) 2021.
[51] Nicolas Y. Masse, Gregory D. Grant, and David J. Freedman. Alleviating catastrophic forgetting using context-dependent gating and synaptic stabilization. Proceedings of the National Academy of Sciences, 115(44), October 2018. ISSN 0027-8424, 1091-6490.
doi:10.1073: htt.://pa...0033//... 1803839115.
[52] Felix W. Moll, Devorah Kranz, Ariadna Corredera Asensio, Margot Elmaleh. Lyn A. Ackert- Smith, and Michael A. Long, Thalamus drives vocal onsets in the zebra finch courtship song. Nature, 636 136, Apr 2023. ISSN 1476-4687. URL. httpt://dd/oi... org/10. 10.
[53] Julia Steinberg and Haim Sompolinsky. Associative memory of structured knowledge. Scientific Reports, 12(1):21808, Dec 2022. ISSN 2045-2322, doi: 10988/44159--022227700--3 URL
https::/doi... org/10. 1038/ 1ww11/00////1---11 1241599-022--21 -22-0220---2------
[54] James C. R. Whittington, Joseph Warren, and Timothy E. J. Behrens. Relating transformers to models and neural representations the hippocampal formation, March 2022.
[55] Lukas Herron, Pablo Sartori, and BingKan Xue. Robust retrieval of dynamic sequences through interaction modulation. arXiv preprint arXiv:2211.17155: 2022.
[56] Mufeng Tang, Helen Barron, and Rafal Bogacz. Sequential memory with temporal predictive coding. arXiv preprint arXiv:2305.11982 2023.
[57] Arjun Karuvally, Terry J Sejnowski, and Hava T Siegelmann. Energy-based general sequential episodic memory networks at the adiabatic limit. arXiv preprint arXiv:2212.0556:. 2022.
[58] Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gruber, Markus Holzleitner, Thomas Adler, David Kreil, Michael K Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. Hopfield networks is you need. International Conference on Learning Representations, 2021. URL https: /ttp////ppe//ee/ee////eee www.eeiwwwwwwwfrrrreee net/forum? id=tL89RnzIidd.
[59] Carlo Lucibello and Mare Mézard. The exponential capacity of dense associative memories. arXiv preprint 230.::2304.149644 2023.
[60] Andreas Knoblauch, Günther Palm, and Friedrich T Sommer. Memory capacities for synaptic and structural plasticity. Neural Computation, 22(():289-33) -411, 2010.
[61] Jacob A. Zavatone- Veth and Cengiz. Pehlevan. On neural network kernels and the stor- age capacity problem. Neural Computation, 34(5):1 11421 04 2022. ISSN 0899-7667. 10i:10.1162//e a 01444. URL https://doi http://......................... a_1494
10.
[62] Jacob A. Zavatone- Veth and Cengiz Pehlevan. Activation function dependence of the storage capacity of treelike neural networks. 2021. doi: 10. 103.0.../////yheeeee.. 103.00003 URL attps://links www.aap....aooe.e..... hts//oii10... 1103/ PhysRevE. 103. L020301.
Phys. Rev. E. 103:L020301, Feb
[63] Rémi Monasson and Riccardo Zecchina. Weight space structure and internal representations: direct approach to learning and generalization in multilayer neural networks. Phys. Rev. Lett., 75:2432-2435, Sep 1995. doi: 10 10 URL https: //l::k///nnk..//.// aps aps.org/ org/
doi/10. 110//11y00teeeeeee h03//hhseeeeett....mmmmem 7432.3.
14

---

[64] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396 2021.
[65] Antonio Orvieto, Samuel Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. arXiv preprint arXiv:2303.06344 2023.
[66] Dmitry Krotov and John Hopfield. Dense associative memory is robust to adversarial inputs. Neural computation, 30(12)331513166 2018.
[67] HH Chen, Lee, GZ Sun, HY Lee, Tom Maxwell, and C Lee Giles. High order correlation model for associative memory. In AIP Conference Proceedings, volume 151, pages 86-99, American Institute of Physies, 1986.
[68] Demetri Psaltis and Cheol Hoon Park. Nonlinear discriminant functions and associative memories. In AIP conference Proceedings, volume 151, pages 370-375. American Institute of Physics, 1986.
[69] Pierre Baldi and Santosh S Venkatesh. Number of stable points for spin-glasses and neural networks of higher orders. Physical Review Letters, 58(9):913, 1987.
[70] Gardner. Multiconnected neural network models. Journal of Physics A: Mathematical and General, 20(11):34553 1987.
[71] Laurence F Abbott and Yair Arian. Storage capacity of generalized networks. Physical review A, 36(10))5091, 1987.
[72] Horn and Usher. Capacities of multiconnected memory models. Journal de Physique, 49 (3):389-333) -998 1988.
[73] Elena Agliari, Alberto Fachechi, and Chiara Marullo. Nonlinear PDEs approach to statistical mechanics dense associative memories. Journal of Mathematical Physics, 63(10):103304 2022. 1oi:10.1063/5.000 10..1605000094411 URL
10. 1063/5060550 009541.
[74] Elena Agliari, Linda Albanese, Francesco Alemanno, Andrea Alessandrelli, Adriano Barra, Fosca Giannotti, Daniele Lotito, and Dino Pedreschi. Dense Hebbian neural networks: a replica symmetric picture of unsupervised learning. arXiv, 2022. doi: 10.44855//RXXI.2211....
URL https::/arxiv..ot
2211.14067.....
[75] Linda Albanese, Francesco Alemanno, Andrea Alessandrelli. and Adriano Barra. Replica symmetry breaking dense Hebbian neural networks. Journal of Statistical Physics, 189(2): 24, Sep 2022. ISSN 1572-9613. doi: 10t100000///10555550000000 10.1007/s1000 022 02966-8.
URI. https::t org/
[76] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities:
A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013. ISBN 9780199535255.
doi: 10. 1tt.10//////oooo/00//00000005510 org/10. 1093/acprof 0000997809995355555
00.22550001.001.... URL https://doi.
[77] DLMF, NIST Digital Library of Mathematical Functions.
http:/ddlmf..is..oovv... Release 1.1.1 of 2021-03-15, 2021. URL http:// http::/ddi /tlmf//mmffff//ff .nst.. .ostt..g....... F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. Schneider, F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
[78] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database, ATT Labs [Online], 2, 2010. URL http://yamm lecun. cww/ comm/exdb/mniste
15

---

A Review of Modern Hopfield Networks
Here we review the Hopfield network and its modern generalization as an auto-associative memory model. These ideas will be helpful for storing sequences in network dynamics.
A.1 The Hopfield Network
We first introduce the classic Hopfield Network [23]. Let N be the number of neurons in the network and Stt) E {-1,+11 +11 N be the state of the network at time t. The task is to store P patterns, {E' ...... ). where ş E {+1] is the jth neuron of the nThh pattern. The goal is to design network with dynamics such that when the network is initialized with pattern, it will converge one of the stored memories.
The Hopfield Network [23] attempts this by following the discrete-time synchronous update rule":
S(I + 1) (S())
(A.1)
where the transition operator THv()), for neuron i is defined in terms of symmetric Hebbian weights:
(S). sgn
Sq
Ju
Σ C
(A.2)
N
Note that we are excluding self-interaction terms (Ji:) in Equation A.2. To interpret this dynamics from another useful point of view, we define the overlap, or Mattis magnetization, my of the network state S with pattern e We can then rewrite the update rule for the Hopfield Network as
THN(S); = sgn Σ E mm
m (N-
S $43
(A.3)
We interpret this at every time f, the network tries to identify the pattern E it is closest and updates neuron i to the value for that pattern. A natural question to ask about the associative memory networks is their capacity: how many patterns can be stored and recalled with minimal error? This question has been the subject of many studies [23, 27-29, 33-36]. Intuitively, in recalling a pattern E", what limits the network's 's capacity is the overlap between the pattern &" and other patterns, referred to as the crosstalk [26, 36].
A precise answer to the storage capacity question can be given under the assumption that the patterns { are sampled from some probability distribution. While different notions of capacity have been considered in the literature [23, 27-29, 33-36), focus on the fixed-point capacity, which characterizes the probability that, when initialized at given pattern, the network dynamics do not move the state away from that point. To render the problem analytically tractable, it is usually assumed that the pattern components are i.i.d. Rademacher random variables, i.c., IP(5) = +1) = 1/2 for all j and μ. Then, finite network size one define the capacity as
PNN(N,c) max { P ,2....,2"%
2N ( (H"N(E) { 2 21 -1-c] c).
(A.4)
where e E 1) is fixed error tolerance. As we review in detail in Appendix B, one finds an asymptotic capacity estimate PuN Tlog(N) [33-35].
N for == 0, which can be shown to be sharp threshold
A.2 Modern Hopfield Networks
Recent work from Krotov and Hopfield [30, 66) reinvigorated line of research into generalized Hopfield Networks with larger capacity [67-72], resulting in what are now called Dense Associative Memories or Modern Hopfield Networks:
TMHN (S); == sgn
Σ f (m))
(A.5)
'For the Hoptield network, one can also consider asynchronous update rule in which only one neuron is updated each timestep [23, 26].
S1

---

where f. referred to as the interaction function, is a nonlinear monotonically increasing function whose purpose to separate the pattern overlaps for better signal noise ratio. Since (t) has maximum value of 1, this means contributions from patterns with partial overlaps will be reduced by the interaction function. This diminishes the crosstalk and thereby increases the probability of transitioning to the correct pattern. If the interaction function is chosen to be f(x) = x², then the N MHN's capacity has been shown to scale polynomially with network size as P ~ Ba Iog(N where Ba
a numerical constant depending on the degree d [30, 73-75]. Using a different definition of capacity, Demircigil et al. [31] have also shown that an exponential nonlinearity can lead to exponential scaling of the capacity. See [32] for a recent review of these results.
B Review of Hopfield network fixed-point capacity
In this Appendix, review the computation of the classical Hopfield network fixed-point capacity. Our approach will follow- but not exactly match- that of Petritis [33]. Though these results are standard, we review them in detail both because this approach will inspire in part our approach to the DenseNet, and because several important steps of the analysis are significantly simpler than the corresponding steps for the DenseNet.
We begin by recalling that the Hopfield network update can be written as
(H) = sgn
Σ
$
Σ
S
(B.1)
N N
j
and that our goal is determine
PuN(N,c) c) max {P (2,...,2
[[ (T = 5n 2 - c)
(B.2)
for some absolute constant in theoretical studies of Hopfield model capacity [26-29, 33-36], we take in these probabilities the pattern components t to be independent and identically distributed Rademacher random variables. We can expand the memorization probability as a union of single-bitflly events:
< least in the regime where P,P [33-36]. As is standard
P
P N = 5d} = =I-P ((THNE(E))) # E
P
n
(TTNN(E")
(B.3)
L=1i==
This illustrates why analyzing the memorization probability is complicated: the single-patted events T H. (E") = g" are not independent across patterns μ4, and each single-pattern event is itself the intersection non-independent single-neuron events THN (g*) = ş!" However, as the single-bitflip probabilities (P(T * E/" are identical for all and we can obtain a straightforward union bound
P
P N (THNN(E"):++
P
T THN (E") =
= P
(B.4)
-=11==
2 1 ΣΣ
P (THN +59
(B.5)
= NNPPTTN(E)) # El).
(B.6)
where we focus without loss of generality the first element of the first pattern. Therefore, if we can control the single-bitflip probability P(TTN((E)) * El]. we can obtain a lower bound on the true capacity. In particular,
PHN(No c) 2 max (P (2. (2...., .22 NNPTTN((E)) + s
(B.7)
S2

---

From the definition of the Hopfield network update rule, we have
F[THN(E*) + stl
sgi
53
+
(B.8)
N
jæi
(B.9)
N
#=1 jFi
PC 1],
(B.10)
where we have defined
P C N-T N-N E Jfi
(B.11)
and used the fact that the distribution of C' is symmetric. C is referred to as the crosstalk, because it represents the effect of interference between the first pattern and the other P- patterns on recall of the first pattern. We can simplify the crosstalk using the fact that, since we have assumed i.i.d. Rademacher patterns, we have the equality distribution
d
(B.
for all μ ....., P Pand j I...., N. yielding
P
C
(B.13)
N
2= sfi
Similarly, we have
5 - 5/
(B.14)
for / = 2.... Pand j ...... N, which finally yields
(B.15)
Therefore, for the classic Hopfield network the crosstalk is equal in distribution the sum of (P - I) - 1) i.i.d. Rademacher random variables.
B.1 Approach 1: Hoeffding's inequality
Now, immediately apply Hoeffding's inequality [76], which implies that for any 0
P
N
t²
IP
5k
1 < exp
(B.
2 2(P 1)(N - 1)
k=
We then have that
P
N
1N - P
P
c N N-1
< exp
(B.17)
2=
We then have the bound
1
PHN (N. 2 max
PE (2....,2N1 NP exp
soj.
(B.18)
2
We now want to consider the regime > 1, and demand that the error probability should tend to zero as we increase N. If we substitute in the Ansatz
N
P log N
(B.19)
S3

---

the bound is easily seen to tend to zero for all a 2 4, yielding an estimated capacity of
PAN- ~ 4log N
(B.20)
As this estimates follows from sequence of lower bounds on the memorization probability, it is a lower bound on the true capacity of the model [33]. However, via a more involved argument that accounts for the associations between the events T THN = 5 it was shown by Bovier [34] to be tight.
For the classical Hopfield network, the single bitflip probability P(C > 1] is easy to control using elementary concentration inequalities because the crosstalk can be expressed as a of (P 1)(N 1) i.i.d. random variables. Therefore, we expect the crosstalk to concentrate whenever N large. However, for the DenseNet, will find in Appendix C that the crosstalk is given as the sum of P - 1 i..dd random variables, each of which is nonlinear function applied to the sum of N 1 i.i.d. Rademacher random variables. Naïve application of Hoeffding's inequality is then not particularly useful. We will therefore take a simpler, though less rigorously controlled approach, which can also be applied to the classical Hopfield network: we approximate the distribution of the crosstalk as Gaussian [26].
or P or both together
B.2 Approach 2: Gaussian approximation
For the classical Hopfield network, the fact that the crosstalk can be expressed as sum of (P 1)(N 1) i.i.d. Rademacher random variables means that the classical central limit theorem implies that it tends in distribution to a Gaussian whenever (P I)(N 1) tends to infinity. By symmetry, the mean of the crosstalk zero, while its variance is easily seen to be
P-1
var(C)
(B.21)
N-1
If we approximate the distribution of the crosstalk for N and P large but finite by a Gaussian, we therefore have
N -
P|C > = H
(B.22)
P-1
where H(x) = erfc(s/V2)/2 is the Gaussian tail distribution function. We want to have IP[C' >
1] + 0, so we must have (P- 1)/(N
1) + 0. Then, we can use the asymptotic expansion [26]
exp (-1) 1 {
H(V²) 2) = V2TZ
as - 0c
(B.23)
to obtain the heuristic Gaussian approximation
(P-1) P(C 1| | 2Tt -1) exp
(N (-N-1) 1) 2(( 1)
(B.24)
If we use this Gaussian approximation instead of the Hoeffding bound applied above, we can easily see that we will obtain identical estimates for the capacity with an eтror tolerance tending to zero. However, we have given up the rigor of the bound from Hoeffding's 's inequality, since we have not controlled the rate of convergence to the Gaussian tail probability. In particular, the Berry-Essedd theorem would give in this case uniform additive error bound of 1/ /PP 1)(N - 1), which in the regime P N/la log N] cannot compete with the factors of N or NP which we want P(C > 1] to overwhelm. We will not worry about this issue, as we are concerned more with whether we can get accurate capacity estimates that match numerical experiment than whether we can prove those estimates completely rigorously.
We can also use the Gaussian approximation to estimate the capacity for a non-zero error threshold e at finite N. Concretely, if we demand that the union bound is saturated, i.c.,
NPP(T + +l c,
(B.25)
S4

---

under the Gaussian approximation for the bitflip probability we have the self-consistent equation
NPH
P-1
=c
(B.26)
for P, which we can re-write as
P-1= N -
(B.27)
[H-Ic//NP)3
This is transcendental self-consistent equation, which not easy to solve analytically. However, we can make some progress at small c/ c/(NP) P). Using the asymptotic expansion of the inverse of the complementary error function [77], we have
[H- (x))² (2v)
(B.28)
1
log
4xxx 2og
(B.29)
2x
1
2 log(()) - -log(4)) log log
(B.30)
2r
2 log(z)
(B.31)
as x - 0. Then, assuming e is such that - -oo((c) is negligible relative to log(N P), we have
N
Pa (lP)
(B.32)
which solve for P
N
P~
(B.33)
2Wo(N2/2)
where Wo is the principal branch of the Lambert- W function [77]. But, at large N, we can use the asymptotic (NNN) ()) to obtain the approximate scaling
P
(B.34)
(
which agrees with our earlier result. Conceptually, this intuition is consistent with there being a sharp transition in the thermodynamic limit, proved rigorously by Bovier [34].
C DenseNet Capacity
In this Appendix, we analyze the capacity of the DenseNet. As introduced in Section 2.1 of the main text, there are two notions of robustness consider: the robustness of a single transition and the robustness of the full sequence. For fixed N E (2. and an error tolerance e E (0, 1). we
define these two notions of capacity as
Cr max (P ( ".....,2] (TDN(E)) = {²] 2 21-c)
(C.1)
and
Ps(N,c) = max respectively.
2n PP (TNN((()) = = 2 1
(C.2)
Our goal to approximately compute the capacity in regime in which N and P are large. Following Petritis [33]'s approach to the HN, to make analytical progress, we can use union bound control the single-step error probability in terms of the probability of single bitflip:
[ IN =
N
= =1 UTTDN(E"): (r
(C.3)
N Σ
2 1
TDN( + e
(C.4)
1
DN )i +
(C.5)
S5

---

where we use the fact that all elements of all patterns are i..d. by assumption. We use similar approach control the sequence error probability in terms of the probability of single bitflip:
P
TT (5* = =
P
N
(t + 5/t11
(C.6)
2 Σ
P
(DN( + s
(C.7)
= 1 NPP((DD((E) * E
(C.8)
Thus, claimed in the main text, we have the lower bounds
Pr(N, 2 max (P E (2....,,2) 2 NTP(TDN(EE)) * + cc
(C.9)
and
Ps(N,c) 2 max {P E (,,..., 2 (NPPTTNN(EE) + E S c].
(C.10)
As introduced in the main text, for perfect recall, we want to take the threshold c to be zero, or at least tend to zero N and P tend to infinity. The capacities estimated through this argument bounds on the true capacities, as they are obtained from lower bounds on the true recall probability, However, expect for these bounds in fact be tight in the thermodynamic limit [33, 34].
lower
By the definition of the DenseNet update rule with interaction function f given in Equation (2), we have
TDN (E*): = sgn
P Σ
catl
1
N N-1 Σ
1
N
(C.11)
p=1
5=2
and therefore the single-bitflip probability is
1
P(TDN(E'), * +
P
sgn
Σ
S1
c++
N Σ
5
*
(C.12)
P
P
N N 55
1
Σ
(C.13)
51
#=1
y=2
P
1
= P
f(1) +
cn+1
Σ
53
<
0
(C.14)
N
1=2
==2
For both the polynomial (/(x) = xd)) and exponential (f(x) = ((N--1)o-1)
interaction functions,
f(1) 1, and so
P
1 - - <-1
((TDN(E)) + =
Σ
2c f
(C.15)
N
2=2
1=2
We refer to the random variable
N N N-1
Σ -
=
Σ SiST
egutt
(C.16)
on the left-hand-side of this inequality as the crosstalk, because it represents the effect of interference between the first pattern and all other patterns [26, 36].
S6

---

We now observe that, as we have excluded self-interactions (i.e., the sum over neurons inside the interaction function does not include j 1). we can use the periodic boundary conditions shift indices as E/ Et+1 for all μ. yielding
C I
1 N N-
5
(C.17)
Thus, the single-bitflip probability for this DenseNet is identical to that for the corresponding MHN with symmetric interactions. Then, we can use the fact that E/ d Ej for all μ 2,..., P obtain
1
C
f
Σ
53
(C.18)
#=2
Now, define the P - random variables
x" Ef'
(C.19)
N
for μ = 2........ such that the crosstalk their sum,
C= Σx
(C.20)
As the patterns Eÿ are i.i.d,, x are i.i.d. random variables of mean
N N
E Exx"| = E f
Sj
=
0
(C.21)
j=2
and variance
N N
var var(x") = E f
(C.22)
which is bounded from above for any sensible interaction function. We observe also that the distribution of each X is symmetric because of the symmetry of the distribution of G We will therefore simply write X for any given x"
Then, the classical central limit theorem implies that the crosstalk tends in distribution to a Gaussian of mean zero and variance (P 1) var(x) as P + oc, at lease for any fixed N. However, we are interested in the joint limit in which N, P - co together. We will proceed by approximating the distribution of C' as Gaussian, and will not attempt rigorously control its behavior in the joint limit.
Approximating the distribution of the crosstalk for N, P > by a Gaussian, we then have
P(TDN(E'), # 2 H
(C.23)
((P - 1) var(x)
where H(x) erfe(1/ /2)/2 is the Gaussian tail distribution function. We want have P(TDN(E')) + e?l -> 0, so we must have (P - 1) var(x) + Then, we can use the asymp- totic expansion [26]
H(V2)= = V2Tz
exp (-2
1 +
as 2 + 00
(C.24)
2
obtain
(P - 1) var(x)
P(TDN(E') # + R
2x
exp
2(P - 1) var(x))
(C.25)
S7

---

For each model, we can evaluate var(x) and then determine the resulting predicted capacity.
As did for the classic Hopfield network in Appendix B, we can estimate the capacity finite within the Gaussian approximation by inverting the Gaussian tail distribution function. Concretely, under the union bound, we estimate the transition capacity by solving
c= NH
(C.26)
VPr - 1) var(x)
which yields
Pr var (xx(x)(H-
(C.27)
and the sequence capacity by solving the transcendental self-consistent equation
c NPsH
(V(Ps 1) var(x)
(C.28)
which we can re-write as
Ps (cxxx))
(C.29)
As in the classic Hopfield case, we can simplify these complicated equations somewhat by assuming that c/N and c/ cs) are small. Concretely, using the asymptotic
(x))² log(r)
(C.30)
for x - 0, the transition capacity simplifies to
Pr - 2 var(x) log(NN)
(C.31)
under the assumption that log(c) is negligible relative to log(N). For the sequence capacity, we can follow identical argument to that used for the classic Hopfield network to simplify the self-consistent equation to
Ps 2 var log(NPs)
(C.32)
under the assumption that 1 log(c) is negligible relative to log( [ Ps), which we can solve obtain
Ps 2 var(x) (N/2 var(x)
(C.33)
Assuming that N/ var(x) - oo N 0o, we can use the asymptotic Wi(N) log(N) obtain the asymptotic
Ps 2 var(x) /og[N/ var(x)]
(C.34)
Our first check on the accuracy of the Gaussian approximation will be comparison of the resulting predictions for capacity with numerical experiment. As another diagnostic, we will consider the excess kurtosis Gaussian, the excess kurtosis vanishes, while large values of the excess kurtosis indicate deviations from Gaussianity. By the additivity of cumulants, we have
Ka (C) (C) for (C) the n-th cumulant of C. If the distribution is indeed
Ken (C) = (P - (x)x
(C.35)
By symmetry, all odd cumulants of x-and therefore all odd cumulants of C-aare identically zero As noted above, we have
var(x) x2(x) = E f
(C.36)
N -
S8

---

If C' is indeed Gaussian, then all cumulants above the second should vanish. As the third cumulant vanishes by symmetry. the leading possible correction Gaussianity the fourth cumulant, which as x has zero mean is given by
K4 xx = [xx) (x)
(C.37)
72
2
N j=2
E
31E
(C.38)
N
Rather than considering the fourth cumulant directly, we will consider the excess kurtosis
x= K4 (C)
Ra(x)
(C.39)
(C)² P-1 (x)
which is a more useful metric because it is normalized.
C.1 Polynomial DenseNet Capacity
We first consider the Polynomial DenseNet, with interaction function f(x) = xd for d E Nyo. To compute the capacity, our goal is then to evaluate
2d
var(x) =E
S
(C.40)
N
1=
at large N. From the central limit theorem, we expect
20
N
22d 1)!! (N
E
Σ
(C.41)
1)d
We can make this quantitatively precise through the following straightforward argument. Let
E
(C.42)
VN
j=2
We then have immediately that the moment generating function of E is
N-1
M(t) B(e² cosh
(C.43)
V
hence the cumulant generating function is
(() log (t) (N (
1) log cosh
(C.44)
VN
The function + log cosh(x:) an even function of x, and is analytic near the origin, with the first few orders of its MacLaurin series being
2.2
x
log cosh(x)
O(*)).
(C.45)
12
Then, the odd cumulants of E vanish as we expect from symmetry-whil the even cumulants obey
Czk
K2z
(C.46)
(N 1)
for combinatorial factors Cz that do not scale with N. We have, in particular, C2 1 and C4 -2. By the moments-cumille formula, we have
E 2
B2 (0, K22, O, K4,""" )
(C.47)
S9

---

for B2x the 2k-th complete exponential Bell polynomial. From this, it follows that
(2k: 1)!! O(N
(C.48)
as all cumulants other than Aig = 1 are O(N Therefore, neglecting subleading terms, we have
2d
N
(2d 1)!!
]
1
var(x)
+ O
(C.49)
N -
Nd
N
Following the general arguments above, we then approximate
P(2d 1)1!
N
P((DNN(E)) E
Nx exp
(C.50)
2P(2d 1)!!
To determine the single-transition capacity following the argument Section 2.1, must determine how large we can take p = P(N) such that NP(TnNN("), # E + O. Following the requirement that P var(x) O, we make the Ansatz
Nd
P a2d 1)!! log N
(C.51)
for some a. We then have
NP(TDDNEE) (E-) + EΩ]
2Ta log Nl-a/2
(C.52)
This tends zero if 2 meaning that the predicted capacity in this case is
Nd
Pf 2(2d 1)!! log
(C.53)
We now want determine the sequence capacity, which requires the stronger condition NPF(TDN(E)) * { + 0. Again making the Ansatz
Nd
P ald 1)!! log N
(C.54)
for some a, then have
NPP(ToN(E") + Ed
2 1)!! (a log Ny3/2 N Nd+1-a/2
(C.55)
which tends to zero if a 2 2d + 2. Then, the predicted sequence capacity is
Nd
Ps
(C.56)
2(d + 1)(2d 1)!! log N
If we consider the alternative asymptotic formulas obtained above from the finite-c argument, we have
Nd
Pr 2 (ra(())og((N) 2(2d 1)!! log(N)
(C.57)
and
Nd
Nd
Ps 2 var(x) log( N/ var(x))
2(2d 1)!! log Nd+1 1/2111/222ddd - 1)!!
2(d + 1)(2d - 1)!! !!!!!!!! log (N)
(C.58)
which agree with these results. For evidence of the finite-e argument for the polynomial DenseNet, observe Figure C.I.
S10

---

Polynomial DenseNet (Finite C)
7
Theery (2+1)
... 5mm Poly (pm2, 0.31
Sim Paly (2-2. c- 0.3)
Sm: Poly (d-3. = 0.5)
sim Pay Ide4, c 0.5)
Theory (2x2)
Sim Poly (sm2, 0.21
Sim Paly (de2 0.2)
Sm Paly (d+3 0.))
sims Payy ide4, 0.2
6
Theory (dw3)
3mm Poly (Sm2.
Sim Paty (de2 0.1
...
Sm Poly (de3, 0.))
sins Poly idea, 0.3
Theary (0
... 5mm Paly (9:3, 0.01
... Sim Pnly 28.2.
... Sm soy de 0.00
boyyydin 0.0)
5
(P+
4
3
2
1
0
10
20
30
40
50
60
70
80
90
100
N
Figure C.1: The transition capacity of the polynomial DenseNet is demonstrated for different values of error tolerance c. We see that even for c + O, we get similar scaling curves although the capacities slightly increase consistently plot from 0.0 to 0.5 for each degree d, with the legend labeling curves to 0.3 to demonstrate the general trend.
increase indicated by transition from dark to light. We
Using the Gaussian approximation for moments of given above, we can easily work out that
xa(x) [l(()*)
3E(())
(C.59)
27
N
E f N
3E
(C.60)
N
デ=2
j=2
= N2d ((4d - 1)!! 3[(dd (2d-1)))1 1
1
(C.61)
N
Then, the excess kurtosis of the Polynomial DenseNet's 's crosstalk is
1
(4d - 1)!! (2d 1)!!
3 1+0 )
(C.62)
Thus, for the Polynomial DenseNet, we expect the excess kurtosis to small for any fixed so long P and N are both fairly large, without any particular requirement on their relationship. In particular, under the Gaussian approximation we predicted above that the transition and sequence capacities should both scale
Nd
P
(C.63)
Ogd log N
where oua depends on but not on N. This gives an excess kurtosis of
Oid log N
(4d - 1)!! (2d 1jm1
111+00 o
1
1 N
(C.64)
Nd
which for any fixed rapidly tends to zero with increasing N. This suggests that the Gaussian approximation should be reasonably accurate even at modest N, but of course does not constitute proof of its accuracy because we not considered higher cumulants. However, this matches the results of numerical simulations shown in Figure 2.
$11

---

Exponential Denseleet capacity C.2
We now turn our attention the Exponential DenseNet, with separation function f(x)
e(N-1)(x=1), In this case, we have
- expl-)=epl1220 2(N - 1)]E
exp
c2
(C.65)
j=2
N
= expl - 1) II
exp (2
(C.66)
j=2
[xpp--2(N))) - 1)] (2)
(C.67)
(C.68)
BN-I1
where we have defined the constant
exp(2)
1.96403.
(C.69)
(2) (2)
Then, we have the Gaussian approximation
P
BN
P(TDN(E')) # E7]
2T
exp
2P
(C.70)
As in the polynomial case, we first determine the single-transition capacity by demanding that NP(TDNNE*), # E O. We plug in the Ansatz
3N
P
(C.71)
log N
for a, which yields
NP(TDN(E")) + +
2Ta log N N 11-a/2
(C.72)
This tends to zero if a 2 2, which gives predicted capacity of
BN-1
Pr
(C.73)
2 log N
Considering the sequence capacity, which again requires that NPP(Tnn(E'), * + in the Ansafz
0, we plug
P~ 3N-1 aN
(C.74)
which yields
NPPTDN(E')) # Gl
2TaN exp
[log 3
2 9) N
(C.75)
aB
This tends to zero for 2 2log 8, meaning that the predicted capacity is in this case
3N-1
Ps 2 2og (3)N
(C.76)
Therefore, while the ratio of the predicted single-transitig to sequence capacities is finite for the Polynomial DenseNet-in is simply Ps/Pr ~ 1-for the Exponential DenseNet it tends to zero as Ps/Pr ~ log N/ N.)
Using the asymptotic formulas obtained above from the finite-c argument, have
1
N
Pr var(x) log(N)
(C.77)
log(NN
$12

---

Exponential DenseNet (Finite C)
7
Theory
6
Sim: cm0.5
Sim: c-0.4
Sim: c-0.3
5
Sim: c=0.2
Sim: c-0.1
4
Sim: c=0.0
6
3
2
1
0
1 2 4
11111111114111111111100002222211
N
Figure C.2: The transition capacity of the exponential DenseNet is demonstrated for different values of error tolerance c. We see that even for c + O, we get similar scaling curves although the capacities slightly increase consistently increase
and
BN
GN
Ps 2 log var(x)]
(C.78)
[og
N
2 log(3)
which agree with these results. For evidence of the finite-c argument for the exponential DenseNet, observe Figure C.2.
Now considering the fourth cumulant, we can easily compute
[cosh(4) exp(4)
N-1
(2))
N-1 exp(4)
Rx(x)=
-3
(C.79)
which yields an excess kurtosis of
cosh(4) c2sh
N-1
3
(C.80)
P-1
For this to be small, P must be exponentially large in N, which contrasts with the situation for the Polynomial DenseNet, which the excess kurtosis is small for any reasonably large P. If we consider taking
BN-1 a log N for constant a, as the Gaussian theory predicts for the Exponential DenseNet transition capacity, we have
(C.81)
a log N BN-1
cosh(4) (4)
N-1
3
(C.82)
c2sh
cosh(4) (4)
N-1
a log N
(C.83)
exp(2) cosh(2)
2 a Colog(N)(O..o0)) (0.9823)--
N-1
(C.84)
This tends zero as N increases, but only very slowly. partieular, (0..9883)) increases with N up to around N ~ 19, where it attains a maximum value around 2, before decreasing towards zero. The situation even worse for the sequence capacity, for which the Gaussian theory predicts
3N-1
P
(C.85)
aN
S13

---

yielding
oN
cosh(4) (4)
N-1
x 3N-1
cosh((2)2
(C.86)
cosh(4)
oN
(C.87)
exp(2) cosh(2)
(0.98.))3)) N-1
(C.88)
N (00.9823) increases with N up to around N = 56, where it attains value of approximately 21.
Taken together, these results suggest that might expect substantial finite-size corrections the Gaussian theory's 's prediction for the capacity. In particular, as the excess kurtosis of the crosstalk is positive, the tails of the crosstalk distribution should be Seavierthan-GGausiin,, Gaussian, suggesting that the Gaussian theory should overestimate the true capacity. This holds provided that the lower bound on the memorization probability resulting from the union bound reasonably tight.
D Bounding the polynomial DenseNet capacity
Here, we adapt Demireigil et al. [31]'s proof of rigorous asymptotic lower bound on the polynomial MHN's capacity to obtain rigorous asymptotic lower bound on the DenseNet capacity. This proof is a step-by-step adaptation of the proof of Theorem 1.2 of Demircigil et al. [31], which we spell out in detail for clarity.
Our objective is to obtain an upper bound on the single-bitflip probability
PP[DDN (5²); * { which we have argued can be expressed in terms of the crosstalk C as
(D.1)
P((TDN(E)) # E2] TP(C -1]
(D.2)
for
N
C
53
(D.3)
N
2
Our goal to prove the following: First, letting a 2(2d 1)!! and P /o/(a N), we have
NP[TDN (E') ) * &
(D.4)
as N co. Second, letting > 2(d + 1) 1)!! and P = N 1a/(a N), we have
NP (5 + + + 0
(D.5)
as N oc.
By Cherooff's inequality (also known as the exponential Chebyschev inequality) [76], then have
P(TnN(E*), *
E
Σ
ch
ca Sj
< <N 1)a
(D.6)
|
j=2
<e- < 1)ah
Eexp
Eexp
Σ
eli
(D.7)
for any & 0. Using the fact that the pattern elements are i.i.d., we have
d
P-1
P
N
Eexp
-t
Σ
Σ
E Eexp
tgg
Σ
c/'
(D.8)
p=2
1=2
f-2
E cosh
t
Σ
(D.9)
j=2
$14

---

Now, let
N
M
(D.10)
VN
and expand the expectation as a sum over the possible values m E (0 1/2 IN. 1) of M:
Cosh
Σ
4
Σ cosh [E(N - 1)d/2m= PIM m].
(D.11)
For N >> 1, the distribution of . is nearly Gaussian. We thus split the sum over to allow to treat tail events separately. We fix 3 > 0, and split the sum at l
Σ cosh [(N 1)4/2m² PIM = m] = E
cosh [((N - 1)d/2m PIM = m]
772
Im No
Σ
cosh [[(N- 110/2m P[M m],
(D.12)
where we have used the fact that M S -VN-1.
We first consider the tail sum over |m| log(N)). As cosh is even and non-decreasing in the modulus of its argument, we have
Σ
cosh [(N 1) m
P|M = m)
(D.13)
log(N)) -
SVN
s cosh [t(N 11) IPM > log(AV)
(D.14)
( 1
< 2 cosh [t(N 11) exp
log (o)(N)22
(D.15)
< 2exp I(N INN - 1
- Nog(N)as
1
(D.16)
where the second line we have applied Hoeffding's 's inequality to bound P(M > log(N) from above, and in the third line we have used the bound cosh(=) S exp(2) for any > 0.
We now consider the sum over [m] S S Using the bound cosh(=) S exp(22/2) we have
Σ
cosh [E(N 1)d/3 m d
P[M = m] S
Σ
exp
P( - m 2d
P = m].
2
[l)
NY
(D.17)
Using the series expansion of the exponential, we have
Σ
exp
f - 1) 2d
PIM = ml
(D.18)
2
[m|] N
(P(N 1)dmmay) 2dyt
=
Σ
+
2
(2 - -1)4m 2d
2
IP[M = m]
(D.19)
(N)
1 12(N - 1
P(|M log(N)))
m 2dp(M ml
2
|m
(t - -1)4m 2dgh
P[M- m]
(D.20)
2/k!
Im (V)
2=2
S15

---

where on the third line we have used the linearity of summation. We will now bound each of the three contributions. The first term trivially bounded from above by 1:
P||M| - log(N)) =
(D.21)
To handle the second, we first observe that
m 2d PdM = m] S 1m
(D.22)
m [No
Then, we observe that as m is the normalized sum of N 1 Rademacher random variables, its moments tend to those of a standard normal from below as N - oo, and are for any N strictly bounded from above by those of the standard normal. Therefore, we have
Blm²1| < (2d - 1)!!
(D.23)
To handle the third term, we first use the fact that for any |mm] & log( ( we have m2d < log( N 2)d which gives
(t
mdyz
PPM = m]
2
Im| (lo)
2=
(P 1)dt log 20dg
Σ |m| (lug(N)
PIM = m]
(D.24)
24
2==2
(L [oglo (2)
PP[M & (o)
(D.25)
2*
R=2
(N - 1)
(D.26)
2*
k=2
At this point, [31] uses the bound
(P - 1)dd 289d
1 ())2))((( -1)d ())(())2dd
2)(((N
(D.27)
24h!
which holds provided that choose the arbitrary parameter / such that
(( - 1)a log(NV)28d 2.
(D.28)
Assuming that condition is satisfied, we can then combine these results to obtain
Σ cosh [(N - 1) P(M = m]
(D.29)
[m| (logso
< + } (N 1)) - 1)!l + 7 (e- - ()( - 1)dd (N) log(
(D.30)
1
< PNNN 1)d - 1)!!
(f2(N 1)d log( log(NN)28d)
(D.31)
4
< exp
PNN ()d 1)11 1 (P(N 1)at (og(A))23d) 2
(D.32)
where on the the second line we have used the fact that - 2 = 0.718 < 1 and on the third line we have used the bound 1 + I exp(x: for x 2
Combining this result with the bound on the tail sum obtained previously, we have that
E cosh
Σ 5
< exp
[
1 P 1)d 11)!! + (P 1)a 22dd
+ 2exp
I(N - 11d
2 log( 22228
(D.33)
S16

---

for any 8 > 1/2 and
2
0 0615
(D.34)
(N - (N)1gllogl (N)
Therefore, we have
P(TDN(E') + e (
- ( - 1)4 1)!! - -1)a -1 log(())))
exp
2
P-1
+ 2exp (e(N - 1)d
2 (o)()))
(D.35)
subject to these conditions on 3 and
We now want to determine the single-transine and full-sequence capacities. To do so, we fix a > 0, and let /a log N). As is arbitrary, fix 7 0, and let P/P. For our choice of P. this gives
(N 1)d log 7222 (N -N--NV1 1)d N2d
log (
(D.36)
which is clearly less than 2 for N sufficiently large. Therefore, we can apply the bound obtained above, which for this choice of simplifies to
P(TDN(E") )1 + E
$ E 1(N-1"
exp
1 2 2 1)!!
log(g N22
+ 7 a N2d
1 (og( 1)
[ 1 o(1)
[+)
2
Nd
P-1
+ 2exp
[
1
log( 2)2281 (2)
log((N))
+ +(]]]]]
(D.37)
2
We can see that the first term in the curly braces tends to I with increasing N as its exponent tends to zero-wwii the second term tends to zero as the term in the round brackets within the exponent is negative for sufficiently large provided that B 1/2. We may therefore neglect the second term, which gives the simplification
N-as
(2- 1)!! log(ND) [1 o(1)].
(' + + S exp -an
(D.38)
To determine the single -tanssittnniiion capacity under the union bound, we want NF(TDN(EE), * + to
tend to zero. We have
NP )1 + E S exp - on 1-2
(111 1)!!)
log(N)) [1+
o(1)). [1+
(D.39)
For this bound tend to zero, we should have
1 a- [ 1 72d 1)!!
< 0.
(D.40)
As is arbitrary, we may 7 1/(2d 1)!!, hence the required condition is clearly satisfied if
2(2d 1)!!,
(D.41)
predicted by the Gaussian approximation. Next, determine the sequence capacity, want NPP(TDN(E + {d] to tend to zero. We have
exp -0ry (1- 1)11) log(N)) } [1 + o(1). [
NPPPTDN(EE) * tdl <
log N
(D.42)
hence an identical line of reasoning to that used for the single-transition capacity shows that we must have
2(d + 1)(2d 1)!!.
(D.43)
Again, this agrees with the Gaussian theory.
$17

---

E
Generalized pseudoinverse rule capacity
Here, we show that the generalized pseudoinverse rule can perfectly recall any sequence of linearly- independent patterns. We recall from (11) that the GPI update rule is
F Σ
]
(S): sgn
Σ
Soottum m)
(E.1)
for
0ur
(E.2)
N
the Gram matrix of the patterns. If the patterns are linearly independent, then O full rank, and the Under this assumption, have
pseudoinverse reduces the ordinary inverse: 0 = 0
TGPr(E"), sgn Σ c f(8un)
(E.3)
sgn f(1) + f(0) Σ tr
(E.4)
for all μ and i, hence separation functions satisfying f(1) > and [f(0)) < f(1)(P-1) 1) we are guaranteed to have TGPr(E"); = ch+1 as desired. For f(xx = æ4, this condition is always satisfied as (0) = and f(1) = 1. For f(x) = e ()) we have f(0) = -NN-1 and f(1) = 1: the condition P - e must therefore be satisfied. However, P s N is required for linear independence, this condition is satisfied so long as N > 3.
F MixedNet Capacity
In this Appendix, we compute the capacity of the mixed network, which from the update rule defined in (14) has
N N
1
1-1E$$ $5 }} (F.I)
N
(M) sgn
ft
-
Σ
5 + SA
+
N - N
j=2
Then, assuming that fs(1) = fa(1) = 1 as is true for the interaction functions considered here, we have
P[TMN(E * E
(F22
=P
Σ fs
Σ
E u+1
fA
Σ
<0>
(F33
N
1=
j=2
= IP <-}}
(F.4)
where we have defined the crosstalk
- c cd Σ Je
N N Σ
+
Eett SA
1
Σ 5/
(F.5)
N
For j = 2, 2,..., .N. and = 2,.... P, we have the equality in distribution CJ d et hence
d
c +
Σ fs
Σ
StS fA("").
(F.6)
p=2
n=2
S18

---

where to lighten our notation we define
Σ Sj -=2
(F.7)
N
However, unlike in the DenseNet, we cannot similarly simplify the terms outside the separation functions. Recalling that we have assumed periodic boundary conditions, have
P-1
C Sist A + Is(E + Σ (s + Σ
5 Sa(
(F.8)
1=3
+ + C C4.
(F.9)
where we have defined
C =
(F.10)
C2 (E \(
(F.11)
P-1 C3 Σ fs(")))), and
(F.12)
#=3
C4 Σ f fa( a=3
(F.13)
Importantly, in this case the influence of El on the crosstalk is O(1), and the distribution is not -pplxxipro by single Gaussian. Instead, shown in Figure F.I, is bimodal. We will therefore approximate it by a mixture of two Gaussians, one for each value of Ej. This approximation be justified by noting that the boundary terms in C and C2 should be negligible at large N and P, while Ca and C4 should give Gaussian contribution at sufficiently large P. We now observe that, for any is and fA. the conditional means of each term
B[G | (E)
(F.14)
B[C2 [ ElAA
(F.15)
E[C₁ [ 0
(F.16)
B[C, | = O,
(F.17)
where we note that all E"s are identically distributed, so we can simply write E for any one of them.
Then, the conditional mean of the crosstalk is
E|C| c + Σ EIC, |()
(F.18)
= {1 +B)
(F.19)
Considering the variance of C, the variances of the different contributions are
var [Ci [|] = varl + X
(F:20)
var
(ar[C2 = EIf varl
(F.21)
var
var(C's [C) = -P -))
(F.22)
var var[C' [C+ = x² - (B)),
(F.23)
while the covariances are
cov|Ci, C2 El] =
(F.24)
cov|Ci, Cs <l] {
(F.25)
cov(C1, C4 | O,
(F.26)
S19

---

MixedNet Crosstalk
Theory Sym
Sim Sym
1.50
Theory Asym
Sim Asym
Theory Mixed
Sim Mixed
1.25
Density
1.00
0.75
0.50
0.25
0.00
-2
-1
1
2
Crosstalk
Figure F.1: Crosstalk of Polynomial MixedNet where 100, À = 2.3, ds dx and P = 1000 patterns stored. Histograms generated for patterns drawn from 5000 randomly sequences and theoretical curves are plotted. Green represents the full crosstalk for the MixedNet. Blue and red represent the asymmetric and symmetric terms of the crosstalk, respectively. Observe that the bimodality in the full model comes from bimodality in the symmetric term.
cov(C2, C3 | =
(F:27)
cov|C2, C. [ (ELL
(F.28)
and
cov|Cs, Ca Cal = Σ
(F.29)
3,0=3
P
=
> Elfs
(F:30)
#=
X(P 33
(F.31)
Therefore, the conditional variance of the crosstalk
varlC; + +
(F.32)
(P +=
(F.33)
(P -
-
(F.34)
For large P and N, the two terms on the second line of this result will be subleading, as they do not scale with P and have identical or subleading scaling with N to the terms that do scale with P. That is, we have
var var [C1[]] P(E 21 + (E)").
(F.35)
S20

---

Collecting these results, we have
= +1+ +Bs((E))
(F.36)
and
~ -
(F:37)
By the law of total probability, we have
P[TMN(5") + < = P(C < -1
(F.88)
PIC < -11 --1
1
PIC < -21 =11
(F.39)
2
(A+E|C|< -1 var = 22"
H
(F.40)
vvar =
under the bimodal Gaussian approximation to the crosstalk distribution. To have P( # Lt) both of these conditional probabilities must tend to zero. By basic concentration arguments, we expect to have
E|C| [ ~ El
(F.4)
up to corrections that are small in an absolute sense. Moreover, have
E|C = +1] - EEC = -I = 2 + {E[f
(F.42)
which for the separation functions considered here is strictly positive. As we keep À constant with N and P, we must have
B = --1>>
(F.43)
and var[C = - in order to have P(TMN(EE)) + E?I + But, given the formula above, var C'I 5 -1] var[C| +1], this implies that the El = +1 contribution to the probability will exponentially suppressed. hen, we can apply an identical argument to that which
we used for the DenseNet in Appendix C to obtain the asymptotic behavior of P < - 11)
yielding
A E
PlTTMN(E")
H
(F.4)
var C 1
var C' [
(A [[C = -1))
2/27 X C [
exp
var[C' -1]
(F.45
For this work, we must clearly have 1.
We could in principle compute the excess kurtosis of the crosstalk for the MixedNet as we did for the DenseNet, but we will not do so here as the computation would be tedious and would not yield substantial new insight beyond that for the DenseNet.
F.1 Polynomial MixedNet
We first consider the polynomial mixed network, with fs(x) as and fa(x) = Ad for two possibly differing degrees ds, d E N We can apply the same reasoning as in Appendix C. to obtain the required moments at large N, which yields the first moments
0
ds odd,
([)s EE
(ds 1)!! Nd
(F46)
1+0
dg even
and
d odd,
E[fa(E)] = B[ = (dA - 1)!!
1+0 1 ]
(F:47)
d even,
Nda/2
S21

---

and the second moments
(2dg 1)!! Nd
1+0 (
B[ʃs(E)²) R[=2ds]
(F.48
N
and
(2d 1)!!
N ]
1
= [
1 + +
(F.49)
Nd
Then, the conditional mean of the crosstalk is given by
E| [ ~
(F.50)
up to corrections which vanish in an absolute, not relative, sense, while the conditional variance is asymptotic
var[C|et] P (2dg 1)!! Nds 22 (ds (dA 1)!!
Nids+da)/2 i[ds, da even) X2 (2d 1)!!
Nda
(F.51)
We must now determine the storage capacity. We recall that, in all case, we want P to tend to infinity slowly enough that | tends to zero. Then, we can see that what matters is which of the terms inside the curly brackets in the expression for the conditional variance above tends to zero with N the slowest. This of course determined by min min(ds, d ). but the constant factor multiplying the leading term will depend on which is smaller, or if they are equal. First, consider the case in which ds = dA = Then, we have
P var[C|s] NJ (2d 1)!! 2A(d 1)!! (d (d even] + (2d - 1)!!
(F.52)
Now, consider the case in which ds < dA. Then, (ds + daa/2 ds, hence the N-ds term dominates and we have
var car[CIsl
Nds (2dg 1)!!.
(F.53)
Similarly, if dA > ds. the N-da term dominates, and we have
P
var(C <il
x
(2d 1)!!.
(F.54)
Nda
We can summarize these results
P
varlC Ads.da Aminn
(F:55)
where
(2ds - 1)!!
ds < dA dg = d if dg > d
Ad
(22 + 1)ds - + - 1)! even]
(F.56)
A?(2dA - 1)!!
Using the general arguments presented above, we then have
(A 1)2 Nminnds exp (A- 1)2 Nmin (F.57)
Yds Ads.da P
P[TMN(() #
571
2 क
2 Ids.da P
for any A >
We must first determine the single-transition capacity, which requires that
( #
2 - 0. Recalling that our argument requires us to take P - oo slowly
enough that var C
0, we make the Ansatz that
P (A 1)2 Nmin(da.da) a'id..da
(F.58)
log N
S22

---

for some a. This yields
MN (Et) + Eñl 2/ log
N1
(F.59)
which tends to zero if a 2 yielding predicted capacity of
() (A-1) (minnds;da))
Pr
(F.60)
2dds.da log
We now consider the sequence capacity, which requires that PPP (5")1 + Efl - Then, making the same Ansatz for P above, we have
N MP + f
2V2T Ids.da (a log N)3/2 N (4t__)
(A-
(F.61)
which tends to zero provided that a 2 2(min(dg, da) 1), yielding a predicted capacity of Nwin(dg.da)
12-1)
Ps 2 (mmin(ss,) dA} + 1dds,da
(F.62)
log N
F.2 Exponential MixedNet
We now consider the Exponential MixedNet, with fs(Ø) = fA(x) e(N-1)(e-1), have the first moments
With this, we
N
BiJs(=)) = E[) expl- 1)
exp
Σ
E
(F.63)
j=2
= e - 1)1
[(ex
(F.64)
(cosh(1)) exp(1)
(F.65)
and the second moments
cosh(2)
N-1
=
(F.66)
exp(2)
BN-I'
where as in Appendix C.2 we let
exp(2)
B cosh(2) 1.96403.
(F.67)
Noting that
exp(1)
~ 1.76159,
(F.68)
cosh(1)
the conditional mean of the crosstalk is then
[ El [1 (f a +
(F.69)
cosh(1)
N-1
cooh((1)
N-1
= c] A
(F:70)
exp(1)
cxp(1)
5
(F.71)
where the corrections are exponentially small in absolute sense. The leading part of the conditional variance of the crosstalk is var (C
|C [
(E) + (EEIL)()) + (E)()(
(F.72)
P
cosh(1)2)
N-1
1+22
2
(F.73)
BN-I
cosh(2)
P
(1))
(F.74)
-N
S23

---

where we note that
cosh(1)² cosh(2)
0.632901
(F.75)
hence the other contribution exponentially suppressed in relative sense.
We thus have
[ ~ E
(F.76)
var [ill 3N-1 (1 +2),
(F.77)
hence from the general argument above we have
1
V(++)) P BN-1 exp
1(A 1)3 3N-1 (11 1+ X2 P
-1
P[TMN(E*) +91
(F.78)
2T A-1
V
for À > 1. We now want to determine the capacity, starting with the single-transition capacity, for which we must have NP[TMNN (5")) * Eी + 0. Recalling that we want to have var[C] | - 0, we make the Ansatz
Pv (A - 1)² 3N-1 X2 +1 log
(F.79)
for some a, which yields
NF(TMN(E # E9 2 log N
N al-a/2
(F.80)
This tends to zero if a 2 2, hence we conclude that the Gaussian theory predicts
1 1 1)² NN-1
Pr
(F.81)
2 X2 + log N
We now want to determine the sequence capacity, which requires that NNP((MN((') # + - 0. Following analysis of the Exponential DenseNet in Appendix C.2, make the Ansatz that
1 1 1)²
NN
P~ a
(F.82)
x
N
which yields
1 (A 1)a 2 2/2TaN a3
NPP(TMN(E") +
X2 +1 exp (1og N).
(F.83)
This tends to zero if a 2 2 log 3, giving predicted sequence capacity of
1 (A 1)2 3N Ps 2 log 3 x2 +
(F.84)
N
Thus, for both definitions of capacity, the Gaussian theory's prediction of the capacity of the Expo- nential MixedNet is
(A-17 1)2
(F.85)
x +1
times the capacity of the Exponential Denseleet analyzed in Appendix C.2. This factor tends to zero from above as À J. 1, and gradually increases to as À - oc. Note that even without explicitly computing the excess kurtosis, we expect the intuition from the Exponential DenseNet carry over to this setting. Indeed, the numerical simulations in Figure F.2 show that the transition capacity is well captured by the Gaussian theory while the sequence capacity shows significant deviation for small MixedNets.
S24

---

Simuratoon Det.
Simu adorr: EVIN
Transition Capacity (logha
Sequence Capacity (log1o(P3)
10
15
25
10
15 Number of Neurons (N)
20
25
Number of Neurons (N)
Figure F.2: The capacities of Exponential MixedNets with À 2.5 are plotted of network size. (A) Transition capacity for the Exponential Mi XidNNet which closely matches theoretical prediction. The predicted capacity is shown by the solid line with dots, while square error bars show the results of numerical experiment. (B) Sequence capacity for the Exponential MixedNet, which diverges from theoretical prediction.
function
G Numerical implementation
Source code is available GitHub at https://githi: att /roupp Experiments were run on the Harvard University FAS RC Cannon HPC cluster fettps://wwi .c. fas harvard. GPUs. This limited the maximum number patterns we could store memory simultaneously to approximately 10 patterns, restricting our experimental evaluation of the Exponential DenseNet approximately N 25 neurons.
using Nvidia A100 80GB
G.1 Transition eapacity
Numerical simulations for transition capacity were conducted follows: For given model of size N, start by initializing 100 sequences Rademacher distributed patterns of length Po. where Po 2P" is well above the model's predicted capacity P* This initialization for Po found through trial and error, where the method detects if you start below capacity. The model's update rule applied in parallel across all patterns and across all sequences. If errors made for any pattern in any sequence, 100 new random sequences are generated with smaller length P1 = 0.99 This is repeated, with the new sequence length being Pt+1 0.99P,, until 100 sequences generated for which no error is made in any transition. This entire process is repeated 20 times starting from Po in order obtain bars.
G.2 Sequence capacity
Numerical simulations for sequence capacity were conducted a similar fashion. For a given model of size N, start by initializing 100 sequences of Rademacher distributed patterns of length Po. where Po is well above the model's capacity. Starting from the first pattern of each sequence, the model's update rule is applied serially for each sequence. As soon 100 new random sequences are generated with smaller length P1 = 0.99P.. This is repeated, with the sequence length being P 0.99P,. until 100 sequences generated for which no made. This entire process is repeated 20 times starting from Po in order to obtain error bars.
error is obtained within any sequence,
G.3 MovIngMNIST
For the MoVIT experiments in Section 2.4, the images were pre- processed to have binarized pixel values. There were 10000 subsequences, each containing handwritten digits from the MNIST dataset moving through each other across 20 images, that were concatenated to construct the entire sequence of 200000 images [78]. Then, different models were run from initialization and their output for different time steps was displayed in Figure 3.
$25

---

G.4 Generalized pseudoinverse rule
For numerical simulations of the generalized pseudoinverse rule in 2.5, the transition capacity of the Polynomial DenseNet was simulated in similar method as described above. However, the Exponential DenseNet suffered from numerical instability when calculating the pseudoinverse of the overlap matrix, resulting in floating point emor. Therefore, we showed results only for the Polynomial DenseNet.
S26


Reviews:
[{"review_id": "mzULFIvl4P", "reviewer": "Reviewer_mTmK", "summary": "This paper focuses on computational memory that stores sequence data. Existing work that considers Hopfield-like neural networks suffer from limited sequence capacity due to the crosstalk issue. To this end, this paper introduces a nonlinear interaction term inspired by Dense Associative Memories, enhancing pattern separation. The authors develop novel scaling laws for sequence capacity relative to network size, outperforming traditional Hopfield-based models. The authors also propose a generalized pseudoinverse rule for recalling sequences with highly correlated patterns. Additionally, this paper presents a biologically plausible implementation with connections to motor neuroscience to store sequences with variable timing. ", "questions": "1. Comparison with PCN-based approaches.\n\n2. Is there any guarantee or analysis of the convergence?\n\n3. Scalability of the proposed method.\n\n4. Performance on real-world large-scale datasets/settings.\n\nMy final score will largely depend on the rebuttal and discussion with the other reviewers. ", "limitations": "No negative societal impact was found in this paper. I have put my concerns in the \"Weaknesses\" section.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Designing computational memory for sequence data is interesting and novel.\n\n2. The paper is well-written and easy to follow.\n\n3. The technical part of this paper seems sound to me.\n\n4. Theoretical analyses such as memory capacity round up good work.\n", "weaknesses": "1. Besides Hopfield-like associative memory (AM), there is another class of AM namely predictive coding network (PCN)-based memory. Some recent works including [1,2,3] have shown superior performance of PCN-based approaches compared with Hopfield-like baselines. Seems [3] also considers associative memories for storing and retrieving sequential manner input. I am interested in both theoretical and empirical comparisons between the proposed method and the PCN-like methods.\n\n2. Hopfield network is susceptible to convergence to local minima during the pattern retrieval process. Local minima are stable states that are not the desired patterns. Just wondering, if there are any theoretical guarantees/analyses of convergence of the proposed method.\n\n3. Scaling up Hopfield networks to handle large-scale problems can be challenging. As the number of neurons increases, the computational and memory requirements grow rapidly. Is there any remedy for the efficiency concern, and what is the scalability of the proposed method?\n\n4. Can the authors comment on the utility/challenges in applying their proposed method to real-world datasets/tasks beyond the MNIST datasets used in their experiments? e.g., using them in large-scale language modeling tasks where transformers are now popular.\n\n[1] Salvatori, Tommaso, et al. \"Associative memories via predictive coding.\" Advances in Neural Information Processing Systems 34 (2021): 3874-3886.\n\n[2] Yoo, Jinsoo, and Frank Wood. \"BayesPCN: A Continually Learnable Predictive Coding Associative Memory.\" Advances in Neural Information Processing Systems 35 (2022): 29903-29914.\n\n[3] Tang, Mufeng, Helen Barron, and Rafal Bogacz. \"Sequential Memory with Temporal Predictive Coding.\" arXiv preprint arXiv:2305.11982 (2023).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and suggestions. We have gone through the weaknesses and addressed them point by point. We are happy to go into more detail for any of these responses.\n\n> Besides Hopfield-like associative memory (AM), there is another class of AM namely predictive coding network (PCN)-based memory. Some recent works including [1,2,3] have shown superior performance of PCN-based approaches compared with Hopfield-like baselines. Seems [3] also considers associative memories for storing and retrieving sequential manner input. I am interested in both theoretical and empirical comparisons between the proposed method and the PCN-like methods.\n\nWe have seen the work on the Predictive Coding Network as an alternative mechanism of for associative memory, and found that it to be very interesting. [3] does indeed consider a similar model and is contemporarenous with our submission, as it was posted to the arXiv on May 19, two days after the NeurIPS paper submission deadline. However, given its relationship to our model, we are ready to cite it in the camera-ready work. Our paper is primarily focused on extending Modern Hopfield Networks, deriving theoretical bounds on capacity and verifying them with numerical simulation. [3] introduces a related model, and even mentions that temporal predictive coding can be viewed as a \"classical Asymmetric Hopfield Network (AHN) with an implicit statistical whitening process, which leads to more stable performance in sequential memory tasks of structured inputs.\" We would be interested in exploring theoretical comparisons between the proposed models and the PCN in future work. [1] provides a brief comparison for the symmetric setting, which we anticipate will extend to the sequence setting as well: \n\n- \"\\[Modern Hopfield Networks\\] are able to exactly retrieve data points, while \\[the Predictive Coding Network\\] always presents a tiny amount of error, even if not visible by the human eye. However, the retrieval process of our model is significantly better, as it always converges to a plausible solution, even when provided with a tiny amount of information, or a large amount of corruption. For example, our model never converges to wrong data points: when tested on complex tasks, it simply outputs fuzzier memories, instead of perfect but wrong reconstructions, as the MHNs.\"\n\n> Hopfield network is susceptible to convergence to local minima during the pattern retrieval process. Local minima are stable states that are not the desired patterns. Just wondering, if there are any theoretical guarantees/analyses of convergence of the proposed method.\n\nThe Hopfield network will converge to these local minima, which we refer to in the paper as \"metastable states,\" if there is too much crosstalk when computing the update. This crosstalk is diminished by adding the nonlinear interaction term, and increasing the nonlinearity generally increases the probability of appropriate recall. The theoretical calculations done in the appendix focus around bounding this crosstalk. There is also previous work (Krotov, Hopfield 2016; Ramsauer et al. 2020; Demircigil et al. 2017) in symmetric modern Hopfield Network which provide theoretical guarantees of convergence, and these calculations will likely carry over to the asymmetric case, at least for the polynomial DenseNet.\n\n> Scaling up Hopfield networks to handle large-scale problems can be challenging. As the number of neurons increases, the computational and memory requirements grow rapidly. Is there any remedy for the efficiency concern, and what is the scalability of the proposed method?\n\nThe proposed method massively increases the capacity and computational efficiency of the Hopfield Network without increasing the network size. This is easily implemented since it simply requires applying a polynomial or exponential nonlinearity. However, Hopfield Networks along with any other associative memory method suffer from the fact that in order to retrieve patterns, then those patterns have to be stored somewhere. In the case of the DenseNet, there are no weights that would need to be stored, only the patterns. Furthermore, the distinguishing factor of the DenseNet is its ability to provide error-correction capabilities for robust recall of extremely long sequences, and can be easily implemented for real-time control applications.\n\n> Can the authors comment on the utility/challenges in applying their proposed method to real-world datasets/tasks beyond the MNIST datasets used in their experiments? e.g., using them in large-scale language modeling tasks where transformers are now popular.\n\nIn the global rebuttal, we include simulations on the Moving MNIST dataset. The model currently proposed and analyzed has been formulated for discrete-valued patterns, but can be extended to store continuous-valued patterns as required for the transformer architecture. We believe that the model holds potential which we will investigate this in future work, but the focus of the current paper is to introduce the model, derive theoretical capacity limits, and verify it with empirical simulations. In particular, there has been an interest in utilizing state space models as an alternative to transformers for long sequence modeling, which we are exploring for potential connections.\n- Albert Gu, Karan Goel, Christopher Ré 2022\n- Poli et al. 2023\n- Orvieto et al. 2023 "}, {"review_id": "XFqKRSeNQG", "reviewer": "Reviewer_Yq1L", "summary": "This is well presented paper one the storage of sequence memories in Hopfield-like networks. It builds on the recent modern Hopfield networks, but now with asymmetric weights connecting adjacent memories within a sequence. Theoretical capacity limits are calculated and then compared to simulations. Adaptations to improve correlated inputs are proposed using a pseudoinverse rule.", "questions": "Relating to the weaknesses above:\nWhat happens when two patterns are identical in different sequences?\nWhat about when the sequence is drawn from a distribution?\n", "limitations": "I think the main limitations are that this paper is a small advancement from existing modern Hopfield nets., and it’s not clear that the proposed update is a general solution. It is also not clear what the asymmetric weights offers more than other sequence memory models – being that the main point of this paper is that the proposed models is a good model, it really does need some comparisons to existing models. I’m really not saying this proposal is bad - I like it, the presentation is v good, and the theory/simulations concordance is great - it’s just not clear where it stands in the overall landscape, so it’s hard to draw any conclusions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Well presented paper. Easy to read. Technically solid.", "weaknesses": "1)\tThis is a small update paper to the recent spate of modern Hopfield network papers (Krotov&Hopfield 2020, Ramsauer et al 2019, etc.,). The proposed method of sequence memory only works when no elements of the sequence are repeated (big limitation), and for unstructured sequences (i.e. it would have no idea if the sequence was drawn from an underlying distributions). \n\n2)\tThere are also papers that use modern Hopfield networks for sequence memories (e.g. Whittington et al 2022) that don’t have these limitations as they essentially control the sequence retrieval via an external controller. There should be some sort of comparison to existing sequence memory models.\n\n3)\tThe connection to motor skills is difficult to mesh with what we know about motor learning and episodic memory systems. Episodic memory is a hippocampal phenomenon, whereas motor skills  / learning are the classic example of procedural knowledge.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your compliments and insightful suggestions. Indeed, this is an extension of existing literature of modern Hopfield networks but we believe that it introduces a general solution for error-correction and the robust retrieval of long sequences. We were primarily focused in this work on theoretically analyzing the model and numerically verifying it via simulation. \n\n**Weaknesses:**\n> This is a small update paper to the recent spate of modern Hopfield network papers (Krotov&Hopfield 2020, Ramsauer et al 2019, etc.,). The proposed method of sequence memory only works when no elements of the sequence are repeated (big limitation), and for unstructured sequences (i.e. it would have no idea if the sequence was drawn from an underlying distributions).\n\nThe first part of this statement is correct. Thank you for clarifying it, and we will mention it explicitly in the camera-ready submission. We are actively exploring extensions of the model to store sequences with repeating elements for future work, but we restricted the scope of this paper to non-repeating elements for theoretical tractability. One route we have considered is adding additional associations across longer time steps (e.g. $\\xi^{\\mu} \\to \\xi^{\\mu+2}$). \n\n\n<!-- However, we do not anticipate this being a major problem in translating the results to represented via contextual embedding which will be  -->\n\nRegarding the second part of the statement, we assume that the sequences are drawn from a Rademacher distribution to compute theoretical capacity as is commonly done in the literature (Amit, Gutfreud, Sompolinsky 1985; McEliece et al. 1987; Krotov, Hopfield 2016). However, the model itself still works when the stored patterns come from a structured underlying distribution, as is demonstrated in the MNIST experiments and Overlapping Patterns experiments in the paper (Figures 5 and 6) and all of the Moving MNIST experiments in the global rebuttal. It simply will have a smaller capacity due to overlap between patterns, although we proposed the generalized pseudoinverse rule as a way to address this.\n\n> There are also papers that use modern Hopfield networks for sequence memories (e.g. Whittington et al 2022) that don’t have these limitations as they essentially control the sequence retrieval via an external controller. There should be some sort of comparison to existing sequence memory models.\n\nWe assume the reviewer is referring to \"Relating transformers to models and neural representations of the hippocampal formation.\" This paper was incredibly insightful in connecting the transformer architecture to the Tolman-Eichenbaum machine, and indeed should have been cited when surveying related sequence memory models. However, we believe that this model takes a different approach, in which the positional encoding for each element of the sequence is learned. We assume this is what the reviewer means by \"controlling sequence retrieval via an external controller.\" We were focused on the setting where one would can recall a sequence without access to an external controller. However, while not exactly the same, we briefly suggest an analagous approach for context-dependent gating in the context of motor sequence generation in lines 314-317: \n\n*\"In particular, the role of the basal ganglia in this network suggests a novel mechanism of context-dependent gating within Hopfield Networks. Rather than modulating synapses or feature neurons in a network, one can directly inhibit (activate) memory neurons in order to decrease (increase) the likelihood of transitioning to the associated state.\"*\n\nIf there are other connections the reviewer sees, we are open to learning about them and further discussing them.\n\n> The connection to motor skills is difficult to mesh with what we know about motor learning and episodic memory systems. Episodic memory is a hippocampal phenomenon, whereas motor skills / learning are the classic example of procedural knowledge.\n\nIndeed, we do not believe that this model is connected to episodic memory as is found in the hippocampus, but rather are interested in motor sequences that are memorized through repetitive training such as a tennis serve. We seek to point out similarities between the model and recent developments in motor action selection and control, which suggest the role of thalamocortical feedback loops in initiating and automatically preparing motor motifs:\n- Logiaco, Abbott, Escola 2021\n- Kao, Sadabadi, Hennequin 2021\n- Moll et al 2023\n\nWe acknowledge that there are differences between our model and the actual neurobiology underlying motor sequence control such as chunking. We will add a sentence to the camera-ready version to clarify this point. \n\n**Limitations:**\n> I think the main limitations are that this paper is a small advancement from existing modern Hopfield nets, and it’s not clear that the proposed update is a general solution. It is also not clear what the asymmetric weights offers more than other sequence memory models – being that the main point of this paper is that the proposed models is a good model, it really does need some comparisons to existing models. I’m really not saying this proposal is bad - I like it, the presentation is v good, and the theory/simulations concordance is great - it’s just not clear where it stands in the overall landscape, so it’s hard to draw any conclusions.\n\nWe appreciate the reviewer's comments and concerns. We present a broader survey of related models in the global rebuttal and will modify the introduction in the camera-ready version. If there are other models the reviewer believes should be included in the comparison, we would be happy to investigate them further. Finally, we simply want to reiterate that the focus of the work is the introduction and theoretical analysis of the DenseNet, which we believe provides a general solution for error correction and robust retrieval of long sequences. "}, {"review_id": "TOyCJ9XgDW", "reviewer": "Reviewer_6yTi", "summary": "This paper combines two modifications to the basic Hopfield network to create a network capable of creating and recalling long sequential memories (i.e. sequences of states of the network). The sequence capacity of the proposed network is bounded analytically, and supported by numerical simulations. This model is then extended to allow memories to be recalled a fixed number of times before transitioning to the next item in the sequence. Finally, an implementation of this network using more biologically plausible neurons is given.", "questions": "* Can you elaborate on the relationship between the models presented here and the Karuvally et al. work mentioned on line 46?\n* What kind of loss in sharpness results if you circumvent the Gaussian approximation (lines 98-105) by using McDiarmid's inequality to bound the tail instead? I believe this should also allow the capacity to be bounded for any $L$-Lipschitz nonlinearity.\n* In lines 201-213, it seems like the patterns are not actually \"correlated\", as each pattern is still i.i.d. but the distribution is no longer uniform. If so, care should be taken to distinguish this meaning from the term \"correlation\" as it is used in Section 2.4, meaning that the patterns are not i.i.d. On that note, a synthetic version of the MNIST experiment where there is a ground truth sequence, and different sequences are generated by flipping each of its bits with some small probability, would be interesting.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "* This work extends the basic Hopfield network in several important directions while retaining the original model's simplicity and (to some extent) analytic tractability.\n* The paper itself is well-written and eminently readable, and is likely to have broad appeal in related disciplines. Although it covers several ideas related to sequential Hopfield networks, the paper still feels cohesive and flows well.\n* The theory and simulations complement each other well.", "weaknesses": "* The theoretical analysis crucially relies on nonrigorously approximating a nonlinear function of i.i.d. random variables as Gaussian. The authors make a substantial attempt to provide justification for this, but this does dilute the utility of the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and suggestions, especially those on improving the rigor of the technical analysis. Since the original submissions, we have proven rigorous bounds for the Polynomial DenseNet and are working on rigorous bounds for the Exponential DenseNet, which has proven to be substantially more difficult.\n\n**Weaknesses:**\n> The theoretical analysis crucially relies on nonrigorously approximating a nonlinear function of i.i.d. random variables as Gaussian. The authors make a substantial attempt to provide justification for this, but this does dilute the utility of the theoretical analysis.\n\nThank you for this comment; as we acknowledge the analysis presented is approximate. A small clarification: the crosstalk is not simply a nonlinear function of a sum of i.i.d. random variables, but a sum of functions of i.i.d. sums of i.i.d. random variables. For the Polynomial DenseNet, we have in hand a rigorous analysis that adapts the analysis of the symmetric MHN by Demircigil et al. 2017 to bound the bitflip probability. We would be happy to add this to our manuscript if the referee believes it would be helpful. Please see also the discussion below under your question about McDiarmid's inequality. \n\n**Questions:**\n> Can you elaborate on the relationship between the models presented here and the Karuvally et al. work mentioned on line 46?\n\nKaruvally et al. 2022 takes an interesting approach toward extending Modern Hopfield Networks to store sequences. While we forego the energy function formulation altogether, they develop a way to analyze an energy function in terms of an adiabatic limit. We believe that their model, GSEMM, can most closely be described as the biologically-plausible implementation of our proposed Mixed Network. Furthermore, they analyze the model in the setting of continuous-time dynamics, allow for different timescales between the hidden and feature layers, and also allow for intralayer synapses within the hidden layer. On the other hand, our paper is focused on providing a theoretical analysis of the model and its sequence capacity, alongside introducing the generalized pseudoinverse rule to store correlated patterns. Karuvally et al. 2022, however, do not derive an analytic expression for the sequence capacity, which is the central result in our paper.\n\n> What kind of loss in sharpness results if you circumvent the Gaussian approximation (lines 98-105) by using McDiarmid's inequality to bound the tail instead? I believe this should also allow the capacity to be bounded for any Lipschitz nonlinearity.\n\nThank you for the suggestion. We have in fact previously attempted to estimate the capacity by using McDiarmid's inequality to bound the bitflip probability. For the polynomial DenseNet, the sensitivity to flipping one of the pattern elements inside the nonlinear separation function led to a bound of the form $\\mathbb{P}[C>1] \\leq [1+o(1)] \\exp[-n/(2p)]$, which only recovers the capacity of the classic SeqNet. If the reviewer has any idea for circumventing this loss of sharpness, we would greatly appreciate their feedback. As an alternative approach to rigorously controlling the bitflip probability for the polynomial DenseNet, we believe that the argument used by Demircigil et al. (2017) to prove their theorem on symmetric networks can be adapted step-by-step to prove the Gaussian prediction. We would be happy to include this argument if the reviewer thinks it would enhance our paper. For the exponential DenseNet, the situation is more substantially more difficult due to the tail decaying more slowly,, and we are investigating alternative derivations.\n\n> In lines 201-213, it seems like the patterns are not actually \"correlated\", as each pattern is still i.i.d. but the distribution is no longer uniform. If so, care should be taken to distinguish this meaning from the term \"correlation\" as it is used in Section 2.4, meaning that the patterns are not i.i.d. \n\nThank you for mentioning this, as the imprecise wording here is a historical artifact. Within the Hopfield Network literature, the term \"correlated patterns\" is often used to refer to \"overlapping patterns\". As it is the overlap between patterns which increases crosstalk, increasing the overlap will reduce the signal-to-noise ratio when computing sequence transitions. In other words, we are concerned with the raw second moment of the distribution of patterns rather than the centered second moment of the distribution. One can increase the overlap by increasing the bias or by increasing the correlation between the patterns. \n\n> On that note, a synthetic version of the MNIST experiment where there is a ground truth sequence, and different sequences are generated by flipping each of its bits with some small probability, would be interesting. \n\nThis is a great suggestion. We assume the intent is to introduce a higher degree of correlation into the network. Due to limited space for figures, we were not able to display this exact experiment but believe that Figures 1 and 2 of the Moving MNIST dataset showcase the model's ability to handle pattern overlap and Figure 3 shows the model's robustness to noise/corruption."}, {"review_id": "jIEuEWy14S", "reviewer": "Reviewer_2PbW", "summary": "This paper proposes to introduce nonlinear interaction terms in the Amari-Hopfield type recurrent networks for learning long binary sequences. Analytical results on the network capacity and a new learning algorithm are provided.", "questions": "Overall, I appreciate the theoretical part of this paper, which is valuable to the community per se. However, I found it is not consistent with the problem addressed in the beginning of this paper, learning long and correlated pattern sequences. The experiments do not convince me that correlated pattern sequences can be handled by the proposed method either.\n\nHowever, I would like to raise my rating by 1-2 points, if the authors can in the rebuttal or revised paper\n1) evaluate their method on the Moving MNIST dataset, in which the successive patterns are highly correlated.\nhttps://www.cs.toronto.edu/~nitish/unsupervised_video/\n\n2) evaluate their method for the robustness of sequence retrieval under noise.\n\nMoreover, if the authors can additionally provide some theoretical justification on storing correlated sequence patterns (a shortcoming which I have pointed out in the review), plus all my concerns are well-addressed, I could raise the rating by 3-4 points.\n\n\n### Rebuttal\nI have read the rebuttal and believe the authors have addressed my points. I therefore raise my rating to \"6. Weakly Accept\".\n\n", "limitations": "Yes, the limitation of the analytic calculation is mentioned in Line 353-358.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The analytic calculation of the network capacity on random sequences in Section 2 is a very interesting theoretical result, extending previous work on the capacity of storing static patterns in the networks. The simulation results match the theoretical calculation, which is excellent.\n2. The paper is well-written and easy to follow.\n3. Code is provided for the reproduction of the experiments.", "weaknesses": "1. It is technically incorrect to state that \"a major limitation of the Hopfield Network and related associative memory models is its capacity\". In [1], it has been shown Hopfield model can store sequences of maximal length 2^N. The short length of sequences is largely due to the temporal asymmetric Hebbian learning algorithm, rather than the model.\n\n2. There is a vast of papers [2,3,4,5] on overcoming the limitation of storing correlated in Hopfield model by the Hebbian algorithm, which are not mentioned this paper. The ideas can be extended to store sequences. The authors should do a literature review on them and compare the pros and cons with their approach in solving the problem.\n\n3. The theory is conducted on random sequences, rather than the correlated pattern sequences which should be addressed. In the experiments in Section 2.4, the MNIST digits images in a sequence are in essentially random orders. Therefore the correlation of patterns is not strong enough to validate the propose method.\n\n4. Robustness of sequence retrieval is missing in the paper. A major feature of Hopfield model is its robustness of recovering static patterns under noise. Can the proposed method recover the rest of a sequence, given a perturbed pattern? An evaluation is needed.\n\n5. In Line 65-68, the $\\xi$ should be bold-faced. In Line 95, $\\xi_2^1$ should be $\\xi_1^2$.\n\n[1] Exponentially Long Orbits in Hopfield Neural Networks, Muscinelli, Gerstner, Brea. Neural Computation, 2017.   \n[2] Learning of correlated patterns in spin-glass networks by local learning rules. Diederich, Opper. PRL, 1987.  \n[3] The space of interactions in neural network models. Gardner. Journal of Physics A, 1988.  \n[4] Perceptron-like learning in time-summating neural networks. Bressloff, Taylor. Journal of Physics A, 1999.  \n[5] Dynamics of Memory Representations in Networks with Novelty-Facilitated Synaptic Plasticity. Blumenfeld, Preminger, Sagi, Tsodyks. Neuron, 2006.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the clear criticism and insightful comments, especially the suggestion to use the Moving MNIST dataset and include simulations demonstrating robust sequence retrieval, which we have included the global rebuttal. We have also sketched an outline for the capacity of biased patterns.\n\n**Weaknesses:**\n> It is technically incorrect to state that \"a major limitation of the Hopfield Network and related associative memory models is its capacity\". In [1], it has been shown Hopfield model can store sequences of maximal length 2^N. The short length of sequences is largely due to the temporal asymmetric Hebbian learning algorithm, rather than the model.\n\nThank you for this comment. By Hopfield Network, we specifically refer to a network with a Hebbian-like learning rule, and will clarify this in the camera-ready version. The paper mentioned in [1] describes an algorithm such that given a network of size $N$, one can construct a sequence of $2^N$ patterns and a specific update rule to recall these patterns. However, it will not work for arbitrary sequences and does not have error correction capabilities, which is a core feature of our model. We will be more precise in the camera-ready version.\n\n> There is a vast of papers [2,3,4,5] on overcoming the limitation of storing correlated in Hopfield model by the Hebbian algorithm, which are not mentioned this paper. The ideas can be extended to store sequences. The authors should do a literature review on them and compare the pros and cons with their approach in solving the problem.\n\nThis is a fair point. We tried to do a brief survey in the introduction of the paper, but the literature on associative memory is vast and some papers were accidentally omitted. We have included a brief comparison to other methods in the global rebuttal and will include a deeper one in the camera-ready version, alongside citing these papers. If you believe any other models are relevant, we would be grateful.\n\n> The theory is conducted on random sequences, rather than the correlated pattern sequences which should be addressed. In the experiments in Section 2.4, the MNIST digits images in a sequence are in essentially random orders. Therefore the correlation of patterns is not strong enough to validate the propose method.\n\nThank you for this suggestion. We ran simulations on the Moving MNIST dataset which has higher overlap between patterns and included the results in the global rebuttal.\n\n> Robustness of sequence retrieval is missing in the paper. A major feature of Hopfield model is its robustness of recovering static patterns under noise. Can the proposed method recover the rest of a sequence, given a perturbed pattern? An evaluation is needed.\n\nThis is great suggestion, and we have ran simulations which we've further discussed in the global rebuttal. In Figure 3, we add noise to each transition in the sequence which would be even more difficult than only perturbing the first pattern.\n\n> In Line 65-68, the $\\xi$ should be bold-faced. In Line 95, $\\xi_2^1$ should be $\\xi_1^2$.\n\nThank you for pointing that out; we have fixed these typos.\n\n**Questions:**\n> Overall, I appreciate the theoretical part of this paper, which is valuable to the community per se. However, I found it is not consistent with the problem addressed in the beginning of this paper, learning long and correlated pattern sequences. The experiments do not convince me that correlated pattern sequences can be handled by the proposed method either. However, I would like to raise my rating by 1-2 points, if the authors can in the rebuttal or revised paper:\n    1. evaluate their method on the Moving MNIST dataset, in which the successive patterns are highly correlated. https://www.cs.toronto.edu/~nitish/unsupervised_video/\n    2. evaluate their method for the robustness of sequence retrieval under noise.\n\nThank you for the valuable suggestions, and we appreciate you pointing us to the Moving MNIST dataset of which we were not previously aware. We have ran both of these simulations and included them in the global rebuttal.\n\n> Moreover, if the authors can additionally provide some theoretical justification on storing correlated sequence patterns (a shortcoming which I have pointed out in the review), plus all my concerns are well-addressed, I could raise the rating by 3-4 points.\n\nThank you for this question. We agree that it would be very interesting to extend our theoretical arguments to correlated patterns. Our approximate Gaussian computations should be easily extensible to the case in which the patterns are biased (not correlated in the statistical sense, but leading to non-zero average overlap, which is the relevant notion in this context); the effect would be to shift the mean and variance of the crosstalk distributions. Concretely, consider patterns with \n$$\\mathbb{P}[\\xi_{j}^{\\mu} = \\pm 1] = \\frac{1 \\pm r}{2},$$\n such that \n$$\\mathbb{E}[\\xi_{j}^{\\mu}] = r$$\nis the bias. This setup mirrors that considered in the classic work of Gardner (JPA 1988), which has been extended to simple nonlinear networks (Zavatone-Veth & Pehlevan PRE 2021); for that unconstrained learning rule the bias does not alter the scaling of capacity with $N$. We propose to do this computation for the final version of our paper, as it should not be challenging. \n\nTo sketch the computation, we recall that our goal is to analyze the crosstalk and approximate its distribution as Gaussian.\n$$ C = \\sum_{\\mu=2}^P \\xi^{2}_{1} \\xi_1^{\\mu+1} f \\left( X^{\\mu} \\right), $$\n\nwhere \n$$ X^{\\mu} = \\frac{1}{N-1} \\sum_{j=2}^{N} \\xi_{j}^{\\mu} \\xi_{j}^{1}$$\nSince the patterns are no longer symmetrically distributed, we must now also track the non-zero mean of the crosstalk. However, the computation is still reasonably straightforward. "}]

Author rebuttal:
Thank you for the insightful comments and suggestions. We found that there were some common themes across the reviewers' comments: sequence retrieval for correlated patterns, robust recall of patterns under noise, and a comparison with other sequence recall methods. We individually respond to each reviewer's detailed comments point-by-point.

To address the problem of correlated patterns, Reviewer 2PbW suggested we test our model on the Moving MNIST dataset, which we were not previously aware of and are grateful for the suggestion. The dataset is constructed so that there are $10,000$ sequences of $20$ images, in which two handwritten digits from the MNIST datasets are slowly moving around. This leads to significant amounts of overlap between images within a sequence and should be a great test for robust recall of correlated patterns. 

In Figure 1, we demonstrate the effect of pattern overlap on sequence recall and the impact of nonlinear interaction functions on overcoming this effect. In the top row, we show a portion of the ground truth sequence of digits $0$ and $3$ moving around. Despite using a network of size $N = 64 * 64 = 4096$, the linear SeqNet is unable to successfully recall the sequence. For the Polynomial DenseNet, increasing the polynomial degree $d$ slowly increases recall until $d=15$ when there is finally perfect recall. The Exponential DenseNet perfectly recalls the pattern. 

In Figure 2, we test the limits of our model by taking all $10,000$ sequences of $20$ Moving MNIST images and concatenating them into a single sequence $200,000$ of images. Here, we display a portion of the ground truth sequence taken from the center, starting in the middle of one subsequence of $2$ and $5$ and ending in the middle of another subsequence of $7$ and $4$. The SeqNet and Polynomial DenseNet are not able to recall anything at all until $d=50$, and the Polynomial DenseNet does not perfectly recall the sequence until $d=70$. The Exponential DenseNet again perfectly recalls the entire sequence. 

To address the problem of robust recall, Reviewer 2PbW suggested we test our model by perturbing the initial pattern in the sequence and Reviewer 6yTi suggested we generate new sequences with noise in each pattern in the sequence. In Figure 3, we tried to combine both of these into a single simulation where we simulated a 20 image sequence of $4$ and $9$ and added a randomly flipped bits at each transition. Note that a bitflip probability of 0.5 corresponds to complete noise as a bitflip probability of 1.0 will simply invert the picture. In the top row, we show the input into the network where the probability of pixel being flipped at random is 0.2. The second row shows target pattern the network should transition to. The next few rows show SeqNet and the Polynomial DenseNet failing to recall the sequence until $d=20$. Finally, the last row shows a modified form of the Exponential DenseNet with a smaller base, replacing the nonlinear interaction function $f(x) = e^{(N-1)(x-1)}$ with $f(x) = b^{(N-1)(x-1)}$ where $b = 1.01$. This is because the network size $N = 64*64 = 4096$ results in extremely large negative values in the exponent therefore floating point overflow. Reducing the base preserves the desired robust recall while circumventing numerical limitations.

Finally, we provide a brief survey of related models: 
- The Predictive Coding Network (Tang, Barron, Bogacz 2023) is a contemporaneous model which the authors describe as a "classical Asymmetric Hopfield Network (AHN) with an implicit statistical whitening process, which leads to more stable performance in sequential memory tasks of structured inputs." While this model always results in some error, it generally converges to a plausible solution and avoids metastable states. On the other hand, our model provides perfect recall when it works but for insufficient nonlinearity converges to metastable states.
- Whittington et al. 2022 introduces a connection between the Transformer architecture and the Tolman-Eichenbaum machine, a model of the hippocampus, and propose the usage of an external network to learn a positional encoding via path integration. We propose a model that does not require an external network, although we briefly explore the possibility of adding an external network for context-dependent gating in the context of motor sequence control in lines 314-317. 
- Karuvally et al. 2022 extends Modern Hopfield Networks to the sequence setting by developing a way to analyze an energy function in terms of an adiabatic limit. The GSEMM is related to the biologically-plausible implementation of our Mixed Network. Furthermore, they analyze the model in the setting of continuous-time dynamics, allowing for different timescales between the hidden and feature layers, and also allow for intralayer synapses within the hidden layer. For theoretical tractability, we focus on the discrete-time setting in order to assess the sequence capacity of the model, but our model can be easily extended to continuous time and continuous patterns. 
- Muscinelli et al 2017 propose a way to construct a sequence of $2^N$ patterns an update rule to perfect recall this sequence. but this model is unable to store arbitrary patterns and lacks the error-correction capabilities that our model possesses. 
- The following works focus on overcoming capacity limitations of correlated patterns: Diederich, Opper. PRL, 1987 proposes 2 local learning rule to store correlated patterns where each pattern must be learned sequentially. Gardener 1987 and Bressloff, Taylor 1992 demonstrates ways to store temporal sequences by utilizing perceptron-style learning rules. Blumenfeld et al. 2006 stores correlated patterns by changing weights proportionally to the difference between input and stored memories. These models all overcome pattern correlation via an iterative learning rule which explicitly accounts for correlation, whereas our model can store patterns without doing so.

Meta-review: Meta Review for Long Sequence Hopfield Memory

As summarized by Reviewer 6yTi, this work looks at combining two modifications to the basic Hopfield network to create a network capable of creating and recalling long sequential memories (i.e. sequences of states of the network). The sequence capacity of the proposed network is bounded analytically, and supported by numerical simulations. This model is then extended to allow memories to be recalled a fixed number of times before transitioning to the next item in the sequence. Finally, an implementation of this network using more biologically plausible neurons is given.

Most authors agree on the novelty of the work which extends the original Hopfield network, that the paper is well written, and the theory and simulations complement each other well. A clear acceptance.
Decision: Accept (poster)