Prompt · Context · Harness · Graph Engineering — and Self-Improving AI

The engineering stack around a frozen model: how you prompt it, what context you feed it, the harness you wrap it in, the graphs you impose on it — and how systems improve themselves.

Prompt engineering · context engineering · harness engineering · graph engineering · agent skills · self-improvement · self-learning · recursive self-improvement (RSI).

Updated August 2026 with 2025–2026 SOTA — new entries marked ★. Method names link to their primary papers (arXiv / official page).

August 2026 · Updated Edition

Contents

1. The Engineering Stack: A Taxonomy
2. Prompt Engineering
3. Context Engineering
4. Harness Engineering
5. Graph Engineering
6. Self-Improvement & Self-Learning
7. Recursive Self-Improvement (RSI)
8. Putting It Together: The 2026 Self-Improving Agent Stack
9. Mathematical Deep Dives

Appendix A: Thirty-One Things to Memorize Appendix B: Decision Guide — "Which Technique?" Appendix C: Glossary Appendix D: Year-by-Year Milestones

1. The Engineering Stack: A Taxonomy

The model weights are fixed at inference. Everything that determines whether a fixed model behaves like a toy or an expert lives in the engineering stack around it. Four concentric layers, from innermost to outermost:

• Prompt engineering — the wording of a single request: instructions, exemplars, format, reasoning elicitation. Governs one call.
• Context engineering — what tokens occupy the window across a multi-turn, multi-tool run: retrieval, memory, compaction, ordering. Governs the state fed to every call. Superset of prompt engineering.
• Harness engineering — the loop, tools, control flow, verification, and orchestration wrapped around the model: the scaffold that turns a next-token predictor into an agent. Governs how many calls, in what topology, with what feedback.
• Graph engineering — imposing explicit graph structure (nodes + typed edges) on reasoning, retrieval, memory, or orchestration to gain branching, aggregation, and traversal that flat sequences cannot express. Cuts across the other three.

Wrapping all four is the temporal dimension — self-improvement: using signals the system generates itself to get better, at inference time (§6), at training time (§6), or by improving the improver itself (recursive self-improvement, §7).

Key

The 2023→2026 arc: the field's leverage moved outward through the stack. First we tuned prompts; then (for agents) we realized context is the real budget; then that the harness determines capability more than the prompt; and now that the highest-leverage move is systems that engineer themselves. Same model, different stack → enormous capability delta. Reference index for prompting: The Prompt Report (a systematic survey of 58+ techniques and standardized terminology).

2. Prompt Engineering

2.1 Core prompt anatomy

• Zero-shot — instruction only, no exemplars; leans on instruction-tuning.
• Few-shot / in-context learning (ICL) — prepend \(k\) input→output demonstrations; the model infers the task from context with no weight update. Origin: GPT-3, "Language Models are Few-Shot Learners".
• Instructions — imperative task spec; specificity dominates zero-shot quality.
• Role / persona — "You are an expert X"; conditions style and domain. A related empirical booster is EmotionPrompt (emotional stimuli such as "this is very important to my career").
• Delimiters — triple quotes, XML tags, or markdown fences separate instruction from data (also a first-line injection defense; §2.7).
• Output-format control / structured outputs — JSON mode, grammar/constrained decoding, and tool schemas; prefer provider-enforced structured outputs over "please return JSON."
• System vs user prompts — the system prompt is durable, highest-trust policy; the user prompt is the per-turn request. Formalized as trust tiers by the Instruction Hierarchy.
• Prompt templates — parameterized strings with slots; the substrate for programmatic prompting (§2.5).

2.2 Reasoning-elicitation techniques

• Chain-of-Thought (CoT) — few-shot exemplars include intermediate reasoning steps; unlocks multi-step reasoning at scale.
• Zero-shot CoT — append "Let's think step by step"; two-stage reasoning-then-answer extraction, no exemplars.
• Auto-CoT — auto-build CoT exemplars by clustering questions and generating rationales with Zero-shot CoT.
• Self-Consistency — sample \(N\) diverse chains at temperature \(>0\) and marginalize by majority vote: \(\hat{a} = \arg\max_a \sum_{i=1}^{N} \mathbb{1}[a_i = a]\). The single highest-ROI add-on to CoT.
• Least-to-Most — decompose into ordered subproblems, solve sequentially feeding earlier answers forward; strong compositional generalization.
• Decomposed Prompting (DecomP) — a decomposer LLM dispatches sub-tasks to specialized (possibly recursive) sub-prompt handlers.
• Tree-of-Thoughts (ToT) — thoughts as tree nodes; generate + self-evaluate states and search with BFS/DFS + backtracking.
• Graph-of-Thoughts (GoT) — thoughts as an arbitrary graph (DAG); supports aggregating/merging and refinement loops beyond trees (see §5.2).
• ReAct — interleave Reason (thought) + Act (tool) + Observation; grounds reasoning in external tools. The canonical agent loop (see §4.2).
• PAL / Program-of-Thoughts — write reasoning as executable code; offload computation to an interpreter (code = reasoning, execution = answer).
• Self-Ask — model explicitly asks and answers follow-up sub-questions before the final answer; narrows the compositionality gap and integrates search.
• Plan-and-Solve — zero-shot "devise a plan, then carry it out"; reduces missing-step errors vs plain Zero-shot CoT.
• Analogical prompting — model self-generates relevant exemplars/knowledge before solving; no hand-labeled demos.
• Step-Back prompting — first derive a high-level principle (abstraction), then reason from it.
• Chain-of-Verification (CoVe) — draft → plan verification questions → answer them independently → revise; cuts hallucination.
• Self-Refine — one model loops generate → self-feedback → refine, no training (see §6.2).
• Maieutic prompting — recursively generate an abductive explanation tree, resolve via MAX-SAT for logical consistency.
• Complexity-based prompting — select/vote using the most complex (most-step) chains; complexity correlates with accuracy.

2.3 In-context learning — theory, selection, calibration

Why ICL works:

• Induction heads — attention heads implementing prefix-match + copy (\([A][B]\dots[A]\to[B]\)); their emergence coincides with an ICL phase change during training (Anthropic).
• ICL as implicit Bayesian inference — demonstrations "locate" a latent task/concept the model already learned in pretraining.
• ICL ≈ implicit gradient descent — linear-attention transformers can implement a GD step per layer over the in-context examples (meta-optimizer view).
• Rethinking Demonstrations — label correctness matters surprisingly little; the input distribution, label space, and format drive ICL.

Selection & ordering:

• Order sensitivity — example permutation swings accuracy from SOTA to random; use entropy-based ordering selection.
• Retrieval-based selection (KATE) — retrieve semantically nearest examples (kNN in embedding space) per test input.

Calibration:

• Contextual Calibration — LMs are biased toward majority/recent/common tokens; estimate the bias with a content-free input ("N/A") and affine-correct: \(\hat{q} = \mathrm{softmax}(W\,p + b)\), with \(W\) fit so the content-free input maps to uniform.

2.4 ★ Prompting modern reasoning models (o-series, R1, extended thinking)

Reasoning models are RL-trained to produce a long internal chain before answering, which changes the rules:

• Don't over-prompt reasoners. Explicit "think step by step" and heavy few-shot CoT become redundant and can degrade results; prefer clear, direct zero-shot instructions with the goal + constraints, and let the model plan. (OpenAI reasoning best-practices; Anthropic extended-thinking guidance.)
• Let's Verify Step by Step — process reward models (PRMs) supervise each reasoning step; the basis for verifier-guided search and o1-style training.
• Scaling test-time compute optimally — spending inference compute (longer thinking, more samples, verifier search) can beat scaling parameters; a "reasoning-effort" knob.
• DeepSeek-R1 — pure-RL (GRPO) elicits emergent long-CoT ("aha moments") without an SFT bootstrap (R1-Zero); the reference open reasoning model.

Key

The prompting objective shifted from eliciting reasoning (CoT, ToT scaffolds) to budgeting it (reasoning-effort controls, verifier-guided test-time compute). On reasoning models, hand-built decomposition scaffolds often hurt — give the objective, not the method.

2.5 Automatic prompt optimization / programmatic prompting

Stop hand-tuning strings; optimize them against a metric.

Discrete / text-search optimizers:

• APE (Automatic Prompt Engineer) — LLM proposes instruction candidates from demos, scores on held-out data, resamples the best.
• OPRO ("LLMs as Optimizers") — the LLM is the optimizer: a meta-prompt holds the (prompt, score) trajectory and it proposes higher-scoring prompts (famously discovered "Take a deep breath and work step by step").
• ProTeGi / APO — textual "gradients" are natural-language critiques of failures; edit the prompt in the opposite semantic direction with beam search.
• EvoPrompt — evolutionary algorithms (GA/DE) with the LLM as mutation/crossover operator over a prompt population.
• Promptbreeder — self-referential evolution: evolves both task-prompts and the mutation-prompts that mutate them (see §7).
• AutoPrompt — gradient-guided (HotFlip) search for discrete trigger tokens; origin of automated discrete prompt search.
• RLPrompt — an RL policy generates discrete prompts with task-metric reward (often ungrammatical but transferable).

Frameworks / compilers:

