Deep Equilibrium Algorithmic Reasoning

Authors: dobrik  georgiev
j j wilson
davide  buffelli
mediatek  research
pietro  liò
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:41:05

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.

Main paper: 
 introduction: 
 Algorithms, while straightforward in theory, become challenging to 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 to "collapse" reality into a 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 to 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 performance can be achieved through alignment [55] -submodules of the model architecture correspond to easy-to-learn subparts of the algorithm (or class of). Graph Neural Networks (GNNs) have emerged as the most convenient architecture to 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 a 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 message-passing function [21] takes into account 3-node interactions.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 at the time of algorithm termination. For the algorithms in the CLRS-30 algorithmic reasoning benchmark [45] once the optimal solution is found, further algorithm iterations will not change it. 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 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 a 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)The main proposed application of NAR is settings where one wants to apply an algorithm, but it is impossible to represent reality with a single scalar, hence an "executor" operating in vector space and faithful to the algorithm is required [47, 50] . As NAR models are neural clones of algorithms, they need to provide correct output even for previously unobserved input sizes. Achieving robust out-of-distribution (OOD) generalisation is tricky. To this end a plethora of works have dedicated their attention to it - [8, 13, 14, 42] to name a 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 or any properties of the last state, such as equilibrium. This work, similarly to Xhonneux et al. [53] , studies neurally finding solutions to algorithms by relying on the equilibrium property. We, however, attempt to 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. 
background: 
 Algorithmic Reasoning Let A : I A → O A be an algorithm, acting on some input x ∈ I A , producing an output A(x) ∈ O A and let I A /O A be the set of possible inputs/outputs A can read-/return. In algorithmic reasoning, we aim to learn a function A :I A → O A , such that A ≈ 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 1 on the intermediate states of the algorithm. To capture the execution of A on an input x we can represent it as h0 = PREPROC(x) (1a) hτ = A t (. . . A t τ times ( h0 ) . . . ) (1b)A(x) = POSTPROC( hτ ) (1c)where PREPROC and POSTPROC are some simple pre-and post-processing (e.g.initialising auxiliary variables or returning the correct variable), hτ ∈ H A is A's internal (hidden) state, A t is a subroutine (or a set of) that is executed at each step and the number of steps depends on a boolean property being satisfied (e.g. all nodes visited). It is therefore no surprise that the encode-process-decode 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 = g A • P • f A , where g A : I A → R dand f A : R d → O A are the encoder and decoder function respectively (usually linear projections) and P : R d → R d is a processor that mimics the rollout (Equation 1b) of A. The processor often uses a message-passing GNN at its core.The CLRS-30 benchmark [45] includes 30 iconic algorithms from the Introduction to Algorithms textbook [11] . Each data instance for an algorithm A is a graph annotated with features from different algorithm stages (input, output, and hint), each associated with a location (node, edge, and graph). Hints contain time series data representing the algorithm rollout and include a 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 out-of-distribution (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 are of the form:EQUATIONwhere x is input, f θ is a function parametrised by θ (e.g. a neural network) and z * 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. f[i] θ = f θ . By re-expressing (2) as g θ = f θ (z * , x) -z * DEQs allow us to find the fixed point z * via any black-box root-finding method [e.g. 2, 9], without the actual need to unroll the equation until convergence, allowing us to reduce steps. For backpropagation the gradient ∂L/∂θ could be calculated using the Implicit Function Theorem (cf. 4) and no intermediate state has to be stored, giving us a 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] . It has been identified that the message passing process can be hindered by a 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 a measurement that a 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 (|E| = O(|V |)) with a low diameter [35] , thus offering advantageous properties for information propagation. Consequently, this facilitates messages to be passed between any pair of nodes in a short number of hops, and as a 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 as 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 SL(2, Z n ) and its generating set S n -see p.5 of Deac et al. [12] for details. Note, that the order of a Cayley graph for Z n is |V | = O(n 3 ). 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] .Denotational semantics To every programming language expression2 P denotational semantics provides an interpretation P , which is a 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 IMP3 . It consists of numbers, 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 Turing-complete and all algorithms we experiment with can be defined in it.Denote the set of variable locations with L -those are all variables/array elements we can ever define. A good analogy to think of is the addresses in the language C. For a large portion of the above language, it is trivial and intuitive to define the denotations by structural recursion. For example:if b then c 0 else c 1 = λs ∈ State. c 0 (s) if b (s) is true c 1 (s) otherwise (c 0 ;c 1 ) = λs ∈ State. c 1 ( c 0 (s)) skip = λs ∈ State. sThe only denotation that cannot be expressed recursively, is that of the while construct. EQUATIONŵ is now a function variable. The denotation of w is the fixed point of f b , c , i.e. w = f b , c ( 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 a framework with which we can both find and also characterise solutions for fixed point equations. 4 D → D is monotonic iff ∀d, d ′ ∈ D. (d ⊑ d ′ ⇒ f (d) ⊑ f (d ′ )).In other words, if 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 whichn≥0 f (d n ) = f ( n≥0 d n )are also called continuous. In plain language, if a function is continuous and we are provided with a chain, the lub of f applied to every chain element is the same as f applied to the lub of the chain. An element d ′′ ∈ D is defined to be pre-fixed point if f (d ′′ ) ⊑ d ′′ -applying f does not define anything new. The fixed point f ix(f ) of f is the least pre-fixed point of f . By utilising antisymmetry 6 of ⊑ and the two properties of f ix(f ) (pre-fixed point and least) we can obtain f (f ix(f )) = f ix(f ). By Tarski's theorem [43] , any continuous f : D → D has a least pre-fixed point. This fixed point can be found, by taking the lub of the chain of applications of f:f ix(f ) = n≥0 f n (⊥).The helper function f b,c from Equation 3 is continuous [proof is given on p.120 of 23], therefore a direct result is that if the while b do c 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 a 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 c" constructs within IMP the least fixed point exists and can be found by taking the first "state" of the algorithm where future iterations on it have no effect. In Appendix C 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 in IMP regardless of their implementation size. While BFS is clearly a "while b do 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 c is another while loop on its own (strongly connected components; Listing 3). Fortunately, our approach is not doomed to fail: a single DEQ layer can model any number of "stacked" DEQ layers [32, chapter 4 ].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 a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
