Deep Equilibrium Algorithmic Reasoning
Authors: Dobrik Georgiev Georgiev
JJ Wilson
Davide Buffelli
Pietro Lio
Venue: NeurIPS 2024 poster (2024)
Keywords: neural algorithmic reasoning
deep equilibrium models
DEQ
Graph Neural Networks
Primary area: graph_neural_networks
TL;DR: We explore approximating neural algorithmic execution by solving an equilibrium equation, ground our approach theoretically and discuss implementation caveats.

Abstract: Neural Algorithmic Reasoning (NAR) research has demonstrated that graph neural networks (GNNs) could learn to execute classical algorithms. However, most previous approaches have always used a recurrent architecture, where each iteration of the GNN matches an iteration of the algorithm. In this paper we study neurally solving algorithms from a different perspective: since the algorithm’s solution is often an equilibrium, it is possible to find the solution directly by solving an equilibrium equation. Our approach requires no information on the ground-truth number of steps of the algorithm, both during train and test time. Furthermore, the proposed method improves the performance of GNNs on executing algorithms and is a step towards speeding up existing NAR models. Our empirical evidence, leveraging algorithms from the CLRS-30 benchmark, validates that one can train a network to solve algorithmic problems by directly finding the equilibrium. We discuss the practical implementation of such models and propose regularisations to improve the performance of these equilibrium reasoners.

Deep Equilibrium Algorithmic Reasoning
Dobrik Georgiev University of Cambridge dgg300cam ac. uk
JJ Wilson Independent Researcher jui com
Davide Buffelli
Pietro Liò
MediaTeek Research
University of Cambridge p12190cam. ac.uk
davide. buffell wttlllliimtteeeerrchhae
Abstract
Neural Algorithmic Reasoning (NAR) research has demonstrated that graph neural networks (GNNs) could learn to execute classical algorithms. However, most previous approaches have always used recurrent architecture, where each iteration of the GNN matches an iteration of the algorithm. In this paper we study neurally solving algorithms from a different perspective: since the algorithm's solution is often equilibrium, it is possible to find the solution directly by solving an equilibrium equation. Our approach requires no information on the ground truth number of steps of the algorithm, both during train and test time. Furthermore, the proposed method improves the performance of GNNs on executing algorithms and is step towards speeding up existing NAR models. Our empirical evidence, leveraging algorithms from the CLRS-30 benehmark, validates that one can train network to solve algorithmic problems by directly finding the equilibrium. We discuss the practical implementation of such models and propose regularisations to improve the performance of these equilibrium reasoners.
Introduction
Algorithms, while straightforward in theory, become challenging deploy in real-world scenarios. They operate in abstract domains with very specific conditions and types of inputs, which are represented with scalars. The main hurdle is the need "collapse" reality into scalar every time an algorithm is used, something usually done based on intuition rather than principled science [25]. Neural Algorithmic Reasoning (NAR; 46) has been proposed address this issue by utilising specialised neural network architectures to break this scalar bottleneck by executing algorithms in higher-dimensional space made out of arrays of numbers (vectors). The task of mapping reality into this vectorial space is delegated to automated gradient-based optimisation techniques rather than relying on human operators.
While NAR does not provide the correctness guarantees of its classical counterparts, robust perfor- mance can be achieved through alignment [55] submodules of the model architecture correspond to casy-to-learn subparts of the algorithm (or class of). Graph Neural Networks (GNNs) have emerged as the most convenient architecture execute all types of algorithms [29] and GNNs that align better to the target algorithm achieve better generalisation. This alignment game [50] has led to sequence of exciting research from aligning the architecture with iterative algorithms [42] to proving that "graph neural networks are dynamic programmers" [13], especially if their pessaageppassing function [21] takes into account 3-node interactions.
Source code available here: https:/ //gt:::////tbbb././/// com wtt.//oo///eeeeee www./H/eeokMMM///..aa..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The aforementioned papers focus on aligning the computation of the GNN with an algorithm or a specific algorithm class (e.g. dynamic programming). but ignore the properties the time of algorithm termination. For the algorithms in the CL.SS-30 algorithmic reasoning benchmark [45] once the optimal solution found, further algorithm iterations will not change For example, in dynamic programming shortest-paths algorithms making additional iterations would not alter the optimality of the shortest paths' distances found. Such a state is called an equilibrium additional applications of a function (an algorithm's 's iteration) to the state leave it unchanged.
In this paper:
1. We explore the connection between execution of algorithms and equilibrium finding through the use of Denotational semantics and Domain theory. (section 3)
2. Inspired by the above, we implement class of deep equilibrium algorithmic reasoners (DEARs) that learn algorithms by identifying the equilibrium point of the GNN equation and propose improvements to them. (section 4)
3. Our results suggest that the above reasoners can be successfully trained. Not only does equilibrium algorithmic reasoning achieve better overall performance with less expressive (and expensive) GNNs, but is also competitive to the more expressive (and expensive) NAR models. All this is done without providing any information on the number of algorithmic steps neither at train nor at test time. (section 5) 4. DEARs also drastically improve the inference speed an achievement made possible by the use of optimised root-finding algorithms and by decoupling the neural model from the sequential implementation of algorithms in standard benchmark datasets. (section 5)
Related work The main proposed application of NAR is settings where one wants to apply an algorithm, but it is impossible to represent reality with single scalar, hence "executor" operating in vector space and faithful to the algorithm is required [47, 50J. As NAR models are neural clones of algorithms,, they need provide correct output even for previously unobserved input sizes. Achieving robust out-of-distribunt dedicated their attention to it [8, 13, 14, 42] to name few. Except for one concurrent work (a blog post:[53]). those works focus on improving the GNN step and many completely ignore the termination of algorithms similarly to Xhonneux et al. [53], studies neurally finding solutions to algorithms by relying on the equilibrium property. We, however, attempt give the precise assumptions required for this approach to work. Further, we implement a more robust model than theirs, which achieves comparable or better performance to baselines. Finally, we propose modifications to improve equilibrium NARs.
(OOD) generalisation is tricky. To this end plethora of works have
any properties of the last state, such equilibrium. This work,
Background
Algorithmic Reasoning Let A LA + OA be an algorithm, acting on some input æ E LA. producing an output A(x) E Oa and let A A be the set of possible inputs/outputs A can read- /return. In algorithmic reasoning, we aim learn a function AA IA + OA, such that A z A. Importantly, we will not be learning simply an input-output mapping. but we will aim to align to the algorithm A's trajectory. The alignment is often achieved through direct supervision' on the intermediate states of the algorithm. To capture the execution of A on an input x we can represent it as
h PREPROC(2) (la)
h A(h.)..(Fh........ ...) (1b) A(x) = PoSTPROC(h.) (Ic)
times
where PREPROC and POSTPROC are some simple pre- and post-processing initialiiii auxiliary variables or returning the correct variable), h, E HA is A's internal (hidden) state, A, is subroutine (or a set of) that is executed at each step and the number of steps depends on boolean property being satisfied (e.g. all nodes visited).
therefore no surprise that the architecture [24] is the de-facto choice when it comes to NAR. Thus, the architecture can be neatly represented as a composition of three learnable components: A = 9. P fA, where 9A TA - B
Recent research [8, 37] has shown that alternative, causality-inspreed, ways of alignment also exist.

---

