AI Interview Questions

The Transformer is a neural network architecture introduced in the 2017 paper "Attention Is All You Need" that processes sequential data using self-attention mechanisms instead of recurrent connections. Unlike RNNs and LSTMs that process tokens sequentially, Transformers process all tokens in parallel while using attention to dynamically model relationships between them. This fundamental shift from recurrence to attention revolutionized how neural networks handle sequential data.

The architecture consists of an encoder and decoder stack, each containing identical layers. Each encoder layer has two sublayers: multi-head self-attention and a position-wise feed-forward network, with residual connections and layer normalization around each. The decoder has three sublayers: masked self-attention (preventing attention to future positions), cross-attention over encoder outputs, and feed-forward network. Positional encodings are added to input embeddings to inject sequence order information, since self-attention is permutation-invariant. During training, masks prevent the decoder from attending to future tokens, ensuring autoregressive generation. The attention mechanism computes relevance scores between all pairs of positions, allowing the model to weigh information from different tokens based on context.

Transformers solved three critical limitations of RNNs/LSTMs. First, parallelization: RNNs process sequentially, making them slow to train on modern hardware as each step depends on previous hidden state. Transformers parallelize computation across sequence length, reducing training time from weeks to days and enabling scaling to massive datasets. Second, long-range dependencies: RNNs struggle with vanishing gradients, limiting effective context to ~200 tokens even with LSTM gating mechanisms. Transformers can directly attend to any token regardless of distance, with attention providing O(1) path length between any positions versus O(n) in RNNs. Third, scaling: Transformers exhibit more predictable scaling laws with data, compute, and parameters, enabling the development of large language models like GPT-4 (1.8T parameters), BERT, and Claude. This has democratized AI capabilities, making state-of-the-art NLP accessible.

Consider translating "The cat that chased the mouse that lived in the house that Jack built was tired" to French. An RNN must process each word sequentially, maintaining hidden state through 20+ words. By the time it reaches "was tired," the subject "cat" may be forgotten or degraded due to vanishing gradients. A Transformer's self-attention lets "was tired" directly attend to "cat" regardless of distance (20 positions apart), maintaining the subject-verb relationship correctly for accurate translation. This enables handling of complex nested structures that RNNs fundamentally struggle with.

Self-attention is a mechanism that allows each token in a sequence to compute a weighted representation of all other tokens, where weights represent the relevance or importance of each token to the current one. It enables the model to capture contextual relationships within the same sequence, creating context-aware representations where each token's meaning depends on its surrounding context. This is fundamentally different from earlier models where token representations were fixed regardless of context.

For each input token, the model computes three vectors through learned linear projections: Query (Q), Key (K), and Value (V). The Query asks "what am I looking for?", Key answers "what information do I contain?", and Value provides "the actual content to pass through". For a sequence of n tokens, we have matrices Q, K, V of shape (n, d_k) where d_k is the dimension per head. The attention scores between all tokens are computed as the dot product of Q and K^T, producing an (n, n) matrix where position (i,j) represents relevance of token j to token i. These scores are scaled by dividing by √d_k to prevent dot products from growing too large (variance of QK^T is approximately d_k). Softmax is applied row-wise to convert scores to probabilities summing to 1. Finally, the output for each token is the weighted sum of all Value vectors using these probabilities: Attention(Q,K,V) = softmax(QK^T/√d_k)V. Multi-head attention runs this process h times with different projections, concatenating results.

Self-attention gives Transformers their power to understand context in ways RNNs cannot. Unlike RNNs that compress entire history into a fixed-size hidden state (information bottleneck), self-attention provides direct access to any token's representation at any layer. This enables modeling of long-range dependencies spanning hundreds or thousands of tokens, coreference resolution (linking pronouns to nouns across paragraphs), capturing nuanced syntactic relationships like subject-verb agreement across clauses, and semantic similarity where words like "bank" disambiguate based on context. Self-attention is the foundation for contextual embeddings where each token's representation is a function of all tokens, enabling the rich understanding seen in modern LLMs. The attention patterns are also interpretable, allowing researchers to visualize what the model focuses on.

In the sentence "The bank refused the loan because it was busy," self-attention helps determine what "it" refers to. The token "it" computes Query based on its position and need for an antecedent. Keys from all tokens are compared: "bank" (financial institution, capable of being busy), "refused" (action, not an entity), "loan" (thing, cannot be busy). The attention mechanism computes higher scores between "it" and "bank" (0.7) than between "it" and "loan" (0.1) based on semantic compatibility learned during training. The Value from "bank" (its full representation) is weighted heavily in "it"'s output, allowing the model to correctly understand that the bank was busy, not the loan. This coreference resolution happens automatically through learned attention patterns.

Multi-head attention runs multiple self-attention operations in parallel, each with different learned linear projections, allowing the model to capture different types of relationships and patterns in the data simultaneously. The outputs from all heads are concatenated and projected to produce the final representation. This is analogous to having multiple experts analyzing the same text from different perspectives, then combining their insights.

Instead of computing attention once with d_model-dimensional Q, K, V, the model projects queries, keys, and values h times (typically 8-16 heads) with different learned linear transformations, reducing dimension to d_k = d_model/h per head. Each head performs independent scaled dot-product attention, producing output vectors of dimension d_k. These h outputs (each d_k-dimensional) are concatenated to restore d_model dimensions, then passed through a final linear projection W^O. Mathematically: MultiHead(Q,K,V) = Concat(head_1,...,head_h)W^O where head_i = Attention(QW_i^Q, KW_i^K, VW_i^V). Each head learns different projection matrices, enabling specialization. The number of heads is a hyperparameter, with more heads increasing model capacity and ability to capture diverse patterns, but also computational cost (each head adds parameters and operations).

