Branch-and-Browse: Efficient and Controllable Web Exploration with Tree-Structured Reasoning and Action Memory

Idea

Branch-and-Browse 将网页操作组织为带动态 subtasks 的 tree search，并结合 nearest-URL replay、background reasoning 与 page action memory。它在分支探索中保持局部目标与历史动作记录，以更少重复操作恢复状态、比较路径并推进长任务。

Research Problem

线性 ReAct 缺少有效回溯，普通网页树搜索又要频繁重放大量页面与动作；跨分支的全局历史容易纠缠，而只保存 URL 丢失表单、tab 等中间状态。预先分解的子任务还可能与实际站点结构不符，导致长时间追逐不存在的入口。

Insight

网页探索的控制粒度应同时包括子目标和页面状态：子目标给搜索值函数明确参照，page-level memory 说明已经尝试过什么，局部 replay 恢复必要交互。这使“换一条分支”不必同时丢失已学网站结构或重走整段历史。

Method

1. task_decomposition 生成子目标，Subtask Manager 在每轮根据 observation 和轨迹更新当前目标，即使未取得进展也可重述；满足局部 success predicate 后推进下一目标。
2. 在页面为节点、动作作边的树上维护 frontier，由 LLM judge 结合当前 subtask、历史与 memory 评分，扩展最高值节点并生成多个候选动作，剪除低值或重复分支。
3. 回溯时加载目标状态前最近的 cached URL，只重放其后的必要动作；background reasoning 先分析未激活节点的 DOM/URL，对明确链接的 click 可预扩展，其余 type/select 等等到 live context 执行。
4. 按 URL 缓存 objective、progress summary、reason–action history、DOM/screenshot 与 tried actions，记录结果和相关性，在重访与重新分解任务时恢复上下文。
5. 以 WebArena 与 VisualWebArena 测任务成功和执行效率，并消融 replay、background reasoning、depth 与 branching factor，分辨搜索控制与加速机制的贡献。