Understanding Transformer Architecture Algorithm: Theory and Implement

1. Introduction and Core Concepts

The transformer architecture algorithm, introduced in the seminal 2017 paper "Attention Is All You Need" by Vaswani et al., fundamentally reshaped the landscape of machine learning algorithms for sequential data. Unlike its predecessors that processed sequences iteratively, the transformer relies entirely on a mechanism called self-attention to draw global dependencies between inputs and outputs, enabling unprecedented parallelization and scalability. It is the foundational architecture behind large language models (LLMs) such as GPT-4, BERT, and T5, as well as vision transformers (ViT) and multimodal systems.

At its core, the transformer architecture algorithm is an encoder-decoder neural network that transforms one sequence into another without recurrence or convolution. It treats input sequences as sets of tokens enriched with positional information, allowing the model to weigh the relevance of every token to every other token simultaneously. This global receptive field solves the long-range dependency problem that plagued recurrent neural networks (RNNs) and long short-term memory (LSTM) networks, where information had to propagate through many time steps and was susceptible to vanishing gradients.

Understanding this algorithm matters because it underpins nearly all state-of-the-art systems in natural language processing, code generation, machine translation, and increasingly, computer vision, speech recognition, and computational biology. For engineers and researchers, mastering the transformer means understanding how modern AI systems scale to billions of parameters, how they can be trained efficiently on massive datasets, and how attention can be adapted to diverse domains. Its design principles — parallel computation, residual connections, layer normalization, and attention — have become standard building blocks far beyond the original machine translation task.

Why Transformers Replaced Recurrence

Before transformers, sequence modeling relied on sequential processing: RNNs processed token t only after token t-1 was complete, which prevented parallelization across the sequence length. This bottleneck made training on long sequences extremely slow and limited the effective context window. Transformers eliminate this sequential dependency by computing representations for all positions at once through matrix multiplications, making them highly amenable to modern GPU and TPU acceleration.

Another critical advantage is the constant path length between any two positions. In an RNN, the number of steps required for a signal to travel from position i to position j grows linearly with |i - j|, making it difficult to learn distant relationships. In a transformer, any two tokens interact directly in a single self-attention layer with O(1) path length, allowing the model to capture syntactic and semantic relationships regardless of distance, such as subject-verb agreement across a long subordinate clause.

2. How It Works

The transformer architecture algorithm consists of two main stacks: an encoder and a decoder. The encoder maps an input sequence of symbol representations (x1, ..., xn) to a sequence of continuous representations (z1, ..., zn). The decoder then generates an output sequence (y1, ..., ym) one element at a time, using the encoder's output and previously generated symbols as context. Both stacks are composed of identical layers, each containing two primary sub-layers: a multi-head self-attention mechanism and a position-wise fully connected feed-forward network, both wrapped with residual connections and layer normalization.

The heart of the model is scaled dot-product attention. Given queries (Q), keys (K), and values (V), the attention function computes a weighted sum of the values, where the weights are determined by the compatibility of the query with each key. Formally, Attention(Q, K, V) = softmax(QK^T / sqrt(d_k))V. The scaling factor sqrt(d_k), where d_k is the dimension of the keys, prevents the dot products from growing too large in magnitude, which would push the softmax into regions with extremely small gradients. In self-attention, Q, K, and V all come from the same source sequence, allowing each position to attend to all positions in the previous layer.

To allow the model to jointly attend to information from different representation subspaces at different positions, the transformer employs multi-head attention. Instead of performing a single attention function, the queries, keys, and values are linearly projected h times with different learned projections, attention is performed in parallel on each head, and the results are concatenated and projected again. This gives the model multiple "views" of the sequence — one head might learn to track syntactic dependencies, another to resolve coreference, and another to capture positional patterns.

Positional Encoding and Feed-Forward Layers

Since the transformer contains no recurrence or convolution, it has no inherent notion of token order. To inject sequence order, positional encodings are added to the input embeddings. The original paper used sinusoidal functions: PE(pos, 2i) = sin(pos / 10000^(2i/d_model)) and PE(pos, 2i+1) = cos(pos / 10000^(2i/d_model)). These encodings allow the model to easily learn to attend by relative positions, as any fixed offset can be represented as a linear function of the encoding. Learned positional embeddings are also common in modern variants like BERT and GPT.

