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

Elan Markowitz , Work done while interning at Amazon
Corresponding author<EMAIL_ADDRESS>Amazon AGI  University of Southern
California  Anil Ramakrishna  Amazon AGI  Jwala Dhamala  Amazon AGI  Ninareh
Mehrabi  Amazon AGI
Charith Peris  Amazon AGI  Rahul Gupta  Amazon AGI  Kai-Wei Chang  Amazon AGI
Aram Galstyan  Amazon AGI

###### 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
https://github.com/amazon-science/tree-of-traversals

((a))  \raisebox{-.9pt} {1}⃝ Initial state seeded with the KG entities from
the query. Each subsequent step consists of selecting a tree node (rectangle),
sampling thoughts or actions from LLM, performing actions, and evaluating
outputs with LLM. ((b))  \raisebox{-.9pt} {2}⃝ Tree-of-Traversals selects
which node to search based on the values of the potential options. The “Expand
KG” option had higher value than “Answer: No one”. After choosing to Expand
KG, the model next selects which entities from the KG to expand. ((c))
\raisebox{-.9pt} {3}⃝ After selecting entities, the model next chooses what
relation to expand upon. The local knowledge graph is then updated with the
requested information. Unfortunately, in this case, the sampled actions
yielded low value output states. ((d))
((e))  \raisebox{-.9pt} {4}⃝ Since the previous selection yielded low-value
states, the model backtracks to the best alternative state. ((f))
\raisebox{-.9pt} {5}⃝ Tree-of-Traversals now has all the information needed
for the query and generates two answers. The correct answer is given a high
value by the LLM and is returned to the user. Figure 1: An example of how
Tree-of-Traversals uses a KG interface for the query, “What actor played in
both Inception and Interstellar?”.

##  1 Introduction

Large language models (LLMs) are used for a range of knowledge-intensive tasks
such as information retrieval Zhu et al. (2023b), summarization Zhang et al.
(2023), and question answering Tan et al. (2023). Trained on large amounts of
textual data, these models learn a wide breadth of information. However, LLMs
suffer from several limitations – they produce hallucinated information Ji et
al. (2022); Bang et al. (2023), lack deep domain-specific knowledge Pan et al.
(2023b), and have a static knowledge cutoff when training ends.

Knowledge graphs (KGs) naturally complement LLM weaknesses. KGs contain up-to-
date information covering general Vrandečić and Krötzsch (2014); Lehmann et
al. (2015) and/or domain-specific topics Abu-Salih (2020); Liu et al. (2019);
Zhu et al. (2017); Choi and Lee (2019); Farazi et al. (2020) in highly
structured and interpretable format. Augmenting an LLM’s ability to reason and
respond in natural language with an external KG’s up-to-date knowledge
presents a path toward a reliable and factual LLM.

The rise of powerful LLMs with new capabilities has renewed interest in
combining LLMs with KGS. Numerous survey and position papers have recently
emphasized their combined potential Pan et al. (2023a); Zhu et al. (2023a);
Yang et al. (2023); Pan et al. (2023b). Existing works augmented LLMs with KGs
in multiple ways, such as integration into pretraining Yasunaga et al. (2022),
fine-tuning Zhang et al. (2022), or later adaptation with subsequently trained
components Lin et al. (2019); Hu et al. (2022). All of these carry some
limitations. In particular, training or fine-tuning a large scale LLMs is
computationally expensive. In some cases, model weights are unavailable
publicly. Finally, the largest KGs require their own servers and cannot be
integrated in-memory with LLMs. Additionally, previous works do not consider
the case of augmenting with multiple KGs.

An algorithm that allows the augmentation of a powerful black-box LLM with any
number of internal or external KGs without training from scratch or fine-
tuning the model is valuable. Such a zero-shot algorithm would enable several
innovative use cases such as (1) customers using a black-box LLM API in
conjunction with an internal domain-specific KG, (2) integration of
personalized KGs into an LLM without the risks associated with training a
model with such personal data, (3) integration of deep domain knowledge via an
array of API accessible KGs (e.g., IMDb111IMDb API, MusicBrainz222MusicBrainz
API).

We introduce Tree-of-Traversals, a novel algorithm that addresses the above
issues by allowing the augmentation of any powerful LLM with arbitrary number
of KGs in a zero-shot fashion. It requires no training, functions with black-
box access to the LLM, and works with any API accessible KG. Our contributions
are:

  1. 1.

Tree of traversals: A novel zero-shot algorithm for augmenting any powerful
LLM with arbitrary number of KGs and enabling advanced KG reasoning using tree
search.

  2. 2.

Evaluation of Tree-of-Traversals on two question answering tasks:
2WikiMultiHop and QALD-10 and comparison with baselines.

  3. 3.

Development of a new dataset to test combined reasoning over a general and a
domain-specific KG, and evaluation of Tree-of-Traversals on this dataset.

We conduct detailed experiments on three models of varied sizes hosted on
Amazon Bedrock and present detailed ablation studies.

##  2 Tree-of-Traversals

The Tree-of-Traversals algorithm maintains a local KG subgraph that is
repeatedly expanded until it contains all the information required by an LLM
to answer the given query. At the start, a local KG subgraph is initialized to
contain the entities present in the original query. It is then expanded using
a tree search algorithm to choose actions and thoughts generated by an LLM in
order to obtain relevant knowledge from the KG using a KG interface. The
algorithm halts when the LLM is able to answer the original query using the
local KG subgraph as context. Tree-of-Traversals consists of three major
components. (1) A knowledge graph interface implemented to interact with one
or more required KGs. (2) An action state machine (ASM) which is a finite
state machine that defines the feasible space of actions, states, and prompt
templates when the LLM interacts with a KG to expand the local KG subgraph.
(3) A tree search algorithm which defines the overall LLM search trajectory
such as best first search, backtrack upon making a mistake, and termination
condition when an answer is found.

###  2.1 Knowledge Graph Interface

The knowledge graph interface allows Tree-of-Traversals to interact with one
or multiple KGs. Let $\mathcal{K}=(\mathcal{E},\mathcal{R},\mathcal{T})$ be a
single KG. $\mathcal{E}$ is the set of entities in which each entity consists
of an identifier, a label, and an optional description (e.g., Q35332,
‘Christopher Nolan’, ‘British-American filmmaker’). $\mathcal{R}$ is the set
of relation types, each consisting of an identifier, a label, and an optional
inverse label (P57, ‘director’, ‘is director of’). $\mathcal{T}$ is the set of
edges or facts in the KG in which each edge is of the form $(s,r,o)$ where
$s,o\in\mathcal{E}$ and $r\in\mathcal{R}$, e.g., (‘Inception’, ‘director’,
‘Christopher Nolan’). Tree-of-Traversals can be used for $\mathcal{K}$ as long
as the following interfaces are implemented.

  1. 1.

$\texttt{initialize}(q)\rightarrow\mathcal{E}_{0}$: It takes as input a query
$q$, extracts entities from $q$ and returns the linked entities
$\mathcal{E}_{0}\subset\mathcal{E}$ where $\mathcal{E}_{0}$ are the entities
from $\mathcal{K}$ that are referenced in $q$.

  2. 2.

$\texttt{get\\_relations}(\mathcal{E}_{selected})\rightarrow\mathcal{R}_{options}$:
It takes a set of entities, $\mathcal{E}_{selected}$, and returns the relation
types, $\mathcal{R}_{options}\subset\mathcal{R}$, that
$\mathcal{E}_{selected}$ have in $\mathcal{K}$:
$\left\\{r|(s,r,o)\in\mathcal{T},s\in\mathcal{E}_{selected}\right\\}$

  3. 3.

$\texttt{get\\_edges}(\mathcal{E}_{selected},r)$ $\rightarrow$
$\mathcal{T}_{added},\mathcal{E}_{added}$: It takes a set of entities and a
selected relation type, and returns all edges with relation type $r$ for
source entities in $\mathcal{E}_{selected}$:
$\left\\{(s,r,o)\in\mathcal{T}|s\in\mathcal{E}_{selected},r=r,o\in\mathcal{E}\right\\}$.
It also returns the new entities, $\mathcal{E}_{added}$, that are entities
reached with $\mathcal{T}_{added}$.

This interface is implemented with SPARQL queries when available; otherwise,
we use the graph API that is available for the KG. For multiple KGs, each
interface is implemented separately.

###  2.2 Action State Machine (ASM)

One of the challenges with developing a zero-shot LLM algorithm that works
with arbitrary KGs is that the LLM does not know what relations are available
in the graph or what relations are valid for a given entity. Few-shot or in-
context learning approaches can only cover a handful of the possible relation
types (e.g., Wikidata has over 11,000 relation types) Brown et al. (2020).

Figure 2: Action State Machine

To overcome these issues we break the task of expanding a local KG subgraph
into multiple subtasks. We use a finite state machine with the following
actions: Think, Answer, ExpandKG, Select_Entities, and Select_Relation, and
states: default, selecting-entities, selecting-relation, and done as shown in
Figure 2. This is named as Action State Machine (ASM) throughout the paper.

From the default state, Tree-of-Traversals can either Think, Answer, or choose
to ExpandKG. After Tree-of-Traversals chooses to ExpandKG, it first is
prompted to Select_Entities about which it needs more information (e.g.,
‘Inception’ in Figure 1). It is then prompted to Select_Relation from a list
of candidate relations provided by the KG interface’s get_relations method.
After selecting a relation (e.g., ‘cast member’ in Figure 1), all edges
containing one of the selected entities as the source and the selected
relation as the relation are added to the local KG subgraph. Tree-of-
Traversals is then able to Answer, Think, or ExpandKG again.

#### Prompt Templates.

Each state in the ASM other than the ‘done’ state is associated with a unique
prompt template. Prompt templates are filled with information from the local
KG subgraph and the KG interface before presenting them to the LLM. A
customized prompt for each state allows us to present precise and relevant
information along with specific instructions for each state to the LLM
simplifying the LLM’s task. For instance, the prompt for ‘selecting-entities’
presents the available options of entities to choose from that are in the
local KG subgraph (see Figure 3). Prompt templates for all the states are in
the Appendix F.1-F.3.

Local KG subgraph is represented using a a token efficient YAML format that
minimizes repetition for multiple edges on the same entity.

⬇

Original Query:

Who is Bob Dylan’s maternal grandmother?

Knowledge Graph Entities:

Q392: Bob Dylan - American singer-songwriter

Q62519478: Beatrice Stone

Knowledge Graph Edges:

Bob Dylan:

mother:

Beatrice Stone

Previous Actions:

...

Current task: Select entities to expand from [Q392, Q62519478]

Selection:

Figure 3: Prompt for the ‘selecting-entities’ state of the ASM. The original
query and the local KG subgraph are part of the prompt for every action state
while the ‘Current task’ differs. The entity options show what entities can be
selected based on the current local KG subgraph. If the model selected
Q62519478: Beatrice Stone here, then in the next action state (selecting-
relation), the dynamic prompt would list the relation types that Beatrice
Stone has edges for.

#### Invoking KG Interfaces.

Outside of initialization, there are two times in which the ASM needs to
invoke the KG interface: (1) When constructing the selecting-relation prompt,
the algorithm calls $\texttt{get\\_relations}(\mathcal{E}_{selected})$ to
gather available choices of relations. (2) When executing the transition from
selecting-relation to default after having selected a relation type $r$, the
algorithm calls $\texttt{get\\_edges}(\mathcal{E}_{selected},r)$ so that it
can add the new edges and entities to the local subgraph.

