From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents

• URL: http://arxiv.org/abs/2608.16002v1
• Date: Mon, 17 Aug 2026 01:40:14 GMT
• Title: From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents
• Abstract summary: We propose a trajectory-level UQ framework for large language model (LLM) agents.<n>RuPA represents an execution history as a directed trajectory graph in which reasoning states, tool interactions, and environment feedback are nodes connected by temporal and semantic dependency edges.<n>We evaluate RUPA on representative agent benchmarks, including $$-2, Terminal-Bench-2, and GAIA, using 6 open-source LLMs spanning multiple model families.
• Score: 75.44420701722915
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reliable uncertainty quantification (UQ) is essential for deploying large language model (LLM) agents in complex interactive environments. Existing UQ methods largely rely on local signals, such as token probabilities, predictive entropy, or per-step confidence, and therefore overlook the long-range dependencies through which errors accumulate across an execution trajectory. As a result, they may fail to identify agent failures whose causes originate several reasoning or interaction steps before the final answer. We propose RUPA (Relational Uncertainty Propagation for Agents), a trajectory-level UQ framework for LLM agents. RUPA represents an execution history as a directed trajectory graph in which reasoning states, tool interactions, and environment feedback are nodes connected by temporal and semantic dependency edges. It then propagates uncertainty over this graph to capture how execution risk accumulates and transfers across interaction steps. The propagated signal is combined with trajectory-level behavioral features and goal-alignment information to produce a confidence estimate for the full agent trajectory. We evaluate RUPA on representative agent benchmarks, including $τ$-2, Terminal-Bench-2, and GAIA, using 6 open-source LLMs spanning multiple model families. Experimental results show that RUPA consistently outperforms existing UQ methods by providing more accurate uncertainty estimates, enabling earlier failure detection, and improving uncertainty-guided agent execution across diverse agent tasks. These results demonstrate that explicitly modeling relational dependency is crucial to reliable UQ for long-horizon LLM agents, providing a practical foundation for trustworthy agent execution.

Related papers

• PropUQ-MAS: Propagation-Aware Uncertainty Quantification for LLM Multi-Agent Systems [8.348628811300268]
  PropUQ-MAS is an error propagation-aware UQ framework for multi-agent systems.<n>It estimates each step's reliability by combining local uncertainty with uncertainty inherited from upstream messages.<n>PropUQ-MAS consistently improves UQ in MAS, with average relative gains of +6.10% in AUROC and+47.58% in PRR.
  arXiv  Detail & Related papers  (2026-08-22T23:07:39Z)
• Beyond LLM-Based Reasoning: Lightweight GNNs for Agent Failure Attribution [47.70578021328887]
  Large language model (LLM)-based multi-agent systems often exhibit complex failure modes.<n>We introduce AFANet, a lightweight graph-based framework that models interaction trajectories through step-level semantic signals and agent-level relationships.<n>Our results suggest that effective agent failure attribution does not require heavy reasoning and a lightweight, structured approach can achieve strong performance.
  arXiv  Detail & Related papers  (2026-08-19T06:16:09Z)
• STAPO: Selective Trajectory-Aware Policy Optimization for LLM Agent Training [25.087853601817688]
  Reinforcement Learning (RL) is the dominant paradigm for training Large Language Model (LLM) agents on long-horizon tasks.<n>We propose normalized entropy, which measures confidence deviations relative to an agent's average behavior under a given state.<n>We introduce Selective Trajectory-Aware Policy Optimization (STAPO), a hierarchical group-based RL framework.
  arXiv  Detail & Related papers  (2026-07-06T11:50:06Z)
• Trust-Aware Multi-Agent Traceability: Confidence-Calibrated Knowledge Graphs for Consistent Software Artifact Management [0.7329200485567826]
  In software engineering, multi-agent AI systems are increasingly used to automate requirements analysis, architecture design, test generation, and traceability linking.<n>We propose a trust-aware coordination framework where a shared knowledge graph serves as both centralized semantic memory and a coordination surface.<n>We evaluate on an automotive software engineering case study measuring link prediction calibration, protocol effectiveness, threshold sensitivity, and the impact of traceability seeding.
  arXiv  Detail & Related papers  (2026-06-15T18:41:50Z)
