acceptodds
Under review as a conference paper at ICLR 2027

MemUQ: Memory Space Uncertainty Quantification for LLM Agents

Abstract

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, uncertainty quantification, agents, trustworthy

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_UroQOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes MemUQ, a memory-centric uncertainty quantification framework for LLM agents in multi-step interactions. MemUQ represents accumulated agent memory as atomic claims, aggregates claims across independently sampled trajectories, and constructs a conflict graph to capture inconsistencies in retrieved evidence. Claim-level extrinsic uncertainty is quantified by combining graph centrality with frequency-based support and is further combined with intrinsic generation uncertainty. Experiments on HotpotQA and StrategyQA across three LLMs demonstrate consistent improvements over existing single-step and agentic UQ baselines.

Critical strengths
  • The paper identifies an important limitation of existing UQ methods in agentic settings and provides a well-motivated solution. Instead of quantifying uncertainty only from final outputs or individual reasoning steps, MemUQ explicitly models inconsistencies in the accumulated evidence stored in agent memory. This provides a meaningful perspective on uncertainty propagation in multi-step agent interactions.

  • The proposed claim-level formulation is interpretable and empirically effective. Decomposing memory into atomic claims and combining conflict-graph centrality with frequency-based support provides fine-grained uncertainty signals while maintaining a clear interpretation. The experiments consistently demonstrate improvements across different models, datasets, and uncertainty baselines, with additional analyses validating the individual components and the reliability of the claim-processing pipeline.

Critical weaknesses
  • The current evaluation is still limited in terms of agent tasks and interaction environments. The experiments focus on two multi-hop QA benchmarks, HotpotQA and StrategyQA, both of which are primarily retrieval/reasoning tasks. Since the paper motivates MemUQ as a general framework for uncertainty quantification in LLM agents, evaluation on more diverse agentic settings, such as longer-horizon planning or heterogeneous tool-use tasks, would provide stronger evidence for its generality.

  • MemUQ remains dependent on LLM-based semantic processing. Claim decomposition, deduplication, and conflict detection are themselves performed by an LLM. Although the paper provides useful validation of this pipeline, errors or biases in these semantic judgments may directly affect the constructed conflict graph and consequently the estimated uncertainty, particularly in domains with more ambiguous or specialized evidence.

  • The related-work discussion could be further expanded to cover recent approaches that explicitly model different sources of uncertainty. In addition to sampling-, semantic-, and representation-based UQ methods currently discussed in the paper, several recent studies have investigated complementary formulations of epistemic and evidential uncertainty, e.g., Detecting Misbehaviors of Large Vision-Language Models by Evidential Uncertainty Quantification (ICLR 2026), Complementing Self-Consistency with Cross-Model Disagreement for Uncertainty Quantification (ICLR 2026), and Epistemic Uncertainty Quantification To Improve Decisions From Black-Box Models (ICLR 2026). Discussing these works and their relationship to the proposed intrinsic/extrinsic uncertainty decomposition would provide a more complete positioning of MemUQ within the recent UQ literature.

Questions for authors

See the weaknesses.

3 comments
AuthorsOpenReview ↗

Rebuttal Response to Reviewer UroQ (1/2)

We sincerely thank the reviewer for the positive assessment and for recognizing that modeling inconsistencies in the accumulated evidence gives a meaningful view of uncertainty propagation in multi-step agents. We address each point below.

The current evaluation is still limited in terms of agent tasks and interaction environments...

To evaluate MemUQ beyond retrieval and reasoning, we add the OS Interaction task of AgentBench (Liu et al., 2024). In this task, the agent operates in an interactive Ubuntu environment through multi-turn shell commands, its actions change the environment state, and many tasks require executing operations rather than answering a question. We evaluate Qwen3-30B and Gemma3-27B with the same setup as the main experiments (K=10K = 10 trajectories, 10 samples per step).

SetupMethodQwen3-30B AUROCQwen3-30B AUTACGemma3-27B AUROCGemma3-27B AUTAC
BaselinePerplexity0.60400.51910.55170.5093
BaselineNE0.60830.51380.54880.5098
BaselineSE0.60750.50920.57390.5156
BaselineSD0.55300.47290.55930.5091
BaselineDeg_E0.59350.50450.59670.5133
BaselineUProp0.57240.49350.50060.4579
Mem_ExtPerplexity0.56540.53690.50380.4322
Mem_ExtNE0.55920.53620.50420.4329
Mem_ExtSE0.58290.55300.49990.4296
Mem_ExtSD0.47770.47330.60800.5106
Mem_ExtDeg_E0.60640.56140.54270.4593
MemUQCBC_B0.68280.58350.61260.5229
MemUQCEC_E0.68090.57730.61640.5220
MemUQCCC_C0.68190.57870.61680.5221
MemUQCPRC_{PR}0.68150.58350.61640.5221

MemUQ achieves the best performance with every centrality metric on both models. With the default PageRank centrality, it improves over the baselines by 19.0% (Qwen3-30B) and 13.7% (Gemma3-27B) on average in AUROC, and over the agentic baseline UProp by 19.1% and 23.1% in AUROC. Applying single-step UQ methods to paragraph-style memory (Mem_Ext) falls below the corresponding trajectory-level baseline in four of five cases for each model. The gains therefore stem from the claim-level decomposition and conflict graph rather than from the memory representation alone.

