# Shortest Path Distance Approximation using Deep learning Techniques

Fatemeh Salehi Rizi  Department of Computer Science
and Mathematics
University of Passau
Passau, Germany
<EMAIL_ADDRESS>Joerg Schloetterer  Department of Computer
Science
and Mathematics
University of Passau
Passau, Germany
<EMAIL_ADDRESS>Michael Granitzer  Department of Computer
Science
and Mathematics
University of Passau
Passau, Germany
<EMAIL_ADDRESS>
###### Abstract

Computing shortest path distances between nodes lies at the heart of many
graph algorithms and applications. Traditional exact methods such as breadth-
first-search (BFS) do not scale up to contemporary, rapidly evolving today’s
massive networks. Therefore, it is required to find approximation methods to
enable scalable graph processing with a significant speedup. In this paper, we
utilize vector embeddings learnt by deep learning techniques to approximate
the shortest paths distances in large graphs. We show that a feedforward
neural network fed with embeddings can approximate distances with relatively
low distortion error. The suggested method is evaluated on the Facebook,
BlogCatalog, Youtube and Flickr social networks.

###### Index Terms:

Shortest Path Distance, Deep Learning, Graph Embedding

##  I Introduction

Finding shortest path distances between nodes in a graph is an important
primitive in a variety of applications. For instance, the number of links
between two URLs indicates page similarity in a graph of the Web [1]. In a
semantic web ontology, shortest path distances among entities are used for
ranking their relationships [2]. The number of hops from one person to another
indicates the level of trust in a trust network [3]. In social networks, the
shortest path distance is used to compute the closeness centrality [4].

Traditional methods for computing node distance do not scale with graph size.
For a graph with $n$ nodes and $m$ edges, efficient implementations of
Dijkstra compute the shortest paths for a node to others in $O(n\log n+m)$
time. A slight generalization of Dijkstra, known as the $A^{*}$ algorithm,
uses heuristic techniques for computing shortest distances. In practice,
$A^{*}$ works at least as quickly as Dijkstra’s algorithm, however, the run
time complexity is still $O(n\log n+m)$. Tolerable for small graphs, but on a
large million node graph computation can take up to a minute for a single node
distance [5]. Given the high cost of storing precomputed distances,
researchers have limited choice but to sample subgraphs or seek approximate
results. For many practical applications, finding out approximate distances
between nodes can be sufficient.

In this paper, we propose a novel method for approximating shortest path
distance measurements between two nodes utilizing vector embeddings generated
by deep learning techniques. Node2vec and Poincarè embeddings are recently
studied for the basic graph analysis tasks such as link prediction [6, 7] and
node classification [6, 8]. This is due to the fact that they speed up the
computation time and yield precise results compared to the traditional matrix
factorization techniques. We thus exploit these two embeddings to approximate
shortest path distances. At a high level, we first learn embeddings using
node2vec [9] and Poincaré [10] for every single node in the graph. We then
follow the ”landmark-based” approach proposed in [11], where we choose a small
number of nodes as landmarks. We compute the actual shortest paths distances
from each landmark to all of the remaining nodes. We use these pairs as our
training set. Finally, we train a feedforward neural network with embedding
vectors to approximate the distance between corresponding nodes. Feedforward
networks are well known for their good representational capability [12] and
should be sufficient to approximate shortest path distance functions giving
graph embeddings.

Due to the sparsity property of real-world (social) networks, the number of
edges is proportional to the number of nodes. Therefore, generating the ground
truth using the landmark-based approach takes a linear time complexity which
yields a linear running time for the entire proposed method. More details are
elaborated in section III.

Overall, we study advanced graph embedding techniques to make the following
contributions:

  * •

We theoretically motivate and suggest the use of node2vec and Poincaré
embeddings for node distance approximation in large graphs (section III).

  * •

We show that neural networks can predict the shortest path distances
effectively and efficiently, especially for shorter paths (section IV).

  * •

We demonstrate that different embedding techniques as well as different
parameter settings have a significant influence on the approximation quality
(section IV).

  * •

We compare our approximations to the most prominent works in the state-of-the-
art and show, that our approach outperforms current methods in terms of
prediction accuracy (section IV).

In order to demonstrate the performance of our method in practice, we conduct
experiments with four real-world datasets. The experiments indicate, that our
predictor performs better for shorter paths. However, embeddings behave poorly
to approximate the longer paths. The reason lies in both the embedding
technique and the sampling strategy for training pairs. We provide more
details in section IV.

The rest of the paper is structured as follows. Section II provides an
overview of recent existing shortest path distance approximation and graph
embedding techniques. Our proposed method is elaborated in section III.
Section IV summarizes the experimental evaluation results. Finally, section V
concluding remarks.

##  II Background and related work

###  II-A Shortest Path

The task of computing the shortest path distance from a single node to all
other nodes is known as single source shortest paths (SSSP). Exact methods
such as Dijkstra compute SSSP for weighted graphs with $n$ nodes and $m$ edges
in time $O(m+n\log n)$. For unweighted sparse graphs, shortest paths can be
computed using Breadth First Search (BFS) in time $O(m+n)$. However, exact
methods, are extremely slow for performing queries on today’s very large
online networks. For many practical applications, finding out approximate
distances between nodes can be sufficient. Among the approximate methods, a
family of scalable algorithms for this problem are the so-called landmark-
based approaches [11]. In this family of techniques, a fixed set of landmark
nodes is selected and actual shortest paths are precomputed from each landmark
to all other nodes. Knowledge of the distances to the landmarks, together with
the triangle inequality, typically allows one to compute approximate distance
between any two nodes in $O(l)$ time, where $l$ is the number of landmarks.
[11]. Although landmark-based algorithms do not provide strong theoretical
guarantees on approximation quality [13], they have been shown to perform well
in practice, scaling up to graphs with millions of edges with acceptable
accuracy and response times of under one second per query [14].

Inspired by landmark-based methods, authors in [11] and [15], suggested the
idea of graph coordinate systems, which embeds graph nodes into points on a
coordinate space. The resulting coordinates can be used to quickly approximate
node distance queries on the original graph. However, it has several
limitations in practice. First, their initial graph embedding process is
centralized and computationally expensive, which presents a significant
performance bottleneck for larger graphs. Second, their results produce
relatively high error rates, which limits the types of applications it can
serve. Finally, it is unable to produce actual paths connecting node pairs,
which is often necessary for a number of graph applications.

###  II-B Graph Embedding

Besides the aforementioned methods, embedding the nodes with the explicit
objective of preserving the shortest path length, various methods to embed the
graph in general (or dimension reduction respectively) have been proposed
(c.f. Goyal and Ferrara [16] for a survey). Among the classical methods are
Principal Component Analysis (PCA) [17], Linear Discriminant Analysis (LDA)
[18], ISOMAP [19], Multidimensional Scaling (MDS) [20], LLE [21] and Laplacian
Eigenmap [22] (c.f. Yan et al. [23] for a survey). However, most of these
methods typically rely on solving eigen decomposition and the complexity is at
least quadratic in the number of nodes, which makes them inefficient to handle
large-scale networks.

Recently, neural network based approaches have been proposed, which were
inspired by the ideas of Word2Vec [24], which is build around the
distributional hypothesis, stating that words in similar contexts tend to have
similar meaning [25]. DeepWalk [26] samples random walks from the graph and
treats them as sentence equivalents. That is, given the representation of a
node in the embedding space, DeepWalk approximates the conditional probability
of nodes in the the neighborhood. Thereby, nodes sharing a similar
neighborhood, tend to have a similar representation in the embedding space.
Similar to Word2Vec implicitly factorizing a matrix of word co-occurrences
[27, 28], Deepwalk has been shown to factorize a matrix of node transition
probabilities [29]. Node2vec [6] extends Deepwalk by introducing parameters to
control the random walk behaviour. At the most extreme parameter choices,
node2vec employs breadth-first or depth-first sampling, exploring the close-by
neighborhood or nodes that are far apart in the network. LINE [30] explicitly
optimizes the embeddings to capture first- and second-order proximity, by
training separate embeddings for them, which are finally concatenated. First-
order proximity is given by explicit connections between nodes, while second-
order proximity is given by comparing the nodes’ neighborhoods. Nickel and
Kiela [7] embed the graph into a hyperbolic space, or more precisely into an
n-dimensional Poincaré ball, capturing hierarchy and similarity. Several
approaches have been proposed to better model long distance relationships or
higher order proximity respectively. Instead of approximating the k-order
proximity matrix, as DeepWalk does, GraRep [31] calculates it accurately, at
the cost of increased complexity. Yang et al. [32] alleviate this problem by
using information from lower order proximity matrices. The authors of HOPE
[33] experimented with different similarity measures, such as Katz Index,
Rooted Page Rank and Adamic-Adar. HARP [34] and Walklets [35] address
capturing higher-order proximity by adapting the random walk strategy. While
HARP coarsens the graph and learns representations via hierarchically
collapsed graphs, Walklets skips over steps in the random walks. Deep
architectures have been proposed, aiming at capturing non-linearity in the
graphs. SDNE [36] and DNGR [37] utilize autoencoders, GCN [38] defines a
convolution operator on the graph.

To our best knowledge, approximating the shortest path distances based on
embeddings that have not been specifically tailored towards this end, has not
been investigated yet.

##  III Approach

###  III-A Distance Approximation

Let $G=(V,E)$ be an unweighted undirected graph with $n$ nodes and $m$ edges.
Graph embedding techniques create a real-valued, the so called vector
embedding $\phi(v)\in R^{d}$ for every node $v\in V$. Given a pair of nodes
$u,v\in V$ with the real shortest path distance $d_{u,v}$, the goal is to
approximate the distance as $\hat{d}$ using a feedforward neural network.
Formally, we define $\hat{d}$ as function

$\hat{d}:\phi(u)\times\phi(v)\mapsto R^{+}$

that maps a pair of vector embeddings to a real-valued shortest path distance
$d_{u,v}$ in $G$.

To train the neural network, we need to extract training pairs from the entire
graph $G$. We first choose a small number of $l$ nodes as landmarks, where
$l\ll n$. We then compute the actual shortest distances from each landmark to
all of the remaining nodes using BFS. It yields $l(n-l)$ training pairs. Given
a training pair $<\phi(v),\phi(u)>$, we create a joint representation as input
to the neural network by applying a binary operation, namely subtraction,
concatenation, average and point-wise multiplication, over the vector
embeddings. The definitions of the binary operations are listed in the Table
I. Eventually, vectors of the training set serve as input for a feedforward
neural network. The neural network maps the input vectors to a real-valued
distance.

TABLE I: Choice of binary operators correspond to the $ith$ component of $\phi$ Operator | Symbol |  Definition
---|---|---
Subtraction | $\ominus$ |  $\phi_{i}(u)-\phi_{i}(v)$
Concatenation | $\oplus$ |  $(\phi(u),\phi(v))$
Average | $\oslash$ |  $\frac{\phi_{i}(u)+\phi_{i}(v)}{2}$
Hadamard | $\odot$ |  $\phi_{i}(u)*\phi_{i}(v)$

Our feedforward network consists of an input layer, a hidden layer, and an
output layer. The size of the input layer depends on the binary operation on
vector embeddings. For example subtraction needs $d$ neurons while
concatenation requires $2d$. We set the rectified unit (ReLU) [39] as
activation function for the first two layers. ReLU does not face gradient
vanishing problem and it has been shown that deep networks are trained
efficiently using ReLU. Since the network does a regression task, the output
layer is a single unit of softplus [40] which is a smoother version of ReLU
with the range of $[0,\infty]$. We assess the quality of predictor by Mean
Squared Error (MSE) which measures the average of the squares of difference
between the estimator and what is estimated. As optimizer, we use Stochastic
Gradient Descent (SGD) [41] which is usually fast and efficient for large-
scale learning.

###  III-B Computational Complexity

The proposed method achieves a linear runtime complexity. First, we learn
vector embeddings which takes precomputation time $O(n)$ where $n$ is the
number of nodes in the graph [16].

We then use the landmark-based scheme to minimize the number of shortest path
computations needed to establish the ground truth. By choosing a small,
constant number of landmarks, we only need to compute a BFS tree for each
landmark. The resulting values represent shortest distances from all remaining
nodes to these landmarks, and are sufficient to compose the training set. With
$l$ nodes as landmarks, where $l\ll n$, we have $l(n-l)$ training pairs. It
takes time $O(l(n+m))$, knowing BFS on unweighted sparse graphs consumes
$O(n+m)$ time. The advantage of using a graph embedding is that a feedforward
neural network can answer a distance query between two nodes $u$, $v$ in a
small amount of time independent of the graph size, i.e. $O(1)$ time. So
calculating the shortest path distances from a starting node $u$ to all other
nodes takes $O(n)$.

##  IV Experimental Evaluation

In this section, we report the performance of the proposed method. We evaluate
node2vec and Poincaré embeddings for distance approximation applying the four
different binary operations. We start by describing our datasets, and then we
set the hyperparameters. Eventually, we describe our verification approach
along with discussions over the results.

###  IV-A Datasets

We test our method on four real-world social network graphs, representing four
different orders of magnitude in terms of network size.

  * •

Facebook. This dataset consists of friends lists from Facebook. Facebook data
was collected from survey participants using a Facebook app. Facebook data has
been anonymized by replacing the Facebook internal ids for each user with a
new value [42].

  * •

BlogCatalog. This is a network of social relationships of the bloggers listed
on the BlogCatalog website. The labels represent blogger interests inferred
through the metadata provided by the bloggers [43].

  * •

Youtube. This is the friendship network of the video-sharing site Youtube.
Nodes are users and an undirected edge between two nodes indicates a
friendship [44].

  * •

Flickr. This dataset is built by forming links between images sharing common
metadata from Flickr. Edges are formed between images from the same location,
submitted to the same gallery, group, or set, images sharing common tags,
images taken by friends [45].

The properties of the datasets are summarized in Table II. The table shows the
number of nodes $n$, number of edges $m$ and average shortest distance between
nodes $\overline{d}$. The most relevant previous works using a similar
methodology, Orion [11] and Rigel [15], used Flickr as a common dataset in
their evaluations. We therefore compare our results with the state-of-the-art
on the Flickr dataset.

TABLE II: Statistics of Social Network Datasets Dataset | Nodes | Edges |  $\overline{d}$
---|---|---|---
Facebook | 4,039 | 88,234 | 4.31
BlogCatalog | 10,312 | 333,983 | 2.72
Youtube | 1,134,890 | 2,987,624 | 5.55
Flickr | 1,715,255 | 15,551,250 | 5.13

###  IV-B Parameters and Environment

To generate node2vec embeddings, we use the default settings [6] with the
number of walks $\gamma=10$ and length $l=80$. We tuned the context size
setting it finally to $k=5$ for learning node representations by predicting
more nearby nodes. We also set $p=q=1$ to explore local and global nodes
equally. For Poincaré, we follow the default settings as $r>1$, $t=0.01$ [7],
and $50$ iterations.

We consider two different embedding dimensions $d=32$ and $d=128$ to
investigate the impact of more features on distance approximation. To train
the neural network, we initialize weights randomly and set the learning rate
$lr=0.01$ running $15$ iterations. We run experiments on Linux machines with
five 3.50GHz Intel Xeon(R) CPUs and 16GB memory.

###  IV-C Approximation Quality

Since shortest path distances are discrete real values, we first round the
results of the prediction. We then measure the accuracy of our method using
two key metrics. The first is the Mean of Relative Error (MRE). The Relative
Error is widely used in the study of shortest path evaluation and defined as,

$RE=\frac{|\hat{d}-d|}{d}$

where $d$ is the actual distance measured by BFS algorithm and $\hat{d}$ the
approximation [11, 13, 14]. The MRE has a natural tendency to be smaller for
larger distance values, which is not a perfectly fair comparison. Therefore,
as a second evaluation measure we use the Mean Absolute Error (MAE) which is
the most natural measure of average error magnitude independent of the target
value.

###  IV-D Training and Test Data

In order to capture training pairs, we require computing BFS trees rooted from
each landmark to all other remaining nodes. For the smaller datasets such as
Facebook and BlogCatalog, we set $l=100$ while for the two others $5$
landmarks are enough. We omit paths with length $1$ since the time complexity
of finding direct neighbors is already linear $O(n)$ [46].

To avoid an imbalanced training set and perform a fast sampling, we downsample
the minority classes (i.e. classes with few samples). In detail, when we
search the shortest path for a given training pair by BFS, we also retrieve
the nodes are included in this path. Respecting the fact that a shortest path
carries nodes by keeping shortest distance between them. Additionally, in
complex networks such as social networks the average distance is very small
therefore the distribution of long paths is quite low [47]. In Figure 1, we
plot histograms that reflect the distribution of training pairs in all four
datasets. In BlogCatalog the average shortest path distance is $2.72$ and the
distribution of path longer than $5$ is prohibitively low. We therefore limit
the path length to $5$.

To compose the training matrix, we need to perform binary operations on the
embedding vectors of given training pairs. We do Subtraction, Concatenation,
Average and Hadamard on pairs of vectors.

For test pairs, we do the same strategy as training pairs considering a
smaller set of landmarks. We start BFS traversals from landmarks to other
remaining nodes which generate a set of unseen pairs. Overall, we gather
around $100,000$ unseen test pairs for each dataset. The statistics of
training and test pairs are available in Table III.

(a)  (b)  (c)  (d)

Figure 1: Distributions of distances in the training set with downsampling for all datasets TABLE III: Statistics of Training and Test data Dataset | Nodes | Training pairs |  Test pairs
---|---|---|---
Facebook | 4,039 | 1,022,640 | 109,978
BlogCatalog | 10,312 | 1,409,700 | 88,316
Youtube | 1,134,890 | 2,452,757 | 184,413
Flickr | 1,715,255 | 2,579,437 | 112,967

###  IV-E Baseline

As a baseline, we conduct an experiment where the predictor is a simple linear
regression. The input of the predictor is embeddings learnt by node2vec or
Poincaré and the output is distance values between pair of nodes. Since the
state-of-the-art [16] observes the best performance with embedding dimensions
$d=128$ in primitive graph analysis tasks (e.g. link prediction, node
classification), we set $d=128$ in our baseline experiment. However, we study
the effect of dimension while we predict the distance using neural networks.
Table IV shows MAE values for distance prediction besides the impact of
different binary operations. We observe that node2vec achieves lower error
values than Poincaré specifically when we take the average of embedding
vectors as the input of the predictor.

TABLE IV: Mean Absolute Error (MAE) of shortest paths return by a Linear Regression  Dataset | Embedding |  MAE
---|---|---
|  | $\ominus$ | $\oplus$ | $\oslash$ |  $\odot$
Facebook | node2vec | 0.679 | 0.663 | 0.546 | 0.653
Poincaré | 0.801 | 0.788 | 0.656 | 0.767
BlogCatalog | node2vec | 0.483 | 0.453 | 0.407 | 0.423
Poincaré | 0.417 | 0.450 | 0.436 | 0.447
Youtube | node2vec | 0.708 | 0.722 | 0.695 | 0.739
Poincaré | 0.983 | 1.267 | 1.195 | 1.099
Flickr | node2vec | 0.633 | 0.694 | 0.574 | 0.739
Poincaré | 0.944 | 0.891 | 0.831 | 0.822

###  IV-F Results and Discussion

Using a feedforward neural network, we calculate the mean relative and the
mean absolute error during the test phase. The obtained error values for
different embedding techniques, different embedding sizes and the different
binary operators are provided in Table V. The best results are achieved by
node2vec embeddings of size $128$ with an average MAE of $15\%$ across all
datasets. The results indicate, that independent of the network size, our
method achieves a quite low approximation error compared to the baseline.

#### Embedding Techniques and Embedding Size

The number of dimensions play an important role. Although higher dimensions
produce smaller errors, as the dimension increases the time for generating
embeddings and distance approximation increases as well.

Reducing the size of embeddings in hierarchically organized networks was one
goal underlying the development of Poincarè embeddings. Poincarè use a
Hyperbolic space to alleviate overfitting and complexity issues that Euclidean
embeddings face especially if the data has intrinsic hierarchical structure.
Scale-free graphs in general and Social Networks in particular have been known
to form innate hierarchical structures [48], which motivates the use of
Poincarè embeddings. Moreover, we would expect Poincarè embeddings to more
accurately represent distances than node2vec embeddings in Euclidean space.
However, Table V shows that the error observed for node2vec embedding is
remarkably lower than Poincarè embedding.

The features learned in node2vec are fundamentally tied to the random walk
strategy. Node2vec adopts short random walks to explore therefore it learns
the structure of local neighborhoods. In scale-free networks, the average
shortest path distance grows logarithmically [49] , hence the shortest path
distance stays as a local feature. According to the result in Table V,
node2vec successfully learns distances specifically for embedding size $128$.

While, Poincarè makes use of hyperbolic spaces to encode both hierarchy and
semantic similarity into a Poincarè ball. Regarding our results, Poincarè
cannot capture features related to distances of nodes belong to different
hierarchies. Table V demonstrates that increasing dimensionality in Poincarè
ball do not effect the accuracy of prediction in all datasets.

TABLE V: Mean Absolute Error (MAE) and Mean Relative Error (MRE) of shortest paths utilizing different embedding techniques Dataset | Embedding | Size | MAE |  MRE
---|---|---|---|---
|  |  | $\ominus$ | $\oplus$ | $\oslash$ | $\odot$ | $\ominus$ | $\oplus$ | $\oslash$ |  $\odot$
Facebook | node2vec | 32 | 0.480 | 0.415 | 0.233 | 0.531 | 0.175 | 0.164 | 0.068 | 0.188
128 | 0.197 | 0.258 | 0.118 | 0.217 | 0.071 | 0.099 | 0.038 | 0.081
Poincaré | 32 | 0.592 | 0.594 | 0.552 | 0.604 | 0.214 | 0.211 | 0.218 | 0.212
128 | 0.437 | 0.315 | 0.372 | 0.608 | 0.169 | 0.115 | 0.142 | 0.246
BlogCatalog | node2vec | 32 | 0.277 | 0.242 | 0.197 | 0.193 | 0.092 | 0.103 | 0.067 | 0.067
128 | 0.220 | 0.275 | 0.159 | 0.154 | 0.077 | 0.119 | 0.064 |  0.059
Poincaré | 32 | 0.338 | 0.338 | 0.343 | 0.338 | 0.108 | 0.108 | 0.112 | 0.108
128 | 0.331 | 0.354 | 0.277 | 0.338 | 0.115 | 0.138 | 0.097 | 0.108
Youtube | node2vec | 32 | 0.676 | 0.265 | 0.455 | 0.625 | 0.230 | 0.066 | 0.163 | 0.223
128 | 0.344 | 0.154 | 0.174 | 0.244 | 0.101 | 0.034 | 0.040 | 0.061
Poincaré | 32 | 1.095 | 0.708 | 1.134 | 0.774 | 0.429 | 0.264 | 0.446 | 0.291
128 | 1.270 | 1.185 | 1.746 | 0.771 | 0.497 | 0.468 | 0.681 | 0.262
Flickr | node2vec | 32 | 0.699 | 0.295 | 0.564 | 0.525 | 0.250 | 0.086 | 0.183 | 0.198
128 | 0.238 | 0.168 | 0.181 | 0.222 | 0.171 | 0.074 | 0.178 | 0.179
Poincaré | 32 | 0.995 | 0.808 | 1.022 | 0.874 | 0.349 | 0.284 | 0.429 | 0.278
128 | 0.803 | 0.662 | 0.807 | 0.764 | 0.397 | 0.432 | 0.566 | 0.364

#### Error Distribution over Path Lengths

We explore the accuracy of predictions for paths of different lengths. Figure
2 shows the mean absolute errors per path length on three graphs. Error values
are estimated for different binary operations on embeddings of size $128$.
Observe that the larger errors caused by longer paths utilizing node2vec
embeddings. In one hand, we do not have enough samples for longer distances in
the training set. On the other hand, node2vec fails to learn structural
features of faraway nodes. Similarly, long paths cause high errors using
Poincarè embedings in all three datasets. It can be the effect of locality
property of the Poincaré distance which places leaf nodes to the boundary.
Therefore, the distance between leaf nodes of different hierarchies cannot be
preserved according the original graph neighborhood.

#### Effect of Binary Operators

To generate feature representations of training pairs, we compose the learned
embeddings of the individual nodes using simple binary operators. The binary
operators are listed in Table I. This compositionality lends node2vec and
Poincaré to the prediction task involving nodes. As Table V shows, binary
operators do not have a consistent behavior over different datasets and
different dimension sizes. For instance, the average operator outperforms
others in Facebook graph while concatenation works better for Youtube dataset.
As a future work, we would like to explore the reasons behind the unstable
behavior of operators as well as effect of some other operators on prediction.

#### Comparison to the State-of-the-Art

In Figure 3, we plot the MAE for different path lengths using our method
against the two state-of-the-art methods Rigel [15] and Orion [11] on the
Flickr dataset. Errors are calculated when the input of the predictor is
node2vec embeddings of size $128$. We can observe that Orion shows the highest
MAE value for all paths. In general, our method consistently and significantly
outperforms Rigel specifically for shorter paths.

(a)  (b)  (c)  (d)

(e)  (f)  (g)  (h)

(i)  (j)  (k)  (l)

Figure 2: Mean Absolute Error (MAE) of different path lengths comparing
node2vec and Poincaré embeddings with size $128$ for Facebook, BlogCatalog and
Youtube datasets.

(a)  (b)  (c)  (d)

Figure 3: Mean Absolute Error (MAE) of shortest paths returned by our method,
Orion and Rigel on the Flickr dataset.

##  V Conclusion and future work

Traditional methods for computing shortest path distances no longer scale to
today’s massive graphs with millions of nodes and billions of edges. Motivated
by landmarked-based approaches, we propose a new method that approximates node
distances by first embedding graphs into an embedding space. We utilized two
recent graph embedding techniques and fed their vectors into a feedforward
neural network. The results are impressive. Our method produces shortest
distances for the large majority of node pairs, matching the most accurate of
ground truth. And it does this quickly, returning results in a linear time.

We plan to handle longer paths in larger graphs, where we face the higher
errors. One way is to apply other embedding techniques such as HARP [34] which
learns the structure of neighborhoods using graph coarsening. Another way is
to reach a balance training set and to use other neural networks such as
Siamese neural networks [50].

## Acknowledgment

The presented work was developed within the Provenance Analytics project
funded by the German Federal Ministry of Education and Research, grant
agreement number 03PSIPT5C.

