  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
\url{https://github.com/amazon-science/tree-of-traversals}
