Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Authors: Artur Back de Luca
George Giapitzakis
Kimon Fountoulakis
Venue: NeurIPS 2025 poster ()
Keywords: neural networks
arithmetic
instruction execution
Primary area: theory
TL;DR: We show that a two-layer NTK-trained network can exactly execute algorithmic instructions—including addition, multiplication, and SBN—using only logarithmically many examples, via training set orthogonalization and correlation control.

Abstract: Neural networks are known for their ability to approximate smooth functions, yet they fail to generalize perfectly to unseen inputs when trained on discrete operations. Such operations lie at the heart of algorithmic tasks such as arithmetic, which is often used as a test bed for algorithmic execution in neural networks. In this work, we ask: can neural networks learn to execute binary-encoded algorithmic instructions exactly? We use the Neural Tangent Kernel (NTK) framework to study the training dynamics of two-layer fully connected networks in the infinite-width limit and show how a sufficiently large ensemble of such models can be trained to execute exactly, with high probability, four fundamental tasks: binary permutations, binary addition, binary multiplication, and Subtract and Branch if Negative (SBN) instructions. Since SBN is Turing-complete, our framework extends to computable functions. We show how this can be efficiently achieved using only logarithmically many training data. Our approach relies on two techniques: structuring the training data to isolate bit-level rules, and controlling correlations in the NTK regime to align model predictions with the target algorithmic executions.

Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Artur Back de Luca' University of Waterloo
George Giapitzakis" University of Waterloo ggiapitz@uuatrlloo.c ca
Kimon Fountoulakis University of Waterloo
abackdel@uwaterloo.co
kfountou@uraterloo.cco
Abstract
Neural networks are known for their ability to approximate smooth functions, yet they fail to generalize perfectly to unseen inputs when trained on discrete operations. Such operations lie the heart of algorithmic tasks such as arithmetic, which is often used as a test bed for algorithmic execution in neural networks. In this work, we ask: can neural networks learn to execute binary-encoded algorithmic instructions exactly? We use the Neural Tangent Kernel (NTK) framework to study the training dynamics of two-layer fully connected networks in the infinite-widthe limit and show how sufficiently large ensemble of such models can be trained execute exactly, with high probability. four fundamental tasks: binary permutations, binary addition, binary multiplication, and Subtract and Branch if Negative (SBN) instructions. Since SBN is Turrng-complett our framework extends to computable functions. We show how this be efficiently achieved using only logarithmically many training data. Our approach relies on two techniques: structuring the training data isolate bit-level rules, and controlling correlations in the NTK regime align model predictions with the target algorithmic executions.
Introduction
There has been growing interest in the computational capabilities and efficiency of neural networks both from theoretical and empirical perspective 77 T6 21 288, 31, 34). Most works have either demonstrated the expressive power of different architectures through simulation results or learnability from probably approximately correct (PAC) viewpoint. While important, the mere existence of parameter configurations that realize a specific computation or generalization bound does not offer insight into the ability learn execute algorithm through gradient- based training. In fact, simulating algorithmic instructions with neural networks often involves approximating discontinuous functions that gradient descent is difficult to converge with standard training datasets ..]
By modeling training with the Neural Tangent Kernel (NTK), we prove that two-layer fully connected networks in the wnith limit can learn to iteratively execute binary permutations, binary addition, binary multiplication, and SBN instructions with a logarithmic number of examples, or cquivalently, number of examples polynomial in the input bit size. Rather than training on traditional input-output pairs, we exploit the locality of these algorithms by casting each step as a set of templates. We show that training with these local templates is sufficient for full algorithmic execution when composed across iterations of a loop. To our knowledge, this the first SYTK-base proof of exact leamability for these tasks. A high-level overview of approach is shown in Figure [
Contributions. Our approach is built on two key innovations that overcome the interference and ambiguity in training data that can usually create problems for neural learning for discrete tasks:
Algorithmic template representation: We demonstrate how to design training data that represent local computations (i.c., operating only subset of bits) that be composed
39th Conference on Neural Information Processing Systems (NcurIPS 2025).
* Equual contribution

---

Algorithm
Representation
Execution
Function binary_ tdd.iiiiiooonooo.
(0.1)
e 0ffa
Zor 1-1 to E:
bitwiae aus
cvpra batwine sun (p.))
Eide X.3)
caszy propagation
Syvv carry propapapopag (p.9))
Rounding
end For
Pr F. I... Pi
return le [s]
and for
sel Pacley
Rarjpu]]
Figure 1: Simplified illustration of the framework used in our analysis. The left panel shows example algorithm (binary addition) where each function, highlighted in blue and red, is translated into binary training instructions shown in the central panel with matching colors. Each instruction specifies a condition over part of the current algorithm state and maps it to a corresponding output. Instructions are grouped into blocks, indicated by boxed column labels in A' and V each representing a subset of the input state, For binary addition, some blocks represent segments of the summands, while others reflect the carry state. For the applications discussed Section 6 this block structure allows the number of instructions in A' and ) to scale linearly with bit length f. The right-most panel shows how instructions are used within an iterative framework update the state vector S;, which serves as input to the neural network at the i-th step. The state is first encoded, as described in 5] before being passed to the model. In the NTK regime, we show that the network performs template matching against training samples to execute the appropriate instructions. As at; evolves, it activates new templates, progressing through the algorithm. Predictions are rounded at each step to mitigate noise, and repeating this process reproduces the algorithm's 's full execution.
Section
to execute complete algorithms. Each algorithmic instruction is represented by "templates" " and entire algorithms (e.g., binary permutations, binary addition, binary multiplication, and SBN instruction execution) can be executed by iteratively matching these templates. The total number of templates is logarithmic in the number of all possible inputs.
2. Provable exact learnability: We prove that, by training on an orthonormalized version of our templates, we can control unwanted correlations in the NTK regime and show that an ensemble of two-layer fully connected networks in the infinite-width limit can learn to execute algorithmic instructions exactly with high probability.
2
Literature review
The NTK framework 14] provides insight into continuous-time time gradient descent (gradient flow) in fully connected feed-forwal neural networks. has been extended to discrete gradient descent and generalized to other architectures like recurrent neural networks (RNNs) and Transformers
18
Although NTK theory has been widely developed, few works offer task-specific guarantees. Notable examples include [3) which proves that Transformers can generalize unseen symbols for a class pattern-matchin language tasks. Our work addresses different setting: we show that shallow hoed-forward neural networks in the -iint limit trained by gradient descent can learn to exactly execute algorithmic instructions using a logarithmic number examples.
39
40.
Complementing NTK- results, other studies have demonstrated the expressive power of neural architectures by simulating algorithmic tasks. Following this approach, [34] proves that RNNs are complee and [1] demonstrates that RNNs can solve the shortest path problem and approxi- mate solutions to the knapsack problem. Similarly, simulation results on Transformers also establish Turing completeness 28 and present constructive solutions that generalize across input lengths for arithmetic tasks 44, linear algebra 7 graph-related problems [1, and parallel computation (2). From a learnability perspective, (37 provides statistical guarantees for learning turing-computable functions, while 20 shows that predictors trained auto-regressively can approximate any such func- tions. However, these approaches either depend on hand-crafted parameter configurations without

---

training or build upon the PAC framework, and therefore do not address the core question of exact learaailiiyy explored in this work.
Learning to execute algorithms has been the focus of numerous empirical studies. These works explore architectural modifications and prompting techniques, particularly aimed improving generalization in arithmetic tasks [5. 6 15 21
23 24 27 29 31 36 38 42). In this context, [16] introduced the Neural GPU, which learns binary addition and multipiication and generalizes to sequences longer than those seen in training. Similarly,
(2
3 proposed the Neural Arithmetic Logic Unit (NALU), which incorporates arithmetic operations into network modules to improve generalization. This approach was further refined in [19] with the introduction of the Neural Addition Unit (NAU) and Neural Multiplication Unit (NMU), offering better stability and convergence. More recent work aims to enhance the length generalization capabilities of Transformers through improved Positional Encodings 15 30 32 43), the use of scratchpads (26), and prompting techniques for large language models (LLMss) such as Shain-of-TThoulle (Co'T) programming [5] [ These empirical efforts provide practical methods to improve both in-distribution and -iitrri-dittiittooonn performance of neural networks on arithmetic tasks. However, they lack formal guarantees regarding the conditions under which generalization occurs. Our theoretical analysis offers precise sufficient criteria under which a neural network in the infinite-width limit can provably learn to execute algorithmic instructions.
3 Notation and preliminaries
Throughout the text, we use boldface to denote vectors. The symbols 1 and O denote the vector of all ones and zeros of appropriate length, respectively. We use the notation [n] to refer to the set the Euclidean norm of æ. We {1, ........ n3. For a vector R" we denote by ||~||| := V z denote the n X n identity matrix by L..
Model and NTK Results. We provide an overview of the theory used to derive results. We refer the reader to (9] for a comprehensive treatment of the NTK theory. We work with two-layer, ReLU- activated fully connected feed-forwand neural networks with bias. Concretely, the architecture W2 ReLU(WWar)) where W R W22 E |=*X xk and n E N is the hidden dimension. The weights are initialized according the NTK parametrization as W = a= w and 5) = ow
is defined the function F R& R* with F(x))
w where wiy and wi, are trainable parameters initialized i.i.d. from standard Gaussian distribution. When nA - oc, the empirical NTK kernel WWw' F Fax') converges to the deterministic limit:
given by V WWw
(x,x')= = x x
||0|| ||=0|| ((T 0) cos f + sin))) La R
(π 0)
(I)
2
2
and the NNGP kernel is given by
-((e)))-/// ||~0||| (( () cos + +in I E Re
||a|||
K(x, x²) =
(2)
2
where 0 = arccos "eTaa/ll |-|||=--||))))) For set of vectors X, we will use the notation 0 0( () and (xx,2') to refer to the limit NTK calculated when the the set {F(x) x E } is vectorized (the outputs are stacked vertically), and similarly for the NNGP kernel. Our learnability results rely on the following theorem by [18), adapted to our architecture:
Theorem 3.1 (Theorem 2.2 from Lee et al. 18). Let and y be the training dataset (training inputs and ground truth labels, respectively). Assume that θ := O(X, X)) is positive definite. Suppose the network is trained with gradient descent (with small-enough step-size) or gradient flow to minimize the empirical MSE loss Then, for every & E RK with | || I 1, as n4p - co, the output at training time t, F2(2), converges in distribution to Gaussian with mean and variance given by
p())) (2
Σ(x) = K( () +
(0(2,
h.c)
where y in Equation 3 denotes the vectorization of all vectors y E V. and "h.c." " is an abbreviation for the Hermitian conjugate.
"The empirical MSE loss is defined as L(D) " 1.f(())) ?lI
3

---

4 Algorithmic execution via template matching
In this section, we introduce template matching principle that offers high-level intuition for representing and executing algorithmic instructions in the NTK regime. This principle transforms binary inputs into binary outputs by comparing input configurations against a set of predefined templates. Matched templates are then used to compose the corresponding output. We use this principle of templates and template matching functions encode and execute algorithms. While this approach may seem unrelated to neural networks, we show in the following sections that, by carefully structuring training and test inputs, neural networks can emulate this template matching mechanism. In doing so, they can learn algorithms on binary data through the lens of the Neural Tangent Kernel. More concretely, we show that this principle, as described here, allows us to learn and express arithmetic operations such addition and multiplication. Furthermore, this approach can be generalized to more general computations, as discussed in Section 5
Input representation: Inputs are vectors of binary variables of length k. i... a E 10, These variables are grouped into disjoint blocks, partitioning æ into blocks. Each block, denoted by B, for i E [b], has length E N. While block sizes may vary, each 8; is assumed to be (1). Let a [[B]] E 10. denote the subvector for block B,, i.e., the bits of a that belong that block.
The transformation of the input vector depends on the configurations present within each block. Each block B3 is associated with finite set of templates Ti S {0, 1) x
Templates and functions:
{0, 1)*h where each template (æ, y) maps a block configuration to complete output vector y. The mapping is functional: for all (x. y), (a', y') E Ti, if x = x', then y yy In other words, no block output. Consequently, the cardinality of Ti is at most 2
configuration maps more than
Using each Tú we define a block specific pattern matching function f, : (0, 13 + {0, 13*h and an aggregation function f {0, 13*h + {0, 1}* by:
y if (a',y) E T fi(('' = 0 otherwise,
b f( V f(((BB))
(5)
(6)
where 0 denotes the all-zero vector in (0, 1)*, and the bitwise disjunction (logical OR) is applied elementwise across the output vectors fal) inside Equation ( Each of these template matching functions is applied independently and simultaneously to the corresponding block.
In this framework, the block-specific templates T, determine the local behavior of the algorithm, specifying how each block contributes to the global state vector â. The global update function f. formed by aggregating the output of all fú enforces this behavior across all blocks simultancously. By applying iteratively, we propagate these local rules over time, effectively executing the algorithm.
4.1 Algorithmic example: computing binary addition
We now demonstrate how to apply the template matching principle to simulate binary addition. Throughout this example and the more formal algorithm descriptions provided in Appendix BB we often assign descriptive variable names to improve clarity. These identifiers serve only as labels and do not affect computation. For this example, denote the two summands by p and q, each consisting of = 2 bits. Consequently, their sum requires at most + 1 = 3 bits to be represented.
The addition algorithm emulates ripple-carry adder built from half-adders [10], performing bitwise addition, while propagating carries to higher-order bits. The process alternates between & summation and l prry-aproagatton steps, reaching steady state after at most 2 iterations. However, as demonstrated in Appendix B.2 is also possible to introduce flag to indicate termination.
To simulate this behavior, the input structure is organized into blocks corresponding to the bits of p and q, along with their associated carry bits. In this example, we use four blocks: two for the individual bits and 9;, and two others for the carries, denoted c; for = 1, 2. In our representation, the final output comprises the most significant carry bit, followed by the bits of p as stored in ă. As shown in Figure 2 the result is formed by concatenating C22 P2, and P1, for a total of { f 1 = 3 output bits. To capture the required operations each block, we define a set of templates, as illustrated in Figure 2 The even-numbered templates implement bitwise summation, while the odd-numeered templates handle carry propagation to the next bit. These templates are designed to ensure that the operations proceed without interfering with one another.

---

(())
Σ B.)
y
10g
11a
101;
x!
6:PpP
Pa
f(8)
B1
C3
1
3F1
P1
P2
B,
42
B2
42
x
X
x?
X
y?
D3
G1
P1
IPa
P1
1
B4
B4
q1
Ta T4
Figure 2: Illustration of the addition algorithm based the template matching approach from Section Two = 2 bit numbers, = 2 (or 102) and 3 (or 112). are added by organizing their bits and carries into blocks B₁. Blocks B2 and B, represent the bits of and q. while B₁ and B3 handle the carries. The imput æ is processed via template matching f. using templates T; producing outputs y; (R) used compose the outpur. Although the method is iterative, this example completes in one step. The final result 5 (or 1012) is stored at the most-significant carry bit and the bits of p in a.
Exact learnability Part I: NTK predictor behavior
In this section, we analyze the exact learnability of algorithmic executions in neural networks by studying the NTK predictor, defined as the mean of the limiting distribution for two-layer network. We show that it preserves sign-based information about the ground truth and can learn to execute algorithms framed as template matching, following the framework in Section 4 The training dataset is built from templates and, in the applications presented, its size scales with the number of bits, hence logarithmic the number possible binary inputs.
5.1 Input specification
We begin our analysis by specifying the structure of the training and testing inputs. Following the framework of Section 4 we construct the training inputs as blckk-artitioned vectors, where each block corresponds to an input template set. Each training input is non-zero only within the block determined by its associated input template in T.. In contrast, test inputs may contain multiple non-zero entries, each corresponding to a configuration appearing in the dataset. A visualization of the input configuration provided in Figure 3
Training dataset We define the training set for any algorithmic task described as in Section Let each of the b block configurations Te be set of f; [Ti] template-label tuples, i.e., each
T (i.1) y (6.1)), (it().., y (.()))) S 10, x 13.
The input dimension to the neural network is
Ei t, We view R² as the direct sum Rh ( @ R&'s and for each subspace R.,, choose orthonormal basis {un,-... ua, For each i 1, 1,.... ........ b, we encode the j-th template of Tr, (ax().)) y (b.))), the block- blckk-artitiooned vector
4g (O.,,-. ......... Or, Unj. Oz,)) with the i-th block being equal to uyj The sets of training inputs and corresponding ground-truth labels are given by
X {q. [b].j E [t] C R
and y = (y( : [b]. j [t.]] RR
*In applications such as binary multiplication and SBN, the dimension Af is extended with auxiliary unitary blocks, each containing template. These extensions. detailed in Appendix ensure Assumption 5.1 satisfied without affecting the algorithm, they never matched during execution.

---

insi
X
y
C2
P2 42
P1 91
R
[ RR R
C2
P2 22
C1
P1
01
P2
42
Q1
Figure 3: Visualization of the input specification of Section 5.1 for binary summation two ? f= bit numbers. On the left, we illustrate the block structure of pre-encoded test sample. Each block should either zero or match the corresponding block of an element (row) of Xi On the left, we showcase the encoding procedure that creates the training dataset. The initial examples (described in Section 4 forming the rows of Xini are augmented and orthogonalized. Notice that the colored parts of each row of Xini along with the corresponding row of y match the Ti's of Figure 2 Also note that the orthogonalization presented here is only one of the many possible ones. Finally, each row of y depicts the corresponding ground-truth output for each training sample.
respectively. This encoding yields an orthonormal, block-partitioned set of training inputs, with no cross-block interference. In total, the dataset has size k E O(b), and depends the number of bits used for number representation in each application. For example, to add two 10-bit numbers, 40 training examples are required.
Test inputs Based on the algorithmic execution framework Section every test input á expressed ã (
with each é; being either Os, matching one of the training
samples of in its i-th block, i.e. i; is equal to the i-th block of qi for some j [tz]. that case, say that & matches Q:y- We denote by na the number of blocks of & that match an entry of the training set. Since each & is ((1), the total number of inputs O(2%), which is exponentially larger than the training dataset size. For instance, the total number of test inputs for the addition of two 10-bit numbers 410 which is exponentially larger than the training dataset size.
5.2 NTK predictor behavior theorem
To derive this result, we introduce and discuss one additional assumption. The specific structure of our orthogonal training and test inputs simplifies the mean of the limiting distribution, μ(.)
"y) This predictor can be expressed as simple weighted sum of the ground-truth training labels y. This sum governed by two distinct weights: a "signal" weight, w w (.). applied to training labels whose corresponding inputs match a block in the test input &, and an "interference" weight, w (.). applied all labels from unmatched training inputs. For any given output bit, an "unwanted correlation" occurs when unmatched training sample (which receives the o weight) also has that bit set, thus contributing interference against the correct signal. Informally, we can interpret the ratio -w- /wo as decision margin. Our assumption, stated below, simply requires that the total number of these unwanted correlations is less than this margin, ensuring the signal's contribution outweighs the total interference. We now formally state the assumption that guarantees lcarnability:
Assumption 5.1. For each test input and for each position E [K'] such that the ground-truth output ( F has the i-th bit set, the number of training examples that do not match á and have the
i-th bit set (which we call unwanted correlations) is less than the ratio w (i)) / (
There is slight abuse notation here when using (()) since f does not operate on encoded inputs. Depending on the context, we may use à to denote both the pre-encnded encoded test inputs. ( is always non-positive and the ratio is non-negative.

---

While, at first, Assumption 5.1 may seem restrictive, we remark that for many algorithms,, including those examined in this work, the number of conflicts is low enough guarantee that it is satisfied. In particular, since the SBN instruction set is Turing-complete it can, in principle, encode any algorithm. Our framework leverages this property by simulating SBN instructions, allowing any algorithm to be represented as input to the system. This does not mean that we directly learn arbitrary Turing- computable functions, but it ensures that such functions can be expressed within our formulation without violating Assumption 5.1 The behavior of the NTK predictor is given in the following theorem:
Theorem 5.1 (NTK predictor behavior). Consider an algorithmic problem cast as cemplate-matching and encoded in training set (X,Y) S TRe R& as described in Section 5.1 Then, under Assumption 5.1 the mean of the limiting NTK distribution y():)- ( X X X
( X)- for any
test input & E BRKK contains sign-based information about the ground-truth output, namely for each coordinate of the output i =l.....k k, p(x); S. O if the ground-trutt bit at position i, f()) is set, and p());; > 0 if the ground-truth bit at position f(()) ) is not set.
Proof outline. We aim to express each ju(:;;; as a weighted bit-sum with weights w and w and then rely on Assumption 5.1 to guarantee that the signs are preserved. The orthogonality of the training dataset forces the train NTK to align with the local computation structure of the template matching framework. In particular, both the train and test NTK kernels assume a scaled identity that keeps different blocks from interfering with one another. Furthermore, since any test input activates at most one vector per block, the test diagonal elements of the test NTK kernel (measuring the similarity of the test input to each element of the training set) take only two possible values: one indicating "this block active" and one indicating "this block is empty". Concretely, θ-1 == O(X, X²)
takes the form Ô-1 1 @ Is where Ô-1 12k xk' is a scaled identity plus rank-l perturbation (noise), and @(2, takes the form f & Ig where f E R² takes only two values, f' and fo denoting match/no-matce By arranging the elements of y as columns in matrix Y and using vectorization, we can rewrite the model as
p())= X)= ((fô1) @ It)) (Y) = Y
We first show that 6-1 E 12K takes only two values wD < and w² > 0 depending on whether the corresponding entry in f equal to f or ft. To conclude, we write
u());
Σ (+)
f(gx)aw +
Σ
f(gx).w
GNEE (#)
where
(+) (G.1) 1 [m],1 1 [s,] and à matches 9,1);
and
(+) - (G.1) : E [m], E [s,] and è doesn't match g,x)-
The sets I+ (i) and (+) partition the training dataset into two disjoint sets: the indices of the training dataset that match & and the ones that do not. When f()); O, Equation 6 yields vanishing first summation and therefore μu();; < O. On the other hand, when f fā); = 1, due to the fact that v matches exactly one of the training samples from the block containing the i-th bit. Equation
( reduces to u()); w' + I I .w.. where I (0) = {()00) E (+): f(gz)): )= = 1} denotes the index set of unwanted correlations. Under Assumption 5.1 we have u()); > 0 and so the sign-based ground truth information is preserved, concluding the proof. A pictorial version of the above outline is given in Figure
Regarding the algorithms discussed throughout this paper, we have the following remar
Remark 5.1. The tasks of binary permutations, binary addition, binary multiplication, and executing SBN instructions all satisfy the assumptions of Theorem 5.1
"Our results for permutation, addition, and multiplication were numerically verified on various random instances by calculating the corresponding limiting mean. For code and implementation details, refer to the supplementary material.
7

---

NTK predictor:
@ (a; by
@
smm(9, (9: 2.)
> e/s
X
x
A
2
B
9u
slmi A +
2
B4
Ba
8n
80
stm(a, (" +
x
Racoding
B1
2
Bq
Bu
96
90
slm( X
Ronnding
B1
+Ba
B1
Ba
Bq
Bo
91 80
90
sam X
B1
B4
Ba
9
80
siml G. n +
B1
Ba
Ao
An
9n
9n
91
stmml R,
Instructions
X'
6 X3)
( X16
Instractions t+
8
Figure 4: Illustration of the NTK predictor structure: inputs are first encoded (normalization omitted) compute the test NTK (á, X).. Due the test input structure, this kernel assumes two values based on matches between the form of scaled identity plus rank-1 I noise perturbation colored black) re-weights these similarities, and the multiplication by y gives the final prediction. When the contribution of the unmatched entries is controlled (black similarities), the sign of each coordinate matches the ground-truth output.
and training imputs within blocks. Multiplying by Ô-1 (which assumes
The proof strategy for Remark 5.1 involves computing lower bound for the decision margin -w² -w"(#) (/)/w"(( (+) over all test inputs & and showing that the number of unwanted correlations falls below this minimum value. For example, in the case of binary addition, this threshold comes out to be equal to 4 while the number of unwanted correlations can be at most 1. In Figure 3 this is captured by the fact that each column of y contains most 2 ones. complete proof of Theorem 5.1 and Remark 5.1 can be found in Appendix
6 Exact learnability Part II: high-probability guarantee
In this section, we continue our proof exact learning of algorithmic instructions using neural networks. The conclusion of Theorem 5.1 suggests simple procedure: for each coordinate, if the output of the network is greater than zero, round to 1, otherwise round to To extend this result from the NTK predictor to actual models and ensure high-probability guarantees of exact learning, we can independently train enough models, average their outputs, and round accordingly We define ensemble complexity the number of models required achieve desired level of post-rounding accuracy. In what follows, we derive a lower bound on the ensemble complexity of learning algorithmic instructions and give its asymptotic order. This completes the proof that neural networks can, with high probability, exactly learn algorithmic instructions.
Given a test input è with ground truth ý f()),, let ( be the output of the j-th model in an ensemble of independently trained networks. By Theorem 3.1 each FD (z) is drawn i.i.d. from ((n(2) (), [) so every coordinate F (xt); follows follows.NV ((((())
(2)) Define the ensemble mean
G(ă)) = E Fi (.)). Because p()); S 0 when y, and (()) when y rounding G( correct (G()), p(:),, < 1//
Applying standard Gaussian concentration bound given in Lemma A.I and the union bound, we obtain, for any E (0, 1), perfect post-rounding accuracy with probability whenever the number of averaged models N satisfies:
o²(
2k 8
N 8 max
In
"In practice. model-to modeellt-mmode variability is often controlled by training several copies (or by collecting multiple checkpoints along training run) and then averaging either their predictions (17) their weights [3]. Our "ensemble complexity" result gives clean theoretical analogue this variance-reduction trick. with concrete high-probability guarantees on post-rounding accuracy.
SSee Appendix D for the calculation of o (

---

Permatation
Addition
Multiplication
1000
10K
100K
Rnomshie complexity
100
1K
10K
2000
100
10
10
20 30
10
30
Number bits
Numeriosl
Theorctool
Figure Numerical and theoretical estimates of ensemble complexity N (in log-scale) for per- mutation, addition, and multiplication tasks as a function of bit length f. Ensemble complexity is computed via union bound over all possible inputs and algorithmic executions for given f. Inset blocks illustrate the ratio of variance to mean in Equation (8) estimated using input size k'. This ratio increases linearly with k' up to a constant. The same ratio is used in the theoretical estimate of N, which matches the numerical estimate in growth rate, differing only by constant factor.
To derive the order the bound on the ensemble complexity of Equation (), we need to analyze the asymptotic orders of u()) and o² (.)). The result is summarized in the following technical lemma:
Lemma 6.1. Suppose we train on any of the four tasks (permutations, addition, multiplication, SBN instructions), described in Section 5 Let in be test input unseen during training matching naa >> 1 training entries and let ju(t) and o² (x) be as Theorem 3.1 Then o² ( E O(1/k'),, and, for each
i [k], depending the relationship between nh and k' have:
0(1)
if n is const. if n non-const. and sublinear in
+
na nh is const. if na non-const. and sublinear in W and In((), e if = ck' for some E (0, []
g
θ
n = ck' for some E (0,1)
vk
lu(t)ale E
if n = k and there are unwanted corr. if na = K and there unwanted corr.
vF
+
when the ground-truu -runnd bit position not set (f((); = 0) or set (f(#); 1), respectively.
The proof of Lemma 6.1 (including the calculation 0² (²)) can be found in Appendix D In light of these asymptotic results, the uniform bound of Equation (8) behaves like O log k'). An application of the union bound shows that for an algorithm requiring m iterations, the ensemble complexity bound when accounting for all O(2)) possible test inputs (where b is the number of templates in Section 4) and all m iterations behaves like O(kb+ k' log m). In particular, for the tasks considered, we have the following remark:
Remark 6.1. For the tasks of binary permutation (b Re' = m = 1), binary addition (b = 2f, K' = 4f, 2l), and binary multiplication (b 116, k' 216, m 48 + 38) the ensemble complexity scales like O(E), where & is the bit length for each application.
Figure plots numerical and theoretical estimates for the ensemble complexity of the permutation, addition, and multiplication tasks, showcasing the conclusion of Remark 6.1 In Appendix D we verify our theory with an empirical estimate of the ensemble complexity for the permutation task. This is done by training multiple two-layer fully connected feed-forward networks, each with 50,000 hidden units, using full-batch gradient descent to form ensemble.

---

7 Limitations and future work
In this work, we have demonstrated that two-layer fully connected feed-forwant neural networks in the infinite-width limit can learn to execute algorithmic instructions expressed within our template matching framework (including binary permutations, binary addition, binary multiplication, and execution of SBN instructions) using training set of logarithmic size in the number of possible binary imputs. This provides an affirmative answer to the question whether neural networks can learn to execute long sequences of binary-encoded instructions exactly.
Our analysis, however, relies on several simplifying assumptions that bound its generality. The first concerns data orthogonality and explicit instruction access, which guarantee that each local computation step is independently learnable. Future work could investigate whether exact learning remains possible under correlated training examples when the network must infer primitive instructions from only partial input-output traces. The second limitation arises from the bounded memory setting of our framework. Increasing the available memory changes the input dimensionality of the model and, therefore, requires retraining, so extrapolation to longer inputs does not occur automatically. Within this bounded memory regime, exact algorithmic execution remains achievable using only logarithmically many short training examples, but extending these results to architectures that naturally process variable-length inputs, such RNNs, Transformers, valuable next step. For example, the use of GNNs on bounded degree graphs may enable controlled forms of length generalization with respect to graph size while preserving the theoretical structure of our exact learning framework.
GNNs, would be
Acknowledgments
K. Fountoulakis would like to acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), IRGPIN-2019-0400
DGECR-2011 -0R---2199-000 2019-00147].
G. Giapitzakis would like acknowledge the support of the Onassis Foundation Scholarship ID: F ZU 120-1/2024-2025.
References
[1] Artur Back De Luca and Kimon Fountoulakis. Simulation of graph algorithms with looped transformers. In Proceedings the 41 International Conference on Machine Learning. volume 235 of Proceedings of Machine Learning Research, pages 2319 2363. PMLR, 2024. URL https://dd) acm.
0ttpo//10.555556620777777 3692162.
[2] Artur Back de Luca, George Giapitzakis, Shenghao Yang, Petar Veličković, and Kimon Foun- toulakis. Positional attention: Expressivity and learnability of algorithmic computation, 2025.
URL httph:ttt/:sttt
wwwp/rg/////aeee 2400b./2411..m 01686
[3] Enric Boix-Adserà, Omid Saremi, Emmanuel Abbe, Samy Bengio, Etai Littwin, and Joshua M. Susskind. When can transformers reason with abstract symbols? In The Twelfth International Conference on Learning Representations, 2024. URL lattps::/ wwwpeerrrviieeeee/oorrrrr net/forum?
STUGUUUU2
[4] Hanseul Cho, Jaeyoung Cha, Srinadh Bhojanapalli, and Chulhee Yun. Arithmetic transformers can length-generalize in both operand length and count. In The Thirteenth International Conference on Learning Representations, 2025. URL https: www.opprrviieeneeetteeeee
id id=elgGeSYKLG
[5] Yuntian Deng, Kiran Prasad, Roland Fernandez, Paul Smolensky, Vishray Chaudhary, and Stuart Shieber. Implicit chain of thought reasoning via knowledge distillation, 2024. URL
[6] Yuntian Deng, Yejin Choi, and Stuart Shieber. From explicit cot to implicit cot: Learning to internalize cot step by step, 2025.
10

---

[7] Angeliki Giannou, Shashank Rajput, Jy- Y--o Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 11398-11442, 2023. URL
attpss//ddi acm. .wm.org//...................o... wwt.oogg//oooooooooooooo doi/10. 5655/3618408. 06118484448318866666
[8] William F Gilreath and Phillip A Laplante. Computer architecture: A minimalist perspective, volume 730. Springer Science& Business Media, 2003.
[9] Eugene Golikov, Eduard Pokonechnyy, and Vladimir Korviakov. Neural tangent kernel: A survey, 2022. URL httphttss///riiii.rrrge.
[10] David Harris and Sarah Harris. Digital Design and Computer Architecture, Second Edition. Mor- gan Kaufmann Publishers Inc., San Francisco, CA, USA, 2nd edition, 2012. ISBN 0123944244.
[11] Christoph Hertrich and Martin Skutella. Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS journal on computing, 35(5): 2023, URL UtL/httpss//puuoonliinn
informs org 2w///////oo/////// 2tt.jjo..222.22220
[12] Wolfram Research, Inc. Mathematica, Version 14.1, 2024. URL com com/mathematica Champaign, II.
wolfram
[13] Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry P. Vetrov, and Andrew Gordon Wilson. Averaging weights leads to wider optima and better generalization. Amir Globerson and Ricardo Silva, editors, Proceedings of the Chirty-Fourih Conference on Uncertainty in Artificial Intelligence. UAI 2018, Monterey, Califormia, USA, August 6-10, 2018, pages -85. AUAI Press, 2018. URL http: / auai oww//org//a...o.oooooo 2018/ wwwpppeioogoeoooeeoppppp preee// httph//gg/pppppps33a.a pdf
[14] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Bisnchi, and Garnett, editors, Advances in Neural Information Processing Sys- tems, volume 31. Curran Associates, Inc., 2018. URL /tB.tttps://pprcceciineee neurips cc/ pdf
paper paper_files/ppeeppppppppppppspep [pppe///f..arrrre..a.aaaaaaaaaar
[15] Samy Jelassi, Stéphane d' Ascoli, Carles Domingo-Enrich, Yuhuai Wu, Yuanzhi L.,, and François Charton. Length generalization arithmetic transformers, 2023. URLpttts::/ //ax/iiv///iiiv//// org/ abb/2306. (0s/2306.15400)
[16] Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http
//arxiv.org borg/bbs//a 111.. 1ttp//11111..1128811
[17] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scal- able predictive uncertainty estimation using deep ensembles. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, edi- tors, Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http:tttttt:/tpceeiiiiia www.inngg..neuurpe www.nnw...ccceeeeaeeeeee Saagerrffilee//ppe/////1 9e 2e7222c4b/fBbcc1166677fffaabbeb2
pdff
[18] Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL http::::/ppoteeeeeeeeeee wnw.eeeeeeddieeeenee..ee...eeepp nwwrips. ccwpsper f filess/aper/
[19] Andreas Madsen and Alexander Rosenberg Johansen. Neural arithmetic units. In International Conference on Learning Representations, 2020. URL htttps///operrerier wtw.://wwwweiii.eeeeooooo.mm net/forum? id=HigNDeHKPS
[20] Eran Malach. ruto-regressive next-token predictors are universal learners. arXiv preprint 270.97230,,0697, 2023.

---

[21] Sean Michael McLeish. Arpit Bansal, Alex Stein, Neel Jain, John Kirchenbauer. Brian R. Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Geiping, Avi Schwarzschild, and Tom Goldstein. Transformers can do arithmetic with the right embeddings. In The 4th Workshop on Mathematical Reasoning and at NeurlPS 24, 2024. URL Sttthttt:://epereeiiee net/
forum?id=cBFsFtt
[22] Bhumika Mistry, Katayoun Farrahi, and Jonathon Hare. A primer for neural arithmetic logic modules. Journal of Machine Learning Research, 23:1-61, 2022. URL BRRLhttps::/ /tttps://www... jmmr o2t/pppprrr//ollmmm2222222111112
påf
[23] Arvind Neelakantan, Quoe V Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. In International Conference on Learning Representations (ICLR), 2016. URL https:
org/ abs/ /ta.////......... 1511.0489 04834
[24] Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2 13019, 2021. URL htt.hhttt///aiiii
org ats/abb/ 13019
[25] Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl- Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference on Learning Representations, 2020. URL https 7/github. com/ googgo/oolleerrrrrloo/o taangggn
[26] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models, 2022. URL
[27] Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gen- eralization beyond overfitting small algorithmic datasets. arXiv preprint arXiv:220..02177 2022. URL sattps://arxivg org/ 22011. 221170
[28] Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75): 2021. URL bttpss//::/// acm.
5555/3546258. 3546333
[29] Scott Reed and Nando de Freitas. Neural programmer-nnteppretess. In International Conference on Learning Representations (ICLR), 2016. utLtttss:://axxi www.aaawww...iooaaaaaaaaa httg//ab/1511..05.5
[30] Anian Ruoss, Grégoire Delétang. Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized positional encodings boost length gen- eralization of transformers. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, ed- itors, Proceedings of the 61st Annual Meeting of the Association for Computational Lin- guistics (Volume 2: Short Pupers), pages 1889-1903, Toronto, Canada, July 2023. Associ- ation for Computational Linguistics. doi: 10. 10.18653/w1/2023.aad actp:///1/222..lshoooooo acl.shorr...1.11111 / //aclanthology.orgg 2023. acl Shoor.161..
URL https
[31] David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations, 2019. WtR.lttttst////. htttppp///ppeeeeeeevv..eee////ee tet.
[32] Ruoqi Shen, Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, Yuanzhi Li. and Yi Zhang. Positional description matters for transformers arithmetic, 2023. URL https://axxiv org htggabss23111 14737
[33] Jack Sherman and Winifred J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of given matrix. The Annals of Mathematical Statistics, 2141):124-127, 1950. ISSN 00034851. URL http::/www. httt///wwww.j..rrro./....o.. wtggsstaable/226551
[34] Hava Siegelmann and Eduardo Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50:132-150, 1995. htt.htttps:/ww..iieeeeeee
nom/science artiicll/p1111000220005//0000000
12

---

[35] Andrew Trask, Felix Hill, Scott E Reed, Jack Rae. Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httpps:://ooooeeiigggs neurips
fiteerf__eeeppppprrrreeeee pdf
[36] Yan Wang, Xiaojiang Liu, and Shuming Shi. Deep neural solver for math word problems. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 845-854, 2017. URL
[37] Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: study on approximating turing machines with transformers. Advances in Neural Information Processing Systems, 35:12071-12083, 2022. URL https://ddl acm. org/doi//ni /0../10...00 5555/
0800270..300114
[38] Jason Wei, Xuezhi Wang. Dale Schuurmans. Maarten Bosma, Brian Ichter. Fei Xia, Ed Chi, Quoe Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages
24824, 2022. URL ptttpe::/prooeeeddnggs wtw.:eeeddiinnnnneiiieeeee nwwripe cc/paper.p..... cc/ppaperfflles//ppeeeee fll.ffflllppppeeee
hatpraaalaaaaapppppe-ooooeeeeeee Conference pdf
[39] Greg Yang. Tensor programs II: Neural tangent kemeel for any architecture, 2020. URL https://arxiv org/ abs/2006. 14548
[40] Greg Yang and Etai Littwin. Tensor programs Lb.: Architectural universality of neural tangent kernel training dynamics, 2021. URL http:/ttp///arrr.oorr////a// 03703
[41] Liu Yang, Kangwook Lee. Robert D Nowak, and Dimitris Papailiopoulos. Looped transformers are better at learning learning algorithms. In The Twelfth International Conference on Learning Representations, 2024. URL URL htttps://openrevies net/forum? www.rrmmmmddiiiixoOO000
[42] Wojeiech Zaremba and Ilya Sutskever. Learning execute. arXiv preprint arXiv: 14t0:4114..5 http::tttt///iiiii /twpvvxxvvvvv//////// wwgg/ba/////.a.o.. 4615
2014. (tRpsttts:: /
[43] Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou. Transformers can achieve length generalization but not robustly. In ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2024. URL https
//openreview. net.:forumm.dd-Diii.......
13

---

A Notation and Preliminaries
For two matrices A1 E _ Xm A2 _ denote by A A2 I Kronecker product. It is relatively easy to show that when A and B are square matrices (i.e. their and f2 m2), the eigenvalues of A @ Ag are given exactly by the products of the eigenvalues of A1 and A2. In particular, A1 @ A2 is positive definite if A and A2 are positive definite.
A.1 Useful Results
In this section, we state results from linear algebra and probability theory that are used derive our main results. The first result is used to compute the train NTK matrix:
Theorem A.1 (Sherman and Morrison 33). Suppose A E R is an invertible matrix and u, v E R". Then A + uw is invertible if and only if 1 + 0. In this case,
A uv TA
(A ue ) A A
1
1 A--u
The second result concentration bound for sums Gaussian random variables, which we used derive our ensemble complexity bounds:
Lemma A.1. Let X1, Xn be independent Gaussian random variables with mean and
variance o² and let Xn -E= Xt. Then for all t O. we have:
nt²2
(IX,, - 11 2 21 S 2exp
2o²
o² Proof. We will use the Chernoff technique. Let À > O. We have X, - ~ N (0,,0(00001 symmetry and Markov's inequality get:
n
and so by
P - 1 2 = 2P 22, - n
2P (e ede) se- [=)
The expectation the right-hand side is equal to the noment-generatten function of normal distribution with mean 0 and variance P/n and so is equal to exp
Now let
2n
x²
<(A) exp
Ad
2n
be the right-hand side of Equation 9 Minimizing ((A) with respect À find that the minimum
occurs at X nf and plugging this back into Equation (9) gives the required bound. 6.
B
Constructive proofs
In this section, we outline the of instructions used illustrate the steps involved in the algorithms described earlier. To ensure clarity and avoid unnecessary repetition, we adopt certain conventions in presentation of these instructions.
To ensure the correctness of our constructive proofs for the numerical tasks presented below, we This validation uses the instructions defined below for permutation, addition, and multiplication. Using the Neural Tangents package (25), we compute the NTK predictor (as in Theorem 3.1 Applying the encoding and rounding procedures described in Section S and Section 6 we demonstrate that the implementations are numerically correct for bit lengths up to f 10. Additionally, we provide demonstration script that more descriptively illustrates each step of the algorithms as executed within our framework.
include numerical validation 2
OOr source code can be found in the supplementary material.
14

---

Conventions
Unless otherwise stated, all variables refer to Boolean values (i.e., elements of {0, 1J), arrays of Boolean values, or natural numbers as appropriate. Let Index(A) denote the index set an array A.
Logical equivalence: For Boolean variables and B,
A = B (A 1 AND B 1) OR (A = 0 AND B = 0)
This represents equality of Boolean values, not assignment.
Logical inequality:
A
B def
(A = AND B = 0) OR (A = 0 AND B =)
Assignment:
We use the symbol <- denote assignment. For Boolean variables:
B+ A means that B is assigned the current value of
Universal indexing:
A[ALL]
def
Vi E Index(A), A(d]
Bitwise comparison:
A[ALL] = B[ALL]
Vi Index(A) Ali]] B[i]
Bitwise assignment:
A[ALL]
Vi Index(A). AAi]]
Binary representation: Let bin(v) denote the binary representation of natural number encoded as a Boolean array. The bit width is inferred from the context unless specified.
B.1 Binary permutation
In this section, we demonstrate how the template matching framework can be applied to exccute binary permutations. Let the binary input be denoted by binary number We begin by defining the input structure in terms blocks and then construct the corresponding templates.
Blocks: For an ê-bit number p. we design & blocks, each encoding a single bit of the number. Let each block correspond
p [i], thus have:
(p[i)) for E [8]
Given this block structure, we now define the instructions that encode the desired permutation. Consider mapping : [?] - [e] that specifies the permutation: takes bit position as input and returns its new position after the permutation. For example, if the third bit of the input is be moved the fifth bit position, then r73)= 5.
Instructions:
Based on this mapping, we construct l samples, one for each block, which encodes the transformation defined by π.
Instructions: Permutation
INPUT: x x[p[i]] OUTPUT: y [p I (i)]] +- 1
Instruction count:
Fach bit permutation is thus encoded as individual instruction in the template set. This captures the behavior that when specific bit position is activated in the input, permuted position must also be activated in the output.
15

---

B.2
Binary addition
With the established framework, we now illustrate how to apply the template matching principle to simulate binary addition. Throughout this and other algorithmic examples, we often assign descriptive variable names to improve clarity. These identifiers serve only as labels and do not affect computation.
Let the binary inputs be denoted p and each consisting of bits. The result of their sum requires l + bits. We begin by defining the block structure of
Blocks: In this implementation, we organize the input into 2 blocks, blocks encode the bits of and q. and the l blocks encode the corresponding carry bits c.
[p[i], q[i]) for i E [d]
(c[i)) for i [e]
Assignments and conditions are written using square bracket notation. Since each block comprises
uniquely named variables, individual variables can be referenced directly by name. For example, setting the second carry variable to I is expressed as [c [2]] 1.
The addition algorithm follows ripple-carry approach using half-adders 10] It proceeds in two alternating phases: bitwise summation and carry propagation.
In the summation phase, the algorithm adds the bits x x[p [i]] and x [i]] for each i, storing the result back in [p [i]] and placing any resulting carry in x [c [i]]. In the subsequent carry propagation phase, the earry x [i]] is transferred to [q [i]]]], allowing it participate in the next summation step.
This iterative process alternates between É summation steps and carry propagation steps. After 26 iterations, the computation reaches a steady state.
In our representation, the final output consists of the carry of the most-significant bit y[c [E]] concatenated with all bits {e...., 13 y [p [i]], yielding a total L + output bits.
The following instructions are purposely designed minimize the number of unwanted correlations when using the NTK predictor. Specifically, the highest number of such correlations (also referred to as conflicts) occurs in the coordinates encoding the bits of the summand p[i] and the most significant carry bit c [(], where instructions share non-zero entry for the same coordinate. Notably, however, the maximum number of conflicts per coordinate equal to I this case remains constant and does not increase with the bit count É. This bounded conflict rate enables learnability, as further discussed in Appendix C
To capture the aforementioned processes in the blocks, define set of represen- tative instructions. By convention, we assume that any variable not explicitly set in the output is assigned value of zero.
Instructions:
Instructions: Bitwise addition
INPUT: x x[p[i]] AND x[q[i]] OUTPUT: ypp [i]]
Instruction count:
INPUT: x [p [i]]]] AND x[q[i]]
OUTPUT: y [p [i]]
Instruction count:
INPUT: x x[p[i]] AND x[q[i]]
OUTPUT: yIc [i+1]] < 1
Instruction count:
The case where both x[p[i]] and x[q[i]] are zero does not require an instruction. Since no template matches, the default behavior results all outputs being zero for that block and its carry, which is consistent with expected addition logic.
16

---

Instructions: Carry propagation
INPUT: x[c[i]]
OUTPUT: (i <i< f): y [q [i+1]] < 1
(i= f): y [c[i]] +
Instruction count:
This defines the carry-propagation behavior: when the carry position is one, its effect is passed to the next summand block.
An important observation is that template matching across different blocks does not interfere between phases. During bitwise summation, the carry blocks are set to zero and thus remain inactive. Conversely, during carry propagation, all [q[i]] entries are empty, summation remains static, allowing the carry from x [cc [i-]]] to transmitted to [qq
without conflict.
Finally, note that once [c [[]] becomes non-zero, it remains set for the remainder of the algorithm. This value represents the most significant bit (MSB) of the final result.
As previously mentioned, this implementation reaches a steady state after 2 iterations. However, it is also possible introduce termination flag that triggered once specific condition is met. In this context, we define termination flag that becomes active once 2 iterations have elapsed. To implement this, we introduce the following additional blocks:
Termination:
(counter [i]) for i [26]
Instructions: termination
INPUT: [counter [i]] =
OUTPUT: (if i < 2f): [counter [i+1]] <-
(if i 2f): [counter [i]] +-
This design introduces 2 additional blocks. Once the first block is activated, each block subsequently activates the next, until x [counter [2[]] is reached. The activation of [counter [2(]] indicates that the algorithm has finished.
B.3 Binary multiplication
In this section, we describe the structure and the components used to perform binary multiplication between two é-bit binary variables. Our implementation simulates the shift-and-add multiplication algorithm [10]
In essence, the shift-and-ade algorithm multiplies two binary numbers by scanning each bit of the multiplier. bit 1, the appropriately shifted multiplicand is added to the running total. This method mirrors the principle of long multiplication, but relies solely on shifts and additions rather than full multiplications.
To implement this algorithm, we divide it into four distinct processes:
1. Check the least significant bit (LSB) of the multiplier
2. Add multiplicand the accumulating total
3. Copy the multiplicand to the addition scratchpad
4. Shift multiplicand and multiplier
Each of these processes is implemented using one more blocks in the input. Because of how the algorithm operates, represent the multiplicand using 26 bits, initializing the most significant bits to zero. The bits are stored in little-endian form, so the first entry represents the least significant bit (LSB).
Blocks: We begin by defining the block structure:
(multiplier [1], to to_shift_right(I] [1], to_check_lsb)
17

---

(multiplier[i] [i], to_shift_rigght3]] for i [2.
(multiplicand [i], to_shift_lefttii wa_copy_to_sum_gee for i [2]]
(sum_p[i), sum_ qi]) for i [28]
(sum_c[i)) for i E [2(]
(sum_counter [i]) for E [46]
The first group of blocks stores the multiplier bits along with their associated shift flags. Flags do not hold data themselves. Instead, they signal when specific action should be triggered. These are typically (though not exclusively) prefixed with to.. The block of the least significant bit of the multiplier includes an additional flag for checking its value.
The multiplicand bits are also paired with their shift flags and an extra flag for copying. This copying flag signals when to transfer the multiplicand into the summation scratchpad.
The remaining blocks represent the summation components, as introduced in Appendix B.2
Therefore, in total, there 11c blocks. However, during execution, most 7 + 1 can be active at any time during execution. This restriction arises from the counter blocks, where only one block can be active at time.
The result of the multiplication 26-bit number, stored in x[sumpp] [ALL]. Each iteration of the algorithm may involve one or more of the four described processes, and some processes themselves may span multiple iterations.
Addition: 4 iterations
Check least significant bit (LSB): iteration
Copy multiplicand: iteration
Shift multiplicand to the left and multiplier to the right (simultaneously)) iteration
The worst-case runtime occurs when the multiplier consists entirely of Is, triggering all operations in each cycle. In this case, the algorithm performs full iterations, resulting in total execution count of 462 + 38.
The following instructions exhibit finite number of confficts per coordinate, crucial property for ensuring NTK Icarnability, as discussed in more detail in Appendix [ These conflicts can quanti- fied by counting the number of outputs that share the same coordinate. In the case of multiplication, the number of conflicts per coordinate 2. This occurs the coordinates corresponding to the multiplion pprierrrrrrr and multiplicant bits, which may be either modified preserved depending on the values of the flags within their respective blocks.
Instructions Based on processes and the block structure previously defined, we now define the binary instructions for each of the processes and their corresponding blocks to perform binary multiplication.
Instructions: preserve multiplier and multiplicand
While any other secondary process is being executed, the values in the multiplier and multiplicand bits must be preserved. For that, define:
INPUT: : x [mmultiplie [1]] 1 AND x x[to_shift_rightth] x x[to_ x[too_heckk___ check_lshll
AND
0
OUTPUT: y [multiplier [1]] f- 1
Instruction count:
INPUT: x [multiplier [i]] 1 AND x [i]] OUTPUT: 1) [multiplier [i]]
Instruction count: & 1
18

---

[i]] = 1 AND x[to_shift_leftthh = OUTPUT: y (multiplicand [i]]
INPUT: x
Instruction count: 2
Instructions: check least significant bit
For this stage, we have to define two instructions for when the to_ too_check_l___ 1sb flag is activated. If the LSB of the multiplier equal to one, then we start the addition process by activating the flags to copy the multiplicand to the addition stage. In contrast, if the LSB is zero, we trigger the shifting process of both multiplicand and multiplier.
INPUT: [mmultiplii [i]] AND x x[to_shift_right [1]] AND x wwaccceecllsbee = 1
OUTPUT: y [multiplier [1]] 1 AND ylto__coy_to__uu sum stt_:_ttt__m____LL____ [[LL]]]]]]]]]]]]] Instruction count:
and
INPUT: x [multiplier[]
[1]] [1]]
0 AND x x[to_shift_rrght
AND
x[to_ check_lab]
OUTPUT: y [_t___hhft_______ www.sshtitrgggee [ --1 AND y y[to_shift_les left [ALL]] <-1
Instruction count:
Instructions: copy multiplicand to addition block
Once the multiplicand copy flag is activated, we have to send the data to the sum_q variable. While the copying should only cover the cases for which the multiplicand bit is equal to one, we have an extra functionality for the first bit of the multiplicand, which triggers the counter to start the addition process. Because of this, we require an additional instruction that also covers the case when 0.
x [multiplicand[[]
INPUT: [multiplice cantiiipplinnndd [1]] AND coppo_cppytt_sum_.oom q[]]]
OUTPUT: [sum_ counter [1]] <-
Instruction count:
INPUT: [multiplicand[i]] 1 AND x[to_copp
[i]]
[i]]
OUTPUT:
y [multiplicand [i]] AND y [sum_q[i]] AND
[ssm_ coun_ccoutrrlii [i]] +- 1
(>> 1) y [multiplicand [i]] AND y [sum_q[i]]
Instruction count:
Instructions: add multiplicand to the running total
For this operation, we define the same instructions that were defined in Appendix B.2 for the variables p and q, which have 2/ bits in this context. These instructions cover the all the processes of bitwise addition, carry propagation, and counter update. By the end of the addition process, signalled by x [sum_counter [2(]] 1, we activate the shift process in the multiplicand and multiplier.
INPUT: [sum_ _ [i]] ]]]]
AND
OUTPUT: y [sum_p [i]] <-
Instruction count: 2f
INPUT: x [suu_pp [i]]
AND [ssu_q[i]]]
OUTPUT: y [sum_pp [i]]
Instruction count: 2f
INPUT: x [[sum_p [i]] = 1 AND [sum_q[i]] =
OUTPUT: y [sum_c [i]] +
Instruction count: 2
19

---

INPUT: x [sum_ c[i]] = 1
OUTPUT: < 26) [sum_ ssum_q[i+1]]]] < 1
Instruction count: 2
INPUT: [sum_ counter [i]]
OUTPUT: 46) [sum_ counter [i+1]]
(i 46) y [tt__shiifft] swistshiisaaeeee right [ALL]] <- 1 AND
<- 1
Instruction count: 46
Instructions: shift multiplier to the right
The purpose of this function is to perform the following behavior: when the to www.sssriifhhiee flag active, bit of multipp multipleer is assigned the value of the previous bit. If multiplier is already it is set to zero directly without further computation. An exception is made for i = 1: it does not shift its value but triggers the check_haa 1sb flag whenever to shift_right [1] is active, regardless of the corresponding multiplier bit.
INPUT: [multiplies [i]] o AND x x[to_ cetto_shift_rightiii [i]]
OUTPUT: (i = 1)
1sb] +
Instruction count:
AND x atto_shif_rrihh OUTPUT: (i = 1) y [tt__chh______ check _tacc_chccl______ <- 1
INPUT: [multiplier
(i 1) y (iultpplier[i-1]]
Instruction count:
Instructions: shift multiplicand to the left
The goal of these instructions is execute the following Instructions: when the to wwwss_hllflfffe flag is active, shift the mul tiplicand by assigning each bit to the next lower-order position. If = 2 or if multiplicant cand is already 0, set the value zero directly, as the shift is implicitly handled.
INPUT: [multiplicand(i]] = AND x ceto_ssift__eftteeee OUTPUT: < 26) [mmlttppliaandiiiin Instruction count: 20 -
=
+
B.4 General computation
In this subsection, we present results that address the generality of the template matching approach previously described in Section 4 To this end, we demonstrate that we can build block structure and corresponding instructions to simulate a one-instruction set computer (OISC), thereby showing that execute any computable function, provided with the right instructions and memory values. More specifically, in this proof, we represent an OISC with a single instruction called "Subtract and branch if negative" or SBN [8)
SBN: Named for its operation "subtract and branch if negative", SBN a one-instruction set computer. One way to express SBN is detailed in Algorithm [ and it consists of subtracting the content at address a from that at address b, and storing the result back b. All these values are stored memory array. If the result is positive, the computer executes the next instruction; otherwise, it jumps to the instruction at address c. Despite this operational simplicity, SBN Turing Complete [8]
Algorithm SBN (a, b)
Require: Input: memory object M, addresses a, b, 1: M[b] < M[b M[a]
2: if M(b] < then
3: go t
4: else
5: go to next instruction
6: end if
SBN is closely related to SUBLEQ ("Subtrach and branch less than or equal to zero"), differing only by the strict inequality instead of the inequality of SUBLEQ. This approach is fairly popular,
20

---

Subtraction
Memory
Lane Fil
Branching
centaic 2913
Instructions
Figure 6: Overview of the simulation of SBN using the template- template-mathhnng framework. Each rectan- gle in the diagram represents a block, with colors indicating specific block categories: Instructions, Memory, Branching, and Subtraction. Within each block are variables, depicted as shapes: squares represent data-holding variables, while triangles denote binary flags. Some blocks contain indexed variables. For simplicity, the sketch illustrates only one representative block for each unique index combination. Arrows between variables indicate interactions as defined by the instructions, repre- senting the flow of data and control between variables and across different blocks. The star symbol on the left highlights blocks active at the start of an iteration. During this phase, each instruction compared the current one, triggering corresponding blocks on the right. An iterative bit-wise comparison of instruction addresses follows, and if match occurs, copy flags for addresses b, and e are triggered in the three adjacent right-hand blocks. The process continues according to the instructions detailed in the following sections.
with SUBLEQ being widely used in other works to demonstrate Turing Completeness in the context of Transformers 7.
To simulate SBN within our framework, several auxiliary functions must be implemented in addition to those listed in Algorithm [] These functions handle tasks such retrieving an instruction from the list of instructions, accessing memory values from specified addresses, determining the next instruction based on the current one, and copying values between different fields, among other operations required by SBN.
The purpose of each function will become clear as their corresponding instructions are introduced. We will also explain the design choices behind them and provide the rationale for these decisions.
Before introducing the implementation details of our solution, we begin by outlining the structure we aim simulate.
Our simulation involves two distinct objects: one for storing instructions and another for storing memory content. Conceptually, the instruction object can be viewed list of quadruples (t, a, b, c). where is the address of the instruction (used for identification), and a, b, and c are, respectively, two memory addresses and instruction address. The triplet (a, 6, e) encodes the SBN instruction, as illustrated in Algorithm|] [ Memory is structured as a list pairs (A:, v), where i denotes a memory address and its corresponding value.
the framework outlined in Section we divide the input into sets of blocks, each representing a large group of functions and variables. Each set of block is identified using the prefix specified in parentheses. The major blocks are organized as follows:
For the input structure, following
Instructions (I): Contains the list of instructions and their associated variables.
Memory (M): Contains the list of memory elements and their associated variables.
Branching (B): Handles the selection of the instruction based on the branching condition in line of Algorithm as well as the computation of the next instruction address.
Subtraction (D): Handles the subtraction of memory contents a and b, as described in Algorithm I
21

---

Since both the instructions and memory objects contain multiple entries, we introduce additional notation. Let f denote the number of instructions, which assumed be constant, the number of instructions in an algorithm remains fixed, even though they may be executed repeatedly. Let ta denote the number of memory slots.
We define the number of bits required to address instructions as πy = [log, εr and similarly, the number of bits required address memory slots as n [log, fM Additionally, each memory slot holds a value, whose bit-width we denote by nc. An overview of our solution is illustrated in Figure
In the following sections, we will derive the structure the input æ, using the quantities defined above to determine the number of blocks and the corresponding instructions.
Blocks:
The total number of blocks
(5r 3nc 3) + (4(nr + nM + 1) 4nr Sng Olem log EM),
and the total length of the input x is given by:
As (11m + one + 4) & (8n, + 4m + 1) + 11m, + 12nc O(eM log Eas).
The structure of the sets blocks is defined as follows.
Instructions blocks: for k E [Er], i [nr]) j E [nm]]:
(I_to__coppaee [k] [i], I_curr, _intr [x] [i], I_instr [k] [i])
(I_is_equal [k] [i], I_ counter [k] [i])
[I_a_addr [k] [j], copy [k] [j])
(I_b_addr [j], I_to_copy_b b[k] [j])
[x] [i], I_to_copy_ce [k] [i])
(I_a_adrr_delay [k] [j])
d____adrr_delay [k] [j])
[I___add__delay [k] [i])
[x)c))))
Memory blocks: for k E [[M], i e [na], j E [nc]
(M_to_comparee [k] [i], M_a_addr [k], M_b_addr [k] [i], M_mem_ addr [k] [i])
(M_ia__quall_a[k] [i], M_counter_als [i])
(M_ (M_is_equal_b(k] [i], M_counter_be [i])
[M_nem_cont[x] [j], M_too_opy_a__me cont [k] [j], M_to__ooy__im saags_ivv___e____e iit_ii__em__onttttttteeeeeeeeeee [k] [j],
M_ M_is_match_bb[]] [j], fLto__cop__from_suulk
submssurroouuuo_____oeoo [k] [j], M_sub_result [k] [j])
(M (M_a_cont_delay) [k] [i])
(M_ coL___oot_symc(kk)
(M_b__onttddelay(k) [i])
(M.b_cont_eync((k))
Branching blocks: for i E [nr]
(B_sum_p[i], B_aun_q[i], ctto_copy_p(i))
(B_carry[i])
(B_to_eync_c, B_to_sync_sub)
[B.pre_candidate_115]] wtt.cooo_candidate_11100
B__candidate_[111 c_cadiddate_111 [ii), cis__conittion0FF1 s_iis_oodittio__
e.to_copy-curr_inste.
22

---

Subtraction blocks: for i E [nc]. j e [2ncl
(D_tc_p(i), D_te_qli], D_to_copy.to_plil)
(D_tc_ayac_a, D_tc_sync_b)
(D_ (D_tc_carryl [i])
(D_ (D_te_counter(] [j])
(D_sub_carme (i])
(D_sub_pli), D_sub_q[i], D_to_copy_suubp(1))
(o_aub_cuunter]]))
Instructions Based on Algorithm I and the block structure outlined earlier, define the binary instructions for each process, grouped according to their corresponding block prefix. Considering all the instructions presented below, the total number of instructions is
Las (13mar + Tnc + 1) + e, (8m, + 4m + 2) + 14nc + 11m, + OleM log las).
Instructions: persist addresses (I)
The purpose of this function is to ensure that instruction addresses are not inadvertently deleted. Notably, do need to handle cases where the instruction address is zero, as any unmatched sample will naturally leave the corresponding entry as zero.
Additionally, note that there I_ cuur_uriie _itrrristtrrrr tr or the comparison flag I_to_ _to_compaee This omission is intentional, as both are temporary variables activated only in execution stage and do not retain their values beyond that stage. Consequently, there is no need to explicitly preserve them.
instructions dedicated preserving the current instruction address
INPUT: x[I_ instr [x] [i]]
AND x _[I_to_________t__ compppreeeeeeeeeeeeeeeem [k] [i]] AND
[iI_curr_instz [k] [i]]
OUTPUT: y[I_insta [k] [i]] <- 1
Instruction count: &
INPUT: x[I a______a a_d_rar addr [k] [i]] AND xlp_ [i]]
OUTPUT: y y[I_a__ a_a addr [k] [i]] +
Instruction count: E, nM
INPUT: x =[d_b_addr addr [k] [i]] AND x(I_to_copy_blkk [i]]
OUTPUT: y [[I_b_ade [k] [i]] <-
Instruction count: ε nM
INPUT: x[I_c__ addr [k] [i]] = 1 AND x[I_to_copy. [[k] [i]]
OUTPUT: y[I_c_ad a_ddrr [i]] +
Instruction count: ar
Instructions: compare addresses (I)
In this function, the goal is to compare the current instruction address with the k-th instruction address, bit by bit. The result of this bitwise comparison is stored in dedicated variable (I_is_e __i___eaa),,,, and counter is activated to trigger process that verifies whether all bits match. The set of instructions defined below handles both possible outcomes: when the addresses match and when they not.
INPUT: : x[I to_ stt__coopreeeeeeeeeeeeeeeeeeeeee [k] [i]] = 1 AND x[I_ [urr instr [k] [i]] x instr [k] [i]]
OUTPUT: 1) y[I_ y[I_inatr [k] [i]]
[I_ instr [k] [i]] AND y [[_ ____i__quuall [k] [i]]
AND y [[__couterrr [k] [i]] +-
i> 1) [I_inntttt [k] [i]] <- x [[__instr [k] [i]] AND y [[I_i_equal [k] [i]] < 1
Instruction count: 28, wr
23

---

* xXI_innstz [k] [i]] OUTPUT: (i = 1) ylI instr [k] [i]] < x[I_ =[I_inatr [k] [i]] AND y[I_counter [k] [i]] <
INPUT: [[I_to____ wtw.ooarreeaaooooo [k] [i]] 1 AND x insti [i]] [
(i > [yy[_instrrr [i]] < x[I_ [k] [i]]
Instruction count: 2. -11
Instructions: check full address match and trigger copy (I)
Following the previous stage, each of the comparison flags is evaluated iteratively using the counter variables. If all of them are equal to one, this indicates that the current instruction address ex- actly matches the k-th instruction address, which activates the copy flags. the case where the I_is_ variable is activated, but its corresponding I_ _ocunterr has not yet been triggered, we preserve the value of [_is_equal using second instruction.
INPUT: x[I____otttee counter [k] [i]] AND <[__ _____i______________ [k] [i]] =
OUTPUT: n)) [I_ counter [k] [i+1]]
(1 = mr) y [I_ _o__tt__oooo cop__oooy__aa.. [ALL]] + AND
_I_to_copy_b(4 [ALL]] <- 1 AND
Instruction count: y[I_to_copy_c [ALL]] <-
INPUT: [I_ counter [i]] AND x[I_is [[I_is_equall [k] [i]]
OUTPUT: y[I_is_eque _qual [k] [i]] +
Instruction count: E
Instructions: copy address a, b and c (I)
The goal of this function is copy the matching k-th instruction triple (a, b, c) into their respective blocks. This is achieved through two distinct sets instructions. The first set defines the conditions under which copying should occur, while the second denoted with the _elay and _sync suffix is responsible for propagating the copy.
Strictly following the framework in Section 4 this second instruction set is technically unnecessary. One could, in principle, use the output from the final stage the delayed process the direct output of the first set. However, we adopt this two-stage implementation due to the nature of Neural Tangent Kernels (NTKs) and the challenge of managing write conflicts. If the alternative (single-stage) approach were used, the number of instructions writing to the same coordinates would increase with the number of instructions the program, thereby leading to a proportional increase write conflicts.
To mitigate this, we introduce delay structure that propagates information sequentially across the instruction items. This design ensures that the number of write conflicts remains constant, regardless of the program size. While this approach incurs additional computational cost the form of more blocks and iterations- it does not hinder learnability, as discussed in Appendix C
guaranteed to be plementary variable for each, prefixed by sync. These sync variables function similarly to their delay counterparts but always set 1. This allows them serve reliable synchronization mechanism across different processes.
Additionally, since not all relevant variables
introduce sup-
INPUT: to_tto_ to_ __I__to_oopy_llllll_____________
coky_a[k]] [i]] AND x[I_a. a_ addr [k] [i]]
OUTPUT: y a_ddr__ _eriddrdeelylll [k] [i]] + 1 AND y [[I___ade addr [k] [i]] +
Instruction count: ε, TMM
INPUT: x [[__ b[__ttt_ooy___]]] [i]] AND <[I_b_ades [k] [i]] =
OUTPUT: y [[I_ addr adddr_delyylld [k] [i]] 1 AND y [I_ addr [k] [i]]
Instruction count: n.
INPUT: x [II_to_copy________________ [i]] = AND x[I_ =[I_c_addr [k] [i]] =
OUTPUT: (i = 1) [[__c_addr [k] [i]] - 1 AND y [[I_ c_drr deerrdeellllll [k] [i]] + 1 AND
_[I_copy_syye [k]] 1
( [I____dddrrrr [k] [i]] AND y [I_c_addr_ aeeaaddrrdeelllll [k] [i]]
Instruction count: E nn
24

---

INPUT: x _[I_a_adde [ [i]]
OUTPUT: (A: < [T) y[I_a_addr_daa [k+1] [i]] < 1
(k ET) yMM_aaddr addr [ALL] [i]] <
Instruction count: nM
INPUT: x x[I_b_addr [_ [i]]
OUTPUT: (A < (T) y[I_b_addr aeladdddeelaaa [++]] [i]] <
(k ÊT) y[M_b_ddan addr] [ALL] [i] +
Instruction count: MMM nM
INPUT: x[I_c_addr: [eddr__eea[[[]]]]]]_]_ [i]] 1
OUTPUT: (h (r) y[I_c_ [[I_c_addr__ l___addddelay_yaaaeeereraaaaaaee [k+1] [eelay[=+1]]]]]]]] <-
(k ÊT) ppre__andidate_lliii <
Instruction count: .nr
INPUT: x[I [[I_copy_sync(k] -
OUTPUT: (A f y[I_ [[I_copy_aai [k+1]] +-
(k fz) y MMM_oo_omparee [ALL] [ALL] < AND y [iB_to__ync___
Instruction count:
Instructions: persist addresses (M)
As with the instruction block, the memory addresses must also be persisted. For the input block below, there no need handle scenarios where other variables are equal to 1, as those cases are either already addressed during the comparison stage or do not arise during execution.
INPUT: : [M_tt__ cttto_cocreeeeeeeeeee [k] [i]] 0 x [M_ haM_mem_adee addr [k] [i]]
AND
x[M_aaadrr [k] [i]] = 0 AND x [_____dda [k] [i]]
OUTPUT: y [KK_mem_adee [ks [i]] +- 1
Instruction count: fM Y
Instructions: compare addresses (M)
In this stage, each memory address is compared to the addresses stored in the instruction fields a and b. Note that the addresses from and b have already been transmitted their corresponding memory
blocks. Below, we describe the behavior for different combinations of the values of M_ a_a_addr, M_ b_addr, and M_mem addr.
INPUT: [M__t__oaa htw.oroarreeeeeeeteeoeeeeeeeeeee [k] [i]] 1
x [M_aa xXX_a_addx [k] [i]] x [M_mem_adde) addr [k] [i]] AND
x[M_b_ addr [k] [i]] x [_M_em__dde____eee______________ [k] [i]]
OUTPUT: (i 1) y [M_is_equalla[k]] [i]]
AND y [M__is_equal_b__ [i]] 1 AND
y [M_ "M__oonter_a_k]] [i]] +- AND "[M_counter_b[3 [i]] AND
y [M_mem_addr [i]] +- x <_M_mee_adddr
(i > 1) y DN_is_equal_a
[i]] < 1 AND y [[M_is_equal_ [x] [i]] < 1 AND
y [_M_em_adees [k] [i]] +- x[M_mem_addr [k] [i]]
Instruction count: 2 RM
INPUT: : x [M_to to_ wow.oooaaeeeeeeeeoo [k] [i]] 1 AND
x[M_a__ x[M_a_addr= [k] [i]] # [M_mem_____ ae__mmmm_ddr__d_mmm addr [k] [i]] AND
x[M_b. addr [k] [i]] [M_ mem_ addr [k] [i]]
OUTPUT:
y [M__i_MeM__u_______e_Si____ wqwel_uualllll..e [x] [i]]
AND yM__cuuneer [[k] [i]] AND
y ww__em_addr/ [k] [i]] + x [MM_em__ddr_] [i]]
( > 1) [M__i_eeuual______ [k] [i]] < 1 AND
y [X__ee_addr [k] [i]] <- x[M_mem_addr [k] [i]]
Instruction count: 2 RM
25

---

INPUT: x [M_to. to_ www.areapeeeeeeeeeo [k] [i]] AND
x x[M_a_ __M_a_addes [k] [i]] x m_m_mmmmmrdrrrraa [x] [i]] AMD
x[M_b_adee bddddr [k] [i]] * x[M__em__ee addr [k] [i]]
OUTPUT: (i y aM_ia__qual_aaa22 [i]]
1 AND y [MM_counter___ [ake]aa[]]]]___]__ [i]]
AND
y [M_mem_ [M__em_addr
addr [k] [i]] - x [M__m [[M_emmaddr [x] [i]]
(i 1) y [M_is_ a [k] [i]] < 1 AND
y y_M_ee__ddee [k] [i]] + x x[M_mem_addr [k] [i]]
Instruction count: M6M RM
INPUT: [M__t__ compare [k] [i]] = AND
x [M_a, addr [k] [i]] x [X_mem_addi [k] [i]] AND
x [M___ b_dddrrf [k] [i]]
[X_mem__ae [k] [i]]
OUTPUT: x [[M_em_aaee addr [k] [i]] + x [[M_mem_adde addr [k] [i]]
Instruction count: M 7MM
Instructions: check full address match and trigger copy (M)
After computing bitwise equalities for each address and each address bit, the comparison flags for both and are checked iteratively. If all bits in given comparison equal to one, this indicates match with the corresponding memory address, and the relevant processes are activated.
In the case of a match with address a, this triggers the process of copying the content of memory address the subtraction block. For match with address similar copying operation is triggered. However, instead of copying the bits directly, the inverse of each bit is copied. This serves negate content of b, as required by the subtraction logic, which will explained the following instructions.
Additionally, when match is found in b, another flag activated indicate which memory slot corresponds to the current match. This flag is used later to update that memory slot with the result of the subtraction.
INPUT: [M_ counter__aae a] [k] [i] AND x x[M_is [MM_i__e_] [IM_is_equal___ a] [k] [i)
OUTPUT: nu) y [M__ [TV__countr___ a_ [k] [i+1]
(i = nM) y [___to_coopp stt_copo___meeeeeeeeaeaaeaaeeeee _am_mm__________________________ mom_comt]] [k] [ALL] +
Instruction count: fM nM
INPUT: : x [M_ counter __] [k] [i] AND x x[M_is_equal_a] [k]
OUTPUT: y [M_is__quuee _s__e__l__a] [k] [i] +
Instruction count: fM
INPUT: counter_rrr____ b] [k] [i] AND x x[M_is_equal_ [k] [i] =
OUTPUT: (i < nM) y _M__ootter___________________ b] [k] [i+1] <- 1
nM) [M_to_ to_tto_______ttttt coppy_o_______ppop_p_________ ca__cooopiiiii inv mem_ cont] [x] [ALL] AND
y [M_is www.hatchhhha b] [k] [ALL] +-
Instruction count: fM TM
INPUT: x [M_ counter b] [k] [i] AND x x[M_is_equal_b] [k] [i]
OUTPUT: y [M__ [KK_i_______ ds_equal_bb [k] [i] <
Instruction count: fx
Instructions: copy memory content (M)
The following instructions cover all combinations of flags and memory content values. In this setting, we ensure that every valid combination memory content and flag activation is captured. The transmission of memory information to the appropriate targets follows the same delay structure previously described, which helps manage write conflicts.
Importantly, the memory content is preserved in all cases, and the indicate the corresponding memory slot for later updates memory b.
M_i_smaaaattteeee sss_mttc__bbb flag is retained to
Additionally, we must account for cases which the memory content is null. This is necessary due to the flag M_ t_tt__oo _tt__opy_____ inv_ mem_em__e wem_cont, which signals that the inverse of the memory content should be copied. As a result, its effect only arises when M_ M_mem_cont cont zero, whereas the effects of other flags triggered when the memory content is non-zero.
26

---

INPUT: [M_ ___mem__oom cont] [k] [i] 1 AND x x to__too_____..c _e__ya__mm_____ cont] [k] [1] AND
x[M_ $[M_to_copp htt__jiv____eee__ee hww_wb__m__coem __mm_mmmmnt [k] [i] 1 AND x [MM_is_match____ [x] [i] = AND
MM__to_copy_trom_tt
[k] [i] = 0 AND x[H_sub_result]] [x] [i]
OUTPUT: 1) y [on_m [k] [i]
1 AND y yiM_is is ma [k] [i] 1
y [MMaa_cont_delay] [x] [i] +
y ylM_b_cont__yy [k] + 1
y cM__a_cont_symc]] [x] <
(i 1) y [M_mem_cont]] [i] + AND
+ AND
[M_ [M_a_com ae___cont_ddilll
[k] [i] <-
Instruction count: fy nc
INPUT: [M_ [K_mem__omm cont] [k] [i] = 0 AND x x[M_to__aa to_ _oppy_a__eeee m__me___ommm [k] [i] AND
[___o_copy-_ iny_
wwwbbb_eemmm__e cont] [k] [i] 1 AND x x[M_is_match__ [k] [i] =
AND
x OUTPUT: (i 1) y [M__ismmatch__B__ [k] [i] <- 1 AMD y [|M_b_ccon_deely]] [k]
[k] [i] 0 AND [[K_subrresul]]] [k] [i]
[i]
AND
y se__coot____se_ [k] + 1 AMD y [M_a, a__aa____y____ [k] + 1
(i > 1) [M_js_match b] [k] [i] + 1 AND y b_t_b_ce_dddeaa// [k] [i] +
Instruction count: tx nc
INPUT: [M_mem_comm [k] [i]
x x[M_to_copp
[k] [i] AND
x [[__o__ooyy_a sto_copy_imt
wew__iiv_e______e harp__bmmm______eeee ft_ee___omm_e comm]_coo]]_______________]_ccc_ [k] [i] 1 AND [k] [i] 0
b] [k] [i] =
AND
x x[M_to_comm htt_to_coo__frm_eeeee poo__ffoo__sblll [k] [i] = o AND [[K_sub_result]]:
OUTPUT: (i 1) ii__i_smmch__Bee b] [k] [i]
1 AND y [M, ylM_b_cont_ddlayy [k] [i]
AND
y [M_ hot__coot_ssce_eeeeeeeee [k] 1
(i 1) [MM_s_mmtchh_ b] [k] [i] < 1 AND y [M__b_cot__delll [k] [i] + 1
Instruction count: fM nc
INPUT: [MM_mem [__ memmmmmmmmomaa_eee [k] [i] AND x I[__to____ so_copy__ a___mm___________m__m________e__ _t_me___ooti cont] [k] [i] AND
_[M_to_copy___e pep__coo_iiiss htrp_invbb__aee hnw_m_mem_____eeeeeeeeeeeeeeee__ cont] [k] [i]
AND x[M_is_matcc b] [k] [i]
AND
x wettttoooo_ffomm_ee
[x] [i] = 0 AND x
[k] [i]
OUTPUT: (i 1) y [M_mem_cont] [k] [i] <- 1 AND y|M_is_match__]
[k] [i] <- AND
y [MM_b_cont_syae [k] 1
y [M_ [M_mem_comm cont] [k] [i] + AND y sas_mmtcc_bb] yMM_is_macch_b)
[ [i] +
Instruction count: Eys nc
INPUT: : [M_ mem_memmmmmeee cem_ [i] = AND x DM_ to a__.em_mcott]] [k] [i] AND
[M_ ht__t_cooy__in_bbb.b ttabbb_mmmoottttt_ [k] [i] AND <MM_ss_atch bl [k] [i]
AND
[[N_tt_copy_from_ete
[k] [i]
x[X_sub_result] [k] [i]
OUTPUT: y ["__mm__mmm p____mmmmmon______ [k] [i] +- 1 AND y Mr__a_cont_delaayy [k] [i] < 1 AND
IMM_a_cot_ssydd [k] + 1
Instruction count: lx ne
INPUT: x [M___cont [k] [i]]
OUTPUT: (A: < ET) y[M_a_com [[M_a_cont_da__ delly [k+1] [i]] <
(k = EM) y yDD_sub_pli]] <
Instruction count: fM nC
INPUT: x [M__b_oottddelll [k] [i]]
OUTPUT: (A < L.) y ba_ob____oe____eeeeeeeeeeeeeeeee [k+1] [i]] +
(k LM) y [D__tcppii]
Instruction count: fM nc
INPUT: x aataa__c____palaa [k]] =
OUTPUT: (A PMT) y yM__a [[t_a_cont, wowottoonctttoooooooooooooooooot [k+1]] [k+]]]+]]]]]]] <-
(k Ear) y [D__tc_sync_al
Instruction count: Êx
27

---

INPUT: x b_cco_ttsssnnn [k]
OUTPUT: (A: < EMT y bat_b__ont__aee [k+1]] <
(k EM) y y[D_te_q[1]] 1 AND [D _D__cc_cunntee [1]] <-
Instruction count: tM
Instructions: negate memory content in (D)
This process takes place after the memory content has been effectively copied. The overall goal of the subtraction blocks is compute the difference between the memory contents at addresses and To achieve this, we adopt two-step procedure.
Before describing the procedure, we clarify that memory content is represented using two's s comple- ment encoding. Specifically, the least significant ne 1 bits represent the magnitude, while the most significant bit stores the sign.
Given this representation, subtraction is implemented by negating the content address b and then adding it to the content at address a.
In the previous step, the content from address negated result of b. Meanwhile, we compute the two's complement negation of b by first taking its bitwise inverse and then adding 1. The instructions below implement this stage, covering each operation involved in bitwise inversion, addition, carry propagation, and counter updates. These instructions follow the same structure described in Appendix B.2 but limited ne bits, meaning the final carry (MSB) is not propagated as an additional bit as was done in Appendix B.2
forwarded holding stage, awaiting the
After 2nc iterations, the addition is completed. The final counter triggers the copy flags, which forward the result to the same staging area as the content of a. In the second step. we sum these two values, yielding the desired result: M [a] M[6..
INPUT: [DD_tc_piil] 1 AND x[D_tc_q[ii 0 AND x cop_toocooy.tc..lli OUTPUT: y +D__c__piii <- 1
Instruction count: nc
INPUT: [D. [c]][[]]] 0 AND x[D_te_q(i]] AND x xiD_to_copy.tc_plil
OUTPUT: y yD__t [o_tc_p[ii] + 1
Instruction count: nic.
INPUT: xDD_tc____ [DD_tc_p(il] AND x[D_tc_q[i]] AND xDD_to_coyy.tc..lit
OUTPUT: yD__tc _tt_ttccrcll__teele [i]] +-
Instruction count: ne
INPUT: xDD_tc__cccc carryyll OUTPUT: (i < ne) [[_tt__((++]] + 1
Instruction count: nc
INPUT: x xDD_tc_ [5]]
DUTPUT: (i < 2nc) yD__tc_counteer [i+1]] +-
(i = 2nc) [D [D_tc_sync_b] <
Instruction count: 2nc
Instructions: synchronize and trigger copy of negated content of b (D)
In this operation, the copy is triggered only after confirming that both processes (negating the content of 6 and copying the content of a) have been completed. This ensures no operation begins before all necessary inputs are available at their designated locations. either of the two flags has not yet been activated, we preserve the current values until both are ready.
INPUT: to0_tc_sycc__aa
AND [DD_c__syc_bl
OUTPUT: y [D_tt__a tt_tttt__o___peeeeee Instruction count: 1
ctt_ccoottc_cceee tc_pp [ALL] +
28

---

INPUT: _D__tc____pp sc_c_aa_ AND x[D_tc_eync_bl
OUTPUT: _tc__aycc_a] =
Instruction count: 1
INPUT: [_D_tc_ayni sc_aync_al 0 AND x[D_tc, sc_ OUTPUT: y[D_ta _t__sync_bl
Instruction count:
Instructions: copy negated content of 6 (D)
Once the the content of copied to D_sub_q This the location where will later summed with the
the___coppp _cpoy_tc_c... flag is activated, the content of D_tc_P. which encodes the negation of
content of
In the following set of instructions, do not include a case for when p_tc__ii since after 2nc iterations, D_tc_q is guaranteed to be zero.
AND x[D_tc_q[i]] OUTPUT: (f = y) _______uu_____]_________________ _[i]] AND y(D_sub_coutter counter] [1] +
INPUT: [[D_tc_ppiii
AND x coptto.coy..tc.llii
(i > y [D__ub_q[[i) [i]] =
Instruction count: nc
Instructions: add the content of the negated content of (D)
Once the negated content of has been copied to the same stage as the content of a, the final subtraction result obtained by performing simple summation. The instructions below follow the same addition structure described in Appendix B.2 After completing 2nc iterations, we trigger the sync flag to proceed the next stage.
INPUT: [D_ s_______pp_ cut__p(it [i]] 1 AND x x[D_aub [i]] 0 AND OUTPUT: y yDD_sub_p (p__ub_pp[i]] <-
=
Instruction count: nc
INPUT: [D_ [D___ub_ppp aau__u_ii__ [[]]] = 0 AND x x[D_aub, [ub_ll AND x c.D.to_copy.eub_plil =
OUTPUT: [o_sub_p[il] <-
Instruction count: ne
INPUT: [D_ sub__[ub_]]]] = AND x x[D_aub_q[il] 1 AND [DD_to_copy_sub_p =
OUTPUT: y ht__sub_carree [i] +-
Instruction count: nc
INPUT: [D__sub____ carry] [ery][s [i] =
OUTPUT: (i < nc) [D_aub, [i+1] Instruction count: ne
INPUT: xDD_sub_cooutt counter) [i] -
OUTPUT: (i < 2nc) y cub__cruter]]] [i+1] +- 1
2nc) [___to_syne
+
Instruction count: 2nc
Instructions: copy subtraction result (D)
At this stage, the flag D_to_ so__o__ssub___ppp indicates that the content of D_sub_p. which holds the result the subtraction, should be copied to all memory slots labeled as M_sub_reeeee result. This update is carried out using the matching flag M_ is matchatchh b and the copy trigger ttttto_o__fooooeee as specified Algorithm|] [ in order to update the memory content at address
In the following set of instructions, we omit the case where D_sub_ _q is 1, since after 2n_C iterations this variable should always zero.
We also implement the condition from Algorithm I used to determine the next instruction. By checking the most significant bit (MSB) of D_ sub_p. which represents the sign of the result, decide the next step: if the MSB is 1, the result is negative and B B_is_ cisisicoooiioooff is activated: otherwise, B B_is_ condition..oooooccoiooooooooocot triggered.
29

---

INPUT: x [D sub [_bb_[[i]]
AND _iD_sub_q[ii)) 0 AND xiD.to_coyy_sub_p[il]
OUTPUT: (i < TC) [M_ su_ resullt((a]]] [i]] <-
(i = nc) ___is_______________ ct__diiitoonnn [ALL]] < AND y_M_subrresult [ALL]
[ALL] [i]] < AND
y i cop.yyoooopooooppoppppo. wtt_ooooffroon.cccppppaaaaaapaae from_ sub [ALL] [ALL]] 4-1
Instruction count: nc
INPUT: x x[D__uul sub
st____u_pppp_ppppp pub__ppil] p[i]]
o AND x xDD_sub_q[ãl] AND xiD_to_copy_sub suppy__su_ppp]]]]]___________p]p =
OUTPUT: nc) y [B_ condittion_O(ALL]]]
[M_ to_ copy. wwtppccoo__..ooo.po from_sub [ALL] [ALL]] +
Instruction count:
Instructions: increment current instruction address (B)
This set of instructions computes the address corresponding to the else condition in the branching logic of Algorithm Specifically, calculates the address of the next instruction, denoted by candidate_ 0, based the current instruction address. The computation follows the same addition
structure described in Appendix B.2
By default, the initial vector & is configured such that the first current instruction is the all-zero vector, and the variable x xB__sum_pp [1] set to 1. This setup ensures that the algorithm always begins with the first instruction. After this initialization, the subsequent iterations proceed according to the logic defined by the instruction set. During the selection of the instruction address based on the branching condition, the chosen address is also copied to scratchpad area, which is then used to compute + Once the + 1 address is calculated, it is stored in the B __sump bits and retained until the appropriate copy flag is activated.
INPUT: : x 1_____mm_____ sum_p[i]]
AND x x[B_sum_qqia 0 AND x LBB_to_copy_plll
OUTPUT: y [___su___[_]] + 1
Instruction count:
AND x IB sam__mmm]l) AND INPUT: : x [B_ sum_ [i]] 0
OUTPUT: y _su__[[i]]] <-
Instruction count:
INPUT: xB sum [i]] AND x x[B_sum_q(i]] 1 AND x[B_to_copy copy-p[i]]
OUTPUT: y [B_ carry [i]] +
Instruction count: n
INPUT: x [[___arryy_aaa [i]] =
OUTPUT: (i < ny) y [B__su sum_gu [i+1] Instruction count: ni
Instructions: copy next instruction address (B)
Once the copying flag is activated, the contents of B_ s_mm_p copied to B_candidar date_ Simulta- neously, we set __swm_pp_ [1] to ensure that it can increment the next instruction address during the next instruction update.
INPUT: : [B__um___ppppp [[___u___[_]]_ [[]]]
0 AND x [B_tt____ _e__to_com to_copy-p[i]] OUTPUT: (i = 1) x x[B__xladddd_ www.ccaannnneeooeececc [[i]] AND x [B. [B__sum__pll [[i]] = (i 1) [B. candidate =
AND x x[B_sun, [1B_sum_[[i]]
Instruction count: y
INPUT: x[B_ssuuu st__ssumppii [i]] - 0 AND x x[B_sum_q[á]] 0 AND x[B_to_copy_plii]
OUTPUT: (i = x[B_su[__pp [[B__sm_p[i]]
Instruction count:
Instructions: synchronize operations (B)
In this operation, we synchronize the two independent phases: the subtraction and the retrieval of address c. Once both processes complete, their results are simultaneously copied to the branching block. To ensure proper synchronization, we also include instructions that preserve the state of one flag if the other has not yet been activated.
30

---

INPUT: x[B_to_sync_cl AND [B__oo_syc__ul
OUTPUT: xDD_ htt_ccoy_auub_ppap
< 1 AND y y___to_copp -p [ALL]] <- AND
y y[__t__ uiB_to_copy_candeee copy_candidate__ [ALL]] <-
Instruction count:
INPUT: x[__oo __B_tt_aynee aync_c] AND LLB__t__ayn__ee
OUTPUT: y y[__o to__s_ys_ccc
Instruction count:
INPUT: x xB__o [[B_to_sync_c
AND [[B_to_sync_sub 1
OUTPUT: y[B_ y[B_to_sa to_sync_sub] +
Instruction count: 1
Instructions: copy instruction address (B)
Once synchronization is complete, copy the value of __cadidate_1 from the staging area __pre_canddaate, The value the staging area is preserved until the corresponding copy flag is activated, as detailed in the instructions below.
INPUT: [B__prr [___pre_________________________ candidate, [[]]] AND xIB coppcccaanidattee1lllll
OUTPUT: y [candidate, [[]]] +
Instruction count: var
INPUT: x __B__pre_caddiieee
[i]] = AND x c can.cooyycanddiatte.... [i]]
DUTPUT: y [[B_pre_candidee candidate_1[i] Instruction count: fr
Instructions: update instruction address (B)
Both candidate addresses are synchronously copied from their respective fields, along with the branching condition specified in [lgorithm[] Based the activated condition, one of the candidates selected. The chosen candidate is then copied into I_ (_curr_ii __urr_instr, and I_to_ I_to__c_paall_aaae compare activated across all bits and instructions. Additionally, previously noted, the selected instruction is also copied to B_sum_q to enable the computation of the next instruction address.
INPUT: x[B [[__is_ wwwnoiiiionnnl..i [i]
AND x htt.iiissoniiiionn_ooco [i] AND
[B_ [e__candidate__111 [[]]
x [[___ann [l__ddaideeee [[]]] x[B x[B_candde St___cnnddate__e0 [[]]]
OUTPUT: (i < 14)
[ALL] [i] <- 1 AND y [B__sm__q [[]]] <-
(i nu) y -nsurrriiss]]]__ [ALL] [i] <- 1 AND
y [I__ to comparee]] [ALL] [ALL]
AND y[B_ sum [i]]]
Instruction count: 2n,
INPUT: x ltl.isscodiiiiono. 1] [i] AND ctw.sissocniiionnnoccoo [i] AND
cTTB_ccadidate_... [_____[[]]]] [[i]] = 0 AND [IB__andidate_ _[[]]] x [BB_canddddate_BBB
OUTPUT: (i 11) [I_tt__________________ totttt__ccpppp compare] [ALL] [ALL] +-
Instruction count: 2
INPUT: x[B wtt.ji__condtiionn1111 [1] [i] AND x[B is www.oiiiiinnno.. [i] AND
x <[B_candidate__[ii
x [[B_candidate___ [i]]]]
les__andidate_11111 [i]]
OUTPUT: (i < n4) [[__[[r_______ _ecurruiurrrr [ALL] [i] <- 1 AND [[B_sum_q(i] [i]] <-
(i n4) y [I_ [____rr______ cuur_inntrr [ALL] [i] <- 1 AND
y [I_to to__t__coooo compare] [ALL] [ALL] 1 AND y [[i]] +
Instruction count: 2n,
INPUT: x [[B_is_conil wtt.iissoniiiion___ 1] [i] AND wtw.iissooiiiion___c [i] AND [el__andidatee_001
= 0 AND x x[B_ sal__canddat__e11ee [[i]]] x [[B__caiddate_____ [[i]]
OUTPUT: (i n1) [I_ [I_to__oomaan to_pprrccceee [ALL] [ALL] +
Instruction count: 2
As required by the NTK learnability results, detailed in Appendix the following instructions exhibit a finite number conflicts per coordinate. These conflicts are quantified by counting number of outputs that write over the same coordinate. In this implementation, the maximum number of conflicts This occurs the ___me____ addr bits, where memory values must be persisted under different combinations of control variables within the same block.
31

---

C Proof of the NTK predictor behavior Theorem
In this section, give the complete proof of Theorem 5.1 For convenience, restate both the underlying assumption and the theorem below: Assumption 5.1. For each test imput a and for each position i E [K]] such that the ground-trun
output (( To has the i-th bit set, the number of training examples that not match and have the i-th bit set (which we call unwanted correlations) is less than the ratio -w (i:) /w" (ix) II
Theorem 5.1 (NTK predictor behavior). Consider an algorithmic problem cast temphate-matching
and encoded in training set (X, S IR R as described in Section 5.1 Then, under
Assumption 5.7 the mean of the limiting NTK distribution μ(ā) @ X (x, x for any test input & E IK contains sign-based information about the ground-truth output, namely for each coordinate of the outpul = 1,.... ., k; p(.); S if the ground-truth bit at position i, f(t), k set, and p( > 0 if the ground-truth bit at position f() is not set.
Proof. The proof begins by calculating the kernels ((X, RR xRE and ((ē. R Using Equation I
+ = x) = ((d c) + +cll @ I E XRE
(10)
where
d = k
and 2
(11)
We can observe that since d > 0, θ is positive definite. Indeed, since 11 (the matrix of all ones) is positive semidefinite, (d - c) TN. + cl1 is (strictly) positive definite and so the Kronecker product with Tg also positive definite (see Appendix (A). Similarly, the test NTK is given by
((a = fT @ Ls E RAxb
where for each i 1.2...., k::
f. cos (T - 0.) + sin 0:
2; π Ó 2
(12)
2
and
0, arccos (2;)
(13)
where z; is equal to 0 or 1/ nn depending on whether & matches the i-th training example. Since takes only two values, the resulting 0; takes two values 0 and @ (corresponding to ã = 0 and
à; = 1/ n.) and subsequently each f; also takes two values 1 and fl. Finally, an application of
Theorem A.1 gives
θ = d Iv (d-c) c ck)
1
c
11T @ 4
Substituting everything in 1- we find that this takes the two values (.t) and w² (it) as discussed in the main paper, namely:
32 ly 2T 1) + 2y sec (g)
(e-'f): = w
(2it - 1) + 2x - 1)
if & does not match the i-th training sample and
(Vi² - 1 - y) (n²² - k))
x <(k kk + 2/1222 -1
(0-'f), w w'())
(2 1)(k: 2nT 1)y
(2T 1)(k: + 2 - 1)y
(I: 82 + 2x 1) csc csc-1(y)
V - 1 2n²
(2ir () + 2n 1)y
if & matches the i-th training sample, where y /ng- Using symbolic calculation system
(Mathematica Inc. [12 we can establish that for all possible values y (i.e y = vmm for m
1, ..... b), nd (i) paper.
< 0 and w' (#) > O. The rest of the proof is exactly as given in the main
'Theeee is a slight abuse notation here when using f()) since f does not operate on encoded inputs. Depending on the context, we may use क to denote both the pre-encnded and encoded test inputs.
Il w (ă) is always non-positive and the ratio is neganegaeive
32

---

To verify that Assumption 5.1 holds for a particular application we need bound the number of unwanted correlations for each possible test imput R. An easier way to verify that Assumption 5.1 holds is by studying the number of conflicts, as defined in Appendix [ Note that if the maximum number of conflicts is c, at most c training examples can have a ground truth label of 1 at the same position. In particular, this shows that the number of unwanted correlations is at most è for any test input é. what follows we show how we leverage this observation to show that Assumption 5.1 is satisfied for all tasks discussed in the main paper:
Satisfying Assumption 5.1
For the case of binary permutations of length e, we have e template configuration and the input dimension k' = t. Since we have no unwanted correlations, Assumption 5.1 trivially satisfied.
For the case of binary addition of two b-bit numbers, we have 2 template configurations and the input dimension is k' 4f. We find symbolically that the ratio -w' (&) / is decreasing as function of ne (for fixed E) and strictly greater than 1 for all é 2 1 and n S 26. Since the maximum number of conflicts is Assumption 5.1 is satisfied.
For the case of binary multiplication of two f-bit numbers, we have 11 template configu- rations and the input dimension is k' = 20 - 2. By adding extra training examples with corresponding ground truth labels of 0 that of training examples to k' 21c. We find symbolically that the ratio -w ( (i)/u" (Ø) is decreasing as function of n (for fixed E) and strictly greater than 2 for all
never matched, can augment the number
1 and n S 78 + 12 Since the maximum number of conflicts is 2, Assumption 1 is satisfied.
For the case of SBN with memory size fs = f, we have = 52 E 01) + 02 log cs template configurations and the input dimension is k' = 13/(logg ( + ca) cs log, E cs. where c C6 are positive constants based on other configurations of the algorithm being executed. In particular, notice that b S C for some Ci > O. By similar augmentation as before, we can achieve a dataset size of k 5C, Again, we find symbolically that the ratio - (#)/ww" (a:) is decreasing as function of ntg (for fixed and strictly greater than 5C//C1 - = for all { 2 and na S C (and in particular for n& S b). Since there are at most 4 unwanted correlations, Assumption 5.1 is satisfied. The previous argument can be repeated with 1 + s for any > 0 in place of 2 at the exponent of & and a different constant Cg 0.
The above is enough to conclude Remark 5.1
D Proof of the lemma for the order of the mean predictor and its variance
In this section, we provide the proof of Lemma 6.1 the NTK predictor, expressing them as functions of the test vector á. Specifically, we characterize their dependence on the input length k and the number of matching blocks, na. We establish that the variance of the predictions scales as O (1/k'), while the mean coordinates exhibit different behaviors depending whether the corresponding ground-truth bit is set and the relation between & and k'. We begin by caleulating the variance: a direct substitution on the formula for the variance E(+) of Equation we find that the variance for a test input àe is given by
We do so by analyzing the mean and variance of
d + TT AM 2P Ag) In
E(t)
2
where
M (dl
I c
A d Iw
11T
(d c)(d - c ch¹)
and for each i 1.2,....4.. KK:
cos 0,( 0.) + sin 0z
g:
2k' n
The maximum number of training examples that any test input can match is 76 + 1. Refer to Appendix B for details.
33

---

The scalars and d, the vector f, and the angles 8g are as defined in Equation Equation 12 and Equation (T3), respectively. This shows that the output coordinates independent Gaussian random variables with the same covariance. Notice that whenever the test input is part of the training set, as expected, the variance vanishes.
Preliminary quantities To discharge notation and facilitate the subsequent proofs, we rewrite some of the already defined quantities and introduce some auxiliary quantities. Recall that:
d = kd
and 2
We further introduce
d and
d'
2 For a test vector á, we introduce the binary indicator ((t) that indicates whether & matches the i-th training example. With that, rewrite:
2 2k
arccos
if (
0,
otherwise
From this, we directly obtain the cosine and sine of 0;:
cos 0; = Vns if) =1
sin 0, = V
(f)
otherwise
otherwise
Using these quantities, we rewrite:
(T
arccos (1/VTE) + Vna
if =
Zakkma
gi
otherwise
2
and we get that Equation
12
is equal to
g:
+
-rcccos(////ng 2x 2
if [ =1 otherwise
f
gi
D.1 Computing the order of the variance
We begin by recalling the expression for the variance (suhstituting d' and c²):
Σ(w) = (d' + AMAF - 2f Ag) Is
where
M Ix +
and A
d Tk
11T
(d od-colo c) c ck²)
We aim to show that the variance bounded by (11kk). To facilitate this, we rewrite E(x) by expanding the matrix multiplication:
E(t)= d' + +fT (AMAf 2A(f -2)) It d'Is fT (AMAf 2Af) I, 2f AzIz
where we define = f- for notational simplicity. It is straightforward to observe that the first term, d' Ir, is bounded by O (1/k'. Thus, we focus our attention on the remaining two terms. For the second term, we begin by showing that AMA A 2A has maximum eigenvalue of O(1), and therefore:
f (AMA f (1/k')
We begin by expressing AMA in a more manageable form. A direct computation reveals:
AMA = uly v11
34

---

where
d' - d
1
d' - d' + kK
d' d
and V k
(d c)
(d (d- c kc)²
(d - c)
Subtracting 2A from this expression gives:
AMA - 22 (u (a) I + (0 + 26) 11
where
a
and
= (d - c ck3 (d
(d
This matrix has two unique eigenvalues: 2a (with multiplicity k 1) and 2a (v 26)k'. We will show that the largest cigenvalue is (1). To this end, we evaluate these two quantities, starting with 20:
d' c 2(d
u 2a
(d c)²
2n( 1)k
(2 - 1)2
which is negative. For the second eigenvalue, we find:
(3h 1)h²
+ 2 (xr + -1)
2 (N 1)
u 2a + (v + 2b)
(2TT - 1)2
(2T + 11)²
(2T - -1)²
4
4x
π + -
(2 (2T - k'
(2 1) (2x + ko' 1)
Rv'
which is positive and clearly (()). With this result, we can bound the multiplication by the norms of its components. Since Amax (AMA A 2A) O(1) and [|f] O (1/k") (since each f, E O (L/K))).
we conclude:
f'MMA - 2A)f E (1/k')
We now turn the third term, T Az. Expressing z component-wis have:
arccos( (/ 2 yT
f +
2,
otherwise
We then decompose the product T Az as:
f Az af z 1(f
(14)
where
2nk
a
and
b = (2it 12 + -
d c
The first term Tf z can be expressed as:
af z 2T 1)(2 (2iT- arccos (+/Vma) - VT - I) (iT 2 arccos (+/VTE)
which positive and O (1/k). For the second term (T)))) we start by expressing the individual quantities f and 1Tz
FT
Vhg ak'
(π arecos (1/vaE) + Vn v n
n
2mT
2x k'
and
T
The (π arccos (1/TT))
2
35

---

Therefore, the entire term can be expressed as:
b(f 1)(1'22 = 22x 1)(2T - 1+ +k)
2n (T arccos (m/
V - (I arccos (1/ (/v)))))
+ (k' n2 / nno (It arccos (2/ (2//na))
which is positive and O (1/k), therefore, the subtraction of Equation 14 O (1/k). Combining the bounds on all three terms, we conclude that:
(which is equal to fl Az)
( E (1/k)) 4x
completing the proof of the first part of Lemma 6.1
D.2 Computing the order of the mean
Recall from Equation (7) that each coordinate of the NTK predictor mean is given as weighted
sum of w² = w (Ø) and wd = (²) where w = (f)'f); for all coordinates i [k] such that a matches the i-th training example, and (= (O f); for all coordinates i [k] such that &; does mechanism of Equation (6)
not match the i-th training example. In particular, the remplate-matchinn
shows that whenever the i-th ground-truti bit of ã. (() is set, the NTK predictor satisfies:
u( = + | (+) w
(15)
where _ (z) denotes the indices of training examples that do not match a and have their i-th ground-truth output bit set. Similarly, whenever f()); O, the NTK predictor satisfies:
p(x): _-_ (+) w"
(16)
Since [T_ ( is bounded by the maximum numher of conflicts (as defined in Appendix B) which constant for all four tasks (i.e. it doesn't scale with k'), the asymptotic order of (())) is determined solely by the asymptotic orders of wD and w We can thus turn our attention to
-- (0--adl
Iw
11 )
d-ch
(d c)(d - c ck)
which we decompose into two terms:
f
cll
- d c - cd d c + ck)
(17)
For the first term in Equation
17
we obtain for each i = 1,2, ki:
f,
arcccoe//////o V'aa
if (() =1
/na
otherwise
2x-1
The second term is constant vector with coefficient:
na (T arccos (L/TTE)
(d (d-c)d-cctel ck)
(2t 1) 1 k²)
2 n
+
+ k6' n
We now evaluate each case separately.
Case I: For w (.). that is, when Ti (Tx 0. have:
k - n&
2 k n1
w (2)
(a arccos (1/vaE)
2T 1
2T + W' -1
(2 + W - 1) Rk' nna
2 n
(18)
2nT 1
(2m k' - 27rk'
1
36

---

The absolute value of Equation (18 behaves like è (yna/k) and setting ne to different regimes yields the bounds:
- (1/K²)
if The is constant n& is non-constant and sublinear in k ne ck' for E (0,
θ (vna/k))
w (
(1/VK)
Case 2: For w (z), that is, when ((:)) = 1, we have:
2T
2
1
w'
(IT arccos (1/vna)) 2T
2T k' -
(2i 1) v f
n
k/ n
2
( arccos l\/))))
2x
k
(2tr 1)
V
1
(19)
2x 1
n 2T -
When setting n& = k', we note that the second term becomes zero and the first term becomes θ (1/k). Alternatively, the first term in Equation (19) is (1/K)) and the second term is θ (1/vmz). implying u(z)1 θ (n/) Setting na to different regimes yields the bounds established in Lemma 6.1 namely:
(1/vTz))
if na is non-constant and sublinear in k', if na ck' for e E (0, if na k'
w (x)) E
+ (1/VR)
(1/k')
Substituting the derived orders in Equation (6) and Equation (15) yields the orders of Lemma 6.1 completing the proof of the second part of Lemma 6.1
Remark D.1. The conclusion of Lemma 6. holds for any task such that the cardinality I does scale with K for any inpul number of conflicts is bounded by constant that does not scale with the number of bits. To interpret the last condition visually, consider y in Figure 3 bounded by a constant which does not scale with the number of bits (and hence the input dimension k'). For example, that constant for addition equal to
particular, holds for tasks such that the maximum
We require each column of y have sum
E Training Experiments on Permutation
We present two experiments that empirically validate our theoretical findings for the algorithmic task of permutation. We chose this task because it requires significantly fewer models achieve reasonable results compared to more complex tasks such as binary addition and multiplication, which exhibit substantially higher ensemble complexity. Addressing those tasks would demand large-scale computational infrastructure, which is currently beyond our available resources. Nonetheless, our present results still offer strong empirical support for our theoretical conclusions.
For this task, we train two-layer fully connected feed-forward network with a hidden layer of width 50,000 only using standard basis vectors and optimized using full-batch gradient descent. Our goal is to learn some random permutation on normalized binary inputs length k. For testing, we evaluate the performance 1000 random vectors with n& = 2 nonzero entries. To match the assumptions of our theoretical analysis, we initialize the weights exactly as given in Section
1. Number of models to achieve 90% accuracy. Our first experiment examines how many indepen- dently trained models need be averaged to achieve testing accuracy of 90% as a function of the input length k.
37

---

Experiment
Experiment
Ensemble size to achieve 90% accuracy
Accuracy ensemble size
0.5
10
Eisemble size
10F
201
0.4
15
10
20
Emprriaal Theuretind
10
20
14
10
18
20
22
24
20
28
30
50
1001
150
200
250
300
Iuput
Ensembble
Figure 7: Experiment (left) presents the required number of models (ensemble size) achieve 90% accuracy as function of input size compared to theoretical bound from Equation (8) with the appropriate 8. Experiment 2 (right) presents accuracy as function of ensemble size for different input sizes k.
2. Accuracy vs ensemble size. Our second experiment fixes h E {5, 10, 15, 20, 25, 30) and examines how the post-rounding accuracy varies as the ensemble size increases.
In Figure 7 the left plot presents the results of Experiment compared to the bound established in Equation (8) for the appropriate choice of 8 guarantee 90% accuracy for all test inputs simultane- ously. We observe that the empirical ensemble size remains below the theoretical bound, and that both curves follow similar pattern function of k. For Experiment the results the right plot of Figure illustrate the convergence to perfect accuracy as function of the ensemble size for different input sizes k. As shown, larger input sizes require more models to achieve perfect accuracy. but with sufficient number of models, all instances eventually reach perfect accuracy.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims made exactly reflect our theoretical contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our theoretical results in Section 7 and provide future work directions that can potentially mitigate them.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
39

---

Justification:
We do exactly what the question asks.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our experiments serve to verify our theoretical results. Code written using the Neural Tangents package and provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
40

---

Answer:
[Yes]
Justification:
We do exactly what the question states.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli//uuuia wwwiiicgguie//eeeeeeee CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We do exactly what the question states.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We do not have experiments that involve randomness.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
41

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We indicate the hardware used train our models the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp/////errppss.cpppttttt/e/e
Answer: [Yes]
Justification:
We do exactly what the question states.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: As mention above, our work is theoretical and don't believe it has direct path to negative societal impact. On the contrary, we hope that our thorough theoretical analysis can help the community better understand the computational capabilities of neural networks.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
42

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is theoretical. It poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
43

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing, nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
44

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
45


Reviews:
[{"review_id": "Emx3Ryyo9c", "reviewer": "Reviewer_8X6V", "summary": "This paper considers the learnability of a particular class of boolean functions (expressed as a disjunction of simpler blocks) by two-layer ReLU networks with large width. Appealing to NTK theory, they suggest that the NTK limit should converge to approximate functions of this form satisfying a particular margin-like assumption (Assumption 5.1).", "questions": "Rather than saying logarithmic sample complexity (implicitly, in the size of the number of possible inputs, which is confusing), say sample complexity polynomial in the input size (i.e., in the number of bits needed to code an input)\n\nWhat is the convergence error of the large-width network to the NTK limit as a function of the hidden dimension?", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. The paper addresses the problem of learning primitive discrete operations with feedforward networks that, when composed, could be computationally powerful. This is tangentially related to methods like chain of thought, and theoretical understanding of the learning difficulty could be interesting and important.\n2. Section 3 on NTK (an existing result) and Section 4 on templates seem rigorous and correct\n\n## Weaknesses\n\n1. The problem considered here could be much better motivated. The authors confusingly allude to Turing completeness but are not particularly careful or clear. The point is that iteratively composing a sequence of boolean functions of the form considered here is quite expressive. You consider the learning problem for one step in this chain - not the end-to-end learning problem. It’s important to clarify this both so that readers do not get the wrong impression and to make it clear what the motivation of the paper is in the first place.\n2. Related to the motivation, the authors should cite and engage with significant existing work on on the expressivity and learnability of iteratively applying simple neural functions to compute more complex ones (e.g., attaining Turing completeness via chain of thought):\n    1. https://arxiv.org/abs/2309.06979\n    2. https://arxiv.org/abs/2107.13163\n3. I am not able to verify the correctness of Sections 5 and 6, which constitute the core new results. In particular, I do not even understand Assumption 5.1, which is central the message here. Why is w0 non-positive if it’s defined as the proportion of training samples that do not match a block? Shouldn’t a proportion always be positive? This part of the paper should be clarified so that it is easier to understand and verify the results.", "was_revised": true, "final_justification": "I thank the reviewers for their thorough response. My biggest issue was being able to verify the correctness of the core results (i.e., Theorem 5.1). I find the reviewers' elaboration helpful and see the high-level idea better, though I still would not say I can rigorously validate all details (though this could be due to a lack of familiarity with the area). I have therefore raised my score.", "rebuttal": "We sincerely appreciate the reviewer’s time in evaluating our manuscript. Below, we address their insightful comments in order of appearance:\n\n**W1. Paper motivation**\n\nWe appreciate the reviewer’s suggestion regarding the presentation of our findings. To clarify, we want to ensure our intent is not misinterpreted.\n> The point is that iteratively composing a sequence of boolean functions of the form considered here is quite expressive.\n\nWe agree that this composition is indeed expressive, and our SBN exact learning result aims to quantify that expressiveness. Specifically, we learn a set of Boolean operations that, in a loop, enable emulation of a general-purpose computer (SBN), which is a common approach in the literature (see [3,4,5]) to demonstrate expressiveness.\n> You consider the learning problem for one step in this chain - not the end-to-end learning problem.\n\nWe believe this is a potential misunderstanding. Our goal was not to learn a universal computer end-to-end. We build upon existing literature that uses the standard looping mechanism to demonstrate the expressivity of neural networks (see [3,4,5]). While most of these works are constructive, our goal was to *exactly learn* the instructions of the looped SBN computer. In our setup, each training data point corresponds to a single instruction that encodes part of an algorithm. As noted in the paper, iterative execution enables composition across steps, allowing full algorithmic behavior. Only the Boolean permutation task requires a single step. All other computations, SBN, addition, and multiplication, require multiple iterations, as specified. We welcome the reviewer to highlight any unclear passages so that we can revise them for clarity.\n\n**W2. Related work**\n\n> Related to the motivation, the authors should cite and engage with significant existing work [...]\n\nWe sincerely thank the reviewer for providing such valuable references, which help to better position our contributions. We discuss their distinctions in more detail below.\nAs mentioned above, our learnability results apply to the setting where the goal is to emulate a general-purpose computer. In our case, we aim to learn the instructions of the universal computer itself. Once trained, the model can accept inputs that encode arbitrary computations, analogous to machine code. This contrasts with the reviewer-cited work [1], where the learning target is a specific Turing-computable function, rather than the computational model that interprets such functions.\nBoth settings are quite reasonable, and as such, we will incorporate the works cited by the reviewer into the related work section. As noted above, we also commit to revising relevant parts of the manuscript to clarify the distinctions between our Turing-completeness results and those presented in [1,2].\nWith this clarification, we hope our intended positioning of the paper is clearer. That said, in light of the reviewer’s references, we acknowledge that certain passages may admit multiple interpretations. To this end, we will revise such passages (e.g., L10–11, L200–201), outlining how such Turing Completeness results differ from works such as [1,2]. We sincerely thank the reviewer for highlighting these points and for sharing these insightful references. We also welcome further suggestions on how to more effectively present these ideas.\n\n**W3. Clarification on results**\n> I am not able to verify the correctness of Sections 5 and 6, which constitute the core new results. [...] This part of the paper should be clarified [...].\n\nWe appreciate the reviewer’s concern regarding the clarity of our theoretical results. We take this opportunity to elaborate on the meaning of Assumption 5.1, which we intend to incorporate into our paper to improve clarity. The reviewer is correct that a proportion must be positive. However, $w_0$ and $w_1$ *are not proportions*; they are scalar weights derived from the structure of the NTK matrices, as described below.\n\nAs described in Section 5.2, due to input data orthogonalization, the NTK predictor\n\n$$\\mu(\\hat{x}) = \\Theta(\\hat{x}, X)\\Theta(X, X)^{-1}\\mathcal{Y}$$\n\ncan be rewritten as:\n\n$$\\mu(\\hat{x}) = w_1 \\sum_{i \\in S(\\hat{x})} y_i + w_0 \\sum_{j \\notin S(\\hat{x})} y_j$$\n\nIn other words, the NTK predictor is a weighted sum of training output examples, where the weights depend on whether the corresponding training input matches the test input $\\hat{x}$, whose matching indexes are indicated by $S(\\hat{x})$. Hence, $w_1$ and $w_0$ are not proportions but rather sample-level weights, with $w_1 > 0$ and $w_0 \\leq 0$.\n\nFor each coordinate of the NTK predictor, our goal is to have the same sign as the correct output: non-positive if the true label is 0 and positive otherwise.\nTo illustrate this, consider the case where we want a particular coordinate of the predictor to be equal to 1. In this case, the weighted sum must be positive. This requires that the negative contribution from output examples with non-zero entries in that coordinate does not outweigh the positive contribution from the correct output example. This is the intuition formalized in Assumption 5.1, which requires that the number of “unwanted correlations” remains below a certain ratio. This condition ensures that the sign of each coordinate reflects the desired classification behavior.\nWe hope this clarification helps convey the intuition behind Assumption 5.1 and improves the overall readability of the theoretical discussion.\n\n**Questions:**\n\n> Q1: Rather than saying logarithmic sample complexity [...], say sample complexity polynomial in the input size (i.e., in the number of bits needed to code an input)\n\nWe thank the reviewer for this constructive feedback. This is an excellent point about clarity, and we will revise our wording accordingly.\nOur choice of “logarithmic in the number of all possible inputs” was motivated by two factors. First, we aimed to highlight the significant efficiency of our framework. For an $\\ell$-bit input, the space of all possible inputs is exponential ($2^{\\ell}$), while our required training data scales polynomially with $\\ell$. Phrasing this as logarithmic in the total number of inputs was our way of underscoring this exponential reduction.\nSecond, we were cautious about using the term “sample complexity”, as it typically implies a statistical PAC-learning setting with random data drawn according to some underlying distribution. Our analysis, in contrast, uses a fixed, deterministically constructed dataset and provides guarantees for any possible test input.\nThat said, we agree that expressing the dataset size in terms of the input's bit length is more conventional and ultimately clearer for most readers. We will update the text to incorporate this change.\n> Q2: What is the convergence error of the large-width network to the NTK limit as a function of the hidden dimension?\n\nThe reviewer asks an important question regarding the convergence error as a function of the network's width. This pertains to the field of finite-width corrections in NTK theory, a topic with a rich literature of its own (see survey [6], for example).\nIn this study, we intentionally focused on the infinite-width regime. This choice was strategic, as this setting provides a clear framework to convey our central message: that, under specific assumptions, neural networks are capable of learning to execute algorithmic instructions exactly. By removing the complexities of finite-width effects (e.g., dealing with higher-order kernels as defined in Section 3 of [6]), we can offer a clear proof of this principle.\nA thorough theoretical analysis of the finite-width case would be a significant research effort in its own right, one that we believe would warrant a separate, dedicated paper. We opted to prioritize the clarity and impact of our core message, but we agree that understanding these corrections might be a promising next step in this research direction. \nThat being said, the reviewer might find the experiments in Appendix E interesting, as they provide an empirical probe into the behavior of finite-width networks. There, we train an ensemble of two-layer fully connected feedforward neural networks with a hidden dimension of 50,000 on the binary permutation task. Briefly, we find that as the ensemble size grows, the accuracy increases and eventually reaches 100%. Furthermore, the ensemble size required to reach 90% accuracy is always well below our theoretical, infinite-width ensemble complexity upper bound. To further satisfy the reviewer’s curiosity, we also conducted a similar experiment for the addition task. Namely, we trained ensembles of two-layer fully connected feedforward neural networks with a hidden dimension of 50,000 on the instructions for binary addition, as described in Section 4.1 and Appendix B.2. Below, we present a table containing the ensemble sizes required to reach 90% accuracy as well as the numerical bound (from Figure 5) for bit-lengths $\\ell\\in \\\\{3,4,5\\\\}$. Observe that the ensemble size still falls below the bound.\n| **Number of bits**                 | 3    | 4    | 5    |\n|------------------------------------|------|------|------|\n| **Empirical ensemble size to reach 90% acc.**       | 870  | 990  |  1090 |\n| **Numerical ensemble complexity bound** | 4003 | 6691 | 9926 |\n\n---\nOnce again, we thank the reviewer and welcome any further comments. We hope the clarifications are sufficient for them to consider raising their score.\n\n[1] Malach (2024). Auto-Regressive Next-Token Predictors are Universal Learners\n\n[2] Wei et al. (2023). Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers\n\n[3] Siegelmann et al. (1992). On the computational power of neural nets\n\n[4] Perez et al (2021). Attention is Turing-Complete\n\n[5] Giannou et al. (2023). Looped Transformers as Programmable Computers\n\n[6] Golikov et al. (2022). Neural Tangent Kernel: A Survey"}, {"review_id": "hloJsqPjhN", "reviewer": "Reviewer_1CbE", "summary": "This paper investigates whether neural networks, specifically two-layer fully connected ReLU networks in the infinite-width limit (analyzed via the Neural Tangent Kernel or NTK), can learn to execute algorithmic instructions exactly. The authors demonstrate that by structuring training data into orthogonal bit-level templates and analyzing training dynamics in the NTK regime, such models can provably learn four core algorithmic tasks: binary permutations, addition, multiplication, and Subtract and Branch if Negative (SBN) instructions—the latter being Turing-complete. They prove that exact learning is possible using a logarithmic number of training examples, and provide ensemble complexity bounds to ensure high-probability correctness after rounding.", "questions": "1. Can the authors clarify how to obtain the orthogonal training set in practical scenarios? This assumption is central to the theoretical results but may not hold for real-world training datasets. Could approximate orthogonality suffice?\n\n\n2. Your setup leads to exact learning under NTK dynamics with small datasets. How do your findings relate to grokking phenomena, where models trained with standard datasets undergo sudden generalization?\n\n\n3. The analysis assumes infinite width and NTK regime. Have you tested the fidelity of your predictions with finite-width networks trained with SGD?\n\n\n4. Assumption 5.1 is central to the correctness of the NTK predictor. How sensitive are your results to this assumption? Can the authors provide more intuition (beyond the bound of 2 unwanted correlations) or empirical plots showing how performance degrades as it is violated?", "limitations": "Yes. The authors explicitly discuss their limitations in Section 7, including the assumptions of orthogonal template training and direct instruction access. They also propose several promising directions to relax these constraints.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. Provides rigorous theoretical results showing exact learnability of discrete algorithmic tasks.\n\n2. Uses NTK formalism effectively to derive precise guarantees, going beyond simulation-based evidence.\n\n3. Covers Turing-complete instruction sets (via SBN), showing generality.\n\n4. Results are supported by illustrative examples, ensemble bounds, and practical template encodings.\n\n## Weakness\n\n1. Main result theorem 5.1 requires assumption 5.1. Also the paper assume orthogonal training data and explicit template access, which may limit applicability in more realistic, data-driven settings.\n\n2. Does not address noisy or partial supervision, which is relevant for LLMs and real-world execution.\n\n3. Empirical validation is limited; most claims rely on infinite-width limits and concentration results. Practical significance may be limited unless these theoretical insights can be extended to finite-width or real-world training settings.", "was_revised": true, "final_justification": "Rebuttal address my concerns.", "rebuttal": "We thank the reviewer for their time and feedback. Below, we address the reviewer’s concerns and answer their questions, one by one.\n\n**Weaknesses:**\n\n> W1: Main result theorem 5.1 requires assumption 5.1.\n\nWe assume that the reviewer perceives Assumption 5.1 as a limitation. However, it is satisfied by (Turing-complete) SBN instructions, allowing for a very expressive model. This means that for any given program, there exists an SBN-based implementation that satisfies Assumption 5.1 and can thus be learned by our framework. Relaxing this assumption, or showing it is necessary for exact learnability, would be an exciting direction for future research. Finally, even for in-distribution learning (a much more relaxed learning framework than exact learning), gradient-based end-to-end learning of algorithmic execution is provably hard without further assumptions such as curriculum learning or CoT-type supervision.\n\n> Also the paper assume orthogonal training data and explicit template access [...]\n\nWe emphasize that our results concern exact learning: we make no assumptions about data distributions, and the output must be exactly correct with high probability, and not just approximately correct, as in PAC learning. Exact learning is a relatively new theoretical framework [1], and our work offers a good first step toward its understanding.\n\nIn the exact learning setting, the central question of our work is: can neural networks perform a fundamental form of algorithmic computation? Assuming perfect knowledge of each elementary step, we examine whether a network trained via gradient descent can execute the full algorithm and produce the exact bit-level output. To our knowledge, this is the first provable, positive result addressing this question. Going beyond orthogonal training data and explicit template access is certainly an exciting future work direction.\n\n> W2: Does not address noisy or partial supervision, which is relevant for LLMs and real-world execution.\n\nWhile we understand the reviewer’s perspective, we would like to reiterate that our work specifically examines the ability of neural networks to learn and execute algorithms exactly.  To the best of our knowledge, we provide the first proof that neural networks can execute algorithms both exactly and correctly when trained solely on the necessary instructions. We agree that developing a theoretical framework for exact learning to explain the real-world execution behavior of modern architectures, such as LLMs, is a highly compelling goal. However, we believe that achieving such a framework will require significant foundational progress, particularly in establishing exact learning results. In our view, tackling simpler, more analyzable settings is a necessary and valuable step in this direction. We see our work as a concrete and meaningful contribution toward that long-term objective (cf. [1]).\n\n> W3: Empirical validation is limited; most claims rely on infinite-width limits and concentration results. Practical significance may be limited unless these theoretical insights can be extended to finite-width or real-world training settings.\n\nOur theoretical claims are supported by empirical results presented in Appendix E, where we train ensembles of two-layer fully connected neural networks (hidden dimension 50,000) on the binary permutation task. We observe that accuracy improves with ensemble size, eventually reaching 100%. Notably, the ensemble size required to achieve 90% accuracy remains well below our theoretical infinite-width ensemble complexity bound.\n\nTo further address the reviewer’s interest, we conducted a similar experiment for the binary addition task. Using the same network architecture, we trained ensembles on instruction sequences for addition (as shown in Section 4.1 and Appendix B.2). Below, we provide a table showing the ensemble sizes required to reach 90% accuracy, alongside the theoretical bounds (from Figure 5) for bit-lengths $\\ell \\in \\\\{3,4,5\\\\}$. In all cases, the required ensemble size remains below the theoretical threshold.\n\n| **Number of bits**                 | 3    | 4    | 5    |\n|------------------------------------|------|------|------|\n| **Empirical ensemble size to reach 90% acc.**       | 870  | 990  |   1090  |\n| **Numerical ensemble complexity bound** | 4003 | 6691 | 9926 |\n\n**Questions:**\n\n> Q1: Can the authors clarify how to obtain the orthogonal training set in practical scenarios? This assumption is central to the theoretical results but may not hold for real-world training datasets. Could approximate orthogonality suffice?\n\nWe detail the dataset construction in Section 5.1. In brief, we map the set of inputs to an orthonormal set of vectors (e.g., the standard basis) and feed this into the neural network instead. The procedure is straightforward: we iterate through the original inputs and assign each one a unique standard basis vector. This pre-processing step is instrumental as it minimizes the number of unwanted correlations during inference, effectively enabling sign-based recovery of the ground-truth output. This process is efficient since the neural network’s input dimension is equal to the size of the dataset, which, in turn, scales linearly in the number of bits. \n\nThe question of approximate orthogonality is a very interesting one from a theoretical standpoint and is one of the points discussed in Section 7: “Limitations and future work”. Intuitively, the strictness of the exact learning requirement requires strong control over unwanted correlations. From a modeling standpoint, an orthonormal training dataset is the most natural choice to achieve this. Yet, it would be interesting to see if, for specific tasks, this could be relaxed (perhaps at the expense of requiring a more sophisticated rounding function or a larger ensemble size) or if this is impossible altogether.\n \n> Q2: Your setup leads to exact learning under NTK dynamics with small datasets. How do your findings relate to grokking phenomena, where models trained with standard datasets undergo sudden generalization?\n\nWe appreciate the reviewer’s insightful question. Below, we elaborate on this point.\nGrokking represents another learning regime in neural networks, which is very interesting but not covered by the present work. In this context, [2] offers useful insights by contrasting learning regimes and suggesting that grokking may exhibit higher data efficiency. However, grokking remains a developing area, and to our knowledge, no unifying theoretical framework has yet been proposed that parallels the NTK formulation for lazy training.\n\nWe also wish to clarify our notion of the training set, which differs from the standard input-output format used in both grokking and NTK studies. For example, in the binary addition task, our training samples are binary instructions rather than input-output pairs (e.g., summands and their sum). This formulation eliminates sample correlations and enables exact execution over all valid inputs. While unconventional, it allows us to prove exact learnability, a result that, to our knowledge, has not been previously established.\n\n> Q3: The analysis assumes infinite width and NTK regime. Have you tested the fidelity of your predictions with finite-width networks trained with SGD?\n\nOur theoretical claims have been empirically tested through experiments with ensembles of finite-width networks, as shown in Appendix E. A summary of these results is also provided in our response to “W3” above. We recognize the importance of this aspect and are happy to move portions of Appendix E into the main paper in the revised version.\n\n> Q4: Assumption 5.1 is central to the correctness of the NTK predictor. How sensitive are your results to this assumption? [...]\n\nWe thank the reviewer for this insightful question. At a high level, Assumption 5.1 ensures that unwanted correlations with incorrect samples do not dominate the signal from correct instructions in the training data. As Assumption 5.1 is violated, the NTK predictor’s behavior can deteriorate, and the results of Theorem 5.1 may not hold.\n\nTo empirically validate its necessity under our learning framework, we construct a toy dataset that incrementally increases the number of unwanted correlations. The dataset consists of inputs with 100 blocks (each of size 1) and 1-dimensional binary outputs. Each input is a standard basis vector, with output value equal to 1 for $p$ randomly chosen data points, and output 0 for the remaining $100-p$ data points.\n\nWe construct an unseen test input by summing one (out of $p$) training input with output 1 and several inputs with output 0. By the template-matching principle, the correct output should be 1. Since only one of the $p$ positive-output inputs is matched, the remaining $p-1$ introduce unwanted correlations, which we refer to as conflicts.\n\nThe table below shows how the NTK predictor’s mean changes with increasing conflicts ($p-1$), reflecting violations of Assumption 5.1. As the number of conflicts grows, the mean drops and eventually reaches a point where the predictor’s sign fails to encode the correct output.\n\n| **Number of conflicts** | 1       | 20      | 40      | 60      | 80      | 90      |\n|-------------------------|---------|---------|---------|---------|---------|---------|\n| **NTK predictor mean**  | 0.36646 | 0.27907 | 0.18708 | 0.09508 | 0.00309 | -0.0429 |\n\n\n---\n\nOnce again, we sincerely thank the reviewer for taking the time to read our manuscript. We welcome any further questions or comments and hope that our clarifications are sufficient for the reviewer to consider raising their score.\n\n\n[1] György et al. (2025). Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence\n\n[2] Kumar et al. (2024). Grokking as the Transition from Lazy to Rich Training Dynamics. ICLR 2024"}, {"review_id": "DpHwBCf7X7", "reviewer": "Reviewer_MLRy", "summary": "The paper proves that NTK-trained networks can learn algorithms solvable by local template matching.", "questions": "- In the caption for Fig. 2, what do the authors mean by \"although the method is iterative, this example completes in one step\"? Also, can the authors clarify if template matching can only provide such iterative solutions?\n- Could the authors replot the two curves in each subplot of Fig. 5 such that they coincide? Also I'd like to know what the constant factors are in each case.\n- How does Turing completeness allow Assumption 5.1 to hold? \n- Since the experiments were done with finite-sized networks, do the authors have any insight for asymptotics on $n_h$ - the width of the network?", "limitations": "There are no important limitations that were not highlighted by the authors.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper presents a rigorous proof that NTK-trained neural networks can learn template matching with high probability.\n- The authors give several examples of algorithms that can be solved via template matching, and hence, prove exact learnability of such algorithms with NTK-trained models.\n\nWeaknesses:\n- The paper suffers from some notational ambiguity. For example, in Section 4 the block configuration is represented by $\\mathbf{x}$, but the dependence on the block $B_i$ is suppressed.", "was_revised": true, "final_justification": "The paper addresses my concerns, and I still recommend this paper to be accepted.", "rebuttal": "We sincerely thank the reviewer for their careful evaluation of our manuscript. We appreciate their recognition of the contributions of our work. Below, we respond to their insightful comments and questions.\n\n**Weaknesses:**\n\n> W1: The paper suffers from some notational ambiguity. For example, in Section 4 the block configuration is represented by x, but the dependence on the block B_i is suppressed\n\nWe thank the reviewer for highlighting this notational ambiguity. To improve clarity and readability, we omitted the dependence on the block $B_i$, as it can be inferred from the context. We will make this explicit in future versions of the manuscript.\n\n**Questions:**\n\n> Q1: In the caption for Fig. 2, what do the authors mean by \"although the method is iterative, this example completes in one step\"? \n\nUnder the template matching framework, our solution to the addition task typically requires at most $2\\ell$ iterations, where $\\ell$ refers to the number of bits. This represents a worst-case upper bound. However, some input samples may require fewer iterations. For instance, if no carry values need to be propagated to subsequent bits, the computation can be completed in a single pass. This is illustrated in Figure 2, which is why it can be completed in just one step, despite the iterative nature of the method. We apologize for any confusion and will revise the caption to improve clarity.\n\n> Q2: Can the authors clarify if template matching can only provide such iterative solutions?\n\nThe principle of template matching is highly versatile and, in some cases, can be applied in configurations that eliminate the need for iteration. The implications of this depend on the complexity of the problem. For instance, in simple tasks such as binary permutations (discussed in the paper), a single pass is sufficient. However, for more complex tasks, such as binary addition, removing the iterative component requires significantly more samples (potentially exponential in the input length) to achieve single-pass execution. Thus, the framework’s iterative nature is key to maintaining a small dataset size.\n\nAdditionally, the number of iterations is directly tied to the algorithm encoded in the instructions. In some cases, an alternative algorithm might reduce the required number of iterations.\n\nFinally, as previously noted, the iteration count may also vary depending on the samples being processed. If the focus is limited to a specific, simpler subset of samples, such as \"easy\" cases in binary addition, the iteration requirement might be relaxed or even eliminated.\n\n> Q3: Could the authors replot the two curves in each subplot of Fig. 5 such that they coincide? Also I'd like to know what the constant factors are in each case.\n\nAs requested, we plotted each theoretical estimate of the sample complexity, scaled by a factor $c$ to align the empirical and theoretical curves. Unfortunately, due to this year’s NeurIPS guidelines, authors are not permitted to include plots or external links in the response. For the three tasks shown in Fig. 5, we find that the curves have a mean relative error of less than 1% when the theoretical estimates are scaled by $c = 4.9$ for permutation, $c = 6.7$ for addition, and $c = 6.0$ for multiplication. We plan to include these results, along with the corresponding plots, in future versions of the paper.\n\n> Q4: How does Turing completeness allow Assumption 5.1 to hold?\n\nWe assume the reviewer is puzzled by the fact that, despite the rigidity of Assumption 5.1, our exact learning results generalize to computable functions. While Assumption 5.1 is rigid, it is important to clarify that our goal in learning SBN instructions is to learn the computations of a universal computer itself. To this end, we carefully designed a set of instructions such that the number of conflicts in each coordinate of the output (corresponding to the ratio in Assumption 5.1) remains constant. Once trained, the resulting model functions as a learned machine that can accept inputs encoding arbitrary computations, much like machine code. Therefore, to execute any computable function, the neural network must be provided with the corresponding machine code as input. In contrast, if we were to attempt to learn an arbitrary computable function directly (without an intermediate computational model like SBN acting as an interpreter) it is possible that, for certain computations, no set of instructions could satisfy Assumption 5.1.\n\n> Q5: Since the experiments were done with finite-sized networks, do the authors have any insight for asymptotics on - the width of the network?\n\nThe reviewer asks an important question regarding the convergence error as a function of the network's width. This pertains to the field of finite-width corrections in NTK theory, a topic with a rich literature of its own (see, for example, the survey [1]).\n\nIn this study, we intentionally focused on the infinite-width regime. This choice was strategic, as this setting provides the cleanest possible framework to convey our central message: that, under specific assumptions, neural networks are capable of learning to execute algorithmic instructions exactly. By eliminating the complexities of finite-width effects (e.g., dealing with higher-order kernels as defined in Section 3 of [1]), we can provide a clear proof of this principle.\n\nA thorough theoretical analysis of the finite-width case would be a significant research effort in its own right, one that we believe would warrant a separate, dedicated paper. We opted to prioritize the clarity and impact of our core message, but we agree that understanding these corrections might be a promising next step in this research direction.\n\n[1] Golikov et al. (2022). Neural Tangent Kernel: A Survey"}, {"review_id": "y085mJY8My", "reviewer": "Reviewer_eFhn", "summary": "This paper gives theoretical results showing that an MLP with 1 hidden layer can learn various bitwise algorithms, using the NTK infinite-width framing. The general idea is to partition the neurons into \"blocks\", each of which functions effectively as a memory slot, and to assume training examples which illustrate how each block transforms independently. Provided that those training examples are provided, and that there are not inter-block correlations, they show that various algorithms can be learned, given step-by-step examples of each block transformation, and with an acceptable sample complexity (logarithmic in the input space, so polynomial in the number of bits). They support their claims with numerical simulations.", "questions": "I am very confused by the claim that the results extend to arbitrary algorithms simply because SBN is Turing complete. It seems that your setup assumes a fixed amount of memory. How can it be Turing complete in that case?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. It's important to understand the computational abilities of neural networks, and while much past work has addressed what neural networks can represent, this work further addresses what is actually learnable\n2. The work appears rigorous, although I am not an expert in the relevant theoretical areas\n3. I found the work to be original and creative. \n\nWeaknesses:\n1. The empirical validation is explained well in the appendix, but given that the NeurIPS crowd has a more empirical leaning, it would be wise to migrate more of this discussion to the main text (for example, I wanted to know how many hidden nodes you use in order to approximate the \"infinite width\" limit)\n2. I'm not so sure about the Turing-completeness claim, see question", "was_revised": true, "final_justification": "The authors were upfront in the discussion about the memory limitations issues / extrapolation to bigger inputs and said they would discuss in revision.", "rebuttal": "We sincerely appreciate the reviewer’s time and effort in evaluating our manuscript. We are grateful for their recognition of the significance of our work. Below, we address their thoughtful and constructive comments.\n\n**Weaknesses:**\n\n> W1: The empirical validation is explained well in the appendix, but given that the NeurIPS crowd has a more empirical leaning, it would be wise to migrate more of this discussion to the main text (for example, I wanted to know how many hidden nodes you use in order to approximate the \"infinite width\" limit)\n\nWe appreciate the reviewer’s suggestion, which makes good sense. Due to the submission page limit, we had to restrict the main text and place some of the empirical details in the appendix. We agree that including more of this discussion in the main text would benefit readers, and we plan to do so in future versions of the paper.\n\n**Questions:**\n\n> Q1: I am very confused by the claim that the results extend to arbitrary algorithms simply because SBN is Turing complete. It seems that your setup assumes a fixed amount of memory. How can it be Turing complete in that case?\n\nThe reviewer raises a valid and important point, which we address below.\n\nIn any realization of a computational model, memory must be bounded in some way, just as physical computers have finite memory. However, the critical aspect of our exact learning framework is that it allows for arbitrarily large memory. That is, if a particular computation requires more memory, the input size and the number of instructions need to scale (in a trivial way) to accommodate the extra memory requirement. Importantly, our exact learning result demonstrates this remains learnable, even as the memory requirements grow."}]

Author rebuttal:

Meta-review: The paper presents a novel theoretical result showing that an ensemble of two-layer networks trained in the infinite-width limit can learn to compute four fundamental binary functions. The analysis relies on reduction of these tasks to local pattern matching and analysis of learnability in the NTK regime.

The reviewers appreciated the rigorous theory provided in the paper, as well as the NTK-analysis and the importance of the tasks studied in the paper. During the review process, some reviewers were concerned about clarity of the assumptions and the results. Reviewers also raised concerns on comparison to prior work. However, after discussion with the authors it seems that all reviewers were satisfied with the further clarification provided by the authors and agree that this paper should be accepted. I therefore decided to accept this paper.
Decision: Accept (poster)