Transformer Language Model in C - A Deep Dive into Attention Mechanisms

Educational Purpose: This codebase implements a transformer from scratch in pure C to help you understand the mathematical depth and architectural principles behind modern language models like GPT and Claude.

Overview

This project implements a Decoder-only Transformer (like GPT) trained on Shakespeare text. Unlike most machine learning frameworks that abstract away the mathematics, this implementation reveals every calculation, making it perfect for deep learning through understanding.

What You'll Learn

Attention mechanism: How models focus on relevant context
Multi-head attention: Why multiple perspectives work better
Positional encoding: How position information is injected
Transformer blocks: Stacking attention and feed-forward layers
Training: Loss computation and gradient descent
Text generation: Autoregressive sampling strategies

Why C?

No abstraction: Every operation is explicit
Computational understanding: See exactly what's happening
Educational clarity: Mathematical operations are transparent
Foundation knowledge: Understand what frameworks do behind the scenes

Architecture Deep Dive

The Big Picture

Input Text (e.g., "To be or not to be")
    ↓
Token Embedding (convert tokens to vectors)
    ↓
Positional Encoding (add position information)
    ↓
Transformer Block 1 [Attention + FFN + Residual + Norm]
    ↓
Transformer Block 2 [Attention + FFN + Residual + Norm]
    ↓
... (N blocks total)
    ↓
Layer Normalization
    ↓
Output Projection (vocab_size logits per position)
    ↓
Softmax (convert to probabilities)
    ↓
Sample next token or pick highest probability

1. Embedding Layer

Purpose: Convert discrete token IDs into continuous vectors

Token ID 42 → [0.15, -0.23, 0.89, ..., 0.12]  (d_model dimensions)

Why it works:

Tokens with similar meanings should have similar embeddings
Learned during training
Matrix shape: [vocab_size × d_model]

Code location: src/transformer.c - create_transformer()

2. Positional Encoding

Problem: Transformers have no inherent sense of order (unlike RNNs)

Sentence "A ate B" vs "B ate A" look identical to transformer
Need to inject position information

Solution: Add sinusoidal position encoding

PE(pos, 2i) = sin(pos / 10000^(2i/d_model))
PE(pos, 2i+1) = cos(pos / 10000^(2i/d_model))

Why sinusoids?

Unique for each position
Different frequencies at different dimensions
Can be computed without training
Smooth and bounded (helps optimization)

Mathematical insight:

Low frequencies (i=0): Change slowly (capture long-range patterns)
High frequencies (i=d_model-1): Change quickly (capture fine details)
Similar to Fourier analysis!

Code location: src/transformer.c - Positional encoding computation

3. Multi-Head Self-Attention (The Heart)

Scaled Dot-Product Attention

This is the revolutionary mechanism from "Attention is All You Need" paper.

Formula:

Attention(Q, K, V) = softmax(Q·K^T / √d_k) · V

Dimensional Analysis:

Q (Query): [seq_len × d_k] - "What am I looking for?"
K (Key): [seq_len × d_k] - "What are these?"
V (Value): [seq_len × d_v] - "What information do I have?"

Step-by-step computation:

Similarity Computation: Q·K^T → [seq_len × seq_len]
- Computes relevance between each position and all others
- Output[i,j] = dot product of query i with key j
- Higher score = more relevant
Scaling: Divide by √d_k
- Critical for training stability!
- Without scaling: for large d_k, dot products become huge
- Huge values → softmax produces near one-hot vectors
- Near one-hot → vanishing gradients
- With scaling: keeps activation variance constant
Softmax: Convert scores to probability distribution
```
Attention_weights[i,j] = exp(score[i,j]) / sum(exp(score[i,k] for all k))
```
- Ensures weights sum to 1
- Differentiable (good for backprop)
- Maintains gradient flow
Value Aggregation: Multiply by V
- Output[i] = sum(attention_weight[i,j] · value[j] for all j)
- Weighted sum of values
- Positions with high attention contribute more

Why this works:

Each position can "see" all other positions
Parallelizable (no sequential processing like RNNs)
Differentiable end-to-end

Computational Cost:

Q·K^T: O(seq_len² × d_k)
This is the bottleneck! Quadratic in sequence length
Longer sequences = exponentially slower
This is why long-context models use approximations

Code location: src/attention.c - scaled_dot_product_attention()

Multi-Head Mechanism

Problem: Single attention head focuses on one relationship type

