基于智能体轨迹的自动机：故障与下一步预测

# 基于智能体轨迹的自动机：故障与下一步预测  
来源：https://arxiv.org/html/2608.23670  

Franklin Cardenoso Fernandez  
隶属机构：Holistic AI  
隶属机构：PUC\-Rio  

Umar Mohammed  
隶属机构：Holistic AI  

Zekun Wu  
隶属机构：伦敦大学学院  

Kleyton Da Costa  
隶属机构：伦敦大学学院  

Ilham Wicaksono  
隶属机构：Holistic AI  

Adriano Koshiyama  
隶属机构：伦敦大学学院  

###### 摘要  
基于大语言模型的智能体执行多步骤任务，但其行为结构仍不透明：冗长的非结构化轨迹难以满足部署所需的安全审计和运行时监控需求。现有方法要么逐轨迹处理，要么仅关注成功轨迹，因此忽略了连接*下一步*与*故障*预测的跨运行拓扑结构。为恢复这种共享结构，我们将整个轨迹语料库整合为一个紧凑的有限状态机（FSM），为LLM智能体原本难以预测的行为提供结构基底。在12个公开数据集上，FSM展现紧凑性（7–43个状态），以≥0.997的适应度重放留出数据，且在不同分割中拓扑结构近乎一致，构建仅需毫秒。该基底同时解决两项预测目标：对于*下一步预测*，FSM状态上下文在所有真实匹配数据集上均优于智能体工作流记忆；对于*故障预测*，基于状态的行为特征在留出数据上AUROC最高达0.94，并且在线监控器能从部分轨迹中将失败运行排序在成功运行之上，在任务完成前较早触发早期停止。因此，行为拓扑似乎更多受部署框架而非LLM塑造，为安全审计和运行时监控提供了模型无关的结构原语。  

###### 关键词：  
LLM智能体、智能体监控、故障预测、有限状态机  

## 1 引言  
随着基于LLM的智能体（Wang等，2024；Sumers等，2024）承担更长的推理链和更广泛的动作空间，未检测故障的风险随其自主性扩展。这些智能体现在能解决GitHub问题（Yang等，2024；Yang等，2025）、浏览网站（Deng等，2023；Zhou等，2024；Koh等，2024）、操作桌面环境（Xie等，2024；Wang等，2025c）、管理客户服务交互（Yao等，22025）并协调多智能体流程（Wu等，2024a；Hong等，2024）。遵循ReAct范式（Yao等，2023），它们交替进行思维链推理（Wei等，2022）与工具调用（Schick等，2023），生成行为结构隐含的执行轨迹。例如编码智能体循环执行搜索→编辑→执行，客服智能体则在数据库查询与用户通信间切换。这种结构源于系统提示、可用工具与任务分布的相互作用，却未在任何地方显式说明。  

理解这种潜在结构对安全审计（Zhang等，2025a；Ruan等，2024；Chen等，2025）、调试瓶颈状态（Zhang等，2025c；Cemri等，2025）以及监控生产环境中的行为漂移（Wang等，2025a）至关重要。然而当前方法在单个轨迹层面运作，需要任务描述、手动指定或成功过滤器（Zhang等，2025d；Wu等，2024b；Wang等，2025d）。  

我们将行为恢复视为逆问题：给定执行轨迹语料库，重构一个解释观测行为的有限状态机。智能体轨迹仅提供金标准意义上的正例（Gold，1967；Angluin，1980），且仅从正例识别目标语言在极限情况下不可能。我们关键观察在于：智能体行为由有限工具集与动作生成，产生的轨迹具有小型活动字母表（6–42个符号）。这种行为拓扑似乎更多受*系统*而非LLM塑造：在tau2‑bench的4个聊天模型上，单个FSM在所有模型上均达到完美适应度。这种结构约束使问题可解：通过最后活动合并的前缀树可在单次线性时间遍历中生成紧凑的直接跟随FSM，无需学习超参数（唯一设计选择是活动提取函数，其鲁棒性见附录G.2验证）。  

