How a Stable Sort Made KlaroSkope Nondeterministic

We found this bug in the residue of a passing test run. A routine build-validation replay put 340 real samples through two builds of the KlaroSkope engine, old against new. The headline result was a clean pass: no regressions on any payload-recovery verdict or indicator count. Five items disagreed on one thing only, the digest of their decoded-strings output. It would have been easy to wave five digest mismatches through on an otherwise green replay. Chasing them uncovered a defect that had been in the engine for eight months, surviving two project renames on the way. A digest can drift for a boring reason: the same strings serialized in a different order. What we found was not the boring reason.

Same build, same input, five answers

Isolating one of the five and re-running it in fresh interpreter processes made the shape of the thing visible. Same build, same input, same engine configuration and no prior requests, five processes: 13, 18, 23, 21 and 17 decoded strings. Different counts cannot be a presentation-order artifact. The membership of the output was changing, not its arrangement.

No application-level randomness existed in the affected path. No threads either. Each process was deterministic on its own, and no two of them agreed. Deterministic within a process, divergent across processes: that signature made Python's per-process hash seed the strongest suspect, though not yet a convicted one. Pinning the seed converted suspicion into measurement:

Each pinned seed tested was stable on the same Python build. Unpinned, the five processes produced five different answers. That table convicts hash randomization. It does not yet say where in the pipeline the seed was leaking in.

Three other suspects, eliminated by measurement

A nondeterministic output has many possible parents, and we had three other live suspects. Each was cleared by a measurement rather than an argument:

One observation from the measurement phase then pointed at the exact mechanism before we read a line of code: the length profile of the selected strings was identical in every run. Same multiset of lengths each time, different identities at exactly one boundary length. Selection by a length preference was working as designed. Only the resolution of ties was leaking. That is the fingerprint of this bug class, and checking for it costs one histogram.

The one-paragraph background

Since Python 3.3, `str` and `bytes` hashing has by default been salted with a random seed chosen when the interpreter starts, as a defence against hash-flooding attacks. Set iteration order for strings can therefore differ between interpreter invocations. Iteration over an unchanged set is stable in practice within one CPython process, but the language guarantees nothing about it. `PYTHONHASHSEED` controls the seed and must be set before interpreter startup; assigning os.environ inside a running process reseeds nothing. Independently started interpreters typically receive independently randomised seeds, so identical requests may diverge across workers or deployments. Forked workers can instead inherit the parent's hash state, causing them to agree within one master lifetime yet potentially change after a master restart. Consistent-but-arbitrary behaviour is harder to catch than visible divergence.

The trap pattern

The distilled version of the offending line, illustrative rather than engine source:

selected = sorted(set(candidates), key=len)[:LIMIT]

Read it the way its author meant it: deduplicate, apply a sensible preference order, cap the work. Most reviewers approve this line. It is seed-dependent, through a conspiracy of four individually correct behaviours.

The escalation is worth spelling out. Without the truncation, every candidate still survives; the seed changes only their order, which already breaks order-sensitive digests and diffs. The boundary cut is what promotes that ordering difference into a membership difference, at which point downstream analysis is consuming different data depending on the process that ran it.

The quieter sibling

Auditing for the pattern turned up a second instance wearing a different coat. A parallel path collected results with `concurrent.futures.as_completed()`, in other words in completion order, which can vary from run to run. Harmless if downstream consumers are order-independent. Ours was not, and the reason is worth being precise about: the deduplication stage is history-dependent. Each accepted result extends the filter that later results are tested against, and the collision relation is not symmetric, so which of two colliding results arrives first changes what the other is tested against, and therefore whether it survives at all. Arrival order changes the outcome, not merely the identity of a surviving representative. An ordering race, without any threads sharing data.

That path turned out to be unreachable from the public API in the current configuration, so it was fixed as a latent invariant rather than a live failure, and its test states that honestly instead of overclaiming. The fix is the standard one: tag each task with its input index and restore that order before any order-sensitive consumer, or use Executor.map() when completion-order handling buys you nothing.

Why the original test was blind

This is the part that generalises furthest. The natural regression test is a loop:

def test_deterministic():
    outputs = {run_analysis(SAMPLE) for _ in range(50)}
    assert len(outputs) == 1

