Memory is Reconstructed, Not Retrieved

Memory is Reconstructed, Not Retrieved: Graph Memory for LLM Agents, ICML, 2026.

Mem0, A-Mem, Zep 같은 Agent Memory 시스템은 대부분 “retrieve-then-reason” 구조를 따라요. 먼저 query로 memory를 한 번 검색하고, 검색된 내용을 reasoning에 넣어요. 이 논문은 이 고정된 파이프라인이 왜 근본적으로 한계인지 지적하고, memory access 자체를 reasoning 안으로 끌어들이는 MRAgent를 제안해요. LOCOMO와 LONGMEMEVAL에서 최대 23% 향상을 보이면서 token과 runtime 비용도 함께 줄였어요.

Retrieve-then-reason은 왜 한계에 부딪히나

기존 memory 시스템은 검색 정책이 query에만 의존해요. 검색이 한 번 끝나면 그 결과를 고정한 채로 reasoning을 시작해요. 문제는 reasoning 도중에 새로 발견하는 중간 증거를 검색에 다시 반영하지 못한다는 점이에요.

논문은 Nate와 Caroline 예시로 이를 보여줘요. “video game tournament”에 대한 query가 들어오면, similarity 기반 검색은 표면적으로 관련된 이벤트를 잔뜩 가져오지만 정작 필요한 증거는 놓쳐요. Graph 기반 확장도 마찬가지예요. Seed 노드의 N-hop 이웃을 가져오지만 Caroline은 “video game tournament” 이벤트와 직접 연결돼 있지 않아서 도달하지 못해요. 반면 reasoning이 검색과 함께 돌면 “July”라는 시간 단서를 중간에 추론해내고, 이걸 새 검색 제약으로 바꿔서 Caroline의 활동을 찾아낼 수 있어요.

Passive와 Active를 어떻게 구분하나

논문은 memory retrieval을 sequential decision process로 정의해요. External memory $M$은 memory unit 집합 $V = {v_1, \dots, v_N}$으로 이뤄져요. Query $x$가 주어지면 $T$ step에 걸쳐 memory unit을 선택하고, step $t$까지 누적된 증거를 $S^{(t)} = {v^{(1)}, \dots, v^{(t)}}$로 둬요.

Passive retrieval은 query만 보고 검색할 unit을 한 번에 결정하는 stateless 정책이에요.

\[\{v^{(1)}, \dots, v^{(T)}\} = \pi_p(x)\]

Active reconstruction은 지금까지 모은 증거를 조건으로 다음 unit을 선택하는 stateful 정책이에요.

\[v^{(t)} = \pi_a^{(t)}(x, S^{(t-1)}), \quad S^{(t)} = S^{(t-1)} \cup \{v^{(t)}\}\]

이 관점에서 보면 기존 시스템은 전부 passive에 속해요. Similarity 기반은 고정된 scoring 함수로 top-$k$를 뽑아요.

\[\pi_{sim}(x) = \mathrm{TopK}(\{\mathrm{sim}(x, v)\}_{v \in V}, k)\]

Graph 기반은 similarity seed에 미리 정해진 N-hop 이웃 확장을 더해요.

\[V^{sim} = \mathrm{TopK}(\{\mathrm{sim}(x, v)\}_{v \in V}, k), \quad \pi_{graph}(x) = V^{sim} \cup \mathrm{Neighbor}(V^{sim})\]

Passive retrieval의 한계는 세 가지로 정리돼요. (1) 중간 상태에 따라 전략을 수정하지 못하고, (2) 고정된 aggregation 때문에 noise가 쌓이며, (3) 미리 구축한 구조에 크게 의존해서 유연성과 확장성이 떨어져요.

인지신경과학은 어떤 힌트를 주나

인지신경과학은 memory retrieval을 저장된 내용을 그대로 읽어오는 과정이 아니라 능동적인 재구성 과정으로 봐요. 검색은 contextual cue에서 시작해서 engram이라는 압축된 내부 상태를 재활성화하고, 그 활성화가 이후 recall을 다시 제약하면서 점진적으로 일관된 기억을 재구성해요.