• DSPy — programming, not prompting. Declare Signatures (typed I/O, e.g. question -> answer), compose Modules (Predict, ChainOfThought, ReAct), then a compiler/optimizer (BootstrapFewShot, MIPROv2) auto-generates demos + instructions against a metric. Decouples logic from prompt strings.
• TextGrad — backpropagation through text: build a graph of LLM calls and propagate natural-language "textual gradients" backward to optimize any text variable (prompt, code, solution).
• Trace / OptoPrime — frames agent/pipeline optimization as generative optimization over execution traces (a "next AutoDiff").
• ★ GEPA (Genetic-Pareto) — reflective prompt evolution: mutate prompts by natural-language reflection on execution traces + feedback, keeping a Pareto frontier of complementary prompts. Beats GRPO by up to ~20% with up to ~35× fewer rollouts; now a DSPy optimizer.

Key

Three families to keep straight: discrete search (APE, OPRO, EvoPrompt) that samples/scores prompt strings; reflective / textual-gradient (ProTeGi, TextGrad, Trace, GEPA) that critiques traces and edits in the "semantic gradient" direction; and soft/continuous prompt tuning (prefix/P-tuning — weight-space, out of scope here). GEPA is the 2025 headline: reflection can beat RL at a fraction of the rollouts.

2.6 Ensembling & sampling

• Self-Consistency — majority vote over sampled chains (§2.2).
• Universal Self-Consistency (USC) — for free-form outputs where exact-match voting fails, the LLM itself picks the most consistent sample.
• Best-of-\(N\) (rejection sampling) — sample \(N\), pick the best by a verifier/reward model/self-eval; gains bounded by verifier quality. The core test-time-compute lever.
• Sampling knobs — temperature rescales logits \(p_i \propto \exp(z_i / T)\) (\(T\to 0\) greedy; higher \(T\) = more diverse, needed for self-consistency/best-of-\(N\)); top-\(p\) (nucleus) samples from the smallest set with cumulative probability \(\ge p\); top-\(k\) restricts to the \(k\) highest-probability tokens. Reasoning/factual → low \(T\); ensembling/creative → higher \(T\) + top-\(p\).

2.7 Adversarial & safety

Attacks:

• Prompt injection (direct) — malicious input overrides system instructions ("ignore previous instructions"); also enables prompt leaking (extracting the system prompt).
• Indirect prompt injection — payload hidden in retrieved/third-party content (web page, email, tool output) that the model later ingests; the dominant risk for agents and RAG.
• Jailbreaks — DAN / "Do Anything Now" — persona/role-play prompts that bypass safety (large in-the-wild study).
• ★ Many-shot jailbreaking — hundreds of faux harmful Q&A demos in a long context erode refusals; efficacy scales ~power-law with shot count (Anthropic).
• Crescendo — multi-turn escalation: benign opener, gradually reference the model's own prior replies until it complies.
• GCG (adversarial suffixes) — gradient-based greedy-coordinate search for universal, transferable adversarial suffix strings.

Defenses:

• Spotlighting — mark/transform untrusted data (delimiting, datamarking, encoding) so the model can tell it from instructions (Microsoft).
• Instruction Hierarchy — train models to prioritize by trust tier (system > developer > user > tool/data) and ignore lower-privileged conflicting instructions (OpenAI).
• Practical layers: input/output classifiers, tool sandboxing, least-privilege agents, human-in-the-loop for high-risk actions, dual-LLM (quarantined) patterns.

2.8 Patterns & anti-patterns

Patterns: durable rules in the system prompt; XML/delimiters to fence data; explicit output contracts via constrained decoding; decompose hard tasks; verify/critique loops for factual work; and optimize, don't hand-tune (DSPy/GEPA) once you have eval data. Anti-patterns: forcing CoT scaffolds on reasoning models; demo overload (recency/majority bias, wider jailbreak surface); relying on example label correctness to teach a task; unfenced retrieved content; assuming few-shot ordering is neutral; and trusting "please output JSON" over constrained decoding.

3. Context Engineering

3.1 What it is and why it superseded prompt engineering

Context engineering is the discipline of curating and maintaining the optimal set of tokens — instructions, tool definitions, retrieved documents, history, memory, tool results — in the window during inference. Prompt engineering writes one good static prompt; context engineering manages the entire dynamic state fed to an agent across many turns and tool calls.

