Contextual Memory Virtualisation: DAG-Based State Management and Structurally Lossless Trimming for LLM Agents

AI summary

Overview

Research area: Software engineering for LLM-based agents, specifically context-window and session-state management (arXiv category cs.SE).

Technical level: Intermediate. The paper assumes familiarity with LLM context windows, tool-use schemas, prompt caching, and version-control concepts such as DAGs and branching, though the algorithms themselves are described at a level a working developer can follow.

Scope: The paper proposes contextual memory virtualisation (CMV), a system that treats accumulated LLM session understanding as version-controlled, snapshottable state organised as a Directed Acyclic Graph, paired with a three-pass trimming algorithm that removes mechanical overhead from conversation logs while preserving all user and assistant messages verbatim.

What This Paper Is About

Long LLM coding sessions accumulate valuable state inside the context window: architecture maps, trade-off decisions, and codebase conventions. When the window fills, native compaction summarises that state away (in one observed case, from 132k tokens of message state down to 2.3k, a 98% reduction), forcing each new session to rebuild understanding from scratch.

The paper's goal is to stop paying that rebuilding cost repeatedly. It reframes conversation history as a persistent, reusable resource that can be snapshotted, branched, and trimmed without losing conversational content, and it checks whether that trimming still pays off economically once prompt caching is taken into account.

Key Contributions

1. A DAG-based state model for LLM context. Session history is formalised as a graph where nodes are immutable snapshots of a session's JSONL conversation log and edges are branches forked from a snapshot. Four primitives are defined: Snapshot, Branch (with optional trimming and an optional orientation message), Trim (a composition of Snapshot and Branch), and Tree (a git log --graph-style visualisation). A snapshot may carry a parent, producing a lineage chain where each snapshot inherits the cumulative understanding of all ancestors.

2. A three-pass structurally lossless trimming algorithm. The trimmer preserves every user message, every assistant response, and every tool request verbatim while stripping tool results over a stub threshold, base64 image blocks, non-portable thinking blocks, file-history and queue-operation metadata, and API usage metadata. Pass 1 detects compaction boundaries by cheap string matching, Pass 2 collects pre-boundary tool_use IDs, and Pass 3 performs the filtering.

3. Orphaned tool result handling for API correctness. Because native compaction often places its boundary between a tool invocation and its result, discarding pre-boundary content leaves tool_result blocks referencing missing tool_use blocks, which causes API validation errors. The algorithm silently discards any tool_result whose tool_use_id belongs to the pre-boundary set collected in Pass 2.

4. An economic evaluation under prompt caching. The paper derives a cost model for cache hit rate h, cold-cache penalty, per-turn savings, and a break-even turn formula, then evaluates it across 76 real-world coding sessions. A reference implementation targeting Claude Code is released at github.com/CosmoNaught/claude-code-cmv, and the authors state the DAG model and trimming architecture are agent-agnostic.

Main Findings

• Trimming reduces tokens by a mean of 20% and up to 86%. Across the 76 qualifying sessions, token reduction had a minimum of 0%, a median of 12%, a mean of 20%, and a maximum of 86%.

• Savings concentrate in sessions with heavy mechanical overhead. Mixed sessions (tool result bytes at 15% or more of total JSONL bytes) numbered 12 and averaged 39% reduction (median 33%), reaching a mean break-even of 10 turns with a mean context of 97k tokens. Conversational sessions (under 15%) numbered 64 and averaged 17% reduction (median 10%), with a mean break-even of 40 turns and a mean context of 82k tokens.

• Break-even is fast under prompt caching at h = 0.9. Overall, break-even was 1 turn at minimum, 38 turns at median, 35 turns on average, and 60 turns at maximum (capped at 60 as a practical planning horizon). Sessions above 30% reduction reach break-even within 15 turns.

