Memory is Reconstructed, Not Retrieved: Graph Memory for LLM Agents Review
0. Introduction
Memory is Reconstructed, Not Retrieved는 agent memory를 “query를 던져 top-k chunk를 가져오는 문제”로 보는 관점을 정면으로 바꾸는 논문이다. 이 논문이 제안하는 MRAgent의 핵심은 memory를 꺼내는 것이 아니라, reasoning 중에 memory를 다시 구성한다는 데 있다.
기존 memory-augmented agent는 대체로 retrieve-then-reason pipeline을 따른다. 먼저 query와 memory item의 similarity를 계산해 top-k를 가져오고, 그 다음 LLM이 가져온 evidence를 읽고 답한다. Graph memory를 붙여도 retrieval seed에서 N-hop neighbor를 확장하는 식이면 기본 구조는 크게 다르지 않다. 문제는 multi-hop, temporal, long-session query에서는 중간 evidence를 본 뒤에야 다음 retrieval cue가 생긴다는 점이다.
MRAgent는 memory access를 sequential decision process로 본다. 처음 query로 cue를 찾고, cue가 연결된 tag를 보고, tag를 통해 content를 확인한다. Retrieved content가 새로운 cue를 활성화하면 다시 graph를 따라가며 candidate path를 확장한다. 이 과정에서 LLM은 accumulated evidence를 보고 어느 branch를 계속 탐색할지, 어느 branch를 버릴지 결정한다.
한 줄 요약: MRAgent는 long-horizon agent memory를 flat top-k retrieval이 아니라 Cue-Tag-Content graph 위의 active reconstruction process로 재정의하고, query, accumulated evidence, graph traversal action을 결합해 memory access 자체를 reasoning loop 안으로 넣는 graph memory framework다.
이 논문을 지금 볼 가치가 있는 이유는 다음과 같다.
- Agent memory retrieval을 static top-k selection이 아니라 stateful exploration으로 정식화한다.
- Cue-Tag-Content graph를 사용해 fine-grained cue와 memory content 사이에 associative tag를 둔다.
- LLM reasoning을 retrieval 후처리가 아니라 traversal routing 안에 직접 넣는다.
- LoCoMo와 LongMemEval에서 strong memory baseline 대비 성능, token cost, runtime을 함께 비교한다.
- Graph memory가 왜 더 좋은가보다, graph를 어떻게 탐색해야 하는가에 초점을 둔다.
- “memory is reconstructed”라는 framing이 personalization, long-session assistant, agent experience replay에 꽤 직접적으로 연결된다.
이 글에서는 MRAgent를 단순 graph RAG 논문이 아니라, LLM agent가 memory access policy를 intermediate evidence에 따라 바꾸도록 만든 active memory system으로 읽는다.
1. Problem Setting
1-1. Problem definition
Long-horizon agent memory의 기본 문제는 다음과 같다. Agent는 긴 interaction history에서 relevant evidence를 찾아 현재 query에 답해야 한다.
External memory를 memory units $V={v_1,\ldots,v_N}$라고 하자. Query $x$가 들어왔을 때 기존 passive retrieval은 retrieval result를 query만의 함수로 정한다.
\[\{v^{(1)},\ldots,v^{(T)}\} = \pi_p(x)\]이 policy는 retrieval 전에 어떤 evidence를 볼지 모두 결정한다. 따라서 첫 retrieval result를 읽고 새 cue가 생겨도 retrieval strategy를 바꿀 수 없다.
MRAgent는 active reconstruction policy를 다음처럼 정의한다.
\[v^{(t)} = \pi_a^{(t)} \left( x, S^{(t-1)} \right)\] \[S^{(t)} = S^{(t-1)} \cup \{v^{(t)}\}\]여기서 $S^{(t)}$는 지금까지 모은 evidence state다. 즉 retrieval action이 query뿐 아니라 accumulated evidence에 의존한다.
이 차이는 작아 보이지만, memory reasoning에서는 매우 크다.
예를 들어 “Nate의 video game tournament와 같은 시기에 Caroline은 무엇을 했는가”라는 질문이 있다고 하자. 먼저 Nate 관련 memory를 찾은 뒤에야 “July”라는 temporal cue가 생길 수 있다. Passive retrieval은 처음 query에 없는 July를 retrieval key로 쓰기 어렵다. Active reconstruction은 intermediate evidence에서 July를 만들고, 이를 이용해 Caroline 관련 memory를 다시 찾을 수 있다.
1-2. Why previous approaches are insufficient
1) Similarity-based RAG
Similarity retrieval은 query와 memory item을 embedding similarity로 비교한다.
\[\pi_{\mathrm{sim}}(x) = \mathrm{TopK} \left( \{\mathrm{sim}(x,v)\}_{v \in V}, k \right)\]이 방식은 surface relevance가 강한 item을 잘 찾는다. 그러나 multi-hop query에서는 첫 item이 직접 answer를 포함하지 않을 수 있고, answer로 가는 중간 cue가 query text에 없을 수 있다.
2) Graph-based neighbor expansion
Graph memory는 similarity seed를 찾은 뒤 neighbor를 확장한다.
\[\pi_{\mathrm{graph}}(x) = V_{\mathrm{sim}} \cup \mathrm{Neighbor}(V_{\mathrm{sim}})\]이 방식은 unstructured RAG보다 낫지만, fixed N-hop expansion은 noise를 많이 가져오고, relevant evidence가 explicit graph edge로 연결되어 있지 않으면 놓칠 수 있다. 또한 expansion policy가 accumulated evidence에 따라 바뀌지 않는다.
3) Retrieve-then-reason split
기존 memory system은 retrieval과 reasoning을 분리한다. Retrieval은 LLM이 reasoning하기 전에 끝나고, LLM은 이미 선택된 evidence만 읽는다. 하지만 실제 memory recall은 중간 단서가 다음 단서를 부르는 과정에 가깝다. MRAgent는 이 split을 없애고, reasoning을 retrieval routing의 일부로 만든다.
2. Core Idea
2-1. Main contribution
MRAgent의 핵심 기여는 세 가지다.
- Active memory reconstruction
- Retrieval을 one-shot top-k selection이 아니라 multi-step decision process로 만든다.
- 각 step은 query와 accumulated evidence를 바탕으로 다음 memory traversal을 선택한다.
- Cue-Tag-Content graph
- Memory를 cue, tag, content node로 구성한다.
- Tag는 cue와 content 사이의 semantic bridge로 작동한다.
- LLM은 content를 바로 열기 전에 tag를 보고 promising path를 고를 수 있다.
- LLM-driven traversal and pruning
- Forward traversal은 Cue -> Tag -> Content 방향으로 evidence를 찾는다.
- Reverse traversal은 retrieved Content에서 새 Cue/Tag를 활성화한다.
- LLM은 accumulated evidence가 충분한지 판단하고, 불필요한 branch를 prune한다.
논문은 active retrieval hypothesis class가 passive retrieval보다 strictly more expressive하다는 이론적 statement도 제시한다. Intuition은 간단하다. Passive policy는 retrieval budget $T$를 query만으로 미리 정해야 하지만, active policy는 이전 step outcome에 따라 다음 node를 고를 수 있다.
2-2. Design intuition
이 논문의 설계 직관은 cognitive memory analogy에 있다. 사람은 memory를 database에서 exact row로 꺼내지 않는다. Contextual cue가 떠오르고, 그 cue가 관련 concept을 활성화하고, 그 concept이 다시 episodic memory를 불러오며, 여러 조각을 맞춰 coherent answer를 만든다.
MRAgent는 이 과정을 graph traversal로 바꾼다.
| Cognitive view | MRAgent component |
|---|---|
| Contextual cue | Cue node |
| Associative bridge | Tag relation |
| Episodic 또는 semantic memory | Content node |
| Recall trajectory | Reconstruction path |
| New cue from evidence | Reverse traversal |
| Stopping when enough evidence exists | LLM sufficiency check |
즉 memory는 final answer를 직접 담은 chunk list가 아니라, cue와 evidence가 단계적으로 연결되는 graph다.
3. Architecture / Method
3-1. Overview
| 항목 | 내용 |
|---|---|
| Goal | 긴 interaction history에서 adaptive memory reconstruction |
| Framework | MRAgent |
| Memory structure | Cue-Tag-Content heterogeneous graph |
| Retrieval policy | Active, stateful, multi-step |
| Traversal actions | Cue->Tag, Cue+Tag->Content, Content->Cue+Tag |
| Routing module | LLM-based routing function |
| Stop condition | LLM evaluates evidence sufficiency |
| Benchmarks | LoCoMo, LongMemEval |
| Baselines | RAG, A-Mem, MemoryOS, LangMem, Mem0 |
3-2. Module breakdown
1) Memory construction
MRAgent는 dialog에서 memory graph를 두 단계로 만든다.
- Element generation
- LLM이 dialog에서 fine-grained cue, content item, association을 추출한다.
- Graph construction
- 추출된 element를 heterogeneous graph로 구성한다.
Graph는 다음처럼 쓴다.
\[M=(C,V,R)\]- $C$: entity나 attribute 같은 cue node
- $V$: episodic 또는 semantic memory item 같은 content node
- $R$: tag를 통해 cue와 content를 잇는 typed relation
Relation은 다음처럼 표현된다.
\[(c,g,v) \in R\]여기서 $g$는 cue $c$와 content $v$를 연결하는 associative tag다.
2) Cue nodes
Cue node는 fine-grained retrieval handle이다. 이름, 사건, 시간 anchor, 장소, attribute, salient concept이 될 수 있다.
중요한 점은 cue가 final memory content가 아니라는 것이다. Cue는 memory reconstruction으로 들어가는 entry point다. Query가 일부 cue를 직접 언급할 수 있지만, 다른 cue는 intermediate evidence를 읽은 뒤에야 사용할 수 있다.
3) Associative tags
Tag는 cue와 content 사이의 semantic relation을 요약한다. Tag는 intermediate bridge 역할을 한다. LLM은 cue에 연결된 모든 content를 바로 여는 대신, 먼저 tag를 보고 어떤 relation path가 유망한지 고를 수 있다.
이 two-stage design은 efficiency 측면에서 중요하다. Content를 prompt에 넣는 비용이 크다면, tag는 full content retrieval 전에 싼 routing information을 제공한다.
4) Content nodes
Content node는 memory item을 저장한다. Concrete episodic memory나 higher-level semantic memory에 해당할 수 있다.
MRAgent는 모든 content node가 retrieve되어야 한다고 가정하지 않는다. Graph traversal은 cue와 tag에 condition된 content를 선택하고, retrieved content는 다시 새로운 cue와 tag를 활성화할 수 있다.
5) Reconstruction state
Step $t$에서 MRAgent는 reconstruction state를 유지한다.
\[S^{(t)} = (Z^{(t)},H^{(t)})\]- $Z^{(t)}$: cue, tag, content를 포함하는 active set of memory elements
- $H^{(t)}$: previous step에서 누적된 evidence인 reconstructed context
이 state가 retrieval을 active하게 만든다. 다음 traversal action은 current active element와 accumulated evidence에 의존한다.
6) Traversal actions
Action set에는 forward traversal과 reverse traversal이 포함된다.
| Action | 의미 |
|---|---|
| Cue->Tag | 선택된 cue에서 associative tag를 활성화 |
| Cue+Tag->Content | Cue와 tag에 condition된 content retrieval |
| Content->Cue+Tag | Retrieved content를 사용해 새로운 cue와 tag 활성화 |
Forward traversal은 evidence를 찾는다. Reverse traversal은 evidence에서 새로운 retrieval handle을 만든다. 이것이 active reconstruction의 핵심이다.
7) LLM routing and pruning
MRAgent는 original query, current reconstructed context, newly retrieved memory elements를 바탕으로 candidate next node를 score하기 위해 LLM-based routing function을 사용한다.
그다음 LLM은 answer하기에 evidence가 충분한지, 아니면 더 탐색해야 하는지 판단한다. 이는 unconstrained graph expansion을 피하게 한다. 동시에 MRAgent가 단순 graph traversal이 아니라 semantic reasoning으로 guided되는 graph traversal이라는 뜻이다.
4. Training / Data / Recipe
4-1. Data
MRAgent는 새로운 pretrained model이 아니다. Agent memory framework다. Main dataset은 long-horizon memory를 평가하는 benchmark다.
| Benchmark | 평가 대상 |
|---|---|
| LoCoMo | 긴 대화 맥락에서 memory understanding을 평가 |
| LongMemEval | 여러 session과 긴 history를 가로지르는 long-term memory를 평가 |
LoCoMo question type은 multi-hop, temporal, open-domain, single-hop을 포함한다. Active reconstruction은 여러 evidence piece가 step을 거쳐 발견되어야 하는 경우에 가장 중요하므로, 이 구성이 유용하다.
4-2. Implementation setup
논문은 두 LLM backbone으로 방법들을 평가한다.
| Backbone | 사용 목적 |
|---|---|
| Gemini-2.5-Flash | 주 평가와 cost analysis |
| Claude-Sonnet-4.5 | 추가 backbone 비교 |
Metric은 F1, GPT-4o-mini를 사용하는 LLM-Judge score, analysis를 위한 evidence recall을 포함한다.
Baseline은 RAG, A-Mem, MemoryOS, LangMem, Mem0를 포함한다.
4-3. Engineering notes
- Tag first, content later
- Tag는 더 싼 routing handle이다.
- Content는 path가 promising해진 뒤에 retrieve해야 한다.
- Reverse traversal이 핵심이다
- Retrieved content는 새로운 cue를 만들어야 한다.
- 그렇지 않으면 reconstruction은 shallow top-k retrieval이 된다.
- Stopping policy가 중요하다
- Active reconstruction은 over-explore할 수 있다.
- LLM은 accumulated evidence가 충분한지 결정해야 한다.
- Graph construction은 단순하게 유지할 수 있다
- MRAgent는 relational reasoning을 retrieval time으로 옮긴다.
- 이는 construction overhead를 줄이지만 query-time traversal work를 늘린다.
- Memory growth는 여전히 문제다
- 현재 implementation은 update, forgetting, consolidation에 초점을 두지 않는다.
- Long-lived deployment에는 maintenance policy가 필요하다.
- Routing prompt도 system의 일부다
- LLM-based router가 branch selection을 결정한다.
- Prompt quality와 model capability가 retrieval quality에 직접 영향을 준다.
5. Evaluation
5-1. LoCoMo main results
LoCoMo에서 MRAgent는 baseline보다 overall LLM-Judge score를 개선한다. Gemini backbone에서 table의 가장 강한 baseline은 overall J score 68.31의 Mem0이고, MRAgent는 84.21에 도달한다.
| Method, Gemini | Multi-hop J | Temporal J | Open domain J | Single-hop J | Overall J |
|---|---|---|---|---|---|
| RAG | 58.16 | 49.22 | 41.67 | 69.20 | 61.30 |
| A-Mem | 53.54 | 49.53 | 33.33 | 61.83 | 55.97 |
| MemoryOS | 63.82 | 47.04 | 41.66 | 71.90 | 63.35 |
| LangMem | 61.34 | 53.58 | 38.54 | 69.68 | 62.86 |
| Mem0 | 68.79 | 61.68 | 41.66 | 73.72 | 68.31 |
| MRAgent | 75.17 | 80.37 | 68.75 | 90.48 | 84.21 |
가장 큰 gain은 temporal category와 open-domain category에서 나온다. 이는 intermediate cue와 associative traversal이 도움이 되어야 하는 바로 그 영역이다.
논문은 Gemini에서 23.3% relative gain, Claude에서 12.4% improvement를 설명한다.
5-2. LongMemEval result and cost
LongMemEval에서 논문은 consistent improvement와 strongest baseline 대비 32% relative gain을 보고한다.
Cost analysis도 중요하다.
| Method | Token consumption | Runtime |
|---|---|---|
| A-Mem | 632k | 1122.23s |
| MemoryOS | 273k | 3135.54s |
| LangMem | 3268k | 1209.57s |
| Mem0 | 245k | 533.29s |
| MRAgent | 118k | 586.11s |
MRAgent는 listed baseline보다 적은 token을 사용하고, runtime은 Mem0에 가깝다. 항상 가장 빠른 것은 아니지만 token-efficient하다.
이 결과는 tag와 selective path expansion이 prompt bloat를 줄일 수 있다는 design claim을 지지한다. 하지만 runtime은 여전히 multi-step LLM routing에 의존하며 exploration depth에 따라 커질 수 있다.
5-3. Ablation and mechanism
Ablation study는 memory structure와 reasoning mechanism variant를 비교한다.
- CE: Cue->Episode direct indexing
- CTE: Cue-Tag-Episode mediated retrieval
- Multi-hop reasoning variants
논문은 tag-mediated graph와 active reconstruction이 모두 중요하다고 보고한다. 또한 multi-hop query가 iterative exploration에서 상당한 이득을 얻으며, successive step을 거치며 recall이 30% 이상 개선된다고 보고한다.
이 점이 핵심이다. One-shot retrieval만으로 충분했다면 deeper reconstruction은 많은 이득을 주지 못했을 것이다. 관찰된 multi-turn recall improvement는 intermediate state가 실제로 도움이 된다는 evidence다.
5-4. What really matters in the experiments
1) Multi-hop과 temporal gain이 핵심 signal이다
Single-hop memory는 강한 retrieval로 처리할 수 있는 경우가 많다. MRAgent가 가장 흥미로운 지점은 initial query에서 명확하지 않았던 cue를 발견해야 answer할 수 있는 경우다.
2) Token efficiency가 중요하다
Memory system은 construction, summarization, prompt expansion 안에 cost를 숨기는 경우가 많다. MRAgent의 token-cost table은 memory construction과 retrieval을 모두 포함하므로 유용하다.
3) Graph quality만으로는 부족하다
Graph memory라도 active traversal이 없으면 실패할 수 있다. 논문의 요지는 “graph가 vector보다 낫다”가 아니라, “graph traversal이 evidence에 따라 adaptive하게 바뀌어야 한다”는 것이다.
4) Runtime 문제는 해결된 것이 아니다
MRAgent는 token-efficient하지만, multi-step reconstruction은 deep query에서 latency를 늘릴 수 있다. Production system에는 routing budget과 early stopping이 필요하다.
6. Limitations
- Query-time cost는 reconstruction depth에 따라 커진다
- Active traversal은 여러 LLM call이나 routing step을 필요로 할 수 있다.
- Deep query는 one-shot retrieval보다 느릴 수 있다.
- Static construction에 가깝다
- 현재 implementation은 비교적 단순한 memory construction을 사용한다.
- Memory update, forgetting, consolidation을 깊게 다루지는 않는다.
- Graph가 단조롭게 커질 수 있다
- Interaction이 누적될수록 memory graph가 커진다.
- Long-lived agent에는 storage와 pruning policy가 필요하다.
- LLM router dependency
- Branch selection은 LLM reasoning quality에 의존한다.
- Weaker backbone이나 나쁜 prompt는 traversal을 잘못 route할 수 있다.
- Graph extraction quality가 중요하다
- Cue, tag, content extraction error는 전파될 수 있다.
- 나쁜 tag는 useful memory를 unreachable하게 만들 수 있다.
- Benchmark scope가 제한적이다
- LoCoMo와 LongMemEval은 유용하지만, production memory에는 privacy, deletion, versioning, conflict resolution이 포함된다.
- LLM-Judge metric
- LLM-Judge score는 judge model과 prompt에 의존한다.
- Human validation이나 stricter task-specific verification이 있으면 결론이 더 강해진다.
- Full memory lifecycle system은 아니다
- MRAgent는 retrieval time의 reconstruction에 초점을 둔다.
- Long-term memory lifecycle, policy, safety를 완전히 해결하지는 않는다.
7. My Take
7-1. Why this matters for my work
MRAgent의 가장 중요한 메시지는 “memory graph를 쓰자”가 아니다. 더 중요한 점은 memory retrieval을 reasoning의 바깥에 두지 말자는 것이다.
Agent가 긴 경험을 다룰 때, 처음 query만으로 필요한 memory key가 모두 정해지는 경우는 드물다. 실무에서는 한 evidence를 보고 나서야 다음 검색어가 떠오른다. Support ticket, long user history, experiment log, codebase change, meeting transcript 모두 그렇다.
MRAgent는 이 human-like search pattern을 system contract로 만든다.
query -> cue -> tag -> content -> new cue -> new content -> answer
이 chain이 retrieval과 reasoning 사이의 경계를 흐린다.
7-2. Reuse potential
Personalized assistant
User preference가 여러 session에 흩어져 있을 때, direct top-k retrieval은 관련 session 일부만 가져올 수 있다. Tag-mediated traversal은 person, time, condition, activity를 따라 memory를 재구성하는 데 유용하다.
Research agent
논문, 실험 log, meeting notes에서 하나의 claim을 확인할 때, first clue가 second clue를 만든다. Active reconstruction은 evidence graph 탐색에 잘 맞는다.
Enterprise support agent
Customer issue는 product version, previous ticket, account setting, policy exception이 얽힌다. Query-time graph traversal로 relevant path를 좁히는 구조가 유용하다.
Codebase assistant
Function name을 cue로 시작해 module tag, design note, previous bug, commit summary를 따라갈 수 있다. 다만 code dependency graph에는 deterministic tool traversal도 함께 써야 한다.
7-3. Production considerations
- Retrieval budget을 query difficulty에 따라 조절해야 한다.
- Tag extraction quality를 monitoring해야 한다.
- Sensitive memory는 content retrieval 전에 permission check가 필요하다.
- Graph path와 retrieved evidence를 audit log로 남겨야 한다.
- Memory deletion request가 cue, tag, content 모두에 반영되어야 한다.
- Static graph growth를 막기 위한 merge, decay, pruning policy가 필요하다.
- LLM router가 prompt injection content를 따라가지 않도록 guardrail이 필요하다.
7-4. Follow-up papers
- Mem0
- A-Mem
- Zep memory graph
- LongMemEval
- LoCoMo
- GraphRAG
- Agentic RAG and Search-o1
- EvoArena and EvoMem
- TaskMem
8. Summary
- MRAgent는 memory retrieval을 active reconstruction으로 재정의한다.
- Cue-Tag-Content graph는 agent가 memory content를 열기 전에 associative tag를 먼저 볼 수 있게 한다.
- LLM reasoning은 traversal, pruning, stopping에 통합된다.
- LoCoMo와 LongMemEval 결과는 특히 multi-hop과 temporal memory에서 강한 gain을 시사한다.
- 주요 open challenge는 memory lifecycle과 query-time reconstruction cost다.
댓글남기기