PaxLabs Research
Andres G. and the PaxLabs Research Team · PaxLabs Inc.
Memory Architecture for Long-Horizon Agents: Taxonomy, Invariants, and Design Principles
Andres G. and the PaxLabs Research Team PaxLabs Inc. Correspondence: legal@paxeer.app
Modern language model agents fail in characteristic ways when tasks span hundreds of steps or days of wall-clock time. We argue that these failures are not primarily failures of reasoning but of memory. Current agent frameworks rely on context windows as their sole memory substrate, which creates a brittle architecture that loses information on compaction, provides no replay guarantees, and cannot maintain stable identity across sessions. In this paper we present a taxonomy of four memory types required for long-horizon agency (working memory, episodic memory, semantic memory, and procedural memory), state the invariants each type must satisfy for reliable operation, and articulate a set of design principles for building memory substrates that support autonomous agents over extended time horizons. We propose that persistent typed memory is not a convenience but a necessary condition for agent identity, and we outline an evaluation protocol for testing memory systems along four axes: recall fidelity, semantic drift, repair cost, and replay integrity.
episodic memory, semantic memory, retrieval-augmented generation, cognitive architectures
The rapid scaling of context windows (from 4K to 128K to 1M tokens over two years) has led many practitioners to treat the context window as the solution to agent memory. We believe this is a category error. A context window is a scratchpad, not a memory system. When an agent operating over a multi-day task hits its context limit, the standard strategies (truncation, summarization, sliding windows) all destroy information irreversibly. The agent cannot recover what it has lost, and it has no principled way to decide what to keep.
The consequences are concrete. An agent debugging a codebase across three days of work may forget a constraint it discovered on day one. An agent managing a research workflow may re-read the same papers because it has no record of prior reads. An agent maintaining infrastructure may lose track of why a particular configuration was chosen, leading to regression. These are not hypothetical failures; we observe them routinely in deployed systems.
In this paper we make three contributions:
(1) We provide a systematic taxonomy of four memory types required for long-horizon agency, drawn from cognitive science but grounded in engineering requirements.
(2) For each memory type we state explicit invariants that a memory substrate must satisfy. We show that different memory types require different invariants (append-only journaling for episodic memory, content-addressing for semantic memory, replay integrity for procedural memory) and that violating these invariants produces characteristic, predictable failures.
(3) We articulate a set of design principles for building agent memory systems and propose an evaluation protocol for testing them.
Claims we do not make: We do not claim that memory architecture alone solves agent reliability. Reasoning, planning, and tool use all matter. We claim that without proper memory architecture, improvements in reasoning and planning are capped by the quality of the agent's memory substrate. We also do not claim that our taxonomy is the only valid one; we claim it is useful and that it maps cleanly onto engineering requirements.
The distinction between short-term and long-term memory is one of the most replicated findings in cognitive psychology [1]. Atkinson and Shiffrin's multi-store model (1968) proposed three stores (sensory register, short-term store, and long-term store) with distinct encoding and decay properties. This model, while refined substantially over the decades, has proven durable because it captures a real architectural difference: some memories are transient buffers and others are persistent stores with different access patterns.
Tulving (1972) further subdivided long-term memory into episodic memory (personal experiences with temporal context) and semantic memory (general knowledge without temporal context) [2]. This distinction is not merely taxonomic; it predicts different patterns of acquisition, retrieval, and degradation. Squire (1992) added procedural memory (skills and habits) as a third long-term store with different neural substrates [3]. We draw on all three distinctions in our taxonomy, but we adapt them to the engineering constraints of agent systems.
The memory-augmented neural network (MANN) literature provides the technical foundation for external memory in neural systems. The Neural Turing Machine [4] and its successor, the Differentiable Neural Computer [5], demonstrated that neural networks can learn to read and write to external memory matrices using differentiable attention mechanisms. These systems showed that separation of computation and memory enables generalization to sequence lengths beyond those seen in training.
More recently, the Transformer-XL [6] introduced segment-level recurrence with a relative positional encoding scheme that allows information to persist across fixed-length segments. The Memorizing Transformer [7] extended standard Transformers with a kNN-augmented attention over a fixed-size external memory. These architectures address a real limitation of vanilla Transformers but they remain bounded by a fixed memory window. They do not provide the kind of persistent, structured memory that long-horizon agents require.
The current generation of LLM-based agents typically uses one of three strategies for managing memory beyond the context window:
(1) Context window management: Truncation, sliding windows, or summarization-based compression [8]. These strategies are simple but lossy. Summarization, in particular, is not invertible; once a fact has been merged into a summary, the original detail is gone.
(2) Retrieval-augmented generation (RAG): The agent retrieves relevant documents from an external store and injects them into the context window at inference time [9]. RAG systems have been shown to improve factual accuracy on knowledge-intensive tasks [10], but they require that the system know what to retrieve. For episodic memory (what happened and when), the retrieval signal is often temporal or causal, not purely semantic, which limits the effectiveness of standard embedding-based retrieval.
(3) Tool-augmented memory: The agent uses file systems, databases, or structured stores as external memory, reading and writing through tool calls [11]. This is the most flexible approach but current frameworks provide little guidance on what to store, how to index it, or what invariants to maintain.
RAG systems deserve specific attention because they are the most common approach to "memory" in deployed agent systems. The core pipeline (index documents, retrieve by embedding similarity, inject into context) was introduced by Lewis et al. [9] and has been extensively refined [10], [12].
The fundamental limitation of RAG as a memory substrate is that it treats memory as a flat collection of documents. It does not distinguish between types of memory (what happened vs. what is known vs. what the agent can do), does not maintain temporal ordering, and does not provide guarantees about completeness or consistency. A RAG system may retrieve a document about a past event but cannot guarantee that it retrieves all relevant events, nor can it distinguish between a fact the agent learned from experience and a fact it was told by the user.
RAG is a retrieval mechanism, not a memory architecture. It can be a component within a memory architecture, but it cannot substitute for one.
We identify four memory types that an agent requires for reliable long-horizon operation. Each type has distinct encoding, storage, and retrieval requirements. We name them by analogy to their cognitive science counterparts but define them in engineering terms.
Definition 1 (Working Memory). The agent's working memory is the set of tokens currently available in its context window during a single inference call. It is volatile (destroyed on session end unless externally persisted), bounded (limited by the model's context length), and sequential (ordered by position in the context).
Working memory is where the agent does its reasoning. It is the scratchpad on which the current chain of thought unfolds. Its role is analogous to registers in a CPU: fast, directly accessible, but small and volatile.
The critical property of working memory is that it is not persistent. When a session ends, the working memory is gone. Any information that exists only in working memory is lost. This is not a bug; it is a design constraint that the other memory types must compensate for.
Definition 2 (Episodic Memory). The agent's episodic memory is a chronologically ordered, append-only journal of events the agent has experienced or participated in. Each entry records what happened, when it happened, and (optionally) the context in which it happened.
Episodic memory answers the question: "What happened?" It is the record of the agent's experience. Examples include: a user asked a question, the agent ran a command and got a specific output, a file was modified, a decision was made for stated reasons.
The defining characteristic of episodic memory is temporal ordering. Events in episodic memory have a position in a sequence, and that position carries meaning. The order in which events occurred determines causation, responsibility, and context. An agent that can recall what happened but not when it happened cannot reconstruct the reasoning that led to a decision.
Episodic memory is the type of memory that current agent frameworks handle worst. When context is truncated or summarized, episodic detail is the first casualty. The specific output of a command, the exact wording of a user's request, the state of a file before modification, these are precisely the details that summarization discards.
Definition 3 (Semantic Memory). The agent's semantic memory is a store of durable facts, relationships, and knowledge that the agent has acquired through experience or instruction. Entries in semantic memory are not tied to specific events (they may have been derived from many events) and do not have inherent temporal ordering.
Semantic memory answers the question: "What is true?" Examples include: the user's preferred programming language is Python, the codebase uses pytest for testing, the deployment target is AWS, the user's name is Alice.
Semantic memory is the type most amenable to RAG-style retrieval. Facts can be encoded as embeddings and retrieved by similarity. However, semantic memory has a specific failure mode: staleness. Facts can become outdated. The user may have switched from Python to Rust. The deployment target may have changed. A semantic memory system must support not just storage and retrieval but also revision and invalidation.
Definition 4 (Procedural Memory). The agent's procedural memory is a store of learned procedures, patterns, and skills that the agent can apply to new situations. Entries in procedural memory encode how to do things, not what happened or what is true.
Procedural memory answers the question: "How do I do this?" Examples include: to set up a new Python project, create a virtual environment, add a pyproject.toml, initialize git, and write a README; to debug a failing test, read the error message, locate the test, examine the code under test, form a hypothesis, and verify.
Procedural memory is the most structured of the four types. It encodes sequences of actions that have been validated by experience. It is also the type most susceptible to silent corruption: if a stored procedure is modified incorrectly, the agent will apply a broken procedure and may not detect the failure until it has caused downstream damage.
Each memory type requires specific invariants to function correctly. We state these as properties that the memory substrate must guarantee.
Invariant 1 (Append-Only). Episodic memory is append-only. Entries are never modified or deleted after they are written. Corrections are added as new entries that reference the entry being corrected.
Rationale: If the agent (or a summarization process) can modify past entries, the temporal ordering of memory becomes unreliable. The agent cannot distinguish between what it knew at time t and what it learned later. This is the temporal analog of source code version control: you never rewrite history, you add new commits.
Invariant 2 (Temporal Ordering). Every entry in episodic memory has a monotonically increasing sequence number. The sequence number is assigned at write time and is never reassigned.
Rationale: Without strict ordering, the agent cannot reconstruct causal chains. If event A caused event B, the agent must be able to verify that A preceded B. This is not a soft preference; it is a hard requirement for reliable reasoning about past events.
Invariant 3 (Provenance). Every entry in episodic memory records its source (user input, tool output, internal decision) and the session in which it was created.
Rationale: When the agent encounters a contradiction in its memory, it needs to assess which source is more reliable. Without provenance information, all memories have equal weight, and the agent cannot perform source-level reasoning about trust.
Invariant 4 (Content-Addressing). Every entry in semantic memory is addressable by its content (via embedding similarity or hash) rather than solely by its position in a sequence or a manually assigned key.
Rationale: Semantic memory is retrieved by what it means, not by when it was stored. An agent looking for "the user's preferred testing framework" should be able to find that fact regardless of when it was learned. Content-addressing via embeddings is the natural retrieval mechanism for this memory type [10].
Invariant 5 (Revisability). Semantic memory entries can be updated or invalidated when new information contradicts them. The memory substrate must record the revision history.
Rationale: Facts change. If the semantic memory system does not support revision, it accumulates contradictions over time. The agent must be able to determine the current state of a fact and, when needed, trace the history of revisions to understand why a fact changed.
Invariant 6 (Consistency). At any point in time, semantic memory should not contain two entries that directly contradict each other without a recorded conflict resolution.
Rationale: Contradictions in semantic memory lead to unpredictable agent behavior. If memory says "the user prefers Python" and also says "the user prefers Rust," the agent's behavior depends on which fact happens to be retrieved, which is effectively random.
Invariant 7 (Replay Integrity). Every procedure in procedural memory must be replayable: given the same inputs and preconditions, executing the stored procedure must produce the same class of outcome.
Rationale: A procedure that cannot be reliably replayed is not a procedure; it is a historical anecdote. The agent must be able to trust that a stored procedure will work when applied, or it must detect the conditions under which it will not.
Invariant 8 (Precondition Specification). Every procedure must specify the preconditions under which it is valid and the expected failure modes when preconditions are not met.
Rationale: Procedures are context-dependent. A procedure for "deploy to AWS" is only valid if the environment is AWS. Without precondition specification, the agent may apply a procedure in an invalid context, producing errors or silent incorrect behavior.
Invariant 9 (Composition Tracking). When a new procedure is composed from existing procedures, the composition must record which procedures were used and how they were combined.
Rationale: If a composed procedure fails, the agent needs to identify which component failed. Without composition tracking, debugging requires re-deriving the composition from scratch, which may not be possible if the context that led to the composition has been lost.
We propose that persistent typed memory is not a convenience for agent systems but a necessary condition for agent identity. This is the central claim of this section.
Definition 5 (Agent Identity). An agent has identity if and only if it can reliably attribute its past actions to itself, distinguish its own actions from those of other agents or users, and maintain consistent behavior patterns across sessions.
Consider two agents, A and B, with identical model weights, identical system prompts, and identical tool access. Agent A has persistent episodic, semantic, and procedural memory. Agent B has only its context window.
At the start of a new session, Agent A can answer: "What did I do yesterday? What facts have I learned about this user? What procedures have I validated?" Agent B cannot answer any of these questions. It has no history. It is, in every operational sense, a different agent from the one that ran yesterday.
This is not a philosophical point. It has engineering consequences:
(1) Accountability. If an agent modifies a production system and something breaks, the ability to reconstruct what the agent did and why requires episodic memory. Without it, the agent cannot explain its past actions, and the operator cannot audit them.
(2) Continuity. If an agent is managing a multi-day workflow, it must be able to resume where it left off. This requires not just recalling the last state (which could be stored in a checkpoint) but understanding the history of decisions that led to that state (which requires episodic and semantic memory).
(3) Trust calibration. Over time, an agent with persistent memory can learn which of its procedures are reliable and which are not. An agent without persistent memory must re-calibrate from scratch each session. This is not just inefficient; it means the agent cannot learn from its own failures.
Proposition 1 (Memory-Identity Correspondence). Let M be the set of persistent memory types (episodic, semantic, procedural) maintained by an agent. The agent's operational identity is isomorphic to M in the sense that: (a) if M is empty, the agent has no operational identity across sessions; (b) if M is complete and well-maintained, the agent has a stable operational identity; (c) partial or corrupted M produces partial or corrupted identity, with predictable failure modes.
This correspondence has a practical implication: designing an agent's memory architecture is designing the agent's identity. The choice of what to remember, how to index it, and what invariants to enforce is not a storage optimization problem; it is an identity design problem.
We propose four axes along which agent memory systems should be evaluated. For each axis we define the metric, describe a testing procedure, and state a pass criterion.
Metric: The fraction of relevant memories that the system retrieves when queried, measured as recall@k over a set of known ground-truth memories.
Test procedure: (1) Seed the memory system with N known entries. (2) For each entry, construct a natural language query that should retrieve it. (3) Measure recall@k for k in {1, 5, 10}.
Pass criterion: Recall@5 >= 0.90 for semantic memory, recall@10 >= 0.85 for episodic memory (episodic recall is harder because queries are often temporal or causal, not purely semantic).
Metric: The fraction of semantic memory entries that are contradicted by the current state of the system after a sequence of updates.
Test procedure: (1) Initialize semantic memory with N facts. (2) Apply a sequence of M updates that invalidate some facts. (3) Query the system and measure the fraction of responses based on stale facts.
Pass criterion: Drift rate < 0.05 after M updates, meaning that fewer than 5% of responses rely on facts that have been invalidated.
Metric: The number of operations required to restore a corrupted memory system to a consistent state, normalized by the total number of entries.