Each layer also contains a position-wise feed-forward network applied identically to each position: FFN(x) = max(0, xW1 + b1)W2 + b2. While attention handles communication between positions, the FFN processes each position independently, adding non-linear capacity and allowing transformation of the aggregated attention output. Residual connections around each sub-layer followed by layer normalization, expressed as LayerNorm(x + Sublayer(x)), are critical for training deep stacks of 12 to 96+ layers by improving gradient flow and stabilizing optimization.

Encoder-Decoder Attention and Masking

In the decoder, two attention mechanisms are present. Masked multi-head self-attention ensures that predictions for position i can only depend on known outputs at positions less than i, preserving the autoregressive property needed for generation. This is achieved by masking future positions (setting their softmax inputs to -infinity) before the softmax. The second attention layer performs cross-attention over the encoder's output, where queries come from the decoder and keys and values come from the encoder, allowing every decoder position to attend over all input positions.

3. Implementation

Implementing the transformer architecture algorithm from scratch clarifies how the mathematical operations translate into efficient tensor computations. Below are modular Python implementations using PyTorch and NumPy that follow the original architecture closely. All examples assume a model dimension d_model, number of heads h, and sequence length n. Pay careful attention to tensor shapes, scaling, and masking.

The first building block is scaled dot-product attention. This function is the primitive used by every attention head and must handle optional masking for decoder self-attention and padding. Numerical stability is maintained by scaling before the softmax and by masking with large negative values.

import math
import torch
import torch.nn as nn
import torch.nn.functional as F

def scaled_dot_product_attention(Q, K, V, mask=None):
    """
    Compute scaled dot-product attention.
    Q, K, V: tensors of shape (batch, heads, seq_len, d_k) or (batch, seq_len, d_k)
    mask: tensor with 0 for positions to mask, 1 for keep (or None)
    """
    d_k = Q.size(-1)
    # QK^T / sqrt(d_k) : shape (batch, heads, seq_len, seq_len)
    scores = torch.matmul(Q, K.transpose(-2, -1)) / math.sqrt(d_k)

    if mask is not None:
        # mask shape must be broadcastable to scores
        # positions where mask == 0 are set to large negative value
        scores = scores.masked_fill(mask == 0, -1e9)

    attn_weights = F.softmax(scores, dim=-1)
    # Optional dropout would be applied here: attn_weights = dropout(attn_weights)
    output = torch.matmul(attn_weights, V)
    return output, attn_weights

Multi-head attention wraps this primitive by projecting inputs into multiple subspaces. The implementation below splits d_model into h heads of dimension d_k = d_model // h, applies attention in parallel, then concatenates and projects. This parallelization is what makes the transformer so efficient on GPUs, as all heads are computed as batched matrix multiplications.

class MultiHeadAttention(nn.Module):
    def __init__(self, d_model, num_heads):
        super().__init__()
        assert d_model % num_heads == 0, "d_model must be divisible by num_heads"
        self.d_model = d_model
        self.num_heads = num_heads
        self.d_k = d_model // num_heads

        self.W_q = nn.Linear(d_model, d_model, bias=False)
        self.W_k = nn.Linear(d_model, d_model, bias=False)
        self.W_v = nn.Linear(d_model, d_model, bias=False)
        self.W_o = nn.Linear(d_model, d_model, bias=False)

    def forward(self, query, key, value, mask=None):
        batch_size = query.size(0)

        # Linear projections and split into heads
        # Shape after view: (batch, seq_len, num_heads, d_k)
        Q = self.W_q(query).view(batch_size, -1, self.num_heads, self.d_k).transpose(1, 2)
        K = self.W_k(key).view(batch_size, -1, self.num_heads, self.d_k).transpose(1, 2)
        V = self.W_v(value).view(batch_size, -1, self.num_heads, self.d_k).transpose(1, 2)

        # Apply attention on all heads in parallel
        # attn_output shape: (batch, num_heads, seq_len, d_k)
        attn_output, attn_weights = scaled_dot_product_attention(Q, K, V, mask)

        # Concatenate heads: (batch, seq_len, d_model)
        attn_output = attn_output.transpose(1, 2).contiguous().view(batch_size, -1, self.d_model)
        output = self.W_o(attn_output)
        return output, attn_weights

Positional encoding and the full encoder layer combine attention with feed-forward processing, residual connections, and layer normalization. The sinusoidal encoding requires no learnable parameters and generalizes to sequence lengths longer than those seen during training, while the encoder layer demonstrates the canonical Add & Norm pattern.

