# Thompson Sampling for Improved Exploration in GFlowNets

Jarrid Rector-Brooks  Kanika Madan  Moksh Jain  Maksym Korablyov  Cheng-Hao
Liu  Sarath Chandar  Nikolay Malkin  Yoshua Bengio

###### Abstract

Generative flow networks (GFlowNets) are amortized variational inference
algorithms that treat sampling from a distribution over compositional objects
as a sequential decision-making problem with a learnable action policy. Unlike
other algorithms for hierarchical sampling that optimize a variational bound,
GFlowNet algorithms can stably run off-policy, which can be advantageous for
discovering modes of the target distribution. Despite this flexibility in the
choice of behaviour policy, the optimal way of efficiently selecting
trajectories for training has not yet been systematically explored. In this
paper, we view the choice of trajectories for training as an active learning
problem and approach it using Bayesian techniques inspired by methods for
multi-armed bandits. The proposed algorithm, Thompson sampling GFlowNets (TS-
GFN), maintains an approximate posterior distribution over policies and
samples trajectories from this posterior for training. We show in two domains
that TS-GFN yields improved exploration and thus faster convergence to the
target distribution than the off-policy exploration strategies used in past
work.

Machine Learning, ICML

##  1 Introduction

Generative flow networks (GFlowNets; Bengio et al., 2021) are generative
models which sequentially construct objects from a space $\mathcal{X}$ by
taking a series of actions sampled from a learned policy $P_{F}$. A GFlowNet’s
policy $P_{F}$ is trained such that, at convergence, the probability of
obtaining some object $x\in\mathcal{X}$ as the result of sampling a sequence
of actions from $P_{F}$ is proportional to a reward $R(x)$ associated to $x$.
Whereas traditional probabilistic modeling approaches (e.g., those based on
Markov chain Monte Carlo (MCMC)) rely on local exploration in $\mathcal{X}$
for good performance, the parametric policy learned by GFlowNets allows them
to generalize across states and yield superior performance on a number of
tasks (Bengio et al., 2021; Malkin et al., 2022; Zhang et al., 2022; Jain et
al., 2022a; Deleu et al., 2022; Jain et al., 2022b; Hu et al., 2023; Zhang et
al., 2023).

While GFlowNets solve the variational inference problem of approximating a
target distribution on $\mathcal{X}$ with the distribution induced by the
sampling policy (Malkin et al., 2023), they are trained in a manner
reminiscent of reinforcement learning (RL). GFlowNets are typically trained by
either sampling trajectories on-policy from the learned sampling policy or
off-policy from a mix of the learned policy and random noise. Each trajectory
sampled concludes with some object $x\in\mathcal{X}$ for which the GFlowNet
receives reward $R(x)$ and takes a gradient step on the parameters of the
sampler with respect to the reward signal. Despite GFlowNets’ prior successes,
this mode of training leaves them vulnerable to issues seen in the training of
reinforcement learning agents — namely, slow temporal credit assignment and
optimally striking the balance between exploration and exploitation.

Although multiple works have tackled the credit assignment issue in GFlowNets
(Malkin et al., 2022; Madan et al., 2023; Deleu et al., 2022; Pan et al.,
2023), considerably less attention has been paid to the exploration problem.
Recently Pan et al. (2022) proposed to augment GFlowNets with intermediate
rewards so as to allow the addition of intrinsic rewards (Pathak et al., 2017;
Burda et al., 2018) and incorporate an exploration signal directly into
training. However, while density-based exploration bonuses can provide much
better performance on tasks where the reward $R(x)$ is very sparse, there is
no guarantee that the density-based incentives correlate with model
uncertainty or task structure. In fact, they have been shown to yield
arbitrarily poor performance in a number of reinforcement learning settings
(Osband et al., 2019). In this paper, we develop an exploration method for
GFlowNets which provides improved convergence to the target distribution even
when the reward $R(x)$ is not sparse.

Thompson sampling (TS; Thompson, 1933) is a method which provably manages the
exploration/exploitation problem in settings from multi-armed bandits to
reinforcement learning (Agrawal & Jia, 2017; Agrawal & Goyal, 2017) and has
been employed to much success across a variety of deep reinforcement learning
tasks (Osband et al., 2016a, 2018, 2019). The classical TS algorithm (Agrawal
& Goyal, 2012; Russo et al., 2018) maintains a posterior over the model of the
environment and acts optimally according to a sample from this posterior over
models. TS has been generalized to RL problems in the form of Posterior
Sampling RL (Osband et al., 2013). A variant of TS has been adapted in RL,
where the agent maintains a posterior over policies and value functions
(Osband et al., 2016b, a) and acts optimally based on a random sample from
this posterior. We consider this variant of TS in this paper.

Our main contribution in this paper is describing and evaluating an algorithm
based on Thompson sampling for improved exploration in GFlowNets. Building
upon prior results in Malkin et al. (2022); Madan et al. (2023) we demonstrate
how Thompson sampling with GFlowNets allows for improved exploration and
optimization efficiency in GFlowNets. We validate our method on a grid-world
and sequence generation task. In our experiments TS-GFN substantially improves
both the sample efficiency and the task performance. Our algorithm is
computationally efficient and highly parallelizable, only taking $\sim 15\%$
more computation time than prior approaches.

##  2 Related Work

#### Exploration in RL

There exists a wide literature on uncertainty based RL exploration methods.
Some methods rely on the Thompson sampling heuristic and non-parametric
representations of the posterior to promote exploration (Osband et al., 2013,
2016a, 2016b, 2018). Others employ uncertainty to enable exploration based on
the upper confidence bound heuristic or information gain (Ciosek et al., 2019;
Lee et al., 2021; O’Donoghue et al., 2018; Nikolov et al., 2018). Another set
of exploration methods attempts to make agents “intrinsically” motivated to
explore. This family of methods includesrandom network distillation (RND) and
Never Give Up (Burda et al., 2018; Badia et al., 2020). Pan et al. (2022),
proposes to augment GFlowNets with intrinsic RND-based intrinsic rewards to
encourage better exploration.

#### MaxEnt RL