These results indicate that MemUQ generalizes from retrieval-based QA to interactive tool use with changing environment state. We agree that longer-horizon planning tasks would further strengthen the evidence, and we consider them an important direction for future work.


We have added the AgentBench-OS results and setup details to the revised paper (Section 5, Table 2).

AuthorsOpenReview ↗

Rebuttal Response to Reviewer UroQ (2/2)

MemUQ remains dependent on LLM-based semantic processing...

We agree that the reliability of the claim pipeline is essential, since its errors could in principle be mistaken for agent uncertainty. We address this from three aspects.

Each pipeline stage is validated. We evaluate decomposition, deduplication, and conflict detection separately (Appendix G):

StageValidationResult
DecompositionSelf-contained claims95.7%
DecompositionInformation loss from previous memory0%
DecompositionClaims contradicting the input0.7%
Deduplication + conflict detectionAgreement with human labels (pipeline / GPT-5.5)80% / 80%
DeduplicationDuplicate pairs not merged (NLI audit, all pairs, Gemma3-27B, StrategyQA)0.91% (1,704 / 187,805)
Conflict detectionConflict edges not confirmed as contradictions (NLI audit, all edges)1.88% (119 / 6,343)

The pipeline, run with the same backbone as the agent (Gemma3-27B), agrees with human judgment at the same rate as a frontier model. Over the full claim set, fewer than 1% of claim pairs are duplicates that the pipeline failed to merge, and fewer than 2% of conflict edges are not confirmed as contradictions by an NLI model.

The score limits the influence of pipeline errors. By Proposition 3.1, the conflict graph does not inject uncertainty of its own. It only reweights the frequency evidence produced by the agent through the covariance term m⋅Cov⁡(Cˉ,f)m \cdot \operatorname{Cov}(\bar{C}, f). In particular, when the agent's support is uniform across claims, this covariance is zero for any conflict graph, so a spurious edge cannot change the score.

The pipeline is modular. Decomposition, deduplication, and conflict detection are independent of the uncertainty computation. Each stage can be replaced by a stronger or domain-specific model, e.g., an NLI model or a specialized LLM judge, without changing the method. In the additional AgentBench-OS evaluation, evidence consists of shell outputs rather than Wikipedia text, and MemUQ maintains its advantage there. This further indicates that the pipeline transfers beyond the QA setting.

The related-work discussion could be further expanded to cover recent approaches that explicitly model different sources of uncertainty...

We appreciate the literature suggestions. These works refine the uncertainty of a model's own predictions through evidential, epistemic, or cross-model formulations, which corresponds to the intrinsic component of MemUQ. Since the intrinsic estimator is modular (we already combine the extrinsic score with five intrinsic methods, Appendix I), they can be adopted without modifying the extrinsic score. MemUQ's extrinsic component instead targets a source specific to agentic settings: uncertainty from external evidence accumulated over multi-step interactions.


We have added these works to Section 4 and discussed their relationship to the intrinsic/extrinsic decomposition.


Thank you again for the insightful comments and we have incorporated your suggestions in the revised version of the manuscript, highlighted in blue. If there are any additional questions or concerns, we would be happy to address them.

Should you find that our responses sufficiently address your feedback, we would sincerely appreciate your consideration of raising the score, if deemed appropriate.

I appreciate the authors’ response and clarifications, which have addressed some of my concerns. However, my overall assessment remains unchanged, and I will maintain my original rating.

Reviewer_XdjgOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper focuses on the problem of estimating uncertainty of LLM agents. Specifically, the authors start from the view of agent memory to construct atomic memory and a graph to describe the uncertainty inside the memory system of the agent. The central assumption is that memory can be a good representation for uncertainty quantification of multi-steps LLM agents.

Critical strengths
  1. The idea to estimate uncertainty from memory space is well-motivated. This design shifts the attention of uncertainty estimation from the output space to the memory space.
  2. The decomposition of the uncertainty and the graph representations of memory allow the method to have good interpretability.
Critical weaknesses
  1. The experimental scope is too limited to support the claims. The proposed method targets “multi-steps LLM agents”. However, both of the benchmarks used, HotpotQA and StratygyQA, are not standard agentic tasks. The agent harness used in experiments is ReACT, which is also a very simple harness. There are no agentic tasks with widely-used agent harnesses used in experiments. So for me it’s not so clear that the method can generalize and scale up.

  2. The definition of uncertainty is fundamentally heuristic. For example, in Eq (3), I’m not so convinced that this formula can represent the uncertainty meaningfully. Specifically, why should a graph centrality represent uncertainty? I hope the author can provide detailed illustration about the design choices in their method.

  3. Insufficient discussion of related work. For example, in Line 015, “existing UQ methods target single-step or response-level settings, failing to capture how uncertainty propagates as agent context and memory evolves”. Actually, some previous works have studied uncertainty propagates in agents [1~3].

[1] SAUP: Uncertainty Propagation on LLM Agent

[2] Sequential Probabilistic Uncertainty Estimation for Parallel Multi-Agent Reasoning Systems

[3] From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents

Questions for authors
  1. Can the proposed method be applied directly to other commonly used agent harnesses and agentic tasks? For example, terminal-bench, SWE-bench.
  2. MemUQ still requires multiple independent agent trajectories samplings. How practical would this approach be for long-horizon agentic tasks where each trajectory can be expensive?
5 comments
AuthorsOpenReview ↗

Rebuttal Response to Reviewer Xdjg (1/3)

