Interview Prep · Multi-Agent & Long-Horizon

# Multi-Agent & Long-Horizon 面试 Cheat Sheet

CAMEL · AutoGen · MetaGPT · MoA · Debate · MemGPT · LATS · SWE-Agent + 25 高频题（L1 必会 · L2 进阶 · L3 顶级 lab）

By Ruofeng Yang (杨若峰), Shanghai Jiao Tong University

Source: `docs/tutorials/multi_agent_long_horizon_tutorial.md` SHA256: `b0be93d29409` Rendered: 2026-05-19 13:21 UTC

## §0 TL;DR Cheat Sheet

9 句话搞定 Multi-Agent & Long-Horizon Agent

2024-2026 LLM agent 第二次浪潮，一页拿下面试核心。

1. 范式定位：单 LLM = "一次 forward 的 system 1"；agent = "把推理拆成 perceive → plan → act → reflect 的 system 2"。multi-agent = 多个 LLM role-play 不同身份协作；long-horizon = 同一 agent 跨多 turn / 多天保持目标。两者正交但常一起出现（如 ChatDev, MetaGPT）。

2. multi-agent 三大原型：

   - role-play 对话（CAMEL, Li et al. NeurIPS 2023, arXiv 2303.17760）：assistant-user 双角色 inception prompting；
   - SOP / 流水线（MetaGPT, Hong et al. ICLR 2024, arXiv 2308.00352）：把软件开发拆成 PM / Architect / Engineer / QA 七个固定角色；
   - debate / aggregation（Du et al. ICML 2024 arXiv 2305.14325 + Liang et al. EMNLP 2024 arXiv 2305.19118）：N agent 独立解答 → 互看 → 多轮迭代到一致。
3. MoA (Mixture-of-Agents, Wang et al. ICLR 2025 Spotlight, arXiv 2406.04692)：N 个 proposer 各出回答，aggregator 把 N 个回答 concat 进 prompt 再合成。开源 6.5B-70B 组合在 AlpacaEval 2.0 上超过 GPT-4 Omni。
4. debate 收敛——经验观察 + 理论近似：把每个 agent 的 update 视作对 peer 答案分布的混合算子，若该算子是 doubly-stochastic averaging 形（majority-vote softmax + temperature β），按 consensus dynamics 理论（线性 averaging 算子在 doubly-stochastic graph 上）会收敛到 fixed-point set（一致分布或离散一致 cluster），而非唯一 fixed point（Banach contraction 一般不成立——因为 averaging 算子有特征值 1）。经验上 N=3 与 N=5 在 GSM8K 上 accuracy gap ≈ 1-2pp（diminishing return，见 Du 2023 Fig 4 + Liang 2024 Table 3）。
5. MemGPT (Packer et al., arXiv 2310.08560, 2023-10)：把 LLM context 类比 OS RAM，把外部存储类比 disk。page fault = 模型 function-call "search archival memory" 触发的 retrieval。延迟代价：一次 page fault ≈ 一次额外 LLM call（数百 ms ~ 数秒），但避免了 context overflow。后续以 Letta 名义工程化（2024+）。
6. GraphRAG (Microsoft 2024, arXiv 2404.16130)：vector RAG 在 multi-hop 上崩；GraphRAG 先用 LLM 抽 entity-relation 三元组，建知识图谱 + community detection，按层级摘要后再做 retrieval-augmented generation。global query（"给整篇文档总结主题"）比 vector RAG 强 70-80%。

7. tree-search agent：

   - ToT (Yao et al., NeurIPS 2023, arXiv 2305.10601) = BFS/DFS + LLM evaluator；
   - RAP (Hao et al., EMNLP 2023, arXiv 2305.14992) = MCTS + world-model rollout；
   - LATS (Zhou et al., ICML 2024, arXiv 2310.04406) = MCTS + 自反思 (Reflexion) + value 估计；
   - Agent-Q (Putta et al., 2024, arXiv 2408.07199) = MCTS + DPO 离线训练 policy。共性：用 PUCT 公式 $a^* = \arg\max_a Q(s,a) + c_\text{puct} P(s,a) \sqrt{N(s)} / (1+N(s,a))$ 平衡 exploit / explore。
8. long-horizon benchmark 三件套：TAU-bench（Yao et al. 2024 arXiv 2406.12045，customer service multi-turn）、OSWorld (Xie et al. NeurIPS 2024 arXiv 2404.07972，real OS GUI)、SWE-bench (Jimenez et al., ICLR 2024, arXiv 2310.06770，真实 GitHub issue 修复)。SOTA 2026-05 在 SWE-bench Verified ≈ 75%（Claude 4.6 Sonnet / o3 等），但 OSWorld 仍 < 60%。
9. 易踩坑：multi-agent 不是越多越好（cost ∝ N, accuracy gain ∝ log N）；long-CoT context overflow 不是写更长 context window 能解（lost-in-the-middle, Liu et al. TACL 2024 arXiv 2307.03172）；memory stale 比 memory missing 更危险（错误 retrieval 会产生 confident wrong answer）；sub-agent blame-shifting（"那是 worker A 的错"）在 hierarchical orchestrator 模式中常见。

## §1 直觉：从 single LLM 到 agent system

### 1.1　为什么 single LLM 不够

把 LLM 当成 $y = f_\theta(x)$ 一次 forward 的 oracle，有三个本质限制：

- 状态有界：context window 是物理上限（即使 1M token 也有限），无法长期保持目标
- 决策一锤定音：一次 sampling 错了就错了，没有"undo / replan" 机制
- 能力切片：单 prompt 既要 reason 又要 act 又要 verify，role drift——前段 reasoning 与后段 verification 互相干扰

agent 的本质是把这三个问题外部化：

LLM 内置 | Agent 外置
--- | ---
context window | persistent memory（vector store / KG / disk）
one-shot sampling | iterative loop: perceive → plan → act → reflect
single role | multi-agent role specialization

mental model — agent = LLM × harness × memory × tools

一个 agent 不是一个 LLM，而是 LLM 套在 outer loop 上。harness 决定 LLM 什么时候被 call、call 什么、怎么把 output 喂回去。Claude Code Agent / Cursor / Devin / SWE-Agent 本质都是 不同 harness 的差异——同样的 LLM，harness 设计差距能拉开 30-50pp 的 task success rate。

### 1.2　multi-agent vs long-horizon vs agentic

这三个词常被混用，但精确含义不同：

概念 | 关注点 | 典型代表
--- | --- | ---
multi-agent | 多个 LLM role-play 不同身份协作 / 对抗 | CAMEL, AutoGen, MetaGPT, debate
long-horizon | 同一 agent 跨多 turn / 长时间保持目标 | MemGPT, Voyager, OSWorld, SWE-Lancer
agentic | LLM 具备自主 plan + tool use + reflection 能力（≥1 agent，≥1 step） | Toolformer, ReAct, AutoGPT

→ 一个真实系统通常三个都涉及（比如 Devin = agentic（自主决策）+ long-horizon（跨小时调试）+ 多 sub-agent（planner / executor / debugger））。

### 1.3　two-thread 心法（每道面试题先 disambiguate）

面试官问 "你怎么理解 multi-agent system？" 时，第一句话先 disambiguate：

> "Multi-agent 字面上是多个 LLM 协作，但语义上分两条线： （1）协作型（CAMEL / AutoGen / MetaGPT），多 agent 不同身份共同完成一个目标； （2）对抗型 / 共识型（debate），多 agent 独立解答再 reconcile。 工程实践里前者更常见，理论分析里后者更多。"

这个 disambiguate 在 RLHF / Diffusion / RAG 等其他主题里也通用——用 30 秒 framing 拿到 reviewer 信任，比直接背 paper 名字加分。

## §2 multi-agent 协作核心范式

### 2.1　CAMEL：role-play inception prompting

CAMEL (Communicative Agents for "Mind" Exploration of Large scale Language model society, Li et al., NeurIPS 2023, arXiv 2303.17760) 是第一个被广泛引用的 LLM multi-agent paper（不是第一个 multi-agent 想法，但第一个把 prompt 工程做到 systematic）。

核心机制：两个 frozen LLM，一个扮演 user（task initiator），一个扮演 assistant（task solver），通过 inception prompt 锁定角色不漂移：

    [user prompt 模板]
    你是 <ROLE_USER>，你正在和 <ROLE_ASSISTANT> 合作完成 <TASK>。
    绝不直接给答案，只给 instruction，等 assistant 回答后再给下一步 instruction。

    [assistant prompt 模板]
    你是 <ROLE_ASSISTANT>，按 <ROLE_USER> 的 instruction 执行。
    绝不主动提问或追加 task。每次回答后说 "Next request."

关键贡献：发现了 role flipping（assistant 不知不觉变 user）和 task drift（任务范围越聊越大）两个失败模式，并通过 prompt 工程缓解。

CAMEL 不是 cooperative game

表面上是 user-assistant 对话，本质上 user 和 assistant 都受同一个 task 锁定，没有 reward 冲突——不是 multi-agent RL 意义上的 game theory。常见误用是把 CAMEL 和 self-play RL（如 AlphaGo）混为一谈。

### 2.2　AutoGen：GroupChat / 通用 multi-agent 框架

AutoGen (Wu et al., arXiv 2308.08155, 2023-08, Microsoft Research; later published at COLM 2024 + presented at ICLR 2024 LLM Agents Workshop) 把 multi-agent 抽象成 conversable agent——每个 agent 是一个对象，有 `send / receive / generate_reply` 三个方法。`GroupChat` 是其中最有影响力的模式：N 个 agent 在一个共享的 message queue 上轮流发言，一个 `GroupChatManager` 决定下一个发言的人。

伪代码（concept）：

    class GroupChat:
        """ N 个 agent 共享 message history，按 selector 策略轮流发言 """
        def __init__(self, agents, max_round=10):
            self.agents = agents
            self.messages = []
            self.max_round = max_round

        def select_speaker(self, last_speaker):
            # 三种策略: round_robin / random / llm_selector (LLM 自己决定下一个)
            # 实际产品常用 llm_selector: 给 manager LLM 看 history + 角色描述, 选下一个
            ...

        def run(self, init_msg):
            self.messages.append(init_msg)
            speaker = self.agents[0]
            for _ in range(self.max_round):
                reply = speaker.generate_reply(self.messages)
                self.messages.append(reply)
                if self._is_terminated(reply):
                    break
                speaker = self.select_speaker(speaker)
            return self.messages

selector 设计是 AutoGen 的成败点

round-robin 简单但容易让弱 agent 拖后腿；random 缺乏控制；llm_selector 让 manager LLM 看 history 选下一个发言，是 production 默认（也是 cost 高的根源——多了一次 manager call）。

### 2.3　MetaGPT：SOP-driven 软件公司模拟

MetaGPT (Hong et al., ICLR 2024 (oral), arXiv 2308.00352) 是把 multi-agent 推向结构化 workflow 的代表。核心 insight：通用 GroupChat 容易 chaos——让 PM / Architect / Engineer 自由对话，往往话题跑偏；不如写死 SOP（standard operating procedure）：

    ProductManager  → PRD (Product Requirement Doc)
    Architect       → Tech Design (class diagram, API)
    ProjectManager  → Task List
    Engineer        → Code (multiple .py files)
    QAEngineer      → Test Cases

每个角色只接收上一节点的 structured output（不是自由对话），输出也是 structured（文档/代码/测试）。

structured vs unstructured 是 multi-agent 工程化的最大分水岭

CAMEL / 早期 AutoGen 是 unstructured（自由聊天）；MetaGPT / ChatDev / 现代 production agent 都是 structured（pipeline of artifacts）。原因：unstructured 容易 hallucinate "我们已经完成了"，structured 强制每一步产出可 inspect 的 artifact。

### 2.4　ChatDev / AgentVerse / Generative Agents