我们在12个公开数据集上评估（表5），与来自自动机学习（RPNI、EDSM、Alergia、k‑Tails）、隐马尔可夫模型、流程挖掘和工作流提取的9个基线对比（§2）：  
- •**工作流记忆**。FSM状态上下文在8/8个数据集上优于智能体工作流记忆（Wang等，2025d）（6项统计显著性p<10⁻⁸；表4）。  
- •**下一步预测**。FSM状态条件使交叉熵比无状态同等方法降低0.155比特（21%）。  
- •**故障预测**。基于状态的特征在留出数据上AUROC最高达0.94，在21组对比中提升MLP/GRU/Transformer基线，并为基于前缀的监控器提供动力，使其在25%检查点将失败SWE‑agent运行排序高于成功运行（rank‑AUROC 0.66 vs 标记全部为0.5），并在32%完成度时触发早期停止。  
- •**压缩**。相比RPNI，状态数减少15–3,036倍，且在≥0.997适应度下通过确定性无超参数构建实现。  

这些结果由一个对象统一：有限的LLM智能体字母表使生成的紧凑确定性有限自动机既小巧又具统计信息量，且同一FSM统一了工作流记忆、下一步预测、故障预测和运行时监控（定理与命题见§3.4）。  

## 2 相关工作  
##### 智能体安全与监控。  
AgentSpec（Wang等，2025a）和ShieldAgent（Chen等，2025）执行安全策略；AgentMonitor（Chan等，2024）使用扁平XGBoost模型从步骤级特征预测任务性能。ProbGuard（Wang等，2025b）从轨迹学习离散时间马尔可夫链并应用有界时域PCTL可达性进行运行时安全过滤；在我们的数据集上直接对比（附录G.6）其平均AUROC落后我们的FSM特征0.176，因其在没有手工不安全谓词时符号状态抽象退化为活动级粒度。同期轨迹异常检测器（Liu等，2025；Deshpande等，2025；He等，2025）通过层次化、行为或图管道针对相同问题；我们的FSM差异在于提供兼具工作流记忆和下一步预测功能的紧凑结构商，而非仅异常分数。最接近的是同期PrefixGuard（Huang等，2026），它同样从LLM智能体轨迹提取DFA用于在线故障预警监控；我们视该紧凑自动机为同时驱动压缩、下一步预测和工作流记忆的基底，而非仅监控构建。Cemri等（2025）从1,600+轨迹中分类多智能体故障模式，为自动检测提供动机。这些方法要么需要手工策略，要么缺乏结构化行为模型。我们的FSM提供可学习的结构模型，支持组合查询与从部分轨迹的早期故障预测。  

##### 智能体行为抽象。  
智能体工作流记忆（Wang等，2025d）从成功轨迹提取线性工作流模式，而Reflexion（Shinn等，2023）和ETO（Song等，2024）通过语言反思或对比对从失败中学习。ReasoningBank（Ouyang等，2025）在AWM基础上扩展成功与失败轨迹。这些方法均未产生具有状态抽象的结构模型。在FSM方面，AFlow（Zhang等，2025b）通过MCTS搜索工作流，MetaAgent（Zhang等，2025d）从任务描述自顶向下构建FSM，StateFlow（Wu等，2024b）依赖手动指定。我们的方法从原始轨迹自底向上恢复FSM，兼具紧凑结构商与故障预测的基于状态分解。  

##### 流程挖掘。  
流程发现（van der Aalst，2016）从事件日志恢复Petri网。应用于智能体轨迹时，标准挖掘器产生精度0.00–0.80的“花模型”（表20），在约束工作流上精度最高（Berti等，2024a；Berti等，2024b）。我们的自动机是通过最后活动右等价关系确定化的直接跟随图（van der Aalst，2016）；最接近的学习变体是通过语法推断的随机直接跟随发现（Alkhammash等，2024），其为业务流程事件日志调整健全性目标，而我们使用单次确定性遍历并保证收敛性，将结果应用于LLM智能体故障预测、下一步预测与监控。  

##### 语法推断。  
从正例学习有限自动机在极限情况下不可能（Gold，1967；Angluin，1980）。RPNI（Oncina和García，1992）、EDSM（Lang等，1998）和L*（Angluin，1987）需要轨迹分析中不可用的负例或预言机。k‑Tails（Biermann和Feldman，1972）合并具有相同k长度未来的状态，但需要超参数且产生的状态数比我们多1.4–10倍且适应度更低。在仅正例方法中，Alergia（Carrasco和Oncina，1994）是最强竞争者：它通过统计检验以1.0–6.0倍更多状态匹配我们的适应度。隐马尔可夫模型（Rabiner，1989）状态数匹配但产生不可解释的隐状态。我们的方法利用有限活动字母表（6–42个符号）生成紧凑、可解释的FSM（7–43个状态）且无需超参数。  

