6 Long-Term Memory
Purpose
Agent stack focus for this chapter.
Why does an agent that can search everything it has ever stored still act on the wrong facts?
A context window holds the working state of one model call, and retained attention state only accelerates computation over that same prefix. Neither decides what an agent should still know across sessions, system restarts, or extended operational horizons. Providing an agent with persistent memory requires an external storage architecture that can index varied experiences, retrieve relevant historical context without polluting active prompts, and resolve conflicting observations over time. However, semantic vector retrieval alone provides no temporal guarantees. Stale facts, superseded code versions, and contradicted preferences score just as highly in cosine similarity as fresh ground truth. The runtime must therefore treat every stored memory as a fallible claim that carries its provenance, the versions for which it holds, and an explicit path to invalidation. Reliability depends on keeping persistent state behind explicit consistency rules rather than trusting the model to reconcile contradictory historical evidence.
Learning Objectives
- Classify persistent records by their source, evidential role, and relationship to derived search representations
- Specify a retrieval contract that bounds access, returned content, resource use, and required freshness
- Choose among pre-staged evidence, a direct read, and model-directed search from how much of the need the task names
- Select retrieval methods for an information need, use a bandwidth floor to screen exact vector scans against a latency budget, and estimate multi-hop evidence against a serialized-token budget
- Design a memory write policy for admission, correction, supersession, expiry, and deletion that keeps derived summaries from perpetuating a withdrawn claim
- Explain version-aware exclusion and fallback without mistaking removal of stale candidates for complete fresh retrieval
- Evaluate cross-session memory policies by task outcomes, update behavior, and total resource cost
6.1 Memory Beyond One Session
Consider the repair agent (Four lighthouse workloads) working on its connection-pool defect across several sessions. When the initial session terminates, the subsequent run must reconstruct the operational state: the candidate source tree at revision r18, the diagnostic failure observed at r17, the passing run of test_waiter_notified_on_return, the integration checks that remain unresolved, and an operational note indicating where to resume execution. None of this state survives inside a transient context window once the process exits. Persisting only the final summary message discards critical supporting evidence. Conversely, retaining raw message transcripts without explicit scope creates confusion; an agent reading an unannotated log can easily mistake an earlier failure under r17 for an error in the new candidate patch.
Durable State, closed by checking each retrieved record against its source.
Standard runtime mechanisms do not bridge this gap. Context engineering selects among information already staged for a single model call, while the inference serving system maintains key-value (KV) attention cache state purely to accelerate that computation. Although a prefix cache can outlive an individual request, it remains a derived acceleration structure for a compatible prompt prefix (principle 5), regardless of the storage medium holding it. Long-term memory addresses a different systems problem, preserving information that must govern decisions across distinct invocations. A durable memory system must explicitly resolve what records to retain, how to index and retrieve them efficiently, and how to update or invalidate them when external sources change. In the formal framing of The H·S·A Exposure Space, these records constitute durable State (\(\StateExposureLevel_3\)), persisting across session boundaries.
Architecting persistent memory for an agent requires solving three interconnected systems problems. First, the data model must establish explicit record roles that keep external sources, tool observations, and agent-authored notes strictly differentiated, ensuring that subsequent sessions recognize what evidence each record supports. Second, the system requires a retrieval contract. Regardless of the candidate generation mechanism, every read must report its query scope, the snapshot versions it admitted, and whether the search terminated cleanly or degraded under resource budgets. Third, the storage engine needs a write lifecycle that admits, updates, supersedes, expires, and deletes records while propagating those mutations to downstream indexes and summaries.
The chapter takes these problems in the order a read depends on them. Record roles come first (section 6.2), because every later indexing, retrieval, and invalidation policy depends on knowing what authority a stored record carries. The retrieval contract (section 6.3) then fixes what any read must specify and report, whatever index sits behind it, and the choice between pre-staged and model-directed retrieval (section 6.4) decides which component formulates the query. Three method sections match index structures to information needs, moving from names and syntax (section 6.5) through learned representations and fused rankings (section 6.6) to chains of related evidence (section 6.7). The write path (section 6.8) and storage invalidation (section 6.9) keep the store and its derived indexes truthful as sources change, and the final section (section 6.10) judges a complete memory policy by the tasks it helps finish across sessions.
6.2 Persistent Records
When a multi-session repair agent stores repository source files, test execution logs, and its own progress notes in a single undifferentiated memory pool, a later session can easily treat an unverified hypothesis or an old r17 test log as current ground truth about the code. Those artifacts play different roles in the repair: the repository source defines what the code looks like at a given commit, an execution log records how a test behaved under specific runtime parameters against that commit, and a progress note records only where the previous session planned to resume work. Retrieval strategies, cache validation, and deletion policies all depend on keeping these operational roles distinct.
6.2.1 Record roles
Most persistent state an agent consumes originates outside its execution loop, in version-controlled repositories, production databases, system configurations, and user profiles, while execution produces raw environment observations, tool output traces, progress summaries, and speculative heuristics on top of those sources. Calling all of those artifacts “agent memory” obscures the distinction between a verifiable source and a derived claim. Table 1 categorizes these records by their architectural role in the evidence chain.
| Record role | Example | What a later use must preserve |
|---|---|---|
| Source record | src/pool.py at a specified revision; the user’s stated scheduling preference |
The designated source, applicable version or scope, and access conditions |
| Observation or event log | The outcome of test_waiter_notified_on_return under recorded source, test, and configuration |
What was observed, when, and under which conditions; gaps in the retained history |
| Agent-written memory | A progress note, session summary, or proposed repair lesson | Supporting records, uncertainty, intended scope, and the policy for correction or removal |
| Derived retrieval index | Search entries over source files, logs, or notes | Which source generation produced the entry and how changes affect its use |
A source of record is the designated authoritative origin for a specific claim. For example, the Git tree serves as the source of record for a file’s contents at a particular commit hash, while an authenticated user message serves as the source of record for that user’s operational constraints. Establishing a source of record defines where any downstream assertion must be validated. It confers evidential provenance rather than correctness. A repository commit may harbor a regression, and an inline code comment may contain unauthorized instructions. Under the principle that authority stays with the source (principle 6), authority describes an evidentiary relationship between a claim and its origin, never an unconstrained permission grant. When an agent’s generated output drifts from its source of record, the output still binds whoever deployed the agent, as one tribunal made explicit in the case that follows. For a memory system, the further question is what happens when such an answer is kept and read again.
War Story 6.1: A support chatbot contradicts its policy page (2024)
Mechanism: The chatbot erroneously informed Moffatt that he could purchase regular-fare tickets immediately and submit a bereavement refund claim within 90 days of ticket issuance, directly contradicting the airline’s published policy. When Moffatt submitted his claim, Air Canada denied it based on the static policy page. Before the British Columbia Civil Resolution Tribunal, Air Canada argued that the chatbot was an independent legal entity responsible for its own actions.
Impact: The tribunal rejected Air Canada’s argument, finding that the chatbot was an integral component of Air Canada’s website and that the airline remained liable for all information published through it. Finding Air Canada liable for negligent misrepresentation, the tribunal ordered the airline to pay CA$650.88 in damages (representing the difference between the full fare and the bereavement rate), alongside interest and statutory tribunal fees.
Fix: The tribunal dismissed the assertion that customers must independently reconcile conflicting guidance across different website pages, holding that the airline was responsible for all information on its website, whether a static page or a chatbot supplied it.
Systems lesson: A generated response is a derived artifact, yet users and legal frameworks treat it as an authoritative corporate commitment. The engineering remedy is to stage the versioned source of record into the model call and constrain the answer to claims that text supports, which is the job of the retrieval contract developed below. Model fluency provides neither evidentiary validity nor legal protection.
Through the taxonomy of table 1, the published policy page functioned as the source of record, while the chatbot’s generated response was a derived artifact that diverged from ground truth. If a customer-support system logs its previous dialogue turns to inform future responses, those conversational turns become agent-written memory. They document past interactions, but they never constitute organizational policy. A store that kept the chatbot’s wrong answer and retrieved it for the next bereavement question would repeat the error with the apparent weight of precedent, unless the record carried its role as a derived answer and a link to the policy version it claimed to reflect.
Observation logs capture empirical execution history. When an agent tests a connection pool, an execution log showing a failure at revision r17 remains valid diagnostic history even after revision r18 resolves the bug. The subsequent passing run confirms that the specific reproducer succeeded under that exact environment configuration. An execution log provides primary evidence of what the system observed during a run, rather than proving the universal validity of any underlying program assertion. Retaining this historical record across machine restarts or worker failures requires durable persistence guarantees.
↪ Durable, replicated logs that survive worker and machine failures are developed in The Trajectory Log.
Agent-written memory synthesizes raw observations into structured artifacts for future execution steps, taking the form of scratchpad notes, session summaries, or learned heuristics. Condensing raw traces prevents repetitive computation and conserves context window capacity. However, summarization introduces its own failure modes, because compression can strip vital boundary conditions or fabricate causal explanations. For instance, the observation that the targeted reproducer passed at r18 is strictly justified by the execution log. In contrast, the generalized claim that connection-pool timeouts always stem from missed thread notifications asserts a universal rule that a single test execution cannot substantiate. Storing an unsupported generalization in a persistent database creates compounding errors in subsequent planning steps.
This divergence mirrors the foundational distinction from cognitive psychology (Tulving 1972) adopted by agent architectures: episodic memory captures discrete, time-stamped events anchored to specific execution contexts, whereas semantic memory stores generalized knowledge, rules, and abstractions extracted across multiple episodes, complemented by procedural memory that preserves executable workflows, tool scripts, and operational runbooks. In the terms of table 1, observation logs and episode summaries are episodic records, generated lessons and reference facts are semantic records, and reusable repair workflows represent procedural records. In an engineered system, semantic and procedural records are therefore derived artifacts whose epistemic validity depends entirely on the fidelity and scope of the underlying episodic records.
A retrieval index serves as an auxiliary acceleration structure for locating information across storage tiers. Whether an index stores term postings, learned vector embeddings, or graph edges over source files, logs, and agent notes (structures this chapter develops in turn), an index only locates candidate records. When a search query matches an index entry, a high similarity score demonstrates lexical or semantic affinity to the query string, but provides no assurance of operational applicability to the current task. Operational applicability depends on whether the referenced record matches the current system state, schema revision, and environment constraints.
6.2.2 Read and write lifecycle
Consider the state of a code-repair agent immediately after it writes revision r18. If its vector or keyword index was generated from revision r17, a retrieval query for src/pool.py will return the unpatched file. While that record remains an accurate historical reflection of r17, serving it as current context leads the model to believe the bug persists, prompting redundant or conflicting edits. The staleness that context invalidation guards against thus extends beyond the active prompt into the persistent storage tiers that feed subsequent inference calls.
↩︎ Context invalidation, which withdraws a staged observation’s authority over current state once its source changes, is established in Context Invalidation.
Precomputing search indexes eliminates the need to scan large repositories or execution histories during inference. However, this optimization incurs an ongoing synchronization cost. Every update to a source file requires indexing new content and invalidating or evicting obsolete embeddings. Executing these updates synchronously blocks read or write operations, while background asynchronous indexing opens a lag window in which the index still answers from r17 although the file is already at r18. A query that arrives inside that window needs an explicit rule for what it may return, which section 6.9.2 supplies.
Conversational agents meet the same consistency problem in user state. A user who said “Schedule no meetings before 10:00 AM” later says “before 11:00 AM.” The two directives are nearly identical as text, yet their intent is mutually exclusive. A store that treats the second as a duplicate keeps the stale behavior, and one that appends it without retiring the first leaves a contradiction in every later prompt. Telling a complementary fact from a superseding one requires explicit lifecycle metadata, which the write path (section 6.8) supplies and carries to every derived index, alongside validation, time-to-live (TTL) expiration, and cascade deletion.
The read side comes first, because lifecycle metadata protects the agent only if every read reports it. A retrieval interface must therefore return candidate text alongside the provenance, version, and completeness information on which safe execution depends.
6.3 The Retrieval Contract
Diagnosing the connection pool’s stalled waiter requires both the current implementation in src/pool.py and the test telemetry associated with test_waiter_notified_on_return. A search across repository history can easily return both an r17 test failure and an r18 reproducer pass. While both records are genuine, they answer distinct questions: one documents the defect that triggered the investigation, whereas the other evaluates a candidate patch. Before choosing an index structure or a similarity metric, a system must specify what the agent’s next decision demands and what guarantees a returned record actually establishes.
Definition 6.1: Retrieval contract
A retrieval contract specifies the information requested, the permitted scope and resource limits of the read, and the provenance, applicability, and completion information returned with its results.
- Significance: It ensures a bounded search result remains interpretable before that result enters the next model invocation. A misread or misattributed result exacts a double penalty in the cost per accepted task (equation 1.2): its tokens consume prompt budget and inference cost during the attempt, while the mistaken decision it induces drives down the acceptance probability.
- Distinction: Ranking algorithms merely score and order candidate items under a specific relevance heuristic. The retrieval contract establishes authorization boundaries, version constraints, serialization budgets, and explicit completion semantics.
- Common pitfall: Mistaking an empty result or a truncated scan for definitive proof that the requested data does not exist.
This contract applies uniformly whether the agent executes an index search, a relational database query, or a direct filesystem read; it mandates no single storage layout or similarity threshold. It divides the work among three parties (figure 1). The runtime sets the request’s bounds, the retrieval service checks access and searches within them, and the result envelope reports status, provenance, and limitations before the runtime stages any evidence for the next model call.
6.3.1 The bounded request
A raw information need such as “find the notification logic” underspecifies the retrieval operation. It leaves undefined whether the caller requires the active workspace, an earlier Git revision, or a diff between them; it says nothing about which repositories the principal may access; and it ignores how many tokens the caller’s remaining context window can accommodate. As summarized in table 2, framing retrieval as a bounded request separates these operational constraints from the underlying index mechanics.
| Request field | Meaning in the repair task | Boundary it establishes |
|---|---|---|
| Query or information need | Locate the waiter-notification implementation or the recorded reproducer result | The requested match or observation, not a promise that it exists |
| Authorized scope and principal | The designated repair workspace and the identity under which it is read | The runtime checks permitted paths and records; a scope string alone grants no access |
| Version or freshness requirement | Read r18, compare r17 with r18, or read the current source under stated snapshot semantics | Which state can answer the question |
| Result-count and payload limits | Bound returned items and their serialized representation | Count and content size are separate limits |
| Execution limits | Deadline and supported bounds on scans, expansions, or other search work | When to stop waiting or searching and report incomplete work |
| Optional filters | Restrict file type, symbol kind, or other relevant metadata | Narrow the information need without replacing authorization |
A version requirement differs from a wall-clock freshness heuristic. An index entry for revision r17 remains invalid as current r18 source code even if an indexing worker refreshed it seconds ago. Wall-clock TTLs merely trigger periodic reindexing, whereas explicit version tokens establish whether a cached representation strictly matches its underlying source snapshot. When the retrieval service cannot fulfill the requested version from its precomputed index, it must either fall back to an authorized direct read of the primary store or return an explicit incomplete status. Section 6.9 develops this trade-off once the index itself can lag its source.
Similarly, result-count, payload-size, and compute limits constrain different dimensions of system resource consumption. Ten complete source files consume far more serialized tokens than ten function docstrings, yet returning a single item might still require scanning millions of candidate records. The payload limit protects the caller’s downstream context window, search-work budgets (such as graph traversal caps or posting-list scan limits) constrain retrieval service compute, and execution deadlines prevent the agent runtime from blocking indefinitely. Client timeouts must also propagate cancellation signals to the underlying storage engines; uncancelled background queries continue to consume backend resources and inflate total execution cost.
6.3.2 The result envelope
Returning bare text snippets from a search leaves the caller unable to tell whether the matches came from r17 or r18, or whether zero hits meant the symbol was absent from the repository or the query simply timed out halfway through the index. To keep search outcomes interpretable, a production retrieval service wraps matching records in a result envelope that specifies the repository scope and snapshot revision actually searched, the terminal execution status, and any operational constraints that qualify the results:
completeconfirms that the declared search algorithm ran to conclusion under its stated semantics. It is a mechanical guarantee about the search performed, not a claim to have found every relevant fact.partialindicates that the operation halted before exhaustive evaluation, explicitly recording the abort reason (such as an expired deadline, an unavailable index partition, or an output payload cap).unavailablesignals that the retrieval subsystem failed to return usable data, whether due to network partitions, authorization failures, or service crashes.
When an operation yields partial results or truncates output to respect payload limits, the envelope provides an opaque continuation cursor so subsequent bounded requests can resume paging without re-executing the entire query. Together with the terminal status, that cursor and envelope decide what the runtime may infer when a query returns zero hits, a rule this chapter calls the absence rule. An empty result proves nonexistence if and only if a fully completed exhaustive scan produced it, and even then only within the scanned scope and revision snapshot. A completed literal string search across the repository showing that a symbol does not occur in revision r18 meets this standard. A truncated or partial scan that returns zero matches proves nothing, because the target may reside in an unvisited partition. An approximate index (section 6.6.2) offers no absence guarantee even when it completes, because it deliberately skips most of the candidate space to save work; a result set that lacks the relevant record may reflect that skipped region rather than the record’s absence from the corpus.
At the item level, every returned record carries structured metadata alongside its raw content: a persistent URI or path, byte or line ranges, the exact source commit or snapshot identifier, and a content hash of the returned bytes. When an item represents an empirical observation, such as a test execution log, the record must document the runtime configuration, environment variables, test revision, and terminal outcome. If an item stores a derived lesson or summary synthesized by an agent in an earlier session, its envelope must link to the primary records supporting that inference and flag its status as a derived model output. If the retrieval engine attaches a relevance score, it must name the algorithm that produced it (a lexical ranking function, a vector similarity, or a learned reranker, each developed later in this chapter). Ranking scores exist on their algorithm’s internal scale; systems must not treat them as calibrated probabilities.
status: complete
scope: {workspace: repair, principal: repair-agent, source_snapshot: r18}
items:
- role: source_record
path: src/pool.py
lines: [a, b]
revision: r18
content_hash: h18
score: {method: lexical_rank, value: s}
content: <slice of the return path>
- role: observation
test: test_waiter_notified_on_return
revision: r17
configuration: c17
outcome: failed
content: <recorded failure trace>In the connection-pool repair task, the staged payload might pair a slice of src/pool.py from revision r18 with an error trace recorded under revision r17, as in listing 1, where the fields outside the two content bodies count against the payload budget just as the bodies do. The r17 trace explains why the repair was initiated, but it provides zero evidence regarding the behavior of the r18 candidate. By packaging each record in an explicit envelope, the retrieval subsystem preserves these applicability distinctions across the boundary between persistent storage and the working context. Envelope labels, however, record provenance without certifying veracity. A cryptographic content hash verifies only that the byte sequence matches a specific snapshot; it does not validate the factual correctness of the text. Similarly, categorizing a record as user input or agent-written memory confers no administrative authority on any instructions embedded within that content.
↩︎ The scope rule and the untrusted span are established in Preserving source and scope.
6.3.3 Evidence staging
Piping top-ranked retrieval hits straight from the search backend into the prompt lets uncalibrated similarity scores, stripped version labels, and uncounted metadata wrappers overrun the context budget or slip stale r17 excerpts into an r18 decision. Instead, the agent runtime, never the retrieval backend or an uncalibrated ranking score, determines which records enter the downstream prompt. The runtime curates evidence tailored to the immediate decision, preserves the source and version tags necessary for correct interpretation, and measures the token footprint of the serialized payload. Staging is where invariant closure (principle 1) reaches the durable read boundary. The bound below the model is mechanical, because a runtime rule rather than the model or the ranker decides what is admitted, and the version labels it preserves are the evidence a later acceptance check needs to tell an r17 observation from an r18 one. Even after those checks, retrieved records remain untrusted spans when fetched from a local repository, because serialization that separates them from system instructions cannot stop the model from following text embedded in a record body, the hazard known as prompt injection.
↪ Indirect prompt injection, delivered through retrieved documents and other observations an agent reads, is developed in Prompt injection entry points.
Accurate payload accounting must measure the entire serialized envelope, including wrapper tags, source paths, version identifiers, and status headers, alongside the raw text bodies. Underestimating this structural overhead leads directly to context exhaustion. The token count in notebook 6.1 shows how metadata overhead changes the number of complete records an agent can stage within a fixed prompt allocation.
Napkin Math 6.1: Making room for retrieved evidence
Math: The retrieval allowance is \(32,768 - 2,048 - 24,576 = 6,144\) tokens. Assume a 128-token response envelope and records that each contain 512 body tokens plus 64 metadata tokens, giving 576 tokens per record.
The maximum number of complete records that fit is 10. Staging these records alongside their envelope consumes \(128 + 10 \times 576 = 5,888\) tokens, leaving a remainder of 256 tokens, too few to hold another complete record.
A naive sizing policy that accounts only for raw document bodies would admit 12 records. When serialized with metadata and envelopes, however, those records require 7,040 tokens, overshooting the allocated retrieval budget by 896 tokens.
Systems insight: Metadata and envelope framing consume context capacity just as surely as document bodies. In this configuration, each record dedicates 64 of its 576 tokens to provenance, causing a body-only heuristic to overcommit the prompt by 2 records. The runtime must reserve capacity for output tokens and the global envelope first, then admit \(\lfloor(\text{allowance} - \text{envelope})/(\text{body} + \text{metadata})\rfloor\) records, remembering that every token assigned to system instructions or tool definitions shrinks the retrieval allowance one for one.
Because subword tokenizers (such as Byte-Pair Encoding) merge tokens across string boundaries, tokenizing text fragments in isolation and summing their counts yields an inaccurate total. Runtimes must measure token lengths on the final, fully serialized prompt structure using the target model’s tokenizer. When a critical record exceeds the remaining budget, the runtime must not silently truncate the text. Instead, it should stage a syntactically coherent excerpt with explicit truncation markers, defer the item to a subsequent retrieval pass, or return an opaque handle that the model can resolve on demand.
Every staged token also incurs concrete inference engine overhead beyond occupying space in the context window. Retrieved context must be processed through the model’s compute-intensive prefill phase and then pinned in accelerator memory as key-value (KV) cache tensors for the duration of the generation cycle or prefix cache retention window. Staging more records increases the token volume that the serving engine must process and retain, although the resulting prefill latency depends on the model, prefix reuse, and serving configuration. Every retained token counts against the resident-fit bound of the serving node’s KV pool, so a generous staging policy reduces how many trajectories the node can serve concurrently.
↩︎ The per-sequence footprint of key-value cache state, and how it limits the number of sequences a node can serve concurrently, is established in The Footprint of Retained Attention State.
Checkpoint 6.1: Interpreting a bounded result
Each question presents a retrieval outcome; decide what operational conclusions it licenses.
The retrieval contract establishes the operational bounds, provenance requirements, and payload limits for each read, but it leaves open an architectural question, namely which component formulates the query. A runtime can predict needed evidence and pre-stage it before invoking the model, or it can equip the agent with search tools to probe the store interactively as discoveries unfold.
6.4 Agentic Retrieval
Predicting every file the repair agent will need before invoking the model either stuffs the prompt with irrelevant code or misses a helper dependency that becomes visible only after reading the first stack frame, whereas forcing the model to search interactively for files the task already named wastes an entire inference turn on a predictable lookup. Two retrieval architectures divide this work differently. In a pre-staged architecture, the runtime predicts which artifacts will be necessary (such as src/pool.py, tests/test_pool.py, and a stack trace from a prior run) and injects them directly into the prompt before model execution begins. In an agentic architecture, the runtime equips the model with bounded text search, file reading, and symbol-navigation tools, allowing the agent to locate notification logic, inspect the test harness, and follow cross-file references as intermediate discoveries dictate. Both architectures operate over the same underlying storage systems and share identical security boundaries. They differ in when the information need is resolved and which component formulates the retrieval queries.
Pre-staging implements standard retrieval-augmented generation (RAG), where the host system selects external documents and packages them alongside the prompt before inference begins (Lewis et al. 2020). By contrast, agentic retrieval delegates query formulation to the model during the execution loop, interleaving environment observations with subsequent reasoning and action steps (Yao et al. 2023). Autonomous systems designed for repository-scale software engineering (Jimenez et al. 2024) rely on this interactive loop, because providing the model with search and navigation commands shaped for code inspection proves far more adaptable than staging a single, static set of top-\(\RetrievalCutoffCount\) retrieved passages up front (Yang et al. 2024). Rather than mutually exclusive alternatives, these two patterns represent complementary policies operating over the same underlying data stores.
Pre-staging excels when the evidence required for the next decision is predictable. Loading src/pool.py and tests/test_pool.py directly into the prompt eliminates the latency and inference cost of an exploratory turn spent locating those files. However, pre-staging carries operational risks. It can consume scarce context capacity with irrelevant code, or conversely, miss transitively imported dependencies that only become apparent upon inspecting the source. Model-directed iterative search resolves this rigidity by allowing each discovery to reshape subsequent queries. For example, a failing assertion in a test file might name an internal helper function, prompting the agent to inspect that specific definition next. Interactive exploration, however, introduces its own failure modes. An agent can chase unpromising leads, execute redundant searches across familiar directories, or terminate its investigation prematurely before gathering sufficient evidence.
Before introducing an auxiliary index, such as an inverted text index or a vector store, an engineer should benchmark against a live-source baseline. Bounded substring searches and direct file reads inspect the target workspace directly on disk, introducing no external index that can lag behind ongoing edits. When a problem description already specifies exact filenames or literal error strings, these live-source primitives often supply all the retrieval capability the agent requires. Direct filesystem access, however, presents distinct systems trade-offs. Live reads observe whichever version of a file exists at the exact moment of execution; if concurrent processes modify the workspace, separate reads executed across successive turns can straddle modifications and observe inconsistent snapshots. Furthermore, raw literal searches locate character matches without semantic awareness, failing to distinguish an active symbol definition from an obsolete comment or an unrelated log message. An auxiliary index justifies its memory footprint, construction time, and synchronization overhead only when it measurably amortizes repetitive scanning costs across long trajectories, resolves vocabulary mismatches through semantic embeddings, or accelerates traversal over structural relationships such as call graphs derived from abstract syntax trees (ASTs). An evaluation must charge the cost of building and refreshing the index directly against its query-time savings, a charge the chapter prices at its end, once lexical, dense, and graph indexes are in hand (notebook 6.5).
When an agent probes its environment, the runtime can optimize query execution through parallelism. A single model turn can emit several independent tool calls that the runtime batches or executes concurrently across threads; only queries that strictly depend on earlier observations must block for sequential resolution. Table 3 summarizes the core trade-offs between runtime pre-staging and model-directed probing.
| Property | Runtime pre-staging | Model-directed probing |
|---|---|---|
| Query selection | Runtime policy selects evidence before model invocation | Model formulates queries dynamically from prior observations |
| Optimal scenario | Likely evidence needs are predictable in advance | Intermediate results dictate which question to ask next |
| Computational overhead | Retrieval latency and staging cost prior to the call | Search latency and extra inference rounds for query refinement |
| Characteristic failure | Missing transitively imported dependencies or bloating context | Chasing unproductive paths or terminating search prematurely |
| Freshness guarantee | Governed by source version and read contract at staging | Governed by the same read contract at tool execution time |
| Resource governance | Bounded by staging timeouts and context-window capacity | Bounded by per-call limits and trajectory-wide step budgets |
Under both policies, the execution runtime retains authority over security boundaries and resource consumption. The model acts strictly as an untrusted query generator. It may propose a narrower search path, supply query strings, or request specific filters, but it can never expand the authorized workspace, assume a different principal identity, or increase its own resource ceilings. The runtime enforces these boundaries at the tool interface. Tool calling schemas define and constrain the supported request parameters, while tool execution results transmit truncation warnings, resource limits, and continuation tokens back to the agent.
↪ Tool interface schemas that bound which request parameters a model may supply are developed in Tool Interface Schemas.
In production systems, these two strategies often merge into a tiered hybrid policy. The runtime pre-stages a compact workspace outline, an architectural summary, or persistent user preferences directly into the initial context window, giving the model immediate structural grounding. The agent then issues targeted tool calls to inspect specific function implementations or test traces only when those details become necessary. Evaluating such a hybrid design requires balancing the upfront token overhead of pre-staging against the inference latency and token expenditure of avoided tool turns.
The choice among a direct read, pre-staging, and directed probing follows from how much of the information need the task itself names. When the task names its targets, such as src/pool.py or a pinned note, a direct read stages exactly those records and spends no ranking or exploratory turn. When the needed evidence is predictable but unnamed, such as the tests that usually accompany a module, pre-staging captures it in one step at the price of some irrelevant tokens. When each needed item can be found only from the one before, as when a failing assertion names a helper whose definition names a lock, no pre-staged set can anticipate the chain, and model-directed probing pays one model round per dependent hop. A hybrid seeds the first hop by pre-staging or direct read and leaves the remaining hops to probing. Whichever component formulates the query, what comes back depends on the matching mechanism behind the read, whether lexical matching, learned similarity, or structural traversal, and each mechanism answers a different kind of information need.
6.5 Lexical and Structural Retrieval
When the repair agent investigates its stalled waiter, it faces distinct information needs: locating tests/test_pool.py, finding references to test_waiter_notified_on_return, and isolating the function enclosing a suspect synchronization statement. A well-designed retrieval contract does not force these varied tasks through a single mechanism. A known file path requires only a direct file read. A specific identifier calls for literal text search or symbol lookup. A broad symptom description requires ranking multiple candidate passages before the agent can decide which source files merit inspection.
6.5.1 Exact lookup and lexical ranking
Searching for a known identifier like test_waiter_notified_on_return across a repository can return dozens of matches across definitions, comments, import lines, and archived failure logs without telling the caller which hit defines the test or which file matters most. Exact path lookup retrieves a named object directly from an authorized repository snapshot, and literal text search scans for exact character sequences under declared matching rules such as case sensitivity and boundary delimiters, but neither interprets semantic role or orders a large candidate set.
To support repeated lexical queries across large corpora without scanning every byte on disk, retrieval systems rely on an inverted index (Zobel and Moffat 2006). The index maps each distinct term to a postings list containing every document where the term appears. Beyond the document identifier, each posting typically stores the term’s in-document frequency and position offsets. How source text maps into postings depends entirely on the index’s analyzer. The analyzer determines token boundaries: whether it preserves full identifier tokens, splits snake_case and camelCase identifiers, normalizes letter case, or strips inflectional affixes through stemming. Consequently, a ranked match on an analyzed identifier behaves differently from an exact match on the raw string. When an agent requires an exact literal hit, it must either query an unanalyzed exact-match field or verify the returned source snippet directly.
1 BM25 (Best Match 25): The name records one weighting in the “Best Match” series of the Okapi retrieval system, built on the simple approximations to a two-Poisson model of term occurrence that Robertson and Walker (1994) derived. The formula survived decades of learned rankers because it needs no training data, only corpus statistics an index already keeps, which is why it remains the baseline a repository agent can deploy on the day its workspace is created.
2 Inverse Document Frequency (IDF): Spärck Jones (1972) proposed weighting a term by how few documents contain it, on the argument that a term shared by most documents cannot tell them apart. In a repository that argument favors exactly the tokens an agent searches for, such as a unique test name or error string, and discounts keywords every file shares, which is why a rare identifier ranks sharply under BM25 while a vague symptom description does not.
When a query matches dozens or hundreds of candidates, ranking determines which documents enter the agent’s bounded context window. The BM251 scoring function balances three factors: term rarity across the corpus,2 sub-linear term frequency saturation within each candidate, and document-length normalization (Robertson and Zaragoza 2009):
\[ \operatorname{score}(\LexicalDocument,\LexicalQuery)=\sum_{\QueryWord\in \LexicalQuery}\operatorname{IDF}(\QueryWord) \frac{\QueryWordFrequency(\QueryWord,\LexicalDocument)(\LexicalFrequencySaturation+1)}{\QueryWordFrequency(\QueryWord,\LexicalDocument)+\LexicalFrequencySaturation(1-\LexicalLengthNormalization+\LexicalLengthNormalization\lvert \LexicalDocument\rvert/\MeanDocumentLength)}, \qquad \operatorname{IDF}(\QueryWord)=\ln\left(1+\frac{\IndexedDocumentCount-\QueryWordDocumentFrequency(\QueryWord)+0.5}{\QueryWordDocumentFrequency(\QueryWord)+0.5}\right). \tag{1}\]
Here \(\LexicalQuery\) contains the query terms, \(\LexicalDocument\) is an indexed document, \(\QueryWordFrequency(\QueryWord,\LexicalDocument)\) is the term frequency of \(\QueryWord\) in \(\LexicalDocument\), \(\lvert \LexicalDocument\rvert\) is the document length in analyzer terms, and \(\MeanDocumentLength\) is the collection’s mean document length. The corpus contains \(\IndexedDocumentCount\) documents in total, of which \(\QueryWordDocumentFrequency(\QueryWord)\) contain query term \(\QueryWord\). These lengths are analyzer counts, not the foundation model’s token counts. These symbols are local to lexical ranking; in particular, \(\LexicalDocument\) and \(\LexicalLengthNormalization\) do not carry the meanings earlier chapters gave those letters. The tuning parameter \(\LexicalFrequencySaturation>0\) controls term-frequency saturation. At a fixed document length, the frequency factor rises toward \(\LexicalFrequencySaturation+1\) as \(\QueryWordFrequency(\QueryWord,\LexicalDocument)\) grows, so each additional occurrence adds less to the score than the one before. The parameter \(\LexicalLengthNormalization\in[0,1]\) modulates document-length normalization, with \(\LexicalLengthNormalization=1\) fully penalizing documents proportional to their relative length and \(\LexicalLengthNormalization=0\) disabling length normalization entirely. Because ranking depends on these mechanics, document chunk boundaries, analyzer choices, and parameter settings alter candidate scores even when the underlying source text remains unchanged.
Example 6.1: A higher lexical score is a ranking decision
Analysis: A short candidate contains 80 terms and 1 occurrence of the query term; a long candidate contains 4,000 terms and 6 occurrences. The length term \(\LexicalFrequencySaturation(1-\LexicalLengthNormalization+\LexicalLengthNormalization\lvert \LexicalDocument\rvert/\MeanDocumentLength)\) in the denominator of equation 1 is 0.48 for the short candidate but 9.3 for the long one, so the long candidate’s extra occurrences are divided by a far larger denominator. Substituting these counts into the scoring rule gives 14.58 for the short candidate and 8.46 for the long candidate. Repetition alone does not determine their order: saturation and length normalization outweigh the long candidate’s additional occurrences.
Systems lesson: Rank orders candidates for inspection. If the short candidate is a comment while the long one holds the implementation, the agent still needs source inspection or structural information, and choosing whole files rather than functions as documents would change both scores.
6.5.2 Structural evidence
A lexical match on notify finds the token inside src/pool.py and inside an archived r17 failure log alike, but it cannot return the complete enclosing function or trace which test calls the method that invokes notify(). Structural retrieval recovers that program organization: the enclosing function, type declarations, lexical scopes, and identifiers in call expressions. A parser translates source text into abstract syntax trees with explicit spans, while symbol resolution and semantic analysis establish directed relationships between definitions and call sites. While parsing a call expression identifies the call site syntactically, resolving which concrete implementation executes at runtime requires interprocedural analysis.
During the connection-pool repair, a structural query can return the entire function containing a notification call in src/pool.py rather than an arbitrary fragment, and a reference query can subsequently identify its callers across the codebase. Static coverage depends on language semantics, dependencies, and build configuration; dynamic dispatch, reflection, generated code, and cross-process calls frequently escape static resolution. In a structural index, a missing edge indicates a gap in static coverage rather than an unreachable path, while a static call edge records a potential invocation rather than an executed one. The two representations see the pool’s sources differently (figure 2). A lexical index finds the term notify in the pool source and the r17 failure log alike, whereas a structural index records that the waiter test calls the pool’s return method, which in turn calls the notification, a caller-callee chain that string matching cannot recover.
Table 4 separates the questions these methods answer. Lexical indexes can carry path and symbol metadata, but text matching alone establishes no semantic relationship.
| Information need | Suitable starting method | What the result establishes |
|---|---|---|
| Read a known path or locate a literal identifier | Direct source read or declared exact-match search | The requested content or occurrences within the searched scope and version |
| Find likely relevant documents from query terms | Lexical ranking such as BM25 | Candidate order under the analyzer, document boundaries, and scoring rule |
| Find an enclosing function or resolved references | Syntax or semantic index with declared coverage | Parsed boundaries or analysis-derived relationships, not complete runtime behavior |
6.5.3 Search scope
When a search service selects its top-ranked candidates globally across the repository and only afterward discards results outside src/pool.py and tests/test_pool.py (post-filtering), it can easily return an empty set while eligible matches sit farther down the global ranking. Restricting an initial probe to src/pool.py and tests/test_pool.py focuses the evidence and limits noise only when filtering and ranking are coordinated and the retrieval interface explicitly reports that bounded scope; a subsequent probe can then widen the scope to investigate callers across the repository. Restricting candidates before final scoring (pre-filtering) avoids the post-filtering drop, as does continuing postings traversal until the requested quota of filtered documents is filled. When query budgets or latency limits terminate the search early, the result remains partial.
Choosing the evaluation order is a cost-based optimization decision analogous to access path selection in relational database optimizers (Selinger et al. 1979).3 The decision balances the filter’s selectivity against the rarity of the query terms. A selective filter, such as one that isolates two files in a repository of thousands, favors pre-filtering candidate documents and evaluating BM25 scores only on the survivors. Conversely, a broad filter paired with a rare identifier favors scoring first, because the rare term’s postings list is already short, provided the search engine continues scanning until enough eligible results remain. This trade-off reemerges with even sharper operational hazards when searching vector proximity graphs (section 6.6).
3 Cost-Based Access Path Selection: The System R optimizer chose among index scans, sequential scans, and join orders by estimating each predicate’s selectivity and the pages each plan would touch (Selinger et al. 1979). A retrieval gateway faces the same estimate with a scope filter as the predicate and a postings list or vector index as the access path, and a wrong estimate costs either a scan of the whole corpus or an empty result that looks like absence.
6.5.4 Vocabulary mismatch
Early in an investigation, the agent may know only an observed symptom such as “a connection is returned, but another caller keeps waiting,” phrased in words the source code never uses, so exact and structural lookups return nothing. This failure is the vocabulary mismatch problem, where code authors and users describe identical concepts using distinct vocabularies (Furnas et al. 1987). Heuristic techniques like identifier splitting, synonym expansion, or query reformulation can recover some lexical matches; once an exploratory search identifies a concrete test name, literal lookup is far more direct than further conceptual search. When lexical heuristics still leave the candidate set inadequate, the agent needs a representation that maps descriptive prose to differently worded source implementations, along with hybrid rankers that combine dense semantic similarity with exact lexical precision without mistaking similarity for verification.
6.6 Dense and Hybrid Retrieval
When an agent investigates a bug report describing a caller that hangs indefinitely, lexical search across the repository can easily rank the critical return path in src/pool.py low or miss it entirely. The line that matters executes notify(), but the report describes a caller that keeps waiting. Dense retrieval supplies a complementary candidate-generation mechanism, using learned representations to match a query against records that share underlying meaning rather than literal tokens. Because dense and lexical methods fail in different places, production systems usually run both and combine their rankings (section 6.6.3).
6.6.1 Dense retrieval
To connect a symptom like “a caller keeps waiting” to self._available.notify() when the two share no keywords, dense retrieval encodes a query and each searchable record as vectors using a learned model, ranking records by vector similarity.4 In a bi-encoder architecture, records are embedded offline before a request arrives, leaving only the query to be encoded online at request time (Karpukhin et al. 2020). This separation removes heavy embedding inference from the critical query path, but offline encoding creates an ongoing maintenance obligation: newly inserted or modified records require fresh vector generation, and upgrading or fine-tuning the underlying encoder invalidates the entire index, demanding a complete corpus re-embedding.
4 Vector Space Model: Ranking documents by the angle between a query vector and each document vector predates learned encoders; Salton et al. (1975) represented every document as a vector of term weights and scored it by cosine similarity. Dense retrieval keeps the geometry and replaces sparse, interpretable term weights with learned components, which is what lets it bridge vocabulary and also why no single component explains a match.
The distance metric is defined by the interaction between the encoder and index configurations. For example, inner product search is mathematically identical to cosine similarity when vectors are unit-normalized (\(\ell_2 = 1.0\)), which shifts the computational cost of vector normalization to indexing time rather than paying for vector division on the query path. Neither metric, however, produces a calibrated probability that a candidate record answers the agent’s question; they represent uncalibrated geometric affinities.
In the software repair task, a dense retriever can readily connect the symptom of a waiting caller to the return-and-notify implementation, yielding a promising candidate for inspection rather than proof of a defect. The semantic abstraction that bridges vocabulary gaps, however, can also blur fine syntactic distinctions on which code execution depends. Consider a concrete case in src/pool.py: the return path invokes self._available.notify(), the shutdown routine invokes self._available.notify_all(), and acquisition invokes self._available.wait(timeout). All three statements share the same condition variable, module context, and conceptual vocabulary of thread synchronization. Consequently, an encoder often maps all three to neighboring points in vector space when queried about thread unblocking. Their operational semantics are nonetheless entirely distinct: one wakes a single waiter, another wakes every waiter, and the third blocks. An exact lexical search for notify( isolates the call site immediately, and BM25 assigns the rare identifier a high inverse document frequency (IDF). The systems challenge is therefore determining which retrieval mechanism surfaces the precise evidence the workload requires.
6.6.2 Exact and approximate vector search
Scoring a query vector against every vector in an unfiltered multi-million-record store streams gigabytes of embeddings from memory on every search, yet building an approximate index is unnecessary complexity when a tenant or file filter already narrows the eligible set to a few thousand vectors. An exact vector scan scores every vector in the eligible search set under the chosen distance metric. It serves as the baseline ground truth for measuring what an approximate search misses, and it remains a practical serving method whenever the eligible candidate set is small enough to stream within the latency budget.
The resource requirements of an exact scan follow directly from dimensional arithmetic, independent of any specific hardware architecture. Let \(\EligibleVectorCount\) be the number of eligible vectors, \(\EmbeddingDimension\) their dimension, and \(\ElementStorageSize\) the storage width in bytes per component; like the ranking symbols before them, these letters are local to vector search. Traversing the stored vectors requires streaming \(\EligibleVectorCount \EmbeddingDimension\ElementStorageSize\) bytes from memory, so on a memory system that sustains bandwidth \(\Bandwidth\) one scan takes at least \(\EligibleVectorCount \EmbeddingDimension\ElementStorageSize/\Bandwidth\). Counting two floating-point operations per multiply-accumulate operation, dot-product scoring requires approximately \(2\EligibleVectorCount \EmbeddingDimension\) FLOPs. These totals account only for the vector inner products; they exclude the latency of query embedding, top-\(\RetrievalCutoffCount\) heap maintenance, and fetching the full record payloads from persistent storage.
↪ The roofline model and the ridge point that separates bandwidth-bound from compute-bound work are developed in Cost Asymmetry Between Input Prefill and Output Generation.
Napkin Math 6.2: Why an exact vector scan is bandwidth-bound
Math: Multiply the vector count by the dimension and component width:
\[ \EligibleVectorCount \EmbeddingDimension\ElementStorageSize = 10^7 \times 768 \times 2\ \text{bytes}. \]
The raw vectors occupy 15.36 GB. Counting two FLOPs per multiply-add gives \(2\EligibleVectorCount \EmbeddingDimension\), or 15.36 GFLOP per scan. Arithmetic intensity, the FLOPs performed per byte moved from memory, is therefore \(2\EligibleVectorCount \EmbeddingDimension/(\EligibleVectorCount \EmbeddingDimension\ElementStorageSize) = 2/\ElementStorageSize\), which is 1 FLOP/byte at FP16 whatever the corpus size or dimension. The reference host delivers 1 TFLOP/s and 50 GB/s, a ridge point of 20 FLOP/byte, the intensity below which memory bandwidth rather than arithmetic limits the rate. The scan sits far below the ridge, so bandwidth sets its floor. Streaming the vectors takes at least 307.2 ms, while the arithmetic alone would take 15.36 ms. A trajectory that issues 20 such searches spends at least 6.1 s moving vectors. Because the floor is linear in the eligible count, a scope filter that leaves 10,000 vectors has a streaming floor of 0.31 ms. A 10 ms search budget sets an optimistic maximum of ~326,000 vectors on this host before accounting for the rest of the request.
Systems insight: The intensity of an exact scan is fixed by the component width, so added arithmetic never speeds it up, and an accelerator’s higher ridge leaves it bandwidth-bound there too. The levers are fewer bytes per vector (compression) and fewer vectors touched (a narrower eligible set or an approximate index). The bandwidth floor screens out exact scans that cannot meet the search budget. When that floor fits, benchmark the complete request, including query encoding, top-\(\RetrievalCutoffCount\) selection, and record fetches. Choose an exact scan when its measured request latency meets the budget; an approximate index must justify its maintenance cost and recall loss against that baseline.
The memory-bandwidth limit behind output-bound latency (principle 2) therefore reappears in retrieval, because an exact scan, like a decode step, performs only a few operations for each byte it streams. The same arithmetic shows where an exact scan remains the right choice. When selective metadata filters restrict the search space to thousands of eligible vectors, an exact scan streams megabytes rather than gigabytes, reducing the streaming floor to sub-millisecond times without the operational overhead of graph maintenance or quantization codebooks.
The exact-scan streaming floor grows with eligible vectors; the search budget sets an optimistic candidate ceiling.
5 Approximate Nearest Neighbors: Exact nearest-neighbor structures that work well in two or three dimensions degrade toward a full scan as dimension grows, the curse of dimensionality. Indyk and Motwani (1998) relaxed the problem to returning a point within a factor of the true nearest distance and showed, through locality-sensitive hashing, that the relaxation admits sublinear query time. Every ANN index an agent uses makes the same bargain, so its misses are part of the contract, measured as recall, never a defect to be tuned away.
When candidate sets grow into millions of vectors and queries must return within tight latency budgets, scanning the entire corpus becomes prohibitive. Approximate nearest-neighbor (ANN) search5 trades mathematical exactness for orders-of-magnitude reductions in latency and memory traffic, pruning the search space at the cost of occasionally missing true nearest neighbors. Systems cut memory traffic in one of two ways: by traversing a proximity graph to evaluate only a tiny fraction of the vector population, or by partitioning the space and compressing vector representations with quantization codes.
A hierarchical navigable small-world (HNSW) index organizes high-dimensional vectors into a multi-layer proximity graph (Malkov and Yashunin 2018). Layer 0 contains every vector in the dataset. Each inserted vector is also assigned a maximum layer \(\ell = \lfloor -\ln \HnswLevelDraw \cdot \HnswLevelNormalization \rfloor\), where \(\HnswLevelDraw\) is drawn uniformly from \((0, 1]\) and \(\HnswLevelNormalization = 1 / \ln \HnswMaximumConnectionCount\), with \(\HnswMaximumConnectionCount\) defining the maximum number of bidirectional connections per node per layer. The assignment gives each vector probability \(\HnswMaximumConnectionCount^{-\HnswLayerIndex}\) of reaching layer \(\HnswLayerIndex\) or above, so each layer holds roughly \(1/\HnswMaximumConnectionCount\) as many nodes as the one beneath it, an exponentially thinning hierarchy that mirrors the express transit lanes of a skip list (Pugh 1990). Traversal begins at an entry point in the sparsest top layer, greedily hopping to whichever neighbor minimizes distance to the query vector \(\SearchQueryEmbedding\). When no neighbor yields further progress, the search drops down to that node’s counterpart in the next layer and resumes the greedy walk. Upon reaching layer 0, the traversal switches from greedy routing to a beam search that maintains a priority queue of the \(\HnswSearchBeamWidth\) closest candidates discovered so far. The search terminates when the closest unexplored neighbor cannot improve the current candidate set, returning the top \(\RetrievalCutoffCount\) vectors. The beam width \(\HnswSearchBeamWidth\) is the primary query-time recall knob. A vector the beam never visits cannot be returned (figure 3), so widening the beam evaluates more distances and recovers more true neighbors at the cost of higher query latency.
Constructing an HNSW graph requires executing this layered search for every incoming vector and establishing bidirectional links to its nearest neighbors in each layer. This graph topology incurs substantial memory overhead beyond the raw vectors. Deletions are harder still, because severing a node without reconstructing edge paths among its neighbors risks partitioning the graph and stranding downstream vectors. Production systems therefore mark a deleted node with a tombstone, an exclusion marker that hides it from results while its links stay in place, and section 6.9 examines how the cost of that compromise compounds.
Rather than navigating a graph over full-precision vectors, an inverted file index combined with product quantization (IVF-PQ) reduces memory traffic by partitioning the vector space and lossily compressing the stored representations (Jégou et al. 2011), with an offline build pipeline and an online query pipeline (figure 4). During index construction, coarse \(\Glyph{k}\)-means clusters the corpus into \(\CoarseCellCount\) Voronoi cells (each cell is the region of vectors nearer its centroid than any other centroid), each backed by an inverted list of vector identifiers. At query time, the system computes the distance from the uncompressed query vector to all \(\CoarseCellCount\) coarse centroids and evaluates only the vectors residing in the \(\ProbedCellCount\) closest cells.
Product quantization then compresses every stored vector. It splits the \(\EmbeddingDimension\) dimensions into \(\PqSubvectorCount\) distinct subvectors of dimension \(\EmbeddingDimension/\PqSubvectorCount\). For each subspace, \(\Glyph{k}\)-means trains a codebook of 256 centroids, allowing any subvector to be represented by a single one-byte index \(\PqCentroidCode_j \in [0, 255]\) indicating its nearest centroid. Storing a compressed vector therefore requires only \(\PqSubvectorCount\) bytes. At query time, the uncompressed query vector \(\SearchQueryEmbedding\) is segmented into the same \(\PqSubvectorCount\) subspaces. The runtime precomputes an asymmetric distance lookup table \(\text{LUT}[\PqSubspaceIndex, \PqCentroidCode]\), which stores the squared Euclidean distance between the query’s \(\PqSubspaceIndex\)-th subvector and centroid \(\PqCentroidCode\) in subspace \(\PqSubspaceIndex\). The approximate distance between the query \(\SearchQueryEmbedding\) and a stored quantized vector \(\StoredIndexVector\) with codes \(\PqCentroidCode_1, \dots, \PqCentroidCode_{\PqSubvectorCount}\) reduces to summing table lookups:
\[ \PqApproximateDistance(\SearchQueryEmbedding, \StoredIndexVector) = \sum_{j=1}^{\PqSubvectorCount} \text{LUT}[\PqSubspaceIndex, \PqCentroidCode_j]. \tag{2}\]
Equation 2 transforms a bandwidth-bound \(\EmbeddingDimension\)-component dot product into \(\PqSubvectorCount\) single-byte reads and table lookups. Because the lookup table is small enough to stay in processor cache, each scored vector costs \(\PqSubvectorCount\) bytes of memory traffic instead of \(\EmbeddingDimension\ElementStorageSize\), a reduction by the factor \(\EmbeddingDimension\ElementStorageSize/\PqSubvectorCount\) in exactly the term that bounded the exact scan. The parameter \(\ProbedCellCount\) balances recall against the number of cells scanned, while the subvector count \(\PqSubvectorCount\) trades distance fidelity against bytes per code. Systems commonly recover distance accuracy by re-scoring a short candidate list against full-precision vectors stored on secondary media or remote memory. The same design scales to billions of vectors on accelerators (Johnson et al. 2019). The quantization codebooks and coarse centroids, however, are calibrated on the vector distribution present during index construction; as the corpus drifts or the embedding model changes, quantization error grows until the index is retrained.
Sizing both designs for the 10-million-vector corpus of the exact-scan notebook shows what each one costs in memory. With 32 eight-byte links per node, an HNSW graph adds 2.56 GB of edge topology to 15.36 GB of vectors. Because greedy routing traverses arbitrary graph links, memory access patterns are dominated by dependent random reads, requiring both the graph and the vectors to remain memory-resident. Product quantization with 64 subvectors of 12 dimensions stores 0.64 GB of codes, 24× smaller than the FP16 vectors, and its per-query lookup table occupies only 65.5 KB. Table 5 sets the three designs side by side.
| Property | Exact scan | IVF-PQ | HNSW |
|---|---|---|---|
| Work per query | Every eligible vector | \(\CoarseCellCount\) centroids plus the codes in \(\ProbedCellCount\) cells | Distances along a greedy path and a beam of width \(\HnswSearchBeamWidth\) |
| Resident bytes (notebook) | 15.36 GB | 0.64 GB of codes, plus centroids and codebooks | 17.92 GB of vectors and links |
| Distance fidelity | Exact under the metric | Approximate; re-scoring a short list recovers it | Exact for each visited vector; misses come from unvisited ones |
| Recall knob | None needed | \(\ProbedCellCount\), \(\PqSubvectorCount\) | \(\HnswSearchBeamWidth\), \(\HnswMaximumConnectionCount\) |
| Insert and delete | Append; delete by exclusion | Cheap append; centroids and codebooks age as the corpus drifts | Insert runs a search and relinks neighbors; delete leaves a marked node |
| Memory access | Sequential streaming, bandwidth-bound | Short sequential scans of small codes | Dependent random reads, one per hop |
Selecting among these index structures requires evaluating them against the specific record volumes, query distributions, and latency budgets the agent encounters. Two evaluation metrics answer different questions here. Recall against an exact scan measures algorithmic fidelity to the mathematical distance metric, whereas end-to-end task success measures whether the retrieved records contain the requisite causal evidence to resolve the agent’s objective.
The filtering hazard from lexical search (section 6.5.3) returns here in sharper form, because scope filters present greater friction on a graph index than on inverted postings lists. In lexical retrieval, intersecting a postings list with an eligibility bitset prunes unauthorized documents without altering how the remaining documents are traversed. In an HNSW graph, restricting search during traversal (pre-filtering) forces the beam to step exclusively onto eligible nodes. If a tenant boundary or file path mask isolates regions of the graph, the greedy walk stalls at a local minimum when all outgoing links lead to masked nodes. The search terminates prematurely and returns incomplete results, even when highly relevant eligible nodes exist just beyond the masked barrier. Conversely, filtering after an unconstrained search (post-filtering) risks returning an empty set whenever the top-\(\RetrievalCutoffCount\) candidates fall outside the authorized scope. Systems escape the dilemma in one of three ways (figure 5). They partition the index into scope-isolated subgraphs, seed extra entry points inside the authorized region, or fall back to an exact scan when the filter is selective enough that the measured full request meets the budget, using the floor in notebook 6.2 as an initial feasibility screen.
6.6.3 Rank fusion and reranking
Running both lexical search and dense retrieval covers each method’s blind spots, but combining their outputs naively fails in two ways: adding unbounded BM25 scores directly to cosine similarities in \([-1, 1]\) skews the combined order toward whichever scale is larger, and deduplicating hits by file path alone merges a stale r17 span with its patched r18 counterpart. Production systems that combine multiple candidate-generation mechanisms through hybrid retrieval must therefore establish unambiguous candidate identity based on tenant scope, source path, commit or version identifier, and span coordinates before merging lists. Strict identity resolution ensures that an r17 passage never erroneously merges with its modified r18 counterpart, and that identical code in another tenant is never treated as authorized local evidence.
Because lexical scores and dense similarity scores reside on non-comparable scales, directly normalizing or adding raw scores introduces calibration instability. Reciprocal rank fusion (RRF) bypasses score calibration by combining ranked lists based solely on candidate ordinal positions (Cormack et al. 2009). Let \(\FusionInputList_i\) denote the list returned by method \(\RetrievalMethodIndex\), and let \(\FusionInputRank_i(\FusionCandidate)\) represent the 1-based rank of candidate \(\FusionCandidate\) within that list. For a positive smoothing parameter \(\RankFusionSmoothingConstant\), the truncated RRF score is defined as:
\[ \operatorname{RRF}(\FusionCandidate) = \sum_{i:\,\FusionCandidate\in \FusionInputList_i} \frac{1}{\RankFusionSmoothingConstant + \FusionInputRank_i(\FusionCandidate)}. \tag{3}\]
A candidate absent from a given list contributes zero from that source. Increasing \(\RankFusionSmoothingConstant\) compresses the score differential between adjacent ranks without making the method entirely parameter-free;6 the runtime must also define an explicit tie-breaking convention and configure candidate cutoff depths for each retrieval path.
6 RRF score monotonicity: With fixed \(\RankFusionSmoothingConstant > 0\), moving an item from rank \(\FusionInputRank\) to \(\PromotedFusionInputRank < \FusionInputRank\) in one input list increases its contribution by \(1/(\RankFusionSmoothingConstant+\PromotedFusionInputRank)-1/(\RankFusionSmoothingConstant+\FusionInputRank)>0\) (Cormack et al. 2009). If its contributions from other lists do not decrease, its total score increases. This is a property of the item’s score, not a guarantee of improved final rank when other candidates also change, or of relevant evidence.
To see how RRF rewards consensus across divergent retrieval mechanisms, consider an illustrative repair query evaluated on the authorized r18 snapshot. Let A be the return-and-notify implementation span, B the reproducer test, and C, D, and E three additional candidate records. Suppose lexical search produces the ranking B, A, D, while dense retrieval produces C, A, E. With the standard choice \(\RankFusionSmoothingConstant =\) 60, equation 3 assigns candidate A two second-place contributions, \(1/(60+2) + 1/(60+2)\), whereas candidate B receives only a single first-place contribution of \(1/(60+1)\). Summing every candidate’s contributions in table 6 puts candidate A at the top fused rank on consensus across both retrieval paths, even though neither individual retriever ranked it first.
| Candidate | Lexical rank | Dense rank | RRF score | Fused position |
|---|---|---|---|---|
| A | 2 | 2 | 0.03226 | 1 |
| B | 1 | — | 0.01639 | 2 |
| C | — | 1 | 0.01639 | 3 |
| D | 3 | — | 0.01587 | 4 |
| E | — | 3 | 0.01587 | 5 |
Dual consensus elevates candidate A for closer inspection, but agreement across two candidate generators remains an incomplete guarantee of relevance when both retrievers share systematic blind spots. To establish higher precision before staging evidence into the agent’s context window, systems employ a cross-encoder reranker (Nogueira and Cho 2019). Rather than scoring query and document independently, a cross-encoder runs the query and the candidate through the model together as one input, so every query token can attend to every candidate token. Because each score depends on a specific query and candidate pair, nothing can be computed before the query arrives, and this joint pass captures fine-grained token interactions at substantial query-time cost. A reranker can only reorder candidates already surfaced by upstream generators; it cannot retrieve missing records, and its score reflects structural and semantic resemblance rather than verified task applicability.
The substantial computational demand of this joint pass is why rerankers operate exclusively on short candidate pools. In a bi-encoder design, candidate vectors are computed offline, reducing query-time evaluation to a lightweight vector dot product. In a cross-encoder, query and candidate tokens must be processed jointly through the transformer layers, preventing offline precomputation. Computational cost scales with both candidate pool depth and token sequence length. For example, reranking a pool of 50 candidates of 300 tokens each against a 100-token query requires processing 20,000 tokens, a prefill load comparable to a substantial model call, spent entirely on ordering. Systems manage this latency budget by constraining candidate pool sizes, invoking rerankers conditionally based on query ambiguity, or executing reranking asynchronously off the interactive path. The complete hybrid pipeline therefore narrows as it proceeds (figure 6). Two candidate generators feed a fusion step that needs only ranks, the costly reranker sees only the short fused pool, and the runtime stages a small labeled set within the payload budget.
Once reranked, top-ranked candidates pass into the staging pipeline (section 6.3.3), where their provenance and authority are verified before injection into the agent’s context payload. Even an optimally ranked evidence set, however, provides bounded guarantees. Retrieving the r18 implementation and a passing reproducer confirms local syntax and isolated test execution, but it cannot prove that all concurrent caller paths remain race-free. Validating broader system properties requires corroborating records, such as runtime execution traces and multi-threaded test outcomes, that no single ranked list assembles on its own.
6.7 Multi-Hop Retrieval
A single ranked passage often identifies an initial point of entry without delivering all the evidence an agent needs to make an informed engineering decision. In the connection-pool repair, the core implementation, the waiter-notification test, and the recorded test execution logs answer entirely distinct questions. Examining the pool implementation in isolation cannot reveal which execution paths the test actually exercised. Conversely, inspecting a passing test log leaves unanswered whether the change preserved wider public interface guarantees. Multi-hop retrieval addresses this gap by traversing explicit relationships between evidence items, assembling an explanatory chain that no individual passage’s retrieval score could justify alone.
Implementing multi-hop retrieval does not necessarily demand a dedicated graph database. An agent can inspect a retrieved passage, extract an unresolved reference, and issue a targeted tool call to fetch the next source artifact. Alternatively, an execution runtime can resolve known references ahead of time before invoking the model. Precomputing and maintaining explicit entity relationships pays off only when downstream queries reuse those links frequently enough to amortize the parsing and indexing overhead.
6.7.1 Evidence paths
Handing the model separate snippets from r17 test logs, tests/test_pool.py, and src/pool.py without recording how they connect leaves the agent to guess which test exercised which method and under which revision. An explicit evidence path instead chains those records together: starting at the recorded failure of test_waiter_notified_on_return under revision r17 (scoped by its test revision and runtime environment), the traversal traces from the test assertion in tests/test_pool.py directly into the pool operations exercised by the waiter-return scenario in src/pool.py, and then compares those source regions against the candidate patch in revision r18 and its corresponding reproducer execution. Public interface contracts and unrelated callers remain isolated for subsequent targeted queries.
The edges along this path carry distinct semantics: a link from a test run to a commit hash binds an outcome to an exact observed artifact, whereas a static symbol reference in test code points only to an implementation entity awaiting inspection and a diff between revisions isolates textual modifications between snapshots. A robust retrieval payload preserves these labeled edge semantics alongside precise source locations and commit hashes. The runtime must also expose unresolved or broken links, such as a missing test log, an ambiguous dynamic dispatch target, or a traversal halted by a token budget. A static evidence path highlights plausible candidate root causes, but it cannot prove that those specific statements executed during the failing run, nor does it guarantee that all contributing dependencies were discovered.
6.7.2 Maintained code graphs
Following every file that merely imports src/pool.py floods a multi-hop search with dozens of irrelevant modules, whereas a flat symbol table cannot trace how a value mutated in one method reaches a waiter queue in another. To support selective reasoning over software repositories, a code property graph unifies abstract syntax trees, control-flow graphs, and program-dependence graphs into a single directed graph of program entities connected by typed edges (Yamaguchi et al. 2014). The edge types most relevant to software agents include syntactic containment and declaration, call edges connecting call sites to function targets, data-dependence edges tracking value definitions to their uses, type inheritance, and module-level imports.
Edge typing is what makes multi-hop graph traversal selective rather than combinatorial. In the connection-pool repair, restricting a search to invocation and mutation edges guides the traversal directly from test_waiter_notified_on_return to the pool’s resource-return method, and onward to the waiter queue that the method mutates, skipping the dozens of unrelated files that merely import the pool module. The entry point for such a traversal, the seed node, can be resolved via an exact symbol lookup, an initial ranked passage retrieval, or an explicit file and line coordinate from an execution trace.
However, an edge is only as reliable as its underlying extraction mechanism. Lexical parsing reliably identifies declared syntax; resolving cross-file call targets requires complete type information and build configuration; dynamic execution traces observe only the concrete paths taken during a specific invocation. Code graphs must therefore track provenance on every edge, ensuring the runtime never presents a statically inferred call as an observed runtime event. Furthermore, maintaining these graphs introduces ongoing invalidation overhead as the codebase evolves. A local edit to a method signature might invalidate caller graphs and dependent summaries across multiple repositories, whereas modifying an internal comment leaves structural edges unchanged. When source artifacts shift, any relationship whose underlying evidence has changed must be pruned or marked stale according to the update contracts established in section 6.9.
6.7.3 Bounded expansion
Unconstrained expansion from a seed node quickly pulls in vastly more context than a downstream language model can process or attend to effectively. Traversal routines require strict operational guards: filtering permitted edge types, restricting traversal direction, capping maximum search depth, and bounding the total number of visited nodes. Tracking visited entity identifiers is essential to prevent cyclic loops from triggering infinite expansion. Even with structural bounds, context packing limits remain binding because a small handful of large code or documentation nodes can easily overrun the prompt budget.
Within these operational boundaries, the runtime can prioritize candidate nodes using semantic relevance, edge type affinities, or graph-centrality algorithms like Personalized PageRank (Page et al. 1999), which concentrates random-walk probability around the initial seed nodes. However, applying a naive score threshold across candidate nodes risks fragmenting the evidence chain. Preserving a coherent explanation often requires retaining an intermediate node with a lower individual query score simply to maintain topological connectivity between the seed and high-value leaf evidence, while compensating by pruning non-essential nodes elsewhere.
↪ The personalized PageRank update and its unique fixed point are developed in PageRank symbol graphing for repository maps.
One more level of depth turns a comfortable fit into an overflow.
Depth, more than node size, decides whether a neighborhood fits the context budget, because every hop multiplies the expansion frontier by the branching factor. Notebook 6.3 counts an exact tree to show how quickly one extra level turns a comfortable payload into an overflow.
Napkin Math 6.3: Graph expansion and the evidence budget
Variables: Suppose the neighborhood is a tree with exactly 3 children per internal node, explored through depth 3, with the seed at depth zero and no repeated nodes. Each complete node record occupies 180 serialized tokens, including its local provenance. Reserve 100 tokens total for edge descriptions and the result envelope. All counts are hypothetical fixed serialization sizes.
Math: Counting the seed and all levels gives the geometric sum \(1 + 3 + 9 + 27 = (3^{4}-1)/(3-1) =\) 40 nodes, in general \((\text{children}^{\text{depth}+1}-1)/(\text{children}-1)\). Staging them requires 40 \(\times\) 180 \(+\) 100 \(=\) 7,300 tokens, exceeding the allowance. With the same envelope reservation, the maximum number of complete equal-sized nodes is \(\lfloor(6{,}144 - 100)/180\rfloor =\) 33.
Stopping one level earlier, at depth 2, stages all 13 nodes in 2,440 tokens.
Systems insight: Depth dominates traversal cost because every additional hop multiplies the expansion frontier by the graph’s branching factor. A single extra level separates an evidence payload that comfortably fits the context window from one that overflows the allocation. Traversal engines must bound depth and filter edge types before ranking nodes; within those limits, scoring should prioritize nodes that preserve path connectivity rather than greedily selecting disconnected high-scoring fragments.
Production code graphs contain clustered communities, cycles, and heavily skewed degree distributions. Consequently, calculating reachable nodes by raising an average branching factor to a traversal depth typically overestimates distinct reachable entities while underestimating the local search work required to evaluate candidate edges. When an evidence path exceeds the staging budget, the runtime must either narrow the query scope, return a truncated subgraph accompanied by an explicit continuation cursor, or defer downstream expansion to subsequent interactive agent turns. Under the absence rule, any traversal halted by an engineering limit must be explicitly reported as partial rather than exhausted.
6.7.4 Community summaries as derived memory
Not every agent question resolves to a single evidence path. High-level architectural queries often span entire subsystems, for example how connection pooling, HTTP request dispatching, and transaction lifecycles interact across a service framework. Graph-based retrieval-augmented generation (GraphRAG) addresses these broader questions by constructing an entity knowledge graph and precomputing hierarchical summaries over densely connected subgraphs, or communities (Edge et al. 2024). Unsupervised community detection7 clusters related nodes based on network topology. However, whether a detected topological cluster corresponds to a true architectural boundary, and whether its generated natural-language summary remains technically accurate, are separate verification concerns.
7 Community Detection: GraphRAG partitions its entity graph using the Leiden algorithm, which refines modularity-based clustering to ensure that every detected community is well-separated and internally connected (Traag et al. 2019). Modularity optimization rewards groups with higher internal edge density than an equivalent random network. A detected community reflects entity co-occurrence density within the extracted corpora; whether that topological cluster corresponds to a logical module boundary recognized by system maintainers must be verified against actual source architecture.
A derived summary amortizes token costs by synthesizing scattered facts into a concise artifact, but it remains a lossy, secondary representation. Every generated summary must retain bidirectional links to its source evidence, record the precise artifact revisions and operating parameters it describes, and inherit the most restrictive access label among its underlying inputs, so that a summary built partly from records restricted to one tenant is itself restricted to that tenant. Detailed execution plans should inspect the authoritative underlying records; the summary serves primarily as an indexed navigational map.
↪ How labels propagate through summaries and other transformations under an information-flow policy is developed in Label propagation through transformations.
For instance, an automated repair summary might record that revision r18 passed test_waiter_notified_on_return under a specific thread-concurrency configuration. Because an observation is scoped to its tested configuration, this fact cannot be generalized into an assertion that “the connection pool is thread-safe.” Moreover, precomputed summaries incur ongoing invalidation debt. Persisting an explicit dependency manifest between source files, detected communities, and generated summaries turns invalidation into a traversal of recorded dependencies rather than a guess. Any code modification flags all dependent summaries (and any higher-level rollups derived from them) as dirty. The runtime can continue to serve a dirty summary as a labeled historical snapshot until an offline job or on-demand trigger recompiles or invalidates it.
Checkpoint 6.2: Choosing and bounding related evidence
Apply these retrieval strategies to the running connection-pool repair.
Deciding whether to retain a detailed path explanation or a high-level subsystem summary is a write-policy decision rather than a search mechanic. That policy dictates the fidelity, staleness, and cost of the evidence that every subsequent agent session can retrieve.
6.8 The Memory Write Path
Retrieval can return only what the system has retained. An assistant that carries the directive “no meetings before 10:00” strictly within its current context window loses that constraint the moment the session terminates. Persisting the preference into long-term storage solves immediate conversational volatility, but it introduces the consistency challenge previewed in section 6.2. When the user later moves the boundary to 11:00, the runtime must ensure the earlier record stops governing new scheduling decisions without corrupting the historical audit trail.
The distinction between authoritative sources and derived records governs writes just as it governed reads (principle 6). A user’s explicit directive provides direct evidence of an intent within a specific operational scope; an agent’s internal paraphrase constitutes a lossy derived representation; and an automated rationale explaining why the user dislikes morning meetings is an ungrounded secondary inference. Storing all three artifacts as interchangeable assertions flattens evidentiary weight, depriving downstream retrieval pipelines of the ability to distinguish verified user intent from speculative model summaries.
Definition 6.2: Memory write policy
A memory write policy is the runtime rule governing which proposed records enter durable storage, what claims and operational scopes they carry, and how the system subsequently corrects, supersedes, revalidates, expires, or deletes those records and their downstream derivations.
- Significance: Every admitted record becomes a candidate for retrieval in subsequent agent sessions. An unverified lesson admitted into storage can degrade the execution accuracy of every future task that retrieves it. The write path provides the most economical barrier against memory pollution because admission checks execute once per write rather than amortizing filtering costs across thousands of subsequent retrieval queries.
- Distinction: Storage retention preserves raw bytes in a database or index. The memory write policy governs the operational authority of those bytes, defining what claims an entry can justify and when it must stop influencing execution decisions.
- Common pitfall: Deduplicating writes based purely on embedding similarity, which erroneously discards near-identical updates (such as a revised meeting time or flipped boolean flag) as redundant duplicates.
6.8.1 Record scope and evidence
A user says “no meetings before 10:00” while looking at their team calendar in New York, and the agent stores the bare rule "no meetings before 10:00". Next month, the agent rejects a 9:30 London client call on the user’s travel calendar because the stored record never captured which calendar, which time zone, or which consent boundary authorized the write. Every candidate memory record requires a concrete provenance tuple: an identifiable owner, an intended operational role, a bounded applicability scope, and verifiable backing evidence. In addition, the runtime must enforce explicit consent boundaries: permission to inspect user messages during active reasoning does not grant permission to commit those details into durable storage.
Software repair trajectories generate a different class of evidence. For example, test execution records showing a failure at revision r17 and a pass at revision r18 represent immutable historical observations, but neither result justifies an unconditioned assertion about the codebase. A synthesized rule such as “inspect the return path when a waiter remains blocked” represents a heuristic hypothesis derived from that sequence, not a proven invariant. Table 7 formalizes these distinctions by categorizing how different memory records bind later execution.
| Record kind | Evidence retained | Limit on later use |
|---|---|---|
| Explicit preference | User statement, identity, scope, and statement version | Applies within that scope until revised or withdrawn |
| Scoped observation | Tool result, checked revision, command, and relevant execution conditions | Reports the observed case, not all later states |
| Generated lesson or hypothesis | Supporting observations, derivation, unresolved assumptions, and contrary evidence | Suggests an investigation; does not establish a new fact or grant authority |
| Episode summary or continuation note | Task identifier and links to retained events and artifacts | Carries selected history or unfinished work; does not replace the underlying evidence |
These record kinds impose distinct demands across different operational archetypes. The research agent and support agent stress the memory write pipeline in different ways than the repair agent does.
Lighthouse 6.1: Persistent memory by archetype
| Lighthouse | Dominant durable record | Source of record | Binding hazard | Write-policy emphasis |
|---|---|---|---|---|
| Repair agent | Test observations and progress notes tied to revisions | The repository at a source generation | Its own edits make indexed copies stale | Tag every observation with its revision; invalidate on the agent’s own writes |
| Research agent | Notes and summaries distilled from fetched pages | Each external page as fetched, with its time | Untrusted text becomes a confident lesson through summarization | Admit distilled claims as hypotheses with links to the fetched pages |
| Support agent | Customer history, preferences, and answers about policy | The customer record and the published policy documents | A superseded preference or ungrounded policy answer is reused | Supersede by explicit replacement; propagate deletion to every derived copy |
Systems insight: The repair agent’s memory hazard comes from its own writes, the research agent’s from other people’s text, and the support agent’s from time. One retrieval contract serves all three, and the write policy is where they diverge.
6.8.2 Admission before deduplication
If a user revises a preference from “no meetings before 10:00” to “no meetings before 11:00” and the write path deduplicates candidates by cosine similarity first, the runtime discards the 11:00 update as a near-identical repeat of the 10:00 record. Even when an architecture allows the language model to manage its active context by paging memory entries explicitly (Packer et al. 2023), context paging controls only working set occupancy; durable admission remains the exclusive responsibility of the storage runtime. The admission gate validates write permissions, confirms that the target store allows persistent retention for the active session, classifies the record type, and verifies that attached evidence satisfies the schema before any deduplication check runs. Structural schema validation checks required fields such as timestamps and provenance identifiers.
Semantic fidelity, the requirement that the proposed record asserts nothing absent from the raw transcript, needs a check of its own, and that check is a verifier with error rates like any other. A deterministic check can validate a constrained structured input against the proposed record’s owner, relation, value, and scope. Finding “11:00” in free-form text establishes only its occurrence; “11:00 applies only on Fridays” does not support an unrestricted scheduling preference. For free-text summaries, a calibrated model-based judge is one fallible fidelity check, and its false acceptance rate (How base rates limit check precision) measures how often unsupported claims pass that check into durable storage, where every later session can retrieve them. Generating a summary and establishing that it is faithful are different events, which is the verification asymmetry (principle 3) applied to memory admission. Sensitive data (such as credentials and private identifiers) demands strict classification and scrubbing policies; regular expression filters miss unstructured disclosures that match no standard secret pattern. When an agent proposes an interpretive conclusion lacking direct observational backing, the admission gate must either reject the candidate or downgrade it to an explicitly tagged hypothesis, preventing it from masquerading as a validated preference or concrete observation.
Only after passing admission validation does the runtime evaluate whether the candidate record inserts a new entry, updates an existing record, or duplicates existing knowledge. Vector similarity in an embedding space is useful for candidate retrieval, but it cannot resolve write semantics. Relying on distance thresholds for deduplication would discard the 11:00 update as an uninformative repeat, quietly dropping the user’s explicit correction.
When an admitted record targets an existing entity under an identical scope, the runtime executes supersession. The runtime creates a newly versioned record and marks the prior entry as superseded. This terminates the prior record’s eligibility for active decision-making while preserving it in historical logs for auditing and provenance tracing. When scopes differ (for example, if the 11:00 restriction applies only to Fridays), both records remain valid within their respective domains. When scopes overlap ambiguously, the runtime must flag an unresolved conflict or prompt the user for clarification; heuristically synthesizing conflicting records into a fuzzy compromise produces brittle, ungrounded behavior. Systems must also distinguish an in-place correction from a true state transition. Fixing a transcription error that corrupted “10:00” repairs the fidelity of an existing record, whereas accepting an 11:00 update documents an authentic change in preference.
Concurrent updates demand explicit coordination primitives at the storage layer. A proposed supersession must carry the base version identifier against which it was generated. The store then evaluates and applies the update atomically through a compare-and-swap or conditional write, the same optimistic validation that context engineering applied to tool preconditions, closing the race inherent in separate read and write phases. Optimistic validation suits memory writes particularly well. Two sessions seldom revise the same preference concurrently, so conflicts are rare, and a model call lasting several seconds makes a pessimistic lock impractical to hold across the invocation that proposes the write. When a collision does occur, the runtime must abort the write, reload the latest state, and re-evaluate the update against an explicit conflict resolution policy. Handing the conflict back to the model to blend the two states without transactional guarantees invites silent corruption.
↩︎ Optimistic validation, which checks at commit that the state a decision read is unchanged and aborts otherwise, is established in Detecting change and bounding uncertainty.
6.8.3 Recorded observations and derived lessons
If an agent waits for a reflective summary and vector embedding to finish before recording a tool’s raw output, a timeout or crash in the summarization model loses the hard evidence of what the tool actually did. When an agent executes an action, the runtime immediately writes the raw observation (the execution context, task ID, source revision, tool parameters, and raw output status) to durable storage. Only after this initial write does the runtime schedule background pipelines for summarization, embedding generation, and heuristic reflection. This separation guarantees that hard evidence persists even if downstream inference fails or crashes, while avoiding costly synchronous model calls on every execution step. Generating reflective summaries has demonstrated substantial empirical gains in autonomous error recovery (Shinn et al. 2023); nonetheless, the resulting verbal reflections must enter the store strictly as generated hypotheses (table 7), maintaining explicit foreign-key links to the raw observations from which they were induced.
Write acknowledgments must explicitly report the durability boundary achieved. Systems must distinguish among three distinct guarantees: buffered in memory (queued in an ephemeral local ring buffer), committed to durable storage (flushed to non-volatile disk or replicated across storage nodes under the durability contract), and indexed for search (visible to vector and keyword retrieval engines). Merely enqueuing an event into an in-memory worker queue provides zero crash durability. If a task requires strict persistence guarantees before taking non-reversible external actions, the runtime must block on storage confirmation rather than proceeding optimistically. In addition, background indexing and reflection pipelines consume significant accelerator cycles and storage I/O; system schedulers must explicitly account for these background workloads to prevent asynchronous memory indexing from starving user-facing interactive inference.
6.8.4 Revalidation, expiration, and deletion
An unchecked scheduling rule retrieved across 30 runs without complaint is thirty times reused, not thirty times verified. A retained record changes status as its supporting evidence and operational context evolve: the superseded 10:00 preference and the r17 test failure both remain valid historical records while losing eligibility for current decisions, and retaining historical snapshots remains a deliberate architectural policy choice.
Revalidation refreshes the empirical support for an existing record. For instance, asking the user to confirm that the 11:00 scheduling boundary remains active provides authoritative fresh evidence. In contrast, repeatedly retrieving an entry across dozens of successful runs indicates frequent usage, not revalidation. Confusing usage frequency with validity is dangerous, because an unchecked error that is retrieved often is simply reused often, and each retrieval adds no evidence. Consequently, storage schemas must maintain distinct timestamps for record creation, last access, and last authoritative confirmation. Similarly, revalidating an automated diagnosis or heuristic rule derived from revision r18 requires evaluating it against the current source code tree and active test environment, rather than treating age-based decay as a proxy for correctness.
Expiration revokes a record’s eligibility for decision-making once an expiration timestamp passes or a defined system condition is triggered. An expired temporary directive, such as an out-of-office scheduling window, must not govern subsequent actions without explicit reconfirmation. Some memory systems rank records by similarity multiplied by a recency factor that shrinks with age. Penalizing an expired record this way is inadequate, because if a query has few close semantic matches, an expired record with a penalized score can still surface in the top-\(\RetrievalCutoffCount\) retrieval set and contaminate the prompt. Robust write paths enforce hard filtering, partitioning or tagging expired records so that operational retrieval filters exclude them unconditionally while retaining the payload for compliance auditing.
Records built from a user’s own data carry an obligation that records about source code do not, because the person they describe has a say in whether and how long they persist. Permission to read a message during reasoning does not grant permission to retain it (section 6.8.1), so each admitted user record should carry the consent under which it was admitted and a retention period after which it must be deleted rather than merely excluded from retrieval. A store can honor a withdrawal of consent only if it can list every record that describes the user, derived summaries included, together with the consent recorded for each. Withdrawal of consent, an elapsed retention period, and an explicit deletion request all start the same deletion procedure.
Deletion addresses the physical and logical lifecycle of the stored data. When a user revokes consent or asks to delete a preference, purging the primary database row is only the initial step. Stale representations frequently linger in secondary indexes, dense vector stores, consolidated episodic summaries, key-value caches, and pre-staged prompt templates managed by the runtime. The key-value case is easy to miss, because a cached prefix that contains the deleted preference still matches any request that repeats those tokens, and a prefix match certifies identical tokens, not current facts. The runtime must therefore evict that prefix or change the prompt so it no longer matches. A comprehensive deletion procedure must identify every downstream derivative, revoke its retrieval eligibility immediately, and schedule background reclamation or re-indexing under the governing data retention policy. To bridge the latency between request receipt and asynchronous garbage collection, systems write the storage counterpart of the marker that context invalidation places in a prompt. This tombstone8 is a durable exclusion record that filters the entity out of all active query paths before physical purging completes.
8 Death Certificates: Distributed replicated databases encountered this challenge decades ago. If a replica silently deletes an entry, a delayed update arriving from a partitioned peer appears to be fresh data and resurrects the deleted record. Demers et al. (1987) resolved this in epidemic replication by writing an explicit “death certificate” that propagates through the cluster and supersedes older versions. In an agent memory architecture, lagging asynchronous indexers, pipeline queues, and restored snapshots function just like stale replicas, making durable tombstone markers necessary prior to physical deletion.
↩︎ Why a prefix-cache hit verifies identical tokens rather than fresh evidence is established in Prefix compatibility.
↩︎ Tombstones as masking records that log-structured storage engines keep until compaction, and their contrast with an advisory notice in a prompt, are established in Removing, replacing, or appending.
A deletion receipt must specify the exact boundary of guarantees achieved. Immutable cold backups, out-of-band external audit logs, and in-flight API payloads dispatched to third-party model providers lie outside the synchronous deletion perimeter. Deleting a record from runtime memory cannot retract a prompt token that an external foundation model has already processed, nor can it un-schedule a calendar invite already sent across an enterprise network. What the runtime can and must guarantee is that every internal index, cache, and prompt assembly buffer within its trust domain immediately ceases to use the deleted entity in future reasoning cycles.
6.8.5 Consolidation
After a dozen debugging sessions on an asynchronous runtime, retrieving forty separate stack traces and raw test logs overflows the retrieval budget before the model sees the pattern connecting them. Consolidation compresses clusters of related, fine-grained records into structured, high-level representations optimized for future retrieval, such as an architectural summary documenting which notification paths were evaluated, which revisions broke invariants, and which hypotheses remain open. Autonomous agent architectures frequently employ background workers to synthesize episodic observations into higher-level reflections (Park et al. 2023). From a systems perspective, every consolidated reflection is a generated lesson (table 7). Clustering records by embedding proximity helps identify candidate groups for consolidation, but vector similarity alone cannot establish causal relationships; verifying that two failures share an underlying defect requires structural evidence that semantic proximity cannot supply.
When generating consolidated records, the write pipeline must preserve provenance graphs, explicitly recording references to the constituent raw records, boundary conditions, and any observed counterexamples. Synthesizing multiple successful execution traces into an unconditioned, global procedure risks overgeneralizing domain-specific behavior. Retaining the underlying source observations alongside the consolidated abstraction also remains a deliberate architectural decision. Consolidated summaries minimize prompt tokens during inference, but stripping the raw logs removes the granular execution traces necessary for deep auditing and subsequent re-indexing.
6.8.6 Self-reinforcing errors
When an unverified hypothesis enters durable memory, subsequent summarization cycles risk treating the stored conjecture as an established premise, echoing and amplifying the error across successive generations of context. Under formal evidentiary rules, repeated retrieval and re-summarization provide zero independent validation. A faulty diagnostic guess that is copied into an episode summary, absorbed into a weekly milestone report, and ultimately consolidated into a cross-project heuristic still rests entirely on the original faulty inference. Memory poisoning is the persistence of an unverified or withdrawn claim through the records derived from it. To prevent it, the storage engine must maintain rigorous dependency provenance across all derived artifacts. When an operator or verification pass invalidates a poisoned record, the invalidation must cascade through the entire dependency graph, retracting or marking as suspect every downstream summary and derived lesson. Merely down-ranking or tombstoning the root record is insufficient if derivative summaries continue circulating through retrieval indexes. Finally, even a fully validated, un-poisoned lesson functions merely as a candidate action suggestion; the execution engine must still enforce strict runtime authorization policies and environmental preconditions whenever an agent attempts to act on retrieved memories.
Checkpoint 6.3: Following a preference through its lifecycle
A user changes “no meetings before 10:00” to “no meetings before 11:00” for the same calendar and later requests deletion of the preference. An index and a session summary still contain the original value.
The memory write path establishes what a stored record claims, what evidence supports it, and when its operational validity ends. Those decisions reach the agent, however, only through derived indexes and caches that are rebuilt after the store changes, and until a lagging index catches up it can still answer with the record the write path just retired.
6.9 Storage Invalidation
The connection-pool repair has reached revision r18, yet a subsequent search can still return an excerpt of src/pool.py indexed at r17. Consider how a single stale read unravels an otherwise systematic debugging trajectory:
- At turn 12, the agent edits the return path in
src/pool.py, and the workspace edit tool confirms the updated file atr18. - At turn 13, a search for the notification logic retrieves the
r17chunk, which still contains the buggy line replaced in the previous turn, without a version label. - At turn 14, the model infers that its earlier modification was lost and reissues the edit. The edit tool rejects the request because the target snippet no longer exists in the current file.
- At turn 15, the model confronts conflicting signals: a confirmed write, an excerpt contradicting that write, and a failed re-edit. It concludes that the workspace filesystem is corrupted and begins issuing speculative, wide-ranging edits. Each action burns context tokens and tool budget while driving the repository further from a reviewed state.
The unlabeled stale read initiates this failure by presenting an accurate historical excerpt as current state. The conflicting evidence does not establish filesystem corruption; a direct read of the current source could expose the mismatch. Model reasoning cannot reliably compensate for a retrieval layer that conceals which version its evidence describes, and each turn the trace wasted lengthens the horizon over which per-turn errors compound (equation 1.1). Maintaining a persistent index therefore forces a clean separation between two operations that an ephemeral staged prompt naturally couples: withholding obsolete records and generating their replacements.
Definition 6.3: Storage invalidation
Storage invalidation is the exclusion of a derived record (an index entry, vector, summary, or cached result) from current-state retrieval once a relevant change to its source makes it inapplicable, independent of when a replacement is built.
- Significance: Coordinating exclusion with the source commit prevents known-obsolete entries from remaining eligible while their replacements are built. Notebook 6.4 compares the additional metadata and indexing work, separately from the common durable commit and coordination costs. In the turn-by-turn trace that opens this section, one unlabeled stale read cost three turns of the repair’s budget.
- Distinction: Rebuilding synthesizes a replacement representation, whereas invalidation merely suppresses the obsolete one. This ensures that any query arriving during the rebuild window receives either an authoritative direct read or an explicit incomplete result rather than stale data.
- Common pitfall: Tracking staleness with an ephemeral dirty flag that clears automatically when a background job finishes. If an uncoordinated indexing worker completes late or a retrieval gateway restarts without durable tombstone state, obsolete entries can be erroneously readmitted.
6.9.1 Source generations
Relying on filesystem modification timestamps (mtime) to detect stale index entries fails when clock skew, branch switches, or sub-millisecond edits leave two revisions with indistinguishable timestamps. To guarantee freshness, an index entry must explicitly record the source generation from which it was derived: a monotonic version identity defined by the storage system’s write contract. In the connection-pool repair, r17 and r18 denote successive repository states. Once the runtime establishes r18 as the active generation, any query seeking current code must systematically discard entries tagged with r17.
Deciding which derived records an edit affects is the dependency tracking that context invalidation applied to staged observations, now applied to records that persist in the store and its indexes. What is new at this layer is that generations make the tracking durable across sessions, and that some derived records cannot be patched in place. Data dependencies often span beyond individual files. A raw code excerpt depends solely on its source file revision; a call-graph edge depends on multiple source files alongside the static-analysis configuration; an episodic summary depends on the tool outputs and diagnostic logs it consolidates. When an underlying artifact changes, the runtime must invalidate all affected downstream records while keeping unrelated entries intact. If the dependency graph is coarse or incomplete, the runtime must conservatively widen the invalidation boundary or explicitly report retrieval uncertainty. A missing dependency link must never be treated as proof of validity.
↩︎ Tracking which claims depend on which observations, and propagating invalidation through that record, is established in Tracking claim dependencies.
From a systems standpoint, every retrieval index is a materialized view over base data, a problem relational database management systems have addressed for decades. Classical incremental view maintenance computes updates to a view algebraically from delta changes in base relations, bypassing the need to re-evaluate the full query (Blakeley et al. 1986; Gupta and Mumick 1995). Unstructured retrieval indexes, however, resist algebraic delta maintenance. Under fixed-size chunking schemes, inserting even two lines near the beginning of a source file shifts the token boundaries of every subsequent chunk. Because deep neural embedding models are non-linear, an updated vector cannot be synthesized from a vector subtraction and a text diff. Consequently, changed text requires discarding existing entries and running end-to-end forward passes to re-embed the new chunks. Practical retrieval architectures therefore decouple invalidation, a metadata exclusion coordinated with the source commit, from index rebuilding, which consumes substantial compute and network latency.
Beyond source generations, an embedding record must also encode the model identifier, tokenization pipeline, and preprocessing hyperparameters that generated it. A valid source generation confirms only that the underlying text is up to date; it does not indicate whether the vector remains compatible with the active retrieval model and query encoder.
6.9.2 Source and index coordination
If the workspace commits r18 and publishes an asynchronous invalidation event on a message queue, a retrieval query arriving two milliseconds later can reach the index gateway before the queue message does and receive r17 as current state. Avoiding that race requires a coordinated protocol among the storage coordinator, the indexing pipeline, and the retrieval gateway. This protocol assumes that the agent runtime governs workspace modifications, that the retrieval gateway can query an authoritative source generation along with its content, and that writes, index publications, and query admission share a coordination boundary, such as an atomic database transaction, a conditional write to a strongly consistent store whose replicas agree on a single commit order, or a local mutex. During an in-flight write, the gateway either holds queries within a tight latency deadline or marks the affected file scope as temporarily unavailable. A message queue or publish-subscribe broker alone cannot enforce these properties, because delivering a message is a separate event from committing the write it announces. The coordination sequence orchestrates a source modification while a straggling index worker remains active:
- The source coordinator commits the patch as generation
r18and atomically updates the active generation watermark for admission checks. Here a watermark is a position marker, the highest generation the gateway treats as current, not one of the compaction thresholds of context engineering. This prevents a visibility split where newly committed code is readable from disk while an out-of-band index registry continues to treatr17as current. - A subsequent query for
src/pool.pyretrieves candidate vectors derived fromr17from the background index. The retrieval gateway checks their embedded generation tag against the active watermark (r18) and suppresses them. This exclusion signals index lag rather than a missing file or a failed edit. - An indexing job started prior to the commit finishes late. During index publication, the worker checks its captured generation within the coordination boundary. Recognizing that generation
r18has superseded its input, the coordinator discards the stale output or redirects it to an archival store. - A fresh worker generates replacement vectors from an
r18snapshot. It publishes them conditionally, committing the batch only if the workspace generation and index configuration remain unchanged throughout the indexing window. - Inbound queries continuously evaluate candidate generations against the active watermark. Publishing
r18records never reactivates olderr17entries, and background garbage collectors reclaim retired vectors on an independent schedule.
Publication validation and index installation must occur as a single atomic operation, because checking generation validity first and writing later introduces a time-of-check to time-of-use (TOCTOU) race condition that allows concurrent edits to invalidate the payload. In-memory and durable tombstones record excluded generations while background workers rebuild representations. Because query admission enforces generation checks on every lookup, old candidates remain excluded even if temporary dirty flags clear prematurely. Similarly, deleting a source file installs a versioned tombstone, preventing delayed workers from accidentally resurrecting an obsolete record from an earlier snapshot.
Source generations allow the exclusion policy to be expressed in a compact, interval-based form. Each derived entry \(\DerivedMemoryEntry\) carries a valid lifetime \([\MemoryEntryBirthGeneration(\DerivedMemoryEntry), \MemoryEntryDeathGeneration(\DerivedMemoryEntry))\), where \(\MemoryEntryDeathGeneration(\DerivedMemoryEntry)\) remains open until a subsequent edit to that source scope closes the interval. A query evaluating workspace generation \(\QueryWorkspaceGeneration\) admits candidate entry \(\DerivedMemoryEntry\) if and only if
\[ \text{IsValid}(\DerivedMemoryEntry, \QueryWorkspaceGeneration) = \big(\MemoryEntryBirthGeneration(\DerivedMemoryEntry) \le \QueryWorkspaceGeneration < \MemoryEntryDeathGeneration(\DerivedMemoryEntry)\big). \tag{4}\]
For current-state execution, the runtime sets \(\QueryWorkspaceGeneration\) to the active workspace generation. For historical diagnostics, such as an agent reviewing why an execution failed at revision r17, the query sets \(\QueryWorkspaceGeneration\) to that historical revision. Subject to retention policies, equation 4 serves both use cases uniformly, preventing historical data from masquerading as current state.
Exclusion solves freshness, but it introduces an efficiency trade-off that compounds over time. Suppressed records continue to occupy memory. In an HNSW graph, tombstoned nodes remain embedded in their neighbors’ adjacency lists. Because greedy graph traversal continues to visit and evaluate these dead nodes before filtering them out at the admission boundary, a search with a fixed beam width explores fewer live items, degrading overall recall. To bound that loss, a background compaction process tracks the ratio of tombstoned records, \(\TombstonedRecordFraction = \lvert \TombstonedNodeSet\rvert/\lvert \IndexGraphNodeSet\rvert\). When this ratio crosses a tuned threshold, the system builds a compacted graph: it purges unreferenced records, recomputes neighbor connections among surviving nodes, rebuilds navigation entry points, and atomically swaps the compacted index into memory. This workflow adopts the compaction design of log-structured merge-trees (O’Neil et al. 1996), balancing query latency and retrieval recall against the compute cost of background rebuilds. This is compaction in the storage-engine sense, rewriting a structure without its dead entries, not the summarization that context compaction performs on a prompt.
This coordination contract must remain robust against system restarts and uncoordinated writers. When a retrieval gateway restarts, it must reconstruct its authoritative generation state from durable storage before accepting queries; an empty in-memory tombstone table must never be treated as evidence that the index is fresh. If external tools or developers modify files without routing through the runtime coordinator, filesystem watcher events may arrive out of order or be dropped. In response, the gateway must fall back to direct, version-validated reads against the filesystem. If it cannot verify whether an indexed chunk matches disk before its query deadline expires, it must flag the result envelope as unverified rather than returning potentially stale data.
Replicated retrieval topologies require explicit read-your-writes9 guarantees, ensuring that an agent always observes the outcomes of its own preceding actions (Terry et al. 1994). When an agent issues a search following an edit, the query carries the log sequence number (LSN) corresponding to that write. A replica whose replay position (the last log entry it has applied) lags that LSN must pause execution within a bounded wait window. If the replica does not catch up before the deadline elapses, the gateway either routes the request to an authoritative primary or returns an explicit partial-status response.
9 Session Guarantees: The Bayou project established four foundational client-centric guarantees for weakly consistent distributed storage: read your writes, monotonic reads, writes follow reads, and monotonic writes (Terry et al. 1994). An agentic system requires more than simple read-your-writes behavior. For example, if an agent reads r18 from an up-to-date replica and subsequently retrieves r17 from a lagging node on the next step, the system violates monotonic reads, and the agent’s view of workspace history moves backward.
6.9.3 Retrieval during index refresh
Excluding an obsolete candidate prevents an agent from consuming erroneous data, but it does not fulfill the retrieval layer’s contract to return actionable context. When invalidation suppresses a record, the gateway must return an honest assessment of available evidence. As outlined in table 9, a production retrieval layer can respond with one of three outcomes.
| Retrieval outcome | Evidence supplied | Remaining limitation |
|---|---|---|
| Current indexed result | Payload whose source generation and index configuration satisfy the request | Ranking and bounded search can still omit relevant records; completion status must reflect the search performed. |
| Authorized direct source read | A bounded source excerpt with its observed version and provenance | Direct access can be expensive, unavailable, or too narrow to answer the whole query. |
| Explicit incomplete result | Admissible partial evidence, or no payload, with an explanation of the unavailable scope | The caller lacks the requested evidence and must not infer that the source contains no match. |
The appropriate fallback depends on query structure. For an explicit target path like src/pool.py, the gateway can execute an authorized direct source read, returning the live r18 text while background embedding jobs run. Conversely, a broad semantic query, such as a search for all modules affected by a modified locking interface, cannot be answered by reading a single file. Answering it accurately requires either a refreshed semantic index or comprehensive static analysis across many files. If bounded direct reads cannot resolve the query within the execution budget, the gateway must return an explicit incomplete result. Artificially inflating candidate limits (such as expanding \(\RetrievalCutoffCount\) during top-\(\RetrievalCutoffCount\) nearest-neighbor retrieval) does not solve this problem, because an unindexed record is absent from the vector index and no search depth can retrieve it.
Where to place this maintenance overhead is an explicit design choice. Synchronous re-indexing moves parsing, chunking, and embedding directly onto the write path, guaranteeing that fresh representations exist before any subsequent tool executes. Background re-indexing acknowledges writes after the required durable source commit and coordinated exclusion, allowing tools to return before rebuilding finishes while relying on the gateway to manage queries during the refresh window. This architectural trade-off depends on workspace edit frequency and whether bounded direct reads can satisfy immediate downstream queries. As notebook 6.4 quantifies, their additional indexing and local metadata work can differ by several orders of magnitude, and they also differ in what a query during the rebuild sees (figure 7). Synchronous re-indexing never exposes that interval but stalls the write, unchecked background indexing serves r17 entries as current, and background indexing with exclusion suppresses r17 and answers the query with a direct read or a partial result.
Napkin Math 6.4: Who pays for keeping the index current
Math: Synchronous re-indexing halts write completion until parsing, postings updates, and vector embeddings are fully finished. Backed by a local embedding model, this pipeline adds 88 ms directly to the write path. A single batched remote embedding call increases write overhead to 210 ms, while serial remote requests per file inflate it to 1.26 s. In contrast, updating 8 local exclusion entries adds 0.4 μs of in-memory metadata work. Subsequent retrieval passes check 50 candidates against this metadata, adding 1.5 μs of local lookup work. The local re-indexing stages consume 220,000× as much time as these metadata updates; this ratio does not compare complete durable write latencies.
Systems insight: Under the coordinated generation protocol, exclusion suppresses known-obsolete entries before subsequent admission, though it does not produce fresh representations immediately. The small local metadata costs do not price the complete durable enforcement path. The computational cost of re-indexing is not eliminated; it is deferred to background workers, requiring the query gateway to manage the staleness gap using the strategies in table 9. Coordinate exclusion with the source commit. Consider synchronous re-indexing when dependent queries arrive before background pipelines can finish and bounded fallback cannot supply the required evidence.
Retrieved evidence represents the source state observed at the moment of the read. In an agentic system, a concurrent write can land before the model finishes deliberating and invokes its chosen action. Any tool call whose correctness depends on an unmodified workspace must therefore enforce an execution-time precondition, such as an optimistic version check, at the tool boundary. The storage subsystem’s core duty is to preserve and surface the exact generation metadata that this precondition requires.
↪ The atomic conditional update that enforces this version precondition at the tool boundary is developed in Conditional updates.
Source-generation checks suppress obsolete records, atomic publication prevents straggling workers from reinstating stale representations, and explicit fallback contracts clarify whether fresh evidence is available. Together, these mechanisms enforce internal storage consistency rather than task success. In accordance with the end-to-end argument (Saltzer et al. 1984), whether the r18 patch truly resolves the stalled waiter can be established only at the system boundary through integration tests executed against the real runtime environment. What the storage layer guarantees to that boundary is an uncompromised, auditable record of the exact source generation reflected in every retrieved fact.
6.10 Evaluating Memory Policies
Excluding a stale failure trace from an earlier run keeps an outdated representation out of the agent’s next request, but it does not ensure that the agent finds the fresh evidence needed to effect a repair. Conversely, a stored reflection might reproduce a recent passing test run accurately while overstating what the pass proves. Rigorous evaluation cannot treat memory as a static lookup table. It must follow information across its full lifecycle: from initial admission into persistent storage, through indexing, retrieval, and prompt staging, to the subsequent updates, supersessions, and deletions that maintain consistency as the environment evolves.
The appropriate unit of comparison is the memory policy. A memory policy encompasses what an agent writes, how it indexes and retrieves records, how it stages evidence in the prompt, and how it maintains that evidence across sessions. The retrieval index is merely one component of that policy. Component-level microbenchmarks help locate failures in search precision or index latency, but task-level outcomes ultimately decide whether the assembled policy satisfies operational acceptance criteria.
6.10.1 Cross-session policy trials
If an evaluation harness shares a single writable vector store across candidate memory policies, a reflection or reference answer written during Policy A’s run leaks into Policy B’s trial and makes Policy B appear to learn from tasks it never solved. A controlled cross-session trial begins with a fixed source snapshot and an isolated initial memory store for each policy, running identical task sequences under identical constraints on model inference, tool execution, and compute budgets. Records generated during one trial session may influence subsequent sessions within that same trial, since that cross-session behavior is what the trial measures, but they must never contaminate a parallel trial. Ground-truth reference answers, test fixtures, and evaluator annotations must remain strictly outside both writable and retrievable stores.
↪ Evaluation leakage, including solutions that persistent memory carries from one run into the next, is developed in Evaluation leakage.
The comparison in table 10 isolates the baseline benefit of raw persistence from the operational benefit of governing what persists. Across all experimental conditions, the system enforces identical access controls and action permissions. The “unchecked” condition isolates content admission alone, while all conditions experience external source modifications and user updates on the same synchronized fixture schedule.
| Policy condition | Question the comparison tests |
|---|---|
| New memory writes disabled | Can the task be completed from the allowed sources without accumulating additional cross-session memory? |
| Unchecked memory writes | Does retaining proposed notes help later sessions, or propagate unsupported claims and duplicates? |
| Checked admission, no lifecycle maintenance | Do admission checks help initially but leave records misleading after later changes? |
| Checked admission and lifecycle maintenance | Do correction, supersession, revalidation, expiry, and deletion preserve useful evidence under change, at an acceptable cost? |
The scheduling preference supplies a concrete lifecycle fixture: an initial preference recorded at 10:00, an explicit supersession at 11:00, and a user deletion request in a subsequent session. The evaluation tests whether the agent applies the active preference before deletion and complies with post-deletion invariants afterward. This requires inspecting every storage tier: primary vector and keyword indices, consolidated summaries, and staged prompt templates. An agent that suppresses the primary record from raw search results but still retrieves an unpruned summary containing the old preference violates its withdrawal contract. System backups or audit logs retained for regulatory compliance must also fall under an explicit data-retention policy rather than being counted as active working memory.
Similarly, an iterative software-repair fixture retains the failing run at r17, records the subsequent passing run at r18, and then challenges a future agent session to distinguish historical debugging context from the current state of the implementation without inappropriately broadening the reproducer’s scope. When source files change, the fixture tests two behaviors: a relevant source edit should trigger revalidation of dependent records, while an unrelated source edit tests whether the policy mistakenly discards valid, useful evidence.
Deterministic fixed-record probes isolate specific defects in admission filtering, retrieval ranking, or cache invalidation. Full task trials then allow policies to accumulate their own records across multi-turn interactions, causing their execution trajectories to diverge naturally over time. Evaluators must hold initial conditions and scoring rubrics constant across runs. When stochastic generation or environment variations introduce noise, evaluations must report the number of independent trials alongside the full distribution of outcomes rather than relying solely on mean performance.
6.10.2 Retrieval relevance judgments
Scoring a retriever by whether it returns the r17 failure log for a query about src/pool.py rewards the right record when the task asks for bug history and rewards a stale defect when the task asks whether r18 passes. For each test query, the benchmark must define the eligible source snapshot, the authorized access scope, and the specific records relevant to the agent’s immediate task. Evaluation fixtures must explicitly label temporal validity rather than expecting an embedding model’s similarity score to distinguish historical context from current state.
Let \(\RetrievedRecordSet_k\) be the set of distinct records returned up to cutoff \(\RetrievalCutoffCount\), and let \(\RelevantRecordSet\) be the set of labeled relevant records in the eligible snapshot. Precision at cutoff \(\RetrievalCutoffCount\) is defined as
\[ \text{P}@\RetrievalCutoffCount = \frac{\lvert\RetrievedRecordSet_k \cap \RelevantRecordSet\rvert}{\RetrievalCutoffCount}, \qquad \RetrievalCutoffCount > 0. \tag{5}\]
The denominator is the target cutoff \(\RetrievalCutoffCount\), not the number of records the retriever actually returned. Unfilled result positions receive zero credit. Under this formulation, an empty result set scores zero, ensuring that a policy that underfills its staged context cannot artificially outscore a policy that retrieves a broader set of useful evidence. In contrast, calculating precision strictly over the returned records (with \(\lvert\RetrievedRecordSet_k\rvert\) in the denominator) can invert these rankings. Evaluators must explicitly declare their denominator convention and report the raw count of returned records alongside precision scores.
Recall measures the fraction of relevant evidence retrieved from the eligible store:
\[ \text{Recall}@\RetrievalCutoffCount = \frac{\lvert\RetrievedRecordSet_k \cap \RelevantRecordSet\rvert}{\lvert\RelevantRecordSet\rvert}. \tag{6}\]
When the relevant set \(\RelevantRecordSet\) is empty, recall is mathematically undefined (\(0/0\)). Evaluators should isolate unanswerable queries into a dedicated reporting cohort, assessing whether the agent correctly recognizes the absence of supporting evidence or fabricates an unsupported claim. Keeping the completion status of every evaluation query visible ensures that such boundary conditions are not swept into an aggregate average.
When surfacing an immediate answer is the priority, Mean Reciprocal Rank (MRR) evaluates how quickly the system finds its first hit. MRR computes the arithmetic mean of the reciprocal rank of the first relevant record across all evaluated queries, scoring zero whenever no relevant item appears within cutoff \(\RetrievalCutoffCount\). However, MRR is insensitive to whether the complete evidence required for a multi-hop reasoning chain was assembled. Multi-hop evaluation fixtures must separately verify that all required entity relationships and source versions are present.
Temporal applicability demands a separate metric. The stale-return rate is the fraction of current-state queries that return at least one record invalidated by subsequent source modifications. It measures the store one layer below the stale-support rate of context engineering (equation 4.7): stale-return counts what retrieval hands back, while stale-support counts decisions that rest on superseded evidence once it is in context, so a stale record that the runtime labels or excludes at staging raises the first without raising the second. Historical retrospective queries must be evaluated and reported separately. Because a retriever that returns nothing returns no stale records, a degenerate policy that returns zero results achieves a perfect stale-return rate of zero while completely failing the task. Consequently, stale-return rates must always be reported alongside recall and evidence coverage.
6.10.3 Lifecycle outcomes and full costs
A memory policy that deletes a user preference from its primary table in 2 ms while leaving the preference inside a cached episode summary and a background embedding queue appears fast and compliant only until the next session stages the summary. In supersession and deletion trials, evaluators track whether an updated or deleted record, along with all its downstream representations (index postings, graph edges, and cached summaries), reached the declared target state within an established deadline. The benchmark logs update latency, queue backlogs, and unresolved timeouts. In this analysis, expiring a record from active retrieval and physically purging it from persistent storage are distinct operations that require distinct accounting; describing a record loosely as “forgotten” obscures whether data was merely hidden from the read path or permanently deleted from the database.
End-to-end task acceptance remains the ultimate arbiter of system quality. The acceptance rate must be calculated across all admitted task trials, explicitly including timeouts, uncaught exceptions, and partial completions in the denominator. Satisfying an obsolete constraint is an operational failure, even if the retriever achieved high precision against a stale label set.
System resource accounting must respect the same strict evaluation boundaries. Cost accounting aggregates the end-to-end compute footprint: query generation, keyword search, dense similarity computation, cross-encoder reranking, model token usage, memory writes, offline consolidation, and background index compaction. This tally must include asynchronous background operations that do not directly block foreground user requests, as well as deferred maintenance tasks lingering at the end of the evaluation window. Dividing the total expenditure by the number of successfully completed tasks yields the cost per accepted task (equation 1.2). If a system completes zero tasks, evaluators must report total expenditure and zero successes rather than computing an undefined or misleading ratio.
Storage measurements require equally clear accounting boundaries. Benchmarks should report raw source bytes separately from auxiliary structures, including inverted index postings, dense vector tables, graph adjacency lists, version metadata, and durability replicas. A benchmark report must explicitly define whether its reported storage amplification represents auxiliary bytes divided by raw source bytes, or total stored bytes (source plus auxiliary) divided by raw source bytes. Similarly, update-latency benchmarks must compare equivalent operations: a full index rebuild against a full index rebuild, rather than comparing a complete re-indexing pass against an asynchronous tombstone lookup. Notebook 6.5 compares both metrics across two representative store architectures.
Dense vectors multiply a store’s auxiliary bytes by an order of magnitude.
Napkin Math 6.5: Why two memory stores differ by an order of magnitude
Math: Store A’s auxiliary structures occupy 14.4 MB, an auxiliary ratio of 0.36× over the raw source (total ratio 1.36×). Store B’s occupy 340.8 MB, of which the vectors alone are 307.2 MB, an auxiliary ratio of 8.52× (total 9.52×). After an edit to 15 files, at stipulated throughputs for postings updates and parsing, Store A re-indexes in 34.1 ms. Store B must re-embed 30 chunks; at 50 chunks per second it needs 612 ms.
Store B carries ~24× the auxiliary bytes of Store A and takes ~18× as long to re-index.
Systems insight: Dense vectors dominate both the bytes and the maintenance time, because each chunk becomes hundreds of floating-point components produced by a model pass. Compressing the vectors attacks the byte term, and storing them at FP16 would halve the vector bytes; only a faster encoder or fewer re-embedded chunks attacks the time term, which sets the stale window after every edit. The time ratio therefore depends on the stipulated encoder throughput and shrinks with a faster encoder, while the byte ratio does not depend on it. A dense index is worth its order of magnitude only when it raises task acceptance enough to repay that maintenance in the cost per accepted task. The live-source baseline of section 6.4 pays neither term, which is why it is the comparison every added index must beat.
Staging depth warrants independent empirical measurement because task success does not increase monotonically with the retrieval cutoff \(\RetrievalCutoffCount\). Recall@\(\RetrievalCutoffCount\) (equation 6) cannot decrease as \(\RetrievalCutoffCount\) increases, but every added record changes the prompt the model must use. Two effects that limit usable working context act together here. Each superficially similar but irrelevant passage adds to the softmax normalizer and so dilutes the attention the critical evidence receives (attention dilution), and a larger staged set pushes some of that evidence toward the middle of the prompt, where models use it least reliably (lost in the middle) (Liu et al. 2024). Too few records starve the decision of evidence; too many bury it. The optimal operating range depends heavily on the model’s attention architecture, task complexity, and reranker quality. This mirrors the working-set view of context (principle 4). In practice, a retrieval pipeline should configure candidate generation to maximize recall, use a precise reranker to stage only a compact working set into the prompt, and systematically sweep staging depth across evaluation trials rather than assuming a single static cutoff.
↩︎ Usable working context, with attention dilution and the lost-in-the-middle effect that bound it, is established in Usable Working Context.
Ultimately, memory evaluation yields a multidimensional trade-off space rather than a single scalar benchmark score. A more expansive memory store retains helpful edge-case experiences, but it also accumulates obsolete or contradictory records. Conversely, a strict admission gate shields the agent from spurious lessons at the expense of rejecting valuable domain context. A thorough evaluation varies read and write policies under identical operational budgets, testing whether variations in accepted task outcomes stem from evidence coverage, temporal applicability, lifecycle maintenance failures, or compute and storage costs.
6.10.4 Adversarial boundary tests
An indirect prompt injection embedded inside a fetched documentation page can trick a background reflection worker into storing an unauthorized directive as a permanent project lesson, where it survives long after the untrusted page is evicted from the context window (Greshake et al. 2023). In an isolated evaluation sandbox, test harnesses inject synthetic credentials, probe unauthorized namespace boundaries, and retrieve documents embedded with indirect prompt injections. The test suite evaluates two enforcement layers: whether the runtime intercepts and suppresses unauthorized reads and writes, and whether an adversarial payload survives in downstream consolidated summaries after the primary source document has been withdrawn.
Evaluators must capture both the model’s proposed actions and the runtime’s actual execution disposition. Logging both stages ensures that the evaluation distinguishes an attempted security breach from an executed vulnerability. The memory policy is accountable for the records it admits, indexes, and stages; the tool and runtime authorization subsystems are accountable for governing what the agent is permitted to execute against the external environment.
↪ The general adversarial-evaluation method developed in Adversarial Robustness and Red-Teaming specifies the trial and the attacker’s capabilities and measures attack success beside useful completion.
Checkpoint 6.4: Evidence across sessions
A proposed memory policy raises retrieval scores on a static snapshot. Its authors have not tested updates, deletion, or later task outcomes.
6.11 Fallacies and Pitfalls
Persistent memory systems fail when they grant a stored representation more operational authority than its underlying provenance supports, or when they treat write-time admission as a permanent guarantee of validity. Each fallacy or pitfall that follows is a design shortcut that produces silent state corruption, latency spikes, or decisions made on stale evidence, and most carry a cost that one of the chapter’s notebooks quantifies.
Fallacy: A near-duplicate memory carries no new information.
The 10:00-to-11:00 revision at the admission gate (section 6.8.2) is one instance of a wider class. A flipped flag (“notify me of failures” becoming “do not notify me of failures”) and a scoped exception (“no meetings before 11:00 on Fridays”) also land beside the record they modify in embedding space, yet the first reverses it and the second must coexist with it. A similarity threshold fails differently on each, dropping the reversal as a repeat and collapsing the exception into the general rule, so the agent either keeps the prohibited behavior or loses the narrower constraint. High geometric proximity does not imply semantic equivalence. An admission pipeline must first establish entity identity, scope, record kind, and explicit update semantics; geometric similarity should deduplicate storage only after verifying that the new record asserts no state change and no change of scope.
Pitfall: Treating a high-ranked record as current.
Vector similarity scores indicate semantic or topical affinity with a query, but they convey nothing about temporal freshness, transactional validity, or operational authority. In the trace that opens section 6.9, the outdated r17 excerpt of src/pool.py ranks first for the notification query. At turn 13 the agent consumed it without a version label, concluded that its own completed edit had been lost, and spent the following turns re-issuing that edit and then making speculative changes that pushed the repository further from a reviewed state. Coordinated generation checks prevent this particular cascade. Filtering 50 candidates adds 1.5 μs of local metadata lookup work under the stipulated scenario, excluding the durable coordination and fallback costs (notebook 6.4). While index rank identifies candidate relevance, the runtime must rely on provenance, version tags, visibility scope, and completion status to govern how a retrieved record is applied.
Fallacy: Staging more retrieved records gives the model more evidence.
Recall@\(\RetrievalCutoffCount\) cannot decrease as \(\RetrievalCutoffCount\) grows, but task success does not follow it (Liu et al. 2024). In notebook 6.1, a staging policy that counts only raw document bodies admits 12 records that serialize to 7,040 tokens, overrunning a 6,144-token allowance before any of it reaches the model. Even within the allowance, the dilution and position effects that make staging depth a measured quantity rather than a maximum still apply. Staging depth must be calibrated against downstream task completion and execution budgets rather than optimizing recall in isolation (section 6.10).
Pitfall: Re-indexing synchronously on every write to keep the index current.
Recomputing dense embeddings and rebuilding index graphs synchronously on every mutation introduces severe write latency and throughput bottlenecks. Under the stipulated costs of notebook 6.4, synchronous re-indexing adds between 88 ms and 1.26 s of blocking latency to every edit. Decoupling exclusion from rebuilding moves that work off the write path. The local exclusion updates take 0.4 μs, and each later query adds 1.5 μs of metadata lookups, excluding the common durable commit and coordination costs and any fallback retrieval. Replacement entries are built in the background. Blocking for fresh indexed representations can still be useful when dependent queries arrive inside the rebuild window and direct fallback cannot answer them within budget.
Fallacy: Every dense store needs an approximate index, because an exact scan is too slow.
Flat, exact vector scans scale linearly with the number of candidate vectors, but memory bandwidth alone carries substantial collections within tight latency budgets. In notebook 6.2, an unindexed scan across 10,000,000 vectors has a streaming floor of 307.2 ms. Applying a tenant or workspace filter beforehand reduces the candidate set to 10,000 vectors, dropping the streaming floor to 0.31 ms. A 10 ms query budget gives an optimistic ceiling of ~326,000 vectors before query encoding, top-\(\RetrievalCutoffCount\) selection, and record fetches are charged. Exact scans deliver perfect recall under the metric with zero graph construction overhead, no index fragmentation, and immediate write availability. The bandwidth floor rules out infeasible scans; measured full-request latency determines whether an exact scan meets the budget and whether an approximate index merits its maintenance overhead.
Pitfall: Evaluating memory on a static snapshot.
Benchmarking a memory subsystem against a static snapshot conceals the operational costs and failure modes that emerge under continuous mutation. Snapshot benchmarks ignore index drift, synchronization lag, compaction overhead, and stale-read anomalies. In notebook 6.5, modifying 15 files leaves a dense vector store without current entries for 612 ms, compared to 34.1 ms for a lexical and structural store, and every query in that window must fall back to a direct read or a partial result. Static tests also miss race conditions such as a delayed worker republishing superseded state or an explicitly deleted user preference persisting inside a rolled-up summary. Evaluate memory architectures using dynamic lifecycle fixtures (section 6.10), measuring end-to-end task completion, synchronization latency, and storage amplification across realistic write-read-delete workloads.
6.12 Summary
A software repair agent needs far more than an index that matches text embeddings against a bug report. Reliable long-term memory requires the system to determine what each retained record represents, which authoritative source supports it, how context budgets constrain its entry into later requests, and how downstream state changes when that underlying support is modified. Retrieval methods locate candidates under an explicit operational contract; the write lifecycle governs which records survive to become candidates; and comprehensive evaluation ensures that engineers do not mistake improved search recall for genuine task performance. Table 11 collects the quantitative relations governing long-term memory systems, linking each computational bound and operational threshold to the systems decision it informs.
| Equation | What it bounds or decides | Where derived |
|---|---|---|
| \(\operatorname{score}(\LexicalDocument,\LexicalQuery)=\sum_{\QueryWord\in \LexicalQuery}\operatorname{IDF}(\QueryWord)\frac{\QueryWordFrequency(\QueryWord,\LexicalDocument)(\LexicalFrequencySaturation+1)}{\QueryWordFrequency(\QueryWord,\LexicalDocument)+\LexicalFrequencySaturation(1-\LexicalLengthNormalization+\LexicalLengthNormalization\lvert \LexicalDocument\rvert/\MeanDocumentLength)}\) | Lexical rank order; saturation (\(\LexicalFrequencySaturation\)) and length normalization (\(\LexicalLengthNormalization\)) outweigh raw repetition | equation 1 |
| \(\EligibleVectorCount \EmbeddingDimension\ElementStorageSize\) bytes, \(2\EligibleVectorCount \EmbeddingDimension\) FLOPs, intensity \(2/\ElementStorageSize\) | Exact-scan time floor \(\EligibleVectorCount \EmbeddingDimension\ElementStorageSize/\Bandwidth\) and an optimistic eligible-set ceiling under a latency budget | section 6.6 |
| \(\PqApproximateDistance(\SearchQueryEmbedding, \StoredIndexVector) = \sum_{j=1}^{\PqSubvectorCount} \text{LUT}[\PqSubspaceIndex, \PqCentroidCode_j]\) | Bytes touched per scored vector under IVF-PQ; \(\PqSubvectorCount\) trades fidelity against code size | equation 2 |
| \(\operatorname{RRF}(\FusionCandidate) = \sum_{i:\,\FusionCandidate\in \FusionInputList_i} 1/(\RankFusionSmoothingConstant + \FusionInputRank_i(\FusionCandidate))\) | Fused candidate order across methods whose scores share no scale | equation 3 |
| \(\lfloor(\text{allowance} - \text{envelope})/(\text{body} + \text{metadata})\rfloor\) | Complete records that fit a retrieval allowance once output and envelope are reserved | section 6.3.3 |
| \((\text{children}^{\text{depth}+1}-1)/(\text{children}-1)\) | Nodes in a bounded traversal neighborhood, set against the payload budget | section 6.7 |
| \(\text{IsValid}(\DerivedMemoryEntry, \QueryWorkspaceGeneration) = \big(\MemoryEntryBirthGeneration(\DerivedMemoryEntry) \le \QueryWorkspaceGeneration < \MemoryEntryDeathGeneration(\DerivedMemoryEntry)\big)\) | Whether a derived entry may answer a query that requires generation \(\QueryWorkspaceGeneration\) | equation 4 |
| \(\TombstonedRecordFraction = \lvert \TombstonedNodeSet\rvert/\lvert \IndexGraphNodeSet\rvert\) | When tombstoned entries cost enough memory and recall to trigger compaction | section 6.9 |
| \(\text{P}@\RetrievalCutoffCount = \lvert\RetrievedRecordSet_k \cap \RelevantRecordSet\rvert/\RetrievalCutoffCount\), \(\text{Recall}@\RetrievalCutoffCount = \lvert\RetrievedRecordSet_k \cap \RelevantRecordSet\rvert/\lvert\RelevantRecordSet\rvert\) | Retrieval quality against a declared relevant set, with precision over the requested \(\RetrievalCutoffCount\) and the stale-return rate beside it | equation 5 |
| \(\CostPerAcceptedTask = \mathbb{E}[\AttemptCost]/\AcceptanceProbability\) | Whether a memory policy’s added retrieval and maintenance cost is repaid in accepted tasks | equation 1.2 |
Key Takeaways: Persistent information needs a lifecycle
- Records retain different kinds of evidence: Primary source records, agent observations, synthesized lessons, and retrieval indexes serve different roles in an evidence chain. Explicit provenance and scope allow downstream systems to distinguish an empirical execution outcome from a speculative hypothesis. System deployers remain strictly accountable when an aggregated summary or derived heuristic contradicts its underlying source of record.
- A retrieval result has a contract: Scope boundaries, access controls, version validity, payload budgets, and completion status dictate what enters prompt context. Formatting envelope overhead and metadata fields consume token allowances alongside record bodies, directly capping candidate capacity. An empty response from a partial or approximate search does not prove absence. Only a completed exhaustive search supports that conclusion within its declared scope and snapshot.
- Search strategy follows the information need: Key-value lookups, lexical ranking, dense vector similarity, and structural graph traversal address distinct retrieval requirements. An exact scan supplies the recall baseline under the chosen metric. Its bandwidth floor (\(\EligibleVectorCount \EmbeddingDimension\ElementStorageSize/\Bandwidth\)) rules out infeasible scans, while measured full-request latency determines whether it meets the search budget. Every auxiliary vector index or inverted list introduces ongoing write amplification and synchronization overhead, which pays off only when it delivers measurable gains in task accuracy.
- Relationships need evidence and a budget: Explicit graph edges connect scattered records into cohesive multi-hop evidence chains. Because candidate neighborhoods expand exponentially with traversal depth (\((\text{children}^{\text{depth}+1}-1)/(\text{children}-1)\)), retrieval pipelines must enforce strict depth and branching limits before scoring nodes. Traversal paths indicate topological reachability rather than verified runtime execution traces, so the agent must treat discovered paths as structural hypotheses that require independent corroboration.
- Memory must change as its support changes: Updates, supersession, time-to-live expiration, and deletion policies dictate whether a record remains eligible for future prompts. Modifying or evicting a primary record invalidates all downstream summaries, embeddings, and inverted postings. Records that describe a user carry the consent and retention period under which they were admitted, and withdrawn consent or an elapsed retention period starts the same deletion procedure as an explicit request. Apparent near-duplicates frequently represent critical real-world state mutations rather than redundant text. Moreover, frequent read access indicates high utilization, but read volume alone does not validate the ongoing factual accuracy of stored state.
- Exclusion and rebuilding incur different work: In the stipulated scenario, local exclusion lookups take microseconds while replacement indexing takes milliseconds to seconds; durable coordination and fallback costs remain separate. Decoupling invalidation from background re-indexing through version-aware visibility windows (\(\MemoryEntryBirthGeneration(\DerivedMemoryEntry) \le \QueryWorkspaceGeneration < \MemoryEntryDeathGeneration(\DerivedMemoryEntry)\)) shields readers from stale state while asynchronous maintenance pipelines converge.
- Evaluate memory policies across multi-session lifecycles: Offline ranking benchmarks reveal candidate retrieval precision, but multi-session evaluations expose how agents compound diagnostic errors or accumulate stale context over time. Assess competing memory architectures by their end-to-end task completion rate (\(\AcceptanceProbability\)), lifecycle contract compliance, and amortized cost per accepted task (\(\CostPerAcceptedTask\)), using isolated search metrics primarily to diagnose local failure modes.
Authority always resides with the source of record (principle 6). Retrieval therefore operates as an enforceable contract governing scope, freshness, and context allowances, rather than an unconstrained similarity lookup, and locating a candidate record does not grant permission to inject it uncritically into downstream execution. The write lifecycle extends this discipline to all derived artifacts that agents generate across sessions, including summaries, graph entities, vector embeddings, and cached lessons. Every transformation must preserve the explicit provenance, boundary conditions, and uncertainty of the original evidence rather than silently amplifying tentative diagnostic guesses into durable facts.
6.13 Historical Perspective and Further Reading
Long before digital computers possessed the capacity to store vast text collections, researchers recognized that locating the right record among many is a selection problem rather than a storage problem. In his influential vision of the memex, Bush (1945) imagined a desk-sized device that would house an individual’s books, records, and correspondence, allowing the user to establish associative trails between related items. Bush observed that human memory operates by association rather than formal indexing, and he located the primary engineering difficulty in selection rather than physical storage capacity. Over the subsequent half-century, classical information retrieval transformed selection into mathematical measurement. Salton et al. (1975) formalized documents and queries as term-weight vectors ranked by geometric similarity in a shared vector space. Spärck Jones (1972) supplied the statistical foundation of inverse document frequency, demonstrating that rare terms provide far higher discriminative power than common ones. Building on probabilistic relevance frameworks, the approximations formulated by Robertson and Walker (1994) culminated in BM25, which remains a durable lexical ranking baseline across modern search engines. To make these rankings practical over large collections within tight latency budgets, search engines turned to inverted files, postings lists optimized for compact compression and fast intersection (Zobel and Moffat 2006). Lexical matching, however, inevitably faced the vocabulary mismatch problem: users and authors routinely describe identical concepts using different words (Furnas et al. 1987), an obstacle that ultimately required learned semantic representations.
A second lineage came from databases and distributed systems, which tackled the maintenance half of the problem long before retrieval systems confronted mutable state. Because an agent’s retrieval index operates as a derived view over evolving execution logs and external environments, it inherits classical database maintenance obligations. Incremental view maintenance established the formal methods required to keep a derived table consistent with its mutating base relations without recomputing the entire view from scratch (Blakeley et al. 1986; Gupta and Mumick 1995). To coordinate concurrent writes without restrictive locking, optimistic concurrency control conditioned updates on validation checks against read sets (Kung and Robinson 1981). In distributed systems with weakly consistent replicas, epidemic replication algorithms proved that deletions must leave explicit tombstone markers; without them, lagging peers interpret the absence of a record as missing data and resurrect the deleted item (Demers et al. 1987). Similarly, session guarantees formalized the exact consistency expectations, such as read-your-writes and monotonic reads, that clients require when querying lagging replicas (Terry et al. 1994). At the storage layer, the log-structured merge-tree turned append-only logging and deferred compaction of superseded entries into an essential systems pattern (O’Neil et al. 1996). Each of these mechanisms reappears in agent memory architectures, because a retrieval index is a ranked materialized view over mutable history as well as a search structure.
Learned retrieval joined these two lineages. Geometric relaxations such as locality-sensitive hashing initially emerged to help approximate nearest-neighbor search escape the curse of dimensionality (Indyk and Motwani 1998). Subsequently, product quantization (Jégou et al. 2011) and navigable proximity graphs (Malkov and Yashunin 2018) made sub-linear vector search practical at the scale of billions of embeddings (Johnson et al. 2019). In parallel, deep learning architectures began incorporating explicit memory components. Memory networks gave neural models a dedicated, addressable store to read and write outside their parameter weights (Weston et al. 2015). Open-domain question answering then paired learned neural retrievers with reading comprehension models (Chen et al. 2017), and dense passage retrieval (Karpukhin et al. 2020) alongside retrieval-augmented generation (Lewis et al. 2020) made the retriever an end-to-end learned component of text generation. Agent architectures extended this design by transforming the memory store into an active workspace that models write as well as read. Systems introduced interleaved search and reasoning traces (Yao et al. 2023), operating-system-inspired virtual context paging (Packer et al. 2023), verbalized self-reflections to correct past failures (Shinn et al. 2023), and continuous observation streams consolidated periodically into higher-level reflections (Park et al. 2023). From these combined lineages, agent systems inherit the engineering obligation this chapter develops. An agent’s memory record is dependable only to the extent that its provenance, version validity, and operational scope are explicitly guaranteed.
The following foundational works repay deeper study, organized in rough chronological progression:
- Bush (1945) frames personal knowledge management around associative trails and selective retrieval, demonstrating that the central challenge of agent memory, extracting relevant context from an expansive repository, predates digital computing.
- Robertson and Zaragoza (2009) provides the authors’ retrospective on the probabilistic relevance framework behind BM25, with a clear explanation of why term saturation and document length normalization take their specific mathematical forms.
- Zobel and Moffat (2006) surveys inverted-file construction, postings compression, and fast top-\(\RetrievalCutoffCount\) query evaluation, detailing the systems engineering that underlies every production lexical index.
- Terry et al. (1994) formalizes four client-centric session guarantees in a few compact pages. Read alongside section 6.9, it clarifies precisely which guarantees a retrieval gateway must enforce when managing asynchronous memory updates.
- Jégou et al. (2011) and Malkov and Yashunin (2018) establish the two dominant architectural patterns in modern vector indexing. The former details product quantization for aggressive vector compression and fast asymmetric distance computation, while the latter introduces Hierarchical Navigable Small World (HNSW) graphs for sub-linear proximity routing. Both provide rigorous analyses of what each approximation sacrifices in recall vs. query latency.
- Park et al. (2023) presents an end-to-end memory architecture for autonomous agents, combining continuous observation streams, multi-factor scoring (recency, importance, and relevance), and periodic hierarchical reflection. It serves as a concrete reference against which the record types and lifecycle contracts of this chapter can be evaluated.
6.14 Exercises
Every quantity below is a hypothetical given chosen for round arithmetic, not a measurement of any system. Each problem ends in a decision; state the decision and the number that justifies it.
1. Serializing a smaller call (Basic). A call permits 16,384 tokens. The runtime reserves 1,024 for output, and all other serialized input occupies 11,264. The result envelope costs 96 tokens, and each retrieved record carries a 300-token body and 60 tokens of source, version, and provenance metadata.
- How many complete records fit, and how many tokens remain?
- A retrieval limit that counts only bodies would admit how many records, and by how much would their serialization overshoot the allowance?
- The task owner wants 13 records staged. Metadata cannot be dropped, because the version labels are what let the model tell
r17fromr18. What is the largest body excerpt per record that meets the request? - Two more tool results adding 512 tokens of other input arrive before the call. How many complete records fit now, and which reservation should the runtime recompute before dispatch?
2. Where the exact scan stops paying (Basic). A tenant’s store holds \(\EligibleVectorCount = 2{,}000{,}000\) vectors of dimension \(\EmbeddingDimension = 1{,}024\) in FP16 (\(\ElementStorageSize = 2\) bytes). The host sustains 100 GB/s of memory bandwidth and 2 TFLOP/s of peak arithmetic, and each search has a 5 ms latency budget.
- Compute the bytes, FLOPs, and arithmetic intensity of one exact scan, and compare the intensity with the host’s ridge point.
- What is the bandwidth floor for one full scan, and what optimistic eligible-vector ceiling does that floor set under the budget?
- A scope filter restricts most queries to one project of 150,000 vectors. Does the bandwidth floor rule out an exact scan, and what measurement would decide whether it meets the search budget?
- Would storing the full corpus as INT8 bring the bandwidth floor of an unfiltered exact scan within budget?
3. How much agreement buys (Basic). Lexical search returns P, Q, R, S in that order, and dense search returns S, T, P, U. Every candidate is fully scoped to the same r18 snapshot, ties break by candidate identifier, and the runtime stages three records.
- With \(\RankFusionSmoothingConstant = 60\), compute every fused score with equation 3 and the staged set.
- Find the largest rank \(\FusionInputRank\) at which a candidate appearing at rank \(\FusionInputRank\) in both lists still outscores a candidate at rank 1 in only one list, for \(\RankFusionSmoothingConstant = 60\) and for \(\RankFusionSmoothingConstant = 1\).
- Candidate Q is the reproducer test the agent must read. Is there any positive \(\RankFusionSmoothingConstant\) at which Q outranks P? How does Q reach the staged set at \(\RankFusionSmoothingConstant = 60\), and what should the runtime do instead of relying on that?
4. How much the task names (Intermediate). Transfer the choice of retrieval policy (section 6.4) to the research agent, whose store holds notes distilled from fetched pages. Every model round takes 4 s, and retrieval operations are fast enough to ignore. Each note serializes to 600 tokens with its metadata, the retrieval allowance is 6,144 tokens, and everything retrieved stays in context until the answer. Three policies are available. A direct read stages exactly the records the task names, with no extra round. Pre-staging stages the top 8 ranked notes before the first call; when that set lacks needed evidence, the model falls back to probing for what is missing. A model-directed probe costs one model round and returns 2 notes. Every policy ends with one answer round. Three tasks arrive:
- R1: “Reconcile pinned notes
n-4412andn-4413.” The evidence is those two notes. Pre-staging captures both with probability 0.9, and a miss costs one probe round. Directed search needs one probe round. - R2: “What has earlier work in this project established about battery fade under fast charging?” The evidence is three unnamed notes. Pre-staging captures all three with probability 0.8, and a miss costs one probe round. Directed search needs two probe rounds.
- R3: “Trace where the 40 percent figure in
n-4412came from.” The evidence isn-4412and three further notes, each found only from a citation in the one before. Pre-staging includesn-4412but captures the whole chain with probability 0.1, and a miss costs three dependent probe rounds. Directed search needs four dependent probe rounds.
- For R1, compute the expected latency and staged tokens of each policy. Which policy wins, and what does pre-staging add that the research agent’s binding constraint makes costly?
- For R2, compare pre-staging with directed search in expected latency, expected staged tokens, and worst-case staged tokens against the allowance. Which should the runtime choose?
- For R3, compute the same quantities for pre-staging and for directed search. Why is pre-staging’s lower expected latency not a reason to choose it?
- Design a policy for R3 that combines two of the three, and compute its latency and staged tokens. State the selection rule the three tasks illustrate, and name the property of a returned record that stays the same whichever policy retrieves it.
5. Fitting an index in memory (Intermediate). A research store holds \(\EligibleVectorCount = 50{,}000{,}000\) passage vectors of dimension \(\EmbeddingDimension = 768\) in FP16 on a host with 64 GB of memory available for the index. The candidate designs are an exact scan of the raw vectors, HNSW with 32 eight-byte links per vector, and IVF-PQ with \(\PqSubvectorCount = 96\) one-byte subcodes, \(\CoarseCellCount = 10{,}000\) FP16 coarse centroids, and an 8-byte record identifier per stored code.
- Which designs fit the memory budget? Compute the resident bytes of each.
- For IVF-PQ, give the subvector dimension, the per-query lookup-table size with FP32 entries, and the compression ratio over the FP16 vectors.
- With \(\ProbedCellCount = 16\) and evenly filled cells, how many bytes of codes does one query scan, and how does that compare with the bytes read to compare the query against every coarse centroid? What does the comparison suggest about the next optimization?
- Full-precision re-scoring of a 100-candidate shortlist reads vectors from secondary storage. How many bytes does that fetch, what distance accuracy does it recover, and which upstream misses can it not repair?
6. Synchronous re-indexing in a repair session (Intermediate). Each edit in a repair session changes 5 files and 15 indexed chunks. Stipulated costs are 4 ms to parse a file, 2 ms to update one chunk’s postings, 40 ms per local embedding batch of up to 8 chunks, 150 ms per batch on a remote service, 50 ns for a local in-memory exclusion update per file, and 30 ns for a local lookup on one of 40 candidates per query. All strategies share a durable source-commit and coordination boundary whose costs are excluded, along with fallback retrieval costs. Background rebuilding starts immediately after that commit and executes the stipulated stages serially without queueing. A session performs 60 edits, and the model’s next dependent query arrives 2 s after each source commit.
- What write-path time does synchronous re-indexing add per edit with the local service, with the remote service, and over the whole session?
- What local metadata work does exclusion add per write and per query, and which costs are absent from this comparison?
- Under background re-indexing with exclusion, is any dependent query served while replacement entries are missing?
- A new runtime issues an automatic verification search 50 ms after every source commit. Which queries now fall inside the rebuild interval, what does the retrieval layer return for them, and does that change justify synchronous re-indexing?
7. Deletion deadlines in a support store (Intermediate). Transfer the invalidation analysis to the support agent. Its store holds 80,000,000 memory vectors under an HNSW graph, kept at constant size because inserts balance removals. Each day 2,000 customers request full deletion of their 40 records apiece, and 20,000 customers supersede one preference, tombstoning its old vector. Compaction is triggered at \(\TombstonedRecordFraction = 0.10\), rebuilds the live graph at a stipulated 20,000 vectors per second, and each tombstone occupies 16 bytes of an in-memory exclusion set. Retention policy requires deleted content to be physically removed within 30 days.
- How many days until the \(\TombstonedRecordFraction\) trigger fires, and what is \(\TombstonedRecordFraction\) when the retention deadline arrives? Which constraint sets the compaction schedule?
- How long does one compaction take, and how large is the exclusion set just before it?
- Each superseded preference also appears in two session summaries of about 1,000 tokens each. How many summary tokens per day would regeneration cost, and what cheaper treatment does the write lifecycle allow for a summary that is only historical?
- The repair agent’s binding hazard is its own edits making indexed copies stale. Name the support agent’s binding hazard and the mechanism in this chapter that answers it.
8. Typed edges as a budget control (Intermediate). A structural graph around a seed function has, on average, 4 outgoing call edges and 10 import edges per node. The retrieval allowance is 8,192 tokens, each node record serializes to 200 tokens, and edges plus the envelope take 150 tokens. Treat the neighborhood as an exact tree with no repeated nodes.
- Through what depth does a traversal restricted to call edges fit, and through what depth does one that also follows imports fit?
- What is the largest number of complete nodes the allowance holds?
- Could trimming node records to 120 tokens let a depth-3 call-only traversal fit? What is the largest node record that would?
- Why would the exact-tree count overstate the staged size of a real repository graph, and why is that no reason to drop the depth bound?
9. Does a dense index pay for itself? (Advanced). Two memory policies serve the same repair workload with one attempt per task. Policy L, lexical plus structural retrieval, accepts 55 percent of tasks at $0.80 per attempt. Policy D adds dense retrieval, accepts 62 percent, and stages more evidence, raising the attempt cost to $0.84. It also re-embeds 20 chunks for each of 6 edits per task at $0.0005 per chunk and carries $0.01 per task of amortized vector storage. Its encoder processes 50 chunks per second.
- Compute \(\CostPerAcceptedTask\) for both policies with equation 1.2. Which is cheaper per accepted task?
- What acceptance rate must Policy D reach to break even with Policy L?
- How long does each edit leave the dense index without current entries, and what must the retrieval layer do for queries in that window?
- The vendor of Policy D’s encoder reports that Recall@10 rose from 0.60 to 0.80 on a static snapshot. Critique the claim as evidence for adopting Policy D, and design the trial that would settle the decision.
10. Redesigning a freshness scheme (Advanced). A team proposes to keep a repair index current with a per-file dirty flag that is set when an edit commits and cleared when a rebuild finishes, plus a five-minute age limit measured from the worker’s source capture. At expiry, an entry becomes ineligible immediately and is scheduled for re-indexing; until a replacement appears, the gateway returns an incomplete result. Every replica applies each primary update exactly 2 s after it commits there, and a publication replaces the file’s current entries. Consider one timeline. At \(\TimeInstant = -0.1\) s worker W1 captures src/pool.py at r17 and begins indexing it. At \(\TimeInstant = 0\) the agent commits r18 and the flag is set. At \(\TimeInstant = 0.5\) s worker W2 publishes r18 entries and clears the flag. At \(\TimeInstant = 0.7\) s W1 finishes and publishes its r17 entries. No other publication occurs before W1’s entries expire. The agent queries the file every 3 s from \(\TimeInstant = 3\) s onward.
- Ignoring replicas, under the proposal, for how long are
r17entries served as current, and how many of the agent’s queries can receive them? - Assign generation intervals to the
r17andr18entries and apply equation 4 with \(\QueryWorkspaceGeneration\) =r18. Which entries are admitted, and what must W1’s publication check do? - A query issued at \(\TimeInstant = 1\) s reaches a replica, carrying the log sequence number of the
r18commit. Using the read-your-writes rule, compare a 0.5 s wait bound with a 1.5 s bound in added latency and in the evidence returned. - Write the redesigned protocol as at most five rules, and state which part of the proposal, if any, survives.