# Large Language Model Augmented Exercise Retrieval for Personalized Language
Learning

Austin Xu  Georgia Institute of TechnologyAtlantaGeorgiaUSA<EMAIL_ADDRESS>,
Will Monroe  DuolingoPittsburghUSA<EMAIL_ADDRESS>and  Klinton Bicknell
DuolingoPittsburghUSA<EMAIL_ADDRESS>
(2024)

###### Abstract.

We study the problem of zero-shot exercise retrieval in the context of online
language learning, to give learners the ability to explicitly request
personalized exercises via natural language. Using real-world data collected
from language learners, we observe that vector similarity approaches poorly
capture the relationship between exercise content and the language that
learners use to express what they want to learn. This semantic gap between
queries and content dramatically reduces the effectiveness of general-purpose
retrieval models pretrained on large scale information retrieval datasets like
MS MARCO (Bajaj et al., 2016). We leverage the generative capabilities of
large language models to bridge the gap by synthesizing hypothetical exercises
based on the learner’s input, which are then used to search for relevant
exercises. Our approach, which we call mHyER, overcomes three challenges: (1)
lack of relevance labels for training, (2) unrestricted learner input content,
and (3) low semantic similarity between input and retrieval candidates. mHyER
outperforms several strong baselines on two novel benchmarks created from
crowdsourced data and publicly available data.

zero-shot exercise retrieval, online language learning, personalization, large
language models

††copyright: acmcopyright††journalyear: 2024††copyright:
rightsretained††conference: The 14th Learning Analytics and Knowledge
Conference; March 18–22, 2024; Kyoto, Japan††booktitle: The 14th Learning
Analytics and Knowledge Conference (LAK ’24), March 18–22, 2024, Kyoto,
Japan††doi: 10.1145/3636555.3636883††isbn: 979-8-4007-1618-8/24/03††ccs:
Applied computing Education††ccs: Information systems Multilingual and cross-
lingual retrieval††ccs: Computing methodologies Artificial intelligence

##  1\. Introduction

Modern personalized education systems typically leverage the power of machine
learning models to estimate user skill levels (Corbett and Anderson, 1994) and
adaptively serve exercises to learners (Wu et al., 2020; Huang et al., 2022;
Cui and Sachan, 2023). Adaptivity, while a critical part of any personalized
education system, is a _passive_ form of personalization from the learner’s
point of view: While exercises are tailored to an estimate of the learner’s
skill level, this customization occurs behind the scenes, with no opportunity
for learners to take initiative in shaping the learning process. In this
paper, we study a complementary form of _learner initiated_ personalization in
the context of _online language learning_. In particular, learners are given
the ability to _explicitly_ request learning content from an education system,
which returns relevant exercises from a fixed catalog for the learner to do.

Figure 1. Exercise retrieval for learner directed language learning and our
proposed solution, multilingual Hypothetical Exercise Retriever (mHyER). At a
high level, learners are allowed to provide _any_ natural language input, and
the goal is to retrieve exercises relevant to that input. Our method utilizes
large language models to perform zero-shot retrieval.

This type of learner initiated personalization can be viewed as a form of
_self-directed learning_ , where learners take initiative over the learning
process. Self-directed learning has been shown to increase learner performance
across multiple topics (Mandasari and Wahyudin, 2021; Lucieer et al., 2016;
Kim and Jang, 2015; Krashen, 2005), improve learner motivation (Patall et al.,
2008), and create more cohesive learner environments (Geng et al., 2019).
Online language learning is a natural setting for self-directed learning, as
people learn languages for very personal reasons: Some learn for fun, while
others have specific goals, such as preparing for an international trip or
developing language skills for business. Different reasons for learning lead
to different needs for exercise content: Someone learning to write in a
business setting may want extra practice with grammar or politeness, whereas
the learner learning for a vacation may want exercises about hotels or
transportation. Beyond highly personalized motivations for learning, online
language learners do not have immediate access to instructors who can plan
learning material to target weaknesses. As such, there is an inherent need for
online language learners to have some degree of self-direction in order to get
the most out of their learning experience.

With the goal of allowing language learners to tailor an online learning
experience to their own needs, we formalize the task of exercise retrieval for
learner directed language learning and evaluate machine learning models for
this task. The goal of this task (Figure 1) is to retrieve relevant exercises
from a set of existing exercises based on a learner’s input. In this setting,
collecting relevance labels (i.e., pairs of learner inputs and relevant
exercises) is particularly challenging, as learners will typically be
presented with only a small number of exercises for any given input. As a
result, we consider the _zero-shot_ setting, where we do not have access to
relevance labels for training. While many off-the-shelf models exist for text-
based retrieval, we show that direct similarity search (i.e., retrieving
exercises that are the most similar to the user input in the representation
space) with these models suffers from a semantic similarity gap between how
users describe their learning objectives and exercise content. To overcome
this gap, we leverage structure inherent to exercises and the generative
capabilities of large language models. Specifically, we make the following
contributions.

  * •

We propose the new task of exercise retrieval for learner directed language
learning in Section 2 and discuss how learner inputs give rise to a
fundamental challenge in this task.

  * •

We present our zero-shot retrieval approach, mHyER, in Section 3, and
illustrate how augmenting retrieval with LLMs helps overcome the pitfalls of
direct similarity search.

  * •

With no existing benchmarks for this task, we create two novel benchmarks in
exercise retrieval with both crowd-sourced data from learners of a popular
language learning app and publicly available Tatoeba data. We evaluate our
method against several strong dense retrieval baselines in Section 4 and
empirically show that mHyER outperforms relevant baselines by a significant
margin.

###  1.1. Related work

Exercise retrieval is naturally connected to the broad field of information
retrieval, and in particular, dense retrieval (Lee et al., 2019; Karpukhin et
al., 2020). Dense retrieval focuses on retrieving documents based on
similarity measured in a learned representation space. Zero-shot retrieval, or
retrieval without training on task-specific relevance information, is of
particular relevance to our task. Such methods typically rely on a supervised
pretraining stage (Thakur et al., 2021; Wang et al., 2022a; Yu et al., 2022b),
where models are trained on large scale retrieval datasets, such as MS MARCO
(Bajaj et al., 2016). However, such supervised pretraining ultimately depends
on the existence of suitable labeled datasets, which are not always readily
available (Izacard et al., 2022). The rise of large language models (LLMs)
with strong zero/few-shot performance in new domains has resulted in a line of
research integrating LLMs into the retrieval pipeline. Such approaches
typically rely on some combination of specialized prompting and synthesizing
retrieval datasets to retrain retrieval models (Bonifacio et al., 2022; Dai et
al., 2022; Sachan et al., 2022; Yu et al., 2022a). Our approach takes
particular inspiration from HyDE (Gao et al., 2023), which utilizes a LLM to
synthesize a hypothetical document, which is used then used with a pretrained
encoder to retrieve documents via nearest neighbors.

A fundamental step in any retrieval method is the representation space used
for similarity comparisons. For the task of exercises retrieval, we focus on
learning sentence embeddings, where pretrained language models such as BERT
(Devlin et al., 2019) or RoBERTa (Liu et al., 2019) serve as strong
foundations. Contrastively learning sentence representations, which leverage
techniques used in the image domain (Hadsell et al., 2006; Chen et al., 2020),
has become especially popular. The goal of contrastive learning is to learn a
representation space where similar items (“positive pairs”) are pulled close
together while dissimilar items (“negative pairs”) are pulled far apart in an
unsupervised manner. In the image domain, positive pairs are formed by
applying _data augmentation_ , such as cropping or rotating an image. Such
techniques are not directly transferable to natural language, resulting in a
long line of methods (Izacard et al., 2022; Gao et al., 2021; Chuang et al.,
2022; Wu et al., 2022; Cheng et al., 2023) studying contrastive sentence
embeddings. Of particular interest to the language learning setting is
multilingual contrastive learning (Wang et al., 2022b), where positive pairs
can be taken as the same sentence in two different languages. In all, mHyER
can be viewed as a combination of multilingual contrastive learning (Wang et
al., 2022b) and HyDE (Gao et al., 2023).

Personalized education systems often gauge a learner’s skill level via
Knowledge Tracing (Corbett and Anderson, 1994) in order to tailor exercise
difficulty level. As a result, a variety of contemporary machine learning
methods (Piech et al., 2015; Pandey and Karypis, 2019; Shin et al., 2021;
Abdelrahman and Wang, 2019; Tong et al., 2020; Xu and Davenport, 2020) have
been developed to track learner skill level from historical data. Such methods
demonstrate strong empirical success and thus have been leveraged to
adaptively recommend exercises to learners (Wu et al., 2020; Huang et al.,
2022) or even generate new exercises based on skill level (Cui and Sachan,
2023). This adaptivity can be viewed as a complementary piece to the problem
of exercise retrieval directed language learning that we study in this paper:
learner initiated personalization can leverage existing tools from adaptivity
to ensure exercises are both relevant and at the right skill level. On the
other hand, adaptive systems can benefit from explicit learner direction. For
example, we can view the learner input of “past tense verbs” as the learner
explicitly saying they are not comfortable with past tense verbs, and use this
information in skill estimation.

##  2\. Problem setup

The goal of exercise retrieval for learner directed language learning is to
retrieve relevant exercises for a learner given a text input from the learner
describing what they want to learn. In particular, we assume that learner is
taking a language learning course, which consists of two languages: the “first
language” (i.e., a language they already know) and the “second language”
(i.e., the language they are learning), which we refer to as L1 and L2,
respectively.111These labels are an imprecise shorthand; L1 need not be the
learner’s first or native language, and L2 may be a third language or beyond.
The learner completes _exercises_ , which are drawn from a fixed set of $N$
exercises $\mathcal{E}=\\{e_{1},\ldots,e_{N}\\}$ that are at an appropriate
level for the learner. We can view this set of $N$ exercises as samples from
an unknown _exercise distribution_ , which captures characteristics (style,
length, content, etc) of exercises. For simplicity, we limit our attention to
translation exercises, in which a learner translates an L1 sentence
$e_{i}^{(\texttt{L1})}$ to the L2, with one correct L2 answer
$e_{i}^{(\texttt{L2})}$ available as an example of a correct translation. The
learner provides some input $t$, and our objective is to retrieve the $K$
(unique) exercises that are the most relevant based on input $t$ in a zero-
shot manner. That is, without using any labeled relevance data for training,
we want to retrieve $K$ unique exercises $e_{1}^{\star},\ldots,e_{K}^{\star}$
that maximize probability $p$ that an exercise is relevant conditioned on
learner input $t$:

(1) $\displaystyle
e_{1}^{\star},\ldots,e_{K}^{\star}=\operatorname*{arg\,max}_{\begin{subarray}{c}e_{1},\ldots
e_{K}\in\mathcal{E}\\\ e_{i}\neq e_{j}\quad\forall i,j,\ i\neq
j\end{subarray}}\quad\prod\limits_{i=1}^{K}p(e_{i}|T=t).$

###  2.1. Learner inputs.

The core of the personalized experience in this problem setting is allowing
learners to provide an input describing what they want to learn with _no
restrictions on input content_ , resulting in large number of potential input
types. For example:

  * •

Topics: Learners can request exercises that teach vocabulary relevant to a
particular topic. Inputs such as “words about animals” or “countries” are such
examples.

  * •

Grammar: Learners can request exercises teaching grammatical concepts, such as
“non-present tenses” or “irregular plurals”.

  * •

Culture: Learners can request to review culture-specific aspects of language,
such as idioms, slang, or region-specific quirks. For example, a learner
learning Spanish may want to learn about “voseo”, a region-specific
grammatical concept in South America.

  * •

Learning process: Learners can request exercises that help with particular
parts of the process of learning a language, such as “words that are hard to
spell” or “sentences for first-year students”.