MRAgent는 여기서 Cue–Tag–Content 구조를 가져와요. Tag는 cue와 memory content를 잇는 중간 연상 구조 역할을 해요. Memory content는 구체적 사건을 담는 episodic memory와 공유 개념·지식을 담는 semantic memory로 나뉘는데, 이 구분도 인지신경과학의 관찰과 맞닿아 있어요.

Cue–Tag–Content graph는 어떻게 생겼나

MRAgent는 memory를 flat한 검색 대상 모음이 아니라 heterogeneous graph $M = (C, V, R)$로 조직해요. 노드는 두 종류예요. Cue $c \in C$는 entity나 attribute 같은 fine-grained keyword이고, Content $v \in V$는 구체적인 memory item을 저장해요.

Cue와 content의 연결은 typed relation으로 표현해요. $R \subseteq C \times G \times V$이고, 각 triple $(c, g, v)$는 cue $c$를 relation attribute $g$, 곧 Tag를 거쳐 content $v$에 연결해요.

Tag가 핵심 설계예요. 큰 graph에서 content 노드로부터 n-hop 이웃을 그냥 확장하면 combinatorial explosion이 생기고 관련 없는 memory가 잔뜩 딸려와요. Tag를 명시적 associative intermediate로 두면, LLM이 무거운 episodic content를 실제로 열어보기 전에 tag만으로 branch를 평가하고 가지치기할 수 있어요. 이걸 위해 두 mapping operator를 정의해요. $\phi_{c \to g}$는 cue에서 후보 tag를 활성화하고, $\phi_{(c,g) \to v}$는 cue와 tag를 조건으로 content를 검색해요.

\[\phi_{c \to g}(c) \triangleq \{g \mid (c, g, \cdot) \in R\}, \quad \phi_{(c,g) \to v}(c, g) \triangleq \{v \mid (c, g, v) \in R\}\]

이 두 operator가 associative reasoning과 content-level retrieval을 분리해줘요. 덕분에 대규모 graph에서도 선택적이고 재구성적인 memory access가 가능해져요.

세 개의 memory layer로 나누는 이유

Memory content는 세 층으로 나뉘어요. Episodic layer는 특정 시점의 사건 $e_i \in V_e$를 저장하고, entity·action 같은 cue로 접근하며 tag로 라우팅돼요. Temporal reasoning을 위해 episodic memory는 통합 timeline 위에 정렬돼요. Semantic layer는 개인 속성·선호·일반 사실 같은 상대적으로 안정적인 지식 $s_i \in V_s$를 담고, cue에 aspect-level tag로 연결돼요. 긴 episodic history를 뒤지지 않고도 원하는 semantic 정보에 바로 접근하려는 설계예요. Abstraction layer는 여러 episode에 걸친 반복 패턴을 요약한 topic 노드 $\tau \in V_\tau$를 저장해요. Topic은 자신의 episode들과 연결돼서 top-down 전이 $\phi_{\tau \to e}$를 지원해요.

Memory는 어떻게 채우나

Memory는 input stream $T$에 LLM distillation 파이프라인을 적용해서 자동으로 채워요. 먼저 stream을 일관된 사건 단위 episodic unit $e_i$로 분할해요. 각 unit에서 tag와 cue를 LLM으로 뽑아요.

\[g_i = F^{tag}_{LLM}(e_i), \quad C_i = F^{cue}_{LLM}(e_i)\]

$F^{tag}_ {LLM}$은 episode의 relational pattern을 요약하는 짧은 associative tag를 만들고, $F^{cue}_ {LLM}$은 entity·attribute·salient descriptor 같은 fine-grained cue 집합을 추출해요. 각 cue는 tag를 통해 episodic unit에 연결돼서 Cue–Tag–Episode relation을 이뤄요. Semantic unit도 같은 방식으로 뽑아서 entity-level cue에 aspect-level tag로 연결해요. Topic 노드는 관련 episode들의 공통 주제를 요약해서 만들고, 각 topic을 구성 episode와 이어줘요.

원 dialogue text는 pronoun resolution, temporal normalization, episodic segmentation을 거쳐 정제돼요. 이 전처리 덕분에 cue가 명시적으로 드러나고, 시간 표현이 YYYY-MM-DD 형태로 정규화돼요.

Active reconstruction은 어떻게 돌아가나

