Open-Book Neural Algorithmic Reasoning

We thank the reviewer for the positive comments. The following addresses the questions and concerns one by one.

W1: Introducing the additional memory seems to have a large storage overhead if the training set is large.

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.

W2: The author's proposal is similar to retrieval augmented generation (RAG) in NLP, so I hope it can be discussed.

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.

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

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.

We thank the reviewer for the valuable comments. The following addresses the questions and concerns one by one.

W1: Concerns about the OOD performance.

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.

W2: This section will benefit from an explanation of what metrics were used for each use case and why.

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.

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.

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)?

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.

Q2: What does the generalisation curve look like across graph sizes (64,128,256,...)?

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.

Q3: How many attention heads are you using for the cross-attention?

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.

W1: Concerns about learning "wrong" algorithms.

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.

W2: It would be good to re-iterate the metric (f1 score I believe) and training graph vs test graph size.

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.

W3: Other weaknesses.

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.