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

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

Elan Sopher Markowitz, Anil Ramakrishna, Jwala Dhamala, Ninareh Mehrabi, Charith Peris, Rahul Gupta, Kai-Wei Chang, and Aram Galstyan, in ACL, 2024.

Download the full text

---

Abstract

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

---

---

Bib Entry

@inproceedings{markowitz2024tree,
  title = {Tree-of-Traversals: A Zero-Shot Reasoning Algorithm for Augmenting Black-box Language Models with Knowledge Graphs},
  author = {Markowitz, Elan Sopher and Ramakrishna, Anil and Dhamala, Jwala and Mehrabi, Ninareh and Peris, Charith and Gupta, Rahul and Chang, Kai-Wei and Galstyan, Aram},
  booktitle = {ACL},
  year = {2024}
}

---

Related Publications

1. Learning Structured Reasoning via Tractable Trajectory Control, ICML, 2026
2. Training LLMs for Divide-and-Conquer Reasoning, ACL, 2026
3. BRIEF-Pro: Universal Context Compression with Short-to-Long Synthesis for Fast and Accurate Multi-Hop Reasoning, ACL-Findings, 2026
4. Beyond Facts: Benchmarking Distributional Reading Comprehension in Large Language Models, ACL-Findings, 2026
5. MQuAKE-Remastered: Multi-Hop Knowledge Editing Can Only Be Advanced with Reliable Evaluations, ICLR, 2025
6. Towards Safety Reasoning in LLMs: AI-agentic Deliberation for Policy-embedded CoT Data Creation, ACL-Findings, 2025
7. QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search, ICML, 2025
8. DRS: Deep Question Reformulation With Structured Output, ACL-Findings, 2025
9. V-ALPHASOCIAL: Benchmark and Self-Reflective Chain-of-Thought Generation for Visual Social Commonsense Reasoning, ACL-Findings, 2025
10. VISCO: Benchmarking Fine-Grained Critique and Correction Towards Self-Improvement in Visual Reasoning, CVPR, 2025
11. BRIEF: Bridging Retrieval and Inference for Multi-hop Reasoning via Compression, NAACL-Finding, 2025
12. QUDSELECT: Selective Decoding for Questions Under Discussion Parsing, EMNLP, 2024
13. Model Editing Harms General Abilities of Large Language Models: Regularization to the Rescue, EMNLP, 2024
14. LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning, EMNLP-Finding, 2024
15. Are LLMs Capable of Data-based Statistical and Causal Reasoning? Benchmarking Advanced Quantitative Reasoning with Data, ACL-Findings, 2024
16. Can small language models help large language models reason better?: LM-guided chain-of-thought, LREC-COLING, 2024
17. IdealGPT: Iteratively Decomposing Vision and Language Reasoning via Large Language Models, EMNLP-Finding, 2023