{"id":"758a2885-dadf-4b85-bea6-24b8731223a1","arxiv_id":"2606.24980","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":5.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Small language models adapted for closed-loop graph algorithm execution achieve reliable policies for traversal and coloring but show high sensitivity to error accumulation in weighted procedures, demonstrating that step accuracy does not ensure rollout reliability.","lead":"This paper evaluates small language models executing graph algorithms like traversal and coloring through repeated closed-loop decisions on synthetic graphs. It finds that good single-step accuracy often fails to produce reliable full executions, especially for weighted algorithms.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.3","headline":"Synthetic graph families + disjoint partitions may not suffice to rule out distribution shift or overfitting that confounds the step-vs-rollout distinction","rationale":"The reader's weakest_assumption directly identifies the load-bearing condition for the central claim. Full-text details on graph generation and state encoding would be needed to tighten or refute it, but the abstract-level concern remains the most material one.","tokens_in":1665,"tokens_out":337,"duration_ms":10353,"concrete_test":"Re-generate the test graphs using the exact same families but with fresh random seeds and altered generator parameters (e.g., ER p=0.05 vs. original p=0.1, or BA m=3 vs. original m=2); re-run the closed-loop evaluation on these new graphs using the published model checkpoints. If exact rollout accuracy or prefix survival changes by >15% relative to the original test set while step accuracy remains comparable, the original distinction is likely sensitive to distribution details.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline finding (strong next-step accuracy need not yield reliable closed-loop rollout) requires that observed gaps reflect genuine error accumulation rather than artifacts. The evaluation rests on synthetic graph families, classical procedures, and train/val/test splits. If graph generators permit the model to exploit family-specific regularities (e.g., degree sequences, label correlations) that are preserved across partitions, or if the state representation allows implicit memorization of traversal patterns, then high step accuracy on held-out graphs could still produce artificially low rollout success without proving the broader claim. This assumption is the least secured link in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies small language models executing classical graph algorithms as a closed-loop prediction task, where the model iteratively selects the next action from the current graph and algorithmic state. It introduces an evaluation framework spanning multiple graph procedures, synthetic graph families, and disjoint train/validation/test partitions, and reports results using step accuracy together with rollout metrics such as exact rollout accuracy, constraint validity, partial solution quality, prefix survival, and intervention diagnostics. The central claim is that adaptation yields reliable policies for structural procedures (traversal, coloring) but weighted algorithms remain sensitive to error accumulation, and that high next-step accuracy does not guarantee reliable autonomous execution.","tokens_in":1808,"tokens_out":444,"duration_ms":21629,"significance":"If the evaluation is robust, the work provides concrete evidence that closed-loop rollout metrics are necessary to assess algorithmic language models and that small models can be adapted to reliably execute certain structured procedures. The multi-metric design (step accuracy contrasted with rollout reliability, constraint validity, and intervention diagnostics) is a strength that allows the distinction between local decision quality and global execution behaviour to be quantified.","major_comments":[{"comment":"The headline finding that strong next-step prediction does not necessarily translate into reliable closed-loop rollout depends on the claim that observed gaps reflect genuine error accumulation rather than artifacts. The evaluation framework (abstract and the data-generation and state-representation sections) relies on synthetic graph families and disjoint partitions, yet provides no explicit verification that graph generators or state encodings prevent exploitation of family-specific regularities (e.g., degree sequences or label correlations) preserved across splits. Without such verification or additional controls (e.g., cross-family generalization tests), the step-vs-rollout distinction could be confounded by distribution shift or implicit memorization.","section":"Evaluation framework (abstract; data-generation and state-representation sections)"}],"minor_comments":[{"comment":"The abstract would benefit from briefly stating the model sizes, number of graph families, and number of procedures evaluated to give readers immediate context for the scope of the empirical study.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and for identifying a potential vulnerability in the evaluation design. The concern about possible exploitation of family-specific regularities is substantive and we address it directly below.","responses":[{"response":"We agree that the absence of explicit verification leaves open the possibility that the reported step-vs-rollout gaps partly reflect distribution artifacts rather than pure error accumulation. The manuscript already employs multiple distinct synthetic generators and strictly disjoint train/validation/test partitions, and the qualitative pattern (reliable structural procedures, fragile weighted ones) is consistent across families; however, these measures alone do not constitute the statistical or cross-family controls the referee requests. In the revised version we will add (i) quantitative checks confirming that degree sequences, label correlations, and other low-level statistics do not remain correlated across splits, and (ii) a set of cross-family generalization experiments in which models are trained on one generator family and evaluated on held-out families. These additions will either corroborate or qualify the central claim and will be reported in a new subsection of the evaluation framework.","revision_made":"yes","referee_comment":"[Evaluation framework (abstract; data-generation and state-representation sections)] The headline finding that strong next-step prediction does not necessarily translate into reliable closed-loop rollout depends on the claim that observed gaps reflect genuine error accumulation rather than artifacts. The evaluation framework (abstract and the data-generation and state-representation sections) relies on synthetic graph families and disjoint partitions, yet provides no explicit verification that graph generators or state encodings prevent exploitation of family-specific regularities (e.g., degree sequences or label correlations) preserved across splits. Without such verification or additional controls (e.g., cross-family generalization tests), the step-vs-rollout distinction could be confounded by distribution shift or implicit memorization."}],"tokens_in":1336,"tokens_out":382,"duration_ms":13873,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that this paper shows adaptation can produce reliable policies for structural graph procedures such as traversal and coloring with small language models, while weighted algorithms stay sensitive to error buildup in full rollouts. It also finds that strong next-step accuracy does not guarantee reliable autonomous execution.\n\nThe new piece is the closed-loop evaluation framework that runs models repeatedly on graph state and algorithmic state together. It covers multiple classical procedures, synthetic graph families, and disjoint train/validation/test partitions. The metrics go beyond single-step accuracy to include exact rollout accuracy, constraint validity, partial solution quality, prefix survival, and intervention diagnostics. That combination gives a practical way to measure how local decisions compound over time.\n\nThe work does a solid job laying out the distinction between local prediction quality and global execution success. The split between structural and weighted algorithms is a clear empirical observation that could help people designing agent benchmarks.\n\nThe soft spot is the evaluation design the stress test points to. Synthetic graph families with disjoint partitions might still let models exploit preserved regularities such as degree sequences or label patterns, which could make step accuracy look stronger than the actual policy generalization. Without details on the generators or checks for that kind of leakage, the rollout gaps might partly reflect testbed artifacts rather than pure error accumulation. The abstract gives no error bars or statistical tests, so the strength of the claims depends on how the full experiments handle this.\n\nThis paper is for researchers working on language model agents and sequential decision benchmarks. Readers focused on practical evaluation of small models on structured tasks would get direct value from the metrics and the cautionary results.\n\nIt shows clear thinking on the evaluation problem and honest engagement with the limits of isolated predictions. It deserves a serious referee.\n\nRecommendation: send it for peer review and ask the referee to check the graph generation process and any controls for distribution shift.","headline":"Small LMs can be adapted for reliable closed-loop execution on structural graph tasks like traversal but weighted algorithms suffer from error accumulation, and the synthetic testbed may not cleanly isolate that from distribution artifacts.","tokens_in":2284,"tokens_out":461,"would_cite":false,"duration_ms":23793,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Small language models adapted for graph algorithms produce reliable closed-loop policies for structural tasks like traversal and coloring, but weighted algorithms suffer from error accumulation.","keywords":["small language models","graph algorithms","closed-loop execution","step accuracy","rollout reliability","error accumulation","algorithmic policies","synthetic graphs"],"falsifier":"Finding that models with high step accuracy on the test partitions also achieve high exact rollout accuracy for weighted algorithms would challenge the claim that they remain substantially more sensitive to error accumulation.","tokens_in":2564,"feed_emoji":"🔄","tokens_out":638,"duration_ms":18903,"temperature":0.7,"pith_summary":"This paper investigates whether small language models can execute classical graph algorithms autonomously by repeatedly choosing the next action based on the current graph and state. It finds that adaptation works well for structural procedures such as traversal and coloring, where the model maintains correctness over full executions on held-out graphs. However, for weighted algorithms, small errors compound and prevent successful completion of the procedure. The key insight is that high accuracy on individual steps does not guarantee success when the model must run the entire algorithm without external intervention. This matters because it shows that testing isolated decisions is insufficient for assessing whether language models can serve as autonomous algorithmic agents.","feed_headline":"Small models reliably execute graph traversals but not weighted algorithms","feed_subtitle":"Step accuracy fails to predict full rollout success, showing why closed-loop tests are needed to assess autonomous execution.","key_machinery":"Closed-loop prediction where a model repeatedly selects the next action from the current graph and algorithmic state, assessed via step accuracy, exact rollout accuracy, constraint validity, and intervention diagnostics across synthetic graph families.","core_discovery":"The paper shows that adaptation can produce reliable policies for structural procedures such as traversal and coloring, while weighted algorithms remain substantially more sensitive to error accumulation. More broadly, the findings demonstrate that strong next-step prediction does not necessarily translate into reliable autonomous execution and motivate evaluating algorithmic language models through complete closed-loop rollouts rather than isolated decisions.","pith_inferences":["The step-versus-rollout distinction may apply to other sequential decision tasks where language models act as agents in structured environments.","Error accumulation in weighted cases suggests that recovery mechanisms or verification steps could improve reliability beyond current adaptation.","Extending the framework to non-synthetic graphs could test whether the reliability patterns hold outside the controlled testbed."],"forward_implications":["Adaptation can produce reliable policies for structural procedures such as traversal and coloring.","Weighted algorithms remain substantially more sensitive to error accumulation.","Strong next-step prediction does not necessarily translate into reliable autonomous execution.","Algorithmic language models should be evaluated through complete closed-loop rollouts rather than isolated decisions."],"fun_headline_variants":["Small models master traversals but not weighted graphs","Step accuracy fails to predict rollout success","Weighted algorithms sensitive to error in small models","Closed loop tests expose small model execution limits"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The chosen synthetic graph families, classical procedures, and disjoint train/validation/test partitions form a sufficient and unbiased testbed for assessing closed-loop reliability without distribution shift or overfitting artifacts.","fun_headline_variants_meta":{"raw":{"variants":["Small models master traversals but not weighted graphs","Step accuracy fails to predict rollout success","Weighted algorithms sensitive to error in small models","Closed loop tests expose small model execution limits"]},"model":"grok-4.3","cost_usd":0.007495,"raw_usage":{"total_tokens":3402,"prompt_tokens":593,"num_sources_used":0,"completion_tokens":53,"cost_in_usd_ticks":74949500,"prompt_tokens_details":{"text_tokens":593,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2756,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":593,"tokens_out":53,"duration_ms":22265,"temperature":1.0,"reasoning_tokens":2756,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T00:43:34.790865+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Finding that models with high step accuracy on the test partitions also achieve high exact rollout accuracy for weighted algorithms would challenge the claim that they remain substantially more sensitive to error accumulation.","supporting_citations":[],"review_version":1}