MRAgent는 미리 정한 검색 파이프라인을 실행하는 대신, 명시적 reconstruction state와 traversal action 집합으로 active reconstruction을 수행해요.

Reconstruction state는 step $t$에서 다음과 같이 정의돼요.

\[S^{(t)} = (Z^{(t)}, H^{(t)})\]

$Z^{(t)}$는 cue·tag·content를 담은 active set으로 다음 traversal의 후보이고, $H^{(t)}$는 이전 step까지 쌓인 reconstructed context예요.

Traversal action은 앞서 정의한 mapping operator에서 유도돼요. Forward action은 Cue–Tag–Content 방향으로 active set을 확장해요. $\Pi_{c \to g}$는 cue 집합에서 associative tag를 활성화하고, $\Pi_{(c,g) \to v}$는 선택된 cue와 tag를 함께 조건으로 content를 검색해요.

\[\Pi_{c \to g}(C^{(t)}) \triangleq \bigcup_{c' \in C^{(t)}} \phi_{c \to g}(c'), \quad \Pi_{(c,g) \to v}(C^{(t)}, G^{(t)}) \triangleq \bigcup_{c' \in C^{(t)}} \bigcup_{g' \in G^{(t)}} \phi_{(c,g) \to v}(c', g')\]

Reverse action은 검색한 content가 새 cue와 tag를 다시 활성화하게 해서, 중간 증거에 따라 탐색 궤적을 수정하거나 방향을 바꿀 수 있게 해요.

\[\Pi_{v \to (c,g)}(V^{(t)}) \triangleq \{(c', g') \mid \exists v' \in V^{(t)}, (c', g', v') \in R\}\]

전체 loop는 세 단계가 반복되는 구조예요. 먼저 LLM이 query $x$, 누적 context $H^{(t)}$, 현재 active set $Z^{(t)}$를 보고 확장할 action을 골라요.

\[A^{(t)} = f_{select}(x, H^{(t)}, Z^{(t)})\]

선택된 action으로 memory system이 후보 노드를 생성해요. 여기서 exhaustive 확장이 아니라 LLM이 고른 방향으로만 확장한다는 점이 중요해요.

\[\tilde{Z}^{(t+1)} = \bigcup_{a \in A^{(t)}} \Pi_a(Z^{(t)})\]

마지막으로 LLM이 후보 중 관련 있는 content만 남기고 나머지를 가지치기해서 state를 갱신해요.

\[Z^{(t+1)} = f_{route}(x, H^{(t)}, \tilde{Z}^{(t+1)}), \quad H^{(t+1)} = H^{(t)} \cup Z^{(t+1)}\]

갱신 뒤에는 $H^{(t+1)}$가 query에 답하기 충분한지 LLM이 판단해서 계속 탐색할지 멈출지 정해요. 실행은 Navigate 모드와 Answer 모드로 나뉘어요. Navigate 모드에서 toolkit을 호출하며 증거를 모으다가, 충분해지면 Answer 모드로 넘어가서 재구성된 context를 조건으로 최종 답을 생성해요. Toolkit은 query tag events, query conversation time, query event context, query personal aspect, query topic events 같은 typed mapping으로 구성돼요.

Active가 정말 더 강력한가

논문은 approximation-theoretic 관점에서 active retrieval이 passive보다 엄격하게 더 강력하다는 걸 증명해요. Retrieval budget $T$에서 LM이 구현할 수 있는 predictor 집합을 hypothesis class로 보고, adaptive하게 $T$번 검색하는 $\mathcal{H}^{LM}_ {active}(T)$와 검색을 query만으로 미리 고정하는 $\mathcal{H}^{LM}_ {passive}(T)$를 비교해요.

\[\mathcal{H}^{LM}_{passive}(T) \subsetneq \mathcal{H}^{LM}_{active}(T), \quad \forall T \geq 2\]

