Automata from Agent Traces: Failure and Next-Step Prediction¶

会议: NeurIPS 2026
arXiv: 2608.23670
OpenReview: https://openreview.net/forum?id=taEDHOLbwW
论文: https://arxiv.org/abs/2608.23670
领域: LLM Agent
关键词: LLM Agent, 有限状态机, 运行时监控, 失败预测, 下一步预测

一句话总结¶

本文提出将大语言模型智能体的无结构执行轨迹在毫秒级内折叠为紧凑的有限状态机（7–43 个状态），以此作为统一的结构化基底，在无需超参数的情况下同时实现高保真下一步预测、零样本与高精度早期失败监控。

研究背景与动机¶

基于大语言模型的自主智能体在软件工程、网页导航与多智能体协作等长程决策任务中展现出强大能力，但其行为结构的不透明性给实际部署带来了严重的安全性与可控性隐患。现有智能体执行轨迹通常是交织着思维链与工具调用的非结构化长序列，开发人员既难以进行形式化的安全审计，也无法在运行时高效预警潜在的陷入循环或执行失败。

解决该问题的核心阻碍在于智能体行为模式的表征范式：现有方案要么局限于单条轨迹的局部 prompt 分析或离线自省，要么仅从成功轨迹中抽取线性的工作流记忆，忽略了跨越不同运行的全局行为拓扑；传统形式化语法推断（如 RPNI、k-Tails）在无反例的纯正样本环境下容易退化为包含数万节点的巨大前缀树，而在实际运行中基于黑盒神经网络的状态建模又缺乏物理可解释性。

面对上述困境，本文发现智能体受限于系统提示词与固定工具集合，其底层行为符号表极其受限（仅 6–42 个动作）。核心 idea：利用大模型智能体动作空间天然有界的结构约束，基于末动作右同余将执行轨迹前缀树精确折叠为紧凑确定性有限状态机（FSM），以单一模型兼顾工作流记忆、下一步动作预测与运行时早期失败阻断。

方法详解¶

整体框架¶

本文将智能体行为恢复形式化为从正样本轨迹中逆向构建有限状态机 $\mathcal{M}=(Q, \mathcal{A}, \delta, q_0, Q)$ 的问题。整个管线首先通过确定性的动作提取函数将异构的系统-用户-工具交互消息映射到紧凑动作字母表；接着将整批轨迹插入前缀树（Trie）；随后通过末动作等价类做商运算将节点精确合并，最后过滤孤立稀疏转移得到直接跟随有限状态机。该状态机作为结构化基底，既可直接导出转移概率赋能下一步预测，又能提取各状态访问统计特征与跨熵异常指标，驱动在线低延迟监控。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["多轮智能体交互轨迹<br/>角色/文本/工具调用"] --> B["动作映射与字母表规约<br/>优先级提取: 工具/Action/命令"]
    B --> C["前缀树构建与末动作同余合并<br/>商运算节点折叠至 |A|+1"]
    C --> D["单次转移剪枝与直接跟随 FSM<br/>过滤稀疏单发转移"]
    D --> E["双任务结构化应用基底"]
    E --> F["下一步预测与极简上下文<br/>状态转移条件概率与 top-15 延续"]
    E --> G["在线监控与早停判定<br/>累积对数似然比与环路率阈值"]

关键设计¶

1. 基于末动作右同余的紧凑商图折叠：消除形式化推断的超参数与状态爆炸

传统被动文法推断在无负例场景下面临 Gold 不可辨识性定理的限制，诸如 RPNI 等算法因不敢冒进合并而产生 $10^3\sim 10^5$ 个状态的庞大前缀树，导致过拟合且每状态样本稀疏。本文利用智能体行为被工具和角色强约束的先验，定义前缀树节点间的末动作右同余关系： $$q \sim q' \iff \kappa(q) = \kappa(q')$$ 其中 $\kappa(q)$ 表示进入前缀树状态 $q$ 的转移边上的动作符号（根节点为初始动作 $\mathrm{init}$）。通过将同一等价类的所有状态合为一个状态，将前缀树直接坍缩为严格包含 $|Q| = |\mathcal{A}| + 1$ 个状态的确定性直接跟随自动机。该定理保证了训练集重放适应度（Fitness）完全无损，并将构造时间压缩至毫秒级（线性复杂度 $\mathcal{O}(N\bar{T}\cdot|\mathcal{A}|)$）。

2. 有限状态转移浓度与似然比统计量：为失败检测提供 Neyman-Pearson 最优性

