Eliminating the Padding Tax via Sequence Packing

48 concepts41 papers1 proposal

Modern hardware accelerators like GPUs are built for dense, uniform matrix operations. They achieve maximum throughput when every processing core executes the same operation on a perfectly aligned block of memory. However, real-world data—whether it is text, audio spectrograms, or user interaction histories—is inherently variable in length.

To process a batch of variable-length sequences in parallel, traditional deep learning frameworks rely on padding. Shorter sequences are padded with zero tokens to match the length of the longest sequence in the batch. While this creates the uniform tensors that GPUs require, it introduces a massive "padding tax." As noted by Portes et al. in their work on MosaicBERT, this tax wastes substantial compute cycles and memory on non-informative tokens that do not contribute to learning. In datasets with highly skewed sequence lengths, padding tokens can easily account for the majority of the total processed data, severely bottlenecking training and inference efficiency.

To eliminate this waste, a prominent research direction has emerged around sequence packing: treating batch creation as a bin-packing problem to combine multiple variable-length sequences into a single, fixed-length block without padding.

The Intuition of Sequence Packing

Instead of filling the empty space of a batch with useless zero tokens, sequence packing fills that space with other actual data samples.

Imagine a batch size of 1024 tokens. If you have three independent sequences of lengths 500, 300, and 200, traditional batching would place them in separate rows and pad them out to 500 tokens each, wasting 500 tokens worth of computation. Sequence packing concatenates them into a single sequence of 1000 tokens, leaving nearly zero waste.

Wang et al. demonstrate in Packing Analysis that using a greedy bin-packing approach during supervised fine-tuning drastically improves training throughput while maintaining or even improving model performance as datasets scale. This concept is not limited to text. In computer vision, Dehghani introduces "Patch n' Pack" via NaViT, a Vision Transformer that packs patches from multiple images of completely different resolutions and aspect ratios into a single sequence. This allows the model to train on native image shapes without wasting compute on padding or distorting the images via forced resizing.

Preventing Information Leakage

While packing solves the hardware utilization problem, it introduces a fundamental algorithmic challenge: information leakage. If you simply concatenate independent sequences together, a standard sequence model will treat them as a single continuous context. Tokens from one sequence will influence the representations of another, corrupting the model's attention or internal states.

To make packing work, researchers must modify the underlying model operators to respect the boundaries of the original sequences.

1. Sequence-Aware Attention Masking

In Transformer architectures, isolation is achieved by modifying the attention matrix. In Prepacking, Zhao et al. show how to construct attention masks that prevent tokens from attending to any token outside their original sequence boundary.

Standard Attention Mask (Padded Batch)       Packed Attention Mask (Sequence-Isolated)
[ 1  1  0  0 ] (Seq 1, length 2)             [ 1  1  0  0 ] (Seq 1 tokens only attend to Seq 1)
[ 1  1  0  0 ]                               [ 1  1  0  0 ]
[ 0  0  1  1 ] (Seq 2, length 2)             [ 0  0  1  1 ] (Seq 2 tokens only attend to Seq 2)
[ 0  0  1  1 ]                               [ 0  0  1  1 ]

By passing sequence segmentation metadata alongside the packed block, hardware-accelerated attention kernels (like FlashAttention) can evaluate the entire packed block in a single pass while mathematically preserving the independence of each prompt.

2. Resetting Recurrent and State-Space States

For architectures that rely on sequential recurrence rather than global attention—such as State-Space Models (SSMs)—masking matrices cannot be used. Instead, the internal hidden states must be explicitly managed.

In PackMamba, Xu et al. modified the core SSM and 1D convolution operators of the Mamba architecture. When the model processes a packed sequence and hits a boundary marker, the operator resets its internal state to zero. This ensures that the historical context of the preceding sequence is completely erased before the first token of the next sequence is processed.

Alternative Strategy: Length-Based Bucket Sampling

An alternative, lighter-weight approach to mitigating padding waste is to group sequences of similar lengths together before forming batches, often referred to as bucket sampling or dynamic batching.

Nagarajan et al. utilize this strategy in TokenDrop + BucketSampler to minimize the variance of sequence lengths within any single batch. If a batch only contains sentences that are roughly 30 tokens long, the padding required to align them is negligible.

However, sorting sequences strictly by length introduces a major trade-off regarding optimization stability. As demonstrated by Morishita et al. in An Empirical Study of Mini-Batch Creation Strategies for Neural Machine Translation, clustering sequences too aggressively by length alters the data distribution seen by the model during training updates. This violates the independent and identically distributed (i.i.d.) assumption of stochastic gradient descent, which can degrade final model accuracy and destabilize training.

Consequently, while bucket sampling requires fewer modifications to model architectures than sequence packing, it requires a careful balancing act between length homogeneity and data randomization to ensure both speed and convergence stability (Gonzalez et al.).

Key Foundational Work

Efficient GPU-based training of recurrent neural network language models using spliced sentence bunch (2014) — contributed 1 concept elements to this direction.
Sequence to Sequence Training of CTC-RNNs with Partial Windowing (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_padding_induced_computational_waste_356613c1,
  title = {padding-induced computational waste},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/padding-induced-computational-waste/rdr_356613c1545245908ad4c0f2d910c502},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_padding_induced_computational_waste_356613c1_v1,
  title = {padding-induced computational waste},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/padding-induced-computational-waste/rdr_356613c1545245908ad4c0f2d910c502/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake