Discrete Neural Algorithmic Reasoning
Authors: Gleb Rodionov
Liudmila Prokhorenkova
Venue: ICML 2025 poster (2025)
Keywords: neural algorithmic reasoning
graph neural networks
Primary area: deep_learning->graph_neural_networks
TL;DR: We achieve perfect neural execution of several algorithms with provable correctness by separating discrete and continuous computation flows, then supervising state transitions to match classical algorithms.

Abstract: Neural algorithmic reasoning aims to capture computations with neural networks by training models to imitate the execution of classical algorithms. While common architectures are expressive enough to contain the correct model in the weight space, current neural reasoners struggle to generalize well on out-of-distribution data. On the other hand, classical computations are not affected by distributional shifts as they can be described as transitions between discrete computational states. In this work, we propose to force neural reasoners to maintain the execution trajectory as a combination of finite predefined states. To achieve this, we separate discrete and continuous data flows and describe the interaction between them. Trained with supervision on the algorithm's state transitions, such models are able to perfectly align with the original algorithm. To show this, we evaluate our approach on multiple algorithmic problems and achieve perfect test scores both in single-task and multitask setups. Moreover, the proposed architectural choice allows us to prove the correctness of the learned algorithms for any test data.

Discrete Neural Algorithmic Reasoning
Gleb Rodionov' Liudmila Prokhorenkova' 2
Abstract
cal guarantees of algorithms to work correctly on any input of any size and distribution, this setting provides unlimited challenges for out-of-distribution generalization of neural networks. Prior work explored this setup using the CLRS-30 benchmark (Veličković al., 2022), which covers classical algorithms from the Introduction to Algorithms textbook (Cormen et al., 2009) and uses graphs as a universal tool to encode data of various types. Importantly, CLRS-30 also provides the decomposition of classical algorithms into subroutines and simple transitions between consecutive exe- cution steps, called hints, which can be used during training in various forms.
Neural algorithmic reasoning aims to capture computations with neural networks by training models to imitate the execution of classical al- gorithms. While common architectures are ex- pressive enough to contain the correct model in the weight space, current neural reasoners strug- gle to generalize well on out-of-dise of-distribution data. On the other hand, classical computations are not affected by distributional shifts as they can be described as transitions between discrete com- putational states. In this work, we propose to force neural reasoners to maintain the execution trajectory a combination of finite predefined states. To achieve this, we separate discrete and continuous data flows and describe the interac- tion between them. Trained with supervision on the algorithm's state transitions, such models are able to perfectly align with the original algorithm. To show this, we evaluate our approach on multi- ple algorithmic problems and achieve perfect test scores both in single-task and multitask setups. Moreover, the proposed architectural choice al- lows us to prove the correctness of the learned algorithms for any test data.
The core idea of the CLRS-30 benchmark is to understand how neural reasoners generalize well beyond the training distribution, namely on larger graphs. Classical algorithms possess strong generalization due to the guarantee that cor- rect execution steps never encounter states, all state transitions predefined by the algo- rithm. In contrast, when encountering inputs from distribu- tions that significantly differ from the training data, neural networks are usually not capable of robustly maintaining internal calculations the desired domain. Consequently, due to the complexity and diversity of all possible data that neural reasoners can be tested on, the generalization perfor- mance of such models may vary depending on particular test distributions (Mahdavi et al., 2023). Given that, it is becoming important to interpret internal computations of neural reasoners to find errors or to prove the correctness of the learned algorithms (Georgiev et al., 2022).
1. Introduction
Learning to capture algorithmic dependencies in data and to perform algorithmic-like computations with neural networks is a core problem in machine learning, long studied using various approaches (Khardon & Roth, 1997; Graves et al., 2014; Zaremba & Sutskever, 2014; Reed & De Freitas, 2015; Kaiser & Sutskever, 2015; Veličković et al., 2020b).
Interpretation methods have been actively developing re- cently due various real-world applications of neural net- works and the need debug and maintain systems based them. Especially, the Transformer architecture (Vaswani et al., 2017) demonstrates state-of-ther oftt---rttt--tttt performance in natural language processing and other modalities, represent- ing a field for the development of interpretability methods (Elhage et al., 2021; Weiss et al., 2021: Zhou et al., 2024; Lindner et al., 2023). Based on active research on a compu- tational model behind the transformer architecture, recent works propose way learn models that are fully inter- pretable by design (Friedman et al., 2023).
Neural algorithmic reasoning (Veličković Blundell, 2021) is research area focusing building models capable of executing classical algorithms. Relying on strong theoreti-
'Yandex Research, Moscow, Russia Yandexx Research, Am- sterdam, The Netherlands. Correspondence to: Gleb Rodionov <rodionovglebe yandex-tcam.nux team.ru>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We found the ability to design models that are interpretable in a simple and formalized way to be crucial for neural

---

Discrete Neural Algorithmic Reasoning
algorithmic reasoning as it is naturally related the goal of learning to perform computations with neural networks.
manipulations over such inputs. Also, GNNs are proven to be well-suited for neural execution (Xu al., 2020; Dudzik & Veličković, 2022).
In this paper, we propose to force neural reasoners to follow the execution trajectory as combination of finite predefined states, which important for both generalization ability and interpretability of neural reasoners. To achieve that, we start with an attention- based neural network and describe three building blocks enhance its generalization abilities: feature discretization, hard attention, and the separation of discrete and continuous data flows. In short, all mentioned blocks are connected:
The CLRS-30 benchmark covers different algorithms over various domains (arrays, strings, graphs) and formulates them as algorithms over graphs. Additionally, CLRS-30 proposes utilizing the decomposition of the algorithmic tra- jectory exccution into simple logical steps, called hints. Us- ing this decomposition is expected to better align the model to desired computations and prevent it from utilizing hid- den non-generalizable dependencies of a particular train set. Prior work demonstrates a wide variety of additional inductive biases for models towards generalizing computa- tions, including different forms of hint usage (Veličković et al., 2022; Bevilacqua al., 2023), biases from standard data structures (Jain et al., 2023; Jürß et al., 2024), knowl- edge transfer and multitasking (Xhonneux et al., 2021; Ibarz et al., 2022; Numeroso et al., 2023). Also, recent studies demonstrate several benefits of learning neural reasoners end-to-end without any hints at all (Mahdavi et al., 2023; Rodionov & Prokhorenkova, 2023).
State discretization does not allow the model to use complex and redundant dependencies in data;
Hard attention is needed to ensure that attention weights will not be annealed for larger graphs and to limit the set of possible messages that each node can receive;
Separating discrete and continuous flows is needed to ensure that state discretization does not lose informa- tion about continuous data.
The recently proposed SALSA-CLES benchmark (Minder et al., 2023) enables more thorough out-of-distribution (OOD) evaluation compared to CLRS-30 with increased test sizes (up to 100-fold train-to-test scaling, compared to 4-fold for CLRS-30) and diverse test distributions.
Then, we build fully discrete neural reasoners for different algorithmic tasks and demonstrate their ability to perfectly mimic ground-truth algorithm execution. As result, we achieve perfect test scores on multiple algorithmic tasks with guarantees of correctness on any test data. Moreover, we demonstrate that a single network is capable of executing all covered algorithms in a multitask setting, also achieving perfect generalization.
Despite significant gains in the performance of neural rea- soners in recent work, current models still struggle to gen- eralize to OOD test data (Mahdavi et al., 2023; Georgiev et al., 2023; Minder et al., 2023). While de Luca & Foun- toulakis (2024) prove by construction the ability of the crunsoorme--bssee neural reasoners to perfectly simulate graph algorithms (with minor limitations arising from the finite precision), is still unclear if generalizable and inter- pretable models can be obtained via learning. Importantly, the issues of OOD generalization are induced not only by the challenges of capturing the algorithmic dependencies in the data but also by the need to carefully operate with continuous inputs. For example, investigating the simplest scenario of learning to emulate the addition of real num- bers, Klindt (2023) demonstrates the failure of some models to exactly imitate the desired computations due to the na- ture of gradient-based optimization. This limitation can significantly affect the performance of neural reasoners adversarial examples and larger input instances when small errors can be accumulated.
In summary, we consider the proposed blocks crucial com- ponents for robust and interpretable neural reasoners and demonstrate that discretized models, trained with hint su- pervision, perfectly capture the dynamics of the underlying algorithms and do not suffer from distributional shifts.
2. Background
2.1. Algorithmic Reasoning
Performing algorithmic-like computations usually requires the execution of sequential steps and the number of such steps depends on the input size. To imitate such computa- tions, neural networks are expected to be based on some form of recurrent unit, which can be applied to a particular problem instance several times (Zaremba & Sutskever, 2014; Kaiser & Sutskever, 2015; Vinyals al., 2015; Veličković et al., 2020b).
2.2. Transformer Interpretability and Computation Model
The CLRS Algorithmic Reasoning Benchmark (CLRS-30) (Veličković et al., 2022) defines a general paradigm of algo- rithmic modeling based on Graph Neural Networks (GNNs), as graphs can naturally represent different input types and
Transformer (Vaswani et al., 2017) is a neural network ar- chitecture for processing sequential data. The input to the transformer is a sequence of tokens from a discrete vocabu-
2

---

