# QueryGraph: Reliable Multi-Tool Query Execution Planning via LLM-Based Graph Generation

arXiv: https://arxiv.org/abs/2606.08300 · HTML: https://mlsanity.com/paper/2606.08300/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 10 of its 19 references that are in the map.
- First posted on arXiv 6 Jun 2026.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 10 of 10)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs](https://mlsanity.com/paper/2404.07103/) (2024)
- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [Tree-of-Traversals: A Zero-Shot Reasoning Algorithm for Augmenting Black-box Language Models with Knowledge Graphs](https://mlsanity.com/paper/2407.21358/) (2024)
- [GTool: Graph Enhanced Tool Planning with Large Language Model](https://mlsanity.com/paper/2508.12725/) (2025)
- [A Roadmap to Guide the Integration of LLMs in Hierarchical Planning](https://mlsanity.com/paper/2501.08068/) (2025)
- [Bootstrapping Object-level Planning with Large Language Models](https://mlsanity.com/paper/2409.12262/) (2024)

## Abstract (arXiv)

Many real-world queries over personal data span multiple applications and require structured planning, as individual tools expose only partial information. While LLMs show strong reasoning and tool use, reliably executing multi-step, cross-tool queries remains challenging. We introduce a system that converts natural language queries into structured graphs and executes them via a deterministic planner. Our approach uses depth-first search to resolve dependencies and combine results across tools, improving reliability and enabling queries beyond traditional keyword-based search. We demonstrate high accuracy even with smaller or locally hosted LLMs.