Transformers and Attention Questions

Scaled dot-product attention computes weighted sums of value vectors V using similarity between queries Q and keys K. Algorithmically and mathematically:

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

Where Q ∈ R^{L×d_k}, K ∈ R^{L×d_k}, V ∈ R^{L×d_v} (L = sequence length). Entry (i,j) of QK^T is the dot product between query i and key j; dividing by sqrt(d_k) stabilizes gradients by keeping logits at a scale ~O(1) instead of O(d_k) (preventing softmax from saturating when d_k is large).

Complexities (single-head):

• Compute QK^T: O(L^2 d_k) time, O(L^2) intermediate memory for the score matrix.
• Multiply softmax scores by V: O(L^2 d_v) time.
  If d_k ≈ d_v ≈ d and using embedding dim d, total time O(L^2 d) and memory O(L^2) (plus O(L d) for Q,K,V storage).

Multi-head attention:
Split embedding into h heads: for head i, project input X by learned W_i^Q, W_i^K, W_i^V to d_k=d/h dims, compute Attention, then concat heads and final linear projection. Mathematically:

head_i = Attention(Q W_i^Q, K W_i^K, V W_i^V)
MultiHead(Q,K,V) = Concat(head_1,...,head_h) W^O

Why multiple heads help:

• Each head attends to different subspaces or relation types (positional patterns, local vs. global dependencies).
• With d_k = d/h, scaling keeps per-head computations efficient while total model capacity (through distinct projections) increases.
• Empirically improves representational richness and allows parallel, diverse attention patterns rather than a single averaged attention.

Trade-offs:

• More heads → more parameters and O(L^2) memory still dominates, so long sequences require sparse/approximate attention variants for scalability.

The transformer encoder processes a sequence in parallel using stacked layers; each layer has multi‑head self‑attention followed by a positionwise feedforward network, with residual connections and layer normalization around each sublayer.

Multi‑head self‑attention: project inputs X into queries Q, keys K, values V via learned linear maps. Each head computes scaled dot‑product attention:
Attention(Q,K,V) = softmax((Q K^T) / sqrt(d_k)) V.
Multiple heads (different projections) let the model attend to different relations; outputs are concatenated and linearly projected.

Scaled dot‑product: dividing by sqrt(d_k) stabilizes gradients when dot products grow with dimension.

Positional encodings: because attention is permutation‑invariant, add position information — either fixed sinusoidal encodings (sin/cos of different frequencies) or learned embeddings — to inputs so the model can use order and relative/absolute position.

Residual connections + layer normalization: after each sublayer, add a skip connection (x + Sublayer(x)) then apply LayerNorm. Residuals ease gradient flow for deep stacks; LayerNorm stabilizes training and speeds convergence.

Complexity: computing QK^T is O(n^2 d) time and O(n^2) memory (n = sequence length, d = dim). For long sequences (e.g., > 4k tokens) this becomes a bottleneck: high GPU memory, slower training/inference, and quadratic runtime. Practical implications: limit sequence length, use sparse/approximate attention (local, windowed, Performer, Longformer, Linformer), gradient checkpointing, or hierarchical models.

When prefer Transformers over RNNs/CNNs:

• Long-range dependencies: self‑attention models capture global context in few layers, unlike RNNs that need many steps.
• Parallelism and training speed: Transformers process tokens in parallel enabling faster GPU utilization and larger batch training.
• Flexibility: pretraining (BERT/GPT) and transfer learning excel with Transformers.
  Use RNNs/CNNs when sequences are short, latency/memory constrained, or when inductive biases like locality/translation equivariance are crucial and data is limited.

We can implement the Transformer sinusoidal positional encoding as described in Vaswani et al.: for position pos and dimension i,
PE[pos, 2k] = sin(pos / 10000^(2k/d_model))
PE[pos, 2k+1] = cos(pos / 10000^(2k/d_model))

Approach: build a (seq_len, d_model) matrix by computing a position vector and a dimension-frequency vector, then apply sin to even dims and cos to odd dims.

import numpy as np