###  2.3 Tree Search Algorithm

Our approach draws inspiration from the Tree-of-Thoughts approach Yao et al.
(2023) in which an LLM is given increased reasoning power by allowing
generation of multiple thoughts at a time and building a search tree over the
resulting reasoning chains. We extend this approach to augment LLMs with KGs
through allowing the generation of actions in addition to thoughts, and
building a search tree over them. Challenges arise because Tree-of-Thoughts
was not designed to incorporate actions and was not designed for knowledge
intensive question answering tasks. As a result, we introduce some
modifications: incorporation of actions via the ASM, a slightly different
search procedure and stopping condition to better handle QA, and a different
sampling procedure for improved diversity when doing constrained sampling.

Algorithm 1 presents the Tree-of-Traversals tree search algorithm. Given a
query $q$ it begins with initialization using $\texttt{initialize}(q)$ as
described in Section 2.1. After initialization, it searches by (1) choosing
the unexplored node to expand based on the node’s value assigned by the value
function (Best First$\rightarrow$ Depth First as tie-breaker), (2) sampling
$k$ actions from the LLM ($k$ is branching factor) using the prompt associated
with the selected node’s state in the ASM, (3) for each of the sampled action,
applying the transition function, and (4) evaluating the value of the
resulting nodes with the LLM value function. The search stops when an answer
is found with a node value exceeding the threshold $\tau$. To bound the search
space we add two hyper-parameters: max depth of the tree search, after which
the algorithm is forced to transition to the done state (i.e., answer the
query), and max expansions after which the model halts exploration and returns
"Cannot find answer".

Algorithm 1 Tree-of-Traversals

Input: $q\leftarrow$ query, $k\leftarrow$ branching factor,
$\tau\leftarrow$ answer threshold, $P\leftarrow$ LLM,
$\mathcal{F}\leftarrow$ ASM
Output: Answer to $q$

1:procedure ToActions($q$)

2: $T\leftarrow\phi$$\triangleright$ Empty tree

3: $Y\leftarrow\phi$$\triangleright$ Empty answer set

4: $s_{0}\leftarrow\texttt{initialize}(q)$

5: $T$.add($s_{0}$)

6: while $!finished$ do

7: $s\leftarrow\texttt{choose\\_node}(T)$

8:$\triangleright$ Sample $k$ actions from $P$ using the action state and
associated prompt of $s$ from $\mathcal{F}(s)$

9: $\textbf{a}\leftarrow\texttt{sample\\_actions}(s,k,\mathcal{F},P)$

10: for $a\in\textbf{a}$ do

11:$\triangleright$ Apply action $a$ to state $s$ according to $\mathcal{F}$

12: $s^{\prime}\leftarrow\texttt{transition}(s,a,\mathcal{F})$

13:$\triangleright$ Evaluate the resulting state $s^{\prime}$ using $P$

14: $s^{\prime}.value\leftarrow\texttt{evaluate}(s^{\prime},P)$

15: $T.add(s^{\prime})$

16: if $s^{\prime}.action\\_state=done$ then

17: $Y.add(s^{\prime})$

18: if $s^{\prime}.value>\tau$ then

19:$\triangleright$ When answer exceeds threshold, stop search

20: $finished\leftarrow True$

21: return $\arg\\!\max_{y\in Y}{y.value}$

#### Value Function Guidance.

Tree-of-Traversals computes the value of a node to determine its utility. This
value is created by the LLM using evaluation prompts (step evaluate in
Algorithm 1). The value can be between 0 to 1 where 1 indicates highest
utility. We use two types of evaluation prompts: one for intermediate states
and one for answer states. The prompts include the original query, the local
KG subgraph, the trajectory of previous actions, followed by instructions for
evaluating the node (see Appendix F.4 and F.5). These values are then used to
guide the exploration of the action space. Specifically, choose_node returns
the unexplored node with the highest value (Best First). If there are nodes
with the same value, Depth First Search is used.

#### Chain-of-Traversals.

In some cases we can find the answer to a query with a single sequence of
thoughts and actions using the ASM and KG interface. This is equivalent to
Tree-of-Traversals with a branching factor of $k=1$. We refer to this as
Chain-of-Traversals. While useful for comparison, experiments show the benefit
of considering multiple branches.

###  2.4 Tree-of-Traversals with Multiple KGs

Augmenting an LLM with more than one KG mainly involves building KG interfaces
for each of the added KGs. There are a few other changes to the algorithm. (1)
The entities extracted in $\texttt{initialize}(q)$ are matched with each KG
interface. (2) When presenting the options of relations during selecting-
relation, $\texttt{get\\_relations}(\mathcal{E}_{selected})$ is called on each
KG interface. (3) When adding a new entity to the local KG subgraph we call an
entity linking function for the other KG interfaces. We allow for the entity
linking function to be a separate function in the KG interface or to fallback
on $\texttt{initialize}(o)$ where $o$ is the text label of the entity that has
just been added. This makes allows the use of explicit links between common
KGs if available while still functioning without.

##  3 Experiments

We evaluate Tree-of-Traversals using three different models available on
Amazon Bedrock333https://aws.amazon.com/bedrock: Claude-Instant (claude-
instant-v1), Llama2 70b (llama2-70b-chat-v1), and Llama2 13b
(llama2-13b-chat-v1). AWS Bedrock provides on-demand access through a single
API to various Foundation Models, including both open source and black box
ones. This is precisely a use case Tree-of-Traversals is designed for.

|  2WikiMultiHop ($\uparrow$)
---|---
Algorithm | Claude-Instant | Llama2-70b | Llama2-13b
Chain-of-Thought | 25.2 | 30.4 | 26.8
ReAct | 5.8 | 30.4 | 6.8
ReAct$\rightarrow$ CoT | 27.0 (84.8%) | 41.6 (41.6%) | 23.6 (71.8%)
FLARe | 35.0 | 45.4 | 34.8
Chain-of-Traversals | 42.6 | 45.0 | 31.0
Tree-of-Traversals | 63.0 | 56.6 | 37.3
|  QALD-10 ($\uparrow$)
Algorithm | Claude-Instant | Llama2-70b | Llama2-13b
Chain-of-Thought | 47.4 | 40.0 | 42.6
ReAct | 3.1 | 23.7 | 8.7
ReAct$\rightarrow$ CoT | 47.9 (72.6%) | 43.4 (44.4%) | 40.8 (79.5%)
FLARe | 39.2 | 38.8 | 23.1
Chain-of-Traversals | 55.7 | 56.9 | 39.6
Tree-of-Traversals | 64.3 | 61.6 | 39.2
Table 1: EM-in on 2WikiMultiHop dataset. $\rightarrow$CoT indicates falling
back to Chain-of-Thought when no answer is given. (%) indicates the number of
such cases.

###  3.1 Tasks and Datasets.

We first evaluate the Tree-of-Traversals algorithm on two common tasks used
for evaluating an LLM’s knowledge: 2WikiMultiHop and QALD-10. To allow testing
on complex questions requiring knowledge from multiple KGs we create a new
dataset that requires knowledge from multiple KGs.

2WikiMultiHop Dataset Ho et al. (2020) was constructed by extracting multi-hop
templates from HotPotQA Yang et al. (2018), combining templates to get complex
reasoning questions, generating candidate questions with Wikidata, and then
confirming that the entity mentions for each edge appear in the Wikipedia
paragraphs. Answers to these questions can be derived from both Wikipedia and
Wikidata Vrandečić and Krötzsch (2014). We subsample 500 questions from the
test set following the approach used in ReAct Yao et al. (2022), including the
sampling seed value of 233.

QALD-10 Dataset Usbeck et al.  is a multi-lingual Knowledge Graph Question
Answering (KGQA) dataset with 395 questions created by humans, translated into
other languages, and then constructed as a SPARQL query over
Wikidata444https://github.com/KGQA/QALD-10. These questions are more varied in
terms of reasoning structure than the questions in 2WikiMultiHop (e.g.
requiring multiple answers or aggregations). We used the questions in English
language.

Which event was hosted in a venue with a largermaximum capacity, Fearless
Tour: Indianapolisor Fearless Tour: Omaha? 1\. Get venue for Fearless Tour:
Indiana-
polis $\rightarrow$ Gainbridge Fieldhouse
2\. Get venue for Fearless Tour: Omaha
$\rightarrow$ CHI Health Center Omaha
3\. Get maximum capacity of the respec- tive venues $\rightarrow$ (18165,
18975) 4\. Answer: Fearless Tour: Omaha was hosted in a venue with a larger
maximum capacity. Figure 4: Example question from MusicBrainz-x-Wiki and how
Tree-of-Traversals arrives at its final answer. Red indicates entities and and
relationships belonging to MusicBrainz. Green indicates relationships only in
Wikidata. Blue indicates entities linked to both KGs.

MusicBrainz-x-Wikidata Dataset One novel use-case of Tree-of-Traversals is
synthesizing and reasoning over multiple knowledge graph sources. There is no
existing dataset that requires synthesizing information from multiple KGs to
answer individual questions. Therefore, to test the reasoning ability using
multiple KGs, we create a new dataset, MusicBrainz-x-Wikidata, containing 109
questions that require reasoning with information from both MusicBrainz and
Wikidata. Unlike Wikidata which contains general knowledge, MusicBrainz is a
deep domain-specific database on the music industry. The vast majority of this
information is unlikely to be known by large language models. We construct the
MusicBrainz-x-Wikidata dataset with human annotators who were provided with
instructions to find reasoning paths between these two KGs, the question types
to focus on, and some example questions. The curated questions were checked
for ambiguity and sensibility. By design, each question requires extracting
information from both knowledge graphs in order to answer it successfully. In
addition to the reasoning types in 2WikiMultiHop, this dataset contains
questions that involve aggregations, comparisons of aggregations,
qualifications, and complex combinations of these. An example can be seen in
Figure 4. Detail on instructions, question types, and examples are in Appendix
A.

###  3.2 Metric.

We use Exact Match Included (EM-in) as the evaluation metric. EM-in is 1 if
the ground truth answer appears with an exact match anywhere in the answer and
0 otherwise. This accounts for the propensity of an LLM to output answers in a
sentence with varying syntax. This is a common metric but is often referred to
interchangeably with Exact Match (EM) Sun et al. (2023). When there are
multiple answers, we compute average EM-in over all labels.

###  3.3 Comparison Baselines.

We experiment against three related approaches that can work with any black-
box LLMs: (1) Chain-of-Thought (CoT) prompting Wei et al. (2022) (2) ReAct Yao
et al. (2022) which iterates between generating thoughts and generating
actions for searching and retrieving from a text knowledge base like
Wikipedia, and (3) Forward Looking Active Retrieval (FLARe) Jiang et al.
(2023b) which iterates between generating thoughts and then retrieving from a
knowledge base to correct inaccuracies.

###  3.4 Implementation details.

For all models, we use a sampling temperature of 0.0 for the LLM when multiple
samples are not required and a temperature of 1.0 when diverse samples are
required. We test our approach in two settings: (1) with a branching factor of
$k=1$ termed as Chain-of-Traversals, and (2) with a branching factor of $k=3$
termed as Tree-of-Traversals. In both setups, we set maximum depth to 7 which
means that upon reaching the default action state beyond depth 7, the only
available action is to answer the question. For Tree-of-Traversals, we set the
maximum total expansions to 20. The answer threshold $\tau$ is set to 0.8
which corresponds to high confidence answers supported by the KG according the
evaluate prompt (Appendix F.5).