deep equilibrium algorithmic reasoning: 
 Architecture We implement our processors/encoders/decoders following Ibarz et al. [29] . The most notable difference 7 to their implementation is that ours uses a sparse graph representation. This requires us to assume a 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 is decoded, are the solution to the equation:EQUATIONwhere P UE (H ( * ) ) = P (H ( * ) , U, E), U/E are the encoded node and edge feature matrices and P is the processor function. H (t) are the stacked latent states of the nodes at timestep t (with H (0) = 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 f θ of a DEQ. Any model using this technique will be called deep equilibrium algorithmic reasoner (DEAR) in our 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.Figure 1 : Proposed alignment rule: every state in the DEAR trajectory should "go forward". Alignments 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 ⊑ may not hold for DEAR's trajectory.Finding the fixed point The torchdeq library provides several solvers. The most basic one is fixed-point iteration, equivalent to repeating Equation 4until 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:EQUATIONThe criteria for pre-fixed point check torchdeq implements is distance-based: for a state H (t) to be considered a pre-fixed point, the distance to the next state has to be under a pre-defined threshold δ.We kept the criteria but modified the library to 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 a decision largely motivated from section 3. Due to a lack of a suitable definition for the domain of NAR trajectories, we define ∀t. H (t) ⊑ H (t+1) , i.e. 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, we 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 a more grounded manner by preserving the complete structure.In GNNs, the benefits of augmenting a graph with virtual nodes and providing message-passing shortcuts have been observed to improve performance in various tasks [10, 26, 27] ; further supported by the theoretical 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 a NAR model can 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 to which algorithm step. While we propose an 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, one obtained from unrolling GNN iterations as in classical NAR and another obtained from using DEAR. We would like to match DEAR to NAR, such that ∀i ≤ j, i ′ ≤ j ′ if we have committed to aligning DEAR stateH (i ′ ) to NAR state H (j)G , we cannot align anyH (j ′ ) to H (i)G and from the same start we would like to reach the same final state. In 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 L 2 norm as a distance metric, we use a dynamic programming algorithm (Appendix F) Figure 2 : Despite converging to slightly higher train loss our models remain stable during optimisation to 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 we switched to GRANOLA [15] ; 2) since f (f ix(f )) = f , we performed a random number of additional iterations [33] and take the last state. The probability of doing s extra steps is 0.5 s . 
evaluation: 
 Setup For each algorithm we generated 10 5 /100/100-sized training/validation/test 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-distribution, so our test samples are of size 64. For algorithms on graphs we generate Erdős-Rényi graphs [17] with edge probabilities p 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 implementation [45] .In our experiments the models have a latent dimensionality of 128, the batch size is 32, the learning rate is 3 × 10 -4 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 δ = 0.1 (and δ 10 on the backwards) and is based on the relative L 2 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 we measure is the out-of-distribution 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] , as no implementation is publicly available, and a NAR architecture with a 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 to understand how we compare to other, architectural alignments, we also provide a comparison with a more expressive processor (Triplet-MPNN).We present results for 10 key algorithms (most of the ones used in Bevilacqua et al. [8] ) in Table 1 .The first set of experiments aims to establish whether learning to execute algorithms by finding the least fixed point is possible. As Xhonneux et al. [53] report that their models Table 1 : Test accuracy for different algorithms and models. Models with a diamond (♢ or ♦) iterate for the correct amount of steps during train time (may differ between datapoints). Filled diamond (♦) means the ground truth number of steps is also given at test time. LT stands for learnt terminationthe model that uses a termination network. For DEM [53] we leave awhen no results are reported and we report two results for shortest path and MST as it 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 on fully-connected graphs. 2 . In line with the previous work, we observed that the DEAR tends to converge to a slightly higher training loss as no algorithm's mean training loss dropped below 0.01. However, as 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 -see Appendix G. We are unaware if Xhonneux et al. [53] observed the same numerical differences, but we were overall satisfied with the convergence of DEARs.EQUATIONEquilibrium 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-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 Bellman-Ford, it outperformed the baseline on Floyd-Warshall, and scored slightly behind on the other two. On unweighted ones, it retained fairly high BFS accuracy compared to DEM and it 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 a 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 a 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 Triplet-MPNN NAR architecture.Effects of using CGP Despite the slightly lower accuracies, our experiments with CGP have not 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. Peralgorithm plots can be found in Appendix I. We believe that the reduced accuracies are due to the 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 in comparison to CGP is 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 to pick algorithms where: 1) The baseline performs reasonably well (90+% accuracy), so as to provide good support; 2) the DEAR underperforms substantially. The algorithms to 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, however, does not represent all reality: Figure 4 shows that the task train loss (loss excluding any regularisers) for the model with alignment 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 that: 1) although GRANOLA+stochasticity 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.DEARs are highly parallel DEAR is not bound to follow sequential trajectories and GNNs are more aligned to parallel algorithms than to sequential ones [16] . As the cost for one step of DEAR (GNN iteration + solver) is at least as high as one step of an NAR model (GNN iteration only), we 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 is that DEAR improves inference times across almost all algorithms. The only ones that were executed slower are: 1) Bellman-Ford and BFS, which are highly parallelised in the CLRS-30 implementation, so an improvement on them was unlikely; 2) Floyd-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-connected components.DEARs are foundational Up until this point, DEAR was run with a PGN processor, which is a 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/architecture. It is rather a 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 Triplet-MPNN 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, as 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 it is possible and even beneficial to merge NAR and DEQs. While our models attained very competitive performance, there are certain limitations that need to be addressed: 1) Better algorithms for alignment can help close the gap even further for Prim'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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: See experimental sections Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: The only exception where we do not report deviations, is DEM [53] -we do not have their code and they do not report standard deviations in their workGuidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: We conformed to the code of ethics Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: See above; we are not LLM research Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 are given.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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 [11] • arithmetic expressions -(5+4)*3, but also A*55. Note how variables can be parts of arithmetic expressions.• boolean expressionstrue, false, but also X==0, 3*A<B and X==0 ∧ 3*A<B. Note how boolean expressions can be made by using variables or using boolean logic on subexpressions.• commands -Commands can be one of:skip, which is a no-op -X:=a, where X is assigned the value of arithmetic expression a. An example a is 3*B+C Below, we will denote the state as [A → a, B → b, . . . ]. It means that the value of variable A is a and so on.Consider the facorial example from above removing the explicit set of Y to 1. To find the denotation w = while X > 0 do (Y:=X*Y; X:=X-1) , we first define our f b,cf b,c (w)([X → x, Y → y]) = w ([X → x -1, Y → y * x]) if X > 0 [X → x, Y → y] otherwiseThe equivalent definition if we were to keep the lambdas from the original text isf b,c = λw ∈ (State ⇀ State).λs ∈ State. w ([X → x -1, Y → y * x]) if X > 0 [X → x, Y → y]otherwise but we will work with the first definition as it is more compact.The approximations of f n b,c starting from f 0 b,c = ⊥ are:f 1 b,c = f b,c (f 0 b,c )([X → x, Y → y]) = = f b,c (⊥)([X → x, Y → y]) = ⊥ ([X → x -1, Y → y * x]) if x > 0 [X → x, Y → y] otherwise = undefined if x > 0 [X → x, Y → y] otherwise f 2 b,c = f b,c (f 1 b,c )([X → x, Y → y]) = f 1 b,c ([X → x -1, Y → y * x]) if x > 0 [X → x, Y → y] otherwise =    undefined if x -1 > 0 [X → x -1, Y → y * x] if x -1 = 0 [X → x, Y → y] if x ≤ 0 =    undefined if x > 1 [X → 0, Y → y] if x = 1 [X → x, Y → y] if x ≤ 0 f 3 b,c = f b,c (f 2 b,c )([X → x, Y → y]) = f 2 b,c ([X → x -1, Y → y * x]) if x > 0 [X → x, Y → y] if x ≤ 0 =        undefined if x -1 > 1 [X → 0, Y → y * x] if x -1 = 1 [X → x -1, Y → y] if x -1 ≤ 0 [X → x, Y → y] if x ≤ 0 =        undefined if x > 2 [X → 0, Y → y * 2] if x = 2 [X → 0, Y → y] if x = 1 [X → x, Y → y] if x ≤ 0 . . . which for n is: f n b,c =    undefined if x ≥ n [X → 0, Y → y * (x!)] if 0 < x < n [X → x, Y → y] if x ≤ 0 The sequence obeys f 0 b,c ⊑ f 1 b,c ⊑ f 2 b,c ⊑ • • • ⊑ f n b,c ⊑ . . . (we can see that whenever f n-1 b,c is defined it agrees with f n b,c ) and f b,c is monotonic (f k b,c ⊑ f l b,c =⇒ f b,c (f k b,c ) ⊑ f b,c (f l b,c )). For a given X = x, f x+1 b,c = f x+2 b,c= . . . . The fixed point is the lub of the whole sequence is therefore:f ∞ b,c = n≥0 f n b,c (⊥) = [X → 0, Y → y * (x!)] if x > 0 [X → x, Y → y] if x ≤ 0By a similar analysis, it is not hard show that the denotation of while true do skip will be undefined. 8C Can algorithms, as implemented in CLRS-30, have an equilibrium?In this appendix, we have copied over some algorithms implementations from CLRS-30 9 . Additionally, we have annotated how and when they follow the while b do c construct. Algorithms, that are not necessarily solved via this construct (e.g. strongly connected components) were also included, so as to showcase if this would break. 24 """ Floyd -Warshall 's all -pairs shortest paths ( Floyd , 1962) . """ 80 if msk [i , j ] == 0 or prev_D [i , k ] + prev_D [k , j ] < D [i , j ]: 81 D [i , j ] = prev_D [i , k ] + prev_D [k , j ] 82 Pi [i , j ] = Pi [k , j ]Our differences are mostly required by software engineering rather than research, hence they live here. Differences are:• 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 at 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 to saying probability for each other node to be predecessor should not drop below 10 -6 .For a 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 a given instance, when two H (t) and H (t ′ ) are under the threshold δ, for some t ≤ t ′ , the torchdeq library prefers the state that has the lower distance to next state. Consequently, out the returned fixed points only one is guaranteed to 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.Assume we have computed pairwise distance matrices between the states and those are stored in a T × T G distance matrix D with elements d i,j . Ignoring the required alignment of the last states, we focus on aligning the rest of the states. This is done via standard dynamic programming algorithm.The dynamic programming state we define is as follows: dp i,j is the most optimal alignment for the first i DEAR states and first j NAR states, with dp 0,j = 0 (having leftover NAR states mean we skipped some, but we do not want to penalise that) and dp i,0 = ∞ (we want to align all DEAR states). We consider two recursive formulas, first one we use, the other we use when T ≤ T G :• when the T > T G , there are extra states. To avoid infinities we will allow for two DEAR states to align to a same state:dp i,j = min    dp i-1,j + d i,jaligning DEAR state i and NAR state j, but allowing for previous states to align to it as well dp i,j-1 skipping alignment with state j• when the T ≤ T G we require that each DEAR state aligns to an unique NAR state: dp i,j = min dp i-1,j-1 + d i,j aligning DEAR state i and NAR state j dp i,j-1 skipping alignment with state jWe have highlighted the difference to the above in purple.The optimal alignment for the whole two sequence is stored in dp T,T G . As both H (0) and HG are concatenation of 0 vectors (due to how we initialise the latent state), their distance is 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 dp T -1,T G -1 and always (even when subsampling, see below) add the distances between the last states to the loss function.As the above will always penalise longer DEQ trajectories, we divide dp T -1,T G -1 by T -1 before 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(⌊ T -1 2 ⌋, 1) DEAR states and apply the dynamic programming algorithm with the subsampled sequence. [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 is large enough to give a slight overall advantage to 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 × -5×, test accuracy becomes comparable to other models, regardless of which version is used.I Training loss: DEAR vs DEAR w/ CGP 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Source code available here: https://github.com/HekpoMaH/DEAR 38th Conference on Neural Information Processing Systems (NeurIPS 2024).Recent research[8,37] has shown that alternative, causality-inspired, ways of alignment also exist.Note the abuse of notation. For this subsection, we will forget we use P for the neural processor.Due to space constraints, we omit the formal language definition (Winskel[52], p. 11-13), and we use a condensed version[18] of the denotational syntax, given in Chapter 5 of Winskel[52].For detailed definitions and proofs, please refer to §5.4 of Winskel[52].It is reflexive, transitive and anti-symmetric.a ⊑ b and b ⊑ a implies a = bSee Appendix D for others not mentioned in the main textomitted in this text -see Winskel[52]https://github.com/google-deepmind/clrs/tree/master/clrs/_src/' msk ': np . copy ( prev_msk ) ,# ( order of visiting depends on finishing time ; 


Decision: 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!

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. DEAR hurts performance on some algorithms like Binary Search (significant drop in performance), DSP, and MST Prime, and the reasoning is unclear. 
2. 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.
questions: questions: 1. Why use a partial function in equation 3?
2. 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? 
 [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.
3. 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: limitations: The limitations have been discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The transition from denotational semantics to the proposed architecture could be further clarified to improve the overall understanding of the method. (Question 1)

2. It is not entirely clear whether the comparison with the baseline is accurate, and further justification or explanation may be needed. (Question 2)

3. 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)

4. 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)
questions: questions: 1. From reviewer's understanding, denotational semantics primarily motivate the equilibrium methods. 
- The connection between the proposed architecture (PGN with gating) and denotational semantics is not clear. 
- The motivation for equilibrium methods does not seem to require denotational semantics, as graph algorithms such as Bellman-Ford inherently have equilibrium points. 