- ChatDev (Qian et al., ACL 2024, arXiv 2307.07924)：和 MetaGPT 思路类似，软件开发 multi-agent，chat chain 串起 design / coding / testing 三阶段。代码量小（~7B token），但开源得早，被广泛 fork。
- AgentVerse (Chen et al., ICLR 2024, arXiv 2308.10848)：提出 expert recruitment + collaborative decision-making + individual action + evaluation 四阶段框架。expert 角色由 LLM 动态生成（不是 fixed pool），适合任务多样场景。
- Generative Agents (Park et al., UIST 2023, arXiv 2304.03442, Stanford + Google)：25 个 agent 在 sandbox 小镇里自由生活，每个 agent 有 daily routine + memory stream + reflection。涌现出生日 party、约会、竞选市长等社会行为——第一次让 LLM agent 表现出 social emergence。

Generative Agents 的 emergence 不等于真智能

Park 2023 强调这是 "believable behavior"（让人觉得像真人），不是有意识或有 agency。Reddit / Twitter 上常被夸大成 "AI village"，面试时要克制：这是一个 prompt 工程极致的 case study，不是 AGI 雏形。

### 2.5　Mixture-of-Agents (MoA) — 2024 NeurIPS 最 catchy 工作

MoA (Wang et al., NeurIPS 2024, arXiv 2406.04692, Together AI) 的核心 idea 简单到没人会信：

            ┌─ proposer_1 (Qwen2-72B)
    prompt ─┼─ proposer_2 (LLaMA3-70B)  ──→ aggregator (Qwen2-72B):
            ├─ proposer_3 (WizardLM)         "把这 N 个 response 综合
            └─ proposer_N (Mixtral)            成最终答案"

关键观察（Wang 2024 fig 3）：把 N 个 proposer 的 response 直接 concat 进 aggregator 的 prompt，比 best-of-N（选最高 reward 一个）效果好。原因：多个不完美回答的互补信号比单个最优回答的信息量大。

MoA 在 AlpacaEval 2.0 上 LC win rate：

系统 | LC Win Rate
--- | ---
GPT-4 Omni (May 2024) | 57.5%
MoA (6× open-source models) | 65.1%
MoA-Lite (3× layer) | 59.3%

MoA 的理论解释（自己加分）

这不是 ensemble averaging（不是简单 vote），而是 LLM-as-aggregator 在 prompt 空间做 latent reasoning：把 N 个不同 perspective 的 response 当成 "expert evidence"，让 aggregator 做一次 in-context reasoning + synthesis。本质是 Wang et al. 2022 self-consistency 的 LLM-aggregator 推广（self-consistency 用 majority vote，MoA 用 LLM）。

    def moa_inference(prompt, proposers, aggregator, num_layers=3):
        """ Wang 2024 MoA 多层版本 (paper 默认 3 层) """
        responses = [p(prompt) for p in proposers]
        for layer in range(num_layers - 1):
            # 每一层把上一层 N 个 response 喂给同一批 proposer 再生成
            aggregate_prompt = build_moa_prompt(prompt, responses)
            responses = [p(aggregate_prompt) for p in proposers]
        # 最后一层用 aggregator 而不是 proposer
        final_prompt = build_moa_prompt(prompt, responses)
        return aggregator(final_prompt)

    def build_moa_prompt(query, responses):
        instructions = (
            "You have been provided with a set of responses from various open-source "
            "models to the latest user query. Your task is to synthesize these responses "
            "into a single, high-quality response. Critically evaluate the information, "
            "recognize that some may be biased or incorrect.\n\n"
        )
        refs = "\n".join(f"[Model {i}]\n{r}" for i, r in enumerate(responses))
        return f"{instructions}{refs}\n\n[User Query]\n{query}"

## §3 multi-agent debate：从 Society of Mind 到现代实现

### 3.1　历史脉络

- Minsky 1986《Society of Mind》：人类智能不是单一过程，而是多个 simple "agent" 在心智社会里互相批评、互相补充。这是 multi-agent debate 的思想原型，但 1986 没有可执行算法。
- Du et al. ICML 2024 (arXiv 2305.14325, MIT)："Improving Factuality and Reasoning in Language Models through Multiagent Debate"——第一个把 Society of Mind 用 LLM 实现：N 个 agent 各自给答案，互看对方答案后再修订，2-3 轮收敛。GSM8K +6-10pp。
- Liang et al. EMNLP 2024 (arXiv 2305.19118, Tencent AI Lab)："Encouraging Divergent Thinking in LLMs through Multi-Agent Debate"——加入 judge 角色，affirmative / negative agent 对抗，judge 仲裁。在翻译 / counter-intuitive 推理任务上 +5-8pp。

### 3.2　最小可运行实现

    import re
    from collections import Counter

    def extract_answer(response: str) -> str:
        """从 LLM response 提取 final answer。生产中要更鲁棒（处理 \\boxed{}、LaTeX、单位）。"""
        m = re.search(r"(?:final answer|答案)[:：]\s*(.+?)(?:\n|$)", response, re.IGNORECASE)
        if m:
            return m.group(1).strip()
        # fallback: 取最后一行
        return response.strip().split("\n")[-1].strip()

    def majority_vote(answers: list[str]) -> str:
        """简单多数投票；平局时返回第一个 mode。"""
        if not answers:
            return ""
        return Counter(answers).most_common(1)[0][0]

    def multi_agent_debate(query, agents, num_rounds=3):
        """
        Du et al. 2023/ICML 2024 风格的 debate.

        Args:
            agents: List of N callable LLMs (same or different)
            num_rounds: 通常 2-3 轮足够 (diminishing return)
        Returns:
            最终多数答案
        """
        # Round 0: 各自独立回答
        responses = [a(query) for a in agents]

        for r in range(num_rounds):
            new_responses = []
            for i, a in enumerate(agents):
                # 把 *其他* agent 的回答展示给 agent i
                others = "\n".join(
                    f"Agent {j}: {responses[j]}"
                    for j in range(len(agents)) if j != i
                )
                debate_prompt = (
                    f"Question: {query}\n\n"
                    f"Other agents have proposed:\n{others}\n\n"
                    f"Your previous answer: {responses[i]}\n\n"
                    f"Critically examine other answers. If they convince you, update "
                    f"your answer; if they are wrong, defend yours with reasoning. "
                    f"Give a final answer at the end."
                )
                new_responses.append(a(debate_prompt))
            responses = new_responses

        # 最终: majority vote over extracted answers
        return majority_vote([extract_answer(r) for r in responses])

### 3.3　收敛性：什么条件下 debate "收敛"？

常见错误：直接套 Banach contraction

debate 的每个 agent update $T_i$ 把 N 个 peer answer 映到自己新答案；联合 update $T = (T_1, \dots, T_N)$ 在 "答案空间" 上通常是 doubly-stochastic averaging 风格（softmax + majority vote）。这类 averaging 算子在 doubly-stochastic graph 上特征值 1 总是存在（对应 consensus 方向），所以严格 Banach contraction 一般不成立 —— 不能直接说 "唯一不动点 + 几何收敛"。

正确说法（consensus dynamics）

应该说收敛到 fixed-point set（一致 cluster），而非唯一 fixed point：

1. Linear averaging case：若 $T$ 是线性 doubly-stochastic operator $A$（即 $A \mathbf{1} = \mathbf{1}, A^\top \mathbf{1} = \mathbf{1}$），按 Perron-Frobenius，iterates $x_k = A^k x_0 \to \pi^\top x_0 \cdot \mathbf{1}$，即收敛到 consensus value（所有 agent 同答案），但起点不同 consensus value 不同 —— fixed-point set 是 $\{c \cdot \mathbf{1} : c \in \mathbb{R}\}$
2. 非线性 case（softmax / majority vote）：fixed-point set 通常是若干离散 consensus cluster（每个对应一个候选答案的全员同意）；从不同 initial 出发收敛到哪个 cluster 取决于初始多数派
3. 真要 Banach 不动点：需要额外引入外部 contraction（如固定 reference answer 的 anchor agent），但这等价于退化为非 debate 算法

实践对收敛的影响：

- majority pull 强（peer 一致时容易 sway agent）→ fixed-point set 中 majority cluster 吸引盆变大
- temperature 低（agent 倾向 majority answer）→ 收敛快但易陷局部 consensus（即使错答案）
- agent heterogeneous（不同 model / prompt）→ fixed-point set 可能完全不重叠，无 consensus

Liang 2024 的 affirmative-negative 反例：刻意设计对抗 agent，averaging 结构被破坏 —— 严格说不是 "$\beta \ge 1$"，而是 没有公共 fixed-point set（两个 cluster 互推），所以必须加 judge 当外部决策器强行裁决。

### 3.4　N=3 vs N=5：边际收益分析

经验观察（Du 2023 / Liang 2024 多组实验综合）：

N | 相对 baseline 提升（GSM8K / MMLU 类推理任务） | Cost (× LLM call)
--- | --- | ---
1 (no debate) | baseline | 1×
3 | +5-10pp (典型) | 3 × R rounds
5 | +1-2pp 在 N=3 之上 | 5 × R rounds
7+ | <1pp 增量 | 7 × R rounds

→ N=3 到 N=5 边际收益急剧下降，N=3, R=2-3 已经吃到大部分收益。具体数字依任务而变（math vs trivia vs translation 表现不同）。

cost-accuracy 关系不是线性

N 增加收益递减，根本原因是 agent 之间 correlation 上升（同 model family 的 N 个 agent 给出高度相关的回答，independent ensemble 假设崩塌；按 Condorcet 定理收敛速率受 $\rho$ 影响，$\rho$ 大则增益小）。面试常问"为什么不 N=100"——除了 cost，是 correlation。

## §4 协调协议：A2A / 黑板架构 / hierarchical orchestrator

### 4.1　通信协议层级

层 | 名字 | 典型代表
--- | --- | ---
应用层 | 任务语义 | "你修 bug，我写 test"
协调层 | message routing | AutoGen GroupChat, GroupChatManager
协议层 | message format | A2A (Google 2025), MCP (Anthropic 2024), OpenAI Agents SDK
传输层 | RPC / WebSocket / stdio | HTTP, gRPC, stdio

- MCP (Model Context Protocol, Anthropic Nov 2024)：LLM ↔ tool 的协议，不是 agent ↔ agent。但很多 agent framework 用 MCP 暴露 sub-agent 作为 tool（"sub-agent as tool"）。
- A2A (Agent-to-Agent, Google April 2025)：明确针对多 agent 互联，定义 agent card / task / message / artifact 四个核心对象，HTTP+JSON-RPC。截至 2026-05 仍是 spec 阶段，业界用得少。
- OpenAI Agents SDK (2025) 提供 handoff / guardrails / tracing 抽象，事实上是 OpenAI 私有协议。

### 4.2　黑板架构（Blackboard architecture）

经典 AI 架构（HEARSAY-II 1980，DARPA 项目），multi-agent 共享一个全局可读写的"黑板"，每个 agent 看黑板决定要不要发言。在 LLM 时代它的变体是：

    ┌─────────────────────────────────────────────┐
    │  Shared Blackboard (vector store / KG)      │
    │  - claim_1: "x > 0"                          │
    │  - assumption_1: "f convex"                  │
    │  - subgoal_1: "show g(x) bounded"            │
    └─────────────────────────────────────────────┘
            ↑                ↑                ↑
            │                │                │
        Reasoner          Verifier         Skeptic
       (写 claim)        (验 claim)       (反 claim)

优点：解耦——agent 不需要知道别的 agent 存在，只关心黑板上的状态。缺点：need a control unit 决定谁发言（否则一片混乱）。AutoGen GroupChat 本质就是黑板 + LLM-as-control-unit。

### 4.3　Hierarchical orchestrator + worker（Claude Code 模式）