Discrete Neural Algorithmic Reasoning
lary. The input layer maps each token to high-dimensional embedding and aggregates it with the positional encoding. The key components of each layer are attention blocks and MLP with residual connections. Providing a detailed de- scription of mechanisms learned by transformer models (El- hage et al., 2021) is of great interest due to their widespread applications.
defined by the task (for graph problems) or on the fully connected graph. For the latter option, the information about the original graph can be encoded into the edge features.
The number of processor steps T can be defined automat- ically by the processor or externally (e.g., as the number of steps of the original algorithm). After the last step, the node and edge features are mapped with another linear layer, called the decoder, to the output predictions of the model.
RASP (Weiss et al., 2021) is a programming language pro- posed high-level formalization of the computational model behind transformers. The main primitives of RASP are elementwise sequence functions, select and aggregate operations, which conceptually relate to computations per- formed by different blocks of the model. Later, Lindner et al. (2023) presented Tracr, a compiler for converting RASP pro- grams the weights of the transformer model, which can be useful for evaluating interpretability methods.
If the model is trained with hint supervision, the changes of node and edge features at each step are expected to be related to the original algorithm execution. In this sense, the processor network aims to mimic the algorithm's 's execution in the latent space.
3.2. Discrete Neural Algorithmic Reasoners
While RASP might have limited expressibility, it supports ar- bitrarily complex continuous functions that in theory can be represented by the transformer architecture, but are difficult to learn. Also, RASP is designed to formalize computa- tions over sequences of fixed length. Motivated by that, Zhou et al. (2024) proposed RASP-L, restricted version of RASP, which aims to formalize the computations that are easy to learn with transformers in size-genn gerereenral way. The authors also conjecture that the geggghhgnnraliitiionn of transformers on algorithmic problems is related to the 'sim- plicity' of solving these problems in the RASP-L language.
In this section, we describe the constraints for the processor that allow us to achieve a fully interpretable neural reasoner. We start with Transformer Convolution (Shi et al., 2020) with a single attention head.
As mentioned above, at each computation step / (1 <IS T), the processor takes the nigh-dimensional embedding vectors for node and edge features as inputs and then outputs the representations for the next execution step.
Each node feature vector 2; is projected into query (Qt), key (K:), and value (V:) vectors via learnable parameter matrices WQ. WK, and Wv, respectively. Edge features Gij are projected into key (Kiz) vector with a matrix W K Then, for each directed edge from node j to a node in the graph G, we compute the attention coefficient
Another recent work (Friedman et al., 2023) describes Trans- former Programs: constrained transformers that can be trained using gradient-based optimization and then automat- ically converted into a discrete, human-readable program. Built on RASP, transformer programs are not designed to be size-invariant.
aij = (Q), K₁ Kaa)
Vh
where (a, 6) denotes the dot product. Then, each node i normalizes all attention coefficients across its neighbors using the softmax function with temperature r and receives the aggregated message:
3. Discrete Neural Algorithmic Reasoning 3.1. Encodd--rroces--Decnde Paradigm
Our work follows the mncode-rooces-decodd paradigm (Hamrick et al., 2018), which is usually employed for step- by-step neural execution.
exp(aug/T)
ā.j" E EKENC exp(a.t/T)*
M, =
Σ de VR, (1)
REV(1)
All input data is represented as a graph G with an adjacency matrix A and node and edge features that are first mapped with a simple linear encoder to high-dimensional vectors of size h. Let us denote node features at a time step (1 < t < T) as X = (ai,..., ²x,) and edge features E. = (et..... ......,. ). Then, the processor, usually a single- layer GNN, recurrently updates these features, producing node and edge features for the next step:
where Ni)) denotes the set of all incoming neighbors of the node and M, is the message sent to the i-th node.
For undirected graphs, we consider two separate edges in each direction. Also, for each node, we consider a self-loop connecting the node to itself. For multi-head attention, each head / separately computes the messages M, which are then concatenated.
x E++ Processor(X*) X", E A).
Similar to Transformer Programs, we enforce attention to be hard attention. We found this property important not only for interpretability but also for size generalization, as
The processor network can operate on the original graph
3

---