Single-head attention averages out different types of relationships into one attention pattern, limiting expressiveness because a single distribution over tokens must serve multiple purposes. Multi-head attention provides several critical benefits: First, it allows the model to attend to information from different representation subspaces simultaneously, capturing both local syntax and long-range semantics in parallel. Second, different heads can specialize in different linguistic phenomena: one head might track subject-verb agreement, another captures coreference relationships, a third focuses on semantic roles, and a fourth attends to positional proximity. Third, it provides redundancy and robustness - if one head misses important information due to noisy patterns, others may capture it. Fourth, it increases model capacity without making the network deeper, enabling better performance on complex tasks while maintaining computational efficiency. Fifth, different heads often learn interpretable patterns, aiding model analysis and debugging.

In processing "The teacher who inspired generations of students retired yesterday," multiple attention heads work in parallel to build comprehensive understanding. Head 1 might focus on subject-verb agreement, computing high attention between "teacher" and "retired" across the relative clause. Head 2 captures the relative clause relationship, connecting "teacher" with "inspired" to understand who did what. Head 3 links "generations" with "students" based on semantic relatedness. Head 4 might track temporal aspects linking "retired" with "yesterday". Head 6 might handle determiner relationships. The concatenated output from all heads combines these perspectives into a rich, multi-faceted representation that single-head attention could not achieve, enabling the model to simultaneously understand syntax, semantics, and temporal relationships.

Positional encoding is a technique used in Transformers to inject information about the position of tokens in a sequence into the model's representations. Since the self-attention mechanism is permutation-invariant (it processes tokens as a set without inherent order), positional encodings provide the necessary sequential information for the model to understand word order and token positions. They are vectors added to token embeddings before they enter the first transformer layer.

The original Transformer used sinusoidal positional encodings with different frequencies to create unique patterns for each position. For position pos and dimension i, the encoding is: PE(pos,2i) = sin(pos/10000^(2i/d_model)) for even dimensions and PE(pos,2i+1) = cos(pos/10000^(2i/d_model)) for odd dimensions. This creates a continuous encoding where nearby positions have similar patterns, and the encoding can extrapolate to sequence lengths beyond training. The sinusoidal functions allow the model to easily learn to attend by relative position since PE(pos+k) can be represented as a linear function of PE(pos). Modern models often use learned positional embeddings instead, where each position up to maximum context length has a trainable vector. More recent approaches use relative position encodings (like in RoPE or ALiBi) that capture distances between tokens rather than absolute positions, which often generalizes better to longer sequences.

Without positional encoding, the Transformer would treat "dog bites man" and "man bites dog" identically, as both contain the same bag of words with the same embeddings. Position matters critically in language for syntax (subject-verb-object order), semantics ("almost won" vs "won almost"), and meaning ("the police shot the man" vs "the man shot the police"). Positional encodings enable the model to understand word order, distance between tokens, and sequential patterns essential for tasks like translation (where word order differs across languages), question answering (where proximity between question terms and answer span matters), and any language task where sequence order carries meaning. The choice of positional encoding affects how well models handle long sequences and extrapolate to unseen lengths. Sinusoidal encodings extrapolate better theoretically, while learned embeddings often perform better within training distribution but fail on longer sequences.

In the sentence "The cat sat on the mat and the dog slept," positional encoding helps the model establish a complete spatial and temporal understanding. The encoding tells the model that "cat" appears at position 2 (0-indexed with "The" at 0), "sat" at position 3, "mat" at position 6, "dog" at position 9, and "slept" at position 10. When processing "slept," the model can attend to "dog" knowing they're close in sequence (positions 9 and 10), while "cat" is farther away (position 2). This positional awareness is crucial for correctly understanding that the dog slept, not the cat, even though both nouns appear in the sentence. Additionally, the relative distance helps the model learn that subjects typically appear before their verbs in English, a pattern it can only learn with positional information.

These three architectures represent different ways of organizing transformer layers for different tasks. Encoder-only models stack only encoder layers with bidirectional attention, allowing each token to attend to all tokens for deep understanding. Decoder-only models stack only decoder layers with causal masking, where tokens attend only to previous positions for autoregressive generation. Encoder-decoder models combine both: an encoder processes input bidirectionally, and a decoder generates output with cross-attention to encoder representations for sequence transformation tasks.

Encoder-only models (like BERT) use bidirectional self-attention without masking, meaning each token can attend to all tokens left and right. They produce rich contextual embeddings where each token's representation incorporates full context. They're typically pretrained with masked language modeling (predicting masked tokens) and next sentence prediction. Decoder-only models (like GPT) use causal masking (upper triangular mask with -inf) ensuring token at position t can only attend to positions ≤ t. They're pretrained with autoregressive next-token prediction and generate sequentially during inference. Encoder-decoder models (like T5) have an encoder with bidirectional attention processing input, and a decoder with both self-attention (causal) and cross-attention to encoder outputs. Cross-attention lets decoder query encoder representations at each step, conditioning generation on input. They're pretrained with span corruption (masking spans of text) or denoising objectives.