We sincerely thank the reviewer for recognizing the motivation of measuring uncertainty in the memory space and the interpretability of the graph representation. We address each point below.

The experimental scope is too limited to support the claims... Can the proposed method be applied directly to other commonly used agent harnesses and agentic tasks ...

We thank the reviewer for this suggestion. To evaluate MemUQ on a standard agentic task, we add the OS Interaction task of AgentBench (Liu et al., 2024), a widely used benchmark for LLM agents. In this task, the agent operates in an interactive Ubuntu environment through multi-turn shell commands, its actions change the environment state, and many tasks require executing operations rather than answering a question. We evaluate Qwen3-30B and Gemma3-27B with the same setup as the main experiments (K=10K = 10 trajectories, 10 samples per step).

SetupMethodQwen3-30B AUROCQwen3-30B AUTACGemma3-27B AUROCGemma3-27B AUTAC
BaselinePerplexity0.60400.51910.55170.5093
BaselineNE0.60830.51380.54880.5098
BaselineSE0.60750.50920.57390.5156
BaselineSD0.55300.47290.55930.5091
BaselineDeg_E0.59350.50450.59670.5133
BaselineUProp0.57240.49350.50060.4579
Mem_ExtPerplexity0.56540.53690.50380.4322
Mem_ExtNE0.55920.53620.50420.4329
Mem_ExtSE0.58290.55300.49990.4296
Mem_ExtSD0.47770.47330.60800.5106
Mem_ExtDeg_E0.60640.56140.54270.4593
MemUQCBC_B0.68280.58350.61260.5229
MemUQCEC_E0.68090.57730.61640.5220
MemUQCCC_C0.68190.57870.61680.5221
MemUQCPRC_{PR}0.68150.58350.61640.5221

MemUQ achieves the best performance with every centrality metric on both models. With the default PageRank centrality, it improves over the baselines by 19.0% (Qwen3-30B) and 13.7% (Gemma3-27B) on average in AUROC, and over the agentic baseline UProp by 19.1% and 23.1% in AUROC. Applying single-step UQ methods to paragraph-style memory (Mem_Ext) falls below the corresponding trajectory-level baseline in four of five cases for each model, so the gains stem from the claim-level decomposition and conflict graph rather than from the memory representation alone.

Harness generality. MemUQ does not depend on the ReAct harness. It requires only that the agent's memory be updated after each step (mt=Φ(mt−1,ot)m_t = \Phi(m_{t-1}, o_t), Eq. 2), which uses the observations the harness already produces and is independent of how actions are selected or executed. The claim memory also preserves task performance relative to ReAct (Table 4 in the revision). MemUQ can therefore be attached to other harnesses without modifying their action interface.

Scalability. The claim sets remain compact in practice (median 8–25 distinct claims per query across models and datasets). Claim processing adds only about 3% overhead relative to trajectory collection, and it is independent across queries and therefore trivially parallelizable (Section 5.3).


We have added the AgentBench-OS results and setup details to the revised paper (Section 5, Table 2).

AuthorsOpenReview ↗

Rebuttal Response to Reviewer Xdjg (2/3)

The definition of uncertainty is fundamentally heuristic....

We thank the reviewer for the question and clarify the design below.

Why centrality. Edges in the conflict graph are contradictions between claims retrieved across KK independent trajectories. A claim's centrality therefore measures how strongly it is implicated in cross-trajectory disagreement. Claims that no trajectory contradicts are isolated and receive low centrality, while claims at the core of contradictory evidence receive high centrality. Recursive metrics such as PageRank further assign higher scores to claims that conflict with other heavily contested claims. In Figure 1, for example, the two contradictory claims on the stadium's home team (Gençlerbirliği vs. Bursaspor) receive uncertainty 0.357. The uncontested claims receive 0.046. Centrality alone, however, indicates where the disagreement lies, not which side is supported. We therefore combine it with claim frequency.

Why the product. A claim should be flagged as uncertain only if it is both contested (high Cˉ\bar{C}) and weakly supported across trajectories (low ff). A contested claim that most trajectories repeat, or a rare claim that nothing contradicts, should not be. Since Cˉ\bar{C} and ff are both distributions over claims, the product admits an exact decomposition (Proposition 3.1):

1−Uext=1m⏟trajectory-level support+m⋅Cov⁡(Cˉ,f)⏟conflict-based1 - U_{\mathrm{ext}} = \underbrace{\frac{1}{m}}_{\text{trajectory-level support}} + \underbrace{m \cdot \operatorname{Cov}(\bar{C}, f)}_{\text{conflict-based}}

The 1/m1/m term reflects how the agent's support is distributed over the mm distinct claims it produced across trajectories. The covariance term measures whether the agent's support backs the claims at the center of the conflict structure (positive covariance, lower uncertainty) or whether the contested claims are the rarely retrieved ones (negative covariance, higher uncertainty). Each term therefore has a direct interpretation in terms of the agent's own behavior.

Empirical support for each component. We isolate the components with simple diagnostic baselines, evaluated as extrinsic-only scores on the same trajectories and claim graphs as MemUQ. ∣V∣|V|, 1−1/∣V∣1 - 1/|V|, and frequency-only uncertainty are rank-equivalent and therefore share one row. We report AUROC below.

