基于稠密联想记忆的样本高效学习

# Sample-efficient learning with Dense Associative Memories
Source: [https://arxiv.org/html/2610.27384](https://arxiv.org/html/2610.27384)
Andrew LucasEmail:[andrew\.j\.lucas@colorado\.edu](mailto:[email protected])Affiliation:Department of Physics and Center for Theory of Quantum Matter, University of Colorado, Boulder, CO 80309, USADmitry Krotov

###### Abstract

We analytically study the evolution of the energy function of Dense Associative Memories \(DenseAMs\) as they train on randomly sampled codewords of random expander low\-density parity\-check codes \(a\.k\.a\. solutions of random XORSAT problems\)\. We identify two distinct regimes and a transition between them, reminiscent of grokking in neural networks\. A regime of small training set size is where the model memorizes a few training examples but cannot discover the underlying rules of the entire codeword dictionary generative process\. The opposite regime, corresponding to a larger training set size, is where the model has uncovered the sparse constraints that generated the entire data set after seeing only polynomially many patterns\. We also design a novel class of DenseAMs with a thresholding learning rule, and show that any amount of thresholding enables the model to perform simplified sparse Hamiltonian learning, which exponentially reduces the number of training examples needed to learn the true underlying data set\. In this regime, the model learns how to discoverexp⁡\[O⁡\(n\)\]\\exp\[\\mathrm\{O\}\(n\)\]solutions from onlyO⁡\(log⁡n\)\\mathrm\{O\}\(\\log n\)training samples, which is asymptotically optimal for any learning algorithm\. When training on codewords of certain random codes, the model can even learn the underlying code when a small O\(1\) fraction of bits are latent variables\. These latent variables are not shown to the model during learning, but will be discovered by sparsifying observed higher\-order correlations\. For certain random codes, we show that a simple and conservative algorithm learns a minimal latent representation for the data set\. This provides a transparent, physics\-motivated, and analytically tractable toy model for how deep latent representations emerge in an associative memory training\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2610.27384#S1)
2. [2Basics of Dense Associative Memory](https://arxiv.org/html/2610.27384#S2)
3. [3LDPC codes](https://arxiv.org/html/2610.27384#S3)
4. [4Learning random codes](https://arxiv.org/html/2610.27384#S4)
5. [5Discovering latent variables](https://arxiv.org/html/2610.27384#S5)
6. [6Outlook](https://arxiv.org/html/2610.27384#S6)
7. [AReview of binary linear codes](https://arxiv.org/html/2610.27384#A1)1. [A\.1Basic definitions](https://arxiv.org/html/2610.27384#A1.SS1) 2. [A\.2Useful properties](https://arxiv.org/html/2610.27384#A1.SS2) 3. [A\.3Random expander codes](https://arxiv.org/html/2610.27384#A1.SS3)
8. [BLearning random codes](https://arxiv.org/html/2610.27384#A2)1. [B\.1How many training examples are needed?](https://arxiv.org/html/2610.27384#A2.SS1) 2. [B\.2Dynamics of learning:a→1a\\rightarrow 1](https://arxiv.org/html/2610.27384#A2.SS2) 3. [B\.3Dynamics of learning:a=0a=0](https://arxiv.org/html/2610.27384#A2.SS3)
9. [CLearning latent variables](https://arxiv.org/html/2610.27384#A3)
10. [References](https://arxiv.org/html/2610.27384#Ax1)
11. [References](https://arxiv.org/html/2610.27384#bib)

## 1Introduction

A memorization\-to\-generalization transition is a hallmark of modern AI models\. At early stages of training, large models typically memorize individual instances of training data\. As training progresses, the models discover more abstract features and transition from relying on example\-specific details to forming reusable knowledge via internal representations\. This phenomenon has received substantial attention in Large Language Models, where it is typically called “grokking”\[[1](https://arxiv.org/html/2610.27384#bib.bib1),[2](https://arxiv.org/html/2610.27384#bib.bib2),[3](https://arxiv.org/html/2610.27384#bib.bib3),[4](https://arxiv.org/html/2610.27384#bib.bib4),[5](https://arxiv.org/html/2610.27384#bib.bib5)\]\. Similar observations have been made in Diffusion Models\[[6](https://arxiv.org/html/2610.27384#bib.bib6),[7](https://arxiv.org/html/2610.27384#bib.bib7),[8](https://arxiv.org/html/2610.27384#bib.bib8),[9](https://arxiv.org/html/2610.27384#bib.bib9)\], and Dense Associative Memories \(DenseAMs\)\[[8](https://arxiv.org/html/2610.27384#bib.bib8)\]\. Interest in this phenomenon is motivated both by practical concerns – including privacy and copyright infringement arising from the memorization of training data – and by a more fundamental question: how do individual training examples turn into generalizable knowledge encoded in a model’s weights?

Although the notion of a memorization\-to\-generalization transition is intuitive and widely used, it remains difficult to characterize rigorously in the context of natural datasets\. The underlying rules governing natural datasets are generally unknown\. Consequently, there is no canonical criterion for determining when a model has transitioned from memorizing individual training examples to learning the underlying data\-generating structure\. This ambiguity also makes the transition difficult to quantify as a function of the training set size\.

In this paper we study this problem in a simplified setting where precise results can be found\. Specifically, we study how DenseAMs learn random instances of the XORSAT problem; equivalently, how they learn low\-density parity\-check codes over binary variables\. DenseAMs are a prominent class of energy\-based models, which have super\-linear \(in the size of the neural network\) memory storage capacity\[[10](https://arxiv.org/html/2610.27384#bib.bib10)\]\. They generalize the Hopfield network of associative memory, which has a linear memory storage capacity\[[11](https://arxiv.org/html/2610.27384#bib.bib11)\]\. The generic feature of this class of models is that they have a very large number of basins of attraction \(possibly exponentially large in the size of the network\), and, at the same time, each basin has a substantial volume\. The latter property makes if possible to perform error correction by following a trajectory of the dynamical system minimizing the energy of DenseAM\. To set up the problem, we sample a small number of random codewords from expander low\-density parity\-check \(LDPC\) codes\[[12](https://arxiv.org/html/2610.27384#bib.bib12),[13](https://arxiv.org/html/2610.27384#bib.bib13)\]to form the training set, and ask how many samples are needed until the DenseAM learns the underlying parity\-checks \(constraints\) of the code, rather than simply memorizing individual instances from the training set\. In other words, how many training samples are needed for DenseAM to recover the true underlying generative process of the LDPC codewords?

An LDPC code is a standard method for protecting digital information from errors during transmission or storage\. When transmitting a string of bits, an LDPC code adds a finite fraction of redundant bits: the role of these redundant bits is to act as parity\-checks on the original bits that encoded the logical information\. The code is “low\-density” when each bit is involved in only a finite\-number of \(small\) parity\-checks, and in turn each small check is a constraint involving only a finite number of bits\. If some bits are corrupted by noise, the receiver can use the pattern of satisfied and violated checks to infer which bits are most likely incorrect\. For random LDPC codes, this procedure works with high probability when a smallO⁡\(1\)\\mathrm\{O\}\(1\)fraction of the bits are corrupted\.

The beauty of LDPC codes is that their codewords form a nice*algorithmic dataset*– every codeword comes from a clearly defined mathematical process: in this case, finding solutions to linear equations over𝔽2\\mathbb\{F\}\_\{2\}, a\.k\.a\. the integers \(mod 2\)\. This creates an opportunity for training an AI model on a small subset of codewords \(the training set\), and test the model on the remaining codewords \(the test set\) without ever revealing the underlying mathematical process of code word generation\. Obviously, we can test whether the AI has learned the underlying LDPC code by checking whether or not all of the unseen codewords are verified as solutions by the AI\.

As we will show, DenseAM is a perfect model to train on random LDPC codewords\. The model is defined by an energy function, which has a huge \(possibly exponential in the size of the network\) number of local minima\. Inference dynamics corresponds to a temporal evolution of a dynamical system decreasing the energy, and the low\-energy states correspond to plausible data\-points\. The appealing aspect of DenseAMs is that it is possible to train them both via a self\-supervised learning via the backpropagation algorithm\[[14](https://arxiv.org/html/2610.27384#bib.bib14)\], and, at the same time, via simpler Hebbian\-style learning rules\[[10](https://arxiv.org/html/2610.27384#bib.bib10)\]\. The latter eliminates the complexity of training process from the main phenomenon that we focus on in this work: how sample complexity of the data drives the memorization\-to\-generalization transition\. For this reason we adopt DenseAMs as a toy model laboratory for studying this phenomenon\.

In fact, the architecture of off\-the\-shelf DenseAM is more or less perfectly suited for the efficient learning of XORSAT\. The reason is that under Hebbian learning, the real parity\-checks of the code correspond to weights in the energy function that are maintained as large during training, while false parity\-checks are equally likely to be obeyed or violated\. Therefore under Hebbian learning, DenseAM learns to reduce the weight on false parity\-checks until eventually, the energy landscape is dominated by the true parity\-checks\. Far past this point \(with increasing training set size\), the inference dynamics described in the previous paragraph amounts to gradient descent in the*underlying Hamiltonian*, where each codeword is a local minimum with a large energy basin around it\. Even better, we may read off the underlying rules by identifying the large weights in the learned energy function\. We can, therefore, quantitatively assess exactly how long it takes for DenseAM to learn the underlying code\.

Our results are foreshadowed by earlier literature\. For example, a long time ago, Valiant proposed a PAC theory of approximately\-learnable problems, with satisfiability problems \(which include XORSAT\) as a prime application\[[15](https://arxiv.org/html/2610.27384#bib.bib15)\]\. More recently, a systematic theory of sparse Hamiltonian learning\[[16](https://arxiv.org/html/2610.27384#bib.bib16),[17](https://arxiv.org/html/2610.27384#bib.bib17),[18](https://arxiv.org/html/2610.27384#bib.bib18),[19](https://arxiv.org/html/2610.27384#bib.bib19)\]has been developed, where it is a well\-known result that onlyO⁡\(log⁡n\)\\mathrm\{O\}\(\\log n\)samples are necessary to learn a Hamiltonian when observing random samples drawn from its Gibbs state\. The Hamiltonian itself will typically havepoly⁡\(n\)\\mathrm\{poly\}\(n\)terms, and its Gibbs state may cluster aroundexp⁡\[O⁡\(n\)\]\\exp\[\\mathrm\{O\}\(n\)\]local minima, as in a typical spin glass or complex system\[[20](https://arxiv.org/html/2610.27384#bib.bib20)\]; these features do not make learning the Hamiltonian itself parametrically harder\! The key point is that sparse learning is capable of using the same samples to independently discover many different low\-order correlations corresponding to different interactions in the Hamiltonian\.

The difference between sparse learning and the Hebbian learning rule of DenseAM is that the latter is a computationally efficient algorithm, without an all\-purpose guarantee that it learns the correct problem\. Of particular note is that sparse learning is increasingly slow when the temperature of the sampled Gibbs state is very low\. It turns out, however, that XORSAT is a very special “sparse Hamiltonian” to learn – even at zero temperature \(the limit of interest for our algorithmic dataset\) we may still exactly learn the Hamiltonian\. To achieve the optimalO⁡\(log⁡n\)\\mathrm\{O\}\(\\log n\)scaling of the training set size predicted by sparse learning, we will add a thresholding rule to Hebbian learning, where suitably small couplings are, roughly, rounded down to zero\. We will prove that this modification to DenseAM causes an exponential increase in the efficiency of learning\. Related ideas appeared in\[[21](https://arxiv.org/html/2610.27384#bib.bib21),[22](https://arxiv.org/html/2610.27384#bib.bib22)\], where the authors wished to mock the distribution of solutions to a satisfiability problem, rather than learn it exactly\.

With or without thresholding, we can quantitatively describe the resulting memorization\-to\-generalization transition undergone by DenseAM as a function of training set size\. In the limit of high thresholding, there is a transition between memorization and generalization, reminiscent of the reverse code engineering problem from classical LDPC codes\[[23](https://arxiv.org/html/2610.27384#bib.bib23),[24](https://arxiv.org/html/2610.27384#bib.bib24)\]\. We prove that this transition is surprisingly sharp: with a sufficiently smallO⁡\(log⁡n\)\\mathrm\{O\}\(\\log n\)number of training examples, DenseAM will literally only be able to memorize the seen examples \(and their linear combinations\); with only an O\(1\) factor of extra patterns, it learns the entire code\. In the limit of no thresholding, there is a simple transition as well\. After seeing few patterns, the energy landscape of DenseAM looks Hopfield\-like\[[10](https://arxiv.org/html/2610.27384#bib.bib10),[11](https://arxiv.org/html/2610.27384#bib.bib11)\]and is dominated by the observed patterns\. After seeing sufficiently many \[poly⁡\(n\)\\mathrm\{poly\}\(n\)\] patterns, the weights of the true parity\-checks in the Hamiltonian dominate over the random noisy couplings dominated by the training set, and correspondingly the energy landscape increasingly matches XORSAT \(as the learned energy function becomes the XORSAT Hamiltonian exactly\)\.

Finally, we show that this optimal performance of DenseAM in learning XORSAT persists when a small fraction of the bits in XORSAT are not shown to the AI – they are latent\. Again, the simplifying structure of XORSAT makes it possible for us to very efficiently learn the underlying latent variables, analogous to sparse latent learning\[[25](https://arxiv.org/html/2610.27384#bib.bib25),[26](https://arxiv.org/html/2610.27384#bib.bib26)\]\.

## 2Basics of Dense Associative Memory

We are studying models where the patterns to learn are bitstrings of lengthnn\. We denote each pattern as annn\-component vector\(ξ1μ,…,ξnμ\)\(\\xi^\{\\mu\}\_\{1\},\\ldots,\\xi^\{\\mu\}\_\{n\}\)where eachξiμ∈\{±1\}\\xi^\{\\mu\}\_\{i\}\\in\\\{\\pm 1\\\}\. Here and in what follows, the indicesi,j,…∈\{1,…,n\}i,j,\\ldots\\in\\\{1,\\ldots,n\\\}denote the bits, whileμ,ν,…\\mu,\\nu,\\ldotsdenote the patterns that we will feed the architecture\. We will choose patternsξμ∈𝒞\\xi^\{\\mu\}\\in\\mathcal\{C\}randomly out of some subset𝒞⊆\{±1\}n\\mathcal\{C\}\\subseteq\\\{\\pm 1\\\}^\{n\}\. Our goal will be to learn an energy functionE^:\{±1\}N→ℝ\\widehat\{E\}:\\\{\\pm 1\\\}^\{N\}\\rightarrow\\mathbb\{R\}, such that every element of𝒞\\mathcal\{C\}is a local minimum ofE^\\widehat\{E\}\.

A simple proposal is to chooseE^\\widehat\{E\}as anmm\-local DenseAM\[[10](https://arxiv.org/html/2610.27384#bib.bib10)\]:

E^\(σ\)=−1P∑μ=1P\(∑i=1nξiμσi\)m\.\\widehat\{E\}\(\\sigma\)=\-\\frac\{1\}\{P\}\\sum\_\{\\mu=1\}^\{P\}\\left\(\\sum\_\{i=1\}^\{n\}\\xi\_\{i\}^\{\\mu\}\\sigma\_\{i\}\\right\)^\{m\}\.\(1\)It is convenient to introduce tensor

Ti1⋯im:=1P∑μ=1Pξμi1⋯ξimμ\.T\_\{i\_\{1\}\\cdots i\_\{m\}\}:=\\frac\{1\}\{P\}\\sum\_\{\\mu=1\}^\{P\}\\xi^\{\\mu\}\_\{i\_\{1\}\}\\cdots\\xi\_\{i\_\{m\}\}^\{\\mu\}\.\(2\)and its*thresholded*version

T^i1⋯im=ϕa\(Ti1⋯im\),\\widehat\{T\}\_\{i\_\{1\}\\cdots i\_\{m\}\}=\\phi\_\{a\}\(T\_\{i\_\{1\}\\cdots i\_\{m\}\}\),\(3\)where

ϕa​\(x\):=11−a​sign​\(x\)​max⁡\(0,\|x\|−a\)\.\\phi\_\{a\}\(x\):=\\frac\{1\}\{1\-a\}\\mathrm\{sign\}\(x\)\\max\(0,\|x\|\-a\)\.\(4\)For later purposes, we also write

E^\(σ\)=−∑i1,…,imT^i1⋯imσi1⋯σim,\\widehat\{E\}\(\\sigma\)=\-\\sum\_\{i\_\{1\},\\ldots,i\_\{m\}\}\\widehat\{T\}\_\{i\_\{1\}\\cdots i\_\{m\}\}\\sigma\_\{i\_\{1\}\}\\cdots\\sigma\_\{i\_\{m\}\},\(5\)where the sum over indicesi1,…,imi\_\{1\},\\ldots,i\_\{m\}allows repeated entries\. In the classical DenseAM \([1](https://arxiv.org/html/2610.27384#S2.E1)\), we havea=0a=0:

T^i1⋯im=ϕa=0\(Ti1⋯im\)=1P∑μ=1Pξi1μ⋯ξimμ\.\\widehat\{T\}\_\{i\_\{1\}\\cdots i\_\{m\}\}=\\phi\_\{a=0\}\(T\_\{i\_\{1\}\\cdots i\_\{m\}\}\)=\\frac\{1\}\{P\}\\sum\_\{\\mu=1\}^\{P\}\\xi^\{\\mu\}\_\{i\_\{1\}\}\\cdots\\xi\_\{i\_\{m\}\}^\{\\mu\}\.\(6\)As we will see later, it is also interesting to consider a thresholded DenseAM \(TDenseAM\), where parameter0≤a<10\\leq a<1\. The role of the parameteraais to provide a “noise floor” below which we reject couplings inE^\\widehat\{E\}\. In other words, we wish to only keep terms inE^\\widehat\{E\}where we see a persistent signal across the observed patterns\.

Once we have a learned energy functionE^\\widehat\{E\}, we simply perform gradient descent from any initial condition to deduce the output of the model, as is standard in the literature on EBMs\. In practice, we will perform gradient descent by choosing each bit \(in a random order\), and flipping it if doing so lowers the energy\. We update the value ofEEbefore checking the next bit\. This algorithm terminates in a local minimum after a finite number of steps\[[27](https://arxiv.org/html/2610.27384#bib.bib27)\]\.

## 3LDPC codes

Whether or not the DenseAM can efficiently learn will clearly depend on the choice𝒞\\mathcal\{C\}of patterns\. A natural idea is to choose𝒞\\mathcal\{C\}as the ground states of a frustration\-free energy functionEE, which itself takes the form of

E\(σ\):=−∑i1,…,imJi1⋯imσi1⋯σim\.E\(\\sigma\):=\-\\sum\_\{i\_\{1\},\\ldots,i\_\{m\}\}J\_\{i\_\{1\}\\cdots i\_\{m\}\}\\sigma\_\{i\_\{1\}\}\\cdots\\sigma\_\{i\_\{m\}\}\.\(7\)Then we would want to learnT^i1⋯im=Ji1⋯im\\widehat\{T\}\_\{i\_\{1\}\\cdots i\_\{m\}\}=J\_\{i\_\{1\}\\cdots i\_\{m\}\}\. There’s a natural way to choose suchJi1⋯imJ\_\{i\_\{1\}\\cdots i\_\{m\}\}\. IfEEis frustration\-free, we need, for everyσ∈𝒞\\sigma\\in\\mathcal\{C\},Ji1⋯imσi1⋯σim≥0J\_\{i\_\{1\}\\cdots i\_\{m\}\}\\sigma\_\{i\_\{1\}\}\\cdots\\sigma\_\{i\_\{m\}\}\\geq 0\. For simplicity, suppose eachJi1⋯im≥0J\_\{i\_\{1\}\\cdots i\_\{m\}\}\\geq 0\. Then we needσi1⋯σim=1\\sigma\_\{i\_\{1\}\}\\cdots\\sigma\_\{i\_\{m\}\}=1for anyJi1⋯im\>0J\_\{i\_\{1\}\\cdots i\_\{m\}\}\>0\. This is precisely the XORSAT problem in computer science, also known as a low\-density parity\-check \(LDPC\) code\[[13](https://arxiv.org/html/2610.27384#bib.bib13)\]\.

It is more natural to switch to a binary representation:

ξiμ\\displaystyle\\xi\_\{i\}^\{\\mu\}=:1−2​biμ,\\displaystyle=:1\-2b\_\{i\}^\{\\mu\},\(8a\)σi\\displaystyle\\sigma\_\{i\}=:1−2​xi\.\\displaystyle=:1\-2x\_\{i\}\.\(8b\)The ground states ofEE, or the elements of𝒞\\mathcal\{C\}, are then the right null vectors of a parity\-check matrixHH:

𝒞=\{b∈𝔽2n:H​b=0\},\\mathcal\{C\}=\\\{b\\in\\mathbb\{F\}\_\{2\}^\{n\}:Hb=0\\\},\(9\)where𝔽2=\{0,1\}\\mathbb\{F\}\_\{2\}=\\\{0,1\\\}and the parity\-check matrixHHis𝔽2\\mathbb\{F\}\_\{2\}\-valued\. For everyJi1⋯im≠0J\_\{i\_\{1\}\\cdots i\_\{m\}\}\\neq 0, we can add a rowα\\alphato the parity\-check matrix with

Hα​i=\{1i∈α=\{i1,…,im\}0i∉α\.H\_\{\\alpha i\}=\\left\\\{\\begin\{array\}\[\]\{ll\}1&\\ i\\in\\alpha=\\\{i\_\{1\},\\ldots,i\_\{m\}\\\}\\\\ 0&\\ i\\notin\\alpha\\end\{array\}\\right\.\.\(10\)By construction, notice that𝒞\\mathcal\{C\}has the structure of a vector space\. The dimension of this vector space is labeledkk, and referred to as the number of logical bits\. Clearly then,\|𝒞\|=2k\|\\mathcal\{C\}\|=2^\{k\}\. In what follows, let

ΔB^:=\{1ΔB​is even0ΔB​is odd\.\\widehat\{\\Delta\_\{\\mathrm\{B\}\}\}:=\\left\\\{\\begin\{array\}\[\]\{ll\}1&\\ \\Delta\_\{\\mathrm\{B\}\}\\text\{ is even\}\\\\ 0&\\ \\Delta\_\{\\mathrm\{B\}\}\\text\{ is odd\}\\end\{array\}\\right\.\.\(11\)
In practice, we will prefer to pick a random matrixHHand chooseJi1⋯imJ\_\{i\_\{1\}\\cdots i\_\{m\}\}accordingly\. We choose the random matrixHHas follows\[[12](https://arxiv.org/html/2610.27384#bib.bib12)\]: pick a numberΔB<m\\Delta\_\{\\mathrm\{B\}\}<m, and choose the rows ofHHrandomly such that each row has exactlymm1s and each column has exactlyΔB\\Delta\_\{\\mathrm\{B\}\}1s\. We now summarize some crucial properties of these random codes, leaving a more formal discussion to Appendix[A](https://arxiv.org/html/2610.27384#A1)\. A useful representation of an LDPC code is a Tanner graph \(or a factor graph\), depicted in Figure[1](https://arxiv.org/html/2610.27384#S3.F1)\. The Tanner graph contains nodes that are either bits or checks, with an edge between bitiiand checkα\\alphaif and only ifHα​i=1H\_\{\\alpha i\}=1\. LDPC codes then correspond to sparse Tanner graphs\. We generate LDPC codes randomly by choosing random111The precise distribution of such graphs that we sample \(uniformly\) from is detailed in Appendix[A](https://arxiv.org/html/2610.27384#A1)\.Tanner graphs where every bit node has degreeΔB\\Delta\_\{\\mathrm\{B\}\}and every check node has degreeΔC=m\\Delta\_\{\\mathrm\{C\}\}=m\. Almost surely asn→∞n\\rightarrow\\infty,

k=\(1−ΔBm\)​n\+ΔB^\.k=\\left\(1\-\\frac\{\\Delta\_\{\\mathrm\{B\}\}\}\{m\}\\right\)n\+\\widehat\{\\Delta\_\{\\mathrm\{B\}\}\}\.\(12\)Relatedly, the number𝒩\\mathcal\{N\}of parity\-checks of weightmmis, with high probability,

𝒩=ΔBm​n\+O⁡\(1\)\.\\mathcal\{N\}=\\frac\{\\Delta\_\{\\mathrm\{B\}\}\}\{m\}n\+\\mathrm\{O\}\(1\)\.\(13\)
Figure 1:Illustration of a local patch of a Tanner graph of a random code with\(ΔB,ΔC\)=\(3,4\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)=\(3,4\)\. Bitsiiare depicted as black circles; checksα\\alphaare depicted as orange squares\. The number of small cycles in a Tanner graph is extremely small, so the graph will typically look locally tree\-like\.There are simple, yet useful, observations about the typical weightsTi1⋯imT\_\{i\_\{1\}\\cdots i\_\{m\}\}\. If\{i1,…,im\}\\\{i\_\{1\},\\ldots,i\_\{m\}\\\}is a real parity\-check contained inim⁡\(H𝖳\)\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\), we always have

Ti1⋯im=1\.T\_\{i\_\{1\}\\cdots i\_\{m\}\}=1\.\(14\)Otherwise,ξi1μ⋯ξμim\\xi\_\{i\_\{1\}\}^\{\\mu\}\\cdots\\xi^\{\\mu\}\_\{i\_\{m\}\}equally likely to be±1\\pm 1; hence

𝔼\[Ti1⋯im\]\\displaystyle\\mathbb\{E\}\[T\_\{i\_\{1\}\\cdots i\_\{m\}\}\]=0,\\displaystyle=0,\(15a\)𝔼\[Ti1⋯im2\]\\displaystyle\\mathbb\{E\}\\left\[\{T\_\{i\_\{1\}\\cdots i\_\{m\}\}\}^\{2\}\\right\]=1P\.\\displaystyle=\\frac\{1\}\{P\}\.\(15b\)Hoeffding’s inequality implies

ℙ\(\|TI\|\>s\)≤2e−Ps2/2\.\\mathbb\{P\}\\left\(\\left\|T\_\{I\}\\right\|\>s\\right\)\\leq 2\\mathrm\{e\}^\{\-Ps^\{2\}/2\}\.\(16\)In fact, these observations explain why we should choose𝒞\\mathcal\{C\}as the codewords \(ground states\) of an LDPC code’sEE\.T^i1⋯im\\widehat\{T\}\_\{i\_\{1\}\\cdots i\_\{m\}\}are chosen by \([6](https://arxiv.org/html/2610.27384#S2.E6)\) to be equal weight superpositions of the observed patterns\. So in general, TDenseAM does not perform Hamiltonian learning; it simply measures low\-order correlations between spins when drawing samples uniformly at random from𝒞\\mathcal\{C\}\. We are only guaranteed that these low\-order correlations*exactly*match the terms inEEitself, which follows from the equations above, whenEEparametrizes a linear code\. For this reason, the \(T\)DAM architecture is perfectly suited to learn binary linear codes\. The suitability of the data set to the architecture will enable us to make rigorous statements about how the model learns\.

## 4Learning random codes

Now let us describe the learning process\. Here we give an intuitive and non\-rigorous discussion; all scaling arguments are established rigorously in Appendix[B](https://arxiv.org/html/2610.27384#A2)\.

It is useful to first briefly review how the regular DenseAM \(a=0a=0\) architecture trains on random data\[[10](https://arxiv.org/html/2610.27384#bib.bib10)\]\. Suppose that the number of patternsP∼nαP\\sim n^\{\\alpha\}\. Whenα<m−1\\alpha<m\-1, \([1](https://arxiv.org/html/2610.27384#S2.E1)\) is dominated by the actual learned patterns, in the sense that there are deep energy wells surrounding every seen patternξμ\\xi^\{\\mu\}\. \(There are also “mixed minima” corresponding to particular mixtures of patterns\[[28](https://arxiv.org/html/2610.27384#bib.bib28)\]\.\) In contrast, onceα\>m−1\\alpha\>m\-1, the energy landscape becomes corrupted and overtrained\.

The story changes when we train on random codewords of an LDPC code\. Now the learned energyE^\\widehat\{E\}consists of two parts: the genuine parity\-checks of the code, which contribute energy∼𝒩\\sim\\mathcal\{N\}independent of the number of seen examplesPP, along with “junk” pattern\-sensitive terms, which contribute a typical energy∼nm/P\\sim\\sqrt\{n^\{m\}/P\}; these facts follow from \([14](https://arxiv.org/html/2610.27384#S3.E14)\) and \([15b](https://arxiv.org/html/2610.27384#S3.E15.2)\)\. IfP∼nαP\\sim n^\{\\alpha\}withα\>m−2\\alpha\>m\-2, we see that the true parity\-checks of the code begin to meaningfully shape the energy landscape: codewords are lower energy than random locations\. However, this does not mean that DenseAM will successfully recover unseen codewords\. Consider starting at an unseen codeword and perturbing the state by flipping any O\(1\) fraction of bits to align with a seen codeword\. The net energy change is

Δ​E^∼𝒩−nmP,\\mathrm\{\\Delta\}\\widehat\{E\}\\sim\\mathcal\{N\}\-\\frac\{n^\{m\}\}\{P\},\(17\)where the first positive contribution counts the number of violated parity\-checks, while the second negative contribution comes from the huge energy gain from pattern alignment in \([1](https://arxiv.org/html/2610.27384#S2.E1)\)\. Using \([13](https://arxiv.org/html/2610.27384#S3.E13)\), we see that untilα≥m−1\\alpha\\geq m\-1, the second term wins, so the DenseAM has a heavy bias towards reproducing seen patterns, just as when it is trained on random data\. In fact, we prove whenP/nm−1P/n^\{m\-1\}is larger than a suitable O\(1\) constant, there are \(with high probability\) extensive energy barriers around each codeword\. This ensures that the denseAM will*not*simply return a seen pattern – it will at worst give an approximation of the true codeword \(with a bounded fraction of errors\) when initialized on an arbitrary codeword\.

Next, let us turn to the opposite regime ofa→1a\\rightarrow 1\. This extreme thresholding limit is equivalent to Valiant’s \(XOR\)SAT learning algorithm\[[15](https://arxiv.org/html/2610.27384#bib.bib15)\], and to the “reverse code engineering” problem\[[23](https://arxiv.org/html/2610.27384#bib.bib23),[24](https://arxiv.org/html/2610.27384#bib.bib24)\]\. For simplicity in the discussion that follows, let us assume that the first shown pattern isξi1=1\\xi\_\{i\}^\{1\}=1\(we can always “gauge fix” the training data so that this occurs\)\. After the first pattern, TDenseAM will presume that ifmmis odd, every spin must be fixed toσi=1\\sigma\_\{i\}=1; ifmmis even,σi=−1\\sigma\_\{i\}=\-1is also allowed\. TDenseAM presumes that a parity\-check is valid if and only if it has never seen it violated, and at this first step it has learned∼nm\\sim n^\{m\}checks\. All but𝒩\\mathcal\{N\}of them are spurious and should be unlearned during training\. As in \([15a](https://arxiv.org/html/2610.27384#S3.E15.1)\), each subsequent shown random codewordξμ\\xi^\{\\mu\}has a 50% chance of violating each remaining spurious check\. The number of parity\-checks inE^\\widehat\{E\}thus scales as𝒩\+nm​2−P\\mathcal\{N\}\+n^\{m\}2^\{\-P\}and concentrates around this mean in the thermodynamic limit\.

DenoteH^​\(P\)\\widehat\{H\}\(P\)as the learned parity\-check matrix afterPPpatterns\.H^​\(P\)\\widehat\{H\}\(P\)contains checks of weightmm,m−2m\-2, etc\. Further denote

k^​\(P\):=dim\(ker⁡H^​\(P\)\)\.\\widehat\{k\}\(P\):=\\dim\\left\(\\ker\\widehat\{H\}\(P\)\\right\)\.\(18\)The number of minima ofE^\\widehat\{E\}is2k^2^\{\\widehat\{k\}\}, becauseE^\\widehat\{E\}consists only of the parity\-checks consistent with all seen codewords\. Since the minima ofE^\\widehat\{E\}correspond to solutions of a linear equation, superpositions of observed codewords are also valid solutions\.

We conjecture that there is a sharp transition near

P∗=\(m−1\)​log2​n\.P\_\{\*\}=\(m\-1\)\\log\_\{2\}n\.\(19\)Indeed, we can show that onceP\>P∗P\>P\_\{\*\}, the number of spurious checks scales subextensively withnn\. Even if all of these spurious checks are linearly independent \(and they will be with high probability\), they can at most reduce the rank to

k^≈k−nmm\!​2−P;\\widehat\{k\}\\approx k\-\\frac\{n^\{m\}\}\{m\!\}2^\{\-P\};\(20\)the first termk=Θ⁡\(n\)k=\\mathrm\{\\Theta\}\(n\)while onceP∗∼\(m−1\+ϵ\)​log2​nP\_\{\*\}\\sim\(m\-1\+\\epsilon\)\\log\_\{2\}nfor anyϵ\>0\\epsilon\>0, the second term is subextensive\.

The behavior forP<P∗P<P\_\{\*\}depends on the value ofmm\. Form=2m=2, we find thatk^≈2P\\widehat\{k\}\\approx 2^\{P\}forP≪log2​kP\\ll\\log\_\{2\}k\. This is because every LDPC code with weight\-2 checks corresponds to a set of decoupled repetition codes: namely, there will bekkindependent clusters of spins that must all agree within each cluster\. We need only observe codewords where any pair of two repetition code blocks take different values in order to distinguish them\. For example, we can see patterns00000000,00110011,01010101to learn that these 4 bits are all independent\.

In contrast, form\>2m\>2, we instead expect that

k^=P−1\+ΔB^\\widehat\{k\}=P\-1\+\\widehat\{\\Delta\_\{\\mathrm\{B\}\}\}\(21\)untilP∼\(m−1\)​log2⁡n⁡\[1\+o⁡\(1\)\]P\\sim\(m\-1\)\\log\_\{2\}n\[1\+\\mathrm\{o\}\(1\)\]\. The reason for this drastic change in behavior is simple, yet profound: with higher weight checks, the∼nm​2−P\\sim n^\{m\}2^\{\-P\}surviving spurious checks necessarily have many linear dependencies \(i\.e\. redundancies\) untilP=\(m−1\)​log2​nP=\(m\-1\)\\log\_\{2\}n\. These dependencies are also more complex compared tom=2m=2: checksw1w\_\{1\}andw2w\_\{2\}can be violated by the next codeword whilew1\+w2w\_\{1\}\+w\_\{2\}is a combination of non\-violated checks\. We can crudely estimate that the typical number of ways to expressw1\+w2w\_\{1\}\+w\_\{2\}as a linear combination ofLLnon\-violated checks scales as≳2−P​L​nm​L/2−2​m\\gtrsim 2^\{\-PL\}n^\{mL/2\-2m\}\. Hence whenP≲c​m​log2⁡nP\\lesssim cm\\log\_\{2\}n\(withc≤12c\\leq\\frac\{1\}\{2\}\), removingw1w\_\{1\}andw2w\_\{2\}only increasesk^\\widehat\{k\}by 1\. With a little more work, we can prove \([21](https://arxiv.org/html/2610.27384#S4.E21)\) as long asP≲c​m​log2⁡nP\\lesssim cm\\log\_\{2\}n\. \([21](https://arxiv.org/html/2610.27384#S4.E21)\) is related to the fact that most random codes generated by pickingk∼log⁡nk\\sim\\log nrandom bitstrings as codewords are LDPC\[[24](https://arxiv.org/html/2610.27384#bib.bib24)\]; it is then natural that a similar fact such as \([21](https://arxiv.org/html/2610.27384#S4.E21)\) can persist when given random codewords\. It may be a little surprising, though, that the structure of the code reveals itself so rapidly\!

The dramatic change in learnability of the LDPC code is very easy to see when training a weight\-mmTDenseAM on random bitstrings\. Asa→1a\\rightarrow 1, the TDenseAM should eventually learnE^=0\\widehat\{E\}=0, ork^=n\\widehat\{k\}=n\. The random trajectories ofk^​\(P\)\\widehat\{k\}\(P\)behave very differently whenm=2m=2vs\.m\>2m\>2, exactly as predicted above\. A small numerical demonstration is shown in Figure[2](https://arxiv.org/html/2610.27384#S4.F2)\.

Figure 2:k^\\widehat\{k\}as a function ofPPwhen training thea→1a\\rightarrow 1TDenseAM on random bitstrings of lengthn=100n=100\. The bubble plot depicts the probability of seeing a given value ofk^\\widehat\{k\}at eachPPwhen choosing a random sequence of training data\. Left:m=2m=2\. Right:m=4m=4, where \([21](https://arxiv.org/html/2610.27384#S4.E21)\) is clearly visible at smallPP\.The punchline is that whenm\>2m\>2, TDenseAM learns “slowly” at smallPP, and largely by memorization\. Indeed, for thea→1a\\rightarrow 1learner, linear combinations of seen patterns are necessarily minima, sok^→k^\+1\\widehat\{k\}\\rightarrow\\widehat\{k\}\+1learning is the least efficient possible, as long as every new seen pattern is linearly independent of the others \(which almost surely happens asn→∞n\\rightarrow\\infty\)\. At a criticalP=P∗P=P\_\{\*\}, the spurious checks abruptly fall “below” the noise threshold, and TDenseAM begins to rapidly*generalize*beyond the training data it has seen\.

This behavior is reminiscent of the grokking phenomenon seen in neural networks\[[1](https://arxiv.org/html/2610.27384#bib.bib1),[2](https://arxiv.org/html/2610.27384#bib.bib2),[3](https://arxiv.org/html/2610.27384#bib.bib3),[4](https://arxiv.org/html/2610.27384#bib.bib4),[5](https://arxiv.org/html/2610.27384#bib.bib5)\]: one trains a neural network on “algorithmic datasets” such as ours, and observes that first the neural network learns to reproduce training data it has seen, only “discovering” the underlying rules generating the data long after reproducing training data\. In neural networks, one could either talk about such a transition upon showing more training data, or optimizing network weights on a fixed dataset; in our context, only the former makes sense\. In the context of our XORSAT problem, the TDenseAM is basically guaranteed by construction to always correctly reproduce training data it has already seen\. The non\-trivial step in the analogue “grokking” is to generalize, which in this context amounts to correctly assigning unseen codewords \(solutions\) to local minima inE^\\widehat\{E\}\. Figure[2](https://arxiv.org/html/2610.27384#S4.F2)demonstrates our analogue of this “grokking” phenomenon in them\>2m\>2TDenseAM when trained on random data\. In our context, the fact that grokking is a manifestation of the need to suppress spurious couplings inE^\\widehat\{E\}is very clear\. Firstly, it takes a long time for the spurious checks inE^\\widehat\{E\}to be suppressed relative to the true checks\. The abruptness of the transition is, in some sense, simply an artifact of the slow rate at which TDenseAM learns to remove spurious checks\. Secondly, once the spurious contribution toE^\\widehat\{E\}is comparable to the true one, removing half of the spurious checks in each step leads to an explosive growth in generalizability, with nearly the entire code being discovered in a short training window\.

When0<a≪10<a\\ll 1, we expect a rough “interpolation” between the two extreme limits above\. From \([16](https://arxiv.org/html/2610.27384#S3.E16)\), TDenseAM will almost surely learn the code so long as

P\>2​ma2​log2​n\.P\>\\frac\{2m\}\{a^\{2\}\}\\log\_\{2\}n\.\(22\)This follows directly from a sub\-optimal tail bound estimate on the probability of seeing a finite fraction≥1\+a2\\geq\\frac\{1\+a\}\{2\}of codewords that violate \(or not\) any spurious check\. So, any amount of thresholding at all immediately leads to complete discovery of the underlying code – and all of itsexp⁡\(O⁡\(n\)\)\\exp\(\\mathrm\{O\}\(n\)\)codewords – inO⁡\(log⁡n\)\\mathrm\{O\}\(\\log n\)patterns\.

We directly test this transition numerically by studying the behavior of the TDenseAM when it is initialized in an unseen codewordσnew\\sigma^\{\\text\{new\}\}\. Suppose that after initializingσ→σnew\\sigma\\rightarrow\\sigma^\{\\text\{new\}\}and running gradient descent usingE^\\widehat\{E\}, the final bit string isσend\\sigma^\{\\mathrm\{end\}\}\. To test whether or not TDenseAM has simply memorized the patterns it has already seen, we probe

fnew:=1n​minμ​𝖽H​\(ξμ,σend\)\.f\_\{\\mathrm\{new\}\}:=\\frac\{1\}\{n\}\\min\_\{\\mu\}\\mathsf\{d\}\_\{\\mathrm\{H\}\}\\left\(\\xi^\{\\mu\},\\sigma^\{\\text\{end\}\}\\right\)\.\(23\)Here𝖽H\\mathsf\{d\}\_\{\\mathrm\{H\}\}denotes Hamming distance, or the number of bits in different states\. In the case wheremmis even, we must also minimize over−ξμ\-\\xi^\{\\mu\}as the TDenseAM will always have a global spin flip symmetry\.fnewf\_\{\\text\{new\}\}thus represents the fraction of bits in a “new configuration” relative to any trained pattern:fnewf\_\{\\text\{new\}\}should be 0 if we are memorizing, and O\(1\) if we are discovering new codewords\. Since we have fed the TDenseAM an actual codeword, we can test whether it has learned by asking whether or not the initial stateσnew\\sigma^\{\\text\{new\}\}was in fact a local minimum, which is conveniently measured by the fraction of flipped spins:

fflip:=1n​𝖽H​\(σnew,σend\)f\_\{\\text\{flip\}\}:=\\frac\{1\}\{n\}\\mathsf\{d\}\_\{\\mathrm\{H\}\}\\left\(\\sigma^\{\\text\{new\}\},\\sigma^\{\\text\{end\}\}\\right\)\(24\)Figure[3](https://arxiv.org/html/2610.27384#S4.F3)shows the behavior offflipf\_\{\\text\{flip\}\}andfnewf\_\{\\text\{new\}\}as a function ofPP\. Whena≪1a\\ll 1, we see a long period of*strict*memorization – just like in thea=0a=0DenseAM, we are overwhelmingly likely to simply reproduce a seen training example as the energy landscape is overwhelmingly shaped by these seen examples\. \(Occasionally we do see the model settle at an unseen point, but this is rare\.\) At a scale smaller than our bound in \([22](https://arxiv.org/html/2610.27384#S4.E22)\), TDenseAM begins to efficiently generalize:E^\\widehat\{E\}develops local minima appear near typical unseen codewords, so it has learned the rules generating the data set\. The transition from memorization to generalization appears relatively sharp, but we have not analytically characterized this transition, and our simulations are clearly limited by finite\-size effects\. The transition is clearly much more efficient whena→1a\\rightarrow 1\. In this case,fnewf\_\{\\text\{new\}\}is appreciable already atP=2P=2, which is easily understood: TDenseAM in this limit also learns linear combinations of seen codewords\.

Figure 3:The memorization\-generalization transition as a function ofPP, after initializing TDenseAM at unseen codewords\. The probability distributions offflipf\_\{\\text\{flip\}\}andfnewf\_\{\\text\{new\}\}are depicted as bubble plots\. Training is done on a \(3,4\) code \(n=80n=80,k=20k=20\)\. Left:a=0\.2a=0\.2\. Right:a→1a\\rightarrow 1\.It is plausible that right at the memorization\-generalization transition, at anyaa, TDenseAM becomes very “corrupted” by a glassy energy landscape inE^\\widehat\{E\}\. This occurs in Figure[3](https://arxiv.org/html/2610.27384#S4.F3)during the regime when bothfflipf\_\{\\text\{flip\}\}andfnewf\_\{\\text\{new\}\}are sizable, right before generalization\. This is likely due to the glassy energy landscape of random LDPC codes themselves\. It would be interesting to investigate further in future work\.

## 5Discovering latent variables

It is often believed that when studying complex data patterns, some of the relevant degrees of freedom are not directly shown to the observer\. Such bits are called*latent*\. A potential example is that visible bits correspond to the pixels in an image, while latent bits describe what the image represents\. There may not be a simple, local expression forE^\\widehat\{E\}without learning the latent variables\.

Amazingly, we can also use TDenseAM to efficiently learn latent variables in XORSAT\. Let the firstn−n¯n\-\\overline\{n\}bits be observed, and the remainingn¯\\overline\{n\}bits be latent\. In ths section, we will denote observed bits withxix\_\{i\}\(i=1,…,n−n¯\)\(i=1,\\ldots,n\-\\overline\{n\}\)and latent bits withhαh\_\{\\alpha\}\(α=n−n¯\+1,…,n\\alpha=n\-\\overline\{n\}\+1,\\ldots,n\)\. We wish to generalize TDenseAM so that it can discover the latent bits\. Importantly, TDenseAM will not be told how many latent bits there are, nor where latent bits may be relative to the observed interaction graph – it must discover all of this on its own\.

A conservative way to discover a latent variable is to detect what we call an observable 3\-shadow\. In the context of LDPC codes with weight\-mmchecks, this shadow will take the form of three2​m−22m\-2\-weight observable checks with a special structure:

w1\\displaystyle w\_\{1\}=w¯2\+w¯3,\\displaystyle=\\overline\{w\}\_\{2\}\+\\overline\{w\}\_\{3\},\(25a\)w2\\displaystyle w\_\{2\}=w¯3\+w¯1,\\displaystyle=\\overline\{w\}\_\{3\}\+\\overline\{w\}\_\{1\},\(25b\)w3\\displaystyle w\_\{3\}=w¯1\+w¯2\.\\displaystyle=\\overline\{w\}\_\{1\}\+\\overline\{w\}\_\{2\}\.\(25c\)Herew¯1,2,3\\overline\{w\}\_\{1,2,3\}are vectors of Hamming weightm−1m\-1\. Notice thatw1,2,3w\_\{1,2,3\}are consistent with three smaller, weightmm, checks that contain a latent variablehh:

h\+w¯1=h\+w¯2=h\+w¯3=0\.h\+\\overline\{w\}\_\{1\}=h\+\\overline\{w\}\_\{2\}=h\+\\overline\{w\}\_\{3\}=0\.\(26\)The key intuition is that if we observe three such patterns, rather than only two, we have clear insight as to where the latent variable must go\. If we only saww1w\_\{1\}, but notw2,3w\_\{2,3\}, the decomposition intow¯2,3\\overline\{w\}\_\{2,3\}is not knowable\. In principle, one could still introduce many candidate latent variables and keep only the ones which remain predictive\. To keep the story simple, however, we will restrict to learn latent variables when they have a 3\-shadow as above\.

We now summarize how to build a latent TDenseAM, leaving details to Appendix[C](https://arxiv.org/html/2610.27384#A3)\. The strategy is to run TDenseAM looking for weight\-\(2​m−2\)\(2m\-2\)checks\. We immediately accept checks of weight≤m\\leq m, but also look for observable 3\-shadows among the observed variables\. When we detect them, we introduce a latent variable to reduce them into acceptable checks with weight≤m\\leq m\. The value of the latent variable should then be appended to all of the training data\. Then, we re\-run TDenseAM with the learned latent variables treated as observed\. This process continues until we cannot discover any more latent variables\. An illustration is given in Figure[4](https://arxiv.org/html/2610.27384#S5.F4)\.

Figure 4:Illustration of a local patch of a Tanner graph of a random code with observed \(black\) and latent \(white\) bits\. The latent TDenseAM learner will detecth1h\_\{1\}since it has an observable 3\-shadow\. Learningh1h\_\{1\}revealsh2h\_\{2\}, which also subsequently has an observable 3\-shadow\.We prove in Appendix[C](https://arxiv.org/html/2610.27384#A3)that, almost surely asn→∞n\\rightarrow\\infty, latent TDenseAM can learn every latent variable correctly when training on random\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC codes, if5<ΔB<ΔC5<\\Delta\_\{\\mathrm\{B\}\}<\\Delta\_\{\\mathrm\{C\}\},

n¯<γ​n\\overline\{n\}<\\gamma n\(27\)for some O\(1\) constantγ\\gamma, and the number of training patterns exceeds

P\>4​\(m−1\)a2​log2​n\.P\>\\frac\{4\(m\-1\)\}\{a^\{2\}\}\\log\_\{2\}n\.\(28\)In a nutshell, the proof uses the fact that locally, random codes look rather tree\-like\. This property of the code, more accurately called expansion, guarantees that some latent variables will always have observable 3\-shadows, and that any time an observable 3\-shadow is found, it comes from an actual latent variable\. This also guarantees that latent TDenseAM will never introduce incorrect constraints\.

The guarantee above does not rely on the latent bits being distributed randomly amongst the code; every subset ofn¯\\overline\{n\}latent bits will be learned, as long as we have \([27](https://arxiv.org/html/2610.27384#S5.E27)\)\. This is interesting because it means that we can even learn latent bits which are only observable after∼log⁡n\\sim\\log nrounds of running TDenseAM\. The correlations used to detect these deep latent variables will originally be extensive correlations among finite fractions of all of the observed bits\. The expansion of random codes, along with the certification of the shallower latent bits, guarantees that the deepest latent variable is genuine and detectable\.

## 6Outlook

We have presented a simple and largely solvable model for how a \(thresholded\) dense associative memory learns on a specific algorithmic dataset – randomly chosen codewords of an expander LDPC code\. This architecture first learns by memorization of observed patternsξμ\\xi^\{\\mu\}, and later abruptly begins to generalize well beyond the training data, in a sharp transition somewhat reminiscent of grokking\. The same architecture is also capable of discovering latent variables efficiently, providing a simple and solvable cartoon for the role of deep latent variables as sparsifications of the rules that generated the dataset\.

Although we have not explicitly verified it, it is almost certain that the models described here can easily train on corrupted LDPC codewords, and any thresholdinga\>0a\>0ensures learnability inΘ⁡\(log⁡n\)\\mathrm\{\\Theta\}\(\\log n\)corrupted samples \(so long as the corruption is reasonably independent\); it would be interesting to study the dynamics of learning more carefully in this setting\. More non\-trivially, carefully chosen EBMs can provably efficiently learn other problems: for example, certain modular addition tables are discovered\[[29](https://arxiv.org/html/2610.27384#bib.bib29)\]doubly\-exponentially faster in EBMs than in one\-hot neural networks\[[1](https://arxiv.org/html/2610.27384#bib.bib1),[2](https://arxiv.org/html/2610.27384#bib.bib2),[3](https://arxiv.org/html/2610.27384#bib.bib3),[4](https://arxiv.org/html/2610.27384#bib.bib4),[5](https://arxiv.org/html/2610.27384#bib.bib5)\]\. Perhaps the ideas we have fleshed out in a simplified setting may prove relevant more broadly in a theory of how AI learns structured data\.

## Acknowledgments

We thank MPI\-PKS for hospitality as this work was initiated\. ChatGPT 5\.5/6 Pro was used to help write codes and to assist in proving the main theorems\. Codex 5\.5 Medium wrote the code to make figures on small sample sizes for the main text\.

## Appendix AReview of binary linear codes

### A\.1Basic definitions

In the text that follows we will use some convenient shorthand:\[n\]=\{1,2,…,n\}\[n\]=\\\{1,2,\\ldots,n\\\}refers to the set ofnnelements labeled by the firstnnintegers\. Similarly we will just write\[I\]\[I\]to denote the set of all objects that could be labeled withII: in particular, ifIIdenotes anmm\-tuple of the bits which can be a coupling of the dense associative memory, then\[I\]=\{I⊂\[n\]:\|I\|=m\}\[I\]=\\\{I\\subset\[n\]:\|I\|=m\\\}, etc\. We denote the indicator function with

𝕀⁡\[X\]:=\{1Xis true0Xis false\.\\mathbb\{I\}\[X\]:=\\left\\\{\\begin\{array\}\[\]\{ll\}1&\\ \\text\{$X$ is true\}\\\\ 0&\\ \\text\{$X$ is false\}\\end\{array\}\\right\.\.\(A\.29\)Lastly, we will sometimes refer to a vectorx∈𝔽2nx\\in\\mathbb\{F\}\_\{2\}^\{n\}interchangably withI⊂\[n\]I\\subset\[n\]defined byI:=\{i∈\[n\]:xi=1\}I:=\\\{i\\in\[n\]:x\_\{i\}=1\\\}\. So the statementI∈𝔽2nI\\in\\mathbb\{F\}\_\{2\}^\{n\}, and similar statements, should be understood in this light\.

Consider a vector spaceVVover the two\-element field𝔽2=\{0,1\}\\mathbb\{F\}\_\{2\}=\\\{0,1\\\}, defined by addition and multiplication mod 2\. The mod 2 will always be implicit when it is clear from context that operations are done over𝔽2\\mathbb\{F\}\_\{2\}\. A useful representation ofV≅𝔽2kV\\cong\\mathbb\{F\}\_\{2\}^\{k\}will be given by the following proposition, which summarizes basic facts about linear algebra over finite fields:

###### Proposition A\.1:

Define a matrixG∈𝔽2k×nG\\in\\mathbb\{F\}\_\{2\}^\{k\\times n\}such that

V=im⁡\(G𝖳\),V=\\mathrm\{im\}\(G^\{\\mathsf\{T\}\}\),\(A\.30\)namely the rows ofGGare linearly independent generators ofV⊂𝔽2nV\\subset\\mathbb\{F\}\_\{2\}^\{n\}\. Then there exists a \(non\-unique\) matrixH∈𝔽2m×nH\\in\\mathbb\{F\}\_\{2\}^\{m\\times n\}withm≥n−km\\geq n\-ksuch thatH​G𝖳=0HG^\{\\mathsf\{T\}\}=0, and

ker⁡\(H\)=im⁡\(G𝖳\)\.\\ker\(H\)=\\mathrm\{im\}\(G^\{\\mathsf\{T\}\}\)\.\(A\.31\)We will denoteV=ker⁡\(H\)V=\\ker\(H\)andV⟂:=im⁡\(H𝖳\)V^\{\\perp\}:=\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\.222Note that on𝔽2\\mathbb\{F\}\_\{2\},V∩V⟂V\\cap V^\{\\perp\}can be non\-empty\.

###### Definition A\.2\(Canonical form\):

By Gaussian elimination we can always find a canonical form for the generator matrixGGand parity\-check matrixHH:

G\\displaystyle G=\(Ik×kA\),\\displaystyle=\\left\(\\begin\{array\}\[\]\{cc\}I\_\{k\\times k\}&\\ A\\end\{array\}\\right\),H\\displaystyle H=\(A𝖳I\(n−k\)×\(n−k\)\),\\displaystyle=\\left\(\\begin\{array\}\[\]\{cc\}A^\{\\mathsf\{T\}\}&\\ I\_\{\(n\-k\)\\times\(n\-k\)\}\\end\{array\}\\right\),HereAAis ak×\(n−k\)k\\times\(n\-k\)matrix\. Notice that a canonical form ofHHneed not be sparse, even if there exists a sparse representation ofHH\.

### A\.2Useful properties

The following observation is crucial to our subsequent analysis:

###### Proposition A\.3:

Letai∈𝔽2na\_\{i\}\\in\\mathbb\{F\}\_\{2\}^\{n\}\. DefineI⊆\{1,…,n\}:=\{i:ai=1\}I\\subseteq\\\{1,\\ldots,n\\\}:=\\\{i:a\_\{i\}=1\\\}and

ξIμ:=∏i∈Iξiμ\.\\xi\_\{I\}^\{\\mu\}:=\\prod\_\{i\\in I\}\\xi\_\{i\}^\{\\mu\}\.\(A\.33\)Then

12dimV​∑ξ∈VξI=\{1a∈V⟂0a∉V⟂\.\\frac\{1\}\{2^\{\\dim V\}\}\\sum\_\{\\xi\\in V\}\\xi\_\{I\}=\\left\\\{\\begin\{array\}\[\]\{ll\}1&\\ a\\in V^\{\\perp\}\\\\ 0&\\ a\\notin V^\{\\perp\}\\end\{array\}\\right\.\.\(A\.34\)Hereξ∈V\\xi\\in Vis understood via the mapping \([8](https://arxiv.org/html/2610.27384#S3.E8)\)\.

###### Proof\.

Observe that

ξI=\(−1\)∑i=1nai​bi\.\\xi\_\{I\}=\(\-1\)^\{\\sum\_\{i=1\}^\{n\}a\_\{i\}b\_\{i\}\}\.\(A\.35\)Ifb∈im⁡\(HT\)=V⟂b\\in\\mathrm\{im\}\(H^\{T\}\)=V^\{\\perp\}, thenb⋅a=0b\\cdot a=0for everyb∈ker⁡\(H\)=Vb\\in\\ker\(H\)=V, establishing the first line of our identity\.

As for the second line, ifa∉im⁡\(H𝖳\)=ker⁡\(G\)a\\notin\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)=\\ker\(G\)then by definition there existsc∈V=im⁡\(G𝖳\)c\\in V=\\mathrm\{im\}\(G^\{\\mathsf\{T\}\}\)such thatc⋅b=1c\\cdot b=1\. For eachbbin the sum \([A\.34](https://arxiv.org/html/2610.27384#A1.E34)\), it is paired with a unique partnerb\+cb\+cin the sum \(sincec\+\(c\+b\)=bc\+\(c\+b\)=b\), and\(−1\)a⋅b\+\(−1\)a⋅\(b\+c\)=0\(\-1\)^\{a\\cdot b\}\+\(\-1\)^\{a\\cdot\(b\+c\)\}=0\. Summing over all such pairs of partners establishes the second line of \([A\.34](https://arxiv.org/html/2610.27384#A1.E34)\)\. ∎

###### Proposition A\.4:

Let\{wa\}a=1q\\\{w\_\{a\}\\\}\_\{a=1\}^\{q\}be linearly independent non\-trivial cosets in𝔽2n/im⁡\(H𝖳\)\\mathbb\{F\}\_\{2\}^\{n\}/\\operatorname\{im\}\(H^\{\\mathsf\{T\}\}\)\. Then there exist linearly independent codewords\{va\}a=1q⊂ker⁡\(H\)\\\{v\_\{a\}\\\}\_\{a=1\}^\{q\}\\subset\\ker\(H\)such that

wa⋅va′=δa​a′\.w\_\{a\}\\cdot v\_\{a^\{\\prime\}\}=\\delta\_\{aa^\{\\prime\}\}\.\(A\.36\)

###### Proof\.

First look for av1v\_\{1\}such thatw1⋅v~1=1w\_\{1\}\\cdot\\tilde\{v\}\_\{1\}=1\. If such av~1\\tilde\{v\}\_\{1\}did not exist, thenw1∈ker⁡\(H\)w\_\{1\}\\in\\ker\(H\)contradicting our assumptions\. Similarly, we construct candidatev~a\\tilde\{v\}\_\{a\}\. If it was not possible to chooseqqlinearly independentv~a\\tilde\{v\}\_\{a\}, then there would exist some combination ofwaw\_\{a\}which was orthogonal to every possible codeword, in violation of the assumption that thewaw\_\{a\}were independent\. Once we have foundqqlinearly independentv~a\\tilde\{v\}\_\{a\}, we can do Gaussian elimination to find an invertible matrixMa​bM\_\{ab\}such thatva=Ma​b​v~bv\_\{a\}=M\_\{ab\}\\tilde\{v\}\_\{b\}\. ∎

### A\.3Random expander codes

In this subsection, we will review established facts about random expander codes\[[13](https://arxiv.org/html/2610.27384#bib.bib13)\], emphasizing points which are relevant for our discussion\. Its purpose is just to summarize the key properties of random codes which provide provable guarantees on efficient learning of TDenseAM for the remainder of the paper\. The reader should feel free to only refer to this section as results are referenced below\.

###### Definition A\.5\(\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)\-LDPC codes\):

A\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)\-LDPC code corresponds to parity\-check matrixHHfor which each row has Hamming weightΔC\\Delta\_\{\\mathrm\{C\}\}and each column has Hamming weightΔB\\Delta\_\{\\mathrm\{B\}\}\.333Often, we will choosem=ΔCm=\\Delta\_\{\\mathrm\{C\}\}, becauseΔC\\Delta\_\{\\mathrm\{C\}\}will be the natural order of interactions to learn in the dense associative memory\!In other words, each bit connects toΔB\\Delta\_\{\\mathrm\{B\}\}checks, and each check connects toΔC\\Delta\_\{\\mathrm\{C\}\}bits\. It is often useful to define a set of bitsBBand checksCC; in the previous discussion we had informally usedB=\{1,…,n\}B=\\\{1,\\ldots,n\\\}\. Given a subset of bitsB0⊆BB\_\{0\}\\subseteq B, we define its boundary

\{c∈C:Hc​b=1​for some​b∈B0\}=:∂B0⊆C\.\\\{c\\in C:H\_\{cb\}=1\\text\{ for some \}b\\in B\_\{0\}\\\}=:\\partial B\_\{0\}\\subseteq C\.\(A\.37\)An analogous definition \(withH→H𝖳H\\rightarrow H^\{\\mathsf\{T\}\}\) holds for the boundary of a check set\.

It is actually quite easy to generate these codes randomly due to a clever algorithm known as the configuration model\[[30](https://arxiv.org/html/2610.27384#bib.bib30)\]: one simply generates random candidate codes and rejects them if they are “bad” – this will succeed with high probability after only a finite number of attempts, even asn→∞n\\rightarrow\\infty\. We summarize the result without proof below:

###### Theorem A\.6:

Propose a\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)\-LDPC code by randomly connecting each bit to a checkΔB\\Delta\_\{\\mathrm\{B\}\}times, and stopping if the check has more thanΔC\\Delta\_\{\\mathrm\{C\}\}edges\. The probability that there is at least one bit/check pair that are connected more than once is, asn→∞n\\rightarrow\\infty, at most1−e−\(ΔB−1\)\(ΔC−1\)/21\-\\mathrm\{e\}^\{\-\(\\Delta\_\{\\mathrm\{B\}\}\-1\)\(\\Delta\_\{\\mathrm\{C\}\}\-1\)/2\}\[[31](https://arxiv.org/html/2610.27384#bib.bib31)\]\.

We will use this simple generation algorithm below to prove some very useful facts about random LDPC codes\. A key property about random codes is that they are expander codes, as defined below:

###### Definition A\.7\(Left/right\-expansion\):

A code has\(γ,δ\)\(\\gamma,\\delta\)\-left expansion if, for every set of bitsB0⊂BB\_\{0\}\\subset Bwith\|B0\|<γ​n\|B\_\{0\}\|<\\gamma n,\|∂B0\|≥ΔB​\(1−δ\)​\|B0\|\|\\partial B\_\{0\}\|\\geq\\Delta\_\{\\mathrm\{B\}\}\(1\-\\delta\)\|B\_\{0\}\|\. It has\(γ,δ\)\(\\gamma,\\delta\)\-right expansion if the analogous property holds for checks:\|∂C0\|≥ΔC​\(1−δ\)​\|C0\|\|\\partial C\_\{0\}\|\\geq\\Delta\_\{\\mathrm\{C\}\}\(1\-\\delta\)\|C\_\{0\}\|\. If both hold, the code has\(γ,δ\)\(\\gamma,\\delta\)\-expansion\.

###### Proposition A\.8\(Unique\-neighbor expansion\):

Given a code\(B,C\)\(B,C\)with\(γ,δ\)\(\\gamma,\\delta\)\-expansion, consider anyB0⊂BB\_\{0\}\\subset Bwith\|B0\|<γ​n\|B\_\{0\}\|<\\gamma n\. Let∂uB0⊂C\\partial\_\{\\mathrm\{u\}\}B\_\{0\}\\subset Cbe the number of unique\-neighbor checks which connect only to a single bit inB0B\_\{0\}:

∂uB0:=\{c∈C:\|∂c∩B0\|=1\}\.\\partial\_\{\\mathrm\{u\}\}B\_\{0\}:=\\\{c\\in C:\|\\partial c\\cap B\_\{0\}\|=1\\\}\.\(A\.38\)Then

\|∂uB0\|≥\(1−2​δ\)​ΔB​\|B0\|\.\|\\partial\_\{\\mathrm\{u\}\}B\_\{0\}\|\\geq\(1\-2\\delta\)\\Delta\_\{\\mathrm\{B\}\}\|B\_\{0\}\|\.\(A\.39\)

###### Proof\.

The number of edges between bits inB0B\_\{0\}and checks inCCis given byΔB​\|B0\|\\Delta\_\{\\mathrm\{B\}\}\|B\_\{0\}\|\. By Definition[A\.7](https://arxiv.org/html/2610.27384#A1.Thmthm7), there are edges toΔB​\(1−δ\)​\|B0\|\\Delta\_\{\\mathrm\{B\}\}\(1\-\\delta\)\|B\_\{0\}\|checks\. Comparing the total number of edges to the total number of edges to unique checks, vs\. edges to non\-unique checks, we see that

ΔB​\|B0\|≥\|∂uB0\|\+2​\(ΔB​\(1−δ\)​\|B0\|−\|∂uB0\|\),\\Delta\_\{\\mathrm\{B\}\}\|B\_\{0\}\|\\geq\|\\partial\_\{\\mathrm\{u\}\}B\_\{0\}\|\+2\\left\(\\Delta\_\{\\mathrm\{B\}\}\(1\-\\delta\)\|B\_\{0\}\|\-\|\\partial\_\{\\mathrm\{u\}\}B\_\{0\}\|\\right\),\(A\.40\)which implies \([A\.39](https://arxiv.org/html/2610.27384#A1.E39)\)\. ∎

###### Corollary A\.9:

For anyxxwith\|x\|≤γ​n\|x\|\\leq\\gamma n, a code with\(γ,δ\)\(\\gamma,\\delta\)expansion has

\|H​x\|≥ΔB​\(1−2​δ\)​\|x\|\.\|Hx\|\\geq\\Delta\_\{\\mathrm\{B\}\}\(1\-2\\delta\)\|x\|\.\(A\.41\)The code distanced≥γ​nd\\geq\\gamma n\.444This is not an optimal bound, but it suffices for our conceptual purposes in this paper – namely, establishing that the code distance can beO⁡\(n\)\\mathrm\{O\}\(n\)whenever we can establish expansion\.

###### Proof\.

These are immediate consequences of Proposition[A\.8](https://arxiv.org/html/2610.27384#A1.Thmthm8)\. Any check in∂uB0\\partial\_\{\\mathrm\{u\}\}B\_\{0\}must be violated, so \([A\.41](https://arxiv.org/html/2610.27384#A1.E41)\) follows from \([A\.39](https://arxiv.org/html/2610.27384#A1.E39)\)\. Since\|H​x\|=0\|Hx\|=0on any codeword, ifx∈ker⁡\(H\)x\\in\\ker\(H\)eitherx=0x=0or\|x\|\>γ​n\|x\|\>\\gamma n\. ∎

###### Corollary A\.10:

In the setting of Proposition[A\.8](https://arxiv.org/html/2610.27384#A1.Thmthm8), we are guaranteed that there existsb∈B0b\\in B\_\{0\}with\|∂b∩∂uB0\|≥m\|\\partial b\\cap\\partial\_\{\\mathrm\{u\}\}B\_\{0\}\|\\geq mwhenever

δ<1\+ΔB−m2​ΔB\.\\delta<\\frac\{1\+\\Delta\_\{\\mathrm\{B\}\}\-m\}\{2\\Delta\_\{\\mathrm\{B\}\}\}\.\(A\.42\)

###### Proof\.

From \([A\.39](https://arxiv.org/html/2610.27384#A1.E39)\), the average number of unique\-neighbor checks in∂B0\\partial B\_\{0\}isΔB​\(1−2​δ\)\\Delta\_\{\\mathrm\{B\}\}\(1\-2\\delta\)\. IfΔB​\(1−2​δ\)\>m−1\\Delta\_\{\\mathrm\{B\}\}\(1\-2\\delta\)\>m\-1, there must be at least one bit with\|∂b∩∂uB0\|≥m\|\\partial b\\cap\\partial\_\{\\mathrm\{u\}\}B\_\{0\}\|\\geq m\. Hence we find \([A\.42](https://arxiv.org/html/2610.27384#A1.E42)\)\. ∎

The existence of useful codes is established by the following theorem, which we state without proof, although we do note that the bound onkkcomes directly from the rank\-nullity theorem on𝔽2\\mathbb\{F\}\_\{2\}, and the techniques are similar to those discussed at the end of this subsection\.

###### Theorem A\.11:

TakeΔB<ΔC\\Delta\_\{\\mathrm\{B\}\}<\\Delta\_\{\\mathrm\{C\}\}\. Choose a\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)\-LDPC code uniformly at random via the configuration model \(Theorem[A\.6](https://arxiv.org/html/2610.27384#A1.Thmthm6)\)\. Then the code has a linear number of logical bits:

k=n⁡\(1−ΔBΔC\)\+\{1ΔB​even0ΔB​odd,k=n\\left\(1\-\\frac\{\\Delta\_\{\\mathrm\{B\}\}\}\{\\Delta\_\{\\mathrm\{C\}\}\}\\right\)\+\\left\\\{\\begin\{array\}\[\]\{ll\}1&\\ \\Delta\_\{\\mathrm\{B\}\}\\text\{ even\}\\\\ 0&\\ \\Delta\_\{\\mathrm\{B\}\}\\text\{ odd\}\\end\{array\}\\right\.,\(A\.43\)and with probability1−O⁡\(n1−δ​ΔB\)1\-\\mathrm\{O\}\(n^\{1\-\\delta\\Delta\_\{\\mathrm\{B\}\}\}\), the code is a\(γ,δ\)\(\\gamma,\\delta\)\-expander for anyδ\>1/ΔB\\delta\>1/\\Delta\_\{\\mathrm\{B\}\}and any0<γ<γmax0<\\gamma<\\gamma\_\{\\mathrm\{max\}\}, whereγmax\\gamma\_\{\\mathrm\{max\}\}solves

\(1−1ΔB\)​h​\(γmax\)=1ΔC​h​\(ΔC​\(1−δ\)​γmax\)\+ΔC​γmax​h​\(1ΔC​\(1−δ\)\)\\left\(1\-\\frac\{1\}\{\\Delta\_\{\\mathrm\{B\}\}\}\\right\)h\(\\gamma\_\{\\mathrm\{max\}\}\)=\\frac\{1\}\{\\Delta\_\{\\mathrm\{C\}\}\}h\(\\Delta\_\{\\mathrm\{C\}\}\(1\-\\delta\)\\gamma\_\{\\mathrm\{max\}\}\)\+\\Delta\_\{\\mathrm\{C\}\}\\gamma\_\{\\mathrm\{max\}\}h\\left\(\\frac\{1\}\{\\Delta\_\{\\mathrm\{C\}\}\(1\-\\delta\)\}\\right\)\(A\.44\)with

h⁡\(x\):=−x​log⁡x−\(1−x\)​log⁡\(1−x\)\.h\(x\):=\-x\\log x\-\(1\-x\)\\log\(1\-x\)\.\(A\.45\)

Lastly, the following result tells us that the interaction graph of a random LDPC code does not contain very many interesting small subgraphs, with very high probability\. In other words, random LDPC codes look locally tree\-like\.

###### Proposition A\.12:

LetGGbe a bipartite graph withV0V\_\{0\}vertices andE0E\_\{0\}edges, withV0V\_\{0\}andE0E\_\{0\}O⁡\(1\)\\mathrm\{O\}\(1\)constants\. Pick a\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC code uniformly at random, and letNGN\_\{G\}be the number of subgraphs isomorphic toGG\. Asn→∞n\\rightarrow\\infty, there exists a constantC<∞C<\\inftysuch that

𝔼⁡\[NG\]≤C​nV0−E0\.\\mathbb\{E\}\[N\_\{G\}\]\\leq Cn^\{V\_\{0\}\-E\_\{0\}\}\.\(A\.46\)In words, there are a finite number of short cycles in an LDPC code, and these cycles are all far from each other\.

###### Proof\.

We can use Theorem[A\.6](https://arxiv.org/html/2610.27384#A1.Thmthm6)to constrain the properties of a random LDPC code: suppose that a random pairing of bits and checks has propertyXXwith probabilityℙbare​\(X\)\\mathbb\{P\}\_\{\\text\{bare\}\}\(X\)\. Then, lettingq=e−\(ΔB−1\)\(ΔC−1\)/2q=\\mathrm\{e\}^\{\-\(\\Delta\_\{\\mathrm\{B\}\}\-1\)\(\\Delta\_\{\\mathrm\{C\}\}\-1\)/2\}, the probability the event happens on an actual LDPC code must obey

ℙLDPC​\(X\)​q\+ℙnot LDPC​\(X\)​\(1−q\)=ℙbare​\(X\),\\mathbb\{P\}\_\{\\mathrm\{LDPC\}\}\(X\)q\+\\mathbb\{P\}\_\{\\text\{not LDPC\}\}\(X\)\(1\-q\)=\\mathbb\{P\}\_\{\\text\{bare\}\}\(X\),\(A\.47\)meaning that

ℙLDPC​\(X\)≥ℙbare​\(X\)q\.\\mathbb\{P\}\_\{\\mathrm\{LDPC\}\}\(X\)\\geq\\frac\{\\mathbb\{P\}\_\{\\text\{bare\}\}\(X\)\}\{q\}\.\(A\.48\)Now, in the configuration model, it is very easy to bound the probability of seeing a subgraphGG\. If we demanded that the subgraph\{1,…,m0\}⊂B\\\{1,\\ldots,m\_\{0\}\\\}\\subset Band\{m0\+1,…,V0\}⊂C0\\\{m\_\{0\}\+1,\\ldots,V\_\{0\}\\\}\\subset C\_\{0\}was isomorphic toGG, this would occur with probability

ℙ⁡\(G∼\{1,…,m0\}∪\{m0\+1,…,V0\}\)=∏j=0E0−11ΔB​n−j<\(ΔB​n−E0\)−E0\.\\mathbb\{P\}\\left\(G\\sim\\\{1,\\ldots,m\_\{0\}\\\}\\cup\\\{m\_\{0\}\+1,\\ldots,V\_\{0\}\\\}\\right\)=\\prod\_\{j=0\}^\{E\_\{0\}\-1\}\\frac\{1\}\{\\Delta\_\{\\mathrm\{B\}\}n\-j\}<\(\\Delta\_\{\\mathrm\{B\}\}n\-E\_\{0\}\)^\{\-E\_\{0\}\}\.\(A\.49\)Now enumerating over the total number of possible such subgraphs, we bound

𝔼⁡\[NG\]<nm0\(ΔB​n−E0\)E0​\(ΔBΔC​n\)V0−m0<q​C​nV0−E0\\mathbb\{E\}\[N\_\{G\}\]<\\frac\{n^\{m\_\{0\}\}\}\{\(\\Delta\_\{\\mathrm\{B\}\}n\-E\_\{0\}\)^\{E\_\{0\}\}\}\\left\(\\frac\{\\Delta\_\{\\mathrm\{B\}\}\}\{\\Delta\_\{\\mathrm\{C\}\}\}n\\right\)^\{V\_\{0\}\-m\_\{0\}\}<qCn^\{V\_\{0\}\-E\_\{0\}\}\(A\.50\)for someC<∞C<\\infty\. Combining \([A\.48](https://arxiv.org/html/2610.27384#A1.E48)\) and \([A\.50](https://arxiv.org/html/2610.27384#A1.E50)\) we obtain \([A\.46](https://arxiv.org/html/2610.27384#A1.E46)\)\. ∎

The remaining results in this section are a collection of scattered but useful facts about expander codes, which will be useful in establishing how TDenseAM trains on random codes\.

###### Theorem A\.13:

Pick a\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC code uniformly at random with2<ΔB<ΔC2<\\Delta\_\{\\mathrm\{B\}\}<\\Delta\_\{\\mathrm\{C\}\}\. If there aremmchecks, takes∈𝔽2ms\\in\\mathbb\{F\}\_\{2\}^\{m\}and define

\|s\|red:=\{\|s\|ΔB​oddmin⁡\(\|s\|,m−\|s\|\)ΔB​even\.\|s\|\_\{\\mathrm\{red\}\}:=\\left\\\{\\begin\{array\}\[\]\{ll\}\|s\|&\\ \\Delta\_\{\\mathrm\{B\}\}\\text\{ odd\}\\\\ \\min\(\|s\|,m\-\|s\|\)&\\ \\Delta\_\{\\mathrm\{B\}\}\\text\{ even\}\\end\{array\}\\right\.\.\(A\.51\)Then almost surely asn→∞n\\rightarrow\\infty, every vectorssobeys

\|H𝖳​s\|≥κ​\|s\|red\|H^\{\\mathsf\{T\}\}s\|\\geq\\kappa\|s\|\_\{\\mathrm\{red\}\}\(A\.52\)for someO⁡\(1\)\\mathrm\{O\}\(1\)constantκ\>0\\kappa\>0\. This property is known ascheck soundness\.

###### Proof\.

Theorem[A\.11](https://arxiv.org/html/2610.27384#A1.Thmthm11)shows that the dimension of the codespace is minimal – up to a sole redundant check whenΔB\\Delta\_\{\\mathrm\{B\}\}is even, all of the checks are independent\. This redundancy is what requires us to look at the reduced\|s\|red\|s\|\_\{\\mathrm\{red\}\}weight in the even case\.

The desired property follows immediately from Definition[A\.7](https://arxiv.org/html/2610.27384#A1.Thmthm7)if\|s\|<γ​n\|s\|<\\gamma n, so we only need to consider the case where\|s\|\>γ​n\|s\|\>\\gamma n\. Here, we follow the same strategy as the proof of Proposition[A\.12](https://arxiv.org/html/2610.27384#A1.Thmthm12)\. Since\|s\|\>γ​n\|s\|\>\\gamma n, each bit sees one of its edges connected to a check insswith probability no smaller thanp:=ΔB​γp:=\\Delta\_\{\\mathrm\{B\}\}\\gamma\. Our goal is to bound the bare probability that exactlyK:=κ​\|s\|redK:=\\kappa\|s\|\_\{\\mathrm\{red\}\}bits have an*odd*number of edges connecting toss\.

We can use the method of generating functions to bound this\. Define the odd and even parts of the binomial distribution:

Beven​\(z\)\\displaystyle B\_\{\\mathrm\{even\}\}\(z\):=∑j​even\(ΔBj\)​zj,\\displaystyle:=\\sum\_\{j\\text\{ even\}\}\\left\(\\begin\{array\}\[\]\{c\}\\Delta\_\{\\mathrm\{B\}\}\\\\ j\\end\{array\}\\right\)z^\{j\},Bodd​\(z\)\\displaystyle B\_\{\\mathrm\{odd\}\}\(z\):=∑j​odd\(ΔBj\)​zj\.\\displaystyle:=\\sum\_\{j\\text\{ odd\}\}\\left\(\\begin\{array\}\[\]\{c\}\\Delta\_\{\\mathrm\{B\}\}\\\\ j\\end\{array\}\\right\)z^\{j\}\.Then define

G⁡\(z\):=∑n=0∞Gn​zn:=Beven​\(z\)n−K​Bodd​\(z\)K\.G\(z\):=\\sum\_\{n=0\}^\{\\infty\}G\_\{n\}z^\{n\}:=B\_\{\\text\{even\}\}\(z\)^\{n\-K\}B\_\{\\text\{odd\}\}\(z\)^\{K\}\.\(A\.54\)In the random generating model of Theorem[A\.6](https://arxiv.org/html/2610.27384#A1.Thmthm6), we see that

ℙbare​\(K​odd degree bits\)\\displaystyle\\mathbb\{P\}\_\{\\text\{bare\}\}\(K\\text\{ odd degree bits\}\)=\(nK\)​\(ΔB​n/ΔC\|s\|\)​\(ΔB​nΔC​\|s\|\)−1​GΔC​\|s\|\\displaystyle=\\left\(\\begin\{array\}\[\]\{c\}n\\\\ K\\end\{array\}\\right\)\\left\(\\begin\{array\}\[\]\{c\}\\Delta\_\{\\mathrm\{B\}\}n/\\Delta\_\{\\mathrm\{C\}\}\\\\ \|s\|\\end\{array\}\\right\)\\left\(\\begin\{array\}\[\]\{c\}\\Delta\_\{\\mathrm\{B\}\}n\\\\ \\Delta\_\{\\mathrm\{C\}\}\|s\|\\end\{array\}\\right\)^\{\-1\}G\_\{\\Delta\_\{\\mathrm\{C\}\}\|s\|\}≤\(nK\)​\(ΔB​n/ΔC\|s\|\)​\(ΔB​nΔC​\|s\|\)−1​infz\(z−ΔC​\|s\|​G​\(z\)\)\.\\displaystyle\\leq\\left\(\\begin\{array\}\[\]\{c\}n\\\\ K\\end\{array\}\\right\)\\left\(\\begin\{array\}\[\]\{c\}\\Delta\_\{\\mathrm\{B\}\}n/\\Delta\_\{\\mathrm\{C\}\}\\\\ \|s\|\\end\{array\}\\right\)\\left\(\\begin\{array\}\[\]\{c\}\\Delta\_\{\\mathrm\{B\}\}n\\\\ \\Delta\_\{\\mathrm\{C\}\}\|s\|\\end\{array\}\\right\)^\{\-1\}\\inf\_\{z\}\\left\(z^\{\-\\Delta\_\{\\mathrm\{C\}\}\|s\|\}G\(z\)\\right\)\.Let\|s\|=η​n\|s\|=\\eta n; note thatγ<η≤ΔB/ΔC\\gamma<\\eta\\leq\\Delta\_\{\\mathrm\{B\}\}/\\Delta\_\{\\mathrm\{C\}\}\. Notice that asn→∞n\\rightarrow\\infty,

1n​log​infz\(z−ΔC​\|s\|​G​\(z\)\)=infz\(log⁡Beven​\(z\)−ΔC​η​log​z\)\.\\frac\{1\}\{n\}\\log\\inf\_\{z\}\\left\(z^\{\-\\Delta\_\{\\mathrm\{C\}\}\|s\|\}G\(z\)\\right\)=\\inf\_\{z\}\\left\(\\log B\_\{\\text\{even\}\}\(z\)\-\\Delta\_\{\\mathrm\{C\}\}\\eta\\log z\\right\)\.\(A\.67\)Observe thatBeven​\(z\)≤\(1\+zΔB/\(ΔB−1\)\)ΔB−1B\_\{\\text\{even\}\}\(z\)\\leq\(1\+z^\{\\Delta\_\{\\mathrm\{B\}\}/\(\\Delta\_\{\\mathrm\{B\}\}\-1\)\}\)^\{\\Delta\_\{\\mathrm\{B\}\}\-1\}\. Standard manipulations then reveal that

infz\(log⁡Beven​\(z\)−ΔC​η​log⁡z\)\\displaystyle\\inf\_\{z\}\\left\(\\log B\_\{\\text\{even\}\}\(z\)\-\\Delta\_\{\\mathrm\{C\}\}\\eta\\log z\\right\)=\(ΔB−1\)​infu\(log⁡\(1\+u\)−ΔC​ηΔB​log⁡u\)\\displaystyle=\(\\Delta\_\{\\mathrm\{B\}\}\-1\)\\inf\_\{u\}\\left\(\\log\(1\+u\)\-\\frac\{\\Delta\_\{\\mathrm\{C\}\}\\eta\}\{\\Delta\_\{\\mathrm\{B\}\}\}\\log u\\right\)=\(ΔB−1\)​h​\(ΔC​ηΔB\),\\displaystyle=\(\\Delta\_\{\\mathrm\{B\}\}\-1\)h\\left\(\\frac\{\\Delta\_\{\\mathrm\{C\}\}\\eta\}\{\\Delta\_\{\\mathrm\{B\}\}\}\\right\),\(A\.68\)recalling the definiton ofh⁡\(x\)h\(x\)in \([A\.45](https://arxiv.org/html/2610.27384#A1.E45)\)\. We see that asn→∞n\\rightarrow\\infty,

ℙbare​\(K​odd degree bits\)≤en⁡\[h⁡\(κ\)−ψ\]\\mathbb\{P\}\_\{\\text\{bare\}\}\(K\\text\{ odd degree bits\}\)\\leq\\mathrm\{e\}^\{n\[h\(\\kappa\)\-\\psi\]\}\(A\.69\)where

ψ=\[ΔB​\(1−1ΔC\)−\(ΔB−1\)\]​h​\(ΔC​ηΔB\)=\(1−ΔBΔC\)​h​\(ΔC​ηΔB\)\>0\.\\psi=\\left\[\\Delta\_\{\\mathrm\{B\}\}\\left\(1\-\\frac\{1\}\{\\Delta\_\{\\mathrm\{C\}\}\}\\right\)\-\(\\Delta\_\{\\mathrm\{B\}\}\-1\)\\right\]h\\left\(\\frac\{\\Delta\_\{\\mathrm\{C\}\}\\eta\}\{\\Delta\_\{\\mathrm\{B\}\}\}\\right\)=\\left\(1\-\\frac\{\\Delta\_\{\\mathrm\{B\}\}\}\{\\Delta\_\{\\mathrm\{C\}\}\}\\right\)h\\left\(\\frac\{\\Delta\_\{\\mathrm\{C\}\}\\eta\}\{\\Delta\_\{\\mathrm\{B\}\}\}\\right\)\>0\.\(A\.70\)Choose anyκ\\kappaobeyingh⁡\(κ\)<ψh\(\\kappa\)<\\psi\. Combining \([A\.48](https://arxiv.org/html/2610.27384#A1.E48)\) and \([A\.69](https://arxiv.org/html/2610.27384#A1.E69)\), the probability of violating \([A\.52](https://arxiv.org/html/2610.27384#A1.E52)\) vanishes exponentially asn→∞n\\rightarrow\\infty\. ∎

###### Corollary A\.14:

In a random\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC code with2<ΔB<ΔC2<\\Delta\_\{\\mathrm\{B\}\}<\\Delta\_\{\\mathrm\{C\}\}, almost surely asn→∞n\\rightarrow\\infty, there are no non\-zero elements ofim⁡\(H𝖳\)\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)with Hamming weight smaller thanΔC\\Delta\_\{\\mathrm\{C\}\}\. Moreover, the number of distinct weightΔC\\Delta\_\{\\mathrm\{C\}\}checks is almost surely given by

𝒩m=\(1\+o⁡\(1\)\)​ΔBΔC​n\.\\mathcal\{N\}\_\{m\}=\(1\+\\mathrm\{o\}\(1\)\)\\frac\{\\Delta\_\{\\mathrm\{B\}\}\}\{\\Delta\_\{\\mathrm\{C\}\}\}n\.\(A\.71\)

###### Proof\.

By Theorem[A\.13](https://arxiv.org/html/2610.27384#A1.Thmthm13), it suffices to look at small combinations of checks with\|s\|<K′\|s\|<K^\{\\prime\}, where we can then apply the expansion guarantee of Theorem[A\.11](https://arxiv.org/html/2610.27384#A1.Thmthm11)\. For anyδ\>1/ΔB\\delta\>1/\\Delta\_\{\\mathrm\{B\}\}, we know that\|H𝖳​s\|≥ΔC​\(1−2​δ\)​\|s\|\|H^\{\\mathsf\{T\}\}s\|\\geq\\Delta\_\{\\mathrm\{C\}\}\(1\-2\\delta\)\|s\|\. SinceΔB≥3\\Delta\_\{\\mathrm\{B\}\}\\geq 3, we can chooseδ\\deltaarbitarily close to1/31/3\. So if\|s\|≥3\|s\|\\geq 3, the claim is established\.

Thus let us discuss the case of\|s\|=2\|s\|=2, as\|s\|=1\|s\|=1follows analogously\. Here we can apply Proposition[A\.12](https://arxiv.org/html/2610.27384#A1.Thmthm12)\. For anyΔC≥4\\Delta\_\{\\mathrm\{C\}\}\\geq 4, to find a check of weight smaller thanΔC\\Delta\_\{\\mathrm\{C\}\}, we would need to find a subgraph of the Tanner graph \(Figure[1](https://arxiv.org/html/2610.27384#S3.F1)\) isomorphic to two bits connected to≥3\\geq 3checks, one check connected to the same bit≥3\\geq 3times, etc\.: any graph that contains≥2\\geq 2independent cycles, namely hasV0<E0V\_\{0\}<E\_\{0\}; almost surely such a graph never appears\. There are a finite number of such graphs to verify below a fixed number of checks \(supplied by Theorem[A\.13](https://arxiv.org/html/2610.27384#A1.Thmthm13)\), so the probability any one of them fails vanishes asn→∞n\\rightarrow\\inftyby a union bound\.

Finally, let us verify that the number of checks of weightΔC\\Delta\_\{\\mathrm\{C\}\}isΘ⁡\(n\)\\mathrm\{\\Theta\}\(n\)\. We have at leastΔB​n/ΔC\\Delta\_\{\\mathrm\{B\}\}n/\\Delta\_\{\\mathrm\{C\}\}checks by the construction of the code\. Similar to the previous paragraph, we need at least a cycle of length 4 in the Tanner graph to find any redundant checks\. Proposition[A\.12](https://arxiv.org/html/2610.27384#A1.Thmthm12)shows that the expected number of such cycles isΘ⁡\(1\)\\mathrm\{\\Theta\}\(1\); applying Markov’s inequality completes the proof\. ∎

###### Corollary A\.15:

In a random\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC code with parity\-check matrixHHand2<ΔB<ΔC2<\\Delta\_\{\\mathrm\{B\}\}<\\Delta\_\{\\mathrm\{C\}\}, almost surely asn→∞n\\rightarrow\\infty,

𝒩r:=\|\{w∈im⁡\(H𝖳\):\|w\|=r\}\|=o⁡\(nr/2\)\\mathcal\{N\}\_\{r\}:=\|\\\{w\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\):\|w\|=r\\\}\|=\\mathrm\{o\}\\left\(n^\{r/2\}\\right\)\(A\.72\)for anyO⁡\(1\)\\mathrm\{O\}\(1\)rr\.

###### Proof\.

Again, Theorem[A\.11](https://arxiv.org/html/2610.27384#A1.Thmthm11)and Theorem[A\.13](https://arxiv.org/html/2610.27384#A1.Thmthm13)imply we need only worry about combinations of O\(1\) checks whenΔB\>2\\Delta\_\{\\mathrm\{B\}\}\>2, as the code is an expander code\. We then apply Proposition[A\.12](https://arxiv.org/html/2610.27384#A1.Thmthm12)\. Suppose we have a candidate subgraph of the Tanner graph containingsschecks in setS0S\_\{0\}, where we include every edge \(and corresponding bit∈∂S0\\in\\partial S\_\{0\}\) in the subgraph\. If this set of checks gave us a word of weightrrinim⁡\(H𝖳\)\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\), we would have at most12​\(ΔC​s\+r\)\\frac\{1\}\{2\}\(\\Delta\_\{\\mathrm\{C\}\}s\+r\)– this would be the case if allrrbits in the word have degree 1, and all other bits in the subgraph have degree 2\. Then we have

V0−E0=s\+ΔC​s\+r2−ΔC​s=\(1−ΔC2\)​s\+r2<r−12\.V\_\{0\}\-E\_\{0\}=s\+\\frac\{\\Delta\_\{\\mathrm\{C\}\}s\+r\}\{2\}\-\\Delta\_\{\\mathrm\{C\}\}s=\\left\(1\-\\frac\{\\Delta\_\{\\mathrm\{C\}\}\}\{2\}\\right\)s\+\\frac\{r\}\{2\}<\\frac\{r\-1\}\{2\}\.\(A\.73\)By Markov’s inequality \(asNG≥0N\_\{G\}\\geq 0\), with probability at least1−n−1/41\-n^\{\-1/4\}, we see any candidate subgraph with a fixed number of checksssat mostO⁡\(nr/2−1/4\)\\mathrm\{O\}\(n^\{r/2\-1/4\}\)times\. Since there are a finite number of candidate graphs to consider, we deduce that almost surely \([A\.72](https://arxiv.org/html/2610.27384#A1.E72)\) holds\. ∎

###### Corollary A\.16:

In the setting of Corollary[A\.15](https://arxiv.org/html/2610.27384#A1.Thmthm15), a random codewordb∈ker⁡\(H\)b\\in\\ker\(H\)has Hamming weight close ton/2n/2:

limn→∞ℙ⁡\(\|\|b\|−n2\|\>n1/2\+ϵ\)=0\.\\lim\_\{n\\rightarrow\\infty\}\\mathbb\{P\}\\left\(\\left\|\|b\|\-\\frac\{n\}\{2\}\\right\|\>n^\{1/2\+\\epsilon\}\\right\)=0\.\(A\.74\)

###### Proof\.

Almost surely there are no checks of weight≤2\\leq 2\. Use the±1\\pm 1\-valuedξi\\xi\_\{i\}and evaluate

K:=∑i=1nξi=n−2​\|b\|\.K:=\\sum\_\{i=1\}^\{n\}\\xi\_\{i\}=n\-2\|b\|\.\(A\.75\)Proposition[A\.3](https://arxiv.org/html/2610.27384#A1.Thmthm3)shows that

𝔼⁡\[K2\]=n,\\mathbb\{E\}\\left\[K^\{2\}\\right\]=n,\(A\.76\)because the onlynnelements inim⁡\(H𝖳\)\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)are the trivial vectors arising from\(ξi\)2=1\(\\xi\_\{i\}\)^\{2\}=1\. \([A\.74](https://arxiv.org/html/2610.27384#A1.E74)\) follows from Chebyshev’s inequality\. ∎

###### Corollary A\.17:

In a random\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC code with2<ΔB<ΔC2<\\Delta\_\{\\mathrm\{B\}\}<\\Delta\_\{\\mathrm\{C\}\}, almost surely asn→∞n\\rightarrow\\infty, the following property holds: ifI∈im⁡\(H𝖳\)I\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)has weightΔC\\Delta\_\{\\mathrm\{C\}\}, then given a codewordx∈ker⁡\(H\)x\\in\\ker\(H\)chosen uniformly at random,

ℙ\[∑i∈Ixi=j\]=12ΔC−1\(ΔCj\)𝕀\(jis even\)\.\\mathbb\{P\}\\left\[\\sum\_\{i\\in I\}x\_\{i\}=j\\right\]=\\frac\{1\}\{2^\{\\Delta\_\{\\mathrm\{C\}\}\-1\}\}\\left\(\\begin\{array\}\[\]\{c\}\\Delta\_\{\\mathrm\{C\}\}\\\\ j\\end\{array\}\\right\)\\mathbb\{I\}\(j\\text\{ is even\}\)\.\(A\.77\)

###### Proof\.

Corollary[A\.14](https://arxiv.org/html/2610.27384#A1.Thmthm14)shows that almost surely, the only parity\-check with support inIIis the checkIIitself \(anything else would have weight smaller thanΔC\\Delta\_\{\\mathrm\{C\}\}\)\. LetπI:𝔽2n→𝔽2I\\pi\_\{I\}:\\mathbb\{F\}\_\{2\}^\{n\}\\rightarrow\\mathbb\{F\}\_\{2\}^\{I\}denote the projection onto the bits in checkII\. Notice thatπI​\(ker⁡\(H\)\)\\pi\_\{I\}\(\\ker\(H\)\)must be a vector space, sinceπI\\pi\_\{I\}is a linear map\. The dimension of this space must be exactlyΔC−1\\Delta\_\{\\mathrm\{C\}\}\-1since we have exactly one unique check in this regime\. Again by linearity, the distribution over random codewords must be uniform: if

Ww:=\{x∈ker⁡\(H\):πI​\(x\)=w\},W\_\{w\}:=\\\{x\\in\\ker\(H\):\\pi\_\{I\}\(x\)=w\\\},\(A\.78\)thenℙ⁡\(Ww1\)=ℙ⁡\(Ww1\+w2\)\\mathbb\{P\}\(W\_\{w\_\{1\}\}\)=\\mathbb\{P\}\(W\_\{w\_\{1\}\+w\_\{2\}\}\)since, for everyy∈Ww2y\\in W\_\{w\_\{2\}\}, codewordxxandx\+yx\+yare equally likely\. The uniform distribution over all vectors with an even overlap with the checkIIis given in \([A\.77](https://arxiv.org/html/2610.27384#A1.E77)\)\. ∎

## Appendix BLearning random codes

In this section, we will show that the TDenseAM architecture above learns the codewords of classical low\-density parity\-check \(LDPC\) codes efficiently\.

### B\.1How many training examples are needed?

We now describe how the TDenseAM trains on random codewords of a high rate LDPC code withk/n∼O⁡\(1\)k/n\\sim\\mathrm\{O\}\(1\)\.

The first key observation is that the TDenseAMs do correctly learn the underlying code\. In other words, the ground states ofE^\\widehat\{E\}– after training on a large enough number of patternsPP– precisely match the codewords of the input code\. Most excitingly, for any threshold – includinga=0a=0– we do*not*need to see every random codeword in order to recover all of them as local minima ofE^\\widehat\{E\}\. Bounds on a sufficient number of codewords to learn the LDPC code are provided in the following proposition:

###### Proposition B\.1:

Suppose that we train thepp\-local TDenseAM architecture with thresholda\>0a\>0onPPuniformly random codewords, from an LDPC code with≤m\\leq m\-body weights and distanced\>1d\>1\. Then if

P\>2a2​\(m​log⁡n\+log⁡2ϵ\)P\>\\frac\{2\}\{a^\{2\}\}\\left\(m\\log n\+\\log\\frac\{2\}\{\\epsilon\}\\right\)\(B\.79\)for0<ϵ<10<\\epsilon<1, we find a bijection between ground states ofE^\\widehat\{E\}and codewords inVV, with probability at least1−ϵ1\-\\epsilon\.

If we consider the usual dense associative memory \(a=0a=0\), then the lowest energy states ofE^\\widehat\{E\}are the codewords so long as555The exponent of the polynomial scaling here is not expected to be optimal, and may depend on the energy landscape of the code itself\. The key thing is that we do not expect thatP∼log⁡NP\\sim\\log Ncan ever be achieved whena=0a=0\.

P\>8​N2​m\(m−1\)\!2​\(m​log⁡N\+log⁡2ϵ\)P\>\\frac\{8N^\{2m\}\}\{\(m\-1\)\!^\{2\}\}\\left\(m\\log N\+\\log\\frac\{2\}\{\\epsilon\}\\right\)\(B\.80\)

Note that the scaling in this equation is suboptimal, if our goal is to learn an accurate representation of the overall energy landscape\. We return to that issue in Theorem[B\.12](https://arxiv.org/html/2610.27384#A2.Thmthm12)\.

###### Proof\.

We first consider the casea\>0a\>0\.E^\\widehat\{E\}is determined by the random variables

TI:=1P​∑μ=1PξIμ\.T\_\{I\}:=\\frac\{1\}\{P\}\\sum\_\{\\mu=1\}^\{P\}\\xi\_\{I\}^\{\\mu\}\.\(B\.81\)The distribution of these random variables is straightforward to see: eachTIT\_\{I\}is 1 with probability 1 ifI∈im⁡\(H𝖳\)I\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)represents a valid parity\-check \(here we have a slight abuse of notation\), while it is a binomial random variable \(an unbiased random walk withPPsteps, normalized by1/P1/P\) otherwise\. This distribution follows directly from the proof of Proposition[A\.3](https://arxiv.org/html/2610.27384#A1.Thmthm3)\. By the assumption thatHHwas generated by at mostpp\-body checks, the TDenseAM will detect every parity\-check inHH, so the remaining question is how largePPmust be before there is a high probability that\|TI\|<a\|T\_\{I\}\|<afor eachI∉im⁡\(H𝖳\)I\\notin\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\. We can easily address this question using Hoeffding’s inequality \([16](https://arxiv.org/html/2610.27384#S3.E16)\)\. By the union bound, the probability that we fail and findE^≠E\\widehat\{E\}\\neq Eis bounded by \(usingm≥2m\\geq 2\)

ℙ\[fail\]<m\(nm\)⋅2e−Pa2/2<2em​log⁡n−P​a2/2<ϵ\.\\mathbb\{P\}\[\\text\{fail\}\]<m\\left\(\\begin\{array\}\[\]\{c\}n\\\\ m\\end\{array\}\\right\)\\cdot 2\\mathrm\{e\}^\{\-Pa^\{2\}/2\}<2\\mathrm\{e\}^\{m\\log n\-Pa^\{2\}/2\}<\\epsilon\.\(B\.82\)In the last step, we used \([B\.79](https://arxiv.org/html/2610.27384#A2.E79)\) to give a bound onPP\.

The case ofa=0a=0is similar, except that we can never truly threshold away every coupling\. We can still obtain a very conservative bound as follows: there are fewer thanNm/\(m−1\)\!N^\{m\}/\(m\-1\)\!possible parity\-checks of weight≤m\\leq m\. If for eachI∉im⁡\(H𝖳\)I\\notin\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\), we find

T^I<δ0=\(m−1\)\!2​Nm,\\widehat\{T\}\_\{I\}<\\delta\_\{0\}=\\frac\{\(m\-1\)\!\}\{2N^\{m\}\},\(B\.83\)then we are guaranteed that only codewords are ground states ofE^\\widehat\{E\}\. The reason is as follows: as before,TI=1T\_\{I\}=1ifI∈im⁡\(H𝖳\)I\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\), and since each bit will be contained in at least one parity\-check \(as the distance is larger than 1\), the energy cost of an error will be positive: there will be at least one violated check, so the energy cost of any state with a violated parity\-check, relative to any codeword, will be

E^state with error−E^codeword\>\(1−Nm\(m−1\)\!​δ0\)−Nm\(m−1\)\!​δ0\>0\\widehat\{E\}\_\{\\text\{state with error\}\}\-\\widehat\{E\}\_\{\\text\{codeword\}\}\>\\left\(1\-\\frac\{N^\{m\}\}\{\(m\-1\)\!\}\\delta\_\{0\}\\right\)\-\\frac\{N^\{m\}\}\{\(m\-1\)\!\}\\delta\_\{0\}\>0\(B\.84\)using \([B\.83](https://arxiv.org/html/2610.27384#A2.E83)\)\. So we should use Hoeffding’s inequality \([16](https://arxiv.org/html/2610.27384#S3.E16)\) and ask that eachTI<δ0T\_\{I\}<\\delta\_\{0\}, which occurs when \([B\.80](https://arxiv.org/html/2610.27384#A2.E80)\) holds\. ∎

The above proposition guarantees that after seeing enough patterns, the TDenseAM learns the underlying code\. Crucially, either \([B\.79](https://arxiv.org/html/2610.27384#A2.E79)\) or even \([B\.80](https://arxiv.org/html/2610.27384#A2.E80)\) are far smaller than theexp⁡\(O⁡\(N\)\)\\exp\(\\mathrm\{O\}\(N\)\)codewords of a random LDPC code\. Therefore, the associative memory is*not*simply memorizing the training data, it is learning the underlying rules that generated the data set; namely, performing Hamiltonian learning\. Amazingly, in the casea\>0a\>0, we do not even need to show the TDenseAM every linearly independent vector inVVbefore it learns the entire vector space\. Thea\>0a\>0TDenseAM therefore truly learns to generalize on this problem, even going beyond interpolation and learning patternv1\+v2v\_\{1\}\+v\_\{2\}after seeingv1v\_\{1\}andv2v\_\{2\}individually\.

### B\.2Dynamics of learning:a→1a\\rightarrow 1

We will first discuss how the TDenseAM learns – in particular, the nature of the learned energy landscapeE^\\widehat\{E\}as a function ofPP– in the limita→1a\\rightarrow 1\. In this regime, the TDenseAM becomes identical to the SAT learning algorithm of Valiant\[[15](https://arxiv.org/html/2610.27384#bib.bib15)\]applied to the XORSAT \(LDPC\) problem: we reject a constraint if we ever see it violated a single time\. Namely,T^I≠0\\widehat\{T\}\_\{I\}\\neq 0if and only ifξIμ=ξIν\\xi\_\{I\}^\{\\mu\}=\\xi\_\{I\}^\{\\nu\}for every pair of training patterns\(μ,ν\)\(\\mu,\\nu\)\.

In our discussion of the learning algorithm, it will be useful to separate out

E^\(σ\)=−∑I∈im⁡\(H𝖳\)T^IσI−∑I∉im⁡\(H𝖳\)T^IσI=:E\+Ejunk,\\widehat\{E\}\(\\sigma\)=\-\\sum\_\{I\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\}\\widehat\{T\}\_\{I\}\\sigma\_\{I\}\-\\sum\_\{I\\notin\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\}\\widehat\{T\}\_\{I\}\\sigma\_\{I\}=:E\+E\_\{\\text\{junk\}\},\(B\.85\)whereEEis a true code Hamiltonian that we will learn, whileEjunkE\_\{\\text\{junk\}\}is the spurious Hamiltonian that is sensitive to the specific training data we have seen\. Proposition[B\.1](https://arxiv.org/html/2610.27384#A2.Thmthm1)gives us a loose bound on how fast it takes forEjunkE\_\{\\text\{junk\}\}to become negligibly small or even zero\. However, we would like to say more about what happens toEjunkE\_\{\\text\{junk\}\}as a function ofPP\.

There are two useful ways to think about how the TDenseAM learns\. Firstly, we can keep track of

J:=\#⁡\{I:T^I\>0\}=∑IXI\.J:=\\\#\\\{I:\\widehat\{T\}\_\{I\}\>0\\\}=\\sum\_\{I\}X\_\{I\}\.\(B\.86\)JJstands for the number of junk couplings that we have not unlearned, and is a proxy for how corruptedE^\\widehat\{E\}is byEjunkE\_\{\\text\{junk\}\}\. For later use, we have also defined the indicator variables

XI:=𝕀\[T^I≠0\]\.X\_\{I\}:=\\mathbb\{I\}\[\\widehat\{T\}\_\{I\}\\neq 0\]\.\(B\.87\)The second thing we can keep track of is the rank of the learned codespacek^≤k\\widehat\{k\}\\leq k\.

We will show that the way TDenseAM learns in the limita→1a\\rightarrow 1is rather different at early times depending on whetherm=2m=2orm\>2m\>2, and so we will have to tackle those problems separately\. The late time learning is very similar in both cases, so when we talk about late time behavior we will discuss both together\.

###### Proposition B\.2:

Consider the task of learning a random LDPC code withm=2m=2using thea→1a\\rightarrow 1TDenseAM\. Then almost surely ask→∞k\\rightarrow\\infty, ifP<\(1−ϵ\)​log2​kP<\(1\-\\epsilon\)\\log\_\{2\}kfor any0<ϵ<10<\\epsilon<1, the learned rank of codewords is

k^=2P−1\.\\widehat\{k\}=2^\{P\-1\}\.\(B\.88\)

###### Proof\.

Whenm=2m=2, the only allowed codes that TDenseAM can learn are disjoint repetition codes: indeed ifxi=xjx\_\{i\}=x\_\{j\}andxj=xkx\_\{j\}=x\_\{k\}are constraints on the codespace, by transitivityxi=xkx\_\{i\}=x\_\{k\}– therefore, the allowed codewords correspond to independent subsets of\[n\]\[n\]which must all agree with each other\. The rank of the code is the number of non\-empty sets

𝒮⁡\(η1,…,ηP\):=\{i∈\[n\]:ξiμ=ηi\}\.\\mathcal\{S\}\(\\eta\_\{1\},\\ldots,\\eta\_\{P\}\):=\\\{i\\in\[n\]:\\xi\_\{i\}^\{\\mu\}=\\eta\_\{i\}\\\}\.\(B\.89\)For convenience, it is useful to “gauge fix” the firstξi1=1\\xi\_\{i\}^\{1\}=1\. If each𝒮⁡\(η2,…,ηP\)\\mathcal\{S\}\(\\eta\_\{2\},\\ldots,\\eta\_\{P\}\)is non\-empty, then the rank of the learned code must be2P−12^\{P\-1\}\.

The most general code withm=2m=2corresponds to a set of repetition codes, wherein the firstkkbits are arbitrary and the remainingn−kn\-kbits are fixed\. The probability that a giveni∈\[k\]i\\in\[k\]ends up in each𝒮⁡\(η2,…,ηP\)\\mathcal\{S\}\(\\eta\_\{2\},\\ldots,\\eta\_\{P\}\)bucket is2−\(P−1\)2^\{\-\(P\-1\)\}, and each of these are independent events\. The probability that a bucket has zero elements is

ℙ⁡\(any​𝒮​\(η2,…,ηP\)=∅\)≤2\(P−1\)​\(1−2−\(P−1\)\)k\.\\mathbb\{P\}\\left\(\\text\{any \}\\mathcal\{S\}\(\\eta\_\{2\},\\ldots,\\eta\_\{P\}\)=\\emptyset\\right\)\\leq 2^\{\(P\-1\)\}\\left\(1\-2^\{\-\(P\-1\)\}\\right\)^\{k\}\.\(B\.90\)This event happens with probability<ϵ<\\epsilonso long as

P−1\+log2​1ϵ\>k​log2​11−2−\(P−1\)\>2−\(P−1\)​kP\-1\+\\log\_\{2\}\\frac\{1\}\{\\epsilon\}\>k\\log\_\{2\}\\frac\{1\}\{1\-2^\{\-\(P\-1\)\}\}\>2^\{\-\(P\-1\)\}k\(B\.91\)In the limit of largekk, this inequality is false for anyP<\(1−ϵ\)​log2​kP<\(1\-\\epsilon\)\\log\_\{2\}k, for anyϵ\>0\\epsilon\>0\. ∎

###### Proposition B\.3:

Let0<κ<10<\\kappa<1andk=Θ⁡\(n\)k=\\mathrm\{\\Theta\}\(n\)\. In the regime

P=\(m−κ\)​log2​n,P=\(m\-\\kappa\)\\log\_\{2\}n,\(B\.92\)almost surely asn→∞n\\rightarrow\\infty, the rank of learned codewords is

k^=k−2​nκm\!​\(1\+o⁡\(1\)\)\.\\widehat\{k\}=k\-2\\frac\{n^\{\\kappa\}\}\{m\!\}\(1\+\\mathrm\{o\}\(1\)\)\.\(B\.93\)

###### Proof\.

We begin with a useful lemma:

###### Lemma B\.4:

Let𝒜⊂\[I\]\\mathcal\{A\}\\subset\[I\]denote a collection of the possible learned couplings\. Then, in the limita→1a\\rightarrow 1, after training onPPrandom codewords,

ℙ\[T^I\>0for allI∈𝒜\]=2−\(P−1\)​A\\mathbb\{P\}\\left\[\\widehat\{T\}\_\{I\}\>0\\text\{ for all \}I\\in\\mathcal\{A\}\\right\]=2^\{\-\(P\-1\)A\}\(B\.94\)where

A:=rank⁡\(𝒜\)−rank⁡\(𝒜∩ker⁡\(H\)\)\.A:=\\mathrm\{rank\}\(\\mathcal\{A\}\)\-\\mathrm\{rank\}\(\\mathcal\{A\}\\cap\\ker\(H\)\)\.\(B\.95\)

###### Proof\.

When\|𝒜\|=1\|\\mathcal\{A\}\|=1, \([B\.94](https://arxiv.org/html/2610.27384#A2.E94)\) immediately follows from the training rule and Proposition[A\.3](https://arxiv.org/html/2610.27384#A1.Thmthm3)\. Firstly, if the soleI∈𝒜I\\in\\mathcal\{A\}is a valid check, then every codeword satisfies it, soA=0A=0and the probability in \([B\.94](https://arxiv.org/html/2610.27384#A2.E94)\) is 1\. Secondly, ifI∉ker⁡\(H\)I\\notin\\ker\(H\), the probability that patternsξIμ\\xi\_\{I\}^\{\\mu\}withμ=2,…,P\\mu=2,\\ldots,PmatchξI1\\xi\_\{I\}^\{1\}\(which itself was±1\\pm 1with equal probability\) is independently12\\frac\{1\}\{2\}for each pattern, establishing \([B\.94](https://arxiv.org/html/2610.27384#A2.E94)\) as well\.

Next, suppose that\|𝒜\|\>1\|\\mathcal\{A\}\|\>1, but𝒜∩ker⁡\(H\)=∅\\mathcal\{A\}\\cap\\ker\(H\)=\\emptysetand each check in𝒜\\mathcal\{A\}is linearly independent\. In this regime, we may apply Proposition[A\.4](https://arxiv.org/html/2610.27384#A1.Thmthm4): the probability that allT^I\\widehat\{T\}\_\{I\}survive training on each patternμ=2,…,P\\mu=2,\\ldots,Pis2−A2^\{\-A\}: we must lie in an orbit that does not contain anyvav\_\{a\}\.

An analogous argument applies in the case where𝒜∩ker⁡\(H\)=0\\mathcal\{A\}\\cap\\ker\(H\)=0but𝒜\\mathcal\{A\}is not full\-rank\. The values of theT^I\\widehat\{T\}\_\{I\}are compeletely determined by knowledge of their values on a linearly independent subset, where we can apply the argument of the previous paragraph\.

Lastly, suppose that𝒜∩ker⁡\(H\)≠∅\\mathcal\{A\}\\cap\\ker\(H\)\\neq\\emptyset\. In this case, we know that every element ofker⁡\(H\)\\ker\(H\)in the span of𝒜\\mathcal\{A\}is never violated, so we must subtract these contributions from the count above\. If we study the reduced set𝒜∖ker⁡\(H\)\\mathcal\{A\}\\setminus\\ker\(H\), a vector space of rankAAas given in \([B\.95](https://arxiv.org/html/2610.27384#A2.E95)\), then it satisfies the previous case\. ∎

Observe that

𝔼⁡\[J2\]=∑I1𝔼⁡\[XI1\]\+∑I1≠I2𝔼⁡\[XI1​XI2\]=∑I1𝔼⁡\[XI1\]\+∑I1≠I2𝔼⁡\[XI1\]​𝔼​\[XI2\]\.\\mathbb\{E\}\\left\[J^\{2\}\\right\]=\\sum\_\{I\_\{1\}\}\\mathbb\{E\}\[X\_\{I\_\{1\}\}\]\+\\sum\_\{I\_\{1\}\\neq I\_\{2\}\}\\mathbb\{E\}\[X\_\{I\_\{1\}\}X\_\{I\_\{2\}\}\]=\\sum\_\{I\_\{1\}\}\\mathbb\{E\}\[X\_\{I\_\{1\}\}\]\+\\sum\_\{I\_\{1\}\\neq I\_\{2\}\}\\mathbb\{E\}\[X\_\{I\_\{1\}\}\]\\mathbb\{E\}\[X\_\{I\_\{2\}\}\]\.\(B\.96\)The second equality follows from Lemma[B\.4](https://arxiv.org/html/2610.27384#A2.Thmthm4): any two inequivalentIIare linearly independent\. Therefore, so long as the LDPC code has a subextensive fraction of all possible checks \(the vast majority of possible checks are “junk” checks\),

Var⁡\(J\)≤𝔼⁡\[J\]=\(1\+o⁡\(1\)\)​\(nm\)​2−\(P−1\)=nmm\!​2−\(P−1\)​\(1\+o⁡\(1\)\)=2​nκm\!​\(1\+O⁡\(1\)\)\.\\mathrm\{Var\}\(J\)\\leq\\mathbb\{E\}\[J\]=\(1\+\\mathrm\{o\}\(1\)\)\\left\(\\begin\{array\}\[\]\{c\}n\\\\ m\\end\{array\}\\right\)2^\{\-\(P\-1\)\}=\\frac\{n^\{m\}\}\{m\!\}2^\{\-\(P\-1\)\}\(1\+\\mathrm\{o\}\(1\)\)=2\\frac\{n^\{\\kappa\}\}\{m\!\}\(1\+\\mathrm\{O\}\(1\)\)\.\(B\.97\)Chebyshev’s inequality thus shows that

ℙ\[\|J𝔼⁡\[J\]−1\|\>s\]≤s2𝔼⁡\[J\]≤s2​m\!2​nκ\\mathbb\{P\}\\left\[\\left\|\\frac\{J\}\{\\mathbb\{E\}\[J\]\}\-1\\right\|\>s\\right\]\\leq\\frac\{s^\{2\}\}\{\\mathbb\{E\}\[J\]\}\\leq\\frac\{s^\{2\}m\!\}\{2n^\{\\kappa\}\}\(B\.98\)This shows that we see2​nκ/m\!×\(1\+o⁡\(1\)\)2n^\{\\kappa\}/m\!\\times\(1\+\\mathrm\{o\}\(1\)\)checks, almost surely asn→∞n\\rightarrow\\infty\.

With high probability each bit is included in at most one surviving fake check\. This is because for anyI1≠I2I\_\{1\}\\neq I\_\{2\},ℙ\[XI1=1\|XI2=1\]=ℙ\[XI1=1\]\\mathbb\{P\}\[X\_\{I\_\{1\}\}=1\|X\_\{I\_\{2\}\}=1\]=\\mathbb\{P\}\[X\_\{I\_\{1\}\}=1\], again by the linear independence criterion in Proposition[A\.4](https://arxiv.org/html/2610.27384#A1.Thmthm4)and Lemma[B\.4](https://arxiv.org/html/2610.27384#A2.Thmthm4)\. Therefore, supposing that bit1∈I11\\in I\_\{1\}andXI1=1X\_\{I\_\{1\}\}=1, the probability that any other surviving check contains bit 1 is

ℙ\[2 surviving checks contain 1\\displaystyle\\mathbb\{P\}\[\\text\{2 surviving checks contain 1\}\|1 surviving check\]≤∑I2≠I1,1∈I2𝔼\[XI2\]\\displaystyle\|\\text\{1 surviving check\}\]\\leq\\sum\_\{I\_\{2\}\\neq I\_\{1\},1\\in I\_\{2\}\}\\mathbb\{E\}\[X\_\{I\_\{2\}\}\]=\(n−1m−1\)​2−\(P−1\)=2\(m−1\)\!​n1−κ→0\.\\displaystyle=\\left\(\\begin\{array\}\[\]\{c\}n\-1\\\\ m\-1\\end\{array\}\\right\)2^\{\-\(P\-1\)\}=\\frac\{2\}\{\(m\-1\)\!n^\{1\-\\kappa\}\}\\rightarrow 0\.This shows that almost every check is linearly independent asn→∞n\\rightarrow\\infty, and establishes \([B\.93](https://arxiv.org/html/2610.27384#A2.E93)\)\. ∎

###### Theorem B\.5:

Consider the task of learning a random LDPC code withm\>2m\>2andk/n=O⁡\(1\)k/n=\\mathrm\{O\}\(1\), using thea→1a\\rightarrow 1TDenseAM\. Fix anyϵ\>0\\epsilon\>0, and suppose that

P<\(m⁡\(m−1\)2​m−1−ϵ\)​log2​n\.P<\\left\(\\frac\{m\(m\-1\)\}\{2m\-1\}\-\\epsilon\\right\)\\log\_\{2\}n\.\(B\.101\)Then asn→∞n\\rightarrow\\infty, almost surely the learned rank of codewords is

k^=\{P−1m​oddPm​even\.\\widehat\{k\}=\\left\\\{\\begin\{array\}\[\]\{ll\}P\-1&\\ m\\text\{ odd\}\\\\ P&\\ m\\text\{ even\}\\end\{array\}\\right\.\.\(B\.102\)

###### Proof\.

The core strategy of this proof is to argue that when \([B\.101](https://arxiv.org/html/2610.27384#A2.E101)\) is obeyed, each new observed codeword increases the rank only by 1\. If we can establish this fact, \([B\.102](https://arxiv.org/html/2610.27384#A2.E102)\) follows immediately from the fact that after being shown the first patternξi1\\xi\_\{i\}^\{1\}, this is the unique ground state ofE^\\widehat\{E\}ifmmis odd, while ifmmis even,ξi1\\xi\_\{i\}^\{1\}and−ξi1\-\\xi\_\{i\}^\{1\}are both ground states\.

To do this, we proceed as follows\. Define

α:=Plog2​n<m⁡\(m−1\)2​m−1−ϵ\.\\alpha:=\\frac\{P\}\{\\log\_\{2\}n\}<\\frac\{m\(m\-1\)\}\{2m\-1\}\-\\epsilon\.\(B\.103\)Lemma[B\.4](https://arxiv.org/html/2610.27384#A2.Thmthm4)shows that the probability that any spurious check has survived is given by

q:=ℙ\[T^I≠0ifI∉im\(H𝖳\)\]=2n−α,q:=\\mathbb\{P\}\[\\widehat\{T\}\_\{I\}\\neq 0\\text\{ if \}I\\notin\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\]=2n^\{\-\\alpha\},\(B\.104\)which is quite small\. At the same time, there are a huge number of spurious checks:∼nm\\sim n^\{m\}, which naively already wins\. However, we need to be careful: the spurious checks can themselves be highly redundant\.

We will therefore establish \([B\.102](https://arxiv.org/html/2610.27384#A2.E102)\) as follows\. First, defineKPK\_\{P\}to be the set of learned checks \(modulo gauging by the first seen pattern\) afterPPpatterns:

KP:=\{w∈𝔽2n:\|w\|=m​and​w⋅\(bμ−b1\)=0​for​2≤μ≤P\}\.K\_\{P\}:=\\\{w\\in\\mathbb\{F\}\_\{2\}^\{n\}:\|w\|=m\\text\{ and \}w\\cdot\(b^\{\\mu\}\-b^\{1\}\)=0\\text\{ for \}2\\leq\\mu\\leq P\\\}\.\(B\.105\)Without loss of generality for what follows, we setbi1=0b^\{1\}\_\{i\}=0to simplify notation\. We will show that for suitably smallα\\alpha,dim\(span⁡\(KP\+1\)\)−dim\(span⁡\(KP\)\)=1\\dim\(\\mathrm\{span\}\(K\_\{P\+1\}\)\)\-\\dim\(\\mathrm\{span\}\(K\_\{P\}\)\)=1with high probability\. We do this by showing that for any twow1,2∈KP\+1∖KPw\_\{1,2\}\\in K\_\{P\+1\}\\setminus K\_\{P\}acting on disjoint bits,w1\+w2∈KP\+1w\_\{1\}\+w\_\{2\}\\in K\_\{P\+1\}\(w\.h\.p\.\) because it can be represented as a sum over exactly2​m2mchecks that remain inKP\+1K\_\{P\+1\}\. This latter fact will come from establishing the existence of a nice matching, which we define as follows:

###### Definition B\.6\(Nice matching\):

Define the graphGniceG\_\{\\text\{nice\}\}to be the connected subgraph of the bipartite complete graphKm,m\\mathrm\{K\}\_\{m,m\}minus a perfect matching: see Figure[5](https://arxiv.org/html/2610.27384#A2.F5)\. A nice matching onKPK\_\{P\}is a collectionMMofm2\+mm^\{2\}\+mbits:\(v1,…,v2​m,u1,…,um2−m\)\(v\_\{1\},\\ldots,v\_\{2m\};u\_\{1\},\\ldots,u\_\{m^\{2\}\-m\}\)such that there exists a sequential assignment ofv1,…​v2​mv\_\{1\},\\ldots v\_\{2m\}to the2​m2mvertices ofGniceG\_\{\\text\{nice\}\}, andu1,…,um2−mu\_\{1\},\\ldots,u\_\{m^\{2\}\-m\}to them2−mm^\{2\}\-medges ofGniceG\_\{\\text\{nice\}\}such thatw1=\{v1,…,vm\}w\_\{1\}=\\\{v\_\{1\},\\ldots,v\_\{m\}\\\},w2=\{vm\+1,…,v2​m\}w\_\{2\}=\\\{v\_\{m\+1\},\\ldots,v\_\{2m\}\\\}, andKPK\_\{P\}contains every candidate check made out of a vertex along with its incident edges:

\{v\}∪⋃e∈∂v\{ue\}∈KP\.\\\{v\\\}\\cup\\bigcup\_\{e\\in\\partial v\}\\\{u\_\{e\}\\\}\\in K\_\{P\}\.\(B\.106\)We also write𝒰\(M\):=\{u1,…,um2−m\\mathcal\{U\}\(M\):=\\\{u\_\{1\},\\ldots,u\_\{m^\{2\}\-m\}, and𝒜⁡\(M\)\\mathcal\{A\}\(M\)as the vector space spanned by the weight\-\(m−1\)\(m\-1\)checks inMMwith the bitsviv\_\{i\}removed\.

Figure 5:Illustration ofGniceG\_\{\\mathrm\{nice\}\}in the casem=5m=5\.We will restrict our study to candidate matchings whereu1,…,um⁡\(m−1\)∈𝒱u\_\{1\},\\ldots,u\_\{m\(m\-1\)\}\\in\\mathcal\{V\}, where𝒱⊂\[n\]\\mathcal\{V\}\\subset\[n\]is any subset of vertices chosen to ensure the following property:

###### Lemma B\.7:

Suppose thatk≥R​nk\\geq Rnfor some O\(1\) constantRR, andnnis sufficiently large\. For anyW⊂\[n\]W\\subset\[n\]with\|W\|=2​m\|W\|=2m, and O\(1\) constant0<ρ<R0<\\rho<R, there exists a set𝒱⊂\[n\]\\mathcal\{V\}\\subset\[n\]with\|𝒱\|=ρ​n\|\\mathcal\{V\}\|=\\rho n, such that the following holds\. LetD:=im⁡\(H𝖳\)⊕span​\(ei\)i∈WD:=\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\\oplus\\mathrm\{span\}\(e\_\{i\}\)\_\{i\\in W\}; hereeie\_\{i\}denote the unit vectors in𝔽2n\\mathbb\{F\}\_\{2\}^\{n\}\. For every coset\[ei\]∈𝔽2n/D\[e\_\{i\}\]\\in\\mathbb\{F\}\_\{2\}^\{n\}/D, we have that\{\[ei\]\}i∈𝒱\\\{\[e\_\{i\}\]\\\}\_\{i\\in\\mathcal\{V\}\}are all linearly independent vectors\. Therefore, when sampling random codewordsbμb^\{\\mu\}, the random variablesbiμb^\{\\mu\}\_\{i\}are i\.i\.d\. Bernoulli random variables withℙ⁡\(biμ=1\)=12\\mathbb\{P\}\(b^\{\\mu\}\_\{i\}=1\)=\\frac\{1\}\{2\}\.

###### Proof\.

Because we havedim⁡\(im⁡\(𝖧𝖳\)=\(1−R\)​nCLOSE\\mathrm\{dim\}\(\\mathrm\{im\}\(\\mathsf\{H\}^\{\\mathsf\{T\}\}\)=\(1\-R\)n, we know thatdim⁡\(𝔽2n/D\)≥R​n−2​m\\mathrm\{dim\}\(\\mathbb\{F\}\_\{2\}^\{n\}/D\)\\geq Rn\-2m, so anyρ<R\\rho<Rwould suffice, for large enoughnn\! Since the cosets\{\[ei\]\}i∈\[n\]\\\{\[e\_\{i\}\]\\\}\_\{i\\in\[n\]\}span the entire space, there must beρ​n\\rho nof them which are linearly independent\. By Proposition[A\.4](https://arxiv.org/html/2610.27384#A1.Thmthm4), the probability for eachℙ⁡\(biμ=1\)=12\\mathbb\{P\}\(b^\{\\mu\}\_\{i\}=1\)=\\frac\{1\}\{2\}ifi∈𝒱i\\in\\mathcal\{V\}\. Moreover, even conditioned on arbitrary values ofbjμb^\{\\mu\}\_\{j\}forj∈Wj\\in W,biμb^\{\\mu\}\_\{i\}must be independent for all subsets ofii; if this was not true, then there would be a linear combination ofbiμb^\{\\mu\}\_\{i\}which violates Proposition[A\.4](https://arxiv.org/html/2610.27384#A1.Thmthm4)by always taking the same value \(0\)\. Note that the TDenseAM does not need to learn𝒱\\mathcal\{V\}– it’s role is constructive for the proof of Theorem[B\.5](https://arxiv.org/html/2610.27384#A2.Thmthm5)\. ∎

In what follows, we will condition onw1,2⋅bμ=0w\_\{1,2\}\\cdot b^\{\\mu\}=0for2≤μ≤P2\\leq\\mu\\leq Pandw1,2⋅bP\+1=1w\_\{1,2\}\\cdot b^\{P\+1\}=1\. Lemma[B\.7](https://arxiv.org/html/2610.27384#A2.Thmthm7)shows us that allbiμb^\{\\mu\}\_\{i\}are independent variables\. The strategy is now to show that there are typically many nice matchings inKP\+1K\_\{P\+1\}involving the two checksw1,2w\_\{1,2\}, which would immediately imply thatw1\+w2∈span⁡\(KP\+1\)w\_\{1\}\+w\_\{2\}\\in\\mathrm\{span\}\(K\_\{P\+1\}\)\. To do this, we introduce the random variable

XM:=𝕀⁡\[M​is a nice matching onKP\+1\]\.X\_\{M\}:=\\mathbb\{I\}\[M\\text\{ is a nice matching on $K\_\{P\+1\}$\}\]\.\(B\.107\)We further introduce independent Bernoulli random variablesθM\\theta\_\{M\}, withℙ\[θM=1\]=ν\\mathbb\{P\}\[\\theta\_\{M\}=1\]=\\nu\(we will choose the value ofν\\nulater\)\. It would suffice to argue that the following random variable is non\-zero with high probability:

ℳ:=∑MθM​XM\.\\mathcal\{M\}:=\\sum\_\{M\}\\theta\_\{M\}X\_\{M\}\.\(B\.108\)We do this by invoking the following improvement over Hoeffding’s inequality, discussed in\[[32](https://arxiv.org/html/2610.27384#bib.bib32),[33](https://arxiv.org/html/2610.27384#bib.bib33)\]:

###### Lemma B\.8:

Let\{Xa\}a=1N\\\{X\_\{a\}\\\}\_\{a=1\}^\{N\}be Bernoulli random variables:Xa∈\{0,1\}X\_\{a\}\\in\\\{0,1\\\}\. Define a graph on theaa, withaaconnected tobbby an edge \(a∈∂ba\\in\\partial b\) as infrequently as possible, while maintaining the following property: if disjoint index setsAAandBBshare no edges in common, then\{Xa\}a∈A\\\{X\_\{a\}\\\}\_\{a\\in A\}and\{Xb\}b∈B\\\{X\_\{b\}\\\}\_\{b\\in B\}are independent random variables\. Then

ℙ\[∑a=1NXa=0\]≤exp\(−λ\+Δe2​δ\)\\mathbb\{P\}\\left\[\\sum\_\{a=1\}^\{N\}X\_\{a\}=0\\right\]\\leq\\exp\\left\(\-\\lambda\+\\Delta\\mathrm\{e\}^\{2\\delta\}\\right\)\(B\.109\)where

λ\\displaystyle\\lambda=∑a=1N𝔼⁡\[Xa\],\\displaystyle=\\sum\_\{a=1\}^\{N\}\\mathbb\{E\}\[X\_\{a\}\],\(B\.110a\)Δ\\displaystyle\\Delta=∑a=1N∑b∈∂a𝔼⁡\[Xa​Xb\],\\displaystyle=\\sum\_\{a=1\}^\{N\}\\sum\_\{b\\in\\partial a\}\\mathbb\{E\}\[X\_\{a\}X\_\{b\}\],\(B\.110b\)δ\\displaystyle\\delta=max⁡∑b∈∂aa⁡𝔼⁡\[Xb\]\.\\displaystyle=\\max\_\{a\}\\sum\_\{b\\in\\partial a\}\\mathbb\{E\}\[X\_\{b\}\]\.\(B\.110c\)

The idea is to apply this lemma to boundℙ\[ℳ=0\]\\mathbb\{P\}\[\\mathcal\{M\}=0\]\. Clearly ifℳ\>0\\mathcal\{M\}\>0, there exists a nice matching of checks inKP\+1K\_\{P\+1\}, verifying thatw1\+w2∈span⁡\(KP\+1\)w\_\{1\}\+w\_\{2\}\\in\\mathrm\{span\}\(K\_\{P\+1\}\)\. We need to choose an incidence relation compatible with the requirements of Lemma[B\.8](https://arxiv.org/html/2610.27384#A2.Thmthm8)\. A useful way to do this is to say thatM1∈∂M2M\_\{1\}\\in\\partial M\_\{2\}if and only ifM1≠M2M\_\{1\}\\neq M\_\{2\}andM1M\_\{1\}andM2M\_\{2\}share at least one edge in common\.

First, we evaluate

λ:=𝔼⁡\[ℳ\]=⌊ρ​n⌋\!\(⌊ρ​n⌋−m2\+m\)\!​ν​𝔼​\[XM\]\\lambda:=\\mathbb\{E\}\[\\mathcal\{M\}\]=\\frac\{\\lfloor\\rho n\\rfloor\!\}\{\(\\lfloor\\rho n\\rfloor\-m^\{2\}\+m\)\!\}\\nu\\mathbb\{E\}\[X\_\{M\}\]\(B\.111\)where the first combinatorial factor represents the number of candidate nice matchings: note that the order in which we assign the coordinates does matter, which is why there is not an additional1/\(m2−m\)\!1/\(m^\{2\}\-m\)\!\. Lemma[B\.7](https://arxiv.org/html/2610.27384#A2.Thmthm7)implies that in the coset space𝔽2n/D\\mathbb\{F\}\_\{2\}^\{n\}/D, the rank of the2​m2mchecks in the nice matching is2​m−12m\-1– the only dependent combination is the sum of all checks \(which equalsw1\+w2w\_\{1\}\+w\_\{2\}\)\. Using Lemma[B\.4](https://arxiv.org/html/2610.27384#A2.Thmthm4), we then have

𝔼\[XM=1\]=2−P⁡\(2​m−1\)=n−\(2​m−1\)​α\.\\mathbb\{E\}\[X\_\{M\}=1\]=2^\{\-P\(2m\-1\)\}=n^\{\-\(2m\-1\)\\alpha\}\.\(B\.112\)Therefore, using \([B\.103](https://arxiv.org/html/2610.27384#A2.E103)\),

λ≥ν​\(ρ​n\)m2−m​n−\(2​m−1\)​α=ν​ρm2−m​nϵ\.\\lambda\\geq\\nu\(\\rho n\)^\{m^\{2\}\-m\}n^\{\-\(2m\-1\)\\alpha\}=\\nu\\rho^\{m^\{2\}\-m\}n^\{\\epsilon\}\.\(B\.113\)On average, there are many candidate perfect matchings\.

We now need to evaluateΔ\\Deltaandδ\\deltato show that these perfect matchings are largely independent, so the probability of finding one is extremely high\. The key observation is as follows:

###### Lemma B\.9:

LetM1M\_\{1\}andM2M\_\{2\}be two nice matchings \(M1∈∂M2M\_\{1\}\\in\\partial M\_\{2\}\)\. If666Recall the definition for𝒰⁡\(M\)\\mathcal\{U\}\(M\)at the end of Definition[B\.6](https://arxiv.org/html/2610.27384#A2.Thmthm6)\.\|𝒰⁡\(M1\)∩𝒰⁡\(M2\)\|=s\|\\mathcal\{U\}\(M\_\{1\}\)\\cap\\mathcal\{U\}\(M\_\{2\}\)\|=s, then

dim\(row\(𝒜\(M1\)\)∩row\(𝒜\(M2\)\)=:r≤2​m−1m⁡\(m−1\)s=:ams\.\\dim\(\\mathrm\{row\}\(\\mathcal\{A\}\(M\_\{1\}\)\)\\cap\\mathrm\{row\}\(\\mathcal\{A\}\(M\_\{2\}\)\)=:r\\leq\\frac\{2m\-1\}\{m\(m\-1\)\}s=:a\_\{m\}s\.\(B\.114\)In other words, any two matchings with many common checks must also share a large number of bits in common\. As a consequence,

𝔼⁡\[XM1​XM2\]≤2−P​\(2​\(2​m−1\)−r\)=𝔼⁡\[XM1\]​𝔼​\[XM2\]​2P​r\.\\mathbb\{E\}\[X\_\{M\_\{1\}\}X\_\{M\_\{2\}\}\]\\leq 2^\{\-P\(2\(2m\-1\)\-r\)\}=\\mathbb\{E\}\[X\_\{M\_\{1\}\}\]\\mathbb\{E\}\[X\_\{M\_\{2\}\}\]2^\{Pr\}\.\(B\.115\)

###### Proof\.

Recall that a common vector between𝒜⁡\(M1\)\\mathcal\{A\}\(M\_\{1\}\)and𝒜⁡\(M2\)\\mathcal\{A\}\(M\_\{2\}\)is shared only between the coordinates in𝒰⁡\(M1\)∩𝒰⁡\(M2\):=𝒰∗\\mathcal\{U\}\(M\_\{1\}\)\\cap\\mathcal\{U\}\(M\_\{2\}\):=\\mathcal\{U\}\_\{\*\}\. Delete the edges in𝒰∗\\mathcal\{U\}\_\{\*\}from the graphsM1,2M\_\{1,2\}\(isomorphic toGniceG\_\{\\mathrm\{nice\}\}\)\. The common vector must necessarily have disconnected both graphs𝒰⁡\(M1,2\)∖𝒰∗\\mathcal\{U\}\(M\_\{1,2\}\)\\setminus\\mathcal\{U\}\_\{\*\}intoc\>1c\>1connected components: the only way to find a trivial relation involving an unremoved edge is to sum over both checks at its endpoints: all checks on a connected component must be included with equal weight, and the sum over all checks is already a trivial constraint by construction\. We deduce that

Now suppose that we choose a connected component ofA⊂GniceA\\subset G\_\{\\mathrm\{nice\}\}that containsn1n\_\{1\}left vertices andn2n\_\{2\}right vertices, as shown in Figure[6](https://arxiv.org/html/2610.27384#A2.F6)\. Without loss of generality we may taken1\+n2:=ns≤mn\_\{1\}\+n\_\{2\}:=n\_\{\\mathrm\{s\}\}\\leq m\. The number of edges that must have been removed is at least

\|\{e=\(v1,v2\):v1∈A,v2∉A\}\|≥\(n1\+n2\)\(m−1\)−n1n2≥ns\(m−1\)−ns22≥m−12\.\|\\\{e=\(v\_\{1\},v\_\{2\}\):v\_\{1\}\\in A,v\_\{2\}\\notin A\\\}\|\\geq\(n\_\{1\}\+n\_\{2\}\)\(m\-1\)\-n\_\{1\}n\_\{2\}\\geq n\_\{\\mathrm\{s\}\}\(m\-1\)\-\\frac\{n\_\{\\mathrm\{s\}\}^\{2\}\}\{2\}\\geq\\frac\{m\-1\}\{2\}\.\(B\.117\)The last inequality can be checked by brute force sincens∈\{1,…,m\}n\_\{\\mathrm\{s\}\}\\in\\\{1,\\ldots,m\\\}\.

Figure 6:An illustration of a connected componentA⊂GniceA\\subset G\_\{\\mathrm\{nice\}\}; the subsetAAis highlighted in turquoise, and this example hasn1=n2=2n\_\{1\}=n\_\{2\}=2along withm=5m=5\. The red edges are the deleted edges which must have been removed in \([B\.117](https://arxiv.org/html/2610.27384#A2.E117)\)\.Sincec≥2c\\geq 2ifr\>0r\>0, we apply this cut bound to each component of𝒰⁡\(M1\)\\mathcal\{U\}\(M\_\{1\}\)post\-deletion and find

s≥c​m−12≥\(m−1\)​m2​m−1​\(c−1\),s\\geq c\\frac\{m\-1\}\{2\}\\geq\(m\-1\)\\frac\{m\}\{2m\-1\}\(c\-1\),\(B\.118\)where the second inequality uses thatc≤2​mc\\leq 2m\. This implies \([B\.114](https://arxiv.org/html/2610.27384#A2.E114)\)\. \([B\.115](https://arxiv.org/html/2610.27384#A2.E115)\) follows the fact that the rank of checks inM1M\_\{1\}andM2M\_\{2\}is2​\(2​m−1\)−r2\(2m\-1\)\-rand from Lemma[B\.4](https://arxiv.org/html/2610.27384#A2.Thmthm4)and \([B\.112](https://arxiv.org/html/2610.27384#A2.E112)\)\. ∎

Let us then count the number of neighboring pairs in the adjacency graph on matchings\. Clearly, fors\>0s\>0,

\|\{\(M1,M2\):\|𝒰⁡\(M1\)∩𝒰⁡\(M2\)\|=s\}\|≤\(m2−m\)2​s​\(ρ​n\)2​m​\(m−1\)−s,\|\\\{\(M\_\{1\},M\_\{2\}\):\|\\mathcal\{U\}\(M\_\{1\}\)\\cap\\mathcal\{U\}\(M\_\{2\}\)\|=s\\\}\|\\leq\(m^\{2\}\-m\)^\{2s\}\(\\rho n\)^\{2m\(m\-1\)\-s\},\(B\.119\)where the first factor counts the number of candidate identifications of two edges in the matching with the same bit, while the second factor bounds the number of independent bits to choose between the matchings\.

Now we can boundΔ\\Deltaas follows\. FixM1M\_\{1\}\(all matchings are the same on average\), and sum over all potentially correlatedM2M\_\{2\}:

Δ≤⌊ρ​n⌋\!\(⌊ρ​n⌋−m2\+m\)\!​ν2​∑M2∈∂M1𝔼⁡\[XM1​XM2\]\.\\Delta\\leq\\frac\{\\lfloor\\rho n\\rfloor\!\}\{\(\\lfloor\\rho n\\rfloor\-m^\{2\}\+m\)\!\}\\nu^\{2\}\\sum\_\{M\_\{2\}\\in\\partial M\_\{1\}\}\\mathbb\{E\}\[X\_\{M\_\{1\}\}X\_\{M\_\{2\}\}\]\.\(B\.120\)This sum can be broken up by rankrras follows: using \([B\.119](https://arxiv.org/html/2610.27384#A2.E119)\) for the caser=0r=0, and using Lemma[B\.9](https://arxiv.org/html/2610.27384#A2.Thmthm9)for the caser\>0r\>0, we have

Δ\\displaystyle\\Delta≤\(ρ​n\)2​m​\(m−1\)​ν2​𝔼​\[XM1\]2​\(∑s=1m2−m\(m2​\(m−1\)2ρ​n\)s\+∑r=12​m−1∑s=⌈am​r⌉m2−m2P​r​\(m2​\(m−1\)2ρ​n\)s\)\\displaystyle\\leq\(\\rho n\)^\{2m\(m\-1\)\}\\nu^\{2\}\\mathbb\{E\}\[X\_\{M\_\{1\}\}\]^\{2\}\\left\(\\sum\_\{s=1\}^\{m^\{2\}\-m\}\\left\(\\frac\{m^\{2\}\(m\-1\)^\{2\}\}\{\\rho n\}\\right\)^\{s\}\+\\sum\_\{r=1\}^\{2m\-1\}\\sum\_\{s=\\lceil a\_\{m\}r\\rceil\}^\{m^\{2\}\-m\}2^\{Pr\}\\left\(\\frac\{m^\{2\}\(m\-1\)^\{2\}\}\{\\rho n\}\\right\)^\{s\}\\right\)≤C​λ2​n−ϵ\.\\displaystyle\\leq C\\lambda^\{2\}n^\{\-\\epsilon\}\.\(B\.121\)for sufficiently smallϵ\\epsilon, largenn, and a suitable constantCCwhose exact value is unimportant\. The dominant potential contribution comes from ther=1r=1term with the smallest value ofss\.

Similarly it is easy to boundδ\\delta: a fixed matching has at most\[m⁡\(m−1\)\]2​\(ρ​n\)m⁡\(m−1\)−1\[m\(m\-1\)\]^\{2\}\(\\rho n\)^\{m\(m\-1\)\-1\}neighbors, so

δ=m2​\(m−1\)2​\(ρ​n\)m⁡\(m−1\)−1​n−\(2​m−1\)​α=m2​\(m−1\)2​λρ​n\.\\delta=m^\{2\}\(m\-1\)^\{2\}\(\\rho n\)^\{m\(m\-1\)\-1\}n^\{\-\(2m\-1\)\\alpha\}=m^\{2\}\(m\-1\)^\{2\}\\frac\{\\lambda\}\{\\rho n\}\.\(B\.122\)
Now let us put everything together\. We want to ensure that2​δ<12\\delta<1and, additionally,λ\>2​Δ​e2​δ\\lambda\>2\\Delta\\mathrm\{e\}^\{2\\delta\}, or more simply,λ\>6​Δ\\lambda\>6\\Delta\. This happens so long as

λ\>6​C​λ2​n−ϵ\.\\lambda\>6C\\lambda^\{2\}n^\{\-\\epsilon\}\.\(B\.123\)From \([B\.113](https://arxiv.org/html/2610.27384#A2.E113)\), we see that \([B\.123](https://arxiv.org/html/2610.27384#A2.E123)\) is satisfied for large enoughnnif we take

ν=n−ϵ/2,\\nu=n^\{\-\\epsilon/2\},\(B\.124\)Lemma[B\.8](https://arxiv.org/html/2610.27384#A2.Thmthm8)then shows that almost surely asn→∞n\\rightarrow\\infty, any two spurious and non\-overlapping checksw1,2∈KP∖KP\+1w\_\{1,2\}\\in K\_\{P\}\\setminus K\_\{P\+1\}obeyw1\+w2∈span⁡\(KP\+1\)w\_\{1\}\+w\_\{2\}\\in\\mathrm\{span\}\(K\_\{P\+1\}\)\. Indeed, the probability of a fixed pairw1\+w2∉span⁡\(KP\+1\)w\_\{1\}\+w\_\{2\}\\notin\\mathrm\{span\}\(K\_\{P\+1\}\)falls as a stretched exponential innn, so the probability of this event happening for any pair still vanishes at the same rate\. By the union bound, the probability we have ever failed this test at any point is bounded by

ℙ⁡\[removed more checks\]≤nm​P​exp⁡\(−λ\+Δ​e2​δ\)<exp⁡\(−Θ⁡\(nϵ/2\)\)\\mathbb\{P\}\[\\text\{removed more checks\}\]\\leq n^\{m\}P\\exp\\left\(\-\\lambda\+\\Delta\\mathrm\{e\}^\{2\\delta\}\\right\)<\\exp\\left\(\-\\mathrm\{\\Theta\}\(n^\{\\epsilon/2\}\)\\right\)\(B\.125\)for sufficiently largenn\. Since we have seen that almost surely asn→∞n\\rightarrow\\inftywe never remove more than 1 check at a time at this small number of patterns, we establish \([B\.102](https://arxiv.org/html/2610.27384#A2.E102)\)\. ∎

### B\.3Dynamics of learning:a=0a=0

Next, we consider the opposite limit ofa=0a=0\. In this limit, we may expect that following\[[10](https://arxiv.org/html/2610.27384#bib.bib10)\],E^\\widehat\{E\}generically serves as a simple memory at smallPP– even though the dense associative memory is trained on random codewords, it will not uncover the rules that generated the data for some time\. This is made precise in the following discussions\.

The first result is to establish an absence of stability of typical unseen perturbations untilP∼nm−1P\\sim n^\{m\-1\}is sufficiently large\. More concretely:

###### Theorem B\.10:

Consider training thea=0a=0dense associative memory on a random\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC code with weightsΔC=m\>ΔB\>2\\Delta\_\{\\mathrm\{C\}\}=m\>\\Delta\_\{\\mathrm\{B\}\}\>2\. Consider comparing the learned energyE^\\widehat\{E\}at a true codewordc∈ker⁡\(H\)c\\in\\ker\(H\)to the learned energy atc\+ac\+a, where\|a\|=β​n\|a\|=\\beta n\. If

P=A​nm−1,P=An^\{m\-1\},\(B\.126\)then almost surely asn→∞n\\rightarrow\\infty,

ℙ\[E^\(c\)\>E^\(c\+a\)for somea\]→1\\mathbb\{P\}\[\\widehat\{E\}\(c\)\>\\widehat\{E\}\(c\+a\)\\text\{ for some \}a\]\\rightarrow 1\(B\.127\)ifA<Amin​\(β\)A<A\_\{\\mathrm\{min\}\}\(\\beta\), fornn\-independent functionAminA\_\{\\mathrm\{min\}\}, withA⁡\(0\)=0A\(0\)=0\.

###### Proof\.

Without loss of generality, we may consider the stability of the codewordc=0c=0\(call itσ1\\sigma^\{1\}when converting to spin language\), after training onPPrandom codewordsξiμ\\xi\_\{i\}^\{\\mu\}, since the training ensemble is translation invariant onker⁡\(H\)\\ker\(H\)\. It is most useful to express the dense associative memory energy function as

E^\(σ\)=−1P∑μ=1P\(σ⋅ξμ\)m\\widehat\{E\}\(\\sigma\)=\-\\frac\{1\}\{P\}\\sum\_\{\\mu=1\}^\{P\}\\left\(\\sigma\\cdot\\xi^\{\\mu\}\\right\)^\{m\}\(B\.128\)whena=0a=0\. We will analyze larger spin flips biased towards a single observed pattern and show that typical such choices lower the energy ofc=0c=0\.

Towards this end, let us consider the following setup\. Let

Ξ1:=\{i∈\[n\]:ξi1=−1\}\\Xi\_\{1\}:=\\\{i\\in\[n\]:\\xi^\{1\}\_\{i\}=\-1\\\}\(B\.129\)denote the sites where the first \(randomly drawn\) codeword differs fromσ1\\sigma^\{1\}\. Almost surely asn→∞n\\rightarrow\\infty, Corollary[A\.16](https://arxiv.org/html/2610.27384#A1.Thmthm16)shows that

\|Ξ1\|=\(1\+o⁡\(1\)\)​n2\.\|\\Xi\_\{1\}\|=\(1\+\\mathrm\{o\}\(1\)\)\\frac\{n\}\{2\}\.\(B\.130\)LetB⊂Ξ1B\\subset\\Xi\_\{1\}and define

σiB:=1−2​𝕀​\(i∈B\)\.\\sigma^\{B\}\_\{i\}:=1\-2\\mathbb\{I\}\(i\\in B\)\.\(B\.131\)We then consider the random variable

ℰ:=E^​\(σi1\)−E^​\(σiB\)\.\\mathcal\{E\}:=\\widehat\{E\}\(\\sigma\_\{i\}^\{1\}\)\-\\widehat\{E\}\(\\sigma^\{B\}\_\{i\}\)\.\(B\.132\)The goal will be to show that for large enoughBB,ℰB\>0\\mathcal\{E\}\_\{B\}\>0almost surely whenPPis sufficiently small\. In order to show that fact, it is useful to define

Yμ:=\(σB⋅ξμ\)m−\(σ1⋅ξμ\)mY^\{\\mu\}:=\\left\(\\sigma^\{B\}\\cdot\\xi^\{\\mu\}\\right\)^\{m\}\-\\left\(\\sigma^\{1\}\\cdot\\xi^\{\\mu\}\\right\)^\{m\}\(B\.133\)since

ℰ=∑μ=1PYμ\.\\mathcal\{E\}=\\sum\_\{\\mu=1\}^\{P\}Y^\{\\mu\}\.\(B\.134\)It will also be useful to define

β:=\|B\|n\.\\beta:=\\frac\{\|B\|\}\{n\}\.\(B\.135\)
Let us first consider the caseμ=1\\mu=1\. \([B\.130](https://arxiv.org/html/2610.27384#A2.E130)\) implies that

Y1=\(n−2​\|Ξ1\|\+2​\|B\|\)m−\(n−2​\|Ξ1\|\)m,Y^\{1\}=\(n\-2\|\\Xi\_\{1\}\|\+2\|B\|\)^\{m\}\-\(n\-2\|\\Xi\_\{1\}\|\)^\{m\},\(B\.136\)deterministically\. Assume thatβ\>0\\beta\>0is a fixed O\(1\) constant asn→∞n\\rightarrow\\infty\. Using \([B\.130](https://arxiv.org/html/2610.27384#A2.E130)\), we see that

Y1=\(1\+o⁡\(1\)\)​\(2​β​n\)mY^\{1\}=\(1\+\\mathrm\{o\}\(1\)\)\(2\\beta n\)^\{m\}\(B\.137\)In contrast, forμ=2,…,P\\mu=2,\\ldots,P,YμY^\{\\mu\}is a random variable\. Some useful moments of this random variable are captured by the following lemma:

###### Lemma B\.11:

LettingEEdenote the code energy as in \([B\.85](https://arxiv.org/html/2610.27384#A2.E85)\), for anyβ\>0\\beta\>0:

𝔼⁡\[Yμ\]\\displaystyle\\mathbb\{E\}\[Y^\{\\mu\}\]=E⁡\(σ1\)−E⁡\(σB\),\\displaystyle=E\(\\sigma^\{1\}\)\-E\(\\sigma^\{B\}\),\(B\.138a\)𝔼⁡\[\(Yμ−𝔼⁡\[Yμ\]\)2\]\\displaystyle\\mathbb\{E\}\\left\[\(Y^\{\\mu\}\-\\mathbb\{E\}\[Y^\{\\mu\}\]\)^\{2\}\\right\]<\(1\+o⁡\(1\)\)⋅2​\(2​m\)\!2m​m\!​\(1−\(1−2​β\)m\)​nm\.\\displaystyle<\(1\+\\mathrm\{o\}\(1\)\)\\cdot 2\\frac\{\(2m\)\!\}\{2^\{m\}m\!\}\\left\(1\-\(1\-2\\beta\)^\{m\}\\right\)n^\{m\}\.\(B\.138b\)

###### Proof\.

Here it is useful to expand out

\(σ⋅ξμ\)m=∑i1,i2,…,imξi1μσi1⋯ξimμσim\.\(\\sigma\\cdot\\xi^\{\\mu\}\)^\{m\}=\\sum\_\{i\_\{1\},i\_\{2\},\\ldots,i\_\{m\}\}\\xi\_\{i\_\{1\}\}^\{\\mu\}\\sigma\_\{i\_\{1\}\}\\cdots\\xi\_\{i\_\{m\}\}^\{\\mu\}\\sigma\_\{i\_\{m\}\}\.\(B\.139\)Using Proposition[A\.3](https://arxiv.org/html/2610.27384#A1.Thmthm3), we see that when averaging over codewordsξμ\\xi^\{\\mu\}, the only terms that survive are those where the product ofξ\\xiform a valid parity\-check\. From Corollary[A\.14](https://arxiv.org/html/2610.27384#A1.Thmthm14), we know that every valid parity\-check will involvemmdistinct bits\. Using the definition ofYμY^\{\\mu\}in \([B\.133](https://arxiv.org/html/2610.27384#A2.E133)\) then establishes \([B\.138a](https://arxiv.org/html/2610.27384#A2.E138.1)\)\.

Now we turn to the second moment\. It is useful to write it as follows\. LetJ1,2⊂\[n\]J\_\{1,2\}\\subset\[n\]denote orderedmm\-element lists\. First average over random patternsξ\\xi:

𝔼\[\(Yμ\)2\]=∑J1,J2:\|J1,2\|=m𝔼ξ\[ξJ1μξJ2μ\]\(σJ1B−σJ11\)\(σJ2B−σJ21\)\.\\mathbb\{E\}\\left\[\\left\(Y^\{\\mu\}\\right\)^\{2\}\\right\]=\\sum\_\{J\_\{1\},J\_\{2\}:\|J\_\{1,2\}\|=m\}\\mathbb\{E\}\_\{\\xi\}\\left\[\\xi\_\{J\_\{1\}\}^\{\\mu\}\\xi\_\{J\_\{2\}\}^\{\\mu\}\\right\]\\left\(\\sigma^\{B\}\_\{J\_\{1\}\}\-\\sigma^\{1\}\_\{J\_\{1\}\}\\right\)\\left\(\\sigma^\{B\}\_\{J\_\{2\}\}\-\\sigma^\{1\}\_\{J\_\{2\}\}\\right\)\.\(B\.140\)Firstly, we can again use Proposition[A\.3](https://arxiv.org/html/2610.27384#A1.Thmthm3)to conclude

𝔼\[ξJ1μξJ2μ\]=𝕀\[J1△J2∈im\(H𝖳\)\]\.\\mathbb\{E\}\\left\[\\xi\_\{J\_\{1\}\}^\{\\mu\}\\xi\_\{J\_\{2\}\}^\{\\mu\}\\right\]=\\mathbb\{I\}\[J\_\{1\}\\triangle J\_\{2\}\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\]\.\(B\.141\)Notice the following simple bound: since

σJ1B−σJ11=−2​𝕀​\(\|J1∩B\|​odd\)\\sigma^\{B\}\_\{J\_\{1\}\}\-\\sigma^\{1\}\_\{J\_\{1\}\}=\-2\\mathbb\{I\}\\left\(\|J\_\{1\}\\cap B\|\\text\{ odd\}\\right\)\(B\.142\)is either 0 or−2\-2, we have

𝔼\[\(Yμ\)2\]<4∑J1,J2:\|J1,2\|=m𝕀\(J1△J2∈im\(H𝖳\)\)𝕀\(\|J1∩B\|odd\)𝕀\(\|J2∩B\|odd\)\\mathbb\{E\}\\left\[\\left\(Y^\{\\mu\}\\right\)^\{2\}\\right\]<4\\sum\_\{J\_\{1\},J\_\{2\}:\|J\_\{1,2\}\|=m\}\\mathbb\{I\}\(J\_\{1\}\\triangle J\_\{2\}\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\)\\mathbb\{I\}\(\|J\_\{1\}\\cap B\|\\text\{odd\}\)\\mathbb\{I\}\(\|J\_\{2\}\\cap B\|\\text\{odd\}\)\(B\.143\)By Corollary[A\.15](https://arxiv.org/html/2610.27384#A1.Thmthm15), this sum is dominated by terms whereJ1J\_\{1\}andJ2J\_\{2\}contain every bit an even number of times: if they contain some collection of bitsw∈𝔽2nw\\in\\mathbb\{F\}\_\{2\}^\{n\}, we see thatw∈im⁡\(H𝖳\)w\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)is required for the average to be non\-vanishing by Proposition[A\.3](https://arxiv.org/html/2610.27384#A1.Thmthm3); the contribution over all such terms is bounded bynm−\|w\|​𝒩\|w\|=o⁡\(nm\)n^\{m\-\|w\|\}\\mathcal\{N\}\_\{\|w\|\}=\\mathrm\{o\}\(n^\{m\}\)if\|w\|\>0\|w\|\>0\. In contrast the number of ordered listsJ1J\_\{1\}andJ2J\_\{2\}that together share an even number of each element is bounded by2−m​\(2​m−1\)\!\!×nm2^\{\-m\}\(2m\-1\)\!\!\\times n^\{m\}– the first combinatorial factor counts all the ways that2​m2mindicesi1⋯i2​mi\_\{1\}\\cdots i\_\{2m\}can be paired up;nmn^\{m\}is the number of bits that each pair can jointly be assigned\. Notice that in this case, we also have

ℙ⁡\(\|J1∩B\|​odd\)=ℙ⁡\(\|J2∩B\|​odd\)=∑j​odd\(mj\)​βj​\(1−β\)m−j=1−\(1−2​β\)m2\.\\mathbb\{P\}\\left\(\|J\_\{1\}\\cap B\|\\text\{ odd\}\\right\)=\\mathbb\{P\}\\left\(\|J\_\{2\}\\cap B\|\\text\{ odd\}\\right\)=\\sum\_\{j\\text\{ odd\}\}\\left\(\\begin\{array\}\[\]\{c\}m\\\\ j\\end\{array\}\\right\)\\beta^\{j\}\(1\-\\beta\)^\{m\-j\}=\\frac\{1\-\(1\-2\\beta\)^\{m\}\}\{2\}\.\(B\.144\)Therefore using that this contribution dominates𝔼⁡\[\(Yμ\)2\]\\mathbb\{E\}\[\(Y^\{\\mu\}\)^\{2\}\], we find \([B\.138b](https://arxiv.org/html/2610.27384#A2.E138.2)\)\. ∎

The crucial thing we learn from Lemma[B\.11](https://arxiv.org/html/2610.27384#A2.Thmthm11)is thatYμY^\{\\mu\}are not heavy\-tailed random variables; we can apply the central limit theorem toY2\+⋯\+YPY^\{2\}\+\\cdots\+Y^\{P\}\. We conclude that asn→∞n\\rightarrow\\inftywithP=A​nm−1P=An^\{m\-1\}held fixed,ℰ\\mathcal\{E\}is well approximated by a Gaussian random variable with mean and variance

𝔼⁡\[ℰ\]\\displaystyle\\mathbb\{E\}\[\\mathcal\{E\}\]→P​𝔼​\[E⁡\(σ1\)−E⁡\(σB\)\]\+\(2​β​n\)m,\\displaystyle\\rightarrow P\\mathbb\{E\}\\left\[E\(\\sigma^\{1\}\)\-E\(\\sigma^\{B\}\)\\right\]\+\(2\\beta n\)^\{m\},\(B\.145a\)𝔼⁡\[\(ℰ−𝔼⁡\[ℰ\]\)2\]\\displaystyle\\mathbb\{E\}\\left\[\\left\(\\mathcal\{E\}\-\\mathbb\{E\}\[\\mathcal\{E\}\]\\right\)^\{2\}\\right\]=\(2​m\)\!2m−1​m\!​\(1−\(1−2​β\)m\)​nm​P\.\\displaystyle=\\frac\{\(2m\)\!\}\{2^\{m\-1\}m\!\}\\left\(1\-\(1\-2\\beta\)^\{m\}\\right\)n^\{m\}P\.\(B\.145b\)Sinceξ1\\xi^\{1\}is also random and has half±1\\pm 1almost surely, and by Corollary[A\.17](https://arxiv.org/html/2610.27384#A1.Thmthm17)the sampled logicalξ1\\xi^\{1\}is equally likely to have all allowed overlaps with a given check, we have:

𝔼⁡\[E⁡\(σ1\)−E⁡\(σB\)\]\\displaystyle\\mathbb\{E\}\\left\[E\(\\sigma^\{1\}\)\-E\(\\sigma^\{B\}\)\\right\]=−2m\!𝒩m⋅12m−1∑j​even\(mj\)∑k​odd\(jk\)\(2β\)k\(1−2β\)j−k\\displaystyle=\-2m\!\\mathcal\{N\}\_\{m\}\\cdot\\frac\{1\}\{2^\{m\-1\}\}\\sum\_\{j\\text\{ even\}\}\\left\(\\begin\{array\}\[\]\{c\}m\\\\ j\\end\{array\}\\right\)\\sum\_\{k\\text\{ odd\}\}\\left\(\\begin\{array\}\[\]\{c\}j\\\\ k\\end\{array\}\\right\)\(2\\beta\)^\{k\}\(1\-2\\beta\)^\{j\-k\}=−m\!​𝒩m2m−2∑j​even\(mj\)1−\(1−4​β\)2​j2\\displaystyle=\-\\frac\{m\!\\mathcal\{N\}\_\{m\}\}\{2^\{m\-2\}\}\\sum\_\{j\\text\{ even\}\}\\left\(\\begin\{array\}\[\]\{c\}m\\\\ j\\end\{array\}\\right\)\\frac\{1\-\(1\-4\\beta\)^\{2j\}\}\{2\}=\(−1\+12m−1​\(2−4​β\)m\+\(4​β\)m2\)​𝒩m​m\!\\displaystyle=\\left\(\-1\+\\frac\{1\}\{2^\{m\-1\}\}\\frac\{\(2\-4\\beta\)^\{m\}\+\(4\\beta\)^\{m\}\}\{2\}\\right\)\\mathcal\{N\}\_\{m\}m\!=\(−1\+\(1−2​β\)m\+\(2​β\)m\)​𝒩m​m\!=:y\.\\displaystyle=\\left\(\-1\+\(1\-2\\beta\)^\{m\}\+\(2\\beta\)^\{m\}\\right\)\\mathcal\{N\}\_\{m\}m\!=:y\.\(B\.152\)The overall factor ofm\!​𝒩mm\!\\mathcal\{N\}\_\{m\}counts the number of checks – each of which itself is includedm\!m\!times because all possible orderings of the bits are allowed inEE\.

Let us now combine everything together: we find that with high probability a real codeword is higher energy than our random perturbation towards a seen codeword \(ℰ\>0\\mathcal\{E\}\>0\) if, using \([A\.71](https://arxiv.org/html/2610.27384#A1.E71)\),

P<1\+o⁡\(1\)ΔB​\(m−1\)\!​\(2​β\)m1−\(2​β\)m−\(1−2​β\)m​nm−1=:\(1\+o⁡\(1\)\)⋅Amin​\(β\)​nm−1\.P<\\frac\{1\+\\mathrm\{o\}\(1\)\}\{\\Delta\_\{\\mathrm\{B\}\}\(m\-1\)\!\}\\frac\{\(2\\beta\)^\{m\}\}\{1\-\(2\\beta\)^\{m\}\-\(1\-2\\beta\)^\{m\}\}n^\{m\-1\}=:\(1\+\\mathrm\{o\}\(1\)\)\\cdot A\_\{\\mathrm\{min\}\}\(\\beta\)n^\{m\-1\}\.\(B\.153\)Indeed, the variance ofℰ\\mathcal\{E\}scales asnm−1/2n^\{m\-1/2\}whenP∼nm−1P\\sim n^\{m\-1\}, while𝔼⁡\[ℰ\]∼nm\\mathbb\{E\}\[\\mathcal\{E\}\]\\sim n^\{m\}, so it suffices to check that𝔼⁡\[ℰ\]​n−m\>0\\mathbb\{E\}\[\\mathcal\{E\}\]n^\{\-m\}\>0asn→∞n\\rightarrow\\infty, which is what \([B\.153](https://arxiv.org/html/2610.27384#A2.E153)\) guarantees\. ∎

###### Theorem B\.12:

In the same setting as Theorem[B\.10](https://arxiv.org/html/2610.27384#A2.Thmthm10), ifA\>Amax​\(β\)A\>A\_\{\\mathrm\{max\}\}\(\\beta\), for any0<β<γ0<\\beta<\\gammabelow the confinement scale of the code,

ℙ\[E^\(c\)<E^\(c\+a\)for everyawith\|a\|=βn\]→1\.\\mathbb\{P\}\[\\widehat\{E\}\(c\)<\\widehat\{E\}\(c\+a\)\\text\{ for every $a$ with \}\|a\|=\\beta n\]\\rightarrow 1\.\(B\.154\)Therefore, for sufficiently largeAA, there must be a local minimum ofE^\\widehat\{E\}closer to the true codeword than to any other\.

###### Proof\.

This proof begins identically to that of Theorem[B\.10](https://arxiv.org/html/2610.27384#A2.Thmthm10), but we will need to find more sophisticated bounds on the distribution ofYμY^\{\\mu\}\. Towards this end, for anyS⊂\[n\]S\\subset\[n\], define

ζS:=∑i∈Sζi\.\\zeta\_\{S\}:=\\sum\_\{i\\in S\}\\zeta\_\{i\}\.\(B\.155\)Notice that

Yμ:=\(ξScμ−ξSμ\)m−\(ξScμ\+ξSμ\)m\.Y^\{\\mu\}:=\\left\(\\xi^\{\\mu\}\_\{S^\{\\mathrm\{c\}\}\}\-\\xi^\{\\mu\}\_\{S\}\\right\)^\{m\}\-\\left\(\\xi^\{\\mu\}\_\{S^\{\\mathrm\{c\}\}\}\+\\xi^\{\\mu\}\_\{S\}\\right\)^\{m\}\.\(B\.156\)Using elementary inequalities we find

\|Yμ\|≤2​m​\|ξSμ\|​\(\|ξSμ\|\+\|ξScμ\|\)m−1≤2m​m​\|ξSμ\|​\(\|ξSμ\|m−1\+\|ξScμ\|m−1\)\\left\|Y^\{\\mu\}\\right\|\\leq 2m\\left\|\\xi^\{\\mu\}\_\{S\}\\right\|\\left\(\\left\|\\xi^\{\\mu\}\_\{S\}\\right\|\+\\left\|\\xi^\{\\mu\}\_\{S^\{\\mathrm\{c\}\}\}\\right\|\\right\)^\{m\-1\}\\leq 2^\{m\}m\\left\|\\xi^\{\\mu\}\_\{S\}\\right\|\\left\(\\left\|\\xi^\{\\mu\}\_\{S\}\\right\|^\{m\-1\}\+\\left\|\\xi^\{\\mu\}\_\{S^\{\\mathrm\{c\}\}\}\\right\|^\{m\-1\}\\right\)\(B\.157\)Now let us consider theLq\\mathrm\{L\}^\{q\}norms on the uniform distribution onker⁡\(H\)\\ker\(H\): \(slightly abusing notation betweenbbvs\.ξ\\xi\)

∥A⁡\(ξ\)∥q:=\[12k​∑ξ∈ker⁡\(H\)\|A⁡\(ξ\)\|q\]1/q\.\\lVert A\(\\xi\)\\rVert\_\{q\}:=\\left\[\\frac\{1\}\{2^\{k\}\}\\sum\_\{\\xi\\in\\ker\(H\)\}\|A\(\\xi\)\|^\{q\}\\right\]^\{1/q\}\.\(B\.158\)Hölder’s inequality then gives

‖Y‖q\\displaystyle\\left\\lVert Y\\right\\rVert\_\{q\}≤2m​m​‖ξS‖m​q​\(\(‖ξS‖m​q\)m−1\+\(‖ξSc‖m​q\)m−1\)\.\\displaystyle\\leq 2^\{m\}m\\left\\lVert\\xi\_\{S\}\\right\\rVert\_\{mq\}\\left\(\\left\(\\left\\lVert\\xi\_\{S\}\\right\\rVert\_\{mq\}\\right\)^\{m\-1\}\+\\left\(\\left\\lVert\\xi\_\{S^\{\\mathrm\{c\}\}\}\\right\\rVert\_\{mq\}\\right\)^\{m\-1\}\\right\)\.\(B\.159\)
###### Lemma B\.13:

The following inequality holds for anyq≥2q\\geq 2and someq,nq,n\-independentC\>0C\>0:

∥ξS∥q≤C​q​\|S\|\.\\lVert\\xi\_\{S\}\\rVert\_\{q\}\\leq C\\sqrt\{q\|S\|\}\.\(B\.160\)

###### Proof\.

This is a useful generalization of Corollary[A\.16](https://arxiv.org/html/2610.27384#A1.Thmthm16)\(which immediately follows from this result by takingS=\[n\]S=\[n\]\)\. To prove this more general result, we notice the following useful identity, similar to those used in establishing Kramers\-Wannier duality\[[34](https://arxiv.org/html/2610.27384#bib.bib34)\]:

𝔼⁡\[et​ξS\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{e\}^\{t\\xi\_\{S\}\}\\right\]=𝔼\[∏i∈S\(cosht\+ξisinht\)\]=\(cosht\)\|S\|∑Λ⊂S:Λ∈im⁡\(H𝖳\)\(tanht\)\|Λ\|\\displaystyle=\\mathbb\{E\}\\left\[\\prod\_\{i\\in S\}\(\\cosh t\+\\xi\_\{i\}\\sinh t\)\\right\]=\(\\cosh t\)^\{\|S\|\}\\sum\_\{\\Lambda\\subset S:\\Lambda\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\}\(\\tanh t\)^\{\|\\Lambda\|\}<\(cosht\)\|S\|∏i∈S\(1\+∑connected​Λ⊂S:Λ∈im⁡\(H𝖳\),i∈Λ\(tanht\)\|Λ\|\)\\displaystyle<\(\\cosh t\)^\{\|S\|\}\\prod\_\{i\\in S\}\\left\(1\+\\sum\_\{\\text\{connected \}\\Lambda\\subset S:\\Lambda\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\),\\;i\\in\\Lambda\}\(\\tanh t\)^\{\|\\Lambda\|\}\\right\)<\(cosh⁡t\)\|S\|​∏i∈S\(1\+∑s=mn\(e⁡\(m−1\)​ΔB​tanh⁡t\)min⁡\(m,κ​s\)\)\|S\|\\displaystyle<\(\\cosh t\)^\{\|S\|\}\\prod\_\{i\\in S\}\\left\(1\+\\sum\_\{s=m\}^\{n\}\(\\mathrm\{e\}\(m\-1\)\\Delta\_\{\\mathrm\{B\}\}\\tanh t\)^\{\\min\(m,\\kappa s\)\}\\right\)^\{\|S\|\}<exp⁡\[\|S\|​\(log⁡cosh⁡t\+\(e⁡\(m−1\)​ΔB​tanh⁡t\)m1−e⁡\(m−1\)​ΔB​tanh⁡t\)\]=:ec⁡\(t\)​\|S\|,\\displaystyle<\\exp\\left\[\|S\|\\left\(\\log\\cosh t\+\\frac\{\(\\mathrm\{e\}\(m\-1\)\\Delta\_\{\\mathrm\{B\}\}\\tanh t\)^\{m\}\}\{1\-\\mathrm\{e\}\(m\-1\)\\Delta\_\{\\mathrm\{B\}\}\\tanh t\}\\right\)\\right\]=:\\mathrm\{e\}^\{c\(t\)\|S\|\},\(B\.161\)withc⁡\(t\)<t2c\(t\)<t^\{2\}at sufficiently small0<t<t0<10<t<t\_\{0\}<1\(becausem\>2m\>2\)\. In the third line we used the combinatorial fact that there are at most\(e​ΔB​\(ΔC−1\)\)s\(\\mathrm\{e\}\\Delta\_\{\\mathrm\{B\}\}\(\\Delta\_\{\\mathrm\{C\}\}\-1\)\)^\{s\}connected \(on the bit adjacency graph\) clusters in an LDPC code\[[34](https://arxiv.org/html/2610.27384#bib.bib34)\], withm=ΔCm=\\Delta\_\{\\mathrm\{C\}\}, along with the fact that the smallest such cluster ismm\(Corollary[A\.14](https://arxiv.org/html/2610.27384#A1.Thmthm14)\) and check soundness \(Theorem[A\.13](https://arxiv.org/html/2610.27384#A1.Thmthm13)\)\. We see that

𝔼⁡\[et​ξS\]≤e\|S\|​min⁡\(t,c⁡\(t\)\)≤e\|S\|⋅t2/t0\.\\mathbb\{E\}\\left\[\\mathrm\{e\}^\{t\\xi\_\{S\}\}\\right\]\\leq\\mathrm\{e\}^\{\|S\|\\min\(t,c\(t\)\)\}\\leq\\mathrm\{e\}^\{\|S\|\\cdot t^\{2\}/t\_\{0\}\}\.\(B\.162\)Markov’s inequality gives

ℙ\[\|ξS\|\>x\]≤infte\|S\|⋅t2/t0−x​t=e−x2/\(2t0\|S\|\)\.\\mathbb\{P\}\\left\[\|\\xi\_\{S\}\|\>x\\right\]\\leq\\inf\_\{t\}\\mathrm\{e\}^\{\|S\|\\cdot t^\{2\}/t\_\{0\}\-xt\}=\\mathrm\{e\}^\{\-x^\{2\}/\(2t\_\{0\}\|S\|\)\}\.\(B\.163\)\([B\.160](https://arxiv.org/html/2610.27384#A2.E160)\) follows from Gaussian\-like scaling\. More concretely,

∥ξS∥q\\displaystyle\\lVert\\xi\_\{S\}\\rVert\_\{q\}=∫0∞dx\(−∂xℙ\[ξS\>x\]\)xq=q∫0∞dxxq−1ℙ\(ξS≥x\)≤q∫0∞dxxq−1e−x2/\(2t0\|S\|\)\\displaystyle=\\int\\limits\_\{0\}^\{\\infty\}\\mathrm\{d\}x\\left\(\-\\partial\_\{x\}\\mathbb\{P\}\[\\xi\_\{S\}\>x\]\\right\)x^\{q\}=q\\int\\limits\_\{0\}^\{\\infty\}\\mathrm\{d\}x\\;x^\{q\-1\}\\mathbb\{P\}\(\\xi\_\{S\}\\geq x\)\\leq q\\int\\limits\_\{0\}^\{\\infty\}\\mathrm\{d\}x\\;x^\{q\-1\}\\mathrm\{e\}^\{\-x^\{2\}/\(2t\_\{0\}\|S\|\)\}≤q​\(C0​q⋅2​t0​\|S\|\)q/2\\displaystyle\\leq q\(C\_\{0\}q\\cdot 2t\_\{0\}\|S\|\)^\{q/2\}\(B\.164\)for an O\(1\) constantC0C\_\{0\}\. Sinceq1/q→1q^\{1/q\}\\rightarrow 1asqqbecomes large, there exists a constantCCfor which \([B\.160](https://arxiv.org/html/2610.27384#A2.E160)\) holds\. ∎

Now the idea is to use Lemma[B\.13](https://arxiv.org/html/2610.27384#A2.Thmthm13)to bound the tails of the probability distribution ofℰ\\mathcal\{E\}\. A second instrumental ingredient in this bound is the following “sub\-Weibull” tail bound from\[[35](https://arxiv.org/html/2610.27384#bib.bib35)\]\(we are deliberately simplifying/weakening their results, while maintaining sufficiency for our needs\):

###### Theorem B\.14:

LetX1,…,XPX\_\{1\},\\ldots,X\_\{P\}denote independent and identically distributed random variables with𝔼⁡\[X1\]=0\\mathbb\{E\}\[X\_\{1\}\]=0whose probability distribution is “sub\-Weibull”: namely obeys, for some0<α<10<\\alpha<1,

ℙ⁡\(\|X1\|\>x\)≤2​exp⁡\[−\(xx0\)α\]\.\\mathbb\{P\}\(\|X\_\{1\}\|\>x\)\\leq 2\\exp\\left\[\-\\left\(\\frac\{x\}\{x\_\{0\}\}\\right\)^\{\\alpha\}\\right\]\.\(B\.165\)Then there exists a functionℱ⁡\(α\)\\mathcal\{F\}\(\\alpha\)which is positive and finite forα\>0\\alpha\>0such that, for anyt\>0t\>0,

ℙ⁡\(\|∑i=1PXi\|\>ℱ⁡\(α\)​\(t1/α\+P​t\)​x0\)≤2​e−t\\mathbb\{P\}\\left\(\\left\|\\sum\_\{i=1\}^\{P\}X\_\{i\}\\right\|\>\\mathcal\{F\}\(\\alpha\)\\left\(t^\{1/\\alpha\}\+\\sqrt\{Pt\}\\right\)x\_\{0\}\\right\)\\leq 2\\mathrm\{e\}^\{\-t\}\(B\.166\)

The strategy is to apply Theorem[B\.14](https://arxiv.org/html/2610.27384#A2.Thmthm14)as follows: write

Y~​\(ξ\):=Y​\(ξ\)−y\\widetilde\{Y\}\(\\xi\):=Y\(\\xi\)\-y\(B\.167\)wherey<0y<0was defined in \([B\.152](https://arxiv.org/html/2610.27384#A2.E152)\)\. Then𝔼⁡\[Y~\]=0\\mathbb\{E\}\[\\widetilde\{Y\}\]=0\(averaged over codewords\), so we can apply Theorem[B\.14](https://arxiv.org/html/2610.27384#A2.Thmthm14)\. From the triangle inequality,

∥Y~∥q≤∥Y∥q\+y≤2​∥Y∥q\.\\lVert\\widetilde\{Y\}\\rVert\_\{q\}\\leq\\lVert Y\\rVert\_\{q\}\+y\\leq 2\\lVert Y\\rVert\_\{q\}\.\(B\.168\)Next, combining Lemma[B\.13](https://arxiv.org/html/2610.27384#A2.Thmthm13)with \([B\.159](https://arxiv.org/html/2610.27384#A2.E159)\) and the fact thatmax⁡\(\|S\|,\|Sc\|\)≤n\\max\(\|S\|,\|S^\{\\mathrm\{c\}\}\|\)\\leq n, we find

∥Y~∥q≤2​∥Y∥q≤2​m​\(2​C\)m​qm/2​n\(m−1\)/2​\|S\|=:C′​n\(m−1\)/2​\|S\|⋅qm/2\.\\lVert\\widetilde\{Y\}\\rVert\_\{q\}\\leq 2\\lVert Y\\rVert\_\{q\}\\leq 2m\(2C\)^\{m\}q^\{m/2\}n^\{\(m\-1\)/2\}\\sqrt\{\|S\|\}=:C^\{\\prime\}n^\{\(m\-1\)/2\}\\sqrt\{\|S\|\}\\cdot q^\{m/2\}\.\(B\.169\)Then we have the following useful lemma\[[36](https://arxiv.org/html/2610.27384#bib.bib36)\]:

###### Lemma B\.15:

If∥X1∥q≤K​q1/α\\lVert X\_\{1\}\\rVert\_\{q\}\\leq Kq^\{1/\\alpha\}for allqq, then \([B\.165](https://arxiv.org/html/2610.27384#A2.E165)\) holds with

x0≤\(2​elog⁡2\)1/α​K\.x\_\{0\}\\leq\\left\(\\frac\{2\\mathrm\{e\}\}\{\\log 2\}\\right\)^\{1/\\alpha\}K\.\(B\.170\)

We now combine Lemma[B\.15](https://arxiv.org/html/2610.27384#A2.Thmthm15)with \([B\.166](https://arxiv.org/html/2610.27384#A2.E166)\) and \([B\.169](https://arxiv.org/html/2610.27384#A2.E169)\) to find, asn→∞n\\rightarrow\\inftyand withP=A​nm−1P=An^\{m\-1\},Y~\\widetilde\{Y\}must be sub\-Weibull withα=2/m\\alpha=2/m\. More precisely,

ℙ\[\|∑μ=2PYμ−\(P−1\)y\|\>𝒞n\(m−1\)/2\|S\|\(P​t\+tm/2\)\]≤2e−t\\mathbb\{P\}\\left\[\\left\|\\sum\_\{\\mu=2\}^\{P\}Y^\{\\mu\}\-\(P\-1\)y\\right\|\>\\mathcal\{C\}n^\{\(m\-1\)/2\}\\sqrt\{\|S\|\}\\left\(\\sqrt\{Pt\}\+t^\{m/2\}\\right\)\\right\]\\leq 2\\mathrm\{e\}^\{\-t\}\(B\.171\)with

𝒞:=2​ℱ​\(2m\)​C′\.\\mathcal\{C\}:=2\\mathcal\{F\}\\left\(\\frac\{2\}\{m\}\\right\)C^\{\\prime\}\.\(B\.172\)So the tail bound \([B\.171](https://arxiv.org/html/2610.27384#A2.E171)\) is strong when we sett=τ​\|S\|t=\\tau\|S\|\(for constantτ\\tauto be determined\)\. Recall that the regime of interest has\|S\|=β​n\|S\|=\\beta n, and we need the fluctuations in \([B\.171](https://arxiv.org/html/2610.27384#A2.E171)\) to be sufficiently suppressed so that a union bound over all possible\|S\|\|S\|subsets does not find a single favorable spin flip\. In other words, we need

e−τ​β​n​\(n\|S\|\)≪1\\mathrm\{e\}^\{\-\\tau\\beta n\}\\left\(\\begin\{array\}\[\]\{c\}n\\\\ \|S\|\\end\{array\}\\right\)\\ll 1\(B\.173\)or, recalling the binary entropy functionhhdefined in \([A\.45](https://arxiv.org/html/2610.27384#A1.E45)\),

τ​β\>h⁡\(β\)\.\\tau\\beta\>h\(\\beta\)\.\(B\.174\)Note that sinceh⁡\(β\)∼−β​log⁡βh\(\\beta\)\\sim\-\\beta\\log\\betaasβ→0\\beta\\rightarrow 0, we can only hope to do find such aτ\\taufor a fixed positiveβ\\beta, which is what the theorem asks for\.

In any event, let us finalize things\. Forτ\\tauobeying \([B\.174](https://arxiv.org/html/2610.27384#A2.E174)\) we need

0\>\(P−1\)​y\+𝒞​nm/2​β​\(P​τ​β​n\+\(τ​β​n\)m/2\)\+\(2​β​n\)m,0\>\(P\-1\)y\+\\mathcal\{C\}n^\{m/2\}\\sqrt\{\\beta\}\\left\(\\sqrt\{P\\tau\\beta n\}\+\(\\tau\\beta n\)^\{m/2\}\\right\)\+\(2\\beta n\)^\{m\},\(B\.175\)which would ensure that the cutoff in \([B\.171](https://arxiv.org/html/2610.27384#A2.E171)\), along with the positive energy gain fromY1Y^\{1\}given in \([B\.137](https://arxiv.org/html/2610.27384#A2.E137)\), are not enough to pushℰ\>0\\mathcal\{E\}\>0due to the cost of violating many of the \(approximately\) learned checks having arose from theμ=2,…,P\\mu=2,\\ldots,Pcontributions toE^\\widehat\{E\}\. From Corollary[A\.9](https://arxiv.org/html/2610.27384#A1.Thmthm9),

y≥\(1−2​δ\)​ΔB⋅β​n,y\\geq\\ \(1\-2\\delta\)\\Delta\_\{\\mathrm\{B\}\}\\cdot\\beta n,\(B\.176\)for anyδ<1/ΔB\\delta<1/\\Delta\_\{\\mathrm\{B\}\}andβ<γ\\beta<\\gammafor which Theorem[A\.11](https://arxiv.org/html/2610.27384#A1.Thmthm11)ensures we have a\(γ,δ\)\(\\gamma,\\delta\)expander code\. Almost surely asn→∞n\\rightarrow\\infty,

\(1−2​δ\)​ΔB​β⋅A\>𝒞​β​\(A​h​\(β\)\+h​\(β\)m/2\)\+\(2​β\)m\(1\-2\\delta\)\\Delta\_\{\\mathrm\{B\}\}\\beta\\cdot A\>\\mathcal\{C\}\\sqrt\{\\beta\}\\left\(\\sqrt\{Ah\(\\beta\)\}\+h\(\\beta\)^\{m/2\}\\right\)\+\(2\\beta\)^\{m\}\(B\.177\)Solve this quadratic inequality for0<β<γ0<\\beta<\\gammaand call the solutionsA\>Amax​\(β\)A\>A\_\{\\mathrm\{max\}\}\(\\beta\); this establishes \([B\.154](https://arxiv.org/html/2610.27384#A2.E154)\)\. ∎

Theorem[B\.10](https://arxiv.org/html/2610.27384#A2.Thmthm10)and Theorem[B\.12](https://arxiv.org/html/2610.27384#A2.Thmthm12)together imply a clear crossover whenP=Θ⁡\(nm−1\)P=\\mathrm\{\\Theta\}\(n^\{m\-1\}\)where the denseAM establishes basins of stability around each codeword, as claimed in the main text\. Let us now confirm that, as claimed in the main text, codewords are lower energy than random configurations onceP∼nm−2P\\sim n^\{m\-2\}, which we formalize in the proposition below:

###### Proposition B\.16:

Starting at any codeword and flipping a random setSSof bits towards an*unseen*codeword, we find \(using the notation of Theorem[B\.10](https://arxiv.org/html/2610.27384#A2.Thmthm10)\) thatE^​\(σB\)\>E^​\(σ1\)\\widehat\{E\}\(\\sigma^\{B\}\)\>\\widehat\{E\}\(\\sigma^\{1\}\)with high probability asn→∞n\\rightarrow\\inftyifP=nm−2\+ϵP=n^\{m\-2\+\\epsilon\}for anyϵ\>0\\epsilon\>0\.

###### Proof\.

We follow the proof of Theorem[B\.10](https://arxiv.org/html/2610.27384#A2.Thmthm10), but if the bits we flip point us towards an unseen codeword, we simply lose the deterministic\(2​β​n\)m\(2\\beta n\)^\{m\}contribution from \([B\.145a](https://arxiv.org/html/2610.27384#A2.E145.1)\)\. Then we see that

\|𝔼⁡\[ℰ\]\|Var⁡\(ℰ\)=ΔB​\(m−1\)\!​\(1−\(1−2​β\)m−\(2​β\)m\)21−m​\(2​m\)\!/m\!​\(1−\(1−2​β\)m\)​Pnm−2∼nϵ/2\.\\frac\{\|\\mathbb\{E\}\[\\mathcal\{E\}\]\|\}\{\\sqrt\{\\mathrm\{Var\}\(\\mathcal\{E\}\)\}\}=\\frac\{\\Delta\_\{\\mathrm\{B\}\}\(m\-1\)\!\(1\-\(1\-2\\beta\)^\{m\}\-\(2\\beta\)^\{m\}\)\}\{\\sqrt\{2^\{1\-m\}\(2m\)\!/m\!\}\(1\-\(1\-2\\beta\)^\{m\}\)\}\\sqrt\{\\frac\{P\}\{n^\{m\-2\}\}\}\\sim n^\{\\epsilon/2\}\.\(B\.178\)Sinceℰ\\mathcal\{E\}has approximately Gaussian fluctuations,sign⁡\(ℰ\)<0\\mathrm\{sign\}\(\\mathcal\{E\}\)<0almost surely asn→∞n\\rightarrow\\infty\. ∎

BeforeP∼nm−2P\\sim n^\{m\-2\}, we are relatively likely to see a true codeword higher energy than a random state, so it is hardly fair to say that we have “learned” the code at this point\!

It would be very interesting to study the “mixed memories”, which have been studied in dense associative memories trained on random codewords\[[28](https://arxiv.org/html/2610.27384#bib.bib28)\], to the architecture trained on XORSAT codewords\. We leave this to future work\.

## Appendix CLearning latent variables

With a sensible modification, the same TDenseAM architecture described above can \(asymptotically\) optimally recover latent variables – namely, degrees of freedom which are not shown to the model, but which sparsify the energyE^\\widehat\{E\}\. This is*not*achievable for arbitrary problems\[[37](https://arxiv.org/html/2610.27384#bib.bib37)\]\. However, random LDPC codes are a setting where latent variables are often easy to learn, and we will indeed provide some provable guarantees on their learnability in what follows\.

Let us first set up the discussion at a high level\. Divide up the bits of an LDPC code into observed variablesx1,…,xn−n¯x\_\{1\},\\ldots,x\_\{n\-\\overline\{n\}\}which will be given to TDenseAM as training data, and latent variableshn−n¯\+1,…,hnh\_\{n\-\\overline\{n\}\+1\},\\ldots,h\_\{n\}which are not shown\. Notice thatn¯<n\\overline\{n\}<ndenotes the number of latent bits\. The energy function, as before, is a sum over parity\-checks\. We aim to generalize TDenseAM so that it can \(1\) identify latent variableshhand \(2\) learn a correct energy functionE^\\widehat\{E\}\.

As the LDPC problem is perfectly suited to TDenseAM, as discussed above, this will indeed be possible in many circumstances\. The strategy that we will explore is to identify latent variables by their observable shadows, which are defined as follows:

###### Definition C\.1\(Observablemm\-shadow\):

A latent variablehαh\_\{\\alpha\}in an LDPC code with maximal check weightmmhas an observablepp\-shadow if there existp≥2p\\geq 2subsets, any two of whichA,B⊂\{1,…,n−n¯\}A,B\\subset\\\{1,\\ldots,n\-\\overline\{n\}\\\}obey\|A\|,\|B\|≤m−1\|A\|,\|B\|\\leq m\-1and for whichα∪A,α∪B∈im⁡\(H𝖳\)\\alpha\\cup A,\\alpha\\cup B\\in\\mathrm\{im\}\(H^\{\\mathsf\{T\}\}\)\.

Before continuing, let us make a few caveats\. \(1\)hhis not necessarily unique – indeed, we’ll comment more on this shortly\! \(2\) We do not rule out vastly more effective ways to discover latent variables than observable shadows\. Instead, we show that the observable shadow condition allows for a beautifully simple learning algorithm to discover them, and that many random codes guarantee observable shadows for latent bits, even whenn¯=Θ⁡\(n\)\\overline\{n\}=\\mathrm\{\\Theta\}\(n\)\.

Returning to Definition[C\.1](https://arxiv.org/html/2610.27384#A3.Thmthm1), the key observation is thatxA\+xB=0x\_\{A\}\+x\_\{B\}=0is a parity\-check involving at most2​m−22m\-2bits\. Therefore, we propose the following “algorithm” which generalizes TDenseAM to the latent setting\. We should emphasize that exactly as described, this algorithm is tailor\-made for XORSAT/LDPC problems \(as was TDenseAM\); however, there is a natural extension of the philosophy to more generic problems\.

###### Algorithm C\.2\(pp\-latent TDenseAM for XORSAT\):

Thepp\-latent TDenseAM architecture is a deterministic latent variable learner for XORSAT which iteratively proceeds as follows\. Let𝒱0=\[n−n¯\]\\mathcal\{V\}\_\{0\}=\[n\-\\overline\{n\}\]denote the initial set of observed variables\. GivenPPpatterns, use TDenseAM to learn all parity\-checks of weight≤m\\leq m– collect them into a parity\-check matrixH0H\_\{0\}\. Now iterate the following algorithm, beginning att=0t=0:

1. 1\.Run TDenseAM to learn all parity\-checks of weight≤2​m−2\\leq 2m\-2; collect them into parity\-check matrixHt′H\_\{t\}^\{\\prime\}\. Let Zt=span⁡\(Ht′\)/span⁡\(Ht\)Z\_\{t\}=\\mathrm\{span\}\(H\_\{t\}^\{\\prime\}\)/\\mathrm\{span\}\(H\_\{t\}\)\(C\.179\)denote genuinely new higher\-order constraints discovered\.
2. 2\.Suppose there existp⁡\(p−1\)/2p\(p\-1\)/2cosetswA∈𝔽2n/span⁡\(Ht\)w\_\{A\}\\in\\mathbb\{F\}\_\{2\}^\{n\}/\\mathrm\{span\}\(H\_\{t\}\)such that everywAw\_\{A\}has a representative of Hamming weight≤\(m−1\)\\leq\(m\-1\), and for every pair,wA\+wB∈span⁡\(Ht′\)/span⁡\(Ht\)w\_\{A\}\+w\_\{B\}\\in\\mathrm\{span\}\(H\_\{t\}^\{\\prime\}\)/\\mathrm\{span\}\(H\_\{t\}\)\. Then introduce alatent bithhsuch that the following parity\-checks are obeyed: h\+wA=0\.h\+w\_\{A\}=0\.\(C\.180\)In other words,hhhas an observablepp\-shadow \(Definition[C\.1](https://arxiv.org/html/2610.27384#A3.Thmthm1)\)\.
3. 3\.If nohhis found, terminate the process\. Else, appendhhto the observed variables:𝒱t\+1:=𝒱t∪\{h\}\\mathcal\{V\}\_\{t\+1\}:=\\mathcal\{V\}\_\{t\}\\cup\\\{h\\\}\. Append learned parity\-checks \([C\.180](https://arxiv.org/html/2610.27384#A3.E180)\) toHtH\_\{t\}to makeHt\+1H\_\{t\+1\}\. Then sendt→t\+1t\\rightarrow t\+1and repeat\.

The 2\-latent TDenseAM is an aggressive learner, but will necessarily introduce many redundant latent variables\. As a simple example, ifm=3m=3and we observex1\+x2\+x3\+x4=0x\_\{1\}\+x\_\{2\}\+x\_\{3\}\+x\_\{4\}=0, the 2\-latent learner does not know whether to introducex1\+x2\+h=x3\+x4\+h=0x\_\{1\}\+x\_\{2\}\+h=x\_\{3\}\+x\_\{4\}\+h=0vs\.x1\+x3\+h′=x2\+x4\+h′=0x\_\{1\}\+x\_\{3\}\+h^\{\\prime\}=x\_\{2\}\+x\_\{4\}\+h^\{\\prime\}=0\. In contrast, the 3\-latent TDenseAM is more cautious; as such one may expect for it to have a better performance guarantee\. Indeed, the 3\-latent learning rule is analogous to those which have been used in previous studies of latent sparse learning\[[25](https://arxiv.org/html/2610.27384#bib.bib25),[26](https://arxiv.org/html/2610.27384#bib.bib26)\]\. In the context of the XORSAT problem, we can prove that the 3\-latent TDenseAM is capable of learning an extensive number of latent variables, with high probability, on a random realization of the problem\.

###### Theorem C\.3:

Consider a random\(ΔB,ΔC\)\(\\Delta\_\{\\mathrm\{B\}\},\\Delta\_\{\\mathrm\{C\}\}\)LDPC code with5≤ΔB<ΔC5\\leq\\Delta\_\{\\mathrm\{B\}\}<\\Delta\_\{\\mathrm\{C\}\}, and6≤ΔC≤96\\leq\\Delta\_\{\\mathrm\{C\}\}\\leq 9ifΔB=5\\Delta\_\{\\mathrm\{B\}\}=5\. Decompose the bit setB=Bobs⊔BlatB=B\_\{\\mathrm\{obs\}\}\\sqcup B\_\{\\mathrm\{lat\}\}into observed and latent bits\. There existsO⁡\(1\)\\mathrm\{O\}\(1\)constantγ\\gammasuch that, for sufficiently largenn, if\|Blat\|<γ​n\|B\_\{\\mathrm\{lat\}\}\|<\\gamma n, the 3\-latent TDenseAM architecture will learn every latent bit correctly \(and no spurious latent bits\) almost surely asn→∞n\\rightarrow\\infty, after seeing at most

P=\(1\+ϵ\)​4​\(ΔC−1\)a2​log⁡nP=\(1\+\\epsilon\)\\frac\{4\(\\Delta\_\{\\mathrm\{C\}\}\-1\)\}\{a^\{2\}\}\\log n\(C\.181\)random codewords as training examples, for anyϵ\>0\\epsilon\>0\.

###### Proof\.

Theorem[A\.11](https://arxiv.org/html/2610.27384#A1.Thmthm11)shows that a random LDPC code is a\(γ,δ\)\(\\gamma,\\delta\)expander with some O\(1\)γ\\gamma, and anyδ\>1/ΔB\\delta\>1/\\Delta\_\{\\mathrm\{B\}\}, almost surely asn→∞n\\rightarrow\\infty\. The strategy of the proof will be to assume\(γ,δ\)\(\\gamma,\\delta\)\-expansion with suitableγ\\gammaandδ\\delta\(which holds with high probability\), and then demonstrate that conditioned on this likely event, the strict latent TDenseAM learns a latent variable if and only if it is inBlatB\_\{\\mathrm\{lat\}\}\. The key idea is that a certain kind of observable 3\-shadow guarantees \(certifies\) the existence of a latent bit:

###### Lemma C\.4:

Define a clean 3\-shadow as a triple of observed parity\-checks of size2​ΔC−22\\Delta\_\{\\mathrm\{C\}\}\-2:

xA\+xB=xB\+xC=xC\+xA=0x\_\{A\}\+x\_\{B\}=x\_\{B\}\+x\_\{C\}=x\_\{C\}\+x\_\{A\}=0\(C\.182\)with sets\|A\|=\|B\|=\|C\|=ΔC−1\|A\|=\|B\|=\|C\|=\\Delta\_\{\\mathrm\{C\}\}\-1, all three sets disjoint, and none of the parity\-checks explainable as the union of two smaller observed checks\. Then, given the code is a\(γ,δ\)\(\\gamma,\\delta\)\-expander with

δ<ΔC\+26​ΔC,\\delta<\\frac\{\\Delta\_\{\\mathrm\{C\}\}\+2\}\{6\\Delta\_\{\\mathrm\{C\}\}\},\(C\.183\)a clean 3\-shadow certifies the existence of a unique \(latent\) bith0h\_\{0\}such that the code had parity\-checks

xA\+h0=xB\+h0=xC\+h0=0\.x\_\{A\}\+h\_\{0\}=x\_\{B\}\+h\_\{0\}=x\_\{C\}\+h\_\{0\}=0\.\(C\.184\)

###### Proof\.

From Theorem[A\.13](https://arxiv.org/html/2610.27384#A1.Thmthm13), we see that if\|H𝖳​s\|=O⁡\(1\)\|H^\{\\mathsf\{T\}\}s\|=\\mathrm\{O\}\(1\)then we may take\|s\|=O⁡\(1\)\|s\|=\\mathrm\{O\}\(1\)with high probability asn→∞n\\rightarrow\\infty\. This puts us in the regime where Definition[A\.7](https://arxiv.org/html/2610.27384#A1.Thmthm7)applies: for any\|s\|<γ​n\|s\|<\\gamma n, the maximal number of parity\-checks that can add together to make a parity\-check of size2​ΔC−22\\Delta\_\{\\mathrm\{C\}\}\-2obeys:

\|H𝖳​s\|=2​ΔC−2≥ΔC​\(1−2​δ\)​\|s\|\.\|H^\{\\mathsf\{T\}\}s\|=2\\Delta\_\{\\mathrm\{C\}\}\-2\\geq\\Delta\_\{\\mathrm\{C\}\}\(1\-2\\delta\)\|s\|\.\(C\.185\)Clearly we must have\|s\|≥2\|s\|\\geq 2, and the inequality is violated at\|s\|=3\|s\|=3if \([C\.183](https://arxiv.org/html/2610.27384#A3.E183)\) is obeyed\. Hence \([C\.183](https://arxiv.org/html/2610.27384#A3.E183)\) ensures that every parity\-check of size2​ΔC−22\\Delta\_\{\\mathrm\{C\}\}\-2can be written as the sum of exactly two parity\-checks\.

Now, suppose that we see the pattern \([C\.182](https://arxiv.org/html/2610.27384#A3.E182)\)\. There are exactly two ways this can happen\. The first is that we see the pattern \([C\.184](https://arxiv.org/html/2610.27384#A3.E184)\), whereh0h\_\{0\}may or may not be latent – if it is not, we clearly should not introduce a new latent variable\! The other possibility is that

A\\displaystyle A=A0⊔\{x,y\},\\displaystyle=A\_\{0\}\\sqcup\\\{x,y\\\},\(C\.186a\)B\\displaystyle B=B0⊔\{x,z\},\\displaystyle=B\_\{0\}\\sqcup\\\{x,z\\\},\(C\.186b\)C\\displaystyle C=C0⊔\{y,z\}\.\\displaystyle=C\_\{0\}\\sqcup\\\{y,z\\\}\.\(C\.186c\)Because by assumption we have seen3​\(ΔC−1\)3\(\\Delta\_\{\\mathrm\{C\}\}\-1\)observed variables between the observed checks \([C\.182](https://arxiv.org/html/2610.27384#A3.E182)\), the pattern \([C\.186](https://arxiv.org/html/2610.27384#A3.E186)\) can only be observed if all bits are already observed – therefore there will be no latent variables\. Therefore, there is a latent variable if and only if the constraints \([C\.182](https://arxiv.org/html/2610.27384#A3.E182)\) cannot be deduced from any of the observed lower\-order constraints\. ∎

It is clear that seeing a clean 3\-shadow of a latent variable is a guarantee \(with high probability\) that we will correctly infer the intended latent variable\. Now we prove that:

###### Lemma C\.5:

If\|Blat\|<γ​n\|B\_\{\\mathrm\{lat\}\}\|<\\gamma n, then almost surely asn→∞n\\rightarrow\\infty, there exists a latent variable with a clean 3\-shadow\.

Note that we will apply this lemma at each iteration of Algorithm[C\.2](https://arxiv.org/html/2610.27384#A3.Thmthm2), soBlatB\_\{\\mathrm\{lat\}\}is shrinking as we add more latent variables to the observed set\.

###### Proof\.

If the latent subgraph of the LDPC code was a tree, this property would follow immediately, becauseΔB≥5\\Delta\_\{\\mathrm\{B\}\}\\geq 5\. To prove this fact, we will need to show that the latent subgraph is “close enough” to a tree to ensure the existence of a clean 3\-shadow\.

LetBshare⊆BB\_\{\\text\{share\}\}\\subseteq Bdenote the set of bits which have the following property:

Bshare:=\{b∈B:\|∂b∩∂b′\|\>1​for some​b≠b′∈B\}\.B\_\{\\text\{share\}\}:=\\\{b\\in B:\|\\partial b\\cap\\partial b^\{\\prime\}\|\>1\\text\{ for some \}b\\neq b^\{\\prime\}\\in B\\\}\.\(C\.187\)We observe thatb∈Bshareb\\in B\_\{\\text\{share\}\}if and only ifbbis contained in a subgraph of the Tanner graph isomorphic to a 4\-cycle\. Furthermore, Proposition[A\.12](https://arxiv.org/html/2610.27384#A1.Thmthm12)shows us that almost surely,BshareB\_\{\\mathrm\{share\}\}is a collection of disconnected 4\-cycles in the Tanner graph\. Indeed, suppose that there was a set of 3 latent bits, all of which were inBshareB\_\{\\mathrm\{share\}\}and connected to each other\. This would require a finite subgraph of the Tanner graph with 2 loops, which happens with probability∼n−1\\sim n^\{\-1\}and can be neglected\. An analogous argument further shows that for any fixed O\(1\) distancer0r\_\{0\},BshareB\_\{\\mathrm\{share\}\}cannot contain two pairs of bits within a fixed distancer0r\_\{0\}of each other\.

With this in mind, we now provide a proof by contradiction for the lemma\. Suppose that the latent set had no clean 3\-shadows\. Without loss of generality, we may assume thatBlatB\_\{\\mathrm\{lat\}\}is connected: disconnected components cannot hinder learning any other component\. BecauseBlatB\_\{\\mathrm\{lat\}\}has no clean 3\-shadows, every bit inBlat∖BshareB\_\{\\mathrm\{lat\}\}\\setminus B\_\{\\text\{share\}\}must have at most 2 unique\-neighbor checks, while every bit inBlat∩BshareB\_\{\\mathrm\{lat\}\}\\cap B\_\{\\text\{share\}\}has at most 3 unique\-neighbor checks\. Comparing with the definition of expansion, we have that

ΔB​\(1−2​δ\)​\|Blat\|\\displaystyle\\Delta\_\{\\mathrm\{B\}\}\(1\-2\\delta\)\|B\_\{\\text\{lat\}\}\|≤\|∂uBlat\|≤2​\(\|Blat\|−\|Blat∩Bshare\|\)\+3​\|Blat∩Bshare\|\\displaystyle\\leq\|\\partial\_\{\\mathrm\{u\}\}B\_\{\\text\{lat\}\}\|\\leq 2\\left\(\|B\_\{\\text\{lat\}\}\|\-\|B\_\{\\text\{lat\}\}\\cap B\_\{\\text\{share\}\}\|\\right\)\+3\|B\_\{\\text\{lat\}\}\\cap B\_\{\\text\{share\}\}\|=2​\|Blat\|\+\|Blat∩Bshare\|\.\\displaystyle=2\|B\_\{\\text\{lat\}\}\|\+\|B\_\{\\text\{lat\}\}\\cap B\_\{\\text\{share\}\}\|\.\(C\.188\)Notice that as long as we enforce \([C\.183](https://arxiv.org/html/2610.27384#A3.E183)\) andΔB≥5\\Delta\_\{\\mathrm\{B\}\}\\geq 5andΔC≥6\\Delta\_\{\\mathrm\{C\}\}\\geq 6,

ΔB​\(1−2​δ\)≥5​\(1−818\)=259\>2\.\\Delta\_\{\\mathrm\{B\}\}\(1\-2\\delta\)\\geq 5\\left\(1\-\\frac\{8\}\{18\}\\right\)=\\frac\{25\}\{9\}\>2\.\(C\.189\)Therefore, \([C\.188](https://arxiv.org/html/2610.27384#A3.Ex1)\) can only hold if

\|Blat\|≤97​\|Blat∩Bshare\|\.\|B\_\{\\text\{lat\}\}\|\\leq\\frac\{9\}\{7\}\|B\_\{\\text\{lat\}\}\\cap B\_\{\\text\{share\}\}\|\.\(C\.190\)
Let us analyze \([C\.190](https://arxiv.org/html/2610.27384#A3.E190)\) on each connected component ofBlatB\_\{\\mathrm\{lat\}\}\. Clearly a single isolated point inBshareB\_\{\\mathrm\{share\}\}is not possible, and such an isolated latent bit has a clean\-ΔB≥5\\Delta\_\{\\mathrm\{B\}\}\\geq 5\-shadow\. So now consider the case whereBshareB\_\{\\mathrm\{share\}\}is not empty\. If there is a single pair of bits inBshareB\_\{\\mathrm\{share\}\}, then \([C\.190](https://arxiv.org/html/2610.27384#A3.E190)\) implies that2≤\|Blat\|<18/7<32\\leq\|B\_\{\\mathrm\{lat\}\}\|<18/7<3\. So the entire connected latent component is of shared bits, which is a contradiction: each such bit still has a clean\(ΔB−2\)≥3\(\\Delta\_\{\\mathrm\{B\}\}\-2\)\\geq 3\-shadow\. If there are multiple disconnected components ofBshareB\_\{\\mathrm\{share\}\}in the same connected component ofBlatB\_\{\\mathrm\{lat\}\}, then we know there is a path of length≥r0\\geq r\_\{0\}separating them for anyr0r\_\{0\}\. Using this result, we deduce that the largest possible density

\|Blat∩Bshare\|\|Blat\|≤2​m2​m\+\(m−1\)​r0\\frac\{\|B\_\{\\mathrm\{lat\}\}\\cap B\_\{\\mathrm\{share\}\}\|\}\{\|B\_\{\\mathrm\{lat\}\}\|\}\\leq\\frac\{2m\}\{2m\+\(m\-1\)r\_\{0\}\}\(C\.191\)arises whenBlatB\_\{\\mathrm\{lat\}\}is a tree\-like subgraph withmmBshareB\_\{\\mathrm\{share\}\}pairs separated byr0r\_\{0\}\. Taker0=2r\_\{0\}=2: ifm\>1m\>1, we find that \([C\.191](https://arxiv.org/html/2610.27384#A3.E191)\) contradicts \([C\.190](https://arxiv.org/html/2610.27384#A3.E190)\)\. Therefore, in all possible cases, we have found a contradiction, completing the proof\. ∎

It is now clear that the strict latent TDenseAM will provably converge by learning, one at a time, the latent bits by detecting their clean 3\-shadows\. Lemma[C\.4](https://arxiv.org/html/2610.27384#A3.Thmthm4)requires the condition \([C\.183](https://arxiv.org/html/2610.27384#A3.E183)\) which enforcesΔC<10\\Delta\_\{\\mathrm\{C\}\}<10ifΔB=5\\Delta\_\{\\mathrm\{B\}\}=5, while otherwise placing no constraints ifΔB\>5\\Delta\_\{\\mathrm\{B\}\}\>5\. The 3\-latent TDenseAM architecture correctly learns every visible weight\-\(2​ΔC−2\)\(2\\Delta\_\{\\mathrm\{C\}\}\-2\)constraint, by Proposition[B\.1](https://arxiv.org/html/2610.27384#A2.Thmthm1), if we train on the number of patterns given in \([C\.181](https://arxiv.org/html/2610.27384#A3.E181)\), almost surely asn→∞n\\rightarrow\\infty\. Therefore the 3\-latent TDenseAM succeeds\. ∎

## References

## References

- \[1\]Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra, “Grokking: Generalization beyond overfitting on small algorithmic datasets,” arXiv preprint arXiv:2201\.02177 \(2022\)\.
- \[2\]Andrey Gromov,[“Grokking modular arithmetic,”](https://arxiv.org/abs/2301.02679)\(2023\),[arXiv:2301\.02679 \[cs\.LG\]](http://arxiv.org/abs/2301.02679)\.
- \[3\]Mohamad Amin Mohamadi, Zhiyuan Li, Lei Wu, and Danica J\. Sutherland, “Why do you grok? A theoretical analysis on grokking modular addition,” in*Proceedings of the 41st International Conference on Machine Learning*, edited by Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp \(PMLR, 2024\) pp\. 35934–35967\.
- \[4\]John X Morris, Chawin Sitawarin, Chuan Guo, Narine Kokhlikyan, G Edward Suh, Alexander M Rush, Kamalika Chaudhuri, and Saeed Mahloujifar, “How much do language models memorize?” arXiv preprint arXiv:2505\.24832 \(2025\)\.
- \[5\]Ziyue Li, Chenrui Fan, and Tianyi Zhou, “Grokking in llm pretraining? monitor memorization\-to\-generalization without test,” in*International Conference on Learning Representations*, Vol\. 2026 \(2026\) pp\. 89561–89583\.
- \[6\]Gowthami Somepalli, Vasu Singla, Micah Goldblum, Jonas Geiping, and Tom Goldstein, “Diffusion art or digital forgery? investigating data replication in diffusion models,” in*2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\)*\(IEEE, 2023\) pp\. 6048–6058\.
- \[7\]Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace, “Extracting training data from diffusion models,” in*32nd USENIX security symposium \(USENIX Security 23\)*\(2023\) pp\. 5253–5270\.
- \[8\]Bao Pham, Gabriel Raya, Matteo Negri, Mohammed J Zaki, Luca Ambrogioni, and Dmitry Krotov, “Memorization to generalization: Emergence of diffusion models from associative memory,” arXiv preprint arXiv:2505\.21777 \(2025\)\.
- \[9\]Tony Bonnaire, Raphaël Urfin, Giulio Biroli, and Marc Mézard, “Why diffusion models don’t memorize: The role of implicit dynamical regularization in training,” Advances in Neural Information Processing Systems38, 141266–141286 \(2026\)\.
- \[10\]Dmitry Krotov and John J Hopfield, “Dense associative memory for pattern recognition,” Proc\. NeurIPS30, 1180 \(2016\)\.
- \[11\]John J\. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” Proc\. Natl\. Acad\. Sci\.79, 2554–2558 \(1982\)\.
- \[12\]Michael Sipser and Daniel A\. Spielman, “Expander codes,”[IEEE Transactions on Information Theory42, 1710–1722 \(1996\)](https://doi.org/10.1109/18.556667)\.
- \[13\]T\. Richardson and R\. Urbanke,*Modern Coding Theory*\(Cambridge University Press, 2008\)\.
- \[14\]Dmitry Krotov and John Hopfield, “Dense associative memory is robust to adversarial inputs,” Neural computation30, 3151–3167 \(2018\)\.
- \[15\]L\. G\. Valiant, “A theory of the learnable,” Communications of the ACM27, 1134 \(1984\)\.
- \[16\]Pradeep Ravikumar, Martin J\. Wainwright, and John D\. Lafferty, “High\-dimensional Ising model selection usingℓ1\\ell\_\{1\}\-regularized logistic regression,”[The Annals of Statistics38, 1287–1319 \(2010\)](https://doi.org/10.1214/09-AOS691),[arXiv:0804\.4202](http://arxiv.org/abs/0804.4202)\.
- \[17\]Guy Bresler, “Efficiently learning Ising models on arbitrary graphs,” in[*Proceedings of the Forty\-Seventh Annual ACM Symposium on Theory of Computing*](https://doi.org/10.1145/2746539.2746631), STOC ’15 \(Association for Computing Machinery, 2015\) pp\. 771–782,[arXiv:1411\.6156](http://arxiv.org/abs/1411.6156)\.
- \[18\]Marc Vuffray, Sidhant Misra, Andrey Y\. Lokhov, and Michael Chertkov, “Interaction screening: Efficient and sample\-optimal learning of Ising models,” in*Advances in Neural Information Processing Systems*, Vol\. 29 \(Curran Associates, Inc\., 2016\) pp\. 2595–2603,[arXiv:1605\.07252](http://arxiv.org/abs/1605.07252)\.
- \[19\]Adam R\. Klivans and Raghu Meka, “Learning graphical models using multiplicative weights,” in[*2017 IEEE 58th Annual Symposium on Foundations of Computer Science \(FOCS\)*](https://doi.org/10.1109/FOCS.2017.39)\(IEEE, 2017\) pp\. 343–354,[arXiv:1706\.06274](http://arxiv.org/abs/1706.06274)\.
- \[20\]Marc Mézard and Andrea Montanari,*Information, Physics, and Computation*\(Oxford University Press, Oxford, 2009\)\.
- \[21\]Anindya De, Ilias Diakonikolas, and Rocco A\. Servedio, “Inverse problems in approximate uniform generation,” Electronic Colloquium on Computational Complexity19, 152 \(2012\), eCCC Report TR12\-152,[arXiv:1211\.1722](http://arxiv.org/abs/1211.1722)\.
- \[22\]Anindya De, Ilias Diakonikolas, and Rocco A\. Servedio, “Learning from satisfying assignments,” in[*Proceedings of the Twenty\-Sixth Annual ACM\-SIAM Symposium on Discrete Algorithms*](https://doi.org/10.1137/1.9781611973730.33), SODA ’15 \(Society for Industrial and Applied Mathematics, 2015\) pp\. 478–497\.
- \[23\]M\. Cluzeau and J\-P\. Tillich, “On the code reverse engineering problem,” in*Proc\. IEEE\. Int\. Symp\. Inf\. Th\. 2008*\(2008\) p\. 634\.
- \[24\]T\. Kaufman and M\. Sudan, “Sparse random linear codes are locally decodable and testable,” Proc\. FOCS48, 590 \(2007\)\.
- \[25\]Guy Bresler, Frederic Koehler, and Ankur Moitra, “Learning restricted Boltzmann machines via influence maximization,” in[*Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing*](https://doi.org/10.1145/3313276.3316372), STOC ’19 \(Association for Computing Machinery, 2019\) pp\. 828–839,[arXiv:1805\.10262](http://arxiv.org/abs/1805.10262)\.
- \[26\]Guy Bresler and Rares\-Darius Buhai, “Learning restricted Boltzmann machines with sparse latent variables,” in*Advances in Neural Information Processing Systems*, Vol\. 33 \(Curran Associates, Inc\., 2020\)[arXiv:2006\.04166 \[cs\.LG\]](http://arxiv.org/abs/2006.04166)\.
- \[27\]Dmitry Krotov, Benjamin Hoover, Parikshit Ram, and Bao Pham, “Modern methods in associative memory,” arXiv preprint arXiv:2507\.06211 \(2025\)\.
- \[28\]Véronique Gayrard, “Mixed memories in Hopfield networks,”[arXiv:2504\.04879](http://arxiv.org/abs/2504.04879)\.
- \[29\]A\. Lucas, “Learning modular addition as a latent SAT problem,” \(unpublished\)\.
- \[30\]B\. Bollobás,*Random Graphs*,2nd2^\{\\mathrm\{nd\}\}ed\. \(Cambridge University Press, 2001\)\.
- \[31\]A\. Békéssy, P\. Békéssy, and J\. Komlós, “Asymptotic enumeration of regular matrices,” Studia Sci\. Math\. Hungar\.7, 343 \(1972\)\.
- \[32\]W\. C\. S\. Suen, “A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph,” Random Struct\. Alg\.1, 231 \(1990\)\.
- \[33\]S\. Janson, “New versions of Suen’s correlation inequality,” Random Struct\. Alg\.13, 467 \(1998\)\.
- \[34\]Yifan Hong, Jinkang Guo, and Andrew Lucas, “Quantum memory at nonzero temperature in a thermodynamically trivial system,”[Nature Commun\.16, 316 \(2025\)](https://doi.org/10.1038/s41467-024-55570-7),[arXiv:2403\.10599 \[quant\-ph\]](http://arxiv.org/abs/2403.10599)\.
- \[35\]Arun Kumar Kuchibhotla and Abhishek Chakrabortty, “Moving beyond sub\-Gaussianity in high\-dimensional statistics: applications in covariance estimation and linear regression,”[Information and Inference11, 1389–1456 \(2022\)](http://dx.doi.org/10.1093/imaiai/iaac012)\.
- \[36\]Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel, “Sub‐Weibull distributions: Generalizing sub‐Gaussian and sub‐exponential properties to heavier tailed distributions,”[Stat9, 318 \(2020\)](https://doi.org/10.1002/sta4.318)\.
- \[37\]M\. Kearns and L\. Valiant, “Cryptographic Limitations on Learning Boolean Formulae and Finite Automata,” J\. ACM41, 67 \(1994\)\.