Automata from Agent Traces: Failure and Next-Step Prediction 精读

论文链接：arxiv.org/abs/2608.23670 发表时间：2026年8月 机构：Holistic AI（企业）、PUC-Rio（巴西高校）、UCL（英国高校）——企业主导的多机构合作；发表于 ICML 2026 AIWILD workshop 领域标签：cs.AI / 智能体安全 / 行为分析 / 运行时监控

一、论文背景

1.1 Agent 轨迹：行为的"黑匣子飞行记录"

LLM Agent 已经能修 GitHub issue、操作网页、管理桌面环境、处理客服工单。按照 ReAct 范式，它们交替进行"思维链推理 + 工具调用"，每跑完一个任务就留下一条长长的执行轨迹（trace）——一串带角色（系统/用户/助手/工具）的消息序列。

问题在于：这些轨迹是非结构化的。一个编码 Agent 明明有"搜索→编辑→执行→提交"的循环模式，一个客服 Agent 明明在"查数据库↔回用户"之间往返，但这个行为结构从未被显式写出——它隐含在系统提示、可用工具和任务分布的交互里。于是想审计 Agent 是否安全、想在线监控它是否在失败、想预测它下一步要干什么，都只能在一条条孤立的长文本里挣扎。

1.2 现有方法为什么不够用

用一个类比来理解：现有方法像是只看单场球赛录像、且只看赢球的场次。

• 逐轨迹分析：AgentMonitor 等方法对每条轨迹单独提特征，看不到跨运行的共享拓扑——就像只看单场录像永远发现不了"球队总是下半场崩盘"这种跨场次规律；
• 只用成功轨迹：Agent Workflow Memory（AWM）只从成功轨迹里抽取线性工作流，失败模式（恰恰是安全监控最关心的）被完全丢弃；
• 手工指定状态机：StateFlow 等靠人工写 FSM，换一个场景就得重写；
• 经典自动机学习：RPNI、EDSM 需要负例样本或查询 oracle，而 Agent 轨迹只有正例——这是语法推断理论里的一个根本困难。

1.3 理论障碍：只有正例学不出目标语言

Gold 在 1967 年就证明：仅从正例出发，在极限内识别目标语言是不可能的。放在 Agent 场景：你手里只有"Agent 实际做了什么"的轨迹，没有"Agent 绝不会做什么"的负例，想恢复"生成这些行为的完整规则"在数学上无解。

本文的破局点是发现了一个领域特有的逃生通道：Agent 的行为由一组有界的工具和动作生成，活动字母表只有 6-42 个符号——比自然语言小三个数量级。字母表小，问题就从"不可解"变成"良态"。

二、论文定位和关联工作

2.1 研究谱系一：Agent 安全与监控

2.2 研究谱系二：Agent 行为抽象与工作流记忆

• AWM：从成功轨迹抽线性工作流，无状态抽象、无循环表示、不能处理低成功率数据集（SWE-smith 上只有 34.5%）；
• Reflexion / ETO：从失败中做言语反思或对比学习，不产出结构模型；
• MetaAgent / StateFlow / AFlow：要么自上而下从任务描述建 FSM、要么人工指定、要么 MCTS 搜索工作流——都不是从原始轨迹自下而上恢复。

2.3 研究谱系三：过程挖掘与语法推断

过程挖掘从业务事件日志恢复 Petri 网，但标准挖掘器在 Agent 轨迹上产出"花模型"（精度 0.00-0.80）；语法推断侧 RPNI/k-Tails 因缺负例而爆出 10³-10⁵ 状态，Alergia 统计检验合并仍多用 1.0-6.0 倍状态。本文的定位是：用"最后活动右同余"这一确定性单趟合并，站在过程挖掘的直接跟随图与语法推断的状态合并之间，并首次把结果结构用于失败预测、下一步预测与运行时监控。

三、问题定义

3.1 从具体场景到抽象问题

具体诉求是三个看似独立的问题：Agent 下一步会干什么？这条运行会失败吗？能不能在失败早期就拦下来？作者把它们统一抽象成一个逆问题：

给定一个执行轨迹语料库，重建一台能解释这些观察行为的有限状态机（FSM），作为不可预测行为的结构基底。