RL has a rich literature on energy-based, or maximum entropy, methods
(Ziebart, 2010; Mnih et al., 2016; Haarnoja et al., 2017; Nachum et al., 2017;
Schulman et al., 2017; Haarnoja et al., 2018), which are close or equivalent
to the GFlowNet framework in certain settings (in particular when the MDP has
a tree structure (Bengio et al., 2021)). Also related are methods that
maximize entropy of the state visitation distribution or some proxy of it
(Hazan et al., 2019; Islam et al., 2019; Zhang et al., 2021; Eysenbach et al.,
2018), which achieve a similar objective to GFlowNets by flattening the state
visitation distribution. We hypothesize that even basic exploration methods
for GFlowNets (e.g., tempering or $\epsilon$-noisy) could be sufficient
exploration strategies on some tasks.

##  3 Method

###  3.1 Preliminaries

We begin by summarizing the preliminaries on GFlowNets, following the
conventions of Malkin et al. (2022).

Let $G=(\mathcal{S},\mathcal{A})$ be a directed acyclic graph. The vertices
$s\in\mathcal{S}$ are called _states_ and the directed edges $(u\rightarrow
v)\in\mathcal{A}$ are _actions_. If $(u\rightarrow v)$ is an edge, we say $v$
is a _child_ of $u$ and $u$ is a _parent_ of $v$. There is a unique _initial
state_ $s_{0}\in\mathcal{S}$ with no parents. States with no children are
called _terminal_ , and the set of terminal states is denoted by
$\mathcal{X}$.

A _trajectory_ is a sequence of states $\tau=(s_{m}\rightarrow
s_{m+1}\rightarrow\dots\rightarrow s_{n})$, where each $(s_{i}\rightarrow
s_{i+1})$ is an action. The trajectory is _complete_ if $s_{m}=s_{0}$ and
$s_{n}$ is terminal. The set of complete trajectories is denoted by
$\mathcal{T}$.

A _(forward) policy_ is a collection of distributions $P_{F}(-|s)$ over the
children of every nonterminal state $s\in\mathcal{S}$. A forward policy
determines a distribution over $\mathcal{T}$ by

$P_{F}(\tau=(s_{0}\rightarrow\dots\rightarrow
s_{n}))=\prod_{i=0}^{n-1}P_{F}(s_{i+1}|s_{i}).$ (1)

Similarly, a _backward policy_ is a collection of distributions $P_{B}(-|s)$
over the _parents_ of every noninitial state.

Any distribution over complete trajectories that arises from a forward policy
satisfies a Markov property: the marginal choice of action out of a state $s$
is independent of how $s$ was reached. Conversely, any Markovian distribution
over $\mathcal{T}$ arises from a forward policy (Bengio et al., 2023).

A forward policy can thus be used to sample terminal states $x\in\mathcal{X}$
by starting at $s_{0}$ and iteratively sampling actions from $P_{F}$, or,
equivalently, taking the terminating state of a complete trajectory $\tau\sim
P_{F}(\tau)$. The marginal likelihood of sampling $x\in\mathcal{X}$ is the sum
of likelihoods of all complete trajectories that terminate at $x$.

Suppose that a nontrivial (not identically 0) nonnegative reward function
$R:\mathcal{X}\to\mathbb{R}_{\geq 0}$ is given. The learning problem solved by
GFlowNets is to estimate a policy $P_{F}$ such that the likelihood of sampling
$x\in\mathcal{X}$ is proportional to $R(x)$. That is, there should exist a
constant $Z$ such that

$R(x)=Z\sum_{\tau in\mathcal{T}:\tau=(s_{0}\rightarrow\dots\rightarrow
s_{n}=x)}P_{F}(\tau)\quad\forall x\in\mathcal{X}.$ (2)

If (2) is satisfied, then $Z=\sum_{x\in\mathcal{X}}R(x)$. The sum in (2) may
be intractable. Therefore, GFlowNet training algorithms require estimation of
auxiliary quantities beyond the parameters of the policy $P_{F}$. The training
objective we primarily consider, _trajectory balance_ (TB), learns an estimate
of the constant $Z$ and of a _backward policy_ , $P_{B}(s\mid s^{\prime})$,
representing the posterior over predecessor states of $s^{\prime}$ in
trajectories that contain $s^{\prime}$. The TB loss for a trajectory $\tau$
is:

$\mathcal{L}_{TB}(\tau;\theta)=\left(\log\frac{Z_{\theta}\prod_{t=0}^{n-1}P_{F}(s_{t+1}|s_{t};\theta)}{R(s_{n})\prod_{t=0}^{n-1}P_{B}(s_{t}|s_{t+1};\theta)}\right)^{2}$
(3)

where $\theta$ are the parameters of the learned objects $P_{F}$, $P_{B}$, and
$Z$. If $\mathcal{L}_{TB}(\tau;\theta)=0$ for all $\tau$, then $P_{F}$ samples
objects $x\in\mathcal{X}$ with probability proportional to $R(x)$, i.e., (2)
is satisfied. Algorithms minimize this loss for trajectories $\tau$ sampled
from some _training policy_ $\pi_{\theta}$, which may be equal to $P_{F}$
itself (_on-policy training_) but is usually taken to be a more exploratory
distribution, as we discuss below.

Notably, any choice of a backwards policy $P_{B}$ yields a unique
corresponding $P_{F}$ and $Z$ which makes the expression on the right side of
(3) equal to zero for all $\tau\in\mathcal{T}$ (see Malkin et al. (2023) for
interpretations of this result in terms of variational methods).

###  3.2 GFlowNet exploration strategies

Prior work on GFlowNets uses training policies based on dithering or intrinsic
motivation, including:

On-policy

The training policy is the current $P_{F}$:
$\pi_{\theta}(s^{\prime}|s)=P_{F}(s^{\prime}|s;\theta)$.

Tempering

Let
$\alpha_{\theta}(s^{\prime}|s):\mathcal{S}\times\mathcal{S}\rightarrow\mathbb{R}$
be the logits of $P_{F}$, then the training policy is a Boltzmann distribution
with temperature $T\in\mathbb{R}$ as
$\pi_{\theta}(s^{\prime}|s)\propto\exp\left(\alpha_{\theta}(s^{\prime}|s)/T\right)$.