BaselineGemma HQAGemma SQAQwen HQAQwen SQANano HQANano SQA
∥V∥\|V\| (= 1−1/∥V∥1 - 1/\|V\| = frequency-only)0.65590.57400.66030.61220.65040.5661
Claim-frequency entropy H(f)H(f)0.65380.55780.66470.60650.65340.5800
Edge count ∥E∥\|E\|0.67670.61050.68460.59000.64410.5709
Edge density ∥E∥/(m2)\|E\|/\binom{m}{2}0.57570.57310.64570.55970.52110.4917
MemUQ CPRC_{PR} (extrinsic only)0.67860.59160.69050.64570.65660.5815

MemUQ outperforms the claim-count baseline in all six settings, by up to 5.5% (Qwen3-30B, StrategyQA), which shows that the conflict structure adds signal beyond claim count. It also outperforms edge count in five of six settings, which shows that weighting conflicts by support is more informative than counting them. Conversely, removing the trajectory-level support component through a fixed normalization (f(ci)=ni/Kf(c_i) = n_i / K) degrades performance in all 48 AUROC and AUTAC cells (Table 5 in the revision). Both components therefore contribute to the uncertainty signal.

Scope. On calibration, we frame MemUQ as an empirical proxy for uncertainty that correlates well with correctness rather than fulfilling a formal calibration guarantee, as supported by our empirical results. This scope matches the established sampling-based UQ methods [1] [2], in which uncertainty scores are constructed without task-specific labels or model training. Without labeled calibration data, or additional assumptions or proxy supervision, probabilistic calibration with respect to ground-truth correctness cannot be directly estimated or guaranteed.

MemUQ is accordingly validated as a discriminative score, for ranking correct against incorrect outputs (AUROC/AUTAC) and for selective prediction, which is what the paper claims.


[1] Farquhar, Sebastian, et al. "Detecting hallucinations in large language models using semantic entropy." Nature 630.8017 (2024): 625-630.

[2] Qiu, Xin, and Risto Miikkulainen. "Semantic density: Uncertainty quantification for large language models through confidence measurement in semantic space." Advances in neural information processing systems 37 (2024): 134507-134533.


We have expanded Section 3.3 to explain the role of centrality and the two components of Proposition 3.1, and added the diagnostic baselines to Section 5.3 and Appendix N.

AuthorsOpenReview ↗

Rebuttal Response to Reviewer Xdjg (3/3)

Insufficient discussion of related work....

We appreciate the literature suggestions. SAUP [1] is already discussed in our related work (Zhao et al., 2025, Section 4). It aggregates per-step uncertainty along the agent's trajectory using a trained Hidden Markov Model. Together with UProp (Duan et al., 2025), which we also compare against, it models how uncertainty propagates along the sequence of agent decisions. MemUQ captures a complementary signal: it measures the consistency of the evidence accumulated in the agent's memory across independently sampled trajectories. It also requires no training.

We have added [2] and [3] to the related work and discussed their relationship to MemUQ. We have also revised the statement in Line 015 to "most existing UQ methods", so that it accurately reflects prior work on uncertainty propagation in agents.

[1] SAUP: Uncertainty Propagation on LLM Agent

[2] Sequential Probabilistic Uncertainty Estimation for Parallel Multi-Agent Reasoning Systems

[3] From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents


We have expanded the discussion of uncertainty propagation in LLM agents in Section 4 accordingly.

MemUQ still requires multiple independent agent trajectories samplings...

We thank the reviewer for raising this practical concern and address it from three aspects.

Shared sampling budget. Multiple trajectory samples are required by all sampling-based UQ methods for agents, including the compared baselines (SE, SD, Deg_E, and UProp). All methods in our experiments use the same budget of K=10K = 10 trajectories and 10 samples per step. The cost specific to MemUQ is claim processing, which takes 2.03 seconds per question on Gemma3-27B and adds only about 3% overhead relative to trajectory collection (Section 5.3). Since trajectories and claim processing are independent across samples and queries, both can be fully parallelized.

Robustness to fewer trajectories. MemUQ remains effective at a reduced sampling budget (Appendix J). With half the trajectories (K=5K = 5), MemUQ still outperforms every Mem_Ext method evaluated at K=10K = 10 on both datasets. The sampling budget can therefore be halved and still outperform the full-budget baseline, which gives real headroom for reducing deployment cost rather than fixing it at K=10. It also retains most of its K=10K = 10 performance (Gemma3-27B, AUROC; percentage of the K=10K = 10 value in parentheses):

SettingK=10K=10K=5K=5
HotpotQA (CPRC_{PR})0.69710.6630 (95%)
StrategyQA (CPRC_{PR})0.60510.5674 (94%)

Scaling with horizon length. The claim-based memory remains compact as interactions proceed. Final-step memory uses under 5% of the configured capacity (Table 13 in the revision), and the deduplicated claim set has a median of 8–25 claims per query across models and datasets. The conflict graph therefore remains small, and its construction cost is negligible relative to trajectory collection. Our additional evaluation on AgentBench-OS, a multi-turn interactive environment, shows that MemUQ maintains its advantage under the same budget, with average AUROC improvements of 19.0% (Qwen3-30B) and 13.7% (Gemma3-27B) over the baselines.

We agree that reducing the number of trajectories for long-horizon tasks, e.g., through adaptive sampling that stops once the conflict graph stabilizes, is an important direction. We have discussed it in the revised limitations (Section 6).


