@inproceedings{liu-etal-2026-feasible,
    title = "Feasible is Not Enough: Cost-Aware Optimal Tool-Chain Planning on Multi-Solution Tool Graphs",
    author = "Liu, Liangliang  and
      Li, Yanming  and
      Liu, Yigang  and
      Han, Jialong  and
      Shen, Rujia  and
      Guan, Yi  and
      Lin, Yi  and
      Jiang, Jingchi",
    editor = "Liakata, Maria  and
      Moreira, Viviane P.  and
      Zhang, Jiajun  and
      Jurgens, David",
    booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {ACL} 2026",
    month = jul,
    year = "2026",
    address = "San Diego, California, United States",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-acl/2026.findings-acl.860/",
    pages = "17387--17403",
    ISBN = "979-8-89176-395-1",
    abstract = "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 single-solution 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 propose TOPT, an efficient framework for learning optimal TL policies over large TG, as well as construct MultiSoTLBench, a large-scale Multi-Solution TL Benchmark, where each task admits multiple valid solutions. 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 task-relevant links. 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 RL-driven optimality analysis and scheduling on the expanded subgraph to generate an optimal tool chain that balances path length and tool cost. Comprehensive experiments on MultiSoTLBench demonstrate that TOPT generalizes effectively, improving task success and solution optimality by 46.21{\%} and 66.34{\%}, respectively."
}