Overview

In real-world sequence modeling, we rarely have the luxury of fixed-length inputs. Sentences vary in length, audio clips differ in duration, and time series have irregular spans. This note explores the core techniques for handling variable-length sequences in neural networks.

Core Approaches

1. Padding & Masking

Why we need it: Modern deep learning frameworks process data in batches for efficiency. A batch tensor must be rectangular—all sequences need the same length dimension.

Derivation of masked loss: Let's say we have sequences of true lengths $\{L_1, L_2, .., L_B\}$ in a batch, paded to max length $L_{max}$.

For sequence $i$, define a mask: $m_i(t) = \begin{cases} 1 & \text{if } t \leq L_i \\ 0 & \text{if } t > L_i \end{cases}$

Why this mask? We want to ignore padding positions in our loss computation. The mask is 1 for real tokens, 0 for padding.

The masked loss for sequence $i$ becomes: $\mathcal{L}_i = \frac{1}{\sum_{t=1}^{L_{max}} m_i(t)} \sum_{t=1}^{L_{max}} m_i(t) \cdot \ell(y_i(t), \hat{y}_i(t))$

Why divide by the sum of masks? This normalizes by the actual sequence length $L_i$, not the padded length. Without this, shorter sequences would have artificially lower losses simply because they have more zero-weighted terms.

For the full batch: $\mathcal{L}_{batch} = \frac{1}{B} \sum_{i=1}^{B} \mathcal{L}_i$

Paded batch (max_len=4, pad_token=0):

[[1, 5, 7, 0],
 [2, 8, 3, 9],
 [4, 0, 0, 0]]

Mask matrix:

[[1, 1, 0],
 [1, 1, 1, 1],
 [1, 0, 0]]

Why this step? When computing loss or attention scores, we multiply by the mask to zero out the padding positions. For example, if the model predicts class probabilities for each position, we only compute cross-entropy loss where mask=1.

2. Packing & Unpacking (PyTorch)

Why packing? While padding is necessary for batching, RNNs don't need to waste computation on padding tokens. PyTorch's pack_padded_sequence removes padding for efficient RNN computation, then pad_packed_sequence restores the paded format for subsequent layers.

How it works under the hood:

Given paded sequences sorted by length (descending):

Lengths: [4, 3, 1]
Paded:
t=0: [a₀, b₀, c₀]
t=1: [a₁, b₁, 0 ]
t=2: [a₂, b₂, 0 ]
t=3: [a₃, 0,  0 ]

Packed representation concatenates all real tokens:

data: [a₀, b₀, c₀, a₁, b₁, a₂, b₂, a₃]
batch_sizes: [3, 2 1]

Why this ordering? At time step $t$, batch_sizes[t] tells us how many sequences are still "alive" (haven't ended yet). The RNN processes batch_sizes[t] elements at step $t$.

Paded input (batch_size=3, seq_len=5, embed_dim=10)

paded = torch.randn(3, 5, 10) lengths = torch.tensor([5, 3, 2])

Pack

packed = pack_padded_sequence(padded, lengths, batch_first=True)

packed.data.shape: (10, 10) ← 5+3+2=10 real elements

packed.batch_sizes: [3, 2, 1, 1, 1]

**Why `batch_sizes=[3,2,1,1,1]`?**
- t=0: All 3 sequences active
- t=1: 2 sequences active (one ended after length 2)
- t=2-4: 1 sequence active (one ended after length 3)

This lets the RNN dynamically adjust batch size per time step—massive speedup!

---

### 3. Dynamic Unrolling

> [!definition] Dynamic RNN Unrolling
> Instead of unrolling a fixed number of steps, use ==dynamic control flow== (loops) to process each sequence to its actual length.

**Mathematical formulation:**

For a batch of sequences, we process:
$$h_i(t) = \text{RNN}(x_i(t), h_i(t-1)) \quad \text{for } t = 1, 2, .., L_i$$

where $L_i$ is the true length of sequence $i$, not a fixed $L_{max}$.

**Why this works:** Modern frameworks (TensorFlow's dynamic_rnn, PyTorch's native RNN with packed sequences) compile these dynamic loops efficiently.

> [!formula] Hidden State Update (Concrete Example)
> For a simple RNN:
> $$h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b_h)$$

