DBSCAN clustering speedup

Build an exact 2D DBSCAN from a written contract with no starter code, and make it as fast and memory-frugal as possible on point clouds it has never seen; scored in raw millions of points per second.

Final score per graded run

Claude Opus 5
GPT-5.6 Sol
Gemini 3.7 Flash
Kimi K3
Grok 4.6

Most optimization benchmarks hand the agent a slow but working program and grade the speedup. This task hands it a contract instead: DBSCAN pinned down to the float, a generator for the point clouds it will be timed on, a C++ toolchain, and an empty package. The score is not a ratio against anything. It is the engine's raw throughput in millions of points per second, geometric mean over sixteen held-out workloads, scaled down only if the process overruns its memory budget. The author's reference engine is a row in the table, never a denominator.

Every model on the roster built an engine that beat the author's reference on the graded CPU+GPU variant, and Claude Opus 5 beat it roughly fourfold, its strongest engine grading 386.9 against the reference's 96.2. The leaderboard signs speed and memory on every axis of every submission, so the trade-offs behind a score stay visible rather than folding into one number.

The task

The deliverable is an installable torch-native package fastcluster exposing one function, dbscan2d(X, eps, min_samples), that takes a float32 tensor of 2D points and returns an int32 label per point, with -1 for noise. The contract fixes everything a fast implementation might be tempted to bend. A core point has at least min_samples neighbors within eps, counting itself. Clusters are the connected components of core points. A non-core point within eps of a core point joins the cluster of the nearest one, ties to the lowest index. "Within eps" is defined down to the float: squared distances in float32 with no fused multiply-add, compared against a float32 eps squared, so that boundary decisions reproduce across compilers and builds. The same input must give the same labels across repeated calls, thread counts, and processes. Invalid input raises.

The agent-visible gen.py produces the same four point-cloud families the grader draws from (Figure 1), at any size and seed, so local benchmarks have exactly the graded distributions; only the graded seeds are hidden. Each family scales its extent with the square root of the point count, so density stays fixed as the size grows and the smallest size is the most crowded picture of each family.

Figure 1. Four point-cloud families, generated and labeled. Top row: one realization of each family from the task's generator, shown as a 2,500-point subsample, each at a size where the family's structure is visible. Bottom row: the same points with their DBSCAN labels at the family's eps and min_samples, each cluster in one of the five chart hues cycled by cluster id, noise muted. Headings give the size, cluster count and noise share of the full realization. Every graded input is a fresh realization of one of these at 10,000 to 10,000,000 points.

The bottom row of Figure 1 shows what the contract makes of those points. The density choice does real work here. Uniform noise at eps 0.5 sits at the percolation threshold, where a point's expected neighbor count is about the min_samples of five: the realization breaks into 244 small clusters and 7% noise, and a single wrong boundary decision changes the partition, which is exactly what the hidden contract suite is built to catch. The blobs are drawn at 100,000 points, where their islands are large enough to see; three pairs of centers land close enough to touch, so the contract correctly reads seventeen clusters rather than twenty. At the smallest graded size the same family collapses to four, because the centers are drawn from a square only thirteen units wide. The sine curve is one cluster end to end, with no noise at all, and its whole difficulty is that a grid cell of width eps holds almost nothing.

Figure 2 is the picture behind those rules. Every point is one of three things: a core point, with at least min_samples neighbors inside its eps circle; a border point, not core itself but inside a core point's circle; or noise. Clusters are the connected components of core points, and each border point joins the cluster of its nearest core point.

Figure 2. Core, border, noise. The classic DBSCAN picture. Each dashed circle is an eps neighborhood: the core point has at least MinPts points inside its circle (itself included); the border point sits inside a core point's circle but has too few neighbors of its own; the noise points have no core point in reach.

The whole algorithm fits in a few lines. This is the contract's semantics written directly, with none of the structure a fast engine exploits: every pairwise distance, a flood fill over core points, then the border rule. The one float detail the contract adds, that squared distances are computed in float32 with no fused multiply-add, is left out here for readability.

python

def dbscan2d(X, eps, min_samples):
    d2 = ((X[:, None] - X[None, :]) ** 2).sum(-1)     # every pairwise squared distance
    within = d2 <= eps * eps
    core = within.sum(1) >= min_samples               # counting the point itself
    labels = np.full(len(X), -1)
    k = 0
    for seed in np.flatnonzero(core):
        if labels[seed] != -1:
            continue
        labels[seed] = k                              # flood-fill one component of core points
        frontier = [seed]
        while frontier:
            for j in np.flatnonzero(within[frontier.pop()] & core):
                if labels[j] == -1:
                    labels[j] = k
                    frontier.append(j)
        k += 1
    for i in np.flatnonzero(~core):                   # border: nearest core point,
        near = np.flatnonzero(within[i] & core)       # ties to the lowest index
        if len(near):
            labels[i] = labels[near[np.argmin(d2[i, near])]]
    return labels                                     # noise stays -1