Each architecture optimizes for different use cases, and choosing the right one impacts performance, efficiency, and capability. Encoder-only models excel at tasks requiring deep understanding of input: classification, sentiment analysis, named entity recognition, extractive QA, and generating embeddings for retrieval. They're efficient because they process input once and can be used for many downstream tasks. Decoder-only models shine in open-ended generation: chatbots, creative writing, code completion, and any task requiring fluent continuation. They've become dominant for general-purpose LLMs due to their flexibility and strong few-shot performance. Encoder-decoder models are ideal for transformation tasks where input and output differ structurally: translation, summarization, paraphrasing, and generative QA where answer isn't a span from input. They excel when output length or structure differs significantly from input.

For sentiment classification of a movie review, BERT (encoder-only) reads the entire review bidirectionally, builds comprehensive understanding, and uses the [CLS] token representation to classify as positive/negative efficiently. For a chatbot conversation, GPT-4 (decoder-only) generates responses autoregressively, with each new token depending on all previous conversation turns, enabling natural dialogue flow. For translating English "Hello, how are you?" to French "Bonjour, comment allez-vous?", T5 (encoder-decoder) encodes the English sentence once, then decodes French tokens one by one, with each French word attending to relevant English words via cross-attention, ensuring translation fidelity despite different sentence structures.

The scaled dot-product attention formula is the core mathematical operation in transformer attention mechanisms. It computes a weighted sum of values based on the compatibility between queries and keys, with scaling to maintain numerical stability. The formula is: Attention(Q,K,V) = softmax(QKᵀ/√d_k)V, where Q (queries), K (keys), and V (values) are matrices, and d_k is the dimension of the key vectors.

The computation proceeds in several steps. First, the dot product QKᵀ computes compatibility scores between every query (rows of Q) and every key (columns of Kᵀ), producing an n×n matrix where n is sequence length. Each element (i,j) represents how much token i should attend to token j. These scores are then divided by √d_k, where d_k is typically 64-128 per head. The scaling factor is applied element-wise to all scores. Next, softmax is applied row-wise, converting scores into a probability distribution over tokens for each position. Finally, these attention weights are multiplied by V to produce weighted sums, where each output token is a combination of all values weighted by attention probabilities.

Scaling by √d_k is crucial for stable training. Without scaling, for large d_k, the dot products QKᵀ grow large in magnitude because each dot product is a sum of d_k terms, and the variance of the sum is proportional to d_k (assuming unit variance inputs). These large values push the softmax function into regions of extremely small gradients, where most probabilities are near 0 or 1. When softmax saturates, gradients become vanishingly small, and the model stops learning effectively. Dividing by √d_k normalizes the variance to approximately 1, keeping the dot products in a reasonable range where softmax has meaningful gradients. This scaling enables stable gradient flow through attention layers, allowing training of deep transformers with many layers. The √d_k factor is theoretically derived from the variance of dot products assuming independent random variables with zero mean and unit variance.

Consider d_k=64 with unscaled attention. If queries and keys have unit variance, dot product variance is 64, so scores typically range from -24 to +24 (3 standard deviations). The softmax of [24, 0, 0] is essentially [1, 0, 0] with vanishing gradients for the zero positions. After scaling by √64=8, variance becomes 1, scores range from -3 to +3. Softmax of [3, 0, 0] becomes [0.95, 0.025, 0.025] with meaningful gradients of about 0.025 for the non-maximum positions. This allows the model to learn to adjust attention weights gradually rather than being stuck with nearly one-hot distributions that never change.

Residual connections (or skip connections) add the input of a sublayer to its output, following the pattern x + Sublayer(x). Layer normalization is a technique that normalizes activations across the feature dimension for each token independently, computing mean and variance and scaling to unit statistics with learnable parameters. Together, they form the backbone of transformer training stability.

In transformers, each sublayer (multi-head attention and feed-forward network) has a residual connection followed by layer normalization. The original "post-norm" architecture applied LayerNorm after the residual addition: LayerNorm(x + Sublayer(x)). Modern "pre-norm" architectures apply LayerNorm before the sublayer: x + Sublayer(LayerNorm(x)), which often trains more stably. Layer normalization computes statistics per token across features: μ = (1/d)∑x_i, σ² = (1/d)∑(x_i-μ)², then normalizes: (x-μ)/√(σ²+ε), followed by learnable scale γ and bias β. This ensures each token's representation has consistent statistics regardless of layer depth.

These components are critically important for training deep transformers. Residual connections solve the vanishing gradient problem by providing a direct gradient highway from output to input. In networks with hundreds of layers, gradients through non-linear transformations would vanish without residuals. The identity mapping ensures gradients can flow backward unchanged, enabling effective training of models with 100+ layers like GPT-3. Layer normalization addresses the internal covariate shift problem - as activations flow through layers, their distributions change, causing training instability. By normalizing each token's features, layer normalization ensures consistent activation magnitudes, preventing one layer's outputs from destabilizing subsequent layers. It also makes training less sensitive to learning rate and initialization. Together, these components enable transformers to scale to hundreds of layers and billions of parameters where earlier architectures would collapse.

In GPT-3 with 96 layers, consider gradient flow during backpropagation. Without residual connections, the gradient at layer 1 would be the product of 96 Jacobian matrices, each potentially <1 in norm, causing vanishing gradients. With residuals, each layer's gradient includes a direct identity term that doesn't shrink, ensuring early layers receive meaningful updates. Simultaneously, layer normalization keeps activations stable: after 96 layers of transformations, activations could explode or vanish without normalization, but layer norm maintains consistent scale. A concrete effect: training a 96-layer transformer with post-norm often diverges; with pre-norm and proper residuals, it trains stably, which is why all modern large models use this architecture.