For 2WikiMultiHop and QALD-10, we use Wikidata as the knowledge graph
Vrandečić and Krötzsch (2014). For MusicBrainz-x-Wikidata, we use MusicBrainz
in addition to Wikidata. We implement the KG interface for Wikidata using
Wikidata SPARQL queries555https://query.wikidata.org/, and implement the KG
interface for MusicBrainz KG using the MusicBrainz
API666https://musicbrainz.org/doc/MusicBrainz_API.

##  4 Results and Discussion

|  Music-x-Wiki ($\uparrow$)
---|---
Algorithm | Claude-Instant | Llama2-70b | Llama2-13b
Chain-of-Thoughts | 11.9 | 10.1 | 13.8
Chain-of-Traversals | 22.0 | 21.9 | 14.7
Tree-of-Traversals | 40.4 | 23.4 | 16.5
Table 2: EM-in on MusicBrainz-x-Wikidata dataset.

Table 1 presents the results of our experiments on 2WikiMultiHop and QALD-10.
For all the models, Tree-of-Traversals outperforms the baselines on
2WikiMultiHop, setting state-of-the-art results for these tasks in the zero-
shot setting. We hypothesize that much of this gain is due to Tree-of-
Traversals’ access to the knowledge base via proposed KG interface and its
thought-action procedure guided by the ASM. This is evident, as even Chain-of-
Traversals, which does not perform a tree traversal (including multiple
thoughts/actions, backtracking, and node value computation), significantly
outperforms ReAct’s knowledge grounding: 8.7% higher accuracy than
ReAct$\rightarrow CoT$ on 2WikiMultiHop when averaged over all models.
Compared to Chain-of-Traversals, Tree-of-Traversals further improves
performance. It gives on average a 12.8% absolute accuracy increase for
2WikiMultiHop and 4.3% absolute improvement for QALD-10. We note that the
better performing the model is, the more it stands to gain from Tree-of-
Traversals as noted by the difference between Llama-70b and Llama-13b.

Figure 5: The EM-in accuracy for answers with model assigned value 0.0 or 1.0
and the corresponding true EM-in score of the answer. This includes all
proposed answers, not just the final answer returned by the model.

On MusicBrainz-x-Wikidata (Table 2), which contains challenging reasoning
questions requiring access to two KGs, there is an average of 37.4% relative
improvement from Tree-of-Traversals over Chain-of-Traversals as shown in Table
2. Both Chain-of-traversals and Tree-of-Traversals outperform Chain-of-
Thoughts on this dataset. We only compare with Chain-of-Thoughts as other
retrieval methods have low coverage over the MusicBrainz knowledge base.

###  4.1 Effect of the Value Function.

Tree-of-Traversals relies on signal from the value function to pick the final
tree trajectory. If the values were arbitrary, then Tree-of-Traversals would
not do any better than Chain-of-Traversals. Figure 5 shows that there is a
meaningful signal from the value function for all models. There is an average
performance difference of 31.0% between the accuracy for answers valued at 1.0
vs 0.0. This represents an average relative improvement of 83.2% when
selecting answers valued at 1.0 over those valued at 0.0. See Appendix C for
individual profiles of each model’s value function.

###  4.2 Effect of Backtracking.

To determine the effect of backtracking in Tree-of-Traversals, we ask the
counter-factual of how would the model perform if it could not backtrack
(Figure 6). We limit the analysis to 2WikiMultiHop questions in which Tree-of-
Traversals generates answers on a subtree, and the model eventually backtracks
on that subtree (i.e., the cases where we have a counter-factual). As a
result, these questions are generally more challenging than the overall
distribution of questions. In these cases, we compare the result if the
highest-valued answer was taken from the first searched subtree compared to
the ultimate answer after backtracking. We find that the ability to backtrack
gives Tree-of-Traversals a significant accuracy increase ranging from 4.1% to
12.3%.

Figure 6: Comparison of results with and without backtracking on 2WikiMultiHop
questions that needed backtracking. There would be a major degradation in
performance if backtracking was not allowed.

###  4.3 Performance on MusicBrainz-x-Wikidata.

For MusicBrainz-x-Wikidata dataset, we only compare against Chain-of-Thought
since the implementations for other baseline algorithms do not have access to
similar music-specific knowledge bases. Despite this, we observed some
interesting results. Chain-of-Thought does far worse on MusicBrainz-x-Wikidata
than on the more general datasets based exclusively on Wikipedia/Wikidata
(10.1%-13.8% vs. 25.2%-47.4%). This could be because LLMs are trained on vast
amount of general knowledge such as that found in Wikipedia, but they are not
trained with as much data from specific domains such as music. Besides the
presence of KG interface and ASM with Tree-of-Traversals, this could be an
additional reason why Tree-of-Traversals does 2.2 times as well as Chain-of-
Thought on MusicBrainz-x-Wikidata. This demonstrates the importance of
augmenting LLMs with domain-specific KGs and/or multiple KGs which the
proposed Tree-of-Traversals is capable of.

###  4.4 Analysis of Baselines.

ReAct underperforms Chain-of-Thought in most cases. This phenomenon was seen
in the original ReAct paper which noted that their approach significantly
reduced hallucinations despite lower accuracy Yao et al. (2022). Therefore,
falling back on Chain-of-Thought results in an accuracy improvements for for
Llama2-70b and Claude-Instant. We note that claude-instant vastly
underperforms Llama2-70b on ReAct. The primary reason for this is claude-
instant refuses to "search" people and apologizes after performing invalid
actions. Despite this, ReAct$\rightarrow$CoT still improves over CoT on both
2WikiMultiHop and QALD-10. FLARe improves model performance on 2WikiMultiHop
but not on QALD-10. This may be due to better overlap between the text
knowledge base for 2WikiMultiHop.

##  5 Related Works

#### Knowledge Base Question Answering

There is a large history of work that has looked into answering questions
using a knowledge graph Wu et al. (2019); Lan et al. (2021). The approaches
can broadly be broken into those that attempt to parse the question into a
logical form Berant and Liang (2014); Luo et al. (2018); Zhu et al. (2022),
and information retrieval approaches Bordes et al. (2015); Chen et al. (2019)

#### Knowledge Enhancement.

Recently, researchers have looked into enhancing pretrained language models
and LLMs using knowledge graphs. Many works have focused on incorporating
knowledge graph data into LLMs through training, often with architectural
changes to the model Zhang et al. (2019); Wang et al. (2019); Peters et al.
(2019); Yamada et al. (2020); He et al. (2021). Some of these have found
success using specialized graph encoder layers Yasunaga et al. (2021); Sun et
al. (2021). Some have sought to mix this process with pretraining of the
language model Yasunaga et al. (2022). The limitations of including KGs during
LLM training are: the models are incapable of incorporating KG updates without
retraining, are not able to change KG source (e.g., a domain-specific one),
and may have low explainability resulting from learning knowledge in model
weights rather than explicit retrieval. In addition, these methods add
complexity to the training process, increase cost, and do not work with LLM
without access to model weights. As a result, scaling these methods has often
been seen as too risky.

Other methods treat a KG as a more complete source of truth and use the LLM to
generate structured queries for the KG. Tianle et al. (2023) and Choudhary and
Reddy (2023) teach the LLM to generate a logical KG query which then returns
matching entities from the KG. These methods share similarities with the
semantic parsing based approaches mentioned earlier. However, by returning a
logical query for the KG, these methods lose the reasoning and commonsense
abilities of the LLM.

Some approaches have looked at injecting KG or knowledge base data into LLM
prompts. Many methods do a single round of retrieval based on the query Lewis
et al. (2020); Li et al. (2023) using a retrieval mechanism, such as dense
passage retrieval Karpukhin et al. (2020). These methods cannot answer more
complex multi-hop questions as the initial retrieval is unlikely to contain
the secondary or tertiary information that will ultimately be required. Later
methods have made the retrieval process iterative. E.g. FLARe Jiang et al.
(2023b) uses prediction of the upcoming sentence to retrieve relevant
documents and regenerates until the sentence contains high-confidence tokens.
In Wang et al. (2023) multi-round QA format is used for multi-round retrieval.
ReAct Yao et al. (2022) does multiple rounds of thoughts and actions to query
a text-based knowledge base. Jiang et al. (2023a) repeatedly interfaces with a
KG. In other parallel works, Sun et al. (2023); Wen et al. (2023) explore
methods for building KG context for LLMs using path and neighborhood based
search methods. The above methods do not incorporate tree search or forms of
advanced reasoning beyond the LLM’s innate ability. They cannot explore
multiple reasoning paths or solutions and cannot backtrack if making a
mistake. This results in lesser capabilities. Additionally, none of the above
methods explore reasoning over multiple KGs.

#### Multiple Knowledge Base QA.

Some works studied QA on questions derived from differing domains. These works
learn to pick between different domain-specific QA models, each trained on a
single knowledge base Puerto et al. (2021); Geigle et al. (2021); Puerto et
al. (2023). Besides requiring training, such systems cannot answer questions
requiring the synthesis of information from different domains (MusicBrainz-x-
Wikidata).

##  6 Conclusion

Tree-of-Traversals is a powerful algorithm that enables LLMs to utilize KG
reasoning with zero examples, no schema dependency, and no training. We
demonstrate its efficacy experimentally on multiple LLMs and datasets. We hope
Tree-of-Traversals continues to be developed and see value in studying
integration with personalized user KGs as well as with other domain-specific
datasets.

##  7 Limitations

Tree-of-Traversals is slower than simpler retrieval alternatives. Improving
the value function would reduce the number of LLM and KG API calls by avoiding
incorrect paths along the tree to explore. Other engineering solutions, such
as hosting graph servers, could be implemented to accelerate LLM and KG
access. In terms of the token cost, the KG text representation is token
efficient compared to many retrieval methods using unstructured knowledge
bases as the latter tend to maximize usage of the LLM context window. However,
compared to non-retrieval baselines, there is significant increase in token
usage cost.

The types of KG questions that can be answered are limited by the context
window, search depth, and LLM’s reasoning ability. For instance, a very large
aggregation (‘How many mountains have elevation above 3500 meters?’) would
require more entities than what fits in the LLM context. Future work could
look at adding other actions to the ASM, such as aggregations, that could
distill the local KG into more relevant information.

EM-in is also an imperfect metric. False negatives can arise from
discrepancies in date and number formatting, text formatting, and aliasing.
False positives can arise in cases in which the model does not definitively
answer but includes the correct answer in its response.

##  8 Ethical Impact

We do not anticipate Tree-of-Traversals to introduce new areas of risk but it
may have unstudied effects on existing risks of LLMs or KGs. We highlight the
following areas. (i) Tree-of-Traversals gives new capabilities to LLMs after
training. While positive in terms of accuracy, we have not evaluated its
effect on wider safety metrics. (ii) Our evaluation is limited to only English
versions of KGs and datasets. Tree-of-Traversals should be evaluated in other
languages to ensure consistent and fair experience. (iii) We have not
performed analysis under misleading or deceptive knowledge graphs. Using a
publicly modifiable knowledge graph does come with the risk that information
could be deceptively changed.

In terms of positive ethical impact, making this research public democratizes
access to knowledge-augmented LLMs as this method does not require a large
training investment or owning the language model to build and customize.

