MLSys
FlashLib IVF-PQ
Make GPU IVF-PQ search as fast as possible.
Based on FlashLib: Bringing Flash Magic to Classical Machine Learning Operators (Blog) · original code
Solved by 7 of 12 agents. Top score 80.5 by Claude Opus 5.5; the original authors’ code scores 75.6.
Background
IVF-PQ is a standard index for nearest-neighbor search over many vectors. It splits the vectors into thousands of lists and compresses each into 16 short codes. A query scans only its nearest lists and estimates distances with table lookups.
What the agent has to build
This task leaves only a slow, simple search over a fixed index. The agent writes the fast GPU search. It must pick the lists to probe, build each query’s distance table, scan the codes and keep the k best.
How it is judged
Each submission searches the SIFT image-descriptor benchmark with batches of thousands of queries. To pass, it must beat the human reference on search time for every workload. Its recall must be no lower, both against a full scan and for the true nearest neighbor.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 75.6 | |
| Claude Opus 5.5 | Solved | 80.5 | $54.19 |
| Gemini 4 Argon | Solved | 79.8 | $7.64 |
| GPT-6.1 Sol | Solved | 79.3 | $3.45 |
| Kimi K3 | Solved | 79.1 | $6.64 |
| GLM 5.3 | Solved | 78.7 | $7.31 |
| GPT-6 Astra | Solved | 78.2 | $32.15 |
| Muse Wonder 1.0 | Solved | 78.1 | $22.50 |
| DeepSeek V4.1 Flash | Not solved | 78.7 | $0.12 |
| Step 5 Preview | Not solved | 77.6 | $7.55 |
| GLM 5.3 Flash | Not solved | 76.7 | $0.65 |
| Qwen 3.8 Max | Not solved | 75.6 | $6.78 |
| Muse Spark 1.3 | Not solved | 70.2 | $6.39 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Recall at matched costhigher is better | Nearest-neighbor recallhigher is better | Search latency (ms)lower is better |
|---|---|---|---|
| Original code | 1 | 0.967 | 150 |
| Claude Opus 5.5 | 1 | 0.967 | 1.73 |
| Gemini 4 Argon | 1 | 0.967 | 3.41 |
| GPT-6.1 Sol | 1 | 0.967 | 5.46 |
| Kimi K3 | 1 | 0.967 | 3.92 |
| GLM 5.3 | 1 | 0.967 | 7.53 |
| GPT-6 Astra | 1 | 0.967 | 8.35 |
| Muse Wonder 1.0 | 1 | 0.967 | 15.9 |
| DeepSeek V4.1 Flash | 1 | 0.967 | 19.4 |
| Step 5 Preview | 1 | 0.967 | 8.73 |
| GLM 5.3 Flash | 1 | 0.967 | 13.7 |
| Qwen 3.8 Max | 1 | 0.967 | 16.7 |
| Muse Spark 1.3 | 1 | 0.967 | 80.6 |
How Claude Opus 5.5 solved it
- 1.
Choosing the lists to probe
Tensor cores compute approximate query-to-centroid distances in bfloat16, with a rigorous bound on their error. Lists that are clearly inside or outside the nearest set are settled at once. Only the centroids near the boundary are recomputed exactly; the probes are then ordered by distance and centroid id.
- 2.
Scanning list by list
It groups the query–list pairs by list, so each list’s codes are decoded once and compared with every query that probes it, as one tensor-core matrix product. The approximate distance is the query-to-centroid distance plus terms of the decoded residual.
- 3.
A safe shortlist, then exact top-k
A streaming filter per query keeps a small superset that provably contains the true k best, with the error bound as its margin. It rescores this shortlist with the plain search’s table-lookup arithmetic and sorts it by distance, then by index.
- 4.
Exact output, its own idea
Every fast pass is approximate but carries an error bound, and anything near a boundary is recomputed with the plain search’s own arithmetic and order of summation. So the output matches the slow search exactly: the same lists, float32 distances and tie-breaking. Tiny query batches stay on the plain path, where the matrix library rounds differently.
Task and results from frontier-cs.org, as of October 20, 2026.