STRATA: Spatiotemporal Alignment of Agentic Memory for Long-Horizon Preference Tracking

Large language model assistants increasingly maintain relationships with users across months or years, yet most memory systems still treat personalization as a retrieval problem. This framing fails when a user's preferences change over time, and the turns most semantically similar to a query are no longer the correct value. We argue long-term memory should instead be framed as a state inference problem by computing the value of an attribute at a given time from its past states. We present STRATA, a memory architecture organized into three complementary layers (Spatial, Temporal, and Spatiotemporal) that create a single traversable graph via casual and relational edges. Preferences are stored as evolutionary chains, mapping the trajectory of its value over time. At inference time, an LLM agent traverses the memory graph with tool calls both within and across layers to intelligently retrieve relevant context. On PersonaMem, STRATA attains a new SOTA of 61.6% accuracy compared to six baselines, and a second-best on LongMemEval of 86.4% overall, driven by a 6.8-point margin on multi-session recall questions. Tool call analysis reflects the agent exhibiting emergent routing based on dataset and question type. Controlled ablations show the memory representation is crucial for preference tracking questions, and that agentic, query-conditioned traversal at inference time - a property unique to STRATA - drives meaningful gains.