FSM 是什么（给初学者）：有限状态机就是"状态 + 箭头"的图——每个圆圈是一个状态，每条箭头代表"在状态 A 时发生动作 b 就跳到状态 B"。红绿灯（绿→黄→红→绿）就是最简单的 FSM。它的全部行为规则都能画在一张图上，因此可读、可查询、可证明。

3.2 形式化

• 轨迹：τ = (m₁, …, m_T)，每条消息 mₜ 有角色与内容；
• 活动提取函数 φ：mₜ ↦ aₜ ∈ A（工具名优先，其次动作标签，再次命令首 token，兜底"角色:类型"）；
• 目标：构造确定性 FSM M = (Q, A, δ, q₀)，全部状态为接受态；
• 评估：重放适应度 fit(σ, M) = M 能消费 σ 的符号比例；语料适应度为均值。

3.3 抽象的精妙之处

作者不追求"生成自动机"（理论上不可能），只追求"直接跟随自动机"（directly-follows automaton）——记录"哪个活动之后能跟哪些活动"。这个降维打击般的让步换来了三样东西：构造确定性（无超参数）、线性时间、状态数恰为 |A|+1。放弃不可知的，精确拿到可知的——这是整篇论文的方法论灵魂。

四、问题解法

4.1 三步构造：比看上去更简单

三个理论保证（附证明）：

• 定理 2（适应度保持）：合并不丢训练适应度——每个类携带其成员转移的并集，任何树边都存活；唯一适应度损失来源是第③步，且直接被实验测量（≥0.997）；
• 定理 3（确定性与紧凑性）：|Q| = |A| + 1，输出对固定语料唯一——同一份数据任何人跑出来的 FSM 一模一样；
• 命题 5（收敛保证）：N ≥ (1/p_min)·ln(r/δ) 条轨迹后，以 1-δ 概率恢复总体自动机；对 SWE-agent 的 51 条转移只需 ≤690 条轨迹，实证 5-15% 数据即达 0.99 适应度。

构建耗时 1-110 毫秒（RPNI 要 7-36 秒），单轨迹重放 0.003-0.015 毫秒——快到可以塞进生产环境的实时监控循环。

4.2 一个 FSM 驱动四件下游任务

（1）工作流记忆 / 下一步预测：把"当前状态 + 各下一动作概率 + top-15 多步延续"作为最小上下文喂给 LLM。这里有个重要的消融：把整张 FSM 图塞给 LLM（verbose 格式）反而输给 AWM——淹没信号；最小格式才赢 12.9pp。给 LLM 的结构性记忆要"少而准"，不是"多而全"。

（2）失败预测：重放轨迹过 FSM，提取每状态特征（访问频次/消息长度/错误率/时序）+ 五个交叉熵异常特征（轨迹 CE/最大惊讶度/半程漂移/最小转移概率/高惊讶率），一个 200 棵树的梯度提升分类器出分。

（3）运行时监控：两条规则——循环率 > 0.778、唯一状态数低于阈值。失败的运行会早早陷入两状态死循环，成功的运行持续访问新状态；监控器就是盯着这个分歧，纯 FSM 重放，无任何 ML 模型。

（4）异常拒绝：FSM 拒绝 100% 随机轨迹、≥99.9% 置换轨迹——它学到的"活动顺序约束"是真实的。

五、评估指标与实验证据

5.1 数据集与主结果总览

12 个公开数据集横跨 8 个领域（编码/网页/桌面 GUI/客服/电信/安全/OS/移动 GUI），字母表 6-42 符号，80/20 切分。

压缩与适应度（8 个带标签真实数据集）：

次强对手 Alergia 适应度能持平但多用 1.0-6.0× 状态；RPNI 不仅状态爆炸，适应度还崩（0.46-0.98）——在 5 个数据集上直接超时。

四任务成绩单：

5.2 关键的受控实验设计

• 格式消融：AWM、verbose FSM、最小 FSM 三种上下文喂同一个 LLM——证明赢的是"最小格式"而非 FSM 本身自动生效；
• 裁判鲁棒性：换两个 LLM 裁判，FSM 对 AWM 的优势保持 +8.7pp 均值；
• 早预测曲线：50% 完成度时 FSM 特征已达最终 AUROC 的 92%——失败信号在半程就已充足；
• 交叉模型迁移：4 个 LLM 在 tau2-bench 上执行相同任务，单一 FSM 对每个模型重放适应度都是 1.000；失败预测特征跨模型迁移 AUROC 0.786（自身 0.877）。

