# Tree-of-Traversals: A Zero-Shot Reasoning Algorithm for Augmenting Black-box Language Models with Knowledge Graphs

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 0 of its 54 references that are in the map.
- First posted on arXiv 31 Jul 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Built on by (most cited first, 11 of 11)

- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [Why Reasoning Fails to Plan: A Planning-Centric Analysis of Long-Horizon Decision Making in LLM Agents](https://mlsanity.com/paper/2601.22311/) (2026)
- [K-Edit: Language Model Editing with Contextual Knowledge Awareness](https://mlsanity.com/paper/2502.10626/) (2025)
- [RJE: A Retrieval-Judgment-Exploration Framework for Efficient Knowledge Graph Question Answering with LLMs](https://mlsanity.com/paper/2510.01257/) (2025)
- [Enhancing Large Language Models with Reward-guided Tree Search for Knowledge Graph Question and Answering](https://mlsanity.com/paper/2505.12476/) (2025)
- [From Symbolic to Neural and Back: Exploring Knowledge Graph-Large Language Model Synergies](https://mlsanity.com/paper/2506.09566/) (2025)
- [Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval](https://mlsanity.com/paper/2601.13969/) (2026)
- [Matching Game Preferences Through Dialogical Large Language Models: A Perspective](https://mlsanity.com/paper/2507.20000/) (2025)
- [Beyond Textual Context: Structural Graph Encoding with Adaptive Space Alignment to alleviate the hallucination of LLMs](https://mlsanity.com/paper/2509.22251/) (2025)
- [QueryGraph: Reliable Multi-Tool Query Execution Planning via LLM-Based Graph Generation](https://mlsanity.com/paper/2606.08300/) (2026)
- [KGCaRe: Explainable Complex Conditional Question Answering using Automatic Knowledge Graph Construction and Context Retrieval with LLMs](https://mlsanity.com/paper/2608.09779/) (2026)

## Abstract (arXiv)

Knowledge graphs (KGs) complement Large Language Models (LLMs) by providing reliable, structured, domain-specific, and up-to-date external knowledge. However, KGs and LLMs are often developed separately and must be integrated after training. We introduce Tree-of-Traversals, a novel zero-shot reasoning algorithm that enables augmentation of black-box LLMs with one or more KGs. The algorithm equips a LLM with actions for interfacing a KG and enables the LLM to perform tree search over possible thoughts and actions to find high confidence reasoning paths. We evaluate on two popular benchmark datasets. Our results show that Tree-of-Traversals significantly improves performance on question answering and KG question answering tasks. Code is available at urlhttps://github.com/amazon-science/tree-of-traversals