小语言模型执行图算法时，局部准确不等于全局可靠。
Closed-Loop Graph Algorithm Execution with Small Language Models: Step Accuracy and Rollout Reliability
- 将图算法视为闭环决策问题，逐步预测下一步操作。
- 结构化算法如遍历、着色可实现高精度执行，加权算法易累积错误。
- 建议用完整闭环推演评估模型，而非孤立判断单步输出。
小语言模型为大规模系统提供了高效替代方案，但其在多依赖决策中执行结构化算法的能力仍不明确。本文将图算法执行视为闭环预测问题，模型反复根据当前图状态与算法进展选择下一步动作。评估框架涵盖多个经典图算法、多种合成图族，以及独立的训练、验证与测试集。通过步骤准确率、精确回放准确率、约束有效性、部分解质量、前缀存活率及基于干预的诊断方法，同时评估局部决策质量与全局执行行为。结果表明，适配后的小模型能为遍历、着色等结构性算法生成可靠策略，而加权算法对错误累积更为敏感。更广泛而言，强下一步预测能力并不必然带来可靠的自主执行，强调应通过完整的闭环推演来评估算法型语言模型，而非仅分析单步决策。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。