Automata from Agent Traces: Failure and Next-Step Prediction
Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyama
cs.AI, cs.CL, cs.LG
2026-08-25
把十二个公开数据集上的Agent轨迹压成7–43态有限状态机，held-out回放适应度不低于0.997。下一步预测全面超过AWM，失败预测AUROC最高0.94，并可在约32%进度时提前停失败run。
LLM Agent 的执行轨迹很长、没有结构。安全审计、运行时监控、下一步动作预测都需要跨 run 的共享拓扑，但现有做法要么盯单条轨迹，要么只从成功轨迹抽线性工作流。Agent Workflow Memory（AWM）就是后一种：成功路径被收成一串工作流，失败轨迹里的循环和偏航直接丢掉。
Gold 定理说，只有正例时没法在极限里识别目标语言。Agent 的动作字母表却很小，十二个公开数据集只有 6–42 个符号。在 tau2-bench 上，四个聊天模型的轨迹共用一台自动机就能达到完美回放适应度。行为拓扑更接近 harness（系统提示、工具集、任务分布），不太像某个具体 LLM 写出来的。这个约束让从轨迹反推有限状态机变得可做。
构造分三步，没有学习超参。
合并只加出边：训练轨迹在前缀树上能走完，合并后也能走完。得到的对象是观察语料的直接跟随自动机，不是生成语言本身。
有了状态，下一步概率就是该状态下的转移计数加平滑。失败预测把每条轨迹回放到自动机上，抽出按状态的访问频次、消息长度、错误率，再加上轨迹交叉熵、最大 surprise、前后半段漂移这几项异常量，交给梯度提升分类器。在线监控更简单：循环率超过 0.778、加上最少访问状态数和一段预热，全程只做自动机回放，每步 0.006 ms，不训练模型。
十二个数据集上，自动机只有 7–43 个状态，held-out 回放适应度不低于 0.997，构建时间 1–110 ms。相对经典正例学习方法 RPNI，状态数压缩 15–3036 倍；最强正例对手 Alergia 适应度相当，但状态多 1.0–6.0 倍。RPNI 在 WebArena 上会接受 75% 的打乱轨迹，这篇的自动机拒绝全部随机轨迹、以及至少 99.9% 的打乱轨迹。
| 方法 | 平均交叉熵（bits，越低越好） |
| Unigram | 2.44 |
| RPNI | 3.40 |
| 这篇的一阶 FSM | 0.93 |
| FSM + 逻辑回归 | 0.73 |
给 LLM 当下一步上下文时，把整张图塞进去会输给 AWM。最小格式只给当前状态的下一动作概率和 top-15 多步延续：tau2-bench retail 上 top-1 从 AWM 的 52.9% 升到 65.1%，八个数据集全部领先，六组差距 p < 10^{-8}。低成功率数据集上差距更大，因为 AWM 只从成功轨迹抽工作流。
失败预测上，回放适应度本身几乎没信息（AUROC 约 0.50）。按状态特征在 tau2-bench telecom 上 held-out AUROC 达到 0.941，WebArena 0.903，ATBench 0.894，SWE-agent 0.799。SWE-agent 上成功轨迹只用 25 态里的 9 个，失败轨迹铺满全部，长度基线只有 0.659。走完一半时已有最终 AUROC 的 92%。
在线监控在 SWE-agent 上平均 32% 进度触发，精确率 85.9%、召回 95.5%、F1=0.904，省掉后续 68% 计算。高精确率工作点（循环率 > 0.957）精确率 100%、召回 11.3%，更适合自动重置。SWE-agent 失败率 84.3%，「全标失败」的 F1 已经是 0.914；监控器的增量是何时停，不是标不标。字母表更小的 retail 和 SWE-smith 上监控会过触发。
手里已经有轨迹的人，这是一个毫秒级的结构底座，不是一套新的 Agent 架构。状态紧凑，每个状态上的观测够多，正例学习才站得住；RPNI 把同样的观测拆进成千上万个稀疏状态，下一步预测反而比 Unigram 更差。同一台自动机同时当工作流记忆、下一步先验、失败分类特征和运行时监控，不必为四件事各训一条流水线。拓扑跟模型关系弱、跟 harness 关系强，换模型时有机会复用。
这是经典自动机构造搬到 Agent 轨迹上。贡献是证明字母表有界时，这个构造既小又有统计效力。
自动机接受的是观察轨迹的直接跟随闭包。保持活动 bigram 统计的对抗轨迹仍能回放。活动抽取函数按数据集写，需要一点点领域知识，全自动发现还没有。跨模型迁移只在 tau2-bench 三个套件上测过（交叉 AUROC 均值 0.786，自身 0.877）。工作流记忆只对照了 AWM，没对照 ReasoningBank 这类同时用成功和失败轨迹的方法。监控在状态多样性高的数据集上可用，小字母表上要重调规则。SWE-agent 失败率极高，F1 数字会被基率抬起来，读的时候要看精确率和触发时机。