The paper introduces PROVE, a framework that trains large language models to perform multi-step tool calls in stateful environments. It addresses three problems: building realistic execution environments is hard, synthetic training queries often fail because they reference non-existent entities, and standard recall-based rewards encourage unnecessary tool calls.
PROVE provides 20 live servers with 343 tools, a pipeline that generates training queries grounded in actual server state, and a reward function with an adaptive efficiency penalty. Training four different models with this approach improved their performance on three multi-step tool use benchmarks by up to 10 points.