Belief Memory: Agent Memory Under Partial Observability

Meta info.

• Authors: Junfeng Liao, Qizhou Wang, Jianing Zhu, Bo Du, Rui Yan, Xiuying Chen
• Affiliation: MBZUAI, RIKEN AIP, UT Austin, Wuhan University
• Paper: https://arxiv.org/abs/2605.05583 (arXiv:2605.05583v2)
• Published: May 8, 2026 (arXiv preprint)

TL; DR

agent memory가 관측을 단일 deterministic 결론으로 collapse 해서 self-reinforcing error를 만든다는 문제를 짚고, 후보 결론들을 확률과 함께 유지(belief)하며 noisy-OR로 갱신 + retrieval 시 분포 전체를 반환하는 BeliefMem 제안

Background

• LLM agent가 long-horizon / multi-session task를 수행할 때, 세션을 넘어 지식을 축적하기 위해 persistent external memory에 의존 (Hu et al., 2025)
• 2가지 기존 memory 계열: storage 관리와 retrieval 전략에서만 차이, 본질적으로 memory representation은 모든 entry를 noisy/ambiguous 관측에서 추론한 단일 categorical 결론(deterministic)으로 저장, 모든 연산이 all-or-nothing
  • factual memory: 사용자/환경에 대한 관측을 structured entry로 기록 (무엇을 봤는가)
    • Generative Agents (Park et al., 2023): natural-language memory stream + 다중 신호 retrieval
    • MemGPT (Packer et al., 2023): context/recall/storage를 virtual context로 관리
    • Mem0 (Chhikara et al., 2025): salient fact를 동적 추출, consolidate 후 vector retrieval
    • A-MEM (Xu et al., 2025): structured note + indexing/linking
    • MemoryBank (Zhong et al., 2024) forgetting curve, Zep (Rasmussen et al., 2025) temporal KG, MemOS (Li et al., 2025) memory OS, …
  • self-improving memory: 과거 경험에서 actionable lesson을 distill (무엇을 배웠는가)
    • Reflexion (Shinn et al., 2023): 실패 경험에서 self-corrective guidance 생성
    • ExpeL (Zhao et al., 2024): trajectory 전반의 recurring pattern을 insight로 집계
    • Voyager (Wang et al., 2023) / MemSkill (Zhang et al., 2026): 재사용 가능한 skill library 확장
  • RL-based memory (Memory-R1, MEM1, Agentic Memory, MemRL): add/update/delete를 학습된 policy로 대체
• POMDP / belief state 배경: 본질적으로 POMDP (Kaelbling et al., 1998)
  • POMDP: agent는 세계의 true state를 직접 보지 못하고 user message·tool output 같은 partial·noisy 관측만 받음
    • POMDP에서 불확실성은 hidden state에 대한 확률분포인 belief state로 표현됨
  • 최근 LLM agent를 partial observability 하에서 보는 연구 (Belief Engine, CoBelWorld, PABU 등) 등장
    • memory system은 이 함의를 무시: 관측을 곧 ground truth로 등치시켜 불확실성을 단일 결론으로 collapse

Problem States

deterministic memory의 표현 자체가 partial observability와 맞지 않아 시간의 흐름에 따라 오류 누적 + 확대

• Deterministic Bottleneck: 각 latent attribute에 대해 point estimate(가장 그럴듯한 가설 하나)만 저장하고 나머지 후보와 그 확률 폐기 → 완전한 belief가 담고 있던 불확실성이 사라짐
• Self-Reinforcing Error: 저장된 단일 결론을 agent가 행동의 근거로 삼음 → 폐기된 대안 가설을 시험할 행동을 하지 않음 → 잘못된 결론과 일치하는 관측만 추가로 수집 → 그 결론을 시간에 걸쳐 강화
  • e.g. Fig 1 API X가 3번 timeout → “API X failed” 저장 → 이후 세션에서 retry 안 함 → 일시적 rate limiting이었을 가능성을 영영 관측 못 함 (= self-reinforcing error)
  • update-based 방법도 여전히 한계: 고쳐봐야 또 다른 단일 결론으로 대체될 뿐, 다음 transient error 한 번이면 도로 역전될 것
• 복원 불가능성: point estimate로 collapse된 뒤에는 폐기된 대안의 posterior support를 memory만으로 재구성할 수 없고, 완전히 새 evidence로 처음부터 다시 쌓아야 함
• → 따라서 필요한 조건
  • [storage 단계] 후보 결론과 불확실성을 버리지 않고 보존하는 표현
  • [retrieval 단계] 그 불확실성을 다시 agent에게 노출, 대안을 의사결정 시점에 보이게 하는 메커니즘
  • [update rule] 새 관측에 대한 확률 점진적으로 갱신 (강한 결론은 강화하고 약한 결론은 약화)

Suggestions

수식 정의: belief state와 deterministic 한계