def positional_encoding(seq_len, d_model):
    """
    Returns a (seq_len, d_model) numpy array of sinusoidal positional encodings.
    Even indices use sin, odd indices use cos with frequencies 10000^(2i/d_model).
    """
    positions = np.arange(seq_len)[:, np.newaxis]               # (seq_len, 1)
    dims = np.arange(d_model)[np.newaxis, :]                    # (1, d_model)
    # compute the angle rates: pos / (10000^(2i/d_model))
    angle_rates = 1 / (10000 ** ((2 * (dims // 2)) / d_model))  # (1, d_model)
    angles = positions * angle_rates                            # (seq_len, d_model)

    pe = np.empty_like(angles)
    pe[:, 0::2] = np.sin(angles[:, 0::2])   # even dims
    pe[:, 1::2] = np.cos(angles[:, 1::2])   # odd dims
    return pe

# Short example: add to token embeddings
seq_len, d_model = 5, 8
embeddings = np.random.randn(seq_len, d_model)  # example token embeddings
pe = positional_encoding(seq_len, d_model)
emb_plus_pe = embeddings + pe

Key points:

• Vectorized: avoids Python loops for performance.
• Works for any seq_len and d_model (d_model can be odd; the code handles floor division).
  Time complexity: O(seq_len * d_model) and same space.
  Edge cases: d_model=0 or seq_len=0 should return empty arrays; very large d_model may cause extremely small angle_rates (floating precision).
  Alternative: precompute pe up to a max length and slice for variable seq lengths (common in training).

Approach: compute scores = Q @ K^T / sqrt(d_k), apply optional mask (set masked positions to large negative), compute numerically stable softmax over key dimension, then output = softmax @ V. Return output and attention matrix.

import numpy as np

def scaled_dot_product_attention(Q, K, V, mask=None, eps=1e-9):
    """
    Q, K, V: arrays of shape (batch, seq_len, d_k)
    mask: None or array broadcastable to (batch, seq_len, seq_len)
          mask==0 or False indicates positions to mask (e.g., padding/causal)
          mask==1 or True indicates allowed positions
    Returns:
      output: (batch, seq_len, d_k)
      attn: (batch, seq_len, seq_len) -- attention weights (rows sum to 1)
    """
    batch, seq_len, d_k = Q.shape
    # compute raw scores: (batch, seq_q, seq_k)
    scores = np.matmul(Q, K.transpose(0, 2, 1)) / np.sqrt(d_k)

    if mask is not None:
        # convert mask to boolean where True means keep
        bool_mask = np.asarray(mask).astype(bool)
        # broadcast to (batch, seq_len, seq_len) if needed
        if bool_mask.ndim == 2:
            bool_mask = np.expand_dims(bool_mask, 0)
        # Where mask is False, set scores to large negative so softmax -> 0
        scores = np.where(bool_mask, scores, -1e9)

    # Numerically stable softmax along last axis (keys)
    # subtract max for stability
    max_scores = np.max(scores, axis=-1, keepdims=True)
    exp_scores = np.exp(scores - max_scores)
    sum_exp = np.sum(exp_scores, axis=-1, keepdims=True) + eps
    attn = exp_scores / sum_exp  # shape (batch, seq_q, seq_k)

    # weighted sum of values
    output = np.matmul(attn, V)  # (batch, seq_q, d_k)

    return output, attn

Key points:

• Uses sqrt(d_k) scaling to keep gradients stable.
• Masking sets logits to a large negative value before softmax so masked positions get ~0 probability.
• Softmax is stabilized by subtracting the max per row and adding eps to denominator.
  Time complexity: O(batch * seq_len^2 * d_k). Space: O(batch * seq_len^2) for scores/attn.
  Edge cases: ensure mask shape/broadcastability; handle all-equal scores (eps avoids div-by-zero). Alternative: use log-sum-exp for further numeric rigor.

Self-attention lets a transformer decide which tokens in a sequence should influence each other most. Instead of reading text strictly left to right, it builds relationships across the whole input, so the model can connect "it" to the correct noun or compare information from distant parts of a document.

The intuition is simple: each token looks at the others and assigns weights based on relevance.

Transformers became dominant because they:

• Handle long-range dependencies better than older RNNs
• Train efficiently in parallel on modern hardware
• Scale well with more data and parameters
• Work across many tasks, from classification to generation

For data science, that architecture is powerful because it supports summarization, extraction, search, and code generation with the same core design.