Order Beats Randomness: Bisecting Test Pollution in Agent Patches

Most tests labeled "flaky" in an agent-patch pipeline are not nondeterministic at all. They are order-dependent: they pass alone, and fail after some other test leaves shared state behind. Randomization masks that. Bisection names it.

The distinction matters because the two failures have opposite remedies. A genuinely random failure earns a temporary freeze. An order-dependent failure earns a fixture fix — and freezing it instead quietly locks in a bug that resurfaces the next time an agent inserts a file.

What follows is a reproduction-first workflow: prove the target passes alone, delta-debug the smallest prefix that breaks it, then classify the result before anyone touches a quarantine list.

1. Why agent patches make this worse

Agents insert files. Runners collect files in a fixed order, usually alphabetical by path. An agent that adds tests/test_auth_refresh.py next to an existing tests/test_z_session.py changes execution order for everything in between, without editing a single existing test.

Session-scoped fixtures are the usual carrier: a cache, a temp database, an env var, a module-level client. The new first test warms it in a way the old second test does not expect.

Then the pipeline sees test_rotate fail at head, pass at base, and pass when re-run alone. The label "flaky" follows. That label is close to meaningless — the test never was nondeterministic, the schedule changed.

2. Step 1: Establish the passing baseline

Before bisecting, prove the target passes in isolation, repeatedly, at head.

TARGET="tests/test_z_session.py::test_rotate" BASE_CMD=(python -m pytest -q -p no:randomly -p no:cacheprovider) for i in 1 2 3 4 5; do "${BASE_CMD[@]}" "$TARGET" >/dev/null 2>&1 || { echo "fails alone: order dependence is not the primary hypothesis"; exit 1; } done echo "passes alone 5/5 — continue to bisection" 

Three outcomes, and only one of them belongs in this workflow:

• Fails alone at head, passes alone at base → regression. Block the patch. Bisection is the wrong tool.
• Fails alone at both base and head → pre-existing. Separate ticket.
• Passes alone at both → continue to step 2.

-p no:randomly disables the plugin if your suite uses one. Without it, the isolation run and the pollution run are not comparable, and the whole exercise produces noise.

3. Step 2: Delta-debug the polluting prefix

Now find the smallest set of tests that, run before the target in their original order, still makes the target fail. Shrinking matters: a 400-test prefix is not usable evidence in a review comment.

"""Find a minimal set of tests whose presence before TARGET makes TARGET fail.""" import subprocess, sys PYTEST = [sys.executable, "-m", "pytest", "-q", "-p", "no:randomly", "-p", "no:cacheprovider"] def run(node_ids: list[str]) -> int: return subprocess.run(PYTEST + node_ids, capture_output=True, text=True).returncode def pollutes(prefix: list[str], target: str) -> bool: return run(prefix + [target]) != 0 def ddmin(items: list[str], predicate) -> list[str]: """Order-preserving delta debugging; returns a 1-minimal subset.""" n, current = 2, list(items) while len(current) >= 2: chunks = [current[i::n] for i in range(n)] for chunk in chunks: if predicate(chunk): current = chunk n = max(n - 1, 2) break else: if n >= len(current): return current n = min(n * 2, len(current)) return current def collect(root: str) -> list[str]: out = subprocess.run(PYTEST[:3] + ["--collect-only", "-q", root], capture_output=True, text=True).stdout return [ln.strip() for ln in out.splitlines() if "::" in ln] if __name__ == "__main__": target, root = sys.argv[1], sys.argv[2] candidates = [t for t in collect(root) if t != target] if not pollutes(candidates, target): print("no pollution under fixed order — investigate seeds/env instead") sys.exit(2) minimal = ddmin(candidates, lambda subset: pollutes(subset, target)) print("minimal polluting prefix:") for node_id in minimal: print(" " + node_id) 

Run it against the failing target and the suite root:

python orderbisect.py "tests/test_z_session.py::test_rotate" tests/ 

Illustrative output on a suite where a new file landed ahead of an older one:

minimal polluting prefix: tests/test_auth_refresh.py::test_first_login_creates_session 

The predicate is order-preserving on purpose. You are not asking whether the two tests are related. You are asking whether this schedule is sufficient. Reordering the minimized subset afterwards is a separate and useful follow-up: if the pair fails in either order, you have shared global state, not a directional dependency.

4. Step 3: Classify before you freeze

Do not act on the bisection result until it lands in a row of this table.

Only row 3 earns a freeze. Rows 1 and 2 are test bugs with a named owner, and they cost a fixture edit rather than a suppression entry. Mixing the rows is how quarantine lists grow monotonically while suite reliability stays flat.

5. Step 4: Encode the verdict so it cannot drift

Whatever you conclude, write it next to the test. A suppression marker with no reason is an invitation for the next agent to "fix" it by deleting the test.

import pytest # Order-dependent: fails only after test_first_login_creates_session, # which leaves a live session on the shared client. Tracked in #412. # Re-check once the client fixture is function-scoped. @pytest.mark.skip(reason="order-dependent pollution, see #412") def test_rotate(): ... 

Two properties make this note useful: a named issue, and a stated removal condition. A freeze without an exit condition is a permanent deletion with extra steps.

6. Where free compute and free model access fit

The bisection is cheap per target but embarrassingly parallel across targets — every node ID in a failing run is a candidate root cause. That is a short-lived, bursty workload rather than a steady one, which is the shape a free server option handles well. It is why I ran this batch step on MonkeyCode's free server: the machine only needs to exist for the length of a triage pass, then it can go away.

The model side is the second half. Sorting a minimized prefix into the table above is a reading task — does the polluting test touch a session fixture, an env var, a module-level cache, a temp path? Drafting that first pass across dozens of prefixes is well within what free model access handles, and a human then confirms it by reading the two tests side by side. Treat the draft as a hypothesis generator, not a verdict.

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

7. Limitations, and who should skip this

• Fixed-order bisection assumes a stable collection order. Suites that randomize by default need the order pinned first, or the minimized prefix means nothing.
• ddmin costs O(n log n) suite runs in the worst case. On a suite that takes twenty minutes, minimize at file level first, then drill into node IDs.
• Parallel execution breaks the premise. Under -n auto, tests share a worker schedule, not a fixed order. Run the bisection serially or not at all.
• Sharded CI, container-per-test, or worker-isolated setups already separate state. If your suite is that clean, you have this failure class handled and can skip the workflow.
• This finds pollution, not races. A failure that needs two threads and a specific interleaving will not shrink to a prefix.

The gate is not "is this test flaky." The gate is "can I name the test that breaks it." Only one of those questions has an answer you can paste into a review comment.