def dbscan2d(X, eps, min_samples):
    d2 = ((X[:, None] - X[None, :]) ** 2).sum(-1)     # every pairwise squared distance
    within = d2 <= eps * eps
    core = within.sum(1) >= min_samples               # counting the point itself
    labels = np.full(len(X), -1)
    k = 0
    for seed in np.flatnonzero(core):
        if labels[seed] != -1:
            continue
        labels[seed] = k                              # flood-fill one component of core points
        frontier = [seed]
        while frontier:
            for j in np.flatnonzero(within[frontier.pop()] & core):
                if labels[j] == -1:
                    labels[j] = k
                    frontier.append(j)
        k += 1
    for i in np.flatnonzero(~core):                   # border: nearest core point,
        near = np.flatnonzero(within[i] & core)       # ties to the lowest index
        if len(near):
            labels[i] = labels[near[np.argmin(d2[i, near])]]
    return labels                                     # noise stays -1

Semantically that is what the grader compares against, and it is quadratic in the number of points. The task is everything between this and ten million points in a few seconds.

There is no starter code. /app/src begins as a git repo containing the contract and nothing else. The image has torch 2.8 (CPU build), numpy, gcc and ninja, and no package index; the agent writes the package, its own tests, and its own timing harness. check runs the contract's micro cases and a determinism sweep against the installed package; bench times it exactly the way the grader does, on the agent's own seeds; clock reports the budget. Two variants share the contract. dbscan-cpu grades CPU tensors on four cores with sixteen gigabytes. dbscan-cpu-gpu adds an L40S: a CUDA input must be clustered on the GPU and returned there, and the task score is the sum of the CPU and CUDA device scores.

Grading runs on a fixed grid: the four families at four sizes, 10,000 to 10,000,000 points, two held-out realizations per axis, sixteen axes per device. Small sizes are timed as batches of back-to-back calls (fifty at 10,000, ten at 100,000, two at 1,000,000) so the clock is meaningful. Each axis has a time budget of thirty seconds plus twenty microseconds per point, capped at 400 seconds; an axis that runs out scores zero speed and the larger sizes of that family are skipped.

Building the environment

Speed benchmarks grade code, not files, so the leaderboard is a queue with workers. submit seals git archive HEAD of /app/src (only committed files travel), uploads it, and returns an id immediately. A worker claims the job, builds the package with the grader's exact pip command inside a fresh container of the tests image, runs the hidden contract suite (fifteen exact passes, adversarial constructions, determinism across one, two and four threads and across processes), then times the sixteen axes and records peak memory of the clustering process. The signed record carries the public score, the per-axis speed and memory, and each gate's verdict. Grading takes three to five minutes and the agent keeps working; the only feedback is that record. There is no private split: every graded realization is fresh, so overfitting the public pool is not a strategy, and submissions are unlimited.

When the run ends the verifier trusts nothing agent-side. It reads the sealed records, checks each signature and hash, takes the best public score (earliest on ties), and regrades that exact code on its own pool in its own container. That regrade is the final score. A run with no graded submission is graded from the final tree in /app/src instead.

Three decisions carry the task's character. The agent starts from the contract, not a baseline, so the design is its own. The score is raw: no curve, no reference in the formula, and the leaderboard prints speed and memory per axis next to it, so a reader can see the trade-offs rather than a number. And memory is a band, not a co-equal objective: full credit inside the budget, proportionally less above it, and no reward for frugality beyond it.

Evaluation

Per axis the score is throughput times the memory factor, then the axes combine by geometric mean per device:

\mathrm{axis} = \mathrm{speed}_{\mathrm{Mpts/s}} \times \min\!\left(1,\; \frac{\mathrm{budget}}{\mathrm{peak\ memory}}\right)

The memory budget is 0.6 GB plus 256 bytes per point on CPU (2 GB plus 256 bytes per point on CUDA), measured on the whole process including the torch runtime. Every axis counts equally, which is what the geometric mean buys: a family that cannot be handled in budget zeroes the whole device, and a large gain on one axis cannot paper over a loss on another. On the CPU variant the task score is the CPU device score; on CPU+GPU the two device scores add. Gates come first and are binary. A package that fails to build, disagrees with the reference partition on any axis, is non-deterministic, or spawns descendant processes during a timed call scores zero for that submission, with the reason in the record. Timing takes the best of the batched calls per realization with a 25 ms floor, and once an axis falls under 0.05 Mpts/s the larger sizes of that family are skipped.

The reference engine is a grid-based C++ extension with OpenMP. Replayed on the platform's venue it grades 15.9 on CPU and 96.2 on CPU+GPU by the verifier, and 14.3 and 92.1 on the leaderboard. Those are calibration rows: they say what the venue does with a competent conventional engine, and they enter no formula.