Thank you again for the insightful comments and we have incorporated your suggestions in the revised version of the manuscript, highlighted in blue. If there are any additional questions or concerns, we would be happy to address them.

Should you find that our responses sufficiently address your feedback, we would sincerely appreciate your consideration of raising the score, if deemed appropriate.

Reviewer_3mxhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MemUQ, an uncertainty quantification framework for multi-step LLM agents. The method represents agent memory as atomic claims collected across multiple trajectories, constructs a conflict graph between claims, and combines graph centrality with claim frequency to estimate extrinsic uncertainty. This is combined with conventional intrinsic uncertainty. Experiments on HotpotQA and StrategyQA across three LLMs show consistent AUROC improvements over single-step UQ methods, a memory-level baseline, and a reimplementation of UProp.

Critical strengths
  • This paper addresses an important and relatively underexplored problem: uncertainty estimation for multi-step LLM agents rather than isolated generations.
  • Using accumulated memory rather than only actions or final outputs is intuitive and provides interpretable claim-level uncertainty.
  • The experiments cover three different models and two datasets, with several UQ baselines and extensive ablations. The authors investigate intrinsic versus extrinsic uncertainty, trajectory count, memory representation, and claim-pipeline reliability.
  • The claim-level representation provides useful qualitative interpretability, and the empirical AUROC improvements are substantial in several settings.
Critical weaknesses
  • The proposed extrinsic score is strongly confounded by the number of distinct claims. The paper defines f(ci)=ni∑jnjf(c_i)=\frac{n_i}{\sum_j n_j} and Uext(x)=1−∑iCˉ(ci)f(ci)U_{\mathrm{ext}}(x)=1-\sum_i \bar{C}(c_i)f(c_i). Proposition 3.1 further gives 1−Uext(x)=1m+m⋅Cov(Cˉ,f)1-U_{\mathrm{ext}}(x)=\frac{1}{m}+m\cdot \mathrm{Cov}(\bar{C},f), where m=∣V∣m=|V| is the number of distinct claims. Consider an ideal case where every trajectory produces exactly the same mm mutually consistent claims. The conflict graph is edgeless, so the method assigns uniform centrality, Cˉ(ci)=1m\bar{C}(c_i)=\frac{1}{m}. Since every claim appears equally often, f(ci)=1mf(c_i)=\frac{1}{m}. Therefore, Uext=1−∑i=1m1m2=1−1mU_{\mathrm{ext}}=1-\sum_{i=1}^{m}\frac{1}{m^2}=1-\frac{1}{m}. Thus, perfectly consistent evidence receives uncertainty approaching 1 as the number of claims increases. This seems inconsistent with the interpretation of the score as conflict-based uncertainty.

  • The normalized frequency is not really a claim-level probability of correctness. A claim that occurs in every rollout can still receive very low f(ci)f(c_i) when many other claims are present. This means the uncertainty assigned to one claim can change substantially when unrelated claims are added. The paper motivates this as incorporating task complexity, but task complexity and epistemic uncertainty are not necessarily the same quantity.

  • Simple baselines needed to diagnose this confound are missing. I would like to see baselines using only ∣V∣|V|, 1−1/∣V∣1-1/|V|, claim-frequency entropy, number or density of conflict edges, and frequency-only uncertainty. Given Proposition 3.1, these comparisons are important for determining whether the gains actually come from conflict-graph structure or primarily from claim-set size. The fact that multiple centrality measures perform similarly does not by itself establish that graph structure is the primary source of improvement.

  • The experimental setting remains relatively narrow for the claims about LLM agents. HotpotQA and StrategyQA are both QA/reasoning benchmarks, and evaluation uses only the first 500 examples from each dataset. Evaluation on longer-horizon agents with richer tool use, changing environments, or non-QA objectives would provide stronger evidence that the approach generalizes to agentic uncertainty rather than specifically retrieval and reasoning uncertainty.

Questions for authors
  • Which trajectory’s answer defines correctness, and how is correctness judged on HotpotQA (exact match, F1, or an LLM judge)?
  • How many queries have conflict-free graphs? What is the distribution of m and of the edge count?
  • In Table 13, the GPT-4.1-Nano rows for Mem_Ext and Mem_Claim are identical for Perplexity and NE on both datasets, while the other models differ. Is this a copy error?
  • “Eq. equation 2” and “Equation equation 6” are LaTeX reference errors.
  • The Figure 12 caption says “given two claims,” but the prompt takes a claim and a list of claims.
  • The Table 4 caption calls div_10 “Diversity-based,” which does not match the text.
4 comments
AuthorsOpenReview ↗

Rebuttal Response to Reviewer 3mxh (1/3)

We sincerely thank the reviewer for the careful reading of Proposition 3.1 and for the precise derivation of the edgeless case. As both points concern the normalization of ff, we address them together.

The proposed extrinsic score is strongly confounded by the number of distinct claims...

The normalized frequency is not really a claim-level probability of correctness. A claim that occurs in every rollout can still receive very low f(ci)f(c_i)...

We would like to clarify that UextU_{\mathrm{ext}} is not intended as a purely conflict-based score. As demonstrated in Proposition 3.1, it combines two components:

1−Uext=1m⏟trajectory-level support+m⋅Cov⁡(Cˉ,f)⏟conflict-based1 - U_{\mathrm{ext}} = \underbrace{\frac{1}{m}}_{\text{trajectory-level support}} + \underbrace{m \cdot \operatorname{Cov}(\bar{C}, f)}_{\text{conflict-based}}

