测试时计算自适应分配

概述

测试时计算自适应分配（Adaptive Test-Time Compute Allocation）是近年来LLM推理优化的核心研究方向。与传统的对所有问题使用相同计算资源不同，自适应分配的核心思想是：根据问题的难度和性质，动态决定应该投入多少推理计算资源。¹

核心洞察：简单问题（如常识问答）可能只需要一次前向传播就能得到正确答案，而复杂数学证明可能需要多次采样、验证和搜索才能找到正确解。均匀分配计算资源是低效的。

关键成果：使用计算最优的自适应策略，在数学推理问题上相比 Best-of-N 基线实现超过4倍的效率提升。¹

---

1. 问题定义

1.1 形式化表述

给定一个输入提示 $x$ 和有限的测试时计算预算 $B$，目标是选择最优策略使得期望性能最大化：

$${\pi }^{\ast }=\arg \underset{\pi \in \Pi (B)}{\max }\mathbb{E}[R(x,\pi (x))]$$

其中：

• $\Pi (B)$ 是计算预算为 $B$ 的所有策略集合
• $R$ 是评估指标（如准确率）
• $\pi (x)$ 是策略 $\pi$ 对输入 $x$ 的处理结果

1.2 计算预算约束

在实际部署中，我们通常有平均计算预算约束：

$$\frac{1}{N}\sum _{i=1}^{N}c(\pi ,x_i)\le B$$

其中 $c(\pi ,x)$ 是策略 $\pi$ 处理输入 $x$ 所需的计算量。

1.3 挑战

挑战	描述
问题难度异质性	不同问题的难度差异巨大
计算-性能权衡	更多计算不一定带来更好的性价比
预算公平性	简单问题不应占用过多计算资源
动态决策	需要在推理时实时判断问题难度

---

2. 训练计算 vs 推理计算

2.1 两种改进范式

大语言模型能力的提升可以通过两条路径实现：

┌─────────────────────────────────────────────────────────────────┐
│                        模型能力提升                               │
├─────────────────────────────┬───────────────────────────────────┤
│    训练时计算扩展            │       测试时计算扩展               │
│  (Training-time Scaling)    │  (Test-time Scaling)              │
├─────────────────────────────┼───────────────────────────────────┤
│  • 增加模型参数量            │  • 多次采样                       │
│  • 增加训练数据量            │  • 搜索策略                       │
│  • 增加训练步数             │  • 验证与修正                     │
│  • 改进训练算法             │  • 迭代推理                       │
└─────────────────────────────┴───────────────────────────────────┘

2.2 训练时计算扩展

传统的缩放定律（Scaling Laws）表明，模型能力随着训练计算量的增加而提升：

$$L(N,D)\approx {\left(\frac{N_c}{N}\right)}^{{\alpha }_N}+{\left(\frac{D_c}{D}\right)}^{{\alpha }_D}+\text{const}$$

其中 $L$ 是测试损失，$N$ 是参数量，$D$ 是数据量，${\alpha }_N\approx 0.076$，${\alpha }_D\approx 0.095$。

特点：

• 一次性大投入
• 能力提升是”固定”的，对所有问题都一样
• 推理成本随模型规模线性增长

2.3 测试时计算扩展

测试时计算扩展通过在推理阶段增加计算资源来提升性能：

$$P_{\text{test}}(C_{\text{test}})\approx \alpha \cdot \log (C_{\text{test}})+\beta$$

特点：

• 按需分配，成本可控
• 能力提升是”动态”的，可以根据问题调整
• 推理延迟增加，但可以针对特定问题优化

2.4 计算等效性

Snell等人的研究表明，测试时计算可以部分替代训练时计算：

测试时配置	等效参数量增加
Best-of-16	~2-3×
迭代修正×4	~5-7×
自适应策略	~10-14×

关键发现：在FLOPs匹配的情况下，对于基础模型能达到”非平凡”成功率（>~25%）的问题，测试时计算可以超过14倍大的模型的性能。¹

2.5 权衡分析