and fA : R + Og are the encoder and decoder function respectively (usually linear projections) and P: IR + Fd is a processor that mimics the rollout (Equation 1b) of A. The processor often uses massagg GNN at its core.
CLRS-30 The CLRS-30 benchmark [45] includes 30 iconic algorithms from the Introduction to Algorithms textbook [11]. Each data instance for an algorithm A is graph annotated with features from different algorithm stages (imput, output, and hint), each associated with location (node, edge, and graph). Hints contain time series data representing the algorithm rollout and include temporal dimension often used to infer the number of steps Features in CLRS-30 have various datatypes with associated losses for training. The test split, designed for assessing cuttoo-dditriuttiin (OOD) generalisation, comprises graphs four times larger than the training size.
Deep Equilibrium Models Deep equilibrium models [DEQs 4] are a class of implicit neural networks [20]. The functions modelled with DEQs of the form:
fo(z", x))
(2)
where æ is input, fo is function parametrised by 0 (e.g. a neural network) and x' is the output. z" is an equilibrium point to the eventual output value of an infinite depth network where each layer's weights are shared, i.e. s!a = fa- By re-expressing (2) as Jo =fo(2", .) =" DEQs allow us to find the fixed point 2" via any black-box root-finding method [e.g. 2. 9], without the actual need to unroll the equation until convergence, allowing us reduce steps. For backpropagation the gradient 0c/00 could be calculated using the Implicit Function Theorem (cf. 4) and no intermediate state has to be stored, giving constant memory cost of gradient computation regardless of the number of iterations until convergence.
Expander graphs MPNNs operate by exchanging information between adjacent nodes [21]. has been identified that the message passing process can be hindered by phenomenon known as oversquashing [1], which occurs when a large volume of messages are compressed into fixed-sized vectors. The importance of overcoming the negative implication posed by this phenomenon is crucial for the overall expressivity of GNNs [22], particularly in the context of long-range node interactions.
To this end, several spectral methods have been proposed to mitigate oversquashing by increasing the Cheeger constant [3, 6, 30). A higher Cheeger constant provides measurement that graph is globally lacking bottlenecks. The novel approaches include graph rewiring techniques [7, 44], as well as significant independent bodies of research recognising the efficacy of expander graphs [6. 12, 41]. due to their desirable properties.
Expander graphs are proven to be highly connected sparse graphs EE O(V)) with low diameter [35], thus offering advantageous properties for information propagation. Consequently, this facilitates messages be passed between any pair of nodes in a short number of hops, and result, alleviating oversquashing. Formally, a graph G = (V, E) is defined as an expander if it satisfies certain expansion properties. One common definition involves the aforementioned Cheeger constant. In the work of Deac et al. [12], a high Cheeger constant is equivalent to a graph being bottleneck free [12, Definition 3). and that an expander has a high Cheeger constant [12, Theorem 5].
There are various methods for constructing expander graphs. We opt for the deterministic algebraic approach in Deac et al. [12], utilising Cayley graphs. Specifically, we leverage Definition 8 and Theorem 9 of [12] to construct the Cayley graph for the special linear group S2, Z,,) and its generating set S, see p.5 of Deac et al. [12] for details. Note, that the order of a Cayley graph for Z,, is VV = O ( Hence, for many input graphs, a Cayley graph of the same size may not exist.
3 Denotational semantics: The denotation of a while loop statement
This aim of this section is to draw the parallel between finding equilibriums and executing an algorithm, in order to answer if and when an equilibrium NAR model can be successful. The following paragraphs introduce the mathematical tools for formalising fixed points denotational semantics [39] and domain theory [38].
3

---

Denotational semantics To every programming language expression" P denotational semantics
provides an interpretation [P]] which mathematical object (often a function), representing
the behaviour of the expression to different inputs. These denotations must be: 1) abstract, i.e.
independent of language and hardware, hence functions are natural choice; 2) compositional, i.e. [P]] can only be defined in terms of the denotations of P's subexpressions, but not P itself; 3) model the computation P' performs, As an example, we will use the lightweight imperative programming language IMP It consists of rumbers, locations, arithmetic expressions, boolean expressions and commands. Examples of IMP are given in Appendix A - we will use blue for IMP and encourage the reader to check how we use colour in the appendix. Albeit small, the language is luring-complete and all algorithms we experiment with can be defined it.
Denote the set of variable locations with L those are all variables/array elements we can ever define. good analogy to think
the addresses in the language The notation we can use to represent a program state is X + 1, B + -48 ..] and means that the value of X is 1, the value of B is -48 and so on. In other words, program states map locations to integers, s.t. a location can be mapped only once. Hence states are functions and the set of all program states State is the set of functions mapping locations to integers: given 8 E State, s(L) E E is the value at the location L for the state The value for location L in different s' State, s' (L), may may not differ. The denotation of arithmetic boolean expressions / commands are the functions with domain State. These will be represented in the form of lambda abstractions, i.e. dr E S.M rather than f(x S) M. where S is a set and M is a function body. The codomain of the denotation depends on the type of expression: [a] State Z for arithmetic expressions, [6] State + B, for boolean expressions and [c]] State - State for commands. Since commands transform state, they are also called state transformers. Commands' denotations are partial functions, as expressions like while true do skip never terminate and have no denotation.
For large portion of the above language, it is trivial and intuitive to define the denotations by structural recursion. For example:
(c) if [s) is true (sl(s) otherwise
[if b then co else cI] = As E State.
[(]] Às State. [c][([c][ss)
[skip] As E State.
The only denotation that cannot be expressed recursively, is that of the while construct. Let w- = while b do c. By program equivalence, w = if then (c,w) else skip. Therefore
[[w] (Ic]()) if [b](s) is true otherwise
[w] = [if b then (c:w) else skipl As E State.
but this not a valid definition, since it reuses [w]] (highlighted in red above). Denotational semantics solves this problem, by defining a function Je : (State - Slale) - (State - Stale) which takes one state transformer and returns another:
iw (c(s))
b()
fb.c Xuo E (State State).As E State.
(3)
otherwise
S is now a function variable. The denotation of [w]] is the fixed point of f[o).I i.c. [w] = f1o Lof ([w]). In order to find the denotation, we need to solve the fixed point. To aid the reader a full
worked example of computing the denotation for a while loop construct is given in Appendix B.
Domain theory Scott [38] provides framework with which we can both find and also characterise solutions for fixed point equations.* 4 Define D as the domain of state transformers (State -s State). A partial order C on D is defined as follows: w _ w' iff Vss E State if w(s) is defined then w(s) w' (s). In other words w' keeps old mappings and only defines new ones. The totally undefined partial function 1 is the least element in D. This function contains no location to value
Note the abuse of notation. For this subsection, we will forget we use for the neural processor.
'Due to space constraints, we omit the formal language definition (Winskel [52]. 11-13), and we use condensed version [18] of the denotational syntax, given in Chapter 5 of Winskel [52].
4 'orr detailed definitions and proofs, please refer to $5.4 of Winskel [52]. It is reflexive, transitive and anti- suti-symmetric

---

mappings. A chain is sequence of elements of D, s.t. do = 52 The supremum of the chain, called least upper bound (lub), is denoted as Ln20 dn- There could exist different chains, but, by definition, all chains in domain must have a lub.
function f: D + is monotonic iff Vd, E D. (d f(d) E f(d'). In other words, the second state defined more mappings than the first and we apply one iteration step to both states, the state resulting from the second will still define more mappings. Monotonic functions for which Unzo (d,,) f / dn) are also called continuous. In plain language. if a function is continuous and we are provided with chain, the lub of applicd to every chain element is the same f applicd to the lub of the chain. An element d" E D is defined to be pre-fixed point if f(d") [ d" applying does not define anything new. The fixed point ffx:() of f is the least pre- pre-fixed point of f. By utilising antisymmetry of [ and the two properties of fix(f) (pre-fixed point and least) we can obtain f(fix(()) = fíx(f). By Tarski's theorem [43], any continuous f D D has least pre-fixed point. This fixed point can be found, by taking the lub of the chain of applications of f: fin(s) - Un2o0 (L) The helper function fo.e from Equation is continuous [proof is given on p.120 of 23], therefore a direct result is that if the while do e terminates then its denotation exists and is the least fixed point of sequence of iterations (compared to picking any fixed point).
Denotational semantics and NAR The above detour into denotational semantics has affirmed the existence of connection between equilibrium models and algorithms (as conjectured by Xhonneux et al. [53]). Under the assumptions that:
*
the algorithms always terminate while not computable in the general case, this holds true for experiments, as we are dealing with offline algorithms with provable termination
the algorithms we train on can be modelled as "while b do e" constructs within IMP
the least fixed point exists and can be found by taking the first "state" of the algorithm where future iterations on have no effect. Appendix we have further annotated three algorithms from the official code of the CLRS benchmark: BFS, Floyd- Warshall, strongly connected components. Those annotations clearly show that algorithms can be rewritten IMP regardless of their implementation size. While BFS is clearly a "while do c" c"-type of algorithm, annotating the other two reveals that either the network may need more input features to decide termination (Floyd- Warshall; Listing 2) or that the algorithm can be composed of several while loops where each is another while loop on its own (strongly connected components; Listing 3). Fortunately, our approach not doomed to fail: a single DEQ layer can model any number of "stacked" DEQ layers [32, chapter 4].
4 Deep equilibrium algorithmic reasoning
Architecture We implement our processos/enccdersdeeceerr following Ibarz et al. [29]. The most notable difference' to their implementation is that ours uses a sparse graph representation. This requires us to assume fully connected graph on tasks where no graph structure exists, in order to be able to give pointer predictions, and to reimplement the strongly connected components algorithm so that the output pointers are always in the edge set (this did not change the difficulty of the task).
The final node embeddings, from which the output decoded, are the solution the equation:
H
(H)
(4)
where (H) = ((H(*), U, E). U/E are the encoded node and edge feature matrices and P is the processor function. H(O) are the stacked latent states of the nodes at timestep (with H 0).
The above Equation 4 matches the signature of Equation 2, and can be solved via root-finding (we employ torchdeq [19]; MIT License), as if it is fa of a DEQ. Any model using this technique will be called deep equilibrium algorithmic reasoner (DEAR) in experiments. The default processor in the majority of our experiments is a PGN [48] with a gating mechanism as in Ibarz et al. [29], but we note that DEARs can use any kind of processor.
aa E b and 6 E a implies a = "ee Appendix D for others not mentioned in the main text
5

---

GNN unroll
H 00
H (
CH (Ta)
9
DEAR
Required alggment
H
H
H
Allowed aiigment
Disallowed aligmment
Figure 1: Proposed alignment rule: every state in the DEAR trajectory should "go forward". Align- ments to a GNN state that has already been "passed" are disallowed. First and last states must always align. We intentionally use arrows instead of [ for DEAR, as E may not hold for DEAR's s trajectory.
Finding the fixed point The torchdeq library provides several solvers. The most basic one is fixed-point iteration, equivalent to repeating Equation 4 until convergence. However, in our very first experiments the solver needed more iterations than the algorithm we train on. We therefore opted for the Anderson solver (implements Anderson acceleration (2]) and abandoned fixed-point iteration:
(1+1) (UE(H(
H (++1) SolverStep H
H(0)
H(+1)
The criteria for pre-fixed point check torchdeq implements distance-based: for a state H be considered a pre- fixedixed point, the distance to the next state has to be under pre-defined threshold 8. We kept the criteria but modified the library always return the least pre-fixed point (see Appendix E). This is in contrast to picking the pre-fixed point with the least distance to next state (the default option in torchdeq) and is decision largely motivated from section 3. Due to a lack of a suitable definition for the domain of NAR trajectories, we define Vt. ( C H(++1), ie. we pick the first state that passes the pre-fixed point check.
Globally propagating information For problems defined on graphs it is in theory possible that the number of solver iterations needed to find equilibrium is less than the diameter of the graph. While, in practice, this is unlikely to happen we hypothesise that improving long-range interactions could improve the convergence of DEAR. For this reason, adopt the implementation of Cayley Graph Propagation (CGP) [51]. Contrasted to Expander Graph Propagation (EGP) [12), which addresses the graph size misalignment (see section 2) by truncating the Cayley graph, CGP keeps the extra nodes as virtual nodes. The CGP model upholds the aforementioned advantageous properties of an expander graph in more grounded manner by preserving the complete structure.
In GNNs, the benefits of augmenting graph with virtual nodes and providing message- pasaggg shortcuts have been observed to improve performance in various tasks [10, 26, 27]; further supported by the thcoretical analysis [28]. Additionally, by retaining the complete Cayley graph structure we improve the structure-aware representations by varying the neighbourhood ranges [54].
No hint by default We do not make any use of hints (supervising on intermediate algorithm state). First, although it may seem counterintuitive, it has been shown that NAR model successfully generalise, and even give better results when trained to only predict the correct output [8, 37]. Second, the fact that the solver uses the GNN exactly once per call does not imply that one step of the solver would correspond to one iteration of the algorithm, bringing uncertainty which DEAR states to match which algorithm step. While we propose alignment scheme (see next paragraph), which has the potential to integrate hints, we leave this for future work.
Alignment Our idea of alignment is visualised in Figure 1. We are given two trajectories of states, obtained from unrolling GNN iterations in classical NAR and another obtained from using DEAR. We would like to match DEAR to NAR, such that Vi & j, < j if we have committed to aligning DEAR state (') to NAR state H we cannot align any HQ') to H and from the same start we would like to reach the same final state. other words, skipping states is allowed, going back in time is not. This auxiliary supervision would also improve the monotonicity of DEARS, encouraging faster convergence. Enforcing this alignment is done by using an auxiliary loss. Choosing the L2 norm distance metric, use dynamic programming algorithm (Appendix F)

---

NAR
DEAR
109
10-1
Train Loss
10:2
10-1
you pran
10
Roan Scarc
Revey 11
10
20
100
20
40
60
80
Epoch
Epoch
Figure 2: Despite converging to slightly higher train loss our models remain stable during optimisation
compute the most optimal alignment (normalised by the number of solver steps, in order not to penalise longer trajectories) and supervise on that value.
Even with normalisation, the alignment sometimes had the effect of making the optimisation stuck in local minima where the number of steps to hit equilibrium was as low as 2 and the gradients were uninformative. We combated this in two ways: 1) instead of using the default layer normalisation switched to AOANOLA [15]; 2) since [[)i=([)) = J, we performed a random number of additional iterations [33] and take the last state. The probability of doing extra steps is 0.5*.
5
Evaluation
Setup For each algorithm we generated 10$/100//00-sizze training/validationnn/ datasets. Training sample sizes vary between 8 and 16 elements (uniformly randomly chosen) validation samples are of size 16. As is standard in NAR literature, we measure the test performance out-of cuttof-distribution. so our test samples are of size 64. For algorithms on graphs we generate Erdös Erdös-Rényí Rényi graphs [17] with edge probabilities uniformly sampled from the interval [0.1, 0.9], with increments of 0.1, which is the data distribution our baselines [8, 29] have used. We obtained the ground truth execution trajectories and targets using the CLRS-30 330 implementation [45].
In our experiments the models have latent dimensionality of 128, the batch size is 32, the learning rate is 3 x 10-1 and we use the Adam optimizer [31]. We train our algorithmic reasoners for 100 epochs, choosing the model with the lowest task validation loss (discounting any regularisation; focusing on performance only) for testing. Each task is independently learned, minimising the output loss (losses depend on the algorithm, cf. CLRS-30) plus any regularisation losses. Unless otherwise specified, DEARs employ the Anderson root-finding method from the torchdeq library and include Jacobian regularization [5], the tolerance for fixed point criteria on the forward pass is 8 0.1 (and on the backwards) and is based the relative L norm between GNN states. Standard deviations are based on 3 seeds. If run on a single 4090 GPU one would need about 3 weeks of total compute.
The performance metric measure is the out- ofdittribbuti accuracy, hence the larger test instances. The definition of accuracy varies between algorithms and is based on the specification of the algorithm itself. We refer the reader to Veličković et al. [45] and CLRS-30 for corresponding accuracy metrics definitions. The main baselines we compare against are the results reported by Xhonneux et al. [53], implementation is publicly available, and NAR architecture with PGN processor trained in the no-hint regime, as done by Bevilacqua et al. [8]. As, logically, models that are provided the ground-truth number of steps at test time will perform better, we also add as additional baselines a model that always uses 64 steps at test time and a model that has a dedicated network to decide termination [49]. In order understand how compare other, architectural alignments, also provide a comparison with a more expressive processor (Triplet-MPNNN.
5.1 Results
We present results for 10 key algorithms (most of the ones used in Bevilacqua et al. [8] in Table 1.
DEAR Rs are reasoners The first set of experiments aims to establish whether learning to execute algorithms by finding the least fixed point is possible. As Xhonneux al. [53] report that their models
7

---

Table 1: Test accuracy for different algorithms and models. Models with a diamond (0 or iterate for the correct amount of steps during train time (may differ between datapoints). Filled diamond means the ground truth number of steps also given test time. LTT stands for learnt termination the model that uses termination network. For DEM [53] we leave and we report two results for shortest path and MST as is unclear to us from the main text how they differentiated between the two. We do not run DEAR with CGP for array tasks as they operate cully-connected graphs.
when no results are reported
Algoritiun
NAR
NAR (Triplet-PPNN)
NAR (LT)
DEM
DEAR (ours)
DEAR (with CGP; ours)
Weighted graphs
Bellman-F.
97.06% 0.40
97.23% + 0.15
95.99%
96.4%//8888%
96.78% + 0.43
94.23%
Floyd-W.
52.53% + 0.98
61.86% + 1.57
49.30% + 0.53
55.75% + 2.20
53.20%
2.45
DSP
94.21%
1.77
93.32%
+: 1.60
88. 90% t: 1.04
89.81% d: 0.14
89.49%
0.17
MST Prim
93.56% 0.77
92.01% +: 1.50
87.69%
82.3%/75.22%
88.67% +: 0.74
86.37%
0.36
Unweighted graphs
BFS
99.85% 0.09
99. 69.6 + 0.29
99.51% 0.06
53.8%
98.73% + 0.37
98. 28%
0.55
DES
16.89% + 5.73
31 31.20% +: 4.02
29.07% +: 2.32
5.0%
40.62% + 0.44
23.87% 2.49
SCC
40.70% 1.39
46.84% + 1.70
39.33% 1.52
43.63% + 1.19
38.71% 0.45
Arrays (assumes colnecce graph)
Search (Binary)
91.67% + 2.31
93.33% + 2.31
84.33% + 8.33
59.00% : 12.3
Minimum
97.67% + 5.73
96.67% + 2:31
94.00% + 2.00
97 22% +: 3.82
Sort (Ins.) 27.07% 10.3
63.67%
39.97
33.8%
12.01
86.93% +: 3.87
Overall
71.42%
77. 57%
70.07%
75.42%
were prone to optimisation issues, we first compared the training loss for a standard NAR model and DEAR model with the same neural components. The plots are visualised in Figure 2. In line with the previous work, we observed that the DEAR tends to converge to slightly higher training loss as no algorithm's 's mean training loss dropped below 0.01. However, evident in Figure 2, we found the optimisation to be overall stable, and the final train loss difference between NAR and DEAR was never greater than 0.1 numerical differences, but we were overall satisfied with the convergence of DEARS.
Appendix G. We unaware if Xhonneux et al. [53] observed the same
Equilibrium is a useful inductive bias DEAR outperforms both of the above baselines achieving a 4-5% overall score increase, suggesting that aligning to the equilibrium property is a useful inductive bias. Moreover, DEAR with a PGN processor is comparable to a NAR with the more expressive Triplet-MPNN, achieving only 2% lower overall accuracy. This commendable achievement required no information about the ground-trun truth number of steps neither at train time nor during inference. A more detailed performance analysis follows.
On weighted graph algorithms our model performed on par with the baseline NAR no-hint model for Beldman-Ford, it outperformed the baseline on Warshall and scored slightly behind on the other two. On unweighted ones, it retained fairly high BFS accuracy compared to DEM and provided better scores for DFS and Strongly Connected Components (SCC). Unfortunately, even though for this kind of algorithms we used separate edge features for the CGP, in order to distinguish CGP edges from input ones, CGP had detrimental effect. We hypothesise that algorithms like DFS and SCC need a more advanced architecture or require different task specifications (the algorithm for SCC has a parallel "twin"; see [16]) in order to generalise OOD. On algorithms on arrays, we got significant performance improvement in the sorting task and got almost equal scores for min finding. However, the model underperformed by a large margin on the binary search task (in red). This result was very concerning, so we investigated further Appendix H showed that DEARs overfitted a lot on the classic representation of binary search and that when the task is designed carefully, DEARs can reach overall performance of a TriNlet-MPNN NAR architecture.
Effects of using CGP been futile. In Figure 3, we observe that for almost half of the algorithms CGP applies to, it had a positive effect on the loss convergence 3/7 algorithms converged to at least half an order of magnitude lower train loss. The rest did not experience any strong negative effects of CGP. Per- algorithm plots can be found in Appendix I. We believe that the reduced accuracies are due to the
Despite the slightly lower accuracies, our experiments with CGP have not
8

---

DEAR
DEAR W/ CGP
109
NET
10-1
Train Loss
10
10-1
10
10-1
20
100
20
40
60
80
100
Epoch
Epoch
Figure 3: Cayely graph propagation can help with convergence
DAG Shortest Paths
MST Prim
DCAR
DOAT W GA5
OZAR 0A5
Train Logs
10-2
Task Train Loss
10-2
10-2
10:2
10
10-
40
100
10-1
60
Epoch
Epoch
Figure Alignment (with GRANOLA and stochasticity; DEAR w/ GAS) gives better convergence
nearest Cayley graph for the training sizes being unique and a size of 24 nodes. Our deterministic approach of generating fixed Cayley graph for CGP, whose size is still distinct from test-time size leads to overfitting; what we may observe here. Future avenues of work may want to investigate this by methodically removing the Cayley graph's edges, but still retaining the desirable expansion properties [6], or by exploring alternative novel graph wiring techniques [7]. However, the limitation of these proposed approaches comparison CGP that they may require dedicated preprocessing to scale (one of the desirable criteria set by the EGP method), therefore providing an interesting line of future work.
Alignment can distill knowledge into DEARS For evaluating our alignment we focused on the non- CGP version of DEAR and decided pick algorithms where: 1) The baseline performs reasonably well (90+% accuracy), so as to provide good support; 2) the DEAR underperforms substantially. The algorithms fulfil those requirements are: DAG Shortest paths, MST Prim and Binary Search.
Results are presented in Table 2. At first glance, the only algorithm that substantially improved was binary search, giving an almost 20% increase. The final test accuracy, how- ever, does not represent all reality: Figure 4 shows that the task train loss (loss excluding any regularisers) for the model with align- ment decreases, compared to no alignment and reaches similar levels as the one observed for the non-DEQ solution. So, is it overfitting again? We argue it is not. Figure 5 shows that the test (OOD) accuracy per epoch increases when using alignment, reaching similar accuracies to NAR for the DAG shortest path problem and improving over plain DEAR for MST-Prim, suggesting that choosing the right model using validation seed is hard in NAR [34]. Lastly, we would like to note does bring benefits on its own, alignment is necessary to narrow the gap to the NAR training loss (Appendix J); 2) We never reached perfect (0) alignment loss, suggesting better alignment techniques may further boost performance.
Table 2: Test accuracy with and without alignment.
DSP
MST-Prim
Rinary Search
NAR DEAR DEAR
94.21% + 1.77 89.11%
93.56% 0.77
94.67% 1: 2.31 59.00% +: 12.3
88.67%
0.74
89.65% + 2.95
90.37% 1.19
77.33% + 4.51
(eligmmzn)
that: 1) although TRRANOLA*ttccasttiee
DEA Rs are highly parallel DEAR is not bound to follow sequential trajectories and GNNs are more aligned parallel algorithms than to sequential ones [16]. the cost for one step DEAR (GNN iteration + solver) is at least as high as step of an NAR model (GNN iteration only),

---

DAG Shortest Paths
MST Prim
1.0
1.0
0.9
0.8
Tist accuracy
0.7
0.7
0.6
0.5
0.4
DAM
20
Epoch
Epoch
Figure 5: Alignment (DEAR w/ GAS) leads to improvements OOD
Table 3: Mean inference time in seconds per sample. Measured on an RTX 4090 GPU. Up/down arrows denote improvemens/ddecriorttinn.. is used when difference is negligible. A double symbol is used for substantial (5x) differences.
Search (Binary)
Sort
Bellman-F. |
Floyd-W. t
DSP
MST Prim
BES
DES 1J
SCC
Minimum
(Insertion)
NAR 0.0188 DEAR
0.0916
0.1334 0.0345
0.0708 0.0297
0.0094
0.2440 0.0478
0,4017
0.0125 0.0131
0.0684 0.0174
0.5680 0.0260
0.0215
0.1102
0.0137
0.0253
Table 4: DEAR is architecture invariant and can also run with Triplet-MPNN processor.
Search (Parallel)
Floyd-W.
DFS
SCC
Sort
Overall
NAR
61.86% + 1.57
31.20% + 4.02
46.84% + 1.70
93.33% + 0.58
63.67% + 39.97
59. 18%
DEAR
62.29% 2.71
42.73% = 2.79
45.12% + 1.52
87.00% + 5.57
82.34% + 9.46
63 63.90%
(ours)
used the inference speed of a DEAR as a measure of how parallel the final learnt algorithm is. Results are presented in Table 3. An immediate observation that DEAR improves inference times across almost all algorithms. The only ones that were executed slower are: 1) Bellman-Fore Ford and BFS, which are highly parallelised in the CLRS-30 implementation, so an improvement on them was unlikely; 2) Floyd-Warshal Warshall where the difference, although present, is marginal and we account it to the added overhead from the solver; 3) Binary search, where performance was almost identical. These results suggest that although not always guaranteed (the case for searching), it is very likely that a DEAR will learn a parallel algorithm. The most substantial improvements, in line with our past observations in Engelmayer et al. [16], were on the tasks of sorting and strongly strongly-connected components.
DEA Rs are foundational Up until this point, DEAR was run with a PGN processor, which is lightweight, yet well-performant NAR processor architecture. The last set of experiments aims to show that equilibrium reasoning is not tied to only one type of processor/arccitectur.. It is rather class of models/foundational model as it can natively support different types of processors. To verify this claim, we present results with DEAR using the TriNletMMPNN architecture in Table 4. As Triplet-MPNN is computationally expensive, we tested algorithms for which NAR with Triplet- MPNN improves over NAR with PGN. Results indeed confirm that we are not limited to a single type of processor with DEAR, and, expected, the best overall performance is achieved when using DEAR with the more expressive, Triplet-MPNN, processor.
Conclusion
Our investigations with equilibrium models have shown that possible and even beneficial to merge NAR and DEQs. While our models attained very competitive performance, there are certain limitations that need be addressed: 1) Better algorithms for aligument can help close the gap even further for Prim's 's algorithm and binary search; 2) Better model selection is needed in order to know which DEARs would perform well OOD; 3) Graph rewiring techniques may be needed to prevent overfitting with CGP; 4) Algorithmic-aligned criteria for fixed-point may boost OOD generalisation for sequential algorithms. The last point is motivated by the fact that for each step, these algorithms update only a few nodes in the graph, keeping the rest untouched.
10

---

Acknowledgements
Dobrik Georgiev would like to acknowledge the financial support from G-Research towards covering his travel costs.
References
[1] Alon, U. and Yahav, E. (2020). On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05203
[2] Anderson, D. G. (1965). Iterative procedures for nonlinear integral equations. Journal of the ACM ( JACM).
[3] Amaiz- modizzRod A., Begga, A., Escolano, F., and Oliver, N. (2022). Diffwire: Inductive graph rewiring via the Lovåsz bound. arXiv preprint arXiv:2206007366.
[4] Bai, S., Kolter, J. Z., and Koltun, V. (2019). Deep equilibrium models. Neural Information Processing Systems.
[5] Bai, S., Koltun, V., and Kolter, J. Z. (2021). Stabilizing equilibrium models by jacobian regularization. International Conference on Machine Learning.
[6] Banerjee, P. K., Karhadkar, K., Wang, Y. G., Alon, U., and Montúfar, G. (2022). Oversquashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-8. IEEE
[7] Barbero, F., Velingker, A., Saberi, A., Bronstein, M. M., and Giovanni, F. D. (2024). Locality- aware graph rewiring in GNNs. In The Twelfth International Conference on Learning Representa- tions.
[8] Bevilacqua, B., Nikiforou, K., Ibarz, B., Bica, I., Pagannii, M., Blundell, C., Mitrovic, J., and Velickovic, P. (2023). Neural algorithmic reasoning with causal regularisation. Interna- tional Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, 202:2272-2288.
[9] Broyden, C. G. (1965). A class of methods for solving nonlinear simultaneous equations. Mathematics of Computation, 19:577-593.
[10] Cai, C., Hy, T. S., Yu, R., and Wang, (2023). On the connection between mpnn and graph transformer. In International Conference on Machine Learning, pages 1408-3430. PMLR.
[11] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, 3rd Edition. MIT Press.
[12] Deac, A., Lackenby, M., and Veličković, P. (2022). Expander graph propagation. In Learning on Graphs Conference, pages 38-1. PMLR.
[13] Dudzik, A. J. and Veličković, P. (2022). Graph neural networks are dynamic programmers. Advances in Neural Information Processing Systems, 35:20635-2000 206477.
[14] Dudzik, A. J., von Glehn, T., Pascanu, R., and Veličković, (2024). Asynchronous algorithmic aligmment with cocycles. In Villar, S. and Chamberlain, B., editors, Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pages 3:173:17. PMLR.
[15] Eliasof, M., Bevilacqua, B., Schönlieb, C.-B., and Maron, H. (2024). Granola: Adaptive normalization for graph neural networks. arXiv preprint arXiv: 2404.1333 13344.
[16] Engelmayer, V., Georgiev, D. G., and Veličković, P. (2023). Parallel algorithms align with neural execution. In The Second Learning on Graphs Conference.
[17] Erdös, P., Rényi, A., al. (1960). On the evolution random graphs. Publ, Math. Inst. Hung. Acad. Sci, 571):17-60.

---

[18] Fiore, M. (2023/24). Denotational Semantics. Lecture notes for Part 11 of the Computer Science Tripos. University of Cambridge.
[19] Geng, Z. and Kolter, J. Z. (2023). Torchdeq: A library for deep equilibrium models. https: //github. comm//cccsslabbbbccheeee
[20] Ghaoui, L.., Gu, F., Travacca, B., Askari, A., and Tsai, A. Y. (2019). Implicit deep learning. SIAM Journal on Mathematics of Data Science.
[21] Gilmer, J., Schoenholz, S. S., Riley, P. F.F., Vinyals, O., and Dahl, G. E. (2017). Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR.
[22] Giovanni, F. D., Rusch, T. K., Bronstein, M. M., Deac, A., Lackenby, M., Mishra, S., and Veličković, (2023). How does over-squashing affect the power of gnns? arXiv preprint arXiv: 2330.03588
[23] Gunter, A. (1992). Semantics of programming languages: structures and techniques. MIT press.
[24] Hamrick, J. B., Allen, K. R., Bapst, V., Zhu, T., McKee, K. R., Tenenbaum, J. B., and Battaglia, P. W. (2018). Relational inductive bias for physical construction in humans and machines. arXiv preprint 1806.0180..01220
[25] Harris, T. and Ross, F. (1955). Fundamentals of a method for evaluating rail net capacities. Technical report.
[26] Hu, W., Fey, M., Ren, H., Nakata, M., Dong. Y., and Leskovec, J. (2021). Ogb-Isc: A large-scale challenge for machine learning graphs. arXiv preprint arXiv:2103.09430.
[27] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, (2020). Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 13:22118-22111
[28] Hwang, E., Thost, V., Dasgupta, S. S., and Ma, T. (2022). An analysis of virtual nodes in graph neural networks for link prediction. In The First Learning on Graphs Conference.
[29] Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Bennani, M., Csordás, R., Dudzik, A. J., Bosnjak, M., Vitvitskyi, A., Rubanova, Y., Deac, A., Bevilacqua, B., Ganin, Y., Blundell, C., and Velickovic, P. (2022). A generalist neural algorithmic learner. In Rieck, B. and Pascanu, R., editors, Learning on Graphs Conference, LoG 2022, 9-12 December 2022, Virtual Event, volume 198 of Proceedings of Machine Learning Research, page 2. PMLR.
[30] Karhadkar, K., Banerjee, P. K., and Montáfar, G. (2022). Fosr: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprint arXiv:2210.1 17790.
[31] Kingma, D. P. and Ba, J. (2015). Adam: A method for stochastic optimization. In Bengio, Y. and LeCun, Y., editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings.
[32] Kolter, Z., Duvenaud, D., and Johnson, M. (2023), Deep equilibrium models (deq) tuto- rial. https: htt/://mppittttereeeee wawalyyyrrrtttrraa.l.l.... 2024-08-27.
hegg/deep_eeeee wwwppeuuuiiiiuiummmieeeeeee Accessed:
[33] Liu, J., Hooi, B., Kawaguchi, K., Wang, Y., Dong, C., and Xiao, X. (2024). Scalable and effective implicit graph neural networks on large graphs. In The Twelfth International Conference on Learning Representations.
[34] Mahdavi, S.. Swersky, K., Kipf, T., Hashemi, M., Thrampoulidis. C., and Liao, R. (2023). To- wards better dintr---istribution generalization of neural algorithmic reasoning tasks. Transactions on Machine Learning Research.
[35] Mohar, B. (1991). Figenvalues, diameter, and mean distance in graphs. Graphs and combina- torics. 7(1:533-44
12

---

[36] Paszke, A., Gross, S., Massa, F. Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019). Pytorch: An imperative style, pigh-peeffrrmanc deep learning library. arXiv preprint urXiv:
[37] Rodionov, G. and Prokhorenkova, L. (2023). Neural algorithmic reasoning without intermediate supervision. arXiv preprint arXiv:2306.13411.
[38] Scott, D. S. (1982). Domains for denotational semantics. In Automata, Languages and Programming: Ninth Colloquium Aarhus, Denmark, July 12-16, 1982 9, pages 577-610. Springer.
[39] Scott, D. and Strachey, C. (1971). Toward a mathematical semantics for computer languages, volume 1. Oxford University Computing Laboratory, Programming Research Group Oxford.
[40] Sharir, M. (1981). A strong- connnctvnntt algorithm and its applications in data flow analysis. Computers & Mathematics with Applications, 7(1):67-72.
[41] Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. (2023). Exphormer: Sparse transformers for graphs. In International Conference Machine Learning. pages 31613-31632 PMLR.
[42] Tang, H., Huang. Z., Gu, J., Lu, B.-L,, and Su, H. (2020). Towards problem solving by iterative homogeneous gnns. Advances in Neural Information Processing Systems, 33.
graph-related
[43] Tarski, A. (1955). A lattice-theoretical fixpoint theorem and its applications.
[44] Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. (2021). Under- standing over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.
[45] Veličkovic, P., Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., and Blundell, C. (2022). The clrs algorithmic reasoning benchmark. In International Conference on Machine Learning, pages 22084-22102. PMLR.
[46] Velickovic, P. and Blundell, C. (2021a). Neural algorithmic reasoning. Patterns, 100):3
[47] Velickovic, P. and Blundell, C. (2021b). Neural algorithmic reasoning. Patterns, 207)7,
[48] Veličković, P., Buesing, L., Overlan, M., Pascanu, R., Vinyals, O., and Blundell, C. (2020). Pointer graph networks. Advances Neural Information Processing Systems, 33:2232-2244.
[49] Veličković, P., Ying, R., Padovano, M., Hadsell, R., and Blundell, C. (2020). Neural execution of graph algorithms. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
[50] Veličković, P. (2023). Neural algorithmic reasoning. The Gradient.
[51] Wilson, J., Seechler-Spicchee M., and Veličković, P. (2024), Cayley graph propagation. arXiv preprint arXiv:2410.03424.
[52] Winskel, G. (1993). The formal semantics of programmingg languages: an introduction. MIT press.
[53] Xhonneux, S., He, Y., Deac, A., Tang. J., and Gidel, G. (2024). Deep equilibrium models for algorithmic reasoning. In ICLR Blogposts 2024. httss//fclbblogpssssgihhubbbobbb 2020////////////////////lgggg reasoning/.
[54] Xu, K., Li, C., Tian, Y.. Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. (2018). Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pages 5453-5462. PMLR.
[55] Xu, K., Li, Zhang, M., Du, S., ichi Kawarabayashi, K., and Jegelka, (2020), What can neural networks reason about? In International Conference on Learning Representations.
13

---

A IMP: Definitions and examples
Anything highlighted in blue below, is part of the IMP language. Subexpressions, to avoid confusion, are not coloured.
IMP consists of:
numbers 1, -20, 13930
locations AVariableName,, AnotherVar, ArrayName
arithmetic expressions (5+4) +3, but also A+55. Note how variables can be parts of arithmetic expressions.
boolean expressions true, false, but also X==0, 3*A<B and X==0 A A*Λ<B. Note how boolean expressions can be made by using variables or using boolean logic on sub- expressions.
commands Commands can be one of:
skip, which is no-op
=:=a, where X is assigned the value of arithmetic expression An example is 3+B+C
if then co else C1 where b is a boolean expression and co. ci commands. For example if < B then C:=0 else C:=A-B which sets C to the difference of A and B, if it is positive
(coic1)
while do which is while loop repeating command long as boolean expression (classic) example (Y:=1; while 0 do (Y:=X*Y; X==X-1)), which finds the factorial of X and saves it in Y.
B Fixed point of a while loop example
Below, we will denote the state [A + a, B b, b....). It means that the value of variable is and so on.
Consider the facorial example from above removing the explicit set of Y to 1. To find the denotation [w] [wiile x o do (Y:=X+Y; x==X-1]], we first define our fu,c
w ([X -
> x
(lx(w) HX, vl)
otherwise
The equivalent definition if we were to keep the lambdas from the original text
w0 ([X + 1,Y
y y*
if otherwise
fb, Awo (State -Saate-As State.
[X HHHYYH
but we will work with the first definition it is more compact.
14

---

The approximations of fb,c starting from f6.- T are:
fi. 1b,0(1,,0)11 xz v))
- y xx) [X 2, Y2,
- - vl)
+2,
otherwise
Jundefined
i > 0 otherwise
[X H 2, Y
The ([x x 1 1,
x))
if > 0 otherwise
fe. = fo.((fo, +2,Y+
[X + 2; Y +
undefined
if 1 > 0 if 1 = if 50
( 1,Y + y
( + x, Y y)
undefined
i
[X + 0, Y [ ifr=1
[X x, + ifr
Phe (X + 1,y
if > 0 i
= fo.co((( + +2, - 2l)
[X + 2, Y +
undefined
i
[X 0, Y + + y
if f
[X [X x 1,Y + y]
i
[X + Y
if
undefined
i
[ 0, +
if
[ 0,+00
if
X + x, Y
if 50
which for is:
undefined
if 2
fb,c
X + A x (x:!)
if < x
if 5
The sequence obeys fh _ Sb. E Sh. [ ... Sb. .... (we can see that whenever fhi=! is defined agrees with fb and fo,e monotonic (fh. = f. fo.e(fb.)) E fo.eLh.))..
For a given X = I, p0+1
cx42 _... The fixed point is the lub of the whole sequence is Sb.
therefore:
[X OX (x!)] if > 0
L (C =
x 5
n20
By a similar analysis, it is not hard show that the denotation of [shile true do skipl will be undefined.
C Can algorithms, as implemented in CLRS-30, have an equilibrium?
In this appendix, have copied over some algorithms implementations from CLRS-30'. Addition- ally, we have annotated how and when they follow the while b do construct. Algorithms, that are
oomitted this text see Winskel [52]
Phttps://ge htte:://gittti www.ooo//////o http://///....oooooooooe///e/eee
15

---

nor necessarily solved via this construct (e.g. strongly connected components) were also included, so as to showcase if this would break.
(A: _.rrry,, 8: int) Dut:
chez aesert__raat (A, 2)
probes probing- initialize (spece. SPECS ('bée'])
A_pos apange (A. probing.push
(A. shape [0])
probes,
Sracs..tage.11PP
next_prrobe-(
'pos': copy (A_poz) + 1.0 / А. shape [0],
probing maek (s, shape (0]),
11
'A": cp. (A),
12
'adj': probing graph Cup. copy (A))
13
})
14
reach ap. zeros (A. shape (0])
pi ap. arange shape [0])
16
reach(e] -
Initialisation
18
19
# implemented as do-while, but do-whiles are cesentially
20
# while b
21
shile True:
25
rracch copccoyrroacch)
probing. grobing-push! push
25
probes,
26
specs. Stage.Stage.Hx::
next_probe-(
28
'reach_h" copy (prav_roohh)))
'pi_h': copy
30
F command o: update reachability.
32
for range sbape [0])
33
for in range (A. shape [0]):
A[i,
and prev_reach[s]] [i] 1:
35
if pi[]] == and i= a:
pi [i]]] reach []] =
37
38
39
ap all (reach prev_resch): # boolean condition b: has reachability vector changed
break
41
probing - push (probes, a Stage. OUTPUT, next_probo-("pp/ ap. cppy (pi)))
43
probing Sinaliae(proben)
44
return pl, probes Listing I: BFS algorithm. Clearly implemented as while b do c.
sampler
2 class FloyWWrrahallSaaleee (Sampler))
"""SSnpper for all all-pairs shortest paths. ...
_sample_data(
self,
length: int,
[rpoe[rloat, ...] (0.5,),
lox: float - 0., # never changed in the data generation
high:
changed
generation
11 ):
12
graph self. ar graph samplea randon graph with veights [lou;high)
13
14
p-self._rag choice(p))))))
directed-Falee,
16
acyclic=Palse. veighted-True.
18
lov=lox,
19
high-high) return [grepa]
20
21
inplementation def floyd_ varshalla (A: _Arraa) >> Out:
23
"*"ployd Warshall all-pairs shortest paths (Ployd, 1962)
25
26
chex.aseert ascert, rank (A, probing. initialize (spece.. SPBCS (' "loodd_wrrshhll
27
28
A_poe ap. arenge shape [0])
16

---

30
31
probing
push (ush)
probes,
33
next_probba=t
35
'pos': copy (A_pos) / &. shape [o],
36
'A': ap. copyco
ladj': probing graph (np. (A))
18
})
40
D = ap.copy (A)
2eros ((A shape [o], shap [0l))
42
msk probing graph copy (a))
45
44
for
range (A. shape [0]):
45
for J. in ranga(A. shape [0]): j]
47
48
# Initialisation code ende here
49
50 # for loops are while loops
range (1) is equivalant <k:=0; while (1()) (c; k:sk-1) 52 # NOTE #1 The XE, hovever, has to learn to increase the k, solely 'pos" input
# "foor
having 'pred' feature, 54 # (as in atring algorithna) night have been nore appropriate
55
# ROTE #2 *Since the sampler (above) only samples positive edge veights*
37 # no negative veight cycles can exist. Hence any reruns of the inner too loops, after itaraitona
paasad will change natrix
59
iterations 61 # (a necessary, *but not sufficients condition is that D remains unchanged)
boolean condition
passed
62
for & in range (A shape(0)):
prev_D mp. (D) prev_nsk = cp. (nak)
64
66
probes.
68
Stage.Sttge.
69
next_probe-(
'Pi_h': up co.yo
71
'D': up- copy (prav_D),
"mak": up. copy (prev_us) _ask),
23
"k': probing mask_one (k, A. shape (0])
75
76
# command o: update for internediate vertez k for range (A. [0]):
78
for in raage shape [ol):
prev prev_nsk(i, [i,
[rev_ jl
80
if makli, j] = or pie k] [kk j] < D(i, j]:
DÍi, 1] prev_D[s, Pili,
prev_D(k, j]
82.
PPik, 1]
83
else:
Dís, 1] prev_D[s, msk mskli, [] -
85
87
probing push (probes. specs. tenaliz (probes))
noxt_probo-('P3': co. (Pi)))
89
90
return Pi, probes
Listing 2: Gloyd-Warhhie algorithm and its sampler (above). Can also be viewed as while b do c, in CLRS-30.
strongly com.eettedd.ccccannttsa.. Arrray) _Out: "ooaaaaj''s strongly connected components (Aho et al., 1974). ...
chax assert_rank (A, 2)
probes probing, initialize( specs.
SPECS SPece.SPEC3
A_pos ap. wwe.rreneeCo (A. shape (0])
probing. (ush( p
11
probes.
12
apecs. Stage IMPUT,
13
next_probe-(
14
onitted for brevity >
17

---

17 acc_id up. ap..raage (A, sh..aaaapeaa.c [0])
up. zeros shapa[0], dtype=mp. int32)
19 d zeroz shape [0])
up. ap.zerra shape [0])
21 e_prev ap.arange shape [0])
22 time
mp. transpose
24
Initialisation
26
27 boolean condition there are unvisited (color (a]=0) vertices (A shape [
28
for color[s]
29
5_last
31
==a
33
probing push
34
probes,
35
spece. .INT.
36
next_probe-(
omitted for brevity })
38
grey (color-1) recureively visit descendants
40
41
HOTE command is another while b o² with stack while True: # b²: stack is not enpty
42
43
if color [u]
ar duu 0.0:
0.01
45
d[u] time
color [u] probang-pushl
47
48
probes,
specs. Stago.HIIT.
50
next_proba=t
onitted brevity })
52
range ch.
cl: add
descendant top-stack
node to the top of the stack
54
if lu, !- 0:
if color [v]
56
color [v] =
8.prev s_last
58
s_last probing.push!
60
prabes,
61
specs Stage.HIIP HINT. next_proba=<
63
# omitted for brevity
65
break
67
if a_last == u: no descending
68
color [u]
0.01
70
[[u] time
72
probing.pusi push
73
probes.. Spece.Stage.Bee
74
75
next_proba=-
onitted brevity })
77
78
79
if s_prev [u] - u: and ve are on top of the recursion although imaginary, in implenentation here, if stack used, it'd be empty in this if statement
82.
assert [_p break pr s_prev [s.lat]
e_last
84
86
a_prev preev[a_lae [s_last] = s_last a_last pr
87
88
89
u =_last
91
color ap. zeros shape [0], dtype-ap. int32)
s_prev ap. arange shape [0])
93
94
: boolean condition b'; there are unvisited (color(s]-0) vertices
" (erder of vieiting depends finishing tine;
18

---

# Introduction algorithne, 4th edition, Chapter 20)
97
for a in up. ap.argaort(-f))
color[a] 0: s_last -
99
v
probing.puae pueh(
probes,
104
spacs.Stage Stage.HINT;
next_probe-<
196
omitted for brevity >
})
* NOTE command is another while b.* e** with etack while True: # bbtt stack is not eapty
109
acc_id [u]
111
if color [u] o or d[ul =s D.0:
113
d[u] = time
color [u] -
prebing. push
116
probes
specs. Stage.
118
next_probe-((
omitted brevity }) for in range (A, eArehape [0]): # o add lovest id unvieited descendant of top- stack mode the top of the stack if A_t [a, v] !- 0:
121
122
color [v] -1 ir
[v]
124
s_prev s_last s_last
126
127
probing. pueh
probes,
129
Sta.e.
next_probe=<(
131
# omitted for brevity >
133
break
134
if s_last
136
color [u] 0.01
138
[[u] time
140
probing-puse probes. specs Stage. HINT,
141
143
next_probe=t
omitted brevity })
145
147
if s_prev [u] == u: same before assert [s_las]] s_last break
148
150
pr - 8_prev[a_ s_prevee_las s_last s_last pr
152
154
s_leat
155
probing (
157
probes,
specs. Stage Stage. QUTPUT,
159
next_ coxt__probe<"sac__ id'_ (scc__id))
161
probing wwwslise (probes)
162
scc_id, probes
Listing 3: Kosaraju's strongly connected components [40] algorithm. is composed of four (two
nested ones, sequenced one after the other) while do constructs.
D Differences to Ibarz et al. [29]
Our differences are mostly required by software engineering rather than research, hence they live here. Differences are:
19

---

Different DL framework (Pytorch [36])
Ibarz et al. [29] use an extra nonlinearity after the GNN step. We found this to be not necessary (there are plenty of nonlinearities the message function) for the baseline and to be making the training of DEARs less stable so we removed it.
Sorting- based algorithms use a Sinkhorn operator to force the output to be a permutation. However, this gave very negative logits for the predictions at initialisation, leading to runs starting from a very high loss and converging to poorer minima. We fixed this by adding an off-centred leaky ReLU activation with the kink point at (-6, -6) right after the Sinkhorn operator. After conversion of logits to outputs via softmax, our change is mathematically equivalent saying that the probability for each other node be predecessor should not drop below 10-6
E Picking least fixed point
For given batch fixed point finding continues until all instances in the batch converge and at each step the solver is stepped on all instances. For given instance, when two H(t) and H('') are under the threshold 8, for some I. S L', the torchdeq library prefers the state that has the lower distance to next state. Consequently, out the returned fixed points only one is guaranteed be least the one that require the most steps. This not only misaligns with domain theory, but also had the practical effect that the neural models require more iterations to converge the more we train them. Thus, we changed the library to choose the first H(t) that passes the fixed point criteriaq.
F Alignment algorithm
Assume we have computed pairwise distance matrices between the states and those are stored in a T x Tg distance matrix D with elements d Ignoring the required alignment of the last states, focus on aligning the rest of the states. This is done via standard dynamic programming algorithm. The dynamic programming state define is follows: dpi, is the most optimal alignment for the first i DEAR states and first j NAR states, with dpo.j = 0 (having leftover NAR states mean skipped some, but do not want penalise that) and dy;,o states). We consider two recursive formulas, first one we use, the other we use when T < Tg:
(we want to align all DEAR
when the T > Tg. there are extra states. To avoid infinities we will allow for two DEAR states to align to same state:
dp:-1.3 + di,j
aligning DEAR state and NAR state j. but allowing for previous states to align well skipping alignment with state j
dp min
dp..j-1
(5)
when the T < T3 require that each DEAR state aligns to an unique NAR state:
ddi--1.-1 + da,y
aligning DEAR state and NAR state j skipping alignment with state j
dpi,j min
(6)
(dp.j-1
We have highlighted the difference to the above in purple.
The optimal alignment for the whole two sequence is stored in dpT,T, As both (9) and H concatenation of 0 vectors (due to how we initialise the latent state), their distance always 0 and they will always align as required. To enforce alignment of the last state, we take the optimal value for the subsequences without last states dpr-1,7g-1 and always (even when subsampling, see below) add the distances between the last states to the loss function.
(0)
As the above will always penalise longer DEQ trajectories, we divide dpr-1.T;. by including it in the loss function. Lastly, to allow for "intermediate" states (ones not necessarily matching a GNN state) to exist, we subsample randomly, without replacement, T" = max _ DEAR states and apply the dynamic programming algorithm with the subsampled sequence.
before
20

---

G Training loss: NAR vs DEAR
Bellmen-Ford
BFS
DAM
10
10"1
Train Loss
Train Loss
10-4
10-3
10-3
10'4
10'4
10
20
80
100
10
20
80
100
Epoch
Epoch
Binary Search
DAG shortest paths
109
109
Train LoSs
10"1
Train Loss
10
20""
10
10:4
10
20
100
10"9
20
100
Epoch
Epoch
Hlyd
10a
10
Train LOSS
10
Train LOSS
10
10-4
30*4
20-3
20-3
04M
10
10
Epoch
Epoch
Insertion Sort
Minimum
Train Loss
30-1
Train Loss
30"1
301
30
20-3
20-3
20
10
300
100
Epoch
Epoch
MST Prim
SCC
OWNN
CAN
Train Loss
Train Loss
10-3
10-4
10
10"4
10
20
80
100
10
20
80
100
Epoch
Epoch
Figure 6: Side-by-side comparison of NAR vs DEAR. DEAR training loss is always within 1 order of magnitude of NAR. Note the log scale.
21

---

Table Fixing anomalies with CLRS-30's binary search further increases our overall score making our approach very competitive to TriNletMPPNN. Notation taken from Table 1.
NAR (Triplet-PPNN)
NAR (LT)
DEAR (ours)
Algorithm
NAR
Search (Parallel)
95.67% + 0.58
93.33% + 0.58
93.33% + 3.05
85.67% 1 0.58
New Overall
71.52%
77.58%
70.97%
78.38%
H
Binary search anomalies
In the CLRS-30 implementation of binary search, we aim to find the place to insert the target value in sorted array A. Thus need to point the graph node that holds the smallest value in the array A, which is greater than x. However, if x>max (A), the answer is pointer to the last value of the array, which by the convention used by CLRS-30 means we would be inserting x at the wrong place. In other words, the answer to A= [0. 1, 0.2, 0 0.3] x=0. 25 and A= 1, 0.2, 0.3] x=0.35 is the same insert x the left of 0.3. This contributed some noise, so we fixed the sampler always give x within [o, max )A)). The other changes were to explicitly use graph & pointer instead of node mask_one as the location datatype of the pointer the position in the array, also done by Engelmayer et al. [16]. Similarly to them, we also add an additional supervision signal, but at the output level rather than the hint level teaching the models to predict which array elements are smaller than x (binary mask type).
We reran the new, parallel version of search, reporting results in Table 5. Our model still falls short of the baselines, but the 26% increase in accuracy large enough to give a slight overall advantage DEAR over the Triplet-MPNN model. We do note, however, that the task of searching is mostly numerical (comparison between floating point numbers), resulting in DEAR overfitting a lot recall that train accuracy was 95% even for the original (binary) search. We verified that if the training data is increased 3 x -5,, test accuracy becomes comparable to other models, regardless of which version used.
22

---

I Training loss: DEAR vs DEAR w/ CGP
Bellmen-Ford
BFS
187A sicc
109
10"1
Train Loss
Train Loss
10-3
10-3
10'4
10'4
10
20
80
100
10
20
80
100
Epoch
Epoch
DAG shortest paths
DFS
DEAR
DEAR
109
109
Train Loss
10"1
Train Loss
10
20"4
10
10:4
10
20
100
10"9
20
100
Epoch
Epoch
Heyd
OCAA
XCA
109
10
Train LoSs
10
Train LOSS
10
10-4
30*4
20-3
20-3
10
10
Epoch
Epoch
SCC
Trein Loss
10a1
101d
10-3
100
Epoch
Figure 7: Effect of using Cayley Graph propagation on the train loss.
23

---

J Alignment gives closer convergence
Binary Search
100
Task Train Loss
10-1
10-2
10-3
10
NAR
GAS
DEAR
GS
10-5
20
40
60
8.0
100
Epoch
DAG Shortest Paths
100
DEAR GAS
DEAR w/ GS
Task Train Loss
10-1
10-2
10-3
10-4
10-5
20
40
60
80
100
Epoch
MST Prim
NAR
10
DEAR wi GAS
Task Train Loss
10-1
10
10-4
10-5
60
Epoch
Figure Alignment (orange) leads lower task train loss compared to no aligment, but using stochasticity and GRANOLA (green).
24

---

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

---

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

---

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

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Page 7, bottom; also ?? We did not take precise measures since the very beginning of the project, so we give an approximation.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that cttppuucc//tthiicsssileellllllll
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer:
[Yes]
Justification:
We conformed the code ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification; Our work focuses on the improving NAR reasoners on abstract algorithms, not their real-world applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

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

---

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


Reviews:
[{"review_id": "LOlpvndNfs", "reviewer": "Reviewer_1Bds", "summary": "This paper proposes Deep Equilibrium Algorithmic Reasoner (DEAR) which uses a deep equilibrium model (DEQ) to solve algorithmic tasks in CLRS30. The paper first introduces denotational semantics, which can be used to denote programs. It also provides an overview of Domain theory, and uses it to show that algorithms have fixed points. The paper then trains pointer graph network on algorithms from CLRS30 as a DEQ — fixed point solving is done with Anderson solver. The paper also discusses different methods (including failure cases) that were attempted to further improve performance of DEAR — use of Cayley Graph Propagation and alignment loss. DEAR improves performance over NAR (Neural Algorithmic Reasoner, the preivous state-of-the-art) on many algorithms.", "questions": "1. Why use a partial function in equation 3?\n2. There is some prior work [1] which indicates that more steps to find equilibrium points help with better OOD generalization. From my understanding, DEAR penalizes longer trajectories (due to misalignment with domain theory). Is it possible to get improved performance if we ignore the potential conflict with domain theory? \n [1] Anil, Cem, et al. \"Path independent equilibrium models can better exploit test-time computation.\" Advances in Neural Information Processing Systems 35 (2022): 7796-7809.\n3. What loss objective is used to train DEAR (e.g. cross entropy)? I understand that there are auxiliary losses such as alignment loss in Lines 277-298.", "limitations": "The limitations have been discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The premise of this paper makes perfect sense. Message passing in GNNs is known to converge to an equilibrium. Therefore, it is obvious to combine NAR with DEQs.\n2. DEAR improves OOD generalization of algorithms such as Floyd-Warshall, DFS, SCC, Sorting, and performs comparably to NAR (previous state-of-the-art) on algorithms like Breadth-first search, Minimum.  \n3. DEAR improves inference speed of many algorithms as shown in Appendix G.\n\nOverall, this work is quite novel. While there are some prior works (See Anil et al. 2022) that have applied DEQs on very small GNNs and simple algorithmic tasks, this paper picks up a relatively difficult problem of solving standard algorithms. This hasn't been explored before  with DEQ based architecture.", "weaknesses": "1. DEAR hurts performance on some algorithms like Binary Search (significant drop in performance), DSP, and MST Prime, and the reasoning is unclear. \n2. The authors have done an excellent job at explaining literature that many readers might not be familiar with. However, the readability of paper can be improved further if the authors provide more background on domain theory for those who are not familiar with it. It will also help if some discussion is added in Appendix A. I couldn’t understand it even after attempting to read it multiple times.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks to the reviewer for their thoughtful review, and allow us to address both the comments and questions you have raised.\n\n*DEAR hurts performance on some algorithms like Binary Search… and the reasoning is unclear.*\n\nFirstly, we would like to emphasise that the varied algorithms found in CLRS-30 means that some models are expected to perform better on some tasks compared to others. Thus to highlight the strengths of our model, we have added an average across all algorithms (overall row) found in Table 1 in the rebuttal document.\n\nAs stated by the reviewer, the performance of binary search is an anomaly for DEAR’s performance, therefore we chose to investigate this algorithm further. We found several issues for binary search in CLRS-30 (Veličković et al. 2022): sampling process, calculation of ground truths, and misspecification of output type. Consequently, we ran new baselines of the search algorithm (Table 2; rebuttal PDF). With this change, the new overall for DEAR is 7% higher than the baseline NAR, and comparable to both Triplet-MPNN variants. Additionally, our decreased performance on binary search is due to overfitting. Our investigation shows that this is a data-hungry algorithm. To verify this claim, we trained 1 seed with three times larger training data (same number of epochs) and confirmed we got close to perfect performance.\n\nTo provide further clarification of the strength of DEAR we will explain the empirical results found in the rebuttal PDF. The main comparison of DEAR is against the baseline NAR, which has an overall performance increase of 4% (Table 1). The NAR model and other non-equilibrium models have access to exact number of steps at both train and test time. The processor (a recurrent GNN) is unrolled for the given number of steps (may differ between samples). As shown in Table 1 for NAR (HCS), the model is susceptible to step change. For certain algorithms 64 steps may be just right, but for others it might be more or less, hardcoding the number of steps makes the performance 15% worse than DEAR.\n\nA fairer comparison is the NAR (LT) model (Table 1; rebuttal PDF), which has a trained architecture to decide the number of steps during test time; we outperform it by 5% overall and with ~1 standard deviation on DSP/MST Prim. To reiterate this LT model is still trained on the exact number of steps, something never given to our model.\n\nFinally, the DEAR approach is independent of the GNN processor architecture, therefore it can be used in conjunction with the state-of-the-art Triplet-MPNN. In Table 5, we train DEAR with TripletMPNN on the subset of the algorithms Triplet-MPNN improves the most. The overall accuracy was increased by 4%, when using DEAR, suggesting that our approach is also architecture agnostic.\n\n*The authors have done an excellent job at explaining literature ... However, the readability of paper can be improved further if the authors provide more background on domain theory ... It will also help if some discussion is added in Appendix A...*\n\nWe thank the reviewer for raising this point as we understand that these topics may be unfamiliar to readers from the deep learning domain. \n\nAs a result, we improved this section to provide a more readable and comprehensive understanding of domain theory. Upon taking your advice, we also added an appendix solely dedicated to the IMP language and added more details regarding the denotation of a while loop in the appendix.\n\nUnfortunately, the NeurIPS rules prevent us from uploading a revised version of the paper. Some of the key improvements to provide yourself the confidence that we have addressed this concern are:\n* Analogies with the elements of popular programming languages, such as C\n* More details on the definition of States\n* Expanded the definition of Commands with more examples\n* More details on the utility of Domain Theory in our setting\n* Further motivation for our theoretical excursion\n\n*Why use a partial function in equation 3?*\n\nThe domain of a denotation is always a State and the codomain depends on the type of expression. For commands, the codomain is also a state. As some commands may not terminate, the denotation for them is undefined, i.e., we have a function which is not defined for some input arguments, hence a partial function.\n\n*There is some prior work [1] which indicates that more steps to find equilibrium points help with better OOD generalization. … DEAR penalizes longer trajectories... Is it possible to get improved performance if we ignore the potential conflict with domain theory?  ...*\n\nWe will make sure to include the provided reference [1] in our paper. Furthermore, we would like to clarify that DEAR does not necessarily penalise longer trajectories. Regularisation is used only in the case we use alignment and even then the loss is normalised by the length of trajectory (see line 487). We are aware of the observation that more steps to find equilibrium points help with better OOD generalisation (reference [31] in our draft) and we used it with the alignment scheme.\n\n*What loss objective is used to train DEAR (e.g. cross entropy)?...*\n\nThe loss function is algorithm specific as specified in the CLRS-30 paper. Thus motivated by this comment, we have emphasised (\\emph)  and reworded L228-229 to make it clearer for any future readers: “Each task is independently learned, minimising the output loss plus any regularisation loss. The exact output loss is algorithm specific, therefore it can be either binary cross entropy or categorical cross entropy, cf. CLRS-30 for further details.”\n\nOnce again we thank the reviewer for their insightful comments and excellent questions. We hope our reply addresses all concerns and questions, such that it may convince you to increase your score. We are of course happy to further engage with the reviewer for any remaining doubt.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "47HmePbOL2", "reviewer": "Reviewer_fLfp", "summary": "This paper explores a novel approach to NAR using GNNs. Traditional NAR models typically use a recurrent architecture where each iteration of the GNN corresponds to an iteration of the algorithm being learned. Instead, this paper proposes that since many algorithms reach an equilibrium state where further iterations do not alter the outcome, it is possible to directly solve for this equilibrium. By training neural networks to find the equilibrium point, the authors aim to improve the alignment between GNNs and classical algorithms, potentially enhancing both the accuracy and speed of NAR models. Empirical evidence from the CLRS-30 benchmark supports the viability of this equilibrium-based approach.", "questions": "1. From reviewer's understanding, denotational semantics primarily motivate the equilibrium methods. \n- The connection between the proposed architecture (PGN with gating) and denotational semantics is not clear. \n- The motivation for equilibrium methods does not seem to require denotational semantics, as graph algorithms such as Bellman-Ford inherently have equilibrium points. \n\nCould the authors provide further clarification on this aspect?\n\n2. It appears that the data for the experiments was generated by the authors rather than from CLRS-30, as they mention \"For each algorithm, we generate\" in Line 219. However, the baseline scores are identical to those reported in previous papers. To ensure a fair comparison, the authors should consider re-running the baselines on their own dataset.\n\n3. From the reviewer's personal perspective, the introduction and contributions sections may not be well-suited for an academic paper in their current form. The investigated problem could benefit from better motivation, and the contributions might not fully capture the paper's key theoretical and empirical results. \n\n4. The training and test graph sizes used in the experiments seem to be relatively small, although consistent with CLRS-30. The reviewer recommends training on larger graphs (e.g., 50 nodes) and testing on even larger graphs (e.g., 300 nodes) to better demonstrate the performance gains of the proposed methods.\n\n5. The experiments presented in the paper are limited to synthetic graph datasets. The reviewer suggests that demonstrating the performance gains on real tasks (e.g., physical systems [1] or mathematical problems [2]) would enhance the contributions of this paper.\n\n6. The authors mention that DEQ models can be difficult to train, which might be due to the instability of DEQ's gradient. The reviewer recommends considering the use of [3] for training the models, as it provides a more stable approach.\n\n[1] Battaglia, Peter, et al. \"Interaction networks for learning about objects, relations and physics.\" NeurIPS 2016.\n\n[2] Lample, Guillaume, and François Charton. \"Deep learning for symbolic mathematics.\" ICLR 2020.\n\n[3] Fung, Samy Wu, et al. \"Jfb: Jacobian-free backpropagation for implicit networks.\" AAAI 2022.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed method is clearly presented.\n\n2. The performance of the proposed method on benchmark datasets is good.", "weaknesses": "1. The transition from denotational semantics to the proposed architecture could be further clarified to improve the overall understanding of the method. (Question 1)\n\n2. It is not entirely clear whether the comparison with the baseline is accurate, and further justification or explanation may be needed. (Question 2)\n\n3. The authors might consider revising the presentation of their contributions to more effectively convey the significance and novelty of the paper to the audience. (Question 3)\n\n4. Including real-world experiments in the paper could substantially strengthen the contributions and further demonstrate the practical applicability of the proposed method. (Question 4, 5)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks to the reviewer for their thoughtful review and directly linking the weaknesses with their questions. We address all the questions below.\n\n*The connection between the proposed architecture (PGN with gating) and denotational semantics is not clear.*\n\nSection 4 serves as a formal motivation for using neural equilibrium models when learning to simulate algorithms. We propose not an architecture (PGN was invented by Veličković et al. 2020), but a new way to decide termination of algorithm simulation both during training and inference. We have now emphasised the connection between DEAR and denotational semantics, especially the paragraph “Finding the fixed point” (section 5, L178 of our paper draft), by referring specifically to the concepts defined in Section 4.\n\nLastly, our proposed model uses PGN due to being a lightweight and well-performant NAR architecture, which serves as the ideal baseline. However, DEAR is architecture agnostic and it can work with Triplet-MPNN (Table 5; rebuttal PDF).\n\n*The motivation… does not seem to require denotational semantics...*\n\nIn our experience, we have observed sometimes intuition can mislead deep learning. (cf. “Understanding deep learning requires rethinking generalisation” by Zhang et al.) Hence, we decided to formally motivate the paper using denotational semantics. This inspired the alignment scheme proposed and the decision to pick the least fixed point if more than one fixed point exists.\n\n*It appears that the data for the experiments was generated by the authors … To ensure a fair comparison, the authors should consider re-running the baselines on their own dataset.* \n\nFor clarification, the results are generated with our data and code except for Triplet-MPNN with casual registration (Bevilacqua et al., 2023) and DEM (Xhonneux et al., 2024); the implementation for both are not public, hence we reported theirs. \n\nHowever, we have taken your advice and generated our own baseline for Triplet-MPNN (Table 1; rebuttal PDF) without casual registration. Commendably, our model performs only 2% worse than a model whose categorically inspired GNN layer considers interactions between each edge and nodes that are not necessarily connected to the edge. This edge-node interaction, of course, comes at the expense of having to materialise O(V^3) messages. The rebuttal PDF (further explained in the global rebuttal) also highlights the strengths of our models compared to our new experiments. DEAR is 4% better than the baseline NAR model.\n\n*From the reviewer's personal perspective, the introduction and contributions sections may not be well-suited for an academic paper in their current form...*\n\nUnfortunately, the NeurIPS rules prevent us from uploading a revised version of the paper. We have rewritten our contributions to more clearly highlight the main outcomes of our paper, which are:\n* The DEQ-NAR connection is formally motivated\n* The first robust equilibrium algorithmic reasoner; the model from the DEM blogpost performs terribly on the simplest task of BFS.\n* A regularisation scheme to encourage alignment with algorithm execution traces when training deep equilibrium neural algorithmic reasoners \n* A comprehensive evaluation that shows DEAR is competitive to a model using a more expressive GNN\n\n*...The reviewer recommends training on larger graphs and  testing on even larger graphs to better demonstrate the performance gains ….*\n\nAs highlighted by the reviewer, the current standard setting in literature is a training size of 16 nodes and a test size of 64 nodes. We appreciate the recommendation, however, given the tight time constraint, our limited hardware access and the requirement of training 10 algorithms, for 3 seeds, for all models (for a fair comparison) the total number of runs goes beyond 100. This provides an interesting setting for future work.\n\nNevertheless, this comment inspired us to evaluate our currently trained models on larger instances (Table 3; rebuttal PDF); 128 nodes (8x), 256 nodes (16x) and 512 nodes (32x). The results highlight that besides certain algorithms (search; see global rebuttal) we are extremely competitive to the baseline. This is offset by the fact that our model is much faster (Table 4; rebuttal PDF; we never exceed 0.5s/sample at any scale) and speedups sometimes exceed 25x-40x.\n\n*The experiments presented in the paper are limited to synthetic graph datasets. The reviewer suggests that demonstrating the performance gains on real tasks ...*\n\nOur experimental procedure follows the standard in the NAR literature. However, the focus of this paper is presenting a different approach for unrolling an algorithm execution which can serve as a new foundational model in NAR Consequently, even though we agree that it is interesting to test these reasoners in real-world scenarios (Numeroso et al., 2023), this is out-of-scope for this paper and would require work that does not align with the NAR standards, our goals and experiments.\n\n*The authors mention that DEQ models can be difficult to train, … The reviewer recommends considering… [3]...*\n\nWe thank the reviewer for the provided reference. However, in this work, we never mention that DEARs are difficult to train; they converge to a slightly larger final training loss, but we found the training overall stable. We kindly ask the reviewer to point us towards any confusing paragraphs and we will add a reference to the mentioned paper as it can be useful for future readers of our work.\n\nOnce again we thank the reviewer for their insightful comments and excellent questions. We hope our reply addresses all concerns and questions, such that it may convince you to increase your score. We are of course happy to further engage with the reviewer for any remaining doubt.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "OTAiINsEN2", "reviewer": "Reviewer_tzFP", "summary": "This paper proposes to solve the neural algorithmic reasoning by attacking the equilibrium solutions directly, without leveraging the recurrent structures which imitate the iterations in algorithms. They proposed deep equilibrium algorithmic reasoner (DEAR), and compare it with baselines including NAR (w/ and w/o Triplet-MPNN).Their training dynamics is shown to be more stable than baselines, and inference time is smaller than than baselines, although the accuracy is sometimes worse than baselines.", "questions": "* I'm not an expert so I have trouble understanding Section 4. Is it possible to make it clearer how does it connect to the proposed algorithm?\n* Eq. (4) seems still a recurrent structure? I was thinking the point of the new method is to get rid of recurrent structures? But looks like from Figure 1, the point is to reduce the number of recursive steps. Is this correct?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The motivation is clear. \n* Experiments are thorough.", "weaknesses": "* It is not immediately clear what is the takeaway from the experiments. My understanding is that efficiency is the key selling point of the new algorithm. However, there is only one table for efficiency in Appendix G.\n* Section 4 is notation heavy and hard to understand. \n* I fully appreciate authors' honesty to report the results (Table 1) which are not to their advantage, but the inferior accuracy seems to limit the usefulness of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks to the reviewer for their thoughtful review, and allow us to address both the comments and questions you have raised.\n\n*It is not immediately clear what is the takeaway from the experiments. My understanding is that efficiency is the key selling point of the new algorithm…*\n\nThe key selling point is that finding the equilibrium is a proper way to decide termination during training and inference time. Equilibrium also acts as an additional architectural bias, giving further boost in accuracy (Table 1; rebuttal PDF). Fixing the number of steps at test time has detrimental effects. Using a dedicated architecture to learn when to terminate the algorithm also falls short of our approach.\n\n*Section 4 is notation heavy and hard to understand.*\n\nWe thank the reviewer for raising this point as we understand that these topics may be unfamiliar to readers from the deep learning domain.\n\nAs a result, we improved this section to provide a more readable and comprehensive understanding of domain theory. Upon taking your advice, we also added an appendix solely dedicated to the IMP language and added more details regarding the denotation of a while loop in the appendix.\n\nUnfortunately, the NeurIPS rules prevent us from uploading a revised version of the paper. Some of the key improvements to provide yourself the confidence that we have addressed this concern are:\n* Analogies with the elements of popular programming languages, such as C\n* More details on the definition of States\n* Expanded the definition of Commands with more examples\n* More details on the utility of Domain Theory in our setting\n* Further motivation for our theoretical excursion\n\nThe goal of our theoretical analysis is to show that there is a well formalised relationship between equilibrium models and algorithms.\n\n*I fully appreciate authors' honesty to report the results (Table 1) which are not to their advantage…*\n\nThe effectiveness of DEAR may be misinterpreted due to the mixture of results for each algorithm. The varied algorithms found in CLRS-30 means that some models are expected to perform better on some tasks compared to others. Thus to highlight the strengths of our model, we have added an average across all algorithms (overall row) found in Table 1 in the rebuttal document.\n\nThe main comparison of DEAR is against the baseline NAR, which has an overall performance increase of 4% (Table 1). The NAR model and other non-equilibrium models have access to exact number of steps at both train and test time. The processor (a recurrent GNN) is unrolled for the given number of steps (may differ between samples). As shown in Table 1 for NAR (HCS), the model is susceptible to step change. For certain algorithms 64 steps may be just right, but for others it might be more or less, hardcoding the number of steps makes the performance 15% worse than DEAR.\n\nA fairer comparison is the NAR (LT) model (Table 1; rebuttal PDF), which has a trained architecture to decide the number of steps during test time; we outperform by 5%. To reiterate this model is still trained on the exact number of steps.\n\nTo further motivate the strengths of our model we opted to include the state-of-the-art processor architecture of Triplet-MPNN. Commendably, our model performs 2% worse than a model that has many other improvements besides equilibrium. In Table 1 there are two versions of Triplet-MPNN, the latter includes causality based regularisation. We had to copy results from related work (Bevilacqua et al., 2023) as we do not have access to their implementation. Triplet-MPNN is a very strong baseline to compare against, as each categorically-inspired GNN layer considers interactions between each edge and nodes that are not necessarily connected to the edge. This edge-node interaction, of course, comes at the expense of having to materialise O(V^3) messages. Notably, the DEAR approach can be used in conjunction with Triplet-MPNN (Table 5; rebuttal PDF), giving a state-of-the-art overall performance (Table 5; rebuttal PDF).\n\nFinally, we investigated binary search as it was an anomaly for DEAR’s performance. We found several issues for binary search in CLRS-30: sampling process, calculation of ground truths and misspecification of output type. As a result, we ran new baselines of the search algorithm (Table 2; rebuttal PDF). With this change, the new overall for DEAR is 7% higher than the baseline NAR, and comparable to both Triplet-MPNN variants.\n\n*…Is it possible to make it clearer how does it connect to the proposed algorithm?*\n\nSection 4 serves as a formal motivation for using neural equilibrium models when learning to simulate algorithms. What we propose is not an algorithm per se, but rather we propose a new equilibrium-based way to decide termination of algorithm simulation both during training and inference. The most elegant way (in our opinion) to formalise this concept is through denotational semantics in comparison with other approaches, such as coalgebras (category theory concept).\n\nIn our revised version we have emphasised the connection between DEAR and denotational semantics, especially the paragraph “Finding the fixed point” (section 5, L178 of our paper draft), by referring specifically to the concepts defined in Section 4.\n\n*Eq. (4) seems still a recurrent structure? ... new method is to get rid of recurrent structures? But ..., the point is to reduce the number of recursive steps. Is this correct?*\n\nThe point is to find a robust way to decide termination in neural algorithmic reasoning that doesn’t greatly compromise accuracy or efficiency. \n\nOnce again we thank the reviewer for their insightful comments and excellent questions. We hope our reply addresses all concerns and questions, such that it may convince you to increase your score. We are of course happy to further engage with the reviewer for any remaining doubt.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "3IG8kY0PqA", "reviewer": "Reviewer_E2D4", "summary": "This work builds deep equilibrium graph neural networks for algorithmic reasoning.  The paper tests their models on a variety of algorithm problems and finds mixed results with some positive and encouraging observations.  One focus of the work is on speeding up NARs, and the paper also proposes regularizers to boost performance. To be honest, I am not an algorithms person, and a lot of ideas in the paper are foreign to me, so I am not confident about my review.", "questions": "N/A", "limitations": "The authors adequately discuss limitations throughout the paper.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written, polished, and clear.  In general, the idea of learning algorithms with neural networks has the potential for practical value, although it seems to me that this paper focuses on emulating existing known algorithms and not learning new ones.  Also, the experiments show encouraging results.", "weaknesses": "The results seem mixed and not entirely positive.\n\nIn my own experiments with DEQs, I’ve found that often they overfit to the solver used during training.  Other solvers can find fixed points, but those fixed points don’t always map on to solutions.  Whether or not the model actually has unique fixed points corresponding to solutions may be worth studying.\n\nThe paper mentions another paper on DEQs for algorithmic reasoning (“Deep Equilibrium Models For Algorithmic Reasoning”), but does not discuss it in detail.  This other paper has a nearly identical title and probably demands a more careful discussion and contextualization.  As is, it would be easy for a reader to think that this paper is the first one to think about DEQs for algorithmic reasoning.\n\nIt might be worth discussing the work on non-GNN recurrent networks for learning algorithms.  For example, I have found that a model from \"End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking\" actually behaves similar to DEQs in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks to the reviewer for their thoughtful review and for finding our paper’s presentation excellent. Allow us to address both the comments and questions you have raised. \n\n*The results seem mixed and not entirely positive*\n\nThe effectiveness of DEAR may be misinterpreted due to the mixture of results for each algorithm. The varied algorithms found in CLRS-30 means that some models are expected to perform better on some tasks compared to others. To highlight the strengths of our model, we have added an average across all algorithms (overall row) found in Table 1 in the rebuttal document.\n\nThe main comparison of DEAR is against the baseline NAR, which has an overall performance increase of 4% (Table 1). The NAR model and other non-equilibrium models have access to exact number of steps at both train and test time. The processor (a recurrent GNN) is unrolled for the given number of steps (may differ between samples). As shown in Table 1 for NAR (HCS), the model is susceptible to step change. For certain algorithms 64 steps may be just right, but for others it might be more or less, hardcoding the number of steps makes the performance 15% worse than DEAR.\n\nA fairer comparison is the NAR (LT) model (Table 1; rebuttal PDF), which has a trained architecture to decide the number of steps during test time; we outperform by 5%. To reiterate, this model is still trained on the exact number of steps.\n\nTo further motivate the strengths of our model we opted to include the state-of-the-art processor architecture of Triplet-MPNN. Commendably, our model performs 2% worse than a model that has many other improvements besides equilibrium. In Table 1 there are two versions of Triplet-MPNN, the latter includes causality based regularisation. We had to copy results from related work (Bevilacqua et al., 2023) as we do not have access to their implementation. Triplet-MPNN is a very strong baseline to compare against, as each categorically-inspired GNN layer considers interactions between each edge and nodes that are not necessarily connected to the edge. This edge-node interaction, of course, comes at the expense of having to materialise O(V^3) messages. Notably, the DEAR approach can be used in conjunction with Triplet-MPNN (Table 5; rebuttal PDF), giving a state-of-the-art overall performance (Table 5; rebuttal PDF).\n\nFinally, we investigated binary search as it was an anomaly for DEAR’s performance. We found several issues for binary search in CLRS-30: sampling process, calculation of ground truths and misspecification of output type. As a result, we ran new baselines of the search algorithm (Table 2; rebuttal PDF). With this change, the new overall for DEAR is 7% higher than the baseline NAR, and comparable to both Triplet-MPNN variants.\n\n*In my own experiments with DEQs, I’ve found that often they overfit to the solver used during training…*\n\nWe thank the reviewer for providing this observation. We have investigated this, in the context of the search algorithm. We observed improved performances indeed (by ~1%) but we found the increase not as substantial compared to other ablations presented in the rebuttal PDF. We integrate this result and other algorithms for the final version of the paper. Nonetheless, this could pose an interesting setting for future exploration.\n\n*The paper mentions another paper on DEQs for algorithmic reasoning …, but does not discuss it in detail…*\n\nThe concurrent work we highlight in our paper does indeed follow a similar research direction and was submitted to a peer-reviewed conference earlier this year, hence the citation. However it is not a paper, but rather a blogpost, and as a result we strongly recommend the reviewer to treat it as such. Of course blogposts are essential for progressing science by publicly exchanging ideas, but pragmatically the timeline from idea creation to a paper publication differs greatly. \n\nThe key differences between our paper and the blogpost are in how we approach using equilibrium points in NAR. We do not claim we were the first to conjecture the existence of this connection (we accredit this to the blogpost). However, we do claim:\n* We thoroughly formalise the DEQ-NAR connection\n* Following the formalisation we build the first robust equilibrium algorithmic reasoner; The model from the blogpost performs terribly on the simplest task of BFS.\n* Our model outperforms non-equilibrium baselines and is competitive to a model using a more expressive GNN \n* We show our model is also efficient\n\n*It might be worth discussing the work on non-GNN recurrent networks for learning algorithms...*\n\nIdeas from this paper are already implemented in our baselines as well as our equilibrium reasoners (eq. 5, L175). U and E are embeddings of input node/edge features, something given to the DEAR model at each step, which is the recall feature. A similar thing to an incremental progress training algorithm has also been seen in NAR, where trajectories are chunked into independent segments, but we did not find it necessary for the good performance in NAR.\n\nOnce again we thank the reviewer for their insightful comments and excellent questions, especially in regards to their insights about DEQs that present interesting avenues of future work. Consequently, even though you state you’re not an “algorithm person”, we strongly respect your viewpoints and intuition and we believe your confidence score can be improved; a 3 seems like the minimum as per reviewer guidelines.\n\nFinally, we hope that our rebuttal addresses the empirical strengths of the DEAR model via the updated results and the differences between the blogpost and paper, such that it may convince you to increase your score. We are of course happy to further engage with the reviewer for any remaining doubt.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We thank the reviewers for their thorough reviews and insightful comments. Each review has helped improve our paper by identifying areas that may have been misinterpreted and required further clarification. Here, we address the most important points which were raised by several of the reviewers.

*DEAR is a foundational model*

DEAR is a new equilibrium-based way to decide the termination both during training and inference in the setting of NAR. Using deep equilibrium models (DEQs) is motivated well theoretically, our empirical evidence suggests that equilibrium serves as an implicit bias towards better generalising solutions. While we refer to DEAR as a “model” in our paper, it is rather a *class of models* / *foundational model* as it can natively support different types of processors (Table 5; rebuttal PDF). DEAR targets specifically NAR, and any NAR application out there, e.g. Numeroso et al. (2023; ICLR), may benefit from it, but the purpose of the paper is to motivate the DEQ$\leftrightarrow$NAR relationship and integrate DEQs with NAR models.

*DEAR improves on the baselines and can achieve competitive results with highly advanced GNNs*

During the rebuttal period, we conducted new experiments showing DEAR is better than all other baselines that are of the same size/complexity class; this does not include Triplet-MPNN. This is especially exemplified on methods that are not given termination information at test time and also over methods that are given the ground-truth number of steps. After resolving anomalies with CLRS-30 (we give details below), DEAR with PGN outperforms comparable baselines and closely matches TripletMPNN with causal regularisation (2% difference).

If DEAR is used with Triplet-MPNN (Table 5), we achieve the best overall performance from all models. 

Summary of new experimentations and updated results:
* We have added an overall model performance metric across all algorithms. DEAR outperforms baseline models of its size.
* We have shown that standard NAR models are fragile, w.r.t. changing the number of steps, showcasing that a good termination condition is essential to good performance.
* We compared a model that uses a dedicated NN layer to decide termination and we achieved a 5% overall improvement.
* We highlighted (by diamonds; see Table 1; rebuttal PDF) that our model *never* uses any ground-truth termination information – neither at train time nor at test time.
* We have included extreme out-of-distribution up to 32x larger sizes (Table 3; rebuttal PDF) tests with DEAR.
* We have included efficiency measures at those scales, showing that our model can improve inference speeds substantially, while still being performant (Table 4; rebuttal PDF).
* We have included Triplet-MPNN experiments as a baseline and combined with DEAR. We note that Triplet-MPNN is more computationally expensive, so we could manage to only train on a subset of the algorithms (Table 5; rebuttal PDF). We gave priority to those algorithms, that non-DEQ Triplet-MPNN improves over non-DEQ NAR, such as FW/DFS/etc.

*(Binary) Search anomalies*

**For those familiar with CLRS-30 (Veličković et al. 2022)**: The computation of the ground location in the official CLRS-30 implementation, which we use to generate the data, is slightly noisy.

In Binary Search, we aim to find the place to insert the target value `x` in the sorted array. Thus we need to point to the graph node that holds the smallest value in the array `A`, which is greater than `x`. However, if `x>max(A)` the answer is a pointer to the last value of the array, which by the convention used by CLRS-30 means we’d be inserting `x` at the wrong place. In other words, the answer to `A=[0.1, 0.2, 0.3] x=0.25` and `A=[0.1, 0.2, 0.3] x=0.35` is the same – insert x to the left of 0.3. This contributed some noise, so we fixed the sampler to always give `x` within `[0, max(A))`. 

The other changes were to explicitly use `graph+pointer` instead of `node+mask_one` as the location and datatype of the pointer to the position in the array. This is something also done by Engelmayer et al. (2024). We also add an additional supervision signal, as done in Engelmayer et al. (2024), but at the output level rather than the hint level, since DEAR decouples algorithm iterations and solver iterations (L197-203; our paper draft).

**We have, of course, reran all models with this new search algorithm.** (Table 2; rebuttal PDF)

*Denotational Semantics*

Some of you raised the concern that Section 4 is hard to read and understand. As a result, we spent considerable time improving that part, and its corresponding appendix. We have added a new appendix dedicated to IMP. However, the NeurIPS rebuttal rules prevent us from being able to share the revised revisions, thus we opted to provide detail in individual replies by highlighting the changes we have made.

 
-----------
 

Summary of all the new changes:
* Highlighting key contributions of our paper:
  * The first robust equilibrium algorithmic reasoner; the model from the DEM blogpost performs terribly on the simplest task of BFS.
  * A regularisation scheme to encourage alignment with algorithm execution traces when training deep equilibrium neural algorithmic reasoners.
  * A comprehensive evaluation that shows DEAR is competitive to a model using a more expressive GNN.
  * Greatly improved efficiency – the speedup gains are sometimes as high as 50x (Table 4, rebuttal PDF) and we never exceed 0.5s/sample even at the most extreme scales.
  * Improved denotational semantics chapter & appendices, better connection with other sections and improved motivation of our theoretical excursion.
* The DEQ-NAR connection is formally motivated.
* Many new experiments showing integrating equilibrium with NAR results in strong models irrespective of the GNN architecture chosen as the processor.

Meta-review: After carefully reading the reviews and rebuttal, as well as looking over the paper, I feel this work is ready for acceptance. The idea to use equilibrium-based approach to decide termination is interesting and of value to the community. I urge the authors to incorporate all the additional clarifications and details that they provided in the camera ready version of the paper.
I would also suggest punctuating the limitation of the method as well in an explicit paragraph in the camera ready, outlining the underlying assumption made by the approach and when it could fail (to the extend this is clear). In general, determining whether an algorithm terminates and when is an NP-complete problem, therefore it feels natural for there to be failure modes of the approach. But even without such a limitation section, the paper provides a new perspective on the problem that I think is very interesting and useful for the community!
Decision: Accept (poster)