# Generative Knowledge Selection for Knowledge-Grounded Dialogues

Weiwei Sun, Pengjie Ren, Zhaochun Ren
Shandong University, Qingdao, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding
author.

###### Abstract

Knowledge selection is the key in knowledge-grounded dialogues (KGD), which
aims to select an appropriate knowledge snippet to be used in the utterance
based on dialogue history. Previous studies mainly employ the classification
approach to classify each candidate snippet as “relevant” or “irrelevant”
independently. However, such approaches neglect the interactions between
snippets, leading to difficulties in inferring the meaning of snippets.
Moreover, they lack modeling of the discourse structure of dialogue-knowledge
interactions. We propose a simple yet effective generative approach for
knowledge selection, called GenKS. GenKS learns to select snippets by
generating their identifiers with a sequence-to-sequence model. GenKS
therefore captures intra-knowledge interaction inherently through attention
mechanisms. Meanwhile, we devise a _hyperlink_ mechanism to model the
dialogue-knowledge interactions explicitly. We conduct experiments on three
benchmark datasets, and verify GenKS achieves the best results on both
knowledge selection and response generation.

##  1 Introduction

To improve the informativeness in open-domain dialogue agents (Freitas et al.,
2020), knowledge-grounded dialogues (KGD) are proposed to leverage external
structured (Liu et al., 2019) and unstructured (Dinan et al., 2019) knowledge
to dialogue responses. In KGD, it is pivotal to embed factual and
conversationally appropriate knowledge in responses. Two classes of approaches
are considered to embed knowledge: _end-to-end_ and _pipeline_. End-to-end
models, such as FiD (Izacard and Grave, 2021), process the document and
generate the response in one shot. However, they tend to misuse knowledge
(Adolphs et al., 2021). Pipeline models address this problem by explicitly
identifying a specific knowledge snippet to be used in the response (Adolphs
et al., 2021). Typically, pipeline KGD approaches have two sub-steps, i.e.,
knowledge selection and response generation (Dinan et al., 2019; Kim et al.,
2020): The former aims to select knowledge snippets from passages, and the
latter generates responses based on them. Knowledge selection plays a vital
role in KGD as it directly determines the content of the response (Lian et
al., 2019; Meng et al., 2020). In this paper, we focus on selecting knowledge
snippets for dialogue to enhance pipeline KGD models.

Figure 1: An example of knowledge-grounded dialogues. The dialogue agent
selects a knowledge snippet (i.e., <7>) from passages and generates a response
based on it. Intra-knowledge interactions and dialogue-knowledge interactions
are denoted by ➀ and ➁, respectively.

The _Classification_ paradigm dominates knowledge selection studies. In this
paradigm, each snippet is independently classified as “relevant” or
“irrelevant” (Dinan et al., 2019; Zhao et al., 2020b). However, these
approaches ignore _knowledge interactions_ , which refer to flows of
information within the knowledge or between knowledge and dialogues. As shown
in Figure 1, we identify two types of knowledge interactions in KGD:

Intra-knowledge interaction

Intra-knowledge interaction refers to the interactions between snippets. It is
worth noting that the meaning of a knowledge snippet is context-dependent and
can be ambiguous when taken individually. For example, the <8> snippet in
Figure 1 _“This work led to their”_ has a referential element _their_ , and is
difficult to identify its meaning without knowing the remaining context of the
sentence. However, with the existence of the remaining context, we can quickly
infer that it refers to _Lamarr and George Antheil_. _This problem challenges
existing methods when selecting knowledge on new topics._

Dialogue-Knowledge interaction

Previous works also neglect interactions between dialogue and knowledge. There
is a discourse structure and smooth transition of involved knowledge in multi-
turn dialogue. For example, _Lamarr_ ’s profession mentioned in the dialogue
in Figure 1 is demonstrated in a parallel and multi-perspective manner, while
some other cases follow a shallow-to-deep structure in dialogue.

Some recent efforts attempt to fix these problems within the classification
paradigm; for example, Li et al. (2022) build a semantic graph for passages to
capture intra-knowledge interaction, Kim et al. (2020) propose sequential
knowledge selection to model the dialogue-knowledge interaction as latent
variables. However, they are complicated, lack deep semantic interactions, and
are challenging to model the two types of knowledge interaction
simultaneously.

In this work, we propose GenKS (Generative Knowledge Selection), a simple yet
effective _generative_ model that addresses these challenges. GenKS first
assigns an identifier to each snippet, feeds all the snippets into the model
simultaneously, and then selects snippets by generating their identifiers with
a sequence-to-sequence Transformer model (e.g., BART Lewis et al. (2020a)).
Compared with KGD methods with the _classification_ paradigm, GenKS captures
interactions between knowledge snippets through the _self-attention_ mechanism
in Transformer (Vaswani et al., 2017). Therefore, GenKS can obviate the
ambiguity in snippets with the existence of the rest context and improve the
understanding of knowledge. Moreover, we propose a _hyperlink_ method to
capture the dialogue-knowledge interactions explicitly and effectively.
Finally, we propose to joint knowledge selection and response generation
within one generative model.

We evaluate our proposed method on three public KGD datasets: Wizard of
Wikipedia (Dinan et al., 2019), Holl-E (Moghe et al., 2018), and CMU_DoG (Zhou
et al., 2018). The experimental results show that GenKS significantly improves
the accuracy of knowledge selection as well as the quality of response
generation, by establishing new state-of-the-art on KGD benchmarks.
Improvements are particularly significant on unseen topics, outperforming the
BART classification model by up to 8.1% absolute. GenKS also achieves the best
results as the number of dialogue turns increased, with an average of 10%
improvements over the BART classification model in the last three turns. We
also compare our model with recent SOTA end-to-end methods (Shuster et al.,
2021), and find our model can generate responses with fewer hallucinations
while having better controllability and interpretability. The effectiveness of
the proposed method is also validated through human evaluation and ablative
experiments.

Our contributions are summarized as follows:  (1) We propose GenKS, which is
the first attempt at generative knowledge selection in KGD.  (2) GenKScaptures
intra-knowledge and dialogue-knowledge interactions simultaneously.  (3) We
propose a hyperlink method to enhance the interactions between dialogue and
knowledge.  (4) Experiments verify that GenKS establishes a new state-of-the-
art on KGD111The code is available at: https://github.com/sunnweiwei/GenKS.

##  2 Related work

#### Knowledge-grounded dialogues

With the advances in large-scale language models, dialogue agents can now
generate high-quality responses using parametric knowledge (Thoppilan et al.,
2022; Freitas et al., 2020; Bao et al., 2021). However, hallucination remains
a challenge, which means that the language model tends to generate plausible-
looking statements that are factually incorrect (Shuster et al., 2021). To
address this problem, knowledge-augmented approaches are applied in dialogue
generation (Lewis et al., 2020b). In knowledge-grounded dialogues (KGD), the
dialogue models first select a knowledge snippet from passages and then
generate the responses (Liu et al., 2018; Dinan et al., 2019).

#### Knowledge selection

As the critical step in KGD, knowledge selection has received many studies.
The exiting methods mainly employ _classification_ model with dual-encoder
(Dinan et al., 2019; Kim et al., 2020) or cross-encoder (Zhao et al., 2020b)
architecture. However, the classification paradigm is unable to capture the
knowledge interaction in KGD (Kim et al., 2020; Li et al., 2022). To address
this problem, Li et al. (2022) propose a graph-based method to capture the
relationship between candidate snippets, Zhan et al. (2021a) and Wu et al.
(2021) employ machine reading comprehension model to extract span from long
document. Sequential knowledge selection has also been proposed to capture the
topic transition in conversations (Kim et al., 2020; Zhan et al., 2021b; Zheng
et al., 2020; Meng et al., 2020; Yang et al., 2022). Despite their
effectiveness, the existing methods have two drawbacks: (1) they use compact
vectors to represent dialogue and knowledge and thus lack deep semantic
interactions; (2) they are complicated and challenging to capture intra-
knowledge and dialogue-knowledge interactions simultaneously. We address these
drawbacks by shifting the modeling paradigm of knowledge selection to
identifier generation (Sun et al., 2022), and propose GenKS to capture the two
types of interaction simultaneously using Transformer (Vaswani et al., 2017).

#### Generative knowledge selection

A generative paradigm for knowledge selection is not foreign to the NLP
community; for example, sequence-to-sequence models have been applied on
entity retrieval (Cao et al., 2021), document ranking (Nogueira et al., 2020;
Tay et al., 2022), multi-evidence retrieval (Min et al., 2021; Yavuz et al.,
2022), and etc. Our proposed model GenKS differs from existing methods in the
following ways: (1) we are the first to explore generative knowledge selection
in KGD; (2) we consider the effectiveness of intra-knowledge interaction; (3)
we design hyperlinks to capture the interaction between knowledge and
dialogue.

##  3 GenKS

Figure 2: Overview of GenKS. The dialogue context and the knowledge are
serialized and fed into a seq-to-seq model, BART. The outputs are the
identifier of the selected snippet (i.e., <k5>) and the response.

We provide an overview of GenKS in Figure 2. As shown in Figure 2, the
dialogue data is first serialized into a sequence. Then a sequence-to-sequence
model (i.e., BART) is employed to select knowledge and get the response by
generating the target sequence autoregressively. In this section, we first
formulate the task in Section 3.1. Then, we detail the serialization (Section
3.2) and optimization (Section 3.3) methods.

###  3.1 Problem formulation

Suppose that we have a case of knowledge-grounded dialogues
$(C,\mathcal{K},r)$, where $C=(c_{1},...,c_{|C|})$ is a dialogue context that
contains $|C|$ utterances, $r$ is the response to $C$,
$\mathcal{K}=(K_{1},...,K_{|\mathcal{K}|})$ denotes $|\mathcal{K}|$ passages
that are relevant to $C$; for each $i$, $K_{i}=(k_{i,1},...,k_{i,|K_{i}|})$
denotes a passage that contains $|K_{i}|$ snippets. We define
$m=\sum_{i=1}^{|\mathcal{K}|}|K_{i}|$ as the total number of snippets in $K$.
A knowledge-grounded dialogue agent is decoupled into two modules: a knowledge
selection module $P(k|C,\mathcal{K})$ that selects a snippet from
$\mathcal{K}$; a response generation module $P(r|C,\mathcal{K},k_{s})$ where
$k_{s}$ is the selected snippet from knowledge selection module.

###  3.2 Serialization

We formulate the knowledge selection task as a procedure of sequence
generation. As shown in Figure 2, the dialogue context $C$ and knowledge
candidates $K$ are mapped into a sequence and then fed into a sequence-to-
sequence model. The model’s output is converted back to the selected knowledge
$k$ or the response $r$.

Specifically, we first assign an identifier to each snippet in $\mathcal{K}$,
sequentially starting from <k1> to <km>. Then we convert passages
$\mathcal{K}$ into a sequence using a template that packages snippets with the
corresponding identifiers and concatenates them in order; see the green block
in Figure 2. Similarly, the dialogue context $C$ is serialized by adding task
prompts, i.e., task description and speaker name, as shown in the blue block
in Figure 2.

In multi-turn dialogues, the knowledge appearing in the dialogue history
prompts the discourse structure of knowledge transition and knowledge
expression. Hence we propose a _hyperlink_ method to capture the dialogue-
knowledge interaction explicitly. We provide an example of the hyperlink
method in Figure 2. We see that the first utterance of User1 refers to a
snippet (whose identifier is <k2>) in the passage “Skateboarding”. We thus add
a hyperlink to the utterance. The hyperlink includes the identifier and the
title of the snippet, i.e., annotating [Skateboarding]<k2> at the beginning of
this utterance (as shown in the red block in Figure 2). Finally, we splice the
passages and dialogue context sequences as input for a Transformer model
(i.e., BART). Therefore, the model can capture the intra-knowledge and
dialogue-knowledge interactions through a _self-attention_ mechanism (Vaswani
et al., 2017).

