Large Language Model (LLM) agents with tool use can behave inconsistently across independent runs from identical states. They may call different tools, produce contradictory outputs, or follow divergent strategies. This variability compounds over time and undermines deployment reliability. Existing evaluation metrics primarily measure task correctness via completion-based scores and do not capture consistency in agent behavior across executions. Separately, agent behavior is analyzed either at the token level using probability distributions or at the single-response level using semantic clustering, but neither captures how inconsistency propagates across future turns of a trajectory. We introduce Recursive Semantic Divergence (RSD), a trajectory-level consistency metric adapted from bisimulation metrics in reinforcement learning. RSD measures the expected cumulative semantic disagreement between two independent rollouts of the same agent from the same state, using natural language inference to detect logical inconsistency. It is defined recursively over future states and approximated by a neural network trained on independent rollouts. The learned metric estimates future divergence from the current state, providing a consistency score at each turn without requiring the full trajectory to complete. When used as a reward signal for fine-tuning, RSD reduces AUC coefficient of variation (CV) by up to 30.9% on tau2-bench and 50.5% on ToolSandbox. Across Qwen-2.5 and Qwen-3.5 models, RSD reduces AUC CV in seven out of eight model-benchmark settings, while improving the final task progress in all eight settings.
Figures & tables
Figure 1: Diagram illustrating Recursive Semantic Divergence (RSD) in LLM agents. The first three panels display trajectory spreads for perfectly consistent, mostly consistent, and highly inconsistent agents over time. The final panel maps an agent’s expanding and converging semantic action space alongside its corresponding RSD score, demonstrating how the metric tracks the variance of semantic divergence at each turn.
Model
AUC
AUC CV
Progress
Progress CV
pass @ 1
pass ^ 3
ToolSandbox Qwen-2.5-3B
Base Qwen (baseline)
0.271
0.90
0.293
0.86
14.1%
20.0%
Token Entropy
0.302
0.50 ↓ 43.8%
0.317
0.53 ↓ 37.8%
15.6%
20.0%
Semantic Entropy
0.326
0.83 ↓ 7.0%
0.354
0.82 ↓ 4.0%
17.2%
20.0%
SFT
0.311
0.82 ↓ 8.9%
0.327
0.81 ↓ 5.6%
17.2%
20.0%
RSD
0.340
0.44 ↓ 50.5%
0.362
0.43 ↓ 49.3%
18.8%
21.4%
Table 1: Performance and consistency, measured by the coefficient of variation (CV), across different fine-tuning strategies. The upwards and downwards arrows ↑↓ show relative change from the baseline. The blue downwards arrow ↓ indicates reduction in variation, while the red upwards arrow ↑ indicates increase in variation.
Model
AUC
AUC CV
Progress
Prog CV
pass @ 1
pass ^ 3
RSD ( λ =1.0)
0.555
0.28
0.562
0.27
25.0%
28.6%
Hybrid ( λ =0.8)
0.533
0.36 ↑ 29.3%
0.541
0.33 ↑ 21.1%
26.6%
28.6%
Hybrid ( λ =0.5)
0.532
0.37 ↑ 33.6%
0.539
0.35 ↑ 28.2%
29.7%
21.4%
Hybrid ( λ =0.2)
0.518
0.42 ↑ 51.0%
0.536
0.35 ↑ 27.0%
23.4%
21.4%
Table 2: Hybrid ablation on ToolSandbox Qwen-2.5-7B. The RSD weight λ controls the balance between RSD consistency reward ( λ ) and progress delta reward ( 1−λ ). ↑↓ shows relative change from pure RSD ( λ=1.0 ). The red upwards arrow ↑ indicates increased in variation.
ToolSandbox 7B
τ2 -bench 7B
Model
RSD
Reduction
RSD
Reduction
Base Qwen
0.672
—
0.873
—
Token Entropy
0.400
− 40.5%
0.877
+0.5%
Semantic Entropy
0.440
− 34.4%
0.860
− 1.5%
SFT
0.664
− 1.1%
0.800
− 8.3%
Hybrid ( λ =0.8)
0.387
− 42.5%
0.867
− 0.7%
Table 3: Direct RSD evaluation (lower = more consistent) across 8 independent trials per sample, measured via gpt-4.1.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Model
AUC
AUC CV
Progress
Progress CV
τ2 -bench Qwen-3.5-4B
Base Qwen (baseline)
0.627
0.444
0.705
0.454
RSD
0.686
0.355 ↓ 20.0%
0.768
0.359 ↓ 20.9%
τ2 -bench Qwen-3.5-9B
Base Qwen (baseline)
0.607
0.480
0.686
0.483
RSD
0.650
0.428 ↓ 10.8%
0.720
0.427 ↓ 11.6%
Appendix
Table 4: Performance and consistency, measured by the coefficient of variation (CV), for Qwen-3.5 models across both benchmarks. The blue downwards arrow ↓ indicates a reduction in variation, while the red upwards arrow ↑ indicates increased variation relative to the baseline.
Category
N
Entailment
Neutral
Contradiction
Same tool + same args
1,602
97.6%
0.1%
2.3%
Same tool + different args
343
6.1%
0.0%
93.9%
Different tools
695
0.0%
0.0%
100.0%
Appendix
Table 5: GPT-4.1 NLI classification distributions for tool-calling action pairs.
Model Pair
Agreement (%)
GPT-4.1 vs Kimi-K2.5
95.0
GPT-4.1 vs GPT-5.1
98.0
GPT-4.1 vs GPT-4o
97.5
GPT-4.1 vs GPT-4o-mini
97.0
GPT-4.1 vs DeBERTa-v3-large
41.6
Appendix
Table 6: Cross-model NLI agreement on sampled ToolSandbox action pairs.
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.
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.
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.