💻 computer science

Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

本文介绍了\textsc{TraceToChain}，这是一个可复现的流水线，它将大语言模型智能体的执行轨迹建模为吸收式离散时间马尔可夫链，从而将不同的可靠性指标统一为单一的成功时间分布，同时在多个框架下提供严格的统计诊断、不确定性量化和高保真实证验证。

原作者： Phat T. Tran-Truong, Xuan-Bach Le

发布于 2026-04-28

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Phat T. Tran-Truong, Xuan-Bach Le

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在雇佣一位非常聪明、但偶尔会困惑的机器人助手来解决一个复杂的谜题。你给它一个任务，它开始思考、尝试工具、犯错，然后再次尝试。有时它能解开谜题；有时它会放弃或崩溃。

目前，当我们评估这些 AI 智能体时，通常只是给它们打一个单一的分数，比如"72% 的成功率”。这就像在不知道一辆车是在行驶 10 英里后还是 10,000 英里后才会抛锚，或者引擎的微小改动是否会导致其崩溃的情况下，就说这辆车“可靠”一样。

本文介绍了一种评估这些 AI 智能体的新方法，称为TRACETOCHAIN。它不再给出单一分数，而是构建智能体行为的详细“地图”，以精确预测其在不同条件下的可靠性。

以下是论文如何用简单的类比来解释这一方法：

1. 问题：“单一数字”的陷阱

目前，我们使用简单的数字来衡量 AI 智能体，例如"pass@k"（如果我们让它尝试 5 次，它是否成功？）或“可靠性衰减”（运行时间越长，表现是否越差？）。

类比：想象你是一名飞行员。如果有人告诉你“这架飞机的成功率为 90%"，你并不知道这意味着每 10 次飞行就会坠毁一次，还是仅在暴风雨天气下才会坠毁。仅凭这一个数字，你无法回答诸如“如果我添加一个新的导航工具会发生什么？”或“如果我将时间从 10 分钟改为 20 分钟，成功的可能性有多大？”这样的问题。

2. 解决方案：“吸收地图”

作者将智能体的历史（其“轨迹”）转化为一个马尔可夫链。

类比：将智能体的旅程想象成一款棋盘游戏。
- 瞬态状态：这些是智能体仍在工作的“中间”格子（例如“规划”、“调用工具”、“读取错误”）。
- 吸收状态：这些是“终局”格子。一旦你落在这里，游戏就会停止。只有两个：成功（你赢了！）和失败（游戏结束）。
- 地图：作者创建了一张地图，显示了从一个格子移动到另一个格子的概率。例如，如果智能体处于“错误”格子，它有 30% 的概率回到“规划”，10% 的概率进入“成功”，60% 的概率崩溃至“失败”。

3. “审计”（检查地图）

你不能只是画一张地图就信任它。本文引入了一套严格的审计流程，以确保地图确实与现实相符。

类比：想象你是一位正在绘制森林地图的制图师。在让徒步者使用地图之前，你需要检查两件事：
1. 路径是否合理？（论文使用名为AIC的测试，来判断智能体的记忆是否短到可以用简单模型描述，或者是否需要更复杂的地图。）
2. 地图是否与地形匹配？（论文使用名为KS的测试，来查看预测的路径是否与智能体实际走过的路径相符。）
如果地图未能通过这些测试，作者会说：“停止！不要使用此地图进行预测。”这防止了虚假的信心。

4. 这张地图能让你做什么

一旦地图构建并经过审计，它就成为了解决旧“单一数字”系统无法处理的问题的强大工具：

“时间预算”问题：“如果我将智能体的步数从 10 步增加到 50 步，它成功的可能性会增加多少？”
- 论文主张：地图可以瞬间计算出这一点，而无需再运行智能体 1,000 次。
“假设”问题：“如果我们添加一个当智能体卡住时提供帮助的‘回退’工具，会发生什么？”
- 论文主张：你可以调整地图（改变棋盘上的概率），并立即看到成功率提高了多少，而无需重新运行整个基准测试。
“统一”问题："pass@5"和“可靠性衰减”是不同的事物吗？
- 论文主张：不！它们只是同一张地图的不同视角。论文从数学上证明，所有这些不同的指标只是从不同角度观察同一个“首达”分布（从起点到成功的路径）。