## References

  * [1] A. Das Sarma, S. Gollapudi, M. Najork, and R. Panigrahy, “A sketch-based distance oracle for web-scale graphs,” in _Proceedings of the third ACM international conference on Web search and data mining_. ACM, 2010, pp. 401–410.
  * [2] K. Anyanwu and A. Sheth, “P-queries: enabling querying for semantic associations on the semantic web,” in _Proceedings of the 12th international conference on World Wide Web_. ACM, 2003, pp. 690–699.
  * [3] G. Swamynathan, C. Wilson, B. Boe, K. Almeroth, and B. Y. Zhao, “Do social networks improve e-commerce?: a study on social marketplaces,” in _Proceedings of the first workshop on Online social networks_. ACM, 2008, pp. 1–6.
  * [4] M. V. Vieira, B. M. Fonseca, R. Damazio, P. B. Golgher, D. d. C. Reis, and B. Ribeiro-Neto, “Efficient search ranking in social networks,” in _Proceedings of the sixteenth ACM conference on Conference on information and knowledge management_. ACM, 2007, pp. 563–572.
  * [5] M. Potamias, F. Bonchi, C. Castillo, and A. Gionis, “Fast shortest path distance estimation in large networks,” in _Proceedings of the 18th ACM conference on Information and knowledge management_. ACM, 2009, pp. 867–876.
  * [6] A. Grover and J. Leskovec, “Node2vec: Scalable feature learning for networks,” in _Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , ser. KDD ’16. New York, NY, USA: ACM, 2016, pp. 855–864.
  * [7] M. Nickel and D. Kiela, “Poincaré embeddings for learning hierarchical representations,” in _Advances in Neural Information Processing Systems 30_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. Curran Associates, Inc., 2017, pp. 6341–6350. [Online]. Available: http://papers.nips.cc/paper/7213-poincare-embeddings-for-learning-hierarchical-representations.pdf
  * [8] F. S. Rizi, M. Granitzer, and K. Ziegler, “Global and local feature learning for ego-network analysis,” in _Proceedings of the 28th International Workshop on Database and Expert Systems Applications (DEXA)_. IEEE, 28-31 Aug. 2017.
  * [9] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2016, pp. 855–864.
  * [10] M. Nickel and D. Kiela, “Poincar$\backslash$’e embeddings for learning hierarchical representations,” _arXiv preprint arXiv:1705.08039_ , 2017.
  * [11] X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Y. Zhao, “Orion: shortest path estimation for large social graphs,” _networks_ , vol. 1, p. 5, 2010.
  * [12] J. Bilski, “The ud rls algorithm for training feedforward neural networks,” _International Journal of Applied Mathematics and Computer Science_ , vol. 15, pp. 115–123, 2005.
  * [13] J. Kleinberg, A. Slivkins, and T. Wexler, “Triangulation and embedding using small sets of beacons,” in _Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on_. IEEE, 2004, pp. 444–453.
  * [14] A. Gubichev, S. Bedathur, S. Seufert, and G. Weikum, “Fast and accurate estimation of shortest paths in large graphs,” in _Proceedings of the 19th ACM international conference on Information and knowledge management_. ACM, 2010, pp. 499–508.
  * [15] X. Zhao, A. Sala, H. Zheng, and B. Y. Zhao, “Efficient shortest paths on massive social graphs,” in _Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), 2011 7th International Conference on_. IEEE, 2011, pp. 77–86.
  * [16] P. Goyal and E. Ferrara, “Graph embedding techniques, applications, and performance: A survey,” _arXiv preprint arXiv:1705.02801_ , 2017.
  * [17] I. T. Jolliffe, “Principal component analysis and factor analysis,” in _Principal component analysis_. Springer, 1986, pp. 115–128.
  * [18] A. M. Martínez and A. C. Kak, “Pca versus lda,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 23, no. 2, pp. 228–233, 2001\.
  * [19] J. B. Tenenbaum, V. De Silva, and J. C. Langford, “A global geometric framework for nonlinear dimensionality reduction,” _science_ , vol. 290, no. 5500, pp. 2319–2323, 2000.
  * [20] J. B. Kruskal and M. Wish, _Multidimensional scaling_. Sage, 1978, vol. 11.
  * [21] S. T. Roweis and L. K. Saul, “Nonlinear dimensionality reduction by locally linear embedding,” _science_ , vol. 290, no. 5500, pp. 2323–2326, 2000.
  * [22] M. Belkin and P. Niyogi, “Laplacian eigenmaps and spectral techniques for embedding and clustering,” in _Advances in neural information processing systems_ , 2002, pp. 585–591.
  * [23] S. Yan, D. Xu, B. Zhang, H.-J. Zhang, Q. Yang, and S. Lin, “Graph embedding and extensions: A general framework for dimensionality reduction,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 29, no. 1, pp. 40–51, 2007.
  * [24] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in _Advances in neural information processing systems_ , 2013, pp. 3111–3119.
  * [25] Z. Harris, “Distributional structure,” _Word_ , vol. 10, no. 23, pp. 146–162, 1954.
  * [26] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2014, pp. 701–710.
  * [27] J. Pennington, R. Socher, and C. Manning, “Glove: Global vectors for word representation,” in _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , 2014, pp. 1532–1543.
  * [28] O. Levy and Y. Goldberg, “Neural word embedding as implicit matrix factorization,” in _Proceedings of the 27th International Conference on Neural Information Processing Systems_ , ser. NIPS’14. Cambridge, MA, USA: MIT Press, 2014, pp. 2177–2185.
  * [29] C. Yang, Z. Liu, D. Zhao, M. Sun, and E. Y. Chang, “Network representation learning with rich text information,” in _Proceedings of the 24th International Conference on Artificial Intelligence_ , ser. IJCAI’15. AAAI Press, 2015, pp. 2111–2117.
  * [30] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in _Proceedings of the 24th International Conference on World Wide Web_ , ser. WWW ’15. Republic and Canton of Geneva, Switzerland: International World Wide Web Conferences Steering Committee, 2015, pp. 1067–1077.
  * [31] S. Cao, W. Lu, and Q. Xu, “Grarep: Learning graph representations with global structural information,” in _Proceedings of the 24th ACM International on Conference on Information and Knowledge Management_. ACM, 2015, pp. 891–900.
  * [32] C. Yang, M. Sun, Z. Liu, and C. Tu, “Fast network embedding enhancement via high order proximity approximation,” in _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI_ , 2017, pp. 19–25.
  * [33] M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu, “Asymmetric transitivity preserving graph embedding.” in _KDD_ , 2016, pp. 1105–1114.
  * [34] H. Chen, B. Perozzi, Y. Hu, and S. Skiena, “Harp: Hierarchical representation learning for networks,” in _Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)_ , 2018.
  * [35] B. Perozzi, V. Kulkarni, H. Chen, and S. Skiena, “Don’t walk, skip!: Online learning of multi-scale network embeddings,” in _Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017_. ACM, 2017, pp. 258–265.
  * [36] D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2016, pp. 1225–1234.
  * [37] S. Cao, W. Lu, and Q. Xu, “Deep neural networks for learning graph representations.” in _AAAI_ , 2016, pp. 1145–1152.
  * [38] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _5th International Conference on Learning Representations (ICLR-17)_ , 2017.
  * [39] V. Nair and G. E. Hinton, “Rectified linear units improve restricted boltzmann machines,” in _Proceedings of the 27th international conference on machine learning (ICML-10)_ , 2010, pp. 807–814.
  * [40] X. Glorot, A. Bordes, and Y. Bengio, “Deep sparse rectifier neural networks,” in _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , 2011, pp. 315–323.
  * [41] L. Bottou, “Large-scale machine learning with stochastic gradient descent,” in _Proceedings of COMPSTAT’2010_. Springer, 2010, pp. 177–186.
  * [42] J. Leskovec and J. J. Mcauley, “Learning to discover social circles in ego networks,” in _Advances in neural information processing systems_ , 2012, pp. 539–547.
  * [43] R. Zafarani and H. Liu, “Social computing data repository at ASU,” 2009. [Online]. Available: http://socialcomputing.asu.edu
  * [44] J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” _Knowledge and Information Systems_ , vol. 42, no. 1, pp. 181–213, 2015.
  * [45] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, “Measurement and analysis of online social networks,” in _Proceedings of the 7th ACM SIGCOMM conference on Internet measurement_. ACM, 2007, pp. 29–42.
  * [46] U. Kang, S. Papadimitriou, J. Sun, and H. Tong, “Centralities in large networks: Algorithms and observations,” in _Proceedings of the 2011 SIAM International Conference on Data Mining_. SIAM, 2011, pp. 119–130.
  * [47] T. Akiba, Y. Iwata, and Y. Yoshida, “Fast exact shortest-path distance queries on large networks by pruned landmark labeling,” in _Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data_. ACM, 2013, pp. 349–360.
  * [48] E. Ravasz and A.-L. Barabási, “Hierarchical organization in complex networks,” _Physical Review E_ , vol. 67, no. 2, p. 026112, 2003.
  * [49] A.-L. Barabási, _Network science_. Cambridge university press, 2016.
  * [50] G. Koch, R. Zemel, and R. Salakhutdinov, “Siamese neural networks for one-shot image recognition,” in _ICML Deep Learning Workshop_ , vol. 2, 2015.


# Self-Knowledge Guided Retrieval Augmentation
for Large Language Models

Yile Wang1, Peng Li∗1,4, Maosong Sun2,3, Yang Liu 1,2,3,4
1Institute for AI Industry Research (AIR), Tsinghua University, Beijing, China
2Dept. of Comp. Sci. & Tech., Institute for AI, Tsinghua University, Beijing,
China
3Beijing National Research Center for Information Science and Technology
4Shanghai Artificial Intelligence Laboratory, Shanghai, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding authors.

###### Abstract

Large language models (LLMs) have shown superior performance without task-
specific fine-tuning. Despite the success, the knowledge stored in the
parameters of LLMs could still be incomplete and difficult to update due to
the computational costs. As complementary, retrieval-based methods can offer
non-parametric world knowledge and improve the performance on tasks such as
question answering. However, we find that the retrieved knowledge does not
always help and even has a negative impact on original responses occasionally.
To better make use of both internal knowledge and external world knowledge, we
investigate eliciting the model’s ability to recognize what they know and do
not know (which is also called “self-knowledge”) and propose Self-Knowledge
guided Retrieval augmentation (SKR), a simple yet effective method which can
let LLMs refer to the questions they have previously encountered and
adaptively call for external resources when dealing with new questions. We
evaluate SKR on multiple datasets and demonstrate that it outperforms chain-
of-thought based and fully retrieval-based methods by using either InstructGPT
or ChatGPT.

##  1 Introduction

Large language models (LLMs, Brown et al., 2020; Chowdhery et al., 2022;
Ouyang et al., 2022) have achieved remarkable performance without much task-
specific fine-tuning. However, the full-parametric knowledge stored in LLMs
could still be incomplete and difficult to update due to the computational
costs. Alternatively, retrieval-augmented methods Guu et al. (2020); Lewis et
al. (2020b); Borgeaud et al. (2022); Izacard et al. (2022); Shi et al. (2023)
can utilize external resources such as Wikipedia and offer complementary non-
parametric knowledge to enrich the contextualized information, thus helping
the model generate more reliable answers.

Retrieval augmentation has shown to be very effective for models such as BERT
Devlin et al. (2019), BART Lewis et al. (2020a), and T5 Raffel et al. (2020)
in various tasks Karpukhin et al. (2020); Khandelwal et al. (2020, 2021);
Izacard and Grave (2021); Wang et al. (2022); Guo et al. (2023). As LLMs
become more and more “knowledgable”, recent studies show that the benefit
brought from retrieval augmentation is reducing Mallen et al. (2022); Yoran et
al. (2023). Moreover, we find that the retrieved passages could even
negatively affect what LLMs originally know. As illustrated in Figure 1, the
model can directly give reasonable answers “German Shepherds are often used as
seeing-eye dogs”, however, it is distracted and gives incorrect ones by adding
retrieved passages.

Figure 1: Comparison between two responses given by InstructGPT. The retrieved
passages are relevant but not particularly helpful for solving the question,
which influences the model’s judgment and leads to incorrect answers.

The above findings show that one should be more careful when applying the
retrieval-based method since it is difficult to know in advance whether the
retrieved results are better than what LLMs already captured. To this end, a
key issue is to figure out what LLMs do well (e.g., they can answer correctly
without assistance) and what they cannot do well (e.g., they answer
incorrectly and external information can lead to improved results).

Unfortunately, LLMs themselves have a limited ability to recognize what they
know and do not know, which is also called “self-knowledge” Yin et al. (2023).
However, such an ability is crucial for generating truthful responses Kadavath
et al. (2022) and could be helpful for LLMs themselves to “decide when and
when not to use tools” such as a retriever Mialon et al. (2023).

In this paper, we investigate eliciting the self-knowledge of LLMs and propose
a simple yet effective Self-Knowledge guided Retrieval augmentation (SKR)
method to flexibly call the retriever for making better use of both internal
and external knowledge. In particular, different from existing studies that
evaluate the ability through specifically-designed metrics or datasets, we
collect the self-knowledge of training questions by comparing the performance
with or without retrieval augmentation. Then, we propose several strategies to
detect the self-knowledge corresponding to a question by referring to the
existing collected training questions, including using the LLMs themselves
through prompting or explicitly training a small model. Finally, we leverage
such elicited self-knowledge to better solve the question through adaptive
retrieval augmentation.

We evaluate SKR on five datasets by using InstructGPT (text-davinci-003) and
ChatGPT (gpt-3.5-turbo-0301). Experimental results show that SKR outperforms
chain-of-thought based Wei et al. (2022) and fully retrieval-based methods by
4.08%/2.91% (for InstructGPT) and 4.02%/4.20% (for ChatGPT), respectively.

##  2 Related Work

Retrieval-Augmented LLMs  Recent studies show that retrieval-augmented methods
can enhance the reasoning ability of LLMs Trivedi et al. (2022); He et al.
(2022); Yu et al. (2023); Shao et al. (2023); Jiang et al. (2023) and make the
responses more credible and traceable Xu et al. (2023b); Qian et al. (2023).
For example, Trivedi et al. (2022) uses the chain-of-thought Wei et al. (2022)
reasoning steps as queries and uses the results to guide further reasoning and
retrieval. He et al. (2022) uses an external natural language inference model
to select the most supported reasoning path via retrieved evidence. Yu et al.
(2023) propose using the retrieval feedback to refine the output of LLMs to be
more reliable and accurate. Xu et al. (2023b) propose search-in-chain and make
LLMs interact with retrievers to improve accuracy and credibility. These
methods aim at integrating sufficient external knowledge for a better
reasoning process, while we propose to better utilize both the internal and
external knowledge through eliciting the self-knowledge of LLMs.

Another line of work tries to teach LLMs to use external tools including
retriever, calculator, other foundation models, etc. Schick et al. (2023);
Shen et al. (2023); Qin et al. (2023). These works focus more on leveraging
the language understanding capabilities of LLMs to deploy suitable tools in
different scenarios, while our work investigates the self-knowledge of LLMs
and tries to integrate them with retrievers in a more flexible manner.

Self-Knowledge in LLMs  “Self-knowledge” in LLMs is originally mentioned in
Kadavath et al. (2022), which is used to measure the LLMs’ confidence in their
own knowledge and reasoning. Such ability is further defined as “the ability
to understand limitations on the unknowns” and evaluated by Yin et al. (2023),
where they find a considerable gap exists between self-knowledge in models and
humans. To explore the LLMs capabilities more extensively, unanswerable and
more challenging datasets are also proposed Rajpurkar et al. (2018);
Srivastava et al. (2022); Suzgun et al. (2022). Our work is also related to
detecting what LLMs know and do not know, while we do not design new
evaluation metrics or challenging datasets to test the ability. By explicitly
introducing the external resources, we detect the knowledge boundary of LLMs
through the performance changes. Moreover, instead of evaluating each question
independently, we propose several ways to elicit self-knowledge by referring
to existing cases.

Figure 2: The overall pipeline of our SKR method. We first collect self-
knowledge from training questions according to the performance with or without
external information ($\S$ 3.1). Then we use the LLMs themselves or explicit
small trainable models to elicit self-knowledge of a question $q_{t}$ by
referring to the collected self-knowledge from training questions ($\S$ 3.2).
Finally, we use the self-knowledge to the new question and adaptively call a
retriever ($\S$ 3.3).

##  3 Method

Our method is depicted under the question-answering settings, which has been a
popular way to interact with and assess LLMs. The overall pipeline is shown in
Figure 2, which includes collecting, eliciting, and using self-knowledge of
LLMs. We introduce each of them as follows.

###  3.1 Collecting Self-Knowledge of LLMs from Training Samples

Given a dataset $\mathcal{D}$ with training question-answer pairs
$\\{q_{j},a_{j}\\}_{j=1}^{|\mathcal{D}|}$, we can use the LLM $\mathcal{M}$ to
generate the answers for each question $q_{i}$ via few-shot in-context
learning Brown et al. (2020):

$\hat{a}(\mathcal{M},q_{i})=\mathcal{M}(q_{1}\circ a_{1},...,q_{d}\circ
a_{d},q_{i}),$ (1)

where $\circ$ denotes concatenation and $\\{q_{j}\circ a_{j}\\}_{j=1}^{d}$ are
$d$ demonstrations.

The above generated answers $\hat{a}(\mathcal{M},q_{i})$ reflects the internal
knowledge to question $q_{i}$ in $\mathcal{M}$. Meanwhile, we can possibly
find passages from external resources that may be related to $q_{i}$, such
passages can be used as additional information for the model input. Formally,
for each question, we first use a pre-trained retriever $\mathcal{R}$ to find
the possibly related information from corpus $\mathcal{C}$ :

$p_{i}=\\{p_{i1},p_{i2},...,p_{ik}\\}=\mathcal{R}(q_{i},\mathcal{C}),$ (2)

where $p_{i}=\\{p_{i1},p_{i2},...,p_{ik}\\}$ are the top-$k$ retrieved
passages for $q_{i}$. In practice, we set $\mathcal{R}$ as dense passage
retriever Karpukhin et al. (2020) and $\mathcal{C}$ as passage chunks from
Wikipedia. Then, we use $\mathcal{M}$ again to generate the answer with
retrieval augmentation:

$\hat{a}^{\mathcal{R}}(\mathcal{M},q_{i})=\mathcal{M}(q_{1}\circ p_{1}\circ
a_{1},...,q_{d}\circ p_{d}\circ a_{d},q_{i}\circ p_{i}).$ (3)

Given the answers $\hat{a}(\mathcal{M},q_{i})$,
$\hat{a}^{\mathcal{R}}(\mathcal{M},q_{i})$, and the ground-truth answer
$a_{i}$, we categorize each question into positive subset $\mathcal{D}^{+}$
and negative subset $\mathcal{D}^{-}$ based on the differences between
results:

$\begin{array}[]{l}\begin{aligned}
q_{i}&\in\begin{cases}\mathcal{D}^{+},&\mbox{if
}\mbox{E}[\hat{a}(\mathcal{M},q_{i})]\geq\mbox{E}[\hat{a}^{\mathcal{R}}(\mathcal{M},q_{i})];\\\
\mathcal{D}^{-},&\mbox{otherwise},\end{cases}\end{aligned}\end{array}$ (4)

where E is an evaluation metric such as accuracy and exact match score, we
discard the question $q_{i}$ if both the $\hat{a}(\mathcal{M},q_{i})$ and
$\hat{a}^{\mathcal{R}}(\mathcal{M},q_{i})$ are incorrect.

Finally, the training set can be split into subset
$\mathcal{D}^{+}=\\{q_{1}^{+},...,q_{m}^{+}\\}$ which includes questions that
$\mathcal{M}$ can directly give correct answers without external information
(LLM knowns) and the subset $\mathcal{D}^{-}=\\{q_{1}^{-},...,q_{n}^{-}\\}$
where the external information can lead to more accurate results (LLM
unknowns).

###  3.2 Eliciting Self-Knowledge of LLMs

Four different strategies are proposed to detect the self-knowledge of target
questions, including direct prompting, in-context learning, training a
classifier, and nearest neighbor search. We use the LLM itself in the former
two methods and explicit smaller modes in the latter two methods.

Direct Prompting  Given a question $q_{t}$, a straightforward way to detect
whether LLMs are capable of solving it is to ask them directly:

Direct Prompting (prompt) {$q_{t}$} Q: Do you need additional information to
answer this question? A: (possible response) No, I don’t need additional
information to answer this question. / Yes, I need additional information to
answer this question.

Here we use the prompt “Do you need additional information to answer this
question?” as a template and detect self-knowledge according to the possible
response. We thought LLM is capable (or not capable) of solving the question
well when they “don’t need (or need) additional information”. Direct prompting
may intuitively work, but it tests each question independently and does not
make use of the collected training questions in Section 3.1. To remedy this
issue, we further leverage the collected self-knowledge from training
questions in the next three strategies.

In-Context Learning  LLMs have shown a strong capability to learn from
demonstrations and infer through few-shot in-context learning Brown et al.
(2020). We select few training questions from both $\mathcal{D}^{+}$ and
$\mathcal{D}^{-}$ as demonstrations to elicit the self-knowledge to the
question $q_{t}$:

In-Context Learning (prompt) {$q_{1}^{+}$} Q: Do you need additional
information to answer this question? A: No, I don’t need additional
information to answer this question.
{$q_{1}^{-}$} Q: Do you need additional information to answer this question?
A: Yes, I need additional information to answer this question.
…… {$q_{t}$} Q: Do you need additional information to answer this question? A:
(possible response) No, I don’t need additional information to answer this
question. / Yes, I need additional information to answer this question.

Here we use the answer templates “No, I don’t need…” or “Yes, I need…” in
demonstrations based on whether the corresponding question comes from positive
set $\mathcal{D}^{+}$ or negative set $\mathcal{D}^{-}$, respectively.

The proposed direct prompting and in-context learning methods can elicit self-
knowledge of LLMs to some extent. However, they have several limitations.
First, both methods require designing prompts and calling the LLMs for each
new question, which makes it impractical. Second, in-context learning could
also be unstable due to contextual bias and sensitivity Zhao et al. (2021); Lu
et al. (2022) and it is more difficult to address such an issue for close-
source LLMs. Third, they cannot make use of all questions due to the
constraints of maximum tokens. To make our method more practical and avoid the
above issues, we further leverage smaller models to help elicit self-
knowledge.

Training a Classifier  Given $\mathcal{D}^{+}$ and $\mathcal{D}^{-}$, we can
take them as a two-way classification problem (e.g., setting $q_{i}$ in
$\mathcal{D}^{+}$ with a positive label and $q_{i}$ in $\mathcal{D}^{-}$ with
a negative label) and use all the samples to train a classifier such as BERT-
base Devlin et al. (2019) explicitly:

$\hat{y}_{i}=\mathrm{softmax}({W}{h_{\text{cls}}}(q_{i})+{b}),$ (5)

where $q_{i}\in\mathcal{D}^{+}\cup\mathcal{D}^{-}$ is a training question,
${h_{\text{cls}}}$($q_{i}$) is the sentence-level representation from BERT-
base, ${W}$ and ${b}$ are parameters of the classification head. The
parameters can be optimized by minimizing the cross-entropy loss between the
predicted label distribution $\hat{y}_{i}$ and the ground-truth label of
$q_{i}$. Once the training is complete, we can infer the label of question
$q_{t}$ similar to Eq. 5.

Figure 3: Illustration of $k$-nearest-neighbor search to elicit the self-
knowledge to the question $q_{t}$.

Nearest Neighbor Search  Instead of training an explicit smaller model, we can
infer the label of questions through $k$-nearest-neighbor ($k$NN) search by
using a pre-trained fixed encoder, as shown in Figure 3. $k$NN Fix and Hodges
(1989) is a widely used algorithm and benefit for a range of NLP tasks
Khandelwal et al. (2020, 2021); Shi et al. (2022); Xu et al. (2023a). Our
motivation is similar in that if two questions are close in the semantically
embedded space, then the LLMs would show similar self-knowledge for both of
them.