维度	训练时计算	测试时计算
优化时机	离线（训练阶段）	在线（推理阶段）
灵活性	低（固定能力）	高（可适应问题）
成本结构	一次性大投入	按需分配
延迟	不影响推理延迟	增加推理延迟
覆盖范围	广泛（所有问题）	可聚焦（困难问题）

---

3. Best-of-N 采样与迭代修正

3.1 Best-of-N 采样

Best-of-N 是最基础的测试时计算方法：

def best_of_n(model, verifier, question: str, n: int = 16) -> str:
    """
    Best-of-N：生成N个候选答案，用验证器选择最佳
    
    参数:
        model: 语言模型
        verifier: 验证器（可以是结果奖励模型ORM）
        question: 输入问题
        n: 采样数量
    
    返回:
        得分最高的答案
    """
    candidates = []
    scores = []
    
    for _ in range(n):
        # 多次独立采样
        response = model.generate(
            question, 
            temperature=0.8,  # 高温度增加多样性
            do_sample=True
        )
        candidates.append(response)
        
        # 验证器打分
        score = verifier.score(question, response)
        scores.append(score)
    
    # 返回得分最高的答案
    best_idx = max(range(len(scores)), key=lambda i: scores[i])
    return candidates[best_idx]

局限性：

• 仅利用最终概率，忽略中间推理过程
• 对简单问题可能过度计算
• 验证器质量决定效果上限

3.2 迭代修正（Iterative Refinement）

迭代修正通过多轮生成和验证来逐步改进输出：

def iterative_refinement(
    model, 
    verifier,
    question: str, 
    max_iterations: int = 8,
    early_stop_threshold: float = 0.95
) -> str:
    """
    迭代修正：多轮生成-验证-修正
    
    核心思想：
    1. 生成当前解
    2. 验证解的质量
    3. 根据反馈修正
    4. 重复直到满意或达到最大迭代
    """
    current_solution = ""
    best_solution = ""
    best_score = 0.0
    
    for iteration in range(max_iterations):
        # 生成阶段
        if iteration == 0:
            # 首次生成
            response = model.generate(question)
        else:
            # 修正提示
            response = model.generate(
                f"问题：{question}\n"
                f"当前解答：{current_solution}\n"
                f"反馈：{feedback}\n"
                f"请修正上述解答中的错误："
            )
        
        current_solution = response
        
        # 验证阶段
        score = verifier.score(question, current_solution)
        feedback = verifier.get_feedback(question, current_solution)
        
        # 更新最佳
        if score > best_score:
            best_solution = current_solution
            best_score = score
        
        # 早停条件
        if score >= early_stop_threshold:
            break
    
    return best_solution

3.3 过程奖励模型（PRM）

与只评估最终结果的结果奖励模型（ORM）不同，过程奖励模型（Process Reward Model, PRM）能够评估推理过程中每个步骤的质量：

class ProcessRewardModel:
    """
    过程奖励模型：评估推理路径的每一步
    
    优势：
    - 能够识别推理过程中的错误步骤
    - 提供细粒度的修正反馈
    - 更好地引导搜索过程
    """
    def __init__(self, model):
        self.model = model
    
    def score_step(self, prompt: str, reasoning_so_far: str, 
                   next_step: str) -> float:
        """
        评估当前推理步骤的质量
        
        返回:
            0-1之间的分数，越高表示步骤越合理
        """
        input_text = f"问题：{prompt}\n推理：{reasoning_so_far}\n下一步：{next_step}"
        return self.model.score(input_text)
    
    def score_full_reasoning(self, prompt: str, 
                            reasoning: str) -> list[float]:
        """
        评估完整推理路径，返回每一步的分数
        
        返回:
            每一步的分数列表
        """
        steps = self._split_into_steps(reasoning)
        scores = []
        
        reasoning_so_far = ""
        for step in steps:
            score = self.score_step(prompt, reasoning_so_far, step)
            scores.append(score)
            reasoning_so_far += step + "\n"
        
        return scores
    
    def get_verbal_feedback(self, prompt: str, 
                           reasoning: str) -> str:
        """
        生成自然语言反馈，指出推理中的问题
        """
        step_scores = self.score_full_reasoning(prompt, reasoning)
        
        # 找出问题步骤
        low_score_steps = [
            (i, step, score) 
            for i, (step, score) 
            in enumerate(zip(self._split_into_steps(reasoning), 
                            step_scores))
            if score < 0.5
        ]
        
        if not low_score_steps:
            return "推理过程正确，继续。"
        
        feedback = "以下步骤可能有问题：\n"
        for idx, step, score in low_score_steps:
            feedback += f"第{idx+1}步（分数{score:.2f}）：{step[:50]}...\n"
        
        return feedback