$\epsilon$-noisy

For $\epsilon\in[0,1]$, the training policy follows $P_{F}$ with probability
$1-\epsilon$ and takes a random action with probability $\epsilon$ as
$\pi_{\theta}(s^{\prime}|s)=(1-\epsilon)P_{F}(s^{\prime}|s;\theta)+\frac{\epsilon}{\\#\\{s^{\prime\prime}:(s\rightarrow
s^{\prime\prime})\in\mathcal{A}\\}}$.

GAFN (Pan et al., 2022)

The training policy is the current $P_{F}$, but $P_{F}$ is learned by
incorporating a pseudocount-based intrinsic reward for each state $s\in\tau$
into the objective $\mathcal{L}(\tau;P_{F},P_{B})$ so that
$\pi_{\theta}(s^{\prime}|s)=P_{F}(s^{\prime}|s;\theta)$.

###  3.3 Thompson sampling for GFlowNets

Learning GFlowNets over large spaces $\mathcal{X}$ requires judicious
exploration. It makes little sense to explore in regions the GFlowNet has
already learned well – we would much rather prioritize exploring regions of
the state space on which the GFlowNet has not accurately learned the reward
distribution. Prior methods do not explicitly prioritize this. Both dithering
approaches (tempering and $\epsilon$-noisy) and GAFNs encourage a form of
uniform exploration, be it pure random noise as in dithering or a pseudocount
in GAFNs. While it is impossible to _a priori_ determine which regions a
GFlowNet has learned poorly, we might expect that it performs poorly in the
regions on which it is uncertain. An agent with an estimate of its own
uncertainty could bias its action selection towards regions in which it is
more uncertain.

With this intuition in mind, we develop an algorithm inspired by Thompson
sampling and its applications in RL and bandits (Osband et al., 2016a, 2018).
In particular, following Osband et al. (2016a) we maintain an approximate
posterior over forward policies $P_{F}$ by viewing the last layer of our
policy network itself as an ensemble. To maintain a size $K\in\mathbb{Z}^{+}$
ensemble extend the last layer of the policy network to have $K\cdot\ell$
heads where $\ell$ is the maximum number of valid actions according to $G$ for
any state $s\in\mathcal{S}$. To promote computational efficiency all members
of our ensemble share weights in all layers prior to the final one.

To better our method’s uncertainty estimates, we employ the statistical
bootstrap to determine which trajectories $\tau$ may be used to train ensemble
member $P_{F,k}$ and also make use of randomized prior networks (Osband et
al., 2018). Prior networks are a downsized version of our main policy network
whose weights are fixed at initialization and whose output is summed with the
main network in order to produce the actual policy logits. Prior networks have
been shown to significantly improve uncertainty estimates and agent
performance in reinforcement learning tasks.

Crucially, while we parameterize an ensemble of $K$ forward policies we do not
maintain an ensemble of backwards policies, instead sharing one $P_{B}$ across
all ensemble members $P_{F,k}$. Recall from 3.1 that each $P_{B}$ uniquely
determines a $P_{F}$ which
$\mathcal{L}_{TB}(\tau)=0\quad\forall\tau\in\mathcal{T}$. Specifying a
different $P_{B,k}$ for each $P_{F,k}$ would result in setting a different
learning target for each $P_{F,k}$ in the ensemble. By sharing a single
$P_{B}$ across all ensemble members we ensure that all $P_{F,k}$ converge to
the same optimal $P_{F}^{*}$. We show in Section 4.1 that sharing $P_{B}$
indeed yields significantly better performance than maintaining separate
$P_{B,k}$.

With our policy network parameterization in hand, the rest of our algorithm is
simple. First we sample an ensemble member $P_{F,k}$ with
$k\sim\textrm{Uniform}\\{1,\dots,K\\}$ and then sample an entire trajectory
from it $\tau\sim P_{F,k}$. This trajectory is then used to train each
ensemble member where we include the trajectory in the training batch for
ensemble member $P_{F,k}$ based on the statistical bootstrap with bootstrap
probability $p$ ($p$ is a hyperparameter fixed at the beginning of training).
The full algorithm is presented in Appendix A.

##  4 Experiments

###  4.1 Grid

Figure 1: Reward on the grid task. Left: true distribution (normalized reward
function). Right: empirical distribution over last $2\cdot 10^{5}$ states
sampled from the GFlowNet at end of training.

We study a modified version of the grid environment from (Bengio et al.,
2021). The set of interior states is a 2-dimensional grid of size $H\times H$.
The initial state is $(0,0)$ and each action is a step that increments one of
the 2 coordinates by 1 without leaving the grid. A special termination action
is also allowed from each state.

Prior versions of this grid environment provide high reward whenever the agent
exits at a corner of the grid. This sort of reward structure is very easy for
an agent to generalize to and is a trivial exploration task when the reward is
not highly sparse (such reward structures are _not_ the focus of this paper).
To compensate for this, we adopt a reward function based on a summation of
truncated Fourier series, yielding a reward structure which is highly
multimodal and more difficult to generalize to (see Figure 1). The reward
function is given by

$\displaystyle R(x)=\sum_{k=1}^{n}$ $\displaystyle\cos(2a_{k,1}\pi
g(x_{1}))+\sin(2a_{k,2}\pi g(x_{1}))+$ $\displaystyle\cos(2b_{k,1}\pi
g(x_{2}))+\sin(2b_{k,2}\pi g(x_{2}))$

where $a_{k,1},a_{k,2},b_{k,1},b_{k,2}\in\mathbb{R}$ are preset scaling
constants $\forall k$, $n$ is a hyperparameter determining the number of
elements in the summation, $g:\mathbb{Z}_{\geq
0}\rightarrow[c,d],g(x)=\frac{x(d-c)}{H}+c$, and $c,d\in\mathbb{R}$ are the
first and last integer coordinates in the grid.

