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

arXiv: https://arxiv.org/abs/2606.24980 · HTML: https://mlsanity.com/paper/2606.24980/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 13 references that are in the map.
- First posted on arXiv 23 Jun 2026.

## Builds on (most cited first, 11 of 11)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [The CLRS-Text Algorithmic Reasoning Language Benchmark](https://mlsanity.com/paper/2406.04229/) (2024)
- [Are Large-Language Models Graph Algorithmic Reasoners?](https://mlsanity.com/paper/2410.22597/) (2024)
- [TinyGraphEstimator: Adapting Lightweight Language Models for Graph Structure Inference](https://mlsanity.com/paper/2510.08808/) (2025)

## Abstract (arXiv)

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.