## References

  * Abu-Salih (2020) Bilal Abu-Salih. 2020.  Domain-specific knowledge graphs: A survey.  _ArXiv_ , abs/2011.00235.
  * Bang et al. (2023) Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, Quyet V. Do, Yan Xu, and Pascale Fung. 2023.  A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity.  _ArXiv_ , abs/2302.04023.
  * Berant and Liang (2014) Jonathan Berant and Percy Liang. 2014.  Semantic parsing via paraphrasing.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Bordes et al. (2015) Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. 2015.  Large-scale simple question answering with memory networks.  _ArXiv_ , abs/1506.02075.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, T. J. Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeff Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  _ArXiv_ , abs/2005.14165.
  * Chen et al. (2019) Zi-Yuan Chen, Chih-Hung Chang, Yi-Pei Chen, Jijnasa Nayak, and Lun-Wei Ku. 2019.  Uhop: An unrestricted-hop relation extraction framework for knowledge-based question answering.  _ArXiv_ , abs/1904.01246.
  * Choi and Lee (2019) Wonjun Choi and Hyunju Lee. 2019.  Inference of biomedical relations among chemicals, genes, diseases, and symptoms using knowledge representation learning.  _IEEE Access_ , 7:179373–179384.
  * Choudhary and Reddy (2023) Nurendra Choudhary and Chandan K. Reddy. 2023.  Complex logical reasoning over knowledge graphs using large language models.  _ArXiv_ , abs/2305.01157.
  * Farazi et al. (2020) Feroz Farazi, Maurin Salamanca, Sebastian Mosbach, Jethro Akroyd, Andreas Eibeck, Leonardus Kevin Aditya, Arkadiusz Chadzynski, Kang Pan, Xiaochi Zhou, Shaocong Zhang, Mei Qi Lim, and Markus Kraft. 2020.  Knowledge graph approach to combustion chemistry and interoperability.  _ACS Omega_ , 5:18342 – 18348.
  * Geigle et al. (2021) Gregor Geigle, Nils Reimers, Andreas Ruckl’e, and Iryna Gurevych. 2021.  Tweac: Transformer with extendable qa agent classifiers.  _ArXiv_ , abs/2104.07081.
  * He et al. (2021) Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji rong Wen. 2021.  Improving multi-hop knowledge base question answering by learning intermediate supervision signals.  _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_.
  * Ho et al. (2020) Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020.  Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 6609–6625, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Hu et al. (2022) Ziniu Hu, Yichong Xu, W. Yu, Shuohang Wang, Ziyi Yang, Chenguang Zhu, Kai-Wei Chang, and Yizhou Sun. 2022.  Empowering language models with knowledge graph reasoning for open-domain question answering.  _ArXiv_ , abs/2211.08380.
  * Ji et al. (2022) Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Yejin Bang, Wenliang Dai, Andrea Madotto, and Pascale Fung. 2022.  Survey of hallucination in natural language generation.  _ACM Computing Surveys_ , 55:1 – 38.
  * Jiang et al. (2023a) Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji rong Wen. 2023a.  Structgpt: A general framework for large language model to reason over structured data.  _ArXiv_ , abs/2305.09645.
  * Jiang et al. (2023b) Zhengbao Jiang, Frank F. Xu, Luyu Gao, Zhiqing Sun, Li-Yu Daisy Liu, Jane Dwivedi-Yu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023b.  Active retrieval augmented generation.  _ArXiv_ , abs/2305.06983.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Yu Wu, Sergey Edunov, Danqi Chen, and Wen tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Lan et al. (2021) Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji rong Wen. 2021.  A survey on complex knowledge base question answering: Methods, challenges and solutions.  _ArXiv_ , abs/2105.11644.
  * Lehmann et al. (2015) Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, S. Auer, and Christian Bizer. 2015.  Dbpedia - a large-scale, multilingual knowledge base extracted from wikipedia.  _Semantic Web_ , 6:167–195.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandara Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Kuttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _ArXiv_ , abs/2005.11401.
  * Li et al. (2023) Shiyang Li, Yifan Gao, Hao Jiang, Qingyu Yin, Zheng Li, Xifeng Yan, Chao Zhang, and Bing Yin. 2023.  Graph reasoning for question answering with triplet retrieval.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Lin et al. (2019) Bill Yuchen Lin, Xinyue Chen, Jamin Chen, and Xiang Ren. 2019.  Kagnet: Knowledge-aware graph networks for commonsense reasoning.  _ArXiv_ , abs/1909.02151.
  * Liu et al. (2019) Yang Liu, Qingguo Zeng, Joaquín B. Ordieres Meré, and Huanrui Yang. 2019.  Anticipating stock market of the renowned companies: A knowledge graph approach.  _Complex._ , 2019:9202457:1–9202457:15.
  * Luo et al. (2018) Kangqi Luo, Fengli Lin, Xusheng Luo, and Kenny Q. Zhu. 2018.  Knowledge base question answering via encoding of complex query graphs.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Pan et al. (2023a) Jeff Z. Pan, Simon Razniewski, Jan-Christoph Kalo, Sneha Singhania, Jiaoyan Chen, Stefan Dietze, Hajira Jabeen, Janna Omeliyanenko, Wen Zhang, Matteo Lissandrini, Russa Biswas, Gerard de Melo, Angela Bonifati, Edlira Vakaj, Mauro Dragoni, and Damien Graux. 2023a.  Large language models and knowledge graphs: Opportunities and challenges.  _ArXiv_ , abs/2308.06374.
  * Pan et al. (2023b) Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. 2023b.  Unifying large language models and knowledge graphs: A roadmap.  _ArXiv_ , abs/2306.08302.
  * Peters et al. (2019) Matthew E. Peters, Mark Neumann, IV RobertL.Logan, Roy Schwartz, Vidur Joshi, Sameer Singh, and Noah A. Smith. 2019.  Knowledge enhanced contextual word representations.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Puerto et al. (2023) Haritz Puerto, Tim Baumgärtner, Rachneet Sachdeva, Haishuo Fang, Haotian Zhang, Sewin Tariverdian, Kexin Wang, and Iryna Gurevych. 2023.  Ukp-square v3: A platform for multi-agent qa research.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Puerto et al. (2021) Haritz Puerto, Gözde Gül Şahin, and Iryna Gurevych. 2021.  Metaqa: Combining expert agents for multi-skill question answering.  _ArXiv_ , abs/2112.01922.
  * Sun et al. (2023) Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Sai Wang, Chen Lin, Yeyun Gong, Heung yeung Shum, and Jian Guo. 2023.  Think-on-graph: Deep and responsible reasoning of large language model with knowledge graph.  _ArXiv_ , abs/2307.07697.
  * Sun et al. (2021) Yu Sun, Shuohuan Wang, Shikun Feng, Siyu Ding, Chao Pang, Junyuan Shang, Jiaxiang Liu, Xuyi Chen, Yanbin Zhao, Yuxiang Lu, Weixin Liu, Zhihua Wu, Weibao Gong, Jianzhong Liang, Zhizhou Shang, Peng Sun, Wei Liu, Ouyang Xuan, Dianhai Yu, Hao Tian, Hua Wu, and Haifeng Wang. 2021.  Ernie 3.0: Large-scale knowledge enhanced pre-training for language understanding and generation.  _ArXiv_ , abs/2107.02137.
  * Tan et al. (2023) Yiming Tan, Dehai Min, Y. Li, Wenbo Li, Na Hu, Yongrui Chen, and Guilin Qi. 2023.  Can chatgpt replace traditional kbqa models? an in-depth analysis of the question answering performance of the gpt llm family.
  * Tianle et al. (2023) Li Tianle, Xueguang Ma, Alex Zhuang, Yu Gu, Yu Su, and Wenhu Chen. 2023.  Few-shot in-context learning on knowledge base question answering.  In _Annual Meeting of the Association for Computational Linguistics_.
  * (34) Ricardo Usbeck, Xi Yan, Aleksandr Perevalov, Longquan Jiang, Julius Schulz, Angelie Kraft, Cedric Möller, Junbo Huang, Jan Reineke, Axel-Cyrille Ngonga Ngomo, et al.  Qald-10—the 10th challenge on question answering over linked data.
  * Vrandečić and Krötzsch (2014) Denny Vrandečić and Markus Krötzsch. 2014.  Wikidata: a free collaborative knowledgebase.  _Commun. ACM_ , 57:78–85.
  * Wang et al. (2023) Keheng Wang, Feiyu Duan, Sirui Wang, Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and Zhang Xiong. 2023.  Knowledge-driven cot: Exploring faithful reasoning in llms for knowledge-intensive question answering.  _ArXiv_ , abs/2308.13259.
  * Wang et al. (2019) Xiaozhi Wang, Tianyu Gao, Zhaocheng Zhu, Zhiyuan Liu, Juan-Zi Li, and Jian Tang. 2019.  Kepler: A unified model for knowledge embedding and pre-trained language representation.  _Transactions of the Association for Computational Linguistics_ , 9:176–194.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Huai hsin Chi, F. Xia, Quoc Le, and Denny Zhou. 2022.  Chain of thought prompting elicits reasoning in large language models.  _ArXiv_ , abs/2201.11903.
  * Wen et al. (2023) Yilin Wen, Zifeng Wang, and Jimeng Sun. 2023.  Mindmap: Knowledge graph prompting sparks graph of thoughts in large language models.  _ArXiv_ , abs/2308.09729.
  * Wu et al. (2019) Peiyun Wu, Xiaowang Zhang, and Zhiyong Feng. 2019.  A survey of question answering over knowledge base.  In _China Conference on Knowledge Graph and Semantic Computing_.
  * Yamada et al. (2020) Ikuya Yamada, Akari Asai, Hiroyuki Shindo, Hideaki Takeda, and Yuji Matsumoto. 2020.  Luke: Deep contextualized entity representations with entity-aware self-attention.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Yang et al. (2023) Lin F. Yang, Hongyang Chen, Zhao Li, Xiao Ding, and Xindong Wu. 2023.  Chatgpt is not enough: Enhancing large language models with knowledge graphs for fact-aware language modeling.  _ArXiv_ , abs/2306.11489.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018.  Hotpotqa: A dataset for diverse, explainable multi-hop question answering.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Yao et al. (2023) Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. 2023.  Tree of thoughts: Deliberate problem solving with large language models.  _ArXiv_ , abs/2305.10601.
  * Yao et al. (2022) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022.  React: Synergizing reasoning and acting in language models.  _ArXiv_ , abs/2210.03629.
  * Yasunaga et al. (2022) Michihiro Yasunaga, Antoine Bosselut, Hongyu Ren, Xikun Zhang, Christopher D. Manning, Percy Liang, and Jure Leskovec. 2022.  Deep bidirectional language-knowledge graph pretraining.  _ArXiv_ , abs/2210.09338.
  * Yasunaga et al. (2021) Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. 2021.  Qa-gnn: Reasoning with language models and knowledge graphs for question answering.  In _North American Chapter of the Association for Computational Linguistics_.
  * Zhang et al. (2023) Haopeng Zhang, Xiao Liu, and Jiawei Zhang. 2023.  Extractive summarization via chatgpt for faithful summary generation.  _ArXiv_ , abs/2304.04193.
  * Zhang et al. (2022) Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christopher D. Manning, and Jure Leskovec. 2022.  Greaselm: Graph reasoning enhanced language models for question answering.  _ArXiv_ , abs/2201.08860.
  * Zhang et al. (2019) Zhengyan Zhang, Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. 2019.  Ernie: Enhanced language representation with informative entities.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Zhu et al. (2017) Yueqin Zhu, Wenwen Zhou, Yang Xu, Ji Liu, and Yongjie Tan. 2017.  Intelligent learning for knowledge graph towards geological data.  _Sci. Program._ , 2017:5072427:1–5072427:13.
  * Zhu et al. (2023a) Yuqi Zhu, Xiaohan Wang, Jing Chen, Shuofei Qiao, Yixin Ou, Yunzhi Yao, Shumin Deng, Huajun Chen, and Ningyu Zhang. 2023a.  Llms for knowledge graph construction and reasoning: Recent capabilities and future opportunities.  _ArXiv_ , abs/2305.13168.
  * Zhu et al. (2023b) Yutao Zhu, Huaying Yuan, Shuting Wang, Jiongnan Liu, Wenhan Liu, Chenlong Deng, Zhicheng Dou, and Ji rong Wen. 2023b.  Large language models for information retrieval: A survey.  _ArXiv_ , abs/2308.07107.
  * Zhu et al. (2022) Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. 2022.  Neural-symbolic models for logical queries on knowledge graphs.  In _International Conference on Machine Learning_ , pages 27454–27478. PMLR.

##  Appendix A MusicBrainz x Wiki

Question Type |  Count |  Description |  Example
---|---|---|---
Bridge |  30 |  Direct multi-hop questions |  The father of Alexander Newley was the vocal arranger for what song?
Bridge Comparison |  7 |  Comparison of values from two multi-hop reasoning chains |  Which venue was opened more recently, the venue for The Eras Tour: Seattle (night 1) or the venue for Fearless Tour: Seattle?
Bridge Aggregation |  42 |  Count of the number of entities satisfying a multi-hop condition (aggregation only over the second hop) |  The place which is the filming location of Michelangelo Buonarroti, has how many songs recorded there?
Bridge Aggregation Comparison |  7 |  Comparison of counts of entities between two different aggregation conditions |  Who composed more songs, Marie Daulne’s mother or Qubilah Shabazz’s godparent?
Qualification Bridge |  10 |  Multi-hop question in which one of the edges needs to be disambiguated with a qualifying statement |  The filming location of Scream Awards that was built in 1929, has what recording engineered there?
Qualification Bridge Aggregation |  9 |  Count of the number of entities satisfying a qualification bridge style condition |  The sibling of Teppo Ruohonen that was born in 1949, has composed how many songs?
Qualification Bridge Aggregation Comparison |  1 |  Comparison of qualification bridge aggregation type questions |  Which of the children of Isabel Preysler that are singers has released more albums?
Double Qualification |  3 |  Multi-hop question in which each hop requires a disambiguating qualification edge |  The child of Guus Belinfante that was a singer, has a vocal feature on what recording by Doe Maar?
Table 3: Composition of questions for Musicbrainz x Wikidata

Additional information on the creation of the MusicBrainz x Wiki dataset.

###  A.1 Creation steps

The dataset was created by annotators in a semi-automatically supported
manner. We developed an automated tool to support the following process:

  * •

Find linking entities that are present in both MusicBrainz and Wikidata of
various types (artist, label, place, event, etc.)

  * •

Find related entities that could be used in a question to perfectly identify
the entities above (e.g., The place owned by the Detroit Tigers $\rightarrow$
Tiger Stadium)

  * •

Find related entities that could be used in a question to ambiguously identify
a linking entity, so that a qualifier could be added to disambiguate the
linking entity.

  * •

Count the number of edges in Wikidata or MusicBrainz for each relationship
type an entity has.

We use these tools to create an initial set of multi-hop questions falling
into specific reasoning categories. We then have human annotators check each
question for sensibility (grammatically correct and can be definitively
understood) and ambiguity (one right answer in the KGs). If possible, the
question is reworded or fixed to not contain ambiguities. We are then left
with a final set of 109 questions.

###  A.2 Composition of Questions

The composition of questions for Musicbrainz x Wiki can be found in table 3.

###  A.3 Annotators

The annotators consisted of approximately 10 research scientists and
engineers, all English speaking and based in the United States.

##  Appendix B Implementation Details

###  B.1 Diversity Oversampling.

One problem with Tree-of-Thoughts is that when there are constrained options
to choose from, the LLM becomes repetitive and fails to produce diverse
outputs Yao et al. (2023). Their solution used a "propose prompt" with
additional instructions for proposing multiple distinct thoughts. However,
this adds significant complexity to the prompt for purposes that are only
tangential to the task being completed. A simpler approach we employ is to
generate diverse actions by oversampling. Specifically, if the branching
factor is $k$, we sample $2*k$ possible actions from the LLM and then extract
the first $k$ unique ones to use. We only employ this for selecting-entities
and selecting-relation as the action choices are limited and diversity is
required. This change does not noticeably affect the computation cost of Tree-
of-Traversals as multiple actions are sampled for the same prompt and the
average prompt input size (100s-1000s of tokens) is generally much larger than
the average generation length for these actions (<20 tokens). Latency remains
similar as multiple actions are sampled in parallel. With this, we
consistently generate diverse options when selecting-entities or selecting-
relation.

###  B.2 Hyperparameters

Tree-of-Traversals does not have a huge number of hyperparamters. Most of the
hyperparameters were chosen analytically, though some were chosen based on
preliminary experiments. We share some information on choosing them.

$\tau$ was chosen analytically in conjunction with the prompt for evaluate on
the done state (Appendix F.5). Chosen to be 0.8 so that Tree-of-Traversals
only stops when it is confident that the answer is supported by the KG.

The temperature was chosen to be 1.0 to promote diversity. If implementing
with other models which can have temperature >1.0, we recommend hyperparameter
tuning or using a sample prompt of each type and analytically choosing the
temperature such that diverse but sensible actions are output.

The branching factor $k=3$ was chosen based on small scale experimentation.
Larger $k$ makes the model spend longer searching, taking longer time and
increasing expenses. Smaller $k$ did not generate as much diversity and
options. It is worth noting that even with $k=3$ and diversity sampling,
sometimes the actual number of unique outputs is less than 3.

The max depth was chosen analytically to be minimal while enabling answering
of most questions. Some questions in QALD-10 and MusicBrainz-x-Wikidata would
require a greater depth to answer.

The maximum expansions cutoff was chosen purely to ensure the model does not
hang on a single question too long. The actual value is somewhat arbitrary and
has minimal impact on accuracy.

###  B.3 KG Interface

We present some additional details of the KG Interface.

The initialize function is a three step process. First a LLM call and prompt
is used to extract named entities. Second, for each extracted entity
candidates are searched for using the KG API. Finally, another LLM call is
used to match the extracted entity to the best candidate.

get_relations and get_edges are implemented exclusively using the respective
KG API. For Wikidata, these are each one or two SPARQL query (forward and
reverse edges). For MusicBrainz, they each require multiple API calls as the
endpoints are separated for different entity types. E.g. there is a separate
endpoint for Artists and Recordings.

##  Appendix C Value Function Profiles

We profile each value model’s value function to assess their characteristics.
Figure 7 shows the individual answer value vs accuracy profiles for each model
on 2WikiMultiHop. All models have a positive correlation between the answer
value and the answer’s accuracy. However, as is to be expected, there are
differences with Llama2-13b having the lowest correlation and Claude-Instant
having the highest correlation.

Figure 7 only look at the value function response for final answer states as
those are the only ones with a directly associated accuracy score. While
accurately evaluating answer states is more important, we also want to see
some useful signal from the values for intermediary states. Figure 8 shows the
average value for nodes on the search path to the answer, separated by whether
the answer scores as correct or not. We would expect actions that ultimately
lead to a correct answer to have higher values than those that lead to
incorrect ones. We clearly see this with the correct distribution being
further right than the incorrect distribution. This is least pronounced for
Llama2-13b which is to be expected. We also note that the distributions shape
is different between the Llama2 models and Claude-Instant.

These results indicate that larger, stronger models, will likely see more
improvement in the value function, and thus, more utility from Tree-of-
Traversals .

((a)) Llama2-13b

((b)) Llama2-70b

((c)) claude-instant

Figure 7: EM-in Accuracy vs value function for all Tree-of-Traversals answers
on 2Wiki. Points are jittered for visibility. Trendline indicates correlation
and p-value.

((a)) Llama2-13b

((b)) Llama2-70b

((c)) claude-instant

Figure 8: The average value function of intermediary steps along the path to
each answer, separated by whether the answer would be scored as correct or
incorrect. For each answer proposed by the model, the scores along the path
are averaged, and the resulting distribution plotted. Data is from
2WikiMultiHop results.

##  Appendix D Prompt Engineering

Some prompt re-engineering was required when switching between models for both
our methods and ReAct. This engineering was limited primarily to formatting of
responses. For example, Llama2 would start responses with "So the next action
should be" while we required the action to start with "THINK", "EXPAND_KG" or
"ANSWER". Instead we incorporated “So the next action should be:” into the
prompt so that the output began with the chosen action. For selecting-entities
we added “You have selected the following entities to expand:”. For selecting-
property we added “I suggest selecting property:”. These issues could also be
solved by changing the parsing of the presented prompts.

##  Appendix E Fallback to Chain-of-Thought ($\rightarrow$CoT)

We fallback to Chain-of-Thought for the ReAct baseline when either no answer
is provided after depth 7 or when one of the following phrases appears in the
answer: ’determine’, ’unable’, ’cannot’, ’unknown’, ’unsure’, or ’not
possible’. While these certainly could appear in intentional answers, we find
that they occur consistently and exclusively in non-answer style responses.

##  Appendix F Prompts

The following pages contains the prompts used in Tree-of-Traversals. The
dynamic components that change based on the query, KG state, action history
are shown in color.

###  F.1 Prompt for default action state

⬇

Original Query:

Who is Bob Dylan’s maternal grandmother?

Knowledge Graph Entities:

Q392: Bob Dylan - American singer-songwriter

Q62519478: Beatrice Stone

Knowledge Graph Edges:

Bob Dylan:

mother:

Beatrice Stone

Previous Actions:

EXPAND KG: I should search for the mother of Bob Dylan

SELECT ENTITIES: Q392

SELECT RELATION: P25 - has mother

You are a superintelligent AI equipped with the ability to search a knowledge
graph for definitive, up-to-date answers. Your task is to interface with the
knowledge graph in order to answer the above query. You will be able to expand
the knowledge graph until you have found the answer. Think in detail before
acting or answering.

Available actions:

’THINK’ - Generate relevant thoughts to solving the problem. This could
include recalling well known facts from memory.

e.g.,

THINK: I should search for the movies directed by...

THINK: I know that Biden is American, therefore...

THINK: I see that John Cena is in both The Independent and Vacation Friends,
therefore...

’EXPAND_KG’ - Search for edges of entities in the knowledge graph using an
external API. This is a useful function for getting to the correct answer.

e.g., EXPAND_KG: I should search for the country of origin of Jonathon Taylor

’ANSWER’ - Generate the final answer once the problem is solved. Just state
the best answer, do not output a full sentence.

e.g.,

ANSWER: No

ANSWER: Harry Potter

ANSWER: [Harry Potter, Ron Weasley, Hermione Granger]

###  F.2 Prompt for selecting-entities action state

⬇

Original Query:

Who is Bob Dylan’s maternal grandmother?

Knowledge Graph Entities:

Q392: Bob Dylan - American singer-songwriter

Q62519478: Beatrice Stone

Knowledge Graph Edges:

Bob Dylan:

mother:

Beatrice Stone

Previous Actions:

EXPAND KG: I should search for the mother of Bob Dylan

SELECT ENTITIES: Q392

SELECT RELATION: P25 - has mother

EXPAND KG: I should search for the mother of Beatrice Stone

Current task

EXPAND_KG takes two parameters. The first is the entity or entity group to get
more information about. Select which entity or entities from the KG to expand.

Provide the QIDs. Options include [Q392, Q62519478]

SELECT ENTITIES:

###  F.3 Prompt for selecting-relation action state

⬇

Original Query:

Who is Bob Dylan’s maternal grandmother?

Knowledge Graph Entities:

Q392: Bob Dylan - American singer-songwriter

Q62519478: Beatrice Stone

Knowledge Graph Edges:

Bob Dylan:

mother:

Beatrice Stone

Previous Actions:

EXPAND KG: I should search for the mother of Bob Dylan

SELECT ENTITIES: Q392

SELECT RELATION: P25 - has mother

EXPAND KG: I should search for the mother of Beatrice Stone

SELECT ENTITIES: Q62519478

Your current task is to select the property (PID) to expand along for the
selected entities.

The selected entities are: [Q62519478]

The options of properties to choose from are:

P31 - has instance of

P21 - has sex of gender

P27 - has country of citizenship

P735 - has given name

...

Select exactly one property (PID e.g., P10) from those listed above

SELECT PROPERTY:

###  F.4 General Prompt for evaluate

⬇

Original Query:

Who is Bob Dylan’s maternal grandmother?

Knowledge Graph Entities:

Q392: Bob Dylan - American singer-songwriter

Q62519478: Beatrice Stone

Knowledge Graph Edges:

Bob Dylan:

mother:

Beatrice Stone

Previous Actions:

EXPAND KG: I should search for the mother of Bob Dylan

SELECT ENTITIES: Q392

SELECT RELATION: P25 - has mother

EXPAND KG: I should search for the mother of Beatrice Stone

SELECT ENTITIES: Q62519478

Your current task is to evaluate the above knowledge graph and action history.

Based on the original query, the current knowledge graph, and the action
history, give the likelihood that the model will correctly answer the
question.

If the most recent action provided information towards the goal and followed
the preceding thought, give a high score.

If the last action was unhelpful, give a low score.

The output should be a number between 0 and 1 with one decimal. Do not output
anything else.

RATING [0.0-1.0]:

###  F.5 Prompt for evaluate on answer (done)

⬇

Original Query:

Who is Bob Dylan’s maternal grandmother?

Knowledge Graph Entities:

Q392: Bob Dylan - American singer-songwriter

Q62519478: Beatrice Stone

Q62519478: Florence Sara Stone

Knowledge Graph Edges:

Bob Dylan:

mother:

Beatrice Stone

Beatrice Stone:

mother:

Florence Sara Stone

Provided answer: The answer is Florence Sara Stone.

Your task is to score the correctness of the provided answer based on the
original query, and the knowledge graph.

Give a pessimistic score from 0.0 to 1.0 on how likely the answer is to be
correct.

0.0 if definitely wrong

0.0 if unable to answer based on the knowledge graph

0.5 if unsure

0.7 for probably correct but not confirmed in knowledge graph

1.0 for definitely correct and confirmed in knowledge graph.

Give reasoning to get to the correct answer. Then provide a score.

e.g.,

Reasoning...

So the score for the provided answer should be...


# Accented Speech Recognition: Benchmarking, Pre-training, and Diverse Data

###### Abstract

Building inclusive speech recognition systems is a crucial step towards
developing technologies that speakers of all language varieties can use.
Therefore, ASR systems must work for everybody independently of the way they
speak. To accomplish this goal, there should be available data sets
representing language varieties, and also an understanding of model
configuration that is the most helpful in achieving robust understanding of
all types of speech. However, there are not enough data sets for accented
speech, and for the ones that are already available, more training approaches
need to be explored to improve the quality of accented speech recognition. In
this paper, we discuss recent progress towards developing more inclusive ASR
systems, namely, the importance of building new data sets representing
linguistic diversity, and exploring novel training approaches to improve
performance for all users. We address recent directions within benchmarking
ASR systems for accented speech, measure the effects of wav2vec 2.0 pre-
training on accented speech recognition, and highlight corpora relevant for
diverse ASR evaluations.

Index Terms: speech recognition, accented speech, pre-training, benchmarking,
wav2vec 2.0, linguistic diversity

##  1 Introduction

The goal of Automatic Speech Recognition (ASR) systems is to transcribe
speech, allowing voices from speakers of differing accents and language
varieties to be understood. Emerging research aims to address this topic by
quantifying the quality of ASR models depending on various parameters (e.g.
gender, accent), measuring bias in ASR models, identifying data sets to
benchmark quality, and improving model robustness for linguistic diversity.
Moreover, diverse speech recognition has increasingly become the focus of
researchers and policy makers. For example, France is considering banning
discrimination against accents111https://www.bbc.com/news/world-
europe-55069048; and some researchers aim to investigate how the bias
affecting certain groups of speakers arises in speech recognition models, and
how to mitigate this bias [1].

Literature reporting on results of various model evaluations shows that ASR
models seem to frequently struggle with accented speech, be it achieving
significantly higher word error rate (WER) for non-standard language varieties
such as African American Vernacular English [2], code-switching [3], or
observing increased WER in certain geographic areas that could be correlated
with regional dialects [4]. In turn, this can make speakers of certain
linguistic varieties feel excluded, and might prompt them to try
“standardizing” and slowing down their speech [5]. This is why measuring bias
and finding ways to improve ASR models given such factors as linguistic
diversity, data unavailability, model architecture, and others is so crucial.
An increasing amount of research focuses on finding model configurations or
approaches that would help to achieve comparable recognition rates for
speakers of different language varieties. Accented speech is indeed a
challenge for ASR, and some research questions the readiness of end-to-end
models for industrial use [3]. ASR has a significant social impact, since its
use cases range across multiple applications, including high stakes areas such
as medical transcription [6].

In our paper, Section 2 presents an overview of the latest methods and
challenges within the scope of ASR benchmarking, focusing on recognizing
linguistically diverse speech. Section 3 provides a brief overview of
approaches to improving ASR systems for accented speech, emphasizing
experiments exploring various types of wav2vec 2.0 pre-training with different
types of data, e.g. spontaneous unsupervised, synthetic, and accented.
Finally, in Section 4, we outline the current state of accented data sets;
discussing those publicly available, and highlighting linguistic aspects
insufficiently represented.

##  2 Benchmarking ASR systems for accents

Understanding demographic information is crucial for benchmarking ASR quality
for diverse groups of speakers, such as gender, age, speakers of sociolects or
regional language varieties, non-native (L2) speakers, people experiencing
speech impairments, and more [7]. Indeed, WER on a corpus of African American
Vernacular English (AAVE) is sometimes observed to be as much as $85$% higher
than WER for a corpus of Standard American English [2]. Researchers also show
that the quality of speech recognition might not be the same for various
genders [8, 9]. A study exploring the link between increased ASR errors and
dialectal features demonstrated that geographic areas with increased WER might
significantly overlap with regions that have certain dialectal features [4].
For example, higher WER scores are observed in the Southern United States,
likely due to certain linguistic features of AAVE and Southern American
English spoken in those regions. This shows that metadata such as sociolect,
gender, age, location, native language, and more are determining for a
multifaceted analysis of diverse ASR quality.

Table 1: Results with wav2vec 2.0 pre-training and noisy student self-training (NST) on accented data (WER in %). Pre-training | NST | CORAAL:ATL | CORAAL:DCB | CORAAL:PRV | GMU Accent
---|---|---|---|---|---
- | - | 17.5 | 16.6 | 24.7 | 8.2
Libri-Light | - | 16.8 | 17.0 | 22.0 | 5.4
YT-U | - | 14.2 | 15.3 | 20.1 | 4.7
YT-U | YT-T | 12.5 | 14.0 | 20.3 | 4.0

It is important to point out that accents, dialects and other language
varieties are complex linguistic phenomena that span multiple dimensions.
Obviously, differences in pronunciations affect the relationship between
acoustic input and written output symbols. But dialects can also vary in
grammar and vocabulary (a common feature e.g. in AAVE or German as spoken
outside of Germany), affecting the distribution over the target sequences
$p(y)$. This poses a challenge to the language modeling capability, whether in
an external LM or one implicitly learned by a transducer model. It is
difficult to accurately isolate linguistic features from other aspects
affecting ASR quality and control for all variables. Even acoustic conditions
such as recording quality and background noise can correlate with geographic
regions, which are in turn correlated to demographic differences between
populations. Not only will the conversation style (spontaneous, prompted phone
calls, scripted media, interviews, etc.) impact recognition accuracy, but also
its content. A benchmark that does not address these issues explicitly is
likely to confound multiple aspects and mask the real ASR accuracy.

Benchmarking ASR quality when it comes to accented speech is challenging,
since multiple parameters should be accounted for: WER for different speech
varieties, number of affected speakers, types and severity of misrecognitions,
speed, and others. Importantly, to understand how an ASR model performs for
various groups of speakers, there should be a representative data set for
every group, and any overall scores should take all individual scores for
speaker groups into account.

One approach to having a deeper insight into ASR quality is to consider a
distribution of per-utterance WER scores for the given corpus, and determine
the median and the last decile P90 of the distribution instead of a single WER
score [10]. Alternatively, it is possible to use a population-weighted
evaluation [7] where the overall WER is defined by all WER scores per speaker
group normalized by the number of speakers. In the latter scenario, the number
of speakers within that group defines the weight of the WER scores for the
corresponding accents.

However, if no transcribed or supervised data for language varieties is
available, an alternative approach to testing ASR system fairness would be to
use available untranscribed samples. In this approach, samples from diverse
speaker groups undergo various acoustic transformations (e.g. noise, frequency
scaling, etc.), and the scorer checks how the resulting recognition is
affected by those transformations [11]. The overall quality is likely to be
lower for a certain accent if these synthetic perturbations significantly
worsen the recognition rates of the corresponding accented set. In this case,
the data does not necessarily need to be supervised, since it is the stability
of the machine transcript that gives insight into the confusion of the model
due to the introduced transformations.

##  3 Improving quality for accented speech

To find ways of improving ASR quality for all speakers, it is important to
study the impact of the training data, training strategies, and model
configurations on the evaluations that use accented test sets. In this
section, we present several experiments exploring effects of wav2vec 2.0 pre-
training using various types of unsupervised data, and discuss their impact on
the recognition of AAVE and non-native (L2) accented speech.

###  3.1 Previous work

While it is possible to achieve higher accuracy with specialized models
trained on various accents separately, it is usually more convenient to train
a single model on multiple accents simultaneously. Such multi-dialect models
tend to be easier to maintain, more robust and require no explicit dialect
selection, which may be inaccurate. One prominent line of research focuses on
understanding which parts of the neural networks process and encode accent
information. For example, research exploring the weights of the hidden layers
of an end-to-end system DeepSpeech2 for accented speech shows that the first
RNN layer contains the most information about accents [12]. It suggests that
this part of an end-to-end model can be adapted to learn abstract
representations that are less accent specific.

