Chapter 43

Retrieval, Memory, Planning & Evaluation

Retrieval, context engineering, reflection, search, benchmarks, and prompt injection.

A useful agent is mostly context management: put the right facts in front of the model, remember the right state, choose the next subproblem, and measure whether the loop actually works. These systems matter for LLMs in 2026 because raw model weights cannot contain every private document, every current issue, or every intermediate result of a long task. Retrieval, memory, planning, and evaluation are the control surface around the model.

43.1 Retrieval and RAG prompts

Retrieval-augmented generation (RAG) stores external text, retrieves a few relevant chunks for a query, and asks the model to answer from those chunks [lewis2020retrievalaugmented]. The minimal pipeline is enough to understand the production version. Split documents into overlapping chunks; embed each chunk into a vector; rank chunks by cosine similarity to the query; copy the top $k$ chunks into the prompt.

Listing 43.1 Tiny chunking, embeddings, top-k, and prompt construction

def chunk_words(text, size=40, overlap=8):
    """Split text into overlapping word chunks."""
    words = text.split()
    if size <= overlap:
        raise ValueError("size must be larger than overlap")
    chunks = []
    step = size - overlap
    for start in range(0, len(words), step):
        piece = words[start:start + size]
        if piece:
            chunks.append(" ".join(piece))
        if start + size >= len(words):
            break
    return chunks


def hashed_embedding(text, dims=64):
    """A deterministic bag-of-words embedding with signed hash buckets."""
    vector = np.zeros(dims, dtype=np.float64)
    for token in tokens(text):
        digest = hashlib.blake2b(token.encode(), digest_size=8).digest()
        bucket = int.from_bytes(digest[:4], "little") % dims
        sign = 1.0 if digest[4] % 2 == 0 else -1.0
        vector[bucket] += sign
    norm = np.linalg.norm(vector)
    return vector if norm == 0 else vector / norm


def cosine_top_k(query, documents, k=2, dims=64):
    q = hashed_embedding(query, dims)
    matrix = np.vstack([hashed_embedding(doc, dims) for doc in documents])
    scores = matrix @ q
    order = np.argsort(-scores)[:k]
    return [(int(index), float(scores[index])) for index in order]


def retrieval_prompt(question, documents, k=2):
    hits = cosine_top_k(question, documents, k)
    context = "\n".join(f"[{i}] {documents[i]}" for i, _ in hits)
    return f"Use only this context:\n{context}\n\nQuestion: {question}"

The embedding here is a signed hashed bag of words. It is not semantic like a trained embedding model, but it has the same interface: $ext{embed}(x) o v^d$ , normalize, then score by cosine similarity,

s(q, d) = \frac{\ve_q^\T \ve_d}{\lVert \ve_q\rVert_2\lVert \ve_d\rVert_2} .\tag{43.1}

Chunk size trades recall against precision. Small chunks are easy to fit in the context window but may omit necessary neighbors. Large chunks preserve context but waste tokens and can bury the answer. Overlap reduces boundary failures at the cost of storing repeated text. The prompt should label retrieved text as context, not as higher-priority instructions.

Retrieval also has a failure mode that looks like confidence. The model may answer smoothly from a bad nearest neighbor because the prompt contains no better evidence. Good systems therefore log the retrieved chunk IDs, expose citations to the user, and let downstream evaluation distinguish \"retrieved the wrong evidence\" from \"reasoned incorrectly from the right evidence.\" That split is often more actionable than a single accuracy number.

43.2 Memory and planning

An agent usually has several memories. A scratchpad is the current trace: tool calls, observations, and partial results. A summary memory compresses old turns when the trace grows too large. A vector memory stores snippets under embeddings and recalls them like retrieval.

Listing 43.2 Vector memory as retrieval over past notes

def add_vector_memory(memory, text, dims=64):
    memory.append({"text": text, "embedding": hashed_embedding(text, dims)})


def recall_vector_memory(memory, query, k=2, dims=64):
    if not memory:
        return []
    q = hashed_embedding(query, dims)
    scores = [float(item["embedding"] @ q) for item in memory]
    order = np.argsort(-np.array(scores))[:k]
    return [(memory[int(i)]["text"], scores[int(i)]) for i in order]

Memory is useful only when it is selective. Saving every token forever makes later prompts slower and noisier. A practical system stores durable preferences, decisions, and facts; it discards failed attempts unless they explain a future constraint; and it keeps sensitive data out of memories that will be reused across tasks.

Summaries need the same care as retrieval chunks. A summary is a lossy compression of the trace, so it should preserve decisions, open questions, and invariants rather than narrative detail. If a summary says \"tests passed\" when only one targeted test ran, later planning will inherit a false state. For long jobs, the summary format should make uncertainty explicit.

Planning is the same idea applied to actions. In plan-then-execute, one model call proposes a short list of steps and later calls execute them. In reflection, the loop critiques a failed attempt and appends a summary before retrying; Reflexion is one named version of this pattern [shinn2023reflexion]. In tree search, the system expands several candidate next states and keeps those with the highest value estimate.

Listing 43.3 A tiny value-guided tree search

def tree_search(start, expand, value, depth, beam=2):
    """Keep the best partial plans under a learned or scripted value estimate."""
    frontier = [(start, [start])]
    best = (value(start), [start])
    for _ in range(depth):
        candidates = []
        for state, path in frontier:
            for child in expand(state):
                child_path = path + [child]
                candidates.append((value(child), child, child_path))
        if not candidates:
            break
        candidates.sort(key=lambda item: item[0], reverse=True)
        frontier = [(state, path) for _, state, path in candidates[:beam]]
        if candidates[0][0] > best[0]:
            best = (candidates[0][0], candidates[0][2])
    return best[1]

The value function can be another model call, a reward model, a unit-test score, or a scripted heuristic. Tree search spends more tokens and tool calls to reduce myopia. It should be budgeted like any other agent loop: depth, branching factor, and evaluation cost all multiply.

43.3 Evaluation and pass@k

Agent evaluation must score outcomes, not just fluent transcripts. For code, pass@ $k$ asks whether at least one of $k$ samples passes the tests. If we draw $n$ samples and observe $c$ correct ones, the unbiased estimator from HumanEval is

\widehat{\operatorname{pass@}}k = 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}} .\tag{43.2}

The derivation is counting. Among all $\binom{n}{k}$ subsets of $k$ samples, $\binom{n-c}{k}$ contain only incorrect samples. Subtract that failed-subset fraction from 1. For unbiasedness, average over the random draw of $n$ samples: each fixed $k$ -subset is all wrong with probability $(1-p)^k$ , so the expectation is $1 - (1-p)^k$ . The tests enumerate all correctness patterns for small $n$ .

Listing 43.4 Unbiased pass@k estimator

def pass_at_k(n, c, k):
    """Unbiased estimator: probability a k-subset contains a correct sample."""
    if not 0 <= c <= n:
        raise ValueError("c must be between 0 and n")
    if not 1 <= k <= n:
        raise ValueError("k must be between 1 and n")
    if n - c < k:
        return 1.0
    failed = 1.0
    for i in range(k):
        failed *= (n - c - i) / (n - i)
    return 1.0 - failed


def expected_pass_at_k(n, k, p):
    total = 0.0
    for bits in product((0, 1), repeat=n):
        c = sum(bits)
        probability = (p ** c) * ((1 - p) ** (n - c))
        total += probability * pass_at_k(n, c, k)
    return total

SWE-bench measures whether agents resolve real GitHub issues by editing repositories and passing held-out tests [jimenez2023swebench]. $\tau$ -bench measures tool-agent-user interaction in realistic domains where the agent must follow policies across turns [yao2024bench]. LLM-as-a-judge can scale preference evaluation, but pairwise judges can have position bias; swap answer order, randomize labels, calibrate against human labels, and report confidence rather than a single magic score [zheng2023judging].

Cost and latency are part of the metric. A plan that wins by making 200 model calls may be unusable next to a slightly weaker one that makes 5. Track total input tokens, output tokens, tool calls, wall-clock time, and failure recovery. Agentic RL turns the loop into an environment: actions are messages or tool calls, observations are state, and rewards come from tests, users, or verifiers. DeepSeek-R1 is one 2025 example of using reinforcement learning to incentivize reasoning behavior in LLMs [deepseekai2025deepseekr1].

