ToolGraph as a Q-Function for Test-Time Scaling of Tool-Use Agents

Tool-use agents must compose long chains of interdependent calls, and the dependency structure of a particular deployed catalog---which outputs satisfy which later inputs, and in what order---is not something a general-purpose language model reliably infers from tool descriptions alone. We treat that structure as an external representation to be compiled once and reused. ToolGraph is a directed, weighted dependency graph over a deployed tool catalog: parameter matching and interventional probes independently propose edges, a probe executes a candidate chain with and without its proposed predecessor, and the resulting evidence is combined into an edge confidence. Prior work couples such a graph to a language model by retrieving relevant tools, searching it for tool paths, or scoring the call that immediately follows. We ask instead whether the same structure can supply a \emph{multi-step} value, by composing graph paths into a goal-conditioned action value (Q(s,a,g)). We study three estimators---analytic dynamic programming over entity sets, an inductive GraphSAGE estimator distilled from it, and an LLM scorer conditioned on graph evidence---together with a verbalizer that returns action--goal feedback to the original agent, which retains final action selection. Across two tool-use benchmarks and three backbones we compare graph-derived value ranking against graph-derived retrieval ranking over the identical graph, and against direct and reflective agents. Composition pays off only when the estimator also reads the concrete state: the LLM estimator improves on personalized-PageRank ranking of the same edges in every benchmark--backbone setting, by (7.4) points on average, while the two purely structural estimators fall below it, because a value defined over tool types cannot separate a correct tool called with a wrong argument. Graph construction is a one-time cost reused across all later requests; we report it separately rather than assume it amortized away --- at our evaluation scale it is comparable to request-time cost --- and sweep four knobs controlling how much graph evidence to expose against both success and tokens.