Exercises — Handling variable-length sequences

What we do: $L_{max}$ is just the biggest of the true lengths. $L_{max}=\max (4,7,2)=7.$ The grid has one row per sequence ($B=3$) and $L_{max}=7$ columns. Shape: $3\times 7$. Row 1 has $4$ real cells and $3$ pad cells; row 3 has $2$ real cells and $5$ pad cells — exactly the left panel of figure s01.

Row $i$ has $L_i$ ones followed by pad zeros (this is the right panel of figure s01):

row 1 (L=4): 1 1 1 1 0 0 0
row 2 (L=7): 1 1 1 1 1 1 1
row 3 (L=2): 1 1 0 0 0 0 0

Check: the ones in each row count its true length: $4,7,2$. ✓

False. The sum runs to $L$, the actual length, so the math handles any length directly. Padding only appears because we store sequences in a rectangular tensor; we use a mask to stop attention from looking at those pad cells, but the formula never requires padding.

Recall the formula (time steps run $t=1\dots L_{max}$): ${\mathcal{L}}_i=\frac{1}{{\sum }_{t=1}^{L_{max}}{m}_i(t)}{\sum }_{t=1}^{L_{max}}{m}_i(t){\ell }_t.$ What each piece does: the mask $m_i=[1,1,1,0,0]$ zeroes out the padding losses in the numerator, and the denominator $\sum m_i=3$ divides by the real length. $\text{numerator}=1(2.0)+1(4.0)+1(0.0)+0(9.9)+0(9.9)=6.0,$ ${\mathcal{L}}_i=\frac{6.0}{3}=\mathrm{2.0.}$ The garbage pad values $9.9$ vanish because their mask is $0$.

Sequence 1: ${\mathcal{L}}_1=2.0$ (from 2.1). Sequence 2: mask is all ones, ${\mathcal{L}}_2=\frac{1+1+1+1+1}{5}=1.0$. ${\mathcal{L}}_{batch}=\frac{1}{2}(2.0+1.0)=\mathrm{1.5.}$

Indexing note: everywhere else on this page time runs $t=1,2,3,\dots$, but batch_sizes is an ordinary Python list, so it is read from index $0$. Below, "$t$" means the list index, i.e. the $(t+1)$-th time step. The story is identical; only the starting number differs. batch_sizes[t] = how many sequences are still alive (have a real token) at that step. This is exactly the "alive count" glyph shown above each column in figure s02.

• $t=0$ (1st step): all $3$ alive → $3$
• $t=1$ (2nd step): all $3$ still have $\ge 2$ tokens → $3$
• $t=2$ (3rd step): the length-$2$ one ended, $2$ remain → $2$
• $t=3$ (4th step): the length-$3$ one ended, $1$ remains → $1$
• $t=4$ (5th step): still $1$ remains (the length-$5$ one) → $1$ $\text{batch\_sizes}=[3,3,2,1,1].$ Check: the sum equals the number of real tokens: $3+3+2+1+1=10=5+3+2$. ✓

Why $-\infty$? After softmax, $\exp (-\infty )=0$, so the padding key gets exactly zero weight and never leaks into the output. ${\alpha }_j=\frac{\exp (s_j)}{{\sum }_k\exp (s_k)},\exp (2)=7.389,\exp (1)=2.718,\exp (-\infty )=0.$ Denominator $=7.389+2.718+0=10.107$. ${\alpha }_1=\frac{7.389}{10.107}=0.731,{\alpha }_2=\frac{2.718}{10.107}=0.269,{\alpha }_3=0.$ Check: $0.731+0.269+0=1.000$. The distribution is valid and padding is fully ignored. ✓

Variance: each term $q_i{k}_i$ has variance $1$ (product of two independent unit-variance zero-mean values), and there are $d_k$ independent terms, so $\text{Var}(q^{\top }k)={\sum }_{i=1}^{64}\text{Var}(q_i{k}_i)=64.$ Standard deviation $=8$. So raw scores routinely swing by $\pm 8$ or more. Why that hurts: softmax of scores like $[8,-8]$ gives $\approx [1,0]$ — it saturates, meaning the gradient through softmax is nearly zero and learning stalls. Scaling gives $\text{Var}\left(\frac{q^{\top }k}{\sqrt{64}}\right)=\frac{64}{64}=1$, keeping scores in a range where softmax stays responsive. Why before, not after: softmax is nonlinear; dividing its output by $\sqrt{d_k}$ would break the "sums to 1" property and would not undo the saturation, which already happened inside the $\exp$. You must tame the input to the exponential.

Plan A (padding): the RNN steps over every cell of a $3\times 7$ grid $=3\times 7=21$ evaluations. Plan B (packing): it only touches real cells $=4+7+2=13$ evaluations. Wasted work in A: $21-13=8$ pad evaluations, a fraction $\frac{8}{21}\approx 0.381=38.1\%.$ Packing eliminates that $38\%$ of pointless computation.

Design reasoning: a naive mean $\frac{1}{L_{max}}{\sum }_t{h}_i(t)$ would average in the garbage pad values. Multiply by the mask to zero pads, then divide by the real count ${\sum }_t{m}_i(t)$: ${\text{pool}}_i=\frac{{\sum }_{t=1}^{L_{max}}{m}_i(t)h_i(t)}{{\sum }_{t=1}^{L_{max}}{m}_i(t)}.$ Evaluate: numerator $=1(3)+1(5)+1(1)+0(99)+0(99)=9$; denominator $=3$. $\text{pool}=\frac{9}{3}=\mathrm{3.0.}$ The pads $99$ never entered the answer.

