Multi Agent Long Horizon Tutorial En

§0 TL;DR Cheat Sheet

1. Paradigm positioning: a single LLM = "system 1, one forward pass"; an agent = "system 2, decomposing reasoning into perceive → plan → act → reflect". multi-agent = several LLMs role-playing distinct identities and collaborating; long-horizon = the same agent maintaining a goal across many turns / many days. The two axes are orthogonal but usually co-occur (e.g. ChatDev, MetaGPT).

2. Three multi-agent archetypes:

   • role-play dialogue (CAMEL, Li et al. NeurIPS 2023, arXiv 2303.17760): assistant-user inception prompting;
   • SOP / pipeline (MetaGPT, Hong et al. ICLR 2024, arXiv 2308.00352): decompose software development into seven fixed roles — PM / Architect / Engineer / QA, etc.;
   • debate / aggregation (Du et al. ICML 2024 arXiv 2305.14325 + Liang et al. EMNLP 2024 arXiv 2305.19118): N agents answer independently → cross-read → iterate over several rounds to consensus.
3. MoA (Mixture-of-Agents, Wang et al. ICLR 2025 Spotlight, arXiv 2406.04692): N proposers each produce an answer; an aggregator concatenates the N answers into its prompt and synthesizes. An open-source 6.5B-70B mix beats GPT-4 Omni on AlpacaEval 2.0.
4. Debate convergence — empirical observation + theoretical approximation: treat each agent's update as a mixture operator over peer answer distributions. If the operator has the doubly-stochastic averaging form (majority-vote softmax + temperature β), then by consensus dynamics (linear averaging operators on a doubly-stochastic graph) the iterate converges to a fixed-point set (a consensus distribution or a discrete consensus cluster), not a unique fixed point (Banach contraction generally fails — averaging operators always have eigenvalue 1). Empirically, the GSM8K accuracy gap between N=3 and N=5 is ≈ 1-2pp (diminishing returns, see Du 2023 Fig 4 + Liang 2024 Table 3).
5. MemGPT (Packer et al., arXiv 2310.08560, 2023-10): treat the LLM context as OS RAM and external storage as disk. A page fault = the model function-calls "search archival memory" to trigger retrieval. Latency cost: one page fault ≈ one extra LLM call (hundreds of ms to seconds), but avoids context overflow. Subsequently engineered under the name Letta (2024+).
6. GraphRAG (Microsoft 2024, arXiv 2404.16130): vector RAG collapses on multi-hop; GraphRAG first uses an LLM to extract entity-relation triples, builds a knowledge graph + community detection, makes hierarchical summaries, and then performs retrieval-augmented generation. Global queries ("summarize the themes of the whole document") beat vector RAG by 70-80%.

7. tree-search agents:

   • 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 + self-reflection (Reflexion) + value estimation;
   • Agent-Q (Putta et al., 2024, arXiv 2408.07199) = MCTS + DPO offline policy training. Common ground: all use the PUCT formula $a^* = \arg\max_a Q(s,a) + c_\text{puct} P(s,a) \sqrt{N(s)} / (1+N(s,a))$ to balance exploit / explore.
8. Three long-horizon benchmarks: 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, fixing real GitHub issues). 2026-05 SOTA on SWE-bench Verified ≈ 75% (Claude 4.6 Sonnet / o3, etc.), but OSWorld still < 60%.
9. Common pitfalls: multi-agent is not better with more (cost ∝ N, accuracy gain ∝ log N); long-CoT context overflow cannot be solved simply by writing a longer context window (lost-in-the-middle, Liu et al. TACL 2024 arXiv 2307.03172); stale memory is more dangerous than missing memory (wrong retrieval produces a confidently wrong answer); sub-agent blame-shifting ("that's worker A's fault") is common in hierarchical orchestrator setups.

§1 Intuition: from single LLM to agent system

1.1 Why a single LLM is not enough

Treating an LLM as a one-shot forward oracle $y = f_\theta(x)$ has three fundamental limitations:

• Bounded state: the context window is a hard physical limit (even 1M tokens are finite), so it cannot keep a goal in mind long-term
• One-shot decisions: a wrong sample is permanent — there is no "undo / replan" mechanism
• Capability slicing: a single prompt has to reason + act + verify, which causes role drift — earlier reasoning interferes with later verification

The essence of an agent is to externalize these three problems:

