大模型GUI系列论文阅读 DAY3续4：《TREE SEARCH FOR LANGUAGE MODEL AGENTS》
摘要
自主代理由语言模型（LMs）驱动，已在执行诸如网页自动化等决策任务方面展示出良好前景。然而，语言模型的一个主要局限在于：它们主要针对自然语言理解和生成进行了优化，在解决现实世界的计算机任务时，难以应对多步推理、规划以及环境反馈的利用。
为了解决这一问题，我们提出了一种推理时搜索算法，使语言模型代理能够在交互式网页环境中执行显式的探索和多步规划。我们的方法是一种基于最佳优先（best-first）的树搜索算法，它直接在实际环境空间内运行，并且能够与现有的最先进代理互补。该方法是首个在现实网页任务中展现出有效性的树搜索算法。
在具有挑战性的 VisualWebArena 基准测试中，结合我们搜索算法的 GPT-4o 代理，成功率相比无搜索基线实现了 39.7% 的相对提升，达到 26.4%，刷新了当前最先进的成功率纪录。在 WebArena 任务中，搜索算法同样实现了 28.0% 的相对提升，使成功率达到 19.2%，展现出较强的竞争力。
实验结果证明了搜索算法在网页代理任务中的有效性，并表明随着推理计算资源的增加，性能进一步提升。我们对结果进行了深入分析，以突出搜索算法带来的改进、当前的局限性以及未来的研究方向。
我们的代码和模型已在 jykoh.com/search-agents 公开发布。
1. 引言
构建能够自主感知、规划和行动的智能体一直是人工智能研究的长期目标（Russell & Norvig, 1995；Franklin & Graesser, 1996）。近年来，具备强大通用能力的大型语言模型（LMs）的出现，为构建语言引导的自主代理以自动执行计算机任务奠定了基础。然而，即便是当前最先进的 LM 代理，其性能仍远不及人类。
在现实世界的网页基准测试 WebArena（Zhou 等，2024b）和 VisualWebArena（Koh 等，2024）上，人类的任务成功率分别为 78% 和 89%，但即便是最新的前沿模型，其成功率通常低于 20%。现有代理的一大瓶颈在于：它们在测试时无法充分利用计算能力进行探索（exploration）和多步规划（multi-step planning）。
在开放式网页环境中，搜索和规划至关重要，因为潜在的动作空间（即网页上所有可执行的操作）远大于大多数视频游戏或基于文本的模拟器。在此类任务中，通常存在多种合理的操作序列需要按顺序执行，以达成目标。高效地探索并裁剪（prune）轨迹对于任务成功至关重要。
在人工智能系统中，一种常见且有效的方式是搜索（Search）：通过迭代地构建、探索和裁剪中间状态及潜在解的图结构，从而优化决策过程（Newell 等, 1959；Laird, 2019；Silver 等, 2016）。搜索算法的有效性已多次在各类游戏中得到验证，使模型在围棋（Silver 等, 2016；2017）、扑克（Brown & Sandholm, 2018；2019）和外交游戏（Gray 等, 2020）中达到了或超越了人类水平。
如何将搜索应用于计算机任务自动化？
在网页导航等任务中，搜索空间极其庞大，且与游戏不同，没有明确的奖励或胜利条件。为了解决此问题，我们提出了一种新方法，使自主网页代理能够在交互式网页环境中构建并搜索轨迹图。该搜索过程基于真实环境空间，并利用环境反馈进行引导。
我们的方法使代理能够在测试时探索更多潜在的有前景轨迹，通过显式的探索（explicit exploration）和多步规划来减少不确定性。
我们的贡献：
- 首次 证明了推理时搜索（Inference-Time Search）可以提高自主代理在现实网页环境中的成功率。
- 针对这些多样化环境中缺乏明确奖励的问题，我们提出了一种基于模型的价值函数（model-based value function），用于指导最佳优先搜索（best-first search）。
- 该价值函数通过**多模态语言模型（multimodal LM）**对代理的观察结果进行推理，生成细粒度的评分，以有效指导搜索过程。
实验结果：
我们的实验表明，该搜索过程可以与现有语言模型代理互补，使其在更复杂、需要更长规划的任务中表现更优。
- 在 VisualWebArena（Koh 等，2024）上，搜索使 GPT-4o（OpenAI, 2024）代理的成功率相较无搜索基线提升 39.7%，并达到了26.4% 的最新最先进（SOTA）成功率。
- 在 WebArena（Zhou 等，2024b）上，搜索同样带来了 28.0% 的相对提升，使成功率达到了 19.2%，展现出强劲的竞争力。
此外，我们的研究表明，该搜索方法的性能随着测试时计算资源的增加而进一步提升，说明搜索过程可随计算能力扩展并带来更好的效果。
我们的代码和模型已公开发布，详见 jykoh.com/search-agents。
2. 背景
2.1 真实模拟网页环境
为构建由大型语言模型（LMs）驱动的自主网页代理，许多早期研究致力于开发评估基准，以衡量模型在网页任务上的进展。
- Mind2Web（Deng 等，2023）是一个评估基准，用于衡量前沿模型在静态网页上的动作预测能力。
- VisualWebBench（Liu 等，2024b）引入了一个多模态基准，用于评估模型对网页内容的理解能力。
- MiniWoB（Shi 等，2017；Liu 等，2018）是首批用于网页任务的交互式模拟器，但其简化环境无法直接转化为现实世界的表现。
- WebShop（Yao 等，2022a）模拟了一个简化的电商网站，包含真实世界的数据。
- WebLINX（Lü 等，2024）提出了一个面向对话式网页导航的基准，涉及代理与人类指导员之间的交互。
- MMInA（Zhang 等，2024b）和 OSWorld（Xie 等，2024a）提出了基准来评估代理在多个计算机应用程序间执行任务的能力。
- WorkArena（Drouin 等，2024）是一个专门用于 ServiceNow 平台任务的模拟环境。
- WebArena (WA)（Zhou 等，2024b）包含 812 个任务，涵盖 5 个热门网站（购物、Reddit、CMS、GitLab、地图）的真实数据再实现。
- VisualWebArena (VWA)（Koh 等，2024）是 WebArena 的多模态扩展，包括 3 个热门网站（分类广告、Reddit、购物）的 910 个新任务。代理需要利用**视觉定位（visual grounding）**并理解图像输入，从而为多模态代理提供了真实且具有挑战性的测试环境。
由于 (V)WA 环境是目前最真实和全面的网页任务评估工具之一，我们的研究主要在 (V)WA 基准上进行实验。其环境定义如下：
E=(S,A,Ω,T)E = (S, A, Ω, T)E=(S,A,Ω,T)
其中：
- SSS：状态集合
- AAA：动作集合（见表 1）
- TTT：确定性状态转换函数，定义了动作与状态之间的关系
- III：以自然语言形式提供的任务目标，例如：“为我找到 2000 美元以下的最便宜的红色丰田汽车。”
- RRR：奖励函数，衡量代理的执行是否成功，R:S×A→{0,1}R : S \times A \to \{0,1\}R:S×A→{0,1}
我们的搜索算法在 (V)WA 网络模拟器上实现，但该方法具有通用性，适用于任何交互式环境。
2.2 语言引导的自主代理
目前，前沿的多模态语言模型（如 Google, 2023；OpenAI, 2024；Anthropic, 2024）已成为许多网页导航基准测试的最先进（SOTA）方法。
- Kim 等（2024） 证明大型语言模型可通过提示学习（prompting）在 MiniWoB++（Liu 等, 2018）上完成计算机任务，并且所需示例远少于强化学习方法。
- AutoWebGLM（Lai 等，2024）通过网页浏览数据进行课程训练，开发了基于 60 亿参数的模型，在 WebArena 上超越了 GPT-4。
- Patel 等（2024） 证明 LM 代理可以通过微调其合成数据来提升性能。
- Pan 等（2024） 发现引入自动评估器（automatic evaluator）可改进代理在 Reflexion 框架下的表现。
- Fu 等（2024） 通过从离线数据中提取领域知识，并在推理时提供给语言代理，以帮助其更好地利用相关知识。
- SteP（Sodhi 等，2024） 和 AWM（Wang 等，2024） 提出了一些策略，使代理能够动态地组合策略以完成网页任务。
在多模态领域，相关研究包括：
- WebGUM（Furuta 等，2024）对 30 亿参数的多模态模型进行微调，在 MiniWoB 和 WebShop 上取得了强劲表现。
- SeeAct（Zheng 等，2024）证明 GPT-4V（Yang 等，2023b）和 Gemini（Google，2023）可以用于网页任务。
- ICAL（Sarch 等，2024）利用演示数据和人类反馈建立多模态记忆，提升了 VisualWebArena 的表现。
我们的推理时搜索方法与这些基于 LM 代理的技术兼容，能够在现有代理的基础上进一步提升性能。
2.3 搜索与规划
我们的研究灵感来源于计算机科学中关于搜索与规划的丰富历史。
- 经典的搜索算法如**广度优先搜索（BFS）、深度优先搜索（DFS）以及 *A 搜索（Hart 等, 1968），在人工智能系统中长期被应用。
- Newell 等（1959）和 Laird（2019）将目标导向行为视为在状态空间中的搜索问题。
- Dean 等（1993）和 Tash & Russell（1994）提出了基于有限搜索视野的规划算法，并通过启发式扩展策略改进计划质量。
- 深蓝（Deep Blue）（Campbell 等, 2002）采用大规模并行树搜索，击败了国际象棋世界冠军卡斯帕罗夫。
- Pluribus（Brown & Sandholm, 2019） 利用搜索在多人扑克中制定最佳策略。
在深度学习领域，搜索算法与神经网络组件的结合已成功在多种游戏中实现超人类水平：
- 蒙特卡洛树搜索（MCTS） 被用于 AlphaGo（Silver 等，2016）和 AlphaGo Zero（Silver 等，2017）等系统，使其在围棋上达到超人水平。
- Gray 等（2020）通过一步前瞻搜索，在无聊天外交游戏中取得最先进的性能。
最近，Yao 等（2024）和 Besta 等（2024）展示了在大语言模型上应用搜索的潜力，以探索多条推理路径，提升需要复杂规划的文本任务性能。其他研究还将 MCTS 应用于数学基准（Cobbe 等, 2021）或简化环境（Yao 等, 2022a）。
与先前研究不同，我们的方法专注于真实网页环境，直接在实际环境空间（即网页）上进行搜索。这意味着我们的搜索机制不仅需要处理代理的文本输出，还需结合来自复杂环境的外部反馈，以优化代理的行为。
3. 方法
本节详细描述了搜索过程（见图 1）。在网页环境（如 (V)WA）中，成功完成任务可以被解释为导航至某个目标状态 s∗s^*s∗，其奖励函数 R(s∗)=1R(s^*) = 1R(s∗)=1。代理从初始状态 s0s_0s0（例如主页）出发，目标是通过执行一系列操作 (a0,...,at)∈A(a_0, ..., a_t) \in A(a0,...,at)∈A 导航至目标状态。每个操作都会从环境中产生新的状态 st+1∈Ss_{t+1} \in Sst+1∈S 和观察值 ot+1∈Ωo_{t+1} \in \Omegaot+1∈Ω。状态转换 st→st+1s_t \rightarrow s_{t+1}st→st+1 由确定性转换函数 T:S×A→ST: S \times A \rightarrow ST:S×A→S 控制。
大多数方法将该问题视为部分可观测的马尔可夫决策过程（POMDP），仅依赖当前观察值 oto_tot 来预测下一个操作 ata_tat。这一策略存在显著局限性：代理的错误会随着步骤的增加而积累，若在某一时刻 ttt 采取错误操作导致进入不利状态，则很难纠正。
我们的方法 旨在通过**显式搜索和回溯（backtracking）**来缓解这些问题，以识别更优的轨迹。以下各小节将描述构成搜索过程的关键组件：基础代理模型（第 3.1 节）、价值函数（第 3.2 节）和搜索算法（第 3.3 节）。
3.1 代理基础架构
目前最先进的网页代理通常通过**提示（prompting）**大型（多模态）语言模型构建（Zhou 等, 2024b; Pan 等, 2024; Fu 等, 2024; Zheng 等, 2024; Koh 等, 2024）。
一个预训练语言模型或多模态模型 fϕf_\phifϕ 接收当前网页的观察值 oto_tot，并被提示生成要执行的下一个操作 ata_tat。常见的提示技巧包括：
- ReAct（Yao 等, 2022b）：结合推理和行动
- RCI（Kim 等, 2024）：递归提示
- CoT（Chain-of-Thought） 提示（Wei 等, 2022）：多步推理增强
这些提示策略提高了代理的性能。此外，语言模型代理还支持多样化采样（如核采样，Holtzman 等, 2020），这对于在搜索过程中生成可探索的分支至关重要。
我们的搜索算法原则上可以应用于任何基础代理。第 4 节的实验表明，该搜索方法在不需重新训练或微调 fϕf_\phifϕ 的情况下，可提高推理时性能。
3.2 价值函数
我们实现了基于最佳优先搜索（best-first search）的启发式算法，该算法使用价值函数 fvf_vfv 来估计当前状态 sts_tst 的期望奖励，即 E[R(st)]E[R(s_t)]E[R(st)]。在目标状态 s∗s^*s∗ 下，该奖励应为 1。
由于模拟环境的状态 sts_tst 并不总是对代理可见（例如某些网站可能包含私有数据库条目），价值函数的计算依赖于当前和先前的观察值以及自然语言任务指令 III ：
vt=fv(I,{o1,...,ot})∈[0,1]v_t = f_v(I, \{ o_1, ..., o_t \}) \in [0,1]vt=fv(I,{o1,...,ot})∈[0,1]
在实验中，价值函数由多模态语言模型实现，通过提示语言模型使用自然语言指令和网页截图来估计当前状态的价值（详见第 4.1 节）。
3.3 搜索算法
我们提出的搜索算法是一种最佳优先搜索（best-first search）方法，其灵感来源于经典的 A* 搜索算法（Hart 等, 1968），该算法广泛应用于计算机科学中的图遍历问题。
我们使用语言模型代理来生成搜索树的候选分支，搜索过程受以下超参数控制：
- 搜索深度 ddd：最大可探索层数
- 分支因子 bbb：每个状态可生成的候选操作数
- 搜索预算 ccc：搜索最大可执行步数
- 终止阈值 θ\thetaθ：当状态得分超过阈值时停止搜索
搜索过程概述（详见图 1）：
- 在时间步 ttt，代理已执行一系列操作到达当前状态 sts_tst。
- 初始化前沿集合 F←{}F \leftarrow \{\}F←{}（使用最大优先队列存储待评估状态），最佳状态 st^←st\hat{s_t} \leftarrow s_tst^←st，当前最佳轨迹得分 vt^←0\hat{v_t} \leftarrow 0vt^←0，搜索计数器 s←0s \leftarrow 0s←0。
- 每次迭代，弹出下一个待评估状态 sps_psp 并计算其得分： vp=fv(I,{o1,...,op})v_p = f_v(I, \{ o_1, ..., o_p \})vp=fv(I,{o1,...,op})
- 如果 vpv_pvp 优于当前最佳分数 vt^\hat{v_t}vt^，则更新最佳状态： st^←sp若 vp>vt^\hat{s_t} \leftarrow s_p \quad \text{若 } v_p > \hat{v_t}st^←sp若 vp>vt^ vt^←max(vt^,vp)\hat{v_t} \leftarrow \max(\hat{v_t}, v_p)vt^←max(vt^,vp)
- 检查终止条件：如果 vp≥θv_p \geq \thetavp≥θ 或 s≥cs \geq cs≥c，则停止搜索并导航到最佳状态 st^\hat{s_t}st^。
- 如果当前分支深度未超过最大深度（即 ∣(s0,...,sp)∣<d|(s_0, ..., s_p)| < d∣(s0,...,sp)∣<d），从语言模型代理 fϕf_\phifϕ 中生成 bbb 个候选操作 {ap1,...,apb}\{ a_p^1, ..., a_p^b \}{ap1,...,apb}，并将执行后新状态加入前沿集合： F←F∪(vp,spi)for i=1,...,bF \leftarrow F \cup (v_p, s_p^i) \quad \text{for } i = 1, ..., bF←F∪(vp,spi)for i=1,...,b
- 若未满足终止条件，则回溯至前沿集合中的下一个最优状态并重复该过程。
4. 实验
我们在 910 个 VisualWebArena (VWA) 任务 和 812 个 WebArena (WA) 任务 上进行了实验。这些任务涵盖多个多样化且真实的网页环境，包括：
- VWA（VisualWebArena）：分类广告、Reddit、购物网站环境
- WA（WebArena）：购物网站、CMS、Reddit、GitLab 和地图环境
4.1 实现细节
基线代理模型
我们的搜索算法与大多数现成的语言模型代理兼容。在本研究中，我们测试了几种较为通用的**基于提示（prompt-based）**的代理，并将结合特定领域技术（Fu 等, 2024; Sodhi 等, 2024）的方法留作未来工作。
我们运行了多个基于提示的代理基线，采用不同的输入格式（完整提示见附录），具体包括：
-
多模态 SoM 代理
- 针对能够接收多图像-文本输入的多模态模型（例如 GPT-4o (OpenAI, 2024)），我们使用 Koh 等（2024）提出的多模态代理，并采用相同的提示。
- 在网页上应用 Set-of-Marks (SoM) 标记法（Yang 等, 2023a），即为网页上的所有交互元素添加边界框和唯一 ID。
- 代理的输入包括带有 SoM 标记的网页截图，以及对应页面元素的文本描述及其 SoM ID。
-
基于增强描述的代理
- 针对非多模态的基础模型（如 Llama-3-70B Instruct (Dubey 等, 2024)），我们使用与 Koh 等（2024）相同的增强描述代理。
- 通过预训练的图像描述模型（在本实验中使用 BLIP-2，Li 等, 2023），为网页上的每个图像生成描述。
- 从网页中提取**无障碍树（accessibility tree）**表示，并将其作为语言模型的输入观察。
-
纯文本代理
- 在 WebArena（不需要视觉信息）环境下，我们运行了纯文本代理，使用 Zhou 等（2024b）的提示对 GPT-4o 和 Llama-3-70B Instruct 进行评估。
- 该模型使用网页的无障碍树作为输入观察，但与增强描述代理不同的是，它不包含图像说明。
搜索参数
我们分别在使用与不使用搜索的情况下运行这些代理。搜索的参数设置如下：
- 深度（d）：5
- 分支因子（b）：5
- 搜索预算（c）：20
- 最大执行步骤：5
由于计算和预算限制，我们限制了最大步骤数量。尽管如此，我们预计增加这些参数可能会进一步提高结果（详见第 5.1 节关于搜索参数扩展的结果）。
值得注意的是，较严格的最大动作限制意味着某些任务可能难以完成。例如，VWA 中的“困难”任务通常需要人类执行 10 次或更多的操作。然而，即使搜索被限制在 5 次最大操作，GPT-4o+搜索的性能仍然显著优于不使用搜索、最大操作为 30 的 GPT-4o 基线。
操作获取
我们使用核采样（nucleus sampling）（Holtzman 等, 2020），在所有实验中设置温度为 1.0，top-p 为 0.95。
在每个执行步骤中，我们使用思维链（CoT）推理（Wei 等, 2022），生成 20 个候选操作，并统计每个候选操作的出现次数。然后，选择出现频率最高的前 bbb 个操作进行分支。
价值函数
如第 3.2 节所述，我们需要一个价值函数来评估当前状态 sts_tst 是否接近目标状态。
价值函数的实现方式：
- 使用多模态语言模型，对以下输入进行提示：
- 任务指令 III
- 代理执行轨迹的网页截图
- 代理的先前操作
- 当前页面的 URL
完整的提示内容在附录 A.3.2 中提供。
多模态 LLM 的输出类别：
- 成功（Success）：状态得分为 1
- 失败（Failure）：状态得分为 0
- 部分成功（On trajectory towards success）：状态得分为 0.5
- 无效输出（Invalid output）：状态得分为 0
为了获得更细粒度和可靠的评分，我们借鉴了自洽提示（self-consistency prompting）（Wang 等, 2023）的思路，进行多次采样，以减少噪声和提高稳定性。
推理路径和搜索结果分析
在本节中，我们将详细描述在多模态语言模型（LLM）中执行推理路径的计算方式，并总结实验结果。
推理路径（Reasoning Paths）
我们使用 思维链（CoT, Chain-of-Thought）提示（Wei et al., 2022）来提示多模态 LLM，以探索不同的推理路径。具体流程如下：
-
路径采样：
- 我们使用 GPT-4o 进行 祖先采样（Ancestral Sampling），设置温度为 1.0，top-p 为 1.0。
- 从 GPT-4o 模型中采样 20 条不同的推理路径。
-
最终值计算：
- 将 20 条推理路径的输出值进行平均，计算最终分配给状态 sts_tst 的值，该值用于启发式最佳优先搜索（best-first search heuristic）。
-
计算开销：
- 在我们的实现中，调用**价值函数（value function）**的成本显著低于预测下一个操作的成本。
- 由于动作预测需要更多的输入 token（包括 few-shot 示例和网页表示），我们估算 GPT-4o + SoM 代理执行动作预测的 API 成本约为计算价值函数的 2 倍。
4.2 结果（Results）
我们的实验结果总结如下（见表 2）：
-
引入搜索后，成功率显著提高：
- 在 VisualWebArena（VWA） 上，添加搜索后，GPT-4o + SoM 代理的成功率相对提高 39.7%（从 18.6% 提升至 26.4%），设立了新的基准。
- 在 WebArena（WA） 上，成功率相对提升 28.0%（从 15.0% 提升至 19.2%），表现与其他基于提示的代理具有竞争力。
-
在更弱的基础模型上，搜索同样带来了显著改进：
- 对于 Llama-3 caption-augmented 代理，引入搜索后，其在 VWA 上的成功率提升 119.7%（从 7.6% 提升至 16.7%）。
- 在 WA 上，纯文本的 Llama-3 代理 也实现了 32.2% 的提升（从 7.6% 提升至 10.1%）。
- 在引入搜索后，Llama-3-70B-Instruct 代理 的成功率接近未使用搜索的最先进多模态模型，表明其可能成为未来开发中具有成本效益的选择。
-
广泛适用性：
这些结果表明，无论模型规模或能力如何，我们提出的方法均表现良好，证明了其在不同场景中的通用性和有效性。
5. 分析（Analysis）
5.1 消融实验（Ablations）
我们在 200 个 VWA 任务子集 上进行了多项消融实验，这些任务包括：
- 100 个购物（Shopping）任务
- 50 个 Reddit 任务
- 50 个分类广告（Classifieds）任务
搜索预算（Search Budget）
- 在图 2 中，我们绘制了搜索预算对成功率的影响，测试的搜索预算取值为 c∈{0,5,10,15,20}c \in \{0, 5, 10, 15, 20\}c∈{0,5,10,15,20}。
- 所有实验的搜索参数固定为：
- 搜索深度（depth） d=5d = 5d=5
- 分支因子（branching factor） b=5b = 5b=5
- 搜索预算指定了在每个步骤中执行的最大节点扩展数。例如，搜索预算为 10 时，表示最多可以扩展 10 个节点。
扩展实验分析与结果
搜索预算的影响
在实验中，我们观察到 成功率（Success Rate, SR） 随着搜索预算的增加而提高：
- 少量搜索（c=5） 已显著提升成功率 30.6%，从 24.5% 提升到 32.0%。
- 较大搜索预算（c=20） 进一步提高成功率 51.0%，从 24.5% 提升到 37.0%。
- 这些结果表明，增加搜索预算 能够显著提升任务的成功率，因此进一步扩展搜索预算来研究其趋势是未来值得探索的方向。
搜索深度与宽度
实验中，我们对搜索的**分支因子（branching factor, b）和最大深度（maximum depth, d）**进行了消融实验，结果总结如下：
- 成功率随着搜索树规模的增加（无论是宽度 bbb 还是深度 ddd 的增加）而提高。
- 同时增加 bbb 和 ddd 是获得高性能的必要条件，单独增加其中一个因素的效果较为有限。
不同价值函数的影响
我们在不同的价值函数（value functions）配置下对 GPT-4o 代理进行了实验，结果如下表所示：
| 价值函数 | 成功率（↑） |
|---|---|
| 无搜索（基线） | 24.5% |
| LLaVA（w/ SC, n=20） | 30.0% |
| GPT-4o（无自一致性） | 28.5% |
| GPT-4o（w/ SC, n=5） | 32.5% |
| GPT-4o（w/ SC, n=20） | 37.0% |
| 真实奖励（ground truth） | 43.5% |
- 结果显示，使用 GPT-4o 作为价值函数优于 LLaVA-v1.6-34B 模型，成功率从 30.0% 提升到 37.0%。
- 使用真实奖励信号（ground truth reward）实现了 43.5% 的成功率，表明仍有改进空间，可以通过训练更精确的价值函数来进一步提升性能。
- 自一致性（Self-Consistency, SC） 是搜索算法性能的关键，启用 SC 后成功率从 28.5% 提升到 37.0%。
- 这一改进归因于 SC 能够对多个推理路径进行边际化处理，从而在状态评估时减少噪声。
5.2 成功率分析（Success Rate Breakdown）
VWA 基准测试根据任务的操作难度提供了标注，分为**简单（easy）、中等（medium）、困难（hard）**三类。任务难度是由人类标注员根据完成任务所需的平均操作次数估算得出：
-
简单任务（3步以内）：
- 无搜索：34.2% → 搜索后：42.3%（+24% 提升）
-
中等任务（4-9步）：
- 无搜索：12.7% → 搜索后：22.2%（+75% 提升）
-
困难任务（10步以上）：
- 无搜索：10.2% → 搜索后：14.9%（+47% 提升）
这些结果表明，引入搜索在各个难度水平上均有显著改进，特别是在中等和困难任务上的提升尤为明显，这进一步证明搜索能够帮助代理更好地规划复杂的任务路径。
搜索改进对不同难度任务的影响
搜索在所有难度级别的任务上都能提高性能，但对于中等难度任务的提升最为显著，成功率相对提高了 75%（从 12.7% 提升至 22.2%）。
这种提升可能是由于我们设定的搜索参数（最大深度 d=5d=5d=5）非常适合处理大部分中等难度的任务。
- 对于难度较高的任务，要进一步提高成功率可能需要搜索更深的树结构。
- 对于简单任务，由于通常不需要多步规划（部分任务仅需 1-2 步即可完成），搜索带来的改进相对较小，且基线模型的成功率已经较高。
网站类别的成功率分析
下表总结了在 VisualWebArena（VWA） 和 WebArena（WA） 基准测试中不同网站的成功率：
- 在 VWA 基准测试中，Classifieds 和 Shopping 网站的成功率增长最为显著，分别提升了 44% 和 45%。
- 在 WA 基准测试中，CMS 网站的成功率相对提高了 50%。
这些结果表明，我们提出的方法在各种网站类型上的普适性，具有广泛的适用性。
5.3 质量结果分析
在本节中，我们讨论代理在任务轨迹中的一些典型示例，并分析搜索如何帮助解决某些失败模式。
更稳健的多步规划
许多 VWA 和 WA 任务要求代理具备长期记忆功能，以跟踪多个先前的操作和观察结果。
在没有搜索的情况下，常见的失败模式包括：
- 代理撤销了先前的操作，或者陷入无限循环（例如在网页间来回跳转）。
- 例如，在 VWA Shopping 任务 #256 中，代理需要将同一品牌的两种不同类型的罐头水果添加到比较列表。
- 基线代理成功添加了第一个物品，但在步骤 3 时返回到首页，导致混乱并最终失败。
- 搜索的引入使代理能够探索更多可能的路径并在失败时回溯。具有搜索的 GPT-4o 代理能够找到正确的多步路径，包括输入搜索查询并添加第二个正确的物品。
解决不确定性
使用语言模型生成动作时，由于文本生成的不确定性，第一次采样的动作不一定总是最优的。
- 搜索允许代理通过在模拟环境中执行生成的动作来评估每个选项，并根据环境反馈进行更明智的决策。
- 例如，在 VWA Classifieds 任务 #48 中，代理需要找到包含特定图片的帖子。
- 如果代理在每一步都执行第一次采样的动作，则最终会失败。
- 搜索使代理能够执行所有可能的动作并接收环境反馈，从而找到最佳成功路径。
5.4 方法的局限性
尽管引入搜索可以显著提高语言模型代理在网页任务中的成功率，但它也存在以下局限性：
1. 搜索的计算成本
- 搜索的引入会显著增加推理时间，因为代理必须执行更多的探索，并因此需要更多的语言模型调用。
- 例如，当搜索预算为 c=20c = 20c=20 时，代理在每次搜索迭代中最多可以扩展 20 个状态，这可能会导致比没有搜索的代理多 20 倍 的 LM 调用。
- 需要权衡搜索参数 bbb、ddd 和 ccc 之间的关系，以在性能提升与任务完成时间之间找到平衡。
2. 回溯的环境成本
- 目前的方法通过重置环境并重新执行动作序列来实现回溯，这可能会引入额外的延迟。
- 在某些情况下，简单地执行“返回（go back）”操作可能会导致页面丢失关键信息，如滚动偏移量和已输入的文本。
- 这些额外的环境调用会导致开销增加，尤其是在高成本的环境中。
3. 破坏性操作的风险
- 在现实应用中，需要限制搜索空间以避免执行不可逆的“破坏性操作”，例如在电商网站下单，这类操作难以自动撤销。
- 解决方案可能包括：
- 使用分类器检测何时存在破坏性操作，并防止该节点的扩展。
- 如果对应用程序有特定领域知识（例如某些页面禁止访问），可以手动强制执行规则。
- 在树搜索中，可以将约束直接整合到价值函数中，以防止执行潜在危险的操作。
6. 结论
在本研究中，我们提出了一种推理时搜索算法，旨在提升语言模型代理在真实网页任务上的能力。
- 该方法集成了最佳优先树搜索（best-first tree search），使代理能够探索并评估多种动作轨迹，从而在网页任务中实现更优的性能。
- 这是首次在**（Visual）WebArena**基准测试中证明搜索能够显著提高 LM 代理的成功率。
- 我们的方法是通用的，未来可扩展至其他领域，如编程和自动化任务。
原文地址：https://blog.csdn.net/feifeikon/article/details/145288986
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！