AlgoTune: graph isomorphism

An AlgoTune task as a project (PER-305): agents make src/solver.py fast, and the grader times it on problems drawn from a secret seed, checking every answer with the task's own verifier. AlgoTune (MIT) is a benchmark of numerical Python functions to speed up; this project is its task graph_isomorphism, built from the platform's AlgoTune kit (sdk/algotune in the platform's repository, whose README says how to add another task).

File	What it is
autoresearch.toml	the metric (wall_ms, minimized, MMI 6%), runner class cpu-s, editable src/**, K = 15
PROGRAM.md	instructions for the agents: the task, its check, and what counts as cheating
CONTRACT.md	the worker HTTP contract (the template's)
src/solver.py	the solver being improved: AlgoTune's reference solve to start with
harness/worker.py	the frozen HTTP server: one Solver(), then solve(problem) per item, answers as JSON
requirements.txt	numpy, scipy, networkx and numba, pinned by hash (the worker's, and the grader's as grader/requirements.txt)
dockerfile.worker, compose.yaml	Python 3.13, one thread per numerics library; worker on core 0, grader on core 1
dockerfile.grader, grader/	the grader (grade.py), the task's upstream file, base.py's stand-in, the grader SDK (grader/arh_grader)
sample/params.json	the public parameters: 128 problems of sizes n 140 to 180, after 3 warmup problems

harness/, requirements.txt, dockerfile.*, compose.yaml, grader/grade.py, grader/requirements.txt and grader/AlgoTuneTasks/base.py are the kit's (mise run algotune:vendor).

How a run is scored

The grader draws 128 problems from the run's seed (rng("items")): for each a size n between 140 and 180 and a 32-bit seed, never the same seed twice, and makes the problem with the task's generate_problem(n, seed). It sends 3 untimed warmup problems of the same kind (rng("warmup")), then each problem once, one a request, and times the requests; wall_ms is their total. Then it checks every answer with the task's is_solution against the problem as the worker got it (through JSON). One wrong or missing answer makes the run invalid.

On the platform it then times and checks the public sample's problems as arh run draws them (the public seed and sample/params.json, which the grader's image keeps) and reports their total as public, which never counts for the verdict. That pass is best effort: at most 60 s, and it ends 20 s before the run's 300 s are up.

The held-out parameters (projects/algotune-graph-isomorphism-heldout/params.json in the platform's repository, outside this directory) are the public sample's: what agents never see is each verification's seed, which picks every problem. Startup is capped, not folded: nothing can be computed before the problems arrive. There is no null worker (no table can answer a random problem), so nothing but review catches an impossibly fast candidate; K = 15 (the steps of a 10x speedup) holds anything faster than that for the author's review (PROGRAM.md).

Sizing

128 problems of n 140 to 180 nodes. The reference solve takes about 120 ms at n 140 and 170 ms at n 160 (a 61-82 KiB problem), so the solve dominates the transfer. On the eval VM a problem took about 290 ms (9.3 s for 32), so a run's timed part is about 37 s. Generating a problem costs about 0.24x a solve and checking one 0.12x, so the run, start to checks, takes about 62 s; run_timeout_s = 300 is 3x that plus the public pass's 60 s cap and 20 s margin. At n 70 to 100 (1.5 s timed) the sd of d was 20.8%; at n 140 to 180 with 32 problems (9.3 s) it was 11.9%.

The grader image

Built from grader/, dockerfile.grader and sample/ (the image keeps the public sample). The live reward version's image is built by its application's conformance report from the project repository's commit (PER-305), and its digest is the version's; changing any of those files needs a new build and a new reward version. The image installs grader/requirements.txt with the same pip step as the worker's (and deletes site-packages' tests/ the same way), so it has the workers' package layer, byte for byte (PER-316): an evaluation carries it once.

Running it

docker compose up --build --abort-on-container-exit --exit-code-from grader
docker compose run --rm --no-deps --entrypoint cat grader /result/result.json
docker compose down --volumes

compose.yaml pins the worker to core 0 and the grader to core 1. The first build downloads the packages from PyPI. arh run (the platform's CLI, cli/README.md) runs the same three commands and prints the result. To compare a change against the baseline in alternating runs, as the platform does, commit the baseline and run, with the change in the working tree:

arh run --pairs 10 --against HEAD

It prints each pair's gain in MMIs and what the platform's decision rule would say on those pairs: advisory only, since it's the public sample on this machine.

Noise and the MMI

Measured on the eval VM path (services/controller/tests/test_algotune_cluster.py, the baseline against itself, every pair run, cpu-s VM; commit acfe6bf, whose slimmer grader let the two images fit prepare; the worker image is the same as here but for site-packages' tests/). Node load is the node's /proc/loadavg sampled every 30 s by a pod on it; the per-pair analysis is in PER-305's pull request.

run	node, time	load1	prepare s	inputs bytes	ms per run	sd of d
1 (n 70-100, 24 items; superseded)	r630, 18:11-18:16Z	34-37 (mean 36)	90	931,752,960	1,542	20.8%
2 (n 140-180, 32 items)	r630, 18:36-18:46Z	33-60 (mean 48)	110	931,752,960	9,298	11.9%

sd 11.9% at 32 problems a run. At 128 (4x the timed work) the estimate was sd 6.0-6.8% (a provisional MMI of 14%, K 6). The conformance report's noise profile (report 16, PER-305: the dedicated timing core, 10 pairs) measured sd 2.66%, a floor of 5.32%: MMI 6%, K 15.

At the compute nodes' usual load, 1.4 to 2.5 runnable threads per core, sd(d) didn't follow node load: the per-pair correlations of |d| with load1 were weak and of mixed sign. Heavier contention does raise it. At 4 to 8 threads per core the shared pool's sd was 2 to 3 times higher (for gge, 30% against 12% on a dedicated core at the same hours), which is why verifications are to run on a dedicated timing core (PER-205, PER-215). What remains is run-to-run noise over seconds, and it falls with more timed work per run, roughly as 1/√work; medians and more pairs don't lower it. The MMI is twice the sd of d, rounded up; K = floor(0.9 / MMI), the whole steps of a 10x speedup. The estimates scale the measured sd by 4^-0.4 to 4^-0.5 (the exponent seen when the timed work grew); the definitive MMI and K come from baseline runs at this sizing on the dedicated timing pool: the noise profile of the project's conformance report, before it goes live.

Licences

What	Source	Licence
grader/AlgoTuneTasks/graph_isomorphism/graph_isomorphism.py (git blob fa4fedfcbe0a2a6ab3a91e4b9bcb040d4ee11042) and description.txt (blob d97dd3932181b67f035f4cd394929068a3d8a513)	oripress/AlgoTune at dff9914c10800c7a031c9e8c3d4d1c8cd1b38906, verbatim	MIT, Copyright (c) 2025 Ori Press and the AlgoTune contributors
src/solver.py (the baseline)	the reference solve of the same file, verbatim	MIT, as above
grader/AlgoTuneTasks/base.py	written for this platform after upstream's AlgoTuneTasks/base.py interface (Task, register_task)	MIT, as above, for the interface
numpy, scipy, networkx, numba, llvmlite (requirements.txt)	PyPI, installed in the images, not vendored	BSD-3-Clause, BSD-3-Clause, BSD-3-Clause, BSD-2-Clause, BSD-2-Clause (its wheel bundles LLVM: Apache-2.0 WITH LLVM-exception; numpy's and scipy's bundle OpenBLAS, BSD-3-Clause)
Python 3.13 (python:3.13-slim-bookworm)	Docker Hub, the images' base	PSF-2.0
Problems	generated by the task's generate_problem from seeds: no external data

AlgoTune's licence, verbatim (copyright and permission notice), is grader/LICENSE-AlgoTune and harness/LICENSE-AlgoTune: it ships in the grader's and the worker's images with the code they carry. The project is public, as its upstream is MIT. On the platform it has no upstream ([project].upstream left out): its repository is its own, an admin's import based on this directory, with no pull mirror.