Motivation (ANALOGY): Imagine analyzing a sentence with multiple experts:

Expert 1: Focuses on syntactic relationships (grammar)
Expert 2: Focuses on semantic relationships (meaning)
Expert 3: Focuses on discourse relationships (context)
They all contribute their analyses

How it works:

Project to smaller dimensions
```
For each head h:
    Q_h = Q · W_Q^h        (linear projection)
    K_h = K · W_K^h
    V_h = V · W_V^h
```
- Instead of d_model, each head uses d_k = d_model / num_heads
- Multiple sets of learned projection matrices
Compute attention independently
```
head_h = Attention(Q_h, K_h, V_h)
```

Concatenate results

concat = [head_1 || head_2 || ... || head_h]  (shape: seq_len × d_model)

Final projection
```
output = concat · W_O
```

Why multiple heads work better:

Representations are now multi-dimensional
Each head can specialize in different patterns
8 heads (typical) = 8 different "view points"
Empirically found to improve model capacity without computational cost

Parameter efficiency:

Single head: Q [d_model × d_model] = d_model² params
8 heads: 8 × Q [d_model × d_k] = 8 × d_model × (d_model/8) = d_model² params
Same number of parameters, much more expressive!

Code location: src/attention.c - multi_head_attention_forward()

4. Transformer Block (Stacking Layers)

Each block consists of:

Residual Connection
    ↓
LayerNorm → MultiHeadAttention → Add Input (Residual)
    ↓
LayerNorm → FeedForwardNetwork → Add Input (Residual)
    ↓
Output

Residual Connections (Skip Connections)

Problem: Deep networks suffer from vanishing gradients

Gradients exponentially decay through many layers
Weights barely update in early layers
Can't train very deep models

Solution: Shortcuts

Output = sublayer(x) + x

Why it helps:

Gradient can flow directly through skip connection
Unblocked path: ∂L/∂x_initial reaches even deep layers
Allows training of 100+ layer networks
ResNets use this everywhere

Gradient flow:

Without skip: ∂L/∂x = ∂L/∂output · ∂output/∂sublayer · ∂sublayer/∂x
With skip: ∂L/∂x = 1 + ∂L/∂output · ∂output/∂sublayer · ∂sublayer/∂x
                    ↑
                    Direct path!

Layer Normalization

Formula:

LayerNorm(x) = (x - mean(x)) / sqrt(variance(x) + epsilon) * gamma + beta

What it does:

Normalizes each sample independently across features
Keeps activation magnitudes reasonable
Stabilizes training

Why before sublayer (Pre-LN):

Modern transformers use LayerNorm before sublayer (Pre-LN)
Better for training stability
Enables training very deep models without careful initialization

Mathematical insight:

Prevents activation explosion/vanishing
Makes learning rate less sensitive
Gradient magnitudes more uniform across layers

Feed-Forward Network

Each block has a two-layer network:

FFN(x) = ReLU(x · W1 + b1) · W2 + b2

Dimensions:

Input: d_model
Hidden: d_ff (typically 4 × d_model)
Output: d_model

Why expand and contract?

Expansion: increases model capacity
Hidden layer: introduces non-linearity (ReLU)
Contraction: projects back to d_model
Total params: 2 × d_model × d_ff (majority of parameters!)

With GELU activation (what modern transformers use):

FFN(x) = GELU(x · W1 + b1) · W2 + b2

GELU vs ReLU:

GELU: smoother, sigmoid-like, better for transformers
More expensive to compute but better results
GELU(x) ≈ x · Φ(x) where Φ is CDF of standard normal

Code location: src/transformer.c - ffn_forward()

5. Output Layer

hidden_state [seq_len × d_model] → Linear [d_model × vocab_size] → logits [seq_len × vocab_size]

Logits: Raw unnormalized scores for each token

Not probabilities yet
Softmax converts to probabilities
Temperature scaling changes distribution shape

Installation & Usage

Prerequisites

GCC compiler (gcc or clang)
Make utility
Standard C library with math support

Build

cd transformer-shakespeare
make clean
make

Run

make run
# or
./build/transformer

Expected Output

╔════════════════════════════════════════════════════════════╗
║  TRANSFORMER LANGUAGE MODEL - SHAKESPEARE EDITION         ║
║  Written in Pure C for Educational Purposes              ║
╚════════════════════════════════════════════════════════════╝

