Execution-Guided Verification for Reliable Tool-Using Large Language Model Agents

Large language model (LLM) agents increasingly operate on real systems through tool calls, yet their behavior is stochastic: the same request may be resolved correctly in one run and incorrectly in the next, and erroneous write operations are costly to undo. This paper presents execution-guided verification (EGV), a training-free and model-agnostic procedure that decides which agent behavior to commit by executing candidate trajectories instead of judging their text. EGV replays the tool calls of k independently sampled trajectories against isolated copies of the backend state, groups candidates that reach an identical final world state, and commits a representative of the best-supported state, while failed tool calls serve as a secondary signal for tie-breaking and representative selection. The support share of the committed state acts as a verification confidence for selective execution with escalation to human operators. Experiments on 1,980 real trajectories of GPT-4o and Claude-3.5-Sonnet in the retail and airline domains of τ-bench, replayed in a sandbox that reproduces 99.96% of the recorded tool observations, show that EGV improves task success over single-run execution in every setting, e.g., from 61.0% to 68.7% for Claude-3.5-Sonnet in retail, with a pooled gain of 6.1 points (95% CI [3.8, 8.3]), and that it consistently outperforms voting over emitted action sequences. Execution agreement predicts trajectory success with an AUROC of 79.4–82.8, and committing only unanimously supported states yields 81.0–100% success on 16–40% of the requests. These results establish world-state equivalence as an effective and inexpensive verification signal for stateful tool-using agents.