class PositionalEncoding(nn.Module):
    def __init__(self, d_model, max_len=5000):
        super().__init__()
        pe = torch.zeros(max_len, d_model)
        position = torch.arange(0, max_len, dtype=torch.float).unsqueeze(1)
        div_term = torch.exp(torch.arange(0, d_model, 2).float() * (-math.log(10000.0) / d_model))
        pe[:, 0::2] = torch.sin(position * div_term)
        pe[:, 1::2] = torch.cos(position * div_term)
        pe = pe.unsqueeze(0)  # shape (1, max_len, d_model)
        self.register_buffer('pe', pe)

    def forward(self, x):
        # x shape: (batch, seq_len, d_model)
        seq_len = x.size(1)
        # pe[:, :seq_len, :] broadcasts correctly
        # Check that seq_len <= max_len for safety
        if seq_len > self.pe.size(1):
            raise ValueError("seq_len exceeds max_len in PositionalEncoding")
        x = x + self.pe[:, :seq_len, :]
        return x

class EncoderLayer(nn.Module):
    def __init__(self, d_model, num_heads, d_ff, dropout=0.1):
        super().__init__()
        self.self_attn = MultiHeadAttention(d_model, num_heads)
        self.ffn = nn.Sequential(
            nn.Linear(d_model, d_ff),
            nn.ReLU(),
            nn.Linear(d_ff, d_model)
        )
        self.norm1 = nn.LayerNorm(d_model)
        self.norm2 = nn.LayerNorm(d_model)
        self.dropout = nn.Dropout(dropout)

    def forward(self, x, mask=None):
        # Self-attention sub-layer with residual + norm
        attn_out, _ = self.self_attn(x, x, x, mask)
        x = self.norm1(x + self.dropout(attn_out))
        # Feed-forward sub-layer with residual + norm
        ffn_out = self.ffn(x)
        x = self.norm2(x + self.dropout(ffn_out))
        return x

Finally, a minimal training step shows how masking, loss computation, and optimization interact. For language modeling, the decoder uses a causal mask to prevent looking ahead, and label smoothing or cross-entropy loss is computed over the vocabulary.

def create_causal_mask(seq_len):
    # Lower triangular mask: 1 for allowed, 0 for masked (future)
    mask = torch.tril(torch.ones(seq_len, seq_len)).unsqueeze(0).unsqueeze(0)
    # mask shape (1, 1, seq_len, seq_len) broadcastable to (batch, heads, seq_len, seq_len)
    return mask

# Example training loop fragment for a decoder-only transformer
def train_step(model, optimizer, criterion, src, tgt_input, tgt_target, pad_mask=None):
    model.train()
    optimizer.zero_grad()
    seq_len = tgt_input.size(1)
    causal_mask = create_causal_mask(seq_len).to(tgt_input.device)

    # Combine padding mask and causal mask if needed
    # if pad_mask is not None and causal_mask is not None:
    #    combined_mask = pad_mask & causal_mask  (ensure < > escaped in HTML)

    logits = model(src, tgt_input, tgt_mask=causal_mask)  # (batch, seq_len, vocab_size)
    # Flatten for cross-entropy: (batch * seq_len, vocab_size) vs (batch * seq_len)
    loss = criterion(logits.view(-1, logits.size(-1)), tgt_target.view(-1))
    loss.backward()
    # Gradient clipping is critical: torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
    optimizer.step()
    return loss.item()

4. Step-by-Step Example

To make the abstract matrix operations concrete, consider a tiny transformer processing the sentence "the cat sat" with d_model = 4 and h = 2 heads (so d_k = 2). Assume the tokens have already been embedded into vectors: "the" -> [0.2, 0.1, 0.3, 0.4], "cat" -> [0.5, 0.6, 0.1, 0.2], "sat" -> [0.3, 0.2, 0.5, 0.1]. Positional encodings for positions 0, 1, 2 are added, yielding position-aware inputs X of shape (3, 4). This matrix is the input to the first encoder layer.

Step 1: Linear projections. For each head, we multiply X by learned weight matrices W_q, W_k, W_v of shape (4, 2). Suppose for head 1, Q1 = X * W_q1 results in [[0.1, 0.2], [0.4, 0.3], [0.2, 0.5]], similarly K1 and V1 are computed. The same is done for head 2 with different weights. This creates two separate query/key/value spaces, allowing distinct attention patterns.

