基于小语言模型的闭环图算法执行：步骤准确性与展开可靠性

# 使用小型语言模型执行闭环图算法：步骤准确性与展开可靠性

来源：https://arxiv.org/html/2606.24980

11institutetext：NASK国家研究所，波兰华沙
https://nask.pl/
11email：michal\.podstawski@nask\.pl

###### 摘要

小型语言模型为大规模系统提供了一种高效的替代方案，但它们执行涉及多个依赖决策的结构化算法的能力仍然知之甚少。我们将图算法执行作为一个闭环预测问题来研究，其中模型根据当前图和算法状态反复选择下一个动作。我们的评估框架涵盖了几种经典图过程、多个合成图族，以及互不相交的训练、验证和测试划分。它使用步骤准确性、精确展开准确性、约束有效性、部分解质量、前缀存活率以及基于干预的诊断方法，同时评估局部决策质量和全局执行行为。结果表明，适应可以产生用于遍历和着色等结构过程的可靠策略，而加权算法对误差累积仍然更为敏感。更广泛地说，研究结果表明，强大的下一步预测不一定能转化为可靠的自主执行，并激励通过完整的闭环展开而非孤立决策来评估算法语言模型。

## 1 引言

语言模型越来越多地被用于预测不是最终答案而是改变外部系统状态的动作的设置中。在这种设置中，可靠性不仅取决于孤立预测的质量。一个动作会改变下一步观察到的输入，因此即使是小的局部误差也可能使系统偏离训练中遇到的状态，并改变后续的每一个决策。经典图算法提供了一个受控的环境来研究这种区别：它们的状态转换是显式的，正确的动作可以自动生成，最终输出可以在没有学习评判的情况下检查。

本文研究小型语言模型（SLMs）作为图算法执行的闭环策略。在每个步骤中，模型接收图和当前符号状态的文本描述，并发出一个紧凑的、机器可解析的动作。一个确定性的执行器应用该动作并构建下一个状态。这种分离将状态转换语义保留在模型之外，同时让模型暴露于自身决策的后果。我们在六个图过程上评估两个经过指令调优的SLM，并比较教师强制下的下一步动作准确性与自主展开的结果。

实验揭示了局部能力与全局可靠性之间的一致分离。遍历策略在完整展开中保持其高步骤准确性，着色则相对稳健。相比之下，加权过程表现出大的步骤-轨迹差距：模型经常选择看似合理的单个动作，但无法在完整执行中保持正确性。前缀存活率和干预诊断定位了这种失败，并表明单个聚合步骤分数可能掩盖显著不同的执行行为。

本工作的贡献是：

- •一个闭环公式，其中SLM预测一个图算法动作，符号执行器拥有状态转换；
- •在六种算法、三个随机图族和两个独立适应的SLM架构上的受控评估；
- •结合教师强制步骤准确性、自主展开准确性、前缀存活率、任务特定部分质量和预言修正需求的联合分析；
- •经验证据表明，高的下一步动作准确性可能与严重的展开不可靠性共存，特别是对于加权图过程。

## 2 相关工作