2024-2025 production agent 的事实标准：1 个 orchestrator + N 个 worker。

               ┌──────────────────────┐
               │   Orchestrator       │ ← 看用户 query, 决定:
               │   (main LLM, big)    │   - 拆 subtask
               │                      │   - 哪个 worker 接
               │                      │   - 怎么 aggregate result
               └──────────────────────┘
                    ↓     ↓     ↓
             ┌──────┘     │     └──────┐
             ↓            ↓            ↓
        ┌────────┐  ┌────────┐  ┌────────┐
        │Worker A│  │Worker B│  │Worker C│
        │ (code) │  │ (web)  │  │ (math) │
        └────────┘  └────────┘  └────────┘

Claude Code Agent / Cline / Aider 都是这个模式：

- Claude Code Agent：main loop = orchestrator，TaskCreate 调出 subagent（不同 system prompt + 工具子集），完成后 subagent 把 final message 回传 orchestrator。
- Cline：plan mode = orchestrator 思考，act mode = worker 执行（同一 LLM 不同 prompt）。
- Aider：自动 split 大改成 small commit，每个 commit 是一个 sub-conversation。

orchestrator-worker 的成本结构

orchestrator 用大模型（Claude 4.6 Sonnet 级别）决策，worker 用便宜模型（Haiku / Sonnet）执行——叫 "cascading inference"（Yue 2023 FrugalGPT 提出, arXiv 2305.05176）。1 次 orchestrator call + 10 次 worker call 比 11 次 orchestrator call 便宜 5-10×。

### 4.4　Sub-agent blame-shifting (常见 bug)

    Orchestrator: "任务失败了。"
    Worker A: "我已经写完代码了，是 Worker B 的 test 没写好。"
    Worker B: "我 test 写的没问题，是 Worker A 的代码 bug。"
    Orchestrator: 陷入 deadlock

根因：每个 worker 只看到自己的 conversation，没有 ground truth artifact。

修复：

1. artifact-level verification：让 worker 跑 unit test / linter，把 result 作为 objective evidence
2. third-party judge：单独跑一个 fresh-context judge LLM 看双方 conversation + artifact，做判断
3. incremental commit：每个 worker 的 output 立即落盘 + checksum，blame 时直接 diff 文件

## §5 long-horizon agent：memory architecture

### 5.1　memory 三类：sensory / short-term / long-term

借用认知心理学的 Atkinson-Shiffrin 三级模型：

Memory | LLM 对应 | 容量 | 持续时间
--- | --- | --- | ---
Sensory | 当前 input token | 几 K | 一次 forward
Short-term / Working | LLM context window | 几 K - 1M | 一次 session
Long-term | 外部 store (vector / KG / file) | unbounded | 永久

Long-term 又分两类（Tulving 1972）：

- Episodic memory：具体事件（"昨天我和 Alice 讨论 RLHF"）
- Semantic memory：抽象知识（"DPO 的 loss 是 ..."）

在 agent 系统里：

- episodic ≈ trajectory log（过去 action + observation 序列）
- semantic ≈ knowledge base（论文、文档、API 知识）

episodic 与 semantic 用不同 retrieval 策略

episodic 按 temporal + spatial proximity（"过去 24h 在这个 file 改过的事"）；semantic 按 semantic similarity（"和当前问题最相关的知识"）。production 常用 hybrid retrieval：先按 time decay 过滤再按 embedding rank。

### 5.2　MemGPT：OS-style virtual memory

MemGPT (Packer et al., arXiv 2310.08560, 2023-10; engineered as Letta 2024+) 把 LLM context 类比 OS RAM，把外部 vector store 类比 disk：

      +─────────────────+         +─────────────────+
      │  Main Context   │         │  External Store │
      │  (RAM analog)   │  ←─→    │  (disk analog)  │
      │  - system info  │         │  - archival     │
      │  - recall snip  │         │    memory       │
      │  - chat history │         │  - recall mem   │
      └─────────────────┘         └─────────────────┘
            ↑   ↓
            │   │  page in / out via function call
            │   ↓
       ┌──────────────────┐
       │ LLM + functions: │
       │ - search_archi   │
       │ - insert_archi   │
       │ - search_recall  │
       │ - send_message   │
       │ - pause          │
       └──────────────────┘

关键术语：

- Main Context = 当前 LLM input（system prompt + working context + recall snippet + dialogue）
- Recall Memory = 过去对话历史（按时间存）
- Archival Memory = 任意 fact / document（按 semantic store）
- Page Fault = main context 不够，需要 retrieve archival/recall → 触发 function call

page fault 对 latency 的影响：

操作 | 延迟典型值（GPT-4o-class）
--- | ---
一次 LLM forward（4K context） | 1-2 秒
一次 archival search（vector store） | 50-200 ms
一次 page fault（search → LLM 再 generate） | 1-2 秒（搜索） + 1-2 秒（合成）
主上下文 hit（无 page fault） | 1-2 秒

→ page fault 把单次 turn 延迟 ~翻倍。生产系统常用 prefetch（预测要用什么 archival，提前 retrieve）来缓解。

### 5.3　MemoryBank：海马体启发

MemoryBank (Zhong et al., AAAI 2024, arXiv 2305.10250) 受 Ebbinghaus forgetting curve 启发，每条 memory 带 strength 和 last_access_time，用指数衰减：

$$S_t = S_0 \exp\left(-\frac{t - t_\text{last\_access}}{\tau}\right)$$

retrieval 时按 similarity × current strength 排序，经常被访问的 memory 强度回升（mimic 海马体 reactivation）。

MemoryBank vs MemGPT

MemGPT 把 memory 当 disk（无优先级，按 query 检索），MemoryBank 给 memory 加 dynamic priority（按访问频率衰减/强化）。production agent 常两者结合：MemGPT 的 disk 抽象 + MemoryBank 的 forgetting curve 做 cache eviction。

### 5.4　GraphRAG：knowledge graph + community

vector RAG（最朴素 RAG）的核心问题：multi-hop / global question 上崩。

例：

- "总结整个 codebase 的设计哲学" → vector RAG 只能找几个 file，无法 global synthesize
- "Alice 的朋友的朋友是谁" → 三跳 query，vector retrieval 一次拿不到三跳路径

GraphRAG (Microsoft 2024, Edge et al., arXiv 2404.16130) 解决方案：

    Stage 1 (offline, expensive):
      document → LLM extract (entity, relation, entity) 三元组
             → 构 KG → Leiden community detection → 多层社区摘要

    Stage 2 (online, cheap):
      query → 判断 query 类型 (local entity? global theme?)
           ↓
      local: 找最相关 entity, 看邻居, 用 vector RAG 补
      global: 用社区摘要做 map-reduce

Wins：

Benchmark | Vector RAG | GraphRAG | Δ
--- | --- | --- | ---
Multi-hop QA (HotpotQA-class) | ~50% | ~70% | +20pp
Global summarization | poor | strong | qualitative

Loss：

- offline cost 高（一次 build KG 要扫全语料）
- KG schema 设计成败决定一切

GraphRAG 不是 silver bullet

单跳 factoid（"DPO 的 loss 公式"）vector RAG 已经够好；GraphRAG 只在 multi-hop / global 上有优势。先 profile query 分布再决定要不要上 GraphRAG——盲目堆 GraphRAG 是 2025-2026 见过最常见的 over-engineering。

### 5.5　代码：episodic + semantic 双轨 retrieval

    from dataclasses import dataclass
    from typing import List
    import time
    import numpy as np

    @dataclass
    class MemoryItem:
        text: str
        embedding: np.ndarray
        created_at: float
        last_access: float
        access_count: int = 0
        kind: str = "semantic"   # "episodic" / "semantic"

    class HybridMemory:
        """ 简化版 MemoryBank + episodic/semantic 分轨 """
        def __init__(self, decay_tau_episodic=86400.0, decay_tau_semantic=864000.0):
            self.items: List[MemoryItem] = []
            self.tau_e, self.tau_s = decay_tau_episodic, decay_tau_semantic

        def add(self, text, embedding, kind="semantic"):
            now = time.time()
            self.items.append(MemoryItem(text, embedding, now, now, 0, kind))

        def _strength(self, item: MemoryItem, now: float) -> float:
            tau = self.tau_e if item.kind == "episodic" else self.tau_s
            # access_count 增益: 每次 access 强度 +0.1 (Ebbinghaus spaced repetition)
            boost = 1.0 + 0.1 * item.access_count
            decay = np.exp(-(now - item.last_access) / tau)
            return boost * decay

        def retrieve(self, query_embedding, k=5, kinds=("episodic", "semantic")):
            now = time.time()
            scores = []
            for it in self.items:
                if it.kind not in kinds:
                    continue
                # cosine similarity (假设已归一化)
                sim = float(np.dot(query_embedding, it.embedding))
                score = sim * self._strength(it, now)
                scores.append((score, it))
            scores.sort(reverse=True, key=lambda x: x[0])
            top = [it for _, it in scores[:k]]
            # 访问会强化
            for it in top:
                it.last_access = now
                it.access_count += 1
            return top

strength × similarity 的乘法 vs 加法

这里用乘法：strength 衰减到 0 时该 memory 完全消失（即使 similarity 高）；加法会让 strength 只是 bias。production 用乘法，但对 episodic memory 加 floor（避免新 episodic 立刻被淘汰）。

## §6 planning + tree search agents

### 6.1　Plan-then-execute 范式

HuggingGPT (Shen et al., NeurIPS 2023, arXiv 2303.17580, Microsoft + Zhejiang U) 是早期代表：

    User Query
       │
       ↓
    LLM (Plan)         ← 用 ChatGPT 把 task 拆成 sub-task DAG
       │
       ↓
    HF Models (Execute) ← 调用 HuggingFace 上各种 vision / speech 模型
       │
       ↓
    LLM (Aggregate)    ← 把各 sub-task 输出综合

问题：plan 一次定死，执行失败无法 replan。这就引出 ReAct / Reflexion / tree-search 系列。

### 6.2　ReAct：思考 + 行动交替

ReAct (Yao et al., ICLR 2023, arXiv 2210.03629, Princeton + Google) 形式：

    Thought 1: I need to find Colorado mountain heights.
    Action 1: search("Colorado eastern sector elevation range")
    Observation 1: 1800 to 7000 ft.
    Thought 2: Now I need to find the High Plains elevation.
    Action 2: search("High Plains elevation")
    ...

每一步 thought 和 action 交替，这种格式现在是所有 agent 的事实基础——AutoGPT / LangChain Agent / Toolformer 都是 ReAct 的变种。

### 6.3　Tree of Thoughts (ToT)

ToT (Yao et al., NeurIPS 2023, arXiv 2305.10601) 第一次显式 search：

                    root (problem)
                   /    |    \
                t1.a  t1.b  t1.c     ← LLM propose N thoughts
                  |   |   |
              ┌────────────────┐
              │  LLM evaluator  │     ← 每个 thought 评分 (1-10 / "sure")
              └────────────────┘
                  ↓ BFS / DFS expand
                t2.aa t2.ab ...

- expand：LLM 提议 K 个 thought
- evaluate：LLM 给每个 thought 打分 / 标 "sure / maybe / impossible"
- search：BFS（按 layer 推进 top-k）或 DFS（带 backtrack）

ToT 的 LLM-as-evaluator 是 self-referential 风险

同一个 LLM 既 propose 又 evaluate，可能给自己的 thought 打高分。production 用 ToT 时要么换 reward model 当 evaluator，要么用 cross-model evaluator。

### 6.4　RAP：MCTS + world model

RAP (Hao et al., EMNLP 2023, arXiv 2305.14992) 升级：把 ToT 的 LLM-as-evaluator 换成 MCTS + LLM-as-world-model。

    MCTS step:
      1. select: 按 PUCT 公式选 leaf
      2. expand: LLM propose next action
      3. simulate: LLM rollout 到 terminal, 估 reward
      4. backup: 把 reward 沿 path 回溯更新 Q(s,a)

    PUCT 公式 (UCT 的 AlphaGo 改良版):
      a* = argmax_a [ Q(s, a) + c_puct * P(s,a) * sqrt(N(s)) / (1 + N(s,a)) ]

公式各项：

