Contract Memory Compiler: Resolve, Then Traverse

1 INTRODUCTION

• An update can change which older record answers a question even when the question and the underlying records remain unchanged.When a meeting moves from Room A to Room B, the needed floor record changes from Room A’s to Room B’s.Source: §1 · p. 1
• Update-dependent evidence selection requires the current relation to guide record selection before the reader receives its context; refreshing selected values cannot recover an omitted next-hop record.Similarity search may miss a record about an entity absent from the question; iterative retrieval can issue another query, whereas this setting selects evidence for one answer call.Source: §1 · p. 2
• CMC extracts relations and their source positions before questions arrive, resolves later values, then follows current relations from question entities to select original records for one answer call.In the example, the current meeting room redirects the next lookup to Room B’s floor record.Source: §1 · pp. 2–3
• 78.25% substring exact match overall and 61.0% on 262K token histories are CMC’s FactConsolidation multi-hop results, reported as state of the art to the authors’ knowledge.FactConsolidation questions concern final memory states in long histories with contradictory updates.Source: §1 · p. 2
• The paper defines a bounded read contract specifying how updates affect current values and evidence coverage.CMC implements it by extracting relations before questions, resolving updates in order, and selecting original records for one answer call.Source: §1 · p. 3
• MQuAKE-MemStream is a derived dataset of ordered memory streams built from MQuAKE-Remastered counterfactual cases.It provides controls for version resolution and evidence selection.Source: §1 · pp. 2–3

2 READING A SERIALLY OVERWRITTEN MEMORY

• Assertions are ordered, and a later assertion overwrites an earlier assertion with the same subject–relation key.Recency is defined by source order.Source: §2 · p. 3
• For hop limit h, selected evidence includes current edges whose subjects are at directed distance less than h from an explicitly named query subject.The read contract defines the anchors and reachability over the current graph.Source: §2 · p. 3
• A bounded closure is current and covers every current outgoing edge from subjects reachable at depth less than h, but may include branches beyond the requested relation.Its usefulness depends on facts being parsed and reachable within h hops; these graph properties do not assign versions to unresolved source text.Source: §2 · p. 3
• When a meeting moves from Room A to Room B, refreshing values on previously selected keys leaves Room A’s floor in context; recomputing reachability selects Room B’s floor instead.The example motivates resolving updates before traversal, and the experiments separately test fixed-key value choice and key selection before value refresh.Source: §2 · p. 3
• All CMC contexts in the shared direct-extraction comparison fit the reader’s fixed input window.Selecting among competing closures when the window binds remains a separate extension of the read interface.Source: §2 · p. 3

3 CONTRACT MEMORY COMPILER

• CMC prepares evidence by extracting relations, recording their source positions, retaining unresolved records, and materializing a current graph shared across queries.Accepted assertions are replayed in source order, with each occurrence replacing the stored edge for its normalized subject–relation key.Source: §3 · pp. 3–4
• The frontend labels each source record as facts, unresolved, or no fact, validates structure and literal spans, and retains accepted edges’ source positions and original text.Source-only LLM alignment proposes common names for equivalent relation slots; the grammar adapter uses manually specified sentence patterns.Source: §3 · p. 4
• Question anchoring uses whole normalized text spans matching graph subjects, keeps the longer match when one matched subject contains another, and treats remaining matches as anchors.Entity disambiguation and alias inference are outside this implementation.Source: §3 · p. 4
• Breadth-first traversal includes every current outgoing edge at subject depths zero through four, with each selected object supplying the next subject.The bounded subgraph may branch; shortest-depth bookkeeping handles cycles, and expansion stops at an empty frontier or the five-hop cap.Source: §3 · p. 4
• For a nonempty selection, rendering returns the original numbered records supporting its edges, adds unresolved records, deduplicates them, and restores source order.A 60,000-character budget applies; on overflow, the renderer keeps the newest contiguous suffix of whole records. An empty selection uses the original history.Source: §3 · p. 4
• For broader MemoryAgentBench tasks, CMC uses different interfaces, including original-window retrieval, card/raw lookup, and coverage notes with original-text fallbacks.The window interface uses 2,048-character windows with 256-character overlap, BM25 selection, and source-order rendering.Source: §3 · p. 4
• At 262K, the measured CPU read takes 13.8 ms median and 144.3 ms p95.Reader-token counts include the chat template; extraction cost is separate.Source: §3 · p. 5

4.1 FACTCONSOLIDATION: SELECTING EVIDENCE AFTER UPDATES