Discrete Neural Algorithmic Reasoning
hard attention allows to overcome the annealing of the attention weights for arbitrarily large graphs and strietly limit the set of messages that each node can receive.
Discrete states
Scalare
After the message computation, node and edge features are updated depending on the current values and received messages using feed-forward MLP blocks:
Feed Forward
at+1 FFN nodes (1rf M()), .++ FFNedgee ( (ley Ces dry VzD).
Message Passing
We also enforce all node and edge features be from fixed finite set, which we call states. We ensure this property by adding discrete bottlenecks at the end of the processor block:
Discrete states
Scalars
Discretizenodes (#f (1
[+1 Discrelizeeagess (e)+1).
Figure 1. An illustration of the proposed separation between dis- crete and continuous data flows. Scalars can only affect the at- tention weights (Green) and can be modified with actions via Scalar Update (Blue).
We implement discretization by projecting the features into vectors of size & (states logits) which we then use to produce a one-hot vector corresponding to a discrete state. During training with hints, we use teacher forcing and directly use ground-truth states as inputs for the next processor step. For no-hint learning, we apply Gumbel-Softmax (Jang et al., 2017) with annealing temperature to the states logits. During inference, we simply use the argmax function over the states logits dimension.
and node indexes), we use multi- head attention, where each head operates with separate scalars.
Thus, the interface of the proposed processor can be de- scribed as
3.3. Continuous Inputs
X++1 E Processor poncesssorX'..5 (',E',,,, A,S).
Clearly, most algorithmic problems operate with continu- ous or unbounded inputs (e.g.. weights on edges). Usually, all input data is encoded into node and edge features and the processor operates over the resulting vectors. The pro- posed discretization of such vectors would lead to the loss of information necessary for performing correct execution steps. To handle such inputs (which we will call sealars re- ferring to both continuous and size-dependent integer inputs such as node indexes) one option is to use Neural Execu- tion Engines (Yan et al., 2020) that enable operating with bit-wise representations of integer and (in theory) real num- bers. Such representations are bounded by design, but fully discrete and interpretable.
where X X ('+++ and E E are from fixed sets. State sets are independent of the execution step i and the input graph (including scalar inputs S).
3.4. Manipulations over Continuous Inputs
The proposed selector offers a read-only interface to scalar inputs, which is not expressive enough for most algorithms. However, we note that the algorithms can be described as discrete manipulations over input data. For example, the Dijkstra algorithm (Dijkstra, 1959) takes edge weights as inputs and uses them to find the shortest path distances. Computed distances can affect the subsequent execution steps. We note that such distances can be described as the sum of the weights of the edges that form the shortest path to the given node. other words, the produced scalars depend only on input scalars and discrete execution states.
We propose another option: to maintain scalar inputs (denote them by SS) separately from the node and edge features and use them only as edge priorities Sij in the attention block. If scalars are related to the nodes, we assign them to edges depending on the scalar of the sender or receiver node. We implement this simply by augmenting the key vectors Kij of each edge with the indicator of whether the given edge has the "best" (min or max) scalar among the other edges to node j with the same discrete state. Thus, scalars affect only the attention weights, not the messages or the node states.
To avoid the challenges of learning continuous updates with high precision (Klindt, 2023), we propose to learn discrete manipulations with scalars. The updated scalars can then be used with the described selector in the next steps.
In our experiments, we use a scalar updater capable of incre- menting, moving, and adding scalars depending on discrete
For multiple different scalar inputs (e.g., weighted edges
4

---

Discrete Neural Algorithmic Reasoning
node/edge states:
4.1. Datasets
We perform our experiments on the problems from the re- cently proposed SALSA-CLRS benchmark (Minder et al., 2023), namely BFS, DFS, Prim. Dijkstra, Maximum Inde- pendent Set (MIS), and Eccentricity. We believe that the proposed method is not limited to the covered problems, but we leave the implementation of the required data flows (c.g.. edge-based reasoning (Ibarz et al., 2022), graph-level hints, interactions between different scalars) for future work.
st = inc(af) + keep(z)) sf +
Σ push(ejp) sfj
(EN(()
" = inc(ely) keep(e),) oig + push(z;) s
(2)
where 8; are node-related scalars, Aiy are edge-related scalars, and inc, keep, push are 0-1 functions representing whether a scalar each node/edge should be incremented, kept, or pushed to any of its neighbors. We implement these functions simple linear projections of node/edge features with subsequent discretization.
The train dataset of SALSA-CIRS consists of random graphs with at most 16 nodes sampled from the Erdös- Erdös-Rényi Rényi (ER) distribution with parameter chosen to be as low as possible such that graphs remain connected with high prob- ability. The test set consists of sparse graphs of sizes from 16 to 1600 nodes.
Finally, our proposed method (see Figure 1) can be de- scribed as:
X++1 F Processor(X* F. F
We slightly modify the hints from the benchmark without conceptual changes (e.g., have modified the hints for the DFS problem to remove graph-level hints and node dis- covery/finish times). Our discrete states are defined by the benchmark's non-scalar hints, while our scalars are exactly the hints of the scalar type (see Veličković et al. (2022) for details on hint design).
8t+1 ScalarUpdale( X A,
The proposed neural reasoners are fully discrete and can be interpreted by design. Moreover, the proposed selec- tor block guarantees predictable behavior of the message passing across all graph sizes, as it compares discrete state importance and uses continuous scalars only to break ties between equally important states.
4.2. Baselines and Evaluation
We compare the performance of our proposed discrete model with two baseline sparse models, GIN (Xu al., 2019) and Pointer Graph Network (Veličković et al., 2020a). We report both node-level and graph-level metrics for the baselines and our model. Graph-level metrics measure the proportion of test graphs for which all node-level outputs are predicted correctly. For example, for the BFS problem, the output of the algorithm a tree, where each node points to its parent in the BFS exploration tree (and the starting node points to itself). Pointer is specific hint/output type which forces each node to point to exactly one node.
4. Experiments
In this section, we perform experiments to evaluate how the proposed discretization affects the performance of neural reasoners on diverse algorithmic reasoning tasks. Our main questions are:
1. Can the proposed discrete neural reasoners capture the desired algorithmic dynamics with hint supervision?
2. How does discretization affect OOD and size- generalization performance of neural reasoners?
Additionally, we compare our model with Triplet-GMPNN (Ibarz et al., 2022) and two recent approaches, namely Hint-ReLIC (Bevilacqua et al., 2023) and G-ForgetNet (Bo- hde et al., 2024), which demonstrate state-of oof-the-art perfor- mance in hint-based neural algorithmic reasoning. However, as these methods are evaluated on the CLRS-30 benchmark and their code is not yet publicly available, we only com- pare them on the corresponding tasks (BFS, DFS. Dijkstra, Prim) and the CLRS-30 test data, namely ER graphs with = 0.5 of size 64. Note that this test data is denser than that of SALSA-CLRS, meaning shorter roll-outs for the given tasks. Furthermore, only node-level metrics have been reported for these methods.
3. Is the proposed model capable of multi-task learning?
Additionally, are interested in whether discrete neural reasoners can be learned without hints and how they tend to utilize the given number of node and edge states to solve the problem. We discuss no-hint experiments separately in Section 6.
Finally, we investigate whether graph sizes in the train set can be reduced without compromising generalization per-
formance; see Appendix B for details.
We additionally investigate if the operation set can be ex- tended, see Appendix
5

---

Discrete Neural Algorithmic Reasoning
4.3. Model Details
Table I. Node/graph-level test scores for the proposed discrete reasoner and the baselines on SALSA-CLRS test data. Scores are averaged across different seeds; standard deviation is omit- ted. For the eccentricity problem, only the graph-level metric is applicable.
For our experiments, we use the model described in Sec- tion 3. We use one attention head for each scalar value. The number of processor steps is set to the length of the ground- truth algorithm trajectory, which is consistent with prior work. We use one architecture (except the task-dependent cncoders/deecoders), including the Scalar Update module, for all the problems.
TASK
SIZF
GIN
PGN
DNAR (OURS)
BFS
16
98.8 / 92.5
100. / 100.
100. / 100.
80
9
9 88.1
100. 100.
160
95.1/37.
99.6 / 66.3
100. 100.
We recall that neural reasoners can operate either on the orig- inal graph (which is defined by the problem) or on denser graphs with the original graph encoded into edge features. SALSA-CLRS proposes to enhance the size- serereeeealliziionn abilities of neural reasoners with increased test sizes (up to 100-fold train-to-test scaling), so we use the original graph for wesssag--pssing similar to the SALSA-CLRS baselines. We also add a virtual node that communicates with all nodes of the graph.
800
8..9/0.9
9.2
100. / 100.
1600
8.05
9 0.0
100. / 100.
DFS
16
41.5
82.0/ 19.9
100. / 100.
80
3..4/0.0
38,4/0.0
100. / 100.
160
20.0/0.0
26.9
100. 100.
800
19.5
2..9/0.0
100. / 100.
1600
17.8/0.0
23.1
100. / 100.
SP
16
95.2/49.8
99.3 89.5
100. / 100.
80
62.4/0.0
9..2/3.3
100. / 100.
160
53.3/0.0
92.0
100. / 100.
800
40.4/0.0
87.1/0.0
100. / 100.
4.4. Training Details and Hyperparameters
1600
36.9/0.0
8..5
100. / 100.
We train each model for 1000 optimization steps using the Adam optimizer with learning rate of v) = 0.001 and batch size of 32 graphs; teacher forcing is applied through- out training. For the discrete bottlenecks (attention weights and Scalar Update operations), we anneal the softmax tem- perature geometrically from 3.0 to 0.01, decreasing it at each training step. A complete list of all hyperparameters is provided in our source code.
PRIM
16
89.6/29.7
96.4
100. / 100.
80
51.6/0.0
79.7
100. 100.
160
49.5/0.0
7..
100. 100.
800
4..0/0.0
0.0
100. 100.
1600
/3.2
66.8/ 0.0
100. 100.
MIS
16
7..9/3.3
99.8 /
100. / 100.
80
/
99.4 / 88.9
100. 100.
160
78.2/0.0
99.4 / 76.2
100. 100.
800
0.0
98.8 / 18.0
100. 100.
1600
7.0
98.9 / 5.2
100. 100.
During training, we minimize the standard hint and out- put losses: scalar hints are optimized with the MSE loss, and the other types of hints are optimized with the cross- entropy and categorized cross-entropy losses (Veličković et al., 2022; Ibarz et al., 2022). Notably, we do not supervise any additional details in model behavior, such as selecting the most important neighbor in the attention block or the exact operations with scalars.
Ecc.
16
NA 25.3
NA / 100.
NA / 100.
80
NA / 23.8
NA / 100.
NA/ / 100.
160
NA 26.1
NA 100.
NA / 100.
800
NA / 17.1
NA / 100.
NA / 100.
1600
NA / 16.0
NA 83.0
NA / 100.
form the exact transitions between the states. Trained with step-wise hint supervision, discrete neural reasoners are able to perfectly align with the original algorithm and generalize larger test data without any performance loss. We report the evaluation results in Tables and 2. Also, our multitask experiments show that the proposed discrete models are capable of multitask learning and demonstrate the perfect generalization scores in a multitask manner too.
For multitask experiments, we adopt the setup from Ibarz et al. (2022) and train single processor with task-dependent encoders/decoders to imitate all covered algorithms simulta- neously. We make 10000 optimization steps on the accumu- lated gradients across each task and keep all hyperparame- ters the same as in the single task.
Our models are trained a single A100 GPU, requiring less than 1 hour for single-task and 5-6 hours for multitask training.
Recall that we have three key components of our contribu- tion: feature discretization, hard attention, and separating discrete and continuous data flows. To evaluate the impor- tance of each component for generalization capabilities of the proposed models, we conduct an ablation study; the details can be found in Appendix A. In short, we demon- strate that removing each of these components yields the model without provable guarantees of perfect generalization. However, these components differ in terms of the impac
4.5. Results
We found learning with teacher forcing suitable for discrete neural reasoners, as discretization blocks allow us to per-
phttps://gf www.hhcw..aaaeeeeoccooo.tt www/yaadee-oeeo///oo/ooocc wewendexxxeeeeeeee maasercch/daa
6

---

Discrete Neural Algorithmic Reasoning
by manually verifying state transitions. As result, we con- firm that the attention block indeed operates select best selector, as the model actually uses these indicators to in- crease the attention weights. Thus, we can guarantee that for any graph size, the model will mirror the desired algorithm, which is correct for any test size.
Table 2. Node-level test. scores for the proposed discrete reasoner and the baselines on CLRS-30 test data. Test graphs are of size 64. Scores are averaged across 5 different seeds.
TASK
HINT-RELIC
G-FORGETNET
DNAR (OURS)
BFS
99.00 + 0.2
99.96 = 0.0
100. + 0.0
DFS
100. 0.0
74.31 = 5.0
100. = 0.0
SP
97.74
0.5
99.14 0.1
100. = 0.0
6. Towards No-Hint Discrete Reasoners
PRIM
87.97 + 2.9
95.19 + 0.3
100. 0.0
In this section, we discuss the challenges of training discrete reasoners without hints, which can be useful when tackling new algorithmic problems.
on the performance. In particular, using regular attention instead of hard attention yields perfect test scores for given datasets, but it is possible to construct adversarial examples with large neighborhood sizes where performance drops. On the other hand, removing discretization from the scalar updater significantly affects the performance even on the small test graphs.
Training deep discretized models is known to be challenging (Mahdavi et al., 2023). We observe that without hyperpa- rameter search, discrete models are only slightly improved over the untrained models. Therefore, we focus only on the BFS algorithm, as it is well-aligned with the message- passing framework, has short roll-outs, and can be solved with a small number of states (note that for no-hint mod- els node/edge state count is a hyperparameter due to the absence of the ground-truth states trajectory).
5. Interpetability and Testing
In addition to the empirical evaluation of the trained mod- els on diverse test data, the discrete and bizeinndepnndent design of the proposed models allows us to interpret and test them manually. Namely, we can validate that the model will perform the exact discrete state transitions (including discrete operations with scalars) as the original algorithm.
We recall that the output of the BFS problem is the explo- ration tree pointing from each node to its parent. Each node chooses as parent the neighbor from the previous distance layer with the smallest index.
We perform hyperparameter search over graph sizes in the train set (using ER graphs with p = 0.5 and n E [4, 16), discrete node state count (from
First, due to the hard attention, each node receives exactly one message. Also, the message depends only on the dis- crete states of the corresponding nodes and edges. Thus, node and edge states after single processor step depend only on the current states and the received message. There- fore, all the possible options can be directly enumerated to test if all states change to the correct ones.
states). softmax tem- perature annealing schedules ([3, 0.01], [3, 0.1], [3. 1)) For each hyperparameter choice, train 5 models with differ- ent seeds. We validate the resulting models on the graphs of size 16. The best resulting model is obtained with the graph size n = 5 and 4 node states. The trained models never achieved perfect validation scores (see Table for the results).
The final component to fully interpret the whole model is the attention block. We note that our implementation simply augments the key vectors with the indicators of whether the given edge has the best scalar among others. For ex- ample, it may happen that for some state, the maximum attention weight is achieved for an edge without the indi- cator. However, given the finite number of discrete states, we can manually check the unnormalized attention scores between each pair of states both with this indicator and with- out it. Combined with hard attention, this would imply that the attention block attends to nodes based on their prede- fined states and uses scalar priorities only to break ties. A particular example with more detailed explanation for the BFS problem can be found in Appendix D.
Table 3, BFS node/graph scores of the best no himt model for different graph sizes.
16
64
best no hint model
99 86
94 / 34
79 0
Then, we select the best-performing models and try to ana- lyze the errors of the resulting models and reverse-engineer how they utilize the given states. First, we look at the node states after the last step of the processor and note that the states correspond to the distances from the starting node. More formally, we note that the model with four states uses the first state for the starting node, the second state for its neighbors, the third state for nodes at distance two from the starting node, and the last state for all other nodes. Such baste classification of distance has ac-
Given that, we can unit-test all possible state transitions and attention blocks. With full coverage of such tests, we can guarantee the correct execution of the desired algorithm for any test data. We tested our trained models from Section 4
7

---

Discrete Neural Algorithmic Reasoning
euracy 98% when tested on 1000 random graphs with 16 nodes. We observe that for the nodes that belong to the first four distance layers from the starting node, the pointers are predicted with 100% accuracy and these pointers are computed layer-by-layer as in the ground-truth algorithm (we refer to Appendix E for illustrations). The model's er- rors occur at distances 2 from the starting node (we did not reverse-engineer the specific logic of computations on larger distances).
be combined with the proposed discretization ideas. Addi- tionally, there are several potential ways balance between expressive power of the model and strong generalization guarantees, e.g., removing hard attention or removing fea- ture discretization (while keeping the discretization inside the ScalarUpdate module).
Second, while we report perfect scores for the covered tasks, we cannot guarantee that the training will converge to the correct model for any initialization/rraiing data distribu- tions. However, we empirically found the proposed method to be quite robust to various architecture/rraining hyperpa- rameter choices.
We found this behavior well-aligned with the BFS algorithm, which indicates the possibility of achieving the perfect vali- dation score with enough number of states. However, this algorithm does not generalize since it fails at distances larger than those encountered during training.
Future work Our method is based on the particular archi- tectural choice and actively utilizes the attention mechanism. However, the graph deep learning field is rich various architectures exploiting different inductive biases and com- putation flows. The proposed separation between discrete states and continuous inputs may apply to other models. However, any particular construction may require additional effort.
On the other hand, one can demonstrate that for a small enough state count (for BFS, it is two node states and two edge states) and sufficiently diverse validation data, the per- feet validation performance implies that the learned solution will generalize to any graph size.
Therefore, we highlight the need to achieve perfect vali- dation performance with models that use as few states as possible, which corresponds the minimum description length (MDL) theory (Myung, 2000; Rissanen, 2006) and is related to the notion of Kolmogorov complexity (Kol- mogorov, 1963).
Also, we provide only one example of the SealarUpdato block. We believe that utilizing a general architecture (e.g.. some form of discrete Neural Turing Machine (Graves et al., 2014; Gulcehre et al., 2016)) capable of executing wider range of manipulations is of interest for future work.
Finally, we note that for sequential problems, such as DFS, obtaining a good no-h model can be even more challeng- ing and may require additional effort. One possible way to overcome this limitation is to implement a curriculum learning setup, which we leave for future work.
With the development of neural reasoners and their ability to execute classical algorithms on abstract data, it is becom- ing more important to investigate how such models can be applicable in real-world scenarios according to the Neural Algorithmic Reasoning blueprint (Veličković & Blundell, 2021) and transfer their knowledge to high-dimensional noisy data with intrinsic algorithmic dependencies. While there are several examples of NAR- based models tackling real-world problems (Beurer-Kellle et al., 2022; Numeroso et al., 2023), there are no established henchmarks for exten- sive evaluation and comparison of different approaches.
7. Limitations and Future Work
Limitations In this work, we propose a method to learn robust neural reasoners that demonstrate perfect general- ization performance and are interpretable by design. In this section, we describe some limitations of our work and important directions for future research.
Lastly, we leave for future work a deeper investigation of learning interpretable neural reasoners without hints, which we consider essential both from theoretical perspective and for practical applications, e.g., combinatorial optimization.
First, several proposed design choices strictly reduce the expressive power of the model. For example, due to the hard attention, the proposed model is unable to compute the mean value from all the neighbors in single message- passing step, which is trivial for attention-based models (note that this can be computed in several passage-passing steps). Thus, the model in its current form is unable to express transitions between hints for some algorithms in the CLRS-30 benchmark in a single processor step.
8. Conclusion
In this paper, we force neural reasoners to maintain the execution trajectory as combination of finite predefined states. To achieve that, separate discrete and continu- ous data flows and describe the interaction between them. The obtained discrete reasoners are interpretable by design. Moreover, trained with hint supervision, such models per- feetly capture the dynamics of the underlying algorithms and do not suffer from distributional shifts. We consider
However, we believe that the expressivity of the proposed model can be enhanced with additional architectural mod- ifications (e.g., edge-based reasoning (Ibarz et al., 2022), global states, interactions between different scalars) that can
8

---

Discrete Neural Algorithmic Reasoning
discretization of hidden representations crucial component for robust neural reasoners.
Georgiev, D., Barbiero, P., Kazhdan, D., Veličković, P., and Liò, P. Algorithmic concept-basee explainable reason- ing. In Proceedings of the AAAI Conference Artificial 2022.
Impact Statement
Intelligence, volume 36, pp.
Georgiev, D., Lio, P., Bachurski, J., Chen, J., and Shi, T. Beyond Erdös- -énös- Generalization in algorithmic rea- soning on graphs. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Graves, A., Wayne, G., and Danihelka, 1. Neural Turing machines, arXiv preprint arXiv:1410.5401 2014.
References
Beller- L., Vechev, M., Vanbever, L., and Veličković, P. Learning to configure computer networks with neural algorithmic reasoning. Advances in Neural Information Processing Systems, 35:730-742, 2022.
Gulcehre, C., Chandar, S., Cho, K., and Bengio, Y. Dynamic neural Turing machine with soft and hard addressing schemes, arXiv preprint arXiv: 660700036,, 2016.
Hamrick, J. B., Allen, K. R., Bapst, V., Zhu, T., McKee, K. R., Tenenbaum, J. B., and Battaglia, W. Relational inductive bias for physical construction in humans and machines. In Proceedings of the Annual Meeting of the Cognitive Science Society, volume 40, 2018.
Bevilaequa, B., Nikiforou, K., Ibarz, B., Bica, I., Paganini, M., Blundell, C., Mitrovic, J., and Veličković, P. Neu- ral algorithmic reasoning with causal regularisation. In International Conference on Machine Learning, pp. 2272- 2288. PMLR, 2023.
Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Ben- nani, M., Csordás, R., Dudzik, A. J., Bošnjak, M., Vitvit- skyi, A., Rubanova, Y., et generalist neural algorith- mic learner. In Learning on Graphs Conference. PMLR, 2022.
Bohde, M., Liu, M., Saxton, A., and Ji, S. On the Markov property of neural algorithmic reasoning: Analyses and methods. In International Conference on Learning Rep- resentations, 2024.
Jain, R., Veličković, P., and Liò, P. Neural priority queues for graph neural networks. arXiv preprint arXiv:2307.06660 2023.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction Algorithms. MIT press, 2009.
de Luca, A. B. and Fountoulakis, K. Simulation of graph al- gorithms with looped transformers. In International Con- ference on Machine Learning, pp. 2319-2363. PMLR, 2024.
Jang, E.,, Gu, S.,, and Poole, B. Categorical reparameteriza- tion with Gumbel-Softmaal In International Conference on Learning Representations, 2017.
Jürß, J., Jayalath, D. H., and Veličković, P. Recursive algo- rithmic reasoning. In Learning on Graphs Conference. PMLR, 2024.
Dijkstra, F. W. A note on two problems in connexion with graphs. Numerische Mathemarik, 1:269-271, 1959.
Dudzik, A. J. and Veličković, P. Graph neural networks are dynamic programmers. Advances in Neural Information Processing Systems, 35:20635-2066 2022.
Kaiser, t. and Sutskever, I. Neural GPUs learn algorithms. arXiv preprint arXiv:1511.08226 2015.
Khardon, and Roth, D. Learning to reason. Journal of the ACM (JACM), 44(5):697-725, 1997.
Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., DasSarma, N., Drain, D., Ganguli, D., Hatfield-Dodde Z., Hernandez, D., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T., Clark, J., Kaplan, J., McCandlish, S., and Olah, C. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021.
Klindt, D. A. Controlling neural network smoothness for neural algorithmic reasoning. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Kolmogorov, A. N. On tables of random numbers. Sankhya: The Indian Journal of Statistics, 25, 1963.
Lindner, D.,, Kramár, J., Farquhar, S., Rahtz, M., McGrath, T., and Mikulik, V. Tracr: Compiled transformers as a laboratory for interpretability. Advances in Neural Infor- mation Processing Systems, 36:37876-37899, 2023.
Friedman, D., Wettig, A., and Chen, D. Learning trans- former programs. Advances in Neural Information Pro- cessing Systems, 36:49044 4906004449067,,, 2023.

---

Discrete Neural Algorithmic Reasoning
Mahdavi, S., Swersky, K., Kipf, T., Hashemi, M., Thram- poulidis, C., and Liao, R. Towards better out-of- distribution generalization of neural algorithmic reason- ing tasks. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. Advances in Neural Information Processing Systems, 28, 2015.
Weiss, G., Goldberg, Y., and Yahav, E. Thinking like trans- formers. In International Conference on Machine Learn- ing, pp. 11080-1 1109. PMIR, 2021.
Minder, J., Grötschla, F., Mathys, J., and Wattenhofer, R. SALSA-CLRS: A sparse and scalable benchmark for algorithmic reasoning. arXiv preprint arXiv:2309.122 12253, 2023.
Xhonneux, L.-P., Deac, A.-I., Veličković, P., and Tang, J.
How to transfer algorithmic reasoning knowledge to learn new algorithms? Advances in Neural Information Pro- cessing Systems, 34: 14:19900019511, 2021.
Myung, The importance of complexity in model se- lection. Journal of Mathematical Psychology. 44(1):190- 204, 2000.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Numeroso, D., Bacciu, D., and Veličković, Dual algorith- mic reasoning. In Interaational Conference on Learning Representations, 2023.
Xu, K., Li. Zhang, M., Du, S. S., Kawarabayashi. K.-i., and Jegelka, S. What can neural networks reason about? International Conference on Learning Representations, 2020.
Reed, S. and De Freitas, N. Neural programmer-interpreterr. arXiv preprint arXiv:151..06279 2015.
Rissanen, Information and complexity in statistical mod- eling. In Information Theory Workshop, 2006.
Yan, Y., Swersky, K., Koutra, D., Ranganathan, P., and Hashemi, M. Neural execution engines: Learning to execute subroutines. Advances in Neural Information Processing Systems, 33:17298-17300 2020.
Rodionov, G. and Prokhorenkova, L. Neural algorithmic reasoning without intermediate supervision. Advances in Neural Information Processing Systems, 36:51663- 51674, 2023.
Zaremba, W. and Sutskever, I. Learning to execute. arXiv preprint arXiv:
2014.
Shi, Y., Huang, Z., Feng, S., Zhong, H., Wang, W., and Sun, Y. Masked label prediction: Unified message passing model for seni-super classification. arXiv preprint arXiv:2009.03509 2020.
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J. M., Bengio, S., and Nakkiran, P. What algorithms can transformers learn? A study in length generalization. In International Conference on Learning Representations, 2024.
Vaswani, A., Shazeer, N., Parmar, N.. Uszkoreit, J., Jones, L.. Gomez, A. N., Kaiser, L., and Polosukhin, I. Atten- tion is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Veličković, P. and Blundell, C. Neural algorithmic reasoning. Patterns, 107): 2021.
Veličković, P., Buesing, I.., Overlan, M., Pascanu, R., Vinyals, O., and Blundell, C. Pointer graph networks. Advances in Neural Information Processing Systems, 33: 2232-2244, 2020a.
Veličković, P., Ying. R.. Padovano, M., Hadsell, R., and Blundell, C. Neural execution of graph algorithms. In International Conference on Learning Representations, 2020b.
Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Ban- ino, A., Dashevskiy, M., Hadsell, R., and Blundell, C. The CLRS algorithmic reasoning benchmark. In Inter- national Conference on Machine Learning, pp. 22084- 22102. PMLR, 2022.
10

---

Discrete Neural Algorithmic Reasoning
A. Ablation Study
Recall that we have three key components of our contribution: feature discretization, hard attention, and separating discrete and continuous data flows. In this section, we study the importance of these components for generalization capabilities of the proposed models.
Discrete bottlenecks First, we evaluate the model without any of its discrete bottlenecks: the result is simple Transformer Convolution processor, which performs comparably to the other baseline models (Table 4).
Table Node/graph-level test scores for our base model without discrete bottlenecks. Scores are averaged across different seeds; standard deviation is omitted.
SIZE
16
80
160
800
1600
BFS
99.9 / 99.3
99.7 / 88.2
99.5 57.9
9..4/0.0
97.2 0.0
DFS
79.2 6.8
0..
2.01
24.7
2..9
SP
99.3/888 88.7
94.1 12.4
90.3/0.0
86.9/0.0
8.04/0.0
PRIM
/ 72.7
82.6 0.0
79.7 0.0
6..1/0.0
6.0
MIS
99.8 / 98.6
99.6 / 86.1
99.2 / 69.0
97.1/11.9
96.3 16.3/0.00 0.0
Ecc.
NA 79.2
NA/41.1 NA/
NA / 28.1
NA 24.7
NA 21.9
Hard attention To highlight the importance of the hard atten- tion for strong size generalization, we train the proposed model but with the regular attention mechanism on the BFS task. The resulting model also demonstrates perfect scores for the given test data. However, the standard test data (the Erdös-Reng Renyi graphs with low edge probability) does not contain nodes with large number of neighbors, while such nodes can be problematic due to the annealing of the attention weights. Thus, we addition- ally test the resulting model on the complete bipartite graphs K2,n-2 for different n. For each n, we assign the starting node from smaller component and test if the second node in this component correctly selects its parent in the BFS tree (Figure 2).
Figure 2. Complete bipartite graphs K2,..2 used to evaluate the effect of the attention weight annealing. The black node the starting node. The highlighted edge (Green) is the ground- truth pointer from the bottom node its parent in the BFS tree.
Our experiments demonstrate that the model without hard attention fails to predict the correct pointer for larger graphs due to the attention weight annealing (see Table 5). We note that the models from Section 4 are provably correct on any test data.
Table 5. Attention weights for the ground-truth pointer (green pointer from Figure 2) for different graph sizes; (+/-) denotes whether the correct pointer was predicted.
SIZE
16
80
160
800
1600
ATTENTION WEIGHT
0.97 (+)
0.86 (+)
0.76 (+)
0.38 (-) 0.24 (-)
Scalar updater As demonstrated in Klindt (2023), simple neural networks trained to sum two real numbers fail to learn the structure of the task and struggle to extrapolate beyond the training data distributions. In this section, we study how these limitations affect the overall performance of neural reasoners to highlight the importance of the proposed discrete manipulations with scalars.
First, we recall that usually all input data is encoded into node and edge features and the processor operates over the resulting vectors. Then, hints of type scalar directly predicted from the node/edge features. To evaluate the effect of non-discrete ScalarUpdate modules, we simply replace the proposed discrete ScalarU Update module with single-layer transformer convolution network, which inputs scalars and node/edge states and outputs the scalars for the next step, keeping the remaining architecture the same as in the main experiments. We train the resulting model on Dijkstra and MST problems.
Additionally, we evaluate the non-discrete ScalarUpdate module in a more straightforward setup. Similarly to Klindt (2023), we train a 2-layer MI.P to add two real numbers and use the resulting model as ScalarUpdate module for the

---

Discrete Neural Algorithmic Reasoning
Dijkstra algorithm. We manually use the learned addition module when the node distances are updated (e.g., the distance of the node is updated with the sum of the distance of e and the edge (v, u) cost), and use the ground-truth scalars for other scalar updates. Our experiments demonstrate that the resulting model outperforms the baselines on the test size of 16 nodes, but does not generalize well on larger graphs (see the evaluation results in Table 6).
Table 6. Node/graph-Ievel test scores for the proposed model with ScalarU replaced by regular attention-haset network trained to predict hints of type scalar. 'Addition only' means that ScalarUpdate is replaced by 2-layer MLP trained to predict the sum of numbers (the other values are taken from the ground truth).
SIZE
16
160
800
1600
DUKSTRA
99.3 / 94.6
60.7 0.0
42.8 0.0
19.
11.8/0.0
MST DUKSTRA (ADDITION ONLY)
99.8 / 98.1
98.2 54.1
97.2 / 28.1
0.00
91.73 /
99.8 / 96.6
95.3 /710
86.5 / 46.3
41.6/3.1
22.2 /..0
We note that all the resulting models demonstrate perfect scores when evaluated with teacher-forced ground-truth scalars. Thus, all state transitions are learned correctly and imperfect test scores are fully described by the errors in manipulations with continuous values.
To summarize, small errors in manipulations with scalars (even restricted the simplest addition sub-task) severely affect the overall performance of the model, highlighting the importance of the proposed discrete manipulations with scalars.
B. Minimal Training Sizes
In this section, we highlight an important property of the proposed models: the correct state transitions can be learned even from a trivially small size.
For example, for the BFS problem, it is enough to use graphs with only 3 nodes to observe whether an unvisited node be- comes visited depending on the received message. However, the subtask of selecting the parent from multiple visited neighbors requires at least nodes (where the minimum sufficient example is the complete bipartite graph K (2)
Table 7. Node-level test scores for the proposed discrete soner on test graphs with 160 nodes, across different training sizes.
TASK
nodes
nodes
5 nodes
BFS
41
100
100
To demonstrate that, we conducted additional experiments to empirically find the smallest graph size for perfect fitting of each covered algorithm. For this experiment, we used training with hints: we trained our models for each problem on ER(n, 0.5) graphs for different n and tested the resulting models on graphs with 160 nodes. Table 7 presents the results. Note that the empirical bound is around 4-5 nodes.
DFS
38
100
100
DUKSTRA
13
26
100
MST
11
14
100
MIS
79
100
100
Ecc.
45
100
100
C. CcalarUpdate Module
In this section, we first provide an example demonstrating the role of the proposed ScalarUpdate module and then investigate whether this module can be successfully extended to support more complex manipulations with scalars.
To give an example, consider the Dijkstra algorithm. The algorithm uses edge weights to compute the shortest distance from the starting node to each node, building a tree step-by-step. When adding a new node B to the tree and assigning node as a parent in the tree, the algorithm computes the distance from the starting node the node B by summing the distance to the node A with the weight of the edge AB. To mimic this behavior with our model, we use the Scalar Update module. At node level, this module receives inputs the discrete states of the node and its neighbors and the scalar values stored in the corresponding edges. Depending on the discrete states, this module updates the scalar values by one of the supported operations, as shown in the formula (2). In our example, this module would push the scalar (the distance from the starting node to A) from the node A to the edge AB and sum it with the edge's 's weight. Thus, for edges in the shortest path tree, the scalar value on edges represents the exact shortest distance from the starting node, and for other edges the scalar value will represent the edge weight.
12

---

Discrete Neural Algorithmic Reasoning
This module allows one perform any (predefined) operation with scalars needed for the algorithms, while guaranteeing that the correct operation is chosen based on the discrete states, thus being robust to OOD scalar values.
We note that simple manipulations with scalars cover a significant part of the classical algorithms. In this work, we use the minimum set of the required functions, but this set can be directly extended with other functions. Importantl, as Udate can be viewed as a separate module, we can separately check if is possible to train it with any given set of predefined manipulations for any problem only with supervision on the results.
Let us formalize the problem: each imput to the Scalar Update module can be described as an object with a discrete state &t (from fixed predefined set) and several scalar values (we consider two scalars 2; and y:). Note that omit the separation between nodes and edges and consider objects with several scalar values. For each discrete state 85, there exists ground-truth update of scalars, e.g.. [(8,2, v) cos(y). The output of the scalar updater can be viewed as a sum:
ScalarUpdate(s,22./
Σ gEOPS
g(z. y) activateg(s)
where OPS is predefined set of operations and activateg is a 0-1 function representing whether specific operation should be applied. Note that activate, depends only the discrete state of the input.
For our additional experiment, train several different ScalarUpdat modules with an extended set of operations:
(1, y) 1;
gi (z. y) 2; g2 (2, y) cos(
(3(r,, y) 1/3
ga(2, 3) atan2(x,
to learn the following set of ground-truth updates simultaneously:
fo(æ, v) 2;
fz 3) = cos(x);;
f2(2, y) = cos( + x y:
fa(x, v) atan2(x, y):
fa(x,y) + r x atan222.. y).
In particular, we consider a set of 16 discrete states (numbered from 0 to 15 and sampled uniformly) and the ground-truth scalar update is derived from these states by taking the remainder of the division by (updates count).
The learnable parameters of the ScalarUpdate are state embeddings and linear projections for each indicator. We train ScalarUpdate minimize the MSE loss between the ground-truth and predicted outputs with 5000 optimization steps. Additionally, train non-discrete scalar updater (2-layer MIP), similar to ablation experiments. We refer to the source code for the experiment details.
Inspired by Klindt (2023), we generate training scalars X and Y from Uniform(0.5, 1.0] and generate the test set by sampling scalars from the Uniform (0., 0.5] distribution.
We report the evaluation results Table The proposed discrete Scalar Update module successfully learned the correct operations for updates fi.... fA for all seeds and for in 3 of runs (note that the model was trained to predict different manipulations for different states simultaneously). For unsuccessful runs, when fo was not learned correctly, the learned operation for fo was ys for some states (i.e., instead of x)), which can be explained by optimization challenges as the distribution of is close to 1.
Our experiment demonstrates that the proposed ScalarUpdate module can be extended to support a wider range of manipulations with scalars. We note that such an extension might complicate the optimization problem of selecting the correct operationssopprrndds from the operations results (e.g. such decomposition might not be unique).
13

---

Discrete Neural Algorithmic Reasoning
Table MSE train/test distributions for the discrete and non-discrete ScalarUpdate modules and different operations.
fu
fz
fa
discrete
0.01 0.1 5.7e-6 0.003
0. 5.1e-6/0.001
0/0
0/0
0/0
non-discrete
1.le5/0.00 0.007
1.0e5500m
2.0e-5/0.03
D. Interpetability and Testing Details
In this section, we provide additional details on interpretability and testing of the proposed discrete reasoners. As an example, consider the BFS algorithm. First, recall the pseudocode of the algorithm:
Starting-node +- visited All other nodes 6- nol visited for step in range(T) do for node U in a graph do if U visited on previous steps then continue
end if
if U has neighbor P that visited on previous steps then
U +- visited on this step
U selects the smallest-indexed such neighbor /' as parent:
Edge (U, P) + pointer
Self-loop (U, U) + not.pointer
end if end for
end for
return a BFS tree described by pointers
Now let us describe how we can verify that the trained DNAR model will perfectly imitate this algorithm for any test data.
First, we note that for each node U, the node state on the step ++1 (denoted by U241) is the function of U, and V,, where V the node that sends the message to U step t:
U = StateUpdate(UU, message.from.V))
How does the node U select node that will send message to it? For any node V connected U, the node U computes attention scores depending on discrete states of V of each node and a discrete indicator of whether each node has the smallest (or largest) scalar among all neighbors of U with the same discrete state as V. Then, the node U selects the node V with the largest attention score.
In our case, the attention scores only depend on the tuples (Ustates Vstates indicator _ there are only 8 such tuples. We can directly compute these attention scores and verify the required invariants, e.g.,
_indee)) and
Attention(not.viiiitl visited, visited, smallest) Attention(not -isited, =any others),
which would imply that the not visited node will receive the message from the smallest-indexed visited neighbor if such exists independently of the graph size and distribution. If there is no such neighbor, the node will receive the message from another visiiid node (or from itself).
After verifying the correctness of the message flows, we need to ensure that the state updates are computed correctly, e.g.,
visited StateUpdatecnott visited, message. from visited),
visited StateUpdate(visiteer sang*), message.from.not.usstteed
not_visited State
The main idea is that due to the finite state count and discrete manipulations with scalars, there are only finite amounts of such checks that can cover all possible state transitions and all of them should be evaluated only once.
14

---

Discrete Neural Algorithmic Reasoning
E. State Usage for No-Hint Models
In this section, we illustrate the internal states and pointer prediction dynamics model trained for BFS without hint supervision (Figures 3-5). Our analysis suggests that no-hint models with K states tend to use these states as distances from the starting node, with the distances K merged into the same state. Also, pointer predictions for the first K BFS layers are correct and computed layer-by-layer in the ground-truth algorithm. Errors occur at layers beyond K, where some pointers are predicted earlier than in the ground-truth algorithm (Figure 5c). For clarity, we use the model with K = 3 discrete states.
(a) Node states after the last processor step
(b) Predicted pointers (self-loops are omitted)
Figure 3. Node states and predicted pointers after the last processor step of the DNAR model (with 3 states) trained without hints. Node colors correspond to their states and the green node is the starting node for BFS.
(a) Node states after the last processor step
(b) Predicted pointers (self-loops are omitted)
Figure Node states and predicted pointers after the last processor step the DNAR model (with 3 states) trained without hints. Node colors correspond to their states and the green node is the starting node for BFS.
(a) Node states after the last processor step
(b) Predicted pointers after the first proces- sor step (self-loops are omitted)
(c) Predicted pointers after second pro- cessor step (self-loops are omitted)
Figure Node states and dynamics the pointer prediction updates of DNAR model (with 3 states) trained without hints. Node colors correspond to their states and the green node is the starting node for BFS.
15


Reviews:
[{"review_id": "6Ur4de1dgk", "reviewer": "Reviewer_fqbZ", "summary": "The authors define a learning paradigm where they force a neural reasoner to stay exactly on an execution trajectory as provided by the algorithm they aim to imitate, thus achieve perfect generalization. The architecture allows for verification.\nThey highlight three crucial architectural choices:\nfeature discretization, hard attention, discrete and continuous data flow separation\n\n## update after rebuttal: i have updated my score, see last comment.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review of our paper! We address your questions and concerns below.\n\n> The method mostly needs supervision from the algorithms they aim to mimic to work well\n\nLet us note that for the current state of the field, learning with hints is an important and unsolved problem. E.g., the large body of research (Section 2.1 of the paper), including the state-of-the-art approaches (Bevilacqua et al., 2023; Bohde et al., 2024) heavily rely on different forms of carefully designed step-by-step hints and are not applicable for no-hint learning without additional modifications.\n\nHowever, we fully agree that learning without hints is an important and challenging problem for further developments of NAR.\n> Their experiments without hints in Sec 6. show that for small problems some advances can be achieved, but they do not seem to be compared to existing work\n\nWe will add no-hint scores for baselines to the paper. As we write in Section 6, we focus only on the BFS algorithm as it is well-aligned with the message-passing framework, has short roll-outs, and can be solved with small states count. Even in this setup, we do not outperform baselines.\n\n\nAdditionally, we would like to highlight the important property of the proposed models which supports our motivation to focus only on small problems: the correct state transitions can be learned only from a trivially small size. \n\nFor example, for the BFS problem, it is enough to use graphs with only 3 nodes to observe that a not_visited node becomes visited or not depending on the received message. However, the subtask of selecting the parent from the multiple visited neighbors requires at least 4 nodes (where the minimum sufficient example is the complete bipartite graph K(2, 2)).\n\nTo demonstrate that, we conducted additional experiments to empirically find the smallest training size for perfect fitting of each covered algorithm. For this experiment we used training with hints, but we consider such examples as additional evidence of the prospects of learning with small graph sizes. We train our models for each problem on ER(n, 0.5) graphs for different n and test the resulting models on the graphs with 160 nodes.\n\nNode level scores on graphs with 160 nodes for different training sizes:\n\n\n|              | 3  | 4   | 5   |\n|--------------|----|-----|-----|\n| BFS          | 41 | 100 | 100 |\n| DFS          | 38 | 100 | 100 |\n| Dijkstra     | 13 | 26  | 100 |\n| MST          | 11 | 14  | 100 |\n| MIS          | 79 | 100 | 100 |\n| Ecc. | 45 | 100 | 100 |\n\nNote that the empirical bound is around 4-5 nodes. We leave a deeper investigation of learning models without hints for future work.\n> What do you mean by annealing of the attention weights?\n\nBy annealing of the attention weights we mean the convergence to zero of the maximum of attention weights when the count of neighbors limits to infinity. We refer to Appendix A (hard attention) for a specific graph construction which demonstrates that increasing the neighborhood size of a node breaks the ability of that node to select the most important neighbor, which supports our choice of the hard attention for strong size generalization with guarantees.\n> In 3.3 (and 3.4): I think a simple example (with an example algorithm like dijkstra) would help to understand why this treatment of the scalars makes sense\n\nFor example, consider the Dijkstra algorithm. The algorithm uses the edge weight to compute the shortest distance from the starting node to each node, building the tree step-by-step. When adding a new node B to the tree and assigning a node A as a parent in the tree, the algorithm computes the distance from the starting node the the node B by summing the distance to the node A with the weight of the edge AB. To mimic this behavior with our model, we use a scalar updater module. At node level, this module receives as inputs the discrete states of the node and its neighbors and the scalar values stored in corresponding edges. Depending on the discrete states, this module updates the scalar values by one of the supported operations, which is described by the formula (lines 228-230 of the paper). In our example, this module will push the scalar (the distance from the starting node to B) from the node A to the edge AB (edge weight) and sum them. Thus, for edges in the shortest path tree, the scalar value on edges represents the exact shortest distance from the starting node, and for other edges the scalar value will represent the edge weight.\n\nThis module allows one to perform any (predefined) operation with scalars needed for the algorithms, but with guarantees to choose the exact operation based on the discrete states, thus being robust to OOD scalar values.\n\nWe will add this example (with an illustration) to Appendix. Additionally, you can find the Appendix C useful for this context.\n\nWe hope that our response addresses your concerns and will be happy to answer any additional questions during the discussion period if needed.", "claims_and_evidence": "Clear and convincing evidence. Authors do not overclaim.", "methods_and_evaluation_criteria": "The evaluation criteria make sense and the method looks sound.", "theoretical_claims": "There are no significant theoretical claims.", "experimental_designs_or_analyses": "The experimental design and the analyses make sense.", "relation_to_broader_scientific_literature": "I am not well versed in the broader literature to gauge this.", "essential_references_not_discussed": "see above", "other_strengths_and_weaknesses": "Strengths:\n\nI enjoy the perfect and provable accuracy with OOD guarantees due to algorithm verification (interpretability)\nIt is very appealing that the models can do multiple tasks at once, albeit needing task dependent encoder/decoders.\n\nWeakness:\n\nThe method mostly needs supervision from the algorithms they aim to mimic to work well, making this much less useful in practice that it could otherwise be. Their experiments without hints in Sec 6. show that for small problems some advances can be achieved, but they do not seem to be compared to existing work.what do you mean by annealing of the attention weights\n\nI am not an expert in this area and I wonder about the scope of this work. It seems very narrow, esp. given the above limitation.", "other_comments_or_suggestions": "In 3.3 (and 3.4): I think a simple example (with an example algorithm like dijkstra + its its inputs illustrated) would help to understand why this treatment of the scalars makes sense. You can put 4.4 in the appendix, that doesn’t really need to be in the main text.", "questions_for_authors": "What do you mean by annealing of the attention weights?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GGlhVCxNsq", "reviewer": "Reviewer_KDUc", "summary": "This paper introduces a novel approach to neural algorithmic reasoning by forcing neural networks to maintain execution trajectories as combinations of finite predefined states.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback! We address the raised concerns below.\n\n> The approach sacrifices some expressivity for perfect generalization, which may limit its applicability to certain problems\n\nLet us highlight the main part of our contribution: we consider the proposed model in its current form as a potential answer on where perfect generalization might come from. In this sense, we investigate different architectural choices which are needed for different forms of the generalization.\n\nWhile there are several ways to improve expressiveness without losing the generalization at all, we also can improve expressiveness by reducing the generalization (as we briefly mention in lines 430-435):\n- Removing hard attention: as we demonstrate in our ablation experiments, using regular attention instead of hard attention yields perfect test scores for the BFS problem, but it is possible to construct adversarial examples with large neighborhood sizes where performance drops. While for more complex attention patterns (besides strictly attending to the single node) the OOD performance might be less robust, the expressivity gain is significant.\n- Removing feature discretization, but updating scalars with discrete operations: as shown by prior work and our ablation experiments, learning precise continuous manipulations is non-trivial and small inaccuracies in such manipulations can significantly affect the overall performance of the NARs. Thus, we can use the proposed separation between the discrete and continuous data flows and do not discretize node/edge features at all (and use discretization in ScalarUpdater). However, for non-attention-based models one needs to come up with how scalars will affect the discrete flow. \n\n\n> No discussion of the model size, and can it connect to LLM (scale up?)\n\nFor our experiments we use the model with hidden size 128 and a total 400K parameters, which corresponds to the prior work in the field. \nWhile there is no direct need to scale up the models on covered tasks, none of the proposed ideas are based on the small model sizes. Importantly, there is some connection between our work and [1]. In short, TransNAR[1] discusses a method to enhance reasoning capabilities of large language models with the task-specific GNN-based NAR model, where any NAR model can be used as an “internal tool”. Thus, replacing the baselines GNN with the proposed DNAR model improves the quality of the tool that the language model can use and the overall performance will be limited only by the correctness of the “tool usage”, and not by the inaccuracies of the tool itself.\nHowever, there are some difficulties in measuring the direct effect of including the proposed DNAR model in the TransNAR pipeline, as the source code for TransNAR is not yet publicly available. \n\n\n[1]  Bounsi et al. (2024), Transformers meet Neural Algorithmic Reasoners\n\n\n\n> How does your approach scale to algorithms requiring more complex state spaces? For example, algorithms that need to maintain ordered collections or hierarchical structures?\n\nWe think that for any specific algorithm it is straightforward to modify the architecture (or only the hints, keeping the architecture the same). However, the main challenge arises with the goal of building the universal architecture for different algorithms and data structures. \n\nIn its current form, the proposed model is not capable of executing some algorithms from the CLRS-30 benchmark, however, simple modifications can enhance its expressivity, e.g., by supporting more complex aggregations with top-k attention (with fixed k). Also, as we mention in Section 4.1, the model can be extended with additional architectural modifications, such as edge-based reasoning. For example, edge-based attention with top-2 attention (where each edge chooses the top 2 adjacent edges to receive the message from) can implement the sort of triplet reasoning. In our work, we aim to describe the key principles that help to build perfectly generalizable models and do not focus on a general architecture capable of executing a wide range of algorithms.\n\n\n> For problems where the ground truth algorithm is unknown, how might we determine the appropriate number of discrete states needed? Is there a principled way to discover minimal state representations?\n\nWe think that different forms of discrete search are possible techniques for this problem. Additionally, possible techniques can be inspired from the finite automata theory, e.g., constructing the automata from the examples of strings from some regular language. After finding some feasible set of states one can iteratively find equivalent states and merge them. However, we leave a deeper investigation of no-hint discrete neural reasoners for future work.\n\nWe hope that our response addresses your concerns and will be happy to answer any additional questions during the discussion period if needed.", "claims_and_evidence": "I think the claims made in this submission are strongly supported by the experimentation. The author demonstrate good generalization scores on both in-distribution and out-of-distribution test data across all evaluated tasks.", "methods_and_evaluation_criteria": "I believe the proposed methods are appropriate and well-motivated. The authors evaluate on the SALSA-CLRS benchmark which provides a challenging testbed with sparse graphs up to 100× larger than training graphs. Both node-level and graph-level metrics are reported, and comparisons are made against several baseline models.", "theoretical_claims": "no theory", "experimental_designs_or_analyses": "The author compare against multiple baselines including GIN, PGN, and state-of-the-art models, and they evaluate on diverse algorithmic tasks with different computational requirements. They also test on graphs up to 100× larger than training graphs", "relation_to_broader_scientific_literature": "I think this work makes some contributions to neural algorithmic reasoning. It builds upon prior work on the CLRS-30 and SALSA-CLRS benchmarks while addressing the fundamental limitation of poor generalization to larger graphs.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "1. I find the approach conceptually simple yet highly effective\n2. Perfect generalization to graphs 100× larger than training examples is impressive\n3. The ability to formally verify correctness on any input is a significant advantage over previous approaches\n\n\n4. The approach sacrifices some expressivity for perfect generalization, which may limit its applicability to certain problems\n5. No discussion of the model size, and can it connect to LLM (scale up?)", "other_comments_or_suggestions": "My major question is can this method scale up to LLM. If the author can show this in an experiment, I will raise my score", "questions_for_authors": "How does your approach scale to algorithms requiring more complex state spaces? For example, algorithms that need to maintain ordered collections or hierarchical structures?\n\nFor problems where the ground truth algorithm is unknown, how might we determine the appropriate number of discrete states needed? Is there a principled way to discover minimal state representations?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2VVP08SpDe", "reviewer": "Reviewer_6CKL", "summary": "Neural reasoners are robust to the noisy data but struggling with out-of-distribution data. Classic symbolic algorithms have complementary features – they are crisp to noisy inputs, but applicable for any out-of-distribution data.\n\nAuthors propose a novel approach that guides neural reasoners to maintain the execution of classic symbolic algorithms, so that they could reason with out-of-distribution data. The execution trajectory of classic symbolic algorithm is interpreted as a combination of finite predefined states. The approach identifies discrete states in continuous data flows, and uses a hard attention mechanism to force neural reasoners to align with discrete states.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review! We addressed the questions and concerns below.\n\n> I am not very clear about the detailed process that described from Section 3.3 and 3.4. It would be nice that authors can give a concrete example in the supplementary material.\n\nFor example, consider the Dijkstra algorithm. The algorithm uses the edge weight to compute the shortest distance from the starting node to each node, building the tree step-by-step. When adding a new node B to the tree and assigning a node A as a parent in the tree, the algorithm computes the distance from the starting node the the node B by summing the distance to the node A with the weight of the edge AB. To mimic this behavior with our model, we use a scalar updater module. At node level, this module receives as inputs the discrete states of the node and its neighbors and the scalar values stored in corresponding edges. Depending on the discrete states, this module updates the scalar values by one of the supported operations, which is described by the formula (lines 228-230 of the paper). In our example, this module will push the scalar (the distance from the starting node to B) from the node A to the edge AB (edge weight) and sum them. Thus, for edges in the shortest path tree, the scalar value on edges represents the exact shortest distance from the starting node, and for other edges the scalar value will represent the edge weight.\n\nThis module allows one to perform any (predefined) operation with scalars needed for the algorithms, but with guarantees to choose the exact operation based on the discrete states, thus being robust to OOD scalar values.\nWe will add this example (with an illustration) to Appendix.\n\nAdditionally, you can find the Appendix C useful for this context.\n\n\n> Authors neglected the following two essential papers.\n\nThank you for your suggestion, we will cover works on symbolic reasoning, including the mentioned ones, in the background section.\n\n> But, authors’ experiments do not fully support their claim. …  In my opinion, it is impossible to provide data-independent theoretical proof that the trained processor follows the execution trajectory of classic algorithms.\n\nOur claim is based not only on the empirical results, but also on the design of our model. Discrete and size-independent design allows us to unittest all state transitions to ensure that the model will perform correctly on any test data. \n\nFrom the theoretical perspective, this is similar to proving that a specific algorithm (e.g. bubble sort or BFS) is working correctly for any input (by working correctly we mean that the outputs of the algorithm satisfy a certain condition), but with a difference that we do not need to prove the correctness of the algorithm, we only need to prove that the model will mimic the execution of the algorithm.  Zooming to the node level, at each step, each node needs to select the neighbor and update its own state based on the current discrete state. Both selection and state transition can be tested independently from any input distribution, because there are only finitely many node/edge states. We refer to Appendix B for details of such proof for the BFS problem.\n\n\n> Nodes and features are represented by vectors. You enforce them to be from a fixed finite set. Do you mean the members of the set are symbolic states of the classic algorithm?\n\nYes. You can find a specific example in Appendix B.\n\n> All input data is represented as a graph, and the processor updates features of nodes and edges. Intuitively, what represents the states of classic algorithms, the configuration of the whole graph, or all features of nodes and edges, or features of some nodes or edges?\n\nIn general, the overall state of the algorithm is represented by all features of all nodes and edges. For example, for the BFS problem, at each step, each node is either visited or not and each edge either represents a pointer in the BFS tree or not. At each step, the processor network updates node/edge features with message passing between adjacent nodes. \n\n> The main work of the proposed method is to correctly discretize continuous data flow to align with a classic algorithm. This is not yet the whole story to train a neural reasoner to mimic classic algorithms. Classic computing can be roughly stated as data + algorithm + knowledge. How can your method distinguish data from knowledge?\n\nZooming to the node level, each node essentially has a state transition matrix (from the architectural perspective this is an MLP that updates node states depending on the current state and the received message from the selected neighbor). In this level, this update is similar to the finite state machine, so the data is the input states and the knowledge is encapsulated in the learned transition rules (e.g., MLPs).\n\nWe hope that our response addresses your concerns and will be happy to answer any additional questions during the discussion period if needed.", "claims_and_evidence": "Authors claim the proposed method is perfect (the word ‘perfect’ or ‘perfectly’ appears 22 times in the paper), evidenced by experiments on SALSA-CLRS benchmark datasets with 100% accuracy.", "methods_and_evaluation_criteria": "The proposed approach is an encode-process-decode procedure. Input data is represented as a graph whose node and edge features are encoded into vector embeddings. The processor is a graph neural network that repeatedly updates the vector embeddings.  Hint supervision trains the processor to follow the execution status of the original algorithm. When the processor finishes, the vector embeddings are fed into a decoder network.", "theoretical_claims": "Authors claim that they built fully discrete neural reasoners for different algorithmic tasks and demonstrated their ability to perfectly mimic ground-truth algorithm execution. Their experiments achieved perfect test scores (100%) on the multiple algorithmic tasks (with guarantees of correctness on any test data).", "experimental_designs_or_analyses": "Authors conducted and analysed experiments within the statistical machine learning paradigm.", "relation_to_broader_scientific_literature": "Yes. This important research is in line with the broader scientific research to improve the interpretability and reliability of neural networks.", "essential_references_not_discussed": "Authors neglected the following two essential papers.\n\nSphere Neural Networks for Rational Reasoning. https://arxiv.org/abs/2403.15297 \nNeural Reasoning for Sure Through Constructing Explainable Models. AAAI 2025\n\nThese two papers demonstrate one kind of novel neural networks that achieves symbolic-level syllogistic reasoning, with theoretical proof that this network works for any out-of-distribution input data.", "other_strengths_and_weaknesses": "Researching how neural networks can mimic symbolic algorithms is not only a nice idea but also of huge scientific and practical value.   \n\nBut, authors’ experiments do not fully support their claim. A neural network perfectly mimic classic algorithm requires the network to achieve 100% on any out-of-distribution datasets. Using benchmark datasets is far beyond sufficient, even these datasets contain out-of-distribution testing items.", "other_comments_or_suggestions": "Authors use supervised learning to train the processor to mimic the execution trajectory of classic algorithms. In my opinion, it is impossible to provide data-independent theoretical proof that the trained processor follows the execution trajectory of classic algorithms.\n\nI would like to suggest authors to weaken the claims (it is not necessary to make such strong theoretical claims here, as your experiments are good enough) and mention the methodological limitation above.", "questions_for_authors": "1. “We also enforce all node and edge features to be from a fixed finite set, which we call states.” Nodes and features are represented by vectors. You enforce them to be from a fixed finite set. Do you mean the members of the set are symbolic states of the classic algorithm?\n\n2. All input data is represented as a graph, and the processor updates features of nodes and edges. Intuitively, what represents the states of classic algorithms, the configuration of the whole graph, or all features of nodes and edges, or features of some nodes or edges?\n\n3.  The main work of the proposed method is to correctly discretize continuous data flow to align with a classic algorithm. This is not yet the whole story to train a neural reasoner to mimic classic algorithms. Classic computing can be roughly stated as data + algorithm + knowledge. How can your method distinguish data from knowledge?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DvhKO7dJVI", "reviewer": "Reviewer_XN76", "summary": "This paper addresses the problem of neural algorithmic reasoning, where the objective is to train a neural network to mimic each step of a given classical algorithm. The authors propose a novel architecture for this task. They partition the input graph instance into discrete and continuous components and process them separately. Specifically, the discrete component is handled similarly to previous approaches, while the continuous component is used exclusively in the attention weights of the graph neural network. Empirical evaluations demonstrate that their architecture achieves SOTA performance on several algorithmic tasks.\n\n## update after rebuttal\nI appreciate the authors' rebuttal and will keep my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive review and positive feedback! We address the questions below.\n\n> The performance on other algorithmic tasks in the benchmark dataset should be presented\n\nLet us highlight the main part of our contribution: we consider the proposed model in its current form as a potential answer on where perfect generalization might come from. In this sense, we investigate different architectural choices which are needed for different forms of the generalization.\n\nWe agree that a more general architecture is of great interest for future work. In its current form, the proposed model is not capable of executing some algorithms from the CLRS-30 benchmark, however, simple modifications can enhance its expressivity, e.g., by supporting more complex aggregations with top-k attention (with fixed k). Also, as we mention in Section 4.1, the model can be extended with additional architectural modifications, such as edge-based reasoning. For example, edge-based attention with top-2 attention (where each edge chooses the top 2 adjacent edges to receive the message from) can implement the sort of triplet reasoning. In our work, we aim to describe the key principles that help to build perfectly generalizable models and do not focus on a general architecture capable of executing a wide range of algorithms.\n\n> what exactly does the discrete state refer to? Could you provide a concrete example using BFS? If these discrete states are simply the hints provided in the dataset, then except for the part of handling scalar information, the overall framework doesn’t seem significantly different from previous methods, as prior approaches also produced discrete states via the decoder, which were then fed into the next algorithmic step.\n\nYes, except for the part of handling the scalar information the overall framework is similar to prior work. The main remaining difference is that we use discrete bottleneck (essentially feed hint predictions to the processor at the next step) and do not use the hidden states from the previous steps. Most of the previous methods use both re-encoded hint predictions and previous hiddens. \nOur architectural choice is close to ForgetNet (not G-ForgetNet) from Bohde et al. (2024). From this perspective, the difference of our method from ForgetNet can be described as adding discretization to scalar updates, using hard attention, and stepwise training (i.e. training with teacher-forcing). We will add an architecture diagram with additional clarifications to the main text.\n\n> In an algorithmic task with hints, does the proposed method require invoking the encoder and decoder at each step? As far as I know, previous approaches call the encoder and decoder at every algorithmic step. \n\nYes, similar to prior work, the encoder is the module which maps the discrete state to the high-dimensional vector and the decoder is the module which projects the high-dimensional vectors to the logits of hints/states. Similar to hints reencoding after each step in the prior work, the encoder and decoder invoked in the discrete bottleneck after each processor step.\n\n\n> What are the specific node-level and graph-level evaluation metrics? Could you provide a concrete example?\n\nFor all covered problems, node-level metrics represent the accuracy of predicting correct pointers from each node averaged across all nodes in all test graphs. The exception is the MIS problem, where the node-level metric is the accuracy of predicting the correct binary class (in the MIS, not in the MIS) for each node.\n\nGraph-level metrics represent the accuracy of correctly predicting all node-level outputs in a graph, averaged across all test graphs. \nFor example, for the BFS problem, output of the algorithm is presented as a tree, where each node points to its parent in the BFS exploration tree (and the starting node points to itself). Pointer is a specific hint/output type which forces each node to point to exactly one node. Technically this is usually implemented via taking the softmax/argmax over the neighbors. \nWe will add the example above to the paper.\n\nWe thank the reviewer for thoughtful questions and we are happy to discuss further.", "claims_and_evidence": "Yes, the paper provides experiments and ablation studies to support their claims.", "methods_and_evaluation_criteria": "The proposed method seems reasonable (though I still have some uncertainties about the details; see below). In certain algorithmic tasks, it does make sense to handle scalar information differently. The method was tested on a public dataset, but the authors only presented results for a subset of algorithmic tasks, without specifying the evaluation metric. It would be better to clarify the specific evaluation metric used and provide results for all algorithmic tasks in the dataset.", "theoretical_claims": "NA", "experimental_designs_or_analyses": "Yes, the experiment is sound.", "relation_to_broader_scientific_literature": "The paper contributes to the field of neural algorithmic reasoning. The proposed method makes sense and could influence future research in this area, I think.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "- A more comprehensive architecture diagram, including the encoder and decoder modules, should be provided. The current architecture is somewhat confusing (see the questions below). \n\n- The performance on other algorithmic tasks in the benchmark dataset should be presented and the evaluation metric should be clarified.", "other_comments_or_suggestions": ".", "questions_for_authors": "- In an algorithmic task with hints, does the proposed method require invoking the encoder and decoder at each step? As far as I know, previous approaches call the encoder and decoder at every algorithmic step. This actually raises another question I am confused: what exactly does the discrete state refer to? Could you provide a concrete example using BFS? If these discrete states are simply the hints provided in the dataset, then except for the part of handling scalar information, the overall framework doesn’t seem significantly different from previous methods, as prior approaches also produced discrete states via the decoder, which were then fed into the next algorithmic step.\n\n- What are the specific node-level and graph-level evaluation metrics? Could you provide a concrete example?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a new architecture for training neural networks to imitate algorithms. It forces intermediate discrete states, and requires supervising on "hints" (intermediate execution states), but is able to perfectly learn an impressive range of nontrivial algorithms. Reviewers unanimously recommend acceptance. I also like the paper, but I think it's a major limitation that it requires this high level of supervision. The authors are upfront about this limitation, and also give interpretability and verification results. Overall, because of the extra supervision, it's not exactly the result that you would want for a neural algorithmic reasoner, but it's a good step forward.
Decision: Accept (poster)