[1] Building Vocabulary...
    - Vocabulary size: 50 unique characters
    - Text length: 450 characters

[2] Tokenizing Text...
    - Total tokens: 450

[3] Creating Dataset...
    - Sequence length: 16
    - Training examples: 434

[4] Creating Transformer Model...
    ...
[5] Training Model...
    ...
[6] Generating Text...

Customization

Edit src/main.c to change:

Training data: modify sample_shakespeare
Model size: d_model, num_layers, num_heads
Training: num_epochs, batch_size
Hyperparameters: learning rate, sequence length

Code Structure

transformer-shakespeare/
├── include/                    # Header files with documented interfaces
│   ├── math_utils.h           # Linear algebra, activations, initialization
│   ├── attention.h            # Attention mechanisms
│   ├── transformer.h          # Transformer model definition
│   ├── data.h                 # Data loading and tokenization
│   ├── training.h             # Training loop and optimization
│   └── inference.h            # Text generation and sampling
│
├── src/                        # Implementation files
│   ├── math_utils.c           # Mathematical operations (~300 lines)
│   ├── attention.c            # Attention implementation (~250 lines)
│   ├── transformer.c          # Transformer blocks (~350 lines)
│   ├── data.c                 # Data handling (~200 lines)
│   ├── training.c             # Training loop (~250 lines)
│   ├── inference.c            # Generation (~200 lines)
│   └── main.c                 # Example usage (~150 lines)
│
├── Makefile                    # Build configuration
└── README.md                   # This file

Total: ~2000 lines of carefully commented code

Module Dependencies

main.c
  ├── transformer.h (model definition)
  ├── training.h (training loop)
  ├── inference.h (text generation)
  └── data.h (data handling)
       └── ...

Mathematical Foundations

Why Attention Works (Theoretical Understanding)

Information Theory Perspective

Transformers solve this problem: how to aggregate information efficiently

Traditional approaches:

RNNs: Process sequentially (O(seq_len) time)
CNNs: Fixed receptive field (hard to capture long-range)
Attention: Every position can see every other position (O(seq_len²) space but parallelizable)

Optimization Perspective

Why gradient descent finds good solutions:

Smooth loss landscape: Softmax creates smooth, differentiable functions
Well-behaved gradients: Cross-entropy + softmax combination gives clean gradients (grad = softmax - target)
Scaling helps: 1/√d_k prevents activation explosion

Statistical Perspective

Why attention learns to attend to relevant information:

Model minimizes cross-entropy loss
Cross-entropy penalizes wrong predictions exponentially
Attention weights that focus on relevant context reduce loss
Gradient descent finds these weights

Key Mathematical Insights

Why Softmax?

Among all normalization schemes, softmax has special properties:

Exponential penalty for wrong answers: exp makes differences matter more
Simple gradient: ∇softmax = Jacobian with simple form
Information theory: Softmax is KL divergence minimizer
Probability interpretation: Exponential family distribution

Why Layer Norm before Attention?

Pre-LN empirically works better than Post-LN:

Stabilizes gradient flow
Prevents activation explosion
Enables training of very deep models
Mathematical analysis shows lower gradient variance

Why Feed-Forward Networks?

FFN = depth × width trade-off:

Expands to d_ff (add capacity)
Contracts back (keep parameters same)
Non-linearity makes combinations of features

Key Concepts Explained

1. Token & Embedding

Raw text: "To be"
  ↓ [Tokenize - split into tokens]
Tokens: ["To", "be"]  (or character-level: ["T", "o", " ", "b", "e"])
  ↓ [Embedding - lookup table]
Embeddings: [[0.1, 0.2, ...], [0.3, 0.4, ...]]  (d_model dimensional)

Character-level tokenization (used here):

Pros: Small vocabulary, doesn't need preprocessing
Cons: Longer sequences, harder to learn

Word-level tokenization:

Pros: Shorter sequences, more meaningful
Cons: Large vocabulary, rare words problem

Subword tokenization (BPE, WordPiece - used in real models):

Pros: Best of both worlds
Cons: More complex

2. Sequence Masking (Causal Mask)

Problem: During generation, model shouldn't look at future tokens

Want to generate token at position i
Can only use tokens 0..i-1 (not i+1, i+2, ...)
Prevents cheating

Solution: Causal mask

For position i, set attention to j>i to -infinity
After softmax, these become 0
Model can't attend to future

