arXiv:2607.17082cs.AIcs.CL2026-07

用最优传输度量智能体轨迹的结构,更精准评估计划与执行质量。

OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories

  • 构建依赖图并用非平衡融合格罗莫夫-沃瑟斯坦距离计算轨迹差异
  • 在三个基准上优于语义匹配等传统方法,能区分有效与无效轨迹
  • 适合无验证器的开放域任务评估,对计划顺序和粒度变化不敏感

大型语言模型智能体通过交织规划、工具调用和中间结果生成任务轨迹。现有评估指标将轨迹简化为二元成功标志,或通过精确匹配比较,或交由另一语言模型判断。成功标志无法区分合理解与侥幸成功,且无法说明失败原因;精确匹配会惩罚合法但顺序或分解方式不同的计划。本文将轨迹评估重构为代理执行图与一组有效解图之间的距离,并通过属性化依赖图上的非平衡融合格罗莫夫-沃瑟斯坦运输问题实现。所得评分称为OTAP(Optimal Transport for Agentic Planning),是一种伪度量,对保持依赖关系的重排具有不变性,且对冗余步骤敏感度有界。其非平衡边际可处理缺失或幻觉步骤而不强制匹配,软耦合机制适应计划粒度差异。在受控扰动和三个公开基准测试中,当仅依赖语义的指标表现低于随机水平时,OTAP仍能有效区分有效与无效轨迹。其优势随依赖图保真度提升:在边由操作语义推导出时最大,由自由文本推断时最小。当存在形式化验证器时,严格表面指标预测有效性更优;而OTAP适用于无验证器的开放域场景。

原文摘要 · Abstract (English)

Large language model agents solve tasks by generating trajectories that interleave planning, tool calls, and intermediate results. Current evaluation metrics reduce such a trajectory to a binary success flag, compare it against a reference by exact matching, or delegate judgment to another language model. A success flag cannot distinguish a sound solution from one that succeeds by luck, and says nothing about why a failed run went wrong. Exact matching penalizes plans that are valid but reordered or decomposed differently from the reference. We reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiate it via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs. The resulting score, termed OTAP (Optimal Transport for Agentic Planning), is a pseudo-metric that is provably invariant to dependency-preserving reorderings and has bounded sensitivity to redundant steps. Its unbalanced marginals handle missing or hallucinated steps without forcing a match, and its soft coupling accommodates variation in plan granularity. On controlled perturbations and three public benchmarks, OTAP separates valid from invalid trajectories in a regime where semantics-only metrics score below chance. Its advantage tracks the fidelity of the dependency graph: largest where edges follow from operator semantics, smallest where they are inferred from free text. Where a formal verifier exists, strict surface metrics predict validity better than OTAP does, which places OTAP in open-ended domains where no verifier is available.

智能体评估最优传输轨迹分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。