###  3.3 Optimization

The knowledge selection model is optimized by the cross-entropy loss:
$\mathcal{L}=-\log P(k_{true}|C,\mathcal{K})$ , where $k_{true}$ denotes the
label knowledge. Since $k_{true}$ needs to be labeled manually and is not
available in some scenarios (Zhou et al., 2018), we construct pseudo-labels
for model training following Zhao et al. (2020b) in cases the knowledge label
is absent. In particular, we calculate the F1 score (Dinan et al., 2019)
between each knowledge snippet and the response. We use the snippet with the
highest score as the pseudo label. Such a method is based on the intuition
that human responses provide hints regarding the relevance of the snippets
(Zhao et al., 2020b; Li et al., 2020).

Since both knowledge selection and response generation are modeled with the
_generative_ paradigm, we unify the two modules with one joint generative
model. In this joint model, the knowledge selection and the response
generation are optimized jointly, with shared parameters. To this end, we
splice the knowledge identifier $k_{true}$ and response $r$ into one sequence
(as shown in Figure 2). Then, we optimize the sequence-to-sequence model using
cross-entropy loss on all the tokens of the target sequence. In inference, the
model generates knowledge identifier $k_{s}$ and responses $r$ in an
autoregressive fashion. We note that the end-to-end model allows the two tasks
to be mutually enhanced and improves the model’s efficiency.

##  4 Experimental setup

###  4.1 Datasets

We conduct experiments on Wizard of Wikipedia (WoW) (Dinan et al., 2019),
Holl-E (Moghe et al., 2018), and CMU_DoG (Zhou et al., 2018). The statistical
details on these three datasets are shown in Table 6 in the appendix.

  * •

WoW is an open-domain KGD dataset using Wikipedia passage as background
knowledge. The test set of Wizard is split into seen and unseen versions,
where the unseen test set contains 58 new topics not discussed in the training
data.

  * •

Holl-E focuses on the movie domain. The background knowledge consists of
plots, comments, and movie reviews collected from different websites. Holl-E
has two versions of the test set: single test and multi-reference test. In the
multi-reference test, there are multiple human-annotated ground-truth
knowledge and corresponding responses for each instance.

  * •

CMU_DoG focuses on the domain of movies. The workers discuss a movie in depth
given the background knowledge(e.g., introduction, plots, and key scenes).

###  4.2 Baselines

We compare GenKS with baselines of two categories: (i) _End-to-end methods_
that generate response directly without explicit knowledge selection, and (ii)
_Pipeline methods_ that explicitly select knowledge snippet to be used in
response.

The end-to-end methods we consider are:

  * •

BART (Lewis et al., 2020a) that generates responses without access to the
external passage and uses knowledge inside model parameters instead.

  * •

BART FID (Izacard and Grave, 2021) concatenates and encodes each candidate
knowledge with dialogue separately and fuses all the encoded representation in
the decoder to generate the response.

  * •

BART RAG-DPR is a baseline adopted by Adolphs et al. (2021), which uses DPR-
retrieved passages and produces response usning RAG.

  * •

BART FiD-RAG DPR-Poly (Shuster et al., 2021) uses DPR-Poly to retrieve passage
and uses FiD-RAG to generate the response.

Regarding the pipeline baselines, according to their knowledge selection
modeling paradigm, we sub-categorize pipeline baselines into four groups:
(1) The _Classification methods_ includes:

  * •

SKT (Kim et al., 2020) proposes sequential knowledge selection.

  * •

DiffKS (Zheng et al., 2020) captures the knowledge differences between
adjacent turns.

  * •

DukeNet (Meng et al., 2020) models the knowledge shift and tracking processes
with a dual learning scheme.

  * •

KnowledGPT (Zhao et al., 2020b) exploits pre-trained language models in KGD.

  * •

MIKe (Meng et al., 2021) distinguish user-initiative and system-initiative.

  * •

K-Mine (Lotfi et al., 2021) proposes a score-and-aggregate module.

  * •

TAKE (Yang et al., 2022) propose a topic-shift aware network.

(2) The _MRC methods_ includes:

  * •

CoLV (Zhan et al., 2021a) proposes a collaborative latent variable model.

  * •

DIALKI (Wu et al., 2021) proposes a MRC-based model to extract span from
passage.

(3) The _Graph-based methods_ includes:

  * •

Graph (Li et al., 2022) builds a semantic graph upon candidate documents and
employs a GNN model. And

(4) The _Knowledge generation methods_ includes:

  * •

K2R (Adolphs et al., 2021) uses the RAG-based model to generate knowledge text
and then generates dialogue response based on it.

###  4.3 Evaluation metrics

In WoW, we choose perplexity (PPL) of the ground-truth responses, unigram
F1222https://github.com/facebookresearch/ParlAI (Dinan et al., 2019),
Knowledge-F1 (Shuster et al., 2021), and BLEU-4 (Papineni et al., 2002) score
as metrics. In Holl-E, we additionally use ROUGE-1, and ROUGE-2 following Meng
et al. (2020). In CMU_DoG, we additionally use embedding-based metrics
includes Average, Extreme, and Greedy following Zhao et al. (2020b).

In addition, we randomly sample 100 examples from the WoW test seen and WoW
test unseen, respectively, and recruit three experts for human evaluation. The
annotators are asked to judge the model-generated response in four ways:

  * •

Fluency, which measures whether the response is fluency in expression;

  * •

Coherence, which measures whether the response is coherence to the dialogue
context;

  * •

Relevance, which measures whether the knowledge used in the response is
relevant to the dialogue; and

  * •

Factuality measures whether the response’s content is factual. In Factuality
evaluation, the experts check the content using Google.

The annotators are asked to assign a score in {0, 1} (representing
“nonfactual” and “factual”) for factuality, and a score in {0, 1, 2}
(representing “bad”, “fair”, and “good”) for the others.

###  4.4 Implementation details

We implement the GenKS using BART large (with 400M parameters) (Lewis et al.,
2020a) in HuggingFace’s Transformers library. We truncate the dialogue context
to 256 tokens, then truncate the knowledge so that the total length is less
than 1024 tokens. During inference, the responses are decoded using a greedy
search. See Appendix A for more details.

Typically, the number of passages in $\mathcal{K}$ is large, so that the input
sequence exceeds the maximum input length of BART (i.e., 1024 tokens). To
address this problem, we take advantage of a lightweight passage selector
based on DistilBERT (with 66M parameters) (Sanh et al., 2019), which aims to
rank the passages in $\mathcal{K}$. Specifically, we concatenate each passage
with dialogue context and encode the sequence using DistilBERT. Finally, the
representation of [CLS] token is used to estimate the relevance score of the
passage through a learnable MLP classifier. The passage selector is optimized
via contrastive learning objective (Nogueira and Cho, 2019), in which the
model learns to assign a higher score to positive passages than negative
passages. During inference, we keep only the top-1 passage ranked by the
passage selector. The passage selector gets Recall@1 of 75.5%, 76.5%, and
68.0% for the WoW test seen, WoW test unseen, and Holl-E, respectively.

Methods | WoW | Holl-E
---|---|---
Seen | Unseen | Single | Multi
_Classification methods_ |  |  |  |
SKT (Kim et al., 2020) | 26.8 | 18.3 | 29.2 | 39.2
DukeNet (Meng et al., 2020) | 26.4 | 19.6 | 30.0 | 40.3
DiffKS (Zheng et al., 2020) | 25.5 | 19.7 | 33.0 | -
KnowledGPT (Zhao et al., 2020b) | 28.0 | 25.4 | - | -
MIKe (Meng et al., 2021) | 28.4 | 21.5 | 31.9 | 41.8
K-Mine (Lotfi et al., 2021) | 29.7 | 28.3 | 31.7 | -
TAKE (Yang et al., 2022) | 28.8 | 25.8 | - | -
_Other methods_ |  |  |  |
CoLV (Zhan et al., 2021a) | 30.1 | 18.9 | 32.7 | -
DIALKI (Wu et al., 2021) | 32.9 | 35.5 | - | -
Graph (Li et al., 2022) | 29.4 | 30.8 | 37.7 | 46.1
GenKS | 34.2 | 36.6 | 37.9 | 46.8
_Variants for comparison_ |  |  |  |
\- BART classification | 29.8 | 29.7 | 34.0 | 44.0
\- BART classification w/ position | 30.1 | 31.2 | 34.0 | 44.0
\- Hierarchical classification | 30.0 | 31.4 | 33.8 | 43.7
\- Without passage selector | 31.4 | 32.0 | 34.5 | 44.4
\- Unorder knowledge snippets | 31.8 | 33.3 | 36.5 | 45.8
\- Without hyperlink | 33.4 | 35.4 | 36.9 | 45.4
Table 1: Knowledge selection accuracy on WoW (seen and unseen test set) and Holl-E (single reference and multi-reference test set). Bold denote the best results with significant improvements over the previous SOTA (t-test, $p<0.05$). Underline denote second best results. Methods | WoW Seen | WoW Unseen
---|---|---
PPL | F1 | KF1 | B4 | PPL | F1 | KF1 | B4
_End-to-end models_ |  |  |  |  |  |  |  |
BART (Lewis et al., 2020a) | 14.7 | 20.9 | 17.4 | 1.7 | 18.9 | 18.8 | 15.1 | 0.9
BART FiD (Izacard and Grave, 2021) | 17.0 | 21.5 | 20.0 | 3.6 | 18.4 | 20.6 | 19.2 | 3.2
BART RAG-DPR (Adolphs et al., 2021) | 11.5 | 22.6 | 26.1 | 3.7 | 13.1 | 21.5 | 22.7 | 3.0
BART FiD-RAG DPR-Poly (Shuster et al., 2021) | 11.4 | 22.1 | 29.7 | 4.1 | 13.1 | 21.1 | 27.1 | 3.8
_Pipeline models_ |  |  |  |  |  |  |  |
DukeNet (Meng et al., 2020) | 48.3 | 19.3 | 18.5 | 2.4 | 69.4 | 17.1 | 16.5 | 1.7
CoLV (Zhan et al., 2021a) | 39.5 | 20.3 | 18.2 | 2.8 | 54.3 | 18.5 | 17.5 | 2.1
KnowledGPT (Zhao et al., 2020b) | 19.2 | 22.0 | 23.8 | 3.7 | 22.3 | 20.5 | 22.1 | 3.0
K-Mine (Lotfi et al., 2021) | 13.2 | 21.8 | - | - | 16.4 | 21.1 | - | -
K2R RAG-DPR (Adolphs et al., 2021) | 18.3 | 22.0 | 27.3 | 3.7 | 22.3 | 19.9 | 23.2 | 2.8
K2R BART RAG-DPR (Adolphs et al., 2021) | 17.9 | 21.3 | 29.2 | 3.5 | 21.1 | 19.9 | 24.3 | 2.5
GenKS | 13.1 | 22.9∗ | 29.5 | 4.5∗ | 13.2 | 22.7∗ | 28.1∗ | 4.6∗
_Ablative variants_ |  |  |  |  |  |  |  |
\- With BART classification knowledge | 14.7 | 22.0 | 25.9 | 3.5 | 16.2 | 21.1 | 24.4 | 3.1
\- Without identifiers generation | 13.8 | 21.7 | 23.2 | 3.7 | 14.1 | 21.8 | 23.3 | 3.9
\- Without hyperlink | 14.2 | 22.1 | 27.2 | 3.9 | 15.5 | 22.3 | 26.9 | 4.2
\- With oracle knowledge | 8.9 | 38.8 | 74.2 | 13.1 | 10.5 | 38.9 | 74.5 | 12.8
Table 2: Evaluation results on WoW seen and unseen test set in terms of
response quality. We compare against the ground-truth dialogue response in
terms of perplexity (PPL), F1, Knowledge F1 (KF1), and BLEU-4 (B4). The four
groups lists previous end-to-end models, previous pipeline models, GenKS, and
ablative variants. The best results are highlighted with bold, and the second-
best results are highlighted with underline. * indicates significant
improvements over all baselines with p-value $<0.05$.

