How Large Language Models Generate Text: Tokenization, Internal Representations, and Probabilistic Sampling

Introduction: The Mechanics of Modern Foundation Models

To the casual observer interacting with state-of-the-art foundation models such as GPT-4, Claude 3.5 Sonnet, or Llama 3, the software appears to exhibit a seamless, human-like grasp of rhetoric, analytical thought, and domain expertise. A user inputs a high-level software architectural question, and the interface streams back syntactically pristine code, architectural diagrams, and nuanced trade-off analyses.

Underneath the graphical interface, however, sits an uncompromising mathematical engine: an autoregressive, causal probabilistic transformer. Modern Large Language Models (LLMs) do not compose paragraphs through holistic conceptual deliberation in the human cognitive sense. Instead, they execute an intensely optimized loop of high-dimensional matrix transformations designed to achieve one foundational objective: given an arbitrary prefix sequence of discrete symbols, predict the exact conditional probability distribution over a finite vocabulary for the immediate next symbol, sample an item from that distribution, append it to the sequence, and repeat.

This chapter dissects every mechanical stage of that generative loop. We will follow the computational lifecycle of an input prompt as it is decomposed into numerical subwords, projected onto high-dimensional continuous manifolds, routed through stacked layers of multi-head causal attention and non-linear feed-forward transformations, transformed into unnormalized logits, and ultimately sampled through stochastic decoding algorithms.

1. Subword Tokenization: Transforming Text into Discrete Integers

Computers cannot perform floating-point matrix multiplications on raw Unicode text strings. The preliminary phase of any language model pipeline is therefore tokenization: the deterministic conversion of a continuous character string into a sequence of discrete numerical indices drawn from a pre-computed vocabulary $\mathcal{V}$.

1.1 The Granularity Trade-Off

Language model system designers must balance competing constraints when establishing the granularity of their vocabulary:

• Character-Level Tokenization: Decomposing text into individual characters minimizes vocabulary size ($|\mathcal{V}| \approx 256$ to a few thousand for Unicode). Out-Of-Vocabulary (OOV) errors are virtually eliminated. However, sequence length explodes dramatically; a 500-word essay requires thousands of individual character steps. Because the computational cost of standard self-attention scales quadratically ($\mathcal{O}(L^2)$) with sequence length $L$, character-level modeling imposes massive memory and latency penalties.
• Word-Level Tokenization: Splitting text purely on whitespace or punctuation preserves linguistic semantics within single units. However, vocabulary size balloons past millions of entries, causing the input embedding and output projection layers to dominate total parameter counts and GPU memory. Furthermore, word-level models fail catastrophically when encountering typos, regional dialect variations, code identifiers, or newly coined terms.

1.2 Byte-Pair Encoding (BPE) and Byte-Level Fallbacks

Modern foundation models universally adopt subword tokenization algorithms, primarily Byte-Pair Encoding (BPE) (Sennrich et al., 2016; Radford et al., 2019) or SentencePiece Unigram models.

Byte-level BPE begins by treating all input text as a stream of raw individual bytes ($0$ to $255$). The algorithm iterates through massive training corpora, counting adjacent byte or subword co-occurrences, and iteratively merges the most frequent pairs into new composite tokens until a target vocabulary size—typically between $32,000$ and $128,000$ unique tokens—is reached.

# Conceptual implementation of the Byte-Pair Encoding tokenization loop
from collections import Counter

def train_toy_bpe(corpus: list[str], target_vocab_size: int = 300) -> dict[tuple[str, str], str]:
    # Represent words as lists of individual character tokens terminated by an end symbol
    vocab = Counter([" ".join(list(word)) + " </w>" for word in corpus])
    merges = {}

    while len(merges) < target_vocab_size:
        pairs = Counter()
        for word, freq in vocab.items():
            tokens = word.split()
            for i in range(len(tokens) - 1):
                pairs[(tokens[i], tokens[i + 1])] += freq

        if not pairs:
            break

        best_pair = pairs.most_common(1)[0][0]
        replacement = "".join(best_pair)
        merges[best_pair] = replacement

        # Re-encode vocabulary with newly merged token
        new_vocab = {}
        bigram = " ".join(best_pair)
        for word, freq in vocab.items():
            new_word = word.replace(bigram, replacement)
            new_vocab[new_word] = freq
        vocab = new_vocab

    return merges

