从智能体轨迹提取自动机：失败与下一步预测 Automata from Agent Traces: Failure and Next-Step Prediction
用无超参方法把智能体轨迹压成小型FSM，统一支撑下一步预测、失败预测与运行时监控
前置知识
有限状态机（FSM/DFA）
由状态集合 $Q$、字母表 $A$、转移函数 $\delta: Q\times A\to Q$、初始状态 $q_0$ 组成的计算模型；确定性指每个（状态，符号）对至多一个后继。本文把每个状态定义为“最近一次活动”，消息轨迹经活动抽取函数映射成符号序列 $\sigma(\tau)$ 后即可被该自动机逐符号重放或拒绝。
论文的全部贡献——压缩、下一步预测、失败预测、运行时监控——都建立在这台从轨迹中重建的紧凑 FSM 之上，不理解 FSM 就无法理解方法本体。
重放 fitness
把测试轨迹的符号序列喂进自动机，统计能被走通的符号比例 $fit(\sigma,M)=k/T$，再对语料取平均 $Fit(D,M)=\frac{1}{|D|}\sum_\tau fit(\sigma(\tau),M)$。它衡量模型对行为序列的解释覆盖度，是自动机抽取质量的第一个硬指标。
本文报告所有数据集测试重放 fitness $\ge 0.997$，并用它证明压缩没有牺牲保真度；几乎所有对比表格都以此列为主线。
只用正例的语法推断（Gold 定理、RPNI/Alergia）
从正例样本学习正则语言在极限意义下不可辨识（Gold 1967）。经典算法中 RPNI/EDSM 依赖负例或反例预言机，k-Tails 需要超参数 $k$，Alergia 用统计兼容性检验做状态合并。智能体轨迹只有成功/失败的执行记录，天然是只含正例的语料，这构成了本文问题的理论难点。
理解这一不可能性结果，才能明白作者的贡献不是又一个合并启发式，而是论证“小字母表 + 确定性设计”可以绕开该障碍并给出样本复杂度界。
直接跟随图与过程挖掘
过程挖掘（van der Aalst）从事件日志恢复流程模型，其中直接跟随结构记录“活动 $a$ 之后紧跟活动 $b$”的频率。标准挖掘器（Alpha/Inductive/Heuristic）在智能体轨迹上过度宽松，产生接受一切顺序的“花朵模型”，精度仅 0.00–0.80。
本文证明“按进入边活动合并前缀树”恰好得到确定化的直接跟随自动机——方法在数学上就是过程挖掘直接跟随图加一个右同余商，了解这一脉络才能看清它在文献中的位置。
交叉熵（CE）与逐状态转移估计
预测器对序列的编码代价 $CE=-\frac{1}{T}\sum_t \log_2 \hat P(a_t\mid \text{context})$，单位 bit，越低越好。本文在 FSM 状态 $q_t$ 上用 Laplace 平滑计数估计 $\hat P(a\mid q)=\frac{C(q,a)+\alpha}{\sum_{a'}C(q,a')+\alpha|A|}$，并可用 PPM 混合多阶上下文。
下一步预测实验的统一指标；FSM 状态条件化带来的 CE 下降（+0.155 bit，21%）是“状态包含信息”的直接证据。
AUROC 与 Neyman–Pearson 检验
ROC 曲线下面积，衡量成功/失败二分类在不设阈值时的排序质量：0.5 为随机，1.0 为完美。Neyman–Pearson 引理指出似然比是最优检验统计量；论文证明 FSM 惊异差 $CE_-(\tau)-CE_+(\tau)$ 正是这样的统计量（误差 $O(1/\sqrt{n_q})$）。
失败预测（最高 AUROC 0.941）与在线监控（rank-AUROC 0.66）实验的核心指标，理论保证也全部用这套语言陈述。
研究动机
LLM 智能体在 ReAct 范式下交替进行思维链推理与工具调用，产生动辄几十到上千条消息的执行轨迹：编码智能体在 search→edit→execute 之间循环，客服智能体在数据库查询与用户沟通之间切换。这种结构隐含在系统提示、工具集与任务分布的交互中，但从未被显式刻画，导致长而无结构的轨迹难以支撑部署所需的安全审计、瓶颈状态调试与生产行为漂移监控。现有方法各管一段：AgentSpec、ShieldAgent 等需要手工安全策略；AgentMonitor 用扁平 XGBoost 逐轨迹预测；Agent Workflow Memory 只从成功轨迹抽线性工作流，无法表达循环与分支，在低成功率数据集上覆盖率崩塌（SWE-smith 仅 74.7%、tau2-telecom 仅 28.5%）；过程挖掘标准算法在智能体轨迹上产生精度 0.00–0.80 的“花朵模型”；RPNI 等经典语法推断在只给正例时产生 $10^3$–$10^5$ 状态的过拟合自动机（SWE-agent 上 59,510 状态且 fitness 只有 0.646），而 Gold 定理又从理论上说明仅凭正例无法在极限意义下识别目标语言。更麻烦的是这些方法互不兼容：工作流记忆、异常检测、失败预测各需一条定制流水线。
本文的目标是本文把“从轨迹语料恢复行为结构”形式化为一个逆问题：给定一批执行轨迹 $D=\{\tau_1,\dots,\tau_N\}$，重建一台紧凑、可解释、确定性的有限状态机 $M=(Q,A,\delta,q_0)$，使其既高保真地重放训练与测试数据（测试重放 fitness $\ge 0.997$），又能同时充当四类下游任务的共享结构基座——压缩表示、给 LLM 的工作流记忆（提升下一步动作预测）、逐状态特征化的失败预测、以及带 sub-linear regret 保证的在线失败监控与早停。作者希望整条流水线无需学习超参数、在毫秒级完成构建（单 CPU 核 1–110 ms）、对活动抽取粒度的选择稳健，从而用一个结构原语替代四条定制管道，服务于安全审计与运行时监控。
与已有工作不同的是，独特切入角度有三层。其一，问题重构：作者观察到智能体行为由有界工具集生成，活动字母表天然很小（12 个数据集上仅 6–42 个符号），这使“正例不可辨识”的 Gold 障碍在实践中失效——紧凑状态空间保证了每状态的观测密度，估计才是良定义的。其二，方法上不做任何启发式或统计合并：直接按“进入边的活动”这一右同余 $q\sim q'\iff \kappa(q)=\kappa(q')$ 合并前缀树，一步得到确定化的直接跟随自动机，并配套证明其保 fitness、确定性、唯一性与样本复杂度界。其三，视角上的关键发现是“拓扑由部署脚手架而非 LLM 决定”：tau2-bench 上 4 个不同聊天模型（GPT-4.1、Claude 3.7 Sonnet、GPT-4.1-mini、o4-mini）的轨迹能被同一台 FSM 以 1.000 fitness 完美重放，且失败预测特征跨模型迁移 AUROC 达 0.786（自模型 0.877）。这把 FSM 从又一个异常分数提升为模型无关的结构原语。
核心方法
直觉上，无论智能体多复杂，它每一步只能从有限动作/工具集中选择，因此轨迹的活动序列高度重复、条件熵极低——从 0 阶到 1 阶条件熵下降 51–80%，这正是小型自动机可行的统计前提。技术路线分四步：第一步定义活动抽取函数 $\phi$，把每条消息映射为符号，优先级为工具调用名 > [ACTION] 标签 > 代码块首命令（归入 search/edit/execute 等语义类）> 兜底的 role:content-type（如 assistant:text）；第二步把所有活动序列插入前缀树，此时训练 fitness 完美但状态数达 $O(\sum_i T_i)$；第三步按进入边活动的右同余合并 trie 状态，得到恰好 $|A|+1$ 个状态的确定性直接跟随自动机，循环自然出现在活动递归处（如工具调用的 a:tc↔tool 环）；第四步过滤只在语料中出现恰好一次的转移（除非它是源状态唯一出路），这是唯一可能损失 fitness 的步骤。整体复杂度对语料规模线性，12 个数据集全部在单核 110 ms 内构建完成，无任何学习超参数。
核心创新是把“最近一次活动”当作状态抽象：活动计数相同但顺序不同的两条轨迹会落入不同状态，因此 FSM 编码的是轮转与工具调用约束而非词袋统计。与已有方法的本质区别有四：(1) 相对 AWM、Reflexion、ReasoningBank 等无结构记忆方法，本文产出带状态抽象的结构模型，能表达循环与分支，并同时利用成功与失败轨迹；(2) 相对 RPNI/EDSM/k-Tails 等经典语法推断，本文不做负例依赖或统计合并，而用单个确定性设计选择（末活动合并）实现 15–3,036 倍压缩且零超参数，固定语料输出唯一；(3) 相对 PrefixGuard 等监控专用构造，同一台 FSM 同时驱动压缩、下一步预测与失败预测，而非单一异常分数；(4) 相对过程挖掘的宽松花朵模型，直接跟随自动机是确定性的、高精度的。理论配套完整：fitness 保持（Theorem 2）、确定性/紧凑性/唯一性（Theorem 3）、样本复杂度 $N\ge \frac{1}{p_{\min}}\ln\frac{r}{\delta_f}$（Proposition 5）、逐状态估计集中性（Proposition 6）、惊异差的 Neyman–Pearson 最优性（Corollary 7）、在线监控 $O(\sqrt{T\log|Q|})$ regret（Proposition 8）。
方法步骤详情
第一步，活动抽取：对每条消息 $m$ 按优先级应用三条规则得到符号 $a=\phi(m)$——消息含工具调用字段则取函数名；含 [ACTION] 描述则取动作标签；代码块则取首命令并归入 search/navigate/edit/execute/submit 等 7 个语义类；都不匹配则退化为 role:content-type。输入原始消息轨迹，输出符号序列 $\sigma(\tau)=(\phi(m_1),\dots,\phi(m_T))$。第二步，构建前缀树：逐条插入符号序列，每个唯一前缀是一个状态，训练重放 fitness 为 1 但状态数可达 $O(\sum_i T_i)$。第三步，末活动合并：把进入边活动相同的 trie 状态归为一类（共 $|A|+1$ 类），对每条 trie 边 $q\xrightarrow{a}q'$ 聚合出类级转移 $\kappa(q)\xrightarrow{a}\kappa(q')$，一遍遍历即得直接跟随自动机。第四步，稀有转移过滤：删除聚合计数恰为 1 的转移（除非它是源状态的唯一延续），只删边不删状态。第五步，推理与应用：测试轨迹按转移重放得 $fit(\sigma,M)=k/T$；当前状态 $q_t=\delta^*(q_0,a_1\dots a_{t-1})$ 上的转移计数经平滑给出 $\hat P(a\mid q_t)$，PPM 变体可混合多阶上下文；逐状态访问频率、消息长度、错误率加上 5 个 FSM 交叉熵惊异特征喂给 200 棵深度 3 的梯度提升树做失败预测；运行时监控用 cycle-rate>0.778 与唯一状态数（带 warm-up）两条规则触发早停。
技术新颖性
技术新颖性在于“用可证明的平凡换可靠性”。算法本身是经典的——作者自承与 Daciuk 等人 2000 年的增量构造、Hopcroft 教科书同源，真正新的是设定与整套保证：证明了末活动合并保持训练 fitness（Theorem 2，合并只加边不删边，商序列 $[q_0],[q_1],\dots,[q_T]$ 仍被接受）；产出恰好 $|A|+1$ 状态、对语料唯一的确定性自动机（Theorem 3，类映射与边集都只是训练转移多重集的函数）；恢复总体直接跟随自动机只需 $N\ge \frac{1}{p_{\min}}\ln\frac{r}{\delta_f}$ 条轨迹（SWE-agent 的 $k=51$ 个转移、$p_{\min}\approx 0.01$、$\delta=0.05$ 时上界 690 条，而实测 5–15% 训练数据即收敛）；逐状态转移估计的 TV 集中界（Proposition 6）；成功/失败混合模型下惊异差是 Neyman–Pearson 最优统计量（Corollary 7）；以及在线阈值监控的 $O(\sqrt{T\log|Q|})$ sub-linear regret（Proposition 8）——RPNI 的 $10^3$–$10^5$ 状态会同时膨胀两项。系统层面，把同一结构原语贯穿压缩、工作流记忆、失败预测、监控四个任务，以及发现“最小上下文格式”与模型同等重要（ASG-minimal 65.1% vs ASG-full 52.2%），都是以往工作没有的贡献。
实验结果
结果分四条线。压缩与保真：12 个公开数据集上 FSM 仅 7–43 个状态，测试重放 fitness $\ge 0.997$，对 RPNI 压缩 15 倍（WebArena）到 3,036 倍（GUI-Odyssey，RPNI 21,255 状态且超时）；Alergia 是最强正例基线但需 1.0–6.0 倍状态，k-Tails 多 1.4–10 倍且 $k\ge 2$ 时爆到 1,085 状态，EDSM 无负例退化为 1 状态，HMM 状态数相当但状态不可解释，过程挖掘精度仅 0.00–0.80。构建耗时 1–110 ms，比 RPNI（7–36 s）快 328–10,611 倍；fitness 在 5–15% 训练数据处即达 0.99（SWE-agent 2,000 条中 240 条）。精度：FSM 拒绝 100% 随机轨迹与 ≥99.9% 置换轨迹，而 RPNI 在 WebArena 接受 75% 的置换轨迹。下一步预测：order-1 Markov 平均 CE 0.934 bit，比 Unigram 2.439 降 62%，且该一步状态条件化解释了各数据集总提升的 83–99%；受控消融中 FSM 状态条件化净贡献 +0.155 bit（21%），FSM-LR-K7 以 0.729 bit 最优，RPNI 3.397 bit 竟比均匀分布还差。FSM 作为 LLM 上下文在全部 8 个数据集胜过 AWM（+0.8 到 +25.3pp，6/8 显著性 $p<10^{-8}$；统计评测下 SWE-smith 100% vs 34.5%，tau2-telecom 61.8% vs 19.8%），上下文格式消融显示最小格式 65.1% 显著优于全图格式 52.2%。失败预测：逐状态特征 held-out AUROC 最高 0.941（tau2-telecom，43 状态），WebArena 0.903、AgentNet 0.890、ATBench 0.894、SWE-agent 0.799，而 raw fitness $\approx 0.50$ 无信息、长度基线仅 0.659；FSM 特征在 20/21 个数据集×架构对上提升 MLP/GRU/Transformer。运行时监控：25% 进度处 rank-AUROC 0.66（flag-everything 为 0.5），SWE-agent 在 32% 完成度触发早停（精度 85.9%、召回 95.5%、节省 68% 剩余算力），高精度操作点（cycle-rate>0.957）下达 100% 精度、11.3% 召回；OOD 跨数据集重放 AUROC 1.000。跨模型：单一 FSM 对 4 个模型各自 1.000 fitness（共享 80–92% 转移主干），失败特征 36 个跨模型对平均 AUROC 0.786 vs 自身 0.877。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 自动机抽取/压缩（12 个公开数据集） | 状态数 $|Q|$ 与测试重放 fitness | 7–43 状态，fitness ≥0.997，确定性且无超参数 | RPNI：382–63,897 状态，fitness 0.491–1.000（多处 120s 超时）；Alergia 需 1.0–6.0× 状态 | 15–3,036× 状态压缩且保真更高 |
| 构建效率 | 单 CPU 核构建时间 | 1–110 ms（逐轨迹重放 0.003–0.015 ms） | RPNI 7,000–36,000 ms | 328–10,611× 提速，可实时监控生产系统 |
| 下一步预测（5 数据集，5×5 折 CV） | 交叉熵（bits，越低越好） | 纯 FSM（1 阶 Markov）平均 0.934；FSM-LR-K7 最优 0.729 | Unigram 2.439；RPNI 3.397（比均匀分布差） | 纯 FSM 相对 Unigram 降 62%；状态条件化净贡献 +0.155 bit（21%） |
| FSM 作为 LLM 工作流记忆（8 数据集） | gpt-4.1-mini 判定 top-1 准确率 (%) | 全部 8 数据集胜出：SWE-smith 100.0、WebArena 81.2、OSWorld 70.7 | Agent Workflow Memory：SWE-smith 74.7、WebArena 65.5、OSWorld 55.0 | +0.8 至 +25.3pp，6/8 数据集 p<10⁻⁸ |
| 失败预测（9 个带标注数据集） | held-out AUROC（80/20 划分） | 最高 0.941（tau2-telecom）；ATBench 0.894（安全基准，CV 0.864±0.024） | raw fitness ≈0.50；长度基线 0.659（SWE-agent） | 在 20/21 个数据集×架构对上超越匹配的 MLP/GRU/Transformer 序列特征 |
| 在线早停监控（SWE-agent / tau2-airline） | 触发完成度、精度、召回、节省算力 | 32% 完成度触发（56% on tau2-air），精度 85.9%、召回 95.5%，节省 68% 剩余算力；rank-AUROC 0.66 | flag-everything（rank-AUROC 恒为 0.5；F1 0.914 但无法给出时机） | 在部分轨迹上即可把失败运行排到成功运行之上 |
局限与改进
作者承认的局限：(1) FSM 接受的是观测轨迹的直接跟随闭包而非智能体的生成语言，保持活动 bigram 统计的对抗性轨迹可以完美重放，因此不能作为唯一防线；(2) 活动抽取函数 $\phi$ 依赖少量数据集特定的领域知识，虽在粒度上稳健（12 数据集中 10 个上默认粒度不差于 role-only）但仍非全自动；(3) 收敛保证的 i.i.d. 假设只是近似——实际轨迹来自固定任务分布上的迭代部署；(4) 对动作空间很大或条件结构弱的智能体，紧凑性与逐状态观测密度都会退化，下游收益随之消失。我的补充观察：(1) 失败率极高的数据集上 F1 被基率主导——SWE-agent 84.3% 失败率下 flag-everything 的 F1=0.914 反而高于监控器的 0.904，作者改用 rank-AUROC 和精度/召回补救，读者对比其他文献时需小心指标口径；(2) 跨模型迁移有 0.091 的 AUROC 缺口（最差的 o4-mini→Claude 3.7 在 airline 上低至 0.560、retail 0.544），说明部分失败模式确实是模型特异的，“模型无关”结论主要适用于拓扑层面；(3) 失败预测绝对水平并不均匀，SWE-agent 仅 0.799，距可单独依赖的监控还有距离；(4) tau2 airline↔retail 因共享 schema 导致 OOD 检测近 1.0 重放，暴露了分布外检测在任务同构时的边界。
独立分析的弱点
第一，对抗鲁棒性：直接跟随闭包只约束相邻活动对，攻击者可以构造保 bigram、乱全局顺序的轨迹绕过重放与惊异检测，而安全场景恰恰要防这类规避；改进方向是引入更高阶结构（$k>2$ 的上下文）、路径级指纹（对 top-k 常见路径的偏离度量），或与形式化策略层（AgentSpec 的 PCTL 可达性过滤）组合成纵深防御。第二，抽取函数 $\phi$ 依赖人工规则，每接一个新框架新格式都要重写；改进方向是用 LLM 少样本自动提议候选 $\phi$ 并以重放 fitness + 精度双指标自动验证，或学习字符级符号化器并把粒度鲁棒性作为正则。第三，二值成功标签掩盖了失败的位置与类型：逐状态特征能定位“哪个状态出问题”，但文章没有系统评估故障归因能力；改进方向是把逐状态 KL/访问偏差聚合成带置信度的状态排名，与 Who&When 式多智能体归因基准对接。第四，监控阈值看似通用实为数据集上调出的常数（cycle-rate 0.778），部署分布漂移时可能失效；改进方向是利用 Corollary 7 的似然比统计量配合 conformal 校准，给出分布无关的误报率保证。第五，非平稳性：模型更新或提示改动都会改变转移概率，需要轻量的拓扑漂移检测与 FSM 增量重建协议，而当前构建是一次性批处理。
未来方向
作者明确列出的方向：$\phi$ 的全自动化发现；更广的跨架构、跨域迁移评测；与 ReasoningBank 这类同时利用成功与失败轨迹的记忆方法对比；大动作空间智能体上紧凑性退化的系统研究。基于本文成果可自然延伸的：(1) 把 FSM 作为约束解码或规划先验，用 $\hat P(a\mid q)$ 引导智能体搜索、对低概率跳跃动作触发二次确认；(2) 多智能体系统建模——把 Who&When 式委派失败表示为多个 FSM 的乘积自动机，定位“哪个智能体在哪个状态失联”；(3) 与形式化验证结合，把逐状态危险谓词编译成 PCTL 公式做模型检测，让监控从统计阈值升级为可验证规约；(4) 以瓶颈状态（高失败率状态）为信号做奖励塑形或课程学习，反哺智能体微调；(5) 增量式、概念漂移感知的在线重建，把毫秒级构建变成生产级持续监控闭环；(6) 把跨模型不变拓扑用作新模型的“行为规范契约”，新模型上线即插即测、无需重训练监控器。
复现评估
复现门槛在同类论文中属于最低一档。方法本身确定性、零学习超参数、固定语料输出唯一，单 CPU 核 1–110 ms 即可完成 12 个数据集的全部构建，完全不需要 GPU；核心算法（前缀树 + 末活动合并 + 计数过滤）几十行代码可实现，附录 A.1 给出完整伪代码，A.2 给出全部证明，B.1 逐一说明每个数据集的活动抽取规则与字母表（6–42 符号）。数据全部来自公开基准：SWE-agent/SWE-smith、WebArena、AgentNet/OpenCUA、tau2-bench（4 模型）、ATBench、OSWorld、Mind2Web、GUI-Odyssey、Who&When，且采样量明确（如 SWE-agent 2,000 条、WebArena 8,337 条）。失败预测只用到 200 棵深度 3 的梯度提升树，预测基线是 n-gram/逻辑回归/ESN 级别的小模型，算力需求可忽略。注意点：这是 ICML 2026 AIWIND workshop 论文，文中未给出开源代码仓库链接，所有结果需按附录自行实现；AWM 对比使用其 published 默认上下文格式，严格复现需对齐该实现；抽取规则的数据集特定性意味着换新智能体需重写 $\phi$ 并重验粒度稳健性（附录 G.2 提供了验证协议）。
论文图表