1.2 multi-agent vs long-horizon vs agentic

These three terms are often used interchangeably, but their precise meanings differ:

→ a real-world system usually touches all three (e.g. Devin = agentic (autonomous decisions) + long-horizon (debugging across hours) + multi-sub-agent (planner / executor / debugger)).

1.3 Two-thread framing (disambiguate every interview question first)

When the interviewer asks "how do you understand multi-agent systems?", the first sentence should disambiguate:

"Multi-agent literally means multiple LLMs collaborating, but semantically it splits into two threads: (1) cooperative (CAMEL / AutoGen / MetaGPT), where agents with different roles complete a single goal together; (2) adversarial / consensus-based (debate), where agents answer independently and then reconcile. In engineering practice the first is more common; in theoretical analysis the second is."

This disambiguation also generalizes to RLHF / Diffusion / RAG and other topics — a 30-second framing to win reviewer trust scores more than reciting paper titles directly.

§2 Core multi-agent collaboration paradigms

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) is the first widely cited LLM multi-agent paper (not the first multi-agent idea, but the first to make the prompt engineering systematic).

Core mechanism: two frozen LLMs, one playing the user (task initiator), one playing the assistant (task solver), with their roles locked in by an inception prompt to prevent drift:

[user prompt template]
You are <ROLE_USER>, working with <ROLE_ASSISTANT> to complete <TASK>.
Never give the answer directly; only issue an instruction, wait for the
assistant's reply, then give the next instruction.

[assistant prompt template]
You are <ROLE_ASSISTANT>, executing the instructions of <ROLE_USER>.
Never proactively ask a question or add a new task. After every reply,
say "Next request."

Key contributions: identifying two failure modes — role flipping (the assistant slipping into the user role) and task drift (task scope widening with conversation) — and mitigating them via prompt engineering.

2.2 AutoGen: GroupChat / a general multi-agent framework

AutoGen (Wu et al., arXiv 2308.08155, 2023-08, Microsoft Research; later published at COLM 2024 + presented at ICLR 2024 LLM Agents Workshop) abstracts multi-agent into conversable agents — each agent is an object with three methods: send / receive / generate_reply. GroupChat is its most influential mode: N agents share a single message queue and take turns speaking, with a GroupChatManager deciding who speaks next.

Pseudocode (concept):

class GroupChat:
    """ N agents share a message history and speak in turn per selector policy. """
    def __init__(self, agents, max_round=10):
        self.agents = agents
        self.messages = []
        self.max_round = max_round

    def select_speaker(self, last_speaker):
        # Three policies: round_robin / random / llm_selector (the LLM picks the next).
        # Production usually uses llm_selector: feed the manager LLM the history +
        # role descriptions, and let it choose the next speaker.
        ...

    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 software-company simulation

MetaGPT (Hong et al., ICLR 2024 (oral), arXiv 2308.00352) is the standard-bearer of pushing multi-agent toward structured workflow. Core insight: free-form GroupChat easily descends into chaos — letting PM / Architect / Engineer chat freely makes the topic drift; instead, hard-code an 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

Each role only receives the structured output of the previous node (no free-form chat), and its own output is also structured (a doc / code / test).

2.4 ChatDev / AgentVerse / Generative Agents

• ChatDev (Qian et al., ACL 2024, arXiv 2307.07924): similar in spirit to MetaGPT, software-development multi-agent, with a chat chain linking design / coding / testing across three phases. The codebase is small (~7B tokens) but was open-sourced early and has been widely forked.
• AgentVerse (Chen et al., ICLR 2024, arXiv 2308.10848): proposes a four-stage framework — expert recruitment + collaborative decision-making + individual action + evaluation. Expert roles are dynamically generated by an LLM (not from a fixed pool), suiting diverse-task scenarios.
• Generative Agents (Park et al., UIST 2023, arXiv 2304.03442, Stanford + Google): 25 agents live freely in a sandbox town, each with a daily routine + memory stream + reflection. Birthday parties, dates, mayoral campaigns, and other social behaviors emerge — the first time LLM agents have exhibited social emergence.

2.5 Mixture-of-Agents (MoA) — the catchiest work at NeurIPS 2024

The core idea of MoA (Wang et al., NeurIPS 2024, arXiv 2406.04692, Together AI) is so simple no one would believe it:

        ┌─ proposer_1 (Qwen2-72B)
prompt ─┼─ proposer_2 (LLaMA3-70B)  ──→ aggregator (Qwen2-72B):
        ├─ proposer_3 (WizardLM)         "synthesize these N responses
        └─ proposer_N (Mixtral)            into a final answer"

Key observation (Wang 2024 Fig 3): concatenating the responses of N proposers directly into the aggregator's prompt works better than best-of-N (picking the highest-reward one). Why: the complementary signal from multiple imperfect answers carries more information than a single best answer.

MoA LC win rate on AlpacaEval 2.0:

def moa_inference(prompt, proposers, aggregator, num_layers=3):
    """ Wang 2024 multi-layer MoA (paper default: 3 layers). """
    responses = [p(prompt) for p in proposers]
    for layer in range(num_layers - 1):
        # Each layer feeds the previous layer's N responses to the same
        # batch of proposers to regenerate.
        aggregate_prompt = build_moa_prompt(prompt, responses)
        responses = [p(aggregate_prompt) for p in proposers]
    # Final layer uses the aggregator instead of the proposers.
    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: from Society of Mind to modern implementations

3.1 Historical lineage

• Minsky 1986 "Society of Mind": human intelligence is not a single process but multiple simple "agents" in a mind-society criticizing and supplementing each other. This is the conceptual prototype of multi-agent debate, but in 1986 there was no executable algorithm.
• Du et al. ICML 2024 (arXiv 2305.14325, MIT): "Improving Factuality and Reasoning in Language Models through Multiagent Debate" — the first instantiation of Society of Mind with LLMs: N agents each give an answer, revise after seeing each other's answers, and converge in 2-3 rounds. +6-10pp on GSM8K.
• Liang et al. EMNLP 2024 (arXiv 2305.19118, Tencent AI Lab): "Encouraging Divergent Thinking in LLMs through Multi-Agent Debate" — adds a judge role, with affirmative / negative agents in opposition and the judge arbitrating. +5-8pp on translation / counter-intuitive reasoning tasks.

3.2 Minimal runnable implementation

import re
from collections import Counter

def extract_answer(response: str) -> str:
    """Extract the final answer from an LLM response. Production needs more robust parsing (\\boxed{}, LaTeX, units)."""
    m = re.search(r"(?:final answer|answer)[:]\s*(.+?)(?:\n|$)", response, re.IGNORECASE)
    if m:
        return m.group(1).strip()
    # Fallback: take the last line.
    return response.strip().split("\n")[-1].strip()

def majority_vote(answers: list[str]) -> str:
    """Plain majority vote; on ties, return the first 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-style debate.

    Args:
        agents: List of N callable LLMs (same or different)
        num_rounds: 2-3 rounds usually suffice (diminishing returns)
    Returns:
        Final majority answer
    """
    # Round 0: each agent answers independently.
    responses = [a(query) for a in agents]

    for r in range(num_rounds):
        new_responses = []
        for i, a in enumerate(agents):
            # Show the *other* agents' answers to 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

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

3.3 Convergence: under what conditions does debate "converge"?

1. Linear averaging case: if $T$ is a linear doubly-stochastic operator $A$ (i.e. $A \mathbf{1} = \mathbf{1}, A^\top \mathbf{1} = \mathbf{1}$), then by Perron-Frobenius the iterates $x_k = A^k x_0 \to \pi^\top x_0 \cdot \mathbf{1}$, i.e. they converge to a consensus value (all agents agree), but different starting points yield different consensus values — the fixed-point set is $\{c \cdot \mathbf{1} : c \in \mathbb{R}\}$
2. Nonlinear case (softmax / majority vote): the fixed-point set is typically several discrete consensus clusters (each corresponding to unanimous agreement on a candidate answer); which cluster the iteration falls into depends on the initial majority
3. For a true Banach fixed point: you need to inject an external contraction (e.g. an anchor agent fixed to a reference answer), but this degenerates to a non-debate algorithm

Practical implications for convergence:

• majority pull is strong (an agent is easily swayed when peers agree) → the attraction basin of the majority cluster in the fixed-point set grows
• low temperature (agent leans to the majority answer) → fast convergence but easy to land in a local consensus (even a wrong answer)
• heterogeneous agents (different models / prompts) → fixed-point sets may not overlap, so no consensus emerges

Liang 2024's affirmative-negative counterexample: deliberately designed adversarial agents break the averaging structure — strictly speaking it is not "$\beta \ge 1$", but rather no common fixed-point set (two clusters push each other), which is why a judge is required as an external arbiter.

