How LLMs Actually Work: Autoregression, BPE & Scratchpads

AI Systems Syllabus

Syllabus Progress0/24 (0%)

1. Foundational Prompting Mechanics0/6

2. RAG, Vector Search & Embeddings0/5

3. Model Context Protocol (MCP) & Tools0/4

4. Autonomous Agents & Multi-Agent Swarms0/4

5. ML Training, Evals, Inference & Safety0/5

Foundational Prompting Mechanics • Core Foundation9 min read

How LLMs Actually Work: Autoregression, BPE & Scratchpads

Demystifying next-token prediction, vocabulary boundaries, and why models fail without scratchpads.

Practice in Prompt Lab Test in AI Interview

Core Conceptual Brief

Large Language Models are probabilistic next-token predictors. Understanding Byte-Pair Encoding (BPE), context window attention, and why reasoning requires token generation is fundamental to AI engineering.

Theoretical & Empirical Architecture

A Large Language Model (LLM) is fundamentally an autoregressive neural network trained to predict the conditional probability distribution of the next token given an input sequence of tokens:

$P(w_t \mid w_1, w_2, \dots, w_{t-1})$

In Simple English: Read that formula as "Given all the words typed so far ( $w_1$ through $w_{t-1}$ ), what is the probability score of each possible next word $w_t$ ?" Think of it like phone autocomplete on steroids: for the text "The sky is", it gives "blue" a ~75% score, "cloudy" ~12%, and "pizza" ~0.001%, picks one, appends it to the sentence, and repeats the exact same loop until the answer finishes.

When an engineer prompts an LLM with "Write a quicksort in Python", the model does not "think" or plan in a hidden cerebral space before answering. Instead, it computes attention weights across the prompt's token representations and samples the highest probability token (or samples from top-p/temperature distribution) step-by-step.

Under the Hood: Key Engineering Mechanics

1Byte-Pair Encoding (BPE) & The "Strawberry" Problem

LLMs do not see characters; they see integer token IDs produced by subword tokenizers like Tiktoken (cl100k_base or o200k_base). A common prompt like "How many 'r's are in strawberry?" frequently fails on naive models because the word is tokenized into chunks: ["str", "aw", "berry"]. The token for "berry" is an atomic integer (e.g. 8421). The model has no internal activation counting individual characters within that token unless forced to spell it out character by character in a scratchpad.

2The Scratchpad Principle (Compute via Generation)

Because Transformer feedforward layers have a fixed compute budget per token, an LLM cannot perform $O(N^2)$ algorithmic computation in a single forward pass. To solve complex arithmetic, logic, or code diffs, the model MUST emit intermediate tokens. When you instruct an LLM to "Think step-by-step" or output intermediate scratchpad notes, you are giving the model extra inference time compute to attend to its own prior intermediate thoughts.

3Attention Quadratic Complexity (O(N²))

Standard self-attention computes an $N \times N$ matrix where every token attends to every previous token. In simple terms: if your prompt doubles from 1,000 tokens to 2,000 tokens, the attention comparisons quadruple (4x work). Techniques like FlashAttention-2/3, Ring Attention, and PagedAttention are what make modern long-context models computationally viable.

Inspecting Tokenization Boundaries with Tiktoken

import tiktoken

enc = tiktoken.get_encoding("cl100k_base")

def analyze_tokens(text: str):
    token_ids = enc.encode(text)
    token_strings = [enc.decode_single_token_bytes(t).decode('utf-8', errors='replace') for t in token_ids]
    print(f"Text: '{text}'")
    print(f"Token Count: {len(token_ids)}")
    print(f"Tokens: {token_strings}")
    print(f"Token IDs: {token_ids}\n")

# Notice how subwords chunk unevenly:
analyze_tokens("strawberry")
# Output: ['straw', 'berry'] -> Explains why letter counting fails without scratchpads!

analyze_tokens("19842 * 4392")
# Output: ['198', '42', ' *', ' 43', '92'] -> Explains why direct multiplication fails!

Production Guardrails & Takeaways

LLMs operate on tokens, not characters or words. Tokenizer boundaries dictate model capability.
Token generation equals inference compute. If you need complex reasoning, you must prompt the model to emit intermediate tokens.
Never expect a zero-shot model to solve complex multi-step math or logic in a single sentence output without a scratchpad.

Real Staff AI Systems Interview Question

Q: Why does an LLM fail when asked: "Count the number of 's' characters in Mississippi" unless prompted to think step-by-step?

Staff Answer:

The tokenizer maps "Mississippi" into 2 or 3 tokens (e.g. ["Miss", "iss", "ippi"]). The model attends to embeddings representing tokens, not ASCII characters. When asked zero-shot, the model must guess the count in 1 token. When prompted to spell it out character-by-character ("M-i-s-s-i-s-s-i-p-p-i"), each character becomes an explicit token, allowing the self-attention heads to count accurately.