Step 2: Attention scores. For head 1, we compute Q1 * K1^T / sqrt(2). For the query "cat" (row 1 of Q1), dot products with all keys might yield raw scores [1.2, 2.8, 1.5]. Dividing by sqrt(2) ≈ 1.414 gives [0.85, 1.98, 1.06]. Applying softmax converts these to attention weights [0.19, 0.58, 0.23], showing "cat" attends most strongly to itself but also significantly to "the" and "sat". The output for "cat" is then 0.19*V1["the"] + 0.58*V1["cat"] + 0.23*V1["sat"].

Step 3: Multi-head concatenation and feed-forward. The outputs from head 1 (shape 3x2) and head 2 (3x2) are concatenated to 3x4 and multiplied by W_o (4x4) to return to model dimension. Residual connection adds the original X, followed by layer normalization. The result then passes through the position-wise FFN: for each of the 3 positions independently, the 4-dimensional vector is expanded to d_ff (e.g., 8), ReLU activated, and projected back to 4 dimensions. This final output becomes the input to the next encoder layer, now enriched with contextual information from the entire sentence.

During decoding for translation, the process repeats autoregressively. If translating to French, the decoder starts with a start-of-sequence token, attends to the encoder output via cross-attention, predicts "le", then feeds "le" back in to predict "chat", masking future positions at each step so the model cannot cheat by seeing the target it is trying to predict.

5. Complexity Analysis

The efficiency of the transformer architecture algorithm is best understood through its time and space complexity, which differ markedly from recurrent and convolutional alternatives. The dominant cost is the self-attention operation, which scales quadratically with sequence length n, making it extremely fast for moderate lengths but expensive for very long contexts. The feed-forward network and linear projections scale linearly with n but quadratically with model dimension d.

For a sequence of length n and model dimension d, self-attention requires O(n^2 * d) time because computing QK^T involves multiplying an (n x d) matrix by a (d x n) matrix, resulting in an (n x n) attention matrix, followed by multiplication with V (n x d). Space complexity is O(n^2) for storing the attention matrix and O(n * d) for activations. In contrast, an RNN processes the sequence in O(n * d^2) time but with O(d) sequential steps that cannot be parallelized, while a CNN with kernel size k requires O(k * n * d^2) time but with logarithmic path length if dilated.

The quadratic dependency on n is the transformer's main scalability bottleneck. For n = 512 and d = 768 (BERT-base), n^2 * d ≈ 201 million operations per attention layer, which is manageable. For n = 32,768 (long documents), this grows to over 800 billion operations, necessitating optimizations like sparse attention, linear attention, or FlashAttention. However, the number of sequential operations is O(1) per layer versus O(n) for RNNs, which is why transformers train orders of magnitude faster on modern hardware despite higher total FLOPs.

Best, average, and worst cases are identical for transformers because the computation graph is data-independent — unlike sorting algorithms, there is no early exit. The cost depends solely on n, d, and h, not on input values. This determinism simplifies performance modeling and memory provisioning in production systems. The key optimization for inference is the KV-cache, which stores previously computed keys and values so that decoding each new token costs O(n·d) instead of recomputing O(n^2·d) for the entire sequence.

6. Variations and Optimizations

The vanilla transformer has spawned a vast family of variants designed to improve efficiency, handle longer contexts, or adapt to specific modalities. Three major architectural families have emerged: encoder-only (BERT, RoBERTa), decoder-only (GPT-3/4, LLaMA, PaLM), and encoder-decoder (T5, BART). Encoder-only models use bidirectional attention for understanding tasks, decoder-only models use causal masking for generation, and encoder-decoder models retain both for sequence-to-sequence tasks like translation and summarization.

Efficiency optimizations target the O(n^2) attention bottleneck. Sparse attention patterns, as in Sparse Transformer and Longformer, restrict each token to attend only to a subset of positions — such as local windows plus a few global tokens — reducing complexity to O(n·w) where w is window size. Linear attention methods like Performer and Linformer approximate softmax attention with kernel features to achieve O(n·d) complexity. FlashAttention and FlashAttention-2 do not change the mathematical result but reorder computations to minimize slow high-bandwidth memory reads/writes, yielding 2-4x speedups and enabling much longer contexts without approximation.