Learner inputs of these types result in what we call a _referential similarity
gap_ : Under modern text-based retrieval models, how learners express their
learning objectives (i.e., the learner input $t$) is not considered similar to
what it is referring to, i.e., the content of the exercises
$e^{(\texttt{L1})}$ and $e^{(\texttt{L2})}$. We explore this gap in greater
detail in Section 3.3.

##  3\. Method

Figure 2. mHyER consists of two stages. Contrastive finetuning (left) is
employed as a training stage to optimize our semantic similarity space for
multilingual exercises. Then at retrieval time (right), a large language model
is employed to synthesize hypothetical retrieval candidates. These retrieval
candidates are then used in direct similarity search to retrieve exercises.

In this section, we present multilingual Hypothetical Exercise Retriever
(mHyER), our zero-shot exercise retrieval framework, and show that it
overcomes the pitfall of direct similarity search in learned representation
spaces.

###  3.1. Baseline: direct search with similarity spaces.

The backbone of text-based retrieval is a vector space representation of text
that reflects some notion of similarity between different pieces of text.
Forming these representation spaces remains a core part of text-based
retrieval, with early methods such as BM25 (Robertson et al., 2009) formed
representations via word frequency. Such methods struggle to generalize as
their representation spaces are formed based on counting exact or near text
matches. To improve generalization, contemporary methods for text-based
retrieval typically train a model $f_{\theta}$ (parametrized by $\theta$) that
maps natural language inputs (from the space of all text inputs $\mathcal{T}$)
to some $d$-dimensional vector space:
$f_{\theta}:\mathcal{T}\rightarrow\mathbb{R}^{d}$. Such models are referred to
as _encoders_ , and learn representations of text called _embeddings_. That
is, if $t\in\mathcal{T}$ is some text, then $f_{\theta}(t)$ is its embedding
representation. Because exercises are typically short sentences or sentence
fragments, we focus on encoders specifically geared towards learning sentence
embeddings in this work.

Harnessing the vast availability of text data, contemporary encoders are
typically neural networks trained such that texts with similar content are
more similar in the representation space under some measure, like cosine
similarity. That is, if $t_{1},t_{2}\in\mathcal{T}$ are similar in content,
then $\text{sim}(f_{\theta}(t_{1}),f_{\theta}(t_{2}))$ is large (and
positive). This similarity space suggests a natural approach for retrieving
exercises: Pass each exercise $e_{i}$ through the model $f_{\theta}$ to obtain
its embedding representation $f_{\theta}(e_{i})$.222 We slightly abuse
notation here and write $f_{\theta}(e_{i})$ to mean either
$f_{\theta}(e_{i}^{(\texttt{L1})})$ or $f_{\theta}(e_{i}^{(\texttt{L2})})$.
The choice to compare against the representation of the L1 or L2 sentence is
explored in Section 4.  Then, when a learner provides an input $t$, pass $t$
through the model to obtain $f_{\theta}(t)$ and return the $K$ exercises with
largest cosine similarity $\text{sim}(f_{\theta}(e_{i}),f_{\theta}(t))$. As we
see in Section 3.3, direct similarity search often retrieves sentences
featuring “language about language”, which are often irrelevant to the
learner’s input. This leads us to leverage the generative abilities of LLMs,
as we discuss next.

Figure 3. TSNE visualization of exercise, learner input, and GPT-4-synthesized
retrieval candidate representations in the representation space of a trained
mBERT encoder (left). Learner inputs concentrate in the language about
language region (top right), making direct similarity search sub-optimal.
Retrieval candidates bridge the referential similarity gap between learner
inputs and exercise text and are close in similarity to exercises that meet
the learner’s specifications (bottom right).

###  3.2. mHyER: augmenting direct search with generative capabilities.

If large quantities of relevance data were available, we could train a model
to approximate the relevance probability in Equation 1 by learning a
representation space where learner inputs and relevant exercises are
considered similar and then performing direct search. However, input relevance
data is unlikely to be available at the scale necessary to train such a model.
Instead, we propose mHyER, visualized in Figure 2, which after a multilingual
contrastive training stage, retrieves exercises in a two-step manner. First,
we sample a set of $N_{c}$ hypothetical exercises from the exercise
distribution _conditioned on the learner input_. We call these sampled
exercises our _retrieval candidates_. In principle, we do not have access to
this exact distribution, but we can efficiently approximate sampling via LLM.
Second, we use the retrieval candidates to perform similarity search via
$K$-nearest neighbors. mHyER is inspired by two complementary methods: the
multilingual contrastive learning approach of (Wang et al., 2022b), and the
HyDE retrieval method of (Gao et al., 2023). We now discuss both the training
and retrieval stages in greater detail.

Stage 1: Learning a multilingual similarity space. While we operate in a
setting where no explicit learner relevance data is provided, the multilingual
nature of our exercises implies that a certain structure should exist in our
representation space. Namely, the sentence $e_{i}^{(\texttt{L1})}$ in L1
should be similar to its translation $e_{i}^{(\texttt{L2})}$ in L2. To ensure
this structure is reflected in our representation space, we take inspiration
from (Wang et al., 2022b) and utilize multilingual contrastive learning, an
unsupervised approach that aims to learn a representation where similar items
(called _positive_ pairs) are closer together and dissimilar items (called
_negative_ pairs) are far apart. For exercise $e_{i}$, the contrastive loss
$\mathcal{L}_{i}$ with a mini-batch of $N_{B}$ sentence pairs is

(2)
$\displaystyle\mathcal{L}_{i}=-\log\frac{\exp\left(\text{sim}\left(f_{\theta}(e_{i}^{(\texttt{L1})}),f_{\theta}(e_{i}^{(\texttt{L2})})\right)/\tau\right)}{\sum_{j=1}^{N_{B}}\exp\left(\text{sim}\left(f_{\theta}(e_{i}^{(\texttt{L1})}),f_{\theta}(e_{j}^{(\texttt{L2})})\right)/\tau\right)},$

where $\tau$ is the user-set temperature parameter and
$\text{sim}\left(\cdot,\cdot\right)$ is the cosine similarity:

(3)
$\displaystyle\text{sim}\left(f_{\theta}(t_{1}),f_{\theta}(t_{2})\right)=\frac{\langle
f_{\theta}(t_{1})f_{\theta}(t_{2})\rangle}{\lVert
f_{\theta}(t_{1})\rVert_{2}\lVert f_{\theta}(t_{2})\rVert_{2}}.$

In this work, rather than train a sentence encoder from scratch, we follow the
commonly accepted practice of initializing our encoder with existing BERT-
based checkpoints and contrastively finetuning these checkpoints on exercise
data.

Stage 2: Sampling retrieval candidates and exercise retrieval. A core
component of mHyER is sampling from the exercise distribution conditioned on
the learner input. While we cannot sample directly from this distribution, we
can approximate sampling with a LLM. In particular, we prompt the LLM with a
fixed a description of the exercise distribution and instruct the LLM to
synthesize _hypothetical_ exercises based on this description and based on a
learner’s input. Crucially, we can synthesize exercises _without requiring any
labeled examples_ , i.e., we do not embed examples of inputs and relevant
exercises in the prompt. To retrieve exercises, the LLM synthesizes $K_{h}$
hypothetical exercises, which we denote
$\tilde{e}_{1},\ldots,\tilde{e}_{K_{h}}$. We then encode these hypothetical
exercises via $f_{\theta}$ to obtain $K_{h}$ vectors
$f_{\theta}(\tilde{e}_{1}),\ldots,f_{\theta}(\tilde{e}_{K_{h}})$. To retrieve
exercises, we retrieve the $K$ exercises that have the highest similarity
score compared to the average of the $K_{h}$ vectors:
$\frac{1}{K_{h}}\sum_{i=1}^{K_{h}}f_{\theta}(\tilde{e}_{i})$. We use GPT-4
(OpenAI, 2023) in this work, but in practice, any LLM of sufficient capacity
can be used.

###  3.3. Bridging the referential similarity gap with mHyER.

In an effort to better understand the task of retrieving exercises from
learner inputs, we crowdsourced a small dataset of learner inputs from users
of Duolingo, a popular language learning app. We then contrastively finetune
mBERT with roughly 40,000 real exercises from the app, spanning 4 different
language courses. To get a sense of how contrastively learned similarity
spaces reflect learner inputs and exercise text, we visualize our collected
data, along with a subsample of the exercises, via TSNE in Figure 3. This
visualization reveals a fundamental referential similarity gap between learner
inputs and exercise text: How learners describe what they want to learn
occupies a distinct part of the representation space, characterized by
explicit use of words or phrases about language (e.g., “verbs”, “past tense”,
“adjectives”). We refer to this region as the “language about language”
region. As a result, direct similarity search yields exercises that similarly
contain words explicitly about language. As shown in Figure 3, the input “past
tense verbs” is most similar to exercises about language (e.g., “I explained
the new words to him”). Figure 3 also highlights how synthesizing retrieval
candidates helps bridge this referential similarity gap by “translating” the
learner’s input (which is typically expressed in “language about language”) to
a hypothetical in-distribution exercise whose content satisfies the learner
input. We provide concrete examples of learner inputs and synthesized
retrieval candidates in Table 1.

Table 1. Examples of collected learner inputs and retrieval candidates synthesized based on the learner input via GPT-4. For a variety of input types, GPT-4 is able to bridge the referential similarity gap by synthesizing text that closely resembles real exercise text while incorporating the concept that the learner wants to learn. Input | Synthesized retrieval candidates |
---|---|---
Past tense |  | They went to the concert last night.
---
Did you finish your project on time?
We didn’t have any coffee this morning.
| She cooked a delicious meal for us.
---
He had never seen such a beautiful sunset.
Were they able to solve the problem?
Future tense |  | She will be moving to France next year.
---
I won’t attend the party tonight.
When will you finish the project?
| They’ll be studying for the exam tomorrow.
---
In five years, I’ll have my own business.
We’re going to plant a garden this summer.
| Present
---
progressive
verbs
| Are you studying for the test?
---
She’s preparing dinner for tonight.
They’re practicing their dance routine.
| He’s not listening to the lecture.
---
I’m writing a letter to my friend.
The cat is chasing its tail.
| Idiomatic
---
syntax
| It’s raining cats and dogs!
---
Don’t put all your eggs in one basket.
He’s feeling under the weather.
| She has a heart of gold.
---
I’m on cloud nine.
Keep your chin up!
| How to order
---
food at a
restaurant
| Could I see the menu, please?
---
I’d like to order the grilled salmon.
Does this dish contain any nuts?
| May I have a glass of water?
---
Can I substitute fries for a salad?
Are there any vegetarian options?

##  4\. Datasets and experimental results

In this section, we first give an overview of two novel datasets specifically
for the task of learner directed language learning. We then compare mHyER
against a variety of baselines on these datasets.

###  4.1. Datasets

Duolingo Relevance (DuoRD) Dataset. To evaluate our method, we collected a
small scale dataset of 61 learner inputs from learners of Duolingo, a popular
language learning app. For each input, we asked the learner to rate 15
exercises as relevant or irrelevant to their input, resulting in 915 total
exercises rated. Exercises were sourced a pool of approximately 40,000
sentence pairs across four distinct courses. To ensure that the dataset was
not skewed too heavily towards relevant or irrelevant responses, we utilize a
sampling approach. Using mHyER, we retrieved the top 555 exercises in terms of
similarity. To form the set of 15 exercises for the learner to rate, we select
the top 5 scoring exercises deterministically (Tier 1). From the next 50
highest scoring exercises, we randomly select 5 exercises uniformly at random
without replacement (Tier 2). We repeat this sampling again, randomly drawing
5 exercises from the remaining 500 exercises (Tier 3). We observe that 64% of
exercises from Tier 1 were rated as relevant, 50% from Tier 2, and 34% from
Tier 3, resulting in 49% of all exercises rated as relevant.

Tatoeba Tags dataset. To test our method on a larger scale, we construct a
retrieval dataset from Tatoeba, a public database of sentences and their
translations. We begin by noting that when sentences are uploaded to Tatoeba,
they are often tagged by grammatical concepts, language specific concepts, or
topics. For example, the sentence “The brown bear is an omnivore” is tagged
with “animals” and the sentence “That way I kill two birds with one stone” is
tagged with “idiomatic expression”. We treat each of these tags as a learner
input, and deem an exercise relevant if it has been tagged accordingly. While
per sentence tags are not necessarily exhaustive, they provide useful signal
for evaluating retrieval approaches with typical retrieval metrics as well as
binary classification metrics, as we discuss in the Section 4.2. We form 3
benchmarks for evaluation, collectively referred to as the Tatoeba Tags
dataset:

  * •

English benchmark: only English sentences with 139 tags and 89,392 sentences.

  * •

Spanish from English benchmark: Spanish-English sentence pairs with 114 tags
in Spanish and 49,258 pairs.

  * •

English from Spanish benchmark: Spanish-English sentence pairs with 108 tags
in Spanish and 46,837 pairs.

To form the benchmarks, we collect all tags corresponding to the benchmark,
filter out tags and sentences containing profanity, merge similar tags
together, and then perform benchmark specific language and content processing.
We then keep only the tags with more than 20 sentences and download the
corresponding sentences. The benchmark specific processing is done to better
align the benchmark with how learners would interact with real-world language
learning courses. Specifically, we perform both language and content
processing. For language processing, we translate all tags (which appear in a
variety of languages) to the L1. This is done to emulate the learning process:
we use tags as a stand-in for learner inputs, which are likely to be the
learner’s L1. For content processing, we remove tags that do not make sense in
the context of a particular learning direction. For example, a Spanish speaker
learning English would not input “voseo” (a Spanish grammatical concept), nor
would an English speaker learning Spanish input “British English”.

###  4.2. Evaluation procedure and metrics

For the DuoRD dataset, we treat the 915 exercises that have been rated for
some learner input as the exercise set. Because each of the 915 exercises was
not assigned a relevance rating for every learner inputs, we cannot use
typical information retrieval metrics such as Recall or Precision. As a
result, we treat evaluation on this dataset as a binary classification
problem, where the goal is to predict whether an exercise is relevant or
irrelevant. To evaluate methods, we use area under the receiver operating
characteristic curve (AUC) and accuracy. To compute AUC, for each retrieved
exercise, we compute a score equal to the similarity measure between the
retrieval candidate and all exercises. We then aggregate relevance labels and
scores across all learner inputs to define the ROC curve. To compute accuracy,
we compute the scores as in AUC, and set a threshold such that any exercise
above the threshold is deemed relevant and vice versa. Because the similarity
score ranges between -1 and 1, we set the threshold by sweeping over $[-1,1)$
in increments of $0.1$. We then report the highest accuracy among all
thresholds in the sweep.

For the Tatoeba Tags dataset, because we have a notion of relevance, as
indicated by the presence of a tag, we utilize Precision@$K$, which is a
common metric in information retrieval that reports the fraction of the $K$
retrieved exercises that are relevant. To compute Precision@$K$, we retrieve
$K$ sentences per learner input (i.e., tag) and record the fraction of the $K$
retrieved sentences tagged with the learner input tag. Because the tagging of
Tatoeba sentences is not exhaustive, the absolute values of reported
Precision@$K$ may be low, but relative performance still indicates how methods
would perform if tagging was comprehensive. In light of this, we again follow
the evaluation approach of the DuoRD dataset and report AUC.

When performing evaluation in both datasets, we can retrieve exercises in two
distinct ways. We can synthesize retrieval candidates in the L1 and perform
similarity search on the L1 exercise texts. Alternatively, we can synthesize
retrieval candidates in the L2 and perform similarity search on the L2
exercise texts (example translations). As a result, we report AUC, accuracy,
and precision@$K$ in both the L1 and L2 setting.

###  4.3. Baselines

For both the DuoRD dataset and Tatoeba tags dataset, we evaluate mHyER against
direct similarity search using BERT and mBERT (Devlin et al., 2019), as well
as the following BERT-based models: Contriever, mContriever (Izacard et al.,
2022), and SimCSE (Gao et al., 2021). In particular, we use the BERT
${}_{\texttt{base}}$ (110 million parameters) variant of each of the above
methods. These methods achieve strong unsupervised performance in a variety of
retrieval and semantic text similarity tasks. BERT and mBERT were trained in a
self-supervised manner by using masked language modeling and next sentence
prediction objectives, with the only difference being the training data (only
English for BERT and a multilingual corpus for mBERT).

Contriever and mContriever propose two new approaches in contrastively tuning
BERT: (1) utilizing an inverse-cloze task and independent cropping as means of
forming positive pairs and (2) utilizing a Momentum encoder as described in
(Izacard et al., 2022) to ensure better representation of negative items.
Contriever is initialized with BERT and trained on English CCNet (Wenzek et
al., 2020) and Wikipedia data, whereas mContriever was initialized with mBERT
and trained on multiple languages in CCNet. We also consider supervised
variants of Contriever and mContriever, which are finetuned on the MS MARCO
(Bajaj et al., 2016), a large scale retrieval dataset. SimCSE uses dropout to
create synthetic positive pairs for the contrastive loss by passing the same
sentence through the encoder with different random dropout parameters.
Starting with BERT, SimCSE is trained on Wikipedia data.

Table 2. Examples of exercises retrieved with direct similarity search and mHyER for the same input on the Tatoeba Tags English Benchmark. Direct similarity search is not capable of bridging the fundamental referential similarity gap between learner inputs and exercise content, as illustrated by “Subject verb agreement”, “Second person”, and “Colloquial” inputs. In settings where learners ask about specific topics, direct similarity search returns exercises that most literally match the learner input, as shown with the “Preference”, “Cooking” and “Sports” inputs. On the other hand, mHyER retrieves exercises well aligned with the learner input. Input | Direct similarity search | mHyER
---|---|---
| Subject verb
---
agreement
| Correct the underlined words
---
That’s a transitive verb
It’s a transitive verb
| The dogs are in the garden
---
They grow flowers in the garden
The children are playing in the garden
Second person |  | It’s secondhand
---
It is secondhand
Next person please
| Are you sure you want me to help you with your homework?
---
I’m assuming you could speed through your testimony…
Will you please check to see if my order has been dealt with?
Colloquial |  | Be punctual
---
Speaking
Talk is cheap
| You drive me round the bend
---
You’re laying it on a bit thick
You’re joshing me
Preference |  | Make your choice
---
Compromise
Make a choice
| Which do you like better, Mexican food or Chinese food?
---
Which sweet do you prefer?
Which do you better, pizza or tacos?
Cooking |  | My hobby is cooking
---
Eat and drink
Do the laundry
| Pour melted butter over the popcorn
---
Add the chives and season the salad
Will you warm up the soup?
Sports |  | I like playing sports
---
I love sports
I like sports
| One must practice every day in order to become a worldclass athlete
---
Which do you like better skating or skiing?
Which do you like better cycling or jogging?
Figure 4. Length of the top 3 retrieved exercise sentences, measured in number
of characters, for direct similarity search and mHyER. Exercises retrieved via
direct similarity search are inherently _biased_ in length, with a majority of
exercises being relatively short. Using mHyER results in exercises of more
varied length. This variation in length aligns well with the global
distribution of exercises, showing that mHyER effectively translates learner
inputs to the in-distribution exercises.

###  4.4. Direct similarity search vs. mHyER: A qualitative case study

Before we present our full experimental results, we first present examples of
inputs and retrieved sentences on the English benchmark of the Tatoeba Tags
dataset. To qualitatively gauge the difference between direct similarity
search and mHyER, we provide examples of retrieved exercises for a small
number of inputs in Table 2. We present the top three retrieved exercises
measured in terms of similarity score for both direct similarity search and
mHyER, using mBERT finetuned on Tatoeba data as our similarity space. The
input “Subject verb agreement” highlights the “language about language”
phenomena: Instead of retrieving exercises containing correct subject verb
agreement, direct similarity retrieves exercises in the “language about
language” part of the similarity space. These exercises contain words such as
“words” and “verb”. On the other hand, mHyER is capable of bridging the gap
between input and exercises, retrieving exercises that focus on ensuring
sentences with plural objects have the right verb form. The “Preference” input
illustrates an example of a nebulous input, as the learner wants exercises
that have to do with expressing preferences. However, direct similarity search
returns exercises explicitly about “choice”, whereas mHyER retrieves exercises
that have learners practice expressing preference in more natural settings.
The last two inputs, “Cooking” and “Sports”, illustrate instances where direct
similarity search yields exercises that too literally match the input.

Aside from retrieval quality, we observe that retrieved results from direct
similarity search also suffer from _sentence length bias_. In contrastively
learned similarity spaces, it has been empirically observed that the length of
a sentence is implicitly encoded in the representation of a sentence, meaning
sentences of a similar length are more likely to be considered similar (Wu et
al., 2022). The retrieved exercises from direct similarity search shown in
Table 2 clearly exhibit this bias whereas those retrieved via mHyER exhibit a
higher variation in length. We confirm that this phenomena holds for all
inputs in the Tatoeba Tags English benchmark by retrieving the top 3 exercises
across all 139 tags with both direct similarity search and mHyER. For each
exercise, we record its length (measured in number of characters). As shown in
Figure 4, exercises retrieved with mHyER are longer on average, aligning
remarkably well with the global sentence length distribution. On the other
hand, direct similarity search yields sentences that are notably shorter on
average. This empirical observation highlights that generating in-distribution
retrieval candidates allows us to retrieve sentences of varied length that
track well with our set of exercises.

###  4.5. Experimental results

