Skip to main content
Back

NUS's MRAgent Beats Every Memory Baseline by Reasoning While It Retrieves

MRAgent replaces static memory retrieval with an iterative graph-traversal loop, cutting token costs by 5x while beating all baselines by up to 23% on long-conversation benchmarks.

  • MRAgent replaces one-shot memory retrieval with an iterative LLM-guided graph traversal loop, letting the agent update its search strategy based on evidence found mid-query.
  • Memory is stored as a Cue-Tag-Content graph with two layers: episodic (concrete events) and semantic (stable personal facts), connected via short associative tags that guide traversal.
  • On LoCoMo, MRAgent scores 84.21 vs. 68.31 for the best baseline (Mem0) -- a 23.3% relative gain; on LongMemEval, a 32% relative improvement.
  • Token cost is 5x lower than the closest graph-based competitor (118k vs. 632k tokens per sample on LongMemEval), with faster runtime than most baselines.
  • The paper includes a formal proof that active retrieval policies are strictly more expressive than passive ones for any retrieval budget of two or more steps.
  • Code is open-source on GitHub; the framework is model-agnostic and was tested with Gemini-2.5-Flash and Claude-Sonnet-4.5 backbones.

Every serious LLM agent eventually hits the same wall: the conversation grows long, the relevant facts are buried dozens of turns back, and a single similarity search just doesn't cut it. A new paper from the National University of Singapore, accepted at ICLR 2026, argues the whole retrieval paradigm is wrong -- and proposes a fundamentally different model inspired by how human memory actually works.

The paper introduces MRAgent (Memory Reasoning Agent), a framework that treats memory access as an active, iterative reconstruction process rather than a one-shot lookup. The core claim: memory is never simply retrieved -- it is rebuilt, piece by piece, guided by what you've already found.

The retrieve-then-reason trap

Despite recent progress, LLM agents still struggle with reasoning over long interaction histories. Current memory-augmented agents rely on a static "retrieve-then-reason" paradigm, and this rigid pipeline design prevents them from dynamically adapting memory access to intermediate evidence discovered during inference.

The two dominant approaches both fail in predictable ways:

  • Similarity-based retrieval (RAG): Embeds the query, pulls the top-k most similar chunks. Works for simple lookups, but for a question like "What was Caroline doing when Nate won his third video game tournament?" it floods the context with every "video game" mention and misses the actual answer entirely.
  • Graph-based retrieval (A-Mem, Zep): Seeds from a similarity match, then expands N-hop neighbors. Better for relational queries, but the expansion is fixed and blind -- it pulls in irrelevant neighbors and still can't infer new retrieval cues from what it's already found.

The fundamental flaw in both is that retrieval decisions are locked in before any evidence is seen. By integrating LLM reasoning directly into memory access, active reconstruction enables the agent to infer new retrieval cues and adapt traversal strategies based on accumulated evidence -- intermediate findings can be explicitly transformed into new retrieval constraints, allowing the agent to recover evidence that is unreachable under passive policies.

Comparison of similarity-based, graph-based, and active reconstruction retrieval approaches

The Cue-Tag-Content graph

MRAgent organizes all memory into a heterogeneous graph with three node types. Think of it as a two-level index that separates "what to look for" from "what was actually said."

  • Cues: Fine-grained keywords -- entities, actions, attributes -- extracted from dialogue. These are the entry points into the graph.