Closed-Loop Graph Algorithm Execution with Small Language Models: Step Accuracy and Rollout Reliability

Michal Podstawski

REVIEW 1 major objections 1 minor 13 references

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.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-26 00:43 UTC pith:E52E6VHA

load-bearing objection 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. the 1 major comments →

arxiv 2606.24980 v1 pith:E52E6VHA submitted 2026-06-23 cs.LG

Closed-Loop Graph Algorithm Execution with Small Language Models: Step Accuracy and Rollout Reliability

Michal Podstawski This is my paper

classification cs.LG

keywords small language modelsgraph algorithmsclosed-loop executionstep accuracyrollout reliabilityerror accumulationalgorithmic policiessynthetic graphs

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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.

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

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.

read the 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.

The 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.

The 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.

The 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.

This 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.

It shows clear thinking on the evaluation problem and honest engagement with the limits of isolated predictions. It deserves a serious referee.

Recommendation: send it for peer review and ask the referee to check the graph generation process and any controls for distribution shift.

Referee Report

1 major / 1 minor

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.

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 (1)

[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.

minor comments (1)

[Abstract] 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.

Simulated Author's Rebuttal

1 responses · 0 unresolved

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.

read point-by-point responses

Referee: [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.

Authors: 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: yes

Circularity Check

0 steps flagged

No circularity: purely empirical evaluation with no derivations or self-referential reductions

full rationale

The paper is an empirical study that trains and evaluates small language models on closed-loop execution of classical graph algorithms (traversal, coloring, etc.) across synthetic graph families with disjoint train/val/test partitions. It reports observational metrics (step accuracy, rollout accuracy, constraint validity, etc.) without any claimed derivations, fitted parameters renamed as predictions, uniqueness theorems, or ansatzes. The central claim—that strong next-step prediction need not yield reliable rollouts—is presented as an experimental finding, not a mathematical reduction to inputs. No load-bearing self-citations or self-definitional steps appear in the provided text. This matches the default case of a self-contained empirical paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No mathematical derivations, free parameters, or invented entities are described; the work is an empirical evaluation study.

pith-pipeline@v0.9.1-grok · 5677 in / 1095 out tokens · 19920 ms · 2026-06-26T00:43:34.790865+00:00 · methodology

0 comments

read the original abstract

Small language models offer an efficient alternative to large-scale systems, but their ability to execute structured algorithms over multiple dependent decisions remains poorly understood. We study graph algorithm execution as a closed-loop prediction problem in which a model repeatedly selects the next action from the current graph and algorithmic state. Our evaluation framework covers several classical graph procedures, multiple synthetic graph families, and disjoint training, validation, and test partitions. It assesses both local decision quality and global execution behaviour using step accuracy, exact rollout accuracy, constraint validity, partial solution quality, prefix survival, and intervention-based diagnostics. The results show 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.

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 6 canonical work pages · 3 internal anchors

[1]

Learning to Execute

Zaremba, W., Sutskever, I.: Learning to execute. arXiv preprint arXiv:1410.4615 (2014)

work page internal anchor Pith review Pith/arXiv arXiv 2014
[2]

In: International Conference on Learning Representations (ICLR) (2020)

Veličković, P., Ying, R., Padovano, M., Hadsell, R., Blundell, C.: Neural execution of graph algorithms. In: International Conference on Learning Representations (ICLR) (2020)

2020
[3]

In: Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR, vol

Veličković, P., Puigdomènech Badia, A., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., Blundell, C.: The CLRS algorithmic reasoning bench- mark. In: Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR, vol. 162, pp. 22084-22102 (2022)

2022
[4]

In: Proceedings of the First Learning on Graphs Conference, PMLR, vol

Ibarz, B., Kurin, V., Papamakarios, G., et al.: A generalist neural algorithmic learner. In: Proceedings of the First Learning on Graphs Conference, PMLR, vol. 198, pp. 2:1-2:23 (2022)

2022
[5]

In: Proceedings of the 40th International Conference on Machine Learning (ICML), PMLR, vol

Bevilacqua, B., Nikiforou, K., Ibarz, B., Bica, I., Paganini, M., Blundell, C., Mitro- vic, J., Veličković, P.: Neural algorithmic reasoning with causal regularisation. In: Proceedings of the 40th International Conference on Machine Learning (ICML), PMLR, vol. 202, pp. 2272-2288 (2023)

2023
[6]

arXiv preprint arXiv:2406.04229 (2024)

Markeeva, L., McLeish, S., Ibarz, B., Bounsi, W., Kozlova, O., Vitvitskyi, A., Blundell, C., Goldstein, T., Schwarzschild, A., Veličković, P.: The CLRS-Text al- gorithmic reasoning language benchmark. arXiv preprint arXiv:2406.04229 (2024)

work page arXiv 2024
[7]

Podstawski

Taylor, A.K., Cuturrufo, A., Yathish, V., Ma, M.D., Wang, W.: Are large-language models graph algorithmic reasoners? arXiv preprint arXiv:2410.22597 (2024) 10 M. Podstawski

work page arXiv 2024
[8]

In: International Conference on Learning Representations (ICLR) (2022)

Hu, E.J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W.: LoRA: Low-rank adaptation of large language models. In: International Conference on Learning Representations (ICLR) (2022)

2022
[9]

In: Advances in Neural Information Processing Systems (NeurIPS), vol

Dettmers, T., Pagnoni, A., Holtzman, A., Zettlemoyer, L.: QLoRA: Efficient fine- tuning of quantized LLMs. In: Advances in Neural Information Processing Systems (NeurIPS), vol. 36 (2023)

2023
[10]

The Llama 3 Herd of Models

Dubey, A., Jauhri, A., Pandey, A., et al.: The Llama 3 herd of models. arXiv preprint arXiv:2407.21783 (2024)

work page internal anchor Pith review Pith/arXiv arXiv 2024
[11]

Qwen2.5 Technical Report

Qwen Team: Qwen2.5 technical report. arXiv preprint arXiv:2412.15115 (2024)

work page internal anchor Pith review Pith/arXiv arXiv 2024
[12]

arXiv preprint arXiv:2510.08808 (2025)

Podstawski, M.: TinyGraphEstimator: Adapting lightweight language models for graph structure inference. arXiv preprint arXiv:2510.08808 (2025)

work page arXiv 2025
[13]

https://chatgpt.com/

OpenAI: ChatGPT. https://chatgpt.com/. Accessed 23 June 2026

2026

[1] [1]

Learning to Execute

Zaremba, W., Sutskever, I.: Learning to execute. arXiv preprint arXiv:1410.4615 (2014)

work page internal anchor Pith review Pith/arXiv arXiv 2014

[2] [2]

In: International Conference on Learning Representations (ICLR) (2020)

Veličković, P., Ying, R., Padovano, M., Hadsell, R., Blundell, C.: Neural execution of graph algorithms. In: International Conference on Learning Representations (ICLR) (2020)

2020

[3] [3]

In: Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR, vol

Veličković, P., Puigdomènech Badia, A., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., Blundell, C.: The CLRS algorithmic reasoning bench- mark. In: Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR, vol. 162, pp. 22084-22102 (2022)

2022

[4] [4]

In: Proceedings of the First Learning on Graphs Conference, PMLR, vol

Ibarz, B., Kurin, V., Papamakarios, G., et al.: A generalist neural algorithmic learner. In: Proceedings of the First Learning on Graphs Conference, PMLR, vol. 198, pp. 2:1-2:23 (2022)

2022

[5] [5]

In: Proceedings of the 40th International Conference on Machine Learning (ICML), PMLR, vol

Bevilacqua, B., Nikiforou, K., Ibarz, B., Bica, I., Paganini, M., Blundell, C., Mitro- vic, J., Veličković, P.: Neural algorithmic reasoning with causal regularisation. In: Proceedings of the 40th International Conference on Machine Learning (ICML), PMLR, vol. 202, pp. 2272-2288 (2023)

2023

[6] [6]

arXiv preprint arXiv:2406.04229 (2024)

Markeeva, L., McLeish, S., Ibarz, B., Bounsi, W., Kozlova, O., Vitvitskyi, A., Blundell, C., Goldstein, T., Schwarzschild, A., Veličković, P.: The CLRS-Text al- gorithmic reasoning language benchmark. arXiv preprint arXiv:2406.04229 (2024)

work page arXiv 2024

[7] [7]

Podstawski

Taylor, A.K., Cuturrufo, A., Yathish, V., Ma, M.D., Wang, W.: Are large-language models graph algorithmic reasoners? arXiv preprint arXiv:2410.22597 (2024) 10 M. Podstawski

work page arXiv 2024

[8] [8]

In: International Conference on Learning Representations (ICLR) (2022)

Hu, E.J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W.: LoRA: Low-rank adaptation of large language models. In: International Conference on Learning Representations (ICLR) (2022)

2022

[9] [9]

In: Advances in Neural Information Processing Systems (NeurIPS), vol

Dettmers, T., Pagnoni, A., Holtzman, A., Zettlemoyer, L.: QLoRA: Efficient fine- tuning of quantized LLMs. In: Advances in Neural Information Processing Systems (NeurIPS), vol. 36 (2023)

2023

[10] [10]

The Llama 3 Herd of Models

Dubey, A., Jauhri, A., Pandey, A., et al.: The Llama 3 herd of models. arXiv preprint arXiv:2407.21783 (2024)

work page internal anchor Pith review Pith/arXiv arXiv 2024

[11] [11]

Qwen2.5 Technical Report

Qwen Team: Qwen2.5 technical report. arXiv preprint arXiv:2412.15115 (2024)

work page internal anchor Pith review Pith/arXiv arXiv 2024

[12] [12]

arXiv preprint arXiv:2510.08808 (2025)

Podstawski, M.: TinyGraphEstimator: Adapting lightweight language models for graph structure inference. arXiv preprint arXiv:2510.08808 (2025)

work page arXiv 2025

[13] [13]

https://chatgpt.com/

OpenAI: ChatGPT. https://chatgpt.com/. Accessed 23 June 2026

2026