Other researchers employ an accent classifier to explicitly annotate
utterances with certain accent-indicating features that are in turn added to
the input of ASR models [13]. Modeling approaches include accent conversion
[14], where a transformation is applied to a non-native utterance to make it
sound as if the speaker had a native accent. For a thorough overview of
research on improving speech recognition for accents, see [15].

Table 2: Results for adding synthetic data to wav2vec 2.0 pre-training (WER in %). Pre-training data | Fine-tuning data | CORAAL:ATL | CORAAL:DCB | CORAAL:PRV
---|---|---|---|---
(unsupervised) | (supervised) |  |  |
1 M hrs YT | 1000h | 12.8 | 16.5 | 23.0
|  $+$100k hrs TTS utterances
---
1000h | 12.1 | 15.8 | 23.4

###  3.2 Improving ASR quality via pre-training

Our experiments show that pre-training of various kinds is able to improve
recognition on accented data. Importantly, it does not harm performance of the
same models on the standard test sets. Previous work suggests that pre-
training is also helpful in settings when little data is available, e.g. for
building ASR systems for Sub-Saharan African languages [16]. In this section,
we consider pre-training of wav2vec 2.0 models [17] using natural and
synthetic unsupervised speech. Our ASR model is a large hybrid autoregressive
transducer (HAT) [18] with Conformer layers [19] in both encoder and
prediction network.

####  3.2.1 Pre-training with unsupervised spontaneous speech

In the first set of experiments we explored the effect of wav2vec 2.0 pre-
training with spontaneous untranscribed speech [17]. The settings we
considered are pre-training using unsupervised Libri-Light [20] and
unsupervised YouTube (YT-U) data [21]. We also compared the results with a
wav2vec 2.0 model without pre-training. Additionally, we explored the effects
of noisy student self-training (NST) [22] using some of the transcribed public
domain YouTube data (YT-T). In all cases, we trained on the entire SpeechStew
data set, totalling roughly 5k hours [23].

We report the results on AAVE data represented by the CORAAL corpus [24], and
non-native (L2) accented English data represented by the GMU Accent data set
[25]. AAVE data was collected in Atlanta, GA (ATL, 11 hours), Washington, DC
(DCB, 34.5 hours) and Princeville, NC (PRV, 31 hours). It is important to
point out that the PRV data exhibits significantly more diverse dialectal
features than sets coming from the other two locations [2]. GMU Accent
consists of 18 hours of speech produced by native speakers of 200 various
languages.

The results in Table 1 show that the model pre-trained on unsupervised YouTube
data together with the NST component gives the overall best results. The WER
on AAVE test sets decreases by 18 to 28% relative. The pre-training is even
more effective on L2 data from the GMU Accent corpus, where the WER drops from
8.2 to 4.0%.

####  3.2.2 Pre-training using synthetic speech

Another way of sourcing more relevant data is to use synthetic speech, e.g.
with encoder pre-training following the tts4pretrain algorithm for various
accents [26]. In this scenario, a text-to-speech (TTS) system is employed to
augment the training data given text. This approach helps to expand the scope
of the available data, enriching it with potentially novel lexical items.

For our experiment, we follow the setup laid out in [26]. We used a wav2vec
2.0 model pre-trained with 1 million hours of untranscribed speech, followed
by TTS to further inject synthetic speech into the pre-training with around
100 million utterances of text, corresponding to roughly 100k hours of
synthesized speech. The TTS system is trained on LibriTTS dataset. After pre-
training, we fine-tune the system on a small subset of supervised data (around
1000 hours).

The results in Table 2 show that synthesizing data using TTS and adding it to
pre-training decreases the WER on two out of three accented test sets from the
CORAAL corpus [24]. Namely, the model that uses 100M additional synthetic
utterances achieves a WER as low as 12.1% on the AAVE speech.

####  3.2.3 Fine-tuning with real accented speech

If real accented data is available, adding it to the training can be expected
to significantly improve the accuracy on accented speech test sets. We find
that simply blending in a small amount of in-domain data during supervised
fine-tuning can greatly reduce the WER on accented speech while maintaining
performance on other test sets.

For this experiment we sampled accented data from various publicly available
sources representing different dialects and language varieties; the accented
dataset corpus is roughly 45 hours long. The non-accented test set that we
used for control is composed of short queries sampled from anonymized traffic
data. We evaluated these test sets using pre-trained wav2vec 2.0 models, and
observed that the overall quality of recognition improves when accented data
is added to the training. The results in Table 3 show that while the WER on
accented data decreases by 30% (from 28.8% to 20.4%), it remains unchanged on
the short queries test set.

Table 3: Fine-tuning with real accented data (WER in %). Real accented data | Accented | Short queries
---|---|---
- | 28.8 | 6.7
+ | 20.4 | 6.7

###  3.3 Further sources of accented speech

As we showed in the previous subsection, adding various types of unsupervised
data to the pre-training improves the recognition of accented speech. This
suggests that further experiments for pre-training are promising, e.g. mixing
in data from non-target languages in order to achieve better recognition for
speakers with non-native accents.

Alternatively, using voice conversion (VC) to produce more training data can
be helpful as well. The idea of a VC model [27] is to perform an on-the-fly
conversion from any type of speech to accented speech in the audio domain.
Down the line, ASR models can be jointly trained with this accented data
generated by the VC model, potentially augmented with other components, such
as consistency loss [28]. Such on-the-fly VC allows us to augment the training
data for more accent robust ASR models. VC is capable of manipulating phonetic
and phonological aspects of the accent, and even phonotactic ones depending on
the type of VC model. Overall, VC improves the quality of recognition for
accented speech without requiring any additional metadata or human
annotations. However, parameters such as lexical choice and syntactic
differences cannot be addressed by VC directly without adding a TTS generator.
Furthermore, recent studies suggest that VC is particularly helpful for
improving ASR in very low-resource settings [29].

One could use the VC model in order to increase speaker diversity of the
training data, allowing various accents to be added to already existing data
augmentation.

##  4 Data sets representing linguistic diversity

Annotating speech utterances with metadata becomes more and more common for
many data sets. For example, gender annotation is provided for LibriSpeech
[30] speakers, and both gender and age buckets are available for Mozilla
Common Voice [31] utterances, one of the biggest open-source speech data sets.
In this section, we describe multiple data sets and approaches that can be
used for diverse model evaluations.

###  4.1 Regional language data sets

TIMIT (LDC93S1) represents $7$ dialects of American English, and there are two
versions of the CALLFRIEND corpus of phone conversations: one for Standard
American English (LDC96S46) and one for Southern American English (LDC96S47).
As for dialects spoken in the UK and Ireland, they are represented within an
OpenSLR data set (SLR83) [32]. Regional corpora are available for other
languages as well, e.g. Swiss German [33], Galician Spanish [34] and Arabic
dialects [35], along with several multilingual corpora [36]. Additionally,
public challenges such as The MGB Challenge target evaluations of various ASR
topics including dialect identification.

Still there are not many data sets that represent speech on a more detailed
level of geographical granularity, e.g. in various metro areas or regions for
a given language. However, the practice of utterance annotation with at least
country-level metadata is becoming more common. A recent study suggests ways
to create such open-source data sets using public domain videos [37], showing
that the construction of regional corpora can be partially automated. Other
research focuses on machine learning methods to identify dialectal utterances,
using the example of local accents spoken in Pakistan [27].

###  4.2 L2 accented sets

A number of corpora represent accented English speech, including GMU Accent
[25], IDEA [38], and ALLSSTAR [39]. In GMU Accent corpus, for example, as many
as $200$ native languages of the speakers are represented. Data is available
in other languages as well: for example, West Point developed corpora
representing both native and non-native speakers for Spanish [40], Russian
[41], and Arabic [42]. A European consortium published IFCASL [43], a corpus
of French and German native and non-native speech.

###  4.3 Sociolectal data sets

While it is often possible to find a representation of regional and accented
speech in widely spoken languages, less data is available for sociolects (e.g.
Chicano English or Cockney English). African American Vernacular English
(AAVE), for example, is spoken by approximately 40 million speakers, and is
represented within the CORAAL [24] and Voices of California corpora. CORAAL
also showcases regional variation within AAVE, comparing data from six metro
areas. However, more work is needed to adequately represent other sociolects.

###  4.4 Sets representing speech impairments

Another category of data sets that we would like to highlight exemplifies
various types of speech disorders. Speech recognition for impaired speakers is
a different problem than improving accuracy for various accents. However, this
group of speakers might benefit from more available data and training
approaches promoting accent robustness as well. For example, the Euphonia
project involved collecting one million utterances representing different
types and severities of speech impairments [44]. More of such data is
available in the Whitaker corpus [45], the Dysarthric Speech Database for
Universal Access Research [46] and EasyCall [47]. A Spanish corpus published
in [48] contains recordings of children with speech impairments in particular.

A growing number of researchers are working towards creating data sets
representing different types of factors affecting ASR quality, e.g. accented
speech, noise, various acoustic environments and other aspects. For example,
ASR4REAL [10] is a combination of benchmarks assembled at FAIR that is
intended to represent various accents and real-life conditions.

##  5 Discussion

To understand how well ASR models serve people speaking different dialects and
accents, we need data representing various language varieties, and a
methodology of how to approach the evaluation. In this paper, we discuss
several experiments aiming to improve ASR quality for accented speakers, along
with some recent results in the area of ASR benchmarking.

Indeed, a crucial research direction is to improve ASR quality for accented
speakers. This goal is impossible to achieve without representative test sets
and established benchmarks, since improving recognition for widely used
corpora representing mainstream types of speech does not guarantee improving
ASR for other groups of accented speakers. And indeed, without a proper way to
measure speech recognition quality for various accents there is no way to know
how certain configurations affect different groups of speakers and types of
language diversity. To help researchers with the challenge of obtaining
representative data samples for various regions, non-native accents,
sociolects, and speech disorders, we provided a quick survey of currently
available corpora suitable for evaluating ASR quality on such speech
varieties.

Previous works suggested accent conversion or employing additional accent
classifiers to create more in-domain data. In this paper, we showed how
various types of wav2vec 2.0 pre-training and fine-tuning affect the
recognition accuracy on accented test sets representing AAVE and non-native
speakers. Namely, we explored the effects of pre-training using unsupervised
spontaneous and synthetic speech, showing that it indeed helps to achieve
higher recognition quality for accents without increasing the WER on the other
sets.

To conclude, we would like to highlight the importance of collaboration in
this emerging field of inclusive ASR technologies. Researchers and developers
can get insights into challenging areas and language aspects from linguists
and dialectologists, who, in turn, could help to analyze the patterns of
recognition issues, and address the issues of missing data for some groups of
speakers. Crowdsourcing and community involvement allows for scaling data
collection projects, and extensive metadata annotation enables understanding
of the overall recognition quality with respect to the factors of language
variation. Finally, it is crucially important for the researchers to share
their results and findings, drawing greater attention to this area.

##  6 Acknowledgments

We are grateful for the resources provided by Google, and for our
collaborators from Speech and Brain teams, especially Françoise Beaufays,
James Flynn, Bo Li, Pedro J. Moreno, Daniel Park, Sandy Ritchie, Pierric Sans,
Benyah Shaparenko, and Yu Zhang. For critical work on data sets, our thanks go
to Landis Baker, Jonathan Endale, Mandy Jordan, Prescott Nicoll, and Travis
Trekell.

