so today I'm going to talk about
retrieval and retrieval augmented
generation so if we look at our standard
prompting flow normally what we do is we
combine together a prompt template with
an input so if we say please answer this
question I think Vin Diesel has been a
voice actor for several pictors in TV
series do you know what their names
are we could get a response from a
language model but there are several
problems with
this the first is accuracy issues
the models generally have a knowledge
cut off so the parameters are usually
only updated to a particular time so for
example if a new Vin Diesel TV series
comes out then the model that was
trained up to a certain time Point won't
be able to know anything about
it there's also issues of private data
so data stored in private text or data
repositories is not suitable for
training for a number of reasons number
one it's not available to to particular
language model training providers such
as you know open AI or Google or anybody
else like this the second thing is
Access Control issues so even if you're
within an organization that has lots of
private data and you can train a
language model on that certain people in
the organization may have access to
certain varieties of data and other
people may not so it's not just solely
an issue of third party providers it's
an issue of organization level Access
Control in
general in addition there are learning
failures so even for data that the model
was trained on it might not be
sufficient to get the right answer and
this is particularly the case for very
very large uh training data sets and
models that are you know modestly sized
because the models very often won't be
able to learn from a single look at a
particular fact or or whatever else like
this especially if iter early in
training another thing is even if the
answer is correct it might not be
verifiable so you might want to be very
sure that the model is not making any
accuracy
problems and so in order to do that very
often a human will want to go back to
the source of the
data so to solve this there's a method
called retrieval augmented generation
which will also be the topic of our
second assignment
here and the way it works is you
retrieve relevant passages
efficiently ones that kind of entail the
answer to a question and then read the
passages to answer the
query so we have documents like this we
have a query based on the query we form
retrieval we get a whole bunch of uh
passages we do reading and then we get
the
answer so this is in fact implemented in
many or even most uh language modeling
providers including open AI so to give
an example I asked the question that I
just said about Vin Diesel's voice
acting and TV
series and Chad GPT gave me an answer
and you can see that J gpt's answer
includes several places with quotes um
they the little blue quotes
there and if you click on the quote it
tells you where the information Source
came from and so this one says behind
the voice actors been
Diesel and behind the voice actors TV
shows Big Mouth V
diesel now if we look
closer into this answer we'll see that
it's not perfect even though it is uh
performing retrieval augmented
Generations so for example I only asked
about TV series but it's giving me lots
of things about movies where it says
Groot in Guardians of the Galaxy volume
3 2023
movie and in fact uh Vin Diesel was not
even voicing a character named gut here
so that's definitely an accuracy
mistake and separately there's a place
where it says additionally though the
website for big mouthless Vin Diesel it
appears to be a misunderstanding or err
as Nick croll is credited as the voice
of Vin Diesel in that show so there
actually Nick croll was acting as V
diesel but that's um kind of a
misunderstanding of the reader model but
anyway you can get the general idea here
you can also see that it's not perfect
even for very strong models like GPD
4 so now I'd like to go into the actual
methodology that we use for this uh we
have retrieval
methods and for the retrieval methods we
have uh quite a few different options
I'm going to go through each one of them
at a time so sparse retrieval document
level dense retrieval token level DSE
retrieval cross- encoder reranking and
blackbox retrieval so blackbox retrieval
I'm not really going to go into it a
whole lot basically this is just asking
a blackbox search engine to retrieve uh
you know the relevant context and
getting the top several results
nonetheless this is a pretty you know
reasonable method to do it if you want
to do search over you know lots of data
that exists on the internet already and
that in is what chat jpt does it looks
up on Bing by generating a query to
Bing so anyway let's go into the actual
methods that you develop and control
yourself so the first one is sparse
retrieval and the way this works is you
express the query and document as a
sparse word frequency Vector usually
normalized by length and so if I ask uh
query what is NLP we get a vector where
each row the vector corresponds to a
different
token and we asked what is
NLP and so uh the places for what NLP
and is will all have a non-zero value
and everything else will have a zero
value and we also normalize by the
length of vectors so we get something
like
333333 then we have a whole bunch of
documents so the first document says
what is life can is life someone really
likes
candy we also have another one that says
NLP as an acronym for natural language
processing so this is a pretty good uh
you
know answer to our
question then we also have I like to do
good research on NLP which is you know a
nice sentiment but not a very good
answer to our question I
guess so if we look at the vectors here
we have uh what and candy and is have uh
a fairly high
score and we have here NLP and is have a
high score and NLP has a a nonzero
score So based on this um we find the
document similarity with the highest
inner product or cosine similarity in
the document
collection and so if we take the inner
product between these vectors we
actually see that the first one got the
highest score because of its
relatively High values for the words
what and
is
so as you can see common words like what
and is can get a high score kind of
regardless of whether a document is very
relevant and so one way we can fix this
is through something called term
waiting and the way that term waiting
works is in addition to having this
Vector that
calculates
the frequency within a particular
document we also have an upweighting
term that gives higher weight to low
frequency words because low frequency
words like NLP tend to be more
informative about whether the document
is relevant than high frequency words
like what it is because these high
frequency words like what and is Could
Happen kind of regardless of whether
the you know document is relevant the
particular terms the person is asking
about so one well used and easy to
understand version of this is uh tfidf
or term frequency indument
frequency so the way we Define term
frequency is exactly what I talked about
before so it's basically the frequency
of the term uh T in the document d
normalized by the total term frequency
within the document so that that's what
I already showed in the previous
slide and then indument frequency is a
little bit more involved but basically
the way this works is we have log of the
total number of documents in the
collection divided
by the total number of uh times this
term appeared in any particular
document and so if a term appears many
times in any particular document it will
have a low IDF score uh one that's close
to zero but if it rarely appears it will
have a high IDF score so basically this
is upweighting our frequent terms and
then for
tfidf uh we basically multiply these two
terms together and we upweight the low
frequency
words there's another version of this
called bm25 that is uh widely used used
um this is more involved so I'm not
going to go into all of the details but
basically if you remember back to the
lecture on count-based language models
there were a bunch of smoothing
techniques for these count-based
language models and this uses uh kind of
a m multiplicative additive smoothing
term to upway things instead of using
the term
frequency and uh the actual formula is
here K and B are kind of
hyperparameters and um average DL is
average document length the details of
this are not really important but
basically what you should know is that
this is doing some smoothing on the term
frequencies and you can look in more
detail if you're
interested so now that we have this sort
of term
based uh sparse Vector we would like to
use this to look up relevant documents
in a collection very quickly because you
know we might have a collection that's
extremely large like as large as the
entire internet like what Google is
doing when it searches and so in order
to solve this we need a data structure
that allows for efficient sparse lookup
of
vectors and so we have all of these
sparse vectors like this
and we uh basically turn this into an
index where we have something like a you
know python style dictionary or map that
has it's the key each uh word we would
look like to look up and is the vector
the corresponding um index of that
document so for example what in our case
here only appears in document one so it
would point to document one candy uh
also appears in document one NLP appears
in two and three and so you can create
this index IND like this and this is
called an inverted
Index this is an important application
of course so there's lots of software
the most kind of pical software for this
is Apache Lucine so if you want to build
a big index uh to look up vectors using
this sparse index like this you can uh
take a look at
Lucy so the next thing I'd like to talk
about is dense retrieval and the way
dense retrieval works is you encode the
document in query into a dense factor
and find the nearest
neighbor in order to do this encoding
you can use a number of things you can
use out of the box embeddings or you can
use learned embeddings specifically
created for the purpose of
retrieving and so what we do is we take
all of these uh documents here we
convert them into embeddings using
whatever embedding method that we want
to use we then have a query and we take
that query and we match it and find the
nearest neighbor
here so if you're just using out of the
box embeddings you don't need to um you
know do anything special for retrieval
you can just take your favorite
embeddings like the sentence BT
embeddings or the open AI uh Adda
embeddings or something like this but
actually the type of embeddings you need
for retrieval are kind of
very special and because of that it's
important
to if you're very serious about doing a
good job of retal it's important to use
embeddings that were specifically
tailored for
retrieval and the reason why it is
important to do this is severalfold but
the most intuitive way to think about it
is if we think about uh the things that
tfidf does tfidf is giving a very high
weight to
contentful words and rare words and
we're not guaranteed that any random
embedding that we get is going to do
that so for example if we just take the
average word embeddings of every word in
a sequence it's going to give the same
weight to all of the words um in the
output and in fact common words tend to
have slightly higher Norms than
infrequent words and so that would
actually upli common wordss which is
kind of exactly the opposite thing we
want so how do we learn retrieval
oriented
embeddings the normal way we do this is
we select positive and negative
documents and then train using a
contrastive loss and so an example of
this is we have a query and then we have
negative documents for that query and we
have positive documents for that query
and uh we form formulate a hinge loss or
maybe some sort of probabilistic loss
similar to the Hench loss and uh do fine
tuning of the
embeddings so if
you have gold standard positive
documents then this is relatively easy
to train uh because you just need the
positive documents and then you can get
Negative documents in a number of ways
one common way of getting negative
documents is you just form a batch of
data and given that batch of data you
take all of the other documents in the
batch um all of the documents in the
batch that are positive for some other
query and you use those as negative
documents so you sample 32 query
document pairs you use the aligned ones
as positive documents and then use the
31 other ones as negative documents and
this is both effective and efficient
because you can kind of learned from the
query document pairs all at the same
time in an efficient
implementation however this is not
enough in many cases because that will
end up having lots of very kind of
obviously wrong documents because you
know
they're documents that are relevant for
a completely different query and it's
kind of easy to distinguish uh between
those you can just at superficial word
overlap so another common thing to do
when you're training these models is to
get hard
negatives so hard negatives are
basically negative examples that look
plausible but are actually wrong and
so here uh this famous method called DPR
is it basically learns the uh encoders
based on both inbatch negatives like I
mentioned before and hard negatives that
were created by looking up documents
with
bm25 and so the ones that were looked up
by bm25 you know kind of look very
similar superficially but they might
have you know subtle errors in them for
why they're
inappropriate there's also methods to
learn these
retrievers based on kind of not
supervised data so one major bottleneck
if you're taking the positive documents
from Human annotations of whether
something is correct or not or human
clickthrough logs or other things like
this is that you need that data in order
to start training a bottle so uh
contriver is another method that uses
two random spans within a document is a
positive pair and random spans from
across documents is negative Pairs and
so this can be used for you know very
very large scale initial pre-training of
the
models and then after you've done that
large scale initial pre-training you can
then go in and fine-tune it on you know
actually annotate the data to improve it
further Okay so we've talked about
training uh these dense product uh
models these uh models that look at
dense embedding overlap for nearest
neighbors but the problem is in order to
calculate this you would need to
calculate it over a very very large
document base and just taking a product
between the query and all of the other
documents in the document base is
extremely
costly and so in order to fix this there
are methods for approximate nearest
neighbor
search and these are methods that allow
you to retrieve embeddings that have the
maximum inner product between them in
sublinear time and because you're doing
the maximum inner product this is also
often called maximum inner product
search or
myips so I'm going to introduce on a
very high level two common methods to do
this the first one is locality sensitive
hashen um or this can also be called
kind of inverted index as well and what
you do is you make partitions in
continuous space and then you use it
like an inverted index
so let's say we have a whole bunch of
embeddings uh I demonstrated two
dimensional embeddings here but in
reality this would be you know as large
as your word
embedding your query and document
embedding space so this would be you
know 512 or 1024 or something like that
and what you do is you define a whole
bunch of planes that separate these
points into two spaces so if this is our
first plane all the points above the
plane will get a one for this partition
and all the points below the plane will
get a zero for this partition and we do
it similarly we we create a whole bunch
of them and then based on this we can
now assign sparse vectors depending on
each of these planes so we have uh for
example the top one uh one0 0 because
it's on the right side of the blue plane
and the um wrong side of the red and the
green planes and then for the top right
we have one1 because it's on the right
side of the blueing the green planes and
the wrong side of the red plane and So
based on this now we have a sparse
vector and we already know what to do
with a sparse Vector right we look it up
in an inverted index just like we did
for a sparse um you know sparse lookup
table so that's one
method another method uses a graph-based
search and the basic idea behind this is
that we create hubs uh and these hubs
are kind
of a small number of points that are
close to other points in the space and
so we create some hubs and then we
search from there so if we have a
similar
looking uh set of points in the space we
find these hubs which are something like
cluster centroids and then based on the
cluster centroids we then rule down or
we greatly reduce the number of
points that we need to be looking at and
then we search through only those points
in a more kind of extensive Manner and
you can even turn this into a tree where
you have hubs and then you have uh kind
of mini hubs and then you have all the
points so this allows you to do a kind
of tree based or graph based
search so obviously unless you're really
excited about these algorithms this is
something that you probably don't want
to be implementing yourself um and the
good news is there's lots of very good
libraries that help you do this in fact
there are so many libraries it's hard to
manage them but some libraries that
people very commonly use I I think face
uh FIS
SS is a widely used one created by uh
fair and meta and chroma DB is a
separate one uh that is kind of an AI
native uh embedding search database so
both those are good
options even with intelligent training
of dense embeddings however there still
are
problems and the biggest
problem that you face when you're
looking at something like uh cross
encoders um that sorry when you're
looking at dense embeddings is that in
order to form a good dense embedding you
need to kind of know in advance what
you're looking for right because you're
taking a long document you're condensing
it down into a single embedding and or a
long passage and you're condensing it
down to a single embedding and so if
that during that condensation process
actually there's other information that
is relevant to a query but you have to
throw out because of the limited
embedding capacity this causes you to
you know essentially fail at um doing
retrieval
appropriately so there's a couple
methods that can be used to fix this so
the first method is in contrast to the
buy encoder which is what I've been
talking out about at this point where
you kind of do full encoding of queries
full encoding of documents and then do
inner product search for a score uh you
can use a cross encoder and the way the
cross- encoder works is you append the
query and document and then you run them
through a model like a Transformer model
and you calculate the output
score so the problem with this um so
this this is great uh because it gives
you maximum flexibility um Transformer
models are powerful you can uh assess
relevance very well the problem with
this is this precludes approximate
nearest neighbor lookup because now
you're running through you know many
many nonlinearities
here so this is can only be used for
reranking documents um or if even if
you're doing retrieval doing retrieval
over a very very small number of
documents but if you really want maximal
accuracy I definitely would recommend uh
doing something like this because it can
allow you to do kind of a second pass
filtering over the most relevant looking
documents to identify the ones you
really want to add to your
context so then there are also
approaches that are kind kind of in the
middle of these two uh the most famous
one is
Kar and the I called this token level
dense retrieval it's also called uh late
interaction in the coold bear paper but
the way it works is you use
contextualized representations of all
query and document tokens to compute a
retrieval
score and so you do offline indexing of
every token in the document and then
based on this offline X indexing of
every token in the document you then
have a query encoder and you do matching
between each token in the query and the
highest scoring tokens in each
document
and the reason why this is good is it
still allows you to encode all of the
tokens in the
document and but each of these
similarity searches is still just
a kind of maximum product search and
because of this this allows you to do
each of these searches efficiently and
doesn't preclude you from running it
over an entire
database the downside to this method uh
may already be obvious but in the
traditional bu encoder we have a single
Vector for each document but here we
have one vector for um each token in the
document so BAS basically your vector
database gets n times larger where n is
the number of tokens in the document and
there are certain methods to make this
better like you can compress each
document to a smaller number of n uh but
still this is definitely going to be
more costly than looking up each uh
token so this is definitely something to
consider if you want to get you know
very good scores and Co bear is a good
implementation of that to start with if
you're interested in trying it out
so this is a final thing this is uh
something that is a little bit uh
different than all the other things I I
talked about before but I've used it
myself and it actually can be pretty
effective um it was also made at CMU so
by Lal so I would like to promote our
CMU work of course but um the HP idea
between behind a hypothetical document
embedding
is that it's actually somewhat difficult
to match a query and a document right
because a query is a very short possibly
ungrammatical output that's asking a
question and then a document is a very
long output that's written in a
different proos style and you you know
it might have lots of irrelevant
information or or boiler plate or fluff
or something like
that so the idea behind a hypothetical
document embedding is that it's e easier
to match a document in a document than
it is to match a query in a
document but the input to our model is a
query right so what do we
do and so essentially what we do is we
then take a large language model we feed
it in a query in a prompt and say
generate a document that looks like it
should be the answer to this
query and so so then the llm goes in and
it generates a document and hopefully
this document looks more similar to the
documents you want to retrieve than the
um than the original query does and I've
actually found this to be relatively
effective at improving accuracy
on kind of difficult uh tasks especially
ones that are out of domain from the
trend models that I'm
using so I've gone through a whole bunch
of methods and I would like to finish up
this section by giving some insight
about which one you should be
using so my impression right now is
that a good basine to start out with is
something like bm25 it's very easy to
start out and compared to embedding
based models it tends to be relatively
robust to new domains so if you have a
new domain you're more less guaranteed
that bm25 will give you some performance
whereas embeddings may be really good
but they may be really bad uh depending
on how out of domain that is compared to
your underlying embedding
model
so however if you want to get the
highest accuracy definitely tuned models
are going to be better and if you're not
worried about computation efficiency
using something like P bear um with kind
of the token level retrieval will
definitely give you uh good accuracy
here however there's better support for
bu encoder style models um in kind of
standard Vector databases like feice and
uh chroma and other things like that so
if you want a kind of easier method to
get started very quickly then using a bu
encoder is probably the best way to
go okay so now moving on to actual
retrieval augmented generation models we
have uh retriever reader
models and the way these work is you
basically the simplest way they can work
is you basically just chain retrieval
and reading together so you use an outof
thebox Retriever and an outof thebox
reader model and you have your query uh
you could for example look something up
on Google get a whole bunch of passages
and then feed them into a GP key model
and get an
answer this overall is quite effective
um you it's easy to implement and it
will give you decent results so
definitely it's something to be worth
thinking about uh for assignment two in
the um in the class you're required to
only use uh kind of public models or
open source implementations so you could
still replace that with Apachi Lucine
and then um you know any standard llm
and that could be you know llama llama
Chad or M mistol or mixol or something
like that so uh you could definitely
feel feel free to do something like
that um of course the passages are
concatenated to the context and so
because the passages are concatenated to
context the contacts can get relatively
long and expensive and other things like
that but it's just something you have to
deal with when you're using
R there are methods also for Retriever
and Generator endtoend
training so this is the paper actually
where the name rag came from and I'll
use that as an example here uh but
basically um there are several methods
that propos to train the Retriever and
reader to improve
accuracy and specifically the rag p by
Lewis at all the way it trained the um
reader was to maximize generation
likelihood given a single retrieved
document and for the retriever it
maximized overall likelihood by
optimizing the mixture weight over
documents so here's kind of a a
schematic uh which is you have your
query encoder um you run the Retriever
with uh maximum inner product search it
gives you several documents and each
document has a score and then based on
the documents and the scores you
generate uh with each document in the
context and
then sum together the probabilities
multiplied by the weights and I have the
actual equations here because I think
it'll be a little bit easier to
understand after looking at the
equations so generation is a mixture
model and you pick a document and
generate from the document this
p z given X is the probability of
picking that document given the query X
and then this P Theta x z and all of the
previous tokens is basically the uh
probability of the next token given that
you have this particular document so you
can see that this is basically linearly
interpr ating between the multiple
documents and if we look this can be
considered the Retriever and the
generator the Retriever and the
reader one really important thing here
uh that enables endtoend training is
they have this probability of the
retriever be based on
embeddings and so here we have the
document embedding and the query
embedding and the probability is
proportional to the inner product of
these exponentiated so you're basically
taking a soft Max over uh the inner
product between the
two
and this adjusts the retriever to give
higher similarities to helpful
documents
and
so because the prob probability of the
retriever model here is included in the
endtoend probability you don't actually
need any annotations
about which documents are useful you can
just train all of this end to end and
let backrop do its thing to update the
uh the retriever as
well one important issue when training
models like this is that the search
index will become stale so what do I
mean by this if we go back to our
previous uh thing about dense
models creating this blue search index
on the right side of the figure here is
very costly so like let's say you want
to embed a million documents or a
billion documents if you're a big search
engine company so doing this is very
slow and
in contrast doing lookup with kind of
these approximate nearest neighbor
searches is sublinear time or even you
know log time so you can do it
relatively quickly
so it's fine to do lookup over this big
index but if you start updating this
document embedding you need to recreate
the entire index and that would be you
know very computationally costly so the
solution to this proposed in this rag
paper by Lewis at all is uh we only
train the query embeddings and we keep
the document embedding
swix there's other Alternatives like um
there was a paper called realm uh from
early in retrieval base modeling and in
that in that method they basically had
an asynchronous process that was going
through and using the most recent
document in better to re-update the
search index during training but that is
uh you know kind of a very onerous
process so I think it's quite common to
use kind of a fixed document embedding
in update only the
queries another thing to think about is
when do we do retrieval um so there's a
bunch of different methods the rag paper
that I mentioned before did this only
once right at the very beginning of
generation it grabbed a single document
and generated the entire output this is
the default method used by most
systems however there's other options as
well you can retrieve uh several times
during generation as
necessary and the way this works uh we
can do this either by generating a
search token uh saying that we should
start searching or searching when the
model is
uncertain and another way is to do this
every token so we can do this by finding
similar final embeddings and using this
to influence the
probabilities or approximating attention
with nearest neighbors so I'm going to
explain about each of these in a bit
more detail
in so triggering retrieval with token
embeddings is um was proposed by Tool
forer shik all and the way it works is
you generate tokens that Tri trigger
retrieval or other tools so in this
particular method it uh had several
tools including asking a QA model or
getting a calculator or having a machine
translation system but with respect to
retrieval augmented generation it had
this essentially Wiki search
functionality that would look up
something in Wikipedia and then use that
to influence the final
probabilities
and the way this was trained is training
was done in an inative manner where it
basically generated uh kind
of examples of tools being useful and
when the
tools improve the probability of the
following output then that would be kind
of treated as a positive example and
used to further train the model so this
was really influential and in fact this
is how things are implemented in chat
GPT nowadays not only for um doing
retrieval but also doing other tools
like um for example uh generating code
or generating images or other things
like
this another option is to trigger
retrieval uh with uncertainty estimates
so flare this is a paper by my student
Jang bang um where we try to generate
content and then do retrieval if the
language model certainty is low so
here's a schematic of how this works but
basically um if we have
some uh retrieved documents we can say
generate a a summary about Joe Biden and
when it generates a summary maybe for
the first output um the language model
has high
confidence and because the language
model has high confidence we just
generate the
output
however in the next step if it might
generate something like saying Joe Biden
attended the University of Pennsylvania
where he earned a law degree but the
model might not be very certain about
this it might have a low probability of
certain important entities and So based
on this uh we then form a a query where
what we do is essentially we blank out
the low probability parts of this and we
do a search and so this is also a little
bit like the hypothetical
edings method where we basically create
a document that we think will look
similar to the document that we want to
find we use that to create search
results and then we generate the output
and then we continue doing that and
whenever we have a high confidence
output like the one here we don't do any
retrieval we just you know generate uh
directly from the parameters of the
model but whenever we have low
confidence outputs we do the retrieval
and base the output on this and so I I
think this is uh you know a nice method
that could potentially be uh used the
downside to that is you might sometimes
need to generate twice because you would
generate the output once and then find
the low confidence parts and generate
again but you know if you really care
about the uh kind of quality of the
output this is I think a reasonable
thing to
do okay so now moving on to the Token by
token retrieval
methods the kind of original or one of
the methods that popularized this idea
of token by token retrieval is something
called K&N LM and the way it works is it
retrieves similar
examples and then uses the following
tokens from these
examples and this is kind of like a very
powerful count-based byr model in a way
so if you remember back to when we were
talking about count based Pam models
what we would do is we would take the
previous token and we would calculate
the probability of the next token by
summing up together all of the next
tokens and dividing by the total number
of times that previous token
occurred and so given that background uh
we can talk about how the KLM
works so we have the text context X
and we want to generate a Target output
separately from this we have all of the
training contexts so this is all of the
contexts that appeared in our training
data and we encode all of these training
contexts specifically by calculating the
representation of the final layer or
near the final layer of the model and so
we encode that as
representations separately from that we
remember the next word that appeared
after this Contex
so now we have a data store consisting
of representations in next words we then
take the representation of the current
context and we calculate the distance
between the current context and all of
the other similar context in the
database we take the nearest K so we
take the top uh K examples here which
would be Hawaii Illinois and
Hawaii we then do uh some sort of
normalization based on the
distance and this gives us a probability
distribution over all of the next tokens
sometimes these tokens are duplicated
multiple times and so we aggregate all
of these counts to be Hawaii for example
0.8 and Illinois
0.2 and then we interpolate this with
the probability given by the standard
language model using an interpolation
coefficient Lambda and this gives us our
final
probability so the nice thing about this
is this allows us to explicitly ground
our outputs in individual
examples uh and it's a pretty effective
way to improve the probability of models
improve translation and other stuff like
this the disadvantage of doing this is
that it provides it it kind of ADD add
an extra component of the model it adds
extra
um kind of hyperparameters like Lambda
and things like this so it is a little
bit finicky and it doesn't work in all
situations and so another method that we
uh proposed or by Manda Birch who gave
the uh previous lecture on generation in
this class is unlimi forer and basically
what unlimi forer does is it notes that
attention itself is an in inner product
search and it does topk
attention and the way we do this is we
first process the input with a sliding
window and then perform attention using
a vector index so if we have a really
long input that we want to encode what
we do is we first encode chunks so we
encode for example AB
then we encode CD and we encode EF we
concatenate them together into a big
index of one long input so in a way that
this is similar to what they did in the
KLM you know concatenate all of these
embeddings into a single
input but the difference is that this is
done with
um the values that we are attending to
as opposed to just the final
layer and
the interesting thing about this is now
we have an index of one long input and
when we want to do our next version of
attention we do KNN search from the
query we take the retrieved hidden
States and then we just do attention
over them so the nice thing about this
is in the extreme case this makes no
changes to the model what I mean by this
is let's say our input was small enough
that we could coded in only a single
chunk and for KNN search we also did KNN
search um we did you know exact Canon
search over all of the embeddings in the
trunk in that case this would just be
normal attention it's exactly the same
as normal
attention however there are some
approximations that go into here like
when we encode chunks they might not be
exactly the same as if we encoded the
entire thing together and we're also
chopping off some of the values with
very low um kind of inner products and
so because of this there are some
approximations being made but in the
extreme case if we made no
approximations this would just be
exactly the same model as we were using
before so I find this pretty attractive
and uh you know empirically it gives
very good results over long
distances and you know we can always
make our approximations better and
improve this model as well so I I think
this is a attractive method that you
might be interested in taking a look
at okay for the final part of this I'd
like to talk about long context
Transformers and these are models that
are explicitly trained in a way that
allows you to attend to longer contexts
in an efficient
manner
so one way that we can train over longer
context is just append all of the
context together and in fact shortly
after Transformers came out uh this
paper by VOA at all demonstrated that um
it doing this can learn you know
interesting document level phenomena so
it can identify when
multiple uh words refer to the same
thing or co-reference and other things
like
this however the problem with
Transformers is that computation is
quadratic in the sentence length because
you're multiplying all of the query
vectors by all of the key
vectors
and that basically causes a big problem
if your sequences become very
long so if we go back to what we did in
rnns uh from the very beginning of the
class in rnns they don't have this
problem because computation is linear in
the length of the sequence you just pass
along the RNN State and every single
time you do the same computation over it
so there's no quadratic term in
calculating rnns
another thing is that when doing rnns
you can actually P State infinitely
during the forward pass by just
calculating the hidden State and then
throwing away the rest of the
computation graph that was used in
calculating that hidden State and
there's no approximation that goes on
there so unlike on in un liform that I
was talking about before where we needed
to make approximations none need to be
made in this
case however there is a problem with
doing back propop uh because in order to
do back propop normally you maintain the
entire you know state of the computation
graph and so there a common method to
fix this is basically you pass along the
RNN state from the previous sentence but
you just don't do backdrop into the
previous sentence and this is called
truncated backrop or truncated back
propagation through time and this allows
you to essentially train models with
infinite context um or at least models
that can pass along context infinitely
even if you're not back propping into
they Cod ear
there so of course a problem with this
over long contexts is recurrents uh
recurrent models can be slow due to the
kind of sequential dependence they're
not ideal for um you know running on
gpus or things like that and this is
improved by recent architectures like
Mamba and RW KV which are more conducive
to GPU Based training um while still
maintaining linear time complexity and
so I'm looking forward to talking about
that more in a future
class so actually if we take this idea
of truncated back propagation through
time this can also be applied to
Transformers and there's a really nice
paper Transformer XEL also created by
kungai who was formerly at
CMU and what this does is this attempts
to fix vectors from the previous
sentence so if we have a standard
Transformer uh in a Transformer XL
normally what we do in the standard
Transformer is each Vector attends back
to all the other vectors in the current
context what Transformer XEL does
instead is when you have a new segment
that you want to do backrop
into um you have a new segment that you
want to basically train over you also
attend to all of the previous tokens in
the previous segment but you don't do
back propop into
them so this is essentially truncated
backpropagation through time from the
Transformer
perspective this is also really nice
because what it allows you to do is if
you have a multi-layer
Transformer it allows you to attend far
back so if you look at the last layer
it's attending um to things in the
previous context window but the second
to last layer is attending to things in
the um not just one context window
before but multiple context windows
before and actually this allows you to
very effectively attend a very long
context because each time kind of the
context expands in an exponential
manner so um recently there's a popular
model called mistol that I'm sure a lot
of people have heard about and this is
using sliding window attention which is
essentially the same mechanism proposed
by Transformer XEL so this method is
still uh used in uh very practical
systems another paper that has been
pretty influential in this general area
is something called sparse
Transformers and the way sparse
Transformers work is instead of
attending to every single previous state
you attend to every n previous
States and what this allows you to do is
this allows you to essentially create
something like the strided uh
convolutions or um pyramidal recurrent
neural networks that I talked about
earlier um so what this looks like
essentially is you have um this like if
you have a particular state it might
attend to all of the previous end tokens
but then it
also attends to all of the
previous um kind of M chunks so you kind
of have a combination of local and
Global
attention or not local and Global but
local and kind of longer range attention
and this can be very effective because
you can attend to you know much longer
context with a minimal increase in a
computational
complexity
so another method that's a little bit
like this uh or it's very similar in
spirit but slightly different in
implementation is something called the
compressive
Transformer and in the compressive
Transformer you also have this idea of a
local memory and then a longer term
compressed
memory but you have an explicit
compression step that
directly essentially generates this uh
compressed mem M itself and so this is a
little bit more flexible I guess it
allows you to take all of the you know
relevant things from your local memory
and compress it down so it's another
method that's worth thinking
about finally uh there are some very
interesting methods that do low rank
approximations for
Transformers and so calculating the
attention Matrix is expensive but this
is a matrix and because it's a matrix we
can also approximate it with a lower
rank
Matrix and there's a couple methods that
do things uh like this uh the first one
is something called Blind forer which
adds low rank linear projections into
the model at appropriate
places and um there's another one called
NR forer which approximates using the ni
run method which is based on sampling
Landmark points but basically the
general IDE aide behind this is normally
we do this kind of softmax over you know
a very large attention Vector but
instead we can approximate the softmax
by having some low rank vectors kind of
like what we used in Laura and uh
nonetheless get a reasonable
approximation of the softmax used
inion okay so we're nearing the end of
what I want to talk about today and
finally the thing that I'd like to talk
about is benchmarks for long PEX models
and there's a few benchmarks one very
well-known one is something called long
range Arena this is a composite
Benchmark containing mostly non NLP
tasks and it's definitely used for long
sequence modeling but the results on the
long range Arena actually tend to
diverge uh somewhat from the results
that you get for longdistance language
modeling so in addition to this another
benchmark that I uh personally like and
have used a bit is something called
Scrolls which uh combines together a
whole bunch of kind of QA style or
summarization style tasks that have very
long contexts including over narratives
or books or government reports or other
things like that so you can also take a
look at this if you're interested in
kind of benchmarking longer range
models okay the final thing I'd like to
talk about is now that we have retriever
models we have reader models we maybe
even have reader models that can
effectively use very long contexts like
the ones that we retrieve over whole
documents how do we effectively use them
in our
models so there was a very nice paper um
by Nelson Leo at Stanford that about a
phenomenon that was kinded lost in the
middle and basically what it does is it
demonstrates that many many different
models including state-of-the-art model
models pay less attention to things in
the middle of long context windows and
so if we have an answer and we put it in
you know the first position in Doc in
you know a concatenated context or the
20th position in a concatenated context
it tends to attend more to the ones at
the beginning or the
end in contrast the ones in the middle
kind of get
lost hence the name lost in the middle
and the problem with this is you know if
we are doing something like retrieval in
Reading then that's maybe not such a
huge problem because we could just put
you know the highest scoring documents
at the beginning that might even be more
effective than uh you know concatenating
lots of low scoring documents together
but if we want to read a really long
document and synthesize something
without doing kind of another uh scoring
step uh that can be an issue and also
you know our retriever is not perfect so
we would like the model to the reader
model to do a good job with the outputs
that it
has so there are methods uh to ensure
use of relevant
context so of course better retrievers
make more relevant context you can do
you know reranking or other things like
that and only include the context that
looks most
relevant um or you know refine your
reader model but there's also methods
that can decide whether contact should
be used in the first place so um there
are methods uh to decide whether to use
whether to include passages or not and
also uh recently we proposed a method to
filter down to parts of retrieve
passages uh to have only appropriate
content and this is a model uh that we
called filco it basically filters the
context down to the most relevant
content that we think is appropriate and
that allows us to get better results
when it's fed to the
generator so that's all I have for today
um thank you for watching the video and
for people in the class I'll be happy to
take questions on Piaza or during the
office hours that I had planned thanks a
lot