Table 3. Evaluation results on the DuoRD dataset. $\text{mHyER}_{[\texttt{model}]}$ indicates that contrastive finetuning was employed with [model] as the initial checkpoint. $+\text{DuoRD dataset}$ denotes that the DuoRD dataset was used for contrastive finetuning. In all cases, mHyER outperforms relevant baselines dramatically. |  |  | AUC
---
L1
| AUC
---
L2
| Accuracy @ threshold
---
L1
| Accuracy @ threshold
---
L2
Unsupervised pretraining | BERT | 0.458 | 0.421 | 0.491 @ -1.0 | 0.507 @ 0.9
mBERT | 0.485 | 0.471 | 0.491 @ -1.0 | 0.491 @ -1.0
Contriever | 0.565 | 0.586 | 0.557 @ 0.4 | 0.540 @ 0.3
mContriever | 0.497 | 0.499 | 0.548 @ 0.6 | 0.523 @ 0.5
SimCSE | 0.579 | 0.536 | 0.564 @ 0.5 | 0.523 @ 0.4
| $\text{mHyER}_{\text{mBERT}}$
---
+DuoRD dataset
0.679 | 0.669 | 0.631 @ 0.5 | 0.605 @ 0.5
| $\text{mHyER}_{\text{mContriever}}$
---
+DuoRD dataset
0.680 | 0.678 | 0.635 @ 0.3 | 0.624 @ 0.3
Supervised pretraining |  Contriever-sup | 0.609 | 0.605 | 0.579 @ 0.3 | 0.581 @ 0.2
mContriever-sup | 0.558 | 0.543 | 0.541 @ 0.3 | 0.529 @ 0.3
| $\text{mHyER}_{\text{Contriever}-\texttt{sup}}$
---
+DuoRD dataset
0.674 | 0.578 | 0.632 @ 0.4 | 0.562 @ 0.4
| $\text{mHyER}_{\text{mContriever}-\texttt{sup}}$
---
+DuoRD dataset
0.684 | 0.678 | 0.637 @ 0.3 | 0.612 @ 0.4
Table 4. Evaluation results on the Tatoeba Tags dataset. $\text{mHyER}_{[\texttt{model}]}$ indicates that contrastive finetuning was employed with [model] as the initial checkpoint. $+[\texttt{dataset name}]$ denotes that [dataset name] data was used for contrastive finetuning. In all cases, mHyER outperforms relevant baselines dramatically, with large gains coming from finetuning on _out-of-distribution_ data. | English | English (L2) from Spanish (L1) | Spanish (L2) from English (L1)
---|---|---|---
|  | AUC | P@15 |  | AUC
---
L1
| AUC
---
L2
| P@15
---
L1
| P@15
---
L2
| AUC
---
L1
| AUC
---
L2
| P@15
---
L1
| P@15
---
L2
Unsupervised pretraining | BERT | 0.495 | 0.032 | 0.481 | 0.428 | 0.019 | 0.020 | 0.492 | 0.505 | 0.044 | 0.020
mBERT | 0.468 | 0.037 | 0.446 | 0.487 | 0.038 | 0.040 | 0.469 | 0.442 | 0.039 | 0.019
Contriever | 0.536 | 0.161 | 0.542 | 0.523 | 0.112 | 0.073 | 0.529 | 0.549 | 0.165 | 0.087
mContriever | 0.571 | 0.064 | 0.438 | 0.503 | 0.051 | 0.063 | 0.559 | 0.564 | 0.061 | 0.027
SimCSE | 0.646 | 0.115 | 0.535 | 0.559 | 0.069 | 0.054 | 0.635 | 0.610 | 0.127 | 0.068
| $\text{mHyER}_{\text{mBERT}}$
---
+en-from-es
0.722 | 0.225 | 0.686 | 0.701 | 0.227 | 0.208 | 0.710 | 0.696 | 0.243 | 0.242
| $\text{mHyER}_{\text{mBERT}}$
---
+es-from-en
0.717 | 0.223 | 0.697 | 0.693 | 0.219 | 0.211 | 0.702 | 0.706 | 0.237 | 0.244
| $\text{mHyER}_{\text{mBERT}}$
---
+DuoRD dataset
0.752 | 0.211 | 0.734 | 0.738 | 0.215 | 0.206 | 0.739 | 0.757 | 0.225 | 0.242
| $\text{mHyER}_{\text{Contriever}}$
---
+DuoRD dataset
0.768 | 0.239 | 0.644 | 0.780 | 0.106 | 0.232 | 0.749 | 0.659 | 0.265 | 0.099
| $\text{mHyER}_{\text{mContriever}}$
---
+DuoRD dataset
0.729 | 0.258 | 0.748 | 0.723 | 0.267 | 0.264 | 0.713 | 0.744 | 0.271 | 0.294
Supervised pretraining |  Contriever-sup | 0.541 | 0.164 | 0.491 | 0.492 | 0.120 | 0.086 | 0.530 | 0.492 | 0.180 | 0.105
mContriever-sup | 0.575 | 0.104 | 0.548 | 0.510 | 0.126 | 0.108 | 0.560 | 0.581 | 0.112 | 0.101
| $\text{mHyER}_{\text{Contriever}-\texttt{sup}}$
---
+DuoRD dataset
0.775 | 0.246 | 0.668 | 0.797 | 0.102 | 0.240 | 0.760 | 0.692 | 0.268 | 0.108
| $\text{mHyER}_{\text{mContriever}-\texttt{sup}}$
---
+DuoRD dataset
0.738 | 0.255 | 0.761 | 0.734 | 0.260 | 0.264 | 0.722 | 0.752 | 0.255 | 0.280

In this section, we present our experimental results on the DuoRD dataset and
Tatoeba Tags dataset. For both datasets, we consider two starting points for
fine-tuning the BERT embedding model: _Unsupervised pretraining_ , where we
contrastively train a BERT checkpoint that has been pretrained in an
unsupervised manner, and _supervised pretraining_ , where we start with a BERT
checkpoint that has been pretrained on MS MARCO (Bajaj et al., 2016), a large
scale retrieval dataset that covers different tasks, such as passage ranking
and keyphrase extraction. In all settings, $\text{mHyER}_{[\texttt{model}]}$
denotes mHyER with starting with [model] as its initial checkpoint for
contrastive training. [model]-sup indicates [model] was trained in a
supervised manner. We emphasize that at no point in training mHyER is labeled
training data for exercise retrieval used; sup only indicates MS MARCO was
used to train the initial BERT checkpoint. For all experiments, we take the
[CLS] representation as the sentence representation, except when working with
Contriever and mContriever, where we use their custom mean pooling333See
https://huggingface.co/facebook/contriever for further details.. For all
experiments with mHyER, we adopt the training setup of (Wang et al., 2022b),
which is adapted from (Gao et al., 2021), including all default
hyperparameters. For retrieval, we synthesize $K_{h}=10$ hypothetical
retrieval candidates from GPT-4 and perform nearest neighbors search with the
averaged embedding of all $K_{h}$ candidates.

DuoRD dataset. The evaluation results of baselines and mHyER on the DuoRD
dataset are presented in Table 3. For both unsupervised and supervised
settings, we contrastively finetune BERT checkpoints on the full 40K exercises
in the DuoRD dataset. In the unsupervised pretraining setting, we start our
contrastive finetuning with two multilingual checkpoints: mBERT and
mContriever. In this setting, mHyER outperforms all relevant baselines in both
AUC and accuracy, with mHyER ${{}_{\text{mContriever}}}$ achieving the best
performance among all methods. mHyER ${{}_{\text{mContriever}}}$ results in
36.8% and 40.2% AUC gains over mContriever and mBERT, respectively. It is
notable that direct similarity search generally fails to perform well,
highlighting that the gap between learner inputs and relevant exercises: BERT,
mBERT, and mContriever baselines fail to even achieve an AUC of 0.5
corresponding to random guessing, reinforcing the fact that direct similarity
search cannot overcome the fundamental mismatch between how learners describe
what they want to learn and exercise content. In the supervised pretraining
setting, we start our finetuning from the Contriever-sup and mContriever-sup
checkpoints, which were finetuned on labeled MS MARCO data. mHyER once again
outperforms all baselines, with mHyER ${}_{\text{mContriever}-\texttt{sup}}$
as the best performing method. Here, supervised pretraining modestly improves
the performance of direct similarity search, suggesting that supervised
pretraining can lessen the referential similarity gap in a limited manner. The
improvement due to supervised pretraining is less pronounced when utilizing
mHyER, with even one instance of decreased accuracy. This suggests synthesized
retrieval candidates bridge the gap to the point where further improvement is
difficult.

Tatoeba Tags dataset. The evaluation results of baselines and mHyER on the
Tatoeba Tags dataset are presented in Table 4. On this dataset, we experiment
with contrastive finetuning on _out-of-distribution data_. This experiment was
inspired by empirical observations from finetuning mBERT. In particular, we
contrastively finetuned mBERT on the Spanish from English benchmark (denoted
es-from-en) and the English from Spanish benchmark (denoted en-from-es), as
well as the 40K _out-of-distribution_ sentence pairs from the DuoRD dataset
(which contains English-Spanish pairs). We observe that finetuning on the
DuoRD dataset outperforms finetuning on in-distribution data. This surprising
observation leads us to finetune Contriever and mContriever checkpoints with
the DuoRD dataset in both the unsupervised and supervised settings. In the
unsupervised setting, we once again observe poor performance from direct
similarity search baselines and sizable increases in performance when using
mHyER: Up to 39% increases in AUC and more than doubling the performance of
precision@15 between the best mHyER method and best direct similarity. We
observe similar gains in the supervised pretraining setting. Methods that use
Contriever (pretrained only on English data) typically perform better when
retrieving in English, whereas methods using mContriever typically perform
better in multilingual settings.

###  4.6. Ablation study

Table 5. Ablation results on the Tatoeba Tags dataset. We experiment by removing either the contrastive finetuning step or the retrieval candidate synthesis step. +GPT indicates that retrieval candidates were used with no contrastive finetuning, whereas +DuoRD dataset indicates that direct similarity search was used after contrastively finetuning on the DuoRD dataset. In a vast majority of cases, contrastive finetuning and retrieval candidate synthesis boost performance, with retrieval candidates generally contributing more. | English | English (L2) from Spanish (L1) | Spanish (L2) from English (L1)
---|---|---|---
|  | AUC | P@15 |  | AUC
---
L1
| AUC
---
L2
| P@15
---
L1
| P@15
---
L2
| AUC
---
L1
| AUC
---
L2
| P@15
---
L1
| P@15
---
L2
Unsupervised pretraining | mContriever | 0.571 | 0.064 | 0.438 | 0.503 | 0.051 | 0.063 | 0.559 | 0.564 | 0.061 | 0.027
| mContriever
---
+GPT
0.676 | 0.237 | 0.613 | 0.663 | 0.213 | 0.213 | 0.643 | 0.602 | 0.245 | 0.217
| mContriever
---
+DuoRD dataset
0.665 | 0.096 | 0.670 | 0.665 | 0.119 | 0.106 | 0.656 | 0.657 | 0.090 | 0.077
| $\text{mHyER}_{\text{mContriever}}$
---
+DuoRD dataset
0.729 | 0.258 | 0.748 | 0.723 | 0.267 | 0.264 | 0.713 | 0.744 | 0.271 | 0.294
Supervised pretraining |  mContriever-sup | 0.575 | 0.104 | 0.548 | 0.510 | 0.126 | 0.108 | 0.560 | 0.581 | 0.112 | 0.101
|  mContriever-sup
---
+GPT
0.731 | 0.250 | 0.642 | 0.724 | 0.238 | 0.243 | 0.706 | 0.636 | 0.263 | 0.258
|  mContriever-sup
---
+DuoRD dataset
0.672 | 0.106 | 0.678 | 0.677 | 0.128 | 0.120 | 0.662 | 0.661 | 0.113 | 0.091
| $\text{mHyER}_{\text{mContriever}-\texttt{sup}}$
---
+DuoRD dataset
0.738 | 0.255 | 0.761 | 0.734 | 0.260 | 0.264 | 0.722 | 0.752 | 0.255 | 0.280

The two key steps in mHyER are multilingual contrastive pretraining and
synthesizing retrieval candidates. To characterize the relative contributions
of each step, we create variants of mHyER performing direct similarity search
after contrastive pretraining or retrieving with GPT-synthesized retrieval
candidates with a non-finetuned encoder (i.e., HyDE (Gao et al., 2023)). As
shown in Table 5, the combination of both stages yields the best performance
in the vast majority of cases. Utilizing only synthesized retrieval candidates
results in the larger increases in precision compared to contrastive
finetuning, while the opposite is true for AUC. This suggests that the two
steps drive performance increases in complementary ways: Contrastive
finetuning changes the similarity space such that relevant exercises are
closer to learner inputs at a _global_ level, resulting in increases in AUC
(which measures a global ranking of predicitions). However, direct similarity
search still cannot overcome referential similarity gaps, and hence, increases
in precision@$15$ are low relatively. Meanwhile, synthesizing retrieval
candidates directly improves retrieval quality, resulting in higher retrieval
quality, but does not change representations, resulting in relatively lower
increases in AUC.

##  5\. Discussion

In this paper, we introduce the problem of exercise retrieval for learner
directed language learning and highlight an important challenge in this
setting: how learners express what they want to learn and exercise content are
fundamentally semantically different. The effects of this referential
similarity gap are especially pronounced when attempting to retrieve exercises
via direct similarity search: even models supervised on MS MARCO, a large
scale retrieval dataset, struggle to bridge this referential similarity gap.
As a result, we propose mHyER, a zero-shot retrieval approach that leverages
the generative capabilities of pretrained LLMs to synthesize relevant in-
distribution sentences which are then used to retrieve exercises. We form two
novel benchmark datasets by collecting human responses and processing publicly
available data. mHyER outperforms several strong baselines, including ones
trained in a supervised fashion.

Future work. mHyER lays the methodological foundation for self-directed online
language learning. Many interesting directions of future work exist, ranging
from investigating different learning areas to methodological extensions that
accommodate labeled relevance information. We discuss several of these
directions below.