##  5 Experimental results

###  5.1 Performance on knowledge selection

We evaluate the knowledge selection effectiveness of GenKS on WoW and Holl-E,
respectively333We are unable to evaluate the knowledge selection accuracy on
CMU_DoG accuracy of knowledge selection on CMU_DoG due to the lack of manual
labeling.. In Table 1, we compare the knowledge selection accuracy of GenKS
with previous pipeline methods. Results show that GenKS outperforms the
baselines and achieves the highest accuracy of knowledge selection on both
datasets.

We find that GenKS particularly excels at topics that do not appear in
training dataset, as evidenced by its performance on the WoW unseen test
split. In comparison, the classification models show a noticeable decrease in
accuracy on the unseen topic. We also find that the baselines that incorporate
intra-knowledge interaction, such as, GenKS, Graph, DIALKI, have a better
grasp of knowledge of unseen topics444Note that the higher accuracy results on
unseen than seen might be due to the smaller number of topics included in the
unseen test set..

To evaluate the performance of GenKS as dialogue goes deeper, we compare GenKS
with four classification baselines (SKT, DiffKS, KnowledGPT, and BART-CLS)
overturns in Figure 3. We find that in the early stages of the conversation,
both GenKS and the baseline methods achieve high accuracy. However, as the
dialogue dives deeply into a topic, a significant performance decline is
observed among the baseline methods. In contrast, GenKS, which explicitly
captures the interaction between multi-turn dialogue and knowledge, maintained
a relatively high accuracy (around 22%-23%).

Figure 3: Knowledge selection accuracy over different dialogue turns. BART-CLS
represents a text-matching model with cross-encoder architecture.

###  5.2 Quality of generated responses

We report response generation evaluation results on WoW in Table 2. The
results on Holl-E and CMU_DoG are available in Table 7 and Table 8 in the
appendix. The results of baselines are cited from original papers or re-
evaluated using officially released checkpoints.

Compared with previous pipeline models, GenKS achieve the best performance on
almost all metrics. For example, GenKS surpasses KnowledGPT by 0.7% and 2.4%
in terms of F1 on WoW seen and WoW unseen, respectively. Note that the
improvements on the unseen test set are more notable than on the seen test
set, which agrees with the experimental results regarding knowledge selection.
GenKS also achieve competitive results compared to SOTA end-to-end models. For
example, GenKS performs comparably to BART FiD-RAG DPR-Poly on WoW seen and
outperformed on WoW unseen.

###  5.3 Ablation study about knowledge selection

To analyze the effect of each component in GenKS, we designed several variants
and conducted an ablation study about knowledge selection. Results are listed
in Table 1, “Variants for comparison”. The details of compared variants and
the findings are as follows:

BART classification We use BART to classify each candidate snippet into two
classes: “relevant” or “irrelevant”. The results show that BART in the
classification paradigm performs worse than GenKS by a large margin.

BART classification w/ position To understand the influence of position bias,
we splice the snippet’s position into the classification model’s input. We
find that the results are improved to a certain extent (about 1% improvement),
but there is still a clear gap compared with GenKS.

Hierarchical classification This variant first uses the passage selector model
of GenKS to rank the passages and then selects the snippets in the top-ranked
passage using BART classification w/ position. The results show that the
passage selector does not affect the classification model’s performance.

Without passage selector When the passage selector model of GenKS is removed,
the model has more probability of truncating the label knowledge, resulting in
an evident decline in performance.

Unorder knowledge snippets To disable the intra-knowledge interaction, we
unorder the snippets so that order of the snippets is inconsistent with the
original passages. This variant shows a decline in selection accuracy,
especially on unseen topics, indicating that keeping the order of the snippets
in the passage is necessary.

Without hyperlinks We remove the hyperlinks in the dialogue context. About a
1% accuracy drop is seen, indicating the effectiveness of hyperlinks.

###  5.4 Ablation study about response generation

As shown in Table 2, we also conduct an ablation study about response
generation. The details of compared variants and the findings are as follows:

With BART classification knowledge When replacing the generated identifier
with the knowledge selected by BART classification, a performance decline is
witnessed –the F1 value drops by 0.7% and 1.8% on Wizard seen and unseen,
sustaining the effectiveness of the knowledge selection of GenKS.

Without identifier generation This variant removes the identifier generation
by directly generating the response. We see notable performance drops,
especially in the KF1 metric. The results indicate that explicit training and
inference about knowledge selection enable to use of more appropriate
knowledge in response generation.

Without hyperlinks This variant removes hyperlinks from GenKS. It performs
worse than GenKS, probably due to its lower accuracy of knowledge selection
than GenKS.

Use the oracle knowledge We replace the model-predicted snippet identifier
with the oracle one (knowledge used by ground-truth response). The results
(e.g., KF1=74) suggest that GenKS can effectively locate and incorporate the
corresponding knowledge into the responses following the guidance of the
identifier.

Methods | WoW Seen | WoW Unseen
---|---|---
Flu. | Coh. | Rel. | Fact. | Flu. | Coh. | Rel. | Fact.
BART | 1.82 | 1.51 | 1.45 | 0.82 | 1.76 | 1.50 | 1.47 | 0.76
BART FiD | 1.88 | 1.70 | 1.55 | 0.84 | 1.85 | 1.67 | 1.53 | 0.82
TMN | 1.59 | 1.41 | 1.08 | 0.62 | 1.42 | 1.30 | 0.98 | 0.59
DukeNet | 1.69 | 1.56 | 1.22 | 0.71 | 1.66 | 1.47 | 1.10 | 0.72
KnowledGPT | 1.89 | 1.67 | 1.58 | 0.87 | 1.87 | 1.68 | 1.51 | 0.83
GenKS | 1.90 | 1.72 | 1.69 | 0.89 | 1.91 | 1.71 | 1.67 | 0.91
Table 3: Human evaluation results. Flu, Coh, Rel, and Fact denote Fluency,
Coherence, Relevance, and Factuality, respectively.

###  5.5 Human evaluation

Table 3 shows the human-evaluating results. Results show that GenKS
consistently outperforms baselines on all datasets. The Fleiss’ kappa value is
above $0.60$, indicating substantial agreement among the annotators. GenKS
outperforms KnowledGPT by about 0.02 and DukeNet by about 0.20 in terms of
response generation evaluation metrics (i.e., _Fluency_ and _Context
Coherence_). Moreover, for the _Knowledge Relevance_ , the annotators agree
that GenKS is capable of selecting knowledge that is more relevant to the
dialogue and generating more informative responses than baselines. The
_Factuality_ results show that by explicitly identifying the knowledge snippet
used in response, GenKS can reduce the hallucination of response generation.

Figure 4: Inference time (minutes) on one GPU on WoW unseen test set. The
values of models with ∗ are estimated based on the model size and input/output
length.

###  5.6 Efficiency evaluation

To evaluate the efficiency of GenKS, we compare it with previous end-to-end
models and pipeline models. The results are presented in Figure 4, which shows
that GenKS is more efficient than previous pipeline models. This may be
because GenKS integrates knowledge selection and response generation in an
end-to-end model, avoiding repeated encoding of dialogue history and
background knowledge. Furthermore, we find that GenKS, as a pipeline method,
achieves comparable efficiency to end-to-end models like RAG, but with the
added advantage of explicit knowledge selection.

Methods | WoW Seen | WoW Unseen
---|---|---
F1 | KF1 | B4 | F1 | KF1 | B4
GenKS | 22.9 | 29.5 | 4.5 | 22.7 | 28.1 | 4.6
GenKS-2 | 22.4 | 29.3 | 4.2 | 22.2 | 27.6 | 4.2
GenKS (5 Snippets) | 22.3 | 27.6 | 4.2 | 21.8 | 25.5 | 4.1
GenKS (3 Snippets) | 21.1 | 29.3 | 3.2 | 20.0 | 20.9 | 2.9
GenKS (128 Tokens) | 21.5 | 25.6 | 3.5 | 20.7 | 22.9 | 3.4
GenKS (64 Tokens) | 20.7 | 23.3 | 3.0 | 20.1 | 20.6 | 2.9
Table 4: Analytical experiment results on WoW. The first group compares GenKS
and its variant GenKS, which selects two snippets instead of one. The second
group includes the results of GenKS with different maximum number of snippets
inputs or maximum input tokens.

###  5.7 Analytical experiment

#### Multi-snippets selection

GenKS initially selects a single snippet following the experimental setup
outlined in the baselines (Dinan et al., 2019), but can also select multiple
snippets by generating multiple identifiers. To evaluate the performance of
this approach, we test a variant of the GenKS model, namely GenKS-2, which
selects two snippets by generating two identifiers consecutively. We compare
its performance with the original GenKS on the WoW dataset. The results are
listed in Table 4 group 1. GenKS-2 performs slightly worse than the original
GenKS, likely because the WoW dataset only uses one snippet in response
annotation and therefore does not benefit from using multiple snippets (Dinan
et al., 2019). Nevertheless, the results suggest that the proposed generative
knowledge selection approach has the ability to select multiple knowledge.

#### Hyper-parameter analysis

We also conduct ablation experiments on the number of input snippets to the
model and maximum input tokens. The results are listed in Table 4 group 2. We
find that reducing the number or length of knowledge reduces model
effectiveness.

Topic |  Budweiser
---|---
User |  I think Budweiser taste terrible. Have you ever had it?
Know 1 |  Produced in various breweries around the world, Budweiser is a filtered beer available in draft and packaged forms.
Res 1 |  Yes, I have. It is produced in various breweries around the world!
Know 2 |  Budweiser is an American-style pale lager produced by Anheuser-Busch, currently part of the transnational corporation Anheuser-Busch InBev.
Res 2 |  Yes, I have. I know that it is an American-style pale lager produced by Anheuser-Busch.
Table 5: Examples of GenKS outputs on the WoW.

###  5.8 Case study

To better understand end-to-end baselines and our model, we provide an example
in Table 5, which shows that GenKS appropriately changes its response
prediction when providing different knowledge snippets555Note that this
example only aims to show the output of the model. In fact, according to
https://en.wikipedia.org/wiki/Budweiser, Budweiser is also a famous lager from
the Czech Republic, and American Budweiser is sold and known as Bud through
most of the European Union.. Therefore, GenKS is more controllable and
interpretable than end-to-end models, where the end-to-end system is a black
box. We provide more case studies in Appendix B.

##  6 Conclusion

In this paper, we have proposed GenKS, a simple yet effective knowledge-
grounded dialogue model. GenKS is a generative model, which learns to select
knowledge snippets by generating their identifiers. Benefiting from the
modeling of intra-knowledge interaction and dialogue-knowledge interaction,
GenKS effectively addresses the challenges of _ambiguity_ and _discourse
structure_. Our experiments have shown that GenKS establishes a new state-of-
the-art on three knowledge-grounded dialogue benchmarks. Notably, GenKS
particularly excels at new topics and as the dialogue goes deeper. GenKS also
outperforms SOTA end-to-end models. Hence, we believe GenKS reveals a new
paradigm for knowledge selection in open-domain dialogue.

## Limitations

The limitations of this work include the modular modeling of passage reranks,
which reduces the efficiency of the approach. Besides, we only conduct human
evaluation on one popular dataset, i.e., Wizard of Wikipedia. Furthermore, the
effectiveness of GenKS is only verified in the English dataset. Research on
other languages establishes a new challenge, especially for languages with
limited knowledge and annotated data. In future work, we would like to explore
more efficient passage rerank techniques on knowledge-grounded dialogues. We
will also conduct human evaluation for more datasets. Besides, generative
knowledge selection can be extended to future studies about conversational
recommendation.