The m⋅Cov⁡(Cˉ,f)m \cdot \operatorname{Cov}(\bar{C}, f) term is the conflict-based component. It shifts the score according to whether the agent's support backs or avoids the claims at the center of the conflict structure. The 1/m1/m term is the trajectory-level support component, which arises from normalizing ff by the total claim mass.

We agree that the wording in Section 3.3 is inaccurate: ff is not a probabilistic estimate of correctness, but the share of the agent's evidence mass assigned to each claim, interpreted relative to the other claims of the same query. This normalization captures how trajectories distribute their support. Verbose trajectories spread their mass over many claims (lower per-claim weight), while focused trajectories concentrate it (higher per-claim weight), implicitly reflecting trajectory-level confidence.

The ideal example corresponds to the zero-covariance case, in which the conflict-based component vanishes and only the support component remains. The resulting score 1−1/m1 - 1/m is therefore consistent with the design: a large claim set with no conflicts is not treated as certain. Agreement among KK rollouts does not by itself establish correctness, and in multi-step agents a larger claim set means the answer depends on more diverse evidences, which increases the opportunity for error accumulation across steps.

The per-claim alternative is evaluated in the paper as an ablation. div_10 replaces the trajectory-dependent normalizer with a fixed, claim-number-independent constant (K=10K = 10), i.e., f(ci)=ni/Kf(c_i) = n_i / K, which is precisely the definition from the concern raised; under it, the perfectly consistent case receives Uext=0U_{\mathrm{ext}} = 0. For our reported configuration with PageRank centrality, the trajectory-dependent definition wins in every setting (Table 5 in the revision):

CPRC_{PR} AUROCGemma3-27BQwen3-30BGPT-4.1-Nano
HotpotQA, Freq0.69710.70480.6586
HotpotQA, div_100.66460.66240.5932
StrategyQA, Freq0.60510.65390.5911
StrategyQA, div_100.53740.56410.5414

Across datasets and models, frequency normalization consistently outperforms the invariant alternative. This shows that the trajectory-level support component is informative for uncertainty estimation, rather than a confound to be removed.


We have revised Equation 7 to highlight that UextU_{\mathrm{ext}} combines a trajectory-level support component and a conflict-based component, and replaced "probabilistic estimate of correctness" and the task-complexity motivation with the evidence-share interpretation above (Section 3.3).

AuthorsOpenReview ↗

Rebuttal Response to Reviewer 3mxh (2/3)

Simple baselines needed to diagnose this confound are missing...

We thank the reviewer for the suggested diagnostics. We evaluate all requested baselines as extrinsic-only scores, without the intrinsic component, on the same trajectories and claim graphs as MemUQ. Three of the requested baselines are rank-equivalent and therefore share one row: ∣V∣|V| and 1−1/∣V∣1 - 1/|V| are monotone in each other, and frequency-only uncertainty with uniform claim weights reduces to 1−∑i1mfi=1−1/m1 - \sum_i \frac{1}{m} f_i = 1 - 1/m. We report AUROC below.

BaselineGemma HQAGemma SQAQwen HQAQwen SQANano HQANano SQA
∥V∥\|V\| (= 1−1/∥V∥1 - 1/\|V\| = frequency-only)0.65590.57400.66030.61220.65040.5661
Claim-frequency entropy H(f)H(f)0.65380.55780.66470.60650.65340.5800
Edge count ∥E∥\|E\|0.67670.61050.68460.59000.64410.5709
Edge density ∥E∥/(m2)\|E\|/\binom{m}{2}0.57570.57310.64570.55970.52110.4917
MemUQ CPRC_{PR} (extrinsic only)0.67860.59160.69050.64570.65660.5815

Claim count carries signal but does not explain the gains. ∣V∣|V| alone is a competitive signal, which is consistent with the trajectory-level support component of Proposition 3.1. MemUQ outperforms it in all six settings, by up to 5.5% (Qwen3-30B, StrategyQA). This margin isolates the contribution of the covariance term, i.e., the conflict structure beyond claim count. Claim-frequency entropy, a finer summary of the support distribution, likewise falls below MemUQ in all six settings.

Conflict structure is informative, and centrality uses it most effectively. Edge count is the strongest simple baseline, which confirms that the conflict graph itself carries uncertainty signal. However, edge count weights every conflict equally. MemUQ weights each conflict by the support the agent assigns to the contested claims, and it outperforms edge count in five of six settings. Edge density normalizes away the claim count and performs worst overall. This indicates that the support and conflict components are complementary rather than redundant.


We have added these diagnostics to the appendix (Appendix N) and summarized them in Section 5.3, and removed the statement in Section 5.2 that attributed the improvement to the graph structure alone.

The experimental setting remains relatively narrow for the claims about LLM agents...

We thank the reviewer for this suggestion. To evaluate MemUQ beyond retrieval and reasoning, we add the OS Interaction task of AgentBench (Liu et al., 2024). In this task, the agent operates in an interactive Ubuntu environment through multi-turn shell commands, its actions change the environment state, and many tasks require executing operations rather than answering a question. We evaluate Qwen3-30B and Gemma3-27B with the same setup as the main experiments (K=10K = 10 trajectories, 10 samples per step).

