Graph method improves confidence estimates for reasoning and acting agents
GRUET: Quantifying Uncertainty of Agentic Reasoning-and-Acting Processes
Artificial Intelligence
Summary
Agents that use large language models to think and act in steps often show uncertain behavior, making their actions hard to trust. The authors found that this uncertainty often comes from unclear reasoning at each step, which builds up. They created a new method called GRUET that uses graphs to measure how complex the reasoning options are at each step and combines this to estimate overall confidence in the agent’s actions. Tests across many language models and tasks showed that GRUET can effectively predict when an agent’s behavior might be unreliable.
What this means in practice
- •For ai system developers: Estimate confidence levels in multi-step reasoning and acting performed by AI agents to improve reliability in dynamic tasks.
- •For software testing teams: Identify uncertain or unreliable reasoning sequences in AI-driven workflows to prioritize testing and debugging efforts.
Authors
Shuang Liang, Xin-Yu Hu, Shao-Qun Zhang
Abstract
Agents have attracted considerably increasing attention due to the power of executing both Reasoning and Acting (ReAct) in open and dynamic environments. The ReAct process typically exhibits a multi-turn trajectory in which one drives Large Language Models (LLMs) to generate both reasoning chains and task-specific actions in an interleaved manner. However, agents often suffer from significant uncertainty, where identical tasks yield divergent trajectories; trajectories with higher uncertainty often produce incomprehensible behaviors, severely undermining agent credibility. This work conjectures that such trajectory-level uncertainty frequently stems from cumulative turn-level reasoning uncertainty induced by LLMs; the latter often exhibits a collection of branches of divergent reasoning chains and their resulting actions. Built upon this, we present the Graph-based Reasoning UncErtainty in Trajectories (GRUET) method for the uncertainty quantification of ReAct, comprising turn-level reasoning uncertainty quantification and trajectory-level uncertainty aggregation; the former precisely quantifies reasoning uncertainty via modeling the reasoning space spanned by potential reasoning branches as a graph and then approximating the reasoning space complexity with graph complexity, while the latter employs simple aggregation strategies for quantifying the overall trajectory credibility. Empirical evaluations across nine LLMs and five benchmarks validate the effectiveness of our proposed GRUET in terms of selective generation performance, measured by AUROC, AUPRC, and AUARC.