Technical Summary: S3Mem – Structured Spatiotemporal Scene-Event Memory for Long-Horizon Interactive Question Answering

1. Problem Statement

Long-horizon interactive agents accumulate extensive trajectory histories but frequently fail to answer questions regarding earlier events. The paper argues that the primary bottleneck is not merely context length, but the trajectory-to-answer interface of long-term memory.

Current approaches typically externalize trajectory history as plain-text chunks and retrieve top-$k$ snippets using standard Retrieval-Augmented Generation (RAG). While effective for short contexts, this "flat" approach fails in long-horizon settings for three reasons:

1. Structural Erasure: Writing trajectories as flat text destroys the scene, event, state, and temporal structure required for downstream reasoning.
2. Chain-Incomplete Retrieval: Surface-similarity-based retrieval often returns locally relevant snippets that lack the global chain completeness needed for multi-hop reasoning (e.g., "What happened two steps after the second visit?").
3. Inefficient Evidence Exposure: The answer stage receives long, unstructured fragments, forcing the model to reconstruct the evidence chain itself, which is token-inefficient and error-prone.

The core challenge is defined as an episodic evidence-construction problem: how to write, retrieve, and expose the right structured evidence from an agent's own trajectory under a strict token budget.

2. Methodology: S3Mem

S3Mem is a structured scene-event episodic memory framework designed to convert long agent trajectories into a compact, query-aligned evidence chain. It operates through four distinct stages:

2.1 Structured Scene-Event Write

Instead of flattening history into generic text, S3Mem writes each interaction step (or local segment) as a structured memory unit.

• Schema: Each unit $m_t$ contains specific fields: step index ($t$), action ($a_t$), salient objects ($O_t$), local event types ($E_t$), relations ($R_t$), local state/inventory ($S_t$), location/spatial context ($L_t$), and a short raw summary ($u_t$).
• Environment Adaptation: The schema varies by environment (e.g., emphasizing spatial relations in Crafter vs. inventory and item gains in ALFWorld), but always preserves the joint representation of scene, event, state, and temporal context.

2.2 Anchor-Sensitive Retrieval

S3Mem moves beyond surface similarity by performing anchor-sensitive retrieval. It explicitly extracts an anchor tuple $A(q)$ from the question, comprising:

• Target-step anchors: Directly referenced steps.
• Occurrence anchors: Specific occurrences (e.g., "second visit," "last time").
• State-transition anchors: Key events like item gains or location changes.

Retrieval proceeds in two stages:

1. Initial Search: Standard text-based candidate search.
2. Anchor-Aware Reranking: Candidates are re-ranked using a scoring function that prioritizes units with high anchor compatibility ($s_{anchor}$) and local chain support ($s_{chain}$), not just lexical similarity ($s_{text}$). This ensures the retrieval of the full evidence chain surrounding a specific anchor.

2.3 Token-Budget-Aware Evidence Interface

To address efficiency, S3Mem constructs a compact evidence interface under a fixed token budget $B$.

• Packing Strategy: A greedy packing algorithm selects units based on priority: (1) anchor-bearing steps, (2) minimal local neighborhoods required to support temporal offsets or state transitions, and (3) missing state facts.
• Differentiation: Unlike generic summarization, this stage does not compress arbitrarily; it preserves the decisive evidence chain while discarding chain-redundant or chain-irrelevant units.

2.4 Answer-Time Layer

The system exposes this compact, structured evidence set to a frozen answer-time layer. The paper evaluates this under a "current frozen answer-time protocol," treating S3Mem as a structured memory interface rather than a full end-to-end agent operating system.

3. Key Contributions

1. Methodological: Introduction of S3Mem, a unified framework for structured writing, anchor-sensitive retrieval, and budget-aware evidence exposure tailored for long-horizon interactive QA.
2. Empirical: Establishment of a stronger accuracy–efficiency frontier across four environments (Crafter, Jericho, ScienceWorld, ALFWorld). S3Mem consistently outperforms Vanilla RAG and Graph-NoReader while using significantly fewer evidence tokens.
3. Interpretative: A bounded claim that the performance gain stems from the structured evidence harness (write + retrieve + pack) rather than generic memory storage or increased context length alone. This is validated through extensive controls including recent baselines (A-MEM, MemoryOS, LightMem), write-side ablations, and generic compression checks.

4. Experimental Results

The evaluation spans internal headline environments (Crafter, Jericho) and out-of-family environments (ScienceWorld, ALFWorld).

• Accuracy vs. Efficiency: S3Mem achieves higher Exact Match (EM) scores than Vanilla RAG and Graph-NoReader while consuming dramatically fewer evidence tokens.
  • On Crafter, S3Mem (EM $\approx$ 0.72) outperforms Graph-NoReader (EM $\approx$ 0.70) with ~140 tokens vs. ~1600+ tokens.
  • On ALFWorld, S3Mem shows strong accuracy and efficiency gains over all baselines.
  • On ScienceWorld, S3Mem matches the accuracy of Graph-NoReader while using a fraction of the tokens, demonstrating efficiency generalization.
• Comparison with Recent Baselines: Adapted versions of A-MEM, MemoryOS, and LightMem improve upon Vanilla RAG in some settings but fail to match S3Mem's overall frontier.
• Ablation Studies:
  • Write-Side: Full scene-event writing significantly outperforms variants using only events, objects, or plain chunks, confirming the necessity of joint structural representation.
  • Anchor Sensitivity: Removing anchor recovery ("no_seed") causes the largest performance drop, identifying anchor retrieval as the core driver of accuracy.
  • Generic Compression: Controlled RTK-style compression (generic text shrinking) fails to preserve the evidence chain, causing accuracy to collapse on complex families (multi-hop, temporal offsets) even at similar token costs.
• Robustness: The method remains robust across four different rollout actor families in Crafter, maintaining a low-token, high-accuracy regime compared to high-cost baselines.
• Out-of-Family Transfer: On ATM-Bench (a personalized memory archive), S3Mem remains competitive with significantly lower token usage, though the ranking is less dominant than in interactive environments.

5. Claims and Significance

The paper maintains a modest and bounded scope regarding its claims:

• Primary Claim: Under the current frozen answer-time protocol, structured write and anchor-sensitive evidence routing provide a stronger accuracy–efficiency frontier for long-horizon interactive QA than generic memory interfaces (plain-text RAG, graph-only retrieval, or generic compression).
• Limitations & Boundaries:
  • The paper does not claim full protocol independence. The fairness analysis shows that gains are coupled to the answer-time layer; a "generic" answerer collapses performance for all methods, while a "gold_executor" does not perfectly reproduce the ranking.
  • The contribution is framed as a structured evidence harness, not a general agent operating system. The goal is to improve the trajectory-to-answer interface for episodic QA, not to solve all agent memory challenges.
  • The strongest remaining source of non-generality lies in the answer-time consumption rather than the memory representation itself.

Conclusion: The paper posits that for long-horizon agents, the key to memory is not exposing more history, but exposing the right structured evidence. S3Mem demonstrates that converting trajectories into structured scene-event units and retrieving them via anchor-sensitive logic yields a superior trade-off between reasoning accuracy and token efficiency.