The feed-forward network (FFN) is a per-token multi-layer perceptron applied independently to each position after the attention mechanism. It consists of two linear transformations with a non-linear activation function in between: FFN(x) = W₂·σ(W₁·x + b₁) + b₂. It processes each token's representation identically but independently, adding non-linear transformation capacity to the model.

The FFN operates on each token position separately, with the same learned weights applied to all positions (like a 1×1 convolution in CNNs). Typically, the hidden dimension is expanded by a factor of 4 (e.g., from 768 to 3072 in BERT-base, or from 12,288 to 49,152 in GPT-3). Common activation functions include GELU (Gaussian Error Linear Unit) in GPT models, ReLU in original Transformer, or SwiGLU in more recent models like LLaMA. After the activation, a second linear projection projects back to the original model dimension. The FFN is applied after layer normalization in pre-norm architectures, and its output is added to its input via residual connection: x = x + FFN(LayerNorm(x)).

The FFN is where much of the model's knowledge storage and complex pattern transformation happens. Attention mechanisms perform weighted averaging of token information - a linear operation in terms of values. Without non-linearities, stacking attention layers would still result in a linear transformation overall, severely limiting expressiveness. The FFN provides the essential non-linearity that allows the model to learn complex functions, pattern matching, and factual knowledge. Each FFN can be viewed as a key-value memory where the first layer projects to a high-dimensional space (like addressing memory), and the second layer projects back (like reading memory). Research suggests FFNs store substantial factual knowledge in their parameters. The expansion factor (typically 4×) creates a richer representation space where patterns can be more easily separated before projection back to model dimension.

After attention identifies that "Paris" is related to "capital" and "France" in the context "Paris is the capital of France," the FFN transforms that contextual representation to recall specific facts about Paris. The first linear layer might activate neurons corresponding to "European cities," "French landmarks," "population statistics." The activation function introduces non-linearity, allowing combinations like "European city" AND "capital" to activate different patterns than either alone. The second layer then projects to output representations containing specific facts: "Eiffel Tower," "population 2.1 million," "located on the Seine." This enables the model to answer follow-up questions like "What river is Paris on?" even though that information wasn't explicitly in the immediate context - the FFN stored it from training.

In decoder-only models, a causal mask (also called triangular mask) prevents tokens from attending to future tokens during training, ensuring the model learns proper autoregressive next-token prediction. The mask is applied to the attention scores before softmax, setting scores for future positions to negative infinity so they receive zero attention weight after softmax.

The causal mask is an upper-triangular matrix of shape (seq_len, seq_len) with 0s on and below the diagonal (allowed positions) and -∞ above the diagonal (masked positions). Before softmax, this mask is added to the scaled attention scores: masked_scores = (QKᵀ/√d_k) + mask. When softmax is applied, the -∞ values become effectively zero probability because exp(-∞) = 0. This ensures that at position t, attention can only look at positions ≤ t. During training, for each sequence, the model processes all positions in parallel but with this mask applied, so the prediction for token at position t+1 depends only on tokens 0..t. The loss is computed only on the predictions for actual tokens (excluding padding), typically using cross-entropy between predicted next-token distributions and actual tokens.

The causal mask is essential for autoregressive language modeling. Without it, the model could "cheat" by attending to future tokens during training, learning to simply copy the next token rather than predict it from context. This would result in a model that fails at generation, where future tokens aren't available. The mask ensures training matches inference conditions exactly: during generation, when producing token t+1, the model only has access to tokens 0..t. This consistency is crucial for the model to learn proper next-token prediction. The mask also enables efficient parallel training - despite the sequential nature of language, the transformer can process all positions simultaneously because the mask enforces the causal constraint mathematically rather than requiring sequential computation. This parallelization is what makes transformer training so efficient compared to RNNs.

Training on the sentence "The cat sat on the mat." With sequence length 7, we have tokens: [The, cat, sat, on, the, mat, .]. The causal mask for position 4 (token "the" before "mat") allows attending to positions 0-3: [The, cat, sat, on] but blocks position 5-6 ("mat", "."). When computing the loss for position 5 (predicting "mat"), the model uses only tokens 0-4. It cannot see that the actual next token is "mat" - it must predict it from context. This forces the model to learn that after "sat on the," "mat" is likely. During actual generation, when the model has generated "The cat sat on the," it will predict "mat" based on the same pattern learned during training.

Self-attention has queries, keys, and values all coming from the same sequence, allowing tokens to attend to other tokens within the same input to understand internal relationships. Cross-attention has queries coming from one sequence (typically decoder states) while keys and values come from another sequence (typically encoder outputs), allowing one sequence to attend to another to condition generation on input.

In self-attention, the Q, K, V projections all receive the same input sequence X, producing Q = XW_Q, K = XW_K, V = XW_V. The attention then computes relationships within X: each token attends to all tokens in X. In cross-attention, the queries come from one sequence (e.g., decoder hidden states Y), while keys and values come from another sequence (e.g., encoder outputs H): Q = YW_Q, K = HW_K, V = HW_V. The attention computes how each token in Y should attend to tokens in H, allowing information flow from H to Y. In encoder-decoder models, the encoder uses self-attention to understand input, the decoder uses masked self-attention on generated tokens, and cross-attention between decoder and encoder to incorporate input information during generation.

