Open-Book Neural Algorithmic Reasoning
Authors: Hefei Li
Chao Peng
Chenyang Xu
Zhengfeng Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: Neural Algorithmic Reasoning
Graph Neural Network
Primary area: graph_neural_networks

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.

Open-Book Neural Algorithmic Reasoning
Hefei Li, Chao Peng: Chenyang Xu, Zhengfeng Yang
Shanghai Key Laboratory Trustworthy Computing Software Engineering Institute
East China Normal University, Shanghai, China
51255902121 127 @ wwu.ecnu.edu.cm {epeng, cyxu, zfyang J @ cei.ccnu.edu.cm
Abstract
Neural algorithmic reasoning is emerging area of machine learning that focuses on building neural networks capable 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 classical algorithm. We challenge this mode and propose novel open-poor learning framework. In this framework, whether access and utilize all instances in the
during training or testing, the network 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 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 robust tool for interpretable multi-task training.
Introduction
Deep neural networks have achieved remarkable advancements various areas, such as image processing [18, 6] and natural language processing [16, 21]. In recent years, deep learning continues to evolve, there has been an increasing desire to see deep neural networks take on more complex tasks. Algorithmic reasoning tasks [27, 5, 28] have emerged as particularly crucial category. In classical domains, deep neural networks have demonstrated their ability to learn predictive patterns from training data. The aspiration now is to extend this capability to the field of algorithmic reasoning, which motivates a burgeoning domain - Neural Algorithmic Reasoning (NAR).
Neural algorithmic reasoming was initially coined by [30]. The central objective of this domain is develop and train neural networks with the capability imitate classical rule-based algorithms, such as sorting algorithms and graph algorithms. Networks built in this manner demonstrate the ability to perform algorithmic computations similar to traditional algorithms in reasoning tasks, while showcasing improved computational efficiency compared to them [17]. Moreover, recent literature [31, 22] shows that owing to the characteristics of deep learning. these networks exhibit flexibility in handling diverse input formats, making them robust even in scenarios where certain input features are missing.
Correspondence to Chao Peng and Chenyang Xu. The authors are ordered alphabetically.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Challenging Benchmark for NAR. CLRS Algorithmic Reasoning Benchmark proposed by [26] is currently the most popular and definitive benchmark for evaluating the algorithmic capabilities of neural networks. This benchmark comprises 30 diverse algorithmic reasoning tasks extracted from the foundational algorithms textbook "Introduction to Algorithms" [4], including sorting, searching, dynamic programming, graph al algriithms, string algorithms, and more. Beyond the task diversity, another notable challenge of this benchmark is the significant differences in scale between problem instances in the training and test sets. The test instances are substantially larger in scale compared to those in the training set.
There have been many recent advances in exploring CLRS [7. 19, 8, 24, 3]. As classical algorithms can often be represented by graph structures, several successful approaches leverage the Graph Neural Network (GNN) framework, including models such as PGN [29] and MPNN [9]. In addition to directly applying these classical GNNs, the literature has observed that the execution of some classical algorithms often relies on specific data structures. Consequently, there have been proposals to integrate classical GNNs with data structures like priority queues [12] or stacks [14] to enhance neural reasoning capabilities.
However, we notice that all prior approaches predict algorithmic executions based solely on their parameters and the features of single input. Although this mode is commonly used in traditional supervised learning tasks [20, 1], may not be well-suited for NAR due to the inherent difference between complicated reasoning tasks and traditional tasks like image processing. In practical scenarios, when recognizing images, extensive background knowledge is typically not required; but when faced with complex reasoning tasks, a substantial amount of background knowledge is often necessary to complete various aspects of the reasoning process. In such situations, having real-time illustrative examples or formulas available for reference can significantly reduce our memory burden, thereby enhancing task completion. This naturally raises a question:
!f allowing a neural network to access additional examples for reference during reasoning, will its reasoning capability improve result?
1.1 Our Contributions
We explore the aforementioned question and introduce open-book neural algorithmic reasoning. In this model, the neural architecture is enhanced with an additional memory component that stores representations of instances in the training dataset. Whether during training or testing, whenever the network engages in reasoning for a specific instance, it has the capability to leverage this supplementary memory aggregate information from other instances within the training set, akin to an open- exam. The main results of the paper are summarized as follows:
We present general framework for open- book NAR. This framework builds upon the foun- dation of previous NAR architectures by introducing two additional modules for embedding and information aggregation from the training set, and can seamlessly integrate with existing methods. We further provide a detailed implementation of the framework, which is grounded in the cross-attention mechanism. This design not only caters single-task training but also proves to be highly effective in scenarios involving multi-task training.
Empirical evaluations are conducted on the challenging CLRS Benchmark [26]. We incor- porate the proposed framework with three popular network architectures in the literature. The results demonstrate that each architecture's 's reasoning capability can be improved signif- icantly when utilizing the training instances through the framework. Across the majority of the reasoning tasks within the benchmark, the framework yields statc-of-the the-thrrrt results.
Multi-task training is also investigated in the paper. As highlighted in [11], on certain reasoning tasks, generalist network trained on all datasets in CLRS outperforms the networks trained in single-task manner. We provide an interpretation of this observation using the proposed open- book framework. Specifically, when training a neural network to solve task, we input information from other task datasets into the framework for its use. The results show that our open-book framework can nearly replicate the effects of multi-task training for each algorithmic task, while in some tasks, it even achieves higher accuracies. Additionally, our attention-based implementation enables us to analyze the attention weights of various tasks, facilitating deeper understanding of the intrinsic relationships among

---

tasks. A "paired training" experiment is further conducted to verify the effectiveness of the learned attention weights.
1.2 Other Related Work
Our work closely aligned with the exploration non- pan--aaameticc models [23, 25, 13], where models abstain from training specific parameters and, instead, utilize dependencies among training data points for predictions. Our framework can be viewed as a fusion of deep neural networks and non-parametrie models. We have noted analogous efforts in recent work within the field of image processing [15]. This work focuses on the CIFAR-I0 dataset, employing self-attention mechanisms among different points in the dataset finish image classification tasks.
2
Preliminaries
This section introduces the setting of an NAR dataset formally and outlines the standard paradigm employed in NAR.
The objective of an NAR task is to train a neural network such that it can imitate each execution step of classical algorithm on given problem instances. Hence, a NAR dataset is labeled by a specific problem and the algorithm employed to solve it. Each data point includes a problem instance, represented by graph structure, and the corresponding algorithm execution that instance, conveyed through a sequence of graph-structured states. Denote by x the problem instance and by y = {y(*), ,..., states (e.g., g. the current nodes in the queue of breadth- first search) the t-th step of the algorithm.
NAR Dataset.
y...... y(t) ...} the algorithm execution, where y(()) signifies the graph-structured
Training Objective. The training objective of the neural network is to perform sequential reasoning tasks over a given problem instance. At each step the network takes as input the pair (x, y (((+)) and produces the output y(t). This process enables the neural network to learn and predict the evolution of the algorithmic execution on the problem instance in a step- step-wise fashion.
Encodee-rrocesso--eeceo Paradigm. To achieve the aforementioned step-wise objective, the literature follows the standard encode-process-decod paradigm [10], which consists of three modules: Encoder, Processor, and Decoder. At each step I, the input (x, ((-1)) traverses through these modules sequentially?:
The encoder module encompasses multiple neural networks that operate on (x, (t-1( thereby transforming into a collection of graph- to denote the graph structure. Following this module, we obtain h, corresponding each node v E V, New associated with each edge (v, a) E E, and h representing the hidden state of the entire graph G.
hidden states. Use = (V, E)
The processor module usually consists of a graph neural network. This module maintains the historical hidden states of nodes, edges, and the graph: (ofl-1))vev- (h(t=-)) " (va)eE
b (b-1) and integrate them with the newly generated states {h,}. {/v.u. h2 yield updated states. We borrow the language of the mnssagee-psssing architecture [9] to formalize this process. For brevity, the following focuses only updating the state of each node At each step f, the node computes and aggregates messages mae from its incoming edges, updating its own hidden state:
<(01 < fi (ho.h(-1)) : Muv + fo (2))) 24 hovs hy) ()
M, +
Man :
( t fa (, M.)
ai(u,)EE
Different processors employ different layers fi, f2. fs. and aggregation function D
The decoder module utilizes the states (() input forecast the algorithmic execution (*) at step t. It is noteworthy that recent literature [11] also incorporates and (t- within this module.
For simplicity, we abuse the notion slightly, allowing (t-1) represent the outcome of the last step.
3

---

Open-Book Reasoning
The paradigm above be denoted by function FF mapping y for each data point. Given NAR dataset, this function implies a standard supervised learning mode: during a training step, a (or mini- of) random datapoint y).)) is selected. The loss between F(x) and then computed, and the parameters in F are updated accordingly. In this section, we go beyond the individual x + mode conventional supervised learning, exploring more general and practical learning paradigm.
3.1 Framework
We introduce an open-book reasoning framework. Within the framework, when the network tasked with solving problem instance and deducing it not only utilizes x as input but is also allowed to leverage information from other data points within the training set during the reasoning process.
x, (
Training set T
Dataset Encoder
Encoder
h
R
h (1)
n (+)
Open-Bos Book Processor
y())
Processor
Decoder
Figure 1: An illustration of the open-book framework. At each reasoning step 1, we simultaneously input ((-1)) and instances from the training set T, yielding (()).
The intuition behind the open-book framework is analogous to our real-world scenario of solving algorithmic problems or engaging other reasoning tasks. In practical situations, we often consult textbooks and refer to example problems to aid in completing tasks. Typically, the structure and solutions these examples provide substantial assistance our reasoning process. Denoting the training set as T, the framework essentially aims to learn comprehensive function F UUT
illustration of the framework present in Figure In addition the original three modules, we introduce two new modules: Dataset Encoder and Open- Book Processor:
The dataset encoder module employs encoding function fg compute the latent feature each data point d; = (x,, y+) in the training set: r; + fÆ yx). is worth noting that this encoder module is essentially different from the original one. It maps entire data point d, = (x,, y:), encompassing the ground truth of each node (and edge) at each step, into single representation r,.
The open-book processor module is incorporated between the original processor and decoder modules. The output (() from the processor no longer directly feeds into the decoder; instead, it passes through the open-book book processor, where it undergoes information aggre- gation with the training data representation R (rı,..,, (generated by the dataset encoder). Subsequently, the open-book processor produces the latent features (() required by the decoder. Formally, for each node v E V, vV + fr (N.,,
The central component of the framework is the open- book processor module. Within this module, the current problem instance to be solved is integrated with examples from the training set. It crucial to acknowledge that this integration has both advantages and disadvantages. While it often enhances the architecture's 's reasoning capabilities, there are instances when it may lead to counterproductive effects, particularly during multi-task training. We will claborate on this in the experiments.

---

3.2 Attention-Based Implementation
Diverse implementations within the framework be achieved by employing different functions for fE and fp. For the case of investigating multitask training, we adopt an attention mechanism-bas implementation. description of the network implementation and training given Algorithm 1.
Algorithm 1 Attention-Based Implementation of Open-Book Book Reasoning
Input: Training set T.
while current epochs I maximum training epochs do
2: Initialize the hidden state h()) and (())
3: Randomly pick target data point d (x, ' and several auxiliary data points D. Dataset Encoder
d1,d2, .2,...d; E T.
4:
for each auxiliary data point d; (x, V:) do
5:
Let G = (V, F)) represent the underlying graph of d;. This data point encompasses a state sequence x, Yi (0) ( yi
the graph.
6:
Randomly select two adjacent states y: y for each node v V do
(p+1) from the sequence.
7:
Let ye and V. be node v's states in y, (n) and v(rt respectively. Employ a linear layer 2, + linear 2 (yv + v.)). end for < [V] EvEV Zv.
8:
9:
11:
12:
end for
13:
Define :: [ri.....rri re].
14:
for each algorithm execution step & of the target data point do
15:
Feed x and the outcome from the previous step into the encoder and processor sequentially
to obtain the hidden states (4),
16:
Employ linear layer: R(() + R linear (h (t)).
Open-Book Processor Set a QKV attention function with linear layers query(-), value(-).
17:
18:
Compute a cross-attention between (() and (t)::
queryy (h(*) key )R
h softmax
value (R(*)
ddz
where dg is the dimension of the key vectors.
Add gate function: (0 gate (h())
19:
20:
Feed (9) into the decoder module, yielding the predictions of this step.
21:
end for
22:
Compute the prediction loss and update the network parameters.
23:
end while
From the description, a targer data point and several auxiliary data points randomly selected in each training iteration. The target data point serves as the focal point for neural optimization in this iteration: the network predicts its ground truths, computes the loss, and consequently updates the network parameters. The auxiliary data points assist the network in reasoning for the target data point. Their latent features are obtained through the dataset encoder, and they subsequently influence predictions through the open-book processor.
At each algorithmic step f, the hidden states (1) are computed conventionally. However, these states are not directly input into the decoder. Instead, they need to undergo cross-attention with the representations of auxiliary data points within the open- book processor module. This design allows the network to incorporate hints provided by the auxiliary data points during the reasoning process.
The construction of the dataset encoder is bit subtle. We observe a crucial aspect that all these pieces of information ultimately serve the decoder module. In single algorithmic step, the decoder's role to facilitate the transition between two adjacent states throughout the entire reasoning process. Therefore, to better provide effective hints to the final decoder, for each auxiliary data point,
5

---

randomly sample pair of adjacent states from its corresponding state sequence. Subsequently, we employ linear layer to yield the latent representations of these data points.
Remark, The testing process is essentially similar to the training. is worth noting that during the testing phase, the target data points are sourced from the testing set, while the auxiliary data points must still originate from the training set.
4 Experiments
This section evaluates the open-book implementation empirically on the CLRS benchmark. We aim to investigate the following three questions during the experiments:
For various processor architectures present in the literature, can the open-book framework consistently enhance their empirical performances across the majority of the algorithmic tasks within the CLRS benchmark?
There is recent literature [11] proposing a multi-task training approach for CLRS. They train common network for various tasks in the benchmark and find that some tasks benefit from the multi-task approach, achieving higher accuracy than when trained individually. the context of the open-booe book setting, does this phenomenon imply that incorporating training sets from various tasks into the open-book framework may enhance the network's performance on certain tasks?
Can the attention-base training? When integrating training sets from various tasks into the open- book framework for a specific task, the network eventually learns attention weights in the open-book processor, signifying the task's relevance to other tasks. Does this imply that if a task performs better in multi-task training than in single-task training, retaining only those tasks with prominent attention for multi-task training still outperform single-task training?
implementation serve as a robust tool for interpretable multi-task
To tackle these questions, conduct three types of experiments': single-task augmenting, multi-task augmenting. and multi-task interpretation. Note that our "multi-task augmenting" experiment differs essentially from traditional multi-task training; here, still train the network for specific task, but with the inclusion of datasets from other tasks in the dataset encoder. Additional ablation experiments also conducted. Due to space limitations, defer them the full version of this paper. We initially outline the experimental setup and subsequently delve into each experiment.
4.1 Setup
Baselines. We incorporate the open-book framework into three existing processor architectures: PGN [29], MPNN [9] and Triplet-GMPNN [11]. Given that the feature dimension of hidden states is set to 128 in the literature, we adjust the parameters of the dataset encoder and open-book processor to ensure seamless integration. The results (F1 scores) achieved by open-book reasoning are compared with them. Moreover, we also compare the performance with other recent architectures like Memnet [26] and NPQ [12].
Computational Details. The experiments conducted machine equipped with 17-13700K CPU, an RTX 4090 GPU, and an RTX A6000 GPU. The results are averaged over 4 runs. To ensure fair comparisons, we follow the widely-used experimental hyperparameter settings in [11], where the batch size is 32 and the network is trained for 10,000 steps by Adam optimizer with a learning rate of 0.001. During each training and testing iteration, allow Algorithm 1 to sample 240 auxiliary data points and use only one attention head. The average training time for each reasoning task is approximately 0.5 GPU hours.
4.2 Single-Tass Task Augmenting
This subsection considers single-task environment: for each reasoning task in CLRS, both target and auxiliary data points in Algorithm sourced from its dataset. We create comparison charts for results on three existing architectures. Due to space, only one chart Figure is presented
The codes are provided in https:///githeei htg.gttubb.cc//ofeeeeee////aapaa http://////ttttttoooo/aaoeeeeee/

---

126
NPTE Opan-Bask HiMA
90
20
Ne've Scring Moncherr
1outh Moms Frott
Quicocor
Jarvis Worch
mzerbion Sort
Max Subarray
timry search
Heaportt
SCC.
DFS
(CStangth
Undges
MST-Primn
Activtyy Selector
Fbyd, Warshall
Moimam
Metro Chain Ordar
Ophimlliss
Dijettra
MST-Kruskul
Sogmantinnarsers
GrahermScan
Belimen-Ford
Taok Scheduling
SFS
Quickseeec
Bubble
Afticuletion
Topologica
DAG Shorted
Figure 2: Comparison of the MPNN architecture's performance before and after augmentation with the open-book framework. The 30 tasks are arranged in descending order of improvement magnitude.
Table 1: The summary of our results on each task category in CLRS. The best- cesst-erforming results in
each are highlighted in bold. To save space, results among four existing approaches: Memnet [26], PGN [26], MPNN [26], and NPQ [12], and the column "Ours" to denote the best results achieved by applying the open-book framework the three existing architectures.
the column "Prior Best" to denote the best
Task Category
Prior Best
Triplet-GMPNN
Ours
Graphs
64.98%+4..59
81.41%+1.55
85.37%+1.73
Geometry
92.48%+11.35
94.09%+40.7
96.55%+0.55
Strings
4.08%:+0.57
49.09%:+4.78
72.41 %22266
Dynamic Programming
76%442.47
81.99%+1.30
82.14%#1.45
Divide and Conquer
65.23%+2.55
10.36%#1.43
74.52%++1.8
Greedy
84.139:2..59
91.22%:+..40
93.40%+2.12
Search 56.119940.36
58.61 1.05
63.15 40.900
Sorting
71.53%:4.97
60.38%45.25
83.65 #:3.06
in the main body, while the other two deferred the full version of this paper. The figure uses bar charts to illustrate average scores for each task, with standard deviations denoted by black lines. Additionally, arrange the tasks in descending order of improvement magnitude to better illustrate trends.
We also provide tables to comprehensively compare the accuracies that the open-book framework yields with existing results. In CLRS, the 30 tasks are partitioned into categories: Divide and Conquer, Dynamic Programming. Geometry, Graphs, Greedy, Search, Sorting, and Strings. So we present two tables: one showcasing the performance on the 30 individual tasks and another displaying the average performance for each of the task categories. Due to space constraints, the latter is included in the main body (Table 1), while the former is deferred to the full version of this paper.
From the figures and tables, we observe that our approach outperforms the original architectures in the majority of tasks. The improvements provided by the open-book framework are particularly significant for certain tasks, such as the Naive String Matcher task (see Figure 2). However, we also notice relatively large standard deviation in performance for some tasks. We attribute this variability to the fact that during testing, we sample data from the training set and input it into the dataset encoder each time. The quality of the sampled data influences the final inference results, leading to performance fluctuations.
7

---

Mu Oubb-peeBBrok
80
Average Score]
20
Royd Worshall
Find Max Suborrey
Kruth korrs Pratt
jarvis March
Natve String Matcher
Gra mamarann
Activity Selecior
MST--rim
Bubole Sort
SCC
Apppaot
Diiaii
Mrrmnum
Quickselect
DAG Shortest Patro
segmensirreenn rersectt
quicksort
Matric Choin Order
MSTAruskel
Tesk Schetulin
BFS
Inse ton Sort
ardgges
Opti naESS
Articatation Paints
DFS
Topological
Dellman
binary,
Figure 3: Comparisons between our multi-task augmented approach and Triplet- Triplet-GMPNN. The 30
tasks are arranged in descending order of improvement magnitude.
4.3 Multi-Task Augmenting
This subsection considers "multi-task" environment: for each task in CLRS, Algorithm 1 selects target points from its own dataset, while the sampled auxiliary points are drawn from all datasets in CLRS. Since CLRS comprises 30 datasets, in each iteration, we randomly sample 8 instances from each dataset, ensuring that the total number of auxiliary points remains the same in the single- task experiment, i.e., 240. Given that Triplet-GMPNN is the only architecture used for multi-task training in the literature, both this subsection and the following one "multi-task interpretation" focus exclusively on the results obtained by integrating the open-boot framework with TripletGMMPNI
The results are present in Figure 3. We find that incorporating data from different tasks into the open-book processor indeed replicates multi-tast training. Our multi-task augmented method closely matches the previous multi-task training results, and even outperforms them on the vast majority of tasks. It worth noting that multi-task, training requires simultaneous training on all 30 algorithmic tasks, which is extremely time-consuming. If the goal is simply to enhance performance on specific task using multi-task training, the cost is substantial. However, with the open-bool framework, we can nearly achieve the effects of multi-task training on a target task in approximately the same amount of time it takes to train a single algorithm.
4.4 Multi-Tast Interpretation
This subsection delves into interpreting multi-task training. In our multi-task augmenting experiments, the acquired attention weights the open-book processor reveal the significance of each task in relation to others. Specifically, for each task, we aggregate the attention weights of each node at every algorithmic step on each test instance. The resulting 30-dimensional vector is then normalized, serving the total attention vector for that task relative other tasks in the benchmark. Table 2 shows the task with the highest attention weight for each task. Moreover, we present a heatmap regarding the attention weights among CLRS tasks in the full version of this paper.
Surprisingly, the table indicates that the majority of tasks exhibit preference for attention toward tasks outside their own categories, contrary to our initial expectations. Only four bolded pairs show high attention to tasks within the same category, with most of these being graph algorithms. An intuitive explanation for this phenomenon is that tasks within the same category might not contribute additional information compared the dataset used for training the task itself. Instead, tasks from other categories seem to play crucial role in improving training accuracy.
8

---

Table 2: For each target (task), show the task with the highest attention weight among other tasks in column "Auxiliary". We use bold text to indicate when the paired tasks belong to the same algorithmic category.
Target
Auxiliary
Target
Auxiliary
Activity Selector Articulation Points
Topological Sort
Jarvis' March
MST-Kruskal
Soutt-Morris-PPattt
BrauthMMrrrs--Paee
Quicksort
Bellman-Ford
Bridges
LCS Length
Dijkstra
BFS
Task Scheduling
Matrix Chain Order
Jarvis' March
Binary Search
Quickselect
Minimum
Quicksort
Bridges
Optimal BST
MST-Kruskal
Heapsort
Bubble Sort
Task Scheduling
MST-Prim
Bridges
DAG Shortest Paths
Naïve String Matcher
Naïve String Matcher
I.CS Length
DFS
Binary Search
Optimal BST
Find Max. Subarray
Dijkstra
Bellman-Ford
Quickselect
Dijkstra
Find Max. Subarray
Jarvis' March
Quicksort
BFS Topological Sort
Heapsort
Segments Intersect
Graham Scan
Quicksort
SCC
Task Scheduling
Heapsort
Activity Selector
Task Scheduling
Heapsort
Insertion Sort
Minimum
Topological Sort
DAG Shortest Paths
Table 3: Comparisons among three training manners under GMPNN.
Task
Single- Task
Multi- Task
Paired-Task
Heapsort
31.04%15.82
55.62%+15.9
46.63%=10.43
mouth-Morris
19.51%44.57
51.61%48.63
65.67%
Insertion Sort
78.14%:4.64
87.00%+4.16
95.78%+4.800
LCS Length
80.51%:11.84
83.43%+1.19
85.86%+1.47
Quicksort
64.64%.25.12
75.10%:9.52
88.43%24.22
SCC
43.43%:43.15
48.48%%49.96
73.09%+3.00
Jarvis' March
1.30
74.51
04.44%:20.6.
MST-Kruskal
89.80%=+0.77
89.08%+11.64
90.55%#1..1
MST-Prim
16.39%++1.33
86.26%+4.08
92.56%+0.99
Topological Sort
87.27%+42.67
81.65%+2.53
24.66%
Dijkstra
96.05%22060
94.29%++104
97.44%#2.55
Binary Search
77.58%+2.35
69.30%+5.65
79.77
Bubble Sort
67.68%45.50
52.94%+1999
70.30 267777
Graham Scan
93.62%:2091
87.74%
94.58 10.87
Minimum
97.78%.4..5
92.50%+4.53
98.32% 10114
We proceed to more in-depth examination of the relationships among tasks learned by the framework. We select a partner for each task according to Table namely, the task it pays the most attention to. We conduct training and testing in a multi-task manner for each task paired with its chosen partner, and refer to this type of training as paired-task training. In this experiment, that either demonstrate accuracy improvements or slight declines in multi-task training compared to single-task training, and train them in the paired manner. The results given in Table 3. The table validates our hypothesis. On these tasks, paired-task training achieves improvements compared to single-task training, with most tasks even surpassing the performance of multi-task training.
only focus tasks
4.5 Experimental Summary
The experiments address the three questions posed the beginning of the section.
The open-book framework can significantly enhance the reasoning capabilities of various existing architectures, yielding otate-of-the-art results across the majority tasks in CLRS.
By feeding data from various tasks into the dataset encoder, the framework can successfully replicate the effects of multi-task training, and in most datasets, even outperform it.

---

The attention bassdd implementation provides valuable tool for the interpretability of multi- task training. By examining the learned attention weights, we can gain insights into the influences and intrinsic relationships among tasks during multi-task training.
5
Conclusion
This paper considers open- open-book neural algorithmic reasoning, introducing a novel open-book frame- work accompanied by attention based implementation. Through empirical evaluations, demon- strate that this implementation not only enhances the reasoning capabilities of the existing architecture but also functions
effective tool for interpretable learning.
Several interesting direction for future research exist, such as exploring more effective implementa- tions within the open-book framework. Note that although our current implementation demonstrates performance improvements for the majority of tasks in CLRS, there are instances where the open- book approach may yield counterproductive results. Refining the current architecture to ensure performance enhancements across all tasks remains a significant challenge.
10

---

Acknowledgements
This work supported by the National Key Research Project of China under Grant No. JU23YFA1009402 the Scientific and Technological Innovation 2030 Major Projects under Grant 2018AAA0100900, NSFC Programs (62161 146001, 62302166, 62372176), Shanghai Key Lab of Trustworthy Computing, Henan Key Laboratory of Oracle Bone Inscription Information Processing (AnYang Normal University), and the Key Laboratory of Interdisciplinary Research of Computation and Economics (SUFE), Ministry of Education.
References
[1] Abeer Aljuaid and Mohd Anwar. Survey of supervised learning for medical image processing. SN Comput. Sci., 3(4):292, 2022.
[2] 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 PMLR, 2023.
[3] 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.09300 2024.
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.
[5] Andreea Deac, Petar Velickovic, Ognjen Milinkovie, Pierre-Luc Bacon, Jian Tang, and Mladen Nikolic. Neural algorithmic reasoners are implicit planners. In NeurlPS, pages 15529-15542. 2021.
[6] Shisheng Deng, Dongping Liao, Xitong Gao, Juanjuan Zhao, and Kejiang Ye. survey on cross-domain few-shot image classification. In BigData, volume 14203 of Lecture Notes in Computer Science, pages 3-17. Springer, 2023.
[7] Cameron Diao and Ricky Loynd. Relational attention: Generalizing transformers for graph- structured tasks. In ICLR. OpenReview.net, 2023.
[8] Andrew Joseph Dudzik and Petar Velickovic. Graph neural networks are dynamic programmers. In NeurlPS, 2022.
[9] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML., volume 70 of Proceedings Machine Learning Research, pages 1263-1272. PMLR, 2017.
[10] 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. cognitivesciencesocity.oorg 2018
[11] Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bosnjak, Alex Vitvitskyi, Yulía Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Velickovic. A generalist neural algorithmic learner. LoG, volume 198 of Proceedings of Machine Learning Research, page 2. PMLR, 2022.
[12] 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.
[13] Zhiying Jiang, Yiqin Dai, Ji Xin, Ming Li, and Jimmy Lin. Few-shot non-parametric learning with deep latent variable model. In NeurIPS, 2022.
[14] Jonas Jürß, Dulhan Hansaja Jayalath, and Petar Veličkovié. Recursive algorithmic reasoning. In The Second Learning Graphs Conference, 2023.

---

[15] 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 NewrlPS, pages 18742228756,, 2021.
[16] Ivano Lauriola, Alberto Lavelli, and Fabio Aiolli. An introduction deep learning in natural language processing: Models, techniques, and tools. Neurocomputing, 470:443-4555 2022.
[17] Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals. Strong generalization and efficiency in neural programs. CoRR, abs/2007.03622 03629, 2020.
[18] Weibo Liu, Zidong Wang, Xiaohui Liu, Nianyin Zeng, Yurong Liu, and Fuad Alsaadi. A survey of deep neural network architectures and their applications. Neurocomputing, 234:11-20 2017.
[19] 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.
[20] Mohammed Amine EI Mrabet, Khalid EI Makkaoui, and Ahmed Faize. Supervised machine learning: A survey. In CommNet, pages 1-10. IEEE, 2021.
[21] Wongyung Nam and Beakcheol Jang. A survey on multimodal bidirectional machine learning translation of image and natural language processing. Expert Syst. Appl., 235: 121 168, 2024.
[22] Danilo Numeroso, Davide Bacciu, and Petar Velickovic. Dual algorithmic reasoning, In ICLR. OpenReview.net, 2023.
[23] 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.
[24] Gleb Rodionov and Liudmila Prokhorenkova. Neural algorithmic reasoning without intermedi- ate supervision. In NeurIPS, 2023.
[25] 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.
[26] Petar Velickovie, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy. Raia Hadsell, and Charles Blundell. The CLRS algorithmic reasoning benchmark. ICML, volume 162 of Proceedings of Machine Learning Research, pages 22084-22102. PMIR, 2022.
[27] Petar Velickovic and Charles Blundell. Neural algorithmic reasoning. Patterns, 207))100273, 2021.
[28] Petar Velickovic, Matko Bosnjak, Thomas Kipf, Alexander Lerchner, Raia Hadsell, Razvan Pascanu, and Charles Blundell. deasoning-modulatee representations. In LoG, volume 198 of Proceedings of Machine Learning Research, page 50. PMLR, 2022.
[29] Petar Velickovie, Lars Buesing, Matthew C. Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. In NeurIPS, 2020.
[30] Petar Velickovic, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In ICLR. OpenReview.net, 2020.
[31] Louis-Pasce 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

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our topic and contributions are present clearly in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have a discussion on the limitations in the experimental section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
13

---

Justification:
The contributions of the paper are experimental.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The experimental section gives all the details needed to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: We will make our open-source code and datasets publicly available to facilitate others in reproducing the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/ public/guides/ https//ooSSSuuuiiinnneee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https:
CoodeSubmiis ssi asionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental setup and relevant hyperparameters for reproducibility can be found in the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our table and figures provide the standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: In the experimental section of this paper, have specified the model of the graphics card used in our experiments, and further discussed the duration of the model training.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //werr//e.....e.eeeeee cc httpppull//Etiiice csGuidel ines?
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper is just standard experimental study for a public benchmark.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The data and model used in the paper properly respected.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
18


Reviews:
[{"review_id": "Ta3fyJiZYC", "reviewer": "Reviewer_m7Ww", "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.", "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)?\n- What does the generalisation curve look like across graph sizes (64,128,256,...)?\n- How many attention heads are you using for the cross-attention?", "limitations": "- Few ablations (see questions)\n- Related work is too brief (see weaknesses)", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is clear and easy to understand.\n- The idea is interesting and well-executed.\n- 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.\n- There is no ablation for the architectural design decisions.\n- 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.\n- It would be good to re-iterate the metric (f1 score I believe) and training graph vs test graph size.\n- 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).\n\n[1] https://proceedings.neurips.cc/paper_files/paper/2023/file/a2370db7c99791ad5d9f3ef48ad6d464-Paper-Conference.pdf\n[2] https://proceedings.neurips.cc/paper_files/paper/2021/file/a2802cade04644083dcde1c8c483ed9a-Paper.pdf\n[3] https://arxiv.org/pdf/2406.09308\n\nI am willing to raise my score further if the above weaknesses and questions are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments. This paper explores a new paradigm in neural algorithmic reasoning (NAR). We propose an open-book framework and provide a concrete implementation to demonstrate that open-book information does have the potential to enhance neural network reasoning capabilities. What we believe is that this work will influence future directions in NAR, as the open-book framework, combined with many other fancy techniques, will likely lead to more powerful neural architectures, and our implementation is just the beginning. The following addresses the questions and concerns one by one.\n\n**Q1:** How does the network perform as you scale the available training data points (as far as I can tell only 240 examples are tested)?\n\n**A:** In our experiments, we set the number of auxiliary data points to 240 (= 30*8), where 30 represents the number of algorithms (tasks) and 8 represents the number of task categories. This ensures that both the single-task and multi-task settings have the same number of auxiliary data points, and can facilitate future research on the impact of open-book information across different categories in the multi-task setting. Additional results are provided in the PDF attached to the global response. The performance of our method remains robust as the number of auxiliary data points varies; note that when the number of auxiliary data points is zero, our method becomes the existing model.\n\n**Q2:** What does the generalisation curve look like across graph sizes (64,128,256,...)?\n\n**A:** This is a very constructive question and provides new insight into further testing the reasoning capability. In the original test data provided in CLRS, the graph size is set to 64. We construct larger testing datasets and present our performance curve when the test graph size grows exponentially from 64 to 512 in Figure 2 of the attached PDF (in the global response). We observe that the curves for different algorithmic tasks vary, likely due to the complexity of the solution space for each task. Overall, as the testing size grows exponentially, the performance in most tasks declines smoothly. Another related experiment is shown in Figure 3, where we fix the testing size and vary the training size. We conclude that the average performance of our method remains robust as the testing/training ratio increases exponentially.\n\n**Q3:** How many attention heads are you using for the cross-attention?\n\n**A:** The results presented in the paper use only one attention head. We've tried other settings, but the results were almost the same. We'll add a short discussion about this in the final version.\n\n**W1:** Concerns about learning  \"wrong\" algorithms.\n\n**A:** For the CLRS models, the training loss is defined as the average loss of outputs and all intermediate hints (If the hint is categorical, we calculate the cross-entropy loss; if it's scalar, we use the MSE loss.) Thus, the network is always trained to mimic each step of the algorithm rather than focusing solely on the final score. This training approach helps prevent shortcut learning. In Figure 4 of the attached PDF, we show the loss during the training of the Dijkstra algorithm. Furthermore, in Figure 5, we present the loss trajectory on the validation set, demonstrating that open-book information indeed enhances the step-by-step imitation process.\n\n**W2:** It would be good to re-iterate the metric (f1 score I believe) and training graph vs test graph size.\n\n**A:** You're right. The evaluation metric is the F1 score, where we first partition the algorithm's output into different types (such as node states, edge states, etc.), calculate the percentage of output elements that match the ground truth for each type, and then take the average. The maximum graph size in the training set is 16, while in the testing data, the graph size is 64.\n\n**W3:** Other weaknesses.\n\n**A:** Thank you for these valuable comments. We will add the missing reference as well as more training details, and incorporate additional ablation studies in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TO1Tx3GMEt", "reviewer": "Reviewer_8uzp", "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.", "questions": "(addressed in weaknesses section)", "limitations": "The authors have adequately addressed limitations, though I recommend an explicit limitations section in the appendix.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n- Clarity: The manuscript is well-structured and easy to read. \n\n\n`[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.\n\n\nPresently, 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.\n\nMinor comments:\n- 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.\n- L223: This section will benefit from an explanation of what metrics were used for each use case and why.\n\n\n\n`[2]`: https://arxiv.org/pdf/2309.12253\n\n`[3]`: https://arxiv.org/pdf/2302.10258\n\n\n-----\n\nIncreasing score to __Weak Accept__ after discussions with the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. The following addresses the questions and concerns one by one.\n\n\n**W1:** Concerns about the OOD performance.\n\n**A:** The results presented in the paper are exactly the out-of-distribution performances of the proposed framework. As pointed out in Line 42 of the paper, the test instances are substantially larger in scale compared to those in the training set. For each dataset in the CLRS benchmark, the training set graphs contain approximately 12 nodes on average, while the test set graphs contain 64 nodes and are specifically generated to evaluate the model's OOD performance (as claimed by the CLRS creators). To further validate our framework's OOD performance, we include two additional experiments in the PDF attached to the global response. The overall design principle is consistent with that of the SALSA-CLRS dataset. In Figure 2, we fix the training set and increase the test set's graph size; in Figure 3, we fix the test set and vary the training set's graph size. We observe that even when the ratio of test to training graph sizes grows exponentially, the framework's performance across different datasets changes in a relatively smooth manner.\n\n\n\n**W2:** This section will benefit from an explanation of what metrics were used for each use case and why.\n\n**A:** Thanks for this comment. In the paper, we follow the standard evaluation metric used in the CLRS benchmark to ensure a fair comparison with previous work. The metric is called the F1 score, which involves dividing the algorithm's output into different types (such as node states, edge states, etc.), calculating the percentage of output elements that match the ground truth for each type, and then taking the average. We’ll add this detail in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NAxP7FnMS5", "reviewer": "Reviewer_pXFF", "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.", "questions": "What are the implications if the testing phase is supported by unseen datasets?", "limitations": "The limitations of the study and the possible negative social impact have been well documented by the authors.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Innovation: The use of training datasets to enhance algorithmic reasoning tasks is novel.\n\nWorkload: Your research workload is significant. The article provides sufficient experimental support.\n\nWriting 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.\n\nExperimental 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.\n2. The author's proposal is similar to retrieval augmented generation (RAG) in NLP, so I hope it can be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments. The following addresses the questions and concerns one by one.\n\n**W1:** Introducing the additional memory seems to have a large storage overhead if the training set is large.\n\n**A:** The proposed open-book framework is flexible enough to adapt to different computational environments. As the number of auxiliary data points decreases, the memory required by the framework also decreases; when the number of auxiliary data points is 0, the memory requirement of the framework is the same as that of the original methods. In our experimental setting, the memory required increased by an average of 30% compared to the original methods.\n\n**W2:** The author's proposal is similar to retrieval augmented generation (RAG) in NLP, so I hope it can be discussed.\n\n**A:** Thanks for pointing this out. The proposed framework shares some similarities with the technique of retrieval-augmented generation in LLMs. Both approaches involve augmenting the final step of model generation with additional information to aid the output. Although the high-level concept is similar, our open-book framework targets smaller models and opens the black box of these models, resulting in some technical differences compared to LLMs. We'll add a discussion on this point in the final version.\n\n**Q:** What are the implications if the testing phase is supported by unseen datasets?\n\n**A:** Due to the design of the gate mechanism (see line 19 of Algorithm 1), our method achieves robustness. When supported by unseen data in the testing phase, the framework can adjust the influence of auxiliary data points through the gate function, resulting in robust performance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for the helpful and constructive comments. We greatly appreciate the time and effort you put into this review, and we will incorporate your suggestions into the final version. The paper explores a new paradigm in neural algorithmic reasoning. We propose an open-book framework and demonstrate that open-book information can indeed enhance the reasoning capabilities of existing architectures. We believe that there is significant potential for further exploration within the open-book framework, and that this work could influence future directions in NAR. To address some concerns raised by reviewers, we provide additional experimental results in the attached PDF file. Due to constraints, we only show five figures involving representative algorithmic tasks as the remaining tasks exhibit similar trends. We will add these additional results to the paper’s full version.

Meta-review: After carefully reading the reviews and rebuttal, I agree with the reviewers that the work is interesting for the community. I believe that there were a few questions raised by the reviewers that were answered in the rebuttal fully. I urge the authors to incorporate these answers in the final version of the paper. In particular look at the related work section (and comments about this) as well as incorporating the additional results that were provided in the rebuttal.

Overall, I believe the work could also benefit from more analysis and ablation (e.g. checking when and how these examples from the episodic memory -- the open book -- are being used, and whether semantically this makes sense, etc.), rather than focusing just on the performance of the system in different settings. This can add another dimension of understanding and certainty in the starting hypothesis of the work. However, while it would be nice to have additional analysis, even without it, the work is already sufficiently interesting and useful for the community. So as long as all the details in the rebuttal are incorporated the paper should be ready for acceptance.
Decision: Accept (poster)