• POMDP 설정: agent는 매 시점 관측 $o_t$를 받고 행동 $a_t$를 고르지만 세계의 진짜 상태 $s_t$는 직접 못 봄.
  • API X가 죽었는지 아니면 일시적으로 막혔는지($s_t$)는 hidden, 관측되는 timeout($o_t$)은 그 흔적일 뿐
• belief state $b_t$: 지금까지의 관측/행동 기록으로 조건화한 hidden state의 posterior 분포
  • 본 걸 종합하면 진짜 상태가 무엇일 확률 계산 → 최적 행동에 필요한 정보는 단일 분포 (sufficient statistic)
  • 기존 external memory도 결국 접근 불가능한 $b_t$를 압축해 흉내 내는 장치: 관측으로 조회(Read)해 행동을 고르고, 새 관측이 오면 갱신(Update)
• attribute $c$ = 추적하는 사실 단위 (user preference, tool status, object-location 등)
  • 그 attribute가 가질 수 있는 결론들이 후보 가설
  • 후보 $h$에 대한 belief를 $b^{(c)}_t(h)$로 표기
• deterministic memory는 확률 최댓값 후보 하나만 저장하고 나머지는 drop, ideal memory는 후보 분포 전체(합 = 1) 저장

\[\text{deterministic: } \hat h_t(c) \in \arg\max_{h \in H(c)} b^{(c)}_t(h) \qquad \text{ideal: } b^{(c)}_t,\ \textstyle\sum_{h} b^{(c)}_t(h) = 1\]

• e.g. failed 0.5 / rate-limit 0.35 / network 0.15
  • deterministic: “failed”만 남기고, 한 번 버린 불확실성은 memory만으로 복원 불가
  • ideal: 전부 남기고 지속적으로 갱신

Belief Memory: 무엇을 저장? (Representation)

• ideal 분포의 한계 → 정확한 분포 대신 근사 belief를 사용: 저장값은 엄밀한 posterior가 아니라 ranking/갱신용 confidence score
  • 후보가 미리 정해지지 않고 대화 중 새로 생겨 정규화 분포 정의가 어려움
  • 매 관측마다 모든 후보를 갱신하면 비용 측면 비효율
• (근사 1) $H_{\text{sub}}(c)$: 증거가 실제로 본 후보만 저장
  • 저장량이 (전체 후보 수가 아니라) 본 증거에 비례, 안 본 후보는 비용 0
  • 모든 가능한 후보가 아니라, 증거가 실제로 한 번이라도 지지한 후보만 저장
• (근사 2) confidence $p^{(c)}_t(h)$: 후보별 독립 유지, 합 = 1로 정규화하지 않음
  • 각 숫자는 후보 하나만 놓고 보면 증거가 얼마나 강하게 지지하는지에 대한 confidence

Belief-aware Memory Update: Add / Merge / Contradiction (Fig 2)

• 새 관측이 오면 LLM이 후보 결론들과 각 confidence를 뽑고, 셋 중 하나로 처리
• Add (처음 보는 attribute): 새 entry로 등록, 초기 confidence는 $[0.7, 0.9]$ 구간에서 시작 (0이나 1이 되지 않도록)
• Merge (이미 있는 attribute를 지지하는 관측일 때): noisy-OR로 기존 confidence를 끌어올림

\[p^{(c)}_{t+1}(h) = \min\!\left(1 - \big(1 - p^{(c)}_t(h)\big)\big(1 - \Delta(o_{t+1}, h)\big),\ 0.99\right)\]

• 지지 증거가 들어올수록 confidence가 올라가기만 하고(단조 증가) 0.99에서 멈춤
• $\Delta$: 새 관측이 $h$를 얼마나 강하게 지지하는지
  • LLM이 매긴 confidence이지 보정된 likelihood가 아님
• 갱신 전 옛 버전은 archive: “이전 세션엔 어떻게 알고 있었지” 같은 temporal query 대응 (Appendix B.3)
• Contradiction (같은 attribute에서 반대 결론을 지지하는 관측): 기존 $h$의 confidence를 0.25로 강등
  • 모순 판정은 rule-based 키워드 매칭, 이전 값은 보존
  • noisy-OR이 위로만 움직이므로 하향은 이 규칙이 전담하는 비대칭 구조

Belief-aware Retrieval

• retrieval 설계: 후보 분포를 보존하는 storage
  • storage에서 불확실성을 보존해도 retrieval에서 결론 하나로 압축하면 의미 없으므로, retrieval도 분포 단위로 동작할 수 있도록
  • entry별 점수:

\[\alpha_t(c) = \text{sim}(o_t, c) \cdot \lambda^{\tau_t(c)}, \quad \lambda \in (0, 1]\]

• (지금 관측과 얼마나 관련 있나) × (최근에 갱신됐나): $\text{sim}$은 embedding 0.7 + lexical 0.3 hybrid, $\lambda^{\tau}$는 오래 안 건드린 entry일수록 점수를 깎도록 decay
• staleness는 검색 우선순위만 낮추고 그 안의 confidence 값 자체는 안 건드림 (recency ≠ belief)
• Read: 점수 상위 K개를 골라 각 attribute의 후보 분포를 통째로 output
  • agent는 결정 직전에 failed 0.1 / rate-limit 0.8 같은 분포로 된 대안 전체를 봄
  • deterministic처럼 저장 시점에 지워지지 않으니 retry 같은 대안 행동을 다시 시도 가능