By operating at the byte level, modern tokenizers ensure that any arbitrary string of bytes can be represented without generating unknown (<unk>) token exceptions, gracefully handling multilingual text, emojis, mathematical symbols, and raw binary formats.

2. Continuous Geometry: Embeddings and Rotary Position Encodings (RoPE)

Once a prompt string is mapped into a discrete integer array $\mathbf{x} = [t_1, t_2, \dots, t_L]$, each integer $t_i \in \{0, \dots, |\mathcal{V}|-1\}$ is transformed into a continuous representation via a lookup table: the Embedding Matrix $W_e \in \mathbb{R}^{|\mathcal{V}| \times d_{\text{model}}}$.

In modern architectures, $d_{\text{model}}$ ranges from $2048$ in lightweight edge models to $8192$ or higher in frontier deployments.

2.1 The Permutation Invariance Problem

The core self-attention operator possesses an inherent symmetry: it is completely permutation-invariant. If the input vectors are shuffled into an arbitrary temporal order, the un-indexed attention mechanism produces mathematically identical sets of output vectors. Natural language, however, is intensely order-dependent; "The dog bit the man" represents an entirely different assertion than "The man bit the dog."

2.2 Rotary Position Embedding (RoPE)

While earlier models utilized additive sinusoidal position encodings (Vaswani et al., 2017) or learned absolute position vectors, state-of-the-art models (such as LLaMA, Mistral, Qwen, and Gemma) universally implement Rotary Position Embedding (RoPE), formulated by Su et al. (2024).

RoPE incorporates positional information by rotating the Query and Key vector representations in complex two-dimensional subplanes. For a 2D vector component $(x_1, x_2)$ located at sequence position $m$, the transformation is given by an orthogonal rotation matrix:

When the dot product between a query vector at position $m$ and a key vector at position $n$ is evaluated within the attention head, an extraordinary trigonometric identity emerges:

The resulting inner product depends strictly on the relative distance $n - m$ rather than their absolute positions. This property endows RoPE with superior length extrapolation characteristics, enabling models pre-trained on $4,096$-token sequences to scale smoothly to contexts exceeding $128,000$ tokens via dynamic frequency scaling techniques such as YaRN (Yet another RoPE extensioN).

3. The Transformer Backbone: Attention, SwiGLU, and the Residual Stream

The sequence of embedded and position-encoded vectors enters the deep Transformer decoder stack, which consists of $N$ identical, sequentially stacked transformer blocks (typically $32$ to $80$ layers deep).

3.1 The Residual Stream as a Central Highway

The structural backbone of the network is the Residual Stream (Elhage et al., 2021). Rather than forcing each layer to completely reinvent the representation of each token, vectors propagate straight through the network via skip-connections:

Each attention and MLP sub-layer reads features from the residual stream, performs localized geometric transformations, and writes results back to the stream via additive accumulation. This design eliminates gradient degradation across hundreds of layers and allows early layers to focus on syntactic grouping while deeper layers perform complex semantic synthesis and factual retrieval.

3.2 Causal Multi-Head Self-Attention

Within each layer, the Multi-Head Attention module allows tokens to communicate dynamically. For an input matrix $X$, linear projections compute queries ($Q = X W_Q$), keys ($K = X W_K$), and values ($V = X W_V$).

In autoregressive generation, a token at index $i$ must never receive information from any subsequent token $j > i$. To enforce strict temporal causality, an additive lower-triangular mask $M$ is applied before the softmax operation:

Positions where $M_{ij} = -\infty$ yield zero weight after softmax exponentiation, ensuring complete isolation from future tokens.

3.3 SwiGLU Feed-Forward Networks

