{"id":"503db3dd-9b58-49b4-b070-a9701df67f53","arxiv_id":"2506.17419","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"UProp estimates extrinsic uncertainty in multi-step LLM decision-making by approximating pointwise mutual information over trajectory samples, improving AUROC for identifying incorrect agent outputs by 2.3 to 11% over single-step baselines.","lead":"UProp adds an 'inherited uncertainty' term to LLM uncertainty scores, estimated from how much earlier agent decisions vary, and it improves detection of wrong answers on multi-step agent benchmarks with GPT-4.1, GPT-3.5, and open-weight models. It matters because safety-critical uses of LLM agents need a trustworthy signal for when to abstain or ask for help.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (8) cancels the y_t likelihood, so dPMI reduces to a kernel-density score over previous actions and cannot equal the PMI/KL of Eq. (4); Theorem 2's Eq. (18) also samples from the conditional prefix distribution rather than the required marginal p(y_{t-1}|x).","rationale":"I evaluate the paper on its own terms. The empirical section is the strongest part: UProp consistently improves AUROC and AUARC across AgentBench-OS, HotpotQA, and StrategyQA over five LLMs, and the ablation study shows that the extrinsic term contributes. But the central contribution is advertised as 'principled, information-theoretic,' and Theorem 2 is the stated justification for Eq. (8). The proof has a genuine gap: the estimator that results from Eq. (7) cancels the current-step likelihood and becomes a function only of previous-action kernel distances, and the Monte Carlo step in Eq. (18) draws from conditional, not marginal, distributions. These are not stylistic issues; they mean dPMI is not the claimed MI/PMI approximation. The paper's own Limitations section acknowledges sampling deviation and latency but does not flag this formal mismatch. Because the empirical gains could be driven by the 'surprise of the previous action' heuristic rather than by the information-theoretic quantity, the central formal claim should be treated cautiously. This supports the reader's CONDITIONAL verdict. I do not recommend rejection: the heuristic may be useful, and the empirical comparisons are consistent across models. A conditional acceptance requiring corrected proofs, released code, and error bars is appropriate.","tokens_in":20073,"tokens_out":10496,"duration_ms":106819,"concrete_test":"Build a synthetic two-step process with known pθ(y1|x) and smooth pθ(y2|y1,x), e.g., Gaussian mixtures, where conditional samples pθ(y1|prefix) differ from the marginal p(y1|x). Compute the exact PMI(y2; y1=y1^k|x) by enumeration and the Eq. (8) dPMI from the paper's TDP sampling protocol. If dPMI does not track the exact PMI as N grows, while the same computation with samples from the true marginal p(y1|x) does converge, Theorem 2's proof is invalid. Equivalently, verify that dPMI is invariant to changes in pθ(y2|y1^k,x) for fixed y1^k; if it is invariant, it cannot be a PMI estimator.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The formal core of UProp is Theorem 2 (Section A.5), which claims that the dPMI estimator in Eq. (8) converges to the PMI/KL defined in Eq. (4). This claim fails on two independent grounds. First, substituting Eq. (7) into Eq. (6) gives dPMI = -log Σ_n K_N(d(y_{t-1}^{(n)}, y_{t-1}^{(k)})). The conditional likelihood pθ(y_t|y_{t-1}^{(k)},x) appears in both the numerator and every denominator term and cancels, so dPMI does not depend on y_t at all. But PMI(yt; y_{t-1}^{(k)}|x) is an expectation over y_t of the log ratio involving pθ(y_t|y_{t-1}^{(k)},x), which generally varies with y_t. A quantity independent of y_t cannot approximate this quantity. Second, even if the cancellation were repaired, Eq. (18) replaces the marginal p(y_t|x) with a kernel-weighted average using samples drawn from pθ(y_{t-1}|y_{1:t-2}^{(k)},x) under the TDP protocol, not from p(y_{t-1}|x). The Monte Carlo approximation in Eq. (18) therefore targets the wrong distribution. Local smoothness of pθ(y_t|·,x) near y_{t-1}^{(k)} does not close this gap, because the omitted mass of the marginal outside the kernel neighborhood is uncontrolled. Thus Theorem 2 is not established as stated, and UProp's extrinsic term is at best a heuristic measure of how surprising the selected previous action is under its own conditional distribution.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces UProp, an uncertainty quantification method for LLM multi-step agentic decision-making. It decomposes the total uncertainty at each decision step into an intrinsic component, estimated by single-step predictive entropy, and an extrinsic component, defined as a mutual-information quantity between the current decision and preceding decisions. UProp estimates the extrinsic component by sampling multiple trajectory-dependent decision processes (TDPs), computing a pointwise mutual information (PMI) score for each trajectory, and aggregating these scores with a step-length normalization. The authors provide two convergence theorems, one for TDP sampling (Theorem 1) and one for the PMI approximation (Theorem 2), and evaluate the method on AgentBench-OS, HotpotQA, and StrategyQA with GPT-4.1-Nano, GPT-3.5-Turbo, Gemma-2-27b-it, DeepSeek-V3, and Qwen2.5-72B-Instruct. The paper reports AUROC improvements of 2.3% to 11% over single-turn uncertainty baselines and includes ablations, sampling-efficiency studies, and selective-prediction experiments.","tokens_in":20513,"tokens_out":6784,"duration_ms":68403,"significance":"The conceptual decomposition of decision uncertainty into intrinsic and extrinsic components is appealing, and the TDP sampling protocol is a practical way to address the exponential decision space in multi-step LLM reasoning. The empirical evaluation is broad in terms of benchmarks, backbone LLMs, and baselines, and the paper explicitly studies sampling efficiency and ablation of the two uncertainty components. If the theoretical claims were established, the paper would make a solid contribution to LLM uncertainty quantification. However, the current proof of Theorem 2 has a distribution mismatch that undermines the claim that the proposed dPMI estimator converges to the defined PMI, and the reported empirical gains lack error bars and significance tests. The method may still be useful as a heuristic score, but the paper's central theoretical justification is not yet established.","major_comments":[{"comment":"The proof of Theorem 2 replaces an integral against the marginal p(y_{t-1}|x) with a Monte Carlo average over TDP samples y_{t-1}^{(i)}, but those samples are drawn from the conditional distribution p_θ(y_{t-1}|y_{1:t-2}^{(k)},x) of a single trajectory prefix. These are generally different distributions, and the local-smoothness assumption on p_θ(y_t|·,x) does not control the discrepancy between the conditional and marginal distributions of y_{t-1}. The omitted mass of the marginal outside the kernel neighborhood is therefore uncontrolled, and Theorem 2 is not established as stated. The authors need either a sampling scheme that targets the marginal, or an additional argument that the conditional samples are representative of the marginal with a quantitative bound on the approximation error.","section":"Section A.5, Eq. (18)"},{"comment":"Substituting Eq. (7) into Eq. (6) causes the conditional likelihood p_θ(y_t|y_{t-1}^{(k)},x) to factor out of the numerator and denominator, so dPMI reduces to -log Σ_n K_N(d(y_{t-1}^{(n)}, y_{t-1}^{(k)})), which is independent of y_t. This is consistent with the local-smoothness approximation only if the log-ratio in the PMI is treated as constant in y_t, but the paper does not state this explicitly. As written, Eq. (8) measures the local density of the preceding action under the TDP samples rather than the mutual information defined in Eq. (4). The authors should either present dPMI as a heuristic proxy for extrinsic uncertainty, weakening the wording around Theorem 2, or derive a corrected estimator that retains dependence on y_t.","section":"Section 3.3, Eq. (8)"},{"comment":"No confidence intervals, standard deviations, or significance tests are reported for the AUROC and AUARC results. Several reported differences are small relative to the likely sampling variability, for example StrategyQA GPT-3.5-Turbo in Table 1 (UProp 0.604 vs. SE 0.623), and the paper's claim of significant outperformance by 2.3% to 11% AUROC is not supported without error bars or a paired statistical test. Please add uncertainty estimates and significance tests, such as bootstrapping or the DeLong test, for at least the main results in Tables 1, 2, and 4.","section":"Tables 1-4 and Figure 2"},{"comment":"The Gaussian kernel sharpness τ is a free hyperparameter that directly controls dPMI through K_N, but the paper reports no sensitivity analysis and does not state how τ was chosen or whether the same value was used across all benchmarks and models. Since the reported gains could depend on this choice, the authors should report AUROC for a range of τ values or provide a principled selection procedure.","section":"Section 3.3 and Section 4.1"}],"minor_comments":[{"comment":"In the last line of the proof of Theorem 1, the text says convergence holds 'with N→∞', but the statement of the theorem requires Z→∞; the proof also relies on Theorem 2 for the dPMI terms, so it is not independent of the PMI approximation.","section":"Section A.4"},{"comment":"The index n is used ambiguously both as the summation index over TDP samples and as the label of the selected trajectory sample, and Eq. (18) contains typographical errors such as 'dist(yyt−1,y' and an unclosed parenthesis. Please clean up the notation and typos.","section":"Equations (7) and (18)"},{"comment":"Several entries in the tables have formatting errors that make them hard to read, such as '0.6200.707' in Table 1 and '0.5510.506' in Table 4; please insert proper spacing or column separators.","section":"Tables 1 and 4"},{"comment":"The normalization factor λ_z is defined using dPMI terms, and because the kernel weights in Eq. (8) are not normalized, dPMI can be negative if the kernel sum exceeds one. The paper should clarify whether extrinsic uncertainty can be negative and how such cases are handled in the total uncertainty estimate.","section":"Section 3.3, Step Length-Normalization"},{"comment":"The paper says code will be released, but it does not provide the exact τ value, random seeds, or the number of sampled trajectories per question in the appendix; including these reproducibility details would strengthen the empirical claims.","section":"Section 4.1 and Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the proof of Theorem 2 and the interpretation of Eq. (8). If the authors cannot close the distribution mismatch, they should reframe UProp as an empirical heuristic for extrinsic uncertainty rather than claim a principled mutual-information approximation. The empirical study is useful, but the theoretical narrative currently overstates what has been established. I would not accept the paper in its present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a useful empirical paper with a broken convergence proof. The TDP sampling scheme and the reduction of PMI to a kernel-density score over previous actions are new in this space, and the experiments show consistent AUROC gains. But Theorem 2, as proved in Section A.5, does not go through, and the estimator is better described as a heuristic.\n\nWhat the paper does well: it identifies a real gap—single-turn UQ methods ignore how uncertainty accumulates across agent steps—and it proposes a cheap, model-agnostic fix. The decomposition into intrinsic and extrinsic uncertainty is textbook entropy chaining, but the TDP protocol and the negative-log-kernel-density estimator are genuinely new. The empirical evaluation is broad: five LLMs, three benchmarks, multiple baselines, and consistent gains (2.3% to 11% AUROC). The ablation showing that removing the extrinsic term hurts more than removing the intrinsic term is the strongest evidence that the idea has merit. The paper also acknowledges its own limitations (sampling noise, latency, closed-source model reproducibility), which is more honest than most.\n\nWhere it falls apart: the formal justification. The proof of Theorem 2 in Section A.5 approximates the marginal p(y_t|x) with a kernel-weighted average over samples drawn from the conditional prefix distribution—not from the marginal p(y_{t-1}|x). Local smoothness of the conditional likelihood does not patch that; the mass of the marginal outside the kernel neighborhood is uncontrolled. On top of that, substituting Eq. (7) into Eq. (6) makes the y_t likelihood cancel, so dPMI in Eq. (8) does not depend on the current decision at all. It cannot be converging to the PMI/KL of Eq. (4), which is an expectation over y_t. The estimator is really just a negative log kernel density over previous actions—a measure of how surprising the selected action is under its own conditional distribution. That may be a perfectly good heuristic, but it is not the claimed mutual information.\n\nSmaller issues: no error bars or significance tests, the code is not actually available yet, and the kernel sharpness tau is a hand-chosen hyperparameter with no reported sensitivity. The empirical claims are plausible but not pinned down.\n\nWho this is for: anyone working on uncertainty quantification for LLM agents. The empirical recipe is worth trying even if the theory is not certified. A serious referee should see this—it addresses an important problem and has enough empirical substance to warrant a major-revision cycle that fixes or removes the overclaimed theory.","headline":"Useful empirical work on propagating uncertainty through LLM agent trajectories, but the main convergence theorem does not hold as stated.","tokens_in":20994,"tokens_out":2912,"would_cite":false,"duration_ms":29424,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"UProp argues that a language model's uncertainty during multi-step decisions splits into intrinsic uncertainty about the current step and extrinsic uncertainty inherited from earlier decisions, and that tracking the inherited part…","keywords":["uncertainty quantification","large language models","multi-step decision-making","LLM agents","mutual information","pointwise mutual information","uncertainty propagation","hallucination detection"],"falsifier":"Enumerate a toy two-step decision problem with a tiny action vocabulary, compute the true pointwise mutual information exactly by summing over all pairs of decisions, and compare it with UProp's dPMI at growing $N$ and $Z$; if the gap does not shrink to zero for appropriately shaped kernels with fixed sharpness $\\tau$, the convergence claim fails. A second check: run UProp on two trajectories that reach the same observation through very different preceding actions; if the score moves with the surface similarity of the actions rather than with the information state, the kernel is measuring text distance, not inherited uncertainty.","tokens_in":19851,"feed_emoji":"🤖","tokens_out":15571,"duration_ms":139336,"temperature":0.7,"pith_summary":"This paper tries to answer when an LLM should be trusted as it makes several decisions in a row. Its claim is that the uncertainty of the decision at step t is the sum of two pieces: how unsure the model is about the current step given all prior steps, and how much uncertainty is inherited from earlier decisions because those earlier choices could have gone differently. Existing single-turn uncertainty quantification targets only the first piece, so the paper introduces UProp to estimate the second piece as a pointwise mutual information over sampled decision trajectories. On AgentBench-OS, HotpotQA, and StrategyQA with several LLMs, adding this inherited-uncertainty term to a standard entropy score raises AUROC for detecting wrong agent outputs by 2.3% to 11% over single-turn baselines. If correct, this gives a practical information-theoretic signal for deciding when to stop or double-check a multi-step agent.","feed_headline":"Track uncertainty across steps to spot bad LLM agent output","feed_subtitle":"UProp adds uncertainty inherited from earlier decisions to each step's own confidence, lifting wrong-output AUROC up to 11%","key_machinery":"The load-bearing object is the trajectory uncertainty decomposition $H(y_t|x) = H(y_t|y_{1:t-1},x) + \\sum_{i<t} I(y_t; y_i | y_{i+1:t-1},x)$. The estimator UProp is built on Trajectory-Dependent Decision Process (TDP) sampling—at each step, sample $N$ decisions conditioned on the realized prefix, then keep one sampled decision as the prefix for the next step—which converts the exponential mutual-information integral into a linear number of conditional samples. Extrinsic uncertainty is then approximated by dPMI, which reduces to $-\\log$ of a Gaussian-kernel-weighted count of how many sampled previous decisions resemble the realized one; string fuzzy matching over the agent's action gives the distance. Two convergence theorems (for TDP averaging and for the kernel PMI) are what license the approximation, with the second resting on a local smoothness assumption on $p_\\theta(y_t | y_{t-1}, x)$.","core_discovery":"The paper's central claim is that the total uncertainty $H(y_t|x)$ of the decision at step $t$ in a multi-step agent decomposes exactly into $H(y_t|y_{1:t-1},x)$ plus a cumulative sum of conditional mutual informations $I(y_t; y_i | y_{i+1:t-1},x)$, so the \"extrinsic\" uncertainty inherited from every earlier decision is a well-defined information-theoretic quantity. Because direct mutual information requires exploring an exponentially branching decision space, UProp samples Trajectory-Dependent Decision Processes: at each step it draws $N$ candidate decisions, keeps one sampled decision as the realized prefix, and continues; each TDP is one linear trajectory plus $N$ per-step samples. On each TDP, the estimator replaces mutual information with pointwise mutual information and further reduces it to $dPMI(y_t; y_{t-1}^{(k)} | x) = -\\log \\sum_n \\kappa_N(d(y_{t-1}^{(n)}, y_{t-1}^{(k)}))$, a kernel-weighted count of alternative previous decisions similar to the realized one. The paper presents convergence theorems for the TDP average and for the kernel PMI under a local smoothness assumption, and reports that ablating the extrinsic term degrades AUROC more than ablating the intrinsic term.","pith_inferences":["Editorial extension: because dPMI depends only on sampled actions and a string-similarity kernel, it should transfer to agents whose actions are structured function calls; if it fails there, the action-distance choice is the bottleneck rather than the information decomposition.","Editorial extension: the paper's framework measures total uncertainty but does not separate model-epistemic from environment-aleatoric uncertainty; a natural follow-up would be to extend the same mutual-information decomposition to distinguish the two.","Editorial extension: the kernel sharpness is a hyperparameter, so the testable claim is whether the reported AUROC gains survive across a range of kernel sharpness values without tuning on each benchmark."],"forward_implications":["The full UProp score, which sums a per-step entropy with the extrinsic term, improves AUROC for detecting wrong answers on AgentBench-OS and StrategyQA across GPT-4.1-Nano, GPT-3.5-Turbo, Gemma-2-27b-it, DeepSeek-V3, and Qwen2.5-72B-Instruct.","The extrinsic component carries more of the signal than the intrinsic component: removing it from UProp lowers AUROC more than removing the intrinsic component does, so single-turn uncertainty scores alone under-use the trajectory's history.","UProp keeps most of its advantage when the numbers of trajectories and of per-step samples are as low as 2-4, so the estimate remains feasible when environment calls are expensive.","The same uncertainty score can serve as a rejection rule and as a selector of the most reliable answer among multiple generations, improving success rate over unguided decoding."],"supporting_citations":[{"why":"Supplies the entropy chain rule and mutual information decomposition used to split uncertainty into intrinsic and extrinsic parts.","marker":"Cover (1999)"},{"why":"Establishes the exponential cost of direct mutual-information estimation, motivating the trajectory-dependent sampling instead.","marker":"Kraskov et al. (2004)"},{"why":"Defines Monte Carlo predictive entropy and length normalization that UProp uses for the intrinsic uncertainty component.","marker":"Malinin and Gales (2020)"},{"why":"Provides semantic entropy, the principal single-turn uncertainty baseline UProp is compared against.","marker":"Kuhn et al. (2023)"},{"why":"Provides the AgentBench-OS environment used to benchmark multi-step LLM decision-making.","marker":"Liu et al. (2023)"},{"why":"Provides the HotpotQA multi-hop QA dataset for trajectory-level evaluation.","marker":"Yang et al. (2018)"},{"why":"Provides the StrategyQA dataset with implicit reasoning strategies.","marker":"Geva et al. (2021)"},{"why":"SAUP is the prior multi-step uncertainty propagation method UProp contrasts against, and it requires test-domain ground-truth labels.","marker":"Zhao et al. (2024)"},{"why":"Supplies the ReAct reasoning-action-observation format used to generate decision trajectories.","marker":"Yao et al. (2023)"},{"why":"Supplies the fuzzy string matching used as the decision distance inside the dPMI kernel.","marker":"SeatGeek (2020)"}],"fun_headline_variants":["UProp: propagate uncertainty across agent steps to catch wrong decisions","UProp: decompose agent uncertainty into current and inherited parts","Extrinsic uncertainty from past steps keys UProp's multi-step agent doubt","UProp: track how much uncertainty to inherit at each agent step"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the model's next-step distribution changes smoothly as the previous decision varies, so samples drawn from one decision path can stand in for samples from all possible paths; if that mismatch is not covered by the smoothness assumption, the kernel estimate is not actually approximating the defined mutual information.","fun_headline_variants_meta":{"raw":{"variants":["UProp: propagate uncertainty across agent steps to catch wrong decisions","UProp: decompose agent uncertainty into current and inherited parts","Extrinsic uncertainty from past steps keys UProp's multi-step agent doubt","UProp: track how much uncertainty to inherit at each agent step"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000624,"raw_usage":{"total_tokens":2972,"prompt_tokens":1108,"completion_tokens":1864,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":724,"completion_tokens_details":{"reasoning_tokens":1791}},"tokens_in":724,"tokens_out":1864,"duration_ms":13428,"temperature":1.0,"reasoning_tokens":1791,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:09:09.379660+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate a toy two-step decision problem with a tiny action vocabulary, compute the true pointwise mutual information exactly by summing over all pairs of decisions, and compare it with UProp's dPMI at growing $N$ and $Z$; if the gap does not shrink to zero for appropriately shaped kernels with fixed sharpness $\\tau$, the convergence claim fails. A second check: run UProp on two trajectories that reach the same observation through very different preceding actions; if the score moves with the surface similarity of the actions rather than with the information state, the kernel is measuring text distance, not inherited uncertainty.","supporting_citations":[{"cited_title":"thefuzz: Fuzzy string matching in python","cited_arxiv_id":null,"evidence_quote":"Supplies the fuzzy string matching used as the decision distance inside the dPMI kernel."}],"review_version":1}