以下数字均为教学假设,不构成对任何真实系统或供应商的承诺。树的规模、启发式噪声与命中率只用于展示搜索宽度与成本的关系,不代表任何生产环境的最优配置。
当 Agent 面对的不是一条计划,而是多个可选分支时,搜索就出现了。最直接的做法是穷举:把每个分支都展开,选出最好的叶子。问题是成本按分支因子指数增长,几步之后就无法接受。Beam Search 的折中是:每一层只保留评分最高的 $w$ 个节点,其余剪掉。$w$ 就是宽度,也是唯一需要调的旋钮。
宽度调小,成本低,但可能把包含最优解的分支提前剪掉;宽度调大,命中率上升,成本也上升,最后退化成穷举。这一节要回答的不是“宽度取多少”,而是宽度买到的是什么、代价是什么、在什么条件下值得买。
Beam Search 的形式
设树的分支因子为 $b$,深度为 $d$。第 $\ell$ 层的候选集合记为 $B_\ell$,初始时 $B_0$ 只含根节点。Beam Search 的递推是:
$$
B_{\ell+1} = \text{top-}w \left( \bigcup_{s \in B_\ell} \text{children}(s) \right)
$$
排序依据是每个节点的启发式评分 $h(s)$。每一层需要展开 $|B_\ell|$ 个节点、评估 $b|B_\ell|$ 个子节点。总评估次数约为:
$$
C(w) = \sum_{\ell=0}^{d-1} b \cdot \min(w, b^\ell)
$$
这个式子里有两个关键事实。第一,成本对 $w$ 是线性的,对深度 $d$ 也是线性的;它不是指数,因为每层只保留固定数量的节点。第二,当 $w \ge b^{d-1}$ 时,Beam 等价于穷举,成本也退化为穷举成本。
命中率定义为:最终保留下来的叶子里,是否包含全局最优叶子。它衡量的是搜索有没有“找到最好的”,而不是“找到还行的”。这两个指标在 Agent 场景里经常被混为一谈:如果验证器只要求测试通过,那么接近最优的计划也可能合格;如果要求严格最优,接近最优就是失败。
| 概念 | 定义 | 工程含义 |
|---|---|---|
| 分支因子 $b$ | 每个节点生成多少个候选 | 一次生成几个方案 |
| 宽度 $w$ | 每层保留多少个节点 | 同时维护几条思路 |
| 启发式 $h$ | 对子树价值的估计 | 用模型或验证器打分 |
| 命中率 | 是否保住全局最优叶子 | 搜索质量的严格指标 |
| 质量比 | 找到的最优值与全局最优值之比 | 容忍近优时的指标 |
最小实验:宽度从 1 走到 64
实验构造一棵深度 4、分支因子 4 的完整树,共 256 个叶子。叶子的真实效用由固定公式生成,内部节点的启发式评分等于其子树最优效用加上一个有界噪声(±120)。同一批 20 棵树用于每个宽度,统计平均评估次数、命中率与平均质量比。
# file: agp_lab/tree_search.py | write
# tier: 3
# verify: python3 -m unittest tests.test_tree_search
"""Beam Search 的最小实验:宽度如何影响命中率与节点评估成本。
树是一棵完整的 b 叉树,叶子有真实效用,内部节点有一个带噪声的启发式
评分。Beam Search 每层只保留启发式评分最高的 w 个节点;穷举搜索保留
全部节点。实验在固定的一批树上比较不同宽度的命中率(是否找到全局最优
叶子)与节点评估次数。
启发式噪声是刻意加入的:如果启发式完全准确,宽度为 1 也能命中,实验
就失去意义。所有参数均为教学假设。
"""
from __future__ import annotations
from dataclasses import dataclass
DEFAULT_DEPTH = 4
DEFAULT_BRANCHING = 4
DEFAULT_NOISE = 120
DEFAULT_SEEDS = 20
@dataclass(frozen=True)
class Node:
path: str
depth: int
children: tuple["Node", ...]
utility: int
heuristic: int
@property
def is_leaf(self) -> bool:
return not self.children
def _noise(path: str, seed: int, amplitude: int) -> int:
digest = sum((index + 1) * ord(char) for index, char in enumerate(path))
span = 2 * amplitude + 1
return ((digest * 37 + seed * 101) % span) - amplitude
def _lcg(seed: int) -> int:
return (seed * 1103515245 + 12345) % (2**31)
def make_tree(
seed: int,
depth: int = DEFAULT_DEPTH,
branching: int = DEFAULT_BRANCHING,
noise: int = DEFAULT_NOISE,
) -> Node:
"""构造一棵确定性的完整树;同一个 seed 永远得到同一棵树。"""
if depth < 1:
raise ValueError("depth 必须至少为 1")
if branching < 2:
raise ValueError("branching 必须至少为 2")
if noise < 0:
raise ValueError("noise 不能为负")
state = _lcg(seed + 1)
def build(path: str, level: int) -> Node:
nonlocal state
if level == depth:
state = _lcg(state)
utility = state % 1000
return Node(path, level, (), utility,
utility + _noise(path, seed, noise))
children = tuple(build(f"{path}{index}", level + 1) for index in range(branching))
utility = max(child.utility for child in children)
return Node(path, level, children, utility,
utility + _noise(path, seed, noise))
return build("", 0)
@dataclass(frozen=True)
class SearchResult:
best_utility: int
expanded: int
evaluations: int
def beam_search(root: Node, width: int) -> SearchResult:
"""每层按启发式评分保留前 width 个节点。
expanded 是被展开的内部节点数;evaluations 是生成的子节点数,
也就是实际需要打分的候选数。
"""
if width < 1:
raise ValueError("width 必须至少为 1")
frontier: list[Node] = [root]
expanded = 0
evaluations = 0
while not frontier[0].is_leaf:
candidates: list[Node] = []
for node in frontier:
expanded += 1
evaluations += len(node.children)
candidates.extend(node.children)
candidates.sort(key=lambda node: (-node.heuristic, node.path))
frontier = candidates[:width]
best = max(node.utility for node in frontier)
return SearchResult(best_utility=best, expanded=expanded, evaluations=evaluations)
def exhaustive_search(root: Node) -> SearchResult:
"""穷举搜索:展开所有内部节点,返回全局最优。"""
expanded = 0
evaluations = 0
stack = [root]
while stack:
node = stack.pop()
if node.is_leaf:
continue
expanded += 1
evaluations += len(node.children)
stack.extend(node.children)
return SearchResult(root.utility, expanded, evaluations)
@dataclass(frozen=True)
class Row:
width: int
mean_evaluations: float
hit_rate: float
mean_quality: float
def evaluate(
widths: tuple[int, ...] = (1, 2, 4, 8, 16, 32, 64),
seeds: int = DEFAULT_SEEDS,
depth: int = DEFAULT_DEPTH,
branching: int = DEFAULT_BRANCHING,
noise: int = DEFAULT_NOISE,
) -> list[Row]:
"""在 seeds 棵不同的树上统计每个宽度的平均成本与命中率。"""
rows: list[Row] = []
for width in widths:
hits = 0
quality = 0.0
evaluations = 0
for seed in range(seeds):
root = make_tree(seed, depth, branching, noise)
result = beam_search(root, width)
hits += int(result.best_utility == root.utility)
quality += (result.best_utility + 1) / (root.utility + 1)
evaluations += result.evaluations
rows.append(
Row(
width=width,
mean_evaluations=evaluations / seeds,
hit_rate=hits / seeds,
mean_quality=quality / seeds,
)
)
return rows
if __name__ == "__main__":
exhaustive = exhaustive_search(make_tree(0))
print(f"{'宽度':<8}{'节点评估':>10}{'命中率':>10}{'平均质量':>10}")
for row in evaluate():
print(
f"{row.width:<8}{row.mean_evaluations:>10.1f}"
f"{row.hit_rate:>10.2f}{row.mean_quality:>10.3f}"
)
print(f"{'穷举':<8}{exhaustive.evaluations:>10}"
f"{1.0:>10.2f}{1.0:>10.3f}")
运行:
cd private/labs/agp-lab
python3 -m agp_lab.tree_search
输出:
宽度 节点评估 命中率 平均质量
1 16.0 0.05 0.939
2 28.0 0.05 0.960
4 52.0 0.35 0.990
8 84.0 0.60 0.998
16 148.0 0.80 0.998
32 212.0 1.00 1.000
64 340.0 1.00 1.000
穷举 340 1.00 1.000
这张表最值得读的不是“宽度越大越好”,而是三组数字之间的关系。
命中率在 $w=4$ 之后才开始明显上升。 $w=1$ 和 $w=2$ 都只有 5% 的命中率,$w=4$ 到 35%,$w=8$ 到 60%,$w=16$ 到 80%,$w=32$ 才到 100%。原因是启发式噪声足以让最优分支在某一层掉出前两名;只要掉出一次,后面再宽也救不回来。宽度买的是对启发式错误的容忍次数,不是单纯的分支数量。
成本是线性的,但基数是分支因子。 从 $w=1$ 的 16 次评估到 $w=32$ 的 212 次,成本涨了 13 倍多;而穷举是 340 次。$w=32$ 用 62% 的穷举成本买到了这批树上的 100% 命中率。但这个 100% 只属于这 20 棵树和这组噪声参数,不是保证。把噪声幅度调大,$w=32$ 也会开始漏。
平均质量比远高于命中率。 $w=1$ 的命中率只有 5%,平均质量比却有 0.939。意思是:窄束经常找不到全局最优,但找到的叶子通常只差一点。这对 Agent 很重要——如果计划只要“能跑通测试”就算成功,窄束的实际失败率远低于 95%;如果计划必须严格最优,窄束几乎不可用。先定义成功判据,再选宽度。
还有一个被成本表掩盖的问题:评估次数不等于实际成本。真实系统里,不同节点的打分成本可能差很多,评估可以并行,剪枝还会带来额外的上下文组装与状态管理开销。实验只比较“评估了多少个子节点”,不比较延迟、金额或 token。
启发式才是真正的杠杆
Beam 的效果几乎完全取决于 $h$。两个极端可以说明这一点:
- 如果 $h$ 完全准确,$w=1$ 就能沿着最优路径走到叶子,宽度没有意义。
- 如果 $h$ 完全随机,Beam 就退化成每层随机保留 $w$ 个节点,宽度只能靠数量覆盖,和随机采样没有本质区别。
真实系统落在两者之间。模型打分有噪声,验证器可能只看局部。于是宽度的作用变成“给启发式的错误留冗余”。这也解释了为什么提高宽度往往不如改进评分:把 $h$ 的噪声从 ±120 降到 ±30,$w=4$ 可能就能达到原来 $w=16$ 的命中率,成本却低得多。
Agent 里常见的评分来源有三类:模型自评、外部验证器、执行反馈。模型自评便宜但有系统性偏差;验证器准确但可能贵或慢;执行反馈最可信,但只能对已执行的节点使用。Beam 的评分函数最好把三者组合起来,并且明确每一层的评分依据是否一致。如果浅层用模型自评、深层用测试结果,分数就不可比,剪枝会失真。
三条负载的宽度取舍
| 负载 | 树的形状 | 推荐宽度 | 评分依据 | 主要风险 |
|---|---|---|---|---|
| W1 检索问答 | 浅、分支少 | 1–2 | 检索相关度 + 引用可核对性 | 漏掉一个关键文档 |
| W2 代码修复 | 深、分支多 | 4–8 | 测试通过 + 静态检查 | 剪掉唯一能修好的补丁 |
| W3 运维处置 | 浅、动作不可逆 | 只搜索方案,不搜索执行 | 审批规则 + 健康检查 | 把不可逆动作放进搜索树 |
W1 的分支通常很浅,一次检索几个候选就够,宽度 1–2 往往足够;真正的瓶颈是召回,不是搜索。W2 的树更深,一个补丁可能牵动多个文件,宽度 4–8 是常见起点;但更有效的做法是用测试作为硬验证器,把不合格分支尽早剪掉。W3 的关键区别是:搜索可以生成多个处置方案,但执行不能并行试探。重启服务不是可以“先试一条分支,失败再回退”的动作;搜索必须停在方案层,执行前进入审批。
Beam 的判据
| 判据 | 合格的样子 | 不合格的样子 |
|---|---|---|
| 宽度 | 有明确取值与依据,随负载变化 | 全局固定一个数,从不复评 |
| 评分 | 每层评分来源与口径一致 | 浅层自评、深层测试,分数混用 |
| 剪枝 | 保留多样性,避免近重复节点 | 只按分数排序,前 $w$ 个几乎一样 |
| 成本 | 统计评估次数、延迟与金额 | 只数“生成了几个方案” |
| 停止 | 有深度、预算与验证三重上限 | 搜到模型自己说停为止 |
其中“保留多样性”最容易被忽略。纯按分数剪枝时,前 $w$ 个节点可能只在措辞上不同,实际是同一个方案;这时加宽只是重复付费。一个常见的补救是给候选加去重或多样性惩罚,确保保留下来的节点覆盖不同的动作路径。
小结
- Beam Search 每层保留 $w$ 个节点,成本对宽度和深度都是线性的,不是指数。
- 宽度买的是对启发式错误的容忍;命中率在实验里从 $w=1$ 的 5% 升到 $w=32$ 的 100%。
- 平均质量比远高于命中率:窄束常找不到最优,但通常接近最优;成功判据决定宽度是否够用。
- 评分函数才是主要杠杆;改进 $h$ 往往比加宽更便宜。
- W1 用窄束,W2 用中等宽度加验证器,W3 只搜索方案、不搜索不可逆执行。
- 成本要按评估次数、延迟与金额统计,不能只数方案个数。
阅读导航:上一节:4.3 重规划 · 下一节:5.2 MCTS 。
常见错误与边界
- 把宽度当质量保证。 宽度只降低漏掉最优的概率,不消除;噪声大时 $w=32$ 也会漏。
- 只看命中率,不看质量比。 窄束可能经常找到近优解;如果任务接受近优,命中率会高估失败。
- 忽略启发式质量。 评分随机时,Beam 退化为随机保留,加宽只是增加采样量。
- 每层评分口径不一致。 浅层用模型自评、深层用测试,分数不可比,剪枝结果不可解释。
- 剪掉所有多样性。 前 $w$ 个候选如果是同一方案的变体,加宽没有收益。
- 在不可逆动作上做 Beam。 W3 的搜索必须停在方案层;把执行放进搜索树,等于用生产环境做试错。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。