3.4 PRM驱动的束搜索

结合PRM和束搜索，可以实现更高效的推理：

class PRMBeamSearch:
    """
    基于PRM的束搜索
    
    与标准束搜索的区别：
    - 使用PRM评估每一步而非仅评估最终结果
    - 能够更早地剪枝错误路径
    - 提供更好的中间引导
    """
    def __init__(self, model, prm: ProcessRewardModel, 
                 beam_width: int = 4, max_depth: int = 20):
        self.model = model
        self.prm = prm
        self.beam_width = beam_width
        self.max_depth = max_depth
    
    def search(self, question: str) -> str:
        """
        束搜索主流程
        """
        # 初始化：每个beam是一个(state, log_prob, step_scores)元组
        beams = [(question, 0.0, [])]
        
        for depth in range(self.max_depth):
            candidates = []
            
            for content, log_prob, step_scores in beams:
                # 生成下一步候选
                next_tokens = self.model.generate_next_tokens(content)
                
                for token, token_prob in next_tokens[:self.n_candidates]:
                    new_content = content + token
                    new_log_prob = log_prob + math.log(token_prob)
                    
                    # 使用PRM评估这一步
                    step_score = self.prm.score_step(
                        question, content, token
                    )
                    new_step_scores = step_scores + [step_score]
                    
                    # 综合评分：语言模型概率 + PRM评估
                    combined_score = (
                        0.3 * new_log_prob / (depth + 1) +
                        0.7 * sum(new_step_scores) / len(new_step_scores)
                    )
                    
                    candidates.append((
                        new_content, 
                        combined_score,
                        new_step_scores
                    ))
            
            # 剪枝：保留top-k
            beams = heapq.nlargest(
                self.beam_width, 
                candidates, 
                key=lambda x: x[1]
            )
            
            # 检查是否完成
            for content, score, _ in beams:
                if self._is_terminal(content):
                    return self._extract_answer(content)
        
        # 返回最佳beam
        return self._extract_answer(max(beams, key=lambda x: x[1])[0])

---

4. 计算最优自适应分配策略

4.1 核心思想

计算最优策略（Compute-Optimal Strategy）的核心思想是：对于每个输入，分配恰好足够的计算资源以达到目标性能，同时不超过预算约束。¹

4.2 问题难度分类

不同难度的问题应采用不同的策略：

难度级别	基础成功率	特征描述	推荐策略
简单	> 90%	模型直接输出正确	单次前向传播
中等	50-90%	多次尝试可修正	Best-of-N（N较小）
较难	25-50%	需要验证搜索	PRM引导的束搜索
困难	< 25%	需要深度探索	迭代修正+树搜索

4.3 自适应分配算法

