NaViT Sequence Packing of Variable-Size Images

1. Background Knowledge

In modern Vision-Language Models (VLMs) like NaViT ("Patch n' Pack"), images are not resized to a fixed grid. Instead, each image is divided into a variable number of patch tokens based on its native resolution. To train efficiently on a GPU, these variable-length token lists must be packed into fixed-length sequences of capacity max_len. This avoids wasting compute on padding, which is critical because attention cost scales quadratically with sequence length.

The packing strategy described here is First-Fit. This is a classic heuristic from bin-packing problems. Unlike First-Fit Decreasing (FFD), which sorts items by size before packing, First-Fit processes items in their original order. For each item, you scan the currently open bins (sequences) and place the item in the first bin that has enough remaining capacity. If no open bin fits, you open a new bin. This approach is simple, deterministic, and preserves the temporal or spatial ordering of images, which can be important for certain training dynamics.

A special case exists for "oversized" items: if a single image's token count exceeds max_len, it cannot be split. The problem states such an image is truncated to max_len and placed in its own dedicated sequence. This ensures the sequence capacity constraint is never violated, even at the cost of discarding some tokens from that specific image.

2. Algorithm Approach

The problem is a simulation of the First-Fit bin-packing algorithm. You do not need to optimize for the minimum number of bins (which is NP-hard); you just need to faithfully simulate the greedy rule.

The core data structure is a list of "open sequences," where each sequence tracks its current used capacity. For each token count in the input list:

1. Check if it exceeds max_len. If so, truncate it and open a new sequence.
2. Otherwise, iterate through the existing open sequences.
3. If a sequence has enough remaining space (max_len - used >= tokens[i]), add the tokens to it and stop searching.
4. If no existing sequence fits, open a new sequence with this token count.

After processing all images, calculate the total padding and utilization based on the final state of the open sequences.

3. Step-by-Step Strategy

1. Initialize State: Create an empty list to hold the used capacities of open sequences, e.g., sequences = [].
2. Iterate Through Tokens: Loop through each t in tokens.
3. Handle Oversized Tokens:

• If t > max_len, set t = max_len.
• Append a new sequence with used capacity t to sequences.
• Continue to the next token (it does not share with others).

4. First-Fit Search:

• Loop through the indices of sequences.
• For each sequence s, check if s + t <= max_len.
• If it fits, update sequences[i] += t and break out of the inner loop.

5. Open New Sequence:

• If the inner loop completes without finding a fit, append a new sequence with used capacity t to sequences.

6. Calculate Metrics:

• num_sequences: Length of the sequences list.
• used_total: Sum of all values in sequences.
• total_capacity: num_sequences * max_len.
• padding: total_capacity - used_total.
• fill: used_total / total_capacity, rounded to 4 decimal places.

7. Return: Construct and return the dictionary with the three keys.

4. Common Pitfalls

• Off-by-One Errors in Capacity Check: Ensure you check used + t <= max_len, not used + t < max_len. A sequence can be exactly full.
• Oversized Token Handling: Do not try to fit an oversized token into an existing sequence. The problem explicitly states it is truncated and placed in its own new sequence. Forgetting to truncate will lead to sequences exceeding max_len.
• Modifying List While Iterating: When checking for a fit, you are reading from the list. Only append to the list if no fit is found. Be careful not to append inside the inner loop.
• Division by Zero: If tokens is empty, num_sequences will be 0. Ensure you handle this edge case to avoid division by zero when calculating fill.
• Rounding Precision: The problem asks for fill rounded to 4 decimals. Use Python's round(value, 4) function. Be aware of floating-point representation issues, though round usually handles this correctly for this precision.

5. Time & Space Complexity

• Time Complexity: $O(N \cdot K)$, where $N$ is the number of images (tokens) and $K$ is the number of open sequences. In the worst case, each new token might need to scan all existing sequences before finding a fit or opening a new one. Since $K \le N$, the worst-case time is $O(N^2)$.
• Space Complexity: $O(K)$, where $K$ is the number of open sequences. We store the used capacity for each open sequence. In the worst case, $K = N$, so space is $O(N)$.