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 × 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 ±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 ( wv=1 instead of wv=nv ).
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.
Agent evaluation relies almost entirely on outcome metrics such as success rate, which capture whether an agent succeeds but not how consistently it behaves. We argue that behavioral consistency across tasks is a distinct and measurable property, and we introduce the Behavioral Consistency Metric (BCM) to quantify it. BCM trains a model to predict task success from behavioral features of agent execution traces, derives a per-trajectory feature-attribution vector, and measures the mean pairwise similarity of these vectors within an agent system. Across roughly 9,000 trajectories from six language model agents on software engineering tasks, our central finding is that cross-task and within-task consistency are distinct axes that can diverge: some systems are locally reproducible, behaving similarly on repeated attempts at one task, yet globally fragmented, with no stable strategy across different tasks, while others are consistent at both scales. Prior work measures only same-task reproducibility and so cannot observe this separation. We further find that consistency is not reducible to success rate, since systems with comparable success can differ sharply in consistency, and that the frontier-versus-open-source consistency gap persists under a within-task control that holds task difficulty constant. We position BCM as a process-level reliability signal that complements outcome metrics, and we are explicit about the conditions under which it is meaningful.
Amritesh Banerjee, Pranil Raichura
University of Massachusetts Amherst · Mantis AI Research (MIT CSAIL)
Large language model (LLM) agents with tool-calling capabilities are increasingly deployed in production systems, yet a fundamental reliability question remains under-explored: does the same agent behave the same way twice? We present a systematic empirical study of behavioral consistency in multi-step tool-calling agents, measuring whether agents select the same tools, in the same order, with the same arguments, across repeated identical invocations. Unlike prior work on consistency in ReAct-style agents(search-only, free-text actions), we study the richer setting of structured tool-calling interfaces with typed parameters and consequential side effects.