Research map / Graph learning / Graph algorithms and clustering
Deep Equilibrium Algorithmic Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Deep Equilibrium Algorithmic Reasoners (DEARs) that learn algorithms by finding the least fixed point of a GNN processor via DEQ root-finding, without ground-truth step counts, evaluated on CLRS-30.
Problem
Neural algorithmic reasoning models typically unroll a recurrent GNN for a number of steps matched to the algorithm's iterations, requiring ground-truth step counts at train or test time and being slow at inference.
Approach
Treat the algorithm's final state as an equilibrium of the processor and find it directly with a deep equilibrium model root-finder (Anderson solver), returning the least pre-fixed point; motivated by denotational semantics and domain theory (least fixed point of while loops). Adds alignment loss via DP over trajectories, GRANOLA normalisation, and random extra iterations.
Key results
- DEAR achieves 75.42% overall OOD accuracy vs 71.42% for the NAR no-hint baseline (PGN), with no ground-truth step count at train or test time.
- DEAR with PGN is within about 2% of Triplet-MPNN NAR overall (77.58%).
- DEAR substantially reduces inference time on most algorithms, e.g. DFS 0.0478s vs 0.2440s and sorting 0.0260s vs 0.5680s per sample.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DEAR instead of NAR (Triplet-MPNN) | algorithmic reasoning · DFS | accuracy: 31.20%± 4.02 -> 40.62% ± 0.44 | Helped |
| use DEAR instead of NAR | algorithmic reasoning · Binary Search | accuracy: 94.67% ± 2.31 -> 59.00% ± 12.3 | Hurt |
| use DEAR instead of NAR | algorithmic reasoning · Insertion Sort | accuracy: 63.67% ± 39.97 -> 86.93% ± 3.87 | Helped |
| add Cayley Graph Propagation (ablation) | DEAR · weighted and unweighted graph algorithms | accuracy: 96.78% ± 0.43 -> 94.23% ± 0.59; 55.75% ± 2.20 -> 53.20% ± 2.45; 89.81% ± 0.14 -> 89.49% ± 0.17; 88.67% ± 0.74 -> 86.37% | Hurt |
| add trajectory alignment (ablation) | DEAR · DAG Shortest Paths | accuracy: 89.81% ± 0.14 -> 89.65% ± 2.95 | No clear effect |
| add trajectory alignment (ablation) | DEAR · MST Prim | accuracy: 88.67% ± 0.74 -> 90.37% ± 1.19 | Helped |
| add trajectory alignment (ablation) | DEAR · Binary Search | accuracy: 59.00% ± 12.3 -> 77.33% ± 4.51 | Helped |
| use a Triplet-MPNN processor instead of the default PGN (ablation) | DEAR · Floyd-Warshall, DFS, SCC, Parallel Search, Sort | accuracy: 52.53% ± 0.98 -> 62.29% ± 2.71; 40.62% ± 0.44 -> 42.73% ± 2.79; 43.63% ± 1.19 -> 45.12% ± 1.52; 59.00% ± 12.3 -> 87.00% | Mixed |
| revise the binary-search task specification | DEAR · Overall | accuracy: 75.42% -> 78.38% | Helped |
| use DEAR instead of NAR | algorithmic reasoning · Bellman-Ford | inference time (seconds per sample): 0.0118 -> 0.0215 | Hurt |
| use DEAR instead of NAR | algorithmic reasoning · Insertion Sort | inference time (seconds per sample): 0.5680 -> 0.0260 | Helped |
Surprising findings
- DEAR underperforms badly on binary search with the classic representation (59.00%), which the authors attribute to overfitting on numerical comparisons.
- Cayley graph propagation (CGP) reduced accuracy on most graph algorithms despite improving train loss convergence for some.
Limitations
- Gap to Triplet-MPNN and to step-supervised baselines remains on binary search, Prim and some graph algorithms.
- Model selection on validation data is hard for OOD generalisation.
- CGP overfits because the fixed Cayley graph size differs from test sizes.
Experimental setup
Datasets: CLRS-30
Benchmarks: CLRS-30
Metrics: out-of-distribution test accuracy inference time per sample training loss
Baselines: NAR (PGN, no hint) Triplet-MPNN NAR NAR with learnt termination DEM
Builds on: deep equilibrium models CLRS-30 triplet-MPNN Cayley graph propagation GRANOLA
Closest papers by meaning
- Primal-Dual Neural Algorithmic Reasoning (ICML 2025 · similarity 0.88)
- Open-Book Neural Algorithmic Reasoning (NeurIPS 2024 · similarity 0.87)
- Discrete Neural Algorithmic Reasoning (ICML 2025 · similarity 0.86)
- Simulation of Graph Algorithms with Looped Transformers (ICML 2024 · similarity 0.86)
- On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods (ICLR 2024 · similarity 0.86)
- Equilibrium Reasoners: Learning Attractors Enables Scalable Reasoning (ICML 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.