**Derivation from first principles:**
- **What are we computing?** A new hidden state that depends on current input and previous state
- **Why tanh?** Squashes values to [-1, 1], preventing exploding activations
- **Why two weight matrices?** $W_{xh}$ transforms input dimension to hidden dimension; $W_{hh}$ transforms previous hidden state (recurrence)

For variable lengths, we simply stop updating at $t > L_i$ for sequence $i$. The key insight: **the weights $W_{h}, W_{xh}$ are shared across all time steps and all sequence lengths**—this is parameter efficiency.

---

### 4. Attention Mechanisms (Length-Agnostic)

> [!intuition] Why Attention Solves Variable Lengths Naturally
> Attention doesn't care about sequence length because it's a ==weighted sum over all positions==. Whether you have 5 or 500 tokens, the attention mechanism computes:
> $$\text{output}_i = \sum_{j=1}^{L} \alpha_{ij} v_j$$

where $L$ is the actual sequence length (no padding needed in the math itself).

**Derivation of scaled dot-product attention:**

Given:
- Query: $q \in \mathbb{R}^{d_k}$ (what we're looking for)
- Keys: $K \in \mathbb{R}^{L \times d_k}$ (what's available)
- Values: $V \in \mathbb{R}^{L \times d_v}$ (what we return)

Step 1: Compute similarity scores
$$s_j = q^T k_j \quad \text{for } j=1,...,L$$

**Why dot product?** Measures alignment between query and key. High dot product = similar directions in embedding space.

Step 2: Scale the scores
$$s_j' = \frac{q^T k_j}{\sqrt{d_k}}$$

**Why scale by $\sqrt{d_k}$?** For high-dimensional vectors, dot products grow large in magnitude. If $q$ and $k$ have unit variance, $q^T k$ has variance $d_k$. Dividing by $\sqrt{d_k}$ normalizes variance to 1, preventing softmax saturation.

**Mathematical proof:**
If $q, k \sim \mathcal{N}(0, I)$, then:
$$\text{Var}(q^T k) = \text{Var}\left(\sum_{i=1}^{d_k} q_i k_i\right) = \sum_{i=1}^{d_k} \text{Var}(q_i)\text{Var}(k_i) = d_k$$

So $\text{Var}\left(\frac{q^T k}{\sqrt{d_k}}\right) = \frac{d_k}{d_k} = 1$.

Step 3: Compute attention weights
$$\alpha_j = \frac{\exp(s_j')}{\sum_{k=1}^{L} \exp(s_k')}$$

**Why softmax?** Converts scores to a probability distribution (sum to 1, all positive). The $\exp$ emphasizes differences.

Step 4: Weighted sum
$$\text{output} = \sum_{j=1}^{L} \alpha_j v_j$$

**Key insight for variable lengths:** This entire computation works for any $L$. No padding needed in the attention math! We only need masks to prevent attending to padding positions.

> [!example] Attention with Masking
> Suppose we have 2 sequences, lengths [3, 2], paded to length 3:
> ```
> Sequence 1: [a, b, c]    ← real
> Sequence 2: [d, e, PAD]  ← PAD should be ignored
> ```

Attention scores before masking (query at position 1 of seq 2):
$$s = [s_d, s_e, s_{PAD}]$$

Apply mask by setting $s_{PAD} = -\infty$ before softmax:
$$s_{masked} = [s_d, s_e, -\infty]$$

**Why $-\infty$?** After softmax: $\exp(-\infty) = 0$, so padding gets zero attention weight.

After softmax:
$$\alpha =[\alpha_d, \alpha_e, 0]$$

The output naturally ignores the padding position.

---

## Common Strategies Compared

| Method | Memory Computation | Complexity |
|--------|---------|------------|
| Padding + Masking | High (stores padding) | Wastes cycles on padding | Simple to implement |
| Packed Sequences | Low (no padding stored) | Efficient (skips padding) | Moderate (packing/unpacking) |
| Dynamic Unrolling | Medium | Efficient | Framework-dependent |
| Attention | Medium | Length-independent per head | High (quadratic in length) |

---

## Implementation Patterns

> [!example] PyTorch Packed Sequence
> ```python
# Assume: batch of sequences, sorted descending by length
# embedded: (batch, max_len, embed_dim)
# lengths: [7, 5, 3]

packed = pack_padded_sequence(embedded, lengths, batch_first=True)
# packed.data: (15, embed_dim) ← 7+5+3=15

packed_output, hidden = rnn(packed)
# packed_output.data: (15, hidden_dim)

output, _ = pad_packed_sequence(packed_output, batch_first=True)
# output: (batch, max_len, hidden_dim) ← back to paded

Why this sequence?

1. Pack removes padding → RNN processes only real tokens
2. RNN operates on packed format (internally handles variable batch sizes)
3. Unpack restores rectangular shape for subsequent layers (attention, linear layers, etc.)

Why this feels right: "I paded the sequences, so everything should work."

The problem: The model learns to predict padding tokens! This:

• Dilutes the loss signal from real tokens
• Causes the model to "cheat" by predicting PAD accurately
• Ruins perplexity and other metrics

Correct approach:

mask = (targets != pad_token).float()  # 1 for real, 0 for padding
loss = (criterion(predictions, targets) * mask).sum() / mask.sum()

Why the fix works: We zero out loss at padding positions, then normalize by the number of real tokens.

Why this feels right: "The function should handle any order."

The problem: pack_padded_sequence assumes lengths are sorted descending. Otherwise, the packed representation is incorrect—batch_sizes will be wrong.

The fix:

lengths, sort_idx = lengths.sort(descending=True)
embedded = embedded[sort_idx]
packed = pack_padded_sequence(embedded, lengths, batch_first=True)
# ... process ...
# Unsort outputs if needed: output = output[sort_idx.argsort()]

Option 1 (Padding): Tell everyone to submit exactly 5 pages. If you only wrote 2 pages, add 3 blank pages. But then you have to flip through those blank pages—wasted time! And when calculating the average essay quality, you need to remember to skip the blank pages.

Option 2 (Packing): Collect all the real pages in a stack, and keep a note: "Student A wrote 1 page, Student B wrote 5 pages, Student C wrote 2 pages." Now you only read real content! When you're done, you can reorganize them back into separate essays if needed.

Option 3 (Attention): Instead of reading page-by-page in order, you read all pages and decide which parts are most important for each question you're answering. Doesn't matter if it's page 1 or page 5—you just focus on what's relevant. Some pages might be blank (padding), so you completely ignore them.

Neural networks face the same problem with variable-length sentences. We use these tricks so the network doesn't waste time processing blank pages!

Remember: "PAM packs your sequences efficiently!"

Connections

• Recurrent Neural Networks - core architecture neding variable-length handling
• Attention Mechanism - alternative paradigm that handles lengths naturally
• Transformers - use positional encoding + attention, no recurrence needed
• Batch Processing - why variable lengths complicate batching
• Sequence-to-Sequence Models - encoder-decoder with different input/output lengths
• LSTM and GRU - specific RNN variants that use these techniques
• Masking in Deep Learning - general concept beyond sequences

#flashcards/ai-ml

Why do we need padding in sequence models? :: Neural networks process batches as rectangular tensors—all sequences in a batch must have the same length dimension for efficient matrix operations.

Concept Map

Hinglish (regional understanding)