NaViT Sequence Packing of Variable-Size Images

Problem Statement

NaViT ("Patch n' Pack") trains at native resolution by packing patch sequences from many images into fixed-length sequences, first-fit greedy, so almost no compute is wasted on padding. Given each image's patch count and a maximum sequence length, pack them and report utilization.

Background

Each image contributes tokens[i] patch tokens. We fill sequences of capacity max_len using first-fit: for each image in order, place it in the first open sequence that still has room; if none fits, open a new sequence. An image whose token count exceeds max_len on its own is truncated to max_len and placed in its own new sequence (it never shares). Padding for a sequence is max_len - used.

Your Task

Implement:

def pack_sequences(tokens, max_len):

Return a dict:

• "num_sequences": how many sequences were opened.
• "padding": total padding tokens summed across all sequences.
• "fill": overall utilization used_total / (num_sequences * max_len), rounded to 4 decimals.

Input Format

• tokens: list of ints (patch counts), processed in the given order.
• max_len (int): sequence capacity.

Output Format

• A dict with the three keys above.

Sample

print(pack_sequences([100, 50, 60], 128))

Output:

{'num_sequences': 2, 'padding': 46, 'fill': 0.8203}