3.4 N=3 vs N=5: marginal-return analysis

Empirical observation (synthesizing the experiments in Du 2023 / Liang 2024):

→ Marginal returns drop sharply from N=3 to N=5; N=3, R=2-3 captures most of the gain. Exact numbers depend on the task (math vs trivia vs translation behave differently).

§4 Coordination protocols: A2A / blackboard architecture / hierarchical orchestrator

4.1 Communication-protocol stack

• MCP (Model Context Protocol, Anthropic Nov 2024): protocol between LLM ↔ tool, not between agent ↔ agent. But many agent frameworks expose sub-agents as tools via MCP ("sub-agent as tool").
• A2A (Agent-to-Agent, Google April 2025): explicitly targets multi-agent interconnection, defining four core objects — agent card / task / message / artifact — over HTTP+JSON-RPC. As of 2026-05 still in spec stage with limited industry adoption.
• OpenAI Agents SDK (2025) provides handoff / guardrails / tracing abstractions; in practice it is a proprietary OpenAI protocol.

4.2 Blackboard architecture

A classical AI architecture (HEARSAY-II 1980, DARPA project): multi-agent share a globally readable / writable "blackboard", and each agent looks at the blackboard to decide whether to speak. The LLM-era variant looks like:

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

Pros: decoupling — agents don't need to know about each other, they only care about the blackboard state. Cons: you need a control unit to decide who speaks (else chaos). AutoGen GroupChat is essentially a blackboard + LLM-as-control-unit.

4.3 Hierarchical orchestrator + worker (the Claude Code pattern)

The de facto standard for production agents in 2024-2025: 1 orchestrator + N workers.

           ┌──────────────────────┐
           │   Orchestrator       │ ← look at user query, decide:
           │   (main LLM, big)    │   - split into subtasks
           │                      │   - which worker handles which
           │                      │   - how to aggregate results
           └──────────────────────┘
                ↓     ↓     ↓
         ┌──────┘     │     └──────┐
         ↓            ↓            ↓
    ┌────────┐  ┌────────┐  ┌────────┐
    │Worker A│  │Worker B│  │Worker C│
    │ (code) │  │ (web)  │  │ (math) │
    └────────┘  └────────┘  └────────┘

Claude Code Agent / Cline / Aider all follow this pattern:

• Claude Code Agent: main loop = orchestrator; TaskCreate spins up a subagent (different system prompt + subset of tools), and on completion the subagent passes its final message back to the orchestrator.
• Cline: plan mode = orchestrator thinking, act mode = worker execution (same LLM, different prompt).
• Aider: automatically splits large changes into small commits; each commit is a sub-conversation.

4.4 Sub-agent blame-shifting (a common bug)

Orchestrator: "Task failed."
Worker A: "I finished the code. Worker B's tests are broken."
Worker B: "My tests are fine. Worker A's code has bugs."
Orchestrator: stuck in deadlock

Root cause: each worker only sees its own conversation, with no ground-truth artifact.

Fixes:

1. Artifact-level verification: have workers run unit tests / linters and use the result as objective evidence
2. Third-party judge: spin up a separate fresh-context judge LLM that reads both conversations + artifacts and decides
3. Incremental commit: persist each worker's output to disk immediately + checksum; on blame, diff the files directly

§5 Long-horizon agents: memory architecture

5.1 Three memory classes: sensory / short-term / long-term

Borrowing the Atkinson-Shiffrin three-stage model from cognitive psychology:

Long-term further splits in two (Tulving 1972):

• Episodic memory: concrete events ("yesterday I discussed RLHF with Alice")
• Semantic memory: abstract knowledge ("the DPO loss is ...")

In an agent system:

• episodic ≈ trajectory log (past sequences of action + observation)
• semantic ≈ knowledge base (papers, docs, API knowledge)

5.2 MemGPT: OS-style virtual memory

MemGPT (Packer et al., arXiv 2310.08560, 2023-10; engineered as Letta 2024+) treats LLM context as OS RAM and the external vector store as 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          │
   └──────────────────┘

Key terms:

• Main Context = the current LLM input (system prompt + working context + recall snippets + dialogue)
• Recall Memory = past conversation history (stored chronologically)
• Archival Memory = arbitrary facts / documents (stored by semantics)
• Page Fault = main context is insufficient, so the LLM needs to retrieve archival/recall content → triggers a function call