$$\boxed{\;a^* = \arg\max_a \left[ Q(s, a) + c_\text{puct} \cdot P(s, a) \cdot \frac{\sqrt{N(s)}}{1 + N(s, a)} \right]\;}$$

- $Q(s, a)$：从 $(s,a)$ 出发 rollout 的 mean reward
- $P(s, a)$：prior probability（LLM 给的 action 概率）
- $N(s)$：状态 $s$ 的访问数
- $N(s, a)$：(s, a) 边的访问数
- $c_\text{puct}$：exploration constant（典型 1.0-3.0）

直觉：第一项 $Q$ exploit（选 reward 高的），第二项 explore（次数少 + prior 高的）。$\sqrt{N(s)} / (1 + N(s,a))$ 是 UCB1 + AlphaGo prior 混合。

### 6.5　LATS：MCTS + Reflexion + value

LATS (Zhou et al., ICML 2024, arXiv 2310.04406, Penn + UIUC) 把 RAP 进一步加 Reflexion：

    For each expansion:
      1. action = LLM_policy(state, history)
      2. observation = env.step(action)
      3. value = LLM_value(state, history)   ← scalar 估计
      4. if failed: reflection = LLM_reflect(history)  ← 写入下次 prompt
      5. backup value 沿 path

LATS 在 HotpotQA / WebShop / HumanEval 上都比 ReAct + Reflexion 单独用强。

LATS = ToT + Reflexion + MCTS 的混合体

三个技术合一，工程复杂度高，但 sample efficiency 显著好。production 部署成本 + 工程难度让其至今不是主流，但论文意义 / 思想完整性强——面试可作为"我读过最 well-designed agent 论文之一"的例子。

### 6.6　Agent-Q：MCTS + DPO 离线训练

Agent-Q (Putta et al., 2024, arXiv 2408.07199, MultiOn + Stanford) 反思：MCTS at inference 太慢，能不能用 MCTS 离线产生数据训 policy？

    Offline:
      for many episodes:
        trajectory = MCTS_search(env, llm)
        for state, good_action, bad_action in trajectory.preferences():
          DPO_dataset.add(state, good_action, bad_action)
      fine-tune LLM via DPO

    Inference: 直接用 fine-tuned LLM (无 MCTS)，速度 ↑↑

结果：WebShop 任务上从 28% → 51% success rate，且 inference 速度比 in-loop MCTS 快 10×。

### 6.7　LATS 风格 tree-search 实现（核心 60 行）

    import math
    from dataclasses import dataclass, field
    from typing import Optional, List, Callable

    @dataclass
    class Node:
        state: str
        action: Optional[str] = None
        parent: Optional["Node"] = None
        children: List["Node"] = field(default_factory=list)
        visits: int = 0
        value_sum: float = 0.0
        prior: float = 1.0
        is_terminal: bool = False

        @property
        def Q(self):
            return self.value_sum / self.visits if self.visits > 0 else 0.0

    def puct(child, parent, c=1.5):
        """ PUCT: Q + c * P * sqrt(N_parent) / (1 + N_child) """
        explore = c * child.prior * math.sqrt(parent.visits) / (1 + child.visits)
        return child.Q + explore

    def select(node):
        while node.children and not node.is_terminal:
            node = max(node.children, key=lambda c: puct(c, node))
        return node

    def expand(node, llm_propose, k=3):
        if node.is_terminal: return
        for action, prior in llm_propose(node.state, k=k):
            node.children.append(Node(state=None, action=action, parent=node, prior=prior))

    def simulate(node, env_step, llm_propose_one, llm_value, max_depth=5):
        """ Rollout 从 (parent.state, node.action) 起跑 env 到 terminal 或深度上限.

        Args:
            llm_propose_one: policy — 给 state 返回单个 action（greedy/random rollout）
            llm_value:       value — 给 state 估剩余 cumulative reward
        """
        state, cur_action, cum_r = node.parent.state, node.action, 0.0
        for _ in range(max_depth):
            state, r, done = env_step(state, cur_action)
            cum_r += r
            if done:
                node.is_terminal, node.state = True, state
                return cum_r
            cur_action = llm_propose_one(state)   # policy rollout 选下一步 action
        node.state = state
        return cum_r + llm_value(state)            # value head 估剩余

    def backup(node, value):
        while node:
            node.visits += 1
            node.value_sum += value
            node = node.parent

    def lats_search(initial_state, llm_propose, llm_propose_one, llm_value, env_step,
                    num_iter=50, c_puct=1.5, max_rollout=5):
        """LATS = MCTS + Reflexion + value 估计.

        llm_propose:       expand 时给 (state, k) → [(action, prior)]
        llm_propose_one:   rollout 中给 state → action（policy）
        llm_value:         value 估计 state → cumulative reward 剩余
        """
        root = Node(state=initial_state, visits=1)
        for _ in range(num_iter):
            leaf = select(root)
            if not leaf.is_terminal:
                expand(leaf, llm_propose, k=3)
                if leaf.children:
                    leaf = leaf.children[0]
            value = simulate(leaf, env_step, llm_propose_one, llm_value, max_depth=max_rollout)
            backup(leaf, value)
        return max(root.children, key=lambda c: c.visits).action if root.children else None

LATS 实现陷阱

(1) `simulate` 必须从 parent + action 推（不复用 select leaf 的 state）；(2) policy（`llm_propose_one`）和 value（`llm_value`）必须分开传——之前版本误把 value 当 policy 用，rollout 行为退化为只看 state value 不选 action；(3) `expand` 时 prior 用 `softmax(LLM_logp)` 归一化；(4) terminal 判定要严格，否则 rollout 无限循环；(5) PUCT 系数 c 典型 1.0-3.0；(6) 生产里加 wall-time budget 检查，避免 50-iter 跑超时。

## §7 long-horizon evaluation benchmarks

### 7.1　Benchmark 对比表（2024-2026）

Benchmark | 论文 | 任务类型 | 步长 | 2026-05 SOTA
--- | --- | --- | --- | ---
AgentBench | Liu et al., ICLR 2024, arXiv 2308.03688 | 8 envs (OS, DB, WebShop, HouseHold...) | 10-50 | GPT-4 ≈ 4.0/10 overall
τ-bench (TAU-bench) | Yao et al., 2024, arXiv 2406.12045 | customer service multi-turn (retail, airline) | 20-50 | Claude 3.5 Sonnet ≈ 45-55% (retail)
OSWorld | Xie et al., NeurIPS 2024, arXiv 2404.07972 | real OS GUI (Linux/macOS/Win, ≈ 369 任务) | 5-100 | Anthropic Claude (2026-05) ≈ 60% (subset)
WebArena | Zhou et al., ICLR 2024, arXiv 2307.13854 | self-hosted web (Reddit-clone, Gitea, etc.) | 5-30 | GPT-4 ≈ 14.4% (2024)，2026 头部 ~ 50%
VisualWebArena | Koh et al., ACL 2024, arXiv 2401.13649 | WebArena + 视觉理解 | 10-30 | GPT-4V ≈ 16.4%
SWE-bench / Verified | Jimenez et al., ICLR 2024, arXiv 2310.06770 | 2294 真实 GitHub issue (Python repos) | 多文件多 commit | Claude 4.6 Sonnet (2026-05) ~ 75% (Verified)
MLE-bench | Chan et al., 2024 (OpenAI), arXiv 2410.07095 | 75 Kaggle ML 比赛任务 | 24h compute budget | GPT-4o + AIDE ≈ 16.9% medals
SWE-Lancer | OpenAI, 2025, arXiv 2502.12115 | 1488 真实 Upwork freelance task ($1M+ payout) | 持续 hours-days | GPT-4o ≈ 8% (managerial), 26% (IC)
Adventure / TextWorld | Yuan et al., AAAI 2019, arXiv 1806.11532 | text adventure game | 50-500 | RL-trained baseline + LLM > 80% on Coin Collector

### 7.2　benchmark 选择决策表

想测什么 | 选哪个
--- | ---
通用 agent 能力 | AgentBench
客服对话 + 工具调用准确率 | TAU-bench
真实 GUI 操作（最难） | OSWorld
编程 agent + 真实 repo 修复 | SWE-bench Verified
长达数天的 ML 工作 | MLE-bench
经济价值实测 | SWE-Lancer
Web navigation | WebArena / VisualWebArena

### 7.3　benchmark 的 horizon 长度对失败模式的暗示

- 短 horizon (5-20 step)：失败主要是 single-step error（误解 query / 调错 tool）
- 中 horizon (20-100 step)：开始出现 context overflow / lost-in-the-middle / replan 失败
- 长 horizon (100+ step, multi-day)：memory stale, sub-agent blame, cost explosion, decision paralysis

长 horizon 上每多 10 step 成功率约衰减 1/2（Anthropic 2025 内部观察，公开 blog 部分提及，不是严格 scaling law）——这是为什么 long-horizon agent 是 2026 最难也最有研究价值的方向。

## §8 long-horizon 特有失败模式

### 8.1　Context overflow + lost-in-the-middle

Liu et al. TACL 2024 (arXiv 2307.03172) 发现：LLM 对 context 中间位置的信息利用率显著低于开头和结尾——U-shape curve（开头>结尾>中间）。

    Recall vs position in 25-doc QA (Liu 2024 fig 2):

      recall %
      100 ┤●                                 ●
          │  ●●●                          ●●●
       75 ┤      ●●●                  ●●●
          │          ●●●          ●●●
       50 ┤              ●●●  ●●●
          │                  ●●
          │
        0 └─────────────────────────────→ doc position
           1    5    10    15    20    25

对 long-horizon agent 的暗示：

1. 重要 fact 别放中间——把 task instruction 放头部 + 当前 working memory 放尾部
2. context window 不是越长越好——超过 ~30K 时 utilization 显著下降
3. periodic summarization——周期把 context 中段总结成短 snippet 推到尾部

### 8.2　Error compound / drift

长任务里单步错误率虽小，多步后必崩。简化模型：

设单步 success rate $p$，独立假设下 $T$ step 总成功率：

$$P(\text{all success}) = p^T$$

$p=0.95$, $T=20$: $P = 0.358$ $p=0.95$, $T=50$: $P = 0.077$ $p=0.99$, $T=50$: $P = 0.605$

→ single-step 95% 的 agent 在 50 step 任务上只有 7.7% 成功率——必须把 single-step 提到 99%+ 才能撑住 50 step。

缓解方法：

- rollback / replan：每隔 N step checkpoint，失败时回滚（类似 video gen 的 keyframe）
- hierarchical sub-task：把 50 step 拆 5 个 10-step sub-task，每个 sub-task 内部独立失败可单独 retry
- self-verify after each critical step：每个关键 action 后让 verifier 检查

drift vs catastrophic failure

drift 是渐进偏离目标（每步只错一点），catastrophic 是某一步彻底跑偏。drift 比 catastrophic 更难发现——agent 可能继续 happily 执行错误轨迹。production 防 drift 靠 periodic self-check（每 5 step 复核 task description vs current state）。

### 8.3　Decision paralysis / loop

agent 卡在某个状态反复执行相同 action：

    Action: search("foo")
    Observation: no results
    Thought: I should search with different keywords
    Action: search("foo")   ← 又来！
    Observation: no results
    ...

根因：LLM 在该 prompt context 下被 greedy decode 到同一个 mode。

修复：

1. action history hash：检测最近 N step 是否重复（fingerprint），重复则强制 explore
2. temperature ramp：连续失败 K 次后调高 temperature
3. explicit "give up" tool：让 agent 知道 "I cannot solve this" 是合法 action（避免假装能解）

### 8.4　Stale memory

agent retrieve 一条过时 memory，并基于此做决策。例：

    Memory: "API endpoint = https://api.foo.com/v1/users"
    Reality: 该 endpoint 已迁移到 /v2/users (memory 是 6 个月前的)
    Agent: 调用旧 endpoint → 404 → 困惑

比 memory 缺失更危险：缺失会让 agent 主动 search 新信息，stale memory 让 agent confidently wrong。