Self-attention builds rich, context-aware representations of a single sequence, capturing internal dependencies like syntax, coreference, and semantic relationships. It's the foundation for understanding tasks. Cross-attention enables conditional generation where the output must be grounded in input, essential for tasks where output depends on external information. In translation, cross-attention lets each French word attend to relevant English words. In summarization, it lets summary sentences attend to important parts of source document. In question answering, it lets answer generation attend to retrieved context. Without cross-attention, decoder-only models must include all input in the context window, which is less efficient for long documents and doesn't provide the same focused attention mechanism.

In an English-to-French translation task, self-attention in the encoder processes the English sentence "The cat sat on the mat," building representations where each English word understands its context. In the decoder, self-attention processes the partially generated French translation "Le chat s'est assis sur" ensuring fluency and grammatical agreement within French. Then cross-attention lets each French token query the English encoder representations: when generating "assis" (sat), cross-attention computes high weights with the English token "sat" to ensure correct verb translation; when generating "chat," it attends heavily to "cat"; when generating "tapis" (mat), it attends to "mat." This selective attention to relevant input tokens ensures translation accuracy while maintaining target language fluency.

In the attention mechanism, Query (Q) represents what a token is looking for, Key (K) represents what information a token offers or how it can be matched, and Value (V) represents the actual content that will be passed through if the token is selected. This is analogous to a retrieval system where Query searches against Keys to retrieve relevant Values.

Each token in the input sequence is projected into three different vector spaces via learned weight matrices: Q = xW_Q, K = xW_K, V = xW_V. The Query from token i is compared with Keys from all tokens via dot product, producing similarity scores. These scores determine how much of each token's Value should be mixed into token i's output. Mathematically, for token i, output = Σ_j (softmax_j(Q_i·K_j/√d)) V_j. The projection matrices are learned during training to produce Q, K, V spaces that optimize this retrieval for the model's objectives. The dimensions of these spaces (d_k, d_v) are hyperparameters, typically with d_k = d_v = d_model/h for multi-head attention.

This separation of concerns into Q, K, V is what makes attention so powerful and flexible. The Query encodes what information the current token needs - this could be syntactic (looking for a subject if token is a verb), semantic (looking for related concepts), or positional (looking for nearby tokens). The Key encodes what information each token can provide - its role, category, and relevance to different types of queries. The Value carries the actual content that will be passed forward. This decomposition allows the model to learn sophisticated information retrieval patterns: a token can have a Key that says "I'm relevant to verb queries" while its Value carries its actual meaning. The same token can be retrieved for multiple purposes by different Queries. This flexibility enables the rich contextual understanding seen in modern LLMs.

In the sentence "The cat chased the mouse," consider the token "chased" (a verb). Its Query might be structured to look for agents (who performs the action) and patients (who receives the action). The token "cat" has a Key that signals "I'm a noun, animate, could be an agent" and a Value containing "cat" identity. The token "mouse" has a Key signaling "I'm a noun, animate, could be a patient" and Value containing "mouse." When "chased" computes attention, its Query dot product with "cat" Key is high (matching agent-seeking pattern), and with "mouse" Key is also high (matching patient-seeking pattern). Their Values are then weighted and combined, allowing "chased" to understand both who chased and who was chased, producing a representation that encodes the full action.

Standard self-attention has O(n²) time and memory complexity with respect to sequence length n, where n is the number of tokens. This quadratic scaling is the primary computational bottleneck for processing long sequences with transformers, as both the number of operations and memory required grow with the square of sequence length.

For a sequence of length n with hidden dimension d, self-attention computes an n×n attention matrix representing relationships between every pair of tokens. Computing QKᵀ requires O(n²·d) operations (matrix multiplication of n×d with d×n). Storing the attention scores requires O(n²) memory. The subsequent softmax and weighted sum with values also require O(n²) operations. With multi-head attention having h heads, this is repeated h times, but heads operate on dimension d/h, so total complexity remains O(n²·d). The quadratic term n² dominates for long sequences because d is constant (typically 512-4096) while n can grow to hundreds of thousands.

Quadratic complexity fundamentally limits how long of a context transformers can process. A 1,000-token sequence requires 1 million attention computations (manageable). A 100,000-token sequence requires 10 billion computations - 10,000× more. This 10,000× increase in compute and memory makes long contexts prohibitively expensive on current hardware. For example, processing a 1M token book would require 1 trillion attention operations - infeasible for practical applications. This limitation drives research into efficient attention variants: sparse attention (attending to subsets), linear attention (approximating attention with O(n) complexity), recurrent memory mechanisms, and better hardware utilization. Understanding this complexity is crucial for practitioners designing systems for long documents, multi-turn conversations, or any application requiring extensive context.

Consider processing a 300-page book with 300,000 tokens. Full self-attention would require 90 billion attention pairs (300k²). If each attention operation takes 1 nanosecond (optimistic), this would be 90 seconds just for attention in one layer. With 32 layers, that's 48 minutes per forward pass - impossible for practical use. Even with modern GPUs, 100k tokens push the limits of available memory (100k² = 10B floats = 40GB just for attention scores). This explains why models like GPT-4 with 128k context are remarkable achievements requiring significant optimization like sparse attention patterns and FlashAttention.

Transformers handle variable-length inputs primarily through padding and attention masking. During training and inference, sequences of different lengths are padded to a common maximum length within a batch, and attention masks ensure that padded positions do not affect the computation or loss. This allows efficient batch processing while maintaining correctness for individual sequences.