Could the authors provide further clarification on this aspect?

2. 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.

3. 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. 

4. 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.

5. 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.

6. 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.

[1] Battaglia, Peter, et al. "Interaction networks for learning about objects, relations and physics." NeurIPS 2016.

[2] Lample, Guillaume, and François Charton. "Deep learning for symbolic mathematics." ICLR 2020.

[3] Fung, Samy Wu, et al. "Jfb: Jacobian-free backpropagation for implicit networks." AAAI 2022.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* Section 4 is notation heavy and hard to understand. 
* 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.
questions: 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?
* 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: limitations: The authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: The results seem mixed and not entirely positive.

In 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.

The 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.

It 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.
questions: questions: N/A
limitations: limitations: The authors adequately discuss limitations throughout the paper.

Comments: title: Thanks for your response
comment: Thank you for taking the time to read our rebuttal. We are happy we have addressed all your questions through our detailed response, and will ensure that the updated experiments and additional literature on domain theory will be included in our paper. For these reasons, could we therefore kindly ask if there is any particular reason why you have not increased your score? We found your review insightful and it helped strengthen our paper. Please let us know if you have any further questions or suggestions.
Thank you for your detailed responses my questions. I hope the authors will include the new experiments as well as additional literature on domain theory as promised. I would like to retain my score.
We would like to sincerely thank you again for the insightful feedback from your rebuttal, and for additionally raising your score. We truly believe you helped strengthen our paper. Please let us know if you have any further suggestions to help us improve our work.
Thank you for taking the time to read our rebuttal. We believe we have addressed all your concerns, therefore could we kindly ask if there is any particular reason why you have not increased your score or confidence?  We found your review insightful and would be happy to listen to further comments. We are available for any additional concerns or questions.
Thanks for your response.  I keep my review.
I want to thank the authors for nicely addressing my concerns. Therefore, I'm raising my score.
Although the performance of the proposed method is superior, I am not convinced that the motivation outlined by the authors differs significantly from any other theoretically inspired motivations. Therefore, I will maintain my score as a borderline accept.
We thank the reviewer for promptly replying to our rebuttal and we’re glad we were able to address some of your concerns.

