A Multi-Domain Evaluation of Scaling in a General Episodic Memory

Nate Derbinsky, Justin Li, John E. LairdAAAI 2012 · DOI

Introduction

For artificial agents to achieve true autonomy and longevity, they require an episodic memory (EM)—a task-independent record of past experiences. However, as an agent operates over days or weeks, its memory grows significantly. A primary challenge in cognitive architecture is ensuring that memory retrieval does not slow down linearly with the number of stored episodes, which would eventually cause the agent to lose its "reactivity"—the ability to respond to environmental stimuli in real-time.

This paper evaluates the episodic memory implementation within the Soar cognitive architecture, demonstrating that it can maintain real-time performance (under 50ms) across diverse domains, including robotics, gaming, and linguistics, even when managing millions of episodes.

Architectural Approach

The researchers leverage several key architectural assumptions to optimize memory scaling:

  • Graph-Based Representation: Working memory is treated as a connected directed graph, allowing for complex relational data storage.
  • Temporal Contiguity and Structural Regularity: The system assumes the environment changes incrementally and that representational structures are frequently reused. This allows for efficient indexing using a "Working Memory Graph" (WMG) that tracks temporal intervals for edge changes rather than storing redundant full states.
  • Two-Phase Cue Matching: Retrieval involves a low-cost "surface match" to identify potential episodes based on features, followed by a more intensive "structural match" to verify relational constraints.

Experimental Evaluation

The system was tested across four distinct areas to assess its general-purpose utility:

  1. Linguistics: Word Sense Disambiguation using the SemCor corpus (4.6 million episodes).
  2. Generalized Planning: 12 standard planning domains (e.g., Blocksworld, Hanoi) across 44 problem instances.
  3. Video Games: Environments including TankSoar, Eaters (PAC-MAN-like), and Infinite Mario.
  4. Mobile Robotics: A simulated office-exploration task spanning the equivalent of over three days of continuous operation (634 million episodes).

Key Results and Scaling Performance

In nearly all tested domains, the system successfully maintained reactivity. Storage costs remained low, correlating with the rate of change in working memory rather than the total memory size. For example, in planning domains, the system could manage up to 91 million episodes within 48GB of RAM.

Maximum cue-matching time remains stable and well below the 50ms reactivity threshold as the number of stored episodes grows to over 100 million.

As shown in the scaling data, the maximum cue-matching time typically plateaus or grows very slowly, staying well within the 50ms limit required for real-time interaction. The specific performance metrics across different gaming and robotics tasks further highlight the efficiency of the storage and retrieval mechanisms.

Performance metrics across gaming and robotics domains, highlighting storage efficiency and the impact of cue selectivity on retrieval time.

The Importance of Selectivity

The research identifies "selectivity" as the critical factor for performance. Retrieval speed depends on how unique a cue is within the temporal record. If a cue is too common (low selectivity), the search space expands, leading to potential slowdowns. This was observed in linguistics tasks where certain word sequences (4-grams) hit scaling limits because they required traversing too many temporal intervals.

Insights and Limitations

While the system excels at retrieving specific past events, it is not a replacement for general-purpose analogical reasoning. The researchers found that "direct analogy"—finding similar states without grounded features—is computationally expensive. However, performance scales perfectly when the agent uses "recognition knowledge" to mark important patterns in memory, which can then be queried efficiently.

Future work will focus on handling "unselective" cues that currently cause linear slowdowns and better integrating task-dependent recognition with task-independent episodic storage.

Summary updated

BibTeX
@inproceedings{derbinsky2012multi,
  author = {Nate Derbinsky and Justin Li and John E. Laird},
  title = {{A Multi-Domain Evaluation of Scaling in a General Episodic Memory}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2012},
  doi = {10.1609/aaai.v26i1.8151},
}
Figure