From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents
Zhengzhao Ma. Boxi Cao, Yaojie Lu, Hongyu Lin, Xianpei Han, Le Sun
cs.CL, cs.AI
2026-08-17
RUPA turns an agent execution history into a directed dependency graph and propagates uncertainty over it, beating five existing uncertainty quantification methods on failure prediction across three agent benchmarks and six open-source LLMs.
Knowing when to trust a running agent and when to intervene is an open problem. The standard signals (token probabilities, predictive entropy, or a verbalized confidence score) come from the model's own output. The authors' preliminary study is blunt: on the Airline domain of τ-2, sequence probability reaches an AUROC of 0.205 for trajectory-level failure prediction (worse than the 0.5 random baseline) and verbalized confidence 0.485, essentially a coin flip.
The root cause is representation. Agent failures rarely come from a single wrong step; they accumulate across interdependent steps. An early misunderstanding looks harmless until every later decision is built on it. When the authors locate the highest-risk step inside failed trajectories, those steps spread evenly across the whole execution rather than clustering at the end, with an average repetition score of 0.981 and stagnation score of 0.883. Failure signal lives in the structure of the trajectory, which a linear sequence plus local confidence cannot hold.
RUPA (Relational Uncertainty Propagation for Agents) rewrites the execution trajectory as a directed graph and lets uncertainty flow along the edges.
Graph construction is deterministic rule matching. Nodes are execution events (user instructions, reasoning or actions, tool calls, environment observations); edges fall into seven relation types: sequential, latest, repetition, progression, parallel, feedback, and goal alignment. Edge types are decided by embedding distance (bge-m3) plus lexical cues: progression looks for continuation words like next, therefore, verify; feedback looks for traceback, error, timeout. Future information and final labels are never touched.
Propagation runs in three steps:
The load-bearing choice is making relation asymmetry explicit. Repetition and feedback edges show the largest structural variation across failed trajectories and receive the largest propagation weights; uncertainty flowing in from unrelated branches is suppressed. Replacing the graph with a random topology in the ablation . The gains come from real dependency structure, not from having a graph at all.
Three benchmarks (τ-2, Terminal-Bench-2, GAIA), six open-source models from 26B to 230B. AUROC for failure prediction:
| Model | Best baseline | RUPA |
| Qwen3.5-27B | 0.608 (Tracer) | 0.656 |
| Qwen3.6-35B | 0.629 (Tracer) | 0.645 |
| Gemma4-26B | 0.761 (SAUP) | 0.780 |
| Gemma4-31B | 0.842 (SAUP) | 0.861 |
| MiniMax-M2.7 | 0.694 (Tracer) | 0.718 |
| GPT-OSS-120B | 0.567 (UProp) | 0.577 |
Three practical settings:
Agent deployment is bottlenecked on reliability, and a trustworthy risk score is often more urgent than another five points of success rate: routing high-risk runs to humans, auto-releasing low-risk ones, and stopping wasted budget mid-run all depend on it. RUPA requires no model changes and no training; it is an inference-side add-on, and its rule-based graph construction means integration cost is mostly structuring execution logs. For agent platform builders, trajectory structuring plus relation-weighted propagation is a feature-engineering template that ports even without adopting the whole framework.
Within limits: the gains are 2–4 AUROC points, an incremental improvement. The conceptual move from sequences to relations matters more than the absolute numbers. And 0.577 on GPT-OSS-120B is far from production-grade risk judgment.
Both self-reported and observed: