group-testing: find the defectives in the fewest tests

A count project (PER-363), and the first to use the grader's oracle. Agents improve a tester (src/) that finds an instance's defective items by pooled tests: "is any item of this pool defective?".

• The count can't be reported away. Each test is a call to an endpoint the grader serves and counts itself.
• The priors are the opening. The tester sees each item's prior probability of being defective, which the baseline, binary splitting, ignores.
• The score is the tests an instance takes, relative to binary splitting's, averaged over 500 held-out instances (relative_tests, minimized).

File	What it is
autoresearch.toml	the metric (relative_tests: a count, minimized, MMI 0.02 absolute, deterministic, epsilon 0), runner class cpu-s, editable src/**, K = 25; no upstream; public
PROGRAM.md	instructions for the agents: the tester, its budget, the instances, what counts as cheating
CONTRACT.md, CONTRACT-*.md	the template's worker contract ("The oracle" included) and its language companions, verbatim
src/tester.py	the tester being improved: binary splitting to start with
harness/worker.py	the frozen HTTP server: it imports src/tester.py, and gives find its test, one call to the grader's oracle at AR_ORACLE_URL
grader/grade.py	the grader: it serves the oracle, checks every answer and scores the counted tests
grader/arh_grader	the grader SDK, release 5 (sdk/grader/src verbatim): Oracle
sample/items.jsonl	the public sample: 40 instances, their defectives shown
dockerfile.worker, dockerfile.grader, compose.yaml	Python 3.13, standard library only; the worker on core 0 and the grader on core 1, as runner class cpu-s places them; the worker's AR_ORACLE_URL=http://grader:8081
LICENSE	MIT

The instances

sdk/group-testing/instances.py (in the platform's repository) draws them. Each instance has:

• n items, 64 to 512;
• each item's prior, from one of three families (PROGRAM.md, "Data");
• the defectives, each item drawn defective with its prior, redrawn until there is at least one;
• baseline, the tests binary splitting makes on the instance, which the generator counts with the baseline's algorithm.

The sample is drawn with a fixed seed. The held-out set is drawn with a secret one, never recorded, so nobody can regenerate it.

Set	Instances	Families (uniform / two-tier / log-normal)	Defectives, mean	Baseline tests, mean	Entropy bound / baseline, mean
sample	40	17 / 14 / 9	7.40	61.95	0.82
held-out	500	177 / 145 / 178	6.37	54.19	0.75

The entropy bound is the sum of the items' binary entropies. Adaptive tests can't beat it in expectation, so a tester that uses the priors well has about a quarter of the baseline's tests to win.

How a run is scored

1. The instances are checked: their fields, n, the priors, the defectives (sorted, distinct, in range, at least one) and baseline. Otherwise the run is invalid.
2. One instance a request. The grader opens an oracle session for the instance and sends the worker its token, n and the priors. Each test is {"pool": [...]}, answered {"positive": ...}.
   • The oracle counts every test before answering it.
   • A pool that isn't 1 to n distinct indices in range is an invalid query: answered 400, and counted.
   • The session closes once the grader has read the answer: a later test is refused, and not counted.
   • The instance's tests are capped at 2n + 64.
3. An instance fails if its answer isn't exactly its defectives, sorted (wrong), if it went over its cap (oracle_cap), or if it failed in any of the SDK's ways (no answer, not a list of integers). Any failure makes the run invalid.
4. Otherwise relative_tests is the mean over the instances of their tests divided by baseline, in the file's order; each instance's ratio is its item score. The secondary values are:
   • tests, the mean tests an instance;
   • query_bytes and answer_bytes, the canonical JSON the tests moved.

The MMI

The metric is deterministic: the oracle's count depends only on the instances and the tester's pools, and testers must be deterministic too (PROGRAM.md). Its floor is the held-out set's sampling error, twice the bootstrap standard error of the item scores.

At the baseline, every instance scores exactly 1.0, so the floor there is the platform's minimum. That says nothing about how far a better tester's gain generalizes, so the MMI comes from one instead. A tester that groups items by prior mass and splits within each group scores 0.80 on the held-out set, and its item scores' floor is 2 x 0.0093 = 0.019. So the MMI is 0.02: 2% of binary splitting's tests, with epsilon 0.

Scoring each instance against its own baseline keeps the large instances from drowning the rest. Counted in raw tests, the baseline's mean on the held-out set would have a floor of 4.5 tests, 8.4% of its 54.19.

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 baseline scores relative_tests 1.0 on the public sample (61.95 tests an instance). arh run (the platform's CLI, cli/README.md) runs the same three commands and prints the result.

Licences

What	Source	Licence
everything	this project	MIT
Python 3.13 (python:3.13-slim-bookworm)	Docker Hub, the images' base	PSF-2.0

The project has no upstream ([project].upstream left out, ADR-0004). Its repository on the platform is its own, based on this directory in one commit, with no pull mirror.