Research map / Large language models / Agents, code and math
Open-Book 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 open-book neural algorithmic reasoning, where a NAR network attends over encoded training instances (via cross-attention) during training and testing, improving CLRS-30 performance and enabling interpretable multi-task analysis via attention weights.
Problem
Neural algorithmic reasoning models predict algorithm executions only from their parameters and a single input instance, ignoring the training set; the paper asks whether giving networks access to training examples at reasoning time improves CLRS-30 performance.
Approach
An open-book framework adds a dataset encoder that maps each training data point (state pairs) to a latent vector, and an open-book processor that cross-attends from the current hidden states to these training representations before decoding; attention weights between tasks are then used to interpret multi-task relationships.
Key results
- Open-book Triplet-GMPNN reaches 82.91% overall average test accuracy on CLRS-30 versus 75.98% for Triplet-GMPNN and 66.04% for prior best.
- Multi-task augmenting with open-book framework closely matches or exceeds Triplet-GMPNN multi-task training on most tasks.
- Paired-task training (task with its highest-attention partner) beats single-task training on most selected tasks, e.g., Knuth-Morris-Pratt 19.51% to 65.67%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the open-book framework to the best of PGN, MPNN, or Triplet-GMPNN | CLRS single-task models · CLRS Overall Average | accuracy: 75.98% -> 82.91% | Helped |
| Add the open-book framework | Triplet-GMPNN · CLRS tasks | accuracy | Mixed |
| Use auxiliary data from all CLRS tasks instead of only the target task's dataset | Triplet-GMPNN open-book framework · CLRS tasks | accuracy | Mixed |
| Pair the target task with its highest-attention auxiliary task rather than using single-task training | Triplet-GMPNN · Insertion Sort | accuracy: 78.14%±4.64 -> 95.78%±0.80 | Helped |
| Pair the target task with its highest-attention auxiliary task rather than using single-task training | Triplet-GMPNN · Knuth-Morris-Pratt | accuracy: 19.51%±4.57 -> 65.67%±12.36 | Helped |
| Pair the target task with its highest-attention auxiliary task rather than using single-task training | Triplet-GMPNN · Jarvis’ March | accuracy: 91.01%±1.30 -> 94.44%±0.63 | Helped |
| Pair the target task with its highest-attention auxiliary task rather than using single-task training | Triplet-GMPNN · Dijkstra | accuracy: 96.05%±0.60 -> 97.44%±0.50 | Helped |
| Increase the number of auxiliary data points across the tested range (ablation) | Open-book framework · CLRS single-task augmenting | accuracy | No clear effect |
| Increase training graph size across the tested range (ablation) | Open-book framework · CLRS single-task augmenting | accuracy | No clear effect |
| Increase test graph size across the tested range (ablation) | Open-book framework · CLRS single-task augmenting | accuracy | No clear effect |
Surprising findings
- Most tasks attend most strongly to auxiliary tasks outside their own algorithmic category, contrary to expectations.
- Open-book augmentation can be counterproductive on some tasks, e.g., DFS, Quickselect, and Optimal BST drop relative to baselines.
Limitations
- Performance is counterproductive on some tasks, and the authors state refining the architecture to improve all tasks remains a challenge.
- Relatively large standard deviations on some tasks, attributed to variability in sampled auxiliary data at test time.
- Scalability experiments omit string and quickselect tasks due to memory constraints on larger graphs.
Experimental setup
Datasets: CLRS Algorithmic Reasoning Benchmark
Benchmarks: CLRS-30
Metrics: F1 score accuracy
Baselines: PGN MPNN Triplet-GMPNN Memnet NPQ
Builds on: Encode-Processor-Decode Triplet-GMPNN PGN MPNN
Closest papers by meaning
- Deep Equilibrium Algorithmic Reasoning (NeurIPS 2024 · similarity 0.87)
- Primal-Dual Neural Algorithmic Reasoning (ICML 2025 · similarity 0.86)
- On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods (ICLR 2024 · similarity 0.85)
- Discrete Neural Algorithmic Reasoning (ICML 2025 · similarity 0.85)
- Neural Reasoning Networks: Efficient Interpretable Neural Networks with Automatic Textual Explanations (AAAI 2025 · similarity 0.85)
- OpenThoughts: Data Recipes for Reasoning Models (ICLR 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.