Belief Memory: Agent Memory Under Partial Observability

Problem: Self-Reinforcing Error in Deterministic Memory
Current Large Language Model (LLM) agents operating in long-horizon, partially observable environments rely on external memory to accumulate knowledge. However, existing memory methods—ranging from factual streams to self-improving reflection systems—adhere to a deterministic paradigm. They store each observation as a single, categorical conclusion (e.g., "API X failed"), discarding alternative hypotheses and the inherent uncertainty of the observation. This approach creates a "self-reinforcing error": once an agent commits to a flawed conclusion, it acts based on that conclusion, generating further observations that appear to support it while never revisiting discarded alternatives. In Partially Observable Markov Decision Processes (POMDPs), where agents cannot directly access the true state of the world, collapsing noisy observations into a single ground truth prevents the agent from correcting errors when new evidence arrives.

Methodology: BeliefMem
To address this, the authors propose BeliefMem, a memory paradigm that shifts from storing deterministic conclusions to maintaining an attribute-level belief representation. Instead of a single point estimate, BeliefMem stores multiple candidate conclusions for each attribute, each associated with a probability.

The methodology operates through three core mechanisms:

1. Belief-Based Storage: For every attribute $c$ (e.g., tool status, user preference), the system maintains a set of candidate hypotheses $H(c)$. Rather than a normalized posterior over a fixed set, it stores evidence-based probabilities for candidates that have been supported by observations.
2. Probabilistic Update (Noisy-OR): When new observations arrive, BeliefMem updates the memory using two operations:
   • Add: Initializes new attributes or candidates with a probability bounded by $[p_{min}, p_{max}]$.
   • Merge: Updates existing candidates using a Noisy-OR rule. If an observation supports a hypothesis, its probability increases; if it supports a contradictory hypothesis, the probability of the conflicting hypothesis is reduced (e.g., to 0.25). This allows the system to incrementally refine confidence without discarding alternatives.
3. Belief-Aware Retrieval: During retrieval, the system returns not just the top-ranked conclusion but the top-$K$ entries along with their full set of candidate probabilities. This ensures that competing hypotheses remain visible to the agent at decision time, allowing it to reason under uncertainty and select actions that test or refine its beliefs.

Key Contributions

• Paradigm Shift: The paper identifies and addresses the "deterministic bottleneck" in agent memory, proposing a shift from point estimates to probabilistic belief states.
• Mitigation of Self-Reinforcing Error: By preserving uncertainty and alternative hypotheses, BeliefMem prevents agents from becoming trapped in incorrect conclusions, enabling them to correct errors as new evidence accumulates.
• Practical Approximation: The authors provide a computationally feasible approximation of belief states using Noisy-OR evidence merging, avoiding the intractability of maintaining exact posteriors over open-ended hypothesis spaces.

Experimental Results
The authors evaluated BeliefMem on two benchmarks: LoCoMo (long-term conversational memory) and ALFWorld (embodied agent interaction).

• Performance: BeliefMem achieved the best average performance on both benchmarks, outperforming well-known baselines such as MemGPT, MemoryBank, and Mem0.
• Data Efficiency: Notably, BeliefMem achieved superior results using only 50% of the standard memory corpus size. In some settings, it outperformed baselines with as little as 16.67% of the data.
• Correction and Convergence: Adversarial experiments showed that BeliefMem corrects flawed memory entries nearly twice as effectively as deterministic baselines and converges to the true conclusion with high probability (87.68% Top-1 rate) as evidence accumulates.
• Generalization: In out-of-distribution (Unseen) scenarios, BeliefMem demonstrated robust generalization, often outperforming baselines by significant margins (e.g., 12.4% in ALFWorld unseen tasks).

Significance
The paper claims that replacing deterministic memory entries with probabilistic belief representations yields substantial gains in partially observable environments. By preserving uncertainty rather than discarding it, BeliefMem enables agents to act with high confidence on well-evidenced knowledge while retaining the capacity to update their beliefs when new evidence contradicts prior assumptions. This work explores a new direction for agent memory, demonstrating that maintaining a belief state approximates the optimal POMDP solution more effectively than current deterministic approaches, leading to more reliable and adaptable long-term agents.