从 Agent 轨迹中提取自动机：失败与下一步预测

TL;DR 将 LLM agent 的大量轨迹压缩为紧凑 FSM（7-43 状态），利用跨运行行为拓扑同时提升 next-step 预测与故障预测，实现可审计的在线监控。

问题

问题背景

LLM-based agents 在工具调用、网页浏览、代码生成等多步任务中应用广泛，但产生的长轨迹（trace）是无结构文本流，难以进行系统性安全审计和运行时监控，而这正是部署中的关键需求。

现有方法局限

现有工作大多采用逐 trace 分析或仅利用成功轨迹，忽略了不同运行之间共享的行为拓扑，导致无法将下一步动作预测与失败预测统一到同一结构框架中。具体来说，Agent Workflow Memory (AWM) 等方法依赖外部记忆检索，没有对行为进行紧凑的归纳表示；过程挖掘或语法推断方法（如 Alergia、EDSM）往往只能处理单一轨迹或需要大量样本，且缺乏对 LLM agent 特定噪声（如文本动作提取）的鲁棒性。这些方法难以在保持高拟合度的同时提供可解释的有限状态机。

为什么这个问题难且重要

技术上，LLM 输出空间大且非平稳，行为模式受部署 harness 和工具调用影响，提取稳定跨运行结构极具挑战；而安全审计和在线监控要求模型无关、可快速构建、并能支撑下一步和失败预测。业界对可问责 AI 系统的需求日益增长，缺乏结构基板使得监控只能依赖事后分析，难以及时干预。

行业类比

类似于对分布式系统调用日志构建状态机以检测服务异常，这里将 agent 行为轨迹压缩为 FSM，使得安全团队可以像审计传统软件控制流一样审计 LLM agent。

核心洞察

• 将 agent 轨迹语料压缩为单一有限状态机 (FSM)，捕获跨运行共享的行为拓扑，作为模型无关的结构基元。与 per-trace 或仅成功轨迹的方法不同，该 FSM 同时编码成功与失败路径，揭示部署 harness 而非 LLM 主导的结构规律，为安全审计提供稳定、紧凑、可解释的抽象。
• 在 FSM-state 条件下进行下一步预测，超越了 Agent Workflow Memory 等显式记忆基线。FSM 状态是压缩的行为模式而非原始轨迹存储，既保留判别性又降低冗余，在多个数据集上以最小上下文格式取得更优精度，说明结构化抽象比记忆容量更关键。
• 每状态行为特征使失败预测 AUROC 高达 0.94，且在线 monitor 可从部分轨迹早期触发停止。这一能力源于 FSM 将跨运行拓扑与状态级统计结合，而非依赖序列学习，避免了对长程依赖建模的脆弱性，为运行时监控提供实时、可解释的判别信号。

方法

方法概览

输入：LLM 智能体执行多步任务的原始轨迹语料，每条轨迹包含观察、动作和反馈等非结构化记录。

关键模块：

1. Activity Extraction（活动提取）
   将每条原始轨迹转成离散活动标签序列，例如“查询用户信息”“调用工具”“输出结果”等。该步骤类似文本 tokenization，但面向行为语义，且对提取器选择具有鲁棒性。

2. FSM Construction（有限状态机构建）
   将整个语料的所有活动序列压缩为单个紧凑的 FSM。构建分三步：

   • 前缀树：先枚举所有出现过的子序列，形成完整前缀树；
   • 合并最后活动相同的状态：把行为上等价的状态合并，大幅减少状态数；
   • 稀有转移过滤：删除出现频率极低的边，去除噪声，得到最终 FSM（通常 7–43 个状态）。

3. Prediction via FSM State Conditioning（基于 FSM 状态的预测）
   将任意轨迹映射到当前 FSM 状态，用该状态作为上下文特征。对 next-step prediction，直接根据状态转移分布预测下一活动；对 failure prediction，从状态中提取行为特征（如停留时间、转移熵、失败占比等）训练分类器，实现在线监测。

输出：一个紧凑 FSM 以及两个下游预测器；FSM 本身可作为运行时监视器，对部分轨迹即可判断失败风险并提前停止。

差异点：相比逐轨迹分析或只考虑成功轨迹的方法，本方法从整个语料中归纳出跨运行共享的有限状态拓扑，作为模型无关的结构原语，同时支持下一步预测与失败预测。