## Ethics statement

The paper proposes a knowledge-grounded dialogue system to generate a response
using external knowledge. The intended use of this system is to perform chit-
chat with the user on topics such as books and movies. The system is developed
using large pre-trained language models (i.e., BART), who are trained on
large-scale web data known to contain biased or discriminatory content. The
datasets (i.e., WoW, Holl-E, CMU_DoG) that we train on also include subjective
knowledge (comments on movies) that may express the bias of the writers.
Although the system is able to reduce the hallucination of response compared
to end-to-end models, the outputs from our system may still contain non-
factual information and should not be considered as advice for any critical
decision-making.

## Acknowledgements

This work was supported by the National Key R&D Program of China with grant
No. 2020YFB1406704, the Natural Science Foundation of China (62272274,
62202271, 61902219, 61972234, 62072279, 62102234), the Natural Science
Foundation of Shandong Province (ZR2021QF129), the Key Scientific and
Technological Innovation Program of Shandong Province (2019JZZY010129). All
content represents the opinion of the authors, which is not necessarily shared
or endorsed by their respective employers and/or sponsors.

## References

  * Adolphs et al. (2021) Leonard Adolphs, Kurt Shuster, Jack Urbanek, Arthur D. Szlam, and Jason Weston. 2021\.  Reason first, then respond: Modular generation for knowledge-infused dialogue.  _ArXiv_ , abs/2111.05204.
  * Bao et al. (2021) Siqi Bao, H. He, Fan Wang, Hua Wu, Haifeng Wang, Wenquan Wu, Zhihua Wu, Zhen Guo, Hua Lu, Xinxian Huang, Xin Tian, Xinchao Xu, Yingzhan Lin, and Zhengyu Niu. 2021.  Plato-xl: Exploring the large-scale pre-training of dialogue generation.  _ArXiv_ , abs/2109.09519.
  * Cao et al. (2021) Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2021.  Autoregressive entity retrieval.  In _ICLR 2021_.
  * Dinan et al. (2019) Emily Dinan, Stephen Roller, Kurt Shuster, Angela Fan, Michael Auli, and Jason Weston. 2019.  Wizard of wikipedia: Knowledge-powered conversational agents.  In _ICLR 2019_.
  * Freitas et al. (2020) Daniel De Freitas, Minh-Thang Luong, David R. So, Jamie Hall, Noah Fiedel, Romal Thoppilan, Zi Yang, Apoorv Kulshreshtha, Gaurav Nemade, Yifeng Lu, and Quoc V. Le. 2020.  Towards a human-like open-domain chatbot.  _ArXiv_ , abs/2001.09977.
  * Izacard and Grave (2021) Gautier Izacard and Edouard Grave. 2021.  Leveraging passage retrieval with generative models for open domain question answering.  In _EACL 2021_.
  * Kim et al. (2020) Byeongchang Kim, Jae Hyun Ahn, and Gunhee Kim. 2020.  Sequential latent knowledge selection for knowledge-grounded dialogue.  In _ICLR 2020_.
  * Lewis et al. (2020a) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020a.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _ACL 2020_ , pages 7871–7880.
  * Lewis et al. (2020b) 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. 2020b.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  In _NIPS 2020_ , volume 33, pages 9459–9474.
  * Li et al. (2020) Lin-Xiao Li, Can Xu, Wei Wu, Yufan Zhao, Xueliang Zhao, and Chongyang Tao. 2020\.  Zero-resource knowledge-grounded dialogue generation.  In _NIPS 2020_ , pages 8475–8485.
  * Li et al. (2022) Sha Li, Madhi Namazifar, Di Jin, Mohit Bansal, Heng Ji, Yang Liu, and Dilek Z. Hakkani-Tür. 2022.  Enhancing knowledge selection for grounded dialogues via document semantic graphs.  In _NAACL 2022_.
  * Li et al. (2019) Zekang Li, Cheng Niu, Fandong Meng, Yang Feng, Q. Li, and Jie Zhou. 2019.  Incremental transformer with deliberation decoder for document grounded conversations.  In _ACL 2019_ , pages 12–21.
  * Lian et al. (2019) Rongzhong Lian, Min Xie, Fan Wang, Jinhua Peng, and Hua Wu. 2019.  Learning to select knowledge for response generation in dialog systems.  In _IJCAI 2019_ , pages 5081–5087.
  * Liu et al. (2018) Shuman Liu, Hongshen Chen, Zhaochun Ren, Yang Feng, Qun Liu, and Dawei Yin. 2018\.  Knowledge diffusion for neural dialogue generation.  In _ACL 2018_ , pages 1489–1498.
  * Liu et al. (2019) Zhibin Liu, Zheng-Yu Niu, Hua Wu, and Haifeng Wang. 2019.  Knowledge aware conversation generation with explainable reasoning over augmented graphs.  In _EMNLP 2019_ , pages 1782–1792.
  * Lotfi et al. (2021) Ehsan Lotfi, Maxime De Bruyn, Jeska Buhmann, and Walter Daelemans. 2021.  Teach me what to say and i will learn what to pick: Unsupervised knowledge selection through response generation with pretrained generative models.  In _EMNLP 2021 | NLP4ConvAI_ , pages 254–262.
  * Meng et al. (2021) Chuan Meng, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Tengxiao Xi, and M. de Rijke. 2021.  Initiative-aware self-supervised learning for knowledge-grounded conversations.  In _SIGIR 2021_ , page 522–532.
  * Meng et al. (2020) Chuan Meng, Pengjie Ren, Zhumin Chen, Weiwei Sun, Zhaochun Ren, Zhaopeng Tu, and M. de Rijke. 2020.  Dukenet: A dual knowledge interaction network for knowledge-grounded conversation.  In _SIGIR 2020_ , page 1151–1160.
  * Min et al. (2021) Sewon Min, Kenton Lee, Ming-Wei Chang, Kristina Toutanova, and Hannaneh Hajishirzi. 2021.  Joint passage ranking for diverse multi-answer retrieval.  In _EMNLP 2021_ , pages 6997–7008.
  * Moghe et al. (2018) Nikita Moghe, Siddharth Arora, Suman Banerjee, and Mitesh M. Khapra. 2018.  Towards exploiting background knowledge for building conversation systems.  In _EMNLP 2018_ , pages 2322–2332.
  * Nogueira and Cho (2019) Rodrigo Nogueira and Kyunghyun Cho. 2019.  Passage re-ranking with bert.  _ArXiv_ , abs/1901.04085.
  * Nogueira et al. (2020) Rodrigo Nogueira, Zhiying Jiang, Ronak Pradeep, and Jimmy J. Lin. 2020.  Document ranking with a pretrained sequence-to-sequence model.  In _Findings of EMNLP 2020_ , pages 708–718.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _ACL 2002_ , pages 311–318.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  _ArXiv_ , abs/1910.01108.
  * Shuster et al. (2021) Kurt Shuster, Spencer Poff, Moya Chen, Douwe Kiela, and Jason Weston. 2021.  Retrieval augmentation reduces hallucination in conversation.  In _Findings of EMNLP 2021_ , pages 3784–3803.
  * Sun et al. (2022) Tianxiang Sun, Xiangyang Liu, Xipeng Qiu, and Xuanjing Huang. 2022.  Paradigm shift in natural language processing.  _Int. J. Autom. Comput._ , 19:169–183.
  * Tay et al. (2022) Yi Tay, Vinh Quang Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Gupta, Tal Schuster, William W. Cohen, and Donald Metzler. 2022.  Transformer memory as a differentiable search index.  _ArXiv_ , abs/2202.06991.
  * Thoppilan et al. (2022) Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam M. Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, Yaguang Li, Hongrae Lee, Huaixiu Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang, Maxim Krikun, Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Yanqi Zhou, Chung-Ching Chang, I. A. Krivokon, Willard James Rusch, Marc Pickett, Kathleen S. Meier-Hellstern, Meredith Ringel Morris, Tulsee Doshi, Renelito Delos Santos, Toju Duke, Johnny Hartz Søraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Diaz, Ben Hutchinson, Kristen Olson, Alejandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravindran Rajakumar, Alena Butryna, Matthew Lamm, V. O. Kuzmina, Joseph Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Aguera-Arcas, Claire Cui, Marian Croak, Ed Chi, and Quoc Le. 2022.  Lamda: Language models for dialog applications.  _ArXiv_ , abs/2201.08239.
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _NIPS 2017_ , volume 30.
  * Wu et al. (2021) Zeqiu Wu, Bo-Ru Lu, Hannaneh Hajishirzi, and Mari Ostendorf. 2021.  Dialki: Knowledge identification in conversational systems through dialogue-document contextualization.  In _EMNLP 2021_.
  * Yang et al. (2022) Chenxu Yang, Zheng Lin, JiangNan Li, Fandong Meng, Weiping Wang, Lan Wang, and Jie Zhou. 2022.  Take: Topic-shift aware knowledge selection for dialogue generation.  In _COLING 2022_.
  * Yavuz et al. (2022) Semih Yavuz, Kazuma Hashimoto, Yingbo Zhou, Nitish Shirish Keskar, and Caiming Xiong. 2022.  Modeling multi-hop question answering as single sequence prediction.  In _ACL 2022_ , pages 974–990.
  * Zhan et al. (2021a) Haolan Zhan, Lei Shen, Hongshen Chen, and Hainan Zhang. 2021a.  Colv: A collaborative latent variable model for knowledge-grounded dialogue generation.  In _EMNLP 2021_ , pages 2250–2261.
  * Zhan et al. (2021b) Haolan Zhan, Hainan Zhang, Hongshen Chen, Zhuoye Ding, Yongjun Bao, and Yanyan Lan. 2021b.  Augmenting knowledge-grounded conversations with sequential knowledge transition.  In _NAACL 2021_ , pages 5621–5630.
  * Zhao et al. (2020a) Xueliang Zhao, Wei Wu, Chongyang Tao, Can Xu, Dongyan Zhao, and Rui Yan. 2020a.  Low-resource knowledge-grounded dialogue generation.  In _ICLR 2020_.
  * Zhao et al. (2020b) Xueliang Zhao, Wei Wu, Can Xu, Chongyang Tao, Dongyan Zhao, and Rui Yan. 2020b.  Knowledge-grounded dialogue generation with pre-trained language models.  In _EMNLP 2020_ , pages 3377–3390.
  * Zheng et al. (2020) Chujie Zheng, Yunbo Cao, Daxin Jiang, and Minlie Huang. 2020.  Difference-aware knowledge selection for knowledge-grounded conversation generation.  In _Fingdings of EMNLP 2020_ , pages 115–125.
  * Zhou et al. (2018) Kangyan Zhou, Shrimai Prabhumoye, and Alan W. Black. 2018.  A dataset for document grounded conversations.  In _EMNLP 2018_ , pages 708–713.

##  Appendix A Implementation details

We use gradient clipping with a maximum gradient norm of $0.1$. We optimize
the model for up to 5 epochs with a batch size of 16 on 4 3090 GPUs with 24G
memory. We choose the model checkpoints by evaluating the metrics on the
validation set for each epoch. During inference, the responses are decoded
using a greedy search. We have tried some advanced decoding algorithms (e.g.,
nucleus sampling) and found no improvement. The training of the model can be
completed within 5h, and the latency of the model inference for one example is
within 0.1s. The passage rerank model gets Recall@1 of 75.5%, 76.5%., 61.0%
for WoW test seen, WoW test unseen, and Holl-E, respectively.

