AlgoTune: graph isomorphism

An AlgoTune task as a project (PER-305): agents make src/solver.py do less work, and the grader counts the instructions it takes on each problem of a held-out set, 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). Until PER-378 the project timed the solver (wall_ms); now the score is work done, not wall time: fewer instructions (vectorising, for example) count, parallelism and cache layout don't.

File	What it is
autoresearch.toml	the metric (instruction_ratio, a deterministic count, minimized, MMI 2%), runner class cpu-s, editable src/**, K = 25
PROGRAM.md	instructions for the agents: the task, its check, how the solver runs, and what counts as cheating
CONTRACT.md, 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: it hands the files of src/ to the grader and runs none of them
requirements.txt	numpy, scipy, networkx and numba, pinned by hash: the grader's packages (grader/requirements.txt), which the solver runs on
dockerfile.worker, compose.yaml	the worker, Python 3.13 with no packages; worker on core 0, grader on core 1
dockerfile.grader	the grader's image: QEMU 11.1.2 and the counting plugin built from source, Python 3.13 and the packages
grader/grade.py	the grader: counts the solver on each problem, checks every answer, writes the result
grader/driver.py	the program the grader runs under the emulator: imports the environment and the solver, answers each problem
grader/measure.py	the refs: a solver's counts on a set, as items.jsonl's instructions
grader/sandbox.py, grader/native/	the instruction-count kit (sdk/insncap): the sandbox, the plugin insncap.c and the emulator's patch
grader/task.json, grader/AlgoTuneTasks/	the task's name and environment, its upstream file, base.py's stand-in
grader/arh_grader/	the grader SDK
sample/items.jsonl	the public sample: 24 problems, each {"n", "seed", "instructions"}

harness/, requirements.txt, dockerfile.*, compose.yaml, grader/grade.py, grader/driver.py, grader/measure.py, grader/requirements.txt and grader/AlgoTuneTasks/base.py are the AlgoTune kit's (mise run algotune:vendor); grader/sandbox.py and grader/native/ are the instruction-count kit's (mise run insncap:vendor).

How a run is scored

The set is an items.jsonl, one problem a line: {"n": 160, "seed": 123456, "instructions": r}. Locally it is the public sample, sample/items.jsonl (24 problems); on the platform the held-out set (128 problems, projects/algotune-graph-isomorphism-heldout/items.jsonl in the platform's repository, outside this directory). The grader makes each problem with the task's generate_problem(n, random_seed=seed): a random graph of n nodes (each edge with probability 0.3) and the same graph with its nodes relabelled at random, n 140 to 180. r is the incumbent's count on that problem.

1. The worker hands over the solver: the files of src/ (at most 64, 1 MiB in all, solver.py among them). The grader writes them, read-only, to /tmp/algotune/src.
2. The grader runs grader/driver.py in its own Python 3.13 under QEMU's user-mode emulator with the counting plugin, in the instruction-count kit's sandbox with its tree profile. The driver imports the task's environment (grader/task.json), then gets framed items, each sent once it has answered the one before: go (import the solver, make one Solver(), answer ready), each problem as one line of JSON (answer solve(problem) as one line of JSON), end.
3. The plugin reports the count at each item's start. The solver's import, I, runs from go to the first problem; problem i's work, P_i, from its start to the next item's. The environment's import, before go, isn't the solver's work and isn't counted.
4. The grader checks every answer natively with the task's is_solution, against the problem as sent. One wrong or missing answer makes the run invalid.

Problem i scores (n_items * P_i + I) / r_i: its instructions, with an even share of the solver's import, over the incumbent's, measured the same way (grader/measure.py). The incumbent scores exactly 1.0 on every problem. instruction_ratio is the mean over the problems, to minimize; the result also reports instructions (I plus every P_i), import_instructions (I) and each problem's score.

A run is invalid, with its kind, at the first of: the worker's (the SDK's kinds, timeout, schema, ...; bad_source for files that aren't a solver); the solver's (over_budget, over_item_budget, escape, threads, solver_timeout, output_too_large, solver_failed); the answers' (wrong); invalid_set or grader_error (the platform's problem). PROGRAM.md, "Objective", says what each means for the solver.

The refs are the incumbent's: no attempt has been accepted on this project yet, so that is this directory's src/, AlgoTune's reference (networkx's VF2 GraphMatcher). The sample's 24 problems were drawn from random.Random("algotune-graph-isomorphism-sample"), the held-out set's 128 from secret seeds drawn once (Python's secrets).

Budget and time

The incumbent takes about 650 million instructions a problem, its import's share included (P + I / n_items): about 15.6 billion over the sample and 83 billion over the held-out set. The environment's import, uncounted, is another 2.16 billion a run.

Two caps bound a run:

• a problem: a score over 4 (ITEM_FACTOR), four times the incumbent's count on it, fails the run as over_item_budget. The solver's import is part of every problem's score, so a heavy import counts against every problem.
• the run: the emulator stops the solver past CAP_SLACK (30 billion instructions, for the environment's import and then some) plus 4 times the incumbent's whole count (I and every P_i, the refs' sum over n_items): over_budget. A solver within 4 times every ref is within it; it is the backstop that stops a solver running away on one problem, about 360 billion instructions on the held-out set.

The emulator runs at about 50 to 200 million instructions a second, depending on the host's load. On a loaded 48-core build host, grader/measure.py took 102 s on the sample and several minutes on the held-out set. run_timeout_s is 7200 s: the score doesn't depend on speed, so the deadline leaves room for a contended pool. A solver that ran to the run's cap would take 30 minutes to 2 hours of emulation; on the slowest hosts the wall-clock backstop (solver_timeout) ends it first. build_timeout_s is 1800 s, for building the emulator.

The grader image

Built from grader/ and dockerfile.grader. It builds QEMU 11.1.2's user-mode emulator from the release tarball, pinned by its SHA-256 and fetched from download.qemu.org ([build] egress), with the kit's patch (grader/native/qemu.patch), and the plugin (grader/native/insncap.c) against it. It installs grader/requirements.txt, the packages the solver runs on, without their tests/, and compiles them and the standard library to hash-based .pyc with the hash seed fixed: under the tree profile every file has the same time, so a timestamp-based .pyc would never match its source and every import would compile it again. The step sets every file's time, so every build is the same bytes. The worker's image has no packages: it only serves src/.

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.

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

The first build downloads QEMU's tarball and the packages and builds the emulator (about 2 minutes on a quiet machine). arh run (the platform's CLI, cli/README.md) runs the same three commands and prints the result. The count is deterministic, so one run is the number: there is nothing to repeat or pair.

grader/measure.py counts a solver on a set the way a run does and prints the set again with each line's instructions set to that solver's count: how the refs were made, and a way to see a solver's count on each problem. In the grader's image:

docker compose build grader
docker run --rm -v "$PWD/src:/w/src:ro" -v "$PWD/sample:/w/set:ro" \
    algotune-graph-isomorphism-grader python measure.py /w/src /w/set > counts.jsonl

Divide each line's instructions by the sample's to get the solver's score on that problem.

Determinism and the MMI

The same solver on the same problems counts the same instructions on every run and every machine, so the metric is deterministic (deterministic = true): one pair a verification, and the noise floor is the platform's minimum for a deterministic metric, 0.1%. The MMI is 2%, one instruction in fifty; K = 25, a solver twice as cheap (a gain of 0.5), holds anything larger for the author's review (PROGRAM.md).

The count is exact and out of the solver's reach because of what the instruction-count kit adds to the emulator (grader/native/insncap.c's header is the specification):

• The tree profile: the solver reads a read-only tree (the grader's Python and packages, the C library, its own files) that looks the same on every host: normalised stat, sorted directory listings, nothing outside the tree (ENOENT), constant identities. Clocks read the count, getrandom comes from a fixed seed, the time-stamp counter steps by a fixed amount, and the emulated CPU is fixed (Haswell-noTSX), so numpy's dispatch takes the same path everywhere. Nothing the solver can observe changes from run to run, so neither does its count. A second thread ends the run (threads).
• The range check: the emulator doesn't isolate the guest's memory from its own, and Python can make a pointer (ctypes, numpy). The patched emulator checks every load and store the solver makes against its reserved space before it happens and ends a run that reaches outside it (escape), so the count can't be read or written (sdk/insncap/README.md lists every path QEMU takes from a guest address to a host one, and what covers it).
• Framed items: the grader sends each problem only after the answer to the one before, and the plugin reports the count at each item's first read. Each problem's work is apart, and the solver can't see a problem before it has answered the last.

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 grader's image, 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)
QEMU 11.1.2, patched (grader/native/qemu.patch)	https://download.qemu.org, built from its release tarball in the grader's image, not vendored	GPL-2.0-only
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.