During batching, all sequences in a batch are padded with special [PAD] tokens to match the length of the longest sequence in that batch. Two types of masks are typically used: padding masks and attention masks. Padding masks (usually binary) indicate which positions are real tokens vs. padding. These masks are applied in two ways: first, they're added to attention scores (with -inf for padding) to prevent tokens from attending to padding positions; second, they're used in loss calculation to ignore loss contributions from padding tokens. For decoder-only models, a causal mask is combined with the padding mask. During inference with a single sequence, no padding is needed - the model processes whatever length is provided, up to its maximum context window. The key insight is that transformer computations are identical for each token position; masking simply prevents certain positions from influencing others.

Real-world data has inherently variable lengths - user queries range from 3 to 300 words, documents from paragraphs to books, conversations from 2 to 100 turns. Efficient handling of this variability is crucial for practical deployment. Batching with padding enables parallel processing of different-length sequences, dramatically improving throughput compared to processing each sequence individually. Without efficient padding and masking, GPU utilization would be poor because short sequences would waste compute. The choice of padding strategy affects both efficiency and correctness: dynamic batching (grouping similar-length sequences) minimizes wasted padding tokens. Attention masking ensures that despite variable lengths within a batch, the mathematical correctness of each sequence's processing is preserved - no token ever incorrectly attends to padding from another sequence.

A batch contains three sequences: "Hello" (2 tokens after tokenization), "How are you?" (5 tokens), and "I'm doing well, thank you for asking" (10 tokens). All are padded to length 10 with [PAD] tokens. When computing attention for the first token in the first sequence, the attention mask ensures it can attend to token 2 (real) but not tokens 3-10 (padding). The loss for positions 3-10 in the first sequence is masked out, so the model isn't penalized for incorrectly predicting padding tokens. This allows the GPU to process all three sequences in parallel, achieving ~3x throughput compared to sequential processing, while maintaining training correctness.

FlashAttention is an optimized attention algorithm that reduces memory usage and improves speed by avoiding materialization of the large attention matrix. It uses tiling to compute attention in smaller blocks on fast SRAM, fusing multiple operations together rather than writing intermediate matrices to slower HBM (High Bandwidth Memory).

Standard attention computes S = QKᵀ (n×n matrix), writes to HBM, reads it back for softmax, writes P = softmax(S) to HBM, reads it back for P·V - requiring O(n²) HBM access and storage. FlashAttention processes attention in blocks: it loads blocks of Q, K, V from HBM to fast SRAM, computes attention for that block, updates output incrementally, and writes back only the final result. It uses techniques like recomputation to avoid storing intermediates, and kernel fusion to combine operations. For backward pass, it recomputes attention matrices on the fly rather than storing them. This reduces HBM reads/writes from O(n² + n·d) to O(n²·d / M) where M is SRAM size, achieving 2-4× speedup and significantly reducing memory footprint.

Standard attention's memory bottleneck limits practical sequence lengths. For a 64k sequence with 64-head attention, storing attention scores alone requires 64k² × 2 bytes × 64 ≈ 524GB - impossible. FlashAttention reduces memory from O(n²) to O(n), enabling processing of much longer sequences under same hardware constraints. This has several critical implications: 1) Enables training with 128k-1M context windows that were previously infeasible. 2) Allows larger batch sizes for same sequence length, improving training efficiency. 3) Makes attention compute-bound rather than memory-bound, better utilizing GPU compute capacity. 4) Democratizes long-context research by making it accessible on fewer GPUs. FlashAttention-2 further improves efficiency with better parallelism and work partitioning.

Training a model with 128k context length. Standard attention would require storing 128k² = 16.4B floats per head per layer. With 32 heads and 32 layers, that's 16.8TB just for attention scores - impossible on any current hardware. FlashAttention processes this by tiling: with 128KB SRAM, it processes attention in blocks of ~256 tokens, never materializing the full matrix. The same 128k sequence fits in memory on a single A100 GPU, enabling training that was previously impossible. This is why models like GPT-4 with 128k context and Claude with 200k context are now possible - FlashAttention and similar optimizations made them feasible.

Softmax is a mathematical function that converts raw attention scores (logits) into a probability distribution over tokens. It ensures that attention weights are non-negative and sum to 1, making the attention mechanism a proper weighted average of value vectors. The function is defined as softmax(z_i) = exp(z_i) / Σⱼ exp(z_j) for vector z.

After computing scaled dot products between queries and keys, we have raw scores s_ij for each pair of positions. These scores can be any real number - positive or negative, large or small. Softmax transforms each row of this score matrix independently: first, it exponentiates each score, making all values positive and amplifying differences (a score of 2 gets exp(2)=7.4, while 1 gets exp(1)=2.7). Then it normalizes by dividing by the sum of exponentials in that row, ensuring all weights sum to 1. The resulting attention weights w_ij are between 0 and 1 and represent the proportion of token j's value that should be included in token i's output. The temperature parameter can adjust the sharpness of the distribution by scaling scores before softmax.

Softmax is essential for several reasons. First, it ensures attention produces a convex combination of values - the output is always within the convex hull of the input values, providing stability. Second, the exponential creates competition between tokens - small differences in raw scores are amplified, encouraging the model to make crisp decisions about which tokens are most relevant. Third, the normalization makes the total attention budget fixed (sums to 1), forcing tokens to compete for influence. Fourth, the resulting probabilities are interpretable as "how much attention" each token receives. Fifth, softmax with its exponential is differentiable, enabling gradient-based learning. Without softmax, raw scores could produce arbitrary weighted sums with negative weights, leading to instability and outputs outside reasonable ranges. The softmax attention mechanism is what allows models to selectively focus on relevant information while ignoring irrelevant tokens.