*[..] the term 'formal motivation' used by the authors in reference to denotational semantics has left me a bit perplexed. [..] the connection between denotational semantics and graph reasoning problems seems tenuous [..]* 

We appreciate the comment from the reviewer, and we would like to clarify that we do not aim at providing a connection between "denotational semantics and graph reasoning problems", but rather to provide a connection between finding the fixed point of a function and executing an algorithm to termination. This then provides an analogy between finding the fixed point of a neural algorithmic reasoner and executing an algorithm to termination, which is the base motivation of our proposed method. We will change our language in our paper to remove any ambiguities and make clear that we use the mathematical background as a strong motivating factor for our method.

*[..] I have reservations about the ethical implications of reusing scores from a previous paper [..]*
We understand the comment from the reviewer and we would like to add a comment, as perhaps the words used should be related to scientific rigour, rather than ethical concerns.

Reporting results from other papers, providing proper citation and mention (we agree that it would be extremely unethical without this), is a common practice in literature, especially when the code for some models is not made public. We make sure to use the **same data generation code** used by all considered papers in the literature. For CLRS there isn't a predefined dataset, but rather everyone uses the same data-generation library, ensuring the same data distribution. 

We note however, that there is some [official downloading code](https://github.com/google-deepmind/clrs/blob/d1c2ad7af8437c7536cf329d9cef8fdf93184d9d/clrs/examples/run.py#L152) for test data generated with CLRS. All algorithms are reported in the results below except for SCC. This algorithm was skipped as pointers in the downloaded dataset were not in the edge-set. PyTorch Geometric does not support this feature and this difference will be mentioned in Appendix B within our paper.

We report results with DEAR on all remaining algorithms. They are consistent with our data and even improve on DSP, Bellman-F. and Floyd-W..

| Algorithm          | Mean    | Std Dev  |
|--------------------------|---------|----------|
| Bellman-F.       | 98.59%  | 0.34   |
| Floyd-W.       | 63.92%  | 0.04   |
| DSP           | 92.95%  | 1.38   |
| MST Prim            | 89.33%  | 1.09   |
| BFS                 | 99.65%  | 0.15   |
| DFS                  | 38.27%  | 0.82   |
| Search (Binary)       | 74.00%    | 11.5    |
| Minimum            | 99.33%  | 1.15   |
| Sort (Ins)    | 85.48%  | 6.90   |


We thank the reviewer again for all the insightful comments, and remain available for further clarifications if any doubts remain.
I appreciate the authors' efforts to address my concerns, which has led me to increase my evaluation to a score of 5. The size generalization performance of DEQ is particularly noteworthy, aligning with the out-of-distribution generalization capabilities demonstrated in previous DEQ studies. 

Concerning the first point, the term 'formal motivation' used by the authors in reference to denotational semantics has left me a bit perplexed. While I recognize the attempt to provide a theoretical grounding, it appears to me more as an intuition rather than leading to a rigorous formal derivation that substantiates the utility of DEQ in graph reasoning. Moreover, the connection between denotational semantics and graph reasoning problems seems tenuous, with the only clear link being the capability to solve such problems through programming.

As for the second point, **I have reservations about the rigorousness of reusing scores from a previous paper when the test dataset has changed**, but I am not sure about it.