Neural Algorithmic Reasoning Without Intermediate Supervision
Authors: Gleb Rodionov
Liudmila Prokhorenkova
Venue: NeurIPS 2023 poster (2023)
Keywords: neural algorithmic reasoning
graph neural networks
self-supervised regularization

Abstract: Neural algorithmic reasoning is an emerging area of machine learning focusing on building models that can imitate the execution of classic algorithms, such as sorting, shortest paths, etc. One of the main challenges is to learn algorithms that are able to generalize to out-of-distribution data, in particular with significantly larger input sizes. Recent work on this problem has demonstrated the advantages of learning algorithms step-by-step, giving models access to all intermediate steps of the original algorithm. In this work, we instead focus on learning neural algorithmic reasoning only from the input-output pairs without appealing to the intermediate supervision. We propose simple but effective architectural improvements and also build a self-supervised objective that can regularise intermediate computations of the model without access to the algorithm trajectory. We demonstrate that our approach is competitive to its trajectory-supervised counterpart on tasks from the CLRS Algorithmic Reasoning Benchmark and achieves new state-of-the-art results for several problems, including sorting, where we obtain significant improvements. Thus, learning without intermediate supervision is a promising direction for further research on neural reasoners.

Neural Algorithmic Reasoning Without Intermediate Supervision
Gleb Rodionov
Liudmila Prokhorenkova
Yandex Research
Yandex Research Amsterdam, The Netherlands
Moscow, Russia
rooiionovgle@@yadeee-eee.
aarroumovallllyandeee teetyandee-team....
Abstract
Neural algorithmic reasoning is an emerging area of machine learning focusing building models that can imitate the execution of classic algorithms, such sorting, shortest paths, etc. One of the main challenges is to learn algorithms that --i-tii-iittiittionn data, in particular with significantly larger input sizes. Recent work on this problem has demonstrated the advantages of learning algorithms
are able generalize
giving models access to all intermediate steps of the original algorithm. In this work, we instead focus on learning neural algorithmic reasoning only from the input-output pairs without appealing the intermediate supervision. We propose simple but effective architectural improvements and also build a self-supervised objective that can regularise intermediate computations of the model without access to the algorithm trajectory. We demonstrate that our approach is competitive to its trajectory-supervised counterpart on tasks from the CLRS Algorithmic Reasoning Benchmark and achieves new state-of-the-art results for several problems, including sorting, where we obtain significant improvements. Thus, learning without intermediate supervision is promising direction for further research on neural reasoners.
Introduction
Building neural networks that can reason has been a desired goal for decades of research. While the ability reason be defined and measured in various ways, most of them represent challenge for current models, solving which can allow the community to use such models for complex real-world problems. Significant progress has been achieved in the reasoning abilities of language models (Touvron et al. 2023 Hoffmann et al. 2022), where reasoning can be described as the ability to answer questions solve logical and mathematical problems in formal (Polu and Sutskever 2020) or natural language (Lewkowyez et al.) [2022] Jiang et al.) 2023). However, the essential part of this progress is inseparable from the large scale of such models, which is needed abstract over complex language structures (Wei et al. 2022).
Recent research considers classic algorithms as universal tool to define reasoning simple instances like sets of objects and relations between them, making algorithmic modeling a popular domain for testing neural networks and highlighting current reasoning limitations of existing architectures
(Zaremba and Sutskever, [014] Kaiser and Sutskever 20133] Trask et al. 2018
Kool et al. 2019
Dwivedi al. 2023 Yan et al. 2020 Chen al. 2020b))
Neural algorithmic reasoning an area of machine learning focusing on building models that execute classic algorithms (Veličković and Blundell, (021). The motivation is to combine the advantages of neural networks (processing raw and noisy input data) with the appealing properties of algorithms (theoretical guarantees and strong generalization). Assuming that we have neural network capable of solving a classic algorithmic task, we can incorporate into a more complex
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

pipeline and train end-to-end. For instance, if we have neural solver aligned to the shortest path problem, it can be used as a building block for routing system that accounts for complex and dynamically changing traffic conditions.
The main challenge of neural algorithmic reasoning is the requirement of out-of-distribution (OOD) generalization. Since algorithms have theoretical guarantees to work correctly on any input from the domain of applicability, the difference between train and test data distributions for neural algorithmic reasoners is potentially unlimited. Usually, the model is required to perform well on much larger input sizes compared to the instances used for training. This feature distinguishes neural algorithmic reasoning from standard deep learning tasks: neural networks are known to perform well on unseen data when it has the same distribution as the train data, but changes in the distribution may significantly drop the performance. This challenge is far from being solved yet; for example, as shown by Mahdavi eet al.) (2023), even achieving the almost perfect test score, neural reasoners can rely on implicit dependencies between train and test data instead of executing the desired algorithm, which was demonstrated by changing the test data generation procedure.
The area of neural algorithmic reasoning has been developing rapidly in recent years, and graph neural networks (GNNs) have proven their applicability in this area in various contexts. In particular, Veličković et al. (222)) and Xu et al. (020)) analyzed the ability of GNNs to imitate classic graph algorithms and explored useful inductive biases. Further, Dudzik and Velicković (2022) showed that GNNs align well with dynamic programming. Also, several different setups demonstrated that neural reasoners benefit from learning related algorithms simultaneously. explicitly (Georgiev and
Li6 2020 Numeroso et al. 2023) or implicitly (Xhonneux et al. [021] [barz et al., 2022) reusing common subroutines. signifieant step forward in developing neural algorithmic reasoners was made with the proposal of the CLRS benchmark (Veličković et al. (022) that covers 30 diverse algorithmic problems. In this benchmark, graphs are used as a general tool to encode data since they straightforwardly adapt to varying input sizes.
An important ingredient of the CLRS benchmark is the presence of hints that represent intermediate steps of the algorithm's 's execution. With hint- based supervision, the model is forced to imitate the exact trajectory of a given algorithm. Such supervision is considered a fundamental ingredient for progress in neural algorithmic reasoning (Veličković et al., (002)..
In this paper, we argue that there are several disadvantages of using hints. For example, demon- strate that the model trained without hint supervision has a greater tendency to do parallel processing, thus following the original sequential trajectory can be suboptimal. We also show that while the model trained with supervision on hints demonstrates the alignment to the original algorithm trajectory, it could not capture the exact dependency between the hint sequence and the final result of the execution.
Motivated by that, we investigate whether it is possible to train a competitive model using only input-output pairs. To improve OOD generalization, we propose several modifications to the standard approach. As a first step, we propose a simple architectural improvement of the no- no-hint regime that makes it better aligned with the hint-based version and, at the same time, significantly boosts the performance compared to the typically used architecture. More importantly, for several tasks, we add contrastive regularization term that forces similar representations for the inputs having the same execution trajectories. This turns out to be a useful inductive bias for neural algorithmic reasoners.
The experiments show that our approach is competitive with the current state-of-the-art results relying on intermediate supervision. Moreover, for some of the problems, we achieve the best known performance: for instance. get the Fl score 98.7% for the sorting, which significantly improves over the previously known winner with 95.2%.
We hope our work will encourage further investigation of neural algorithmic reasoners without intermediate supervision.
2 Background
Our work follows the setup of the recently proposed CLRS Algorithmic Reasoning Benchmark (CLRS) (Veličković et al. 2022). This benchmark represents set 30 diverse algorithmic problems. CLRS proposes graphs as general way to encode data since any particular algorithm can be expressed as manipulations over a set of objects and relations between them. For example, for the Breadth- first search (BFS), the input represents the original graph with masked starting node, and the output
2

---

Hr
Hint prediction
prediccciinoon
prediction
prediction
Hintsfort-1
Hints
Hints
Figure I: Hints usage diagram for the Bubble sort. Green lines represent the encoders, and red the decoders. The dotted lines illustrate the supervision. Hints at each step represent the current order of the elements and two indicated elements for the last comparison.
of the algorithm (traversal order of the graph) can be encoded via predicting the predecessor node for any node. For non-graph tasks, CLRS proposes an approach derive the graph structure. For example, for sorting algorithms, each element of the array can be treated as separate node, endowed with position scalar input for indexing, and the output is encoded as pointer from each node to its predecessor in the sorted order.
important component of the CLRS benchmark hints, which represent the decomposition of the algorithm's ' execution into intermediate steps. Each hint contains all the necessary information define the next execution step. For example, for Bubble sort, hint encodes the current order of the elements and two indexes of the elements for the next comparison. We note that each algorithm defines a unique way of solving the problem, which can be learned separately.
Each transition between the consecutive trajectory states defines a new task, which can be learned separately or simultaneously. Recent work has demonstrated the utility of the encode-procedd pronee--pooesseecdeee paradigm for learning the whole trajectory of the algorithm at once (Veličković et al. 2022 [barz
al. 2022) (Figure D At each time step all input data are encoded with simple encoders
nigh-dimensiones (we use d = 128) latent space, producing vectors (xt) E BR*d representing nodes,
(et)) E Rexaxx edges, and (g') E IRd graph features, where n is the task size (nodes count).
Then, processor, usually graph neural network (Veličković et al. 2022 Ibarz et al. 2022) transformer (Diao and Loynd 2023 Mahdavi et al. 2023), operates this latent space, executing a transition the next step. The processor computes the hidden states hf for the nodes (and optionally edges) from the combination of the encoded inputs and hidden states h from the previous step, where h. O. After this transition, the latent vectors are decoded to predict the hints for the current step. Then, the current step hints prediction can be discarded or fed back into the processor model for the next step, similarly to the encoded input, allowing the model to follow the predefined dynamic of the hints sequence.
At the last step of the trajectory, decoders project the output prediction to the problem. Similarly to the encoders, the decoders rely mainly on a linear layer for each hint and output. The decoders are also endowed with a mechanism for computing the pairwise node similarities when appropriate, which allows one to unify method for predicting node-to-node pointers for graphs with different sizes. We refer to Veličković et al. (2022) for a more detailed explanation. It was also recently shown that the processor can be shared across tasks and thus reuse algorithmic subroutines (lbarz et al. 2022].
Another recent work (Bevilacqua et al. 2023) shows significant improvement in size generalization via a novel way of using hints called Hint-ReLIC. The method comes from the observation that for some algorithms, there exist multiple different inputs on which certain steps of the algorithm will perform identically. Designing causal structure on the algorithm's trajectory, the authors have demonstrated that the execution of each step depends only on small part of the current snapshot, meaning that the invariance under changes of irrelevant parts can serve as a regularization for the model. For example, the Bubble sort each step compares only two elements of the array, any

---

changes of other elements or adding new elements to the array should not affect the execution of the given step. Such regularization forces better alignment of the model to the relevant computations. improving size generalization. Invariance is forced via self-supervised objective which is modified version of the ReL.C algorithm (Mitrovic et al. 2
3 Neural algorithmic reasoning without hints
Motivation There are several disadvantages of using hints in neural algorithmic reasoning. First, hints need to be carefully designed separately for each task and each particular algorithm. This may require a significant amount of human effort: c.g., the hint at the next step should be predictable by the hint from the previous step using single round of the message passing (Veličković et al. (022). Moreover, as this example shows, different model architectures may benefit from differently designed hints: for processor based on graph transformer, the optimal hints can be different. MMhdavi et al. ) demonstrated the comparison of the performances for different GNN architectures depending hint usage, showing that for some algorithms the question of using hints is faced by each architecture separately.
As discussed above, hints force the model to follow particular trajectory. While this may help the interpretability and generalization of the trained model, following the algorithm's 's steps can be suboptimal for neural network architecture. For instance, may force the model to learn sequential steps, while parallel processing can be preferable. Moreover, a model trained with direct supervision on hints could not necessarily capture the dependencies between hints and the output of the algorithm.
To demonstrate this disadvantage with a practi- cal example, we compared the dynamics of the predictions for the model trained on the Inser- tion sort problem depending on hint usage, see Figure 2 For each model, we evaluated the in- termediate predictions after each processor step and compared them with the final predictions of the model. We note that for hint-based models we have two decoders for predictions: the hint decoder and the output decoder, both of which can be used for this purpose.
10
0.6
0.4
Baseline model, hint prediction model, output prediction
Model without hints, output prediction
We see that the model trained with supervision on the trajectory for Insertion sort struggles to learn the relation between the intermediate pre- dictions of the pointers and the output predic- tions (blue line). In other words, the model potentially can consider the hint sequence (and even each transition between hints) as separate task, not related to the output of the algorithm directly.
10
30
40
60
Steps
Figure 2: The ratio of pointers predicted after given number of steps which are equal to the final model output. Insertion sort task, test data (64 nodes).
We also see that the execution trajectory for the models with hints inherits some sequential order of intermediate updates (orange line). The model without hints has much stronger tendency to do parallel processing - almost output predictions are obtained on the first steps of the execution.
Finally, we note that if model is not restricted to a particular trajectory, it may potentially learn new ways to solve the problem, and thus by interpreting its computations, may get new insights into the algorithms' design.
Simple improvements of the no-hint mode Let us describe several changes to the no-hint mode that make the comparison with hint-based methods more straightforward and, at the same time, significantly boost the performance compared the typically used no-hint regime.
First, we propose an architectural modification of the no-hint mode that makes its computational graph more similar to the standard regime with hints. As described in Section 2 in the default implementation of the encode-pree pooodd-proees-deoode paradigm the CLRS benchmark, all hint predictions from the current step fed back to the processor model (as illustrated in Figure I]. Thus, in addition

---

Helpredi
Leterstie
Hebsforte
(a) Standard no-hint mode
(b) Hints supervision
(c) Proposed no-hint mode
Figure 3: One step of the algorithm's execution depending on the different hint usage modes for the Bubble sort algorithm.
to the intermediate supervision, hint predictions are also used in the next computational step. So, the transition of the hidden states from step step uses not only the encoded inputs and hidden states h but also the current hint predictions, which are derived from the hidden state via additional computations.
However, for the no-hint version, as there predicted and not fed back to the model. While this approach seems natural, it leads to significant computation graph differences compared to the model with hints. We note that the computation of hint predictions and encoding them to the processor in the encoded-decoded mode can expressed additional message- passsing step over the nodes, edges, and graph features (which can differ the processor, if any). Thus, it can reasonable to preserve
intermediate steps supervise, hints are not
from the message- message-passing passing procedure this part even in the no- no-hint regime. So, propose mode but do not supervise hint predictions, allowing the model to construct useful representations and use them in the next steps. This modification makes the computation graphs similar and also noticeably improves the performance of the no-hint regime. We refer to Figure for the illustration of the proposed changes.
the no-hint model in the encoded- decoded")
Second, we note that all algorithms (and, therefore, hint sequences) assume sequential data represen- tation. However, for some algorithms, only the intermediate steps depend on the position encoding of nodes, while the outputs are independent of the position scalars. For example, the output for the sorting algorithms is represented as pointers to the predecessor in the sorted order (and the node with the minimal value points to itself). Positions are only needed to tie-break identical elements, but due the data generation in the CLRS benchmark, such collisions do not occur. To avoid unnecessary dependency of models on the position encodings, we do not use them the output is independent of positions. For some algorithms, however, the positions search traversal depends on vertex indexing. Thus, we keep the position scalars only for the DFS, SCC, and Topological sort problems.
needed: for instance, the Depth-first
Self-supervised regularization
4.1 Reducing the search space
In this section, we propose a self-supervised objective that can regularise intermediate computations of the model by forcing similar representations for the inputs having the same execution trajectories. The proposed technique can be directly applied to the following algorithms of the CLRS benchmark: Minimum spanning tree algorithms, Sorting, Binary search, and Minimum.
As we mentioned the previous section, any predefined trajectory can be suboptimal for given architecture. To design alternative approach, make observation that helps combine the advantages of learning algorithms only from input-output pairs with inductive bias improving the size generalization capabilities of the models.
'We note that for models without hints there is no abstract meaning for encoding/decoding of the intermediate states, such wording only for consistency with bint-based models.
5

---

Output prediction
Apunthmiaaly rpoit
Fonding airilanty intermaciete mpieseetations equi rppute
Qut prediction
Algorthenically coneeiatieeen iipurts
Outout prediction
4
Figure Self-supervised regularization for neural algorithmic reasoning.
In the absence of hints, the model does not have any knowledge about the algorithm's 's trajectory and its intermediate steps and potentially can align new way of solving the problem. Hence, obtaining any information about underlying computations of the model, for example, detecting the part of the data irrelevant the current step. non-trivial. Moreover, given the parallel nature of modern model architectures, all nodes can potentially be used at all steps. Thus, we propose constructing such a pair of different inputs that every step of a given algorithm the same for both inputs.
aligg
Although constructing such pairs for an arbitrary algorithm is not always trivial, the underlying combinatorial structure of some tasks allows us describe the properties of the desired algorithm. Such properties can reduce the search space of the model while remaining in the wide range of possible algorithms, which can solve the given problem.
For example, any comparison sort has the same trajectory for any pair of arrays with the same relative order of its elements. We clarify that we consider the sequence of the intermediate relative orders of the elements as a trajectory, not the array values themselves. A less trivial example is the minimum spanning tree problem. A wide range of algorithms (Prim (9957). Kruskal (1956), etc.) have the same execution trajectory on graphs with fixed topology (graph structure) and different weights on edges if the relative order of the corresponding edge weight is the same. As the set of all subsets of edges that do not contain a cycle forms a matroid (Harary) 1969), any greedy construction of the tree would lead the optimal result. This observation allows us weights, not the weights themselves. We note that the CLRS benchmark considers the set of edges in the tree (a mask edges) as the result of the algorithm, not the total weight of the constructed tree.
only the relative order of the edge
One important remark is that for two different inputs, the exact matching of all the intermediate steps is generally more strict condition than the matching of the result. For example, consider Kruskal's algorithm for the minimum spanning tree problem. The first stage of this algorithm is sorting the edges by their weight. The edges are then greedily added to the disjoint set of independent edges until the spanning tree is constructed. Thus, an edge with a weight that is larger than any weight from the minimum spanning tree does not affect the result but can cause the different states of the algorithm after the sorting stage.
Now we describe our idea more formally. Given a problem P X' + y, we define set A of the algorithms solving this problem, and a decomposition of the set of inputs X' = U to the disjoint equivalent classes, such that for every two elements X,, E X's from the same class Xx. all algorithms from A produce the same exccution trajectory. We note that the properties of the input data that we mentioned above produce such decomposition of the input spaces for the specified tasks. Now we can use this to reduce the search space for our model to the space of functions acting the same way on any pair of inputs from the same equivalence class, being invariant under input t changes that do not affect the algorithm's 's trajectory. Our idea is illustrated on Figure 4
In contrast to HiC,. we do not decompose each snapshot of the execution to the relevant and non-relevant nodes, as the dynamic of such decomposition is defined by the hints sequence and thus may inherit its disadvantages. Instead, we highlight the property of the whole input of the algorithm.

---

This idea allows us to give the model additional useful signals about the data without any explicit or implicit enforcing to any predefined dynamic, which can be suboptimal for a particular model architecture.
4.2 Adding contrastive term
Now, let us describe how classic contrastive learning techniques can be applied for this purpose. As mentioned above, for given task, our goal is to learn representations of intermediate steps I E [1.. ......77 7). which are similar for any pair of inputs from the same equivalence class. One natural way to do this is to build contrastive objective aimed at solving the instance discrimination task
(Wu et al. 2018 Chen et al. 2020a Mitrovic et al. 202T
We note that there are different ways to define an instance. For example, one may consider the whole exccution of the algorithm choice. In this case, all the intermediate states of all the nodes can be used as a single instance. However, as the algorithm's 's execution can be described as a step-by-step more fine-graine grained approach is suitable, defining each node representation at each step as separate instance. We focus on the latter option.
single classification task, where each class represents trajectory
rerision-maaing process,
Let us denote by Xx the class of equivalence for X E X' which is a set of valid augmentations for X, under which the similarity of representations for the corresponding nodes each step can be directly enforced. For this purpose, we use the following contrastive regularization term:
xxp(o((((X.0,
- EE Σ XEX X.EXx
log
R Σ
Eep(o(f((X, 1). f((Xa.)))) 5=1
f(
where Je(X, i) denotes the representation of i-th node (i E n1)..n),, obtained at step 4, and 6(x, v) denotes a comparison function for the obtained representation, which we implement as ó(x, y) = (o(x),(()) where g is a fully-connected neural network. We compute this term for each step t E [1... and add it to the output loss.
We note that this term is similar to the contrastive part of the Hint-ReLIC objective with some differences. First, in Hint-ReLIC, certain hints are contrasted (such as intermediate prediction of the predecessor in the sorted order for sort algorithms, namely pred_ h) to be invariant under changes that affect only those parts the data, which are not included to the current step of execution. Such an approach allows for highlighting the importance of different nodes at different execution steps. Our method does not specify any additional details about intermediate computations, so the whole latent representations of each node state are forced to be invariant under valid augmentations. Another difference is in the augmentations choice. While Hint-ReLIC compatible with a wide range of interventions, such connecting the underlying graph to any randomly generated subgraph, our augmentations for X are defined by the equivalence class Xx in which by design all the inputs have the same size. To summarize, we propose different way of applying the standard contrastive learning technique to the algorithmic reasoning setup. While Bint-ReLIC demonstrates an advanced way to align the model to the particular trajectory of the execution, our method can be applied as additional regularization to the model, which does not favor any particular trajectory from the wide range of possible algorithms.
5 Experiments
In this section, we evaluate the performance of the proposed modifications to the no-hint mode and test the impact of contrastive regularisation on OOD generalization. To deepen our analysis, we also conducted additional experiments, evaluating the impact of the step count and demonstrating the influence of the contrastive term on similarity of trajectories for algorithmically equivalent inputs.
5.1 Experimental setup
Baselines We compare our approach with several forms of hint usage. First, we consider the standard supervision of the hints, denoted as Baseline (Ibarz et al. 2022). Then, No hint is the model that completely ignores the hint sequence. Finally, Hint-ReLIC utilizes advanced way of using the
7

---

Table Training details and model hyperparameters
Train sizes
4, 7, 11, 13, 16
Validation size
16
Test size
64
Optimiser
Adam
Learning rate
0,001
Train steps count
10000
Evaluate each (steps)
50
Early-stopping patience (steps) Batch size
500
32
Processor
Triplet-GMPNN
Hidden state size
128
Number of message passing steps per processor step
1
hints (Bevilaqqua et al., 2023). All models the Triplet-GMPNN architecture proposed by Ibarz et al. 2022).
Model and training details We train our model using the Adam optimizer with an initial learning rate 1) = 0.001, with batch size 32, making 10,000 optimization steps with early stopping based on the validation performance. Our models are trained on single A 1100 GPU, requiring less than 1 hour to train. We report the results averaged across five different seeds, together with the standard error. We report all hyperparameters in Table !
We note that our proposed modification of the no-hint mode allows for the use any type of representation replacing the hint prediction. For example, each sorting algorithm in the CLRS benchmark has a unique description of the intermediate computations inspired by the algorithm itself. Each step of the Bubble sort algorithm is described by the current elements order and two indexes for the current comparison. At the same time, hints for the Heapsort have a more complex structure that defines the current state of the heap and other details (Veličković et al., 2022). Such differences in the specifications of the algorithms produce differences in computational graphs for models trained for Bubble sort and Heapsort. While the proposed modification of the no-hint mode leaves freedom for such architecture choices, wC consider search the optimal specifications (description of the representation of the input, intermediate steps, and output) for each algorithm beyond the scope of our work. Moreover, we do not use the original specifications for the hints from the CLRS benchmark, as their design (combination of types of hints) can potentially align the model to the original algorithm even without the supervision of the hints. Thus, we only construct a single type of intermediate representations to demonstrate the advantage of the proposed modification in the simplest way. We use a latent representation of type mask located at edges and use them for all the algorithms.
We also need to set the trajectory length (the number of message-passe passing steps) for our model. For the regime with hints, the number of steps can obtained from the original trajectory. However, for the no-hint version, there are several options: take the number of steps from some algorithm, use a predefined steps count, or add a separate model that predicts the algorithm execution is ended. We use the steps count linearly depending the input size, with factors and 5 for array and graph problems, respectively.
Data augmentations Recall that our proposed regularisation technique aimed at forcing the invariance of the execution under the choice of the elements from the same equivalence class. To achieve this, we augment the inputs by sampling from the same data distribution, preserving the relative order of the elements for the array-based problems and the relative order of the corresponding edges for graph problems. We generate one augmentation for each data point.
Dataset
We test our modifications of the no-hint mode on the same subset of the algorithms from the CLRS benchmark as in Bevilacqua et al. (2023). We additionally evaluate our contrastive objective on the Sorting, Minimum, Binary search, and Minimum spanning tree problems.
8

---

Table 2: Comparing performance for different hint usage modes. standard error for the test micro-F1 score across different seeds.
The table shows the mean and
Algorithm
No hint
Baseline
Hint-ReLLn
No hint (ours)
Add contr. (ours)
Artic, points
81.97 5,08
88.93 1.92
98.45 0.60
94.55 2.47
Bridges
95.62 = 1.03
93.75 2
99.32 + 0.09
98,91 + 0.47
DFS
33.94 # 2.57
39.71 # 1.34
34.52 + 1.17
SCC
57.63 0.68
38.53 # 0.45
76.79 3.04
66.38 + 7.12
Topological sort
84.29 = 1.16
87.27 2.67
96.59 # 0.20
94.58 + 0.60
Bellman-Fooe
93.26 + 0.04
96.67 + 0.81
95.54 + 1.06
95.25 + 0.58
BFS
99.89 # 0.03
99.64 0.05
99.00 =
99.95 + 0.04
DAG SP
9.62
8.71
0.26
98.18 = 0.99
Dijkstra
95.01
93.41
0.57
96.97 = 0.32
40.80 # 2.90
46.51 1.30
42.16 4.84
MST-Kruskal
92.28 0.82
91.18 1.05
96.01 =
92.89 0.92
93.15 # 1.01
MST-Prim
8
87.64 1.79
87.97
85.70 1.44
85.20 + 1.77
Insertion
75.28 7..29
92.70 1.29
90.67 + 8.22
98.74 1.12
Bubble sort
8
79.87 6.85
92.94
90.67 + 8.22
98.74 # 1.12
Quicksort
70.53 = 11.59
9.96
90.67 + 8.22
98.74 # 1.12
Heapsort
68.50 # 2.81
3
9.21
90.67 + 8.22
98.74 1.12
Binary Search
93.21 1.10
7..60
89.68 2.13
85.29 + 4.52
87.12 + 2.23
Minimum
99.24 + 0.21
97.78
99.37 = 0.20
99.98 + 0.02
99.99 + 0.01
Table Comparing test performance of the no-hint (ours) model on the sorting problem for different processor step counts.
Steps count
Test score
Linear (same as for Insertion sort from CLRS)
90.67 + 8.22
Quadratic (same for Bubble sort from CLRS)
90.97 8,03
Linearithmic (same as for Quick sort from CLRS)
91.05 + 8.17
Linearithmic (same as for Heap sort from CLRS)
89.66 7.40
5.2 Results
Table compares the performances of several hint usage modes, including those proposed in Sec- tions and We first note that modification of the no-hint mode significantly improves the performance compared to the standard No hins version, achieving the best-known results on the BFS, DAG shortest paths, and Minimum problems. For instance, for sorting, the performance increases from 68.5%-81.37 for No hint to 90.7% for our version. Here we note that such a spread per- formance between different sorting algorithms in the standard no-hint mode is caused by different step counts: No hint does not rely on hints, but uses particular algorithm when setting the number of message-passing steps. In contrast, our modification uses pre-defined step count depending on the input size. Also, compared to baseline supervision on hints, our no-hint model yields better performance on 14 out of 18 tasks. To conclude, our simple modifications of the no-hint mode already demonstrate competitive performance on most of the problems.
The last column of Table 2 demonstrates further improvements obtained due to the proposed self- supervised regularization. In particular, with this regularization, we achieve the best results for sorting (98.7%), significantly outperforming the existing models.
We also evaluate the effect of the step count for the sorting problem, see Table For our experiments, we used the same step count as the Baseline model for Insertion sort. We demonstrate that mimicking the step counts from other baseline models still shows the advantages of the proposed no-hint changes.
"The Hint-ReLLe ReLIC results for DFS are not reported since Bevilacqua et al. with simpler technique.
2023 achieve the perfect score

---

Finally, we show that for the sorting prob- lem, the proposed contrastive term forces the model to have similar representations for inputs from the same equívalence class, as intended. For this purpose, we took dif- ferent pairs of equivalent inputs and for calculated each step of the execution the following ratio: if we take one node from one input and take the closest node from the augmented imput, what is the prob- ability that the closest node will represent the element with the same relative order. Figure shows that while the model with- out the contrastive term (green line) is able to mainly rely the relative order, contrastive term is forcing much more con- fidence (and speed) in achieving that prop- erty.
10-
Ratio
02-
1.
O. (Model without contrastive loss)
0.0
Steps
Figure 5: Influence of the contrastive term on similarity of the representations of equivalent inputs depending on weight factor of the contrastive term. Insertion sort problem, test data (64 nodes).
Limitations
In this paper, we propose improvements the no-hint regime for neural algorithmic reasoning and method to regularise intermediate computations without enforcing the model to any predefined algorithm trajectories. While this approach seems natural and promising, some limitations remain.
Our contrastive learning approach applies to the limited set of problems. While for many algorithms is possible construct the inputs that produce the same trajectory, sometimes it can be non-trivial. For example, for the shortest path problems, linear transformation of each weight does not affect the resulting paths and all intermediate computations (such the order of inserting nodes the heap for the Dijkstra's 's algorithm (Dijkstra 1959). However, such augmentations are not informative due to the layer normalization, and constructing more diverse examples represents a separate task.
While the proposed self-supervised regularization aims to reduce the search space for the model, it does not give a model strong inductive bias towards underlying computations. We believe that more advanced techniques can be useful for algorithms with long sequential reasoning, such as the minimum spanning tree. Developing stronger inductive biases promising direction for future research.
For self-supervised regularization, we augment the inputs by sampling from the same data distribution. While this gives signal to the model that it should account only for the relative order, this signal can be more significant if we different distributions. Investigating the effect of diverse data distributions on the performance of neural algorithmic reasoners is good subject of a separate study.
7 Conclusion
In this work, we propose several improvements to learning algorithms without intermediate supervi- sion. We also demonstrate the possibility of regularising all computational steps the model without enforcing it to any predefined algorithm trajectory. The obtained models outperform previous no- no-hint models and show competitive performance with models that have access to the entire algorithm trajectory. We also achieve new state-of-the-an of-the-art results several tasks. In particular, considerable improvement obtained for the sorting algorithms, where we get the score of 98.4%.
We consider neural algorithmic reasoning without intermediate supervision promising direction for further advances in neural algorithmic reasoners.
10

---

References
B. Bevilaequa, K. Nikiforou, B. Ibarz, I. Bica, M. Paganini. C. Blundell, J. Mitrovic, and P. Veličković. Neural algorithmic reasoning with causal regularisation. In International Conference on Machine Learning, 2023.
T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. simple framework for contrastive learning of visual representations. In International Conference Machine Learning, pages 1597-1607. PMLR, 2020a.
Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems, 33:10383-10395, 2020b.
C. Diao and R. Loynd. Relational attention: Generalizing transformers for graph-structured tasks. In International Conference Learning Representutions, 2023.
E. W. Dijkstra. A note two problems in connexion with graphs. Numerische Mathematik, 1: 269- 271, 1959.
A. Dudzik and P. Veličković. Graph neural networks are dynamic programmers. Advances in Neural Information Processing Systems, 35:20635-20641 2022.
V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43): 1-48, 2023.
D. Georgiev and P. Lió. Neural bipartite matching. arXiv preprint
2020.
F. Harary. Graph theory. 1969.
J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. d. L.. Casas, L. A. Hendricks, J. Welbl, A. Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203. /5556, 2022.
B. Ibarz, V. Kurin, Papamakarios. Nikiforou, M. Bennani. Csordás, A. J. Dudzik, M. Bošnjak, A. Vitvitskyi, Y. Rubanova, et al. A generalist neural algorithmic learner. In Learning on Graphs Conference. PMLR, 2022.
A. Q. Jiang, Welleck,
Zhou, Lacroix, Liu, W. Li, M. Jamnik, G. Lample, and Wu. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. In International Conference on Learning Representations, 2023.
E. Kaiser and Sutskever. Neural GPUs learn algorithms. arXiv preprint arXiv: 2015.
W. Kool, H. van Hoof, and M. Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
J. B. Kruskal. On the shortest spanning subtree of graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48-50, 1956.
A. Lewkowyez, A. Andreassen, D. Dohan, E. Dyer, H. Michalewski, V. Ramasesh, A. Slone, C. Anil, Schlag, T. Gutman-Solo, al. Solving quantitative reasoning problems with language models. Advances in Neural Information Processing Systems, 35:3843-3857, 2022.
S. Mahdavi, K. Swersky, T. Kipf, M. Hashemi, C. Thrampoulidis, and R. Liao. Towards better out-o--distribution generalization of neural algorithmic reasoning tasks. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Mitrovic, B. McWilliams, C. Walker, H. Buesing, and C. Blundell. Representation learning via invariant causal mechanisms. In International Conference on Learning Representations, 2021.
D. Numeroso, D. Bacciu, and P. Veličković. Dual algorithmic reasoning, In International Conference on Learning Representations, 2023.
S. Polu and I. Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03393 2020.

---

R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401, 1957.
H. Touvron, Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, al. Llama: Open and efficient foundation language models. arXiv preprint 13X1122302.1371,, 2023.
A. Trask, F. Hill, S. E. Reed, Rae, in Neural Information Processing Systems, 31, 2018.
C. Dyer, and P. Blunsom. Neural arithmetic logic units. Advances
Veličkovié and C. Blundell. Neural algorithmic reasoning. Patterns, 2(7):100273,, 2021.
Veličković, Ying. M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2020.
P. Veličković, A. P. Badia, D. Budden, R. Pascanu, A. Banino, M. Dashevskiy, R. Hadsell, and C. Blundell. The CLRS algorithmic reasoning benchmark. International Conference on Machine Learning, pages 22084-22101 PMLR, 2022.
J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler, E. H. Chi, T. Hashimoto, O. Vinyals, P. Liang, J. Dean, and W. Fedus. Emergent abilities of large language models. Transactions Machine Learning Research, 2022. ISSN 2835-8856.
Z. Wu, Y. Xiong, S. X. Yu, and D. Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 3733-3742, 2018
L.P. Xhonneux, A.II Deac, P. Veličković, and J. Tang. How to transfer algorithmic reasoning knowledge to learn new algorithms? Advances in Neural Information Processing Systems, 34: 19500-19512, 2021.
K. Xu. J. Li, M. Zhang. S. S. Du, K.-i. Kawarabayashi, and S. Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020.
Y. Yan, K. Swersky, D. Koutra, P. Ranganathan, and M. Hashemi. Neural execution engines: Learning to execute subroutines. Advances in Neural Information Processing Systems, 33:1 33:17298-17300 2020.
W. Zaremba and I. Sutskever. Learning to execute. arXiv preprint arxiv: 141..4610, 2014.
12


Reviews:
[{"review_id": "A4kloD2vZ0", "reviewer": "Reviewer_Sqsb", "summary": "The paper focuses on neural networks that learn to execute algorithms, using the CLRS benchmark. It tackles the case of learning to execute when there are no hints available (no access to intermediate steps of the algorithm's trace). To do that, it proposes two modifications: the first is architectural, which is maintaining the latent representation of the current step and using it for the next step, which previous no-hint architectures discard and architectures using the hints use to decode the predicted hint and compute an additional loss by comparing with the ground-truth hint. The second one proposes a contrastive loss aimed to reduce the function search space, by using the following invariance: inputs that have the same (algorithmic) trajectory (belonging to the same equivalence class should have the same representation. The two modifications improve on the no hints baseline and in many cases match the model with hints.", "questions": "Please see weaknesses section.", "limitations": "The authors have included a discussion on the limitations of the proposed method.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "As the strengths outweigh the weaknesses of this paper, I recommend acceptance in its current form. I would be happy to increase my score if some of the weaknesses are addressed.\n\nThe strengths of the paper include great clarity and sensible proposals to improve no-hint performance, such as maintaining a similar computation graph and using invariances to reduce the search space in lack of stronger inductive biases. Moreover, the evaluation is thorough and the improvements brought show a clear step in the direction of accurately learning algorithms without hints.", "weaknesses": "I think the paper would be greatly strengthened by improving the motivation towards doing no-hint learning. As the performance of the proposed models is not consistently better than that using hints, it is likely that at the moment, this is not enough evidence to convince towards porting to no-hint neural algorithmic reasoners for polynomial algorithms. \n\nOne way to improve this would be to improve it empirically (considering other invariances, introducing stronger inductive biases, extending the number of algorithms it is applicable to—perhaps applying the model to NP-hard problems, where having hints is not scalable because of exponential-time complexity), or providing ablation studies of some of the initial motivating points: abilities of no-hint architectures to do parallel processing or new ways/insights of learning to solve the problem.  I also think that the argument of human effort should be further clarified in the limitations — while hints are generated using the algorithm's implementation therefore they come \"for free\" with the dataset generator, finding augmentations requires understanding of the algorithm's invariances, which is also based on human effort.\n\nIt would be useful if a few phrases could be clarified: \n- “We note that the computation of hint predictions and encoding them to the processor in the encoded-decoded mode can be expressed as an additional message-passing step over the nodes, edges, and graph features” could be made clearer by including information on how hints are computed\n- \"a latent representation of type mask located at edges” is not immediately obvious\n- it is mentioned that the setup is the same as in previous work, but restating the training and testing regime (such as size of inputs) would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and constructive comments!\n\nWe would like to additionally support our motivation towards investigating no-hint reasoners with an experiment (Fig. 1(a) from the global response), which demonstrates the execution trajectories for sorting models. We discuss our observations in the [global response](https://openreview.net/forum?id=vBwSACOB3x&noteId=UUd9q6foXC). In particular, we observe that models with hints may struggle to learn the relation between the intermediate predictions of the pointers and the output predictions. Also, the model without hints has a much stronger tendency to do parallel processing. Such insights combined with common intuition about the redundancy of over-engineering (as models usually find solutions that are more aligned with their architectures) represent the core of our motivation.\n\nAlso thank you for your notes on human effort for hints/augmentations - we definitely agree that finding augmentations is not trivial and requires a deep understanding of the algorithm and we will describe it in the limitations section. However, we also note that hints don’t come “for free” with dataset generator, at least, the useful ones: Veličković et al. (2022) noted some difficulties with hint generation, such as compression (simple ‘for’ loops can be described as a single step for parallel architectures) or ability to predict the next hint from the current one, which can represent a separate task for different architectures. Also, the same hints can be encoded/predicted differently, which can affect the model performance. While we believe that for most of the tasks and architectures useful hint sequences can be found, the comparison between simple supervision on hints and no-hint mode (“Baseline” and “No hints (ours)” columns in Table 1 of the paper) shows that for most of the problems (14 of 18) no-hints performance is better (or better hints are needed). We also note that invariants/augmentations from the paper need to be discovered/developed once for a task, while helpful hints may need to be engineered separately for different architectures (line 131 in the paper). \n\nWe also thank the reviewer for noticing parts that could be clarified in the text, we will describe them in more detail in our updated version. However, we are happy and open to clarifying something during the discussion period if needed.\n"}, {"review_id": "cZV5hkRNYb", "reviewer": "Reviewer_P3vy", "summary": "This paper proposes a novel method for Algorithmic Reasoning without intermediate supervision. The core idea is to use a self-supervised objective that regularize the internal computations. The authors evaluated the proposed method with CLRS algorithmic reasoning benchmark and achieve state-of-the-art performance on a subset of problems. To the best of my knowledge, the contribution is novel and clear and I recommend acceptance.", "questions": "In the limitation sections, the authors mentioned the issues with requirements for strong inductive bias for the self-supervised regularization scheme. I would appreciate the authors to address the potential concern on computation with respect to search.", "limitations": "As mentioned in Strength, I appreciate authors' detailed inclusion of limitations. I do not think there are major limitations in addition to the said ones given the current content.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well-motivated and relatively easy to follow. The design of regularization for the self supervision scheme is also quite intuitive. The evaluations are comprehensive and seems to support the effectiveness of the proposed approach. I appreciate the specific emphasis of potential limitations.", "weaknesses": "While the main experiment/evaluation is informative, I would appreciate if the authors address some potential ablations such as varying numbers of augmentations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and positive feedback!\n\nFollowing your suggestion, we conducted several ablations (please, see the details in the [global response](https://openreview.net/forum?id=vBwSACOB3x&noteId=UUd9q6foXC)):\n\n- Different augmentations count (Table 3 from the global response). Keeping the batch size equal to 32, we tried different distributions of positive and negative examples for each element in the batch, and used them in the contrastive term, as described in lines 242-248 of the paper. This experiment shows that the method is not sensitive to a particular choice of the augmentations count. For the results in the paper, we used only one positive example, and the other 30 were used as negative examples.\n- Different processor steps count for sorting (Table 2 from the global response). \n- Experimental verification of stronger invariance of the model trained with the contrastive term (Fig. 1(b)).\n\nAnswering your question, we also would like to clarify our thoughts on stronger inductive biases for other problems. The core reason why the proposed contrastive term improves the performance differently for different tasks is that the invariance under order-preserving shifts reduces the space differently for different tasks. For example, learning the sorting algorithm from information about the relative order is almost trivial, while solving the MST problem having the relative order over edge weights still requires additional logic, such as checking cycles between edges, adding edges to the tree, etc., which is not forced by the proposed regularization. That is why we consider developing additional/stronger inductive biases as a promising direction for future work. Does that answer your question? We are happy and open to further discussion on this topic.\n"}, {"review_id": "wYRU57bIWk", "reviewer": "Reviewer_uiKS", "summary": "The paper is about neural algorithmic reasoning, which is the task of building models that can execute classical algorithms. The paper focuses on learning algorithms without intermediate supervision, which means using only input-output pairs and not the steps (hints) of the algorithm. The paper proposes two improvements for this setting: a simple architectural change that makes the model more similar to the hint-based version, and a self-supervised objective that regularizes the model by forcing similar representations for inputs with the same execution trajectories. The paper shows that these improvements lead to competitive or state-of-the-art results on a subset of the CLRS benchmark. The paper argues that learning algorithms without intermediate supervision is a promising direction for neural algorithmic reasoning.", "questions": "1. Table 2 should be merged into Table 1 since only one column is different.\n2. Can you show the latent representation change with the number of steps? Can it correspond to the hint of the algorithm?", "limitations": "Limitations have been discussed by the authors.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. Learning algorithms without intermediate supervision is an important direction for neural algorithmic reasoning.\n2. The contrastive term added is insightful and the corresponding results are promising.", "weaknesses": "1. The fundamental difference between the proposed \"no-hint\" and the original \"no-hint\" has not been stated clearly - the proposed \"no hint\" seems to only have added the hidden layer size or the neural network capacity. If so, the comparison against the original “no-hint” is unfair. Can the authors give a more detailed description of the proposed “no hint” architecture? Also, please list relevant hyperparameters (like size, layers) on the network, and conduct a comparative experiment on the network size. \n2. The “step count” setting in section 5.2 is also confusing: is step count the main reason why the proposed no-hint performs better than the original no-hint?\n3. Table 2 is somewhat confusing: No hint (with our updates) & Binary Search has 93.21 ± 1.10 which is different from 87.12 ± 2.23 or 85.29 ± 4.52  in  Table 1. Also, I think taking the maximum of No hints (ours) and Add contr. (ours) as “ours” in Table 2 is not a good choice since they are different methods proposed.\n4. Although the proposed new contrast item can improve the performance without hints, I doubt that the design of this item is extremely challenging (which might have already been mentioned in section 6 limitations), even more so than obtaining hint data. This is because the design of this item requires a deep understanding of the target algorithm itself and the designer must be an algorithm expert, while obtaining hint data only requires a corresponding executable algorithm. This may deviate from the original intention of “without intermediate supervision” and greatly reduce the actual effectiveness of this paper. \n5. The writing needs to be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thoughtful review! Let us address the raised concerns and questions.\n\n> Can the authors give a more detailed description of the proposed “no hint” architecture?\n\nThe main difference between the original no-hint version and the proposed one is the presence of an encoding-decoding stage after each processor step. The difference is demonstrated in Figure 2 of the paper and motivated by the presence of such stages in hint-based models. Such modifications add a small group of parameters for the encoder (green line in Figure 2) and decoder (red line in Figure 2) (encoder and decoder are single linear layers), keeping the hidden size of the model the same. \n\n> The comparison against the original “no-hint” is unfair\n\nOne of the key points of our paper is that the original (used in previous work) comparison hint vs no-hint, which demonstrated the advantages of using hints, is unfair due to the significant computation graph differences (left and middle parts of Figure 2). Our proposed modification makes the comparison hint vs no-hint more accurate (middle and right parts of Figure 2) and demonstrates the disadvantage of direct hint supervision over the no-hint version for most of the problems (columns \"Baseline\" and \"No-hint (ours)\" in Table 1).\n\n> Also, please list relevant hyperparameters (like size, layers) on the network, and conduct a comparative experiment on the network size.\n\nModel sizes and other hyperparameters are nested from the previous work. To address your question, we specified all the hyperparameters in Table 1 of the [global response](https://openreview.net/forum?id=vBwSACOB3x&noteId=UUd9q6foXC). Also, since our contribution is not a development of new model architecture, we believe that experiments with the network size are orthogonal to our work. However, we added some other ablations to the global response.\n\n> The “step count” setting in section 5.2 is also confusing: is step count the main reason why the proposed no-hint performs better than the original no-hint?\n\nNo, for example, for sorting, we used the same step count as in the original Insertion sort hint trajectory ($n$ steps for input with $n$ nodes). Also, to answer this question, we conducted an ablation on the steps count for sorting (Table 2 from the global response), demonstrating almost the same performance for different step counts. The motivation behind our choice was to avoid an input-dependent number of steps (as, for example, for Heap sort) as it is unnecessary for the no-hint mode. So we made the simplest choice which is applicable to all the problems at the same time.\n\n> the design of this item requires a deep understanding of the target algorithm itself and the designer must be an algorithm expert, while obtaining hint data only requires a corresponding executable algorithm\n\nWe definitely agree that finding augmentations is not trivial and requires a deep understanding of the algorithm and will describe it in the limitations section. However, we also note that hints don’t come “for free” with dataset generator, at least, the useful ones: Veličković et al. (2022) noted some difficulties with hint generation, such as compression (simple ‘for’ loops can be described as a single step for parallel architectures) or ability to predict the next hint from the current one, which can represent a separate task for different architectures. Also, the same hints can be encoded/predicted differently, which can affect the model performance. While we believe that for most of the tasks and architectures useful hint sequences can be found, the comparison between simple supervision on hints and no-hint mode (“Baseline” and “No hints (ours)” columns in Table 1 of the paper) shows that for most of the problems (14 of 18) no-hints performance is better (or better hints are needed). We also note that invariants/augmentations from the paper need to be discovered/developed once for a task, while helpful hints may need to be engineered separately for different architectures (line 131 in the paper). \n\n> The writing needs to be improved.\n\nWe would be grateful if you could clarify which aspects of writing need to be improved, then we will revise the paper accordingly.\n\n> Table 2 should be merged into Table 1 since only one column is different.\n\nOur motivation for including a separate table was to use the aggregated numbers depending on the different hint usage modes, for highlighting the progress of no-hint and hint-based reasoners. While such a comparison of different methods can be imprecise, it serves as a proxy to answering the question: Given fixed model size and different strategies of hint usage, which strategy is preferable for different tasks? We think that combining two tables could be more confusing for readers as some results from Table 2 were taken not from Table 1, for example, for the DFS problem (see the footnote on page 7 of the paper).\n\n> Table 2 is somewhat confusing: No hint (with our updates) & Binary Search has 93.21 ± 1.10 which is different from 87.12 ± 2.23 or 85.29 ± 4.52 in Table 1.\n\nAs we mentioned above, the motivation behind Table 2 was to aggregate the best results depending on hint usage mode. Binary search is the only problem that did not gain performance with our updates, so the best performance without hints is still 93.21 ± 1.10, which is taken from the first column.\n\n> Can you show the latent representation change with the number of steps? Can it correspond to the hint of the algorithm?\n\nThank you for the suggestion! We refer to Fig. 1(a) in the global response. \n\nWe would like to know whether we have answered all the questions and concerns raised by the reviewer. We are happy to discuss further any of the raised weaknesses and questions!\n"}, {"review_id": "qzvRZX4Z4n", "reviewer": "Reviewer_Fw9t", "summary": "This paper addresses the challenge of developing neural networks capable of performing algorithmic reasoning. The paper discusses disadvantages about the use of intermediate hints during training of algorithmic reasoners. The authors propose a regularisation term to ensure that meaningful representations are learnt during the neural execution of algorithms, even when no supervision occurs on intermediate steps.", "questions": "Q1) Can the Authors provide some insights on why the proposed technique only works for sorting algorithms?\n\nQ2) The proposed technique seems likely to be effectively used in conjunction with supervision on hints: have the Authors tried that? Or do the Authors believe that it is not applicable?\n\nQ3) Given that the manuscript reports 98.74% \\pm 1.12 for all sorting algorithms, it looks like that the network is not aligning with any specific sorting algorithm, but potentially learns a different one. Have the Authors tried investigating in this direction?\n\nQ4) What is the exact number of steps that the network performs during algorithm rollout?", "limitations": "Limitations are adequately addressed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The paper is written clearly. Discussion of background and prior work is comprehensive. Source code is provided for reproducibility of the experiments. The paper is not very original, as it borrows concepts and formulations from [1]. However, the authors use these concepts in an alternative way.\n\nWhile [1] uses the regularisation loss to build a causal model, the authors use it to ensure that a neural network computes the same representations (at all steps) for any two inputs x_1, x_2 for which the execution of the algorithm A would be the same. I find this idea a clever augmentation technique. Quantitative results show supposedly good improvements in sorting algorithms with respect to baselines.\n\n[1] B. Bevilacqua, K. Nikiforou, B. Ibarz, I. Bica, M. Paganini, C. Blundell, J. Mitrovic, and P. Velickovic. Neural algorithmic reasoning with causal regularisation.", "weaknesses": "As mentioned above, all concepts and regularisation terms are not new and borrowed as-is from [1]. Experimental details are somewhat scarce and sometimes imprecise. For instance, the authors do not state the hidden dimensions of their models. Furthermore, this technique seems to be applicable only on a small portion of all problems in the CLRS benchmark, which greatly limits the potentiality of the method. Fundamentally, this technique seems to be only useful in the case of sorting, since in all other tested techniques it performs significantly worse. Plus, training networks the way authors propose in this paper will not align with any specific algorithm dynamics (as the authors correctly recognised in the limitation). In fact, judging from the sorting results (98.74% everywhere) it seems that the network has learnt a different algorithm w.r.t to insertion/bubble/quick/heap sort (or possibly only one of them).\n\nThe authors main point is that the regularisation term is forcing similar representations for the inputs to have the same execution trajectories, but there’s no experiments nor theoretical analysis confirming this property. \n\nOne thing I find very concerning is that the authors claim to fix the number of steps of the network (i.e., the number of steps in the “neural execution” phase) to be linearly dependent on the number of input size (i.e., O(n)). This means that the network must have learnt a sorting algorithm that achieves around 98% accuracy and runs in linear time, which feels very strange, unless the constant is high enough to behave well with array of 64 elements (test size).\n\n[1] B. Bevilacqua, K. Nikiforou, B. Ibarz, I. Bica, M. Paganini, C. Blundell, J. Mitrovic, and P. Velickovic. Neural algorithmic reasoning with causal regularisation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thoughtful review of our paper!\n\nFirst, we would like to emphasize one of our contributions - the modification of the no-hint mode towards being more similar to the hint-based one - that is not discussed in the review. While this contribution is technically simple, we believe it has great importance, as a simple modification, which is applicable for all problems, demonstrates clear (14 of 18) disadvantages of direct hint supervision (\"Baseline\" vs \"No-hint (ours)\" columns in Table 1). This contributes to the main takeaway of our paper that no-hint training is competitive to the hint-based one and thus requires more attention from the community.\n\nWe address the questions and concerns below.\n\n> all concepts and regularization terms are not new and borrowed as-is from [1]\n\nWe note that the concept and the regularization from [1] is a standard contrastive technique, see, e.g., [2], [3]. However, the main contribution of [1] is the application of this technique to algorithmic reasoning in a particular way. The way this technique is applied in [1] has a significant difference from our work: [1] uses the contrastive term to align intermediate computations of the model to the ground-truth dynamics of the algorithm, while our contrastive term gives the model additional signal about the problem without providing any constraints about computations which the model needs to follow.\n \n> experimental details are somewhat scarce and sometimes imprecise. For instance, the authors do not state the hidden dimensions of their models\n\nWhile we used the same setup as in the past works, we agree that all experimental details should be clarified in the text. We listed our hyperparameters in Table 1 in the [global response](https://openreview.net/forum?id=vBwSACOB3x&noteId=UUd9q6foXC) (please, see the attached pdf).\n\n> training networks the way authors propose in this paper will not align with any specific algorithm dynamics (as the authors correctly recognised in the limitation)\n\nA model without hints indeed may not align with any algorithm dynamics, but we consider this as a desirable property, since\n- Aligning to a particular algorithm can be suboptimal (lines 136-139 of the paper)\n- Allowing the model to find optimal dynamic can lead to new ways to solve the problem (lines 140-142)\n\n> There’s no experiments nor theoretical analysis confirming that the regularisation term is forcing similar representations.\n\nTo address this comment, we conducted an additional illustrative experiment. Please, see our global response and Fig. 1(b) in the attached pdf.\n\n> One thing I find very concerning is that the authors claim to fix the number of steps of the network (i.e., the number of steps in the “neural execution” phase) to be linearly dependent on the number of input size (i.e., O(n)). This means that the network must have learnt a sorting algorithm that achieves around 98% accuracy and runs in linear time\n\nWe note that each processor's step is the message-passing, which operates (in the case of Triplet-GMPNN) over the full graph, so in terms of the problem size the computation complexity is $O(n^3)$ (which is the upper bound for all considered algorithms), so there is no need to use high constant, we used 5 for graph problems, and 1 for others. For more clarity, we used the exact same steps count as the original hint trajectory for Insertion sort, so this choice seems reasonable.\n\nOther options for step count are described in lines 286-288 of the paper.\n\nWe also include ablation on the step count for sorting (Table 2 from the global response).\n\nQ1) In our opinion (which reflects the second limitation from Section 6) the reason is that invariance under order-preserving shifts reduces space differently for different tasks. For example, learning the sorting algorithm from information about the relative order is almost trivial, while solving the MST problem having the relative order over edge weights still requires additional logic, such as checking cycles between edges, adding edges to the tree, etc., which is not forced by the proposed regularization. We consider developing additional/stronger inductive biases as a promising direction for future work.\n\nQ2) We have not tried that and it seems applicable, but it does not reflect the key points of our paper: 1. The usual comparison hint vs no-hint is inaccurate due to the significant computation graph differences; 2. For some problems, it is possible to give a model additional inductive bias without any predefined constraints about underlying computations (such as the original algorithm trajectory). \n\nNevertheless, we believe that these two directions (hints vs no-hints) can converge to the point with a balance between strong inductive biases and the absence of intense supervision, which is closely related to your idea.\n\nQ3) We would like to refer to Fig. 1(a) from the global response, which demonstrates that due to the parallel architecture, the model without hints is making most of the final predictions in a parallel way, which differs from the sequential nature of the sorting algorithms.\n\nQ4) As mentioned above, it is $5 n$ for the graph problems and $n$ for the array problems.\n\nWe are happy to discuss further any of the raised weaknesses and questions!\n\n[1] B. Bevilacqua, K. Nikiforou, B. Ibarz, I. Bica, M. Paganini, C. Blundell, J. Mitrovic, and P. Velickovic. Neural algorithmic reasoning with causal regularisation.\n\n[2] Mitrovic, J., McWilliams, B., Walker, J. C., Buesing, L. H., and Blundell, C. Representation learning via invariant causal mechanisms\n\n[3] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations\n"}, {"review_id": "qjr5bWwIo2", "reviewer": "Reviewer_y7mK", "summary": "The paper addresses neural algorithmic reasoning without the supervision of intermediate steps of reasoning. Typically, neural algorithmic reasoning requires supervision on the intermediate steps of reasoning. The paper proposes a method that does not require intermediate supervision and achieves competitive results with full-supervised benchmarks. The paper proposed a modified no-hint reasoning scheme that mimics the hints-supervision setting and self-supervised objective using the contrastive loss term for nodes for each step.", "questions": "Why are some values not available in Table 1? \n\nIn the right-most column of Table 1 and Table 2, values for Insertion/Bubble/Quick/Heap sort are all the same, even though the experiments are conducted on 5 different random seeds and stochastic gradient descent. Why does this happen?", "limitations": "Some limitations are argued in the paper.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Overall the paper addresses an important problem of the integration of reasoning with neural networks.\nThe motivation is clearly argued in the paper. Neural algorithmic reasoning has been showing its strong capacity for structured reasoning as neural networks, but the approach requires dense supervision on intermediate steps. The proposed method mitigates this issue, reducing the amount of required effort and thus would extend the capacity and applicability of neural algorithmic reasoning for different tasks.\nThe proposed method achieves competitive results against fully supervised benchmarks and shows its advantages. The obtained results are interesting and promising. The source code is available in the supplementary material.", "weaknesses": "My major concerns regarding this paper are as follows.\n- The explanation of the method is somewhat unclear and is not easy to follow. For example, Hint-ReLIC is repeatedly referred to and used as an explanation. However,  the paper does not provide enough explanations regarding Hint-ReLIC (although textual explanations are distributed in different parts of the paper), and that makes the presentation not easy to follow.  Readers would gain benefits from a bit more detailed explanations regarding the key relevant method in the background section to understand the proposed method.\n- Experimental details are not explained enough.  In Table 1, some cells do not contain values, but no specific reasons are clarified in the main text (if I am not missing them). In the right-most column of Table 1 and Table 2, values for Insertion/Bubble/Quick/Heap sort are all the same, even though the experiments are conducted on 5 different random seeds and stochastic gradient descent. This seems to imply that the proposed method produces exactly the same values for each different random seed across different tasks via stochastic optimization. If there is an explanation for why this happens, it would need to be mentioned in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your thoughtful review!\n\nWe agree that adding a more detailed explanation of the Hint-ReLIC method to the background section would make the paper easier to follow, we will update this section. However, we are happy and open to clarifying something during the discussion period if needed.\n\nWe address your questions below.\n\n> Why are some values not available in Table 1?\n\nFor the Hint-ReLIC method, the DFS scores were not reported by Bevilacqua et al. (2023) (as we mention in the footnote on page 7). For the last column, as mentioned in line 180 of the paper, our proposed regularization term is applicable only for part of the problems, which is also mentioned as one of the main limitations in Section 6.\n\n> In the right-most column of Table 1 and Table 2, values for Insertion/Bubble/Quick/Heap sort are all the same, even though the experiments are conducted on 5 different random seeds and stochastic gradient descent. Why does this happen?\n\nAs the proposed no-hint regime does not use any information about the algorithm, all sorting tasks become the same and scores may differ only by a random seed, so we reported the same numbers for all sorting algorithms. But, as we mention in lines 303-306 of the paper, the standard no-hint regime uses the ground-truth step count for each algorithm, which produces the difference for sorting algorithms in the first column.\n\nWe hope that our response addresses your concerns and will be happy to answer any additional questions during the discussion period if needed.\n"}]

Author rebuttal:
We thank all the reviewers for their feedback and many constructive suggestions and comments.

We have incorporated additional clarifications and experiments in the attached pdf, which contains:

**Table 1.** Parameters of the model and training procedure.

**Table 2.** Ablation on the steps count for the sorting problem. In the paper, we used the same steps count as the Baseline model for Insertion sort. We demonstrate that mimicking the steps count from other baseline models still shows the advantages of the proposed no-hint changes.

**Table 3.** Ablation on the augmentations count for the contrastive term.

**Figure 1(a).** Demonstration of the execution dynamics for the hint-based model vs the no-hint model on the sorting task.

While the interpretation of the underlying computations of a model is non-trivial, we can use the decoders of models to demonstrate the dynamics of the intermediate predictions. We took two models for the sorting problem: No-hint (ours) and Insertion sort (trained with hints supervision). Both models use the same steps count (64 steps for the test data). After each processor step, we can apply the output decoder to node embeddings to see the intermediate predictions of the predecessor (we remind that the output for the sorting problem is represented by the prediction of the predecessor node in the sorted order). For each step, we visualize the ratio of the intermediate pointers that are equal to the final output of the model.

We note that for hint-based models we have two decoders: the Hint decoder and the output decoder, both of which can be used for this purpose (orange and blue line, respectively).

We would like to highlight several insights from this experiment:

1. Models trained with supervision on the trajectory for Insertion sort struggle to learn the relation between the intermediate predictions of the pointers and the output predictions (orange line). In other words, the model potentially can consider the hint sequence (and even each transition between hints) as a separate task, not related to the output of the algorithm directly. However, the execution trajectory for the models with hints inherits some sequential order of intermediate updates (blue line).

2. The model without hints has a much stronger tendency to do parallel processing - almost all output predictions are obtained on the first steps of the execution (green line). 

**Figure 2(b).** We demonstrate that the proposed contrastive term forces the model to have similar representations for inputs from the same equivalence class. For this purpose, we took different pairs of equivalent inputs and for each step of the execution we calculated the following ratio: if we take one node from one input and take the closest node from the augmented input, what is the probability that the closest node will represent the element with the same relative order (and not, for example, the closest value)?

While the model without the contrastive term (blue line) is able to mainly rely on the relative order, we see that our contrastive term is forcing much more confidence (and speed) in achieving that property.

We are happy to discuss these experiments further or answer any questions!

Meta-review: Neural algorithmic reasoning aims at training neural networks that are capable of imitating classical algorithms. These methods often use the intermediate state of the algorithm as supervision to improve the representation learning and the final performance. This of course, create a limitation and makes it difficult to use these methods out-of-the-box for a new algorithm. This paper proposes a method to remove intermediate hint supervision. The method however does rely using augmentations and a contrastive loss which should be carefully designed and depend on the specific target algorithm. That being said, demonstrating this alternative seems very useful. Overall most reviewers find this work interesting and voted for acceptance. However, there are several existing concerns as well and I suggest authors take those concerns seriously and improve the camera-ready version of the paper. Improving the quality would certainly encourage more people to build on this work.

A few areas to improve for camera-ready:

- Specifying all experiment details and choices in the appendix for all experiments. Everything should be reproducible from reading the paper.
- Adding experiments on at least one other graph family (see reviewer Fw9t's comments)
- Add ablations to see if some of the improvement of the proposed architecture can be attributed to extra capacity added to the network. Authors can then discuss what would be a "fair" comparison but having those results allow the reader to make up their own mind after seeing all the experimental results and reading authors' arguments.
-  For some of the CLRS algorithm discuss how easy it is to come up with invariances as opposed to using hints so that the reader can understand this issue better (see reviewer uiKS's comments)

This is a borderline paper. I am voting for acceptance and hoping that authors would understand that taking the above comments seriously would ultimately benefit their own paper and the community.
Decision: Accept (poster)