class AdaptiveComputeAllocator:
    """
    自适应计算分配器
    
    核心算法：
    1. 估计问题难度
    2. 根据难度分配计算预算
    3. 使用合适的策略处理
    4. 动态调整（如需要）
    """
    def __init__(self, model, prm: ProcessRewardModel,
                 base_budget: int = 1.0):
        self.model = model
        self.prm = prm
        self.base_budget = base_budget
    
    def estimate_difficulty(self, question: str) -> str:
        """
        估计问题难度
        
        方法1：基于置信度
        方法2：基于问题特征
        方法3：基于快速采样
        """
        # 快速采样估计
        quick_samples = []
        for _ in range(3):
            response = self.model.generate(question, temperature=0.8)
            answer = self._extract_answer(response)
            quick_samples.append(answer)
        
        # 一致性判断
        if len(set(quick_samples)) == 1:
            return "easy"  # 高度一致，简单问题
        elif len(set(quick_samples)) == 2:
            return "medium"  # 有分歧，中等问题
        else:
            return "hard"  # 分歧大，困难问题
    
    def allocate_budget(self, difficulty: str, 
                       global_budget: float) -> int:
        """
        根据难度分配计算预算
        
        关键：困难问题分配更多资源
        """
        difficulty_budget_map = {
            "easy": 1,      # 简单问题：1个单位
            "medium": 4,    # 中等问题：4个单位
            "hard": 16,     # 困难问题：16个单位
        }
        
        return difficulty_budget_map.get(difficulty, 4)
    
    def solve(self, question: str, global_budget: float) -> str:
        """
        自适应求解
        """
        # Step 1: 估计难度
        difficulty = self.estimate_difficulty(question)
        
        # Step 2: 分配预算
        budget = self.allocate_budget(difficulty, global_budget)
        
        # Step 3: 选择策略
        if difficulty == "easy":
            return self.model.generate(question)
        
        elif difficulty == "medium":
            # 中等问题：轻度采样
            return self.best_of_n(question, n=budget)
        
        else:  # hard
            # 困难问题：PRM引导搜索
            return self.prm_beam_search(question, n_rollouts=budget)
    
    def best_of_n(self, question: str, n: int) -> str:
        """
        简化版Best-of-N
        """
        candidates = []
        for _ in range(n):
            response = self.model.generate(question)
            candidates.append(response)
        
        # 简单多数投票
        answers = [self._extract_answer(c) for c in candidates]
        return Counter(answers).most_common(1)[0][0]
    
    def prm_beam_search(self, question: str, 
                       n_rollouts: int) -> str:
        """
        PRM引导的束搜索
        """
        searcher = PRMBeamSearch(
            self.model, self.prm,
            beam_width=4,
            max_depth=n_rollouts // 4
        )
        return searcher.search(question)

4.4 AdaCompute框架

AdaCompute（Adaptive Test-Time Compute Allocation for Reasoning LLMs）提出了一种原则性的自适应计算分配框架。²

4.4.1 约束优化问题

AdaCompute将自适应分配形式化为：

$$\underset{\pi }{\max }{\mathbb{E}}_{(x,y)\sim \mathcal{D}}[\text{Acc}(\pi ,x,y)]\text{s.t.}\mathbb{E}[c(\pi ,x)]\le B$$

4.4.2 拉格朗日松弛

使用拉格朗日松弛将全局约束分解为：

$$\mathcal{L}(\pi ,\lambda )=\mathbb{E}[\text{Acc}(\pi ,x)]-\lambda (\mathbb{E}[c(\pi ,x)]-B)$$

关键洞察：对偶变量 $\lambda$ 与计算成本呈单调关系

4.4.3 闭式解

对于每个输入 $x$，最优操作 $a^{\ast }(x)$ 存在闭式解：

$$a^{\ast }(x)=\arg \underset{a}{\max }[\text{Acc}(a,x)-\lambda \cdot c(a,x)]$$

这本质上是一个准确性-成本权衡的定价问题。

4.4.4 学习路由器

训练一个轻量级分类器来预测神谕动作：

class ComputeRouter:
    """
    计算路由器：学习何时使用多少计算
    """
    def __init__(self, feature_extractor, classifier):
        self.feature_extractor = feature_extractor
        self.classifier = classifier  # 轻量级MLP
    
    def predict_action(self, question: str) -> int:
        """
        预测应该使用的计算动作
        
        返回:
            计算级别（1, 2, 4, 8, 16）
        """
        # 提取廉价特征
        features = self.feature_extractor.extract(question)
        # features可能包括：词汇数、句法复杂度、问题类型等
        
        # 预测
        action = self.classifier.predict(features)
        return action
    
    def train(self, questions, oracle_actions):
        """
        从神喻动作学习
        """
        features = [self.feature_extractor.extract(q) for q in questions]
        self.classifier.fit(features, oracle_actions)

