OPEN-DAG: Bounded Active-State and Version-Aware Execution Memory for Long-Horizon LLM Agents

Abstract

A long-running agent accumulates an execution history that branches, fails, and rolls back. This conflates two questions: how to keep the model-visible active state bounded as history grows, and whether a retrieved historical state is still valid for the current execution branch. We present OPENDAG, an execution-state substrate that stores history as an immutable directed acyclic graph on a graph database, keeps a byte-bounded active cache, recovers from failure by a versioncontrol HEAD reset, and applies a deterministic, retrieverindependent execution-validity filter to retrieved state. On one frozen implementation: (i) the active window is independent of execution depth by construction, whereas a transcript crosses a configured 32k context-window limit near depth 40; (ii) recovery latency does not grow with depth (0.28 ms in memory over N=10. . .5000, 16.6 ms against live ArangoDB, versus a transcript rewrite reaching a 371 ms median); (iii) across three retrievers and seven model families and sizes (2–32B), removing executioninvalid nodes drives invalid contamination to zero and raises task success in every retriever×model cell (paired McNemar p < 10−3; risk-difference +0.10 to +0.24), the effect saturating by 14B, while an adversarial relevant-but-invalid lure defeats relevance-only retrieval for every retriever and model. We prove the filter sound and complete relative to the version-control state, and among contemporary memory baselines (transcript, slidingwindow, RAG, extractive-summary, Mem0-style) only OPENDAG both excludes invalid state and keeps the valid answer. The filter is a safety guarantee, not a universal accuracy gain: where a reversion is legible in the text, even small models reason around it. We withhold the broader bounding claims,constant process memory, a global context bound under concurrency, anO(1) rollback class, universal superiority over retrieval that measurement did not support.