实验

实验设计

论文在 12 个公开 agent 轨迹数据集上构建 FSM，覆盖编码（SWE-smith、SWE-agent）、网页导航（Mind2Web、WebArena）与工具交互（tau2-bench）等任务。方法流程：从原始轨迹提取活动序列，构建前缀树并按末活动合并得到紧凑 FSM，再过滤稀有转移。评估包括重放 fitness、跨分割拓扑稳定性、next-step 预测（与 Agent Workflow Memory 对比）以及基于每状态行为特征的失败预测（留出 AUROC、在线早期停止）。

关键发现

• FSM 极其紧凑（7–43 状态），重放留出数据 fitness ≥0.997，构建仅需毫秒级，且跨数据分割拓扑几乎一致。
• FSM 状态作为上下文进行 next-step 预测时，在所有 ground-truth-matched 数据集上显著优于 Agent Workflow Memory。
• 失败预测中，每状态行为特征达到留出 AUROC 最高 0.94；在线监视器能从部分轨迹将失败运行排在通过运行之上，并在完成前触发早期停止。
• 行为拓扑主要受部署 harness（环境/工具固定结构）塑造，而非 LLM 本身，说明 FSM 可作为模型无关的结构化基元。

与基线对比

相比逐轨迹或仅成功轨迹的方法，FSM 捕获跨运行拓扑，同时支撑 next-step 与失败预测两大目标。与 Agent Workflow Memory 相比，FSM 状态上下文在匹配数据上全面领先，说明结构归纳优于记忆检索。在失败预测上，FSM 特征在留出集上达到高 AUROC，且在线监视器无需完整轨迹即可判别，这对安全审计与运行时监控有直接工程价值。该方法构建成本极低，可作为 agent 部署中的轻量监控层。

行业影响

落地场景

LLM agent 在多步任务（客服、流程自动化、代码生成）中的不可预测性制约生产部署。本工作将 trace 压缩为紧凑 FSM，可作为 运行时监控 与 安全审计 的结构原语。典型 use case：

• 电商客服 agent：建模退换货、订单修改等标准流程，FSM 状态偏离时触发人工接管或重试。
• 企业服务 RPA：监控财务审批等敏感流程，发现非法状态跳转立即终止。

商业价值

• 降本：早期停止失败运行，减少 token 消耗与人工补偿；实际部署中失败任务常占大量成本。
• 增收/体验：FSM 状态增强下一步预测，提高任务成功率，缩短用户等待。
• 合规：可解释行为模型满足审计要求（如金融、医疗）。

与现有 stack 集成

• 作为轻量中间件嵌入 LangGraph / AutoGen 等框架：在每个 step 捕获 agent 动作，映射到 FSM 状态，计算风险分数。
• 构建只需毫秒级，支持在线增量更新；也可用于离线回归测试与行为漂移检测。

局限

• **Activity extraction** 的选择对 FSM 构建影响显著。虽然论文声称对提取选择鲁棒，但在真实部署中，agent 输出的活动标签可能模糊、噪声多，或需要领域专家定义。若提取粒度不当，可能导致状态爆炸或关键行为路径丢失。此外，**rare-transition filtering** 的阈值需要人工设定，可能过滤掉低频但重要的故障前兆转移，从而削弱 failure prediction 的召回率。
• FSM 是静态结构，假设行为分布稳定。但 LLM agent 常表现出非平稳性，如上下文学习、环境反馈适应或策略漂移。本文方法需要离线构建完整 FSM，无法在线更新，难以应对动态变化的任务或新出现的 agent 行为。在持续部署场景中，可能需要定期重建 FSM，增加了运维成本，并存在状态滞后风险。
• 实验基于 12 个公开数据集，任务类型偏向 web 导航、代码生成等，且行为拓扑主要由部署 harness 决定，这意味着方法可能对特定 harness 过拟合，跨 harness 或跨领域迁移性存疑。同时，next-step prediction 仅与 **Agent Workflow Memory** 比较，缺乏与更强神经序列模型（如 Transformer 基线）的对比，难以全面评估其竞争力。failure prediction 的 AUROC 虽达 0.94，但未分析不同 failure 类型的细粒度表现。