5. 证明：它有效吗？

作者在七种不同类型的 AI 智能体框架（如 ReAct、Reflexion 和 ToolFormer）上测试了这种方法。

结果：他们将数据一分为二：在一半数据上构建地图，在另一半数据上测试（这部分数据地图从未见过）。
结果：地图以极高的精度（误差约 5% 以内）预测了智能体的成功率。“审计”测试正确地接受了优质地图并拒绝了劣质地图。

总结

论文认为，我们应该停止将 AI 智能体视为抛硬币（正面/反面），而是开始将其视为带有地图的旅程。

通过将原始数据转化为经过验证的“吸收马尔可夫链”，我们可以：

预测随时间推移的成功率。
测试变更（如新工具），而无需昂贵的重新运行。
统一令人困惑的指标，形成清晰的图景。
审计结果，确保我们不是在自欺欺人。

作者强调，这是一个有条件的工具：只有当“地图”通过审计时，它才有效。如果智能体的行为过于混乱而无法适应地图，系统会正确地表示“我们目前无法预测这一点”，而不是给出一个具有误导性的数字。

以下是论文《测量不可测量之物：LLM 代理的马尔可夫链可靠性》的详细技术总结。

1. 问题陈述

大型语言模型（LLM）代理正日益被部署为顺序软件系统，执行规划、调用工具、观察结果和重试等操作。然而，其可靠性目前仍使用标量基准指标（例如 pass@k、passk 和可靠性衰减曲线 RDC）进行评估。这些指标存在三个关键局限性：

缺乏分布洞察：它们将结果概括为单一数值，而未识别底层的成功 - 时间分布。
无拟合优度验证：它们未验证观察到的执行轨迹是否真正支持假设的分布。
忽略不确定性：它们未能量化由有限轨迹长度引起的不确定性，使得回答反事实问题变得困难（例如，“如果我们添加一个回退工具会发生什么？”或“可靠性如何随更大的步骤预算变化？”）。

作者认为，LLM 代理的可靠性应被视为首达问题（即在失败前多快达到成功），并包含明确的不确定性和模型验证，而非仅仅关注终端通过率。

2. 方法论：TRACETOCHAIN

本文介绍了TRACETOCHAIN，这是一个可复现的流水线，将原始代理执行轨迹转换为经审计的吸收离散时间马尔可夫链（DTMC）。该方法论包含四个主要阶段：

A. 状态构建（特征化与聚类）

输入：由推理步骤、工具调用和观察结果组成的原始轨迹。
过程：
1. 特征化：使用基于规则的特征（例如工具类型、错误代码）或学习到的编码器，将步骤映射为向量表示。
2. 聚类：使用凝聚 Ward 链接法将这些向量聚类为离散瞬态状态（ $S_T$ ）。聚类数量通过轮廓系数（silhouette score）进行选择。
3. 结果映射：轨迹终止于成功（ $\oplus$ ）或致命失败（ $\ominus$ ），这两者作为吸收状态。

B. 转移估计

模型：系统拟合一个 DTMC $\hat{M} = (\hat{Q}, \hat{R}^\oplus, \hat{R}^\ominus)$ ，其中 $\hat{Q}$ 表示瞬态状态之间的转移， $\hat{R}^\oplus, \hat{R}^\ominus$ 表示转移到成功或失败的概率。
估计：参数使用**拉普拉斯平滑最大似然估计（MLE）**进行估计，以防止未观察到但合理的转移出现零概率。

C. 拟合优度（GoF）协议

为了确保马尔可夫抽象的有效性，流水线采用复合诊断测试：

柯尔莫哥洛夫 - 斯米尔诺夫（KS）检验：比较首达时间（到达成功的时间）的经验累积分布函数（CDF）与从拟合链推导出的解析 CDF。
赤池信息量准则（AIC）：将一阶马尔可夫模型与二阶替代模型进行比较，以确保满足记忆需求。