After computing raw scores for a token, we might have [2.0, 1.0, 0.1, -0.5] relative to four other tokens. Softmax computes exponentials: [7.39, 2.72, 1.11, 0.61], sum = 11.83. Normalized weights: [0.62, 0.23, 0.09, 0.05]. The first token gets 62% of the value contribution, the second 23%, etc. This creates a clear focus on the most relevant token while still incorporating some information from others. If we had used raw scores directly (without softmax) as weights, the output could be arbitrarily scaled and potentially dominated by negative weights causing instability.

Autoregressive generation is the process where a transformer produces text one token at a time, with each new token conditioned on all previously generated tokens. The model computes a probability distribution over the vocabulary for the next token, selects one based on a decoding strategy, appends it to the context, and repeats until a stopping condition is met.

Generation begins with a prompt (user input) tokenized into a sequence of tokens. The model performs a forward pass through all layers, computing hidden states for each position. At the final layer, a language modeling head (typically a linear layer with softmax) produces a probability distribution over the entire vocabulary for the next token position. A decoding strategy then selects a token from this distribution: greedy decoding picks the highest probability token, sampling picks randomly according to probabilities (optionally with temperature scaling), top-k samples from the k most likely tokens, and beam search maintains multiple candidate sequences. The selected token is appended to the context. Crucially, the model caches key and value vectors (KV cache) from previous tokens, so for subsequent steps it only computes attention for the new token while reusing cached K,V from earlier tokens, dramatically speeding up generation. This process repeats until the model generates an end-of-sequence token or reaches a maximum length limit.

Autoregressive generation is how all modern chat models, code completers, and writing assistants work. Understanding it is essential for controlling output quality, latency, and cost. The decoding strategy choices dramatically affect results: greedy decoding is fast but can lead to repetitive or dull text; sampling with temperature creates diversity but risks incoherence; beam search improves quality for tasks like translation but is slower. The KV cache is critical for acceptable latency - without it, generating 1000 tokens would require 1000 full forward passes over the entire sequence, each O(n²) in current length, which is prohibitively slow. With KV cache, each new token is O(n) in current length (only attention for new token), making generation practical. The sequential nature creates inherent latency-quality tradeoffs that system designers must navigate.

Generating a response to "What is the capital of France?" Step 1: Model processes prompt, computes distribution: P(Paris)=0.7, P(Lyon)=0.2, P(Marseille)=0.1. Greedy picks "Paris". KV cache stores all K,V from this forward pass. Step 2: Context is now "What is the capital of France? Paris". Model computes only new token's attention using cached K,V, distribution: P(is)=0.9, P(was)=0.05, P(,)=0.03. Greedy picks "is". Continue until model generates "." or max length. Total time: 1 full forward pass for prompt + N incremental passes for N generated tokens, enabled by KV cache.

Scaling transformer models faces multiple interconnected bottlenecks across compute, memory, communication, and data that limit how large models can grow and how efficiently they can be trained. These constraints arise from fundamental hardware limitations and algorithmic scaling properties.

The primary bottlenecks include: 1) Attention O(n²) complexity: As sequence length increases, attention computation and memory grow quadratically, eventually dominating all other costs. 2) Memory for parameters: Model weights themselves require significant memory - a 175B parameter model in FP16 requires 350GB just for weights, plus optimizer states (another 700GB for Adam), and gradients (350GB), totaling ~1.4TB per replica. 3) Activation memory: Intermediate activations during forward pass must be stored for backward pass, scaling with batch size × sequence length × layers. 4) Communication bandwidth: In distributed training, gradients must be synchronized across GPUs via all-reduce operations, with bandwidth becoming bottleneck as model size increases. 5) Data pipeline: Training data must be processed and fed to GPUs faster than they can consume it, requiring efficient data loading and preprocessing. 6) IO and checkpointing: Saving and loading large model checkpoints can take hours.

Understanding these bottlenecks guides architecture decisions, hardware selection, and optimization strategies. Different bottlenecks dominate at different scales: at small scales, compute may be limiting; at medium scales, memory becomes critical; at large scales, communication and data pipeline dominate. This understanding has driven innovations like FlashAttention (addressing attention memory), ZeRO/FSDP (addressing parameter memory), tensor/pipeline parallelism (addressing compute distribution), and gradient checkpointing (addressing activation memory). Scaling laws research shows optimal model size depends on compute budget, but practical deployment is constrained by these bottlenecks regardless of theoretical optimality. For practitioners, these bottlenecks determine what's possible with available hardware and guide optimization priorities.

Training GPT-3 175B: Parameters 350GB in FP16. With Adam optimizer (2 states per parameter), total optimizer state = 700GB. Gradients = 350GB. Total memory per GPU if using data parallelism = 1.4TB - impossible on any GPU. Solution: Use model parallelism (sharding parameters across GPUs) and ZeRO-3 (sharding optimizer states and gradients). With 1000 A100 GPUs (80GB each), parameters sharded to 350MB per GPU, making training possible. Communication becomes bottleneck: all-reduce for 175B gradients across 1000 GPUs requires moving 175GB per iteration, limiting training speed. This is why infrastructure engineering is as important as model architecture for large-scale training.