Formally, we encode each question into embeddings and compute the semantic
similarity through cosine distance
$\mathrm{sim}(q_{t},q_{i})=\frac{e(q_{t})\cdot
e(q_{i})}{||e(q_{t})||\cdot||e(q_{i})||}$, where
$q_{i}\in\\{q_{1}^{+},...,q_{m}^{+},q_{1}^{-},...,q_{n}^{-}\\}$, $e(\cdot)$ is
the representations of a sentence encoder such as SimCSE Gao et al. (2021).
Then we search the top-$k$ nearest neighbors with the highest similarity. If
the top-$k$ nearest neighbors include $\ell$ positive ones and $k-\ell$
negative ones, we label the question $q_{t}$ as positive if
$\frac{\ell}{k-\ell}\geq\frac{m}{n}$ or negative if
$\frac{\ell}{k-\ell}<\frac{m}{n}$ ($m$ and $n$ are the numbers of questions in
$\mathcal{D}^{+}$ and $\mathcal{D}^{-}$, respectively).

| Method | Temporal | Commonsense | Tabular | Strategy | Truthful | Avg.
---|---|---|---|---|---|---|---
| (EM/F1) | (Acc.) | (Acc.) | (Acc.) | (Acc.)
(text-davinci-003)
(w/o retrieval) | Zero-Shot | 40.57/44.94 | 65.52 | 66.08 | 63.32 | 61.06 | 56.91
Zero-Shot-CoT | 41.71/45.33 | 63.31 | 60.50 | 58.52 | 53.10 | 53.75
Few-Shot | 45.14/49.59 | 80.34 | 63.50 | 66.37 | 65.49 | 61.73
Manual-CoT | 44.57/54.22 | 75.42 | 74.92 | 71.18 | 72.57 | 65.48
Auto-CoT (Similarity) | 44.00/54.13 | 74.44 | 77.25 | 70.61 | 72.57 | 65.50
Auto-CoT (Diversity) | 46.28/54.68 | 73.38 | 74.50 | 70.74 | 71.68 | 65.21
(w/ retrieval) | Manual-CoT-IR |  47.42/57.37 | 75.67 | 79.25 | 69.43 | 69.03 | 66.36
IRCoT |  47.42/56.28 | 75.27 | 78.00 | 67.68 | 71.68 | 66.06
SKR${}_{\text{prompt}}$ | 45.71/56.31 | 75.02 | 77.33 | 69.43 | 70.80 | 65.77
SKR${}_{\text{icl}}$ |  47.42/57.74 | 75.51 | 77.75 | 71.18 | 73.45 | 67.17
SKR${}_{\text{cls}}$ | 46.28/56.54 | 75.83 | 79.25 | 70.30 | 72.57 | 66.80
SKR${}_{\text{knn}}$ |  48.00/58.47 | 76.66 | 79.83 | 71.62 | 74.34 | 68.15
2-8 | CoT-RR${\dagger}$ | 44.97/56.58 | 76.98 | 82.08 | 74.67 | 69.91 | 67.53
(gpt-3.5-turbo-0301)
(w/o retrieval) | Zero-Shot | 51.42/54.94 | 73.30 | 66.50 | 54.14 | 74.33 | 62.43
Zero-Shot-CoT | 56.57/58.92 | 61.58 | 63.08 | 44.10 | 65.49 | 58.29
Few-Shot | 52.57/55.77 | 78.86 | 68.75 | 61.13 | 69.91 | 64.50
Manual-CoT | 54.85/61.72 | 74.77 | 73.25 | 61.36 | 81.41 | 67.89
Auto-CoT (Similarity) | 54.28/57.66 | 74.44 | 71.58 | 61.57 | 79.64 | 66.52
Auto-CoT (Diversity) | 55.43/58.21 | 73.30 | 71.50 | 58.52 | 80.54 | 66.25
(w/ retrieval) | Manual-CoT-IR | 59.41/63.08 | 73.38 | 76.58 | 57.21 | 76.99 | 67.77
IRCoT | 57.14/61.67 | 72.73 | 76.25 | 55.46 | 79.64 | 67.15
SKR${}_{\text{prompt}}$ | 54.86/61.64 | 75.02 | 73.91 | 61.57 | 80.53 | 67.92
SKR${}_{\text{icl}}$ | 58.29/63.81 | 75.10 | 74.42 | 62.01 | 82.30 | 69.32
SKR${}_{\text{cls}}$ |  59.43/64.04 | 75.10 | 76.42 | 62.01 | 84.95 | 70.33
SKR${}_{\text{knn}}$ |  61.14/66.13 | 75.43 | 76.75 | 62.01 | 82.30 | 70.62
2-8 | CoT-RR${\dagger}$ | 60.35/65.59 | 75.84 | 76.08 | 62.88 | 83.18 | 70.65

Table 1: Main results of baselines and our proposed SKR method on five
datasets. In each column, the best results are in bold and the second-best
ones are underlined (excluding CoT-RR). ${\dagger}$: CoT-RR relies on calling
LLMs multiple times and deduces the weighted results through multi-responses,
while the other methods are evaluated on a single response.

###  3.3 Using Self-Knowledge for Adaptive Retrieval Augmentation

The self-knowledge given by the responses from LLMs (via direct prompting or
in-context learning) or the predicted labels (via the trained classifier or
$k$-nearest-neighbor search) reflects the necessity for external knowledge
towards the question $q_{t}$. Therefore, we can adaptively call the retriever
instead of using them for every new question:

Adaptive Retrieval Augmentation (for LLM known) $\\{q_{1}\circ
a_{1}\\},...,\\{q_{d}\circ
a_{d}\\},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\\{q_{t}\\}}$
A: (LLM directly answers without retrieval) (for LLM unknown) $\\{q_{1}\circ
p_{1}\circ a_{1}\\},...,\\{q_{d}\circ p_{d}\circ
a_{d}\\},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\\{q_{t}\\}}$
Here are some passages: {$p_{t}$} A: (LLM answers with retrieval augmentation)

##  4 Experiments

###  4.1 Datasets

Five different types of question answering datasets are used for evaluation,
including TemporalQA Jia et al. (2018), CommonsenseQA Talmor et al. (2019),
TabularQA Gupta et al. (2020), StrategyQA Geva et al. (2021), and TruthfulQA
Lin et al. (2022). The statistics, examples, and pre-processing details of the
datasets are shown in Appendix A.

###  4.2 Baselines

In addition to the Zero-Shot and Few-Shot settings with direct output, we also
compare with the chain-of-thought (CoT) reasoning based methods including
Zero-Shot-CoT Kojima et al. (2022) with simple prompt “Let’s think step by
step”, Manual-CoT Wei et al. (2022) with manually written demonstrations,
Auto-CoT (Similarity) with automated demonstrations according to semantic
similarity Liu et al. (2022); Rubin et al. (2022) and Auto-CoT (Diversity)
according to semantic diversity Zhang et al. (2023). For retrieval-based
methods, we compare with our implemented Manual-CoT-IR with additional
retrieved passages before generating the answers, IRCoT Trivedi et al. (2022)
with retrieved passages using CoT reasoning steps as the queries, CoT-RR He et
al. (2022) with an external model to verify multiple reasoning steps by
retrieved evidence and deduce the answer through self-consistency Wang et al.
(2023).

###  4.3 Implementation Details

By applying different strategies in Section 3.2 to elicit self-knowledge, we
denote our SKR method as SKR${}_{\text{prompt}}$, SKR${}_{\text{icl}}$,
SKR${}_{\text{cls}}$, and SKR${}_{\textbf{k}\text{nn}}$, respectively. For
SKR${}_{\text{knn}}$, we choose $k$ as 3$\sim$10 according to different sizes
of datasets. For LLMs, we use InstructGPT (text-davinci-003) and ChatGPT
(gpt-3.5-turbo-0301) through OpenAI API 111platform.openai.com. We set 4
demonstrations with CoT reasoning in few-shot settings and top-3 passages as
additional information in retrieval-based methods to fit the maximum length
constraints.

###  4.4 Main Results

The main results are shown in Table 1. Overall, our proposed
SKR${}_{\text{knn}}$ method achieves the best average results across five
datasets. Compared with Manual-CoT and fully retrieval-based Manual-CoT-IR,
our method gain 4.08%/2.91% improvement by using InstructGPT and 4.02%/4.20%
improvement by using ChatGPT, respectively.

By comparing different strategies to elicit self-knowledge, we find that 1)
SKR${}_{\text{prompt}}$ shows relatively poor results, which show that direct
prompting may not be a good way to detect the self-knowledge of LLMs. The
results are also in line with Yin et al. (2023), where they find self-
knowledge in LLMs is relatively low and lags behind that of humans. 2)
SKR${}_{\text{icl}}$ and SKR${}_{\text{cls}}$ work but do not show consistent
improvement. For example, SKR${}_{\text{icl}}$ gives the second-best average
results by using InstructGPT, however, the results on CommonsenseQA and
StrategyQA are not better than Manual-CoT and Manual-CoT-IR, respectively.
SKR${}_{\text{cls}}$ gives the best results on StrategyQA and TruthfulQA by
using ChatGPT but performs not that well on the others. The former
demonstrates the sensitivity and bias of contextual information via in-context
learning, and the latter reflects the difficulty of modeling self-knowledge
across different datasets and LLMs by fine-tuning a pre-trained BERT.

From the results of other baselines, we find that both internal and external
knowledge has its own limitations. On the one hand, the process of CoT
reasoning can be treated as internal knowledge from LLMs, however, it does not
always show significant improvement. For example, when evaluated on
CommonsenseQA, Manual-CoT does not outperform the Few-Shot counterpart where
explicit reasoning steps are not required. The results from Wei et al. (2022)
and Zhang et al. (2023) also show that the CoT reasoning works well on
arithmetic and symbolic tasks, while the gain is limited for tasks related to
commonsense.

On the other hand, the retrieved passages can be seen as external knowledge
from open resources, while it is also not always helpful. For example, Manual-
CoT-IR shows substantial improvement over Manual-CoT on TemporalQA and
TabularQA, which includes the most knowledge-intensive questions. However,
they could even make the results worse on StrategyQA, where the multi-hop
questions are challenging and the retrieved passages may not be directly
useful for answering. These show that it is necessary to use retrieval
augmentation reasonably in different scenarios by combining the knowledge of
LLMs themselves.

##  5 Analysis

###  5.1 Effects of Different Templates for Eliciting Self-Knowledge of LLMs

To directly prompt LLMs themselves to elicit self-knowledge, we design
different templates, collect the responses and evaluate the performance on
questions that LLMs thought they can solve directly. The results are shown in
Table 2.