缓解：

1. TTL on memory：每条 memory 带过期时间戳，过期后降权或删除
2. memory consistency check：weekly 跑一遍 memory vs ground truth 对比
3. prefer recent over similar：retrieval 公式从 `sim` 改成 `sim * exp(-age/τ)`

### 8.5　Sub-agent conflict / blame-shifting

见 §4.4。

### 8.6　Cost explosion

long-horizon agent 的 token consumption 不是线性：

- 每 turn 都把 full history 喂进 LLM（KV cache 也救不了 prompt token 计费）
- $T$ turn 的累计 cost $\sim \sum_{t=1}^T O(t \cdot c) = O(T^2 c)$，其中 $c$ 是 per-turn 新增 token

实测：50-turn agent task 比 5-turn task token 消耗 ~ 50-200×（不是 10×）。

cost explosion 是 production agent 头号杀手

Devin / Claude Code 等都用 history compaction：把过去 30 turn 的 raw conversation 压缩成 ~ 1K token 的 summary。Anthropic 在 2025-05 加的 `/compact` 命令就是这个。

## §9 self-improvement + verification loops

### 9.1　Reflexion：从 trajectory log 反思

Reflexion (Shinn et al., NeurIPS 2023, arXiv 2303.11366) 算法：

    For each episode:
      1. trajectory = run agent on task
      2. reward = evaluator(trajectory)
      3. if reward low:
           reflection = LLM(trajectory, reward)
                        --> 自然语言总结失败原因
           memory.add(reflection)
      4. Next episode: prompt includes memory

自然语言 reflection 比 scalar reward 信息密度高——agent 不仅知道"失败"，还知道"为什么失败"。

### 9.2　test-time self-improvement (frame + video 双级)

A²RD 风格的 hierarchical test-time self-improvement (HITS) (Liu et al. 2026)：

- Frame 级：每生成一个 segment 后，用 frame-level verifier 检查（是否人脸变形、是否光照不一致）
- Video 级：每 K 个 segment 后做 video-level check（是否长程一致 / character 是否漂移）

类比 long-horizon agent：

- Step 级：每个 action 后用 unit-test / linter 检查
- Sub-task 级：每完成一个 sub-task 后做 integration check
- Task 级：最终用 acceptance test 验收

三级 self-correction 是 agent 工程的事实最佳实践

Cursor agent / Claude Code 都是这个三级模式：immediate（lint），中间（partial test），最终（full test + user review）。

### 9.3　Cross-Time Replay (避免 over-specialization)

Ctx2Skill 风格的 Cross-Time Replay：

- 维护一个 hard probe set（历史上失败过的 hard cases）和 easy probe set
- 每次 agent skill update 后，在两个 set 上 re-evaluate
- 选 $\rho_\text{hard} \times \rho_\text{easy}$ 最大的版本（不是只看当前任务变好）

防止 agent 在新任务上"学会作弊"导致旧能力退化（catastrophic forgetting at the skill level）。

### 9.4　Dependency DAG for memory retrieval

A²RD 风格的 MVMem 用 dependency DAG 决定生成某 segment 时去 retrieve 哪些过去 segment：

    seg_1 -- spatial overlap --> seg_5
    seg_2 -- char A appearance --> seg_7
    seg_3 -- camera continuation --> seg_4

→ 生成 seg_5 时只 retrieve {seg_1}，而不是 {seg_1..seg_4} 全部塞进 prompt。

对 long-horizon agent 的意义：把 episodic memory 之间的依赖显式建图（不是单一向 list），retrieval 时按图路径而不是全量 similarity。production 还在探索阶段（GraphRAG 是早期尝试）。

## §10 工程实践：subagent orchestration + budget tracking

    from dataclasses import dataclass
    from typing import Callable, Dict
    import time

    @dataclass
    class Budget:
        max_tokens: int = 200_000
        max_wall_seconds: float = 600.0
        max_subagent_calls: int = 20
        used_tokens: int = 0
        used_seconds: float = 0.0
        used_subagent_calls: int = 0

        def remaining(self):
            return dict(tokens=self.max_tokens - self.used_tokens,
                        seconds=self.max_wall_seconds - self.used_seconds,
                        subagents=self.max_subagent_calls - self.used_subagent_calls)

        def can_afford(self, est_tokens: int) -> bool:
            return (self.used_tokens + est_tokens <= self.max_tokens
                    and self.used_subagent_calls + 1 <= self.max_subagent_calls)

    class Orchestrator:
        """ Claude Code 风格的 orchestrator + N worker（带 budget tracking） """
        def __init__(self, llm_orch: Callable, llm_workers: Dict[str, Callable], budget: Budget):
            self.llm_orch, self.workers, self.budget, self.history = llm_orch, llm_workers, budget, []

        def call_subagent(self, name: str, prompt: str, est_tokens: int = 4000):
            if not self.budget.can_afford(est_tokens):
                return None
            t0 = time.time()
            out, used = self.workers[name](prompt)   # returns (output, tokens_used)
            self.budget.used_tokens += used
            self.budget.used_seconds += time.time() - t0
            self.budget.used_subagent_calls += 1
            return out

        def run(self, query: str, max_steps: int = 20):
            for step in range(max_steps):
                decision = self.llm_orch(query=query, history=self.history,
                                         budget=self.budget.remaining())
                if decision["action"] == "finalize":
                    return decision["answer"]
                out = self.call_subagent(decision["subagent"], decision["prompt"],
                                         decision.get("est_tokens", 4000))
                if out is None:   # 预算不够 → forced finalize
                    return self.llm_orch(query=query, history=self.history,
                                         budget=self.budget.remaining(),
                                         hint="budget_exhausted")["answer"]
                self.history.append({"step": step, "subagent": decision["subagent"], "result": out})
            # 步数耗尽: forced finalize
            return self.llm_orch(query=query, history=self.history,
                                 budget=self.budget.remaining(),
                                 hint="forced_finalize")["answer"]

budget tracking 是 production agent 的硬要求

没有 budget 的 agent 会烧钱无上限。Anthropic Claude Code / Cursor / OpenAI Agents SDK 都在 SDK 层加 budget hook——不只是 token，还有 wall time、sub-agent 调用次数、API rate-limit。生产环境必须三轨同时控。

## §11 复杂度分析

### 11.1　multi-agent 协作 cost 模型

设：

- $N$ = agent 数
- $R$ = debate / collaboration 轮数
- $C$ = 单个 LLM call 平均 token cost
- $L$ = 累计 message history 长度

round-robin GroupChat： $$\text{cost} = N \times R \times C \times O(L)$$ 其中 $L$ 单调增长（每个 agent 写一条 message，所有 agent 都看），所以总 cost $\approx O(N^2 R^2 C)$ 量级（前提 message 长度 ~ const, 即 $L \propto NR$）——N 和 R 都是 quadratic。

MoA（N 个 proposer + 1 个 aggregator）： $$\text{cost} = (N + 1) \times C \times O(L_\text{prompt}) + 1 \times C \times O(NL_\text{response})$$ 线性 in $N$，实际上更便宜。

debate (Du 2023)： $$\text{cost} = N \times R \times C \times O(NL_\text{response})$$ （每个 agent 看其他 $N-1$ 个 response）→ $O(N^2 R C L_\text{response})$。

对比：

模式 | Cost 量级
--- | ---
Single LLM | $O(C L)$
MoA | $O(N C L)$
Debate (Du) | $O(N^2 R C L)$
GroupChat (round-robin) | $O(N R^2 C L)$ 或更糟

→ GroupChat 是最贵的（这就是为什么 production AutoGen 几乎都改用 hierarchical orchestrator）。

### 11.2　long-horizon agent memory cost

设 $T$ = total turn 数, $M$ = total memory size。

- No retrieval（all in context）: cost $\sim O(T^2)$（每 turn 看全 history）
- Vector RAG：每 turn retrieve $k$ 条 memory，cost $\sim O(T \cdot (k + \log M))$
- GraphRAG：offline build $O(M^2 / \text{community size})$, online query $O(T \cdot \log M)$ + occasional global synthesis
- MemGPT：cost $\sim O(T \cdot (k + L_\text{archival\_search}))$，page fault 增加 ~ 2× per-turn 延迟

### 11.3　PUCT-based tree search

LATS / Agent-Q 类的 tree search at inference：

- 单次 search: $O(I \cdot D \cdot C)$，其中 $I$ = MCTS iteration, $D$ = max depth, $C$ = per-LLM-call cost
- $I = 50, D = 5, C = $ 4K token → 单 query ~ 1M token

→ tree search at inference 很贵——这就是 Agent-Q 的核心动机（offline MCTS 训完 inference 直接用 fine-tuned policy）。

## §12 与相关方法对比

### 12.1　multi-agent vs single-agent + reflection

维度 | Multi-Agent (debate, MoA) | Single + Reflection (Reflexion, Self-Consistency)
--- | --- | ---
多样性 来源 | 多个 model (heterogeneous) | 同 model 不同 sampling
Cost | $O(NRC)$ 起 | $O(NC)$
失败模式 | sub-agent conflict, blame-shifting | echo-chamber (同一 bias 重复 N 次)
何时选 | model 之间真的有不同 capability 互补 | 主要靠 sampling diversity

经验：若 N 个 agent 是同 base model 同 prompt，multi-agent 与 self-consistency 收益几乎等同（同源 bias），没必要上 multi-agent。

### 12.2　Tree search vs long CoT (o1-style)

维度 | Tree search (ToT/LATS) | Long CoT (o1, R1)
--- | --- | ---
哪里 search | 外部显式 tree | LLM 内部 hidden CoT
可观测性 | 高（tree 可视化） | 低（hidden trace）
Inference 延迟 | 高（多次 LLM call） | 中（单次 long generation）
训练成本 | 几乎无（inference-only） | 高（RL on reasoning）
何时选 | 需可解释 / 没法训 | 有足够 compute 训

### 12.3　memory architecture 选型

场景 | 推荐
--- | ---
小项目 / prototype | LangChain ConversationBuffer (in-memory list)
中等规模 / 单用户 long session | MemGPT-style RAM/disk + recall
多用户产品 + 知识库 | vector store (Chroma / Pinecone) + recall
复杂 multi-hop QA / 文档密集 | GraphRAG
Agent 需要"忘记" | MemoryBank (Ebbinghaus decay)
视频/科研等强结构化 | typed memory + dependency DAG (A²RD 风格)

## §13 2025-2026 前沿系统

### 13.1　Anthropic Claude Code Agent / Computer Use

- Claude Computer Use (Oct 2024)：让 Claude 直接操作 desktop（截屏 → reason → mouse/keyboard action）。OSWorld 上 ~ 14.9% (2024)，到 2026-05 已 ~ 60% (Anthropic blog)。
- Claude Code Agent (Feb-2025 GA)：orchestrator + subagent 模式，subagent 可用 TaskCreate 调出（不同 system prompt + tool 子集）。CLI tool 形式开放给开发者。

### 13.2　OpenAI Operator / Agents SDK

- Operator (Jan 2025)：Anthropic Computer Use 的对标产品，但用 CUA (Computer-Using Agent) 训练专门 vision policy（不是通用 Claude），WebArena 准确率 ≈ 58.1%。
- OpenAI Agents SDK (Mar 2025)：Python framework，提供 handoff / guardrail / tracing 抽象。handoff = orchestrator 把任务"递交"给另一个 agent（不只是 tool call）。

### 13.3　Cognition Devin / SWE-Agent

- Devin (Cognition, Mar 2024 demo)：第一个商业化"AI 软件工程师" demo，能 plan + code + debug + browser 全 stack。SWE-bench Verified ~ 13.9% (Mar 2024)→ ~ 50% (2025-late, Devin 3.0)。
- SWE-Agent (Yang et al., NeurIPS 2024, arXiv 2405.15793, Princeton)：开源 SWE-bench agent，提出 Agent-Computer Interface (ACI) 概念——给 LLM 设计专门 file-edit / shell / search 接口（不是直接给 bash），SWE-bench Lite 上 18.0%。

