GraphACM: Graph-based Action Consistency Measurement for Uncertainty Quantification in LLM Agents

Yaxin Ma; Wenbo Zhang; Satya Krishna Pothapragada; Alina Zare

cs.AIOct 15, 2026

GraphACM: Graph-based Action Consistency Measurement for Uncertainty Quantification in LLM Agents

Authors: Yaxin Ma, Wenbo Zhang, Satya Krishna Pothapragada, Alina Zare

Organizations: University of Florida, Gainesville, FL, USA · University of California, Irvine, CA, USA

Abstract

Behavioral consistency across repeated executions provides an informative signal for assessing the reliability of large language model (LLM) agents. However, existing approaches typically summarize consistency with a single task-level score, without identifying where behavioral differences occur or whether actions are compared under equivalent decision contexts. We propose a graph-based framework for fine-grained behavioral consistency measurement and uncertainty quantification. Given multiple rollouts of the same task, we merge equivalent states into a directed, action-labeled graph, enabling action comparisons at shared decision states. We introduce node-level and global measures of action consistency, using the global consistency score as a proxy for uncertainty to predict task success or failure. Experiments across three LLMs on ALFWorld, AppWorld, and WebShop demonstrate that our measure is positively associated with task success and achieves an average AUROC of 0.811 for task-success prediction, outperforming the strongest behavioral-consistency baseline (0.729) and verbalized confidence (0.769). These results highlight the effectiveness of state-conditioned behavioral consistency and pinpoint where agent actions agree.

Figures & tables

Figure 1: Illustration of sequence-based and graph-based behavioral consistency measurement. (a) Position-wise comparison may align actions originating from different decision states, while equivalent states can occur at different timesteps. (b) GraphACM merges equivalent states across rollouts and compares actions at shared decision states, identifying consistent decisions and localized behavioral disagreement.

Figure 2: Merged state–action graph for an ALFWorld task (“put some saltshaker on cabinet”) using Qwen3.8-27B with $k=10$ successful rollouts. Nodes represent states, and directed edges represent actions, with $\times$ indicating the number of rollouts taking each action.

Figure 3: Global action consistency versus empirical task success rate. Lines show mean consistency across tasks at each success-rate level; shaded bands indicate

\pm 1

standard deviation.

Methods	ALFWorld			AppWorld			WebShop			Average
	GPT	Qwen	Gemma	GPT	Qwen	Gemma	GPT	Qwen	Gemma
UAS	0.655	0.741	0.866	0.476	0.504	0.531	0.702	0.592	0.618	0.632
DSE	0.655	0.741	0.866	0.476	0.504	0.531	0.703	0.596	0.613	0.632
TSS	0.523	0.777	0.670	0.847	0.849	0.754	0.519	0.553	0.571	0.674
AC	0.730	0.728	0.777	0.819	0.888	0.704	0.683	0.611	0.618	0.729
ASC	0.509	0.900	0.773	0.878	0.835	0.722	0.500	0.500	0.500	0.680

Table 1: AUROC comparison of our method and baselines for task-success prediction across ALFWorld, AppWorld, and WebShop using GPT-5.4-mini, Qwen3.8-27B, and Gemma-4-31B. Best results are shown in bold and second-best results are underlined .

Figure 4: Consistency scores of successful and failed tasks across benchmarks and LLMs. Boxes show the median and interquartile range; whiskers extend to the furthest task within

1.5

IQR of the box.

Methods	ALFWorld			AppWorld			WebShop			Average
	GPT	Qwen	Gemma	GPT	Qwen	Gemma	GPT	Qwen	Gemma
Name only	0.807	0.948	0.883	0.860	0.894	0.756	0.701	0.627	0.672	0.794
Name + arguments	0.907	0.962	0.922	0.857	0.883	0.754	0.718	0.636	0.664	0.811

Table 2: AUROC of our method under two action-equivalence criteria: matching action types only (name only) or matching both action types and arguments (name + arguments).

Figure 5: Effect of the number of sampled rollouts

k

on task-success prediction AUROC across three benchmarks, averaged over three LLMs.

Figure 6: Ablation of episode-length normalization and node weighting. We compare the full method against variants without length normalization or with uniform node weights (

w_{v}=1

instead of

w_{v}=n_{v}

Behavioral Consistency of LLM Agents

See all 23 papers

When Agents Disagree With Themselves: Behavioral Consistency as an Uncertainty Signal for LLM Agents
Feb 12, 2026Aman MehtaAI Agent Reliability Selective Prediction
Snowflake AI Research
Measuring Cross-Task Behavioral Consistency in Language Model Agents
Jul 31, 2026Amritesh Banerjee, Pranil RaichuraAI Agent Reliability Software Engineering Agents
University of Massachusetts Amherst · Mantis AI Research (MIT CSAIL)
How Consistent Are LLM Agents? Measuring Behavioral Reproducibility in Multi-Step Tool-Calling Pipelines
Apr 23, 2026Abel YagubyanAI Agent Reliability LLM Agent Evaluation
Independent Researcher

Feb 12, 2026J/K move · Enter open · S save

When Agents Disagree With Themselves: Behavioral Consistency as an Uncertainty Signal for LLM Agents

Aman Mehta

Snowflake AI Research

AI Agent Reliability Selective Prediction LLM Agent Evaluation Reasoning Consistency in Language Models Language Model Calibration LLM Reliability+3

Open paper AskPDF arXiv

Running the same LLM agent on identical inputs yields 2.3-4.2 distinct action sequences per 10 runs; this behavioral variance constitutes a training-free, black-box uncertainty signal that instantiates selective classification and distribution-free calibration for agentic systems. Across 8,000 runs of four models on 200 HotpotQA questions, consistent tasks (at most 2 unique paths) achieve 82-87% accuracy while inconsistent tasks (4 or more paths) achieve 41-65%, a gap that survives controls for task difficulty. Divergence concentrates at step 2 (50.5% of Llama tasks), and consistency metrics detect failures with AUROC 0.62-0.78. Exploiting this signal, selective prediction (answering only when k=3 runs agree) achieves 87-88% accuracy at 54-62% coverage, a 6-14pp gain over single-run baselines, and matches a split-conformal baseline without a held-out calibration set. A cross-benchmark validation on SWE-bench (50 tasks, 1,000 runs) preserves the consistency hierarchy while revealing an ~8x spread in mean trajectory length across models, and bootstrap analysis shows single-run evaluations misrank models 29.3% of the time.

Abstract

Behavioral Consistency of LLM Agents

Explore similar work

When Agents Disagree With Themselves: Behavioral Consistency as an Uncertainty Signal for LLM Agents

Measuring Cross-Task Behavioral Consistency in Language Model Agents

How Consistent Are LLM Agents? Measuring Behavioral Reproducibility in Multi-Step Tool-Calling Pipelines