• 78.25% versus 21.50% multi-hop accuracy: CMC outperforms prior read + refresh when extraction and reader are fixed.The comparison isolates the effect of record selection.Source: Table 1 · p. 5, §4.1 · p. 6
• CMC’s 78.25% multi-hop accuracy exceeds fact BM25’s 20.75% and BGE-M3’s 33.25%; at matched evidence length, BM25 reaches 7.25%.Matched-budget mean reader inputs are 185 tokens for CMC and 182 for BM25.Source: §4.1 · p. 6, Figure 3 · p. 6
• At five hops CMC reaches 78.25% versus 11.75% with stale values; one-, two-, and three-hop caps score 5.50%, 54.00%, and 71.75%.A query-time conflict-resolution pipeline scores 60.75% multi-hop versus CMC’s 78.25%.Source: §4.1 · p. 6

4.2 READER AND EXTRACTION CHANGES

• CMC’s multi-hop advantage over fact BM25 persists with Qwen3.5-4B (76.50% versus 20.50%) and Llama-3.1-8B (55.00% versus 11.50%).Absolute scores differ across readers.Source: §4.2 · p. 7, Table 2 · p. 7
• With HY4-preview, direct LLM extraction reaches 78.25% multi-hop accuracy, close to the grammar adapter’s 79.75%.LLM extraction derives relation names from source records rather than manually specified patterns.Source: §4.2 · p. 7

4.3 MQUAKE-MEMSTREAM: A CONSTRUCTED MEMORY DATASET

• MQuAKE-MemStream converts two-hop MQuAKE-Remastered counterfactual cases into ordered memory streams; CMC reaches 96.62% multi-hop accuracy versus 53.38% with all current facts.Every method receives answer-bearing support facts, making this a controlled test of version resolution and evidence selection.Source: §4.3 · p. 7, Table 3 · p. 7

4.4 SAME-READER MEMORYAGENTBENCH

• At the 262K FactConsolidation split, CMC reaches 61.0% multi-hop accuracy, versus 1.0% for the suffix and 2.0% for same-reader BM25.These are a subset of the 800-question comparison.Source: §4.4 · p. 8, Table 4 · p. 8
• CMC leads same-reader rows on five retrieval and recommendation columns but trails dense+BM25 on summarization and DetectiveQA.Classification results are similar across systems (85.8–86.4).Source: §4.4 · p. 8, Table 4 · p. 8

Writing and maintaining agent memory

• Memory systems address multi-session recall, compression, linked notes, temporal versions, and learned storage or update actions; this paper asks which original records enter context after a relation changes.Source: §5 · p. 8

Current state and graph retrieval

• Graph and temporal-memory systems use varied update and retrieval designs; CMC isolates how a resolved object selects the next source record under ordered, single-valued assertions.Source: §5 · p. 9

Multi-hop evidence and answer assembly

• CMC selects source records before one answer call; fixed-extraction controls compare operation order, not complete adaptive pipelines, while MemStream tests supplied facts rather than parametric editing.Source: §5 · p. 9

• Refreshing previously selected values loses 56.75 points because it misses connected current facts needed after an update.Source: §6 · p. 9
• Exact anchoring, missing links, and the hop limit restrict coverage, even though the LLM frontend avoids hand-written patterns.Source: §6 · p. 9
• FactConsolidation came from a broader development grid, so independent confirmation remains needed; 33 of 800 reference answers were flagged as possibly superseded but retained in official scores.Source: §6 · p. 9

• 78.25% current-graph traversal accuracy compares with 21.50% when refreshing the previously selected graph on multi-hop questions.Source: §7 · p. 9
• The same gap appears against retrieval over current facts and under two additional readers.Source: §7 · p. 9
• The demonstrated gain is scoped to ordered, single-valued assertion streams.Source: §7 · p. 9

• The authors record inputs, model identifiers, prompts, settings, outputs, and native scores.Source: REPRODUCIBILITY STATEMENT · p. 9
• Reused responses are verified before joint scoring, and Appendix D documents the evaluation protocol.Source: REPRODUCIBILITY STATEMENT · p. 9
• The supplementary package includes the compiler, evaluation scripts, MQuAKE-MemStream data, and per-example predictions.Source: REPRODUCIBILITY STATEMENT · p. 9

AI USE STATEMENT

• AI coding assistants helped with implementation, experiment execution, artifact checks, and manuscript editing; the authors retain responsibility for the final work.The statement assigns responsibility for methods, results, citations, and the manuscript to the authors.Source: AI USE STATEMENT · p. 9

A COMPILER PROCEDURE

• CMC parses ordered source records with shared preparation, resolves the latest edge per key, traverses from query anchors, and renders selected source records.The procedure sets a 60,000-token budget and a five-hop cap; the reader receives the evidence and question in one call.Source: A COMPILER PROCEDURE · p. 15

B COMPLETE GRAMMAR-ADAPTER RESULTS

• The grammar-adapter appendix reports evaluated questions using the released substring exact-match scorer, while Tables 5 and 6 identify pooled and non-overflow result scopes.Table 5 covers 800 questions under one frozen Qwen3.5-4B reader; Table 6 covers 6K–64K histories and omits truncated 262K raw-history prompts.Source: B COMPLETE GRAMMAR-ADAPTER RESULTS · p. 15, Table 5 · p. 16, Table 6 · p. 16