神经算法推理研究学习模型是否能够重现算法的转换过程，而不仅仅是预测其最终输出。早期循环方法学习了短执行轨迹[1 (https://arxiv.org/html/2606.24980#bib.bib1)]，而基于图的神经执行器引入了与关系算法结构一致的架构[2 (https://arxiv.org/html/2606.24980#bib.bib2)]。后来的CLRS基准提供了跨多种算法的标准化中间监督[3 (https://arxiv.org/html/2606.24980#bib.bib3)]，支持多任务迁移和分布外泛化的研究[4 (https://arxiv.org/html/2606.24980#bib.bib4),5 (https://arxiv.org/html/2606.24980#bib.bib5)]。这条工作线主要研究学习处理器设计和算法泛化；我们则使用图算法来检查自回归语言模型策略的执行可靠性。

最近的工作将算法执行表示为文本。CLRS-Text训练语言模型生成文本轨迹和输出[6 (https://arxiv.org/html/2606.24980#bib.bib6)]，而MAGMA评估中间执行阶段的图算法推理[7 (https://arxiv.org/html/2606.24980#bib.bib7)]。这些研究侧重于生成或评估文本轨迹和中间状态。我们的公式则将模型视为动作策略：它发出一个紧凑的动作，一个外部符号执行器应用相应的状态转换。这使得相同的策略既可以在参考状态上评估，也可以在其自身先前动作诱导的状态下评估。由此产生的比较，连同前缀存活率和预言修正诊断，直接衡量局部预测误差在自主执行期间如何累积。

## 3 问题公式化

设 G=\(V,E,w\) 为一个图，其中 w 对于无权重任务省略。对于算法 A，令 s_t 表示经过 t 次转换后的符号状态，a_t 表示离散动作。一个确定性的转移函数

s_{t+1}=T_A(G,s_t,a_t) (1)

更新状态，终止谓词 D_A(G,s_t) 指示执行是否完成。一个确定性的参考实现为每个可达参考状态定义规范动作 a_t^⋆，并产生轨迹

τ^⋆=\( (s_0^⋆,a_0^⋆),...,(s_{T-1}^⋆,a_{T-1}^⋆) \)。 (2)

语言模型表示策略

π_θ( a_t | x(G,s_t) )， (3)

其中 x(G,s_t) 是图和当前状态的文本序列化。输出空间被有意地紧凑化：一行代表一个动作。执行器解析该行，验证其语法，并通过 T_A 应用结果动作。

从这个公式出发，有两种评估体制。在教师强制步骤评估中，模型仅在参考状态 s_t^⋆ 上被查询。这衡量了当输入状态已知正确时它能否识别正确的局部转换。在自主展开评估中，执行从 s_0^⋆ 开始，但随后的每个状态都是由模型自身动作产生的。因此，在发生错误后，模型可能遇到参考轨迹之外的状态。两种体制之间的差异是研究的主要对象。

## 4 实验协议

### 4.1 图与数据划分

我们使用来自 TinyGraphEstimator 集合 [12 (https://arxiv.org/html/2606.24980#bib.bib12)] 的图。实验子集包含 1,200 个无向图，分为 900 个训练图、150 个验证图和 150 个测试图。每个划分在 Barabási-Albert、Erdős-Rényi 和 Watts-Strogatz 生成器之间平衡：训练集包含每个族 300 个图，而验证集和测试集各包含每个族 50 个。图包含 20 到 30 个顶点。使用生成器族、种子、图大小和生成器参数检查划分完整性；没有这样的来源签名出现在多个划分中。

源数据是无权重的。对于 Prim、Borůvka 和 Dijkstra，每条无向边获得 [1,10] 范围内的确定性整数权重。权重通过对图来源和规范化的端点对进行哈希获得，使权重在机器和重复运行之间保持稳定，而不会在训练期间暴露测试信息。

### 4.2 算法策略

我们评估 BFS、DFS、贪心着色、Borůvka 最小生成树过程、Dijkstra 最短路算法和 Prim 最小生成树过程。基于源的算法从顶点 0 开始。一个参考实现提供了统一接口，用于状态初始化、规范下一个动作生成、动作应用、终止和最终答案提取。表1 (https://arxiv.org/html/2606.24980#S4.T1) 总结了紧凑的动作空间和生成的监督量。

每个训练示例包含完整的文本状态，后跟一个目标动作。BFS 和 DFS 预测哪些新发现的邻居被入队或入栈。着色为当前顶点分配颜色。Prim 和 Borůvka 选择一条加权边，而 Dijkstra 选择下一个要访问的顶点及其松弛操作。提示仅暴露当前算法状态中可用的信息；不包含预计算的未来动作。

表1：任务公式和生成的监督。成对计数报告从 900/150 个图生成的训练/验证下一步动作示例；平均长度在 150 个测试轨迹上计算。

### 4.3 模型与适应

我们适应 Llama-3.2-1B-Instruct 和 Qwen2.5-1.5B-Instruct [10 (https://arxiv.org/html/2606.24980#bib.bib10),11 (https://arxiv.org/html/2606.24980#bib.bib11)]。为每个模型-算法对训练一个单独的适配器。基础权重被量化为 4 位 NF4 并双重量化，LoRA [8 (https://arxiv.org/html/2606.24980#bib.bib8),9 (https://arxiv.org/html/2606.24980#bib.bib9)] 更新应用于查询、键、值、输出、门、上投影和下投影模块。我们使用秩 16、缩放因子 32 和丢弃率 0.05。

训练只最小化目标动作标记上的因果语言模型损失；提示标记被掩码。我们使用 AdamW，学习率 2×10^{-4}，零权重衰减，余弦调度，3% 热身，梯度裁剪于 1.0，以及通过物理批大小 1 和 16 梯度累积步骤获得的有效批大小 16。训练最多运行 8 个 epoch，种子 42。保留验证损失最低的适配器，并在两个 epoch 没有改进后停止训练，最小改进为 10^{-4}。

最大上下文长度由任务选择：BFS 和 DFS 为 1,024 个标记，着色为 1,536 个，加权算法为 2,048 个。评估使用贪心解码，无采样或束搜索，最多生成 64 个新标记。仅第一个非空输出行被解析为动作。所有报告的测试结果使用验证选择的适配器和固定的 150 图测试划分。

### 4.4 未适应基线

为了将适应与指令遵循分开，我们使用相同的图状态、动作格式、确定性解码和每个算法 150 个测试图评估未适应的指令模型。零样本提示指定所需的一行语法，但不提供演示或参数更新。我们另外评估一个链式思考 (CoT) 变体，要求先有一个简短的推理，然后是最终的可执行动作。在两种模型和六种算法上，零样本提示没有产生任何精确轨迹（0/1,800 次展开；0.00%），CoT 提示产生相同结果（0/1,800；0.00%）。尽管两种设置偶尔正确预测单个动作，但在任何模型-算法组合中都没有实现完整的规范执行。因此，未适应模型在这种设置下几乎没有闭环执行能力，引出额外的推理并不能解决失败。

## 5 评估度量

##### 步骤准确性。

步骤准确性是模型解析出的动作与规范下一个动作精确匹配的参考状态比例。它是教师强制的：每次查询都使用正确的参考状态，即使模型在更早的步骤会失败。

##### 精确展开准确性。

从算法初始化的状态开始，模型自主选择动作，直到终止或失败。精确展开准确性是最终答案等于规范参考答案的测试图比例。对于 BFS 和 DFS，相等性由有序遍历定义；对着色和 Dijkstra，由完整节点分配定义；对 Prim 和 Borůvka，由规范化的选定边集定义。因此，该度量评估完整闭环执行的结果，而不仅仅是最后教师强制步骤。

##### 约束有效性。

我们还报告一个故意较弱的、任务特定的约束检查。对于遍历，它验证一个源于源、无重复且仅包含可达顶点的序列；对于 Prim 和 Borůvka，它验证所选边形成一棵生成树；对于 Dijkstra，它验证一个满足边不等式的完整非负距离标签；对于着色，它验证一个完整无冲突的分配。此诊断不应被解释为精确任务准确性：例如，它不测试生成树的最小权重，也不要求遍历序列包含每个可达顶点。

##### 软得分。

软得分衡量与参考答案的部分一致性。对于 BFS 和 DFS，它是顺序位置准确性；对着色，是节点颜色准确性；对 Prim 和 Borůvka，是边 F1；对 Dijkstra，是精确节点距离准确性。由于这些定义不同，软得分在算法内可跨模型比较，但不可跨算法比较。

##### 展开诊断。

步骤-轨迹差距是步骤准确性与精确展开准确性之间的差异。位置 k 上的前缀存活率是前 k 个动作匹配参考轨迹的测试展开比例；前缀 AUC 是该存活曲线在所有允许位置上的平均值。首个错误索引是错误展开首次偏离参考的位置。最后，干预展开在每个参考修正状态处查询模型，使用预言动作推进，并统计模型预测需要被替换的次数。报告的修正次数是每个图此类替换的平均数量。

## 6 结果

未适应模型在六种算法上均未产生精确自主展开。这一结果不能仅由格式错误的输出解释：模型偶尔选择正确的单个动作，但这些动作没有形成完整的规范执行。参数高效适应显著改变了这种行为。

表2 (https://arxiv.org/html/2606.24980#S6.T2) 报告了主要结果。BFS 和 DFS 是最可靠的任务。Llama 分别达到 97.33% 和 96.00% 的精确展开准确性，而 Qwen 达到 95.33% 和 94.00%。它们的步骤准确性也很高，但更重要的观察是这种局部能力在完整的自主执行中仍然存在。着色稍难：对于 Llama，展开准确性为 80.00%，Qwen 为 86.00%，尽管两个模型的步骤准确性都超过 98%。

表2：在 150 个保留测试图上的性能。所有值都