• From Knowing to Acting: Benchmarking Self-Awareness Capability of LLM Agents [69.07911499189129]
  We introduce KAPRO, a framework that evaluates cognitive-behavioral alignment by decoupling an agent's metacognitive judgment (Knowing) from its spontaneous execution (Acting)<n>Experiments show that self-awareness capability is strongly correlated with task success but degrades sharply in internal-capability settings.<n> proprietary and reasoning-oriented models demonstrate more reliable cognitive gating.
  arXiv  Detail & Related papers  (2026-06-09T17:17:08Z)
• FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search [11.638321375070047]
  We propose FALAT, a diagnostic framework for failure attribution in LLM agent trajectories.<n>We evaluate FALAT on the Who&When benchmark, which includes both algorithm-generated and hand-crafted multi-agent failure trajectories.
  arXiv  Detail & Related papers  (2026-05-30T15:11:35Z)
• Agent-ToM: Learning to Monitor Autonomous LLM Agents via Theory-of-Mind Reasoning [11.914433611519359]
  Monitoring autonomous large language model (LLM) agents for covert malicious behavior is challenging due to delayed, context-dependent, and long-horizon attack patterns.<n>We propose textbfAgent-ToM, a learning-to-monitor framework grounded in Theory-of-Mind (ToM) reasoning for security analysis of autonomous agents.
  arXiv  Detail & Related papers  (2026-05-22T20:57:20Z)
• VerifyMAS: Hypothesis Verification for Failure Attribution in LLM Multi-Agent Systems [79.51005192758262]
  Large language model-driven multi-agent systems excel at complex tasks.<n>However, unreliable agents remain a key bottleneck to system-level reliability.<n>We propose a hypothesis verification framework for agent failure attribution.
  arXiv  Detail & Related papers  (2026-05-17T14:09:35Z)
• AgentV-RL: Scaling Reward Modeling with Agentic Verifier [63.55502685076245]
  Verifiers have been demonstrated to enhance LLM reasoning via test-time scaling (TTS)<n>We propose Agentic Verifier, a framework that transforms reward modeling into a multi-turn, tool-augmented deliberative process.<n>We show that Agentic Verifier yields consistent performance gains under both parallel and sequential TTS.
  arXiv  Detail & Related papers  (2026-04-17T12:27:36Z)
• AgentTrace: Causal Graph Tracing for Root Cause Analysis in Deployed Multi-Agent Systems [0.0]
  We present AgentTrace, a lightweight causal tracing framework for post-hoc failure diagnosis in deployed multi-agent AI systems.<n>AgentTrace reconstructs causal graphs from execution logs, traces backward from error manifestations, and ranks candidate root causes using interpretable structural and positional signals.<n>Our results suggest that causal tracing provides a practical foundation for improving the reliability and trustworthiness of agentic systems in the wild.
  arXiv  Detail & Related papers  (2026-03-16T00:46:44Z)
• DLLM Agent: See Farther, Run Faster [94.74432470237817]
  Diffusion large language models (DLLMs) have emerged as an alternative to autoregressive (AR) decoding with appealing efficiency and modeling properties.<n>We study this in a controlled setting by instantiatingDLLM and AR backbones within the same agent workflow.<n>We find thatDLLM Agents are on average over 30% faster end to end than AR agents, with some cases exceeding 8x speedup.
  arXiv  Detail & Related papers  (2026-02-07T09:01:18Z)
• Towards Reducible Uncertainty Modeling for Reliable Large Language Model Agents [72.26774492844167]
  Uncertainty quantification (UQ) for large language models (LLMs) is a key building block for safety guardrails of daily LLM applications.<n>This paper presents the first general formulation of agent UQ that subsumes broad classes of existing UQ setups.<n>We propose a novel perspective, a conditional uncertainty reduction process, that explicitly models reducible uncertainty over an agent's trajectory.
  arXiv  Detail & Related papers  (2026-02-04T21:47:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.