• Cache miss penalties are modest. The one-time penalty ranged from −$0.02 at minimum (when a trimmed session's cold-cache cost is below the pre-trim steady-state cost) to $0.82 at maximum, with a median of $0.32 and a mean of $0.30, under Opus 4.6 pricing of $5.00 per million base input tokens, $6.25 cache write, and $0.50 cache read.

• Two distinct reduction modes exist. The highest-reduction sessions (60–86%) are driven primarily by pre-compaction history skipping rather than tool result stubbing, while mixed-profile sessions benefit from tool output and metadata stripping.

• A representative session shows the cost crossover. Cumulative input cost curves for a session with 46% reduction diverge after the cold-cache first turn, breaking even at turn 6.

• The dominant benefit may be context rebuilding, not trimming. The mean session in the corpus holds 84k tokens of accumulated state; rebuilding it from a blank session is reported to take 10–20 user turns and 15–30 minutes of wall-clock time. Branching from a snapshot instead loads the full prior context in one prompt at $0.53 at cache-write rates for an 84k-token session, dropping to $0.04 on subsequent cache hits.

• Byte-to-token estimation overstates gains for image-heavy sessions. The benchmark derives tokens from bytes via a chars/4 heuristic plus a fixed system overhead; the API charges a fixed vision-token cost of approximately 1,600 tokens independent of base64 encoding size, so image-heavy sessions are overestimated while text-dominated sessions (the majority of the corpus) are unaffected.

Methodology in Plain English

The authors start from an analogy: an operating system hides limited physical RAM behind virtual memory, and CMV hides limited context windows behind saved, swappable conversation state. They formalise session history as a graph of snapshots and branches, defining operations that copy a conversation log to immutable storage, fork it into a new session with a fresh identifier, and render the resulting lineage.

For the trimmer, they inspect real session logs and observe that most of the window is consumed by mechanical artefacts (raw file dumps returned as tool results, base64 images, thinking-block signatures, file-history metadata) rather than by the conversation. The model's own synthesis of those artefacts lives in assistant response blocks, which are a small fraction of total tokens — so removing the raw dumps while keeping the synthesis should be safe. The algorithm makes three sequential sweeps over the JSONL log: one to find the last compaction boundary without parsing every line, one to collect tool IDs from before that boundary, and one to apply trim rules and write the output. Outputs over a 500-character threshold (minimum 50, configurable) are replaced with a stub reading [Trimmed: ~N chars], except for whitelisted metadata fields like file_path and command, so the model still knows what was read and run.

For evaluation, the authors scanned one user's Claude Code installation running Claude Opus 4.6 over a three-month period, excluding internal subagent sessions and sessions with fewer than 10 messages or 5,000 tokens, leaving 76 qualifying sessions. They built a cost model incorporating cache read and write prices, treated the first post-trim turn as a cold-cache penalty, and computed the turn at which accumulated per-turn savings recover that penalty. They report the model with a steady-state cache hit rate of h = 0.9 and note that break-even scales linearly across pricing tiers.

Why This Matters

This work argues that context ephemerality is a tooling-layer problem that can be addressed now, rather than something requiring model-level breakthroughs or ever-larger context windows. It reframes context from ephemeral session data into a version-controlled resource with branching, lineage, and reuse patterns — a shift that also supplies empirical evidence for a gap the authors identify in agent operating system designs such as AIOS, which they say handles snapshot and restoration within a single agent lifecycle but not named branching points, DAG lineage, or conversationally lossless trimming.

Real-world applications:

• Long-running coding agents. A developer spends 40 minutes generating 80k tokens of architectural understanding, snapshots it as a stable root, and spawns independent parallel branches for authentication work, API refactoring, or performance tuning without repeating the context-building phase.

• Multi-day agentic tasks. As agents are deployed for increasingly complex, multi-day work, routinely discarding hours of accumulated context at window limits becomes an unacceptable overhead.

• Flat-rate subscription users. For these users, trimming yields no direct financial saving but acts purely as context window optimisation, extending effective session length because the reduced per-turn token footprint depletes rate limits less rapidly.

• Agent operating system design. The DAG state model and trimming algorithm are offered as a possible reference implementation for a persistent context subsystem in an AIOS-style architecture.

Industry relevance: for API-key users, the analysis suggests the prompt-cache invalidation penalty is recovered within a small number of turns, making trimming economically viable; the reference implementation targets Claude Code, though the authors state the design is agent-agnostic for any system that stores conversation logs and uses tool-call schemas.

Future Directions

• Controlled accuracy comparisons. The paper states it has not quantified the impact of trimming on downstream reasoning accuracy. Future work listed includes comparing trimmed versus untrimmed branches given identical follow-up tasks to measure any reasoning degradation, and the authors note the algorithm is structural rather than semantic — removing content blindly by type, with the risk that the model hallucinates a stripped tool result or requests a re-read.

• Multi-user evaluation. The current evaluation is a single-user case study, and results may not generalise across usage patterns, codebases, or programming styles.

• Adaptive trim thresholds. Future work proposes using auto-trim log data to inform thresholds informed by actual usage.

• Integration into an agent OS. Exploring how the DAG state model and trimming algorithm could serve as a reference implementation for a persistent context subsystem in an AIOS-style architecture.

• Improved token accounting. The byte-to-token estimation overestimates reduction for image-heavy sessions, pointing to a need for more accurate accounting of vision-token costs.

Target Audience

Developers building LLM agent tooling and session management, particularly those working with Claude Code or similar tool-use APIs; software engineering researchers studying agent architectures and context management; and designers of agent operating systems who need to specify how persistent conversational state is stored, branched, and reused. It is most useful to readers already comfortable with context windows, tool-call schemas, and prompt caching, and least useful to those seeking results on downstream reasoning quality, which this paper explicitly does not measure.

Authors’ abstract

As large language models engage in extended reasoning tasks, they accumulate significant state -- architectural mappings, trade-off decisions, codebase conventions -- within the context window. This understanding is lost when sessions reach context limits and undergo lossy compaction. We propose Contextual Memory Virtualisation (CMV), a system that treats accumulated LLM understanding as version-controlled state. Borrowing from operating system virtual memory, CMV models session history as a Directed Acyclic Graph (DAG) with formally defined snapshot, branch, and trim primitives that enable context reuse across independent parallel sessions. We introduce a three-pass structurally lossless trimming algorithm that preserves every user message and assistant response verbatim while reducing token counts by a mean of 20% and up to 86% for sessions with significant overhead by stripping mechanical bloat such as raw tool outputs, base64 images, and metadata. A single-user case-study evaluation across 76 real-world coding sessions demonstrates that trimming remains economically viable under prompt caching, with the strongest gains in mixed tool-use sessions, which average 39% reduction and reach break-even within 10 turns. A reference implementation is available at https://github.com/CosmoNaught/claude-code-cmv.