Pith. sign in

REVIEW 3 major objections 5 minor 62 references

This paper proves that a graph neural network can be trained to execute graph algorithms exactly, without approximation error, from a small set of local binary instructions.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 06:10 UTC pith:OZN7PDCS

load-bearing objection Good LOCAL simulation construction; the NTK learnability step it rests on is unproved and looks wrong as stated. the 3 major comments →

arxiv 2601.23207 v2 pith:OZN7PDCS submitted 2026-01-30 cs.LG cs.AI

Learning to Execute Graph Algorithms Exactly with Graph Neural Networks

Muhammad Fetrat Qharabagh , Artur Back de Luca , George Giapitzakis , Kimon Fountoulakis This is my paper
classification cs.LG cs.AI MSC 68T07
keywords graph neural networksexact learnabilityalgorithmic reasoningNeural Tangent KernelLOCAL modeltemplate matchingmessage passingBellman-Ford
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper claims that a graph neural network (GNN) can be trained to execute graph algorithms exactly, not approximately. The recipe is to train an ensemble of simple multilayer perceptrons on binary "template" instructions describing one node's local update, then reuse that ensemble as the update function inside a message-passing GNN. Using neural tangent kernel theory, the authors argue that with a dataset whose size grows only linearly in the message/state size and quadratically in the maximum degree, the network's output, after a step-function binarization, matches the algorithm's true output at every iteration with arbitrarily high probability. If correct, this gives an exact learnability guarantee for the LOCAL model of distributed computation and for concrete algorithms such as message flooding, BFS, DFS, and Bellman-Ford, and it removes the error-compounding problem that plagues approximate neural execution.

Core claim

On its own terms, the paper's central discovery is that exact algorithmic execution does not require training on input-output pairs of the whole algorithm; it is enough to train on the algorithm's local step. More precisely, the main theorem (formalized in the appendix as Theorem D.7) states that for any graph of maximum degree D and any LOCAL-model algorithm A with bounded local memory and message size, there exists a training set of size scaling linearly with the local state and message sizes and quadratically with D such that the GNN of Equation (2), run for O(L) iterations, executes A exactly on every node, with failure probability driven to zero by increasing the ensemble size polynomia

What carries the argument

The load-bearing object is the graph template matching framework: each node's binary vector is split into computation and communication sections, and a local function f is defined by template-label pairs operating on disjoint blocks; the output is the bitwise OR of the labels of all matching templates. Communication is handled by D^2+1 slots keyed by a node's local ID, so aggregation does not corrupt bits. The GNN implements one iteration of this framework: the ensemble MLP with orthogonal block encoding and Heaviside binarization replaces f, and the mask matrices P_C and P_M, together with adjacency multiplication, implement local retention plus neighbor aggregation. The proof that the ense

Load-bearing premise

The guarantee hinges on an unproved inequality about how strongly matched training templates outvote unmatched ones in the infinite-width network predictor; if that sign separation fails, the exactness proof breaks, and the paper asserts this inequality via a padding trick rather than proving it.

What would settle it

Compute the limiting NTK predictor's output on the orthogonally encoded template inputs and check, for every output coordinate, whether the sign of the predictor agrees with ground truth whenever the collision count is below the asserted bound; a single coordinate where the ratio condition fails while collisions stay bounded would invalidate the key learnability lemma, and with it the main theorem.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any LOCAL-model algorithm with bounded degree and bounded per-node memory can be executed exactly by a GNN after training only on local step instructions.
  • For algorithms without global identifiers, such as message flooding, the same trained model works on graphs of arbitrary size, since the training set and feature dimension do not grow with node count.
  • For algorithms requiring global IDs, such as BFS, DFS, and Bellman-Ford, the guarantee holds for graphs up to 2^l nodes, where l is the bit precision used for identifiers.
  • Because every iteration is binarized before aggregation, one-step sign errors cannot compound across rounds; exactness is preserved for the full L-round execution.
  • The ensemble size needed is polynomial in the maximum degree and bit precision, giving an explicit, if large, resource bound for exact neural execution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same local-training, global-inference pattern could extend to attention-based or transformer architectures if a suitable blockwise encoding is found; the paper leaves this open.
  • The cascade-chain construction for avoiding template collisions is a general trick: replace many parallel writes to one bit by a sequential shift register. It likely applies beyond the four algorithms studied here.
  • The large gap between theoretical ensemble bounds and empirical accuracy suggests a tighter concentration analysis, avoiding the union bound over iterations, could substantially reduce the stated resource requirements.
  • A natural test beyond the paper's experiments is to run the exact NTK predictor on instruction sets where collision counts are deliberately pushed above the asserted bound and check whether execution fails exactly at the predicted threshold.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a two-stage framework for exact algorithmic execution with GNNs: local MLPs are trained on binary template-instructions via an NTK-type analysis, and the trained ensemble is inserted into a message-passing GNN with a Heaviside binarization and masking matrices. The main formal claim (Theorem 5.1 / D.7) is that this architecture can learn to execute any bounded-memory LOCAL-model algorithm on bounded-degree graphs, with explicit bounds on dataset size, embedding dimension, and ensemble size. Concrete instantiations are given for Message Flooding, BFS, DFS, and Bellman-Ford, with small-scale experiments on Message Flooding and NTK-based verification of the instruction sets.