Why it matters: an agent runs many inference cycles, assembling context fresh each turn, and context is a finite budget. Transformer attention is pairwise over \(n\) tokens, and models are trained on shorter sequences than their max window, so effective use degrades before the nominal limit. The canonical framing — Anthropic, "Effective context engineering for AI agents" — treats attention as a scarce resource to spend on the "smallest set of high-signal tokens." A useful operational taxonomy (LangChain): Write (persist outside the window), Select (pull in what's relevant), Compress (summarize/trim), Isolate (split across sub-agents).

3.2 Long-context mechanics & failure modes

• Lost in the Middle — U-shaped positional bias: models recall information best at the start/end of context, worst in the middle.
• ★ Context Rot — performance degrades as input length grows, even on trivial tasks; long-window claims are overstated and distractors amplify the decay (Chroma).
• Needle-in-a-Haystack (NIAH) — insert a fact at varying depths in filler text; the de-facto long-context retrieval probe.
• ★ NoLiMa — NIAH beyond literal matching: needle and question share no lexical overlap, forcing latent association; exposes a sharp long-context drop that literal NIAH hides.
• The four failure modes (Breunig) — poisoning (a hallucination re-referenced as truth), distraction (bloated history overrides trained knowledge), confusion (irrelevant content, e.g. too many tool defs, degrades output), clash (contradictory accrued facts conflict).

3.3 Retrieval-Augmented Generation (RAG)

Naive RAG = chunk → embed → top-\(k\) vector search → stuff. Advanced RAG adds pre-retrieval (query transformation), retrieval (hybrid + rerank), and post-retrieval (compression, reordering). Agentic RAG makes retrieval a tool an agent invokes in a loop (§3.4).

Foundational:

• RAG — original: a parametric seq2seq generator + a non-parametric DPR retriever over Wikipedia, trained end-to-end (Lewis 2020).

Query transformation:

• Query Rewriting for RAG — a "rewrite-retrieve-read" step reformulates the query (and underlies multi-query/expansion).
• HyDE — generate a hypothetical answer document and embed that (not the query) for zero-shot dense retrieval.

Hybrid search & rerankers:

• Hybrid search — fuse lexical (BM25, exact terms) with dense (embedding) scores via reciprocal-rank fusion.
• ColBERT / ColBERTv2 — late interaction: per-token embeddings + MaxSim retain fine-grained matching at scale.
• Cross-encoder reranker — jointly encode the (query, doc) pair for a precise second-stage score over top-\(k\) candidates.

Embedding models: E5 (contrastive, query:/passage: prefixes), BGE / C-Pack, GTE, Nomic Embed (open-data, 8192-token).

Structure-aware & adaptive:

• ★ Contextual Retrieval — prepend an LLM-generated chunk-specific blurb before embedding/BM25; cuts retrieval failures ~35–49% and pairs with prompt caching (Anthropic).
• RAPTOR — recursively cluster + summarize chunks into a tree; retrieve at multiple abstraction levels for multi-hop/global questions.
• Self-RAG — model emits reflection tokens to decide when to retrieve and to grade passages + its own output.
• CRAG (Corrective RAG) — a lightweight evaluator grades docs (correct/ambiguous/incorrect) and triggers web search + knowledge refinement.
• FLARE — active retrieval: predict the next sentence and, if any token is low-confidence, retrieve mid-generation and regenerate.

3.4 Agentic context management

Short-term memory = the working window (this session's messages/tool results). Long-term memory = an external store (vector DB / graph / files) selectively read back in. Strategy: keep the window lean, offload the rest.

• MemGPT / Letta — "LLM as an OS": tiered memory (main context vs external) self-paged via function calls; the agent moves data in and out of the window.
• Mem0 — extraction + consolidation pipeline for a scalable long-term memory layer (graph variant Mem0ᵍ for relational recall; see §5.5).
• Zep / Graphiti — a temporal knowledge graph for agent memory with bi-temporal edges (§5.5).
• Reflexion — "memory of experiences": verbal self-reflection on failures stored in episodic memory to improve the next attempt (§6.2).
• Agentic RAG: A Survey — taxonomy of agent-driven retrieval (routing, planning, reflection, multi-agent).
• Sub-agent context isolation — an orchestrator spawns sub-agents with clean windows; only condensed results return, giving parallelism + context hygiene.
• Compaction, note-taking, just-in-time retrieval — summarize old turns into a digest near the budget limit; write durable notes to a file/memory tool outside the window; store lightweight identifiers (paths, IDs) and load full content only when needed (Anthropic).

3.5 Prompt / context compression

Hard (discrete) = drop/edit actual tokens (model-agnostic, portable). Soft (continuous) = compress into embeddings/soft tokens (needs model access). KV-cache-aware / prompt caching = reuse a stable prefix's KV cache instead of reprocessing it.

• Selective Context — prune low-information tokens by a small LM's self-information.
• LLMLingua — coarse-to-fine, budget-controlled, perplexity-based token dropping (up to ~20×).
• LongLLMLingua — extends it to long-context RAG with question-aware compression + document reordering (fights Lost-in-the-Middle).
• LLMLingua-2 — task-agnostic compression as token classification, distilled from GPT-4; faster and more faithful.
• Prompt caching — cache stable prefixes (system prompt, tools, docs) for large latency/cost cuts; pairs with contextual retrieval.

3.6 Structured context assembly

Design the system prompt at the "right altitude" (specific enough to steer, general enough not to overfit); use XML/markdown structure to demarcate instructions vs data vs tool results; format tool outputs to be token-efficient (signal over raw dumps); exploit the U-shaped bias by placing the most critical content at the start or end, not buried mid-context; use a few diverse canonical examples rather than exhaustive rules; and quarantine/validate tool outputs and retrieved text before they become trusted history (Anthropic).

3.7 Evaluation of context / RAG

• RAGAS — reference-free RAG metrics: faithfulness (claims supported by context), answer relevancy, context precision (signal-to-noise of retrieved chunks), context recall (was all needed evidence fetched).
• LongBench — bilingual multitask long-context benchmark (QA, summarization, code, few-shot).
• RULER — synthetic multi-needle/variable-tracking/aggregation tasks measuring effective vs claimed context length.
• HELMET — application-centric long-context suite (RAG, ICL, re-ranking, long-QA) with controllable lengths.
• ★ NoLiMa — latent-association long-context eval (§3.2); shows literal NIAH overstates true long-context reasoning.

Key

"Bigger window" ≠ "problem solved" — Context Rot and NoLiMa show degradation is real at scale. The 2025 shift: for long-horizon agents, treat context as a managed budget — retrieve just-in-time, compact aggressively, isolate sub-agents, and keep only high-signal tokens resident. Memory tooling (Mem0, Zep/Graphiti, cognee) is moving from flat vector stores to temporal/knowledge graphs (§5.5).

4. Harness Engineering

4.1 What a harness is and why it dominates

The weights are fixed; the harness — loop + tools + context assembly + control flow + verification + orchestration — is what turns a next-token predictor into an agent. The canonical design reference is Anthropic, "Building effective agents", which separates workflows (predefined code paths) from agents (the LLM directs its own process) and catalogs the reusable patterns:

• Prompt chaining — decompose into a fixed sequence of steps, each gating the next.
• Routing — classify input, dispatch to a specialized path.
• Parallelization — sectioning (split subtasks) or voting (sample many, aggregate).
• Orchestrator–workers — a lead LLM dynamically decomposes and delegates to workers.
• Evaluator–optimizer — one LLM generates, another critiques in a refinement loop.
• Autonomous agent — open-ended tool-use loop until a stop condition.

Guidance: start with the simplest thing that works; add agentic complexity only when it pays.

4.2 The core agent loop

• ReAct — interleave reasoning traces with actions and observations; the foundational perceive–think–act loop.
• Function/tool calling — the loop primitive: the model emits a structured tool call → the harness executes → feeds the observation back until a stop condition (final answer / no tool call / max steps / budget).

4.3 Tool use & interfaces

• JSON-schema tools — tools declared as typed schemas the model binds to.
• Model Context Protocol (MCP) — an open client–server standard exposing tools/resources/prompts to any model, decoupling integrations from the harness.
• ★ Code execution with MCP — present servers as code APIs the agent calls via generated code (token-efficient vs many direct tool calls).
• ★ Writing effective tools for agents — consolidate tools, return high-signal/token-efficient output, namespace clearly, evaluate with agents.
• CodeAct — use executable Python as the unified action space; composes tools, uses control flow, self-debugs from execution output.
• Computer use / GUI agents — act on screenshots via mouse/keyboard primitives.

4.4 Planning & control flow

• Plan-and-Solve — plan first, then execute subtasks (vs reactive ReAct).
• Reflexion — reflect on failure feedback, store it in episodic memory, retry.
• Tree-of-Thoughts — a search harness over thoughts with lookahead/backtracking.
• LATS — MCTS over ReAct actions, unifying reasoning + acting + planning with a value function + external feedback.
• Self-Consistency — sample many paths, majority-vote (a best-of-\(N\) verification harness).

4.5 Multi-agent orchestration

• Anthropic multi-agent research system — orchestrator–worker for parallel research; documents when multi-agent helps (breadth, parallel search) vs hurts (~15× token cost, coordination overhead, tightly-coupled tasks).
• CAMEL — role-playing "inception prompting" between paired agents for autonomous cooperation.
• AutoGen — conversable agents; multi-agent conversation as the programming model.
• MetaGPT — encodes SOP/role workflows (PM, architect, engineer) into an assembly-line agent company.
• ChatDev — a virtual software company chaining role-pair chats across design → code → test.
• Multiagent Debate — multiple LLM instances propose and critique across rounds to converge.
• CrewAI / handoffs — role/goal/task "crews" (CrewAI); agent-to-agent control transfer as a tool call (OpenAI Agents SDK).

4.6 Verification & reliability harness

• Evaluator–optimizer loops and LLM-as-judge / self-verification — score candidate outputs; pair with best-of-\(N\).
• Execution/unit-test feedback — run code/tests and feed failures back (core to SWE-agent, CodeAct, Reflexion).
• Guardrails AI and NeMo Guardrails — validators/re-asking on failure; programmable input/output/dialog rails.
• Retry/error-recovery & sandboxing — bounded retries, tool-error handling, isolated (containerized) execution.

4.7 Agent frameworks / SDKs

• LangGraph — agents as explicit stateful graphs (nodes/edges) with checkpointing and human-in-the-loop (see §5.6).
• LlamaIndex — data/RAG-centric agents + event-driven workflows.
• DSPy — declarative programs with compilers that optimize prompts/weights (§2.5).
• AutoGen / CrewAI — conversation-driven and role-based multi-agent runtimes.
• OpenAI Agents SDK (successor to the experimental Swarm) — agents, tools, handoffs, guardrails, sessions, tracing.
• Claude Agent SDK — the Claude Code harness as a library: agent loop, tools, MCP, subagents, permissions, context management.
• Pydantic AI (type-safe, validated outputs) and smolagents (agents that "think in code").

4.8 Coding-agent harnesses & benchmarks

• SWE-agent — introduces the Agent-Computer Interface (ACI): LM-optimized commands (search, view, lint-aware edit). Shows interface design drives performance more than the model.
• OpenHands (ex-OpenDevin) — an open platform for generalist software agents (sandboxed runtime, browser+bash+editor).
• Agentless — no agent loop: a fixed localize → repair → validate pipeline, competitive on SWE-bench (harness-minimalism baseline).
• Aider (repo-map + git-commit-per-edit) and Devin (long-horizon autonomous SWE agent).
• Benchmarks: SWE-bench (real GitHub issue→PR, hidden tests), SWE-bench Verified (500 human-validated tasks), Terminal-Bench (real command-line tasks).

4.9 Observability & agent evals

• LangSmith — tracing, observability, and eval tooling for agent runs.
• τ-bench (tool-agent-user with a simulated user + policy rules; pass^k reliability), GAIA (real assistant questions needing tools), AgentBench (8 environments), WebArena (self-hosted web agents).

4.10 Agent Skills — the capability layer

An Agent Skill packages reusable procedural knowledge as a folder: a SKILL.md file with YAML frontmatter (name + description) and a Markdown body of instructions, plus optional bundled reference files and executable scripts. It is the harness's modular capability layer — where "how to do this task well" lives, versionable and inspectable, with no fine-tuning.

Progressive disclosure is the core mechanism: context loads in three tiers so a large library stays cheap.

1. Metadata — only name + description (~100 tokens/skill) are always resident; this is what the model routes on.
2. Instructions — the full SKILL.md body (target <5k tokens) loads when the description matches the task.
3. Resources & code — bundled files and scripts load or execute on demand; a script's output enters context, not its source.

Per the docs, the description must state both what it does and when to use it — it is the routing signal (§4.11). Skills run across the Claude apps, Claude Code, the Agent SDK, and the API, and ship as an open format (anthropics/skills). The quantitative payoff of progressive disclosure is derived in §9.19.

4.11 Skills vs tools/MCP; authoring; plugins

Skills vs tools/MCP. MCP and function calling provide actions (what the agent can do or connect to); a skill provides procedure (how to do a multi-step task well), typically orchestrating those tools plus bundled scripts. They are complementary, not competing — the skill teaches the workflow, MCP supplies the connections.

Authoring (best practices): write a crisp third-person description with concrete trigger terms (routing quality depends on it); keep the body short (only what the model doesn't already know); push detail into reference files one level deep; bundle scripts for determinism ("sorting a list via token generation is far more expensive than running a sort"); pick the right degrees of freedom (prose for open tasks → exact scripts for brittle ones); and build evals first, testing across model sizes.

Plugins & marketplaces. A plugin bundles skills + MCP servers + slash commands + subagents + hooks, installed from a marketplace — the distribution unit for capability, and how a team ships a coherent set (skills + connections + commands) as one install.

4.12 Skill libraries & self-authored skills (bridge to self-improvement)

A skill library is external, growing procedural memory, which makes accumulating skills a form of self-improvement without weight updates (§6–§7). The canonical research anchor is ★ Voyager: an LLM agent that writes, stores, retrieves, and composes an ever-growing library of executable-code skills, achieving lifelong learning with no gradient updates and no catastrophic forgetting. Related lines let models create their own tools/skills — CREATOR and LLMs as Tool Makers build reusable tools on the fly, and ADAS has a meta agent program new agents from a growing archive (§7.2). An agent that authors and reuses its own skills sits on the recursion ladder (§7.3, rung 4): it improves capability by editing its scaffold's skill set rather than its weights.

Key

The harness, not the checkpoint, is often the biggest lever: SWE-agent showed a better Agent-Computer Interface beats a bigger model, and Agentless showed a minimal fixed pipeline can rival full agents. 2025–2026 harness trends (★): Agent Skills (progressively-disclosed skill folders), code-execution-over-MCP for token efficiency, context engineering for long-horizon runs, and RL-trained agent harnesses co-designed with the loop.

5. Graph Engineering

5.1 Framing: five loci of graph structure

"Graph engineering" means deliberately imposing graph structure (nodes + typed edges) on part of an LLM/agent system to gain non-linear composition, aggregation, and traversal that flat sequences cannot express. Five places it shows up:

• (a) Reasoning topologies — the shape of inference is a graph (thoughts = nodes), enabling branching, backtracking, merging.
• (b) Retrieval over knowledge graphs (GraphRAG) — the corpus is an entity–relation graph, so retrieval is traversal/community-summarization, not flat top-\(k\).
• (c) Agent/workflow graphs — orchestration is a (possibly cyclic) computation graph of nodes passing state along edges.
• (d) Graph-structured memory — the agent's memory is a (often temporal) knowledge graph of facts and their validity.
• (e) GNN + LLM fusion — representations couple graph neural networks with LLMs over text-attributed graphs.

The unifying move: replace sequences with graphs so that structure carries semantics.

5.2 Reasoning topologies as graphs

Chain = one linear path. Tree = branching + search/backtrack, no merging. Graph = arbitrary edges: aggregate multiple thoughts into one, cycles/refinement, reuse.

• Chain-of-Thought → Tree-of-Thoughts → Graph-of-Thoughts — the chain→tree→graph progression.
• Everything-of-Thoughts (XoT) — MCTS + pretrained policy/value nets inject external thought structure ("defying the Penrose triangle" of performance/efficiency/flexibility).
• Skeleton-of-Thought — generate an answer skeleton, then expand points in parallel (latency-oriented).
• Algorithm-of-Thoughts — embed algorithmic (exploratory) examples in-context so one query traverses an idea space.
• Buffer-of-Thoughts — a meta-buffer of reusable high-level "thought-templates" retrieved per problem.
• Forest-of-Thought — multiple ToT trees + consensus/self-correction to scale test-time compute.
• Demystifying Chains, Trees, and Graphs of Thoughts — a formal taxonomy of thought topologies.

5.3 Graph RAG / knowledge-graph retrieval

• Microsoft GraphRAG — LLM builds an entity KG → Leiden community detection → hierarchical community summaries → map-reduce answering of "global" questions a flat top-\(k\) cannot.
• LightRAG — dual-level (low/high) retrieval on an incrementally-updatable graph index + vectors; cheaper than GraphRAG.
• HippoRAG / ★ HippoRAG 2 — hippocampus-inspired: an OpenIE KG + Personalized PageRank gives single-step multi-hop retrieval; v2 pushes toward continual non-parametric memory.
• PathRAG — retrieve and prune key relational paths between nodes to cut redundant graph context.
• GraphReader — an agent builds a graph from long documents, then navigates nodes/notes to answer.
• KAG — knowledge-augmented generation over schema-constrained (SPG) knowledge graphs with logical-form reasoning for professional domains.
• G-Retriever — RAG for text-attributed graphs via a Prize-Collecting Steiner Tree subgraph + a GNN soft prompt to the LLM.
• ToG / Think-on-Graph — an LLM agent beam-searches over KG paths for deep, traceable reasoning.
• GNN-RAG — a GNN reasons over a dense KG subgraph to fetch candidate paths, verbalized to the LLM (KGQA).
• StructRAG — at inference, pick the best structure (table/graph/tree) to structurize retrieved knowledge.
• RAPTOR — recursive clustering + summarization into a tree (§3.3); the tree-structured cousin of GraphRAG.
• nano-graphrag — a minimal, hackable GraphRAG reimplementation.

5.4 Knowledge-graph construction with LLMs

Not one paper but a pipeline: LLM-driven entity + relation (triple) extraction → coreference/entity resolution → optional ontology/schema typing → graph assembly + community/embedding indexing. Entity resolution/dedup is the load-bearing step for graph quality. The canonical framing is Unifying LLMs and Knowledge Graphs: A Roadmap (KG-enhanced LLMs, LLM-augmented KGs, synergized); concrete pipelines are GraphRAG's extraction→community step, LightRAG's incremental dedup/merge, and KAG's schema-constrained construction.

5.5 Graph-structured agent memory

Store memory as a temporal / bi-temporal knowledge graph — edges carry validity intervals (event time vs ingestion time), so facts can be superseded/invalidated without deletion and point-in-time queries become possible.

• ★ Zep / Graphiti — a temporal-KG memory architecture (Zep) powered by a real-time bi-temporal graph engine (Graphiti); outperforms full-context and MemGPT on long-memory benchmarks.
• ★ Mem0 / Mem0ᵍ — extract/consolidate salient facts into a scalable long-term layer; the graph variant stores entities + relations.
• ★ A-MEM — "Zettelkasten" agentic memory: notes auto-link and evolve into a knowledge network.
• cognee — open-source ECL (Extract-Cognify-Load) turning data into a persistent agent-memory knowledge graph.

5.6 Agent & workflow graphs

• LangGraph — orchestration as a stateful graph: nodes (functions/agents) + edges (including conditional/cyclic), a shared typed state, and Pregel-style super-step message passing; supports loops, checkpoints, and human-in-the-loop.
• ★ GPTSwarm — language agents as optimizable computational graphs; nodes are operations, edges are flow, and you optimize both node prompts and the edge topology (the graph is the thing you learn).
• ★ AFlow — workflows as code-represented graphs; MCTS searches the space of workflow structures automatically.
• Computation graphs / DAGs + Pregel dataflow — agents as DAG nodes passing messages; Pregel's vertex-centric BSP super-steps are the basis for LangGraph-style engines.

5.7 GNN + LLM fusion / can LLMs reason on graphs?

• NLGraph — a benchmark of graph/algorithmic problems in natural language (+ "build-a-graph" prompting).
• Talk like a Graph (GraphQA) — how you encode a graph as text for an LLM hugely affects performance.
• GraphToken — a GNN encodes structure into soft "graph tokens" prepended to the LLM (parameter-efficient).
• GraphFormers — GNNs nested inside transformer layers for text-attributed-graph representation.
• ★ Graph Foundation Models (survey) — pretrained, transferable graph models as an emerging thrust.

Key

Match the graph to the failure mode: use thought graphs (ToT/GoT) when a task needs branching + aggregation; GraphRAG when questions are global/multi-hop over a corpus that flat top-\(k\) misses; temporal-KG memory (Zep/Graphiti, Mem0ᵍ) when an agent must remember evolving facts over time; and workflow graphs (LangGraph) or optimizable agent graphs (GPTSwarm, AFlow) when orchestration itself should be explicit or learned. 2025–2026 (★): agentic GraphRAG (the agent traverses the graph), graph memory going mainstream, and graph-of-agents where topology is searched.

6. Self-Improvement & Self-Learning

6.1 Taxonomy

• Self-improvement — a model/agent improves its own outputs or weights using signals it generates itself (self-feedback, self-generated data, self-reward), not fresh human labels.
• Self-learning / self-training — training on model-generated (usually filtered) data; the model is both producer and consumer.
• Inference-time (test-time) self-improvement — gains at generation via iterative critique/refinement/search; weights unchanged (§6.2).
• Training-time self-improvement — weights updated on self-generated data (§6.3–§6.4).
• Recursive self-improvement (RSI) — improving the improver itself (§7).

Organizing reference: ★ A Survey of Self-Evolving Agents and ★ A Comprehensive Survey of Self-Evolving AI Agents (a unified System-Inputs / Agent-System / Environment / Optimisers framework bridging foundation models and lifelong agentic systems).

6.2 Inference-time self-correction

• Self-Refine — generate → self-critique → revise, looped, no training.
• Reflexion — "verbal RL": reflect on failed episodes in language, store reflections in episodic memory to guide retries.
• CRITIC — verify and correct outputs by interacting with external tools (search, code interpreter) for grounded feedback.
• Self-Debugging — the model debugs its own code by explaining and inspecting execution results ("rubber-duck").
• Chain-of-Verification and Self-Verification — plan/answer verification questions, or back-verify candidate answers as conditions on the original problem.
• LATS — MCTS over agent trajectories with self-reflection + value feedback (§4.4).
• ★ Caveat — LLMs Cannot Self-Correct Reasoning Yet — intrinsic self-correction (no oracle/external feedback) often fails to improve and can degrade reasoning; prior gains frequently leaned on oracle labels or ground-truth stopping. Self-improvement works where verification is cheap and reliable (code execution, math checkers, games), not open-endedly.

6.3 Training-time self-improvement (learn from self-generated data)

• STaR (Self-Taught Reasoner) — generate rationales, keep those reaching the correct answer (rationalize failures given the answer), fine-tune, repeat.
• ReST — Grow (sample from policy) + Improve (filter by reward, offline RL/FT), batched.
• ReST-EM ("Beyond Human Data") — ReST as expectation-maximization: sample → filter-by-binary-reward → SFT; beats human-data FT on reasoning/code.
• V-STaR — train a DPO verifier on both correct and incorrect self-generated solutions to rerank at inference.
• Quiet-STaR — learn to generate token-level rationales on arbitrary text (think before speaking).
• RISE (Recursive Introspection) — fine-tune the model to improve its own prior answer over multi-turn attempts (self-correction as an MDP).
• RFT / rejection-sampling FT — augment SFT with distinct correct sampled reasoning paths.

6.4 Self-rewarding & self-play alignment

• Self-Rewarding Language Models — the model is its own LLM-as-judge, generates preference pairs, trains via DPO iteratively; the reward model improves alongside the policy.
• Meta-Rewarding — add a meta-judge: the model judges its own judgments to improve its judging.
• RLAIF and Constitutional AI — replace human preference labels with AI feedback; CAI critiques/revises against a written "constitution" then RLAIF (Anthropic).
• SPIN (Self-Play Fine-Tuning) — self-play: the model learns to distinguish its own generations from human data (a DPO-like game vs its past self), no extra preference data.
• SPAG — RL on self-play of an adversarial "Taboo"-style language game broadly improves reasoning.
• rStar / rStar-Math — generator–discriminator mutual reasoning (rStar); small models reach frontier math via MCTS "deep thinking" + a process preference reward, self-evolving over rounds (rStar-Math).
• ★ Absolute Zero — the model proposes AND solves its own tasks, verified by a code executor; zero external data.
• ★ R-Zero — from-zero co-evolution: a Challenger proposes tasks at the edge of a Solver's ability; two copies of one base model bootstrap without human data.
• ★ TTRL (Test-Time RL) — RL at inference on unlabeled test data using majority-vote pseudo-rewards (self-consistency as the reward).
• SASR — step-wise adaptive integration of SFT and RL (dynamic SFT↔︎RL weighting).

Key

The load-bearing ingredient is a verifier. Where correctness is cheaply checkable (unit tests, math answers, game outcomes), self-generated data + filtering (STaR/ReST-EM) and self-play (Absolute Zero, R-Zero) compound impressively. Where it isn't, self-reward loops risk reward hacking and self-training risks model collapse (Curse of Recursion — recursively training on generated data degrades the distribution's tails over generations). Filtered self-training amplifies what a model can already verify; it rarely creates net-new capability without external signal or exploration.

7. Recursive Self-Improvement (RSI)

7.1 The idea and its theory

RSI is improving the improver: a system that edits its own code, prompts, learning algorithm, or agent scaffold so that improvements compound. Conceptual lineage: I.J. Good's 1965 "intelligence explosion" and the notion of seed AI — a minimal system capable enough to iteratively rewrite itself toward far greater capability. The rigorous theoretical object is the Gödel Machine (Schmidhuber): a self-referential program that rewrites any part of its own code once it can prove the rewrite is beneficial — provably optimal self-improvement, but the proof requirement makes it impractical.

7.2 Practical self-modifying & auto-design systems

• STOP (Self-Taught Optimizer) — a fixed LLM runs a seed "improver" program that recursively improves scaffolding code, including the improver itself; recursively self-improving code generation.
• Promptbreeder — self-referential evolution of task-prompts and the mutation-prompts that evolve them (§2.5).
• ADAS / Meta Agent Search — a meta agent programs new agents in code, searching an ever-growing archive of discovered agentic designs.
• Gödel Agent — a self-referential agent that reads and rewrites its own runtime logic/code (monkey-patches itself) to recursively self-improve.
• ★ Darwin Gödel Machine — the empirical, open-ended relaxation of the Gödel Machine (Sakana, 2025): agents edit their own code, are kept in a Darwinian archive, and are selected by benchmark performance (empirical validation replaces proof). Reported SWE-bench 20.0→50.0%, Polyglot 14.2→30.7%.
• ★ AlphaEvolve — a Gemini-powered evolutionary coding agent that evolves algorithms/programs scored by automated evaluators; found new results including matrix-multiplication improvements (DeepMind, 2025).
• EvoAgent — evolutionary algorithms auto-extend a single agent into a multi-agent team via mutation/crossover.
• ★ SEAL (Self-Adapting LLMs) — the model generates its own finetuning data + update directives ("self-edits") and applies persistent weight updates via an RL loop (MIT, 2025).
• The AI Scientist — an end-to-end automated research agent: ideation → code → experiments → paper writing → automated review.

7.3 The recursion ladder

Five rungs of increasing self-reference, each a real system today:

1. Improve outputs — Self-Refine/Reflexion revise this answer (§6.2).
2. Improve weights from self-data — STaR/ReST-EM/Self-Rewarding update the model (§6.3–§6.4).
3. Improve the prompt/program — DSPy/GEPA/STOP/Promptbreeder optimize the scaffold text.
4. Improve the agent design — ADAS/AFlow/GPTSwarm search over agent code/topology.
5. Improve the self-improver — Gödel Agent / Darwin Gödel Machine / SEAL modify the very mechanism that modifies them.

7.4 Meta-learning & test-time adaptation

• MAML — learn an initialization such that a few gradient steps adapt to a new task ("learning to learn").
• ICL as meta-learning — transformers implicitly implement a learning algorithm in the forward pass (§2.3).
• Test-Time Training (TTT) — adapt per test instance via a self-supervised auxiliary loss before predicting; handles distribution shift. Test-time adaptation (e.g. entropy minimization) is the label-free deployment cousin.

7.5 Limits & safety

• Verification gap — RSI compounds only where improvements are cheaply and reliably verifiable; open-ended domains lack the ground-truth signal that keeps the loop honest.
• Reward hacking / self-reward drift — self-rewarding and LLM-as-judge loops can game their own signal; judge quality caps policy quality (motivating Meta-Rewarding).
• Model collapse — recursive training on self-generated data degrades distribution tails over generations.
• Capability ceilings — self-improvement typically saturates at a base-model-dependent ceiling absent external signal or genuine exploration.
• RSI safety — self-modifying agents raise alignment/control concerns (loss of oversight, spec-gaming the improvement metric); DGM and SEAL include sandboxing + human-oversight discussion.

Key

As of 2026, "recursive self-improvement" in practice means empirical, benchmark-gated self-modification of code and scaffolds (Darwin Gödel Machine, ADAS, AlphaEvolve) and RL-learned weight self-edits (SEAL) — not the provably-optimal Gödel Machine. Every working system is bounded by a verifier and a sandbox. The open question is whether the loop keeps paying off past the base model's ceiling, or plateaus.

8. Putting It Together: The 2026 Self-Improving Agent Stack

A modern capable agent composes all five layers:

• Prompt layer — direct, minimally-scaffolded instructions for reasoning models; structured outputs; prompts compiled by DSPy/GEPA against evals rather than hand-written.
• Context layer — retrieval (hybrid + rerank, contextual retrieval), a lean working window, compaction + note-taking for long horizons, and temporal-KG long-term memory; context treated as a managed budget.
• Harness layer — a ReAct/tool-calling loop over MCP tools (or code-execution actions), the simplest workflow pattern that works, evaluator-optimizer and execution-feedback verification, and sub-agents for isolation/parallelism.
• Graph layer — thought graphs where branching/aggregation help; GraphRAG for global/multi-hop corpora; a temporal knowledge graph for memory; an explicit (LangGraph) or learned (AFlow/GPTSwarm) orchestration graph.
• Self-improvement layer — inference-time self-refine/verify loops behind a real verifier; offline STaR/ReST-EM or RLVR to fold successful trajectories back into weights; and, at the frontier, benchmark-gated self-modification of the scaffold (ADAS/DGM) or RL-learned self-edits (SEAL).

9. Mathematical Deep Dives

This section collects the mathematics behind the techniques above — the derivations worth being able to reproduce, not just cite. Notation: \(\pi_\theta\) is a policy / language model with parameters \(\theta\); \(q\) a query/prompt; \(\sigma(z)=1/(1+e^{-z})\) the logistic function; \(\mathrm{KL}(\cdot\|\cdot)\) the Kullback–Leibler divergence; \(\mathbb{1}[\cdot]\) the indicator; \(\mathbb{E}\) expectation.

9.1 In-context learning as implicit gradient descent

Why do demonstrations in the prompt behave like training? Consider a single linear self-attention layer processing demonstrations \((x_i, y_i)_{i=1}^N\) and a query token \(x_q\). Writing the value/key/query projections so that tokens carry \((x_i, y_i)\), the attention read-out added to the query prediction has the form \(\Delta\hat{y}_q = \big(\sum_i (W_V e_i)(W_K e_i)^\top\big) W_Q e_q\). With the natural choice of projections this equals one step of gradient descent on the in-context least-squares loss \(L(W)=\tfrac12\sum_i \lVert W x_i - y_i\rVert^2\):

\[W_1 = W_0 - \eta \sum_{i=1}^{N} (W_0 x_i - y_i)\,x_i^\top, \qquad \hat{y}_q = W_1 x_q .\]

So the forward pass is a learning algorithm executed on the context, and depth ↔︎ number of GD steps (von Oswald et al.). This "meta-optimizer" view explains why more and cleaner demonstrations help monotonically and why ICL sharpens with scale — the model has learned to implement optimization in-weights.

9.2 In-context learning as Bayesian inference

A complementary view: pretraining learns a mixture over latent tasks/concepts \(\theta\). At inference the prompt \(S=(x_1,y_1,\dots,x_N,y_N,x_q)\) induces a posterior over the task and the prediction marginalizes over it:

\[p(y \mid x_q, S) = \int p(y \mid x_q, \theta)\, p(\theta \mid S)\, d\theta .\]

As \(N\) grows, \(p(\theta\mid S)\) concentrates on the concept \(\theta^\star\) consistent with the demonstrations, so ICL locates a task the model already knows rather than learning a new one (Xie et al.). This is why the demonstration format and input distribution carry most of the signal while individual label correctness matters surprisingly little (Min et al.): the demos act as task selectors for the posterior, not as supervised training pairs.

9.3 Self-consistency: marginalization and an error bound

A chain-of-thought samples a latent reasoning path \(r\) and then an answer \(a\). The quantity we actually want is the marginal over paths:

\[p(a \mid q) = \sum_{r} p(a, r \mid q) = \sum_{r} p(a \mid r, q)\, p(r \mid q).\]

Self-consistency estimates \(\arg\max_a p(a\mid q)\) by sampling \(N\) chains and majority-voting, \(\hat{a} = \arg\max_a \tfrac1N\sum_i \mathbb{1}[a_i = a]\). Why does voting help? Treat a (binary) decision where each sample is independently correct with probability \(p\). The majority is wrong only if at most half the \(N\) votes are correct; by Hoeffding's inequality,

\[\Pr[\text{majority wrong}] \le \exp\!\big(-2N\,(p - \tfrac12)^2\big).\]

For any \(p>\tfrac12\) the error decays exponentially in \(N\) — the Condorcet jury theorem. The load-bearing assumption is independence: correlated failure modes (the model is confidently wrong the same way every time) put a floor under the error that more samples cannot break.

9.4 Decoding distributions: temperature, top-\(k\), top-\(p\)

Given logits \(z\in\mathbb{R}^{|V|}\), temperature-\(T\) sampling uses

\[p_i(T) = \frac{\exp(z_i/T)}{\sum_j \exp(z_j/T)} .\]

As \(T\to 0^+\) this tends to the argmax (greedy; entropy \(\to 0\)); as \(T\to\infty\) it tends to uniform (entropy \(\to \log|V|\)), and the Shannon entropy \(H(p(T))\) is monotonically increasing in \(T\). Truncation then trims the tail: top-\(k\) keeps the \(k\) largest logits; top-\(p\) (nucleus) keeps the smallest set \(V_p\) with \(\sum_{i\in V_p} p_i \ge p\) and renormalizes. Consequence for the methods above: self-consistency and best-of-\(N\) need \(T>0\) to generate diverse samples, whereas single-shot reasoning wants low \(T\) to avoid derailing — the same knob trades exploration against reliability.

9.5 Test-time compute: best-of-\(N\), pass@\(k\), and the verification gap

Sample \(N\) candidates and return the best under a verifier. If a single sample is correct with probability \(p\) and the verifier is perfect,

\[\Pr[\text{success}] = 1 - (1-p)^N \xrightarrow{N\to\infty} 1,\]

i.e. gains geometric in \(N\). With an imperfect verifier the ceiling is bounded by verifier accuracy — the verification gap that limits all self-improvement (§9.15, §9.17). The standard unbiased coverage estimator is pass@\(k\): with \(c\) correct of \(n\) samples,

\[\text{pass@}k = \mathbb{E}\!\left[\,1 - \binom{n-c}{k}\Big/\binom{n}{k}\right].\]

Contrast reliability, pass\(^k = p^k\) (all \(k\) independent attempts must succeed), which decreases in \(k\): coverage and reliability pull in opposite directions, which is why agentic benchmarks report pass\(^k\) (§4.9). Compute-optimal test-time scaling allocates the sampling/search budget to maximize accuracy per FLOP and can beat parameter scaling in some regimes.

9.6 The quadratic-attention budget and KV-cache accounting

Self-attention over \(n\) tokens forms scores \(S = QK^\top \in \mathbb{R}^{n\times n}\): compute is \(O(n^2 d)\) and memory \(O(n^2)\) for the score matrix. This is the formal content of "context is a finite budget" — doubling the context quadruples attention cost. During autoregressive decoding the keys and values are cached; per generated token the cache costs

\[\text{bytes/token} = 2 \cdot L \cdot H \cdot d_h \cdot \text{bytes}_{\text{dtype}},\]

(\(L\) layers, \(H\) KV heads, head dimension \(d_h\); the factor \(2\) is for \(K\) and \(V\)). Total KV memory grows linearly in context length and dominates long-context serving — the reason GQA/MLA and KV compression (§3.5) exist. Because models are trained on sequences shorter than their maximum window and attention mass disperses over many tokens, effective use degrades before the nominal limit — the quantitative face of Context Rot (§3.2).

9.7 Retrieval scoring: dense, BM25, ColBERT, and rank fusion

A dense bi-encoder scores by inner product \(s(q,d) = E(q)^\top E(d)\) (cosine after normalization); retrieval is maximum-inner-product search. BM25, the sparse lexical baseline, scores

\[\text{BM25}(q,d) = \sum_{t\in q} \text{IDF}(t)\cdot \frac{f(t,d)\,(k_1+1)}{f(t,d) + k_1\big(1 - b + b\,\tfrac{|d|}{\text{avgdl}}\big)}, \qquad \text{IDF}(t) = \ln\frac{N - n_t + 0.5}{n_t + 0.5} + 1,\]

with term frequency \(f(t,d)\), document length \(|d|\), corpus size \(N\), document frequency \(n_t\), and tunables \(k_1\in[1.2,2.0]\), \(b\approx0.75\). ColBERT keeps per-token embeddings and scores by late-interaction MaxSim,

\[s(q,d) = \sum_{i\in q} \max_{j\in d} E_{q_i}^\top E_{d_j},\]

retaining fine-grained matching a single pooled vector loses. Hybrid pipelines fuse lexical and dense rankers by Reciprocal Rank Fusion,

\[\text{RRF}(d) = \sum_{r\in R} \frac{1}{k + \text{rank}_r(d)}, \qquad k\approx 60,\]

and a cross-encoder reranker then scores the joint \((q,d)\) pair directly on the top-\(k\) candidates — higher precision at higher cost, the standard two-stage retrieve-then-rerank design (§3.3).

9.8 Prompt compression as an information-budget objective

Hard (extractive) compression selects a subsequence \(\tilde{x}\subseteq x\) that retains the most information under a token budget \(B\). LLMLingua scores each token by its self-information under a small language model,

\[I(x_i) = -\log p(x_i \mid x_{<i}),\]

and drops the most predictable (low-information) tokens first, i.e.

\[\tilde{x} = \arg\max_{|\tilde{x}| \le B} \sum_{x_i \in \tilde{x}} I(x_i),\]

which approximately minimizes the KL divergence between the target model's output distribution on \(x\) versus \(\tilde{x}\). LLMLingua-2 replaces the perplexity heuristic with a supervised keep/drop token classifier distilled from GPT-4, improving faithfulness and speed. Soft compression instead maps \(x\) to \(m \ll n\) learned embeddings — a better ratio at the cost of portability and model access.

9.9 Search harnesses: MCTS / UCT for ToT and LATS

Tree-of-Thoughts and LATS wrap the model in tree search: each node is a partial solution/state \(s\), the LM proposes actions (thoughts, tool calls) and evaluates states. Selection uses the UCT bandit rule to trade exploitation against exploration,

\[a^\star = \arg\max_a \left[\, Q(s,a) + c\sqrt{\frac{\ln N(s)}{N(s,a)}} \,\right],\]

where \(Q(s,a)\) is the mean value of taking \(a\) at \(s\), \(N(\cdot)\) are visit counts, and the square-root bonus inflates rarely-tried actions. LATS obtains \(Q\) from an LM value estimate plus environment / self-reflection feedback and backpropagates values up the tree; the four MCTS phases (select, expand, evaluate, backpropagate) repeat under a compute budget. Self-consistency (§9.3) and best-of-\(N\) (§9.5) are the degenerate breadth-1, no-backpropagation special cases of this same harness.

9.10 Personalized PageRank for graph retrieval (HippoRAG)

HippoRAG builds a knowledge graph, places probability mass on the query's matched entities as a personalization vector \(s\), and spreads relevance by Personalized PageRank with teleport (restart) probability \(\alpha\):

\[\pi = (1-\alpha)\, W\pi + \alpha\, s \quad\Longrightarrow\quad \pi = \alpha\,(I - (1-\alpha)W)^{-1} s,\]

where \(W\) is the column-stochastic transition matrix of the graph. Passages are ranked by the mass their entities accumulate in \(\pi\) — a single-shot approximation of multi-hop retrieval, since relevance flows across relation edges from the seed entities to associated facts (the associative-memory / hippocampal analogy). The power iteration \(\pi^{(t+1)} = (1-\alpha)W\pi^{(t)} + \alpha s\) converges geometrically at rate \((1-\alpha)\).

9.11 Message passing: Graph-of-Thoughts and GNNs

Both Graph-of-Thoughts reasoning and GNN encoders are neighborhood aggregation. A GNN layer updates each node from its neighbors,

\[h_v^{(l+1)} = \phi\!\left(h_v^{(l)},\ \bigoplus_{u\in\mathcal{N}(v)} \psi\big(h_v^{(l)}, h_u^{(l)}, e_{uv}\big)\right),\]

with a permutation-invariant aggregator \(\bigoplus\) (sum / mean / max / attention), message function \(\psi\), and update \(\phi\). GoT specializes this to thought nodes: aggregation edges merge several thoughts into one (in-degree \(>1\)), refinement edges are value-updating self-loops, and generation edges branch one thought into many. This is precisely why a graph strictly generalizes a chain (a path graph) and a tree (in-degree \(\le 1\), no cycles): only a general graph permits aggregation and refinement cycles. Pregel / LangGraph execute the same abstraction as synchronous BSP super-steps — every node receives messages, updates, then sends — which is the computational model under stateful agent graphs (§5.6).

9.12 STaR and ReST-EM as expectation–maximization

Treat the rationale \(r\) as a latent variable and maximize the marginal log-likelihood of the correct answer \(a^\star\):

\[\mathcal{L}(\theta) = \log p_\theta(a^\star \mid q) = \log \sum_{r} p_\theta(a^\star, r \mid q).\]

The EM lower bound uses the posterior \(p_\theta(r\mid a^\star, q)\):

• E-step — sample rationales from the model and keep only those that reach \(a^\star\). This is a hard-EM (rejection-sampling) approximation to the posterior; STaR's "rationalize on failure" (condition on the gold answer to generate a rationale) improves posterior coverage on hard items.
• M-step — maximize \(\mathbb{E}[\log p_\theta(a^\star, r\mid q)]\) by supervised fine-tuning on the kept \((q, r, a^\star)\) traces.

Iterating is (hard) EM on the reasoning marginal, formalized by ReST-EM. Equivalently, with binary reward \(R(r)=\mathbb{1}[\text{answer correct}]\) the update is a reward-weighted / rejection-sampling policy-gradient step,

\[\nabla_\theta\, \mathbb{E}_{r\sim\pi_\theta}[R(r)] = \mathbb{E}_{r\sim\pi_\theta}\big[R(r)\,\nabla_\theta \log \pi_\theta(r)\big].\]

The objective improves monotonically, but only over rationales the model can already sample correctly — the exploration ceiling that bounds all self-training without external signal.

9.13 Alignment objectives: RLHF, DPO, and GRPO

RLHF maximizes a learned reward under a KL leash to the reference policy:

\[\max_{\pi}\ \mathbb{E}_{x,\,y\sim\pi}\big[r(x,y)\big] - \beta\,\mathrm{KL}\big(\pi(\cdot\mid x)\,\|\,\pi_{\text{ref}}(\cdot\mid x)\big).\]

This constrained problem has a closed-form optimum — a reward-tilted reference policy:

\[\pi^\star(y\mid x) = \frac{1}{Z(x)}\,\pi_{\text{ref}}(y\mid x)\,\exp\!\Big(\tfrac1\beta\, r(x,y)\Big).\]

DPO inverts this relation, \(r(x,y) = \beta\log\frac{\pi^\star(y\mid x)}{\pi_{\text{ref}}(y\mid x)} + \beta\log Z(x)\), and substitutes it into the Bradley–Terry preference model \(P(y_w\succ y_l) = \sigma\!\big(r(x,y_w) - r(x,y_l)\big)\). The intractable partition function \(Z(x)\) cancels in the difference, leaving a purely supervised loss with no reward model and no RL loop:

\[\mathcal{L}_{\text{DPO}} = -\,\mathbb{E}_{(x,y_w,y_l)}\,\log\sigma\!\left(\beta\log\frac{\pi_\theta(y_w\mid x)}{\pi_{\text{ref}}(y_w\mid x)} - \beta\log\frac{\pi_\theta(y_l\mid x)}{\pi_{\text{ref}}(y_l\mid x)}\right).\]

GRPO (used to train DeepSeek-R1) removes the value network: for a group of \(G\) sampled outputs with rewards \(\{r_i\}\), it standardizes within the group to form the advantage

\[\hat{A}_i = \frac{r_i - \operatorname{mean}(r_1,\dots,r_G)}{\operatorname{std}(r_1,\dots,r_G)},\]

used in a PPO-style clipped surrogate with a KL penalty to \(\pi_{\text{ref}}\) — cheaper and stable for verifiable-reward RL. Self-Rewarding LMs set the reward \(r\) from the model's own LLM-as-judge scores and then run DPO, closing the loop but capping quality at the judge's reliability (§9.15).

9.14 Self-play fine-tuning as a two-player game (SPIN)

SPIN casts alignment as a game: the current policy \(\pi_\theta\) tries to distinguish human responses from those generated by its previous iterate \(\pi_t\), which is a DPO-style objective with human data as the "winner" and self-generations as the "loser":

\[\mathcal{L}_{\text{SPIN}} = -\,\mathbb{E}_{x,\,y\sim p_{\text{data}},\,y'\sim\pi_t}\,\log\sigma\!\left(\lambda\log\frac{\pi_\theta(y\mid x)}{\pi_t(y\mid x)} - \lambda\log\frac{\pi_\theta(y'\mid x)}{\pi_t(y'\mid x)}\right).\]

The unique fixed point is \(\pi_\theta = p_{\text{data}}\): once the policy matches the data distribution, its samples are indistinguishable from real ones and the gradient vanishes. Self-play more broadly (SPIN, Absolute Zero, R-Zero) works whenever a checker or the data distribution supplies the winner signal for free — no human preferences required.

9.15 Reward hacking, Goodhart's law, and KL control

Let the true objective be \(r\) and the optimized proxy be \(\hat{r} = r + \varepsilon\). Hard optimization of \(\hat{r}\) drives the policy into regions where the error \(\varepsilon\) is large — and where the true \(r\) may actually fall: Goodhart's law, "when a measure becomes a target it ceases to be a good measure." The KL term in RLHF (§9.13) is the brake: at the optimum \(\mathrm{KL}(\pi^\star\|\pi_{\text{ref}})\) grows as \(\beta\) shrinks, so a smaller \(\beta\) permits more over-optimization. Empirically the true reward traces an over-optimization curve

\[r(\text{KL}) \approx \sqrt{\text{KL}}\,\big(\alpha - \gamma\,\text{KL}\big)\]

(rising, then falling as the proxy diverges from truth; Gao et al.). Controls: KL penalty / early stopping, reward-model ensembles, and stronger verifiers. The self-reward setting is the most exposed, because the policy can learn to fool its own judge — the formal reason Meta-Rewarding adds a meta-judge and why RSI loops need an external, hard-to-game verifier.

9.16 Model collapse: variance contraction under recursive training

Suppose generation \(t{+}1\) is trained on \(n\) samples drawn from the model fit at generation \(t\). Even in the ideal Gaussian case with an unbiased mean, the maximum-likelihood variance estimator is biased downward, and iterating shrinks variance in expectation:

\[\mathbb{E}[\sigma_{t+1}^2] = \Big(1 - \tfrac1n\Big)\,\mathbb{E}[\sigma_t^2] \quad\Longrightarrow\quad \mathbb{E}[\sigma_t^2] = \Big(1 - \tfrac1n\Big)^{t}\sigma_0^2 \xrightarrow{t\to\infty} 0.\]

Variance decays geometrically; the distribution's tails vanish first and its support contracts toward a point mass — the "curse of recursion" (model collapse). With finite \(n\) per generation the process is a supermartingale drifting to degeneracy. This is the quantitative danger in self-training (§6.3) and RSI (§7): recursively self-generated data erodes diversity and rare modes. Mitigations reintroduce external signal — mixing in fresh real data (anchoring), larger \(n\), and reward/verifier filtering.

9.17 Recursive self-improvement as a dynamical system

Let \(x_t\) be capability at round \(t\) and \(F\) the (self-)improvement operator, \(x_{t+1} = F(x_t)\). Local behavior near a fixed point \(x^\star = F(x^\star)\) is governed by the gain \(|F'(x^\star)|\):

• Contraction, \(|F'| < 1\) — diminishing returns; \(x_t \to x^\star\) geometrically, so self-improvement plateaus at a ceiling. This is the empirically common regime (filtered self-training, prompt optimization, most agent self-refinement).
• Expansion, \(|F'| > 1\) — each round amplifies the last; small edges compound into take-off.

In continuous time, writing the improvement rate as a power of current capability, \(\dot{x} = c\,x^{\,p}\), the exponent \(p\) decides the fate:

\[p < 1:\ \text{polynomial (no explosion)}; \qquad p = 1:\ x(t) = x_0 e^{ct}\ \text{(exponential)}; \qquad p > 1:\ x(t)\to\infty \ \text{as}\ t\to t^\star = \frac{x_0^{\,1-p}}{c\,(p-1)}.\]

The \(p>1\) case is a finite-time singularity — the precise mathematical shape of an "intelligence explosion" (I.J. Good's runaway). Which regime actually holds is empirical and, crucially, verifier-bounded: \(F\)'s signal comes from a checker, so capability can only be pushed as far as the verifier is correct (§9.5, §9.15). When verification is cheap and reliable (code, math, games) the loop can compound; in open-ended domains \(|F'|<1\) and it saturates — exactly why the 2025–2026 systems (Darwin Gödel Machine, AlphaEvolve, SEAL) pair self-modification with a hard automated evaluation gate.

9.18 The Gödel machine: provably beneficial self-modification

Schmidhuber's Gödel Machine holds its own program \(p\) (including a proof searcher) and a utility \(u\), and rewrites \(p\to p'\) only upon finding, within its axiomatic system \(\mathcal{A}\), a proof that the rewrite raises expected future utility:

\[\mathcal{A}\ \vdash\ \mathbb{E}\big[U(p')\big] \;>\; \mathbb{E}\big[U(p)\big].\]

Because any beneficial self-rewrite of the proof searcher itself is likewise gated by a proof, the improvements are globally optimal given \(\mathcal{A}\) — no myopic local edit can be provably better than the best provable rewrite. The catch is tractability: useful proofs are astronomically hard to find, so the Gödel machine is a theoretical ideal rather than a runnable system. The Darwin Gödel Machine (§7.2) is its practical relaxation — replace "prove it helps" with "empirically show it helps on a benchmark," trading provable optimality for open-ended, verifier-gated exploration.

Key

One skeleton recurs at every layer: a verifier or target distribution supplies signal, a KL or budget constraint bounds drift, and iteration either contracts to a ceiling or (rarely, when the verifier is reliable and returns super-linear) compounds. Self-consistency (§9.3), best-of-\(N\) (§9.5), EM self-training (§9.12), DPO/GRPO (§9.13), self-play (§9.14), and recursive self-improvement (§9.17) are the same mathematical object instantiated at the output, weight, and scaffold levels. The binding constraint is almost always the verifier.

9.19 Progressive disclosure as a context-budget optimization

Skills (§4.10) come with a clean piece of budget math. A library of \(M\) skills would cost \(\sum_{i=1}^M c_i\) tokens if every full body were resident (\(c_i\) = body size). Progressive disclosure keeps only metadata (\(d_i \ll c_i\), ~100 tokens) resident and loads a body only when the skill is selected. If skill \(i\) is triggered with probability \(\pi_i\), the expected resident cost is

\[\mathbb{E}[\text{tokens}] = \sum_{i=1}^{M} d_i + \sum_{i=1}^{M}\pi_i\,c_i \ \ll\ \sum_{i=1}^{M} c_i,\]

so a library can grow almost for free in metadata while paying a full body only for the few skills a task triggers — the same "smallest set of high-signal tokens" logic as context engineering (§3.1). Skill routing is retrieval: the model scores the task against each description and loads the top matches, so the description is the index key and its precision/recall governs both the hit rate and the false-load cost — exactly the scoring problem of §9.7. This is why authoring guidance obsesses over the description: it is the query-time relevance signal, and a mis-scoped one is either a retrieval miss (the skill never loads) or a false positive (wasted body tokens + distraction, §3.2). Self-authored skill libraries (§4.12) make \(M\) itself grow over time — capability accumulating as procedural memory rather than weights.

Appendix A: Thirty-One Things to Memorize

1. The stack: prompt ⊂ context ⊂ harness, with graph cutting across and self-improvement wrapping all.
2. Same model, different harness → large capability delta.
3. Chain-of-Thought and Zero-shot CoT ("let's think step by step").
4. Self-Consistency: majority vote over sampled chains; highest-ROI CoT add-on.
5. Chain → Tree (ToT) → Graph (GoT) of thoughts.
6. ReAct = reason + act + observe; the canonical agent loop.
7. Don't over-prompt reasoning models — budget reasoning, don't scaffold it.
8. Test-time compute: PRMs, compute-optimal scaling, DeepSeek-R1.
9. Programmatic prompting: DSPy (signatures/compilers), TextGrad, ★ GEPA (reflection beats RL at fewer rollouts).
10. ICL theory: induction heads, Bayesian inference, implicit GD; label correctness matters less than format/distribution.
11. Instruction hierarchy + spotlighting; indirect prompt injection is the top agent risk.
12. Context engineering = managing the whole dynamic window as a finite budget.
13. Lost in the Middle and ★ Context Rot: bigger window ≠ solved.
14. ★ NoLiMa: literal needle-in-haystack overstates long-context reasoning.
15. RAG: original, HyDE, hybrid + ColBERT rerank, ★ Contextual Retrieval.
16. Adaptive RAG: Self-RAG, CRAG, FLARE.
17. Agent memory: MemGPT, Mem0, ★ Zep/Graphiti temporal KG.
18. Compaction, note-taking, JIT retrieval, sub-agent isolation for long horizons.
19. Prompt compression: LLMLingua/-2; prompt caching for stable prefixes.
20. Harness patterns (Anthropic): chaining, routing, parallelization, orchestrator-workers, evaluator-optimizer.
21. MCP standardizes tools; CodeAct uses code as the action space.
22. SWE-agent: the Agent-Computer Interface can matter more than the model.
23. GraphRAG: Microsoft GraphRAG, LightRAG, HippoRAG, PathRAG.
24. Optimizable agent graphs: ★ GPTSwarm, ★ AFlow; orchestration via LangGraph.
25. Inference-time self-correction: Self-Refine, Reflexion, CRITIC.
26. Caveat: LLMs can't self-correct reasoning without external feedback.
27. Self-training: STaR, ReST-EM; self-reward: Self-Rewarding LMs, Constitutional AI.
28. Self-play from zero: ★ Absolute Zero, ★ R-Zero; ★ TTRL.
29. RSI: Gödel Machine (theory) → STOP, ADAS, ★ Darwin Gödel Machine, ★ AlphaEvolve, ★ SEAL.
30. Every self-improvement loop is bounded by a verifier and a sandbox; beware model collapse and reward hacking.
31. ★ Agent Skills: packaged procedural knowledge (SKILL.md) via progressive disclosure; the description is the routing key; self-authored skill libraries (Voyager) are weight-free self-improvement.

Appendix B: Decision Guide — "Which Technique?"

1. One-shot factual/format task? → Clear zero-shot instruction + structured outputs.
2. Multi-step reasoning on a non-reasoning model? → CoT + Self-Consistency.
3. Using a reasoning model? → Direct instructions; skip manual CoT; add a verifier for best-of-\(N\).
4. Have eval data and want a better prompt? → Compile with DSPy / ★ GEPA.
5. Answer needs private/fresh knowledge? → RAG (hybrid + rerank; ★ Contextual Retrieval).
6. Global/multi-hop questions over a corpus? → GraphRAG / HippoRAG.
7. Long-horizon agent losing the thread? → Compaction + note-taking + sub-agent isolation; temporal-KG memory (Zep).
8. Context too big / expensive? → LLMLingua compression + prompt caching.
9. Building an agent? → Simplest pattern that works; ReAct + MCP tools; add verification.
10. Need explicit/loopy control flow? → LangGraph; to learn the flow → AFlow/GPTSwarm.
11. Want the agent to improve at runtime? → Reflexion + a real verifier (never rely on intrinsic self-correction).
12. Want the model to improve offline? → STaR/ReST-EM on verifiable tasks; self-play (Absolute Zero) where a checker exists.
13. Want the scaffold to improve itself? → ADAS / ★ Darwin Gödel Machine, benchmark-gated + sandboxed.
14. Want reusable, shareable procedural capability with no fine-tuning? → Author an Agent Skill (crisp description, progressive disclosure, bundled scripts); ship it in a plugin. Let the agent grow its own library (Voyager) for weight-free self-improvement.

Appendix C: Glossary

• ICL — in-context learning: task acquisition from prompt examples, no weight update.
• CoT / PRM — chain-of-thought; process reward model (per-step supervision).
• RAG — retrieval-augmented generation.
• Reranker — a second-stage model scoring (query, doc) pairs precisely (cross-encoder / ColBERT late interaction).
• Context window / budget — the finite token span an LLM attends over; treated as a scarce resource.
• Compaction — summarizing older context into a compact digest to free budget.
• Harness / scaffold — the loop + tools + control flow + verification around the model.
• MCP — Model Context Protocol, an open tool-integration standard.
• ACI — Agent-Computer Interface (the tool/command surface an agent acts through).
• Agent Skill — a SKILL.md folder (name + description + instructions + optional scripts) packaging reusable procedural knowledge, loaded by progressive disclosure.
• Progressive disclosure — load skill metadata always, the body when relevant, and bundled files/scripts on demand; keeps large capability libraries context-cheap.
• Plugin — a bundle of skills + MCP servers + slash commands + subagents, installed from a marketplace.
• GraphRAG — retrieval over an LLM-built knowledge graph (community summaries / path traversal).
• Temporal / bi-temporal KG — a knowledge graph whose edges carry validity + ingestion times.
• RLVR — RL from verifiable rewards (checker-graded, e.g. code/math).
• RSI — recursive self-improvement: improving the improver.
• Reward hacking — optimizing a proxy signal in ways that break the true objective.
• Model collapse — degradation from training on recursively self-generated data.
• Verifier gap — self-improvement works only as far as outcomes are cheaply checkable.

Appendix D: Year-by-Year Milestones

• 2020: GPT-3 few-shot ICL; RAG; ColBERT.
• 2022: CoT, Zero-shot CoT, Self-Consistency, STaR, ReAct, induction heads, Constitutional AI; prompt-injection named.
• 2023: ToT/GoT, DSPy, Self-Refine/Reflexion, MemGPT, Lost in the Middle, Self-RAG, ReST, STOP, Promptbreeder, "can't self-correct yet"; self-authored skill/tool libraries (Voyager, CREATOR, Tool Makers).
• 2024: MCP; GraphRAG, HippoRAG, LightRAG; SWE-agent/OpenHands; Self-Rewarding LMs, SPIN, ReST-EM; ADAS, Gödel Agent; TextGrad; context-window scaling.
• 2025: DeepSeek-R1 & the reasoning-model era; context engineering formalized (Anthropic); ★ Context Rot/NoLiMa; ★ temporal-graph memory (Zep, Mem0); ★ GEPA; ★ self-play from zero (Absolute Zero, R-Zero), ★ TTRL; ★ Darwin Gödel Machine, ★ AlphaEvolve, ★ SEAL; self-evolving-agent surveys (1, 2); ★ Agent Skills (progressive-disclosure capability layer + plugin ecosystem).
• 2026: the four engineering layers converge into self-improving agent stacks; graph memory + agentic GraphRAG mainstream; harness-level RL and benchmark-gated self-modification at the frontier; the open question is whether self-improvement compounds past the base model's ceiling.