To Know is to Construct: Schema-Constrained Generation for Agent Memory

1. Problem Statement

The paper addresses the limitations of current Long-Term Memory (LTM) systems for autonomous agents, which predominantly rely on dense retrieval (e.g., RAG, vector databases). The authors identify two critical failure modes in existing paradigms:

• Retrieval Noise (Semantic vs. Contextual Mismatch): Dense retrieval relies on semantic similarity. However, semantically similar entities often appear in different contexts. Retrieval systems frequently return contextually irrelevant entries because they cannot distinguish between "semantically identical but contextually distinct" instances.
• Structural Hallucination: An alternative approach, open-ended generative memory, allows LLMs to directly generate memory keys (indices). However, this risks Structural Hallucination, where the model generates keys that do not exist in the memory store. This leads to immediate lookup failures and catastrophic breakdowns in reasoning.

The core problem is how to enable generative memory access (leveraging LLMs' world knowledge) while guaranteeing structural validity (ensuring generated keys actually exist in the memory) and supporting associative reasoning.

2. Methodology: SCG-MEM

Inspired by Constructivist Epistemology (Piaget), which posits that knowledge is actively constructed within cognitive schemas, the authors propose SCG-MEM (Schema-Constrained Generative Memory). The architecture reformulates memory access from "retrieval" to "schema-constrained generation."

The system consists of three synergistic components:

A. Cognitive Schema (The Prefix Trie)

• Concept: The agent's valid knowledge is represented as a discrete set of concepts (keywords) organized into a dynamic Prefix Trie.
• Function: This Trie acts as a hard constraint on the LLM's decoding process.
• Mechanism: During generation, the system performs Schema-Constrained Decoding. It masks the LLM's probability distribution, assigning zero probability to any token that would lead to a path outside the Trie.
• Guarantee: This mathematically ensures that every generated memory key ($\hat{k}$) is a valid entry in the schema ($\hat{k} \in S$), providing a formal guarantee against Structural Hallucination.

B. Evolutionary Schema Construction

To handle long-term adaptation, the schema is not static. It evolves via two Piagetian processes:

1. Assimilation: When new input arrives, the system attempts to map it to existing nodes in the Trie using constrained decoding. This reinforces existing connections without altering the schema's boundaries.
2. Accommodation: If the input cannot be mapped to existing concepts (detected via high perplexity or specific tokens), the system temporarily relaxes constraints to generate novel concepts. These new concepts are then validated and inserted into the Trie, expanding the agent's epistemic boundary.

C. Associative Graph & Reasoning

While the Trie ensures existence, it is topologically flat. To enable reasoning, an Associative Graph is overlaid on the Trie nodes.

• Structure: Nodes are concepts; edges represent co-occurrence in dialogue turns.
• Weighting: Edge weights are calculated using the product of Inverse Document Frequency (IDF) values, emphasizing rare, domain-specific co-occurrences over common stop words.
• Constructive Recall Process:
  1. Schema Activation: Given a query, the LLM uses constrained decoding to generate valid "seed concepts" (entry points).
  2. Associative Propagation: Activation spreads from seed nodes to neighbors via weighted sampling (softmax over edge weights). This allows the system to retrieve contextually relevant information that is implicitly related to the query, enabling multi-hop reasoning.
  3. Context Reconstruction: The retrieved concepts are mapped back to original text segments to form the context for the final LLM response.

3. Key Contributions

1. Schema-Constrained Generation Paradigm: A novel shift from discriminative retrieval to generative access, where a dynamic Prefix Trie acts as a hard constraint to eliminate structural hallucinations.
2. Hybrid Architecture (Trie + Graph): Combines the structural safety of a Trie (ensuring valid keys) with the reasoning capabilities of a graph (enabling associative multi-hop traversal).
3. Evolutionary Mechanism: Introduces a dual-pathway update mechanism (Assimilation/Accommodation) that allows the memory system to grow adaptively while maintaining structural consistency.
4. Formal Guarantee: Provides a mathematical proof that the probability of generating a non-existent memory key is strictly zero under the proposed architecture.

4. Experimental Results

The system was evaluated on the LoCoMo benchmark, which tests long-term, multi-session agentic memory across four categories: Single-Hop, Multi-Hop, Temporal, and Adversarial.

• Performance: SCG-MEM significantly outperformed state-of-the-art baselines (including A-MEM, MemGPT, and MemoryBank) across all models (Qwen2.5 and Llama 3.2) and categories.
  • Notable Gains: On Qwen2.5 3B, it achieved a +146.7% improvement in F1 score for Single-Hop tasks and +126.6% for Multi-Hop tasks.
  • Adversarial Robustness: It showed strong resilience against misleading queries, with up to +88.6% F1 improvement, demonstrating its ability to map traps to relevant memories rather than hallucinating.
• Ablation Studies:
  • Removing the Cognitive Constraint (unconstrained generation) caused severe performance drops (e.g., -39.5% in Multi-Hop), confirming the necessity of preventing structural hallucinations.
  • Removing Evolutionary Updates (disabling assimilation) led to significant declines in Temporal and Multi-Hop tasks, proving the importance of linking new info to existing structures.
• Hyperparameter Sensitivity:
  • Retrieval Size ($k$): Performance peaked at $k \approx 35$. Too few concepts missed context; too many introduced noise.
  • Hop Depth: Hop-1 (one-step propagation) was optimal. Hop-0 (direct match) was insufficient for disjoint sessions, while Hop-2 introduced semantic drift and degraded performance.

5. Significance

This paper represents a paradigm shift in agent memory design. By moving away from the "retrieval-centric" view (treating memory as a static database to be searched) toward a "constructivist" view (treating memory as a dynamic, structured cognitive map), SCG-MEM solves the fundamental trade-off between flexibility (generation) and reliability (validity).

Its significance lies in:

• Eliminating Structural Hallucinations: Providing a formal method to ensure agents never "look up" non-existent data.
• Enabling True Long-Term Reasoning: The associative graph allows agents to bridge disjoint conversations and track evolving facts over time, a capability often lacking in standard RAG systems.
• Scalability: The approach works effectively even on smaller parameter models (1B-3B), suggesting it is a viable architectural upgrade for resource-constrained agents.

Future work directions include memory compression, hierarchical schema structures, and extending the framework to multi-modal inputs (visual/audio).