Significance. If the learnability step were fully established, this would be a significant advance: it would convert expressive-power results for GNNs and the LOCAL model into exact, finite-sample learnability guarantees, with training data that do not grow with the graph size when global IDs are unnecessary. The constructive LOCAL-to-template-matching simulation, the dependence on degree rather than graph size, and the accompanying code and NTK verification are valuable and independently checkable parts of the paper. However, the decisive NTK sign-lemma is currently neither proved nor stated consistently, and the paper's own padding argument does not supply the missing condition. Since Theorems 5.1, D.7, and 6.1-6.4 all inherit this step, the central learnability claim is not established as written.

major comments (3)
  1. [Theorem D.5 / Eq. (2), D.4.2] The formal statement of Theorem D.5 says mu_i <= 0 when the ground-truth bit is set and mu_i > 0 when it is not set. With the Heaviside defined in Eq. (2) as Psi_H(x)=1[x>=0], this is exactly backwards: set bits would be mapped to 0 and unset bits to 1. The prose in D.4.2 clarifies the intended direction ('negative for a ground-truth zero bit and positive for a ground-truth bit equal to 1'), but the formal statement must be corrected. Because Theorem D.7 and Theorems 6.1-6.4 use this step without modification, the inconsistency is load-bearing, not cosmetic.
  2. [Lemma D.6 / Back de Luca et al. [2025]] The proof of Lemma D.6 is not self-contained: it invokes Theorem D.5 and the collision condition |W_j| < -w1(xhat)/w0(xhat), attributing the decisive NTK sign analysis to a same-group paper, Back de Luca et al. [2025], and does not prove the ratio inequality. The padding argument in the proof is also ineffective. Added 'never matched' inputs are block-orthogonal to all original training inputs and to every test input in the D.4.1 encoding; they add a block-diagonal Gram block and have zero kernel with the test point, so they do not change the NTK predictor or the effective weights w0,w1. Thus the claimed augmented dimension k' = (2|dom(delta)|-1)n_T and the feasibility of the collision bound are unsupported. This is the exact point where the learnability guarantee enters the proof.
  3. [D.4.1, Eq. (4), and Heaviside binarization] Even assuming the intended sign convention, the proof must establish that zero ground-truth coordinates receive a strictly negative pre-Heaviside value. For the block-orthonormal one-hot encoding and the ReLU NTK of Eq. (4), a direct computation of the Gram inverse in the normalized test setting gives an effective weight of zero for nonmatching samples, not a negative weight. Coordinates with no matching template writing 1 therefore receive value exactly 0, which Psi_H(t)=1[t>=0] maps to 1, producing wrong outputs. The paper's own C.3 treats non-positive values as failure, consistent with the need for strict negativity, but the theory as written does not deliver it. The authors must either prove strict negativity, change Psi_H to a strict inequality and prove that no exact zeros occur, or modify the encoding/loss.