We investigate a $64\times 64$ grid with this truncated Fourier series reward
(see Appendix B for full reward setup details). We train the GFlowNets to
sample from this target reward function and plot the evolution of the $L_{1}$
distance between the target distribution and the empirical distribution of the
last $2\cdot 10^{5}$ states seen in training111This evaluation is possible in
this environment because the exact target distribution can be tractably
computed..

Figure 2: $L_{1}$ distance between empirical and target distributions over the
course of training on the hypergrid environment (mean is plotted with standard
error bars over 5 random seeds). Left: Thompson sampling learns the
distribution better and faster than all other methods. Right: sharing a
backwards policy $P_{B}$ performs significantly better than maintaining a
separate backward policy $P_{B,k}$ for each forward policy $P_{F,k}$ in the
ensemble.

The results (mean and standard error over five random seeds) are shown in
Figure 2 (left side). Models trained with trajectories sampled by TS-GFN
converge faster and with very little variance over random seeds to the true
distribution than all other exploration strategies.

We also investigate the effect of sharing the backwards policy $P_{B}$ across
ensemble members in Figure 2 (right side). Maintaining a separate $P_{B,k}$
for each $P_{F,k}$ performs significantly worse than sharing a single $P_{B}$
over all ensemble members. Maintaining separate $P_{B,k}$ resulted in the
GFlowNet learning much slower than sharing $P_{B}$ and converging to a worse
empirical $L_{1}$ than sharing $P_{B}$.

###  4.2 Bit sequences

Figure 3: Number of modes found as a function of training time for bit
sequence task.

We consider the synthetic sequence generation setting from Malkin et al.
(2022), where the goal is to generate sequences of bits of fixed length
$n=120$, resulting in a search space $\mathcal{X}$ of size $2^{120}$. The
reward is specified by a set of modes $M\subset\mathcal{X}=\\{0,1\\}^{n}$ that
is unknown to the learning agent. The reward of a generated sequence $x$ is
defined in terms of Hamming distance $d$ from the modes:
$R(x)=\exp\left(1-n^{-1}\min_{y\in M}d(x,y)\right)$. The vocabulary for the
GFlowNets is $\\{0,1\\}$. Most experiment settings are taken from Malkin et
al. (2022) and Madan et al. (2023).

Models are evaluated by tracking the number of modes according to the
procedure in Malkin et al. (2022) wherein we count a mode $m$ as “discovered”
if we sample some $x$ such that $d(x,m)\leq\delta$. The results are presented
in Figure 3 (mean and standard error are plotted over five random seeds). We
find that models trained with TS-GFN find 60% more modes than on-policy,
tempering, and $\epsilon$-noisy. TS-GFN soundly outperforms GAFN, whose
pseudocount based exploration incentive is misaligned with the task’s reward
structure and seems to perform exploration in unhelpful regions of the (very
large) search space.

##  5 Conclusion

We have shown in this paper that using a Thompson sampling based exploration
strategy for GFlowNets is a simple, computationally efficient, and performant
alternative to prior GFlowNet exploration strategies. We demonstrated how to
adapt uncertainty estimation methods used for Thompson sampling in deep
reinforcement learning to the GFlowNet domain and proved their efficacy on a
grid and long sequence generation task. Finally, we believe that future work
should involve trying TS-GFN on a wider array of experimental settings and
building a theoretical framework for investigating sample complexity of
GFlowNets.

## Acknowledgments

The authors acknowledge financial support from CIFAR, Genentech, IBM, Samsung,
Microsoft, and Google.

