LEGR: Latent Execution-Graph Retrieval for Multi-Tool Tasks

Routing natural-language requests to multi-step tool-execution graphs remains a critical challenge for resource-constrained agents. Many existing approaches incur significant latency by relying on multi-step autoregressive planning. Conversely, flat text retrievers often fail when candidate workflows share the same tools but differ in dependency structure. We introduce Latent Execution-Graph Retrieval (LEGR), which retrieves an execution DAG from a pre-indexed corpus using a lightweight dual-encoder architecture that pairs a shared Small Language Model (SLM) backbone with a directed graph neural network. We train LEGR with a symmetric contrastive objective and false-negative masking so paraphrases of the same workflow do not contradict one another in-batch. On ToolTwin, a structural-twin benchmark with nested tool libraries of up to 45 tools, LEGR achieves an in-domain exact-graph Recall@1 of 79.29\% (+8.1 points over a fine-tuned sentence encoder) and a twin-restricted Recall@1 of 77.64\% (+16.3 points over the same text baseline). Mean planning latency is 4.12\,ms, making LEGR ideal for on-device deployment—operating >250$\times$ faster than a 120B planner while guaranteeing valid graphs.