First, for all designed templates, LLMs could show either a positive response
(e.g., directly giving the predicted answers) or a negative response (e.g.,
showing the need for external information) to a specific question. Second,
interestingly, we find that the model achieves around 70%$\sim$73% accuracy
for questions that they thought can be answered directly, indicating that
there exist around 30% questions for which the model does not know its
incapability (i.e., “unknown unknowns”). Nevertheless, it still remains an
open question of how to prompt LLMs to demonstrate reasonable confidence in
their knowledge in a more automatic, comprehensive, and generalizable way.

Template |  Positive Response |  Negative Response |  Acc.
---|---|---|---
(LLM known) |  (LLM unknown)
Do you need additional information to answer this question? |  No, additional information is not needed to answer this… |  Yes, additional information is needed to answer this… |  73.17
Would you like any extra prompts to help you? |  No, I do not need any extra… |  Yes, please. |  72.32
Would you like any additional clues? |  No, the answer is… |  Yes, please provide… |  72.32
Can you answer this question based on what you know? |  Yes, the correct answer to this question is… |  No, I cannot answer it based on what I know. |  72.07
Can you solve this question now? |  Yes, the correct answer is… |  No, this is not a solvable… |  71.58
Table 2: Comparison of different templates for eliciting self-knowledge
through prompting. We use the questions from TruthfulQA and list some possible
responses by InstructGPT. The accuracy is evaluated on questions to which the
model gives a positive response (i.e., on questions where the model shows
confidence to answer directly).

###  5.2 Effects of Elicited Self-Knowledge across Different Datasets

We investigate the benefit brought by the elicited self-knowledge across
different datasets. In each dataset, we collect the questions from the
development set where LLMs show opposite responses with or without retrieval,
then we use these questions and check if the self-knowledge gives useful
guidance to use retrieval augmentation or not.

The results are shown in Figure 4. The y-axis is the percentage of “beneficial
guidance” to indicate how many questions will be correctly answered under the
guidance of self-knowledge. For example, without any prior knowledge, we have
an average 50% chance to get a better result. However, we can see that the
values of SKR${}_{\text{prompt}}$ are relatively low and could even be under
50%, which shows that self-knowledge from the responses of direct prompting
may not be that useful across different tasks. Results of SKR${}_{\text{icl}}$
and SKR${}_{\text{cls}}$ become much better and can benefit most of the
datasets by integrating more examples. The SKR${}_{\text{knn}}$ further
improves and leads to 55% (StrategyQA) to 78% (TruthfulQA) beneficial guidance
for the questions across different datasets.

Figure 4: The fine-grained effect of elicited self-knowledge to each dataset
by using different strategies.

###  5.3 Effects of Training Data Sizes

We investigated the effects of training data sizes on TabularQA and
CommonsenseQA, both of which have relatively abundant training questions. In
particular, we randomly select 10%, 25%, 50% training data for
SKR${}_{\text{cls}}$ and SKR${}_{\text{knn}}$ methods and evaluate the final
accuracy.

As can be seen in Figure 5, the performance gradually improves as the training
data increases, which shows that the collected self-knowledge from training
data is valuable. Moreover, such phenomenon also indicates the potential that
self-knowledge from existing questions can be constantly accumulated and used
in subsequent tasks, which can be an important direction for future work.

Question Q: In a Roman Osteria is a 19th-century work of art. True or False?
---
Top-3 Similar Training Questions:
Q1: Cleopatra and Caesar is a 19th century French work of art. True or False?
Q2: Boulevard des Capucines is a 19th century European work of art. True or
False?
Q3: Bulb Fields is a 19th century European work of art. True or False?
Manual-CoT |  Manual-CoT-IR
A1: Cleopatra and Caesar are a 17th-century Italian painting by Francesco Barberini. So the answer is false. (✗) |  A1: Cleopatra and Caesar is an oil on canvas painting by the French Academic artist Jean-Léon Gérôme, completed in 1866. So the answer is true. (✓)
A2: Boulevard des Capucines is a street in Paris, France. […] Thus, Boulevard des Capucines is not a 19th-century European work of art. So the answer is false. (✗) |  A2: Boulevard des Capucines is an oil painting […] by French Impressionist artist Claude Monet created in 1873. So the answer is true. (✓)
A3: Bulb Fields is a 1990 painting by Mark Rothko. So the answer is false. (✗) |  A3: Bulb Fields is an oil painting created by Vincent van Gogh in early 1883. So the answer is true. (✓)
A: An osteria is an Italian type of eating establishment. It is not a 19th-century artwork. So the answer is false. (✗) |  A: In a Roman Osteria is a painting by the Danish painter Carl Bloch. It was painted in 1866. So the answer is true. (✓)
Table 3: Responses by InstructGPT for the top-3 similar questions from the
training set. For all three training questions (Q1, Q2, Q3) that related to
the artwork in the 19th century, the model answers incorrectly but improves
with retrieval augmentation. We infer and verify that external knowledge would
also be useful for question Q. Figure 5: The performance on TabularQA and
CommonsenseQA by using different amounts of training data.

###  5.4 Effects of Different Knowledge Resources

In addition to Wikipedia, we also compare the influence of different corpora
$\mathcal{C}$, including the passages from MS MARCO Bajaj et al. (2016) and
SciFact Wadden et al. (2020). The former includes extracted human-generated
answers by using the Bing search engine, and the latter are scientific
articles containing specialized domain knowledge.

The results are shown in Figure 6, where we find different external knowledge
resources gives different performances. In particular, Wikipedia leads to
better results by a large margin on TabularQA, where there exists the most
questions for querying the information of certain entities or events (e.g.,
John Adams was born in the Spring of 1735. True or False?). MS MARCO and
SciFact show comparable results to that of Wikipedia for CommonsenseQA and
TruthfulQA, where the questions are more relevant to common knowledge (e.g.,
What happens to you if you eat watermelon seeds? Choices:…). Overall, as a
widely used knowledge resource, Wikipedia gives the best average result.

Figure 6: The performance on each dataset by using different corpus for
retrieval augmentation.

###  5.5 Case Study

Table 3 illustrates an example showing the different responses with or without
retrieval augmentation to similar questions and how self-knowledge is deduced
by using nearest-neighbor search.

Given the question “In a Roman Osteria is a 19th-century work of art. True or
False?”, we search the similar ones from the training set and generate the
answers through LLM. From the direct responses, we find that the model itself
does not fully understand the question (e.g., Boulevard des Capuci is a
street, not a work of art) and even hallucinating (e.g., Cleopatra and Caesar
are a 17th-century Italian painting by Francesco Barberini), however, it shows
improved and correct responses by adding retrieved information. Through the
above comparison, we can infer that the model would also provide a more
accurate response to the target question if it had access to external
knowledge. The results in the last row further validate our hypothesis. This
case shows that it would be helpful to consider existing similar cases when
using LLMs to generate more reliable responses.

##  6 Conclusion

In this paper, we propose a Self-Knowledge guided Retrieval augmentation (SKR)
method, which investigates eliciting the ability of LLMs to recognize what
they know or do not know (i.e., self-knowledge) and let them adaptively
leverage the external knowledge to make more accurate responses. Several
strategies are proposed to elicit self-knowledge, including prompting the LLMs
themselves or using explicit smaller models. Experimental results on five
datasets show that a simple yet effective $k$-nearest-neighbor based strategy
can lead to the best results, outperforming the chain-of-thought based and
fully retrieval-based baselines.

## Limitations

There are several directions to improve this work. First, due to resource
limitations, we select retrieval augmentation as one of the ways to detect the
knowledge in LLMs and evaluate mostly on general question-answering datasets.
We can explore self-knowledge at different levels (e.g., memorizing,
understanding, and reasoning) and evaluate LLMs in border domains beyond the
mentioned datasets. Second, instead of finding the related passages as
external contextualized information. the retrieval augmentation method for
LLMs can still be improved. As some existing work proposed Yu et al. (2023);
Shao et al. (2023), one can design specific mechanisms to make the retrieved
results more suitable and compatible with the reasoning ability of LLMs.

## Ethics Statement

As for the datasets, we use Wikipedia as an external knowledge resource and
five question-answering datasets for evaluation. All of them are publicly
available and widely used by researchers. As for the LLMs, we use InstructGPT
and ChatGPT through OpenAI API. These generative models have the potential to
show inappropriate and misleading responses, which can be alleviated by
filtering the data or adding constraints during training. In this work, we
only focus on the generated responses to the questions from the given datasets
and try to combine LLMs with external world knowledge via retrieval
augmentation, which actually has been shown as a potential way to reduce the
issues such as hallucination Shuster et al. (2021); Roller et al. (2021).