## References

  * Agrawal & Goyal (2012) Agrawal, S. and Goyal, N.  Analysis of thompson sampling for the multi-armed bandit problem.  In _Conference on learning theory_ , pp. 39–1. JMLR Workshop and Conference Proceedings, 2012.
  * Agrawal & Goyal (2017) Agrawal, S. and Goyal, N.  Near-optimal regret bounds for thompson sampling.  _Journal of the ACM (JACM)_ , 64(5):1–24, 2017\.
  * Agrawal & Jia (2017) Agrawal, S. and Jia, R.  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Akiba et al. (2019) Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M.  Optuna: A next-generation hyperparameter optimization framework.  In _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, pp. 2623–2631, 2019.
  * Badia et al. (2020) Badia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., et al.  Never give up: Learning directed exploration strategies.  _arXiv preprint arXiv:2002.06038_ , 2020.
  * Bengio et al. (2021) Bengio, E., Jain, M., Korablyov, M., Precup, D., and Bengio, Y.  Flow network based generative models for non-iterative diverse candidate generation.  _Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Bengio et al. (2023) Bengio, Y., Lahlou, S., Deleu, T., Hu, E., Tiwari, M., and Bengio, E.  GFlowNet foundations.  _arXiv preprint 2111.09266_ , 2023.
  * Burda et al. (2018) Burda, Y., Edwards, H., Storkey, A., and Klimov, O.  Exploration by random network distillation.  _arXiv preprint arXiv:1810.12894_ , 2018.
  * Ciosek et al. (2019) Ciosek, K., Vuong, Q., Loftin, R., and Hofmann, K.  Better exploration with optimistic actor critic.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Deleu et al. (2022) Deleu, T., Góis, A., Emezue, C., Rankawat, M., Lacoste-Julien, S., Bauer, S., and Bengio, Y.  Bayesian structure learning with generative flow networks.  _Uncertainty in Artificial Intelligence (UAI)_ , 2022.
  * Eysenbach et al. (2018) Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S.  Diversity is all you need: Learning skills without a reward function.  _International Conference on Learning Representations (ICLR)_ , 2018\.
  * Haarnoja et al. (2017) Haarnoja, T., Tang, H., Abbeel, P., and Levine, S.  Reinforcement learning with deep energy-based policies.  _International Conference on Machine Learning (ICML)_ , 2017.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  _International Conference on Machine Learning (ICML)_ , 2018.
  * Hazan et al. (2019) Hazan, E., Kakade, S., Singh, K., and Van Soest, A.  Provably efficient maximum entropy exploration.  _International Conference on Machine Learning (ICML)_ , 2019.
  * Hu et al. (2023) Hu, E. J., Malkin, N., Jain, M., Everett, K., Graikos, A., and Bengio, Y.  GFlowNet-EM for learning compositional latent variable models.  _International Conference on Machine Learning (ICML)_ , 2023.
  * Islam et al. (2019) Islam, R., Ahmed, Z., and Precup, D.  Marginalized state distribution entropy regularization in policy optimization.  _arXiv preprint 1912.05128_ , 2019.
  * Jain et al. (2022a) Jain, M., Bengio, E., Hernandez-Garcia, A., Rector-Brooks, J., Dossou, B. F., Ekbote, C., Fu, J., Zhang, T., Kilgour, M., Zhang, D., Simine, L., Das, P., and Bengio, Y.  Biological sequence design with GFlowNets.  _International Conference on Machine Learning (ICML)_ , 2022a.
  * Jain et al. (2022b) Jain, M., Raparthy, S. C., Hernandez-Garcia, A., Rector-Brooks, J., Bengio, Y., Miret, S., and Bengio, E.  Multi-objective GFlowNets.  _arXiv preprint 2210.12765_ , 2022b.
  * Lee et al. (2021) Lee, K., Laskin, M., Srinivas, A., and Abbeel, P.  Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning.  In _International Conference on Machine Learning_ , pp. 6131–6141. PMLR, 2021.
  * Madan et al. (2023) Madan, K., Rector-Brooks, J., Korablyov, M., Bengio, E., Jain, M., Nica, A., Bosc, T., Bengio, Y., and Malkin, N.  Learning GFlowNets from partial episodes for improved convergence and stability.  _International Conference on Machine Learning (ICML)_ , 2023.
  * Malkin et al. (2022) Malkin, N., Jain, M., Bengio, E., Sun, C., and Bengio, Y.  Trajectory balance: Improved credit assignment in GFlowNets.  _Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Malkin et al. (2023) Malkin, N., Lahlou, S., Deleu, T., Ji, X., Hu, E., Everett, K., Zhang, D., and Bengio, Y.  GFlowNets and variational inference.  _International Conference on Learning Representations (ICLR)_ , 2023\.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  _Neural Information Processing Systems (NIPS)_ , 2016.
  * Moritz et al. (2018) Moritz, P., Nishihara, R., Wang, S., Tumanov, A., Liaw, R., Liang, E., Elibol, M., Yang, Z., Paul, W., Jordan, M. I., et al.  Ray: A distributed framework for emerging $\\{$AI$\\}$ applications.  In _13th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 18)_, pp. 561–577, 2018.
  * Nachum et al. (2017) Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D.  Bridging the gap between value and policy based reinforcement learning.  _Neural Information Processing Systems (NIPS)_ , 2017.
  * Nikolov et al. (2018) Nikolov, N., Kirschner, J., Berkenkamp, F., and Krause, A.  Information-directed exploration for deep reinforcement learning.  _arXiv preprint arXiv:1812.07544_ , 2018.
  * Osband et al. (2013) Osband, I., Russo, D., and Van Roy, B.  (more) efficient reinforcement learning via posterior sampling.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Osband et al. (2016a) Osband, I., Blundell, C., Pritzel, A., and Van Roy, B.  Deep exploration via bootstrapped dqn.  _Advances in neural information processing systems_ , 29, 2016a.
  * Osband et al. (2016b) Osband, I., Van Roy, B., and Wen, Z.  Generalization and exploration via randomized value functions.  In _International Conference on Machine Learning_ , pp. 2377–2386. PMLR, 2016b.
  * Osband et al. (2018) Osband, I., Aslanides, J., and Cassirer, A.  Randomized prior functions for deep reinforcement learning.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Osband et al. (2019) Osband, I., Van Roy, B., Russo, D. J., Wen, Z., et al.  Deep exploration via randomized value functions.  _J. Mach. Learn. Res._ , 20(124):1–62, 2019.
  * O’Donoghue et al. (2018) O’Donoghue, B., Osband, I., Munos, R., and Mnih, V.  The uncertainty bellman equation and exploration.  In _International Conference on Machine Learning_ , pp. 3836–3845, 2018.
  * Pan et al. (2022) Pan, L., Zhang, D., Courville, A., Huang, L., and Bengio, Y.  Generative augmented flow networks.  _arXiv preprint 2210.03308_ , 2022.
  * Pan et al. (2023) Pan, L., Malkin, N., Zhang, D., and Bengio, Y.  Better training of gflownets with local credit and incomplete trajectories.  _arXiv preprint arXiv:2302.01687_ , 2023.
  * Pathak et al. (2017) Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T.  Curiosity-driven exploration by self-supervised prediction.  In _International conference on machine learning_ , pp. 2778–2787. PMLR, 2017.
  * Russo et al. (2018) Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z., et al.  A tutorial on thompson sampling.  _Foundations and Trends® in Machine Learning_ , 11(1):1–96, 2018.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint 1707.06347_ , 2017.
  * Thompson (1933) Thompson, W. R.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3-4):285–294, 1933.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I.  Attention is all you need.  _Neural Information Processing Systems (NIPS)_ , 2017.
  * Zhang et al. (2021) Zhang, C., Cai, Y., Huang, L., and Li, J.  Exploration by maximizing rényi entropy for reward-free rl framework.  _Association for the Advancement of Artificial Intelligence (AAAI)_ , 2021.
  * Zhang et al. (2022) Zhang, D., Malkin, N., Liu, Z., Volokhova, A., Courville, A., and Bengio, Y.  Generative flow networks for discrete probabilistic modeling.  _International Conference on Machine Learning (ICML)_ , 2022.
  * Zhang et al. (2023) Zhang, D. W., Rainone, C., Peschl, M., and Bondesan, R.  Robust scheduling with gflownets.  _International Conference on Learning Representations (ICLR)_ , 2023\.
  * Ziebart (2010) Ziebart, B. D.  _Modeling purposeful adaptive behavior with the principle of maximum causal entropy_.  Carnegie Mellon University, 2010.

##  Appendix A Additional algorithm details

Input:

$\\{P_{F,k}\\}_{k=1}^{K}$: Family of $K$ different forward policies

$P_{B}$: Shared backwards policy

$\delta\in[0,1]$: Parameter for the bootstrapping distribution (we assume the
distribution is Bernoulli)