5.3 这些指标为什么真能证明主张

主张是"一个结构基底统一四件事"，证明结构是同一台 FSM 同时出现在四组实验里，而不是四个定制的管线各跑各的分数。压缩比证明的不是"好看"，而是"紧凑性使每状态观察密度充足"这一机制性论断（见第六节）。

六、效果优势的根源解释

核心因果链：紧凑性 → 每状态观察密度 → 一切下游收益。

对比对象是 RPNI，它为什么曾经有效：在有正负例的经典场景里，RPNI 的状态合并有反例约束，能收出接近最小的 DFA——这是它三十年的立身之本。

它的根本局限：只有正例时，RPNI 失去"何时停止合并"的信号，把语料切成 382-59,510 个状态。状态多不是内存问题，而是统计问题：同样的观察量摊到几万个状态里，每个状态只见过零星几次转移，概率估计的方差爆炸（论文给出 O(1/√n_q) 集中界）。于是下一步预测交叉熵 3.40 bits——比"均匀猜"还差；失败预测的异常信号也随之失效。

本文方法的根本性改变：|Q| = |A| + 1 ≈ 7-43 个状态。同样两千条轨迹，每个状态聚合成百上千次访问，转移概率估计紧致。这一步改变的信息流是：每个状态都变成一个统计上可靠的"行为情境"——下一步概率可靠（工作流记忆赢）、惊讶度可靠（失败预测的交叉熵特征有效）、循环检测可靠（监控器成立）。论文证明：在成功/失败混合模型下，轨迹交叉熵差是 Neyman-Pearson 最优统计量（误差 O(1/√n_q)）——紧凑性直接把理论最优性做成了现实可用。

结构而非长度：SWE-agent 上结构特征 AUROC 0.790 vs 纯长度 0.659；成功轨迹只走 25 个状态中的 9 个（聚焦 search-edit-submit 路径），失败轨迹摊满全部 25 个（Jaccard 仅 0.206）。FSM 状态是"轨迹走到哪了"的结构摘要，同样的活动集合、不同的顺序，落在不同状态——这是平坦特征学不到的。

最小上下文为何赢 verbose：把整张图塞给 LLM，下一步信号淹没在 40+ 状态的枚举里；只给"当前状态的概率分布 + top-15 延续"，决策一目了然。这不是 FSM 的胜利，是信息剂量控制的胜利——结构记忆的价值密度取决于投放方式。

反事实推理：如果把 FSM 换成 Alergia 的自动机（状态多 1-6 倍）但用完全相同的特征管线，失败预测在 8/9 数据集上变差——证明增益来自每状态观察密度（构造的紧凑性），而非特征工程。如果去掉"最后活动"合并改用 label-aware 判别商，tau2-air 再升 0.152——说明还有余量，但默认构造已经够好。

一个意外发现的机制解释：4 个模型共享单一 FSM 适应度全 1.000、拓扑 80-92% 的转移骨干相同——因为行为拓扑由部署的 harness（系统提示+工具集+任务分布）决定，而非 LLM 决定。不同模型穿同一套制服，走出同一种队形。这解释了为什么跨模型监控不需要逐模型重训 FSM，也让"FSM 是系统级指纹"成为可能。

七、必要知识反推

7.1 领域知识层

• Agent 轨迹的格式细节：消息角色、工具调用字段、动作标签——不知道 tool_calls[].function.name 长什么样就写不出活动提取函数；
• 各基准数据集的结构：SWE-agent 的代码块命令、Mind2Web 的 [element]→ACTION 格式、pyautogui 原语——提取函数是逐数据集适配的。

7.2 方法论知识层

• 形式语言与自动机理论：DFA、右同余、Gold 定理与 Angluin 的工作——没有"正例不可识别"的共识，就不会想到"退而求直接跟随闭包"这条出路；
• 语法推断算法谱系：RPNI/EDSM/Alergia/k-Tails 各自的机制与失效模式——这是选对 baseline 并解释其失败的必要条件；
• 过程挖掘：直接跟随图、花模型、适应度-精度权衡——本文的构造在概念上就是"直接跟随图的确定性化"；
• 概率论：Neyman-Pearson 引理、集中不等式、regret 界——四个理论保证的底座。

7.3 工程知识层