Other improvements focus on training stability and capacity. Pre-normalization (LayerNorm before attention/FFN rather than after) as used in GPT-2 and later models improves gradient flow for very deep networks. Mixture-of-Experts (MoE) transformers like Switch Transformer and Mixtral replace the dense FFN with many expert networks and a router that selects 1-2 experts per token, scaling total parameters to trillions while keeping active computation constant. Rotary Positional Embeddings (RoPE) and ALiBi replace sinusoidal encodings to better extrapolate to longer sequences than seen during training.

Choosing among these variants depends on deployment constraints. For real-time chatbots, decoder-only models with FlashAttention and KV-caching are standard. For retrieval-augmented generation over long documents, sparse or linear attention may be necessary. For research, understanding the trade-offs between exact and approximate attention is crucial when scaling to million-token contexts.

7. Real-World Applications

The transformer architecture algorithm has transcended its original machine translation domain to become the universal engine for sequence and even non-sequence tasks. In natural language processing, it powers search engines, chat assistants, code completion tools like GitHub Copilot, and document summarization systems. Encoder-only transformers excel at classification, sentiment analysis, and named entity recognition, while decoder-only models dominate generative tasks.

Beyond text, vision transformers (ViT) treat images as sequences of patches, achieving state-of-the-art results on image classification, object detection, and segmentation with fewer inductive biases than convolutional networks. In speech, transformers are used in models like Whisper for automatic speech recognition and in text-to-speech synthesis. In computational biology, AlphaFold2 uses attention to predict protein structures, and transformers model genomic sequences and drug discovery pipelines.

Even traditional systems infrastructure increasingly leverages transformers. In web servers and databases, learned query optimizers use transformers to predict query execution plans. In networks, transformers analyze traffic sequences for anomaly detection and intrusion prevention. Recommendation systems at companies like Meta, Netflix, and Amazon use transformers to model user behavior sequences, capturing long-term interests far better than Markov or RNN-based models.

Deployment Considerations

Production deployment introduces challenges of latency, cost, and memory. A 70-billion-parameter model requires ~140 GB of GPU memory in 16-bit precision, necessitating model parallelism, quantization to 8-bit or 4-bit, and techniques likePagedAttention for efficient KV-cache management. Caching, batching, and speculative decoding are used to meet service-level objectives for interactive applications where token generation must occur in tens of milliseconds.

8. Comparison with Alternatives

Before transformers, the dominant sequence modeling algorithms were recurrent networks (RNN, LSTM, GRU) and convolutional sequence models (Temporal CNN, ByteNet). Each makes different trade-offs among parallelization, path length, and computational complexity, which directly impact training speed and ability to capture long-range dependencies.

RNNs and LSTMs process tokens sequentially, maintaining a hidden state that is updated at each step. While this gives them O(n) sequential operations and theoretically infinite context, the sequential bottleneck prevents parallel training and the repeated multiplication through time leads to vanishing/exploding gradients, even with gating. CNNs allow parallelization across the sequence and have O(1) sequential operations, but require stacking many layers or using large/dilated kernels to achieve a global receptive field, and their path length grows logarithmically with n.

Transformers achieve O(1) sequential operations and O(1) maximum path length between any two positions, with total complexity O(n^2·d). This makes them ideal when n is moderate (512-8192) and massive parallel compute is available. For extremely long sequences (n > 100k) or resource-constrained edge devices, recurrent or state-space models like Mamba (selective state spaces) are regaining attention because they offer O(n·d) linear scaling with competitive quality.

The choice is not always exclusive. Hybrid architectures are common: Conformer combines convolution and attention for speech, and many efficient transformers incorporate recurrent or convolutional inductive biases to handle long contexts while retaining attention's expressiveness.

9. Common Mistakes and Best Practices

Implementing and training transformers is notoriously sensitive to details that can cause divergence, poor generalization, or wasted compute. One of the most frequent mistakes is incorrect masking. Forgetting to apply the causal mask in the decoder allows the model to peek at future tokens during training, resulting in artificially low loss that does not translate to generation quality. Similarly, failing to mask padding tokens causes attention to be diluted by meaningless positions, especially with variable-length batches.