| WoW | Holl-E | CUM_DoG
---|---|---|---
Training size | 18,430 | 7,228 | 3,373
Validation size | 1,948 | 930 | 229
Test size | 965 / 968 | 913 | 619
Number of topics | 1,365 | 858 | 30
Avg. Turn per dialogue | 9.0 | 10.1 | 22.2
Avg. Num of snippets | 62.5 | 57.3 | 36.3
Avg. Num of passages | 11.6 | 5.9 | 4.0
Table 6: Statistics of two experimental datasets, Wizard of Wikipedia (WoW), Holl-E, and CMU_DoG. The two numbers in WoW indicate the size of seen and unseen test set, respectively. | F1 | B4 | KF1 | RG1 | RG2
---|---|---|---|---|---
BART (Lewis et al., 2020a) | 34.7 | 22.3 | 29.1 | 38.0 | 27.9
CoLV (Zhan et al., 2021a) | - | 20.3 | - | 32.0 | 25.8
MIKe (Meng et al., 2021) | 32.1 | 21.1 | - | 38.0 | 25.2
Graph (Li et al., 2022) | - | - | - | 42.5 | 34.4
GenKS | 36.7 | 24.3 | 31.3 | 42.3 | 35.2
Table 7: Results on Holl-E in term of response quality. RG1 and RG2 denote ROUGE-1 and ROUGE-2 respectively. Best results are heighten with bold. | PPL | F1 | Avg. | Ext. | Greedy
---|---|---|---|---|---
ITDD (Li et al., 2019) | 26.0 | 10.4 | 0.748 | 0.390 | 0.587
DRD (Zhao et al., 2020a) | 46.1 | 10.8 | 0.791 | 0.406 | 0.613
TMN (Dinan et al., 2019) | 75.2 | 9.9 | 0.789 | 0.399 | 0.615
KGPT (Zhao et al., 2020b) | 20.6 | 13.5 | 0.837 | 0.437 | 0.654
GenKS | 16.1 | 14.1 | 0.847 | 0.442 | 0.668
Table 8: Results on CMU_DoG in term of response quality. The best results are
highlighted with bold.

##  Appendix B Case study

To better understand baselines and our model, we present two examples in Table
9 and Table 10. Table 9 show example where both GenKS and baselines select out
the proper knowledge (i.e., the knowledge snippet shown in green). We see that
the response generated by GenKS is more appropriate to the dialogue context
than baselines, while KnowledGPT’s response does not answer User2’s question
and is also factually incorrect. In Table 10, we observed that although
neither GenKS nor the baselines selected the label knowledge, the response
generated by GenKS is still more natural and coherence. We also find that
KnowledGPT is more colloquial than GenKS but has problems with hallucinations.

Topic |  Nickelback
---|---
User |  Do you like Nickelback?
… |
User |  Yes, what more can you tell me about Nickelback?
System |  Chad Kroeger is the leading vocalist of the group.
User |  Amazing. What about the other group members
Passage |  The band is composed of guitarist and lead vocalist _Chad Kroeger_ , guitarist, keyboardist and backing vocalist _Ryan Peake_ , bassist _Mike Kroeger_ , and drummer _Daniel Adair_.
TMN |  i think the song is a very popular song
DukeNet |  chad kroeger is a great band
KGPT |  the lead vocalist is chad kroeger. he is also the drummer.
GenKS |  Chad Kroeger, Ryan Peake, Mike Kroeger and Daniel Adair.
Human |  Ryan Peake is the keyboardist an Mike Kroeger is the bassist.
Table 9: Case study on the Wizard Test Unseen dataset. This table shows an example where both GenKS and baselines select the proper knowledge. Topic |  List of national parks of the United States
---|---
User |  I love national parks dont you
… |
User |  I live in Arkansas and love the Hot SPrings National Park and have been there many times, really it is beautiful
DukeNet |  i have heard the city is located in the ouachita mountains among the us
KGPT |  i’ve been to the ouachita mountains, too! i’ve been to the ouachita mountains in the ouachita mountains.
GenKS |  I’ve never been to Hot Springs, but I’ve always wanted to go to there.
Human |  I’ve never been to that one! I bet its beautiful!
Table 10: Case study on the Wizard Test Unseen dataset. This table shows an
example where both models select the wrong knowledge.


Intermodal
Co-Attention Attention-based
Modality Fusion Attention Mapping 4 $\displaystyle\times$Dense Layers Visual
Modality Score Text Modality Score 4 $\displaystyle\times$Dense Layers
Attended
Visual
Features Attended
Textual
Features Fused
Multimodal Features Visual Features (Objects/Faces;
With/Without
Spatial Encoding) Text Features (With/Without
Spatial Encoding) Prediction


# ikd-Tree: An Incremental K-D Tree for Robotic Applications

Yixi Cai, Wei Xu and Fu Zhang Y. Cai, W. Xu and F. Zhang are with the
Department of Mechanical Engineering, Hong Kong University, Hong Kong SAR.,
China<EMAIL_ADDRESS>$\\{$xuweii<EMAIL_ADDRESS>
###### Abstract

This paper proposes an efficient data structure, ikd-Tree, for dynamic space
partition. The ikd-Tree incrementally updates a k-d tree with new coming
points only, leading to much lower computation time than existing static k-d
trees. Besides point-wise operations, the ikd-Tree supports several features
such as box-wise operations and down-sampling that are practically useful in
robotic applications. In parallel to the incremental operations (i.e., insert,
re-insert, and delete), ikd-Tree actively monitors the tree structure and
partially re-balances the tree, which enables efficient nearest point search
in later stages. The ikd-Tree is carefully engineered and supports multi-
thread parallel computing to maximize the overall efficiency. We validate the
ikd-Tree in both theory and practical experiments. On theory level, a complete
time complexity analysis is presented to prove the high efficiency. On
experiment level, the ikd-Tree is tested on both randomized datasets and real-
world LiDAR point data in LiDAR-inertial odometry and mapping application. In
all tests, ikd-Tree consumes only 4% of the running time in a static k-d tree.

##  I Introduction

The K-Dimensional Tree (K-D Tree) is an efficient data structure that
organizes multi-dimensional point data [1] which enables fast search of
nearest neighbors, an essential operation that is widely required in various
robotic applications[2]. For example, in LiDAR odometry and mapping, k-d tree-
based nearest points search is crucial to match a point in a new LiDAR scan to
its correspondences in the map (or the previous scan) [3, 4, 5, 6, 7, 8].
Nearest points search is also important in motion planning for fast obstacle
collision check on point-cloud, such as in [9, 10, 11, 12, 13, 14].

Common-used k-d tree structure in robotic applications[15] is “static”, where
the tree is built from scratch using all points. This contradicts with the
fact that the data is usually acquired sequentially in actual robotic
applications. In this case, incorporating a frame of new data to existing ones
by re-building the entire tree from scratch is typically very inefficient and
time-consuming. As a result, k-d trees are usually updated at a low frequency
[5, 6, 7] or simply re-built only on the new points [11, 12].

To fit the sequential data acquisition nature, a more natural k-d tree design
would be updating (i.e., insert and delete) the existing tree locally with the
newly acquired data. The local update would effectively eliminate redundant
operations in re-building the entire tree, and save much computation. Such a
dynamic k-d tree is particularly promising when the new data is much smaller
than existing ones in the tree.

However, a dynamic k-d tree brings suitable for robotic applications several
challenges: 1) It should support not merely efficient points operations such
as insertion and delete but also space operations such as point-cloud down-
sampling; 2) It easily grows unbalanced after massive points or space
operations which deteriorates efficiency of points queries. Hence re-building
is required to re-balance the tree. 3) The re-building should be sufficiently
efficient to enable real-time robotic applications.

Figure 1: Illustration of incremental k-d tree update and re-balancing. (a):
an existing k-d tree (black dots) and new points (red triangles) to insert,
blue cubes denote the space (i.e., branches) need to be re-balanced. (b): the
k-d tree after points insertion and tree re-balancing, blue cubes denote the
space after re-balancing while rest majority tree does not change.

In this paper, we propose a dynamic k-d tree structure called ikd-Tree, which
builds and incrementally updates a k-d tree with new points only while
simultaneously down-sample them into the desired resolution. It supports
incremental operations including insertion, re-insertion, and delete of a
single point (i.e., point-wise) or a box of points (i.e., box-wise). The tree
is automatically re-balanced by partial re-building. To preserve efficient
real-time tree update, ikd-Tree separates the tree re-building in two parallel
threads when necessary. This paper also provides a complete time complexity
analysis for all tree updates, including both incremental operations and re-
balancing. The time complexity of ikd-Tree is reduced substantially as
verified on both random data and real-world point-cloud in LiDAR-inertial
mapping applications. The ikd-Tree is open sourced at Github111Git:
https://github.com/hku-mars/ikd-Tree.git. Fig. 1 illustrates the incremental
updates and re-balancing on the tree from a 3-D view.

The remaining paper is organized as follows: Section II introduces related
work. The design of ikd-Tree is described in Section III. Theoretical analysis
of time and space complexity are presented in Section IV. Experiments are
shown in Section V, followed by conclusions in Section VI.

##  II Related work

A k-d tree can be viewed as a binary search tree and inherits the same
incremental operations (i.e., insert, re-insert, and delete), such as those in
AVL trees [16], treaps [17] and splay trees[18]. In these techniques, re-
balancing of a binary search tree after many points operations can be easily
achieved by tree node rotations. However, this straightforward tree rotation
only works for one-dimensional data. For k-d trees with higher data dimension,
it requires much more complicated tree reorganization.

Strategies specifically designed for fast re-balancing k-d trees fall into two
categories: hardware-based acceleration and specially designed structure
enabling dynamic re-balancing. Hardware-based algorithms exploits the
computing hardware to (re-) balance a kd-tree by building a new one. It has
been thoroughly investigated to solve the ray tracing problem in dynamic
scenes. In 3D graphic applications, algorithms on single-core CPU[19, 20] and
multi-core CPU [21] are firstly proposed to speed up the k-d tree
construction. Zhou et al. proposed a real-time construction algorithm on
GPU[22]. These algorithms rely heavily on the computing resource which is
usually limited on onboard computers.

For the second category, Bentley et al. proposed a general binary
transformation method for converting a static k-d tree to a dynamic one [23].
The dynamic k-d tree supports only insertion but not delete, which leads to a
growing tree size hence increased time for nearest search. Galperin et al.
[24] proposes a scapegoat k-d tree that can dynamically re-balance the tree by
re-building unbalanced sub-trees, which is much more efficient than a complete
re-building of the entire tree. Bkd tree [25] is a dynamic data structure
extended from a K-D-B tree[26] which focus on external memory adaptions. A set
of static k-d trees are built in the Bkd tree where the trees are re-balanced
by re-building partial set of the trees at regular intervals. The well-known
point cloud library (PCL)[15] uses the fast library for approximate nearest
neighbors (FLANN) search[27]. Point insertion and delete are supported in
FLANN but the trees are re-balanced via inefficient complete tree re-building
after a predetermined amount of points insertion or delete [28].

Our ikd-Tree is an efficient and complete data structure enabling incremental
operations (i.e., insert, re-insert, and delete) and dynamic re-balancing of
k-d trees. Compared to the dynamic k-d tree in [23], our implementation
supports points delete. Besides the point-wise operations presented in [16,
17, 18] and [24], our ikd-Tree further supports the incremental operations of
a box of points (i.e., box-wise operations) and simultaneous points down-
sampling. The dynamic tree re-balancing strategy of ikd-Tree follows the
concept of scapegoat trees in [24], which only re-builds those unbalanced sub-
trees. The ikd-Tree is particularly suitable for robotic applications, such as
real-time LiDAR mapping and motion planning, where data are sampled
sequentially and fast incremental update is necessary.

##  III ikd-Tree Design and Implementation

In this section, we describe how to design, build, and update an incremental
k-d tree in ikd-Tree to allow incremental operations (e.g., insertion, re-
insertion, and delete) and dynamic re-balancing.

###  III-A Data Structure

