Open-Book Neural Algorithmic Reasoning

Summary

This paper proposed an open-book learning framework that allows networks to utilize the entire training dataset during reasoning, significantly enhancing performance on the CLRS Algorithmic Reasoning Benchmark and revealing intrinsic connections between different tasks through an attention-based mechanism.

Strengths

Innovation: The use of training datasets to enhance algorithmic reasoning tasks is novel. Workload: Your research workload is significant. The article provides sufficient experimental support. Writing quality: Your paper is well-written, with clear and precise language and a smooth flow of ideas. The structure is reasonable, and the logic is sound, making it very enjoyable to read. Experimental analysis: Your experimental analysis is rigorous, as your experimental design is reasonable and analysis methods are scientifically reliable.

Weaknesses

1. Introducing the additional memory seems to have a large storage overhead if the training set is large. 2. The author's proposal is similar to retrieval augmented generation (RAG) in NLP, so I hope it can be discussed.

Questions

What are the implications if the testing phase is supported by unseen datasets?

Rating

6

Confidence

2

Soundness

4

Presentation

3

Contribution

3

Limitations

The limitations of the study and the possible negative social impact have been well documented by the authors.

Summary

This paper presents open book Neural Algorithmic Reasoning (NAR). The central claim the authors investigate is whether open book reasoning -- allowing a model to query information from its training set relevant to the current query -- can be unified with existing NAR architectures. In doing so, the authors present a general framework for open book NAR. The authors find that their framework is more performative on the CLRS benchmark. Furthermore, the authors investigate open-book NAR with multi-task training and find that it achieves similar performance to the current best multi-task NAR algorithm -- exceeding the baseline in some tasks.

Strengths

- Significance: Neural algorithmic reasoning models have been highly effective in real world use cases `[1]` and are extremely relevant to the NeurIPS community. This paper introduces an orthogonal direction of improvement over current work in the field. As such, it seems that this paradigm is applicable to any NAR model that follows the Encode - Process - Decode paradigm. - Clarity: The manuscript is well-structured and easy to read. `[1]`: https://arxiv.org/abs/2108.11482

Weaknesses

__Robustness and Generalization__: While I understand the logic of why open-book reasoning is relevant to NAR, wouldn't allowing the features learned at train time overfit to the training set and hurt out of domain performance? 'm concerned that, as the distribution shift increases, the efficacy of an open-book NAR model will decrease considerably faster than that of a vanilla NAR model. Concretely, I recommend the authors compare with the algorithm and dataset presented in `[3]` (one of the papers cited in the introduction). This experiment has the added advantage of lending credence to the generalization claim in L54-57 because, if open-book learning is more performant, it must be extracting “background knowledge” features invariant to distribution shift. Presently, I'm recommending a __Borderline Acceptance__. Open book NAR seems to be highly desirable in real world scenarios, but I'm concerned that the performance gains come at the cost of OOD performance, which seems integral to the practical benefits of NAR algorithms. I'm willing to change my recommendation based on future discussion with the authors. Minor comments: - L36: CLRS is definitely a great litmus test for NAR algorithms. I recommend the authors look into SALSA-CLRS `[2]` as well, where open-book performance might admit better scalability than current baselines. - L223: This section will benefit from an explanation of what metrics were used for each use case and why. `[2]`: https://arxiv.org/pdf/2309.12253 `[3]`: https://arxiv.org/pdf/2302.10258 ----- Increasing score to __Weak Accept__ after discussions with the authors.

Questions

(addressed in weaknesses section)

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have adequately addressed limitations, though I recommend an explicit limitations section in the appendix.

Summary

The paper proposes a method to use the training dataset more explicitly during test time inference to improve performance. This is done with a dataset encoder module plus another processor module named open book processor. The authors validate their method in the single and multi-task set-up with good results. Ablations are performed in the multi-task set up to determine which algorithms are most helpful.

Strengths

- The paper is clear and easy to understand. - The idea is interesting and well-executed. - The evaluation is good and convincing (thank you for the error bars).

Weaknesses

- The related work is very brief, arguably too brief. For instance [1,2,3] are missing. - There is no ablation for the architectural design decisions. - The description of hyper-parameters should be in the Appendix of the paper rather than the reader needing to open a different paper to find them. This would help this paper stand on it's own. - It would be good to re-iterate the metric (f1 score I believe) and training graph vs test graph size. - Only the final performance is measured on the larger graphs. Another important and interesting metric how well the actual algorithm is learned. For a given task, e.g. single-source shortest path, there are several algorithms that solve this problem (e.g. Dijkstra and Bellman-Ford). Not all algorithms are equally easy to learn (e.g. BellmanFord is much more nicely aligned to the GNN architecture than Dijkstra and thus easier). To what extent is the correct algorithm learned, this can be shown by the accuracy on various algorithm specific intermediate hints, e.g. next node selected in Dijkstra. I suspect that for instance in the multi-task set-up it happens that the "wrong" algorithm is learned (see Table 2 Dijkstra relying on BellmanFord). I think this matters because this is a kind of short-cut that the model may learn contrary to what we desire (defined by the training data + loss). [1] https://proceedings.neurips.cc/paper_files/paper/2023/file/a2370db7c99791ad5d9f3ef48ad6d464-Paper-Conference.pdf [2] https://proceedings.neurips.cc/paper_files/paper/2021/file/a2802cade04644083dcde1c8c483ed9a-Paper.pdf [3] https://arxiv.org/pdf/2406.09308 I am willing to raise my score further if the above weaknesses and questions are addressed.

Questions

- How does the network perform as you scale the available training data points (as far as I can tell only 240 examples are tested)? - What does the generalisation curve look like across graph sizes (64,128,256,...)? - How many attention heads are you using for the cross-attention?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

- Few ablations (see questions) - Related work is too brief (see weaknesses)