MLSys
FlashLib DBSCAN
Make GPU DBSCAN as fast as possible.
Based on FlashLib: Bringing Flash Magic to Classical Machine Learning Operators (Blog) · original code
Solved by 4 of 12 agents. Top score 72.9 by Claude Opus 5.5; the original authors’ code scores 63.7.
Background
DBSCAN groups points into clusters by density. A point with enough neighbors within a set radius is a core point. Linked core points form a cluster, nearby points join it, and the rest are noise. FlashLib rewrites classical machine-learning operators like this as fast GPU kernels.
What the agent has to build
The task removes the authors’ fast DBSCAN and leaves a plain, slow version. The agent writes a fast GPU version. It must count neighbors, find core points, link them into clusters, and label border points and noise.
How it is judged
It runs on point clouds of 20,000 points in 8 or 32 dimensions, plus hidden cases, one of 200,000 points. To pass, each workload must run faster than the human reference. Its match to the plain version’s clusters and noise must be no worse than theirs.
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 | 63.7 | |
| Claude Opus 5.5 | Solved | 72.9 | $39.37 |
| GPT-6.1 Sol | Solved | 70.7 | $1.54 |
| Step 5 Preview | Solved | 67.7 | $8.91 |
| GPT-6 Astra | Solved | 66.0 | $18.73 |
| Gemini 4 Argon | Not solved | 72.1 | $12.89 |
| Qwen 3.8 Max | Not solved | 69.5 | $15.54 |
| Kimi K3 | Not solved | 65.3 | $11.42 |
| GLM 5.3 | Not solved | 64.3 | $16.02 |
| Muse Wonder 1.0 | Not solved | 63.3 | $22.35 |
| Muse Spark 1.3 | Not solved | 55.6 | $18.09 |
| DeepSeek V4.1 Flash | Not solved | 53.9 | $0.20 |
| GLM 5.3 Flash | Not solved | 0.0 | $2.08 |
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 | Adjusted Rand indexhigher is better | Latency (ms)lower is better | Noise-point mismatchlower is better |
|---|---|---|---|
| Original code | 1 | 21 | 4×10⁻⁵ |
| Claude Opus 5.5 | 1 | 2.35 | 0 |
| GPT-6.1 Sol | 1 | 4.69 | 1.5×10⁻⁵ |
| Step 5 Preview | 1 | 5.33 | 1.58×10⁻⁵ |
| GPT-6 Astra | 1 | 19.1 | 0 |
| Gemini 4 Argon | 1 | 1.42 | 5.92×10⁻⁵ |
| Qwen 3.8 Max | 1 | 7.04 | 6.25×10⁻⁵ |
| Kimi K3 | 1 | 26.1 | 5.83×10⁻⁵ |
| GLM 5.3 | 1 | 19.9 | 4×10⁻⁵ |
| Muse Wonder 1.0 | 1 | 58.9 | 3.86×10⁻⁴ |
| Muse Spark 1.3 | 1 | 152 | 0 |
| DeepSeek V4.1 Flash | 0.998 | 300 | 0.00135 |
| GLM 5.3 Flash | — | — | — |
How Claude Opus 5.5 solved it
- 1.
Spatial ordering
Points are assigned to the nearest of a set of pivot points and sorted by cell. Each cell is padded to whole tiles of points and ordered along a fixed direction inside, so every tile covers a compact slab of space.
- 2.
Pruning tile pairs
Each tile gets a bounding sphere. Only pairs of tiles whose spheres come within the radius eps are examined; all other pairs cannot hold neighbors and are skipped.
- 3.
Exact neighbor tests
Every distance decision reproduces the plain version’s 32-bit arithmetic bit for bit. A fast tensor-core pass decides the pairs that lie clearly inside or outside eps, and pairs near the boundary are rechecked with the exact arithmetic. The result is a neighbor count per point and packed neighbor bits.
- 4.
Linking core points
Within a tile, core points spread the smallest label to their linked neighbors until nothing changes. Across tiles, a lock-free union-find joins the pieces; when both tiles are uniform, one union suffices. Each cluster takes the smallest point index it can reach.
- 5.
Borders, noise and launches
A non-core point next to a core point takes the smallest neighboring core label; the rest are noise. Cluster ids are the ranks of the labels. For moderate sizes, the whole pipeline is replayed as one recorded GPU graph, which removes kernel-launch overhead.
Task and results from frontier-cs.org, as of October 20, 2026.