The attributes of a tree node in ikd-Tree is presented in Data Structure 1.
Line 2-4 are the common attributes for a standard k-d tree. The attributes
$leftson$ and $rightson$ are pointers to its left and right son node,
respectively. The point information (e.g., point coordinate, intensity) are
stored in $point$. Since a point corresponds a single node on a k-d tree, we
will use points and nodes interchangeably. The division axis is recorded in
$axis$. Line 5-7 are the new attributes designed for incremental updates
detailed in Section III-C.

1 Struct  _TreeNode_ :

// Common Attributes in Standard K-D trees

2 PointType $point$;

3 TreeNode * $leftson$, $rightson$;

4 int $axis$;

// New Attributes in ikd-Tree

5 int $treesize$, $invalidnum$;

6 bool $deleted$, $treedeleted$, $pushdown$;

7 float $range[k][2]$;

8 end

Algorithm 1 Data Structure 1: Tree node structure

###  III-B Building An Incremental K-D Tree

Building an incremental k-d tree is similar to building a static k-d tree
except maintaining extra information for incremental updates. The entire
algorithm is shown in Algorithm 2: given a point array $V$, the points are
firstly sorted by the division axis with maximal covariance (Line 4-5). Then
the median point is saved to $point$ of a new tree node $T$ (Line 6-7). Points
below and above the median are passed to the left and right son nodes of $T$,
respectively, for recursive building (Line 9-10). The LazyLabelInit and Pullup
in Line 11-12 update all attributes necessary for incremental updates (see
Data Structure 1, Line 5-7) detailed in Section III-C.

Input: $V,N$ $\triangleright$ Point Array and Point Number

Output: $RootNode$ $\triangleright$ K-D Tree Node

1 $RootNode$ = Build(_$V,0,N-1$_);

2

3Function  _Build(_$V,l,r$_)_

4 $mid\leftarrow\lfloor(l+r)/2\rfloor$;

5 $Axis\leftarrow\text{Axis with Maximal Covariance}$;

6 $V\leftarrow sort(V,axis)$;

7 Node $T$;

8 $T.point\leftarrow V[mid]$;

9 $T.axis\leftarrow Axis$;

10 $T.leftson\leftarrow$ Build(_$V,l,mid-1$_);

11 $T.rightson\leftarrow$ Build(_$V,mid+1,r$_);

12 LazyLabelInit($T$);

13 Pullup(_$T$_);

14 return $T$;

15

End Function

Algorithm 2 Build a balanced k-d tree

###  III-C Incremental Updates

The incremental updates refer to incremental operations followed by a dynamic
re-balancing detailed in Section III-D. The incremental operations include
insertion, delete and re-insertion of points to/from the k-d tree.
Specifically, the insertion operation appends a new point (i.e., a node) to
the k-d tree. In the delete operation, we use a lazy delete strategy. That is,
the points are not removed from the tree immediately but only labeled as
“deleted” by setting the attribute $deleted$ to true (see Data Structure 1,
Line 6). If all nodes on the sub-tree rooted at $T$ have been deleted, the
attribute $treedeleted$ of $T$ is set to true. Therefore the attributes
$deleted$ and $treedeleted$ are called lazy labels. If points labeled as
“deleted” but not removed are later inserted to the tree, it is referred to as
“re-insertion” and is efficiently achieved by simply setting the $deleted$
attribute back to false. Otherwise, points labeled as “deleted” will be
removed from the tree during re-building process(see Section III-D).

Our incremental updates support two types: point-wise updates and box-wise
updates. The point-wise updates insert, delete, or re-insert a single point on
the tree while the box-wise updates insert, delete or re-insert all points in
a given box aligned with the data coordinate axis. Box-wise updates may
require to delete or re-insert an entire sub-tree rooted at $T$. In this case,
recursively updating the lazy labels $deleted$ and $treedeleted$ for all
offspring nodes of $T$ are still inefficient. To address this issue, we use a
further lazy strategy to update the lazy labels of the offspring nodes. The
lazy label for lazy labels $deleted$ and $treedeleted$ is $pushdown$ (see Data
Structure 1, Line 6). The three labels $deleted$, $treedeleted$, and
$pushdown$ are all initialized as false in LazyLabelInit (see Algorithm 2,
Line 11).

####  III-C1 Pushdown and Pullup

Two supporting functions, Pushdown and Pullup, are designed to update
attributes on a tree node $T$. The Pushdown function copies the labels
$deleted$, $treedeleted$, and $pushdown$ of $T$ to its sons (but not further
offsprings) when the attribute $pushdown$ is true. The Pullup function
summarizes the information of the sub-tree rooted at ${T}$ to the following
attributes of node $T$: $treesize$ (see Data Structure 1, Line 5) saving the
number of all nodes on the sub-tree, $invalidnum$ saving the number of nodes
labelled as “deleted” on the sub-tree, and $range$ (see Data Structure 1, Line
7) summarising the range of all points on the sub-tree along coordinate
$axis$, where $k$ is the points dimension.

####  III-C2 Point-wise Updates

The point-wise updates on the incremental k-d tree are implemented in a
recursive way which is similar to the scapegoat k-d tree[24]. For point-wise
insertion, the algorithm searches down from the root node recursively and
compare the coordinate on division axis of the new point with the points
stored on the tree nodes until a leaf node is found to append a new tree node.
For delete or re-insertion of a point $P$, the algorithm finds the tree node
storing the point $P$ and modifies the attribute $deleted$. Further details
can be found in our Github repository1.

Input: $C_{O}$ $\triangleright$ Operation box
$T$ $\triangleright$ K-D Tree Node
$SW$ $\triangleright$ Switch of Parallelly Re-building

1 Function  _BoxwiseUpdate(_$T,C_{O},SW$_)_

2 Pushdown(_$T$_);

3 $C_{T}\leftarrow T.range$;

4 if  _$C_{T}\cap C_{O}=\varnothing$ _ then return

5

6 if  _$C_{T}\subseteqq C_{O}$_ then

7 UpdateLazyLabel(__) ;

8 $T.pushdown$ = true;

9 return;

10 else

11 $P\leftarrow T.point$;

12 if  _$P\subset C_{O}$_ then Modify $T.deleted$

13 BoxwiseUpdate(_$T.leftson,C_{O},SW$_);

14 BoxwiseUpdate(_$T.rightson,C_{O},SW$_);

15

16 end if

17 Pullup(_$T$_);

18 if  _ViolateCriterion(_$T$_)_ then

19 if  _$T.treesize <N_{\max}$ or Not $SW$_ then

20 Rebuild(_$T$_)

21 else

22 ThreadSpawn(_ParallelRebuild , $T$_)

23 end if

24

25 end if

26

27

28End Function

Algorithm 3 Box-wise Updates

####  III-C3 Box-wise Updates

The box-wise insertion is implemented by inserting the new points one by one
into the incremental k-d tree. Other box-wise updates (box-wise delete and re-
insertion) are implemented utilizing the range information in attribute
$range$, which forms a box $C_{T}$, and the lazy labels on the tree nodes. The
pseudo code is shown in Algorithm 3. Given the box of points $C_{O}$ to be
updated on (sub-) tree rooted at $T$, the algorithm first passes down its lazy
labels to its sons for further passing-down if visited (Line 2). Then, it
searches the k-d tree from its root node recursively and checks whether the
range $C_{T}$ on the (sub-)tree rooted at the current node $T$ has an
intersection with the box $C_{O}$. If there is no intersection, the recursion
returns directly without updating the tree (Line 4). If the box $C_{T}$ is
fully contained in the box $C_{O}$, the box-wise delete set attributes
$deleted$ and $treedeleted$ to true while the box-wise re-insertion set them
to false by function UpdateLazyLabel (Line 6). The $pushdown$ attribute is set
to true indicating that the latest incremental updates have not been applied
to the offspring nodes of $T$. For the condition that $C_{T}$ intersects but
not contained in $C_{O}$, the current point $P$ is firstly deleted from or re-
inserted to the tree if it is contained in $C_{O}$ (Line 11), after which the
algorithm looks into the son nodes recursively (Line 12-13) and updates all
attributes of the current node $T$ (Line 15). Line 16-22 re-balance the tree
if certain criterion is violated (Line 16) by re-building the tree in the same
(Line 18) or a separate (Line 20) thread. The function ViolateCriterion,
Rebuild and ParrallelRebuild are detailed in Section III-D.

Input: $L$ $\triangleright$ Length of Downsample Cube
$P$ $\triangleright$ New Point

1 $C_{D}\leftarrow$ FindCube(_$L,P$_)

2 $P_{center}\leftarrow$ Center(_$C_{D}$_);

3 $V\leftarrow$ BoxwiseSearch(_$RootNode,C_{D}$_);

4 $V.push(P)$;

5 $P_{nearest}\leftarrow$ FindNearest $(V,P_{center})$;

6 BoxwiseDelete(_$RootNode,C_{D}$_)

PointwiseInsert(_$RootNode,P_{nearest}$_);

Algorithm 4 Downsample Figure 2: Point Cloud Downsample. (a): the point cloud
before down-sampling. (b): the point cloud after down-sampling

####  III-C4 Downsample

Our ikd-Tree further supports down-sampling as detailed in Algorithm 4. For
the given point $P$ and down-sampling resolution $L$, the algorithm partitions
the space evenly into cubes of length $L$, then the box $C_{D}$ that contains
point $P$ is found (Line 1). The algorithm only keeps the point that is
nearest to the center $P_{center}$ of $C_{D}$ (Line 2). This is achieved by
firstly searching all points contained in $C_{D}$ on the k-d tree and stores
them in a point array $V$ together with the new point $P$ (Line 3-4). The
nearest point $P_{nearest}$ is obtained by comparing the distances of each
point in $V$ to the center $P_{center}$ (Line 5). Then existing points in
$C_{D}$ are deleted (Line 6), after which the nearest point $P_{nearest}$ is
inserted to the k-d tree (Line 7). The implementation of box-wise search is
similar to the box-wise delete and re-insertion (see Algorithm 3). An example
of downsample is shown in Fig. 2.

In summary, Table I shows the comparison of supported incremental updates on
the static k-d tree[1], the dynamic k-d tree[23], the scapegoat k-d tree[24]
and our ikd-Tree.

TABLE I: Comparison of Supported Incremental Updates |  |  Static K-D Tree |  Dynamic K-D Tree |  Scapegoat K-D Tree | ikd-Tree
---|---|---|---|---|---
Point- wise | Insert | ✗ | ✓ | ✓ | ✓
Delete | ✗ | ✗ | ✓ | ✓
Re-insert | ✗ | ✗ | ✗ | ✓
Box- wise | Insert | ✗ | ✓ | ✓ | ✓
Delete | ✗ | ✗ | ✗ | ✓
Re-insert | ✗ | ✗ | ✗ | ✓
Downsample | ✗ | ✗ | ✗ | ✓

###  III-D Re-balancing

Our ikd-Tree actively monitors the balance property of the incremental k-d
tree and dynamically re-balance it by partial re-building.

####  III-D1 Balancing Criterion

The balancing criterion is composed of two sub-criterions: $\alpha$-balanced
criterion and $\alpha$-deleted criterion. Suppose a sub-tree of the
incremental k-d tree is rooted at $T$. The sub-tree is $\alpha$-balanced if
and only if it satisfies the following condition:

$\displaystyle S(T.leftson)$ $\displaystyle<\alpha_{bal}\Big{(}S(T)-1\Big{)}$
(1) $\displaystyle S(T.rightson)$
$\displaystyle<\alpha_{bal}\Big{(}S(T)-1\Big{)}$

where $\alpha_{bal}\in(0.5,1)$ and $S(T)$ is the $treesize$ attribute of the
node $T$.

The $\alpha$-deleted criterion of the sub-tree rooted at $T$ is

$\displaystyle I(T)<\alpha_{del}S(T)$ (2)

