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

• URL: http://arxiv.org/abs/2606.24980v1
• Date: Tue, 23 Jun 2026 13:02:06 GMT
• Title: Closed-Loop Graph Algorithm Execution with Small Language Models: Step Accuracy and Rollout Reliability
• Abstract summary: 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.<n>Our evaluation framework covers several classical graph procedures, multiple synthetic graph families, and disjoint training, validation, and test partitions.
• Score: 0.48302896549293584
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Test-Time Scaling in Reasoning LLMs: Inference Regimes, Evaluation, and Reproducibility [7.838210213616623]
  We develop a systematic account of test-time scaling along three axes.<n>First, we formalize test-time scaling as budgeted inference over the implicit prefix tree of an autoregressive model.<n>Second, we treat the evaluated object as the entire inference system.
  arXiv  Detail & Related papers  (2026-08-04T17:57:20Z)
• Note on Selection Bias in Observational Estimates of Algorithmic Progress [0.0]
  In this note, I raise one potential methodological problem with the estimation strategy.<n>If part of algorithmic quality is latent, and compute choices are endogenous to algorithmic quality, estimates of algorithmic quality will be contaminated by selection bias.
  arXiv  Detail & Related papers  (2025-08-14T19:38:10Z)
• The Pitfalls of Benchmarking in Algorithm Selection: What We Are Getting Wrong [1.973144426163543]
  We highlight methodological issues that frequently occur in the community and should be addressed when evaluating algorithm selection approaches.<n>We show that non-informative features and meta-models can achieve high accuracy, which should not be the case with a well-designed evaluation framework.
  arXiv  Detail & Related papers  (2025-05-12T16:57:45Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• Examining False Positives under Inference Scaling for Mathematical Reasoning [83.97128486951999]
  We systematically examine the prevalence of false positive solutions in mathematical problem solving for language models.<n>Our experimental results reveal that: (1) false positive solutions persist across different models, datasets, and decoding methods, (2) sampling-based inference time scaling methods do not alleviate the problem, and (3) the pass@N evaluation metric is more susceptible to false positives.
  arXiv  Detail & Related papers  (2025-02-10T07:49:35Z)
• Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models [6.54203362045253]
  We study the problem of learning directed acyclic graphs from continuous observational data.<n>We develop a mixed-integer programming framework for learning medium-sized problems.<n>Our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity.
  arXiv  Detail & Related papers  (2024-04-19T02:42:13Z)
• It's All in the Mix: Wasserstein Classification and Regression with Mixed Features [2.2685251390114565]
  We develop and analyze distributionally robust prediction models that faithfully account for the presence of discrete features.<n>We demonstrate that our models can significantly outperform existing methods that are agnostic to the presence of discrete features.
  arXiv  Detail & Related papers  (2023-12-19T15:15:52Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Approximating Euclidean by Imprecise Markov Decision Processes [3.0017241250121383]
  We investigate what kind of approximation guarantees are obtained when the Euclidean process is approximated by finite state approximations. We show that for cost functions over finite time horizons the approximations become arbitrarily precise.
  arXiv  Detail & Related papers  (2020-06-26T11:58:04Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  We propose a systematic method to transform operations into operations that are differentiable and never locally constant. Our approach relies on perturbeds, and can be used readily together with existing solvers. We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
  arXiv  Detail & Related papers  (2020-02-20T11:11:32Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.