포함 관계는 자명해요. Passive 정책은 history를 무시하는 active 정책으로 그대로 흉내 낼 수 있으니까요. 엄격한 포함을 보이려고 Binary-Tree Needle-in-a-Haystack이라는 분리 태스크를 구성해요. 깊이 $d = T-1$의 완전 이진 트리에서, 각 경로 노드의 payload에 다음에 따라갈 bit를 심고, 정답 label은 오직 target leaf $v_{u^\star}$의 payload에만 넣어요. Active 정책은 노드를 하나 열 때마다 다음 bit를 읽어 경로를 따라가서 $d+1$번 검색으로 오류 없이 정답에 도달해요. 반면 passive 정책은 leaf를 미리 찍어야 하는데, target leaf를 맞힐 확률이 $T / 2^d$를 넘지 못해서 다음 하한을 벗어날 수 없어요.

\[L(\pi^{pass}_\theta; D_{n,d}) \geq \varepsilon_Y \left(1 - \frac{T}{2^d}\right), \quad \varepsilon_Y := 1 - \sup_{y \in Y} P_Y(y)\]

곧 passive는 트리 깊이에 지수적인 budget이 없으면 irreducible error를 갖고, active는 $d+1$ budget으로 zero error를 달성해요. 두 class가 같다면 모든 distribution에서 같은 최적 오류를 가져야 하는데 이 격차가 그걸 반증해요.

실험은 무엇을 보여주나

두 벤치마크로 평가해요. LOCOMO는 최대 35 session, 평균 300 turn짜리 대화 50개와 QA 쌍으로 구성돼서 single-hop, multi-hop, temporal, open-domain query를 다뤄요. LONGMEMEVAL은 query당 약 115K token의 chat history를 갖는 LongMemEval-S 세팅으로 더 긴 상호작용을 평가해요. Backbone은 Gemini-2.5-Flash와 Claude-Sonnet-4.5를 쓰고, F1과 GPT-4o-mini 기반 LLM-Judge(J), 그리고 evidence recall을 report해요. 비교 대상은 RAG, LangMem, A-Mem, MemoryOS, Mem0예요.

MRAgent는 모든 question type과 backbone에서 baseline을 앞서요. Gemini backbone에서 overall J score를 68.31에서 84.21로 올려서 23.3% 상대 향상을 보이고, Claude backbone에서도 12.4% 향상해요. 특히 temporal과 multi-hop처럼 여러 증거를 엮어야 하는 유형에서 격차가 커요. LONGMEMEVAL에서도 가장 강한 baseline 대비 32% 상대 향상을 기록해요. 흥미로운 점은 memory는 Gemini로 구축하고 retrieval만 Claude로 돌린 MRAgent$^*$가 86.76 J로 크게 뛰는 부분이에요. 검색 단계의 reasoning 품질이 성능을 크게 좌우한다는 걸 시사해요.

논문은 이 향상을 두 요인으로 설명해요. 첫째, Cue–Tag–Content 설계가 tag로 associative relation을 명시해서 검색 방향을 semantic relevance 기준으로 고를 수 있게 해줘요. 둘째, LLM reasoning을 multi-turn memory access에 통합해서 검색 방향이 누적 증거에 적응하고 일관된 reasoning chain을 점진적으로 형성해요.

비용은 오히려 줄어드나

MRAgent는 성능을 올리면서 비용을 줄여요. LONGMEMEVAL 기준 per-sample token 소비가 118k로, A-Mem의 632k나 LangMem의 3,268k보다 훨씬 적어요. 비결은 무거운 관계 구축을 construction 단계에서 하지 않고 retrieval 단계로 미루는 설계예요. 기존 방법은 history를 반복 요약하고 복잡한 dependency를 미리 분석하지만, MRAgent는 construction을 가볍게 유지하고 복잡한 relation building을 query별로 필요할 때만 수행해요. 게다가 associative tag로 검색 방향을 semantic하게 안내해서, 비싼 episodic content를 열기 전에 관련 없는 경로를 먼저 쳐내요. 계산 자원을 query 관련 증거에만 집중시키는 on-demand 접근이에요.

어떤 요소가 성능을 만드나