A load-bearing test must start fresh interpreter processes under deliberately different hash seeds:

def run_pinned(seed: str) -> bytes:
    return subprocess.run(
        [sys.executable, "-c", WORKER_SNIPPET],
        env={**os.environ, "PYTHONHASHSEED": seed},
        capture_output=True, check=True,
    ).stdout

def test_output_is_seed_independent():
    assert run_pinned("0") == run_pinned("1")

Two subprocesses, two pinned seeds, one equality. Against the pre-fix code this fails immediately. Be precise about what it proves afterwards: two seeds agreeing cannot demonstrate general seed independence, since two seeds might coincidentally select the same members at one boundary. What it does is turn the observed failure into a permanent regression test, which is what a regression test is for. The fuller diagnostic, when you suspect this class but have no convicted fixture yet, is a small matrix: several fixed seeds, each run more than once. Stable within each seed but different between seeds is hash-seed dependence. Variation within a single fixed seed means another nondeterminism source is still in play and the hash seed is not your only problem.

Our suite additionally asserts permutation invariance at the unit level: shuffle the input iterable, require the selected batch to be byte-identical. That catches input-order sensitivity in the selection itself, which is the specific door the seed walked through here. It is not a net over every hash-seed-dependent behaviour a program can have, and it does not claim to be.

You can watch the whole mechanism in one line, no engine required:

for seed in 1 2; do
  PYTHONHASHSEED=$seed python3 -c \
    'x={f"s{i:02}" for i in range(20)}; print(sorted(x, key=len)[:5])'
done

Twenty strings, all the same length, capped at five. On the same Python build, the two seeds select different members, and re-running either seed reproduces its selection exactly. Stable within a seed, divergent between seeds, membership and not just order: the entire defect in a shell loop. A fixed PYTHONHASHSEED does not promise an identical set layout across Python versions, implementations or builds, which is one more reason the production fix relies on an explicit total ordering rather than a pinned seed.

The fix is one explicit tie-breaker

Make the sort key injective over the inputs, so no two distinct elements can tie:

selected = sorted(set(candidates), key=lambda s: (len(s), s))[:LIMIT]

The primary length preference is unchanged; ties now have an explicit, deterministic resolution. Lexicographic order among equal-length strings is an arbitrary choice, and arbitrary is fine. The requirement was never a meaningful order, it was the same order in every process, and codepoint comparison delivers that everywhere.

To sweep a codebase for the class, here are greps that earn their keep, phrased to avoid drowning you in false positives. sorted(set(nums)), with a natural total order, is deterministic even when sliced; the risk concentrates where hash order, tied sort keys and order-sensitive consumption meet:

• sorted(set(...), key=...) where the key can tie, followed by a slice, an index, or order-sensitive serialization
• list(set(...)) feeding anything order-sensitive
• min( or max( over a hash-ordered iterable with a tie-producing key
• next(iter( on a set
• as_completed( collected into a sequence consumed by order-sensitive logic

Add to that any dictionary built from a set or another nondeterministically ordered source, since dictionaries preserve insertion order and will faithfully preserve your nondeterministic insertion history too.

Then the cheap dynamic sentinel, which we now consider part of any determinism claim: run your golden-output suite twice, once under PYTHONHASHSEED=0 and once under PYTHONHASHSEED=1, and diff the outputs. Two runs, no instrumentation. Agreement is not proof of determinism, but any divergence is a high-signal candidate for this bug class and should escalate to the repeated fixed-seed matrix above. It would have caught ours years earlier.

Blast radius, stated precisely

Honesty about impact is what separates a post-mortem from a press release. In production, this defect meant the same submission could return a different number, and different identities, of decoded strings depending on which worker served it. That is a semantic reproducibility defect: the visible output genuinely differed, while the primary results held. No payload-recovery impact was observed in this replay, and all 340 comparable items agreed on recovery verdict and indicator counts across both builds; the affected samples still recover their payloads after the fix.

It still warranted two root-cause fixes and permanent gate coverage, because nondeterministic analysis output makes build diffs noisy, golden baselines unreliable and incident reconstruction harder to defend. Reproducibility is the property every other guarantee stands on.