### 13.4　Cursor / Cline / Aider / Continue

- Cursor (Anysphere)：commercial IDE-integrated agent，plan/act mode 切换，Composer 是 multi-file edit subagent。
- Cline (开源, originally Claude Dev)：VS Code extension，open-source orchestrator + worker，2025 GitHub stars 增至 30K+。
- Aider：CLI tool，repo-map + LLM auto-commit；auto-split large change 到 small commit 是 long-horizon 工程典范。
- Continue：自托管 alternative，可接 self-hosted LLM。

production agent 工具链汇总（面试可背）

commercial: Cursor, Devin, GitHub Copilot Agent, Claude Code open-source CLI: Cline, Aider, Continue framework: AutoGen (MS), CrewAI, LangGraph (LangChain), LlamaIndex AgentWorkflow

## §14 25 高频面试题 — L1 必会 / L2 进阶 / L3 顶级 lab

### Level 1 — 必会（10 题）

Q1. multi-agent / long-horizon / agentic 三个词的区别？

- multi-agent：多个 LLM role-play 不同身份协作 / 对抗 —— CAMEL, AutoGen, MetaGPT, debate
- long-horizon：同一 agent 跨多 turn / 多天保持目标 —— MemGPT, Voyager, OSWorld, SWE-Lancer
- agentic：LLM 具备自主 plan + tool use + reflection 能力（agent 数可以 ≥ 1） —— ReAct, Toolformer, AutoGPT

→ 真实系统通常三者都涉及，但精确含义不同，面试第一步先 disambiguate。

Q2. CAMEL 的 inception prompt 解决什么问题？

解决 role flipping 和 task drift：

- role flipping：assistant 不知不觉变 user（"我也想知道这个问题"）
- task drift：任务越聊越宽（"我们顺便来讨论一下数据库设计"）

inception prompt = 强约束的 system prompt（"你只能给 instruction，等回答后再下一条" / "你只能 reply 不能主动追加 task"），加上 "Next request." 等格式锁。

Q3. AutoGen 的 GroupChat selector 有几种策略？production 怎么选？

三种：

1. round_robin：按顺序轮 —— 简单，但弱 agent 拖后腿
2. random：随机选 —— 缺乏控制
3. llm_selector：用一个 manager LLM 看 history 决定下一个 —— production 默认，但每轮多一次 LLM call

实际产品（如 Microsoft 自家产品）几乎都是 llm_selector，因为 round_robin 在 N>3 时容易 chaos。

Q4. MetaGPT 为什么强调 SOP？和 CAMEL 的本质差别？

CAMEL 是 unstructured chat：role-play + 自由对话 → 容易 hallucinate "我们已经完成了"，没有可 inspect 的 artifact。

MetaGPT 强制 structured artifact pipeline：

    PM → PRD (markdown)
    Architect → tech design (class diagram, API)
    ProjectManager → task list (JSON)
    Engineer → code (.py files)
    QA → test cases

每个角色只接收上一节点的 structured output（不是自由 chat），强制可 inspect。

→ structured vs unstructured 是 multi-agent 工程化的最大分水岭。

Q5. ReAct = ?

ReAct = Reasoning + Acting (Yao et al., ICLR 2023, arXiv 2210.03629)：

    Thought 1: I need to find X.
    Action 1: tool_call("search X")
    Observation 1: ...
    Thought 2: With X, I can conclude...
    Action 2: ...

thought 和 action 交替，目前是所有 agent framework 的事实标准（AutoGPT / LangChain / Toolformer 等都是 ReAct 的工程化）。

Q6. MoA 是什么？为什么用 N 个 proposer + 1 个 aggregator 而不是 best-of-N？

MoA (Mixture-of-Agents, Wang et al. NeurIPS 2024, arXiv 2406.04692)：N 个 LLM 各自给 response，把 N 个 response concat 进 prompt喂给 aggregator LLM 让它 synthesize。

为什么比 best-of-N 好：

- best-of-N：用 reward model 选一个最高分的 response —— 丢弃了其他 N-1 个的互补信息
- MoA：让 aggregator LLM 看到所有 N 个 perspective，在 prompt 空间做 latent reasoning + synthesis

结果：6× open-source model 的 MoA 在 AlpacaEval 2.0 LC win rate 65.1% > GPT-4 Omni 57.5%。

Q7. multi-agent debate 是怎么收敛的？

Du et al. ICML 2024 / Liang et al. EMNLP 2024 风格：

    Round 0: 各 agent 独立答
    Round 1: 各 agent 看其他 N-1 个答案 → 修订
    Round 2: 再修订
    ...
    最终: majority vote

收敛性质（细节见 §3.3）：averaging 算子（doubly-stochastic）通常没有 Banach 唯一不动点——consensus 方向特征值 = 1。正确说法是收敛到 fixed-point set（多个 consensus cluster），实际落到哪个由初始多数派 + agent 偏置决定。

实践：N=3 round=3 已吃到 ~ 80% 收益；N=5 仅 +1.2pp 但 cost +67%（Du 2023 fig 4）。

Q8. MemGPT 的 RAM 和 disk 对应什么？page fault 是什么？

- RAM = LLM main context（system prompt + working context + recall snippet + dialogue），容量 ~ 几 K - 1M token
- Disk = 外部 storage（recall memory 按时间 + archival memory 按 semantic）
- Page fault = main context 信息不够，模型 function-call `search_archival` 或 `search_recall` → 检索 → 把结果塞回 main context

Page fault 对 latency：一次 page fault ~ 一次额外 LLM call 数百 ms ~ 2 秒，把单 turn 延迟翻倍。production 用 prefetch 缓解。

Q9. Vector RAG 和 GraphRAG 的区别？什么场景 GraphRAG 才值？

| Vector RAG | GraphRAG
--- | --- | ---
表示 | embedding chunks | entity-relation KG + community
索引 | similarity search | graph traversal + community summary
Multi-hop | 弱 | 强
Global query | 不能 | 行
Offline cost | 低 | 高（要 LLM 抽 entity）
单 hop factoid | OK | overkill

→ 多跳 + global theme query 选 GraphRAG；单跳 factoid 用 vector RAG 够了。盲目堆 GraphRAG 是 2025-2026 常见 over-engineering。

Q10. ToT、RAP、LATS、Agent-Q 的关系？

- ToT (Yao 2023, NeurIPS) = LLM-propose + LLM-evaluate + BFS/DFS
- RAP (Hao 2023, EMNLP) = ToT 升级到 MCTS + LLM-as-world-model（rollout）
- LATS (Zhou 2024, ICML) = RAP + Reflexion（自然语言反思） + value estimate
- Agent-Q (Putta 2024, arXiv 2408.07199) = MCTS at training-time + DPO 训 policy → inference 不再需要 MCTS（10× 速度）

共性：都用 PUCT 公式 $a^* = \arg\max_a [Q + c P \sqrt{N} / (1 + N_a)]$ 平衡 exploit / explore。

演化逻辑：ToT 起步 → MCTS 显式化 → 加反思 → 训出来不用 search。

### Level 2 — 进阶（10 题）

Q11. 推 debate 收敛性的充分条件，并解释 N=3 vs N=5 的边际收益差。

收敛性证明：

把每个 agent 的更新看成 operator $T_i : \mathcal{A}^N \to \mathcal{A}$，把 N 个 peer 的当前答案映到自己新答案。联合 update $T = (T_1, \dots, T_N) : \mathcal{A}^N \to \mathcal{A}^N$。

若存在度量 $d$ 使 $d(T(x), T(y)) \le \beta \cdot d(x, y)$ ($\beta < 1$)，则按 Banach 不动点定理，迭代 $x_{k+1} = T(x_k)$ 从任意 $x_0$ 收敛到唯一不动点 $x^*$，收敛速度 $d(x_k, x^*) \le \beta^k d(x_0, x^*)$。

$\beta < 1$ 的实现条件：

- agent 倾向 majority pull（peer 一致时容易动摇 → 拉力强）
- temperature 适中（太高随机不收敛，太低固化）
- 同源 agent（heterogeneous 之间偏置不同会增加 contraction 难度）

N=3 vs N=5（Du 2023 / Liang 2024 经验观察）：

N | 相对 baseline 提升（推理类任务，依 task 而变） | cost
--- | --- | ---
1 | baseline | 1×
3 | +5-10pp | ~9× (N × R)
5 | +1-2pp 在 N=3 之上 | ~15×

边际收益急剧下降原因：

1. agent 之间 correlation：同模型 N agent 给出高度相关回答，ensemble gain $\sim \sigma^2 (1 + (N-1)\rho)$，$\rho$ 大则增益小
2. diminishing return on independent voices：投票理论的 Condorcet 定理告诉我们，多数对的概率随 N 增长但收敛速率递减

production 选 N=3, round=2 已吃到 80% 收益。

Q12. MoA 和 self-consistency (Wang 2022) 的区别在哪？为什么 MoA 看起来更强？

- Self-consistency (Wang 2022)：同模型 sample N 个 CoT，majority vote
- MoA (Wang 2024)：N 个不同模型 sample，LLM aggregator 合成

关键差：

1. diversity 来源：SC 靠 sampling temperature，MoA 靠模型异质性——后者更强（不同模型偏置不同 → independent error）
2. 聚合方式：SC 是 hard vote（丢弃 reasoning trace），MoA 是 LLM-as-aggregator（保留 trace 信息，做 latent synthesis）

但 MoA 的强可能也部分来自 aggregator 是大模型（Qwen2-72B）——如果 aggregator 用小模型，gap 缩小。

面试加分：MoA 本质是 "self-consistency 把 majority vote 升级成 LLM-as-aggregator + 模型异质性"——两次升级的乘积。

Q13. lost-in-the-middle 现象是什么？对长 context agent 设计意味着什么？

Liu et al. TACL 2024 (arXiv 2307.03172)：把答案放在 25-doc context 不同位置，测 QA recall。发现 U-shape：头部和尾部 recall 高（80%+），中间 dip 到 50%。

根因：

- attention sink 现象（头部 token 被广泛 attended）
- recency bias（尾部 token 因 causal mask 影响后续 logit）
- 训练数据偏置（人写文章重要点在头尾）

对长 context agent 设计的暗示：

1. 重要 fact 别放中间：task instruction → 头部；当前 working memory → 尾部
2. context window 不是越长越好：超过 30K 时 utilization 显著下降；先 retrieve 再 generate 比塞满 1M context 更稳
3. periodic summarization：把中间累积的 conversation 周期性压缩到尾部 snippet
4. 多 chunk re-rank 把最相关的放尾部（不是头部）

Q14. error compound 对 long-horizon agent 的影响怎么量化？

简化模型：独立单步成功率 $p$，$T$ step 任务总成功率：

$$P(\text{all success}) = p^T$$

$p$ | $T=10$ | $T=20$ | $T=50$ | $T=100$
--- | --- | --- | --- | ---
0.90 | 0.349 | 0.122 | 0.005 | 2.7e-5
0.95 | 0.599 | 0.358 | 0.077 | 0.006
0.99 | 0.904 | 0.818 | 0.605 | 0.366
0.999 | 0.990 | 0.980 | 0.951 | 0.905

→ single-step 99% 才能撑住 50 step。

实际中并非独立——某些 step 的失败会 propagate（同 mode 错），所以 effective $p$ 更低；反之 step 间有 verify/rollback 时可"修复"，effective $p$ 提高。真实长 horizon agent 的 effective $p$ ≈ 0.95-0.98。

缓解：

1. checkpoint / rollback：每 5-10 step 一个 checkpoint
2. hierarchical sub-task：拆成短 horizon，每段独立 verify
3. per-step verifier：unit test / linter，把 $p$ 推高

Q15. 为什么 RAG 在 multi-hop 上崩？GraphRAG 如何修？

