《AI Agent 技术原理与架构·决策、记忆与学习》5.1 树搜索与 Beam

Beam Search 的宽度是一个成本旋钮。本节用带噪声启发式的完整树做确定性实验,比较宽度 1 到 64 的节点评估次数与命中率:窄束便宜但容易剪掉最优分支,宽束接近穷举。实验给出命中率随宽度上升、成本线性上升的曲线,并讨论 Agent 计划搜索中宽度、评分与剪枝依据的选择,以及 W1/W2/W3 的取舍。

以下数字均为教学假设,不构成对任何真实系统或供应商的承诺。树的规模、启发式噪声与命中率只用于展示搜索宽度与成本的关系,不代表任何生产环境的最优配置。

当 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 。

常见错误与边界

  1. 把宽度当质量保证。 宽度只降低漏掉最优的概率,不消除;噪声大时 $w=32$ 也会漏。
  2. 只看命中率,不看质量比。 窄束可能经常找到近优解;如果任务接受近优,命中率会高估失败。
  3. 忽略启发式质量。 评分随机时,Beam 退化为随机保留,加宽只是增加采样量。
  4. 每层评分口径不一致。 浅层用模型自评、深层用测试,分数不可比,剪枝结果不可解释。
  5. 剪掉所有多样性。 前 $w$ 个候选如果是同一方案的变体,加宽没有收益。
  6. 在不可逆动作上做 Beam。 W3 的搜索必须停在方案层;把执行放进搜索树,等于用生产环境做试错。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图