4.5 策略选择流程图

                    ┌─────────────┐
                    │   输入问题   │
                    └──────┬──────┘
                           │
                           ▼
                    ┌─────────────┐
                    │  难度估计   │
                    │ (采样/特征)  │
                    └──────┬──────┘
                           │
              ┌────────────┼────────────┐
              │            │            │
              ▼            ▼            ▼
         ┌────────┐  ┌────────┐  ┌────────┐
         │ 简单   │  │ 中等   │  │ 困难   │
         │(高一致) │  │(中一致) │  │(低一致) │
         └───┬────┘  └───┬────┘  └───┬────┘
             │           │           │
             ▼           │           │
      ┌──────────┐      │           │
      │单次生成   │      │           │
      └──────────┘      │           │
                         ▼           ▼
                  ┌────────────┐ ┌────────────┐
                  │ Best-of-N  │ │PRM束搜索   │
                  │  (N=4-8)   │ │(N=16-64)   │
                  └────────────┘ └────────────┘

---

5. 问题难度与策略选择的关系

5.1 难度估计方法

5.1.1 基于采样一致性

def estimate_difficulty_by_consistency(model, question: str, 
                                       n_samples: int = 8) -> float:
    """
    通过采样一致性估计问题难度
    
    一致性高 → 问题简单 → 需要较少计算
    一致性低 → 问题困难 → 需要更多计算
    """
    samples = []
    for _ in range(n_samples):
        response = model.generate(question, temperature=0.8)
        answer = extract_answer(response)
        samples.append(answer)
    
    # 计算答案一致性
    answer_counts = Counter(samples)
    max_count = max(answer_counts.values())
    consistency = max_count / n_samples
    
    # 难度 = 1 - 一致性
    difficulty = 1.0 - consistency
    
    return difficulty

5.1.2 基于问题特征

class DifficultyEstimator:
    """
    基于问题特征的难度估计器
    """
    def __init__(self):
        self.feature_weights = {
            "num_tokens": 0.2,
            "num_numbers": 0.15,
            "has_conditionals": 0.25,
            "reasoning_depth": 0.3,
            "domain_knowledge": 0.1
        }
    
    def extract_features(self, question: str) -> dict:
        """提取问题特征"""
        return {
            "num_tokens": len(question.split()),
            "num_numbers": sum(c.isdigit() for c in question),
            "has_conditionals": 1 if any(
                kw in question.lower() 
                for kw in ["if", "假设", "given", "条件"]
            ) else 0,
            "reasoning_depth": self.estimate_reasoning_depth(question),
            "domain_knowledge": self.has_domain_knowledge(question)
        }
    
    def estimate_difficulty(self, question: str) -> str:
        """估计难度级别"""
        features = self.extract_features(question)
        
        # 加权计算难度分数
        difficulty_score = sum(
            features[k] * w 
            for k, w in self.feature_weights.items()
        )
        
        # 映射到难度级别
        if difficulty_score < 0.3:
            return "easy"
        elif difficulty_score < 0.6:
            return "medium"
        else:
            return "hard"

5.2 策略-难度匹配矩阵

难度	基础成功率	推荐策略	计算预算	预期提升
简单	> 90%	直接生成	1×	无需提升
中等	50-90%	CoT + 轻度采样	4-8×	5-15%
较难	25-50%	PRM + 束搜索	16-32×	15-30%
困难	< 25%	迭代修正 + 树搜索	64×+	30-50%

5.3 理论分析

设问题的基础成功率为 $p_0$，使用策略 $\pi$ 后成功率为 $p_{\pi }$。

关键发现：策略效果与基础成功率呈倒U型关系：

$$\text{Effectiveness}(\pi )\propto p_0(1-p_0)$$

• $p_0$ 接近 0：问题太难，任何策略都难以解决
• $p_0$ 接近 1：问题太简单，无需额外计算
• $p_0\approx 0.5$：策略效果最佳

策略效果
    ▲
    │         ╭─── 最佳效果区域
    │       ╱
    │     ╱
    │   ╱