vector RAG 在 multi-hop 上崩的根因：

    Q: "Alice 的朋友的朋友是谁?"
    向量空间: "Alice", "Alice 的朋友", "Bob 的朋友" 在 embedding 上不一定接近

第一跳的 chunk（"Alice 朋友 = Bob"）和第二跳的 chunk（"Bob 朋友 = Carol"）在向量空间不直接关联，单次 retrieval 只能拿到第一跳，第二跳要 reasoning 出来再 retrieve（多步 retrieval-then-reason）—— production 实现复杂。

GraphRAG 修法：

    Stage 1 (offline):
      doc → LLM extract triples (Alice, friend, Bob), (Bob, friend, Carol)
           → 构 KG → Leiden community detection → 多层社区摘要

    Stage 2 (online):
      multi-hop query: Alice → friend → ?? → friend → ??
      KG traversal 直接拿到 Carol
      global query: 用社区摘要 map-reduce

性价比：multi-hop QA 上 ~ +20pp；single-hop factoid 没收益但 cost 高。

Q16. PUCT 公式各项的物理意义？c_puct 怎么调？

$$a^* = \arg\max_a \left[ Q(s, a) + c_\text{puct} \cdot P(s, a) \cdot \frac{\sqrt{N(s)}}{1 + N(s, a)} \right]$$

- $Q(s, a)$：exploit —— 该 action 历史平均 reward
- $P(s, a)$：prior —— LLM 给的 action 概率 (softmax over candidates)
- $\sqrt{N(s)}$：随父节点访问数增长 → 更激进 explore
- $1 / (1 + N(s,a))$：访问越多越不偏向 explore
- $c_\text{puct}$：exploration 系数 —— 典型 1.0-3.0

调 $c_\text{puct}$：

- 任务有 noisy reward → $c_\text{puct}$ 大一点（多 explore 避免被 single noisy reward 误导）
- 任务 reward 干净 + branching factor 高 → $c_\text{puct}$ 中等
- 任务 prior 很准（LLM 提议质量高）→ $c_\text{puct}$ 小（trust prior）

AlphaZero 用 1.25-3.0，LATS/RAP 实现常用 1.0-2.0。

Q17. orchestrator + worker 模式比 GroupChat 强在哪？

维度 | GroupChat (flat) | Orchestrator + Worker (hierarchical)
--- | --- | ---
Cost 量级 | $O(N R^2 C L)$ | $O(R \cdot (C_\text{orch} + N_\text{used} \cdot C_\text{worker}))$
控制流 | 隐式（selector LLM） | 显式（orchestrator 决定）
失败追溯 | 难（多 agent 互相引用） | 易（orchestrator 是唯一决策者）
模型分层 | 同 model | 可 cascade（orch 用大，worker 用小）
适合任务 | 短任务 / 探索性 | 长任务 / 工程化

经验：production agent 几乎全是 orchestrator + worker——Claude Code、Cursor、Devin、SWE-Agent 都是这个模式。GroupChat 主要在学术 demo 和 早期 prototype 用。

Q18. agent loop / decision paralysis 怎么检测和缓解？

检测：

1. action history hash：把最近 K step 的 (action, observation) 做 fingerprint，比较是否重复
2. embedding-level similarity：把每个 step 的 (thought, action) 嵌入向量，连续相似度高于阈值 → flag loop
3. reward stagnation：每 step reward 不变 → 可能 loop

缓解：

1. 强制 explore：检测到 loop 后调高 temperature 或加 random prompt 扰动
2. explicit "give up" action：让 agent 知道 "I cannot solve this" 是合法 → 避免假装能解
3. history compaction：周期性把 history 压成 summary，强制 agent forget bad pattern
4. outer-loop time budget：单 step 超时 → orchestrator 强制干预

Q19. SWE-bench Verified / SWE-Lancer / MLE-bench 各测什么？怎么选？

Benchmark | 测什么 | 任务长度
--- | --- | ---
SWE-bench Verified | 真实 GitHub Python bug 修复（人审过 500/2294 题） | 小时级
SWE-Lancer | 真实 Upwork freelance task（含 IC + managerial） | 小时 ~ 天级
MLE-bench | Kaggle ML 比赛（数据探索 + 模型训练） | 天级 (24h budget)
OSWorld | Real OS GUI 任务（截屏 + mouse/keyboard） | 分钟级
TAU-bench | Customer service multi-turn | 分钟级

选：

- 想 demo coding agent → SWE-bench Verified（事实工业标准）
- 想 demo 经济价值 → SWE-Lancer（payment 信号）
- 想 demo ML R&D agent → MLE-bench
- 想 demo OS / desktop agent → OSWorld（最难）
- 想 demo 客服对话 + tool → TAU-bench

Q20. stale memory 比 missing memory 更危险？

是的：

- missing memory：agent retrieve 不到 → 主动 search 新信息 / 老实承认不知道
- stale memory：agent retrieve 到过时 fact → confidently wrong（不会 search verify）

例：

    Memory (6 个月前): "OpenAI API endpoint = api.openai.com/v1"
    Reality: 该 endpoint 已迁移到 /v2 with new auth scheme
    Agent: 调用旧 endpoint → 403 forbidden → 困惑 → 反复 retry

缓解：

1. TTL on memory：每条 memory 带过期时间戳
2. memory consistency check：周期对照外部 source（如 API docs）
3. prefer recent over similar：retrieval score = sim × exp(-age/τ)
4. explicit refresh signal：如果 retrieve 出来的 fact 用了 → action 失败 → 标记该 memory stale → 降权 / 删除

### Level 3 — 顶级 lab（5 题）

Q21. 推 multi-agent debate 收敛性的充分条件（formal），并解释 Liang 2024 加 judge 的本质作用？

Setup：$N$ agent，每个在 round $k$ 给出 answer $x_i^{(k)} \in \mathcal{A}$。Round-update operator：

$$x_i^{(k+1)} = T_i\!\left(x_1^{(k)}, \dots, x_N^{(k)}\right)$$

Joint operator $T : \mathcal{A}^N \to \mathcal{A}^N, \; (T(x))_i = T_i(x)$。

重要前置：直接说 "Banach contraction → 唯一不动点" 是 错的。Debate 的 averaging 算子（majority + softmax）通常是 doubly-stochastic 形，对应 $A \mathbf{1} = \mathbf{1}$，特征值 1 总是存在 —— 严格 $\beta < 1$ 通常不成立。正确的收敛性 framework 是 consensus dynamics（多智能体一致性理论），结论是收敛到 fixed-point set（一致 cluster）而非唯一不动点。

线性 averaging 情形（formal）：

$$x_i^{(k+1)} = \sum_{j} A_{ij}\, x_j^{(k)},\quad A \in \mathbb{R}^{N \times N}\text{ doubly-stochastic}$$

由 Perron-Frobenius，$\lim_{k \to \infty} A^k = \mathbf{1} \pi^\top$（$\pi$ 是 stationary distribution），故 $x_i^{(k)} \to \pi^\top x^{(0)}$，所有 agent 同意 stationary mean。fixed-point set 是 $\{c \mathbf{1} : c \in \mathbb{R}\}$（参数化的 consensus 直线），起点不同 $c$ 不同——所以不是 Banach 唯一不动点。

非线性 case (softmax-over-peers)：

$$T_i(x) = \sum_{j \ne i} w_{ij}(x) \cdot x_j$$

若 $w_{ij}$ 是 majority-vote softmax（temperature $\tau$），收敛动力学非线性，但 fixed-point set 仍是若干离散 consensus cluster（每个对应一个候选答案的全员同意）；从不同 initial 收敛到不同 cluster。真要唯一不动点需要 anchor agent（固定 reference），但那已经不是 debate。

Liang 2024 (affirmative vs negative) 不收敛：

Liang 把 agent 分两组 (affirmative / negative)，affirmative 倾向 confirm 当前 majority，negative 倾向 否定 majority。两组互推 —— fixed-point set 为空或者 disjoint，没有公共 consensus。

加 judge：

$$x^{(k+1)} = J(x_\text{aff}^{(k)}, x_\text{neg}^{(k)})$$

$J$ 是 外部 contractive operator（不基于 affirmative/negative 内部 update，由独立 judge LLM 决策），把整个迭代映射到一个新的 contractive 系统。Judge 引入了人工 contraction——这是 Liang 2024 加 judge 的本质：用 design 引入 $\beta < 1$ 的外部信号。

经验校准：

Du 2023 实验观察到 GSM8K 类推理任务上：N=1 baseline → N=3 R=2-3 即可大幅提升 (+5-10pp)，N=5 在 N=3 之上仅边际提升。这与 $\beta \approx 0.5$ 的几何收敛速度 $\beta^3 \approx 0.125$ 匹配（即 ~12.5% 的剩余不一致后就达到饱和）。Liang 2024 的 affirmative/negative + judge 设计在翻译 / counter-intuitive 推理上有类似 +5-8pp 的提升。

Q22. MemGPT 的 RAM vs disk 类比里 page fault 对 latency 的影响怎么量化？怎么 amortize？

单 turn 延迟模型（无 page fault）：

$$L_\text{single} = L_\text{prefill} + L_\text{decode} \cdot T_\text{out}$$

其中 $L_\text{prefill}$ 与 prompt 长度 $L_\text{in}$ 大约成线性（attention $O(L_\text{in}^2)$ 但被 KV cache 摊平），$L_\text{decode}$ 是 per-token decoding latency。

单 turn 延迟模型 (k 次 page fault)：

$$L_\text{with\_pf} = L_\text{single} + k \cdot (L_\text{search} + L_\text{rerun})$$

- $L_\text{search}$ ~ 50-200 ms (vector store)
- $L_\text{rerun}$ ~ 1 个完整 LLM call（重新 prefill + decode）

典型数字（GPT-4o-class，4K context input, 500 token output）：

配置 | latency
--- | ---
无 page fault | ~ 1.2 s
1 page fault | ~ 2.5 s
3 page fault | ~ 5-7 s

延迟 ~ 翻倍 per page fault。

Amortize 方法：

1. prefetch：基于当前 conversation predict 下一个 turn 需要什么 memory，在 user 输入 / LLM 思考时并行 retrieve
2. batch fault：把多个 small fault 合并成一次大 retrieval（cache locality）
3. hierarchical paging：常用 fact 缓存在 "L2 working memory"（不进 main context 但快速可取），冷数据在 archival
4. speculative archival：retrieve 时多拿 k+ 几条候选，可能用上（避免 next-turn re-fault）
5. streaming response：开始 search 时就开始 stream "I'm checking my notes..."，掩盖延迟
6. session warmup：session 开始时预先把高频 archival 拉到 working memory

理论 amortized 复杂度（OS page replacement 类比）：

若 working set 大小 $W$，main context 容量 $C$, $W \le C$ → 0 page fault（cache hit）。$W > C$ → fault rate $\sim (W - C) / W$ 。production 监控 fault rate < 30% 是健康。

Q23. 推导 RAG retrieval 的 similarity-based selection 概率，并解释为什么 cosine + temperature scaling 在长 retrieval 上崩？

Setup：query $q$, candidates $\{d_1, \dots, d_M\}$，embedding $e(\cdot)$，相似度 $s_i = e(q)^\top e(d_i) / (\|e(q)\| \cdot \|e(d_i)\|)$（cosine）。

Softmax selection：

$$P(d_i | q) = \frac{\exp(s_i / \tau)}{\sum_{j=1}^M \exp(s_j / \tau)}$$

- $\tau \to 0$：argmax（top-1）
- $\tau \to \infty$：uniform
- 实际 retrieval 用 top-k threshold 而非 softmax sample；但 softmax 视角对理论分析有用

长 retrieval 上为什么崩：

设 ground-truth doc $d^*$ 相似度 $s^* = e(q)^\top e(d^*)$, 其他 doc 相似度 $s_j$ i.i.d. ~ $\mathcal{N}(\mu, \sigma^2)$。

