VL12 N-gram Models, LLMs, RAG

Organisation#

Tokens#

Tokens are the individual building blocks of a text. One text can be tokenized in different ways; a token may include spaces and punctuation (Slide 4):

• words: To be or not to be
• subwords: To be , or not to be
• characters: T o b e , …

The n-gram models of this lecture (and the live code) tokenize into characters; modern language models tokenize into subwords.

Count-based n-gram models#

Let $V$ be the vocabulary, the set of distinct tokens. For a token sequence $s$, $\#s$ denotes its number of occurrences in the training text.

Unigram model#

Generating text with a unigram model#

Generate one character after the other, each picked from the distribution independently of the previous (and following) characters (Slide 6).

The lecture code (public/code/lecture-12/ngram_model.py) implements this:

def make_counts_cumulative(counts: list[int]):
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]

def random_char(cumulative_counts: list[int]) -> str:
    r = random.randint(1, cumulative_counts[-1])
    for i, ci in enumerate(cumulative_counts):
        if r <= cumulative_counts[i]:
            return chr(i + ord(" "))

Its vocabulary is the printable ASCII characters from " " to "~"; the models were trained on movie plots from ES11.

Bigram model#

Trigram model#

Generation works as for the unigram model, but the cumulative counts are taken from the distribution of the current context, i.e. the last one (bigram) or two (trigram) generated characters.

General n-gram models#

The N-Gram Model generalizes this to arbitrary $n \in \mathbb{N}$: for each sequence of $n - 1$ previous tokens, a distribution over the next token. Two problems arise (Slide 9):

1. Size. There are $|V| \cdot \ldots \cdot |V| = |V|^n$ possible $n$-grams, infeasibly many for large $n$. For $|V| = 100$: $100$ unigrams, $100^2 = 10\,000$ bigrams, $100^3 = 10^6$ trigrams. Solution: neural models (next section).
2. Unseen contexts. Many sequences of $n - 1$ tokens never occur in the training text, so the model cannot predict the next token after them. Solution: pick the next token at random; this is called smoothing, because it changes the probability distribution.

Neural and large language models#

Neural language models are discussed in depth in WS 26/27; for now it is the same kind of model as above, only trained and computed differently.

Base models vs. instruct models#

(Slide 11)

• Base model: predicts the next token from the previous $n$ tokens (all models seen so far).
• Instruct model: answers questions and converses like a human would. It is still an n-gram model in this sense, only trained so that the produced tokens feel like a human conversation. Instruct models typically have a system prompt that tells the model how to “behave”.

Terminology#

(Slide 12)

• Context size: the number $n$ of previous tokens. Unlike count-based models, neural models allow very large context sizes, up to 1 million.
• Prompt: the sequence of previous tokens. For prompts longer than $n$ tokens, consider only the last $n$, or use RAG (below).
• System prompt: an additional prompt of LLM services; the tokens of a request are the concatenation of the system prompt and the request prompt.

Using an LLM via API (ES12)#

The LLM for ES12 is served at https://ad-llm.cs.uni-freiburg.de/v1/chat/completions. It returns not just the next token but the next $k$ tokens, requested via an HTTP request (Slide 13):

Content-Type: application/json
Authorization: Bearer YOUR_API_KEY

{ "model": "Qwen/Qwen3-Next-80B-A3B-Instruct-FP8",
  "messages": [
    { "role": "system", "content": SYSTEM_PROMPT },
    { "role": "user", "content": PROMPT }
  ],
  "max_completion_tokens": k, "temperature": 0.7 }

max_completion_tokens is the number $k$ of tokens to generate; temperature controls how random the token choice is. In the live demo, the instruct LLM was given the system prompt “Act like a character-based language model and predict the next characters” and compared with the unigram, bigram and trigram models on the same prompt.

Retrieval-Augmented Generation#

Motivation#

Context sizes of current LLMs are large (400k tokens for GPT-5, 1M tokens for Gemini Pro), but many applications need to query a text larger than that. For ES12 the input is the transcripts of all lecture recordings of this course, which exceed the context size of the provided LLM. Idea of Retrieval-Augmented Generation: based on the query, extract a subset of the text and pass only that to the LLM, together with a suitable prompt (Slide 14).

Preprocessing#

(Slide 15)

1. Chunking: split the large input text into (possibly overlapping) chunks. ES12: one chunk per subtitle paragraph (one paragraph per timestamp). Extend each chunk so that its sentences are complete, by searching for the nearest sentence delimiter to the left and to the right.
2. Embedding: compute an embedding of each chunk, of the kind seen in Lecture 11 and ES11. ES12: remove the timestamps before embedding; they carry no useful information for this.

Computing the embeddings#

In ES11 a text embedding was the sum of the embeddings of its words. This is simplistic and does not give the best representation, because not every word is equally relevant for a text. ES12 provides an embedding API that computes an embedding for a given piece of text (Slide 16):

POST https://ad-llm.cs.uni-freiburg.de/v1/embeddings
Content-Type: application/json
Authorization: Bearer YOUR_API_KEY

{ "model": "mixedbread-ai/mxbai-embed-large-v1",
  "input": "Please compute the embedding for this text" }

Processing a query#

(Slide 17)

1. Compute the embedding of the query or prompt, with the same API as for the chunks.
2. Find the $k$ chunks whose embeddings have the highest cosine similarity to the query embedding. ES12: a linear scan over all chunks suffices; real applications precompute a special data structure for this.
3. Pass the text of these $k$ chunks to the LLM, together with a suitable system prompt.

For ES12, experiment with different values of $k$, chunk sizes and system prompts.

References#

Wikipedia articles on word n-gram language models, large language models and retrieval-augmented generation (Slide 18).

Concepts#

• N-Gram Model — unigram, bigram, trigram models learned from counts; $|V|^n$ blow-up and smoothing
• Language Model — distribution over the next token; neural models and LLMs, base vs. instruct, context size, prompt, system prompt
• Retrieval-Augmented Generation — chunk, embed, retrieve top-$k$ by cos-sim, prompt the LLM
• Embeddings — chunk and query embeddings for RAG; sum of word embeddings vs. embedding API
• cos-similarity — ranks chunks against the query embedding
• Token / Tokenization — words, subwords, characters as building blocks of text
• Sampling via Cumulative Counts — generating a token from a count-based distribution
• Smoothing — random next token for unseen contexts
• Large Language Model — neural language model with a very large network
• Base vs. Instruct Model — next-token prediction vs. conversation-tuned model with system prompt
• Chunking — splitting a large text into sentence-complete, possibly overlapping chunks