────┼──────────────────────────▶ 基础成功率(p₀)
    │    0   0.25   0.5   0.75   1.0

---

6. 效率对比分析

6.1 4倍效率提升

Snell等人的论文证明，计算最优的自适应策略相比Best-of-N基线实现超过4倍的效率提升。¹

实验设置

• 任务：MATH数学推理基准
• 基础模型：PaLM 2（540B参数）配合不同规模的验证器
• 评估指标：相同计算预算下的准确率

结果对比

方法	计算量	MATH准确率	效率（准确率/计算）
Best-of-N (N=1)	1×	72.3%	72.3
Best-of-N (N=16)	16×	78.1%	4.88
Best-of-N (N=64)	64×	80.2%	1.25
计算最优策略	可变	88.2%	高

关键数据：使用计算最优策略，仅需约1/4的计算量即可达到Best-of-N (N=64)的性能。

6.2 效率对比图

准确率(%)
    ▲
100│                    ╭───── 计算最优策略
    │                  ╱
 90│─────────────────╱────────────────────
    │              ╱
 85│            ╱
    │          ╱
 80│────────╱─────── Best-of-N (N=64)
    │       │
 75│      ╱
    │     │
 70│────╯
    │  Best-of-N (N=1)
    └──────────────────────────────────▶ 计算量
      1×   4×   16×  32×  64×  128×
      
      4×效率提升区域：16×计算达到64×计算的性能

6.3 计算量-性能权衡曲线

不同方法的计算量-性能曲线具有不同形态：

import matplotlib.pyplot as plt
import numpy as np
 
def plot_scaling_curves():
    """
    绘制不同策略的计算量-性能曲线
    """
    compute = np.array([1, 4, 16, 64, 256])
    
    # 不同策略的性能曲线
    # 1. 贪婪解码（基线）
    greedy = 72.3 * np.ones_like(compute)
    
    # 2. Best-of-N（亚线性增长）
    bon = 72.3 + 8 * np.log2(compute)
    
    # 3. 计算最优策略（更陡峭的增长）
    optimal = 72.3 + 15 * np.log2(compute)
    
    # 4. 迭代修正（分段线性）
    iterative = np.where(
        compute < 16,
        72.3 + 10 * compute / 16,
        82.3 + 5 * np.log2(compute / 16)
    )
    
    plt.figure(figsize=(10, 6))
    plt.plot(compute, greedy, 'o-', label='Greedy (baseline)')
    plt.plot(compute, bon, 's-', label='Best-of-N')
    plt.plot(compute, optimal, '^-', label='Compute-Optimal')
    plt.plot(compute, iterative, 'd-', label='Iterative Refinement')
    
    plt.xscale('log')
    plt.xlabel('Compute (relative units)', fontsize=12)
    plt.ylabel('Accuracy (%)', fontsize=12)
    plt.title('Compute-Performance Trade-off', fontsize=14)
    plt.legend()
    plt.grid(True, alpha=0.3)
    plt.show()

6.4 FLOPs匹配评估

在FLOPs匹配的情况下，测试时计算可以超越更大模型：

配置	模型规模	计算类型	MATH准确率
配置1	1.3B	训练计算	45.2%
配置2	8B	训练计算	58.7%
配置3	8B + 自适应TT	训练+测试计算	72.1%
配置4	15B	训练计算	68.3%

关键发现：使用自适应测试时计算的8B模型，可以超越15B仅使用训练时计算模型的性能！

6.5 效率瓶颈分析

def analyze_efficiency_bottlenecks():
    """
    分析测试时计算效率的瓶颈
    """
    bottlenecks = {
        "验证器质量": {
            "影响": "决定搜索方向和剪枝效果",
            "症状": "即使大量采样也难以提升",
            "解决": "改进PRM训练数据和方法"
        },
        "多样性崩溃": {
            "影响": "多次采样产生相似错误",
            "症状": "投票无助于提升",
            "解决": "模式条件化、prompt工程"
        },
        "计算资源浪费": {
            "影响": "简单问题过度计算",
            "症状": "整体效率低于理论值",
            "解决": "自适应计算分配"
        },
        "同步开销": {
            "影响": "并行采样/验证的协调成本",
            "症状": "线性扩展变为亚线性",
            "解决": "异步执行、推测解码"
        }
    }
    
    return bottlenecks

