Order Is a Hidden Input: A Permutation Verdict for Agent Patches

An agent patch that passes your suite once has passed exactly one sample of a distribution nobody wrote down: the execution order of your tests, and every piece of process state that order exposes. Module-level caches, os.environ, temp directories, class attributes, rows left in a shared SQLite file, stubs installed by an autouse fixture.

So the useful question is not "does the patch pass?" It is "at what rate does it pass across orderings, and which test is it coupled to?" Both are measurable. The measurement costs one seeded shuffle, one state probe, and a table that converts pass rates into a verdict.

What follows is a reference implementation: pytest hooks for counting, a shell sweep for running two trees, and a decision table with defaults you can justify before you ever look at a result.

The failure mode, precisely

An agent asked to fix a parser bug adds test_rejects_empty_header. The test imports app.cache at module scope, and a test file collected earlier already warmed that cache with a valid header. Your suite collects alphabetically, so the new test passes. On a clean machine, in isolation, it fails.

Nothing in that story is exotic. The patch is not wrong because the assertion is weak; the patch is wrong because the test has an undeclared dependency on a global that another test mutates. A single full-suite run cannot see this, because it samples one ordering out of n!.

Two consequences. First, a green run is evidence about one permutation, not about the patch. Second, pytest -p no:randomly-style stability is not the same as order-independence: a fixed order is a constant, and a constant hides a dependency perfectly.

Step 0 — Quarantine flaky tests by fingerprint, not by name

Before any sweep, separate "this test is nondeterministic" from "this test depends on order." Otherwise every flake looks like an ordering bug and every ordering bug looks like a flake.

The cheap discriminator: rerun the same seed. Same seed, different outcome means the variance is not from order, so the test belongs in quarantine and not in the verdict.

Make the quarantine expire by content, not by date. Hash the test body plus the exception signature you saw:

# quarantine.py — reference helper
import hashlib, inspect, json, pathlib

STORE = pathlib.Path('perm/quarantine.json')

def fingerprint(fn) -> str:
    body = inspect.getsource(fn)
    return hashlib.sha256(body.encode()).hexdigest()[:16]

def is_quarantined(fn, signature: str) -> bool:
    data = json.loads(STORE.read_text()) if STORE.exists() else {}
    return data.get(fn.__qualname__) == [fingerprint(fn), signature]

Edit the test, and the fingerprint changes, so the quarantine lapses automatically and the test re-enters the verdict. No calendar, no owner, no reminder to forget.

Step 1 — Shuffle with a seed you can replay

Do not trust a random-order plugin you cannot reproduce. Twenty lines are enough, and the seed becomes part of your CI artifact name.

# perm_shuffle.py — load with: pytest -p perm_shuffle
import os, random

def pytest_collection_modifyitems(session, config, items):
    seed = int(os.environ.get('PERM_SEED', '0'))
    random.Random(seed).shuffle(items)
    print(f'perm_shuffle: seed={seed} n={len(items)}')

Run it as PERM_SEED=7 pytest -q -p perm_shuffle. Seed 0 is a legitimate baseline if you make it the unshuffled order; I keep seed 0 reserved for "whatever pytest does by default" so the sweep always includes your current CI behaviour.

Step 2 — Probe the state order exposes

A pass rate tells you something is coupled. The probe tells you what. Snapshot a small, boring set of observable state before each test and compare after teardown.

# perm_probe.py — load with: pytest -p perm_probe
import json, os, pathlib, sys, tempfile

OUT = pathlib.Path(os.environ.get('PERM_OUT', 'perm/probe.jsonl'))
WATCH = ('app.cache', 'app.settings')
_before = {}

def snapshot():
    tmp = pathlib.Path(tempfile.gettempdir())
    return {
        'env': dict(os.environ),
        'tmp': sorted(p.name for p in tmp.iterdir()),
        'modules': len(sys.modules),
        'cached': {m: id(sys.modules[m]) for m in WATCH if m in sys.modules},
    }

def record(kind, **kw):
    OUT.parent.mkdir(parents=True, exist_ok=True)
    with OUT.open('a') as fh:
        fh.write(json.dumps({'kind': kind, **kw}) + '\n')

def pytest_runtest_setup(item):
    _before[item.nodeid] = snapshot()

def pytest_runtest_teardown(item, nextitem):
    before = _before.pop(item.nodeid, None)
    after = snapshot()
    if before is None:
        return
    changed = sorted(k for k in after if before[k] != after[k])
    if changed:
        record('leak', node=item.nodeid, fields=changed)

def pytest_runtest_logreport(report):
    if report.when == 'call':
        record('outcome', node=report.nodeid, outcome=report.outcome)

Two practical notes. Filter env through an allowlist, or every run reports the PERM_SEED it just set. And id() comparison on module objects catches re-imports, which is usually a bigger problem than leaked dict keys.

Step 3 — Sweep two trees, K seeds each

The verdict is comparative. You need the patched tree and the pre-patch tree measured with the same K and the same seeds, or you cannot tell a new coupling from an old one the patch merely exposed.

