What Is Agent Memory? Definition, Storage, and Performance Prediction

Memory ability (the capacity to store and recall information) is required by large language model (LLM) and reinforcement learning (RL) agents to complete complex tasks. While episodic and semantic memory are widely recognized as critical by psychology, neuroscience, and AI researchers, current analysis of LLM agents primarily describes the typical content stored in each type. However, analyzing content alone fails to capture the structural constraints that dictate deployment success. To address this, we propose a theory of episodic and semantic memory for AI agents, detailing the time and space complexity constraints of each. We prove that these memory types require fundamentally different storage structures with opposing efficiency requirements; for instance, simultaneously supporting fast ($O(1)$) look-up for episodic tasks and minimal ($O(H(A))$) space complexity for semantic tasks is mathematically impossible. Applying this theory, we analyze six popular memory mechanisms (including RAG, long-context transformers, and graph-based memory), categorizing their task-specific performance to provide practitioners with a tool for predicting deployment success and making efficient design choices. Finally, a meta-analysis of existing benchmarks demonstrates that correctly matching the memory mechanism to the task's requirements explains 11% of performance variance.