---

7. 数学公式推导

7.1 迭代修正的期望性能

设问题的正确答案为 $y^{\ast }$，第 $t$ 次迭代得到解 $y_t$。

迭代修正的期望性能：

$$\mathbb{E}[R]\ge R_{\text{single}}+\sum _{t=1}^T{\Delta }_t\cdot P(\text{correct at step }t)$$

其中：

• $R_{\text{single}}$：单次生成的期望性能
• ${\Delta }_t$：第 $t$ 步修正带来的期望提升
• $P(\text{correct at step }t)$：第 $t$ 步正确的概率

7.2 预算约束下的优化

考虑预算约束 ${\sum }_{i=1}^{N}c(\pi ,x_i)\le B$，使用拉格朗日乘子 $\lambda$：

$$\mathcal{L}(\pi ,\lambda )=\mathbb{E}[\text{Acc}(\pi ,x)]-\lambda (\mathbb{E}[c(\pi ,x)]-B)$$

对 $\pi$ 求导并令为零，得到最优策略的必要条件：

$$\frac{\partial \mathbb{E}[\text{Acc}]}{\partial \pi }=\lambda \cdot \frac{\partial \mathbb{E}[c]}{\partial \pi }$$

这表明：边际准确率提升应该等于边际计算成本的 $\lambda$ 倍。

7.3 计算-性能权衡

定义效率 $\eta$ 为性能提升与计算成本的比值：

$$\eta =\frac{\Delta \text{Performance}}{\Delta \text{Compute}}$$

计算最优策略满足：

$${\eta }_{\text{optimal}}\ge {\eta }_{\text{uniform}},\forall \text{策略}$$

即：对于相同的计算预算，计算最优策略总能获得更高的性能。

7.4 难度-策略匹配的理论界

设问题难度 $d$ 的分布为 $P(d)$，策略 ${\pi }_d$ 对难度 $d$ 的效果为 $e({\pi }_d,d)$。

全局最优：

$$\underset{\{{\pi }_d\}}{\max }\int e({\pi }_d,d)P(d)dd$$

约束条件：

$$\int c({\pi }_d,d)P(d)dd\le B$$

使用变分法，可以证明最优匹配满足：

$$\frac{\partial e}{\partial c}{|}_d=\lambda ,\forall d$$

即：所有难度级别应该使用具有相同边际效果的策略。

---

8. LLM Agents的测试时计算

8.1 扩展到Agent场景

论文：Scaling Test-time Compute for LLM Agents 首次系统性地将测试时计算方法应用于语言智能体。³

8.2 Agentic Test-Time Scaling (ATTS)

针对Agent场景的特殊性，ATTS扩展了传统TT方法：

组件	传统TT	Agentic TT
采样策略	固定温度	自适应温度
验证方式	结果验证	轨迹验证
合并方法	多数投票	List-wise合并
状态管理	无状态	有状态环境交互

8.3 Agent专用策略