mHyER provides concrete methodology that can enable future investigations into
the effects of self-directed learning on long-term learning outcomes and
curriculum design at scale. Self-directed learning also play a role in
improving other components of personalized education systems. For example, a
learner input into a self-directed learning system can be viewed as an
indicator of a self-perceived weakness, which would provide a powerful form of
supervision for estimating user skill levels. Studying how inputs and outputs
of complementary parts of a unified personalized education system is an
important direction of future work.

Another interesting avenue of future work is investigating if analogous
“language about language” phenomena appear in settings other than language
learning. We hypothesize that such phenomena exist in one form or another
across all learning settings. For example, how learners describe what they
want to review in math (e.g., “right angles”) exhibits a similar fundamental
mismatch with exercise text (e.g., “Compute the length of the hypotenuse of
this triangle”). If such gaps exist, methods capable of bridging the
referential similarity gap, like mHyER, will be required across different
learning settings. Characterizing the degree to which such gaps appear, as
well as how such gaps differ, in different learning settings remains important
and open work.

From a system design and learner experience perspective, developing machine
learning methods to retrieve relevant exercises based on learner inputs is a
foundational piece of any self-directed language learning system. However,
serving a set of exercises that maximizes relevance may not lead to the best
learner experience. Instead, the objective of exercise retrieval can be made
more flexible: Instead of retrieving $K$ exercises that maximize relevance, we
retrieve all exercises with scores that exceed some pre-determined threshold.
Then, this set of relevant exercises can be re-ranked based on additional
criteria, such as difficulty level (with information from Knowledge Tracing-
based parts of the system) or diversity (in terms of difficulty or length).
Regardless of precise objective (top $K$ vs. all relevant exercises), the
referential similarity gap persists, making mHyER especially suitable for this
initial retrieval step.

Methodologically, mHyER was designed explicitly with the goal of zero-shot
retrieval. However, opportunities to collect learner relevance feedback grow
as self-directed learning systems get implemented. Such feedback can then be
used to train retrieval methods. Investigating how to effectively use limited
learner feedback to help retrieval methods bridge the referential similarity
gap remains an open question. Additionally, extensions of mHyER to learning
settings with multi-modal exercises is direction of future work. Using newly
developed multi-modal models to measure similarity in different domains, such
as images or audio, can unlock a richer learning experience for learners.

Acknowledgements. We thank Ali Malik, Stephen Mayhew, and Mark Davenport for
their helpful comments, feedback, and support. AX was partially supported by
National Science Foundation grants IIS-2212182 and DMS-2134037.

## References

  * (1)
  * Abdelrahman and Wang (2019) Ghodai Abdelrahman and Qing Wang. 2019.  Knowledge Tracing with Sequential Key-Value Memory Networks. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM.
  * 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_ (2016).
  * Bonifacio et al. (2022) Luiz Bonifacio, Hugo Abonizio, Marzieh Fadaee, and Rodrigo Nogueira. 2022.  Inpars: Unsupervised dataset generation for information retrieval. In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 2387–2392.
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. 2020.  A simple framework for contrastive learning of visual representations. In _International Conference on Machine Learning (ICML)_. PMLR, 1597–1607.
  * Cheng et al. (2023) Qinyuan Cheng, Xiaogui Yang, Tianxiang Sun, Linyang Li, and Xipeng Qiu. 2023.  Improving Contrastive Learning of Sentence Embeddings from AI Feedback.  _arXiv preprint arXiv:2305.01918_ (2023).
  * Chuang et al. (2022) Yung-Sung Chuang, Rumen Dangovski, Hongyin Luo, Yang Zhang, Shiyu Chang, Marin Soljačić, Shang-Wen Li, Scott Yih, Yoon Kim, and James Glass. 2022.  DiffCSE: Difference-based Contrastive Learning for Sentence Embeddings. In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. 4207–4218.
  * Corbett and Anderson (1994) Albert T Corbett and John R Anderson. 1994.  Knowledge tracing: Modeling the acquisition of procedural knowledge.  _User modeling and user-adapted interaction_ 4 (1994), 253–278.
  * Cui and Sachan (2023) Peng Cui and Mrinmaya Sachan. 2023.  Adaptive and Personalized Exercise Generation for Online Language Learning. In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics_. 10184–10198.
  * Dai et al. (2022) Zhuyun Dai, Vincent Y Zhao, Ji Ma, Yi Luan, Jianmo Ni, Jing Lu, Anton Bakalov, Kelvin Guu, Keith Hall, and Ming-Wei Chang. 2022.  Promptagator: Few-shot Dense Retrieval From 8 Examples. In _The Eleventh International Conference on Learning Representations_.
  * 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 NAACL-HLT_. 4171–4186.
  * Gao et al. (2023) Luyu Gao, Xueguang Ma, Jimmy Lin, and Jamie Callan. 2023.  Precise Zero-Shot Dense Retrieval without Relevance Labels. In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics_. 1762–1777.
  * Gao et al. (2021) Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021.  SimCSE: Simple Contrastive Learning of Sentence Embeddings. In _2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021_. 6894–6910.
  * Geng et al. (2019) Shuang Geng, Kris MY Law, and Ben Niu. 2019.  Investigating self-directed learning and technology readiness in blending learning environment.  _International Journal of Educational Technology in Higher Education_ 16, 1 (2019), 1–22.
  * Hadsell et al. (2006) Raia Hadsell, Sumit Chopra, and Yann LeCun. 2006.  Dimensionality reduction by learning an invariant mapping. In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , Vol. 2. IEEE, 1735–1742.
  * Huang et al. (2022) Shuyan Huang, Qiongqiong Liu, Jiahao Chen, Xiangen Hu, Zitao Liu, and Weiqi Luo. 2022.  A Design of a Simple Yet Effective Exercise Recommendation System in K-12 Online Learning. In _International Conference on Artificial Intelligence in Education_. Springer, 208–212.
  * Izacard et al. (2022) Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. 2022.  Unsupervised Dense Information Retrieval with Contrastive Learning.  _Transactions on Machine Learning Research_ (2022).
  * 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)_. 6769–6781.
  * Kim and Jang (2015) Kyong-Jee Kim and Hye W Jang. 2015.  Changes in medical students’ motivation and self-regulated learning: a preliminary study.  _International journal of medical education_ 6 (2015), 213.
  * Krashen (2005) Stephen Krashen. 2005.  Free voluntary reading: New research, applications, and controversies.  _Anthology series-Seameo regional language centre_ 46, 1 (2005).
  * Lee et al. (2019) Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. 2019.  Latent Retrieval for Weakly Supervised Open Domain Question Answering. In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_. 6086–6096.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  _arXiv preprint arXiv:1907.11692_ (2019).
  * Lucieer et al. (2016) Susanna M Lucieer, Laura Jonker, Chris Visscher, Remy MJP Rikers, and Axel PN Themmen. 2016.  Self-regulated learning and academic performance in medical education.  _Medical teacher_ 38, 6 (2016), 585–593.
  * Mandasari and Wahyudin (2021) Berlinda Mandasari and Achmad Yudi Wahyudin. 2021.  Flipped classroom learning model: implementation and its impact on EFL learners’ satisfaction on grammar class.  _Ethical Lingua: Journal of Language Teaching and Literature_ 8, 1 (2021), 150–158.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  arXiv:2303.08774 [cs.CL]
  * Pandey and Karypis (2019) Shalini Pandey and George Karypis. 2019.  A Self-Attentive Model for Knowledge Tracing.  _International Educational Data Mining Society_ (2019).
  * Patall et al. (2008) Erika A Patall, Harris Cooper, and Jorgianne Civey Robinson. 2008.  The effects of choice on intrinsic motivation and related outcomes: a meta-analysis of research findings.  _Psychological bulletin_ 134, 2 (2008), 270.
  * Piech et al. (2015) Chris Piech, Jonathan Bassen, Jonathan Huang, Surya Ganguli, Mehran Sahami, Leonidas J Guibas, and Jascha Sohl-Dickstein. 2015.  Deep knowledge tracing.  _Advances in Neural Information Processing Systems_ 28 (2015).
  * Robertson et al. (2009) Stephen Robertson, Hugo Zaragoza, et al. 2009\.  The probabilistic relevance framework: BM25 and beyond.  _Foundations and Trends® in Information Retrieval_ 3, 4 (2009), 333–389.
  * Sachan et al. (2022) Devendra Sachan, Mike Lewis, Mandar Joshi, Armen Aghajanyan, Wen-tau Yih, Joelle Pineau, and Luke Zettlemoyer. 2022.  Improving Passage Retrieval with Zero-Shot Question Generation. In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_. 3781–3797.
  * Shin et al. (2021) Dongmin Shin, Yugeun Shim, Hangyeol Yu, Seewoo Lee, Byungsoo Kim, and Youngduck Choi. 2021.  Saint+: Integrating temporal features for ednet correctness prediction. In _LAK21: 11th International Learning Analytics and Knowledge Conference_. 490–496.
  * Thakur et al. (2021) Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. 2021.  BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track_.
  * Tong et al. (2020) Shiwei Tong, Qi Liu, Wei Huang, Zhenya Hunag, Enhong Chen, Chuanren Liu, Haiping Ma, and Shijin Wang. 2020.  Structure-based knowledge tracing: An influence propagation view. In _2020 IEEE International Conference on Data Mining (ICDM)_. IEEE, 541–550.
  * Wang et al. (2022a) Kexin Wang, Nandan Thakur, Nils Reimers, and Iryna Gurevych. 2022a.  GPL: Generative Pseudo Labeling for Unsupervised Domain Adaptation of Dense Retrieval. In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. 2345–2360.
  * Wang et al. (2022b) Yaushian Wang, Ashley Wu, and Graham Neubig. 2022b.  English Contrastive Learning Can Learn Universal Cross-lingual Sentence Embeddings. In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_. 9122–9133.
  * Wenzek et al. (2020) Guillaume Wenzek, Marie-Anne Lachaux, Alexis Conneau, Vishrav Chaudhary, Francisco Guzmán, Armand Joulin, and Édouard Grave. 2020.  CCNet: Extracting High Quality Monolingual Datasets from Web Crawl Data. In _Proceedings of the Twelfth Language Resources and Evaluation Conference_. 4003–4012.
  * Wu et al. (2022) Xing Wu, Chaochen Gao, Liangjun Zang, Jizhong Han, Zhongyuan Wang, and Songlin Hu. 2022.  ESimCSE: Enhanced Sample Building Method for Contrastive Learning of Unsupervised Sentence Embedding. In _Proceedings of the 29th International Conference on Computational Linguistics_. 3898–3907.
  * Wu et al. (2020) Zhengyang Wu, Ming Li, Yong Tang, and Qingyu Liang. 2020.  Exercise recommendation based on knowledge concept prediction.  _Knowledge-Based Systems_ 210 (2020), 106481.
  * Xu and Davenport (2020) Liangbei Xu and Mark A Davenport. 2020.  Dynamic Knowledge Embedding and Tracing.  _International Educational Data Mining Society_ (2020).
  * Yu et al. (2022a) Wenhao Yu, Dan Iter, Shuohang Wang, Yichong Xu, Mingxuan Ju, Soumya Sanyal, Chenguang Zhu, Michael Zeng, and Meng Jiang. 2022a.  Generate rather than Retrieve: Large Language Models are Strong Context Generators. In _The Eleventh International Conference on Learning Representations_.
  * Yu et al. (2022b) Yue Yu, Chenyan Xiong, Si Sun, Chao Zhang, and Arnold Overwijk. 2022b.  COCO-DR: Combating the Distribution Shift in Zero-Shot Dense Retrieval with Contrastive and Distributionally Robust Learning. In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_. 1462–1479.


# A Principled Framework for Knowledge-enhanced Large Language Model