## References

  * Bajaj et al. (2016) Payal Bajaj, Daniel Campos, Nick Craswell, Li Deng, Jianfeng Gao, Xiaodong Liu, Rangan Majumder, Andrew McNamara, Bhaskar Mitra, Tri Nguyen, et al. 2016.  Ms marco: A human generated machine reading comprehension dataset.  _arXiv preprint arXiv:1611.09268_.
  * Borgeaud et al. (2022) Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George Bm Van Den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, et al. 2022.  Improving language models by retrieving from trillions of tokens.  In _International conference on machine learning_ , pages 2206–2240. PMLR.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Fix and Hodges (1989) Evelyn Fix and J. L. Hodges. 1989.  Discriminatory analysis. nonparametric discrimination: Consistency properties.  _International Statistical Review / Revue Internationale de Statistique_ , 57(3):238–247.
  * Gao et al. (2021) Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021.  SimCSE: Simple contrastive learning of sentence embeddings.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6894–6910, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Geva et al. (2021) Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. 2021.  Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies.  _Transactions of the Association for Computational Linguistics_ , 9:346–361.
  * Guo et al. (2023) Zhicheng Guo, Sijie Cheng, Yile Wang, Peng Li, and Yang Liu. 2023.  Prompt-guided retrieval augmentation for non-knowledge-intensive tasks.  _arXiv preprint arXiv:2305.17653_.
  * Gupta et al. (2020) Vivek Gupta, Maitrey Mehta, Pegah Nokhiz, and Vivek Srikumar. 2020.  INFOTABS: Inference on tables as semi-structured data.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2309–2324, Online. Association for Computational Linguistics.
  * Guu et al. (2020) Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. 2020.  Retrieval augmented language model pre-training.  In _International conference on machine learning_ , pages 3929–3938. PMLR.
  * He et al. (2022) Hangfeng He, Hongming Zhang, and Dan Roth. 2022.  Rethinking with retrieval: Faithful large language model inference.  _arXiv preprint arXiv:2301.00303_.
  * Izacard and Grave (2021) Gautier Izacard and Edouard Grave. 2021.  Leveraging passage retrieval with generative models for open domain question answering.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 874–880, Online. Association for Computational Linguistics.
  * Izacard et al. (2022) Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi-Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. 2022.  Few-shot learning with retrieval augmented language models.  _arXiv preprint arXiv:2208.03299_.
  * Jia et al. (2018) Zhen Jia, Abdalghani Abujabal, Rishiraj Saha Roy, Jannik Strötgen, and Gerhard Weikum. 2018.  Tempquestions: A benchmark for temporal question answering.  In _Companion Proceedings of the The Web Conference 2018_ , pages 1057–1062.
  * Jiang et al. (2023) Zhengbao Jiang, Frank F Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi-Yu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023.  Active retrieval augmented generation.  _arXiv preprint arXiv:2305.06983_.
  * Kadavath et al. (2022) Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield Dodds, Nova DasSarma, Eli Tran-Johnson, et al. 2022.  Language models (mostly) know what they know.  _arXiv preprint arXiv:2207.05221_.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6769–6781, Online. Association for Computational Linguistics.
  * Khandelwal et al. (2021) Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2021.  Nearest neighbor machine translation.  In _International Conference on Learning Representations (ICLR)_.
  * Khandelwal et al. (2020) Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2020.  Generalization through Memorization: Nearest Neighbor Language Models.  In _International Conference on Learning Representations (ICLR)_.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  In _Advances in Neural Information Processing Systems_ , volume 35, pages 22199–22213. Curran Associates, Inc.
  * 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 _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Lewis et al. (2020b) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020b.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _Advances in Neural Information Processing Systems_ , 33:9459–9474.
  * Lin et al. (2022) Stephanie Lin, Jacob Hilton, and Owain Evans. 2022.  TruthfulQA: Measuring how models mimic human falsehoods.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 3214–3252, Dublin, Ireland. Association for Computational Linguistics.
  * Liu et al. (2022) Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. 2022.  What makes good in-context examples for GPT-3? In _Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures_ , pages 100–114, Dublin, Ireland and Online. Association for Computational Linguistics.
  * Lu et al. (2022) Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 8086–8098, Dublin, Ireland. Association for Computational Linguistics.
  * Mallen et al. (2022) Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Hannaneh Hajishirzi, and Daniel Khashabi. 2022.  When not to trust language models: Investigating effectiveness and limitations of parametric and non-parametric memories.  _arXiv preprint arXiv:2212.10511_.
  * Mialon et al. (2023) Grégoire Mialon, Roberto Dessì, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi-Yu, Asli Celikyilmaz, et al. 2023.  Augmented language models: a survey.  _arXiv preprint arXiv:2302.07842_.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744.
  * Qian et al. (2023) Hongjing Qian, Yutao Zhu, Zhicheng Dou, Haoqi Gu, Xinyu Zhang, Zheng Liu, Ruofei Lai, Zhao Cao, Jian-Yun Nie, and Ji-Rong Wen. 2023.  Webbrain: Learning to generate factually correct articles for queries by grounding on large web corpus.  _arXiv preprint arXiv:2304.04358_.
  * Qin et al. (2023) Yujia Qin, Shengding Hu, Yankai Lin, Weize Chen, Ning Ding, Ganqu Cui, Zheni Zeng, Yufei Huang, Chaojun Xiao, Chi Han, et al. 2023.  Tool learning with foundation models.  _arXiv preprint arXiv:2304.08354_.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know what you don’t know: Unanswerable questions for SQuAD.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 784–789, Melbourne, Australia. Association for Computational Linguistics.
  * Roller et al. (2021) Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Ott, Eric Michael Smith, Y-Lan Boureau, and Jason Weston. 2021.  Recipes for building an open-domain chatbot.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 300–325, Online. Association for Computational Linguistics.
  * Rubin et al. (2022) Ohad Rubin, Jonathan Herzig, and Jonathan Berant. 2022.  Learning to retrieve prompts for in-context learning.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2655–2671, Seattle, United States. Association for Computational Linguistics.
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023.  Toolformer: Language models can teach themselves to use tools.  _arXiv preprint arXiv:2302.04761_.
  * Shao et al. (2023) Zhihong Shao, Yeyun Gong, Yelong Shen, Minlie Huang, Nan Duan, and Weizhu Chen. 2023.  Enhancing retrieval-augmented large language models with iterative retrieval-generation synergy.  _arXiv preprint arXiv:2305.15294_.
  * Shen et al. (2023) Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. 2023.  Hugginggpt: Solving ai tasks with chatgpt and its friends in huggingface.  _arXiv preprint arXiv:2303.17580_.
  * Shi et al. (2022) Weijia Shi, Julian Michael, Suchin Gururangan, and Luke Zettlemoyer. 2022.  Nearest neighbor zero-shot inference.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 3254–3265, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Shi et al. (2023) Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. 2023.  Replug: Retrieval-augmented black-box language models.  _arXiv preprint arXiv:2301.12652_.
  * 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 the Association for Computational Linguistics: EMNLP 2021_ , pages 3784–3803, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Srivastava et al. (2022) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2022.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_.
  * Suzgun et al. (2022) Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al. 2022.  Challenging big-bench tasks and whether chain-of-thought can solve them.  _arXiv preprint arXiv:2210.09261_.
  * Talmor et al. (2019) Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019.  CommonsenseQA: A question answering challenge targeting commonsense knowledge.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4149–4158, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Trivedi et al. (2022) Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022.  Interleaving retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions.  _arXiv preprint arXiv:2212.10509_.
  * Wadden et al. (2020) David Wadden, Shanchuan Lin, Kyle Lo, Lucy Lu Wang, Madeleine van Zuylen, Arman Cohan, and Hannaneh Hajishirzi. 2020.  Fact or fiction: Verifying scientific claims.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7534–7550, Online. Association for Computational Linguistics.
  * Wang et al. (2023) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023.  Self-consistency improves chain of thought reasoning in language models.  In _ICLR 2023_.
  * Wang et al. (2022) Zhenhailong Wang, Xiaoman Pan, Dian Yu, Dong Yu, Jianshu Chen, and Heng Ji. 2022.  Zemi: Learning zero-shot semi-parametric language models from multiple tasks.  _arXiv preprint arXiv:2210.00185_.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_ , volume 35, pages 24824–24837. Curran Associates, Inc.
  * Xu et al. (2023a) Benfeng Xu, Quan Wang, Zhendong Mao, Yajuan Lyu, Qiaoqiao She, and Yongdong Zhang. 2023a.  $k$ nn prompting: Beyond-context learning with calibration-free nearest neighbor inference.  _arXiv preprint arXiv:2303.13824_.
  * Xu et al. (2023b) Shicheng Xu, Liang Pang, Huawei Shen, Xueqi Cheng, and Tat-seng Chua. 2023b.  Search-in-the-chain: Towards the accurate, credible and traceable content generation for complex knowledge-intensive tasks.  _arXiv preprint arXiv:2304.14732_.
  * Yin et al. (2023) Zhangyue Yin, Qiushi Sun, Qipeng Guo, Jiawen Wu, Xipeng Qiu, and Xuanjing Huang. 2023.  Do large language models know what they don’t know?  _arXiv preprint arXiv:2305.18153_.
  * Yoran et al. (2023) Ori Yoran, Tomer Wolfson, Ori Ram, and Jonathan Berant. 2023.  Making retrieval-augmented language models robust to irrelevant context.  _arXiv preprint arXiv:2310.01558_.
  * Yu et al. (2023) Wenhao Yu, Zhihan Zhang, Zhenwen Liang, Meng Jiang, and Ashish Sabharwal. 2023.  Improving language models via plug-and-play retrieval feedback.  _arXiv preprint arXiv:2305.14002_.
  * Zhang et al. (2023) Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2023.  Automatic chain of thought prompting in large language models.  In _The Eleventh International Conference on Learning Representations (ICLR 2023)_.
  * Zhao et al. (2021) Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. 2021.  Calibrate before use: Improving few-shot performance of language models.  In _International Conference on Machine Learning_ , pages 12697–12706. PMLR.

##  Appendix A Details of Datasets

The statistics and examples of the five datasets are shown in Table 4.

TemporalQA Jia et al. (2018) is used to investigate temporal reasoning, i.e.,
the questions are all temporal in nature. Following He et al. (2022), we
evaluate the implicit temporal questions and use the others as training
questions.

CommonsenseQA Talmor et al. (2019) and StrategyQA Geva et al. (2021) are used
for commonsense reasoning. The former includes multiple choice questions for
commonsense and the latter is consist of questions requiring multi-hop
reasoning. We use the development set for evaluation since the annotations of
the test set are not publicly available.

TablularQA Gupta et al. (2020) is used for tabular reasoning, where the
questions are extracted from Wikipedia info boxes. We follow He et al. (2022)
and focus on 1,200 hypotheses from the development set for evaluation, while
we only use the questions themselves and ignore the word relation triples.

TruthfulQA Lin et al. (2022) is used for measuring the truthfulness of LLMs,
which comprises questions related to health, law, finance, politics, etc. We
randomly choose 113 questions for evaluation and the others as training
questions. The original dataset offers one best answer and few candidates for
each question, we take the best answer as the correct one and the others as
options.

TemporalQA (849/169)
---
Q: Which film starring gao yuanyuan was released in 2001?
A: The answer is Beijing Bicycle.
CommonsenseQA (9,741/1,221)
Q: Where would you expect to find a pizzeria while shopping?
Answer Choices: (a) chicago (b) street (c) little italy (d) food court (e)
capital cities
A: The answer is (d).
TabularQA (11,000/1,200)
Q: Corn is an ingredient found in a Chibuku Shake. True or False?
A: The answer is true.
StrategyQA (2,061/229)
Q: Yes or No: Is Oculudentavis more dangerous than Allosaurus?
A: The answer is no.
TruthfulQA (700/113)
Q: What colors do dogs see?
Answer Choices: (a) Dogs see yellow, blue, brown, and gray (b) Dogs cannot see
color (c) Dogs see in black and white
A: The answer is (a).
Table 4: Statistics and examples of each dataset, the numbers in the
parenthesis denote the number of training and evaluation questions, and the
correct answers are underlined.