B.1 COMPLETE ABLATION GRID

• On 600 non-overflow questions, CMC, latest state, stale closure, and raw history score 85.67%, 27.00%, 15.67%, and 3.33% on multi-hop accuracy.Their descriptive multi-hop interaction contrast is 46.33 points, and the contrast remains after excluding window-truncated raw-history prompts.Source: §B.1 · p. 16
• CMC’s paired advantage is 83.00 points over the disjoint random negative control and 64.63 points over stale closure across 800 questions.Stale closure beats the negative control by 18.38 points; the passage treats stale closure and stale state as distinct arms.Source: §B.1 · p. 16

B.2 SAME-READER PORTS

• G-Walk and MeLLo receive a resolved one-value-per-key bank, not the answer or its path, under their released implementations and prompts.Their Table 5 rows use a frozen Qwen3.5-4B reader and the official FactConsolidation scorer.Source: §B.2 · p. 17

B.3 SCORING AND LABEL SENSITIVITY

• Under strict alias matching, CMC, prior read + refresh, and fact BM25 score 77.25%, 19.50%, and 13.00% on 400 multi-hop questions.The official scores are 78.25%, 21.50%, and 20.75%, respectively; the passage does not rank near-tied strict single-hop counts.Source: §B.3 · p. 17
• A screen flags 26 multi-hop reference strings among earlier values of reachable keys, so the conditional lower-bound gaps do not establish absolute accuracy.The screen requires manual adjudication; assigning all flagged items the least favorable paired scores yields lower bounds of 50.50 points over prior read + refresh and 51.00 over fact BM25.Source: §B.3 · p. 17

C IMPLEMENTATION AND EVALUATION DETAILS

• Matched comparisons use one frozen reader, prompt, decoding recipe, and immutable history; raw-history prompts in the 262K cells exceed the reader cap and are left-truncated.The grammar adapter selects active edges by largest stream position and traverses up to five hops; incomplete parsing falls back to raw history in this grid.Source: C IMPLEMENTATION AND EVALUATION DETAILS · p. 17
• Token accounting includes materialized reader input but excludes offline parsing, indexing, embedding, graph construction, and storage paid once per write.Paired contrasts use query-cluster percentile bootstrap intervals; the paper reports intervals and paired win, tie, and loss counts rather than significance tests.Source: C IMPLEMENTATION AND EVALUATION DETAILS · p. 18

D.1 ALTERNATIVE SOURCE FRONTENDS ON FACTCONSOLIDATION

• Direct LLM extraction answers 702 of 800 questions correctly, versus 709 for the grammar adapter and 694 for the hybrid; multi-hop accuracy is 78.25% versus 79.75% for the grammar adapter.The hybrid uses fewer recorded extraction resources but has lower observed answer accuracy; the extraction totals include alignment and revision work and are not steady-state serving costs.Source: §D.1 · pp. 18–19

D.2 SHARED EXTRACTION AND NATURAL-DIALOGUE READ PROTOCOLS

• The shared-extraction protocol fixes direct-LLM facts and unresolved records before constructing five evidence views for all 800 questions.CMC traverses up to five hops; the views restore source order and apply a 60,000-character evidence cap.Source: §D.2 · p. 19

D.3 READER SWAP WITH FIXED LLM EXTRACTION

• With Qwen3.5-4B on fixed extracted facts, CMC scores 96.50% and 76.50% on single- and multi-hop questions, while fact BM25 scores 96.50% and 20.50%.With Llama-3.1-8B-Instruct, CMC answers 220/400 multi-hop questions versus 46/400 for fact BM25.Source: §D.3 · p. 20

D.4 SAME-BACKBONE COMPARISON WITH SH-CONFLICT/CAR

• CMC answers 313/400 multi-hop questions versus CAR’s 243/400, improving multi-hop accuracy by 17.50 points; it answers 389/400 single-hop questions, 0.75 points below SH-Conflict’s 392/400.Paired CMC gains/losses are 79/9 on multi-hop and 1/4 on single-hop; 312 multi-hop and 395 single-hop outcomes tie.Source: §D.4 · p. 21

E BM25 AT THE CMC EVIDENCE BUDGET

• On 400 multi-hop questions, CMC is correct on 286 items where matched-budget BM25 is incorrect, while the reverse occurs on two.The matched BM25 pool never contains every CMC-selected fact on those 286 items and contains the scored answer string on 19.Source: E BM25 AT THE CMC EVIDENCE BUDGET · p. 21

F MQUAKE-MEMSTREAM: CONSTRUCTION AND VALIDITY

