Research map / Learning theory and algorithms / Combinatorial and search optimization
Discrete Neural 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 Discrete Neural Algorithmic Reasoners (DNAR) that keep execution states discrete via hard attention, discrete bottlenecks, and a separate discrete scalar-update module, achieving perfect out-of-distribution scores on SALSA-CLRS and CLRS-30 tasks.
Problem
Neural algorithmic reasoners generalize poorly out-of-distribution to larger graphs, because continuous internal computations drift under distribution shift, and their learned algorithms are hard to interpret or verify.
Approach
Force the processor to keep node and edge features in a finite set of discrete states using discrete bottlenecks and hard attention, separate continuous scalars from the state flow so they only affect attention priorities, and update scalars via discrete increment/keep/push operations selected by states.
Key results
- DNAR achieves 100% node and graph-level scores on BFS, DFS, SP, Prim, MIS and Eccentricity from size 16 up to 1600 nodes on SALSA-CLRS, while GIN and PGN degrade substantially at larger sizes.
- On CLRS-30 (size 64 test graphs), DNAR scores 100% node-level on BFS, DFS, SP and Prim, versus 74-100% for Hint-ReLIC and G-ForgetNet baselines.
- Replacing the discrete scalar updater with a continuous one drops Dijkstra graph-level accuracy to 0.0 at size 80 and beyond in the ablation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use discrete neural reasoning with hint supervision | DNAR · SALSA-CLRS tasks at size 1600 | node- and graph-level accuracy: DNAR achieves 100. / 100. on BFS, DFS, SP, Prim, and MIS; PGN scores are 98.5 / 0.0, 23.1 / 0.0, 84.5 / 0.0, 66.8 / 0.0, | Helped |
| use DNAR rather than the strongest reported baseline | CLRS-30, size 64 · BFS | node-level accuracy: 99.96 ± 0.0 -> 100. ± 0.0 | Helped |
| use DNAR rather than the strongest reported baseline | CLRS-30, size 64 · DFS | node-level accuracy: 100. ± 0.0 -> 100. ± 0.0 | No clear effect |
| use DNAR rather than the strongest reported baseline | CLRS-30, size 64 · SP | node-level accuracy: 99.14 ± 0.1 -> 100. ± 0.0 | Helped |
| use DNAR rather than the strongest reported baseline | CLRS-30, size 64 · Prim | node-level accuracy: 95.19 ± 0.3 -> 100. ± 0.0 | Helped |
| remove all discrete bottlenecks (ablation) | DNAR · SALSA-CLRS BFS, size 1600 | graph-level accuracy: 100. -> 0.0 | Hurt |
| replace hard attention with regular attention (ablation) | DNAR · BFS on complete bipartite graphs, size 800 and 1600 | correct pointer attention weight: 0.97 (+) -> 0.86 (+) -> 0.76 (+) -> 0.38 (-) -> 0.24 (-) | Hurt |
| replace discrete ScalarUpdate with a regular attention-based network (ablation) | DNAR · SALSA-CLRS Dijkstra, size 1600 | node-level accuracy: 100. -> 11.8 | Hurt |
| replace discrete ScalarUpdate with a 2-layer addition MLP (ablation) | DNAR · SALSA-CLRS Dijkstra, size 1600 | node-level accuracy: 100. -> 22.2 | Hurt |
| train without hint supervision (ablation) | DNAR no-hint BFS model · BFS validation graphs, size 16 | node-level accuracy: 100. -> 94 | Hurt |
| train the proposed reasoner on smaller graphs | DNAR · SALSA-CLRS Dijkstra, test size 160 | node-level accuracy: 13 -> 26 -> 100 | Mixed |
Surprising findings
- Without any discrete bottlenecks the model reduces to a plain Transformer Convolution that performs comparably to baselines and degrades at larger sizes.
- Regular (soft) attention still achieves perfect standard test scores on BFS, but fails on adversarial K(2,n-2) graphs due to attention annealing.
Limitations
- Hard attention and discretization reduce expressive power; e.g., mean aggregation over neighbors cannot be done in one step.
- Convergence to the correct model is not guaranteed for all initializations or training distributions.
- No-hint discrete reasoners perform poorly without hyperparameter search and only BFS was explored.
Experimental setup
Datasets: SALSA-CLRS CLRS-30
Benchmarks: SALSA-CLRS CLRS-30
Metrics: node-level accuracy graph-level accuracy
Baselines: GIN Pointer Graph Network Triplet-GMPNN Hint-ReLIC G-ForgetNet
Builds on: CLRS-30 SALSA-CLRS Transformer Convolution Transformer Programs Gumbel-Softmax
Closest papers by meaning
- Deep Equilibrium Algorithmic Reasoning (NeurIPS 2024 · similarity 0.86)
- Primal-Dual Neural Algorithmic Reasoning (ICML 2025 · similarity 0.85)
- On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods (ICLR 2024 · similarity 0.85)
- Open-Book Neural Algorithmic Reasoning (NeurIPS 2024 · similarity 0.85)
- Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks (NeurIPS 2025 · similarity 0.83)
- Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization (NeurIPS 2025 · similarity 0.83)
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.