Feasible is Not Enough: Cost-Aware Optimal Tool-Chain Planning on Multi-Solution Tool Graphs

Tool graphs (TG) model dependencies among tools and resources, enabling more structured organization and management of large toolsets. However, existing methods and benchmarks often formulate tool learning (TL) as a singlesolution setting, overlooking the fact that many tasks admit multiple valid tool combinations and therefore require optimal solution selection. Moreover, exploring large-scale TG is computationally expensive, especially under constrained context budgets. To address these challenges, we construct MultiSoTLBench, Multi-Solution TL Benchmark in which each task admits multiple valid solutions. To solve this problem efficiently on large TG, we further propose TOPT, an efficient framework for learning optimal TL policies. Specifically, to improve search efficiency in large action spaces, TOPT adopts a progressive graph expansion strategy: we train a reinforcement learning (RL) agent to acquire transferable expansion skills and construct, on demand, a compact solvable subgraph that preserves only taskrelevant chains. This reduces the size of the candidate space and the context usage from the outset. To enable optimal selection, we further propose a progressive graph reasoning framework. It performs cost-aware planning over the expanded subgraph to generate an optimal toolchain that balances path length and tool cost. Comprehensive experiments demonstrate that TOPT generalizes effectively, improving task success and solution optimality by 46.21% and 66.34%, respectively.