Multi-Agent & Long-Horizon 面试 Cheat Sheet

§0 TL;DR Cheat Sheet

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 的本质是把这三个问题外部化：

1.2　multi-agent vs long-horizon vs agentic

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

→ 一个真实系统通常三个都涉及（比如 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 工程缓解。

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

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（文档/代码/测试）。

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。

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：

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 "收敛"？

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

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

4.1　通信协议层级

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

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 三级模型：

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

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

在 agent 系统里：

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

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 的影响：

→ 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）。

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：

Loss：

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

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

§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）

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 单独用强。

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

§7 long-horizon evaluation benchmarks

7.1　Benchmark 对比表（2024-2026）

7.2　benchmark 选择决策表

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 检查

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×）。

§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 验收

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"]

§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})$。

对比：

→ 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

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

12.2　Tree search vs long CoT (o1-style)

12.3　memory architecture 选型

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

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

Level 1 — 必会（10 题）

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

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

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

Level 2 — 进阶（10 题）

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

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

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

Level 3 — 顶级 lab（5 题）

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

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

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