SetupMethodQwen3-30B AUROCQwen3-30B AUTACGemma3-27B AUROCGemma3-27B AUTAC
BaselinePerplexity0.60400.51910.55170.5093
BaselineNE0.60830.51380.54880.5098
BaselineSE0.60750.50920.57390.5156
BaselineSD0.55300.47290.55930.5091
BaselineDeg_E0.59350.50450.59670.5133
BaselineUProp0.57240.49350.50060.4579
Mem_ExtPerplexity0.56540.53690.50380.4322
Mem_ExtNE0.55920.53620.50420.4329
Mem_ExtSE0.58290.55300.49990.4296
Mem_ExtSD0.47770.47330.60800.5106
Mem_ExtDeg_E0.60640.56140.54270.4593
MemUQCBC_B0.68280.58350.61260.5229
MemUQCEC_E0.68090.57730.61640.5220
MemUQCCC_C0.68190.57870.61680.5221
MemUQCPRC_{PR}0.68150.58350.61640.5221

MemUQ achieves the best performance with every centrality metric on both models. With the default PageRank centrality, it improves over the baselines by 19.0% (Qwen3-30B) and 13.7% (Gemma3-27B) on average in AUROC, and over the agentic baseline UProp by 19.1% and 23.1% in AUROC. Notably, applying single-step UQ methods to paragraph-style memory (Mem_Ext) falls below the corresponding trajectory-level baseline in four of five cases for each model. The gains therefore stem from the claim-level decomposition and conflict graph rather than from the memory representation alone. This is consistent with the memory representation ablation (Table 14 in the revision).

These results indicate that MemUQ generalizes from retrieval-based QA to interactive tool use with changing environment state.


We have added the AgentBench-OS results and setup details to the revised paper (Section 5, Table 2).

AuthorsOpenReview ↗

Rebuttal Response to Reviewer 3mxh (3/3)

Which trajectory's answer defines correctness, and how is correctness judged on HotpotQA (exact match, F1, or an LLM judge)?

Correctness is defined by the final answer of a deterministic trajectory with temperature = 0, scored by token-level F1 against the gold answer after standard normalization (maximum over gold aliases), with a query counted correct when F1 > 0.3. For StrategyQA's yes/no answers this reduces to exact match. We have stated this in the revised experimental setup (Section 5.1).

How many queries have conflict-free graphs? What is the distribution of mm and of the edge count?

We report the requested statistics over all evaluated queries (500 per dataset):

SettingConflict-free graphsmm: mean / median / IQR (interquartile range)∥E∥\|E\|: mean / median / IQR
Gemma3-27B, HotpotQA8.0%27.8 / 25 / [16, 36]25.5 / 10 / [3, 35]
Gemma3-27B, StrategyQA9.2%25.5 / 23 / [17, 31]12.7 / 7 / [3, 15]
Qwen3-30B, HotpotQA35.0%11.0 / 9 / [6, 14]8.9 / 2 / [0, 10]
Qwen3-30B, StrategyQA44.4%8.3 / 8 / [5, 10]2.5 / 1 / [0, 3]
GPT-4.1-Nano, HotpotQA5.8%17.5 / 12 / [7, 21]32.1 / 24 / [6, 24]
GPT-4.1-Nano, StrategyQA9.0%15.0 / 12 / [9, 18]11.0 / 13 / [7, 16]

For Gemma3-27B and GPT-4.1-Nano, conflict-free graphs are rare (5.8–9.2%), so the conflict-based component is active for the vast majority of queries. Qwen3-30B produces the most consistent trajectories, with the smallest claim sets and the largest share of conflict-free graphs (35.0–44.4%). The edge count is right-skewed in most settings, indicating that conflicts concentrate in a subset of harder queries.

For conflict-free queries, UextU_{\mathrm{ext}} reduces to the trajectory-level support component 1−1/m1 - 1/m. Any advantage over the ∣V∣|V| baseline therefore comes from queries with conflicts. On Qwen3-30B StrategyQA, conflicts are present in only 55.6% of queries, yet MemUQ achieves its largest margin over ∣V∣|V| there (5.5%). This shows that the conflict-based component contributes signal even when it is active for only about half of the queries.


We have added these statistics to the appendix (Appendix O).

In Table 13, the GPT-4.1-Nano rows for Mem_Ext and Mem_Claim are identical for Perplexity and NE on both datasets, while the other models differ. Is this a copy error?

Thanks for catching this, the Mem_Claim results for Perplexity and NE were incorrectly overwritten by the Mem_Ext results. Recomputed from the per-trajectory outputs, the Mem_Claim values (AUROC / AUTAC) are 0.6034 / 0.5339 for Perplexity and 0.6168 / 0.5529 for NE on HotpotQA, and 0.5624 / 0.7006 (Perplexity) and 0.5710 / 0.6932 (NE) on StrategyQA. We have updated this in the revised version (Table 14).

"Eq. equation 2" and "Equation equation 6" are LaTeX reference errors.

The Figure 12 caption says "given two claims," but the prompt takes a claim and a list of claims.

The Table 4 caption calls div_10 "Diversity-based," which does not match the text.

Thank you for catching these. Our revision fixes the duplicated "equation" references, corrects the Figure 12 caption to "given a claim and the list of other claims", and renames div_10 in the Table 4 caption (Table 5 in the revision) to the fixed-constant normalization as described in the text.


Thank you again for the insightful comments and we have incorporated your suggestions in the revised version of the manuscript, highlighted in blue. If there are any additional questions or concerns, we would be happy to address them.