$L$: Loss function taking as input a trajectory $\tau$, forward policy
$P_{F}$, and backward policy $P_{B}$

for each episode do

Initialize $s_{0}$ from environment

Initialize trajectory $\tau$ to empty list

Pick forward policy to act with $P_{F,k}$ using
$k\sim\textrm{Uniform}\\{1,\dots,K\\}$

for step $t=1,\dots$ until end of episode do

Pick action $a_{t}\sim P_{F,k}(a_{t}|s_{t-1})$

Receive state $s_{t}$ from environment

Append $(s_{t},a_{t})$ to $\tau$

end for

Add reward for trajectory $R(x)$ to $\tau$ using last state in $\tau$

Sample bootstrap mask $m_{k}\sim\textrm{Bernoulli}(\delta)\quad\forall k$

Compute loss $\ell=\sum_{k=1}^{K}m_{k}\cdot L(\tau,P_{F,k},P_{B})$

Take gradient step on loss $\ell$

end for

Algorithm 1 TS-GFN

##  Appendix B Experiment details: Grid

For brevity, we recall the definition of the reward function from Section 4.1
as

$R(x)=\sum_{k=1}^{n}\cos(2a_{k,1}\pi g(x_{1}))+\sin(2a_{k,2}\pi
g(x_{1}))+\cos(2b_{k,1}\pi g(x_{2}))+\sin(2b_{k,2}\pi g(x_{2}))$

The reward function was computed using the following hyperparameters. The
weights were set as $a_{k,1}=a_{k,2}=b_{k,1}=b_{k,2}=\frac{4k}{1000}$ with
$n=1000$ (the equivalent of np.linspace(0, 4, 1000)). The grid side boundary
constants were $c=-0.5,d=0.5$ and the side length of the overall environment
was $H=64$ (so that the overall state space was of size $H\times
H=64^{2}=4096$). Finally, we raised the reward by the exponent $\beta=1.5$ so
that we trained the GFlowNets using reward $R^{\prime}(x)=R(x)^{\beta}$.

Besides the reward, architecture details are identical to those in Malkin et
al. (2022), Madan et al. (2023), and Bengio et al. (2021). The architecture of
the forward and backward policy models are MLPs of the same architecture as in
Bengio et al. (2021), taking a one-hot representation of the coordinates of
$s$ as input and sharing all layers except the last. The only difference comes
from the TS-GFN implementation which has $K\cdot d$ heads for the output of
the last layer where $d$ is the number of heads in the architecture of the
non-TS-GFNs.

All models are trained with the Adam optimizer, the trajectory balance loss,
and a batch size of 64 for a total of $400,000$ trajectories. Hyperparameters
were tuned using the Optuna Bayesian optimization framework from project Ray
(Akiba et al., 2019; Moritz et al., 2018). Each method was allowed 100
hyperparameter samples from the Bayesian optimization procedure. We reported
performance from the best hyperparameter setting found by the Bayesian
optimization procedure averaged over five random seeds ($0,1,2,3,4$). We now
detail the hyperparameters selected from the Bayesian optimization procedure
for each exploration strategy.

For on-policy we found optimal hyperparameters of $0.00156$ for the model
learning rate and $0.00121$ for the $\log Z$ learning rate. For tempering we
found optimal hyperparameters of $0.00236$ for the model learning rate,
$0.0695$ for the $\log Z$ learning rate, and $1.0458$ for the sampling policy
temperature. For $\epsilon$-noisy we found optimal hyperparameters of
$0.00112$ for the model learning rate, $0.0634$ for the $\log Z$ learning
rate, and $0.00534$ for $\epsilon$. For GAFN we found optimal hyperparameters
of $0.000166$ for the model learning rate, $0.0955$ for the $\log Z$ learning
rate, $0.144$ for the intrinsic reward weight, and the architecture of the RND
networks were a 2 layer MLP with hidden layer dimension of $53$ and output
embedding dimension of $96$ (the hidden layer dimension and embedding
dimension were also tuned by the Bayesian optimization procedure). Finally,
for Thompson sampling we found a model learning rate of $0.00266$, $\log Z$
learning rate of $0.0976$, ensemble size of $100$, bootstrap probability
$\delta$ of $0.274$, and prior weight of $12.03$.

##  Appendix C Experiment details: Bit sequences

The modes $M$ as well as the test sequences are selected as described in
Malkin et al. (2022). The policy for all methods is parameterized by a
Transformer (Vaswani et al., 2017) with 3 layers, dimension 64, and 8
attention heads. All methods are trained for 50,000 iterations with minibatch
size of 16 using Adam optimizer and the trajectory balance loss.

All hyperparameters were tuned according to a grid search over the parameter
values specified below. For on-policy we used a model learning rate of
$0.0001$ picked from the set $\\{0.0001,0.001,0.01\\}$ and a $\log Z$ learning
rate of $0.001$ from the set $\\{0.001,0.01\\}$. For tempering we used a model
learning rate of $0.0001$ picked from the set $\\{0.0001,0.001,0.01\\}$, a
$\log Z$ learning rate of $0.001$ from the set $\\{0.001,0.01\\}$, and
sampling distribution temperature of $1.1$ from the set
$\\{1.05,1.1,1.25,1.5\\}$. For $\epsilon$-noisy we used a learning rate of
$0.001$ picked from the set $\\{0.0001,0.001,0.01\\}$, a $\log Z$ learning
rate of $0.001$ from the set $\\{0.001,0.01\\}$, and $\epsilon$ of $0.005$
from the set $\\{0.01,0.005,0.001,0.0005\\}$. For GAFN we used a learning rate
of $0.001$ picked from the set $\\{0.0001,0.0005,0.001\\}$, a $\log Z$
learning rate of $0.1$ from the set $\\{0.001,0.01,0.1\\}$, an intrinsic
reward weight of $0.5$ from the set $\\{0.1,0.5,1.0,5.0,10.0\\}$, the RND
network was a 4 layer MLP with hidden layer dimension of $64$ and output
dimension of $64$. For TS-GFN we used a model learning rate of $0.001$ picked
from the set $\\{0.0001,0.001,0.01\\}$, a $\log Z$ learning rate of $0.001$
from the set $\\{0.001,0.01\\}$, an ensemble size of $50$ picked from the set
$\\{10,50,100\\}$, a prior weight of $4.0$ picked from the set
$\\{0.1,1.0,4.0\\}$, and a bootstrap probability $\delta$ 0f $0.75$.


