[Paper] 测量不可测的：Markov Chain 可靠性用于 LLM 代理

Source: arXiv - 2604.24579v1

Overview

本文介绍了 TraceToChain，一个可复现的流水线，将大型语言模型（LLM）代理的执行轨迹转换为吸收离散时间马尔可夫链（DTMC）。通过此方法，它将不同的可靠性指标（例如 pass@k、可靠性衰减曲线）统一为单一的、基于统计的 “success‑time” 分布，同时提供了当前基准报告中缺失的诊断信息和不确定性估计。

关键贡献

• Trace‑to‑DTMC pipeline：自动对追踪状态进行聚类，使用拉普拉斯平滑的最大似然估计（MLE）估计转移概率，并为 LLM 代理行为拟合吸收式 DTMC。
• 统计诊断：复合 Akaike 信息准则（AIC）和 Kolmogorov–Smirnov（KS）拟合优度检验，用以验证马尔可夫链能够忠实地再现观测到的追踪。
• 不确定性量化：对每个转移概率给出 Dirichlet‑posterior 可信区间以及非参数自助法（bootstrap）区间。
• 统一的可靠性视角：展示常用指标（pass@k、pass^k、reliability decay curve）实际上是从 DTMC 推导出的单一首通时间分布的不同投影。
• 实证验证：在七个受控的 MAST‑style 框架上，拟合的 DTMC 能以最大 L∞ 误差 0.053 再现保留的可靠性曲线，并在所有框架上通过 KS 检验（p > 0.05）。

方法论

1. 轨迹收集 – 在一套任务上运行 LLM 代理，并记录每个中间状态（例如，工具调用、提示、响应）。
2. 自动聚类 – 使用数据驱动的聚类算法将相似状态分组为“宏‑状态”分类法，在保留语义的同时缩短轨迹长度。
3. 转移估计 – 统计代理从一个宏‑状态移动到另一个宏‑状态的次数。采用拉普拉斯平滑避免零概率边，然后计算转移矩阵 Q（瞬态‑到‑瞬态）以及吸收矩阵 R₊（到成功）和 R₋（到失败）的最大似然估计。
4. 模型拟合检查 –
   • AIC 用于评估模型的简约性与拟合度。
   • KS 检验 将经验首次到达时间 CDF（轨迹首次触及吸收状态时）与由 DTMC 推导的解析 CDF 进行比较。
5. 不确定性报告 – 将转移计数视为 Dirichlet 分布的抽样，以获得可信区间；此外，对整个轨迹集合进行自助抽样（bootstrap），生成非参数置信带。
6. 可靠性提取 – 在拟合的 DTMC 上使用经典可靠性公式（Kemeny–Snell、Goel–Okumoto 等）计算 pass@k、pass^k，以及作为首次到达分布闭式函数的可靠性衰减曲线。

Results & Findings

• Fit Quality: 在所有七个测试框架中，来自 DTMC 的分析可靠性衰减曲线与经验曲线的中位 L∞ 误差为 0.048，表明匹配紧密。
• Statistical Acceptance: 对首次通过 CDF 进行的双样本 KS 检验从未拒绝拟合模型（p 值范围为 0.78 到 1.0）。
• Uncertainty Tightness: 每个转移概率的后验区间和自助抽样区间在中位数处约为 0.01，显示即使在有限的轨迹数据下，管道也能产生稳定的估计。
• Metric Unification: 作者在数学上证明，pass@k、pass^k 与可靠性衰减曲线都是同一底层 DTMC 派生分布的边缘化形式，从而简化了基准结果的解释。

实际影响

• 更可信的基准：开发者现在可以在标量分数（例如，pass@10 = 0.73）旁边提供完整的成功‑时间分布和置信区间，从而更容易在不同延迟或步数预算约束下比较代理。
• 调试与优化：宏状态转移矩阵突出显示“瓶颈”状态（循环或失败的高概率），指导有针对性的提示工程或工具集成改进。
• 服务水平协议（SLA）：提供 LLM 驱动代理的云服务商可以使用 DTMC 模型预测在给定时间预算内任务完成的概率，从而制定更精确的 SLA 定义。
• 自动化监控：通过持续将新轨迹输入 TraceToChain，生产系统可以在漂移出现（例如，向失败状态的转移突然增加）之前检测到它，防止用户可见的错误。
• 跨任务泛化：由于流水线是数据驱动的，它可以应用于任何顺序 LLM 工作流——代码生成、自治网页浏览、多轮推理——而无需手工编写特定任务的可靠性公式。

限制与未来工作

• 受控基准：验证是在合成的 MAST‑style 框架上进行的；真实世界的噪声环境可能导致状态爆炸或非马尔可夫依赖，从而挑战 DTMC 假设。
• 状态聚类敏感性：宏状态分类的质量取决于聚类算法和超参数；聚类不佳可能会掩盖重要的失效模式。
• 可扩展性：对于极长的轨迹或庞大的任务套件，转移矩阵可能变得很大，可能需要稀疏矩阵或层次化建模技术。
• 向连续时间的扩展：当前模型是离散时间的；扩展到连续时间马尔可夫过程可以捕获可变长度的动作（例如具有不同延迟的 API 调用）。
• 与训练循环的集成：未来的工作可以通过将可靠性诊断反馈到 LLM 微调或人类反馈强化学习管道中，直接优化期望的首次通过分布，从而闭环。

作者

• Phat T. Tran‑Truong
• Xuan‑Bach Le

论文信息

• arXiv ID: 2604.24579v1
• 分类: cs.SE
• 出版日期: 2026年4月27日
• PDF: 下载 PDF