Learned Query Compression Ratio
Problem Statement
A resampler (Q-Former, Perceiver) reads N patch tokens with Q learned queries and emits exactly Q tokens, regardless of N. Given a batch of images at possibly different resolutions, report how many tokens the LM sees with and without the resampler and the overall savings.
Background
Without a resampler, the LM ingests the raw patch tokens, sum_i N_i. With a resampler of Q queries, each image contributes exactly Q tokens, so the LM ingests Q * num_images. The token reduction ratio is raw_total / resampled_total.
Your Task
Implement:
def resampler_savings(patch_counts, num_queries):
Return a dict with "raw_total", "resampled_total", "ratio" where ratio is rounded to 4 decimals.
Input Format
- patch_counts: list of per-image patch-token counts.
- num_queries (int): the resampler's query count Q.
Output Format
- A dict: two ints and one float.
Sample
print(resampler_savings([576, 576, 2304], 64))
Output:
{'raw_total': 3456, 'resampled_total': 192, 'ratio': 18.0}
Example:
print(resampler_savings([576, 576, 2304], 64))
{'raw_total': 3456, 'resampled_total': 192, 'ratio': 18.0}- Calculate the total number of raw patch tokens by summing the counts for all images: 576+576+2304=3456.
- Determine the total resampled tokens by multiplying the number of images (3) by the number of learned queries (64): 3×64=192.
- Compute the compression ratio by dividing the raw total by the resampled total: 3456/192=18.0.
- The final output is
{'raw_total': 3456, 'resampled_total': 192, 'ratio': 18.0}
Constraints:
1 <= len(patch_counts) <= 100000,num_queries >= 1.resampled_total = num_queries * len(patch_counts).ratiorounded to 4 decimals.
1. Background Knowledge
In Vision-Language Models (VLMs), the vision encoder (e.g., ViT) processes an image by dividing it into fixed-size patches. If an image is H×W pixels and the patch size is P×P, the number of patch tokens is N=P2H⋅W​. Because input resolutions vary, N is not constant across a batch. The Language Model (LM) backbone typically has a fixed maximum context length, so ingesting thousands of raw patch tokens per image is inefficient and often infeasible.
To solve this, resampler modules like the Q-Former (used in BLIP-2) or Perceiver Resampler are inserted between the vision encoder and the LM. These modules use a fixed set of Q learned query vectors. Through cross-attention, these queries attend to the N patch tokens and compress them into exactly Q output tokens. Crucially, the output size is independent of the input size N. This means that whether an image produces 576 or 2304 patch tokens, the LM always receives exactly Q tokens from that image.
The compression ratio quantifies this efficiency gain. It is defined as the total number of raw patch tokens divided by the total number of resampled tokens. A higher ratio indicates greater savings in computational cost and memory usage for the downstream LM.
2. Algorithm Approach
This problem is a straightforward arithmetic calculation involving aggregation over a list. The core logic involves two main computations:
- Raw Total: Sum the individual patch counts for all images in the batch.
- Resampled Total: Multiply the number of images by the fixed number of queries Q.
Finally, compute the ratio by dividing the raw total by the resampled total. The approach relies on basic list operations and integer/float arithmetic. No complex data structures or iterative algorithms beyond a simple sum are required.
3. Step-by-Step Strategy
- Calculate raw_total:
- Iterate through the patch_counts list.
- Sum all values to get the total number of patch tokens the LM would see without a resampler.
- In Python, this is efficiently done using the built-in sum() function.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.