## 3 方法  
### 3.1 问题形式化  
智能体执行轨迹是消息序列τ=(m₁,m₂,...,m_T)，其中每条消息m_t具有角色（系统、用户、助手、工具）和内容。活动提取函数φ:m_t↦a_t∈A将每条消息映射到有限字母表A中的符号。活动序列为σ(τ)=(φ(m₁),...,φ(m_T))。给定语料库D={τ₁,...,τ_N}，我们构建一个有限状态机M=(Q,A,δ,q₀,Q)，包含状态集Q、部分转移函数δ:Q×A→Q和初始状态q₀；所有状态均为接受状态。转移函数是确定性的：每个（状态，活动）对映射至多一个后继。  

###### 定义1（重放适应度）。  
对于序列σ=(a₁,...,a_T)，令k为从q₀重放σ时被M消耗的符号数（δ(q,a_t)有定义的步骤）。重放适应度为fit(σ,M)=k/T。语料库适应度为Fit(D,M)=1/|D| Σ_{τ∈D} fit(σ(τ),M)。  

### 3.2 活动提取  
智能体轨迹格式多样。我们按优先级应用三条提取规则：  
（1）工具调用：若消息包含tool_call字段，活动为函数名；  
（2）动作标签：若内容包含[ACTION]描述，活动为动作标签；  
（3）命令提取：对于使用代码块的智能体，提取首个命令令牌并映射至语义类别。  
若无规则匹配，默认活动为role:content_type（如assistant:text）。提取是确定性的且与格式相关；附录B.1详述各数据集细节。  

##### 对提取选择的鲁棒性。  
下游管道对此选择稳健：跨提取粒度，重放适应度在所有数据集上保持≥0.999，故障预测AUROC在有意义水平间稳定：在全部12个数据集上，默认（角色‑类型）在10项上匹配或超越仅角色粗粒度级别，仅在仅角色退化为≤3符号字母表时有所提升（附录G.2），因此上述规则是有效设置之一而非唯一。  

### 3.3 FSM构建  
给定活动序列{σ(τ_i)}_{i=1}^N，构建分三步进行（算法A.1，附录A.1）。  

##### 步骤1：前缀树构建。  
将每个轨迹σ(τ_i)=(a₁,...,a_T)作为字符串插入Trie树，树中每条边标记一个活动，每个节点表示从根到该节点的活动序列。Trie在所有轨迹上构建，合并公共前缀。  

##### 步骤2：最后活动合并。  
为生成直接跟随FSM，按节点最后活动分组Trie节点。设组G_a为以活动a结尾的节点集合。定义状态集Q={G_a | a∈A}，初始状态q₀=G_φ(∅)（虚拟起始活动对应的组）。转移函数δ定义为：对于状态G_a和活动b，δ(G_a,b)=G_b若存在节点n∈G_a且其以活动b的子节点；否则δ未定义。  

##### 步骤3：可选精简。  
合并具有相同后续状态集的等价组（如需要）。该过程确保FSM在单次遍历中确定性构建，无需迭代合并或概率估计。  

### 3.4 理论性质  
**定理1（收敛性）**。对于任意轨迹语料库D，步骤1‑3构建的FSM在|D|→∞时收敛至行为覆盖自动机，满足重放适应度≥1-ε，其中ε为小常数。  

**命题1（紧凑性）**。若字母表大小为|A|且最大轨迹长度为L，则构建的FSM状态数|Q|≤min(|A|+1, |D|)。  

**命题2（下一步预测）**。设p_M(a_{t+1}|q)为从状态q出发活动a_{t+1}的最大似然估计。对于平稳过程，交叉熵H(p_true, p_M)≤H(p_true, p_uniform)-log|Q|。  

这些性质确保FSM在实践中既紧凑又具信息量，为预测任务提供结构基础。  

### 3.5 预测任务  
##### 下一步预测。  
给定状态q，预测分布p_M(a|q)。评估指标为交叉熵损失在测试轨迹上的平均值。  

##### 故障预测。  
为每个状态q提取特征向量f(q)，包含历史成功/失败率、进入该状态的轨迹比例等。训练二元分类器区分失败与成功轨迹。监控器从部分轨迹提取当前状态并输出故障概率分数。评估指标为AUROC及早期停止时间（当故障分数超过阈值时）。  

##### 工作流记忆。  
将FSM状态序列视为工作流模式库。对于新轨迹，匹配最长状态子序列作为上下文。  

这些任务共享同一FSM基底，展示其作为统一结构表示的效用。  

（注：因篇幅限制，后续章节参考文献及实验细节请见原文。）