语言模型智能体的探索与利用错误可被度量 Exploration and Exploitation Errors Are Measurable for Language Model Agents
提出无需访问内部策略即可量化大模型智能体探索与利用错误的策略无关指标
前置知识
探索-利用权衡
强化学习中的经典问题，智能体需要决定是利用已知高回报动作，还是探索未知动作以发现更优策略；两者之间的平衡直接影响学习效率与最终性能。
本文研究对象就是 LM 智能体在长视野决策中如何平衡探索与利用，是论文问题的物理基础。
部分可观察马尔可夫决策过程 (POMDP)
智能体无法直接获得完整环境状态，只能通过观察历史来推断隐状态，形式化为 $(\mathcal{S}, \mathcal{A}, T, R, \Omega, O)$ 六元组。
本文的 2D 网格地图本质是 POMDP，地图信息随访问逐步揭示，决定了为何需要把度限制定为策略无关。
任务有向无环图 (Task DAG)
用 DAG 建模任务间的依赖，节点代表子任务，边表示父子约束；只有所有父节点满足才能执行当前节点，本文中存在 AND/OR 两种前置关系。
任务 DAG 是本文建模子任务前置条件的核心数据结构，决定了 pending 集合 $P(t)$ 的计算。
ReAct 智能体框架
Yao 等 2023 年提出的范式，将推理（Thought）与行动（Action）在提示中交替，使 LM 智能体既会思考又会调用工具或执行环境动作。
本文默认采用 ReAct 风格与 LM 交互，是 prompt 设计的事实标准，影响四种 prompt 变体的设计。
循环数 (Cyclomatic Number)
图论中度量结构复杂度的指标，定义为 $c = |E| - |V| + k$，其中 $k$ 为连通分量数，等于独立环路数。
本文 stale score 中 $c_t = |E_{np}| - |V_{np}| + 1$ 即借用此概念，把'在已观察区域闭合新环路'量化为结构冗余。
图探索最优边预算
Tarjan 等 1972 年证明：无向图的在线最优 DFS 探索最多需要把每条边访问两次；超过该预算即为冗余动作。本文进一步给出节点级'良性 gateway'预算也为 2。
stale score 中边/节点阈值硬编码为 2 源自该经典结论，是度规具有理论根基的关键。
研究动机
现有 LM 智能体评测体系几乎只关心任务成功率，缺少细粒度、可解释的过程指标。具体而言，AI 编程（SWE-Bench）、工作流自动化（Anthropic Computer Use）、具身智能等场景都需要智能体在长视野中同时具备良好的探索和利用能力，但目前没有统一框架衡量这种平衡。另一方面，强化学习中衡量探索与利用的标准（如状态访问熵、value function 差异）需要访问智能体内部策略或价值函数，而 LM 智能体通常以黑盒 API 形式提供，我们只能观察其输出动作。因此，如何从动作轨迹中无需内部状态即可分离并量化探索错误与利用错误，是当前评测体系的一个核心缺口。
本文的目标是本文目标明确：提出一种政策无关（policy-agnostic）的指标，仅从 LM 智能体的动作轨迹中量化其在每个时刻产生的探索错误和利用错误数量。为此，作者在 Partially Observable 2D Grid Map 上构建可控评测环境，将任务结构建模为带前置约束的符号化 DAG，并通过程序化生成地图拓扑和任务复杂度来单独调节探索难度（更宽地图、更稀疏任务节点）与利用难度（更浅路径、更密集依赖）。最终在 13 个前沿 LM 上系统验证指标的有效性，并分析 prompt 设计、harness 工程、语义信息注入等因素对两类错误率的影响。
与已有工作不同的是，已有工作要么假设能访问 LM 内部策略（不适配闭源 API 场景），要么依赖预标注参考轨迹（Chen et al., 2024; Ma et al., 2024），存在循环依赖。本文独特定位'任何合理策略都不不会产生的动作'，借助经典图论中的 cyclomatic number 与边/节点复用预算，将每个动作的'非合理性'严格归因于探索、利用或二者皆有，无需指定最优策略、也不需要参考轨迹。同时通过把任务 DAG 中的语义信息全部替换为符号（如 A/B/C/D），剥离预训练知识的影响，让评测直接测出智能体的原始探索利用能力。这是与 SWE-Bench、AgentBench 等仅看成功率的基准的本质差异。
核心方法
方法由三个核心模块构成：可控环境、目标集划分、stale score 度量。环境层面，作者用程序化生成的 2D 部分可观察网格地图 $\mathcal{M} \subset \mathbb{N}^2$ 配合一个未知任务 DAG $\mathcal{G}$，节点只在被访问时揭示且全部用符号（A/B/C/D）命名以剥离语义。动作层面，每个时刻智能体获得四邻域可通行方向；目标集合 $T(t)$ 按四类情形定义：仅有未观察细胞则需探索；goal 在 pending 集合则强制利用；二者皆有则可任选。度规层面，作者定义 no-progress trajectory $\tau_{np}(t)$ 为最近一次进度事件后的动作序列，在其上计算 cyclomatic number $c_t$、边复用 $e_t$、节点复用 $n_t$ 三者之和得到 stale score $S_t$，仅当 $S_t$ 较上一时刻上升且 $|T(t)|>1$ 时才标记为结构性错误。最终按四类情形把每个错误分摊到 exploration / exploitation / both。
核心创新是把'错误'重新定义为'任何合理策略都不会产生的动作'，而非'偏离最优策略的偏差'。这一视角带来三个本质区别：第一，不依赖参考轨迹与最优策略，因此 policy-agnostic，可直接套用任何黑盒 LM；第二，结合目标集 $|T(t)|=1$ 与 $|T(t)|>1$ 两种情形分别检测 gain 类错误与拓扑冗余类错误，避免 Figure 3c 描述的对称陷阱——增益为 1 但智能体仍在原地徘徊的漏检；第三，把 stale score 的边/节点复用阈值设为 2，分别对应 Tarjan 1972 年证明的无向图最优探索边预算与对应的节点级'良性 gateway'预算，赋予度规坚实的图论根基，而非纯经验启发式。
方法步骤详情
完整方法分四步。第一步环境实例化：在网格随机放置 task node，构造 task DAG 的 AND/OR 关系，符号化命名（A/B/C/D），用障碍物控制路径宽度，输出可复现地图种子。第二步交互执行：智能体在 $t$ 时刻执行动作，观测四邻域可通行性与节点状态信息，环境更新 $P(t)$、$U(t)$、$T(t)$。第三步错误检测：按式 (1) 计算 $Gain(t \to t+1)$，为 0 则直接标记为错误；$|T(t)|=1$ 且 gain=1 则不计入；$|T(t)|>1$ 且 gain=1 时，在 $\tau_{np}(t)$ 上计算 $c_t$、$e_t$、$n_t$ 三件套（见上节），令 $S_t = c_t + e_t + n_t$，仅当 $S_t > S_{t-1}$ 才计入结构性错误。第四步归因：按 Table 1 四类情形把每个错误计入 exploration / exploitation / both，再用各自所需 timestep 总数归一化。
技术新颖性
新颖性体现在三方面。第一，从思想层面，作者首次将 LM 智能体评测从纯成功率下沉到'策略无关的过程度规'，并借用 cyclomatic number 把'结构冗余'这一抽象概念形式化为可计算量。第二，从场景层面，相比 SWE-Bench、AgentBench 这类依赖真实语义的端到端基准，本文通过符号化任务 DAG 与部分可观察地图剥离了预训练语义先验，让评测聚焦在'原始探索与利用能力'上。第三，从度规层面，作者把探索与利用错误显式地按四类情形分摊，避免单一指标的归一化歧义；同时 stale score 的边/节点阈值 2 在理论上有 Tarjan 1972、Edmonds & Johnson 1973、Panaite & Pelc 1999 等图探索定理作为支撑，而非凭经验设定。这种'图论根基 + 符号环境 + 策略无关'的组合在 LM 智能体评测中尚属首次。
实验结果
五条核心发现。Finding 1：探索错误与成功率强负相关（Figure 1a $R^2=0.947$），利用错误几乎无关（$R^2=0.006$），探索是瓶颈。Finding 2：Figure 4 显示同为 100% 成功率的 Claude Opus 4.6 与 Gemini 3.1 Pro 行为截然不同——前者直奔已知目标，后者探索未观察区域。Finding 3：Figure 5 显示 explore-focused prompt 让 GPT-4.1 探索错误 0.123→0.099、成功率 51%→63%；exploit-focused prompt 让利用错误 0.143→0.123。Finding 4：Table 2 显示 harness 让 Gemini 3.1 Flash Lite 成功率 51.9%→88.9%、GPT-4.1 63%→92.6%，步数 94.3→68.0。Finding 5：Table 3 显示引入语义时 GPT-4.1 成功率 15%→45%，Gemini 3.1 Flash Lite 保持 25% 但探索率反升 33%，揭示模型对语义先验利用差异。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 2D Grid + Task DAG 探索利用基准（含 harness） | Success Rate (%) | Gemini 3.1 Flash Lite 88.9%，GPT-4.1 92.6%；前沿推理模型 Claude Opus 4.6、Gemini 3.1 Pro 100% | Gemini 3.1 Flash Lite 51.9%，GPT-4.1 63.0%（无 harness） | harness 工程带来约 +30 个百分点（Gemini +37pp、GPT-4.1 +29.6pp） |
| 2D Grid + Task DAG 探索利用基准 | Exploration Error ↓ | Gemini 3.1 Flash Lite 0.030，GPT-4.1 0.053（+harness） | Gemini 3.1 Flash Lite 0.172，GPT-4.1 0.297（baseline） | harness 工程把探索错误率降低约 5–6 倍 |
| 2D Grid + Task DAG 探索利用基准 | Exploitation Error ↓ | Gemini 3.1 Flash Lite 0.071，GPT-4.1 0.044（+harness） | Gemini 3.1 Flash Lite 0.135，GPT-4.1 0.160（baseline） | harness 工程把利用错误率降低约 2–4 倍 |
| 探索-成功率相关性分析 | 线性回归 $R^2$ | $\log$ 探索错误 vs 成功率 $R^2 = 0.947$（13 模型） | $\log$ 利用错误 vs 成功率 $R^2 = 0.006$（13 模型） | 首次给出可量化证据：探索错误率是 LM 智能体成功率的最强线性预测因子 |
| 语义信息注入实验 | Success Rate (%) | GPT-4.1 + 语义 45.0%，Gemini 3.1 Flash Lite + 语义 25.0% | GPT-4.1 符号 15.0%，Gemini 3.1 Flash Lite 符号 25.0% | 语义信息使 GPT-4.1 提升约 3 倍（+30pp），但对 Gemini Flash Lite 几乎无效 |
局限与改进
作者在第 7 节明确承认三点局限：第一，符号化抽象虽能剥离预训练先验、隔离'原始探索能力'，但与真实任务存在分布差距，许多实际场景反而鼓励使用语义知识，因此指标更适合作为补充而非端到端代理；第二，归一化按 case 时长进行，而 case 划分本身依赖智能体自身轨迹，造成'指标与行为耦合'，对不同模型、不同地图的横向比较需要谨慎；第三，per-run variance 即使在 temperature=0 下仍然显著，地图难度与多因素交织，部分实验（如 exploit demand vs exploit error，见 Appendix G）相关性较弱。个人观察层面：Figure 4 仅展示两个 100% 成功率模型，缺乏 50%–100% 区间的差异化分析；Table 3 仅 4 组数据、缺置信区间；评测对 prompt 与 harness 的消融不够充分，缺少 chain-of-thought、self-consistency 等推理增强策略的对比。
独立分析的弱点
独立分析认为有以下不足。其一，stale score 的边/节点阈值硬编码为 2，虽有 Tarjan 1972 经典结论支撑，但 LM 智能体并非最优算法代理，2 这个常数是否对所有网格尺寸与 DAG 复杂度都合适缺乏敏感性分析，可引入阈值 $\tau_e, \tau_n$ 做参数化消融。其二，环境生成仅覆盖 2D 网格 + DAG，缺少连续动作空间、长视野信息瓶颈、随机动力学等复杂要素，外部效度受限。其三，13 个模型虽跨 4 个家族（OpenAI / Gemini / Claude / GPT-OSS），但未涵盖 Qwen、DeepSeek、Llama 3.x、Mixtral 等开源 SOTA，且 GPT-OSS-120B 仅作 baseline 而非最新版本。其四，prompt 仅做了 4 个变体，缺少 tree-of-thought、self-consistency、reflection 等推理增强策略。其五，缺乏对错误率的统计检验，多组对比仅给均值，建议增加配对 t 检验或 bootstrap 置信区间以增强结论稳健性。
未来方向
作者提出未来方向：把框架扩展到更现实的环境结构（增加连续动作、随机事件、工具调用）、更复杂任务依赖（条件分支、循环子任务）。基于成果还可以延伸多个方向：第一，把 stale score 与 policy entropy、token-level uncertainty 等 LM 内部信号联合起来，构建'行为-内部'联合度规；第二，把该度规直接用作 RLHF 或 DPO 的 reward shaping 信号，让训练目标显式最小化探索错误；第三，扩展到 multi-agent 场景，度量协作中的探索-利用分工；第四，在 SWE-Bench、AgentBench 等真实基准上重新引入参考轨迹，检验真实任务中 $R^2=0.947$ 的结论是否仍成立；第五，将符号化与语义化环境联合训练，让模型学会在两种 setting 间自适应切换，从而系统性地缓解 Finding 5 揭示的语义信息利用差异问题。
复现评估
代码完全开源（论文标注 'We release our code here'），作者承诺发布环境生成器、prompt 模板、评估脚本与所有 13 个 LM 的原始动作轨迹。数据方面，每个 episode 包含种子、地图拓扑、task DAG、动作序列、stale score 时间线，可直接复现。算力方面，temperature 设为 0、3 个随机种子，13 个模型在统一 prompt 与 harness 下跑同一组地图，理论上单卡 + API 即可复现。复现难度为中等偏低：核心度规公式 (1) 与 stale score 三件套实现简单，但 prompt 与 harness 的具体模板细节、地图生成参数（节点密度、AND/OR 比例、障碍物比例）需要从附录 C.1/C.2 准确还原；Table 3 的'番茄意面'语义 DAG 也在附录 E。整体而言，依赖 API 调用次数较多（13 模型 × 4 prompt × 3 seeds × 多张地图），完整复现可能需要数百美元 API 预算。
论文图表
