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

Routing natural-language requests to multi-step tool-execution graphs remains a critical challenge in agentic systems. Many existing approaches incur significant latency when they rely on multi-step autoregressive planning, and 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 dual-encoder architecture that pairs a shared text backbone with a directed graph neural network. We train LEGR with a symmetric contrastive objective and false-negative masking so that 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 percentage points over a fine-tuned sentence encoder) and a twin-restricted Recall@1 of 77.64\% (+16.3 percentage points over the same text baseline). Mean planning latency is 4.12\,ms, more than 250$\times$ faster than a 120B autoregressive planner, and every returned graph is a valid member of the index.