class AgenticTestTimeScaling:
    """
    面向Agent的测试时计算扩展
    
    关键差异：
    1. 需要考虑环境状态
    2. 轨迹级别的验证
    3. 工具调用的一致性
    """
    def __init__(self, agent, verifier):
        self.agent = agent
        self.verifier = verifier
    
    def run_with_scaling(self, task: str, 
                        n_rollouts: int = 8) -> str:
        """
        多轨迹Rollout + 验证合并
        """
        trajectories = []
        scores = []
        
        for _ in range(n_rollouts):
            # 运行Agent获取轨迹
            trajectory = self.agent.run(task)
            trajectories.append(trajectory)
            
            # 评估轨迹质量
            score = self.verifier.score_trajectory(task, trajectory)
            scores.append(score)
        
        # List-wise合并：考虑轨迹间的依赖关系
        return self.listwise_merge(trajectories, scores)
    
    def listwise_merge(self, trajectories: list, 
                      scores: list) -> str:
        """
        List-wise合并方法
        
        与pointwise（独立评估）和pairwise（成对比较）相比：
        - List-wise考虑全局最优
        - 保留轨迹间的协同效应
        """
        # 按分数排序
        sorted_trajs = sorted(
            zip(trajectories, scores),
            key=lambda x: x[1],
            reverse=True
        )
        
        # 提取关键决策点
        decision_points = self._extract_decision_points(sorted_trajs)
        
        # 基于多数一致性选择最终轨迹
        final_traj = []
        for dp in decision_points:
            choices = [traj[dp] for traj, _ in sorted_trajs[:3]]
            final_traj.append(Counter(choices).most_common(1)[0][0])
        
        return self._reconstruct_trajectory(final_traj)

8.4 实验结果

基准	基础Agent	+ ATTS	提升
WebArena	42.3%	58.7%	+38.8%
ALFWorld	67.8%	81.2%	+19.8%
MiniWob++	78.4%	89.1%	+13.6%

---

9. 实践指南

9.1 策略选择框架

def select_strategy(config: dict) -> str:
    """
    根据配置选择最优策略
    
    参数:
        config: {
            'task_type': str,      # 'math', 'code', 'fact', 'logic'
            'budget': str,         # 'low', 'medium', 'high'
            'has_verifier': bool,  # 是否有验证器
            'model_size': str,     # 'small', 'medium', 'large'
        }
    """
    task = config['task_type']
    budget = config['budget']
    has_verifier = config['has_verifier']
    
    # 简单问题
    if budget == "low":
        return "标准CoT"
    
    # 中等预算
    if budget == "medium":
        if has_verifier and task in ["math", "code"]:
            return "Best-of-N + PRM"
        elif task in ["math", "logic"]:
            return "CoT + 多数投票"
        else:
            return "并行采样"
    
    # 高预算
    if has_verifier:
        if task in ["math", "code"]:
            return "PRM引导束搜索"
        else:
            return "迭代修正 + 树搜索"
    else:
        return "推理模型 (o1/R1)"

9.2 成本-收益分析表

策略	延迟增加	准确率提升	适用场景
标准CoT	2-3×	10-20%	所有任务
多数投票（N=16）	16×	5-15%	有明确答案
Best-of-N（N=16）	16×	10-25%	有验证器
PRM束搜索（32次）	32×	20-35%	复杂推理
迭代修正（8轮）	8×	15-30%	可验证任务
自适应分配	可变	20-40%	通用

9.3 最佳实践建议

1. 从简单开始：先尝试标准CoT，测量基线性能
2. 添加验证器：如果有可靠的验证器，优先使用Best-of-N
3. 渐进式优化：根据问题难度逐步增加计算
4. 监控效率：跟踪”每单位计算的准确率提升”
5. 考虑延迟约束：实时应用可能需要限制最大计算

---

10. 参考文献

---

相关主题

• 测试时计算扩展：完整的方法分类
• 计算最优测试时扩展：自适应策略详解
• 链式推理：CoT基础原理
• 过程奖励模型：PRM在验证中的应用
• 推理模型架构：o1/o3/R1等推理模型
• LLM推理策略：多种推理策略对比
• MCTS与LLM推理：树搜索增强推理
• 测试时推理技术综述：推理技术全景
• 测试时计算缩放理论：理论基础

Footnotes

1. Snell, C., Lee, J., Xu, K., & Kumar, A. (2024). Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters. ICLR 2025 Oral. (https://arxiv.org/abs/2408.03314) ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Zhai, Z., et al. (2026). AdaCompute: Adaptive Test-Time Compute Allocation for Reasoning LLMs. arXiv:2604.14853. (https://arxiv.org/abs/2604.14853) ↩

3. Zhu, K., et al. (2025). Scaling Test-time Compute for LLM Agents. arXiv:2506.12928. (https://arxiv.org/abs/2506.12928) ↩