where $\alpha_{del}\in(0,1)$ and $I(T)$ denotes the number of invalid nodes on
the sub-tree (i.e., the attributes $invalidnum$ of node $T$).

If a sub-tree of the incremental k-d tree meets both criterion, the sub-tree
is balanced. The entire tree is balanced if all sub-trees are balanced.
Violation of either criterion will trigger a re-building process to re-balance
that (sub-) tree: the $\alpha$-balanced criterion maintains the maximum height
of the (sub-) tree. It can be easily proved that the maximum height of an
$\alpha$-balanced tree is $\log_{1/\alpha_{bal}}(n)$ where $n$ is the tree
size; the $\alpha$-deleted criterion ensures invalid nodes (i.e., labeled as
“deleted”) on the (sub-) trees are removed to reduce tree size. Reducing
height and size of the k-d tree allows highly efficient incremental operations
and queries in future. The function ViolateCriterion in Algorithm 3, Line 16
returns true if either criterion is violated.

####  III-D2 Re-build

Assuming re-building is triggered on a subtree $\mathcal{T}$ (see Fig. 3), the
sub-tree is firstly flattened into a point storage array $V$. The tree nodes
labeled as “deleted” are discarded during flattening. A new perfectly balanced
k-d tree is then built with all points in $V$ by Algorithm 2.

Figure 3: Re-build an unbalanced sub-tree

####  III-D3 Parallel Re-build

An evident degradation of real-time ability is observed when re-building a
large sub-tree on the incremental k-d tree. To preserve high real-time
ability, we design a double-thread re-building method: the main thread only
re-builds sub-trees whose size is smaller than a predetermined value
$N_{\max}$ and the second thread re-builds the rest. The key problem is how to
avoid information lose and memory conflicts between the main thread and the
second thread.

The re-building algorithm on the second thread is shown in Algorithm 5. Denote
the sub-tree to re-build in the second thread as $\mathcal{T}$ and its root
node as $T$. The second thread will lock all incremental updates (i.e., points
insert, re-insert, and delete) but not queries on this sub-tree (Line 2). Then
the second thread copies all valid points contained in the sub-tree
$\mathcal{T}$ into a point array $V$ (i.e. flatten) while leaving the original
sub-tree unchanged for possible queries during the re-building process (Line
3). After the flattening, the sub-tree is unlocked for the main thread to take
further requests of incremental updates (Line 4). These requests will be
suspended and recorded in a queue named as operation logger. Once the second
thread completes building a new balanced k-d tree $\mathcal{T}^{\prime}$ from
the point array $V$ (Line 5), the recorded update requests will be performed
on the balanced sub-tree $\mathcal{T}^{\prime}$ by function IncrementalUpdates
(Line 6-8) where the parallel re-building option is set to false (as it is
already in the second thread). After all pending requests are processed, the
algorithm locks the node $T$ from both incremental updates and queries and
replace it with the new one $T^{\prime}$ (Line 9-12). Finally, the algorithm
frees the memory of the original sub-tree (Line 13). Note that LockUpdates
does not block queries, which can be conducted parallelly in the main thread.
In contrast, LockAll blocks all access including queries, but it finishes very
quickly (i.e., only one instruction), allowing timely queries in the main
thread. The function LockUpdates and LockAll are implemented by mutual
exclusion (mutex).

Input: $T$ $\triangleright$ Root node of $\mathcal{T}$ for re-building

1 Function  _ParallelRebuild(_$T$_)_

2 LockUpdates(_$T$_);

3 $V\leftarrow\textnormal{{Flatten(}}\textnormal{\emph{T}}\textnormal{{)}}$;

4 Unlock(_$T$_);

5
$T^{\prime}\leftarrow\textnormal{{Build(}}\textnormal{\emph{V,0,size(V)-1}}\textnormal{{)}}$;

6 foreach  _ $op$ in $OperationLogger$_ do

7 IncrementalUpdates(_$T^{\prime},op,false$_)

8 end foreach

9 $T_{temp}\leftarrow T$;

10 LockAll(_$T$_);

11 $T\leftarrow T^{\prime}$;

12 Unlock(_$T$_);

13 Free(_$T_{temp}$_);

14

15

End Function

Algorithm 5 Parallelly Rebuild for Re-balancing

###  III-E K-Nearest Neighbor Search

The nearest search on the incremental k-d tree is an accurate nearest search
[2] instead of an approximate one as [27]. The function Pushdown is applied
before searching the sub-tree rooted at node $T$ to pass down its lazy labels.
We use the attribute $range$ to speed up the search process thus hard real-
time ability is preserved. Due to the space limit, the details of k-nearest
search algorithm is not presented in this paper. Interested readers can refer
to the related codes in our open source library.

##  IV Complexity Analysis

###  IV-A Time Complexity

The time complexity of ikd-Tree breaks into the time for incremental
operations (insertion, re-insertion and delete) and re-building.

####  IV-A1 Incremental Operations

The time complexity of point-wise operations is given as

######  Lemma 1 (Point-wise Operations)

An incremental k-d tree can handle a point-wise incremental operation with
time complexity of $O(\log n)$ where $n$ is the tree size.

###### Proof:

The maximum height of an incremental k-d tree can be easily proved to be
$\log_{1/\alpha_{bal}}(n)$ from Eq. (1) while that of a static k-d tree is
$\log_{2}n$. Hence the lemma is directly obtained from [1] where the time
complexity of point insertion and delete on a k-d tree was proved to be
$O(\log n)$. The point-wise re-insertion modifies the attribute $deleted$ on a
tree node thus the time complexity is the same as point-wise delete. ∎

The time complexity of box-wise operations on an incremental k-d tree is:

######  Lemma 2 (Box-wise Operations)

An incremental 3-d tree handles box-wise insertion of $m$ points in $C_{D}$
with time complexity of $O(m\log n)$. Furthermore, suppose points on the 3-d
tree are in space $S_{x}\times S_{y}\times S_{z}$ and $C_{D}=L_{x}\times
L_{y}\times L_{z}$. The box-wise delete and re-insertion can be handled with
time complexity of $O(H(n))$, where

$O(H(n))=\begin{cases}O(\log
n)&\text{if}\Delta_{\min}\geqslant\alpha(\frac{2}{3})\text{(*)}\\\
O(n^{1-a-b-c})&\text{if}\Delta_{\max}\leqslant
1-\alpha(\frac{1}{3})\text{(**)}\\\
O(n^{\alpha(\frac{1}{3})-\Delta_{\min}-\Delta_{\text{med}}})&\text{if (*) and
(**) fail and}\\\
&\Delta_{\text{med}}<\alpha(\frac{1}{3})-\alpha(\frac{2}{3})\\\
O(n^{\alpha(\frac{2}{3})-\Delta_{\min}})&\text{otherwise.}\end{cases}$ (3)

where $a=\log_{n}\frac{S_{x}}{L_{x}}$, $b=\log_{n}\frac{S_{y}}{L_{y}}$ and
$c=\log_{n}\frac{S_{z}}{L_{z}}$ with $a,b,c\geqslant 0$. $\Delta_{\min}$,
$\Delta_{\text{med}}$ and $\Delta_{\max}$ are the minimal, median and maximal
value among $a$, $b$ and $c$. $\alpha(u)$ is the flajolet-puech function with
$u\in[0,1]$, where particular value is provided: $\alpha(\frac{1}{3})=0.7162$
and $\alpha(\frac{2}{3})=0.3949$

###### Proof:

The box-wise insertion is implemented by point-wise insertion thus the time
complexity can be directly obtained from Lemma 1. An asymptotic time
complexity for range search on a k-d tree is provided in [29]. The box-wise
delete and re-insertion can be regarded as a range search except that lazy
labels are attached to the tree nodes. Therefore, the conclusion of range
search can be applied to the box-wise delete and re-insertion on the
incremental k-d tree. ∎

The down-sampling method on an incremental k-d tree is composed of box-wise
search and delete followed by the point insertion. By applying Lemma 1 and
Lemma 2, the time complexity of downsample is $O(\log n)$+$O(H(n))$.
Generally, the downsample hypercube $C_{D}$ is very small comparing with the
entire space. Therefore, the normalized range $\Delta x$, $\Delta y$ and
$\Delta z$ are small and the value of $\Delta_{\min}$ satisfies the condition
(*) for time complexity of $O(\log n)$. Hence, the time complexity of down-
sampling is $O(\log n)$.

####  IV-A2 Re-build

Time complexity for re-building breaks into two types: single-thread re-
building and parallel two-thread re-building. In the former case, the re-
building is performed by the main thread in a recursive way, each level takes
the time of sorting (i.e., $O(n)$) and the total time over $\log n$ levels is
$O(n\log n)$ [1] when the the dimension $k$ is low (e.g., 3 in most robotic
applications). For parallel re-building, the time consumed in the main thread
is only flattening (which suspends the main thread from further incremental
updates, Algorithm 5, Line 2-4) but not building (which is performed in
parallel by the second thread, Algorithm 5, Line 5) or tree update (which
takes constant time $O(1)$, Algorithm 5, Line 10-12), leading to a time
complexity of $O(n)$. In summary, the time complexity of re-building an
incremental k-d tree is $O(n)$ for two-thread parallel re-building and
$O(n\log n)$ for single-thread re-building.

####  IV-A3 Nearest Search

For robotic applications, the points dimension is usually very small. Hence
the time complexity of k-nearest search on the incremental k-d tree can be
simply approximated as $O(\log n)$ because the maximum height of the
incremental k-d tree is maintained no larger than $\log_{\frac{1}{\alpha}}n$.

###  IV-B Space Complexity

As shown Section III, each node on the incremental k-d tree records point
information, tree size, invalid point number and point distribution of the
tree. Extra flags such as lazy labels are maintained on each node for box-wise
operations. For an incremental k-d tree with $n$ nodes, the space complexity
is $O(n)$ though the space constant is a few times larger than a static k-d
tree.

TABLE II: The Parameters Setup of ikd-Tree in Experiments | Randomized Data | LiDAR Inertial-Odometry Mapping
---|---|---
$N_{\max}$ | 1500 | 1500
$\alpha_{bal}$ | 0.6 | 0.6
$\alpha_{del}$ | 0.5 | 0.5
$C_{D}$ | - | $0.2m\times 0.2m\times 0.2$

##  V Application Experiments

###  V-A Randomized Data Experiments

The efficiency of our ikd-Tree is fully investigated by two experiments on
randomized incremental data sets. The first experiment generates 5,000 points
randomly in a $10m\times 10m\times 10m$ space (i.e., the workspace) to
initialize the incremental k-d tree. Then 1,000 test operations are conducted
on the k-d tree. In each test operation, 200 new points randomly sampled in
the workspace are inserted (point-wise) to the kd-tree. Then another 200
points are randomly sampled in the workspace and searched on (but not inserted
to) the k-d tree for 5 nearest points of each. For every 50 test operations, 4
cubes are sampled in the workspace with side length of $1.5m$ and points
contained in these 4 cubes are deleted (box-wise) from the k-d tree. For every
100 test operations, 2,000 new points are sampled in the workspace and
inserted (point-wise) to the k-d tree. We compare the ikd-Tree with the static
k-d tree used in point cloud library[15] where at each test operation the k-d
tree is entirely re-built. The experiments are performed on a PC with Intel
i7-10700 CPU at 2.90GHz and only 2 threads running. The parameters of the
incremental k-d tree are summarized in Table II where no down-sampling is used
to allow a fair comparison. Also the maximal point number allowed to store on
the leaf node of a static k-d tree is set to 1 while the original setting in
point cloud library is 15.

Figure 4: The time performance comparison between an ikd-Tree and a static k-d
tree.