Code: attention.c - scaled_dot_product_attention_causal()

3. Loss Functions & Cross-Entropy

Cross-Entropy Loss:

Loss = -log(P(correct_token))

Why log?

Logarithm penalizes overconfidence
log(0.9) ≈ -0.1 (small loss)
log(0.1) ≈ -2.3 (big loss)
Exponential penalty for wrong confident predictions

Softmax + Cross-Entropy gradient:

∇Loss = softmax(logits) - target_one_hot

This elegant form is one reason softmax+CE is universal in classification.

4. Temperature Sampling

Purpose: Control creativity vs consistency

softmax(logits / temperature)

Temperature effects:

T = 0.5: Sharp distribution (consistent, less creative)
T = 1.0: Default (balanced)
T = 2.0: Flat distribution (more random, more creative)

Use cases:

T = 0.8 for chatbots (coherent, some diversity)
T = 1.0 for text generation (balanced)
T = 0.1 for QA (high confidence answers)

5. Why Gradients Flow in Residual Networks

Without residuals:

x₀ → Layer1 → x₁ → Layer2 → x₂ → ... → xₙ → Loss

Gradient backflow:
∂Loss/∂x₀ = ∂Loss/∂x₁ · ∂x₁/∂x₀ · ∂x₂/∂x₁ · ... (product of many small numbers)

With residuals:

∂Loss/∂x₀ = 1 + (gradient through layers)

The direct path allows gradients to reach deep layers!

Advanced Topics

Topic 1: Training from Scratch vs Fine-tuning

This code implements training from scratch:

Start with random weights
Feed in text examples
Gradually learn patterns
Very slow on small datasets
Better for understanding learning process

Fine-tuning (used in practice):

Start with pre-trained model (e.g., GPT-2)
Only adjust weights for specific task
Much faster, works with less data
Production approach

Why from scratch is educational:

See random → learning → coherent output
Understand what training actually does
See loss decreasing over time

Topic 2: Optimization Deep Dives

Gradient Descent Variants

SGD (Stochastic Gradient Descent):
```
weights -= lr * gradient
```
Simple but oscillates

Momentum:

velocity = beta * velocity + gradient
weights -= lr * velocity

Accelerates in consistent direction

Adam (what this code implements):

m = beta1 * m + (1 - beta1) * gradient       (momentum)
v = beta2 * v + (1 - beta2) * gradient²     (RMSprop)
weights -= lr * m / (sqrt(v) + eps)

Best practical choice

Learning Rate Scheduling

This code includes:

cosine_annealing_lr: Smooth decrease
step_decay_lr: Drop at milestones

Why schedule?

Large LR initially: escape poor local minima
Small LR later: fine-tune solution
Empirically improves convergence

Topic 3: Attention Visualization

The attention weights are interpretable!

For attention head h at position i:

attention_weights[i][j] = probability of attending to position j

Visualizing as heatmap shows what model attends to.

Observations in real models:

Early layers: Attend to nearby tokens (syntax)
Later layers: Attend to semantically relevant tokens
Some heads learn to attend to most common tokens
Some heads learn pattern-specific rules

Topic 4: Scaling to Real Models

This implementation is proof-of-concept. Real models:

Changes needed:

KV Cache: Store key/values to avoid recomputation (50-100x faster)
Flash Attention: IO-aware attention algorithm
Efficient Position Encoding: Rotary embeddings (RoPE)
Mixture of Experts: Replace FFN with conditional experts
Low-Rank Adaptation: LoRA for parameter-efficient fine-tuning

Current limitations:

CPU only (slow)
No GPU CUDA kernels
Naive attention (not fused)
No distributed training

To scale to billions of parameters:

Use PyTorch or Jax
Multi-GPU training
Gradient checkpointing
Sparse attention patterns

References

Core Papers

"Attention is All You Need" (Vaswani et al., 2017)
- Introduced transformer architecture
- Foundation for all modern LLMs
- https://arxiv.org/abs/1706.03762
"BERT: Pre-training of Deep Bidirectional Transformers" (Devlin et al., 2019)
- Encoder-only transformer
- Masked language modeling
- https://arxiv.org/abs/1810.04805
"Language Models are Unsupervised Multitask Learners" (Radford et al., 2019)
- GPT-2: Decoder-only transformer
- Demonstrated scaling laws
- https://d4mucfpksywv.cloudfront.net/better-language-models/language_models_are_unsupervised_multitask_learners.pdf
"Scaling Laws for Neural Language Models" (Kaplan et al., 2020)
- Mathematical laws governing model scaling
- Predictable improvement with parameters
- https://arxiv.org/abs/2001.08361