run_sweep() {
  tree=$1; k=$2; label=$3
  ( cd "$tree" && for s in $(seq 1 "$k"); do
      PERM_SEED=$s PERM_OUT="perm/$label-$s.jsonl" \
        python -m pytest -q -p perm_probe -p perm_shuffle
    done )
}

run_sweep ../repo-baseline 20 baseline
run_sweep ../repo-patched  20 patched

Choosing K: on a suite under two minutes, K=20 is affordable; on a ten-minute suite, K=5 still beats K=1. Record K in the artifact name so nobody compares a 5-seed verdict with a 20-seed one.

Step 4 — Convert pass rates into a verdict

Aggregate per test, not per run. A run-level pass/fail hides the one test whose rate moved.

# verdict.py
import collections, glob, json

def load(pattern):
    runs = collections.defaultdict(dict)
    for path in glob.glob(pattern):
        seed = int(path.rsplit('-', 1)[1].split('.')[0])
        for line in open(path):
            rec = json.loads(line)
            if rec['kind'] == 'outcome':
                runs[seed][rec['node']] = rec['outcome']
    return runs

def rate(runs, node):
    seen = [runs[s][node] for s in runs if node in runs[s]]
    return sum(v == 'passed' for v in seen), len(seen)

base, patched = load('perm/baseline-*.jsonl'), load('perm/patched-*.jsonl')
nodes = set().union(*[set(r) for r in base.values()])
for node in sorted(nodes):
    b, p = rate(base, node), rate(patched, node)
    if b != p:
        print(f'{node}: baseline={b[0]}/{b[1]} patched={p[0]}/{p[1]}')

Read the output against a table you wrote before running the sweep:

Observation (K=20)	Reading	Action
20/20 baseline, 20/20 patched	order-independent at this sampling depth	accept
20/20 baseline, 12/20 patched	patch introduced order coupling	block, require the test to isolate its state
15/20 baseline, 15/20 patched	pre-existing coupling, unchanged	do not blame the patch; fund a cleanup ticket
20/20 baseline, 20/20 patched, new leak records	patch ships passing tests that poison neighbours	block; the leak may only surface on the next patch
15/20 baseline, 19/20 patched	patch added global state that masks another test's leak	review before merge; masking is not fixing
same seed, two outcomes	flake, not order	quarantine by fingerprint, exclude from rate

The last row matters more than it looks. If you let flakes stay in the denominator, every verdict drifts toward "the suite is unreliable," and unreliable suites stop gating anything.

Step 5 — Attribute the coupling to a neighbour

A rate of 12/20 is a diagnosis, not a fix. Get the culprit from the recorded order of a failing seed, then check neighbours one at a time.

# target fails under PERM_SEED=9; grep suspects from the recorded order
PERM_SEED=9 pytest -q -p perm_shuffle --collect-only | grep -B5 test_rejects_empty_header

# two-test minimisation: run target alone, then target + each suspect
pytest -q tests/test_parser.py::test_rejects_empty_header
pytest -q tests/test_parser.py::test_rejects_empty_header tests/test_cache.py::test_warm

If target plus one neighbour reproduces the failure and target alone does not, you have the coupling and usually the line responsible: app.cache.get returning a value the neighbour wrote. That is a one-line fixture change, not a test-suite rewrite.

Where a free tier actually helps

Disclosure: This article was prepared as part of MonkeyCode's product outreach.

The sweep is the expensive part: K × 2 full-suite runs, sequential, mostly waiting. MonkeyCode's free model access and free server option (both availability claims from the operator; no quotas, hardware, or duration guarantees are stated here) fit two narrow jobs in this workflow rather than the whole workflow.

1. The free server runs the sweep. It is a long, boring, CPU-bound loop whose output is JSONL. You do not need a fast machine, you need a machine that stays up for forty runs.
2. Free model access drafts the boring text around the data: an env allowlist for the probe, a first-pass grouping of leak records by changed field, and a draft of the "pre-existing coupling" ticket body from the verdict table row.

What a model should not do here is decide the verdict. The table above is deterministic, and a model that "interprets" a 15/20 versus 15/20 result will happily invent a cause. Keep the decision in the script.

If you want to try it, start with K=5 locally to confirm the hooks fire, then move the full sweep; the free server is the least interesting part of this article and the seed loop is the part that finds bugs.

Limitations, and who should skip this

• Shuffling inside one process does not cross worker boundaries. Under pytest-xdist, shuffle per worker and record the worker id, or the sweep reports a mix it cannot attribute.
• Session-scoped fixtures that build expensive resources make K × runtime unaffordable, and shuffling around them tests the fixture's lifetime rather than your patch.
• Timing, concurrency, and network interference are invisible to a permutation sweep. A test that fails only under load will keep passing all twenty seeds.
• Sampling is not proof. 20/20 means "no coupling found at depth 20," which is a weaker claim than "order-independent."

Skip this approach if your suite is a sequence of stateful user journeys where order is the semantics being tested, if you cannot produce a pre-patch tree, or if the suite already sits at the CI ceiling. In those cases, a fixed order plus the fingerprint quarantine gets you most of the value at none of the multiple.

For everyone else: one seeded shuffle, one probe, two trees, twenty seeds. If the patch's pass rate does not move, you have earned the word "passes."