{"id":"21e9e97a-39db-4363-aa0c-4cd941f0101a","arxiv_id":"2501.00072","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Open-book neural algorithmic reasoners, which attend to stored training instances, beat single-task baselines on most CLRS-30 tasks and expose useful cross-task relationships.","lead":"This paper adds a reference memory of training examples to neural networks that mimic classical algorithms, letting them attend to similar solved instances while solving a new one. On the CLRS benchmark of 30 algorithmic tasks, this open-book setup improved accuracy on most tasks and revealed which algorithm families help each other.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The dataset encoder compresses each auxiliary instance to one mean-pooled vector of a single random adjacent state pair; if that summary is uninformative, the open-book gains could come from added parameters, not from retrieved algorithmic knowledge.","rationale":"The paper's central claim - that open-book access to training instances improves NAR and yields SOTA on most tasks - is broadly supported by the reported tables: the open-book variants improve over their base processors on most of the 30 tasks, and the multi-task augmenting results show effects beyond single-task training. The code link is provided and the experimental protocol (4 runs, 10k steps, fixed hyperparameters) is standard, which is independent support. My concern is not that the method fails to improve F1; it is that the paper's mechanism attribution is underdetermined. Algorithm 1 represents each auxiliary instance as a mean-pooled linear embedding of one random adjacent state pair. This is a severe compression: graph structure, edge features, temporal ordering, and all other execution steps are discarded. If this summary is not informative, the cross-attention block degenerates into a learned bias, and the reported gains would be explained by the added linear/QKV/gate parameters rather than by 'open-book' retrieval. The paper reports no control in which the auxiliary content is removed or corrupted; Appendix C only varies the number of auxiliary points, which does not separate content from capacity. The authors' observation that sampling quality causes test-time variance suggests content has some effect, but a zero-out control is still needed to quantify it. Because this is a missing control rather than a demonstrated contradiction, the conditional verdict stands. Secondary issues include Table 4's 'Ours' column choosing the best of three architectures and several tasks (Bellman-Ford, DFS, Naive String Matcher, Optimal BST) falling below Triplet-GMPNN, which makes the 'state-of-the-art across the majority' phrasing an overstatement, but these do not change the main assessment.","tokens_in":11821,"tokens_out":8207,"duration_ms":85716,"concrete_test":"Run the single-task augmenting protocol on a representative subset (e.g., Knuth-Morris-Pratt, Heapsort, Insertion Sort, Quickselect) with the auxiliary state features y_v and y'_v in Algorithm 1 lines 8-9 replaced by fixed zeros (or any constant), so every auxiliary representation r_i is identical and the cross-attention carries no per-instance information. Keep all other hyperparameters, sampling count 240, and training budget identical. If F1 stays at the reported open-book levels, the gains come from added parameters rather than from the training-set memory channel; if F1 falls back to base-processor levels, the encoder's single-pair summaries are indeed informative.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1's dataset encoder (lines 5-11) reduces each auxiliary instance to a single vector: one randomly sampled adjacent state pair is averaged per node by a linear layer and then mean-pooled over nodes. The open-book processor then cross-attends to these 240 vectors at every decoding step. For the central claim to hold, these summaries must carry enough of the auxiliary algorithm execution for the attention to 'open the book.' But a random transition from an arbitrary training instance is far from the target's current transition; edge features, graph structure, temporal ordering, and all but one step of the trajectory are discarded. It is therefore unclear whether the network is retrieving algorithmic knowledge or just using the added linear/QKV/gate parameters (and the fixed statistics of R) as a learned bias. Section 4 reports no control with content-free auxiliary representations, so the observed F1 gains cannot yet be attributed to the open-book memory channel.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an open-book learning framework for neural algorithmic reasoning (NAR). In addition to the standard encoder-processor-decoder pipeline, the framework adds a dataset encoder that compresses auxiliary training instances into vector representations and an open-book processor that lets the current hidden state cross-attend to these vectors at every decoding step. The authors instantiate this idea with a concrete attention-based implementation (Algorithm 1), apply it on top of PGN, MPNN, and Triplet-GMPNN, and evaluate on the 30-task CLRS benchmark. They report that the open-book framework improves the base architectures on most tasks, that it can nearly reproduce or exceed full multi-task training at single-task cost, and that the learned attention weights provide an interpretable view of task relationships, which they test in a paired-task experiment.","tokens_in":12010,"tokens_out":6122,"duration_ms":59019,"significance":"If the central claim were established, this would be a useful empirical contribution: a simple, architecture-agnostic recipe that consistently improves NAR accuracy on a standard benchmark, with a natural extension to interpretable multi-task transfer. The paper has clear strengths: it uses the standard CLRS-30 benchmark, includes three base architectures, releases code, reports four-run averages, and provides scaling experiments in the appendix. However, the key attribution---that the improvements come from the open-book memory channel carrying algorithmic knowledge---is not yet supported by the experiments, because no control separates the content of the auxiliary summaries from the extra parameters and regularization introduced by the new modules.","major_comments":[{"comment":"The central claim that open-book retrieval of training instances improves reasoning is not yet supported by a control that isolates the information content of the memory channel. Each auxiliary instance is compressed to a single mean-pooled vector of one randomly sampled adjacent state pair, and the open-book processor adds linear, query/key/value, and gating parameters. Without ablations that replace the auxiliary summaries with content-free representations (e.g., random vectors from the same distribution, or summaries with the state-pair information removed), the reported gains could come entirely from the added capacity or from a learned bias over the statistics of R. I ask for at least: (a) a random-memory control, (b) a shuffled-summary control, (c) a capacity-matched baseline that adds the same number of parameters to the base processor without access to auxiliary data, and (d) an oracle control where the auxiliary summary is the true adjacent transition of the target instance. These controls are directly load-bearing for the abstract's claim that the open-book framework itself is responsible for the enhancement.","section":"§3.2, Algorithm 1 (lines 5–11); §4.1"},{"comment":"The summary tables are misleading because the column 'Ours' reports the best result across the three open-book architectures, not the result of a single system. This makes it impossible to verify the claim that 'each architecture's reasoning capability can be improved significantly' from the tables alone; the per-architecture bar charts in Figures 2, 4, and 5 show many overlapping standard deviations. Moreover, the baselines are not capacity-matched: the open-book processor inserts extra parameters on top of Triplet-GMPNN, MPNN, and PGN. I request per-architecture aggregate tables with task-level means and standard deviations, paired statistical tests (e.g., paired permutation tests across the 30 tasks), and at least one capacity-matched baseline per architecture so that the improvement can be attributed to the open-book mechanism rather than to model size.","section":"§4.1, Tables 1 and 4"},{"comment":"The paired-task experiment is presented as validation of the attention weights, but the selection criterion is not stated quantitatively and the data do not match the description. The text says the authors focus on tasks that 'either demonstrate accuracy improvements or slight declines' in multi-task training, yet Table 3 includes tasks with large multi-task declines, e.g., Jarvis' March (91.01% to 74.51%), Bubble Sort (67.68% to 52.94%), Binary Search (77.58% to 69.30%), Graham Scan (93.62% to 87.74%), Dijkstra (96.05% to 94.29%), and Topological Sort (87.27% to 81.65%). The authors need to define the selection threshold, report all 30 tasks for completeness, and compare paired-task training against control partner selections (e.g., randomly chosen partners or all-pairs training) to substantiate that the attention-selected partner, rather than the mere addition of a second dataset, drives the observed gains.","section":"§4.4, Table 3"}],"minor_comments":[{"comment":"The abstract and contribution list state that the network can 'access and utilize all instances in the training dataset,' but Algorithm 1 and Section 4.1 sample only 240 auxiliary instances per iteration. Please harmonize the wording to 'a sample of training instances' and clarify whether sampling is without replacement within an epoch.","section":"Abstract and §1.1"},{"comment":"The claim that multi-task augmenting costs roughly the same as single-task training should be clarified: the dataset encoder must process 240 auxiliary instances per target instance at every training step, so the total computation depends on the auxiliary sample size ℓ. Please report the actual training-time overhead and memory cost relative to the base architecture.","section":"§4.1 and §4.3"},{"comment":"The scaling experiments omit string-category tasks and quickselect due to memory constraints; this caveat should appear in the main text wherever 'robust out-of-distribution performance' is claimed, because several of the omitted tasks are exactly those with the largest open-book gains (e.g., Knuth-Morris-Pratt and Naive String Matcher).","section":"Appendix D"},{"comment":"The word 'significant' in the abstract is used in a colloquial sense; given the overlapping standard deviations visible in the bar charts, the authors should add paired statistical tests across the 30 tasks or across the four runs to substantiate the significance claim.","section":"Figures 2–5"},{"comment":"The procedure for aggregating attention weights (over nodes, algorithmic steps, and test instances) is described only in words; please give one precise equation defining the reported 30-dimensional attention vector, and state how many test instances are used for the aggregation.","section":"§4.4, Tables 2 and 5"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and interesting question, and the reported effect sizes are large enough to be worth pursuing. My recommendation of major revision is driven by the missing attribution controls: the central claim that open-book memory content improves reasoning is not separable from added parameters and best-of-three selection. These are fixable within the manuscript's scope, so I do not recommend rejection. I would also ask the editor to ensure the authors report per-architecture results transparently rather than only the best open-book variant in their headline tables."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the core thing to know: this paper reports a real and fairly large empirical gain on CLRS-30 by letting the processor cross-attend to summaries of training instances. The idea is new for NAR — Kossen et al. did datapoint self-attention for images, and Ibarz et al. did multi-task NAR, but nobody has wrapped an NAR processor with a training-set memory. The paper ships code and extensive tables: overall average F1 goes from 66.0 (prior best) and 76.0 (Triplet-GMPNN) to 82.9, with big wins on strings and sorting. That's not a fluke; the effect shows up across three base architectures and in the multi-task augmenting setting.\n\nCredit where due: the adjacent-state-pair encoder is a sensible way to compress a trajectory, and the attention-based multi-task interpretation, validated by paired-task training, is a nice bonus. The paper is honest that open-book can hurt some tasks.\n\nSoft spots, in order of importance. First, there is no capacity-matched control. The open-book processor adds linear layers, QKV attention, and a gate. The gains could come from extra parameters or from a learned bias rather than from retrieved algorithmic knowledge. The stress-test concern about the dataset encoder is real: one random adjacent state pair, mean-pooled over nodes, is a very lossy summary. The paper never replaces the auxiliary representations with content-free ones to show the memory channel itself matters. The ablation on the number of auxiliary points partially addresses this — performance varies with the sample size — but it doesn't fully isolate the mechanism. Second, the abstract overstates: it says 'all instances' but the implementation samples 240. Third, 'Ours' is the best of three architectures; several individual tasks fall short of the prior best, so 'state-of-the-art across the majority' is accurate but should be phrased carefully.\n\nNone of this falsifies the main claim. The empirical improvement is credible and reproducible (code is provided). The mechanism is underdetermined, and a good revision should add a content-free baseline and a capacity-matched control. I'd send it to review.","headline":"Real empirical gains on CLRS-30 from training-set cross-attention, but the mechanism is underdetermined without a capacity-matched control.","tokens_in":12536,"tokens_out":2715,"would_cite":true,"duration_ms":26161,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that letting a neural algorithmic reasoner attend to compressed summaries of training instances at every reasoning step improves its accuracy on most of the 30 CLRS tasks and can reproduce multi-task training gains at…","keywords":["open-book learning","neural algorithmic reasoning","CLRS benchmark","cross-attention","multi-task training","graph neural networks","algorithmic reasoning","interpretability"],"falsifier":"Replace the auxiliary representations $R$ in Algorithm 1 with random vectors of the same shape while keeping the dataset encoder and open-book processor parameters intact and retraining; if CLRS F1 scores do not drop materially, the open-book channel is not carrying task information.","tokens_in":11577,"feed_emoji":"📖","tokens_out":6885,"duration_ms":60369,"temperature":0.7,"pith_summary":"The paper tries to establish that neural algorithmic reasoners should not process one problem instance in isolation: giving the network access to compressed representations of training instances at every reasoning step, like an open-book exam, improves its ability to imitate classical algorithms. On the CLRS Algorithmic Reasoning Benchmark, which spans 30 tasks from a standard algorithms textbook, this open-book framework improves F1 scores on the majority of tasks over three base architectures and raises the overall average to 82.91%, compared with 75.98% for the strongest prior architecture alone. The same mechanism, with auxiliary instances drawn from other tasks, nearly replicates the benefit of full multi-task training while training only the target task. The attention weights learned in the open-book processor also expose which auxiliary tasks help which target tasks, and paired-task training based on the top attention partner often beats full multi-task training. A reader should care because the result suggests a cheap route to multi-task gains and a way to make cross-task transfer interpretable.","feed_headline":"Open-book memory lifts neural reasoners to 82.9% on CLRS","feed_subtitle":"Cross-attending to training examples beats baselines and near-replicates multi-task training at single-task cost.","key_machinery":"The load-bearing device is the open-book processor, a cross-attention module inserted between the base processor and the decoder. At each algorithmic step $t$, the hidden state $h^{(t)}$ is projected into a query, while the row $R^{(t)}$ concatenates the hidden state with a linear projection of the auxiliary representations $R$; a softmax attention over this row produces $\\hat{h}^{(t)}$, which is gated with $h^{(t)}$ and fed to the decoder. The auxiliary representations themselves come from a dataset encoder that compresses an entire training instance into one vector by mean-pooling a linear embedding of a randomly sampled adjacent state pair. This two-part machinery creates a trainable information channel from the training set into every reasoning step of the target instance.","core_discovery":"On the CLRS benchmark, the authors show that wrapping any of three existing processors (PGN, MPNN, and Triplet-GMPNN) with a cross-attention open-book processor and a dataset encoder that summarizes auxiliary training instances yields F1 improvements on most of the 30 tasks, raising the overall average from 66.04% for the prior best baseline and 75.98% for Triplet-GMPNN alone to 82.91%. They further show that drawing auxiliary instances from all task datasets can reproduce or exceed full multi-task training while training only the target task, and that the learned attention weights identify task pairings that validate the discovered relationships: paired-task training with the highest-attention partner often outperforms both single-task and full multi-task training.","pith_inferences":["One extension the paper leaves implicit is using the learned cross-task attention as a data-driven curriculum: rather than training a generalist on all 30 tasks, a scheduler could select auxiliary tasks by attention weight, potentially reducing cost further than paired training.","Because the dataset encoder compresses each auxiliary instance to a single mean-pooled vector, the framework suggests a retrieval-style scaling direction in which much larger memory banks are searched by the current hidden state; the paper only tests 240 randomly sampled auxiliary points.","The single-transition summary being sufficient would imply that adjacent execution states in CLRS are highly redundant across instances, a hypothesis the paper does not test directly but which could be checked by comparing full-state summaries against the compressed ones.","In a broader reading, the open-book processor turns the training set into a non-parametric memory consulted at every reasoning step, which connects neural algorithmic reasoning to retrieval-augmented inference outside algorithmic tasks."],"forward_implications":["Existing encode-process-decode NAR architectures can be upgraded to open-book reasoning by inserting the dataset encoder and open-book processor, and the upgrade improves F1 on the majority of the 30 CLRS tasks for all three base architectures tested.","The overall CLRS average reaches 82.91% with the best open-book configuration, compared with 75.98% for Triplet-GMPNN alone and 66.04% for the previous best among Memnet, PGN, MPNN, and NPQ.","Auxiliary instances drawn from other tasks can reproduce or exceed full multi-task training while the network is trained only on the target task, so cross-task gains do not require training a single generalist network on all 30 tasks.","The attention weights over auxiliary tasks can be read as a learned task-relationship map, and paired-task training with the highest-attention partner outperforms full multi-task training on most of the tasks tested.","Performance remains stable when training graph sizes vary from 4 to 20 nodes and test sizes from 64 to 128 nodes on the tasks tested, indicating the open-book memory does not simply memorize training instances."],"supporting_citations":[{"why":"Supplies the CLRS benchmark, its 30 tasks, and the reference results the study builds on.","marker":"[26]"},{"why":"Provides the Triplet-GMPNN architecture and the generalist multi-task training results that the open-book framework is built on and compared with.","marker":"[11]"},{"why":"Supplies the pointer graph network processor used as one base architecture in the experiments.","marker":"[29]"},{"why":"Supplies the message-passing neural network processor used as another base architecture.","marker":"[9]"},{"why":"Introduces cross-datapoint attention between data points, the direct precursor of the open-book attention mechanism.","marker":"[15]"},{"why":"Provides the neural priority queue architecture whose reported results are included in the prior-best baseline.","marker":"[12]"}],"fun_headline_variants":["Open-book memory lifts CLRS neural reasoning to 82.9%","Cross-attending training data boosts CLRS F1 to 82.9%","Open-book attention elevates algorithm learning on CLRS","Neural reasoners gain from open-book training examples"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that one randomly sampled adjacent-state pair, mean-pooled over nodes, retains enough of an auxiliary instance's algorithm execution to give useful cross-attention hints; if that compression discards the signal, the open-book gains would come from extra parameters or sampling noise rather than from training-set knowledge.","fun_headline_variants_meta":{"raw":{"variants":["Open-book memory lifts CLRS neural reasoning to 82.9%","Cross-attending training data boosts CLRS F1 to 82.9%","Open-book attention elevates algorithm learning on CLRS","Neural reasoners gain from open-book training examples"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000491,"raw_usage":{"total_tokens":2396,"prompt_tokens":905,"completion_tokens":1491,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":1418}},"tokens_in":521,"tokens_out":1491,"duration_ms":10059,"temperature":1.0,"reasoning_tokens":1418,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:14:27.984007+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Replace the auxiliary representations $R$ in Algorithm 1 with random vectors of the same shape while keeping the dataset encoder and open-book processor parameters intact and retraining; if CLRS F1 scores do not drop materially, the open-book channel is not carrying task information.","supporting_citations":[{"cited_title":"The CLRS algorithmic reasoning benchmark","cited_arxiv_id":null,"evidence_quote":"Supplies the CLRS benchmark, its 30 tasks, and the reference results the study builds on."},{"cited_title":"A generalist neural algorithmic learner","cited_arxiv_id":null,"evidence_quote":"Provides the Triplet-GMPNN architecture and the generalist multi-task training results that the open-book framework is built on and compared with."},{"cited_title":"Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell","cited_arxiv_id":null,"evidence_quote":"Supplies the pointer graph network processor used as one base architecture in the experiments."},{"cited_title":"Schoenholz, Patrick F","cited_arxiv_id":null,"evidence_quote":"Supplies the message-passing neural network processor used as another base architecture."},{"cited_title":"Gomez, Thomas Rainforth, and Yarin Gal","cited_arxiv_id":null,"evidence_quote":"Introduces cross-datapoint attention between data points, the direct precursor of the open-book attention mechanism."},{"cited_title":"Neural priority queues for graph neural networks","cited_arxiv_id":null,"evidence_quote":"Provides the neural priority queue architecture whose reported results are included in the prior-best baseline."}],"review_version":1}