Another pitfall is mishandling layer normalization placement and learning rate scheduling. The original post-norm formulation (norm after residual) can be unstable for deep models; most modern implementations use pre-norm for stability. Transformers require warmup: starting with a very low learning rate and linearly increasing over the first few thousand steps before decaying with cosine or inverse square root schedule. Without warmup, large gradients early in training can cause divergence due to the high variance of Adam's adaptive estimates.

Numerical and memory errors are also common. Not scaling dot products by sqrt(d_k) leads to extremely peaked softmax distributions and vanishing gradients. Using float16 without loss scaling can cause underflow in softmax and layer norm. Forgetting gradient clipping allows occasional large gradients to destabilize training. On the data side, insufficient regularization — dropout (0.1), weight decay, and label smoothing — quickly leads to overfitting on smaller datasets, while not shuffling or not using proper tokenization (e.g., Byte-Pair Encoding) limits vocabulary coverage.

Best Practices Checklist

• Always verify masks by inspecting attention weights on a small batch; future positions should have weight ≈ 0.
• Use pre-norm, AdamW optimizer with weight decay 0.01-0.1, warmup 1-4% of total steps, and gradient clipping at 1.0.
• Employ mixed-precision training with loss scaling, FlashAttention, and activation checkpointing to fit larger batches.
• Initialize weights with Xavier/Glorot or scaled initialization (e.g., 0.02 std) and scale residual weights by 1/sqrt(num_layers).
• Monitor attention entropy and gradient norms during training; sudden spikes often indicate masking or learning rate bugs.
• For inference, implement KV-caching, use key-value quantization, and batch requests to amortize memory bandwidth.

10. Interview Questions

Transformer architecture questions are staples in machine learning interviews for roles involving LLMs, NLP, or deep learning systems. Interviewers probe both conceptual understanding and the ability to reason about trade-offs and implementation details. Below are common questions with concise, interview-ready answers that demonstrate depth.

Q1: Why do we divide by sqrt(d_k) in scaled dot-product attention?

Without scaling, dot products grow with dimension d_k, since the variance of Q·K is d_k if Q and K have unit variance. For large d_k (e.g., 64), dot products become large in magnitude, pushing softmax into saturated regions where gradients are near zero, slowing learning. Dividing by sqrt(d_k) normalizes variance to 1, keeping softmax inputs in a range where gradients flow well. This is especially important early in training when weights are random.

Q2: How does multi-head attention differ from single-head attention, and why is it useful?

Single-head attention performs one attention function in the full d_model dimension. Multi-head attention projects Q, K, V h times into smaller subspaces (d_k = d_model/h), performs attention in each subspace independently, then concatenates and projects. This allows the model to capture different types of relationships simultaneously — e.g., one head may learn syntactic dependencies, another lexical similarity, another positional proximity. Empirically, 8-16 heads outperform a single head with the same total dimension, and the parallel heads provide ensemble-like robustness.

Q3: What is the purpose of positional encoding, and what happens if you remove it?

Self-attention is permutation-equivariant: without positional information, shuffling input tokens yields the same output shuffled. Positional encodings break this symmetry by injecting order information, either via fixed sinusoids or learned embeddings added to token embeddings. If removed, the model becomes a bag-of-words model, unable to distinguish "dog bites man" from "man bites dog," and performance collapses on any order-sensitive task. Recent alternatives like RoPE encode relative positions directly in the attention computation.

Q4: Explain the time and space complexity of self-attention and how you would handle a sequence of length 100,000.

Self-attention is O(n²·d) time and O(n²) space due to the n x n attention matrix. For n=100,000, this is infeasible (10 billion entries). Strategies include: sparse/local attention (attend only to window w, O(n·w)), linear attention approximations (Performer, Linformer, O(n·d)), FlashAttention for memory-efficient exact attention, hierarchical or retrieval-based approaches (process chunks and aggregate), and state-space models like Mamba that scale linearly. The choice depends on whether exact global attention is required or approximation is acceptable.

Q5: Why does the decoder use masked self-attention, and how is it implemented?

During autoregressive generation, the decoder must predict token t without seeing tokens > t, otherwise training would be cheating. Masked self-attention enforces this by setting attention scores for future positions to -infinity before softmax, so their weights become zero. Implementation uses a lower-triangular mask of shape (n x n) where mask[i,j] = 1 if j <= i else 0, added as masked_fill(scores, mask==0, -1e9). At inference time, KV-caching avoids recomputing past keys/values, making generation O(n·d) per step.