Should you find that our responses sufficiently address your feedback, we would sincerely appreciate your consideration of raising the score, if deemed appropriate.

Dear Reviewer 3mxh,

We sincerely hope that our responses have adequately addressed your concerns, and we would be happy to provide further clarification or respond to any additional questions.

If you feel that our revisions have satisfactorily resolved your previous concerns, we would greatly appreciate your reconsideration of the paper’s evaluation and the possibility of a more favorable assessment.

Best Regards,

Authors

Comments on the paper

2 comments
Area_Chair_W4mMOpenReview ↗

Gentle Reminder: ICLR Rebuttal Discussion Deadline – November 18

Dear Reviewers,

Thank you very much for your time, thoughtful reviews, and valuable contributions to the evaluation process. Thank you to the reviewers who have already interacted and provided additional feedback to the authors!

The authors have carefully addressed your comments and concerns, and the discussion period will conclude on November 18. We would greatly appreciate it if you could take a few moments to review their responses and results, engage in the discussion, and indicate whether their clarifications or additional evidence affect your assessment.

Your continued engagement is essential to ensuring a rigorous, constructive, and fair evaluation process.

Thank you again for your time, expertise, and dedication!

Best regards, Area Chair

AuthorsOpenReview ↗

Rebuttal Summary and General Comments

We sincerely thank all reviewers for their insightful reviews and constructive suggestions, and for recognizing the motivation of measuring uncertainty in the memory space, the meaningful view of uncertainty propagation in multi-step agents, and the interpretability of the claim-level graph representation.

We would like to re-emphasize the main contribution of our work. MemUQ quantifies the uncertainty of multi-step LLM agents in the memory space rather than the action space. It decomposes agent memory into atomic claims across KK independently sampled trajectories, builds a cross-trajectory conflict graph, and combines graph centrality with claim frequency to estimate extrinsic uncertainty arising from conflicting evidence. The framework is training-free, yields interpretable claim-level uncertainty, and enables established single-step UQ methods to operate on multi-step agents.


We have revised our paper (changes highlighted in blue) and summarize the additional experiments and clarifications below:

Broader agentic evaluation (Reviewers 3mxh, UroQ, Xdjg). We added the OS Interaction task of AgentBench, where the agent issues multi-turn shell commands in an interactive Ubuntu environment whose state changes with its actions. MemUQ achieves the best performance with every centrality metric on both Qwen3-30B and Gemma3-27B. With PageRank, it improves average AUROC over the baselines by 19.0% and 13.7%, and over the agentic baseline UProp by 19.1% and 23.1%, respectively.

Interpretation of the extrinsic score (Reviewers 3mxh, Xdjg). Following Proposition 3.1, we clarified that UextU_{\mathrm{ext}} combines a trajectory-level support component (1/m1/m) and a conflict-based component (m⋅Cov⁡(Cˉ,f)m \cdot \operatorname{Cov}(\bar{C}, f)). We revised Section 3.3 to interpret ff as the share of evidence mass assigned to each claim rather than a probability of correctness. We also explained the design: centrality locates where trajectories disagree, frequency indicates which side the agent supports, and their product flags claims that are both contested and weakly supported. Replacing the trajectory-dependent normalization with a fixed constant degrades performance in every setting.

Diagnostic baselines (Reviewers 3mxh, Xdjg). We evaluated the requested simple baselines: claim count ∣V∣|V| (rank-equivalent to 1−1/∣V∣1 - 1/|V| and frequency-only uncertainty), claim-frequency entropy, edge count, and edge density. MemUQ outperforms claim count in all six settings (by up to 5.5%) and edge count in five of six, showing that the conflict structure adds signal beyond claim count and that support-weighted conflicts are more informative than raw conflict counts (Appendix N).

Reliability of the claim pipeline (Reviewer UroQ). Each stage is validated: 95.7% of claims are self-contained with no information loss, the pipeline agrees with human labels at the same rate as GPT-5.5 (80%), fewer than 1% of duplicate pairs are missed, and fewer than 2% of conflict edges are not confirmed by an NLI model. By construction, the conflict graph only reweights the agent's own frequency evidence and cannot inject uncertainty on its own, and each stage can be replaced by a stronger or domain-specific model.

Practicality and harness generality (Reviewer Xdjg). All methods share the same budget of K=10K = 10 trajectories, and claim processing adds only about 3% overhead. With K=5K = 5, MemUQ retains 94–95% of its AUROC and still outperforms all memory-based baselines at K=10K = 10. The claim memory remains compact (median 8–25 claims per query). MemUQ requires only a per-step memory update and is therefore independent of the ReAct harness. We discuss adaptive sampling for long-horizon tasks in the limitations.

Additional clarifications (Reviewer 3mxh). We specified the correctness criterion, reported the distribution of claim counts, edge counts, and conflict-free graphs (Appendix O), corrected a copy error in Table 13, and fixed the reported typos.

Related work (Reviewers UroQ, Xdjg). We added the suggested works on uncertainty sources and uncertainty propagation in agents, discussed their relationship to our intrinsic/extrinsic decomposition, and revised the claim on existing UQ methods accordingly.


Lastly, we sincerely thank all reviewers for their constructive feedback, which has helped us broaden the evaluation, clarify the design of the uncertainty score, and strengthen the presentation of our work. We hope that our revisions and additional experiments adequately address their concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.