Padding

The primary function of padding is to allow efficient parallel processing on hardware accelerators like GPUs and TPUs. These processors perform best with regular, rectangular tensors. By adding dummy tokens to make all sequences in a batch the same length, the data can be structured as a single contiguous block in memory, enabling the use of highly optimized matrix multiplication kernels (GEMM operations). Without padding, sequences would need to be processed individually, leading to severe underutilization of parallel hardware and drastically reduced throughput.

Padding introduces computational waste. The model performs calculations on the padding tokens, consuming FLOPs and memory bandwidth without producing useful output. This overhead is quantified by the padding ratio: (Total Tokens with Padding) / (Useful Tokens). For example, in a batch with sequences of lengths [5, 10, 200], padding all to 200 tokens results in a padding ratio of (200*3) / (5+10+200) ≈ 2.79, meaning nearly 65% of the computation is wasted. This directly increases latency and cost per token.

Different strategies balance simplicity with efficiency:

• Fixed-Length Padding: All sequences are padded/truncated to a pre-defined maximum length (e.g., 512, 2048). Simple but can be highly inefficient with variable input sizes.
• Batch-Specific Padding: Sequences within a single batch are padded to the length of the longest sequence in that batch. This is the standard approach in dynamic batching, minimizing waste within each batch.
• Bucket-Based Padding: Requests are sorted into length 'buckets' (e.g., 0-128, 129-256 tokens), and batches are formed from requests within the same bucket. This reduces variance in sequence length per batch, offering a good trade-off between scheduling flexibility and padding efficiency.

Padding tokens affect the attention mechanism and KV cache memory footprint. During attention, a causal mask or padding mask is applied to prevent the model from attending to padding tokens. However, the KV cache—storing key-value pairs for all previous tokens—is still allocated for padded positions. This leads to memory bloat. Optimized inference engines use paged attention (as in vLLM) or ragged tensor representations to avoid allocating cache memory for padding, significantly reducing GPU memory pressure.

Padding is contrasted with methods designed to eliminate its waste:

• Ragged/Jagged Tensors: Data structures that natively store variable-length sequences, allowing kernels to operate only on real data. Requires specialized kernel support.
• Sequence Packing: Concatenating multiple short sequences into one long sequence, separated by special separator tokens. Eliminates padding but complicates attention masking and decoding logic.
• Variable-Length Batching: Advanced scheduling that groups sequences of similar length and uses kernels that can handle variable dimensions within a batch (e.g., NVIDIA's TensorRT-LLM). This represents the state-of-the-art in minimizing padding overhead.

The use of padding creates a direct engineering trade-off:

• Throughput vs. Latency: Larger batches (with more padding) maximize GPU utilization and tokens/sec throughput but increase the time-to-first-token (TTFT) for individual requests waiting for the batch to form and execute.
• Memory Efficiency: High padding ratios waste High-Bandwidth Memory (HBM) bandwidth and capacity, which can become the limiting bottleneck during the decoding phase.
• Optimal Batch Size: The ideal batch size is not simply the maximum that fits in GPU memory. It is found by modeling the trade-off between the arithmetic intensity gained from larger matrices and the incremental latency from increased padding and scheduling delay.

A performance degradation in batching systems where a single long-running or stalled request within a batch delays the completion of all other requests. Padding can exacerbate this if one very long sequence forces excessive padding on all others.

• Cause in Inference: A single long sequence dictates the batch's execution time.
• Mitigation: Techniques like iteration-level scheduling in continuous batching allow shorter sequences to finish and exit the batch early.
• Impact: Directly increases tail latency (p95, p99) for users.

The two primary performance regimes for neural network operations, crucial for understanding padding's cost.

• Compute-Bound: Operation speed limited by processor FLOPs. The prefilling phase is typically compute-bound. Padding adds useless FLOPs, directly increasing cost.
• Memory-Bound: Operation speed limited by memory bandwidth. The decoding phase is memory-bound. Padding wastes memory bandwidth loading irrelevant padding token data into cache.
• Analysis: Padding inefficiency must be evaluated in both regimes for full system optimization.

An inference strategy where a fixed set of requests is grouped, and the entire batch must complete before any results are returned. This is the traditional contrast to continuous batching.

• Padding Role: Essential, as all sequences in the static batch must be padded to the length of the longest sequence before generation begins.
• Limitation: Causes high latency and low GPU utilization, as the GPU sits idle between batches and fast requests wait for slow ones.
• Evolution: Largely superseded by dynamic batching and continuous batching for interactive workloads.

A broad category of techniques for efficient memory use on accelerators. Padding has a direct, negative impact on key areas:

• Activation Memory: Padding increases the size of intermediate tensors, consuming more high-bandwidth memory (HBM).
• KV Cache Memory: In transformer decoding, the Key-Value (KV) Cache must be allocated for the padded sequence length, wasting reserved space.
• Memory Bandwidth: Loading and storing padding tokens consumes bandwidth that could be used for productive data, slowing down memory-bound phases.

The fine-grained scheduling mechanism at the heart of continuous batching. It redefines how padding is managed.

• Core Idea: The scheduler re-groups the set of active requests at each decoding step.
• Padding Impact: Instead of padding to a global max length for the lifetime of a batch, sequences may only need padding to the max length of the currently executing step. This dramatically reduces the average padding overhead.
• System Benefit: Enables efficient request interleaving and mitigates head-of-line blocking.