📘

AnyRes Tiling Token Budget

MediumVision-Language Models 📚 VLM 1: Vision-Language Models

Problem Statement

LLaVA-NeXT feeds high-resolution images to a fixed-resolution vision encoder by tiling: the image is split into a grid of encoder-sized tiles, each tile is encoded separately, and a downscaled thumbnail of the whole image is encoded too. Compute the resulting visual-token budget.

Background

A CLIP/SigLIP encoder is trained at one resolution (say 336x336). Feeding it a 672x1008 document at native resolution is not possible, and downsampling the document to 336x336 destroys the text. AnyRes solves this by cutting the image into tiles:

rows = ceil(image_h / tile_size)
cols = ceil(image_w / tile_size)
num_tiles = rows * cols

Every tile is encoded independently at the encoder's native resolution, and one extra thumbnail tile (the whole image squashed to tile_size x tile_size) is encoded so the model keeps global context:

total_tiles = num_tiles + 1   (when the thumbnail is included)

Each tile produces (tile_size // patch_size)^2 patch tokens. Because that number explodes - 336/14 = 24, so 576 tokens per tile - implementations apply token compression, most simply a pool_stride x pool_stride average-pool over the patch grid before projection:

side = (tile_size // patch_size) // pool_stride
tokens_per_tile = side * side
total_tokens = total_tiles * tokens_per_tile

This is the single most important number in a VLM's context budget: at pool_stride = 1 a 2x3 tiling costs 7 * 576 = 4032 positions, which can exceed the text prompt by two orders of magnitude.

Your Task

Implement:

def anyres_token_budget(image_h, image_w, tile_size, patch_size, pool_stride=1, include_thumbnail=True):

Return [rows, cols, total_tiles, tokens_per_tile, total_tokens] as plain Python integers. Note that total_tiles already includes the thumbnail when include_thumbnail is True.

Input Format

image_h, image_w - source image size in pixels (need NOT be a multiple of tile_size)
tile_size - the encoder's native input resolution
patch_size - ViT patch size; tile_size is divisible by patch_size
pool_stride - side of the square pooling window over the patch grid; tile_size // patch_size is divisible by it
include_thumbnail - whether the global thumbnail tile is encoded as well

Output Format

A list of five integers.

Sample

print(anyres_token_budget(672, 1008, 336, 14))

Output:

[2, 3, 7, 576, 4032]

Example:

Input:

print(anyres_token_budget(672, 1008, 336, 14))

Output:

[2, 3, 7, 576, 4032]

Reasoning:

672/336 = 2 rows and 1008/336 = 3 cols, so 6 tiles, plus 1 thumbnail = 7 tiles. Each 336x336 tile with patch 14 gives a 24x24 grid = 576 tokens. 7 * 576 = 4032 visual tokens.

Constraints:

Tile counts use a CEILING division - a partial tile still costs a full tile
tile_size % patch_size == 0 and (tile_size // patch_size) % pool_stride == 0
The thumbnail, when included, is one extra tile costing the same tokens_per_tile
Return plain Python int values
Do not use floating point for the ceiling (use -(-a // b) or math.ceil on exact values)

More from VLM 1: Vision-Language Models

Visual Token Pruning by Attention MassHard CHAIR-i and CHAIR-s Hallucination RatesMedium Merge a LoRA Update into the Base WeightMedium QLoRA Memory Footprint EstimateMedium POPE Precision, Recall, and F1Medium

1. Background Knowledge

In Vision-Language Models (VLMs) like LLaVA-NeXT, the vision encoder (e.g., CLIP or SigLIP) is typically trained on images of a fixed resolution, such as $336 \times 336$ . When processing high-resolution images, simply downsampling the entire image to this fixed size destroys fine-grained details (like text in documents). To preserve detail while maintaining global context, AnyRes (Any Resolution) tiling is used. This technique splits the high-resolution image into a grid of non-overlapping tiles, each resized to the encoder's native resolution.

Each tile is processed by a Vision Transformer (ViT), which divides the image into patches. If the tile size is $T$ and the patch size is $P$ , the number of patches per dimension is $T/P$ . The total number of visual tokens generated per tile is $(T/P)^2$ . However, this number can be large (e.g., $24^2 = 576$ tokens for $336/14$ ). To reduce the context length, token compression is often applied via average pooling over the patch grid with a stride of $S$ (pool_stride). This reduces the effective grid size to $(T/P)/S$ per dimension, resulting in $((T/P)/S)^2$ tokens per tile.

Finally, a thumbnail of the entire image (downscaled to $T \times T$ ) is often included to provide global context. The total token budget is the sum of tokens from all tiles plus the thumbnail. This budget is critical because it determines the sequence length input to the language model, directly impacting memory usage and inference speed.

2. Algorithm Approach

The problem requires calculating geometric dimensions and token counts based on integer arithmetic. The core approach involves:

Grid Calculation: Determine how many tiles are needed to cover the image height and width using ceiling division.
Token Per Tile Calculation: Compute the number of tokens generated by a single tile after patching and pooling.
Total Tiles Calculation: Sum the grid tiles and optionally add one for the thumbnail.
Total Tokens Calculation: Multiply the total number of tiles by the tokens per tile.

This is a straightforward arithmetic simulation problem. No complex data structures or iterative algorithms are needed. The key is correctly implementing ceiling division and handling the optional thumbnail flag.

3. Step-by-Step Strategy

Calculate Grid Dimensions:

Compute rows as $\lceil \text{image\_h} / \text{tile\_size} \rceil$ .
Compute cols as $\lceil \text{image\_w} / \text{tile\_size} \rceil$ .
Use integer arithmetic for ceiling division: $\lceil a/b \rceil = (a + b - 1) // b$ for positive integers.

Calculate Number of Tiles:

num_tiles = rows * cols.
If include_thumbnail is True, total_tiles = num_tiles + 1. Otherwise, total_tiles = num_tiles.

Calculate Tokens Per Tile:

First, find the number of patches per side: patches_per_side = tile_size // patch_size.
Apply pooling: pooled_side = patches_per_side // pool_stride.
tokens_per_tile = pooled_side * pooled_side.

Calculate Total Tokens:

total_tokens = total_tiles * tokens_per_tile.

Return Result:

Return the list [rows, cols, total_tiles, tokens_per_tile, total_tokens].

4. Common Pitfalls

Incorrect Ceiling Division: Using standard division / and then casting to int truncates towards zero, which is incorrect for ceiling. Always use (a + b - 1) // b or math.ceil(a / b).
Integer Division Order: Ensure tile_size is divisible by patch_size and patch_size is divisible by pool_stride as per problem constraints. If not, integer division // might truncate unexpectedly, but the problem guarantees divisibility.
Thumbnail Logic: Forgetting to add the thumbnail when include_thumbnail is True or adding it when it is False. The thumbnail counts as one additional tile with the same token count as any other tile.
Variable Naming: Confusing num_tiles (grid tiles only) with total_tiles (grid + thumbnail). The problem asks for total_tiles in the output.
Zero Dimensions: While unlikely in this context, ensure tile_size, patch_size, and pool_stride are non-zero to avoid division by zero errors.

5. Time & Space Complexity

Time Complexity: $O(1)$ . The solution involves a constant number of arithmetic operations regardless of the input image size. The calculations are direct formulas.
Space Complexity: $O(1)$ . Only a few integer variables are stored to hold the intermediate and final results. No additional data structures are used.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.