状态机紧凑化使得每个状态聚合了充分的样本观测，状态 $q$ 处的经验转移分布 $\hat{P}(a\mid q)$ 满足全变差范数浓度界： $$\Pr\left(\|\hat{P}(\cdot\mid q) - P^*(\cdot\mid q)\|_{\mathrm{TV}} \geq \epsilon + \frac{\alpha|\mathcal{A}|}{n_q + \alpha|\mathcal{A}|}\right) \leq 2|\mathcal{A}|\exp\left(-\frac{n_q\epsilon^2}{2}\right)$$ 利用该性质，在将成功与失败轨迹建模为同构状态空间上的混合分布时，测试轨迹的跨熵差值 $\mathrm{CE}^-(\tau) - \mathrm{CE}^+(\tau)$ 构成了区分两者的 Neyman-Pearson 渐近最优检验统计量。结合单状态的访问频次、消息长度、执行错误率与时序熵，仅需轻量分类器即可准确捕捉跳步、死循环或错误扩散等结构级失效模式。

3. 在线对数似然比与环路率监控器：亚线性遗憾保障的无损早停机制

为实现生产级在线守卫，本文设计了基于流式累积对数似然比 $L_t(\tau) = \sum_{s\le t}[\log \hat{P}^-(a_s\mid q_s) - \log \hat{P}^+(a_s\mid q_s)]$ 与环路率（Cycle-rate）双重判决的在线监控器。理论证明在线监控器相对事后最优状态相关阈值策略的期望遗憾达到亚线性界： $$\mathrm{Regret}(T) \leq B\sqrt{2T\log|Q|} + \frac{T|\mathcal{A}|}{\sqrt{n_q}}$$ 由于 $|Q|$ 极度紧凑（7–43 个），$\sqrt{\log|Q|}$ 项极小，使得在线监控器无需复杂大模型判决或重训神经网络，仅需单步 $0.006\,\mathrm{ms}$ 的转移重放，即可在智能体出现异常循环时提前触发阻断。

4. 极简概率上下文注入（ASG-minimal）：避免结构信息过载对大模型预测的干扰

在赋能大模型下一步预测时，传统工作流记忆（AWM）仅保留成功样本的线性最长公共子序列，缺少分支与失败回溯；而若向提示词中注入完整图拓扑（节点、所有边和状态转移矩阵），过长的图描述反而会稀释决策焦点。本文设计极简上下文格式，仅注入当前状态的一阶前向转移概率分布及 top-15 高频多步后继延续路径，既提供精炼的拓扑先验，又杜绝了冗余 prompt 带来的上下文污染。

完整示例 / 训练策略¶

以 SWE-agent 上的代码修复任务为例： 1. 轨迹解析：智能体执行交互，提取动作流序列 [search, navigate, edit, execute, submit]。 2. 状态折叠：前缀树中的各个局部历史节点按输入动作分别合并归入对应的 25 个全局状态。 3. 在线阻断实测：某失败轨迹陷入 search 与 edit 的死循环，其状态间转移重复度快速上升，环路率在执行进行到 32% 进度时突破阈值 0.778，监控器即刻触发早停终止任务，避免后续 68% 的无效 Token 与 API 消耗；而成功轨迹持续探索到 submit 节点，平滑完成提交。

实验关键数据¶

主实验¶

在 12 个公开基准数据集（涵盖代码、网页、桌面系统、客服通信与安全评测）上，将本文 FSM 与文法推断算法（RPNI、Alergia、k-Tails）、隐马尔可夫模型（HMM）及工作流记忆（AWM）全面对比：

| 数据集 | 动作数 $|\mathcal{A}|$ | 本文状态数 $|Q|$ (Fit) | RPNI 状态数 (Fit) | Alergia 状态数 (Fit) | 压缩比 (vs. RPNI) | |---|---|---|---|---|---| | SWE-agent | 24 | 25 (0.999) | 59,510† (0.646) | 35 (0.999) | 2,380× | | WebArena | 24 | 25 (1.000) | 382 (1.000) | 149 (1.000) | 15× | | AgentNet | 24 | 25 (1.000) | 62,495† (0.742) | 45 (1.000) | 2,500× | | tau2-bench (air) | 17 | 18 (1.000) | 6,506† (0.844) | 23 (0.999) | 361× | | tau2-bench (ret) | 18 | 19 (1.000) | 14,249† (0.837) | 25 (1.000) | 750× | | tau2-bench (tel) | 42 | 43 (1.000) | 63,897† (0.491) | 75 (0.999) | 1,486× | | ATBench | 14 | 15 (1.000) | 899† (0.984) | 15 (1.000) | 60× | | OSWorld | 26 | 27 (0.997) | 38,232† (0.706) | 31 (0.999) | 1,416× |

(注：† 表示 RPNI 在 120 秒超时限制下被截断。)