# Thistle: A Vector Database in Rust

Brad Windsor
<EMAIL_ADDRESS>
Kevin Choi 11footnotemark: 1
<EMAIL_ADDRESS>
All authors are equal contributors and NYU-affiliated.

###### Abstract

We present Thistle 111All code is open-sourced at
https://github.com/bwindsor22/thistle, a fully functional vector database.
Thistle is an entry into the domain of latent knowledge use in answering
search queries, an ongoing research topic at both start-ups and search engine
companies. We implement Thistle with several well-known algorithms, and
benchmark results on the MS MARCO dataset. Results help clarify the latent
knowledge domain as well as the growing Rust ML ecosystem.

##  1 Introduction & Related Work

Knowledge representation is an unsolved problem in Natural Language
Processing, a study of how machines ought to store information gathered from
text such that it is useful for downstream tasks.

Broadly, one category of knowledge representation is explicit; words are kept
in a human understandable format and explicit connections are made. Examples
include Prolog rules banks, Knowledge Bases like WikiData Vrandečić and
Krötzsch (2014), or SQL tables.

Another is implicit knowledge, keeping formats easier for machines, especially
neural networks, to make use of. Examples include Word2Vec Goldberg and Levy
(2014), ELMo Peters et al. (2018), and BERT Devlin et al. (2018). Such
numerical representations are often made by pre-training networks on large
text corpuses.

Most open-source search engines rely on an explicit knowledge representation
by matching term counts between an input query and each sample corpus match.
Specifically, both ElasticSearch and Vespa are based on BM-25 Robertson et al.
(1995), a modification of the TF-IDF counts. This is quite easy for humans to
understand; a search for “Blue Armadillo” will be more likely to return
documents matching “Armadillo” than “Blue” because “Armadillo” is a rare word.

However, search engines are increasingly beginning to look for ways to
incorporate implicit knowledge. Google recently began using BERT to revise
search results Nayak (2019), NBoost222https://github.com/koursaros-ai/nboost
is a neural booster for ElasticSearch, and PineconeDB333http://pinecone.io
forgoes the BM-25 entirely and operates only on vectors.

Thistle seeks to operate only in the implicit domain, doing search only with
sentence embeddings from neural networks. We look at several ways of doing
this comparison, and measure database accuracy and runtime.

As a secondary goal, Thistle is implemented in Rust to help evaluate machine
learning libraries there. Rust is a new programming language attracting recent
support from Linux, Google, and Facebook as a low-complexity low-level
language.

##  2 Methods

###  2.1 Approach

Thistle’s approach can be outlined as follows: pieces of sentence-level text
are turned into embeddings of size 768 via SBERT (Sentence-BERT), and then two
exact nearest neighbor search algorithms (one using cosine distance and one
using Euclidean distance) as well as three approximate nearest neighbor search
algorithms (two using the proximity graph method and one using locality
sensitive hashing) are provided to retrieve the top k results closest to a
given query. The user selects which algorithm to use at runtime. Details with
regards to these algorithms are delineated below.

BERT’s architecture

###  2.2 SBERT

Applying the bidirectional training of the attention-based Transformer model
to language modeling, BERT has achieved state-of-the-art results since 2018.
Despite its adaptability to various tasks in NLP, one disadvantage of BERT is
that no independent sentence embedding is computed such that one has to use,
as a proxy, either the average of the BERT output layer (a la average word
embeddings) or the output of the [CLS] token (included in the beginning of
every sentence in BERT’s training process). Unfortunately, both of these not
only fall short in the task of similarity comparison and correspondingly
information retrieval (which Thistle tackles), but also suffer from
substantial computation costs from a training perspective.

To address the above limitation of BERT, SBERT is designed to output a stand-
alone sentence embedding using BERT. The idea is to add a pooling operation to
the output of BERT, followed by siamese and triplet networks for fine-tuning
purposes. The pooling operation is in fact a hyperparameter. Three options
include using the output of the aforementioned [CLS] token, computing the mean
of all output vectors, and computing a max-over-time of the output vectors.
All three of these options are provided by Thistle. SBERT substantially
outperforms BERT, Universal Sentence Encoder, and others on key benchmarks,
making it the basis for our work Reimers and Gurevych (2019).

###  2.3 Search Algorithms

####  2.3.1 Iterative

As a basic benchmark, we explore the cumbersome option of comparing an input
embedding to every embedding in the corpus a la exact kNN. This is implemented
in Rust without library support.

####  2.3.2 HNSW

An example of a proximity graph

The proximity graph method helps perform approximate kNN by conceptually
turning a set of data points into a graph whose nodes represent the data
points respectively and are connected if and only if particular geometric
distance requirements between two nodes are met. The basic algorithm can
proceed in a greedy manner as follows. Given a query point, we begin the
search by starting at some enter point (either random or predefined) as our
initial base node, compute the distance between the query node and all the
neighbors of the enter point, choose the neighbor that is closest to the
query, update the base node to be that neighbor, and greedily repeat the
process by computing the distance between neighbors of the updated base node
and the query until some stopping condition is met (e.g. upper bound on the
number of iterations).

While NSW (navigable small world) is an example of the proximity graph method
utilizing navigable graphs (i.e. graphs with polylogarithmic scaling of the
number of hops during the greedy traversal with respect to the network size),
HNSW, short for hierarchical navigable small world, extends it by introducing
a multi-layer structure comprising a hierarchical set of more than one
proximity graphs for nested subsets of data points.