$$P(d^* = \arg\max_i s_i) = P(s^* > s_j, \forall j \ne d^*) = \prod_{j \ne d^*} P(s^* > s_j) \approx \Phi\!\left(\frac{s^* - \mu}{\sigma}\right)^{M-1}$$

当 $M$ 大：

$$\log P \approx (M - 1) \log \Phi\!\left(\frac{s^* - \mu}{\sigma}\right)$$

→ $P$ 关于 $M$ 是指数衰减：M 翻倍时 P 平方衰减。

直观：candidate pool 大 → noise distractor 多 → ground-truth 被淹没。

实际 RAG 系统 4 个崩塌点：

1. distractor density ↑：与 query 表面相关但语义无关的 doc 增多
2. embedding rank collapse：高维 embedding 在大语料上 collapse（Wang et al. 2022 anisotropy），所有 doc 都 ~ 等距
3. chunk boundary 错位：长 doc chunk 后 ground-truth 跨 chunk
4. lexical-semantic 错位：query 用 "RLHF" 但 doc 写 "human feedback fine-tuning"

修法：

- re-ranker（如 Cohere rerank, MS bge-reranker）：cross-encoder 重排 top-100 候选
- hybrid search：BM25 + vector ensemble (BM25 防 lexical 错位)
- query rewriting：用 LLM 把 query 改写多版本，每版本 retrieve top-k 取并集
- chunk overlap + summary：chunk 间留 overlap + chunk-level summary（structured retrieval）

Q24. 为什么 Agent-Q 的 DPO 训练后 inference 比 in-loop MCTS 快 10×？训练时 MCTS 数据怎么转 DPO preference？

Inference 速度差异：

- In-loop MCTS：每次 inference 跑 ~ 50 iteration × ~ 5 depth = ~ 250 LLM call，单 query ~ 1M token
- DPO-trained policy：单次 forward pass + greedy decode = ~ 1-3 LLM call（100× 少）

→ 实测 10× 是因为 trained policy 仍可能多次 sampling / re-plan，但比 MCTS 少 1-2 数量级。

MCTS → DPO 数据生成：

每次 MCTS rollout 产生一颗树 $\mathcal{T}$。在每个状态 $s$ 处有多个 child action $\{a_1, \dots, a_k\}$ 和各自的 visit count $N(s, a_j)$ + value $Q(s, a_j)$。

构造 preference pair：

对每个 state $s$：

- $a^+$ = argmax visit count (MCTS 探索后认为"好"的)
- $a^-$ = argmin visit count among visited (MCTS 探索后认为"差"的)

直接得 preference: $(s, a^+) \succ (s, a^-)$。

也可用 value gap 筛：只保留 $Q(s, a^+) - Q(s, a^-) > \delta$ 的对（高置信度 preference）。

DPO loss：

$$\mathcal{L}_\text{DPO} = -\log \sigma\!\left( \beta \log\frac{\pi_\theta(a^+ | s)}{\pi_\text{ref}(a^+ | s)} - \beta \log\frac{\pi_\theta(a^- | s)}{\pi_\text{ref}(a^- | s)} \right)$$

直接 fine-tune base LLM。

Agent-Q 结果（WebShop）：

方法 | success rate | inference cost
--- | --- | ---
Base LLM | 28% | 1×
ReAct | 38% | 1×
In-loop MCTS | 48% | ~100×
Agent-Q (DPO from MCTS) | 51% | 1×

→ MCTS at training, fast policy at inference 是 2024-2026 一个关键 design pattern——类比 AlphaGo Zero 的 self-play + DPO 风格 distillation。

面试加分：这个 pattern 也出现在 DeepSeek-R1 distill（R1-Zero MCTS-like search 产数据 → 蒸馏小模型）、rStar-Math（Microsoft 2025 MCTS + PPM self-evolution）——共同主题是 inference-time search 是产数据手段，不是部署目标。

Q25. 如果让你设计下一代 long-horizon agent，应该往哪几个方向走？（open-ended 顶级 lab 面试题）

可信回答框架（不需面面俱到，挑 2-3 个深入展开）：

- 方向 1 — typed memory + dependency DAG

  - 现状：memory 主要是 flat list（vector store）或 KG（GraphRAG）
  - 缺：事件之间的因果 / 依赖关系——为什么 retrieve 这条而不是那条？
  - Proposal：参考 A²RD 的 MVMem，把 episodic memory 之间建显式 dependency DAG（spatial/temporal/causal），retrieval 按图路径而不是单次 similarity
  - Expected failure：DAG 维护成本（事件多了图变密）；retrieval policy 选边算法（GNN？LLM-as-graph-traverser？）

- 方向 2 — self-evolving skill set + cross-time replay

  - 现状：agent skill 是人工写的 prompt template（如 ReAct, ToT, Reflexion）
  - 缺：agent 不会自动发现新 skill 也不会 deprecate 旧 skill
  - Proposal：Ctx2Skill 风格 5 角色 self-play（challenger, reasoner, judge, proposer, generator），用 cross-time replay 防止 over-specialization
  - Expected failure：skill collapse（少数 skill 占满所有 task）；reward hacking（generator 学会写让 judge 满意但实际无用的 skill）

- 方向 3 — heterogeneous multi-agent + cross-family verification

  - 现状：multi-agent 几乎全是同 base model
  - 缺：没有 cross-family verification——同 model 共享 hallucination
  - Proposal：Claude + Codex + Gemini 异质 co-evolution，跨模型 audit 防 self-confirmation bias
  - Expected failure：模型强弱 / 价格 / API 版本会混淆变量；reviewer 之间也可能共同 hallucinate

- 方向 4 — long-horizon cost model + adaptive budget

  - 现状：token 计费线性，但长任务实际是 quadratic
  - 缺：没有 cost-aware planner
  - Proposal：agent 决策时把 expected cost 加进 utility（不仅 reward），动态调整 verbosity / search depth / reflection 频率
  - Expected failure：cost prediction 不准（LLM 不会准确估自己用多少 token）；过度节俭导致 quality drop

- 方向 5 — formal verification / safety guarantees

  - 现状：reflection / debate / audit 都是 empirical
  - 缺：没有 formal correctness guarantee——多 agent 投票投错怎么办？
  - Proposal：借鉴 Bayesian truthful elicitation / peer prediction（如 Prelec score），给 audit 一个 incentive-compatible foundation
  - Expected failure：theoretical 桥到 production 难搭；agent 无法理解 truthful 激励

- 方向 6 — evaluation 标准

  - 现状：benchmark fragmented（TAU / OSWorld / SWE-bench 各测一面）
  - 缺：没有统一的 long-horizon 评测标准
  - Proposal：定义 horizon-axis benchmark：5 / 20 / 100 / 1000 step 在同一任务族上分别测；track per-step error compound rate（不是 final accuracy）
  - Expected failure：1000-step task 的人工标注成本极高；replay/contamination 难控制

- 方向 7 — sim-to-real for agent

  - 现状：训练 / 测试都在 simulator (WebArena)
  - 缺：sim-to-real gap——simulator 上的 agent 在真实 web 上崩
  - Proposal：把 robotics sim-to-real 工具搬到 agent（domain randomization, real-world fine-tune）
  - Expected failure：web/OS 比 robotics 更高维（视觉 + 文本 + workflow）；real-world 数据采集成本高

照搬现有方法 + 加一点 —— 不展现 research taste。关键是展现你能列 3-5 个 concrete proposal + 每个有 expected failure mode。

## §A 附录：核心 paper 时间线 + 一句话总结

按时间倒序（截止 2026-05）：

日期 | Paper | arXiv | 一句话贡献
--- | --- | --- | ---
2025-09 | Anthropic Claude Sonnet 4.5 + extended thinking | (no arXiv) | 长程 reasoning + budget-aware thinking
2025-03 | OpenAI Agents SDK | (no arXiv) | handoff / guardrails / tracing 抽象
2025-01 | OpenAI Operator | (no arXiv) | CUA-trained vision-language agent for web
2024-10 | Claude Computer Use | (no arXiv) | desktop GUI agent，OSWorld ~ 14.9% (2024)
2024-08 | Agent-Q | 2408.07199 | MCTS + DPO，WebShop 28% → 51%
2024-06 | MoA (Mixture of Agents) | 2406.04692 | N 个 proposer + aggregator 超 GPT-4 Omni
2024-06 | TAU-bench | 2406.12045 | customer service multi-turn agent benchmark
2024-05 | SWE-Agent | 2405.15793 | ACI for SWE-bench Lite 18.0%
2024-04 | OSWorld | 2404.07972 | real OS GUI 369 任务
2024-04 | GraphRAG | 2404.16130 | LLM-extracted KG + community for global QA
2024-01 | VisualWebArena | 2401.13649 | vision + web 任务
2023-12 | Math-Shepherd | 2312.08935 | MCTS rollout 自动标 PRM
2023-10 | LATS | 2310.04406 | MCTS + Reflexion + value
2023-10 | SWE-bench | 2310.06770 | 2294 真实 GitHub Python bug
2023-10 | MemGPT | 2310.08560 | OS-style virtual memory for LLM
2023-08 | AutoGen | 2308.08155 | conversable agent / GroupChat framework
2023-08 | MetaGPT | 2308.00352 | SOP-driven 软件公司 multi-agent
2023-08 | AgentBench | 2308.03688 | 8 envs 通用 agent benchmark
2023-08 | AgentVerse | 2308.10848 | expert recruitment + collaborative decision
2023-07 | WebArena | 2307.13854 | self-hosted real web benchmark
2023-07 | ChatDev | 2307.07924 | chat chain for software dev
2023-05 | RAP | 2305.14992 | MCTS + world model in LLM agent
2023-05 | Tree of Thoughts | 2305.10601 | LLM propose + LLM evaluate + tree search
2023-05 | Multi-Agent Debate (Du) | 2305.14325 | N agent debate → consensus
2023-05 | Multi-Agent Debate (Liang) | 2305.19118 | affirmative / negative + judge
2023-05 | MemoryBank | 2305.10250 | Ebbinghaus forgetting curve
2023-04 | Generative Agents (Park) | 2304.03442 | 25-agent sandbox social emergence
2023-03 | Reflexion | 2303.11366 | natural-language self-reflection from trajectory
2023-03 | CAMEL | 2303.17760 | role-play inception prompting
2023-03 | HuggingGPT | 2303.17580 | plan-then-execute with HF models
2022-10 | ReAct | 2210.03629 | thought-action 交替

建议精读 5 篇

准备面试时间有限时，按优先级读：

1. MemGPT (2310.08560) —— virtual-memory 抽象，长程 memory 鼻祖
2. MoA (2406.04692) —— multi-agent 实证最强 baseline
3. Multi-Agent Debate (Du, 2305.14325) —— debate 范式起源
4. LATS (2310.04406) —— tree-search agent 工程典范
5. MetaGPT (2308.00352) —— structured multi-agent SOP

常考开放题准备

顶级 lab interview 经常问 open-ended 题（如 Q25），关键是展现 research taste：能列出 3-5 个具体方向（不是"我会做 multi-agent" 这种空话），每个方向能给一个 concrete proposal + 一个 expected failure mode。

2026 秋招重点 framework / 工具链汇总

production agent 在 2026 的事实标准（面试可背）：

- commercial IDE-integrated：Cursor (Anysphere), GitHub Copilot Agent, Continue
- commercial coding agent：Devin (Cognition), Claude Code (Anthropic), OpenAI Codex CLI
- open-source CLI：Cline, Aider, opencode, codex-cli
- multi-agent framework：AutoGen (MS), CrewAI, LangGraph (LangChain), LlamaIndex AgentWorkflow, OpenAI Agents SDK
- protocol：MCP (Anthropic, LLM↔tool), A2A (Google, agent↔agent)
- benchmark：SWE-bench Verified（行业标准）+ TAU-bench + OSWorld + MLE-bench

读完 §10-§14 + 上述 5 篇 paper，multi-agent + long-horizon agent 面试题应能 80%+ 覆盖。