MemUQ: Memory Space Uncertainty Quantification for LLM Agents

As Large Language Models (LLMs) are increasingly deployed as agents in multi-step reasoning and tool-based interaction, reliable uncertainty quantification (UQ) is essential for addressing hallucination and assessing trustworthiness of their decisions. However, existing UQ methods target single-step or response-level settings, failing to capture how uncertainty propagates as agent context and memory evolves, resulting in unreliable confidence estimates that overlook error accumulation and conflicting evidence across steps. To address these limitations, we propose MemUQ, a novel UQ framework leveraging the agent memory space to model both intrinsic generation uncertainty and extrinsic uncertainty from multi-step inconsistencies. MemUQ decomposes agent memory into atomic claims, aggregates them across steps and trajectories, and constructs a conflict graph to quantify claim reliability by combining graph-based importance with frequency-based support. This yields fine-grained, interpretable uncertainty signals grounded in interaction history. Experiments on HotpotQA and StrategyQA demonstrate up to 27% AUROC improvements in error detection over baselines, showing that combining intrinsic uncertainty with memory-centric, claim-level extrinsic uncertainty provides an effective approach to UQ for LLM agents in complex decision-making settings.