Ablation은 memory 구조와 reasoning 메커니즘의 기여를 분리해요. 구조는 세 변형을 비교해요. CE(Cue→Episode)는 직접 인덱싱, CTE(Cue–Tag–Episode)는 tag를 거친 episodic 검색, CTC(Cue–Tag–Content)는 전체 구조예요. 결과는 세 가지를 말해줘요. 첫째, reasoning을 켠 변형이 구조만 쓴 변형을 일관되게 앞서요. Multi-step reasoning과 traversal이 증거 누적과 multi-hop 추론에 핵심이고, one-shot 검색만으로는 복잡한 multi-hop query를 못 풀어요. 둘째, reasoning 없이 봐도 CE→CTE→CTC로 갈수록 성능이 단조 증가해서, 풍부한 associative 구조가 검색 신뢰도를 높인다는 걸 보여줘요. 셋째, semantic memory를 제거하면 성능이 뚜렷하게 떨어져요. Episodic이 사건별 detail을 보존한다면 semantic은 multi-hop reasoning에 필요한 안정적 추상 지식을 담아요.

Multi-turn reasoning은 무엇을 하나

Reasoning turn에 따른 누적 evidence recall을 보면, single-hop과 temporal query는 세 turn 안에 거의 완전한 recall에 도달해요. 반면 multi-hop query는 iterative 탐색에서 크게 이득을 봐서, 연속된 step을 거치며 recall이 30% 넘게 개선돼요. Compositional하고 long-range한 dependency를 풀려면 multi-step 재구성이 필요하다는 증거예요. 또 하나 주목할 점은 Max Valid Turns가 Average Turns와 거의 일치한다는 거예요. LLM이 언제 더 탐색하고 언제 멈출지 스스로 잘 판단해서 불필요한 탐색을 줄인다는 뜻이에요. 추가 실험에서는 turn당 parallel 검색 budget $K$를 늘려도 reconstruction depth $T$를 대체하지 못한다는 게 나와요. 넓게 병렬로 뒤지는 것과 증거를 순차적으로 조합하는 것은 다른 문제예요.

Case study는 어떤 궤적을 그리나

“Joanna의 시나리오 중 제작사에서 거절당한 것은 무엇인가”라는 query는 시나리오 제출 사건과 이후 거절 사건을 여러 session에 걸쳐 연결해야 풀려요. MRAgent는 다섯 turn에 걸쳐 재구성해요. 첫 turn에서 tag 기반 연상으로 제출·거절 후보 사건을 검색하고, 두 번째 turn에서 event context와 keyword로 각 거절의 세부사항으로 확장해요. 세 번째와 네 번째 turn에서 Joanna에 대한 semantic 정보를 조회해서 각 시나리오의 속성을 복원하고, 다섯 번째 turn에서 temporal 정보를 조회해 제출과 거절의 순서를 정렬·검증해요. 결과적으로 첫 번째와 세 번째 시나리오가 거절됐다고 올바르게 추론해요. Evidence coverage 분석을 보면 operator마다 역할이 갈려요. Temporal query는 query conversation time이, multi-hop query는 query tag events와 query topic events가 주로 증거를 회수해요. Query 구조에 따라 다른 operator를 선택적으로 활성화하는 셈이에요.

무엇을 남기고 무엇이 숙제인가

MRAgent의 핵심 선택은 복잡한 relational dependency 모델링을 retrieval 단계로 옮긴 거예요. 덕분에 construction은 단순하게 유지하면서, state-dependent 탐색으로 더 복잡한 query를 더 적은 비용에 풀어요. 다만 이 선택은 두 한계를 낳아요. Relational reasoning을 retrieval로 미룬 탓에 재구성 비용이 탐색 깊이에 따라 커지고, 많은 traversal이 필요한 query는 single-shot보다 latency가 높아져요. 또 static construction이라 memory를 시간에 따라 갱신하거나 통합하지 않아서, 상호작용이 쌓이면 graph가 단조 증가하며 저장 부담이 커져요. Adaptive construction, 가벼운 memory maintenance, 더 견고한 traversal 정책이 후속 방향으로 남아 있어요.

Agent Memory를 다루는 입장에서 이 논문의 메시지는 분명해요. Memory representation을 정교하게 만드는 것만으로는 부족하고, retrieval을 passive한 함수에서 reasoning과 얽힌 active 정책으로 바꾸는 축이 따로 있다는 거예요. Cue–Tag–Content는 그 active 정책이 combinatorial explosion 없이 돌 수 있게 해주는 구조적 장치로 읽혀요.