Impact of page faults on latency:

→ A page fault roughly doubles per-turn latency. Production systems often use prefetch (predicting which archival items will be needed and retrieving them in advance) to mitigate.

5.3 MemoryBank: hippocampus-inspired

MemoryBank (Zhong et al., AAAI 2024, arXiv 2305.10250) is inspired by the Ebbinghaus forgetting curve: each memory carries a strength and a last_access_time, with exponential decay:

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

Retrieval ranks by similarity × current strength, and frequently accessed memories recover their strength (mimicking hippocampal reactivation).

5.4 GraphRAG: knowledge graph + community

The core problem of vector RAG (the most naive RAG): it collapses on multi-hop / global questions.

For example:

• "Summarize the design philosophy of the whole codebase" → vector RAG can only fetch a few files and cannot synthesize globally
• "Who is Alice's friend's friend" → a three-hop query; a single vector retrieval cannot fetch the three-hop path

GraphRAG (Microsoft 2024, Edge et al., arXiv 2404.16130) solution:

Stage 1 (offline, expensive):
  document → LLM extracts (entity, relation, entity) triples
         → build KG → Leiden community detection → multi-level community summaries

Stage 2 (online, cheap):
  query → classify (local entity? global theme?)
       ↓
  local: find the most relevant entity, look at neighbors, supplement with vector RAG
  global: map-reduce over community summaries

Wins:

Losses:

• High offline cost (building the KG requires scanning the whole corpus once)
• KG schema design makes or breaks everything

5.5 Code: dual-track 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:
    """ Simplified MemoryBank + episodic / semantic dual-track. """
    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 boost: each access strengthens by +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 (assumed normalized)
            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]]
        # Access strengthens.
        for it in top:
            it.last_access = now
            it.access_count += 1
        return top

§6 Planning + tree-search agents

6.1 Plan-then-execute paradigm

HuggingGPT (Shen et al., NeurIPS 2023, arXiv 2303.17580, Microsoft + Zhejiang U) is an early representative:

User Query
   │
   ↓
LLM (Plan)         ← use ChatGPT to decompose the task into a sub-task DAG
   │
   ↓
HF Models (Execute) ← invoke various vision / speech models on HuggingFace
   │
   ↓
LLM (Aggregate)    ← synthesize the outputs of all sub-tasks

Problem: the plan is fixed at the start and cannot replan on execution failure. This is the motivation for the ReAct / Reflexion / tree-search line of work.

6.2 ReAct: interleaving thinking + acting

ReAct (Yao et al., ICLR 2023, arXiv 2210.03629, Princeton + Google) format:

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 and action interleave at every step, and this format is now the de facto foundation of every agent — AutoGPT / LangChain Agent / Toolformer are all ReAct variants.

6.3 Tree of Thoughts (ToT)

ToT (Yao et al., NeurIPS 2023, arXiv 2305.10601) introduced explicit search for the first time:

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

• Expand: the LLM proposes K thoughts
• Evaluate: the LLM scores each thought / labels it "sure / maybe / impossible"
• Search: BFS (advance layer-by-layer top-k) or DFS (with backtracking)

6.4 RAP: MCTS + world model

RAP (Hao et al., EMNLP 2023, arXiv 2305.14992) upgrades ToT: replace the LLM-as-evaluator with MCTS + LLM-as-world-model.

MCTS step:
  1. select: pick a leaf via the PUCT formula
  2. expand: LLM proposes the next action
  3. simulate: LLM rolls out to terminal, estimating reward
  4. backup: propagate reward up the path to update Q(s, a)

PUCT formula (AlphaGo's improved UCT):
  a* = argmax_a [ Q(s, a) + c_puct * P(s, a) * sqrt(N(s)) / (1 + N(s, a)) ]

The formula's terms:

$$\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)$: mean rollout reward from $(s, a)$
• $P(s, a)$: prior probability (action probability given by the LLM)
• $N(s)$: visit count of state $s$
• $N(s, a)$: visit count of edge $(s, a)$
• $c_\text{puct}$: exploration constant (typically 1.0-3.0)

Intuition: the first term $Q$ exploits (pick high-reward), the second term explores (pick low-visit + high-prior). $\sqrt{N(s)} / (1 + N(s,a))$ is a UCB1 + AlphaGo prior hybrid.