• 前缀树与哈希实现：线性时间构建的工程基础；
• 梯度提升分类器 + L1 特征选择：失败预测管线的标准件；
• LLM 提示工程：最小上下文格式的设计与消融方法。

7.4 知识融合的关键节点

（1）Gold 障碍 × Agent 字母表有界：理论障碍是全局的，但 Agent 场景的特例（|A|=6-42）让"放弃完整语言、只学直接跟随闭包"变得既可行又够用——理论局限性与领域约束的碰撞产生了正确的问题让步。（2）过程挖掘的经典构造 × 语法推断的评估纪律：直接跟随图是过程挖掘 30 年的老东西，但把它放进"与 RPNI/Alergia 同台、按适应度/压缩/稳定性打分"的语法推断评估框架，才能证明这次它真的赢了。（3）紧凑性 × 统计集中：把"|Q|=O(|A|)“这个构造性质翻译成"每状态观察密度 → 估计方差 → 下游一切指标"的定量因果链，是论文从"工程技巧"升格为"科学论断"的关键一步。

八、论文中可以提取的通用性灵感

灵感一：当问题在理论上不可解时，先找领域的"有界性"特例，再做一个诚实的降级。 论文证据：Gold 定理封死"从正例学生成语言”，但 Agent 字母表只有 6-42 符号；作者不学生成自动机、只学直接跟随闭包，换来确定性、唯一性、线性时间。 推广场景：程序分析中的有界模型检测、推荐系统放弃完美偏好建模改学上下文 bandit、编译器放弃全自动优化改做超算子调度、生物学放弃全基因组预测改做基因家族——“在理论绝望的地方找工程上有界的切口"是通用科研策略。

灵感二：紧凑性不是省内存，是让统计估计变可靠。 论文证据：同样数据，7-43 状态 vs 数万状态，前者概率估计紧致（O(1/√n_q) 集中界），后者下一步预测比均匀猜还差。 推广场景：用户分群（群数超过样本支撑度时画像失真）、决策树剪枝、聚类算法的 k 选择、任何"分桶统计"场景——桶数必须与观察量匹配，否则每桶都是噪声。

灵感三：给 LLM 的结构化记忆，剂量比完整性重要。 论文证据：完整 FSM 图作为上下文输给 AWM；只给"当前状态概率+top-15 延续"赢 12.9pp。 推广场景：RAG 的检索块大小、代码补全的上下文裁剪、Copilot 类工具提示的设计、给管理层的数据看板——信息过载会淹没决策信号，最小充分统计量优于全量信息。

灵感四：行为拓扑由系统（harness）而非个体（模型）决定。 论文证据：4 个 LLM 共享单一 FSM 适应度全 1.000、转移骨干 80-92% 相同；跨模型监控无需重训。 推广场景：组织行为学（流程决定行为模式，换人不换流程则行为不变）、UI 设计（界面决定操作路径分布）、交通工程（路网拓扑决定车流模式）、审计（对系统的合规检查可比对个人更有效）——想预测/约束行为，改结构比改个体便宜得多。

灵感五：失败预测的价值在"早”，监控器要极简才能上生产线。 论文证据：50% 完成度达 92% 最终 AUROC；监控器纯 FSM 重放 0.006ms/步、零 ML 依赖、32% 处早停省 68% 算力。 推广场景：CI 流水线的快速失败门、临床试验的中期分析、自动驾驶的边际风险监测、长训练任务的 checkpoint 策略——把昂贵计算留给"确定要继续"的分支，便宜信号负责"何时喊停"。

灵感六：一个结构化中间表示可以替代多个专用管线。 论文证据：同一台 FSM 同时支撑工作流记忆、下一步预测、失败预测、运行时监控——“四个定制管线变一个结构原语”。 推广场景：数据库的统一查询计划（同一表示服务 OLAP/OLTP）、编译 IR（多语言多后端共用一层中间表示）、监控系统的统一指标模型、数字孪生——找到对的中间层，是系统设计中杠杆率最高的一步。

附录：一句话总结

把上千条杂乱无章的 Agent 执行轨迹，坍缩成一张 7-43 个状态、任何人重跑都一模一样的小图——下一步会做什么、会不会失败、要不要现在就停，从此都只是在这张图上"走到哪儿了"的查询。越紧凑，越可预测；越结构化，越可监控。