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

What it claims

GraphACM is a label-free uncertainty score for an LLM agent on a task. You run the task k times, merge the runs into a state graph, and measure how often rollouts pick the same action when they reach the same state. Across 9 model–benchmark pairs, its average AUROC for predicting task success is 0.811. The strongest consistency baseline, Argument Consistency, reaches 0.729, and verbalized confidence reaches 0.769. The averages hide large variation by benchmark: GraphACM is clearly best on ALFWorld, mixed on AppWorld, and weak on WebShop.

How it works

1. Sample rollouts. Sample k independent rollouts from the same initial state. Only observations and actions are recorded; intermediate reasoning is dropped.
2. Abstract each step. Map each step to an abstract state z = φ(e, h), where e is the execution-relevant environment context and h is history not visible in the current observation. Two states are merged when their canonical forms match. φ is benchmark-specific and hand-defined (Appendix B, not in the fetched text). Anyone applying this to a new environment has to write it.
3. Build the graph. Nodes are merged states. Edges are actions labeled with name and arguments. Each rollout is a walk through the graph.
4. Score each node. Node consistency S_v is the average pairwise agreement among the rollouts that act from v. Agreement is exact match: the action name and all arguments must be equal. A node visited by only one rollout gets S_v = 0. If a rollout revisits a node, its last action there is the one used.
5. Score the task. S_G = (1 / (k·T̄)) Σ_v n_v·S_v, where n_v is the number of rollouts visiting v and T̄ is the mean rollout length. S_G lies in [0, 1], and uncertainty is U = 1 − S_G.

The paper proves that, under an i.i.d. assumption, S_v is an unbiased estimator of Σ_a p_v(a)². This equals exp(−H₂), where H₂ is the order-2 Rényi entropy of the agent's action distribution at that state.

Evidence

Setup

• Models: Qwen3.8-27B, Gemma-4-31B-IT and GPT-5.4-mini, run with the verl-agent harness.
• Sampling: k = 10 rollouts at temperature 1.0.
• Step caps: 50 for ALFWorld and AppWorld, 30 for WebShop.
• Labels: a task counts as "successful" if at least 5 of its 10 rollouts succeed.

AUROC (GPT / Qwen / Gemma)

Spearman ρ between consistency and empirical success rate

• ALFWorld: 0.80–0.83
• AppWorld: 0.57–0.74
• WebShop: 0.25–0.40

The relationship is steepest at high success rates. This suggests the score is best at picking out reliably solved tasks.

Localization example. On one ALFWorld task, 60 actions from 10 rollouts collapse into 11 states and 14 edges. Disagreement sits in the exploration phase: S = 0.44 at the start state, then 0.60 and 0.80. After that, all ten rollouts converge and every later node scores S = 1.

How to use it

The page gives no code, repository or package. To reproduce the method you need:

• A resettable environment, so k runs can start from an identical initial state.
• About k = 10 full rollouts per task, which is roughly 10× the inference cost of a single run.
• Your own state canonicalization φ.

The scoring step itself is cheap and simple to implement from Eq. 1–2 above.

Limits

• WebShop is weak. Some tasks with zero successes still show high consistency, meaning the agent is consistently wrong. Success and failure boxplots overlap for all three models there.
• Exact matching penalizes harmless variation. Paraphrased arguments or semantically equivalent actions count as disagreement.
• The prediction target is task-level, not run-level. The label is the majority outcome over the same 10 rollouts used to compute the score. The paper does not evaluate predicting whether a single run will fail.
• Merging quality depends on φ. Results are only as good as the hand-built state abstraction, and its details were not in the fetched text.
• The fetched text was incomplete. It ends partway through the results (Figure 4). Appendices, ablations on k, and any limitations section were not available for this analysis.