6.5 LATS: MCTS + Reflexion + value

LATS (Zhou et al., ICML 2024, arXiv 2310.04406, Penn + UIUC) further adds Reflexion to RAP:

For each expansion:
  1. action = LLM_policy(state, history)
  2. observation = env.step(action)
  3. value = LLM_value(state, history)   ← scalar estimate
  4. if failed: reflection = LLM_reflect(history)  ← injected into the next prompt
  5. back-propagate value along the path

LATS outperforms ReAct + Reflexion on HotpotQA / WebShop / HumanEval.

6.6 Agent-Q: MCTS + DPO offline training

Agent-Q (Putta et al., 2024, arXiv 2408.07199, MultiOn + Stanford) reflects on this: MCTS at inference time is too slow — can we use MCTS offline to generate data for training a 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: directly use the fine-tuned LLM (no MCTS), with much higher speed

Result: WebShop success rate goes from 28% → 51%, while inference speed is 10× faster than in-loop MCTS.

6.7 LATS-style tree search implementation (~60 lines core)

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 from (parent.state, node.action) through env to terminal or depth cap.

    Args:
        llm_propose_one: policy — returns a single action for a given state (greedy/random rollout)
        llm_value:       value — estimates the remaining cumulative reward from a state
    """
    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 picks the next action
    node.state = state
    return cum_r + llm_value(state)            # value head estimates the remainder

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 estimation.

    llm_propose:       at expand, given (state, k) → [(action, prior)]
    llm_propose_one:   during rollout, given state → action (policy)
    llm_value:         value estimate, given state → remaining 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 comparison table (2024-2026)

7.2 Benchmark selection decision table

7.3 What benchmark horizon length implies about failure modes

• Short horizon (5-20 steps): failures are mainly single-step errors (misreading the query / calling the wrong tool)
• Medium horizon (20-100 steps): context overflow / lost-in-the-middle / replan failures start to appear
• Long horizon (100+ steps, multi-day): memory stale, sub-agent blame, cost explosion, decision paralysis

At long horizon, every additional 10 steps roughly halves success rate (an internal Anthropic 2025 observation, partially mentioned in public blogs — not a strict scaling law) — which is why long-horizon agents are the most difficult and most research-valuable direction of 2026.

§8 Failure modes unique to long-horizon

8.1 Context overflow + lost-in-the-middle

Liu et al. TACL 2024 (arXiv 2307.03172) found: the LLM's utilization of information in the middle of its context is significantly lower than at the beginning or end — a U-shape curve (head > tail > middle).

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

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

Implications for long-horizon agent design:

1. Don't put important facts in the middle — put the task instruction at the head + the current working memory at the tail
2. The context window is not always better when longer — utilization drops significantly above ~30K
3. Periodic summarization — periodically summarize the middle context into short snippets pushed to the tail

8.2 Error compound / drift

In long tasks even a small per-step error rate makes the whole thing fail eventually. A simplified model:

Let single-step success rate be $p$; under independence assumption, total success over $T$ steps is:

$$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$

→ An agent with single-step 95% has only 7.7% success on a 50-step task — single-step must be pushed to 99%+ for 50 steps to hold up.

Mitigations:

• Rollback / replan: checkpoint every N steps, roll back on failure (analogous to keyframes in video gen)
• Hierarchical sub-tasks: split a 50-step task into 5 ten-step sub-tasks, each of which can fail and retry independently
• Self-verify after each critical step: have a verifier check after every key action

8.3 Decision paralysis / loop

The agent gets stuck in a state and repeats the same action:

Action: search("foo")
Observation: no results
Thought: I should search with different keywords
Action: search("foo")   ← again!
Observation: no results
...

Root cause: the LLM, given that prompt context, is greedy-decoded into the same mode.

Fixes:

1. action history hash: detect whether the last N steps are repeating (fingerprint), and force exploration if so
2. temperature ramp: bump the temperature after K consecutive failures
3. explicit "give up" tool: let the agent know "I cannot solve this" is a legal action (to avoid pretending it can solve)

8.4 Stale memory

The agent retrieves a stale memory and makes a decision based on it. Example:

Memory: "API endpoint = https://api.foo.com/v1/users"
Reality: the endpoint has migrated to /v2/users (memory is 6 months old)
Agent: calls the old endpoint → 404 → confused

More dangerous than missing memory: missing memory makes the agent actively search for new info, but stale memory makes the agent confidently wrong.

Mitigations:

1. TTL on memory: each memory carries an expiration timestamp; once expired, demote or remove
2. Memory consistency check: weekly job to diff memory against ground truth
3. Prefer recent over similar: change retrieval from sim to sim * exp(-age/τ)

8.5 Sub-agent conflict / blame-shifting

See §4.4.

8.6 Cost explosion

A long-horizon agent's token consumption is not linear:

• Every turn feeds the full history into the LLM (the KV cache cannot save prompt-token billing)
• Cumulative cost over $T$ turns $\sim \sum_{t=1}^T O(t \cdot c) = O(T^2 c)$, where $c$ is the per-turn new-token count

Measurement: a 50-turn agent task consumes ~ 50-200× the tokens of a 5-turn task (not 10×).

§9 Self-improvement + verification loops

9.1 Reflexion: reflecting from the trajectory log

Reflexion (Shinn et al., NeurIPS 2023, arXiv 2303.11366) algorithm:

For each episode:
  1. trajectory = run agent on task
  2. reward = evaluator(trajectory)
  3. if reward low:
       reflection = LLM(trajectory, reward)
                    --> natural-language summary of the failure cause
       memory.add(reflection)
  4. Next episode: prompt includes memory

Natural-language reflections have higher information density than scalar rewards — the agent knows not only that it "failed" but why.

9.2 Test-time self-improvement (frame + video two-level)

A²RD-style hierarchical test-time self-improvement (HITS) (Liu et al. 2026):

• Frame-level: after generating each segment, check with a frame-level verifier (face deformation? lighting inconsistencies?)
• Video-level: every K segments, do a video-level check (long-range consistency? character drift?)

Analogy for long-horizon agents:

• Step-level: check with unit tests / linters after each action
• Sub-task-level: integration check after each sub-task
• Task-level: final acceptance test

9.3 Cross-Time Replay (avoid over-specialization)

Ctx2Skill-style Cross-Time Replay:

• Maintain a hard probe set (historical hard cases that failed) and an easy probe set
• After each agent skill update, re-evaluate on both sets
• Pick the version that maximizes $\rho_\text{hard} \times \rho_\text{easy}$ (not just whichever does better on the current task)

This prevents the agent from "learning to cheat" on the new task and regressing on old capabilities (catastrophic forgetting at the skill level).

9.4 Dependency DAG for memory retrieval

A²RD-style MVMem uses a dependency DAG to decide which past segments to retrieve when generating a given segment:

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

→ When generating seg_5, only retrieve {seg_1}, instead of stuffing all of {seg_1..seg_4} into the prompt.

Implication for long-horizon agents: explicitly model the dependencies between episodic memories as a graph (not a flat list), and traverse by graph paths instead of brute-force similarity at retrieval time. Production is still exploring (GraphRAG is an early attempt).

§10 Engineering practice: 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-style orchestrator + N workers (with 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:   # budget exhausted → 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})
        # Steps exhausted: forced finalize
        return self.llm_orch(query=query, history=self.history,
                             budget=self.budget.remaining(),
                             hint="forced_finalize")["answer"]

§11 Complexity analysis

11.1 Cost model for multi-agent collaboration

Let:

• $N$ = number of agents
• $R$ = debate / collaboration rounds
• $C$ = average token cost per LLM call
• $L$ = accumulated message history length

Round-robin GroupChat: $$\text{cost} = N \times R \times C \times O(L)$$ where $L$ grows monotonically (each agent writes a message and all agents read), so the total cost $\approx O(N^2 R^2 C)$ (assuming each message length is roughly constant, so $L \propto NR$) — both N and R are quadratic.

MoA (N proposers + 1 aggregator): $$\text{cost} = (N + 1) \times C \times O(L_\text{prompt}) + 1 \times C \times O(NL_\text{response})$$ Linear in $N$, so actually cheaper.

Debate (Du 2023): $$\text{cost} = N \times R \times C \times O(NL_\text{response})$$ (each agent reads the other $N-1$ responses) → $O(N^2 R C L_\text{response})$.

Comparison:

→ GroupChat is the most expensive (which is why production AutoGen almost universally switched to hierarchical orchestrator).

11.2 Long-horizon agent memory cost

Let $T$ = total number of turns and $M$ = total memory size.

• No retrieval (all in context): cost $\sim O(T^2)$ (each turn looks at the full history)
• Vector RAG: each turn retrieves $k$ memories, 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 faults add ~ 2× per-turn latency

11.3 PUCT-based tree search

LATS / Agent-Q-class tree search at inference:

• One search: $O(I \cdot D \cdot C)$, where $I$ = MCTS iterations, $D$ = max depth, $C$ = per-LLM-call cost
• $I = 50, D = 5, C = $ 4K tokens → ~ 1M tokens per query

→ Tree search at inference is expensive — this is exactly the core motivation of Agent-Q (use offline MCTS to train, then deploy the fine-tuned policy directly).

§12 Comparison with related methods

12.1 Multi-agent vs single-agent + reflection

Empirical: if N agents use the same base model + same prompt, multi-agent and self-consistency yield nearly the same gain (shared bias), and there is no point doing multi-agent.

12.2 Tree search vs long CoT (o1-style)

12.3 Memory architecture selection

§13 2025-2026 frontier systems

13.1 Anthropic Claude Code Agent / Computer Use

• Claude Computer Use (Oct 2024): lets Claude operate the desktop directly (screenshot → reason → mouse/keyboard action). ~ 14.9% on OSWorld (2024), reaching ~ 60% by 2026-05 (Anthropic blog).
• Claude Code Agent (Feb-2025 GA): orchestrator + subagent pattern; subagents are spawned via TaskCreate (different system prompt + tool subset). Opened to developers as a CLI tool.

13.2 OpenAI Operator / Agents SDK

• Operator (Jan 2025): the counterpart to Anthropic Computer Use, but with a CUA (Computer-Using Agent) trained specifically as a vision policy (not general Claude); WebArena accuracy ≈ 58.1%.
• OpenAI Agents SDK (Mar 2025): a Python framework providing handoff / guardrail / tracing abstractions. Handoff = the orchestrator "handing off" the task to another agent (more than a tool call).

13.3 Cognition Devin / SWE-Agent

• Devin (Cognition, Mar 2024 demo): the first commercial "AI software engineer" demo, capable of plan + code + debug + browser end-to-end. SWE-bench Verified ~ 13.9% (Mar 2024) → ~ 50% (late 2025, Devin 3.0).
• SWE-Agent (Yang et al., NeurIPS 2024, arXiv 2405.15793, Princeton): an open-source SWE-bench agent that proposed the Agent-Computer Interface (ACI) concept — designing a dedicated file-edit / shell / search interface for the LLM (not giving it bash directly), reaching 18.0% on SWE-bench Lite.

13.4 Cursor / Cline / Aider / Continue

• Cursor (Anysphere): commercial IDE-integrated agent, with plan/act mode switching; Composer is a multi-file-edit subagent.
• Cline (open-source, originally Claude Dev): VS Code extension, open-source orchestrator + worker, GitHub stars grew to 30K+ in 2025.
• Aider: CLI tool; repo-map + LLM auto-commit; automatically splitting large changes into small commits is a benchmark of long-horizon engineering.
• Continue: a self-hosted alternative, can be wired to a self-hosted LLM.

§14 25 frequently-asked interview questions — L1 must-know / L2 advanced / L3 top-lab

Level 1 — must-know (10 questions)

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: each agent answers independently
Round 1: each agent sees the other N-1 answers → revises
Round 2: revise again
...
Final: majority vote

Level 2 — advanced (10 questions)

Q: "Who is Alice's friend's friend?"
Vector space: "Alice", "Alice's friend", "Bob's friend" are not necessarily close in embedding

Stage 1 (offline):
  doc → LLM extracts triples (Alice, friend, Bob), (Bob, friend, Carol)
       → build KG → Leiden community detection → multi-level community summaries

Stage 2 (online):
  multi-hop query: Alice → friend → ?? → friend → ??
  KG traversal directly yields Carol
  global query: map-reduce over community summaries

Memory (6 months ago): "OpenAI API endpoint = api.openai.com/v1"
Reality: this endpoint has migrated to /v2 with a new auth scheme
Agent: calls old endpoint → 403 forbidden → confused → keeps retrying

Level 3 — top-lab (5 questions)

§A Appendix: core paper timeline + one-sentence summaries

In reverse chronological order (as of 2026-05):

After reading §10-§14 + the 5 papers above, you should cover 80%+ of multi-agent + long-horizon agent interview questions.