The results of the first experiment are shown in Fig. 4, where the point
number increases from 5,000 to approximate 200,000. In this process, the time
for incremental updates (including both incremental operations and re-
building) on the ikd-Tree remains stably around 1.6 $ms$ while that for the
static k-d tree grows linearly with number of the points (see Fig. 4(a)). The
high peaks in the time consumption are resulted from the large-scale point-
wise insertion (and associated re-balancing) and the low peaks are resulted
from box-wise delete (and associated re-balancing). As shown in Fig. 4(b), the
time performance of the k-nearest search on the ikd-Tree is slightly slower
than an static k-d tree, possibly due to the highly optimized implementation
of the PCL library. Despite of the slightly lower efficiency in query, the
overall time consumption of ikd-Tree outperforms the static k-d tree by one
order of magnitude (See Fig. 4(c)).

Figure 5:  Fig. (a) and (b) illustrate new points (orange triangles) and
points already on the k-d tree (blue dots). Fig. (c) shows the time for
incremental updates of sparse and compact data on k-d trees of different size.

The second experiment investigates the time performance of incremental updates
for new points of different distribution. In the experiment, we sample two
sets of 4,000 new points in a $10m\times 10m\times 10m$ space (i.e., the
workspace): one is evenly distributed (i.e., sparse data, see Fig. 5 (a)) and
the other concentrated in a $2.5m\times 2.5m\times 2.5m$ space (i.e., compact
data, see Fig. 5 (b)). The sparse and compact data are inserted to an existing
incremental k-d tree of different size but all sampled in the workspace. Fig.
5(c) shows the running time of sparse and compact point-wise insertion on k-d
trees of different size. As expected, the incremental updates for compact data
are slower than the sparse one because re-building are more likely to be
triggered when inserting a large amount of points into a small sub-tree of a
k-d tree.

###  V-B LiDAR Inertial-Odometry and Mapping

We test our developed ikd-Tree in an actual robotic application: lidar-
inertial odometry (and mapping) presented in [3, 4, 5, 6, 7, 8]. In this
application, k-d tree-based nearest points search is crucial to match a point
in a new LiDAR scan to its correspondences in the map (or the previous scan).
Since the map is dynamically growing by matching and merging new scans, the
k-d tree has to be re-built every time a new scan is merged. Existing methods
[3, 4, 5, 6, 7, 8] commonly used static kd-tree from PCL and rebuilds the
entire tree based on all points in the map (or a submap). This leads to a
significant computation costs severely limiting the map update rate (e.g.,
from $1Hz$ [5, 6, 7] to $10Hz$ [8]).

In this experiment, we replace the static k-d tree (build, update, and query)
by our ikd-Tree, which enables incremental update of the map by updating the
new points only. We test ikd-Tree on the lidar-inertial mapping package
FAST_LIO in [8]222https://github.com/hku-mars/FAST_LIO. The experiment is
conducted on a real-world outdoor scene using a Livox Avia
LiDAR333https://www.livoxtech.com/de/avia [30] with 70°FoV and a high frame
rate of 100 $Hz$. All the algorithm is running on the DJI Manifold 2-C444
https://www.dji.com/manifold-2/specs with a 1.8 $GHz$ quad-core Intel i7-8550U
CPU and 8 $GB$ RAM.

Figure 6: Fig. (a) shows the average running time of fusing one new lidar scan
in FAST_LIO using the ikd-Tree and a static k-d tree. Fig. (b) shows time for
nearest search, incremental updates, and total time in fusing one lidar scan.
Fig. (c) shows the balance property after re-building on main thread. Figure
7: Mapping Result of the Main Building, University of Hong Kong. The green
line is the path of the lidar computed by FAST_LIO.

The time of fusing a new lidar scan in FAST_LIO is shown in Fig. 6(a). The
time is the averaged time of the most recent 100 scans. It is seen that the
ikd-Tree achieves a nearly constant time performance around 1.6 $ms$, which
fundamentally enables a mapping rate up to $100Hz$ (against $10Hz$ presented
in the original work [8] using static k-d tree). On the other hand, the time
with the static k-d tree is overall increasing linearly, and decreases
occasionally due to the small overlap between the lidar current FoV and the
map. The resultant processing time with the static k-d tree exceeds 10 $ms$
from 366$s$ on, which is more than the collection time of one lidar scan.

The time for fusing a new lidar scan consists of many operations, such as
point registration, state estimation, and kd-tree related operations
(including queries and update). The time breakdown of kd-tree related
operations is shown in Fig. 6(b). The average time of incremental updates for
ikd-Tree is 0.23 $ms$ which is only 4% of that using an static k-d tree (5.71
$ms$). The average time of nearest search using the ikd-Tree and an static k-d
tree are at the same level.

Furthermore, Fig. 6(c) investigates the balancing property of the incremental
kd-tree by examining the two criterions $\alpha_{bal}$ and $\alpha_{del}$,
which are defined as:

$\displaystyle\alpha_{bal}(T)$
$\displaystyle=\frac{\max\Big{\\{}S(T.leftson),S(T.rightson)\Big{\\}}}{S(T)-1}$
(4) $\displaystyle\alpha_{del}(T)$ $\displaystyle=\frac{I(T)}{S(T)}$

As expected, the two criterion are maintained below the prescribed thresholds
(see Table II) due to re-building, indicating that the kd-tree is well-
balanced through the incremental updates. The peaks over the thresholds is
resulted from parallely re-building, which drop quickly when the re-building
is done. Finally, Fig. 7 shows the $100Hz$ mapping results.

##  VI Conclusion

This paper proposed an efficient data structure, ikd-Tree, to incrementally
update a k-d tree in robotic applications. The ikd-Tree supports incremental
operations in robotics while maintaining balanced by partial re-building. We
provided a complete analysis of time and space complexity to prove the high
efficiency of the proposed dynamic structure. The ikd-Tree was tested on a
randomized experiment and an outdoor LiDAR odometry and mapping experiment. In
all tests, the proposed data structure achieves two orders of magnitude higher
efficiency.

## References

  * [1] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” _Communications of the ACM_ , vol. 18, no. 9, pp. 509–517, 1975\.
  * [2] J. H. Friedman, J. L. Bentley, and R. A. Finkel, _An algorithm for finding best matches in logarithmic time_. Department of Computer Science, Stanford University, 1975.
  * [3] A. Nuchter, K. Lingemann, and J. Hertzberg, “Cached kd tree search for icp algorithms,” in _Sixth International Conference on 3-D Digital Imaging and Modeling (3DIM 2007)_. IEEE, 2007, pp. 419–426.
  * [4] A. Segal, D. Haehnel, and S. Thrun, “Generalized-icp.” in _Robotics: science and systems_ , vol. 2, no. 4. Seattle, WA, 2009, p. 435.
  * [5] J. Zhang and S. Singh, “Loam: Lidar odometry and mapping in real-time.” in _Robotics: Science and Systems_ , vol. 2, no. 9, 2014.
  * [6] T. Shan and B. Englot, “Lego-loam: Lightweight and ground-optimized lidar odometry and mapping on variable terrain,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 4758–4765.
  * [7] J. Lin and F. Zhang, “Loam livox: A fast, robust, high-precision lidar odometry and mapping package for lidars of small fov,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 3126–3131.
  * [8] W. Xu and F. Zhang, “Fast-lio: A fast, robust lidar-inertial odometry package by tightly-coupled iterated kalman filter,” _arXiv preprint arXiv:2010.08196_ , 2020.
  * [9] J. Ichnowski and R. Alterovitz, “Fast nearest neighbor search in se (3) for sampling-based motion planning,” in _Algorithmic Foundations of Robotics XI_. Springer, 2015, pp. 197–214.
  * [10] F. Gao and S. Shen, “Online quadrotor trajectory generation and autonomous navigation on point clouds,” in _2016 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR)_. IEEE, 2016, pp. 139–146.
  * [11] B. T. Lopez and J. P. How, “Aggressive 3-d collision avoidance for high-speed navigation.” in _ICRA_ , 2017, pp. 5759–5765.
  * [12] P. R. Florence, J. Carter, J. Ware, and R. Tedrake, “Nanomap: Fast, uncertainty-aware proximity queries with lazy search over local 3d data,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 7631–7638.
  * [13] F. Gao, W. Wu, W. Gao, and S. Shen, “Flying on point clouds: Online trajectory generation and autonomous navigation for quadrotors in cluttered environments,” _Journal of Field Robotics_ , vol. 36, no. 4, pp. 710–733, 2019.
  * [14] J. Ji, Z. Wang, Y. Wang, C. Xu, and F. Gao, “Mapless-planner: A robust and fast planning framework for aggressive autonomous flight without map fusion,” _arXiv preprint arXiv:2011.03975_ , 2020.
  * [15] R. B. Rusu and S. Cousins, “3d is here: Point cloud library (pcl),” in _2011 IEEE international conference on robotics and automation_. IEEE, 2011, pp. 1–4.
  * [16] R. Bayer, “Symmetric binary b-trees: Data structure and maintenance algorithms,” _Acta informatica_ , vol. 1, no. 4, pp. 290–306, 1972.
  * [17] C. R. Aragon and R. Seidel, “Randomized search trees,” in _FOCS_ , vol. 30, 1989, pp. 540–545.
  * [18] D. D. Sleator and R. E. Tarjan, “Self-adjusting binary search trees,” _Journal of the ACM (JACM)_ , vol. 32, no. 3, pp. 652–686, 1985.
  * [19] W. Hunt, W. R. Mark, and G. Stoll, “Fast kd-tree construction with an adaptive error-bounded heuristic,” in _2006 IEEE Symposium on Interactive Ray Tracing_. IEEE, 2006, pp. 81–88.
  * [20] S. Popov, J. Gunther, H.-P. Seidel, and P. Slusallek, “Experiences with streaming construction of sah kd-trees,” in _2006 IEEE Symposium on Interactive Ray Tracing_. IEEE, 2006, pp. 89–94.
  * [21] M. Shevtsov, A. Soupikov, and A. Kapustin, “Highly parallel fast kd-tree construction for interactive ray tracing of dynamic scenes,” _Computer Graphics Forum_ , vol. 26, no. 3, pp. 395–404, 2007.
  * [22] K. Zhou, Q. Hou, R. Wang, and B. Guo, “Real-time kd-tree construction on graphics hardware,” _ACM Transactions on Graphics_ , vol. 27, no. 5, pp. 1–11, 2008.
  * [23] J. L. Bentley and J. B. Saxe, “Decomposable searching problems i: Static-to-dynamic transformation,” _J. algorithms_ , vol. 1, no. 4, pp. 301–358, 1980.
  * [24] I. Galperin and R. L. Rivest, “Scapegoat trees.” in _SODA_ , vol. 93, 1993, pp. 165–174.
  * [25] O. Procopiuc, P. K. Agarwal, L. Arge, and J. S. Vitter, “Bkd-tree: A dynamic scalable kd-tree,” in _International Symposium on Spatial and Temporal Databases_. Springer, 2003, pp. 46–65.
  * [26] J. T. Robinson, “The kdb-tree: a search structure for large multidimensional dynamic indexes,” in _Proceedings of the 1981 ACM SIGMOD international conference on Management of data_ , 1981, pp. 10–18.
  * [27] M. Muja and D. G. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration.” _VISAPP (1)_ , vol. 2, no. 331-340, p. 2, 2009\.
  * [28] M. Muja and D. Lowe, “Flann-fast library for approximate nearest neighbors user manual,” _Computer Science Department, University of British Columbia, Vancouver, BC, Canada_ , 2009.
  * [29] P. Chanzy, L. Devroye, and C. Zamora-Cura, “Analysis of range search for random kd trees,” _Acta informatica_ , vol. 37, no. 4-5, pp. 355–383, 2001\.
  * [30] Z. Liu, F. Zhang, and X. Hong, “Low-cost retina-like robotic lidars based on incommensurable scanning,” _arXiv preprint arXiv:2006.11034_ , 2020.