GAAMA: Graph Augmented Associative Memory for Agents

1. Problem Statement

AI agents interacting with users across multiple sessions require persistent long-term memory to maintain coherent, personalized behavior. Existing approaches suffer from significant limitations:

• Flat RAG (Retrieval-Augmented Generation): Relies solely on embedding similarity, losing the structural relationships between entities, events, and facts across different conversations.
• Full-Context Approaches: Feeding entire history into the LLM is computationally expensive and does not scale.
• Existing Graph Methods (e.g., HippoRAG): While they use graphs, they are often entity-centric. In multi-session data, recurring entities (like "the user") accumulate hundreds of edges, creating "mega-hubs." This causes Personalized PageRank (PPR) mass to distribute uniformly, diluting retrieval precision.
• Non-Graph Methods (e.g., A-Mem, Nemori): Rely on vector similarity without graph-based relevance propagation or fail to capture associative structures effectively.

2. Methodology: GAAMA

GAAMA proposes a concept-mediated hierarchical knowledge graph constructed via a three-step pipeline, followed by a hybrid retrieval mechanism.

A. Three-Step Knowledge Graph Construction

The system processes conversation sessions into a typed graph with four node types and five edge types:

1. Episode Preservation (No LLM): Raw conversation turns are stored verbatim as Episode nodes. They are linked sequentially via NEXT edges. This preserves exact wording and temporal references (e.g., "yesterday") crucial for temporal reasoning.
2. Fact & Concept Extraction (LLM):
   • Facts: Atomic assertions distilled from episodes (e.g., "User painted a sunset"). Linked to source episodes via DERIVED_FROM edges.
   • Concepts: Topic-level labels (e.g., pottery_hobby, camping_trip) rather than specific entity names. These act as cross-cutting traversal paths.
   • Edges: HAS_CONCEPT (Episode $\to$ Concept) and ABOUT_CONCEPT (Fact $\to$ Concept).
   • Innovation: Using Concept Nodes instead of Entity Nodes avoids the "mega-hub" problem, resulting in a graph ~30x sparser.
3. Reflection Synthesis (LLM): Higher-order insights (e.g., "User prefers outdoor activities on weekends") are synthesized from multiple facts. These Reflection nodes are linked via DERIVED_FROM_FACT edges, enabling cross-session inference.

B. Hybrid Retrieval Mechanism

Retrieval combines semantic similarity with graph traversal using an additive scoring function:

1. Candidate Generation: A broad pool of nodes is retrieved via cosine similarity (KNN) to the query.
2. Graph Expansion: Starting from top-$k$ seeds, the system expands outward (depth $d=2$) to discover structurally connected nodes (e.g., facts linked to an episode, or related episodes via a shared concept).
3. Edge-Type-Aware PPR: Personalized PageRank is run on the local subgraph with specific transition weights based on edge types (e.g., NEXT and HAS_CONCEPT have higher weights than DERIVED_FROM_FACT).
   • Hub Dampening: A mechanism scales down outgoing weights for high-degree nodes to prevent mass dilution.
4. Additive Scoring: The final score is a weighted sum:
   $$\text{score}(n) = w_{ppr} \cdot \text{ppr}(n) + w_{sim} \cdot \text{sim}(n, q)$$
   • Default weights: $w_{ppr} = 0.1$, $w_{sim} = 1.0$.
   • Design Principle: Graph traversal acts as a "tiebreaker" and neighborhood expander to augment, not override, semantic similarity.

C. Memory Packing

Retrieved nodes are bucketed by type (Facts, Reflections, Episodes) with specific budget caps (e.g., max 60 facts, 20 reflections) to ensure the answer-generation LLM receives a diverse mix of information, preventing raw episodes from dominating the context window.

3. Key Contributions

1. Concept-Mediated Graph Schema: A novel graph design that replaces entity-centric hubs with distributed topic-level concept nodes, solving the "mega-hub" problem in multi-session memory.
2. Hierarchical Memory Construction: A pipeline that preserves raw context (Episodes), distills atomic knowledge (Facts), and synthesizes high-level patterns (Reflections), enabling both precise recall and complex reasoning.
3. Hybrid Retrieval Strategy: A method that blends PPR with semantic similarity via an additive score, demonstrating that mild graph augmentation ($w_{ppr}=0.1$) consistently improves retrieval without introducing noise.
4. Per-Type Budgeting: A mechanism to balance the retrieval of different memory types, ensuring facts and reflections are not displaced by high-similarity raw episodes.

4. Experimental Results

Evaluated on the LoCoMo-10 benchmark (1,540 questions across 10 multi-session conversations):

• Overall Performance: GAAMA achieved a 78.9% mean reward, outperforming:
  • Tuned RAG Baseline: 75.0% (+3.9 pp)
  • HippoRAG: 69.9% (+9.0 pp)
  • Nemori: 52.1%
  • A-Mem: 47.2%
• Category Breakdown:
  • Multi-hop (Cat1): 72.2% (Significant improvement over RAG due to fact/reflection synthesis).
  • Temporal (Cat2): 71.9% (+12.9 pp over RAG). The verbatim episode preservation and NEXT edges allow the system to resolve vague temporal references effectively.
  • Open Domain (Cat3): 49.3% (Highest among all systems).
  • Single Hop (Cat4): 87.2% (Comparable to RAG, as simple recall relies heavily on embedding similarity).
• Ablation Study:
  • Removing PPR (Semantic only) dropped performance to 78.0%.
  • This confirms that the knowledge distillation pipeline (creating Facts/Reflections) provides a +3.0 pp gain over flat RAG, while the graph traversal provides an additional +1.0 pp gain.
  • Strong PPR (weight 1.0) performed worse (74.6%), confirming that graph traversal must augment, not override, semantic relevance.

5. Significance and Future Work

• Significance: GAAMA demonstrates that for conversational agents, structure matters. By moving away from entity-centric graphs to concept-mediated ones and combining hierarchical memory distillation with hybrid retrieval, agents can maintain coherent, personalized behavior over long, multi-session interactions.
• Limitations & Future Directions:
  • Concept Canonicalization: Current LLM extraction sometimes creates near-duplicate concepts (e.g., singular/plural variants), fragmenting the graph.
  • Adaptive Gating: Developing a model to predict when graph traversal is beneficial (especially for Open Domain questions where PPR shows high variance).
  • Learned Edge Weights: Replacing hand-tuned edge weights with values optimized via backpropagation through the PPR computation.

In conclusion, GAAMA establishes a new state-of-the-art for long-term memory in AI agents by effectively balancing semantic retrieval with structural reasoning.