Saizhuo Wang21$\text{, Zhihan Liu}^{4}\text{, Zhaoran Wang}^{4}\text{, Jian
Guo}^{13}$
1IDEA Research, International Digital Economy Academy
2The Hong Kong University of Science and Technology
3The Hong Kong University of Science and Technology (Guangzhou)
4Northwestern University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Work done during internship at IDEA
ResearchCorresponding Author

###### Abstract

Large Language Models (LLMs) are versatile, yet they often falter in tasks
requiring deep and reliable reasoning due to issues like hallucinations,
limiting their applicability in critical scenarios. This paper introduces a
rigorously designed framework for creating LLMs that effectively anchor
knowledge and employ a closed-loop reasoning process, enhancing their
capability for in-depth analysis. We dissect the framework to illustrate the
contribution of each component to the LLMs’ performance, offering a
theoretical assurance of improved reasoning under well-defined assumptions.

##  1 Introduction

Large language models (LLMs) have achieved notable success in natural language
understanding and generation, laying the foundation for numerous LLM agents.
These agents leverage LLMs as their cognitive nucleus, supplemented with
various tools, memory, and reasoning mechanisms. This integration empowers
them to conceptualize and act, thereby handling complex and pragmatic tasks.
While proficient in routine tasks like answering questions and assisting with
daily activities such as food orders, online purchases, and bookings, LLM
agents often fall short in knowledge-dense tasks that require complex
reasoning and inference. Such tasks demand intricate reasoning chains and high
factual accuracy, challenges that LLMs face due to their reliance on precise
prompt engineering, a constrained context window that cannot fully track
extensive reasoning processes, and the tendency to generate unverified
information, known as hallucinations.

Efforts to fortify factual accuracy have led to the integration of external
knowledge bases, like knowledge graphs and document databases, and the
enhancement of deep reasoning with iterative or recursive reasoning
mechanisms. Nevertheless, these solutions tend to focus on individual aspects
of the problem. Recognizing the need for a holistic approach, we introduce a
cohesive, principle-driven framework to tackle the challenge of deep and
responsible reasoning in LLMs. This framework systematically analyzes the
intricacies of designing such agents, discussing the architectural decisions
and what they mean for performance and functionality.

##  2 Background

###  2.1 Knowledge-driven LLM and LLM Agent

Current state-of-the-art large language models (LLMs) exhibit notable
deficiencies. They are particularly prone to producing content that may not be
factually accurate, commonly referred to as ’hallucinations’ [6].
Additionally, updating the knowledge within these models is a resource-
intensive process that typically requires retraining the entire model. To
mitigate these limitations, integrating LLMs with external knowledge bases,
such as a knowledge graph (KG), has emerged as a viable strategy. This
integration enables LLMs to ground their responses in the verifiable facts
stored in the KG, and updating knowledge becomes more manageable and cost-
effective through modifications to the KG. A common method in knowledge-driven
LLMs involves retrieving relevant information from the KG to provide context
for the LLM’s inference process. Leveraging LLMs’ ability to learn in context
[2], the output is made to align with the provided knowledge context,
enhancing consistency and reliability.

###  2.2 LLM Inference as Implicit Bayesian Inference

Recent research [5, 7] suggests that the inference mechanisms of Transformer-
based LLMs resemble implicit Bayesian inference. The process can be
mathematically represented as:

$p(y|x)=\int_{\theta}p(y|\theta,x)p(\theta|x)d\theta$ (1)

Here, $x$ denotes the given context, $y$ is the output from the LLM, and
$\theta$ symbolizes the latent ”concept” inferred from the context. This
conceptual model delineates LLM’s text generation process, which initially
deduces the latent concept from the context ($p(\theta|x)$) and subsequently
generates the output based on this deduced concept ($p(y|\theta,x)$). In the
context of knowledge-driven LLMs, the ”concept” encompasses the external
knowledge derived from the knowledge base, which is then seamlessly integrated
by the LLM with its pre-trained knowledge to formulate an accurate response.

Figure 1: Knowledge-driven LLM agent framework. This framework consists of two
levels of interaction. The inner level as shown in the left part corresponds
the iterative reasoning process between LLM and external knowledge base. The
outer level corresponds to the interaction between LLM agent and real world,
where feedbacks is provided to help the agent improve itself.

##  3 Framework

Our framework introduces a two-tiered process for reasoning with LLM agents:
the inner reasoning loop and the outer response-feedback loop. Initially, the
inner loop addresses a user’s natural language query by engaging the knowledge
base and producing a response. Once a response is generated, the outer loop
incorporates user feedback, which may suggest changes to the knowledge base,
to refine the agent’s future responses. This comprehensive approach ensures a
dynamic evolution of the agent’s capabilities, potentially extending across
various domains that utilize iterative learning and feedback. Our framework is
primarily examined in the context of knowledge-based question-answering (KBQA)
systems; however, its flexible architecture is also suitable for various
domains that benefit from iterative learning and feedback loops. Additionally,
although our framework is designed for iterative use, it can be adapted for
one-shot applications, aligning with numerous methodologies such as those that
inject knowledge into LLMs through fine-tuning.

###  3.1 The Inner Reasoning Loop

Algorithm 1 The inner reasoning loop

0: User question $q$, max reasoning step $T$, reward threshold $R$

0: Response $a$

1: $t\leftarrow 0,\mathcal{D}_{t}\leftarrow{q},terminal\leftarrow False$

2: $s_{t}\leftarrow\\{q,\emptyset,\emptyset\\}$

3: while $terminal\neq True$ do

4: $a^{s}_{t},a^{q}_{t}\leftarrow\text{Reason}(\mathcal{D}_{t})$

5:
$s^{p}_{t+1},s^{n}_{t+1}\leftarrow\text{Select\\_and\\_query}(s_{t},a^{s}_{t})$

6: $s_{t+1}\leftarrow(q,s^{p}_{t+1},s^{n}_{t+1})$

7: $r_{t}\leftarrow\text{Judge}(s_{t+1})$

8:
$\mathcal{D}_{t+1}\leftarrow\mathcal{D}_{t}\cup\\{(s_{t},a_{t},r_{t},s_{t+1})\\}$

9: $t\leftarrow t+1$

10: if $r_{t}\geq R\textbf{or\ }t\geq T$ then

11: $terminal\leftarrow True$

12: end if

13: end while

14: return $\text{summarize}(\mathcal{D}_{t})$

The inner loop models the interaction between the reasoning agent—either a
Large Language Model (LLM) or a rule-based system—and the knowledge base,
which could take the form of a knowledge graph, a document trove, or another
LLM. Each cycle involves the agent consulting the memory buffer, which begins
with the user’s question and is progressively enriched with data from the
knowledge base, to identify the next query. When the knowledge base receives a
query, it retrieves and supplies relevant information. Subsequently, a
judge—implemented through rules or an LLM—assesses the accumulated information
in the buffer to determine if it suffices to address the user’s question. The
loop concludes and formulates a response once it is determined that the
gathered information is adequate or when a predefined stopping point is
reached.

##### Components

The inner loop is a sequence of exchanges between the knowledge environment
and the reasoning agent. The knowledge environment is comprised of a knowledge
base, functioning as the transition model by processing queries and returning
results, and a judge module, which evaluates whether the reasoning agent’s
memory buffer contains adequate information to answer the user’s question. The
judge may operate as either a prompted LLM or a set of predefined stopping
rules. The reasoning agent hosts a memory buffer that retains the history of
reasoning trajectories and a reasoning module that devises actions based on
the buffer’s contents. At a given time step $t$, the memory buffer
$\mathcal{D}_{t}$ encapsulates the reasoning paths derived from the LLM. The
reasoning module, which may be an LLM or a suite of rules, inputs
$\mathcal{D}_{t}$ to generate an action.

##### MDP Formalization

At the core of the inner reasoning loop is the interaction between reasoning
agent and knowledge base, which we model as a Markov Decision Process (MDP).
This MDP is defined by the tuple $(\mathcal{S},\mathcal{A},T,r,\gamma)$, where
each component is characterized as follows:

  * •

State Space $\mathcal{S}$: The state at any time $t$, denoted as $s_{t}$, is a
composite of the initial query $q$, the cumulative reasoning path $s^{p}_{t}$,
and the newly acquired information $s^{n}_{t}$ from the knowledge base. At the
outset, $s^{p}_{t_{0}}$ is an empty set, indicating the start of the reasoning
process. $s_{t}$ that encapsulates all historical information explored up to
time $t$, and we call it the information state [3].

  * •

Action Space $\mathcal{A}$: The agent’s actions, represented by $a_{t}$, are
twofold: $a^{s}_{t}$ involves selecting informative segments from the current
information state $s^{n}_{t}$, and $a^{q}_{t}$ concerns formulating queries to
the knowledge base for further information.

  * •

Transition Function $T$: Defined as $T(s^{\prime}|s,a)$, this function
represents the environment’s dynamics, describing how the agent’s selection of
informative segments is a deterministic process, while querying the knowledge
base is probabilistic, depending on the base’s structure and contents.

  * •

Reward Function $r$: This function, $r(s_{t})$, assigns a quantitative value
to the state $s_{t}$ that reflects the adequacy of information within the
state to address the initial query $q$. It is normalized to the interval
$[0,1]$, where a score of 1 indicates a state with fully sufficient
information.

  * •

Discount Factor $\gamma$: It defines the weight of future rewards in the
agent’s consideration, shaping the strategic depth of the reasoning process by
emphasizing the importance of long-term outcomes. In practice, we use
$\gamma\in(0,1)$ to ensure that the value function $V^{\pi}_{\theta}(s)$ is
bounded, which is important for analysis.

Given a policy $\pi:\mathcal{S}\mapsto\mathcal{A}$ and an environment
parameterized by $\theta$, we define its value function and Q-function as
follows:

$V^{\pi}_{\theta}(s)=\mathbb{E}\bigl{[}\sum_{t=0}^{\infty}\gamma^{t}r_{\theta}(s_{t},a_{t})|s_{0}=s\bigr{]},Q^{\pi}_{\theta}(s,a)=\mathbb{E}\bigl{[}\sum_{t=0}^{\infty}\gamma^{t}r_{\theta}(s_{t},a_{t})|s_{0}=s,a_{0}=a\bigr{]},$
(2)

where the expectation is taken over $a_{t}\sim\pi(s_{t})$ and $s_{t+1}\sim
T_{\theta}(\cdot|s_{t},a_{t})$ for all $t>0$. Here $\theta$ can be considered
as knowledge base contents. Specifically, $\theta$ affects the transition
function $T_{\theta}(\cdot|s_{t},a_{t})$ by determining on the query results
of a given query action, and the reward function $r_{\theta}(s)$ can be
instantiated as an oracle based on knowledge base, such as a set of knowledge
rules or a knowledge-enhanced LLM. The goal of the inner loop, therefore, is
to learn a policy that maximizes $V^{\pi}_{\theta}(s)$ for all
$s\in\mathcal{S}$ so as to find enough information for arbitrary user
questions.

##### Workflow

The reasoning process within this MDP framework, as shown in Algorithm 1,
consists of the following iterative steps:

  1. 1.

Reason: The agent observes memory buffer $\mathcal{D}_{t}$, and generates an
action $a_{t}$. The specific reasonoing process can differ across differnt
reasoning agent choices, which we will discuss in detail in Sec. 4.

  2. 2.

Select and Query: The agent applies the action $a_{t}$ to the current
information state, where $a^{s}_{t}$ filters relevant information and
$a^{q}_{t}$ poses a new query to the knowledge base. The knowledge base,
acting as the environment, responds by updating the state with new
information, resulting in $s_{t+1}$. The forms of query action differ across
different KB forms, being databse query for KGs, retrieval command for
document bases, or prompts for LLMs.

  3. 3.

Evaluate: A reward $r(s_{t},a_{t})$ is assigned based on the informativeness
of the new state in answering the query. If the judge is a set of rules, then
the reward could be the extent of satisfaction. If the judge is a LLM, then
the reward can be a relative ranking score or so, depending on how the judge
LLM is prompted.

  4. 4.

