{"id":"04d6a0b7-e32e-4bd7-bd22-7efcc392ca12","arxiv_id":"2502.04402","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Graph-based RL agents can solve logic puzzles larger than anything seen in training, with graph structure, reward design, and recurrence each changing how far extrapolation goes.","lead":"Researchers built a graph-based setup for six classic logic puzzles and trained reinforcement learning agents, comparing graph networks against transformers. The study maps which design choices, such as explicit graph structure, dense rewards, and recurrence, allow agents to handle puzzles up to 16 times larger than anything in training.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 50-puzzle test sets at larger sizes are not controlled for generator difficulty, uniqueness, or per-cell hardness, so the x4/x9/x16 solve rates may measure easy large instances rather than genuine extrapolative reasoning.","rationale":"I read the paper in good faith. Its contributions are real and useful in several respects: the new graph interface for six puzzles is a practical advance, the ablations of reward shape and recurrent state are informative, and the Limitations section is honest about the scope of the study. The reader's verdict of CONDITIONAL is appropriate. The single most load-bearing assumption is exactly the one the reader identified: the extrapolation evaluation assumes that the 50-puzzle test sets at each larger size are fair, representative samples of similar rule-governed difficulty. The paper provides no description of test generation, no difficulty control, and no calibration against an independent solver. Because the central claim is a quantitative statement about percentages of solved puzzles at x4/x9/x16 sizes, this gap is not cosmetic; it determines whether the nonzero bars are evidence of extrapolative reasoning or of a confounded difficulty shift. I do not see an internal contradiction or a dishonest presentation, and I do not think this issue by itself forces a rejection. The right response is to keep the verdict CONDITIONAL and require the authors to provide the missing test-generation specification and a difficulty calibration. If the calibration shows that large test instances are systematically easier, the verdict should move toward REJECT; if it confirms comparable hardness, the central claim is substantially strengthened.","tokens_in":14848,"tokens_out":9344,"duration_ms":105503,"concrete_test":"Re-run the evaluation on 50 freshly generated puzzles per size using the same generator API with an explicit difficulty parameter matched to the training distribution and with uniqueness checks, and additionally record the number of search nodes needed by a standard backtracking/constraint-propagation solver on those same test sets. If the larger test puzzles are solved in very few propagation steps (low solver node count) or if the reported extrapolation percentages move outside the stated 95% bootstrap confidence intervals when the difficulty parameter is fixed, then the extrapolation result is confounded with test-set difficulty. This calibration is the minimal check needed to make the central claim measurable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim depends entirely on the extrapolation evaluation, but the paper does not specify how the 50 test puzzles at each size are generated. Section 'Extrapolation Evaluation' only says 'we test on a set of 50 different puzzles'; it does not state the difficulty parameter of Simon Tatham's generator, whether uniqueness is re-checked, whether clue density is held constant, or how hardness scales with size. Table 3 counts unique configurations for choosing training size and is not a description of test-set construction. If larger instances are generated with a looser uniqueness constraint, more filled-in cells, or an easier difficulty setting, then the nonzero x4/x9/x16 solve percentages can be explained by a distribution shift in per-cell difficulty rather than by learned reasoning that transfers across sizes. The monotone decrease in solve rate across sizes is also expected under any size-dependent difficulty model, so it does not by itself establish successful extrapolation. This is the load-bearing weakness because it directly undermines the headline claim that the agent 'solves puzzles 16 times larger'.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a graph-based, multi-agent reinforcement learning framework for solving logic puzzles from the PUZZLES benchmark. Puzzles are represented as graphs with decision-nodes for atomic cells and meta-nodes for shared constraints, and agents are trained with PPO using either a GCN or a transformer processor, in recurrent or state-less modes, and with sparse, iterative, or partial rewards. The central claim is that this approach extrapolates to puzzle sizes far outside the training distribution, including instances up to 16 times larger, and that the architecture's inductive bias, recurrence, and reward design are the key factors controlling this extrapolation.","tokens_in":15057,"tokens_out":3372,"duration_ms":33487,"significance":"If the extrapolation results are reliable, this is a valuable empirical contribution: it provides a graph interface that enables size generalization for six logic puzzles in an RL setting, and it performs systematic ablations of architecture, reward, and recurrence. The paper also makes its code available and builds on a public benchmark. However, the headline quantitative claim depends on an extrapolation evaluation whose test-set generation is not described, and the model-selection procedure overlaps the reported +1 extrapolation results. The significance is therefore conditional on the evaluation being made rigorous and transparent.","major_comments":[{"comment":"The central claim that agents solve puzzles at x4, x9, and x16 sizes relies on 50 test puzzles per size, but the paper never states how these test instances are generated. In particular, it does not specify the difficulty parameter of Simon Tatham's generator, whether uniqueness of solutions is re-checked, whether clue density is held constant across sizes, or how per-cell hardness scales with size. If larger instances are generated with a looser uniqueness constraint, more filled-in cells, or an easier difficulty setting, then the reported solve rates could reflect a distribution shift in per-cell difficulty rather than learned extrapolation. The monotone decrease in solve rates across sizes is also consistent with any size-dependent difficulty model. Please specify the generation protocol and provide per-size difficulty diagnostics (e.g., clue density, number of solutions), or use matched generators with controlled difficulty.","section":"Extrapolation Evaluation"},{"comment":"Model selection is performed on a validation set that is exactly the +1 extrapolation test set. Table 4 shows, for example, that Tents has validation and +1 both at 6x6, Mosaic has both at 5x5, and Loopy has both at 5x5. Thus the reported +1 solve rates are selected on, not independent evidence of extrapolation, and the checkpoints used for the x4/x9/x16 results are chosen using that same criterion. This affects interpretation of Figures 6-8 and should be corrected by using a separate validation split (e.g., a different random set at the training size, or a size that is not later reported as an extrapolation benchmark).","section":"Training / Table 4"},{"comment":"The comparison against PUZZLES baselines is not controlled: the GNN is trained on larger puzzle sizes (Tents 5x5, Lightup 5x5, Mosaic 4x4, Loopy 4x4, Net 4x4), while the baselines are trained on smaller sizes (Tents 4x4, Lightup 3x3, Mosaic 3x3, Loopy 3x3, Net 2x2). The differing training sizes alone can explain a large part of the performance gap. Before claiming superiority over the baselines, the authors should either retrain the baselines on the same puzzle sizes or explicitly report baseline performance at the GNN's training size.","section":"Table 1"},{"comment":"All central comparisons in Figures 6-8 are based on only three seeds and 50 test puzzles per size. The reported 95% bootstrap intervals appear to be computed over puzzles for a fixed selected checkpoint and do not account for seed variance or for the model-selection uncertainty induced by choosing the checkpoint on the validation set. Please report per-seed results, confidence intervals across seeds, or a per-puzzle breakdown, so the reader can judge whether the x9 and x16 solve percentages are stable and not driven by a single seed or a few easy large instances.","section":"Empirical Evaluation"}],"minor_comments":[{"comment":"The parameter list uses the flag 'gcn' but describes it as representing the GENConv architecture, while the main text consistently calls the model a GCN; please clarify the exact architecture used.","section":"Training Parameters and Baseline Establishment"},{"comment":"The sparse reward is defined as 'R reward if the game is solved', but the value of R is never specified; please state it explicitly.","section":"Reward"},{"comment":"Figures 6-8 aggregate results across six puzzles with the interquartile mean, but no per-puzzle extrapolation tables are provided; this makes it hard to assess which puzzles drive the reported effects.","section":"Empirical Evaluation"},{"comment":"There is a typo in the conclusion: 'approache' should be 'approach'.","section":"Conclusion"},{"comment":"The citation to Tönshoff et al. appears with a malformed TeX accent ('T¨onshoff'); please fix the rendering.","section":"Related Work"}],"recommendation":"major_revision","confidential_remarks":"The core idea is interesting and the benchmark extension is potentially useful, but the evaluation protocol currently does not support the strength of the headline claim. The lack of test-set generation details is the most serious issue; I would not require an entirely new study, but the authors need to document and ideally control generator difficulty, fix the validation overlap, and provide more transparent per-seed/per-puzzle statistics. The paper is on the borderline between a solid empirical contribution and a claims-driven workshop paper; the revision should move it firmly toward the former."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid empirical study of what makes GNN-based RL agents extrapolate to larger logic puzzles. The graph interface for six Tatham puzzles is genuinely useful, and the ablations—GNN vs. transformer, recurrent vs. stateless, and three reward schemes—are clean enough to be informative. The main qualitative findings (graph inductive bias helps, partial reward helps at larger sizes, stateless is better at strong extrapolation) look credible. I'd send it to a workshop or a main conference with revision.\n\nThe paper does a few things well. It formulates puzzles as graphs with decision nodes and meta-nodes, and the per-cell action space is a natural fit for GNNs. The six-puzzle selection is thoughtful, and the training-size determination based on 40k unique configurations is a reasonable design choice. The comparison to the original PUZZLES baselines, while not perfectly controlled, does show a clear advantage over cursor-based agents.\n\nWhere it gets soft: First, the Table 1 comparison is apples-to-oranges—the baselines trained on smaller, easier sizes—and the authors admit this in the note, but the headline 'GNN surpasses baseline' is still presented a bit loosely. Second, model selection on a validation set one size larger leaks into the reported +1 numbers; that's not fatal but should be stated more carefully. Third, the text leaves serious reproducibility gaps: code isn't shipped, and key hyperparameters appear as placeholders (<horizon>, <epochs>, <batch size>) in the appendix. That's a problem for an empirical paper.\n\nThe bigger issue is the extrapolation evaluation itself. The paper says 'we test on a set of 50 different puzzles' at each size, but never specifies how those puzzles are generated: which difficulty parameter of Tatham's generator is used, whether uniqueness is re-checked, or how clue density scales. If larger instances are generated with a looser difficulty setting or more filled-in cells, the x4/x9/x16 solve rates could reflect distribution shift in per-cell difficulty rather than learned reasoning. This doesn't invalidate the relative comparisons—the same test sets are used across architectures—but it does undermine the absolute claim of solving puzzles 16 times larger. The authors should document the generator settings and ideally report per-instance hardness measures.\n\nA minor note: three seeds is a bit thin, and 50 puzzles per test size gives wide confidence intervals. The stratified bootstrap CIs help, but the headline numbers are still noisy.\n\nBottom line: the paper is worth engaging with. The graph interface and the ablation results are a useful contribution to the RL generalization literature. It needs a serious referee to push on the evaluation protocol and reproducibility, but the core idea is sound.","headline":"Useful graph benchmark and ablations for RL extrapolation, but the absolute extrapolation numbers rest on an underspecified test-generation procedure.","tokens_in":15588,"tokens_out":2203,"would_cite":true,"duration_ms":21007,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68T20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Modeling logic puzzles as graphs lets reinforcement-learned agents solve instances up to 16 times larger than anything seen in training.","keywords":["graph neural networks","reinforcement learning","extrapolation","logic puzzles","size generalization","multi-agent RL","PPO","reward design"],"falsifier":"Generate 50 or more larger instances with controlled difficulty (for example, by fixing the number of given clues or the number of solutions), then rerun the trained agents; if the fraction solved collapses when difficulty is held constant, the reported extrapolation is an artifact of easier large instances rather than genuine rule-based reasoning.","tokens_in":14643,"feed_emoji":"🧩","tokens_out":4311,"duration_ms":38131,"temperature":0.7,"pith_summary":"This paper argues that the right representational bias, reward signal, and sequential state can let a reinforcement-learning agent extrapolate to logic puzzles far beyond its training distribution. The authors model six logic puzzles as graphs, train a multi-agent PPO policy with a graph neural network on one small size, and measure how often it solves larger instances. They report that the GNN-based agent solves puzzles up to 16 times larger than the training size, while a transformer baseline and sparse rewards largely fail. The paper's central claim is that architecture inductive bias, recurrence, and reward design control whether a model reasons beyond interpolation.","feed_headline":"Graph-based RL agents solve logic puzzles 16x larger than trained on","feed_subtitle":"A PPO-GNN multi-agent setup with dense rewards extends to unseen, larger instances of six logic puzzles.","key_machinery":"The load-bearing machinery is the graph interface plus the reward formulation. Each puzzle is encoded as a graph with decision-nodes (cells that take actions), meta-nodes (row/column or face constraints), and feature vectors; because the local neighborhood pattern is identical at every size, the same GCN can process larger puzzles by message passing. The reward is defined as the maximal improvement in the number of cells matching the unique solution, $Q(G) = \\sum_{i} \\delta(g_i, \\hat{g}_i)$, with a partial variant that counts only cells not involved in a rule violation. This dense reward is what carries training signal, and the paper's ablations show it is the difference between agents that extrapolate and agents that learn nothing.","core_discovery":"The central claim is that extrapolative reasoning on logic puzzles can be achieved by a graph-based multi-agent reinforcement learning system, and that three design choices determine success. First, representing puzzle cells as decision-nodes and constraints as meta-nodes in a graph lets GNNs operate on any size with the same local structure. Second, replacing sparse terminal rewards with dense rewards that measure improvement toward the unique solution—either iterative improvement or a partial variant that ignores violated cells—is necessary for learning at all. Third, a recurrent state helps at modest extrapolation sizes while a state-less policy solves more puzzles at the largest sizes. With these components, the agent solves a meaningful fraction of instances at x4, x9, and even x16 the training size, which the authors take as evidence that it has extracted the underlying rules rather than memorized patterns.","pith_inferences":["Beyond the paper: a testable extension is to vary the density of clues or the number of candidate solutions at each size; if performance tracks instance difficulty rather than size alone, the reported percentages conflate size with difficulty.","Beyond the paper: the same decision-node/meta-node graph encoding is a generic template for constraint satisfaction problems, so the approach likely transfers beyond the six puzzles studied here.","Beyond the paper: because only 50 test puzzles are used per size, the confidence intervals could hide large variance; a larger test sample or a difficulty-controlled generator would sharpen the extrapolation measure.","Beyond the paper: the recurrent-versus-state-less trade-off suggests a hybrid policy that uses recurrence early in an episode and drops it later, a configuration the paper does not explore."],"forward_implications":["If the central claim holds, a model trained on small puzzle instances can be deployed directly on larger instances of the same rule set, avoiding the need to collect training data at every size.","The observed advantage of GNNs over transformers with positional encodings suggests that explicitly encoding relational structure matters more than raw capacity for size extrapolation.","The result that state-less policies outperform recurrent ones at the largest sizes implies that for stateless puzzles, a 3-hop receptive field plus repeated application can replace an explicit memory mechanism.","Dense, solution-proximity-based rewards appear to be a prerequisite for learning any generalizable policy, which informs reward design in other combinatorial reasoning tasks."],"supporting_citations":[{"why":"Supplies the PUZZLES benchmark and the baseline RL interface that this paper replaces with a graph-based one.","marker":"Estermann et al. (2024)"},{"why":"Provides the iterative reward technique based on improvement toward a known solution that the paper adapts.","marker":"T¨onshoff et al. (2022)"},{"why":"Establishes the CLRS algorithmic reasoning benchmark that motivates evaluating neural models on size generalization.","marker":"Velickovic et al. (2022)"},{"why":"Defines the GCN architecture used as the graph processor for both policy and value estimation.","marker":"Kipf and Welling (2017b)"},{"why":"Supplies the PPO algorithm used to train all agents in the paper.","marker":"Schulman et al. (2017)"},{"why":"Provides the message-passing formalism and sum-aggregation design that the paper adopts for its GNN layers.","marker":"Xu et al. (2019)"},{"why":"Defines the transformer baseline used as the non-graph architecture for comparison.","marker":"Vaswani et al. (2017)"}],"fun_headline_variants":["Graph RL agents reason on logic puzzles 16x larger","GNN-RL: dense rewards unlock extrapolative reasoning","RL+GNN solve unseen logic puzzles via design choices","Multi-agent graph RL scales logic puzzles 16x","Dense rewards key to GNN-RL extrapolation on puzzles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The extrapolation percentages rest on the assumption that the 50 test puzzles at each larger size are fair, representative samples generated by the same rule set, with comparable difficulty per size; the paper does not describe how test instances are produced or how difficulty scales.","fun_headline_variants_meta":{"raw":{"variants":["Graph RL agents reason on logic puzzles 16x larger","GNN-RL: dense rewards unlock extrapolative reasoning","RL+GNN solve unseen logic puzzles via design choices","Multi-agent graph RL scales logic puzzles 16x","Dense rewards key to GNN-RL extrapolation on puzzles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000171,"raw_usage":{"total_tokens":1243,"prompt_tokens":887,"completion_tokens":356,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":503,"completion_tokens_details":{"reasoning_tokens":274}},"tokens_in":503,"tokens_out":356,"duration_ms":4141,"temperature":1.0,"reasoning_tokens":274,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T00:30:05.479661+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate 50 or more larger instances with controlled difficulty (for example, by fixing the number of given clues or the number of solutions), then rerun the trained agents; if the fraction solved collapses when difficulty is held constant, the reported extrapolation is an artifact of easier large instances rather than genuine rule-based reasoning.","supporting_citations":[{"cited_title":"PUZZLES: A Benchmark for Neural Algorithmic Reasoning","cited_arxiv_id":"2407.00401","evidence_quote":"Supplies the PUZZLES benchmark and the baseline RL interface that this paper replaces with a graph-based one."},{"cited_title":"P.; Budden, D.; Pascanu, R.; Banino, A.; Dashevskiy, M.; Hadsell, R.; and Blundell, C","cited_arxiv_id":null,"evidence_quote":"Establishes the CLRS algorithmic reasoning benchmark that motivates evaluating neural models on size generalization."},{"cited_title":"N.; Kaiser, L.; and Polosukhin, I","cited_arxiv_id":null,"evidence_quote":"Defines the transformer baseline used as the non-graph architecture for comparison."}],"review_version":1}