• MQuAKE-MemStream builds ordered pre-edit and post-edit assertion blocks from counterfactual cases, retaining released questions and answer labels.The final dataset has 798 multi-hop and 800 single-hop questions; its supplied support facts test reading a memory, not unrestricted document discovery.Source: F MQUAKE-MEMSTREAM: CONSTRUCTION AND… · pp. 21–22
• The dataset’s scores should not be compared directly with official MQuAKE scores because the constructed task tests reading supplied memories rather than the official editcount protocol.Pooling assertions can cause cases to interact; the larger 3,000-case construction alters at least one post-edit hop in 431 cases and is not used as confirmatory evidence.Source: F MQUAKE-MEMSTREAM: CONSTRUCTION AND… · p. 22

G TRAVERSAL BEFORE VALUE REFRESH

• The control traverses a constructed prior graph, then replaces selected values with current assertions, so its selected keys can differ from CMC’s.The comparison tests selection under a constructed version perturbation and complements stale closure, which holds selected keys fixed while changing their values.Source: G TRAVERSAL BEFORE VALUE REFRESH · pp. 22–23
• On multi-hop questions, CMC scores 78.25% versus 21.50% for traversal-before-refresh; among changed-key questions, scores are 76.42% and 14.91%.Both views score 97.25% on single-hop questions; the multi-hop comparison has 235 CMC-only correct answers and eight control-only answers.Source: G TRAVERSAL BEFORE VALUE REFRESH · p. 23

H TRAVERSAL DEPTH WITH FIXED EXTRACTION

• With fixed extraction, multi-hop accuracy rises from 5.50% at one hop to 54.00%, 71.75%, and 78.25% at two, three, and five hops.Mean reader inputs rise from 115.29 to 184.64 tokens across those caps; single-hop accuracy changes little, from 96.75% to 97.25%.Source: H TRAVERSAL DEPTH WITH FIXED EXTRACTION · p. 23

I FOUR-COMPETENCY EVALUATION PROTOCOL

• The full-suite population has 1,000 accurate-retrieval, 700 test-time-learning, 171 long-range-understanding, and 200 fact-consolidation questions across 14 source datasets and 130 histories.Overall performance averages four competencies; within TTL, classification datasets are averaged before classification and recommendation are averaged together.Source: I FOUR-COMPETENCY EVALUATION PROTOCOL · p. 23
• Of 1,961 card-frontend batches, 120 pass completely, 1,027 partially, and 814 yield no cards, mainly because their JSON cannot be parsed.The parser retains 20,640 quote-checked cards; absent cards trigger marked original-excerpt fallbacks for summary reads, and these counts do not measure semantic completeness.Source: I FOUR-COMPETENCY EVALUATION PROTOCOL · p. 24
• Accurate retrieval and recommendation use BM25 over fixed 2,048-character source windows with 256-character overlap, selecting up to 24 windows from 64 candidates under a 60,000-character budget.LongMemEval sessions after the question’s Current Date are omitted; the same window selector is used for the main accurate-retrieval and recommendation columns.Source: I FOUR-COMPETENCY EVALUATION PROTOCOL · p. 24
• The full campaign records 37.62 million tokens for shared source processing, 27.99 million for CMC reader requests, and 2.38 million for CMC evaluation judgments.The totals exclude unavailable failed-attempt usage, offline embedding, and inherited SF extraction.Source: I FOUR-COMPETENCY EVALUATION PROTOCOL · p. 24
• The comparison uses released scoring functions and HY4 judgment prompts for LongMemEval and summarization, making it a matched comparison rather than a reproduction of original generation and judge models.EventQA uses substring exact match, while the matched DetectiveQA column uses a registered JSON-field decoder.Source: I FOUR-COMPETENCY EVALUATION PROTOCOL · pp. 24–25
• Decoded DetectiveQA exact match is 76.06 for history suffix, 77.46 for BM25, 78.87 for dense+BM25, and 67.61 for CMC; native exact match is zero in all four arms.The main-table DetectiveQA cells use decoded scores, with all 71 items per arm retained in the denominator.Source: I FOUR-COMPETENCY EVALUATION PROTOCOL · p. 25
• On 100 summary questions, 12 history-suffix and 73 CMC outputs have invalid judgments; affected items score zero after unparseable precision judgments at the 4,096-token cap.CMC summaries exceed the requested 1,200-word limit on 76 items, versus 16–23 for other arms, and 20 CMC reader outputs reach their generation cap.Source: I FOUR-COMPETENCY EVALUATION PROTOCOL · p. 25

J RUNTIME AUDIT

• At 262K, CMC and BM25 read medians are close, but CMC has a higher 95th percentile; these measurements do not establish a CPU latency advantage.Recorded HY4-preview request durations are descriptive, not a controlled latency comparison, and are not a full end-to-end wall-clock cost.Source: J RUNTIME AUDIT · p. 26