minor comments (5)
  1. [Section 7 / Figure 3] The text calls the quantities 'theoretical and numerical lower bounds on the ensemble size,' but the theoretical expression is a sufficient ensemble-size bound (an upper-style guarantee), not a lower bound. Please reword.
  2. [Section C.1] The NTK evaluation verifies that the constructed instruction sets are correct for small graphs, but it does not validate the finite-width ensemble learning step. This should be stated explicitly to avoid overclaiming.
  3. [References] Two different works are cited as 'Back de Luca et al. [2025]' (the NeurIPS paper and the ICML paper). Please disambiguate them, especially in Section 2 and in the proof of Lemma D.6.
  4. [Theorems 6.1-6.4] The ensemble-complexity expressions contain typographical errors, e.g., Theorem 6.1 has an unmatched parenthesis in the logarithmic term. Please proofread the formulas.
  5. [Section E] For BFS, DFS, and Bellman-Ford, the statements 'the number of collisions is at most 5' / 'at most 4' are asserted without a detailed collision count analogous to the flooding case. A short table or explicit count would make the proofs checkable.

Circularity Check

1 steps flagged

The general LOCAL learnability result depends on an imported, unproved NTK sign lemma from the authors' own prior work; the decisive ratio condition is asserted rather than derived.

specific steps
  1. self citation load bearing [Appendix D.4.2, Lemma D.6 and proof of Theorem D.7]
    "The correctness of the lemma follows from Theorem D.5. ... Following Back de Luca et al. [2025], we observe that for every normalized input x̂, the ratio w1(x̂)/w0(x̂) is a decreasing function of N_x̂ and is strictly greater than 2·(|dom(δ)|−1) for N_x̂≤n_T."

    Theorem D.7's exact-execution guarantee is obtained by: Theorem D.7 -> Lemma D.6 -> Theorem D.5, where Theorem D.5 is cited as 'Back de Luca et al. [2025]' (three shared authors). The only bridge from template matching to exact GNN execution is Lemma D.6's assertion that the collision condition |W_j| < -w1/w0 holds after zero-label padding. This inequality is not proved in the paper; it is asserted by 'we observe' and attributed to the same self-cited work. Moreover, under the paper's own one-hot orthogonal encoding and ReLU NTK (Eq. 4), nonmatching orthogonal training samples contribute positive kernel weight, so w0 > 0 and -w1/w0 is negative, not a positive collision bound. Zero-label orthogonal padding does not change the NTK predictor. Thus the central learnability step reduces to an u

full rationale

The paper contains substantial independent content: the LOCAL-model-to-template-matching simulation (Lemma D.3) and the bit-level instruction sets for flooding, BFS, DFS, and Bellman-Ford are constructed in the paper and are checked by NTK-based experiments. There is no parameter fitting or renamed empirical fit. However, the step that converts template matching into an exact GNN execution is Theorem D.5 / Lemma D.6, explicitly imported from Back de Luca et al. [2025] with three of four authors shared with the present paper. Theorem D.7 relies directly on Lemma D.6, and Lemma D.6 relies on Theorem D.5 plus an asserted ratio inequality. The paper's formal Theorem D.5 is also internally inconsistent with the Heaviside convention Ψ_H(x)=1[x≥0]: it states µ(x̂)_i ≤ 0 when the ground-truth bit is set and µ(x̂)_i > 0 when it is not, the opposite of what the proof needs; only the later D.4.2 clarification restores the intended direction. Because the decisive sign-based learnability premise is not independently proved or machine-checked here, and the collision-ratio condition is asserted rather than derived, the general LOCAL learnability result is load-bearing on a self-citation. This warrants a score of 5: the framework and simulations have independent content, but the central 'exact execution with arbitrarily high probability' claim is not self-contained at its decisive step.

Axiom & Free-Parameter Ledger

0 free parameters · 8 axioms · 0 invented entities

The paper's claim is conditional on a chain of unproved-in-this-paper assumptions: the NTK learning theorems imported from the authors' prior work (Back de Luca et al. 2025), the infinite-width limit, exact arithmetic, and the LOCAL-model computational premise. The graph-template-matching framework and its correctness proof are given in the appendix, but the NTK sign lemma is not re-derived.