Effects

• Experimental setup
  • benchmark
    • LoCoMo (Maharana et al., 2024)
      • long-term 대화 memory, 평균 ~9,000 token, 최대 35 session
      • 4 category: single-hop / multi-hop / temporal reasoning / open-domain
      • metric: F1, BLEU-1
    • ALFWorld (Shridhar et al., 2020)
      • text 기반 embodied, 6개 household goal
      • in-distribution Seen(140 ep) / out-of-distribution Unseen(134 ep) 분리 → Unseen이 memory transfer 직접 측정
      • metric: success rate(SR↑), solved episode 평균 step(↓), horizon 50-step
  • baseline
    • LoCoMo: LoCoMo baseline, ReadAgent, MemoryBank, MemGPT, A-MEM, Mem0
    • ALFWorld: + LangMem, MemoryOS, No-Memory(현재 관측만으로 행동)
  • evaluation
    • LoCoMo: embedding text-embedding-3-small, base = GPT-4o / GPT-4o-mini
    • ALFWorld: base = Qwen3-Next-80B-A3B-Instruct, Contriever retrieval, memory bank 3,000 expert trajectory (eval trace 미사용)
    • 공통
      • $[p_{\min}, p_{\max}] = [0.7, 0.9]$
      • decay $\lambda$ = 0.5(LoCoMo) / 0.1(ALFWorld)
      • retrieval Top-K = 20 (LoCoMo multi-hop/temporal/open-domain은 30)
      • attribute당 최대 후보 4개
• Results
  • LoCoMo Tab 1: BeliefMem이 GPT-4o-mini / GPT-4o 기준 모두 평균 최고
    • temporal 51.88 / 45.78, multi-hop 40.51 / 32.24에서 큰 폭 우위 → 관측 충돌 해소 및 evidence 집계가 필요한 task에 강하다고 주장
      • temporal 강세는 historical version archiving(과거 상태를 timestamp로 보존)에서 직접 기인한다고 주장
  • ALFWorld Tab 2: Seen/Unseen 전반에서 모든 baseline 상회
    • 2위(ReadAgent) 대비 +11%, 나머지 baseline 평균 대비 +99% (단 이 평균에는 No-Memory·MemoryOS 같은 약한 baseline 포함)
    • BeliefMem (corpus 50%만 사용): Unseen SR 최고 성능, 평균 SR 59.88 → full corpus(58.66)보다 Unseen에서 오히려 더 좋음
    • trade-off: full corpus는 Seen 최고(63.57), 50%는 Unseen 일반화 최고 → in-distribution memory가 많아지면 seen trajectory 암기로 편향
      • 저자는 “plausible하지만 결정적이지 않다”고 표현
  • Ablation Tab 3: 각 구성요소 모두 중요하다는 결론
    • w/o belief-based memory(deterministic로 collapse): LoCoMo F1 42.38 → 22.58, ALFWorld SR 59.88 → 28.71 (가장 큰 하락)
    • w/o belief-aware retrieval: 후보는 두되 확률 폐기
      • 다중 가설 유지만으로도 일부 효과는 있으나, multi-hop/open-domain 같은 충돌 task에서 급락
    • w/o Add: 신규 attribute 편입 불가 → 사실상 붕괴
    • w/o Merge: 확률이 초기값에 frozen → 정적 memory
  • 데이터 효율 Fig 4a: corpus 500~3,000에서 robust하고 corpus 50%만으로 전 baseline 능가
    • 500개(16.67%)로도 6개 중 5개 능가
  • belief 수렴 Fig 4b: Top-1 rate(true 결론이 최고 confidence를 받는 비율)가 evidence 누적에 따라 약 88%까지 상승
    • raw frequency 기반 baseline은 noise에 분포가 왜곡되어 수렴 실패
  • adversarial correction Fig 3: 강하게 틀린 결론을 주입(102 sample) 후 valid/noisy 관측을 섞어 교정
    • correction rate이 deterministic 대비 거의 2배, 평균 교정 step도 약 2배 정도 더 빠름
  • token 비용 Fig 5: LoCoMo에서 generation당 평균 1,414 token (Mem0 약 2K / A-MEM 1.7K)으로 오히려 적음

Personal note. 연구미팅에서 언급했던 것 같은데, memory를 distribution처럼 가져가는 연구입니다. 결과적인 성능은 좋았는데, 이론적으로 엄밀하지는 않았다고 언급되긴 하는데 그래서 그런지 POMDP가 메서드를 유도했다기보다 사후적으로 정당화하는 수단으로 읽히는 부분이 있습니다. 실제로 메모리가 어떻게 생겼는지 살펴보려 합니다.