Masks: $m_1=[1,1,0,0]$, $m_2=[1,1,1,1]$. ${\mathcal{L}}_1=\frac{0.5+1.5}{2}=\frac{2.0}{2}=\mathrm{1.0.}$ ${\mathcal{L}}_2=\frac{1.0+1.0+1.0+1.0}{4}=\frac{4.0}{4}=\mathrm{1.0.}$ ${\mathcal{L}}_{batch}=\frac{1}{2}(1.0+1.0)=\mathrm{1.0.}$

Idea: pad cells in a batch $=B\cdot L_{max}-\sum L_i$. To shrink padding, group similar lengths so $L_{max}$ is close to each member. Good split: $\{2,3,3\}$ and $\{8,9,10\}$.

• Batch 1: $L_{max}=3$, pad $=3(3)-(2+3+3)=9-8=1$.
• Batch 2: $L_{max}=10$, pad $=3(10)-(8+9+10)=30-27=3$.
• Total pad $=1+3=4$. Worst split (mix short with long): $\{2,3,10\}$ and $\{3,8,9\}$.
• Batch 1: $3(10)-15=15$; Batch 2: $3(9)-20=7$; total $=22$. Length-bucketing cuts padding from $22$ down to $4$ — an $18$-cell (about $82\%$) reduction.

Claim: for any $L_{max}\ge L_i$, ${\mathcal{L}}_i$ depends only on the real losses ${\ell }_1,\dots ,{\ell }_{L_i}$. Proof. Split the sum at $L_i$: ${\sum }_{t=1}^{L_{max}}{m}_i(t){\ell }_t=\underset{\text{real}}{\underbrace{\sum _{t=1}^{L_i}1\cdot {\ell }_t}}+\underset{=0}{\underbrace{\sum _{t=L_i+1}^{L_{max}}0\cdot {\ell }_t}}.$ By the mask definition $m_i(t)=0$ for every $t>L_i$, so the second sum is identically $0$ regardless of how many pad columns exist or what garbage ${\ell }_t$ they hold. Likewise the denominator ${\sum }_{t=1}^{L_{max}}{m}_i(t)={\sum }_{t=1}^{L_i}1+{\sum }_{t=L_i+1}^{L_{max}}0=L_i$ is also independent of $L_{max}$. Therefore ${\mathcal{L}}_i=\frac{{\sum }_{t=1}^{L_i}{\ell }_t}{L_i},$ which contains no reference to $L_{max}$. $■$ What it means: you can re-batch the same sequence with any longer padding and its loss (and gradient) will not change — the mask makes padding a no-op.

(a) $L_i=0$: the denominator ${\sum }_t{m}_i(t)=0$, so ${\mathcal{L}}_i=\frac{0}{0}$ is undefined. Correct handling: exclude empty sequences from the batch entirely (or guard the division). An empty sequence carries no supervision signal, so it must not contribute to the average — and dividing by zero would produce NaN gradients that poison the whole update. (b) all-padding attention row: every score becomes $-\infty$, so softmax computes $\frac{\exp (-\infty )}{\sum \exp (-\infty )}=\frac{0}{0}$ → NaN. Correct handling: never let a query attend over a fully-empty key set; if it can happen, force the output to $0$ (or a learned default). This is the attention twin of case (a). (c) all sequences share the same length: then $L_i=L_{max}$ for every $i$, so every mask entry is $1$ (there are no pad columns at all). Masking therefore multiplies each loss by $1$ and the normaliser ${\sum }_t{m}_i(t)=L_{max}$ is the same for all rows. The masked-loss formula collapses to the ordinary unmasked mean ${\mathcal{L}}_i=\frac{1}{L_{max}}{\sum }_t{\ell }_t$, and packing's batch_sizes becomes $[B,B,\dots ,B]$ of length $L_{max}$ (no sequence ever "dies early"). Conclusion: in the equal-length case all our machinery gracefully reduces to plain fixed-length training — masking never hurts, it simply becomes a no-op. This is the reassurance that the variable-length tools are a strict generalisation.

Padding count: the grid is $B$ rows by $L_{max}$ columns and the RNN visits every cell → $B\cdot L_{max}$. Packing count: batch_sizes[t] counts sequences alive at step $t$, and ${\sum }_t\text{batch\_sizes}[t]={\sum }_i{L}_i$ (each real token counted once). So packing does ${\sum }_i{L}_i$ evaluations. Ratio: $\frac{\text{packing}}{\text{padding}}=\frac{{\sum }_i{L}_i}{B{L}_{max}}=\frac{\frac{1}{B}{\sum }_i{L}_i}{L_{max}}=\frac{\bar{L}}{L_{max}}.$ Numbers: $\bar{L}=\frac{4+7+2}{3}=\frac{13}{3}\approx 4.333$, $L_{max}=7$, so ratio $=\frac{13}{21}\approx 0.619$. Packing does about $62\%$ of the work — the more your lengths vary, the smaller $\frac{\bar{L}}{L_{max}}$ and the bigger the win. $■$

L1: shape $3\times 7$; masks as shown ::: see solutions 2.1 ${\mathcal{L}}_i=2.0$ ::: 2.2 ${\mathcal{L}}_{batch}=1.5$ ::: 2.3 batch_sizes $=[3,3,2,1,1]$ 3.1 $\alpha =[0.731,0.269,0]$ ::: 3.2 Var $=64$ ::: 3.3 waste $=38.1\%$ 4.1 pool $=3.0$ ::: 4.2 ${\mathcal{L}}_{batch}=1.0$ ::: 4.3 pad $4$ vs $22$ 5.3 ratio $=13/21\approx 0.619$