决策：仅当 $p_{KS} > 0.05$ 且 $\Delta AIC > 0$ 时，链才被接受。如果被拒绝，则必须对轨迹语料库进行分段或重新特征化。

D. 不确定性量化

流水线使用以下方法为所有可靠性指标提供置信区间：

狄利克雷后验区间：源自拉普拉斯平滑 MLE，用于量化参数不确定性。
非参数自举法：重采样轨迹以估计拟合链的变异性。

3. 主要贡献与理论框架

A. 指标的统一

本文证明了 pass@k、passk 和可靠性衰减曲线（RDC）并非相互竞争的指标，而是单一成功首达分布的投影：

RDC ( $R(d)$ )：在 $d$ 步内成功的概率。
$pass_k$ ： $k$ 次独立试验全部成功的概率（ $R_\infty^k$ ）。
**$pass@k $**：$ k $次试验中至少有一次成功的概率（$ 1 - (1-R_\infty)^k$）。
定理：这些关系在独立同分布（i.i.d.）假设下成立；偏差表明试验之间存在隐藏的相关性。

B. 部署的分析工具

利用基本矩阵 $N = (I - \hat{Q})^{-1}$ ，作者推导出了以下闭式解：

视界可靠性：计算任意步骤预算下的 $R(d)$ ，而无需重新运行基准测试。
扰动敏感性：使用一阶敏感性分析，估计局部变化（例如添加回退工具）对全局可靠性的影响。
NHPP 极限：表明在罕见失败机制下，拟合的代理链收敛于经典的 Goel–Okumoto 非齐次泊松过程（NHPP）模型，从而架起了现代代理可靠性与经典软件可靠性理论之间的桥梁。

4. 结果与验证

作者通过模拟研究和实证案例研究验证了 TRACETOCHAIN：

模拟研究 SS1（数值）：验证了闭式可靠性计算在不同链规模下与蒙特卡洛模拟相匹配。
模拟研究 SS7（GoF 诊断）：
- 正确接受了 100% 由真实一阶马尔可夫链生成的轨迹。
- 正确拒绝了 100% 由二阶链生成的轨迹（其中 AIC 层检测到了依赖性）。
模拟研究 SS9（保留验证）：
- 在 7 个受控的 MAST 风格框架上进行了测试，采用严格的 50/50 拟合/测试分割。
- 结果：拟合的链准确预测了保留的可靠性衰减曲线。
  - 最大 $L_{RDC}^\infty$ 误差：0.053（中位数：0.048）。
  - KS 检验 p 值：所有框架均通过（ $p > 0.05$ ），最小 $p = 0.78$ 。
- 这表明该流水线在不过拟合训练数据的情况下，恢复了底层的成功 - 时间分布。
实证案例研究（SS6）：应用于 7 个真实世界的代理框架（例如 ReAct、Reflexion、ToolFormer）。该流水线成功根据渐近可靠性（ $R_\infty$ ）对框架进行了排名，并可视化了它们特定的 RDC 形状。

5. 意义与影响

从标量到结构：将 LLM 代理评估从静态标量分数转变为动态、可审计的可靠性模型，该模型捕捉执行的过程，而不仅仅是结果。
可审计的可靠性：为可靠性声明提供“证书”（GoF 检验 + 不确定性区间），解决了代理评估的“黑盒”性质。
反事实推理：使工程师能够利用拟合链上的扰动分析回答“如果……会怎样”的问题（例如，“添加重试机制如何影响可靠性？”），从而避免重新运行完整基准测试的成本。
指标协调：通过展示不同基准指标是同一底层分布的数学关联投影，解决了它们之间的混淆。
实用价值：该流水线已准备好用于受控轨迹数据（如 MAST），未来工作计划在获得稳定的步骤级特征后，扩展至 SWE-bench 和 $\tau$ -bench 等复杂基准。

总之，TRACETOCHAIN提供了一个严谨的、数学基础扎实的框架，将原始 LLM 代理轨迹转化为可靠、可诊断且具有预测性的系统依赖性模型。