Pre-norm and post-norm refer to the placement of layer normalization relative to the sublayers (attention and FFN) in transformer blocks. Post-norm, used in the original Transformer, applies normalization after the residual addition. Pre-norm, common in modern large models, applies normalization before the sublayer while keeping the residual connection clean.

Post-norm architecture: x = LayerNorm(x + Sublayer(x)). Each sublayer output is added to its input, then normalized. Pre-norm architecture: x = x + Sublayer(LayerNorm(x)). The input is normalized, then passed through the sublayer, and the result is added to the original unnormalized input. In pre-norm, the residual path remains untouched by normalization, maintaining a clean identity mapping throughout the network. Both architectures typically use multiple blocks stacked sequentially, with final layer normalization after all blocks in pre-norm variants. The choice affects gradient flow and training dynamics significantly.

This seemingly minor architectural difference has major implications for training stability and model depth. Post-norm can be unstable for very deep transformers because gradients must flow through layer normalization on the residual path, which can cause gradient vanishing or explosion. Pre-norm stabilizes training by keeping the residual path clean, allowing gradients to flow directly through the network unchanged. This enables training of much deeper models (hundreds of layers) without special initialization or careful tuning. Pre-norm is now standard in large models like GPT-3, LLaMA, and most modern architectures. However, post-norm can sometimes achieve slightly better performance at moderate depths, and some research suggests post-norm with careful initialization can work well. The difference highlights how architecture details matter for scalability.

Training a 100-layer transformer with post-norm: Gradients at layer 1 are the product of 100 gradients through normalization layers. Each normalization introduces scaling that can shrink gradients if mean activations are large. Without careful initialization and tuning, gradients vanish, and early layers don't learn. With pre-norm: Residual paths provide direct gradient highways from output to input. Gradients at layer 1 include a term from the identity path that's unaffected by depth, ensuring early layers receive updates even in 100-layer networks. This is why GPT-3 (96 layers) and LLaMA (up to 80 layers) use pre-norm - it simply works at extreme depths where post-norm would fail.

Sparse attention restricts each token to attend to only a subset of tokens using predefined patterns, reducing computational and memory complexity from O(n²) to O(n·k) where k is the fixed number of tokens each position attends to. Various patterns balance coverage and efficiency for different tasks.

Instead of computing full n×n attention matrix, sparse attention defines for each position a fixed set of positions it can attend to. Common patterns include: 1) Local window attention: each token attends to w tokens on each side (total 2w+1). 2) Strided patterns: attend to every s tokens for long-range coverage. 3) Global tokens: a few tokens (like [CLS]) attend to all and are attended by all. 4) Block-sparse: divide sequence into blocks, attend within and between blocks in patterns. 5) Dilated attention: attend to tokens at increasing intervals. These patterns can be combined (e.g., local + global) for better coverage. Computation is implemented by masking the attention matrix to zero out disallowed connections, then using block-sparse matrix multiplication kernels for efficiency.

Sparse attention enables processing sequences much longer than full attention would allow. With 64k sequence length, full attention requires 4B operations per head, while local window of 256 requires only 16M - 250× reduction. This makes tasks like book processing, long video understanding, and genomic sequence analysis feasible. Different patterns suit different data types: local window works well for text where nearby tokens matter most, strided patterns capture long-range dependencies, global tokens provide overview. The trade-off is potentially missing some important long-range dependencies if patterns aren't designed appropriately. Models like Longformer, BigBird, and Sparse Transformer use these techniques to handle sequences of 100k+ tokens. Research continues on learnable sparse patterns that adapt to data.

Processing a 100,000-token book with local window attention (window=256). Full attention: 10B operations. Local attention: each token attends to 256 neighbors (128 each side), total 25.6M operations - 390× reduction. Memory similarly reduced from 40GB to 100MB per head. To capture long-range dependencies across chapters, add global tokens at chapter boundaries that attend to all tokens and are attended by all, ensuring information can flow across the entire book. This hybrid approach makes book-length context practical while maintaining reasonable compute.

A transformer is like a brilliant reader that can look at all words in a text simultaneously and instantly understand how they relate, rather than reading word-by-word like older AI models. It's the technology behind modern AI assistants like ChatGPT, Claude, and Gemini.

Imagine you're reading a complex sentence: 'The cat that chased the mouse that lived in the house was tired.' A transformer processes this by drawing mental connections between words - it connects 'cat' to 'was tired' even though they're far apart, links 'chased' to 'mouse' to understand the action, and keeps track of all these relationships simultaneously. It does this using something called 'attention' - basically deciding which words are most important to each other. The transformer learns these connection patterns by reading massive amounts of text (billions of pages) and adjusting its internal understanding until it can predict words accurately.

Before transformers, AI read text sequentially like humans, which was slow and limited - they'd often forget the beginning of a paragraph by the time they reached the end. Transformers revolutionized AI because they can handle much longer contexts (like entire book chapters), understand complex relationships, and learn much faster by processing all words at once. This is why today's AI can write essays, answer follow-up questions remembering what you said earlier, translate languages accurately, and even write computer code. They're the reason AI suddenly became much more capable around 2018-2020.

When you ask ChatGPT a question like 'What were the main causes of World War I and how did they compare to World War II?', the transformer reads your entire question at once, identifies key concepts ('World War I', 'causes', 'World War II', 'compare'), draws connections between them, and constructs an answer word-by-word while remembering everything it just said. It's like having an assistant who reads your entire email before responding, remembers every detail of the conversation, and can reference things you mentioned hours ago. This parallel understanding and generation capability is what makes modern AI feel so natural and intelligent.