RUPA models LLM-agent trajectories as relational graphs and propagates uncertainty across their dependencies, yielding more accurate and earlier failure detection and better uncertainty-guided execution than existing methods across diverse agent benchmarks.</p>\n","updatedAt":"2026-08-19T02:05:13.593Z","author":{"_id":"5fc052241160c47d1d438556","avatarUrl":"/avatars/f508707fc92f1b42f7897b12b727754c.svg","fullname":"Boxi Cao","name":"Bowieee","type":"user","isPro":false,"isHf":false,"isHfAdmin":false,"isMod":false,"followerCount":5,"isUserFollowing":false}},"numEdits":0,"identifiedLanguage":{"language":"en","probability":0.899438738822937},"editors":["Bowieee"],"editorAvatarUrls":["/avatars/f508707fc92f1b42f7897b12b727754c.svg"],"reactions":[],"isReport":false}}],"primaryEmailConfirmed":false,"paper":{"id":"2608.16002","authors":[{"_id":"6a850c56536bdd3bdd48f702","name":"Zhengzhao Ma. Boxi Cao","hidden":false},{"_id":"6a850c56536bdd3bdd48f703","name":"Yaojie Lu","hidden":false},{"_id":"6a850c56536bdd3bdd48f704","name":"Hongyu Lin","hidden":false},{"_id":"6a850c56536bdd3bdd48f705","name":"Xianpei Han","hidden":false},{"_id":"6a850c56536bdd3bdd48f706","name":"Le Sun","hidden":false}],"publishedAt":"2026-08-17T00:00:00.000Z","submittedOnDailyAt":"2026-08-19T00:00:00.000Z","title":"From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents","submittedOnDailyBy":{"_id":"5fc052241160c47d1d438556","avatarUrl":"/avatars/f508707fc92f1b42f7897b12b727754c.svg","isPro":false,"fullname":"Boxi Cao","user":"Bowieee","type":"user","name":"Bowieee"},"summary":"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.","upvotes":6,"discussionId":"6a850c57536bdd3bdd48f707","githubRepo":"https://github.com/icip-cas/RUPA","githubRepoAddedBy":"user","ai_summary":"RUPA models agent execution as a dependency graph to propagate uncertainty across long trajectories, improving failure detection and confidence estimation for LLM agents.","ai_keywords":["uncertainty quantification","LLM agents","trajectory-level UQ","directed trajectory graph","relational dependency","uncertainty propagation","long-horizon agents"],"ai_summary_model":"thinkingmachines/Inkling-Small","githubStars":1,"organization":{"_id":"66b2d691e2d6c59a4067505c","name":"ICIP","fullname":"ICIP","avatar":"https://cdn-avatars.huggingface.co/v1/production/uploads/6216496a9b34d2fb49144599/8xuyYJM4haNE67IzonZN9.png"}},"canReadDatabase":false,"canManagePapers":false,"canSubmit":false,"hasHfLevelAccess":false,"upvoted":false,"upvoters":[{"_id":"6772aa5d35722632fcf1e3d8","avatarUrl":"/avatars/a140021f3e2d670d1b4a44b3e34c269a.svg","isPro":false,"fullname":"Winhana","user":"MaZCH","type":"user"},{"_id":"65767d254fffc3f08b9d054e","avatarUrl":"/avatars/73570e34e11213654e1cff1017ce88d1.svg","isPro":false,"fullname":"Ma Zhengzhao","user":"WinHana","type":"user"},{"_id":"5fc052241160c47d1d438556","avatarUrl":"/avatars/f508707fc92f1b42f7897b12b727754c.svg","isPro":false,"fullname":"Boxi Cao","user":"Bowieee","type":"user"},{"_id":"63ac5701c21e60a3e9b58aa7","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/63ac5701c21e60a3e9b58aa7/g6EX7diOpuA94R2ab-rZC.png","isPro":true,"fullname":"Dipankar Sarkar","user":"dipankarsarkar","type":"user"},{"_id":"6463554dd2044cd1d7c6e0bf","avatarUrl":"/avatars/d7653623117268c545a7063fec69664b.svg","isPro":false,"fullname":"Bingzheng Wei","user":"Bingzheng","type":"user"},{"_id":"65d9be67be18bfea69c63830","avatarUrl":"/avatars/fe68775d214b76f8812db0d066d5be63.svg","isPro":false,"fullname":"Jialong Sun","user":"Pillow-1","type":"user"}],"acceptLanguages":["en"],"dailyPaperRank":0,"organization":{"_id":"66b2d691e2d6c59a4067505c","name":"ICIP","fullname":"ICIP","avatar":"https://cdn-avatars.huggingface.co/v1/production/uploads/6216496a9b34d2fb49144599/8xuyYJM4haNE67IzonZN9.png"},"markdownContentUrl":"https://huggingface.co/buckets/huggingchat/papers-content/resolve/2608/2608.16002.md","query":{}}">
From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents
Abstract
RUPA models agent execution as a dependency graph to propagate uncertainty across long trajectories, improving failure detection and confidence estimation for LLM agents.
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.
Community
RUPA models LLM-agent trajectories as relational graphs and propagates uncertainty across their dependencies, yielding more accurate and earlier failure detection and better uncertainty-guided execution than existing methods across diverse agent benchmarks.
Upload images, audio, and videos by dragging in the text input, pasting, or clicking here.
Tap or paste here to upload images
Cite arxiv.org/abs/2608.16002 in a model README.md to link it from this page.
Cite arxiv.org/abs/2608.16002 in a dataset README.md to link it from this page.
Cite arxiv.org/abs/2608.16002 in a Space README.md to link it from this page.
Discussion (0)
Sign in to join the discussion. Free account, 30 seconds — email code or GitHub.
Sign in →No comments yet. Sign in and be the first to say something.