Section 2:
De nition & Preliminariesfi

1

A Retrieval-based LM: De nition

A language model (LM) that uses
an external datastore at test timefi2

A Retrieval-based LM: De nition

A language model (LM) that uses
an external datastore at test timefi2

A Retrieval-based LM: De nition

A language model (LM) that uses
an external datastore at test timefi2

A Retrieval-based LM: De nition

A language model (LM) that uses
an external datastore at test timefi3

A language model (LM)P(xn | x1, x2, ⋯, xn−1)

4A language model (LM)P(xn | x1, x2, ⋯, xn−1)

Language model (Transformers)

The capital city of Ontario isx1x2

⋯

xn−1

4

A language model (LM)P(xn | x1, x2, ⋯, xn−1)
TorontoOttawaVancouverMontreal
Calgary
…

0.52
0.31
0.13
0.03
0.01

Language model (Transformers)

The capital city of Ontario isx1x2

⋯

xn−14

A language model (LM): Categories
TorontoAutoregressive LM
The capital city of Ontario is ______

5

A language model (LM): Categories
TorontoAutoregressive LM
The capital city of Ontario is ______

capitalvs

Ontario

Masked LM
The ______ city of _______ is Toronto5

A language model (LM): Categories
TorontoAutoregressive LM
The capital city of Ontario is ______

capitalvsOntario

Masked LM
The ______ city of _______ is Toronto

Encoder-only
Image source: Devlin et al. 2019. “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”

5

A language model (LM): Categories
TorontoAutoregressive LM

capitalvs

The capital city of Ontario is ______

Encoder-only

Ontario

Masked LMThe ______ city of _______ is Toronto

Decoder-only

Image source: Devlin et al. 2019. “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”

5

A language model (LM): Categories
TorontoAutoregressive LMcapitalvs

The capital city of Ontario is ______

Encoder-only

Decoder-only

Ontario

Masked LM
The ______ city of _______ is Toronto

Encoder-decoder

Image source: Devlin et al. 2019. “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”

5

A language model (LM): Categories
TorontoAutoregressive LM

capitalvsThe capital city of Ontario is ______

Encoder-only

Decoder-onlyOntario

Masked LM
The ______ city of _______ is Toronto

Encoder-decoder

Image source: Devlin et al. 2019. “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”

5

A language model (LM): Prompting

6

A language model (LM): Prompting
The capital city of Ontario is

LM

TorontoFact probing

6

A language model (LM): Prompting
The capital city of Ontario is

Cheaper than an iPod. It wasLM

TorontoFact probingLMgreatterrible

Sentiment
analysis

6A language model (LM): PromptingLM

TorontoFact probing

Cheaper than an iPod. It was

LM

great
terrible

Sentiment
analysis“Hello” in French is

LM

Bonjourno

Translation

The capital city of Ontario is6

A language model (LM): PromptingLM

TorontoFact probing

Cheaper than an iPod. It was

LM

great
terrible

Sentiment
analysis“Hello” in French is

LM

Bonjourno

Translation

I’m good at math. 5 + 8 x 12 =

LM

101

Arithmetic

The capital city of Ontario is6

A language model (LM)Often evaluated with7

A language model (LM)Often evaluated with

TorontoOttawaVancouverMontreal
Calgary…

0.520.31
0.13
0.03
0.01−log(0.52) = 0.284

Perplexity

7

A language model (LM)Often evaluated with

TorontoOttawaVancouverMontreal
Calgary
…

0.52
0.31
0.13
0.03
0.01−log(0.52) = 0.284

Perplexity

Cheaper than an iPod. It was

LM
great
terrible
Prediction: positive

Downstream accuracy(Zero-shot or few-shot in-context learning,or ne-tuning)fi(More in Section 5)

7

A Retrieval-based LM: De nition

A language model (LM) that uses
an external datastore at test timefi8

A Retrieval-based LM: De nition

A language model (LM) that uses
an external datastore at test timefi9

Typical LMs

The capital city of Ontario is Toronto

The capital city of Ontario is _____

LM

LM

Training time

Test time10Retrieval-based LMs

Datastore!

The capital city of Ontario is Toronto

The capital city of Ontario is _____

LM

LM

Training time