axioms (8)
  • standard math NTK predictor convergence: gradient-trained infinite-width two-layer MLPs are well-approximated by the NTK predictor/Gaussian process (Eqs. 4-7, Section B).
    Adopted from Lee et al. 2019 and used throughout the proof of Lemma D.6 and Theorems 6.1-6.4.
  • domain assumption Theorem D.5: sign-based information of the NTK predictor for template-matching functions under orthogonal encoding and the collision bound |W_j| < -w1/w0.
    Imported from Back de Luca et al. [2025], not proved in this manuscript; with the stated sign convention in the paper it is inconsistent with Psi_H, so the correct form is itself unverified.
  • domain assumption Ratio inequality w1(x_hat)/w0(x_hat) > 2(|dom(delta)|-1) for N_hatx <= n_T and decreasing, used to satisfy the collision condition after dataset padding.
    Asserted in Lemma D.6 by reference to Back de Luca et al. [2025]; no derivation is given in this paper.
  • domain assumption Ensemble concentration: averaging K independently initialized finite-width MLPs converges to the NTK predictor with high probability; ensemble complexity O(k' n_T + k' log(nL')).
    Taken as Lemma 6.1 of Back de Luca et al. [2025] and used to control the probability of exact execution.
  • domain assumption The LOCAL model's local computation step is Turing-computable and can be executed by a fixed local Turing machine with finite tape size m and time tau.
    Necessary for the LOCAL-model simulation in Section D.3; the theorem bounds depend on m and tau.
  • standard math Every graph of maximum degree D admits a 2-hop vertex coloring with D^2+1 colors, and each node knows its local ID.
    Greedy coloring bound stated in Section D.1; the framework requires unique local IDs within the 2-hop neighborhood.
  • domain assumption The GNN operates on the exact binary adjacency matrix A including self-loops, and message passing is over closed neighborhoods.
    Equation (2) and Model 2; the aggregation step requires that A F_node(X) P_M sums over N+_u.
  • domain assumption Infinite-width NTK regime and exact real arithmetic in activations and the Heaviside step (no floating-point rounding).
    Stated in the limitations; the theory is for infinite-width MLPs and exact sign comparisons, so finite-precision arithmetic is not covered.

pith-pipeline@v1.3.0-alltime-deepseek · 3903 in / 3576 out tokens · 203769 ms · 2026-08-03T06:10:22.601244+00:00 · methodology

0 comments
read the original abstract

Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact learnability results for graph algorithms under bounded-degree and finite-precision constraints. Our approach follows a two-step process. First, we train an ensemble of multi-layer perceptrons (MLPs) to execute the local instructions of a single node. Second, during inference, we use the trained MLP ensemble as the update function within a graph neural network (GNN). Leveraging Neural Tangent Kernel (NTK) theory, we show that local instructions can be learned from a small training set, enabling the complete graph algorithm to be executed during inference without error and with high probability. To illustrate the learning power of our setting, we establish a rigorous learnability result for the LOCAL model of distributed computation. We further demonstrate positive learnability results for widely studied algorithms such as message flooding, breadth-first and depth-first search, and Bellman-Ford.

Figures

Figures reproduced from arXiv: 2601.23207 by Artur Back de Luca, George Giapitzakis, Kimon Fountoulakis, Muhammad Fetrat Qharabagh.

Figure 1
Figure 1. Figure 1: Outline of our approach. During training (top), we train [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the template-matching framework on a two-node line graph: the left (blue) node [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Numerical and theoretical lower bounds on the ensemble size required for Message Flooding. Left: [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Impact of ensemble size (number of trained models) on Message Flooding accuracy as message size [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Accuracy on the ablation task for variants of Equation ( [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The figure shows the number of MLPs that need to be trained as the ensemble in the GNN [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Effect of collisions on the execution of Message Flooding on a star graph. The [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Tape layout for the LOCAL Turing machine (LTM). Each section has a fixed, predetermined size [PITH_FULL_IMAGE:figures/full_fig_p027_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The figure shows the structure of the binary input/output vector used for the simulation of [PITH_FULL_IMAGE:figures/full_fig_p030_9.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 10 linked inside Pith

  1. [1]

    Local and global properties in networks of processors

    Dana Angluin. Local and global properties in networks of processors. In ACM Symposium on Theory of Computing (STOC), 1980

    1980

  2. [2]

    Exploring length generalization in large language models

    Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. In Conference on Neural Information Processing Systems (NeurIPS), 2022

    2022

  3. [3]

    Simulation of graph algorithms with looped transformers

    Artur Back de Luca and Kimon Fountoulakis. Simulation of graph algorithms with looped transformers. In International Conference on Machine Learning (ICML), 2024

    2024

  4. [4]

    Learning to add, multiply, and execute algorithmic instructions exactly with neural networks

    Artur Back de Luca , George Giapitzakis, and Kimon Fountoulakis. Learning to add, multiply, and execute algorithmic instructions exactly with neural networks. In Conference on Neural Information Processing Systems (NeurIPS), 2025

    2025

  5. [5]

    Positional attention: Expressivity and learnability of algorithmic computation

    Artur Back de Luca, George Giapitzakis, Shenghao Yang, Petar Veli c kovi \'c , and Kimon Fountoulakis. Positional attention: Expressivity and learnability of algorithmic computation. In International Conference on Machine Learning (ICML), 2025

    2025

  6. [6]

    Neural algorithmic reasoning with causal regularisation

    Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, and Petar Veli c kovi\' c . Neural algorithmic reasoning with causal regularisation. In International Conference on Machine Learning (ICML), 2023

    2023

  7. [7]

    Combinatorial optimization and reasoning with graph neural networks

    Quentin Cappart, Didier Ch \'e telat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veli c kovi \'c . Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 2023

    2023

  8. [8]

    Arithmetic transformers can length-generalize in both operand length and count

    Hanseul Cho, Jaeyoung Cha, Srinadh Bhojanapalli, and Chulhee Yun. Arithmetic transformers can length-generalize in both operand length and count. In International Conference on Learning Representations (ICLR), 2025

    2025

  9. [9]

    Training verifiers to solve math word problems

    Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021

    Pith/arXiv arXiv 2021

  10. [10]

    DROP : A reading comprehension benchmark requiring discrete reasoning over paragraphs

    Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. DROP : A reading comprehension benchmark requiring discrete reasoning over paragraphs. In Conference of the North A merican Chapter of the Association for Computational Linguistics: Human Language Technologies , 2019

    2019

  11. [11]

    Faith and fate: Limits of transformers on compositionality

    Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers on compositionality. In Conference on Neural Information Processing Systems (NeurIPS), 2023

    2023

  12. [12]

    Parallel algorithms align with neural execution

    Valerie Engelmayer, Dobrik Georgiev, and Petar Veli c kovi \'c . Parallel algorithms align with neural execution. In Learning on Graphs Conference (LoG), 2023

    2023

  13. [13]

    Puzzles: A benchmark for neural algorithmic reasoning

    Benjamin Estermann, Luca A Lanzend \"o rfer, Yannick Niedermayr, and Roger Wattenhofer. Puzzles: A benchmark for neural algorithmic reasoning. In Conference on Neural Information Processing Systems (NeurIPS), 2024

    2024

  14. [14]

    Omni- MATH : A universal olympiad level mathematic benchmark for large language models

    Bofei Gao, Feifan Song, Zhe Yang, Zefan Cai, Yibo Miao, Qingxiu Dong, Lei Li, Chenghao Ma, Liang Chen, Runxin Xu, Zhengyang Tang, Benyou Wang, Daoguang Zan, Shanghaoran Quan, Ge Zhang, Lei Sha, Yichang Zhang, Xuancheng Ren, Tianyu Liu, and Baobao Chang. Omni- MATH : A universal olympiad level mathematic benchmark for large language models. In Internationa...

    2025

  15. [15]

    Lee, and Dimitris Papailiopoulos

    Angeliki Giannou, Shashank Rajput, Jy-Yong Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. In International Conference on Machine Learning (ICML), 2023

    2023

  16. [16]

    Neural tangent kernel: A survey

    Eugene Golikov, Eduard Pokonechnyy, and Vladimir Korviakov. Neural tangent kernel: A survey. arXiv preprint arXiv:2208.13614, 2022

    Pith/arXiv arXiv 2022

  17. [17]

    Neural turing machines

    Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014

    Pith/arXiv arXiv 2014

  18. [18]

    Measuring mathematical problem solving with the MATH dataset

    Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Conference on Neural Information Processing Systems (NeurIPS): Datasets and Benchmarks Track, 2021

    2021

  19. [19]

    ReLU neural networks of polynomial size for exact maximum flow computation

    Christoph Hertrich and Leon Sering. ReLU neural networks of polynomial size for exact maximum flow computation. Mathematical Programming, 2025

    2025

  20. [20]

    Provably good solutions to the knapsack problem via neural networks of bounded size

    Christoph Hertrich and Martin Skutella. Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS journal on computing, 2023

    2023

  21. [21]

    Combining label propagation and simple models out-performs graph neural networks

    Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations (ICLR), 2021

    2021

  22. [22]

    A generalist neural algorithmic learner

    Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, R \'o bert Csord \'a s, Andrew Joseph Dudzik, Matko Bo s njak, Alex Vitvitskyi, Yulia Rubanova, et al. A generalist neural algorithmic learner. In Learning on Graphs Conference (LoG), 2022

    2022

  23. [23]

    Neural tangent kernel: Convergence and generalization in neural networks

    Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Conference on Neural Information Processing Systems (NeurIPS), 2018

    2018

  24. [24]

    Length generalization in arithmetic transformers

    Samy Jelassi, Stéphane d'Ascoli, Carles Domingo-Enrich, Yuhuai Wu, Yuanzhi Li, and François Charton. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306.15400, 2023

    Pith/arXiv arXiv 2023

  25. [25]

    Junteng Jia and Austion R. Benson. Residual correlation in graph neural network regression. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2020

    2020

  26. [26]

    Inferring algorithmic patterns with stack-augmented recurrent nets

    Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Conference on Neural Information Processing Systems (NeurIPS), 2015

    2015

  27. [27]

    Neural GPU s learn algorithms

    Lukasz Kaiser and Ilya Sutskever. Neural GPU s learn algorithms. In International Conference on Learning Representations (ICLR), 2016

    2016

  28. [28]

    Wide neural networks of any depth evolve as linear models under gradient descent

    Jaehoon 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 Conference on Neural Information Processing Systems (NeurIPS), 2019

    2019

  29. [29]

    Teaching arithmetic to small transformers

    Nayoung Lee, Kartik Sreenivasan, \ Jason D.\ Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching arithmetic to small transformers. In International Conference on Learning Representations (ICLR), 2024

    2024

  30. [30]

    Locality in distributed graph algorithms

    Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 1992

    1992

  31. [31]

    Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang

    Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In International Conference on Learning Representations (ICLR), 2023

    2023

  32. [32]

    What graph neural networks cannot learn: depth vs width

    Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations (ICLR), 2020

    2020

  33. [33]

    Auto-regressive next-token predictors are universal learners

    Eran Malach. Auto-regressive next-token predictors are universal learners. arXiv preprint arXiv:2309.06979, 2023

    Pith/arXiv arXiv 2023

  34. [34]

    The CLRS -text algorithmic reasoning language benchmark

    Larisa Markeeva, Sean McLeish, Borja Ibarz, Wilfried Bounsi, Olga Kozlova, Alex Vitvitskyi, Charles Blundell, Tom Goldstein, Avi Schwarzschild, and Petar Veli c kovi \'c . The CLRS -text algorithmic reasoning language benchmark. arXiv preprint arXiv:2406.04229, 2024

    Pith/arXiv arXiv 2024

  35. [35]

    Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Geiping, Avi Schwarzschild, and Tom Goldstein

    Sean 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 Conference on Neural Information Processing Systems (NeurIPS), 2024

    2024

  36. [36]

    Aligning transformers with weisfeiler-leman

    Luis M\" u ller and Christopher Morris. Aligning transformers with weisfeiler-leman. In International Conference on Machine Learning (ICML), 2024

    2024

  37. [37]

    What can be computed locally? In ACM Symposium on Theory of Computing (STOC), 1993

    Moni Naor and Larry Stockmeyer. What can be computed locally? In ACM Symposium on Theory of Computing (STOC), 1993

    1993

  38. [38]

    Graph neural networks extrapolate out-of-distribution for shortest paths

    Robert R Nerem, Samantha Chen, Sanjoy Dasgupta, and Yusu Wang. Graph neural networks extrapolate out-of-distribution for shortest paths. arXiv preprint arXiv:2503.19173, 2025

    Pith/arXiv arXiv 2025

  39. [39]

    Investigating the limitations of transformers with simple arithmetic tasks

    Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102.13019, 2021

    Pith/arXiv arXiv 2021

  40. [40]

    Making transformers solve compositional tasks

    Santiago Onta \ n \'o n, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek. Making transformers solve compositional tasks. In Annual Meeting of the Association for Computational Linguistics, 2022

    2022

  41. [41]

    Attention is turing-complete

    Jorge P \'e rez, Pablo Barcel \'o , and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 2021

    2021

  42. [42]

    KNAR sack: Teaching neural algorithmic reasoners to solve pseudo-polynomial problems

    Stjepan Po z gaj, Dobrik Georgiev Georgiev, Marin S ili \'c , and Petar Veli c kovi \'c . KNAR sack: Teaching neural algorithmic reasoners to solve pseudo-polynomial problems. In Learning on Graphs Conference (LoG), 2025

    2025

  43. [43]

    Neural programmer-interpreters

    Scott Reed and Nando De Freitas. Neural programmer-interpreters. In International Conference on Learning Representations (ICLR), 2016

    2016

  44. [44]

    Discrete neural algorithmic reasoning

    Gleb Rodionov and Liudmila Prokhorenkova. Discrete neural algorithmic reasoning. In International Conference on Machine Learning (ICML), 2025

    2025

  45. [45]

    Transformers, parallel computation, and logarithmic depth

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. In International Conference on Machine Learning (ICML), 2024

    2024

  46. [46]

    Analysing mathematical reasoning abilities of neural models

    David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations (ICLR), 2019

    2019

  47. [47]

    On the computational power of neural nets

    Hava T Siegelmann and Eduardo D Sontag. On the computational power of neural nets. In Workshop on Computational learning theory, 1992

    1992

  48. [48]

    Towards scale-invariant graph-related problem solving by iterative homogeneous GNN s

    Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liang Lu, and Hao Su. Towards scale-invariant graph-related problem solving by iterative homogeneous GNN s. In Conference on Neural Information Processing Systems (NeurIPS), 2020

    2020

  49. [49]

    Neural arithmetic logic units

    Andrew Trask, Felix Hill, Scott E Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. In Conference on Neural Information Processing Systems (NeurIPS), 2018

    2018

  50. [50]

    The CLRS algorithmic reasoning benchmark

    Petar Veli c kovi \'c , Adri \`a Puigdom \`e nech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The CLRS algorithmic reasoning benchmark. In International Conference on Machine Learning (ICML), 2022

    2022

  51. [51]

    Neural execution of graph algorithms

    Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations (ICLR), 2020

    2020

  52. [52]

    Unifying graph convolutional neural networks and label propagation

    Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propagation. arXiv preprint arXiv:2002.06755, 2020

    Pith/arXiv arXiv 2002

  53. [53]

    Deep neural solver for math word problems

    Yan Wang, Xiaojiang Liu, and Shuming Shi. Deep neural solver for math word problems. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2017

    2017

  54. [54]

    Statistically meaningful approximation: a case study on approximating turing machines with transformers

    Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers. In Conference on Neural Information Processing Systems (NeurIPS), 2022

    2022

  55. [55]

    How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019

    2019

  56. [56]

    Neural execution engines: Learning to execute subroutines

    Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning to execute subroutines. In Conference on Neural Information Processing Systems (NeurIPS), 2020

    2020

  57. [57]

    Looped transformers are better at learning learning algorithms

    Liu Yang, Kangwook Lee, Robert D Nowak, and Dimitris Papailiopoulos. Looped transformers are better at learning learning algorithms. In International Conference on Learning Representations (ICLR), 2024

    2024

  58. [58]

    Learning to execute

    Wojciech Zaremba and Ilya Sutskever. Learning to execute. arXiv preprint arXiv:1410.4615, 2014

    Pith/arXiv arXiv 2014

  59. [59]

    Susskind, Samy Bengio, and Preetum Nakkiran

    Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? A study in length generalization. In International Conference on Learning Representations (ICLR), 2024

    2024

  60. [60]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should not add it explicitly Type <Return> for now, but then later remove the command n...

  61. [61]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@first@sw \@firstoftwo \@ifundefined NAT@b*@#2 \@firstoftwo @num @NAT@ctr \@secondoft...

  62. [62]

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibsetup #1 @NAT@ctr @ @openbib .11em \@plus.33em \@minus.07em 4000 4000 `\.\@m @bibit...