REVIEW 3 major objections 5 minor 31 references
Open-Book Neural Algorithmic Reasoning
T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read The paper claims that letting a neural algorithmic reasoner attend to compressed summaries of training instances at every reasoning step improves its accuracy on most of the 30 CLRS tasks and can reproduce multi-task training gains at…
desk verdict Real empirical gains on CLRS-30 from training-set cross-attention, but the mechanism is underdetermined without a capacity-matched control. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing device is the open-book processor, a cross-attention module inserted between the base processor and the decoder. At each algorithmic step $t$, the hidden state $h^{(t)}$ is projected into a query, while the row $R^{(t)}$ concatenates the hidden state with a linear projection of the auxiliary representations $R$; a softmax attention over this row produces $\hat{h}^{(t)}$, which is gated with $h^{(t)}$ and fed to the decoder. The auxiliary representations themselves come from a dataset encoder that compresses an entire training instance into one vector by mean-pooling a linear embedding of a randomly sampled adjacent state pair. This two-part machinery creates a trainable information channel from the training set into every reasoning step of the target instance.
What would settle it
Replace the auxiliary representations $R$ in Algorithm 1 with random vectors of the same shape while keeping the dataset encoder and open-book processor parameters intact and retraining; if CLRS F1 scores do not drop materially, the open-book channel is not carrying task information.
Extended reading notes
Core claim
On the CLRS benchmark, the authors show that wrapping any of three existing processors (PGN, MPNN, and Triplet-GMPNN) with a cross-attention open-book processor and a dataset encoder that summarizes auxiliary training instances yields F1 improvements on most of the 30 tasks, raising the overall average from 66.04% for the prior best baseline and 75.98% for Triplet-GMPNN alone to 82.91%. They further show that drawing auxiliary instances from all task datasets can reproduce or exceed full multi-task training while training only the target task, and that the learned attention weights identify task pairings that validate the discovered relationships: paired-task training with the highest-attention partner often outperforms both single-task and full multi-task training.
Load-bearing premise
The load-bearing premise is that one randomly sampled adjacent-state pair, mean-pooled over nodes, retains enough of an auxiliary instance's algorithm execution to give useful cross-attention hints; if that compression discards the signal, the open-book gains would come from extra parameters or sampling noise rather than from training-set knowledge.
Editorial extensions
If this is right
- Existing encode-process-decode NAR architectures can be upgraded to open-book reasoning by inserting the dataset encoder and open-book processor, and the upgrade improves F1 on the majority of the 30 CLRS tasks for all three base architectures tested.
- The overall CLRS average reaches 82.91% with the best open-book configuration, compared with 75.98% for Triplet-GMPNN alone and 66.04% for the previous best among Memnet, PGN, MPNN, and NPQ.
- Auxiliary instances drawn from other tasks can reproduce or exceed full multi-task training while the network is trained only on the target task, so cross-task gains do not require training a single generalist network on all 30 tasks.
- The attention weights over auxiliary tasks can be read as a learned task-relationship map, and paired-task training with the highest-attention partner outperforms full multi-task training on most of the tasks tested.
- Performance remains stable when training graph sizes vary from 4 to 20 nodes and test sizes from 64 to 128 nodes on the tasks tested, indicating the open-book memory does not simply memorize training instances.
Reading between the lines
- One extension the paper leaves implicit is using the learned cross-task attention as a data-driven curriculum: rather than training a generalist on all 30 tasks, a scheduler could select auxiliary tasks by attention weight, potentially reducing cost further than paired training.
- Because the dataset encoder compresses each auxiliary instance to a single mean-pooled vector, the framework suggests a retrieval-style scaling direction in which much larger memory banks are searched by the current hidden state; the paper only tests 240 randomly sampled auxiliary points.
- The single-transition summary being sufficient would imply that adjacent execution states in CLRS are highly redundant across instances, a hypothesis the paper does not test directly but which could be checked by comparing full-state summaries against the compressed ones.
- In a broader reading, the open-book processor turns the training set into a non-parametric memory consulted at every reasoning step, which connects neural algorithmic reasoning to retrieval-augmented inference outside algorithmic tasks.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an open-book learning framework for neural algorithmic reasoning (NAR). In addition to the standard encoder-processor-decoder pipeline, the framework adds a dataset encoder that compresses auxiliary training instances into vector representations and an open-book processor that lets the current hidden state cross-attend to these vectors at every decoding step. The authors instantiate this idea with a concrete attention-based implementation (Algorithm 1), apply it on top of PGN, MPNN, and Triplet-GMPNN, and evaluate on the 30-task CLRS benchmark. They report that the open-book framework improves the base architectures on most tasks, that it can nearly reproduce or exceed full multi-task training at single-task cost, and that the learned attention weights provide an interpretable view of task relationships, which they test in a paired-task experiment.
Significance. If the central claim were established, this would be a useful empirical contribution: a simple, architecture-agnostic recipe that consistently improves NAR accuracy on a standard benchmark, with a natural extension to interpretable multi-task transfer. The paper has clear strengths: it uses the standard CLRS-30 benchmark, includes three base architectures, releases code, reports four-run averages, and provides scaling experiments in the appendix. However, the key attribution---that the improvements come from the open-book memory channel carrying algorithmic knowledge---is not yet supported by the experiments, because no control separates the content of the auxiliary summaries from the extra parameters and regularization introduced by the new modules.
major comments (3)
- [§3.2, Algorithm 1 (lines 5–11); §4.1] The central claim that open-book retrieval of training instances improves reasoning is not yet supported by a control that isolates the information content of the memory channel. Each auxiliary instance is compressed to a single mean-pooled vector of one randomly sampled adjacent state pair, and the open-book processor adds linear, query/key/value, and gating parameters. Without ablations that replace the auxiliary summaries with content-free representations (e.g., random vectors from the same distribution, or summaries with the state-pair information removed), the reported gains could come entirely from the added capacity or from a learned bias over the statistics of R. I ask for at least: (a) a random-memory control, (b) a shuffled-summary control, (c) a capacity-matched baseline that adds the same number of parameters to the base processor without access to auxiliary data, and (d) an oracle control where the auxiliary summary is the true adjacent transition of the target instance. These controls are directly load-bearing for the abstract's claim that the open-book framework itself is responsible for the enhancement.
- [§4.1, Tables 1 and 4] The summary tables are misleading because the column 'Ours' reports the best result across the three open-book architectures, not the result of a single system. This makes it impossible to verify the claim that 'each architecture's reasoning capability can be improved significantly' from the tables alone; the per-architecture bar charts in Figures 2, 4, and 5 show many overlapping standard deviations. Moreover, the baselines are not capacity-matched: the open-book processor inserts extra parameters on top of Triplet-GMPNN, MPNN, and PGN. I request per-architecture aggregate tables with task-level means and standard deviations, paired statistical tests (e.g., paired permutation tests across the 30 tasks), and at least one capacity-matched baseline per architecture so that the improvement can be attributed to the open-book mechanism rather than to model size.
- [§4.4, Table 3] The paired-task experiment is presented as validation of the attention weights, but the selection criterion is not stated quantitatively and the data do not match the description. The text says the authors focus on tasks that 'either demonstrate accuracy improvements or slight declines' in multi-task training, yet Table 3 includes tasks with large multi-task declines, e.g., Jarvis' March (91.01% to 74.51%), Bubble Sort (67.68% to 52.94%), Binary Search (77.58% to 69.30%), Graham Scan (93.62% to 87.74%), Dijkstra (96.05% to 94.29%), and Topological Sort (87.27% to 81.65%). The authors need to define the selection threshold, report all 30 tasks for completeness, and compare paired-task training against control partner selections (e.g., randomly chosen partners or all-pairs training) to substantiate that the attention-selected partner, rather than the mere addition of a second dataset, drives the observed gains.
minor comments (5)
- [Abstract and §1.1] The abstract and contribution list state that the network can 'access and utilize all instances in the training dataset,' but Algorithm 1 and Section 4.1 sample only 240 auxiliary instances per iteration. Please harmonize the wording to 'a sample of training instances' and clarify whether sampling is without replacement within an epoch.
- [§4.1 and §4.3] The claim that multi-task augmenting costs roughly the same as single-task training should be clarified: the dataset encoder must process 240 auxiliary instances per target instance at every training step, so the total computation depends on the auxiliary sample size ℓ. Please report the actual training-time overhead and memory cost relative to the base architecture.
- [Appendix D] The scaling experiments omit string-category tasks and quickselect due to memory constraints; this caveat should appear in the main text wherever 'robust out-of-distribution performance' is claimed, because several of the omitted tasks are exactly those with the largest open-book gains (e.g., Knuth-Morris-Pratt and Naive String Matcher).
- [Figures 2–5] The word 'significant' in the abstract is used in a colloquial sense; given the overlapping standard deviations visible in the bar charts, the authors should add paired statistical tests across the 30 tasks or across the four runs to substantiate the significance claim.
- [§4.4, Tables 2 and 5] The procedure for aggregating attention weights (over nodes, algorithmic steps, and test instances) is described only in words; please give one precise equation defining the reported 30-dimensional attention vector, and state how many test instances are used for the aggregation.
Circularity Check
No significant circularity: the open-book results are empirical comparisons against held-out CLRS test instances, and the framework's use of training-set ground-truth transitions is the method itself rather than a disguised fit.
full rationale
The paper's central claims are empirical: augmenting existing NAR processors with a cross-attention module over compressed training-set representations improves F1 on the external CLRS-30 benchmark. The dataset encoder (Algorithm 1, lines 5-11) summarizes each auxiliary training instance by mean-pooling a linear embedding of one randomly sampled adjacent state pair, and the open-book processor (lines 16-19) computes a gated cross-attention output. This is the proposed architecture, not a derived prediction that reduces to an input by construction. The paper explicitly states in the Remark that during testing the target datapoints come from the test set while auxiliary datapoints come only from the training set, so the target's own ground truth is never accessed at inference time. The paired-task experiment selects partners using attention weights learned on training data and then evaluates on held-out test instances; this is a legitimate, if selection-biased, validation rather than a circular reduction. There are no load-bearing self-citations: the cited baselines and benchmark (Ibarz et al., Velickovic et al., etc.) are external works with no author overlap with the current paper, and no uniqueness theorem is invoked. The skeptical concern that the compressed random-transition summaries may be uninformative and that gains could come from added parameters is a correctness and attribution risk, not a circularity of the kind defined here. Accordingly, the derivation chain is self-contained with respect to its stated empirical claims.
Assumptions & free parameters
free parameters (4)
- auxiliary sample count ℓ =
240
- attention head count =
1
- hidden state dimension =
128
- training schedule =
10,000 Adam steps, batch 32, lr 0.001
assumptions (4)
- domain assumption CLRS-30 benchmark F1 scores measure algorithmic reasoning capability and the provided train/test split is a valid generalization test.
- ad hoc to paper A single randomly sampled adjacent state pair, mean-pooled over nodes, can represent an auxiliary training instance for the purpose of providing hints.
- ad hoc to paper Sampling 240 auxiliary instances is statistically sufficient to represent the training-set distribution for both single-task and multi-task use.
- domain assumption Hyperparameters from the generalist learner [11] transfer to the open-book setting.
Cite this review
Pith. "Pith review of Open-Book Neural Algorithmic Reasoning." pith.science (2026). https://pith.science/paper/2B7CF7W5
@misc{pith2026250100072,
author = {Pith},
title = {Pith review of: Open-Book Neural Algorithmic Reasoning},
year = {2026},
howpublished = {\url{https://pith.science/paper/2B7CF7W5}},
note = {Machine review of arXiv:2501.00072}
}
read the original abstract
Neural algorithmic reasoning is an emerging area of machine learning that focuses on building neural networks capable of solving complex algorithmic tasks. Recent advancements predominantly follow the standard supervised learning paradigm -- feeding an individual problem instance into the network each time and training it to approximate the execution steps of a classical algorithm. We challenge this mode and propose a novel open-book learning framework. In this framework, whether during training or testing, the network can access and utilize all instances in the training dataset when reasoning for a given instance. Empirical evaluation is conducted on the challenging CLRS Algorithmic Reasoning Benchmark, which consists of 30 diverse algorithmic tasks. Our open-book learning framework exhibits a significant enhancement in neural reasoning capabilities. Further, we notice that there is recent literature suggesting that multi-task training on CLRS can improve the reasoning accuracy of certain tasks, implying intrinsic connections between different algorithmic tasks. We delve into this direction via the open-book framework. When the network reasons for a specific task, we enable it to aggregate information from training instances of other tasks in an attention-based manner. We show that this open-book attention mechanism offers insights into the inherent relationships among various tasks in the benchmark and provides a robust tool for interpretable multi-task training.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[1]
Survey of supervised learning for medical image processing
Abeer Aljuaid and Mohd Anwar. Survey of supervised learning for medical image processing. SN Comput. Sci., 3(4):292, 2022
work page 2022
-
[2]
Neural algorithmic reasoning with causal regularisation
Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, and Petar Velickovic. Neural algorithmic reasoning with causal regularisation. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 2272–2288. PMLR, 2023
work page 2023
-
[3]
Hamrick, Larisa Markeeva, Alex Vitvitskyi, Razvan Pascanu, and Petar Velickovic
Wilfried Bounsi, Borja Ibarz, Andrew Dudzik, Jessica B. Hamrick, Larisa Markeeva, Alex Vitvitskyi, Razvan Pascanu, and Petar Velickovic. Transformers meet neural algorithmic reasoners. CoRR, abs/2406.09308, 2024
arXiv 2024
-
[4]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009
work page 2009
-
[5]
Neural algorithmic reasoners are implicit planners
Andreea Deac, Petar Velickovic, Ognjen Milinkovic, Pierre-Luc Bacon, Jian Tang, and Mladen Nikolic. Neural algorithmic reasoners are implicit planners. In NeurIPS, pages 15529–15542, 2021
work page 2021
-
[6]
A survey on cross-domain few-shot image classification
Shisheng Deng, Dongping Liao, Xitong Gao, Juanjuan Zhao, and Kejiang Ye. A survey on cross-domain few-shot image classification. In BigData, volume 14203 of Lecture Notes in Computer Science, pages 3–17. Springer, 2023
work page 2023
-
[7]
Relational attention: Generalizing transformers for graph- structured tasks
Cameron Diao and Ricky Loynd. Relational attention: Generalizing transformers for graph- structured tasks. In ICLR. OpenReview.net, 2023
work page 2023
-
[8]
Graph neural networks are dynamic programmers
Andrew Joseph Dudzik and Petar Velickovic. Graph neural networks are dynamic programmers. In NeurIPS, 2022
work page 2022
Show all 31 references
-
[9]
Schoenholz, Patrick F
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. InICML, volume 70 ofProceedings of Machine Learning Research, pages 1263–1272. PMLR, 2017
2017
-
[10]
Hamrick, Kelsey R
Jessica B. Hamrick, Kelsey R. Allen, Victor Bapst, Tina Zhu, Kevin R. McKee, Josh Tenenbaum, and Peter W. Battaglia. Relational inductive bias for physical construction in humans and machines. In CogSci. cognitivesciencesociety.org, 2018
2018
-
[11]
A generalist neural algorithmic learner
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bosnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Velickovic. A generalist neur...
2022
-
[12]
Neural priority queues for graph neural networks
Rishabh Jain, Petar Velickovic, and Pietro Liò. Neural priority queues for graph neural networks. In The 2023 ICML, Workshop on Knowledge and Logical Reasoning in the Era of Data-driven Learning, volume 202. PMLR, 2023
2023
-
[13]
Few-shot non-parametric learning with deep latent variable model
Zhiying Jiang, Yiqin Dai, Ji Xin, Ming Li, and Jimmy Lin. Few-shot non-parametric learning with deep latent variable model. In NeurIPS, 2022
2022
-
[14]
Recursive algorithmic reasoning
Jonas Jürß, Dulhan Hansaja Jayalath, and Petar Veliˇckovi´c. Recursive algorithmic reasoning. In The Second Learning on Graphs Conference, 2023
2023
-
[15]
Gomez, Thomas Rainforth, and Yarin Gal
Jannik Kossen, Neil Band, Clare Lyle, Aidan N. Gomez, Thomas Rainforth, and Yarin Gal. Self-attention between datapoints: Going beyond individual input-output pairs in deep learning. In NeurIPS, pages 28742–28756, 2021. 11
2021
-
[16]
An introduction to deep learning in natural language processing: Models, techniques, and tools
Ivano Lauriola, Alberto Lavelli, and Fabio Aiolli. An introduction to deep learning in natural language processing: Models, techniques, and tools. Neurocomputing, 470:443–456, 2022
2022
-
[17]
Strong generalization and efficiency in neural programs
Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals. Strong generalization and efficiency in neural programs. CoRR, abs/2007.03629, 2020
2007 arXiv
-
[18]
Weibo Liu, Zidong Wang, Xiaohui Liu, Nianyin Zeng, Yurong Liu, and Fuad E. Alsaadi. A survey of deep neural network architectures and their applications. Neurocomputing, 234:11–26, 2017
2017
-
[19]
Towards better out-of-distribution generalization of neural algorithmic reasoning tasks
Sadegh Mahdavi, Kevin Swersky, Thomas Kipf, Milad Hashemi, Christos Thrampoulidis, and Renjie Liao. Towards better out-of-distribution generalization of neural algorithmic reasoning tasks. Trans. Mach. Learn. Res., 2023, 2023
2023
-
[20]
Supervised machine learning: A survey
Mohammed Amine El Mrabet, Khalid El Makkaoui, and Ahmed Faize. Supervised machine learning: A survey. In CommNet, pages 1–10. IEEE, 2021
2021
-
[21]
A survey on multimodal bidirectional machine learning translation of image and natural language processing
Wongyung Nam and Beakcheol Jang. A survey on multimodal bidirectional machine learning translation of image and natural language processing. Expert Syst. Appl., 235:121168, 2024
2024
-
[22]
Dual algorithmic reasoning
Danilo Numeroso, Davide Bacciu, and Petar Velickovic. Dual algorithmic reasoning. In ICLR. OpenReview.net, 2023
2023
-
[23]
Gaussian processes in machine learning
Carl Edward Rasmussen. Gaussian processes in machine learning. In Advanced Lectures on Machine Learning, volume 3176 of Lecture Notes in Computer Science, pages 63–71. Springer, 2003
2003
-
[24]
Neural algorithmic reasoning without intermedi- ate supervision
Gleb Rodionov and Liudmila Prokhorenkova. Neural algorithmic reasoning without intermedi- ate supervision. In NeurIPS, 2023
2023
-
[25]
Integrating parametric and non-parametric models for scene labeling
Bing Shuai, Gang Wang, Zhen Zuo, Bing Wang, and Lifan Zhao. Integrating parametric and non-parametric models for scene labeling. In CVPR, pages 4249–4258. IEEE Computer Society, 2015
2015
-
[26]
The CLRS algorithmic reasoning benchmark
Petar Velickovic, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The CLRS algorithmic reasoning benchmark. In ICML, volume 162 of Proceedings of Machine Learning Research , pages 22084–22102. PMLR, 2022
2022
-
[27]
Neural algorithmic reasoning
Petar Velickovic and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7):100273, 2021
2021
-
[28]
Reasoning-modulated representations
Petar Velickovic, Matko Bosnjak, Thomas Kipf, Alexander Lerchner, Raia Hadsell, Razvan Pascanu, and Charles Blundell. Reasoning-modulated representations. In LoG, volume 198 of Proceedings of Machine Learning Research, page 50. PMLR, 2022
2022
-
[29]
Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell
Petar Velickovic, Lars Buesing, Matthew C. Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. In NeurIPS, 2020
2020
-
[30]
Neural execution of graph algorithms
Petar Velickovic, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In ICLR. OpenReview.net, 2020
2020
-
[31]
Prior Best
Louis-Pascal A. C. Xhonneux, Andreea Deac, Petar Velickovic, and Jian Tang. How to transfer algorithmic reasoning knowledge to learn new algorithms? In NeurIPS, pages 19500–19512, 2021. 12 A Additional Experimental Results for Single-Task Augmenting The comparison charts of PG...
2021
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.