Supplementary Resources

3Blue1Brown: Visual intuition for attention
Jay Alammar's Blog: Excellent illustrated guides
Andrej Karpathy: GPT architecture explanations
OpenAI Research: Technical reports and blogs

Understanding Deep Learning

"Deep Learning" - Goodfellow, Bengio, Courville (textbook)
"Neural Networks and Deep Learning" - Michael Nielsen (online)
"Transformers from Scratch" - various blogs and tutorials

Common Questions & Troubleshooting

Q: Why is training slow on CPU?

A: Transformers have O(seq_len²) complexity. Modern hardware uses:

GPU acceleration (100x faster)
Optimized CUDA kernels
Mixed precision (float16)

Q: Why doesn't text generation quality improve much?

A: Need larger model, more data, longer training:

This uses 2 layers, 64 dims - very small
Real models: 12-96 layers, 768-12288 dims
Shakespeare text: ~450 chars - tiny dataset
Proper training: billions of tokens

Q: How would I make this production-ready?

A:

Implement on GPU (PyTorch/JAX/Triton)
Use standard architectures (GPT-2, GPT-3 style)
Train on large datasets (millions-billions tokens)
Use established training recipes
Implement caching for inference

Q: Can I use this for other languages?

A: Yes! Character-level tokenization works for any language:

Change sample_shakespeare to your text
Rebuild and run
Model learns language automatically

Q: How do I debug training?

A:

Monitor loss (should decrease)
Check gradients aren't NaN/Inf
Verify batch sizes and learning rates
Sample generations mid-training

Final Thoughts: The Depth of Understanding

This codebase achieves something many ML frameworks don't: making the math transparent.

Every transformation is a matrix multiplication. Every gradient is computed from first principles. Every activation is a mathematical function.

By implementing from scratch in C, you:

✅ Understand what frameworks abstract away
✅ Learn numerical stability tricks
✅ See performance implications of design choices
✅ Gain deep intuition for how models work
✅ Can now read papers with full understanding

What's Really Happening When You Run `make run`:

Vocabulary building: Extract unique characters, create ID mappings
Tokenization: Convert text to token IDs
Dataset creation: Overlapping sequences for training
Model instantiation: Random weight initialization (Xavier init)
Training loop:
- Forward pass: tokens → embeddings → transformer blocks → logits
- Loss computation: compare logits to correct tokens
- Backward pass: compute gradients (simplified in this code)
- Optimizer step: update weights with gradient descent
Text generation: Given seed, autoregressively sample next token

All of this is pure C - no magic, no abstraction. Just mathematics!

Contributing & Extensions

Ideas for extending this project:

Implement full backpropagation (gradients for all parameters)
Add beam search (better generation quality)
Implement KV caching (faster inference)
Add positional interpolation (handle longer sequences)
Implement rotary embeddings (RoPE - modern alternative)
Multi-GPU training (with MPI)
Profile and optimize (SIMD, caching)
Visualization tools (attention heatmaps)

License

Educational use - share and modify freely.

Created for those who want to understand transformers at depth.

If you found this helpful, you now understand more about how language models work than most people. Congratulations! 🎉

The transformer is not magic - it's elegant mathematics made practical. And now you know exactly how it works.

Name		Name	Last commit message	Last commit date
include		include
src		src
00_KV_CACHE_START_HERE.md		00_KV_CACHE_START_HERE.md
00_START_HERE.txt		00_START_HERE.txt
ARCHITECTURE.md		ARCHITECTURE.md
FILES_VERIFICATION.md		FILES_VERIFICATION.md
INDEX.md		INDEX.md
KV_CACHE_COMPLETE.md		KV_CACHE_COMPLETE.md
KV_CACHE_GUIDE.md		KV_CACHE_GUIDE.md
KV_CACHE_QUICK_REF.md		KV_CACHE_QUICK_REF.md
KV_CACHE_SUMMARY.md		KV_CACHE_SUMMARY.md
Makefile		Makefile
PROJECT_SUMMARY.md		PROJECT_SUMMARY.md
QUICKSTART.md		QUICKSTART.md
README.md		README.md

Latest commit

History

Folders and files

Repository files navigation