Test time11

Inference
Query

Input

LM

Index

Datastore

12

Inference: Datastore
QueryInput

LM

Index

Datastore

Raw text corpus
13

Inference: DatastoreQueryInput

LMIndex

Datastore

Raw text corpus

At least billions~trillions of tokens
Not labeled datasets
Not structured data (knowledge bases)
13

Inference: Index
QueryInput

LMIndex

Datastore

14

Inference: Index
Retrieval input

Input(not necessarily input to the LM)

Query

LM

Index

Datastore

14

Inference: Index
Retrieval input

Input(not necessarily input to the LM)

Query

LM

Index

Datastore

Find a small subset of elements in a datastore
that are the most similar to the query

14

Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the queryfi

15

Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the query

sim: a similarity score between two pieces of textfi

15

Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the query

sim: a similarity score between two pieces of text
ExampleN # of total docs
sim(i, j) = tfi,j × log
dfi # of docs containing i# of occurrences of i in j

fi15Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the query

sim: a similarity score between two pieces of text
ExampleN # of total docs
sim(i, j) = tfi,j × log
dfi # of docs containing i# of occurrences of i in j
Examplesim(i, j) = Encoder(i) ⋅ Encoder( j)Maps the text into an h-dimensional vector

fi15

Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the query

sim: a similarity score between two pieces of text
ExampleN # of total docs
sim(i, j) = tfi,j × log
dfi # of docs containing i# of occurrences of i in j
Examplesim(i, j) = Encoder(i) ⋅ Encoder( j)Maps the text into an h-dimensional vector

An entire eld ofstudy on how to get(or learn) thesimilarity function
better(We’ll see some inSection 4)

fifi15Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the query

sim: a similarity score between two pieces of text

𝒟Index: given q, return argTop-kd∈ sim(q, d) through fast nearest neighbor searchfi16

Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the query

sim: a similarity score between two pieces of text
Index: given q, return argTop-kd∈ sim(q, d) through fast nearest neighbor search𝒟k elements from a datastore

fi16

Inference: Index
Goal: nd a small subset of elements in a datastore
that are the most similar to the query

sim: a similarity score between two pieces of text
Can be a totally separate research area on
how to do this fast & accurate

Index: given q, return argTop-kd∈ sim(q, d) through fast nearest neighbor search𝒟k elements from a datastore

fi16

Software: FAISS, Distributed FAISS, SCaNN, etc…

17

Software: FAISS, Distributed FAISS, SCaNN, etc…

17

Software: FAISS, Distributed FAISS, SCaNN, etc…
Exact Search

17Software: FAISS, Distributed FAISS, SCaNN, etc…
Exact Search

Approximate Search(Relatively easy to scale to ~1B elements)

17

Software: FAISS, Distributed FAISS, SCaNN, etc…
Exact Search

CPU vs. GPU
Approximate Search(Relatively easy to scale to ~1B elements)

17

Software: FAISS, Distributed FAISS, SCaNN, etc…
Exact Search

CPU vs. GPU
Approximate Search(Relatively easy to scale to ~1B elements)

More info: https://github.com/
facebookresearch/faiss/wiki 17

Inference: Search
Query

Input

LMIndexfast nearest
neighbor search

Datastore

In this tutorial, we assume
we can do it fast &accurate

18

Inference: Search
Query

Input

LMIndexfast nearest
neighbor search

Datastore

In this tutorial, we assume
we can do it fast &accurate

Retrieval18

Inference: Incorporation
Query

Input

LM

Index

Datastore

19

Questions to answer
Query

Input

LM

Index

Datastore20

Questions to answer
What’s the query &when do we retrieve?
Query

Input

LM

Index

Datastore20

Questions to answer
What’s the query &when do we retrieve?
Query

Input

LM

Index

Datastore

What do weretrieve?

20

Questions to answer
What’s the query &when do we retrieve?
Query

Index

Datastore

Input

LMHow do weuse retrieval?

What do weretrieve?

20

Questions to answer

Input

What’s the query &when do we retrieve?
QueryLMHow do weuse retrieval?

Index

Datastore

What do weretrieve?

We’ll answer these questions in Section 3!
20

Notations
Query qx Input
LMIndex

𝒟

Datastorey Output

21