Report distributions, not only means. Agents have heavy-tailed runtimes: most tasks finish quickly, while a few burn the whole budget through retries or search. A useful evaluation table therefore includes success rate, median latency, high-percentile latency, average cost, and a count of budget exhaustions. The same trace schema used for debugging can produce these metrics automatically.

In practice

Production RAG systems use trained embedding models, metadata filters, rerankers, and caching, but the interface remains top-k chunks into a prompt. Long-running agents keep explicit scratchpads and summaries because relying on the model to remember unstated state is brittle. Benchmarks such as SWE-bench and $\tau$ -bench are more informative than transcript grading because they include real tools, state changes, and hidden checks. LLM judges are useful triage tools, not ground truth; position swaps and human audits are still needed.

Key equations

s(q, d) = \frac{\ve_q^\T \ve_d}{\lVert \ve_q\rVert_2\lVert \ve_d\rVert_2}

\text{RAG}(x) = \text{LLM}(x, d_{(1)}, \ldots, d_{(k)})

\widehat{\operatorname{pass@}}k = 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}}

\E[\widehat{\operatorname{pass@}}k] = 1 - (1-p)^k

\text{cost} = \sum_i \text{tokens}_i \cdot \text{price}_i + \text{tool cost}_i

43.4 Teach it

The one-sentence version. Retrieval supplies facts, memory supplies state, planning chooses where to spend steps, and evaluation tells whether the whole loop helped.

An analogy. A good agent is an open-book exam with a notebook, a plan, and a grader. The book is retrieval, the notebook is memory, the plan orders the work, and the grader checks the final answer.

At the board.

Draw a document split into overlapping chunks, then rank chunks by cosine similarity to a query.
Put the top chunks in a box labeled "context, not instructions."
Show scratchpad, summary, and vector memory as three different stores.
Derive pass@ $k$ by counting failed subsets, then write the cost next to the score.

Misconceptions to address. RAG does not guarantee truth; it only changes what evidence is visible. More memory can make prompts worse. A judge model is still a model with biases.

Check for understanding. Why can increasing $k$ improve pass@ $k$ while also making a system too expensive or slow to ship?

43.5 Exercises

Exercise 43.1 ★ Chunk boundaries

Split ten words into chunks of six words with overlap two. Which words appear in both chunks, and why is that useful for retrieval?

Solution in Appendix D

Exercise 43.2 ★★ Deriving pass@

k

For $n=10$ , $c=3$ , $k=2$ , compute the unbiased pass@ $k$ estimator and explain the failed-subset count.

Solution in Appendix D

Exercise 43.3 ★★ Position-biased judge

A pairwise judge adds one point to the first answer no matter what. Explain why evaluating both orders helps, and write the debiased difference for answers of lengths 4 and 2.

Solution in Appendix D

Exercise 43.4 ★★★ Implement tiny RAG

Using the chapter code, build a one-document RAG prompt for a question. State what the prompt must say to keep retrieved text from becoming an instruction.

Solution in Appendix D

References

[deepseekai2025deepseekr1] DeepSeek-AI et al. DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. 2025. arXiv:2501.12948
[jimenez2023swebench] C. E. Jimenez et al. SWE-bench: Can Language Models Resolve Real-World GitHub Issues? 2023. arXiv:2310.06770
[lewis2020retrievalaugmented] P. Lewis et al. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. 2020. arXiv:2005.11401
[shinn2023reflexion] N. Shinn et al. Reflexion: language agents with verbal reinforcement learning. 2023. arXiv:2303.11366
[yao2024bench] S. Yao et al. τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains. 2024. arXiv:2406.12045
[zheng2023judging] L. Zheng et al. Judging LLM-as-a-judge with MT-Bench and Chatbot Arena. 2023. arXiv:2306.05685
[chen2021evaluating] M. Chen et al. Evaluating Large Language Models Trained on Code. 2021. arXiv:2107.03374