Terminate: The reasoning loop concludes when a termination condition is met,
either because the agent has obtained a state that sufficiently answers the
query (reward threshold met) or when a predefined number of reasoning steps
has been reached.

The reasoning process unfolds as the agent, equipped with a prior belief
$p(\theta)$ about the knowledge environment’s parameters $\theta^{*}$, engages
in a cycle of queries and responses. Initially, the agent faces significant
uncertainty about the true parameter distribution $\theta^{*}$. With each
interaction, the agent refines its understanding by updating the posterior
distribution of $\theta$, which in turn informs more targeted and informed
queries. As the agent accumulates knowledge, its posterior inference becomes
increasingly accurate, more closely mirroring the true parameter distribution
of the knowledge environment, thus enhancing performance. The agent’s learning
progress and policy refinement are quantified by Bayesian regret, which we
expect to be sublinear in $T$, indicating that the agent’s policy is
progressively approaching optimality. The Bayesian regret is defined as:

$\mathcal{R}(T)=\mathbb{E}_{\theta\sim
p(\theta)}\bigl{[}\sum_{t=1}^{T}V^{\pi^{*}}_{\theta}(s_{t})-V^{\pi^{t}}_{\theta}(s_{t})\bigr{]},$
(3)

where the expectation is taken over the prior distribution of $\theta$, and
$\pi^{*}$ is the optimal policy. Here, $p(\theta)$ represents the agent’s
initial model of the environment, shaped by its prior experiences or
pretraining. This prior serves as the baseline from which the agent begins its
learning and adapts through experience.

##### Correspondence with Existing Methodologies

Our framework integrates various established methods into four main
categories, each unified by the concept of a reliable judge—implemented as
either a sophisticated LLM or a set of rules—to ensure consistent assessment.

  1. 1.

Knowledge Graph (KG) Predominant (KG-only): The knowledge base (KB) is
instantiated as a KG, and the reasoning agent operates via a suite of (soft)
logic rules or arithmetic operations. This configuration is akin to
traditional symbolic KG reasoning methods or the embedding-based arithmetic
operations found in neural KG reasoning paradigms.

  2. 2.

LLM Predominant (LLM-only): Both the KB and the reasoning agent are
represented by LLMs. Here, the reasoning agent solicits information from
another LLM, which reflects the operational mechanism of existing
methodologies such as the Chain-of-Thought (CoT) approach [4].

  3. 3.

LLM $\oplus$ KG: Here, a KG serves as the knowledge base while an LLM acts as
the reasoning agent, typically concluding the reasoning in one iteration.

  4. 4.

LLM $\otimes$ KG: A hybrid model where a KG provides the knowledge base and an
LLM acts as an iterative reasoning agent, working continuously until it
satisfies the query’s information requirements.

These classifications highlight our framework’s ability to incorporate and
extend upon a diverse range of reasoning approaches, showcasing its modularity
and adaptability within a cohesive system.

###  3.2 The Outer Feedback Loop

The outer loop functions as an interactive layer where the LLM agent engages
with real-world inputs. The agent processes user queries and produces answers
through reasoned analysis. Feedback from this interaction informs subsequent
updates to the agent’s knowledge, refining its future performance. This
external process can be either a single interaction or a continuous, iterative
dialogue, tailored to the application’s requirements. In a knowledge-based
question-answering (KBQA) scenario, the user presents a question, and the
agent responds. If the interaction is one-time, the user’s feedback may simply
be a rating that concludes the session. In an iterative model, the user’s
feedback includes both a rating and constructive comments, prompting the agent
to refine its subsequent responses.

The iterative nature of this loop can also be modeled as an MDP, analogous to
the inner loop, which allows for a structured analysis of the feedback
mechanism. Here, the combined knowledge base and reasoning agent form the
prior for model parameter distribution, which evolves as it assimilates
feedback from the environment. This process enhances the LLM’s understanding
of the real world, gradually honing its performance as feedback accumulates.
Practically, feedback integration can vary, ranging from direct edits to the
knowledge base, fine-tuning of the LLM, or adjustments to the prompts used for
context. These methods represent design choices that will be explored further
in our discussion. It should be noted that in certain applications, such as
one-off question answering, the LLM’s opportunity for learning from user
feedback is limited, as the interaction with the real-world environment does
not allow for ongoing adjustments.

##  4 Analysis

In this section we analyze the effect of design components in our framework.
We will theoretically prove the query efficiency of the inner reasoning loop
and qualitatively analyze the design choices of other components in this
framework.

Algorithm 2 Reason (LLM-driven Bayesian model-based planning with tree search)

0: Memory buffer $\mathcal{D}_{t}$ at time $t$, model prompt template
$pt_{m}$, critic prompt template $pt_{c}$, actor prompt template $pt_{a}$,
planning lookahead $U$, beam width $W$, beam proposal number $N$

0: Action $a_{t}$

1: Model $\leftarrow$ LLM prompted with $pt_{m}$ and $\mathcal{D}_{t}$

2: Critic $\leftarrow$ LLM prompted with $pt_{c}$ and $\mathcal{D}_{t}$

3: Actor $\leftarrow$ LLM prompted with $pt_{a}$ and $\mathcal{D}_{t}$

4: for $i=0$ to $U-1$ do

5: Actor propose $N$ possible actions

6: Model acts as a fake knowledge base that executes these actions and
generate next states

7: Critic evaluate these actions and select top-$W$ ones

8: Update prompts for Model, Actor, Critic with the $W$ new trajectories

9: end for

10: return The first action on the trajectory with the highest value among $W$
trajectories

Algorithm 3 The adapted inner reasoning loop

0: User question $q$, max reasoning step $T$, reward threshold $R$

0: Response $a$

1: $t\leftarrow 0,k\leftarrow
0,\mathcal{D}_{t}\leftarrow{q},terminal\leftarrow False$

2: $s_{k}\leftarrow\\{q,\emptyset,\emptyset\\}$

3: while $terminal\neq True$ do

4: $B_{k}\leftarrow\mathcal{D}_{t}$ {periodic update memory buffer for LLM}

5: repeat

6: $a^{s}_{t},a^{q}_{t}\leftarrow\text{Reason}(\mathcal{B}_{t})$

7:
$s^{p}_{t+1},s^{n}_{t+1}\leftarrow\text{Select\\_and\\_query}(s_{t},a^{s}_{t})$

8: $s_{t+1}\leftarrow(q,s^{p}_{t+1},s^{n}_{t+1})$

9: $r_{t}\leftarrow\text{Judge}(s_{t+1})$

10:
$\mathcal{D}_{t+1}\leftarrow\mathcal{D}_{t}\cup\\{(s_{t},a_{t},r_{t},s_{t+1})\\}$

11: $t\leftarrow t+1$

12: if $r_{t}\geq R\textbf{or\ }t\geq T$ then

13: $terminal\leftarrow True$

14: end if

15: until Enough-NewInfo

16: $k=k+1$

17: end while

18: return $\text{summarize}(\mathcal{D}_{t})$

###  4.1 Provable query efficiency

Our framework predicates its convergence towards accurate responses on high-
quality knowledge bases, iteratively reasoned. This iterative reasoning is
exemplified by the adapted inner reasoning loop in Algorithm 3, which
underpins our framework’s query efficiency. Our analysis and proof follows the
RAFA framework [3], and we will briefly recite it here.

Our analysis focus on the inner loop with LLM $\otimes$ KG paradigm, where the
Reason (Sec. 3.1) step employs Bayesian model-based planning, with example
provided in Algorithm 2. Updates to the LLM’s context within this
configuration are periodic and significant, transitioning the agent’s
understanding from a prior environmental parameters distribution $p(\theta)$
to a refined posterior $p_{t}(\theta|\mathcal{D}_{t})$ with each iteration.
This process, hinged on following two critical assumptions, enhances the
model-based planning and is assessed through Bayesian regret.

######  Assumption 4.1.

The distribution of the pretraining data for the reasoner LLM mirrors the
knowledge distribution that underlies the knowledge base.

######  Assumption 4.2.

The inner loop judge delivers unerring reward signals about information
sufficiency.

Assumption 4.1 ensures no discrepancy in the inner loop between the prior
distribution provided by LLM and the knowledge distribution. Assumption 4.2
ensures the alignment between knowledge base and judge. With these assumptions
and an optimal planning algorithm in place, Bayesian regret is governed by the
precision of the posterior distribution $p_{t}(\theta|\mathcal{D}_{t})$.
Although Bayesian regret inherently accumulates over time, it does so at a
sublinear rate, indicating that the average regret per iteration approaches
zero, reflecting the policy’s gradual improvement towards optimality. This
relationship between information assimilation and model precision underscores
the agent’s consistent advancement towards the ideal policy. We will delve
into planning optimality and information gains, concluding with the
implications on the sublinear nature of Bayesian regret.

####  4.1.1 Planning Optimality

We will assume that LLM reasoning is performing poesterior inference of model
parameter, and then prove the optimality of our model-based planning algorithm
(example in Algorithm 2). Combining these two provides guarantee for our
planning algorithm, and offloads policy suboptimality to information gap as we
will analyze in Sec. 4.1.2.

######  Assumption 4.3.

LLM-estimated knowledge model parameter a posteriori $p_{t}(\theta)$
essentially follows $\mathbb{P}(\cdot|\mathcal{D}_{t})$

Assumption 4.3 says that LLM performs implicit Bayesian inference on knowledge
model parameters, which echos Sec. 2.2 and is verified in [5].

######  Definition 4.4.

($\epsilon$-Optimality) Under an environment parametrized by $\theta$, a
policy $\pi$ satisfies $\epsilon$-optimality if the following condition holds
with high probability

$\max_{s}V^{\text{PL}^{*}(\theta)}_{\theta}(s)-V^{\pi}_{\theta}(s)\leq\epsilon,$
(4)

where $\text{PL}^{*}(\theta)$ denotes the optimal planner under environment
$\theta$. For planning algorithms, $\epsilon$ is usually related to the
lookhead horizon $U$, since as $U$ increases, the performance gap decreases.
This essentially tells us that we can increase lookahead length to enhance
planning optimality, which is essentially about trading inference cost/latency
with accuracy. Planning algorithm such as value iteration, tree search
(Algorithm 2), and MCTS can usually assure $\epsilon$-optimality with proper
lookheads.

Given that the planning algorithm is based on the posterior estimation of
model parameter $\theta_{t}$, which depends on effective information up to
time $t$, we say that the reasoning LLM induces a corresponding policy
$\pi^{t}$ at time step $t$ that evolves as information accumulates.

####  4.1.2 Information Gain

Consider the entropy of the posterior distribution $p_{t}(\theta)$ at time t:

$H_{t}=-\int p_{t}(\theta)\log p_{t}(\theta)d\theta$ (5)

$H_{t}$ is expected to decrease as $t$ increases, meaning that the uncertainty
in environment estimation reduces as more observations is attained. Meanwhile,
the uncertainty in posterior distribution will be reflected on the estimation
error of value function. To reflect this process, we introduce the idea of
information coefficient $\Gamma_{t^{\dagger}}(\delta)$ [1], which is the
minimum value that makes the following inequality holds for all
$t\in\\{t^{\dagger}+1,...,T-1\\}$ with probability at least $1-\delta$, if
$H_{t^{\dagger}}-H_{t}\leq\log 2$:

$|(r_{\theta^{*}}-r_{\theta_{t}})(s_{t},a_{t})+((P_{\theta^{*}}-P_{\theta_{t}})V)(s_{t},a_{t})|\leq\Gamma_{t^{\dagger}}(\delta)\sqrt{I(\theta;\xi_{t+1}|D_{t})},$
(6)