Following attention aggregation, each token vector passes independently through a position-wise Feed-Forward Network (FFN). Modern architectures utilize the SwiGLU (Swish Gated Linear Unit) variant introduced by Noam Shazeer:

Empirical research in transformer mechanics suggests that while the attention layers act as routing mechanisms directing information between disparate tokens, the large dimensional projections within the FFN layers function as associative key-value memories storing foundational world facts and linguistic patterns learned during pre-training.

4. The Unnormalized Logits and the Language Model Head

When the hidden states reach the final layer of the Transformer stack, they undergo a terminal normalization step (typically RMSNorm). The final vector corresponding to the last sequence position, $\mathbf{h}_L \in \mathbb{R}^{d_{\text{model}}}$, summarizes the accumulated context of the entire prompt prefix.

This vector is projected back into vocabulary space by the Language Model Head (LM Head), a linear transformation matrix $W_{\text{head}} \in \mathbb{R}^{|\mathcal{V}| \times d_{\text{model}}}$:

The resulting vector $\mathbf{z}$ represents the unnormalized log-odds, or logits, for every candidate token in the dictionary. If vocabulary size $|\mathcal{V}| = 128,000$, $\mathbf{z}$ contains $128,000$ individual floating-point values indicating the relative model confidence that each specific token should occupy position $L + 1$.

Applying the softmax function normalizes these logits into a valid categorical probability distribution:

5. Decoding Strategies: From Determinism to Controlled Stochasticity

How an inference engine selects a token from this categorical distribution determines the qualitative nature of the output.

5.1 Greedy Search and Its Failure Modes

The most trivial strategy is Greedy Search, which selects the token with the absolute highest logit:

While computationally trivial, greedy decoding frequently leads to degenerate generation in open-ended creative tasks. Natural human prose does not exclusively consist of the single most predictable word at every step. Over extended passages, greedy search causes the model to become trapped in repetitive loops, cycling through the same phrases indefinitely.

5.2 Beam Search

Beam search maintains the top $B$ most probable cumulative sequence hypotheses at each step. While standard in deterministic tasks like neural machine translation or closed-domain summarization, beam search produces unnatural, monotonous, and surprisingly uncreative text when applied to modern foundational open-ended generation.

5.3 Stochastic Sampling Algorithms

To generate diverse, engaging, and contextually rich responses, systems employ stochastic decoding algorithms governed by multiple hyperparameters:

# Production-grade implementation of stochastic sampling with multi-parameter filtering
import torch
import torch.nn.functional as F

def sample_next_token(
    logits: torch.Tensor,
    temperature: float = 0.7,
    top_k: int = 50,
    top_p: float = 0.9,
    min_p: float = 0.05,
    repetition_penalty: float = 1.15,
    context_tokens: list[int] | None = None
) -> int:
    # 1. Apply Repetition Penalty to reduce looping
    if context_tokens and repetition_penalty != 1.0:
        for token_id in set(context_tokens):
            if logits[token_id] > 0:
                logits[token_id] /= repetition_penalty
            else:
                logits[token_id] *= repetition_penalty

    # 2. Scale by Temperature
    temperature = max(temperature, 1e-5)
    scaled_logits = logits / temperature

    # 3. Top-k Truncation
    if top_k > 0:
        top_k = min(top_k, scaled_logits.size(-1))
        cutoff_val = torch.topk(scaled_logits, top_k)[0][-1]
        scaled_logits[scaled_logits < cutoff_val] = -float('inf')

    # Compute Softmax probabilities over remaining candidates
    probs = F.softmax(scaled_logits, dim=-1)

    # 4. Min-p Filtering (dynamic pruning based on top candidate probability)
    if min_p > 0.0:
        max_p = torch.max(probs)
        min_p_threshold = max_p * min_p
        scaled_logits[probs < min_p_threshold] = -float('inf')
        probs = F.softmax(scaled_logits, dim=-1)

    # 5. Top-p (Nucleus) Filtering
    if 0.0 < top_p < 1.0:
        sorted_probs, sorted_indices = torch.sort(probs, descending=True)
        cumulative_probs = torch.cumsum(sorted_probs, dim=-1)

        # Shift mask to keep the first token exceeding threshold
        remove_mask = cumulative_probs > top_p
        remove_mask[..., 1:] = remove_mask[..., :-1].clone()
        remove_mask[..., 0] = False

        filtered_indices = sorted_indices[remove_mask]
        scaled_logits[filtered_indices] = -float('inf')
        probs = F.softmax(scaled_logits, dim=-1)

    # 6. Multinomial Categorical Sampling
    sampled_token = torch.multinomial(probs, num_samples=1).item()
    return sampled_token