As a simple example for intuition purposes, imagine we start with 8 data
points, all of which are included in the “base” (layer 0) proximity graph
(which is precisely the only graph used in non-HNSW cases of the proximity
graph method). Then we build another proximity graph (call it layer 1) using
only a subset of the nodes from the layer 0 graph. Lastly, we can build a
layer 2 proximity graph using only a subset of the nodes from layer 1. The
number of layers can of course be much higher in practice and is a
hyperparameter. The idea is that we can traverse the graph starting from the
highest layer (as opposed to the base layer) and travel downwards given a
query such that we are essentially able to “skip” potentially unnecessary
intermediary iterations of the greedy process, promoting efficiency. It is for
this reason that Thistle leverages HNSW as opposed to other forms of the
proximity graph method. While Thistle provides two distance metrics (Euclidean
and cosine) for HNSW, it can be easily configured to support other metrics as
well. Overall, HNSW accounts for 2 out of 3 approximate kNN methods that
Thistle offers.

####  2.3.3 LSH

Locality sensitive hashing (LSH) represents yet another approximate kNN method
supported by Thistle. It relies on the fact that data points that are similar
in nature (i.e. close to each other) have a higher probability of getting
hashed to the same bucket, which is untrue for general hashing (where hash
collisions are minimized not maximized). Consequently, this technique can
indeed be used for approximate kNN. Given a query, we simply hash it to some
bucket using LSH and consider the data points in that bucket while keeping
track of the algorithm’s probability guarantees. It is possible to explore and
configure such guarantees on Thistle via hyperparameters.

Locality sensitive hashing (LSH)

###  2.4 RUST

Rust Matsakis and Klock II (2014) is a new programming language that exceeds
or comes within 5% of C++ on many important benchmarks lan  like the n-body
problem or digits of Pi. It is memory- and thread-safe, has no garbage
collection, and is supported by a robust set of tools including excellent
compiler error messages.

The website arewelearningyet.com describes machine learning in Rust as “ripe
for experimentation, but the ecosystem isn’t very complete.” We found this to
be true; we iterated through three libraries to find an HNSW implementation
that worked for us, and with LSH, we fixed an open issue
444https://github.com/ritchie46/lsh-rs/issues/9 so the library would work
again.

Our Rust implementation features a common interface as laid out by Traits,
with load and query operations implemented for each of the database objects.

##  3 Results

###  3.1 Evaluation

The MS Marco dataset Bajaj et al. (2018) is used for evaluation. This dataset
is composed of anonymized questions sampled from Bing’s search logs and
separated into query and result tuples.

Evaluation began by downloading and cleaning the dataset, removing special
characters. For each of the 5 databases instances, the following evaluation
was run:

  * •

Insert the full result corpus into the database.

  * •

For each (query, result) tuple in the corpus, run the query text on the
database. If the result is the expected result, mark as correct.

Total time is taken as time to insert plus time to query, and the experiment
is run for N = 100, 1,000, and 10,000 entries. See figures at end.

###  3.2 Analysis

Trends
Several trends are immediately obvious: as dataset size increases, accuracy
goes down, and runtime goes up.

As expected, a point by point comparison of the query and output through all
data points produces the highest accuracy. Libraries such as LSH and HNSW are
approximate algorithms meant to speed lookups. At the lowest dataset size, a
straight-through iteration of all data is fastest.

Although LSH passed a local unit test, it had very poor accuracy across
dataset sizes. This became clear in testing; as soon as more than a few words
changed, LSH had difficulty making the match. Some tuning of hyperparameters
might improve this result, as LSH takes as input the number of projections and
hash tables.

Assessment
Overall, results bring significant sobriety to the idea of a fully vector-
oriented search database.

One concern is time; the HNSW Euclidean benchmark at 10,000 data points took
11 hours to run, hardly practical for a production application. Over 99% of
this time was in running SBERT, which is significantly slower than
alternatives like Universal Sentence Encoder. Even as benchmark results for
implicit representations improve, it is important to still do work to ensure
representations can be computed in a reasonable time.

Another concern is accuracy; at N=10,000, we see accuracies in the range of
30-40%. One way in which this might be improved would be to use Neural Ranking
on top of the BM-25 algorithm; only use neural networks to refine the top K
results. A more immediate gain might be to constrain the results to passages
that only fit within the SBERT token size, though this is also a constraint:
additional code is needed to represent varying passage sizes with BERT-family
models, though BM-25 handles this easily.

##  4 Conclusion

Overall Thistle is a successful instance of a purely latent knowledge-based
database written in Rust. The project succeeded in benchmarking several Rust
libraries and included a merged pull request on LSH. We were able to compare
implementations and measure runtime and accuracy, though both would need
improvement for a production system. Future work might include benchmarking
results against existing explicit-knowledge databases (such as ElasticSearch),
or exploring the use of latent knowledge to enhance searches in BM-25
databases.

## References

  * (1) Which programming language is fastest?
  * Bajaj et al. (2018) Payal Bajaj, Daniel Campos, Nick Craswell, Li Deng, Jianfeng Gao, Xiaodong Liu, Rangan Majumder, Andrew McNamara, Bhaskar Mitra, Tri Nguyen, Mir Rosenberg, Xia Song, Alina Stoica, Saurabh Tiwary, and Tong Wang. 2018.  Ms marco: A human generated machine reading comprehension dataset.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Goldberg and Levy (2014) Yoav Goldberg and Omer Levy. 2014.  word2vec explained: deriving mikolov et al.’s negative-sampling word-embedding method.  _arXiv preprint arXiv:1402.3722_.
  * Matsakis and Klock II (2014) Nicholas D Matsakis and Felix S Klock II. 2014.  The rust language.  In _ACM SIGAda Ada Letters_ , volume 34, pages 103–104. ACM.
  * Nayak (2019) Pandu Nayak. 2019.  Understanding searches better than ever before.
  * Peters et al. (2018) Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.
  * Robertson et al. (1995) Stephen E Robertson, Steve Walker, Susan Jones, Micheline M Hancock-Beaulieu, Mike Gatford, et al. 1995.  Okapi at trec-3.  _Nist Special Publication Sp_ , 109:109.
  * Vrandečić and Krötzsch (2014) Denny Vrandečić and Markus Krötzsch. 2014.  Wikidata: a free collaborative knowledgebase.  _Communications of the ACM_ , 57(10):78–85.