where $I(\theta;\xi_{t+1}|D_{t})=H_{t+1}-H_{t}$ is the information gain over
after observing the $t+1$-th step $(s_{t},a_{t},r_{t},s_{t+1})$ Equation 6
essentially depicts that as the new information gets smaller with more
explorations, meaning that the exploration has already gained a lot of
information and getting new information is hard, the bound of the estimation
error for value function gets smaller. As long as
$\Gamma_{t^{\dagger}}(\delta)$ is finite, the estimation error can be bounded.

To ensure the stability of policy updates, in Algorithm 3 the context buffer
for the reasoning LLM is periodically updated only when enough new information
compared with the previous checkpoint is obtained. In the following analysis,
we will adopt the same Enough-NewInfo condition as in [3], which is
$H_{k}-H_{t}\geq log2$, indicating there is at least 1-bit of new information
obtained.

####  4.1.3 Sublinearity in Bayesian Regret

With the above discussion, we invoke conclusions in RAFA, showing the
sublinearity of $\mathcal{R}(T)$. Our proof follows Appdx.C in [3]. Here we
will briefly recite it with the proof sketch. For detailed proof, readers may
refer to [3].

######  Theorem 4.5.

Suppose the reasoning algorithm is $\epsilon$-optimal and
$\max_{s}V_{\theta}(s)\leq L$, under Assumption 4.1. With
$\epsilon=O(\frac{1}{\sqrt{T}})$ and $\delta=O(\frac{1}{\sqrt{T}})$, the
Bayesian regret of the reasoning agent satisfies $\mathcal{R}(T)=O(\sqrt{T})$

###### Proof.

According to Eq. C.1 in [3], the Bayesian regret in Eq. 3 can be decomposed
as:

$\displaystyle\mathcal{R}(T)$ $\displaystyle=\mathbb{E}_{\theta\sim
p(\theta)}[\sum_{t=1}^{T}V^{\pi^{*}}_{\theta}(s_{t})-V^{\pi^{t}}_{\theta}(s_{t})]$
$\displaystyle=\mathbb{E}_{\theta\sim
p(\theta)}[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}V^{\text{PL}^{*}(\theta)}_{\theta}(s_{t})-V^{\pi^{t}}_{\theta}(s_{t})]$
$\displaystyle=\underbrace{\mathbb{E}_{\theta\sim
p(\theta)}[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}V^{\text{PL}^{*}(\theta^{k})}_{\theta^{k}}(s_{t})-V^{\pi^{k}}_{\theta^{k}}(s_{t})]}_{\text{term
(A): Policy suboptimality}}+\underbrace{\mathbb{E}_{\theta\sim
p(\theta)}[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}V^{\pi^{t}}_{\theta^{k}}(s_{t})-V^{\pi^{t}}_{\theta}(s_{t})]}_{\text{term(B):
Model estimation gap}}$ (7)

Term(A) in Eq. 4.1.3 recalls the definition of $\epsilon$-optimality (eq. 4),
leading to:

$\text{term(A)}\leq\epsilon T.$ (8)

Since LLM context is updated periodically, in the following we denote
$\theta_{k}=\theta_{t}$ and $\pi^{k}=\pi^{t}$ for all
$t\in\\{t_{k},t_{k}+1,...t_{k+1}-1\\}$. For term(B) in Eq. 4.1.3, according to
lemma C.1 in [3], it can be decomposed into the information gain and value
inconsistency, expressed as Eq. C.6 in [3]:

$\displaystyle\frac{1-\gamma}{\gamma}\cdot\mathbb{E}_{\theta\sim
p(\theta)}\Bigl{[}\sum_{k=0}^{K-1}\mathbb{E}_{\pi^{k}}\Bigl{[}\sum_{t=t_{k}}^{t_{k+1}-1}V_{\theta^{k}}^{\pi^{k}}(s_{t})-V_{\theta}^{\pi^{k}}(s_{t})\Bigr{]}\Bigr{]}$
$\displaystyle\quad=\underbrace{\mathbb{E}_{\theta\sim
p(\theta)}\Bigl{[}\sum_{k=0}^{K-1}\mathbb{E}_{\pi^{k}}\Bigl{[}\sum_{t=t_{k}}^{t_{k+1}-1}({B}_{\theta^{k}}V^{\pi^{k}}_{\theta^{k}})(s_{t},a_{t})-({B}_{\theta}V^{\pi^{k}}_{\theta^{k}})(s_{t},a_{t})\Bigr{]}\Bigr{]}}_{\text{term
(C): information gain}}$
$\displaystyle\quad\qquad+\underbrace{\mathbb{E}_{\theta\sim
p(\theta)}\Bigl{[}\sum_{k=0}^{K-1}\mathbb{E}_{\pi^{k}}\Bigl{[}\bigl{(}V_{\theta^{k}}^{\pi^{k}}(s_{t_{k+1}})-V^{\pi^{k}}_{\theta}(s_{t_{k+1}})\bigr{)}-\bigl{(}V_{\theta^{k}}^{\pi^{k}}(s_{t_{k}})-V^{\pi^{k}}_{\theta}(s_{t_{k}})\bigr{)}\Bigr{]}\Bigr{]}}_{\text{term
(D): value inconsistency}},$ (9)

where $B_{\theta}$ is the Bellman operator satisfying

$B_{\theta}V^{\pi}_{\theta}(s,a)=r_{\theta}(s,a)+\gamma
P_{\theta}V^{\pi}_{\theta}(s,a).$ (10)

For term(C) in Eq. 4.1.3, recall Eq. 6 and Eq. C.10 in [3], we have:

$\text{term(C)}\leq\sup_{t^{\dagger}<T}\Gamma_{t^{\dagger}}(\delta)\cdot\mathbb{E}\bigl{[}\sqrt{T(H_{0}-H_{T})}\bigr{]}+L\delta
T$ (11)

For term(D) in Eq. 4.1.3, according to Eq. C.11 in [3], we have

$\text{term (D)}\leq{(4L/{\log 2})\cdot\mathbb{E}[H_{0}-H_{T}]}+4L.$ (12)

So Bayesian regret is bounded by (Theorem 4.4 in [3]):

$\mathcal{R}(T)=O(\frac{\gamma\cdot(\sup_{t^{\dagger}<T}\Gamma_{t^{\dagger}}(\delta)\mathbb{E}\bigl{[}\sqrt{(H_{0}-H_{T})}\bigr{]}\sqrt{T}+L\delta
T+L\mathbb{E}\bigl{[}\sqrt{(H_{0}-H_{T})}\bigr{]})}{1-\gamma}+\epsilon T)$
(13)

According to Eq. 13, if we have $\epsilon=O(\frac{1}{\sqrt{T}})$ and
$\delta=O(\frac{1}{\sqrt{T}})$, then the whole term is essentially
$O(\sqrt{T}).$ ∎

As the number of iterations increases, the policy is expected to approach
optimality. This is due to the posterior distribution increasingly
concentrating around the true environmental parameter $\theta$ with each new
observation, which in turn refines the model’s estimation. With a more
accurate model and the assumption of planning optimality, we predict the
policy will eventually align with the optimal one. This convergence is further
assured by Assumption 4.2, which posits that the judge module provides perfect
feedback, thus enabling the agent to arrive at the correct answers. The
$\mathbb{E}[\sqrt{H_{0}-H_{T}}]$ term on the right-hand side of Equation 13
indicates that when the information gain is small after exploration,
suggesting that the underlying knowledge environment is simple, the Bayesian
regret bound becomes tighter. Besides, it’s important to note that this
analysis does not account for discrepancies between the knowledge environment
and the actual environment, an aspect relevant to the outer loop and
designated for future investigation.

When considering other paradigms as outlined in Section 3.1, one-shot methods
are limited by a lack of iterative feedback and hence retain a constant
uncertainty in model parameter estimation, precluding convergence. Similarly,
iterative methods that do not engage in Bayesian inference—those unable to
refine estimations using data from the knowledge base—are also devoid of
performance guarantees due to static uncertainty. Therefore, it is the
iterative reasoning algorithms that integrate progressively expanding
information which are endowed with provable efficiency. The specific design
choices within this paradigm will be addressed in subsequent discussions.

###  4.2 Observation Quality

In the context of a knowledge environment considered as noisy, the data’s
quality is crucial for the reasoning agent’s Bayesian inference and the
resulting precision in model parameters. Assessing the influence of the
knowledge base type—LLM versus KG—on reasoning, we note from an information-
theoretic view that KGs, with their structured representation of knowledge,
typically produce less uncertain responses than LLMs. The latter introduces
greater uncertainty through its training on diverse datasets and in-context
generation of responses. This disparity in response entropy is attributed to
the inherent design differences between the deterministic retrieval from KGs
and the probabilistic output from LLMs. When observational data is sparse, it
usually exacerbates the uncertainty in the estimation of model parameters,
leading to policies that may be suboptimal during model-based planning.

###  4.3 LLM as Reasoning Agent

Using an LLM for Bayesian model-based planning is key to achieving
convergence, as its simultaneous functioning as a model, actor, and critic is
essential for the planning’s effectiveness. In contrast, planning methods that
omit Bayesian inference will struggle with persistent uncertainty, obstructing
the path to convergence. Additionally, employing a basic language model
instead of an LLM as the prior requires a greater number of observations for
the model to refine its parameter estimations and approach accuracy.

###  4.4 Real-world Feedback Incorporation

User feedback is a vital form of real-world data that enhances the knowledge
environment, guiding it to refine its reasoning capabilities. Knowledge Graphs
(KGs), with their structured format, adeptly utilize this detailed feedback.
They can directly incorporate corrections or new insights into their
interconnected nodes, aligning closely with user-provided data. On the other
hand, LLMs face more complexity when integrating feedback. As LLMs are trained
on extensive datasets, incorporating new user feedback involves a retraining
or fine-tuning process that might not preserve the feedback’s full detail due
to the data processing inequality. This principle suggests that with each
transformation step, such as integrating feedback, there’s a risk of losing
some useful information. For LLMs, this means the nuanced feedback may get
diluted as it’s merged with pre-existing data patterns, potentially
introducing noise and lessening the impact of the updates. While both KGs and
LLMs can improve from user interactions, KGs are typically better at
preserving the accuracy of user feedback. LLMs may inadvertently alter
feedback due to their complex update mechanisms. Consequently, KGs often
provide a more dependable approach for incorporating new user insights into
the knowledge environment.

## References

  * [1] Y. Abbasi-Yadkori and C. Szepesvári.  Bayesian optimal control of smoothly parameterized systems.  In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI’15, pages 2–11, Arlington, Virginia, USA, 2015. AUAI Press.
  * [2] Q. Dong, L. Li, D. Dai, C. Zheng, Z. Wu, B. Chang, X. Sun, J. Xu, L. Li, and Z. Sui.  A Survey on In-context Learning, June 2023.  arXiv:2301.00234 [cs].
  * [3] Z. Liu, H. Hu, S. Zhang, H. Guo, S. Ke, B. Liu, and Z. Wang.  Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiency, Oct. 2023.  arXiv:2309.17382 [cs].
  * [4] J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. Chi, Q. V. Le, and D. Zhou.  Chain-of-Thought Prompting Elicits Reasoning in Large Language Models.  Advances in Neural Information Processing Systems, 35:24824–24837, Dec. 2022.
  * [5] S. M. Xie, A. Raghunathan, P. Liang, and T. Ma.  An Explanation of In-context Learning as Implicit Bayesian Inference.  Oct. 2021.
  * [6] Y. Zhang, Y. Li, L. Cui, D. Cai, L. Liu, T. Fu, X. Huang, E. Zhao, Y. Zhang, Y. Chen, L. Wang, A. T. Luu, W. Bi, F. Shi, and S. Shi.  Siren’s Song in the AI Ocean: A Survey on Hallucination in Large Language Models, Sept. 2023.  arXiv:2309.01219 [cs].
  * [7] Y. Zhang, F. Zhang, Z. Yang, and Z. Wang.  What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization, Oct. 2023.  arXiv:2305.19420 [cs, stat].