## References

  * [1] N. Markl and S. J. McNulty, “Language technology practitioners as language managers: arbitrating data bias and predictive bias in ASR,” in _LREC 2022 (submitted)_ , 2022.
  * [2] A. Koenecke, A. Nam, E. Lake, J. Nudell, M. Quartey, Z. Mengesha, C. Toups, J. R. Rickford, D. Jurafsky, and S. Goel, “Racial disparities in automated speech recognition,” _Proc. of the National Academy of Sciences_ , vol. 117, no. 14, pp. 7684–7689, 2020.
  * [3] V. Vielzeuf and G. Antipov, “Are E2E ASR models ready for an industrial usage?” 2021.
  * [4] A. Aksënova, A. Bruguier, A. Ritchart-Scott, and U. Mendlovic, “Algorithmic exploration of American English dialects,” in _Proc. IEEE ICASSP_ , Barcelona, Spain, 2020.
  * [5] C. Heldreth, M. Lahav, Z. Mengesha, J. Sublewski, and E. Tuennerman, ““I don’t think these devices are very culturally sensitive.” - The impact of errors on African Americans in automated speech recognition,” _Frontiers in AI_ , vol. 26, 2021.
  * [6] A. Mani, S. Palaskar, and S. Konam, “Towards understanding ASR error correction for medical conversations,” in _Proc. ACL Workshop on NLP for Medical Conversations_ , 2020, pp. 7–11.
  * [7] A. Aksënova, D. van Esch, J. Flynn, and P. Golik, “How might we create better benchmarks for speech recognition?” in _Proc. ACL Workshop on Benchmarking: Past, Present and Future_ , 2021, pp. 22–34.
  * [8] H. Liao, G. Pundak, O. Siohan, M. Carroll, N. Coccaro, Q.-M. Jiang, T. N. Sainath, A. Senior, F. Beaufays, and M. Bacchiani, “Large vocabulary automatic speech recognition for children,” in _Proc. Interspeech_ , Dresden, Germany, 2015, pp. 1611–1615.
  * [9] R. Tatman, “Gender and dialect bias in YouTube’s automatic captions,” in _Proc. ACL Workshop on Ethics in Natural Language Processing_ , Valencia, Spain, 2017, pp. 53–59.
  * [10] M. Riviere, J. Copet, and G. Synnaeve, “ASR4REAL: An extended benchmark for speech models,” in _Proc. IEEE ICASSP (submitted)_ , 2022.
  * [11] S. S. Rajan, S. Udeshi, and S. Chattopadhyay, “Aequevox: Automated fairness testing of speech recognition systems,” in _Int. Conf. on Fundamental Approaches to Software Engineering_ , 2022.
  * [12] A. Prasad and P. Jyothi, “How accents confound: Probing for accent information in end-to-end speech recognition systems,” in _Proc. of the 58th Annual ACL Meeting_ , 2020, pp. 3739–3753.
  * [13] A. Jain, M. Upreti, and P. Jyothi, “Improved accented speech recognition using accent embeddings and multi-task learning,” in _Proc. Interspeech_ , 2018, pp. 2454–2458.
  * [14] G. Zhao, S. Sonsaat, J. Levis, E. Chukharev-Hudilainen, and R. Gutierrez-Osuna, “Accent conversion using phonetic posteriorgrams,” in _Proc. IEEE ICASSP_ , 2018, pp. 5314–5318.
  * [15] A. Hinsvark, N. Delworth, M. D. Rio, Q. McNamara, J. Dong, R. Westerman, M. Huang, J. Palakapilly, J. Drexler, I. Pirkin, N. Bhandari, and M. Jette, “Accented speech recognition: A survey,” _arXiv:2104.10747_ , 2021.
  * [16] S. Ritchie, Y.-C. Cheng, M. Chen, R. Mathews, D. van Esch, and B. Li, “Large vocabulary speech recognition for Sub-Saharan African languages,” in _Proc. Interspeech (submitted)_ , 2022.
  * [17] A. Baevski, H. Zhou, A. Mohamed, and M. Auli, “wav2vec 2.0: A framework for self-supervised learning of speech representations,” in _Proc. NeurIPS_ , vol. 33, 2020, pp. 12 449–12 460.
  * [18] E. Variani, D. Rybach, C. Allauzen, and M. Riley, “Hybrid autoregressive transducer (HAT),” in _Proc. IEEE ICASSP_ , 2020, pp. 6139–6143.
  * [19] A. Gulati, J. Qin, C.-C. Chiu, N. Parmar, Y. Zhang, J. Yu, W. Han, S. Wang, Z. Zhang, Y. Wu _et al._ , “Conformer: Convolution-augmented transformer for speech recognition,” in _Proc. Interspeech_ , 2020.
  * [20] J. Kahn, M. Riviere, W. Zheng, E. Kharitonov, Q. Xu, P. Mazare, J. Karadayi, V. Liptchinsky, R. Collobert, C. Fuegen, T. Likhomanenko, G. Synnaeve, A. Joulin, A. Mohamed, and E. Dupoux, “Libri-light: A benchmark for ASR with limited or no supervision,” in _Proc. IEEE ICASSP_ , 2020.
  * [21] Y. Zhang, D. S. Park, W. Han, J. Qin, A. Gulati, J. Shor, A. Jansen, Y. Xu, Y. Huang, S. Wang _et al._ , “BigSSL: Exploring the frontier of large-scale semi-supervised learning for automatic speech recognition,” _arXiv:2109.13226_ , 2021.
  * [22] D. S. Park, Y. Zhang, Y. Jia, W. Han, C.-C. Chiu, B. Li, Y. Wu, and Q. V. Le, “Improved noisy student training for automatic speech recognition,” in _Proc. Interspeech_ , 2020, pp. 2817–2821.
  * [23] W. Chan, D. Park, C. Lee, Y. Zhang, Q. Le, and M. Norouzi, “SpeechStew: Simply mix all available speech recognition data to train one large neural network,” in _Proc. MLSLP_ , 2021.
  * [24] T. Kendall and C. Farrington, “The corpus of regional African American language. version 2021.07.” 2021, Eugene, OR.
  * [25] S. Weinberger, “Speech accent archive,” 2015, GMU.
  * [26] Z. Chen, Y. Zhang, A. Rosenberg, B. Ramabhadran, G. Wang, and P. Moreno, “Injecting text in self-supervised speech pretraining,” in _Proc. IEEE ASRU_ , 2021, pp. 251–258.
  * [27] S. H. Mohammadi and A. Kain, “An overview of voice conversion systems,” _Speech Communication_ , vol. 88, pp. 65–82, 2017.
  * [28] G. Wang, A. Rosenberg, Z. Chen, Y. Zhang, B. Ramabhadran, Y. Wu, and P. Moreno, “Improving speech recognition using consistent predictions on synthesized speech,” in _Proc. IEEE ICASSP_ , 2020, pp. 7029–7033.
  * [29] M. Baas and H. Kamper, “Voice conversion can improve ASR in very low-resource settings,” in _Proc. IEEE ICASSP (submitted)_ , 2022.
  * [30] V. Panayotov, G. Chen, D. Povey, and S. Khudanpur, “Librispeech: An ASR corpus based on public domain audio books,” in _Proc. IEEE ICASSP_ , 2015, pp. 5206–5210.
  * [31] R. Ardila, M. Branson, K. Davis, M. Kohler, J. Meyer, M. Henretty, R. Morais, L. Saunders, F. Tyers, and G. Weber, “Common Voice: A massively-multilingual speech corpus,” in _Proc. LREC_ , 2020, pp. 4218–4222.
  * [32] I. Demirsahin, O. Kjartansson, A. Gutkin, and C. Rivera, “Open-source multi-speaker corpora of the English accents in the British Isles,” in _Proc. LREC_. ELRA, 2020, pp. 6532–6541.
  * [33] T. Samardžić, Y. Scherrer, and E. Glaser, “ArchiMob - a corpus of spoken Swiss German,” in _Proc. LREC_ , May 2016, pp. 4061–4066.
  * [34] M. Barcala, E. Domínguez, A. Fernández, R. Rivas, M. P. Santalla, V. Vázquez, and R. Villapol, “El corpus ESLORA de Español oral: diseño, desarrollo y explotación,” _CHIMERA: Revista de Corpus de Lenguas Romances y Estudios Lingüísticos_ , vol. 5, no. 2, pp. 217–237, 2018\.
  * [35] K. Lounnas, M. Abbas, and M. Lichouri, “Building a speech corpus based on Arabic podcasts for language and dialect identification,” in _Proc. ICNLSP_. ACL, 2019, pp. 54–58.
  * [36] D. Imseng, H. Bourlard, H. Caesar, P. N. Garner, G. Lecorvé, and A. Nanchen, “MediaParl: Bilingual mixed language accented speech database,” Proceedings of the 2012 IEEE Workshop on Spoken Language Technology, 2012.
  * [37] S. Coats, “A Corpus of regional American language from YouTube,” in _Proceedings DHNB_ , 2019, pp. 79–91.
  * [38] “IDEA. International dialects of English archive.”
  * [39] A. Bradlow, “ALLSSTAR: Archive of L1 and L2 scripted and spontaneous transcripts and recordings.”
  * [40] J. Morgan, “West Point Heroico Spanish Speech LDC2006S37,” 2006, Philadelphia: Linguistic Data Consortium.
  * [41] S. A. LaRocca and C. Tomei, “West Point Russian Speech LDC2003S05,” 2003, Philadelphia: Linguistic Data Consortium.
  * [42] S. A. LaRocca and R. Chouairi, “West Point Arabic Speech LDC2002S02,” 2002, Philadelphia: Linguistic Data Consortium.
  * [43] J. Trouvain, A. Bonneau, V. Colotte, C. Fauth, D. Fohr, D. Jouvet, J. Jügler, Y. Laprie, O. Mella, B. Möbius, and F. Zimmerer, “The IFCASL corpus of French and German non-native and native read speech,” in _Proc. LREC_ , 2016, pp. 1333–1338.
  * [44] R. L. MacDonald, P.-P. Jiang, J. Cattiau, R. Heywood, R. Cave, K. Seaver, M. A. Ladewig, J. Tobin, M. P. Brenner, P. C. Nelson, J. R. Green, and K. Tomanek, “Disordered speech data collection: Lessons learned at 1 million utterances from Project Euphonia,” in _Proc. Interspeech_ , 2021, pp. 4833–4837.
  * [45] J. Deller, M. Liu, L. Ferrier, and P. Robichaud, “The Whitaker database of dysarthric (cerebral palsy) speech,” _The Journal of the Acoustical Society of America_ , vol. 93 (6), p. 3516–3518, 1993.
  * [46] H. Kim, M. Hasegawa-Johnson, A. Perlman, J. Gunderson, T. S. Huang, K. Watkin, and S. Frame, “Dysarthric speech database for universal access research.” in _Proc. Interspeech_ , 2008, pp. 1741–1744.
  * [47] R. Turrisi, A. Braccia, M. Emanuele, S. Giulietti, M. Pugliatti, M. Sensi, L. Fadiga, and L. Badino, “EasyCall corpus: a dysarthric speech dataset,” in _Proc. Interspeech_ , 2021, pp. 41–45.
  * [48] O. Saz, W. Rodríguez, E. Lleida, and C. Vaquero, “A novel corpus of children’s disordered speech,” in _WOCCI_ , 2008.