Behavioral consistency across repeated executions offers a valuable signal for assessing the reliability of large language model (LLM) agents. Existing methods usually compress consistency into a single task‑level score, which neither reveals where behavioral differences arise nor guarantees that actions are compared under equivalent decision contexts. To address this, we introduce a graph‑based framework for fine‑grained consistency measurement.
Given multiple rollouts of the same task, we merge equivalent states into a directed, action‑labeled graph, enabling direct action comparison at shared decision points. On this graph we define node‑level consistency metrics and a global consistency score. The global score serves as a proxy for uncertainty and can be used to predict task success or failure.
We evaluate the approach on three benchmarks—ALFWorld, AppWorld, and WebShop—using three prominent LLMs (e.g., GPT‑4, Claude‑2, Llama‑2). Experiments show that the global consistency score correlates positively with task success and achieves an average AUROC of 0.811 for success prediction, outperforming the strongest behavioral‑consistency baseline (0.729) and verbalized confidence (0.769). These results demonstrate that state‑conditioned behavioral consistency effectively captures where agent actions agree and provides a reliable uncertainty estimate.
Review: GraphACM maps multiple executions onto a unified graph, enabling granular action‑level consistency assessment and offering a robust uncertainty metric, which is crucial for improving the interpretability and safety of LLM agents.