在提供给大模型（GPT-4.1-mini）作为下一步预测上下文的 Top-1 准确率评测中，本文 FSM 显著超越当前最先进的 Agent Workflow Memory (AWM)：

数据集	样本数 $N$	AWM Top-1 (%)	本文 FSM Top-1 (%)	提升幅度 ($\Delta$)
WebArena	4,800	65.5	81.2	+15.7pp
SWE-smith	300	74.7	100.0	+25.3pp
SWE-agent	1,200	67.7	70.5	+2.8pp
tau2-bench (tel)	1,095	28.5	45.6	+17.1pp
tau2-bench (ret)	1,095	52.9	65.1	+12.2pp
tau2-bench (air)	480	56.5	57.3	+0.8pp
ATBench	600	47.8	62.5	+14.7pp
OSWorld	1,286	55.0	70.7	+15.7pp

消融实验¶

上下文提示格式消融（tau2-bench retail, $N=1,095$, GPT-4.1-mini Top-1 %）

提示格式配置	Top-1 准确率 (%)	说明
无外部记忆（仅原始前缀）	27.6	基线能力，无结构先验
AWM（线性成功工作流）	52.9	仅利用成功轨迹的最长公共子序列
ASG-full（注入完整状态与全局图转移）	52.2	详细结构信息过长，稀释核心信号
ASG++（ASG-full + 多步候选延伸）	49.2	上下文冗余度进一步上升，准确率倒退
ASG-success（仅成功轨迹的图结构）	50.3	丢失失败回溯路径，覆盖面下降
ASG-minimal（本文：局部转移概率 + top-15 延续）	65.1	去粗取精，兼顾状态约束与精简提示

关键发现¶

结构化特征击败原始统计量：在失败预测任务上，仅靠轨迹长度在 SWE-agent 上的 AUROC 仅为 0.659，而加入 FSM 状态分解特征后跃升至 0.790（全特征集达 0.799，电信域达 0.941）；成功样本呈现严格收敛的 search $\to$ edit $\to$ submit 主干，失败样本则发散于全状态空间。
早期阻断挽救巨大算力：在线监控器在 SWE-agent 上平均仅需消耗 32% 轨迹长度即可识别出失败（精确率 85.9%，召回率 95.5%），若提高阈值更可在 0 误报前提下达成 11.3% 召回率，直接节省 68% 的冗余推理算力。
拓扑独立于底层模型：在 tau2-bench 多模型评测中，用不同 LLM（GPT-4.1、Claude 3.7 Sonnet、o4-mini）生成的轨迹均能被单一 FSM 实现 1.000 适应度重放，跨模型失败预测平均 AUROC 达 0.786，证明系统环境与工具规范主导了拓扑结构。

亮点与洞察¶

反直觉的极度紧凑性：传统认知中非结构化智能体轨迹变幻莫测，但形式化为末动作右同余后，12 个主流任务仅需 7–43 个状态即可达成 $\ge 99.7\%$ 的重放拟合率，证实智能体执行在系统级高度可规约。
理论与实践严丝合缝：将经典语法推断中的直接跟随自动机与概率浓度不等式无缝结合，直接推导出亚线性在线监控遗憾界，避免了为了监控而盲目堆叠深度检测模型。
极简上下文哲学：在大模型协作交互中，完整的形式化图结构不仅耗费上下文窗口，反而会引入推断干扰；以局部一阶概率加关键多步延续作为提示，为结构化记忆设计提供了范式参考。

局限与展望¶

依赖预设动作映射函数：当前仍需针对不同数据集设定简单的规则（工具名/命令名解析），缺乏从完全无结构自由文本中全自动无监督发现动作字母表的能力。
无法识别同类对抗序列：由于直接跟随自动机只约束动作转移二元闭包，严格保持动作 bigram 转移频率的人工对抗异常轨迹仍可能被 FSM 判定为合法。
多模型迁移尚有差距：跨模型迁移预测 AUROC（0.786）相较本模型自预测（0.877）仍存在 0.091 的落差，表明不同 LLM 虽共享转移拓扑，但局部的步态异常概率分布仍有模型个性。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙跳出复杂文法推断与黑盒神经网络盲区，用极其优雅的末动作同余解决智能体行为表征难题。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖 12 个真实基准数据集、9 类基线方法、跨模型泛化及严谨的理论证明与消融分析。
写作质量: ⭐⭐⭐⭐⭐ 论证环环相扣，理论推导扎实，方法机制清晰且图文呼应。
价值: ⭐⭐⭐⭐⭐ 为大模型智能体安全审计、低成本在线早停与记忆增强提供了极具工程落地价值的极简基底。