AlgoTune: graph global efficiency

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_global_efficiency, 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 14%), runner class cpu-s, editable src/**, K = 6
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: 96 problems of sizes n 150 to 220, 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 96 problems from the run's seed (rng("items")): for each a size n between 150 and 220 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 180 s are up.

The held-out parameters (projects/algotune-graph-global-efficiency-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 = 6 (the steps of a 10x speedup) holds anything faster than that for the author's review (PROGRAM.md).

Sizing

96 problems of n 150 to 220 nodes. The all-pairs shortest paths dominate a problem's time, not sending the graph: JSON encoding and decoding are a few percent of a solve. The baseline takes about 57 ms a problem on the eval VM (1.37 s for 24), so a run's timed part is about 5.5 s. The grader's own work per problem is about 0.17x a solve to generate it and 0.96x to check it (measured on a lease). That makes the run, start to checks, about 22 s; run_timeout_s = 180 is 3x that plus the public pass's 60 s cap and 20 s margin. There were 24 problems (1.4 s) when the noise was measured; 4x the timed work lowers the sd of d roughly as 1/√work (see below).

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	fuji-2, 15:40-16:30Z	not sampled	458	931,752,960	7,058	9.1%
2	fuji-2, 19:07-19:12Z	66-103 (mean 85)	66	931,752,960	1,372	13.3%

Pooled sd 11.4% at 24 problems a run. At 96 (4x the timed work) the estimate is sd 5.7-6.6%: MMI 14%, K 6, provisional.

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_global_efficiency/graph_global_efficiency.py (git blob 70171fe5827a11c8b6f40575c11e15f96a12f8c3) and description.txt (blob 9d7b5d86e47dc6e99b842a85e6dcddceab94c7fc)	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.