Sampling Parameters Decoded

• Temperature ($T$): Modulates the entropy of the probability distribution. As $T \to 0$, the distribution approaches a Dirac delta function, mimicking greedy search. As $T$ increases, probabilities flatten, amplifying randomness and lexical diversity.
• Top-k: Truncates the candidate pool to strictly the $k$ most probable tokens, preventing the generator from selecting nonsensical tail items.
• Top-p (Nucleus Sampling): Dynamically sizes the candidate set to the smallest group of tokens whose cumulative probability exceeds threshold $p$. In low-entropy contexts (e.g., following "The capital of France is"), the candidate set shrinks to one token ("Paris"); in high-entropy contexts, it expands organically.
• Min-p: Sets a dynamic threshold relative to the highest probability token. If the top candidate has probability $0.8$ and $\text{min\_p} = 0.05$, only tokens with probability $\ge 0.04$ are retained.

6. The KV Cache and Memory Bandwidth Bottlenecks

Once the sampled token $t_{L+1}$ is produced, it must be appended to the input sequence to generate token $t_{L+2}$. Without optimization, evaluating each successive token would require passing the entire historical context through all Transformer layers again, leading to an unsustainable computational complexity of $\mathcal{O}(L^2)$ matrix operations per token and $\mathcal{O}(L^3)$ across an entire response.

6.1 The Mechanics of Key-Value Caching

At step $t_{L+1}$, the Key ($K$) and Value ($V$) projections computed for previous tokens $t_1, \dots, t_L$ are completely identical to the keys and values computed during the previous forward pass because the causal mask prevents future tokens from altering past representations.

Inference engines therefore implement the Key-Value (KV) Cache:

1. During the Prefill Phase, the entire user prompt is evaluated in parallel, and all Key and Value projection matrices across all layers and attention heads are written to GPU High-Bandwidth Memory (HBM).
2. During the Decode Phase, the engine processes strictly one token at a time. The model projects only the single query vector $\mathbf{q}_{L+1}$, while reading historical $K$ and $V$ vectors directly from the cache in HBM.

6.2 Memory Bandwidth Bound Inference

The KV Cache eliminates redundant computation, reducing per-token generation complexity to $\mathcal{O}(L)$. However, it introduces an acute hardware bottleneck: Memory Bandwidth.

During the decode phase, the arithmetic intensity (FLOPs per byte of memory read) is exceptionally low. For every single token generated, the GPU must stream gigabytes of cached Key and Value weights from HBM to on-chip SRAM. Consequently, modern LLM inference speed is governed not by tensor core computation speed, but by memory bandwidth saturation. Techniques such as PagedAttention (vLLM), Grouped-Query Attention (GQA), and KV cache quantization (FP8, INT4) represent the forefront of system engineering efforts to overcome this memory wall.

7. Comparative Summary of Sampling Configurations

The following matrix illustrates how common sampling profiles alter generation attributes across enterprise and developer use cases:

8. Conclusion

Text generation in large language models is a continuous cycle of discrete symbolization, continuous vector projection, causal information routing, and stochastic probability decanting.

The remarkable reasoning capabilities that emerge from these models are not the product of magical sentience, but the manifestation of statistical modeling executed at unprecedented scale. By understanding how each discrete token emerges from the convergence of rotary embeddings, SwiGLU gating, residual propagation, and nucleus sampling, developers and engineers can design more resilient, performant, and reliable generative systems.