Optimization: DBSCAN clustering speedup

The agent starts from a written spec and nothing else. No starter code, no test harness. It has to build fastcluster, a real installable torch-native package exposing one function, then push its throughput as far as it can on CPU, from a few hundred thousand points into the tens of millions. It writes its own correctness checks and its own timing harness, and it has twelve hours of autonomous research time.

Exactness is non-negotiable: the spec pins the algorithm's semantics, and slow-and-right beats fast-and-wrong. Memory matters too; huge blowups for speed don't count.

DBSCAN is the standard density-based clustering algorithm, and the general-purpose implementations are slow in exactly the case pipelines hit most: flat 2D data at scale. Restricting to two dimensions under the Euclidean metric opens up structure a general implementation can't touch, spatial gridding, neighbor counting without distance matrices, union-find over cells. Whether an agent finds and exploits that structure is the whole task.

The verifier installs the submitted package into a fresh environment and measures throughput against a co-measured reference engine on hidden datasets running into the millions of points. The score is the fraction of the reference engine's throughput, and it only counts where the submitted package's cluster assignments match the reference partition exactly. A package that fails to install, or clusters wrong, scores zero.

Every run, strongest to weakest, converged on the same design: an epsilon-sized spatial grid with union-find connectivity inside a native extension. Every agent drove it with a timing harness of its own construction, so the spread reflects how far each engine got pushed rather than algorithm choice.

The strongest run kept measuring and reverting for nearly six hours. It shipped an engine with two execution modes selected by sampled cell occupancy. It beat the reference engine on every hidden dataset, at two and a half to four times its throughput on under half the memory. The runner-up worked even longer on hand-written SIMD kernels and a custom thread pool. It ended four times faster than the reference on uniform data but as low as a quarter of its pace on clustered data. The clustered case is what capped it. The weaker runs all declared the job done within about an hour of a twelve-hour budget and left correct but far slower engines. The slowest fell so far behind that the verifier stopped timing them partway through the hidden datasets. One was still holding reference pace on uniform data when the timing stopped.