docs(guidelines): record the HashMap-iteration-order defect class and decide whether a static check can catch it

[inureyes]

Problem / Background

A single review sweep between 2026-08-20 and 2026-08-22 turned up seven independent instances of one defect class, spread across five modules, and no part of the toolchain flagged any of them. The types are correct, cargo check is clean, clippy is clean, and the tests pass most of the time. That last clause is the whole problem: the failure is probabilistic, so a green run is not evidence.

The class is: a HashMap iteration result becomes ordered state, or feeds a consumer that is sensitive to order. Rust's RandomState seeds each map instance separately rather than once per process, so the resulting behavior varies both between runs and between two maps built from identical input inside one run. Measured here with rustc -O on this box, building ten HashMap<&str, u32> instances from the same five keys inside one process and recording the .keys() order of each, repeated over 200 processes: 133 processes produced 10 distinct orders out of 10, 52 produced 9, and 15 produced 8. There is no run in which the ten maps agreed.

The seven instances, all verified, each linked to its fix or its open issue:

• test: the klear prefill-causality parity test is nondeterministic run to run on CUDA, and TF32 amplifies it past its tolerance #1265, fixed by PR fix(tests): seed synthetic model fixtures from a sorted key walk #1266 (merged). Four test fixtures named filled_weights walked a WeightMap and advanced one LCG seed per key, so every process built a different random model. WeightMap is HashMap<String, UniquePtr<MlxArray>>. This is the one that started the sweep, and by the time the cause was found it had already put two wrong conclusions into a tracked file: the note at the verify-test-cuda gate definition in the Makefile had attributed the wandering delta to klear's own numerics and to a quantized MoE accumulation path that the fixture never reaches. Both claims are now withdrawn in place (Makefile:604-616).
• fix(lang-bias): the YAML bias map is a HashMap, so language priority is randomized per process #1267, fixed by PR fix(lang-bias): preserve YAML bias: order so priority is deterministic #1269 (merged). LangBiasYamlConfig::bias was Option<HashMap<String, BiasValueStr>> feeding LangBiasSet.ordered, which is documented as the priority order and consumed first-language-wins, so a multi-CJK YAML config assigned different biases to shared Han tokens on every run. The shipped schema example in the doc comment is itself a three-CJK config, so copying it was enough to trigger this.
• fix(rt-detr-v2): needs_sanitize returns on the first marker found in HashMap order, so its verdict is order-dependent #1276, fixed by PR fix(rt-detr-v2): make needs_sanitize independent of HashMap order #1281 (merged). needs_sanitize returned from inside a weights.keys() walk on the first marker it saw, so a checkpoint carrying both marker families got a coin-flip layout verdict. The wrong direction is the expensive one: re-running the sanitize pipeline over already-MLX weights double-transposes conv weights into a shape-valid tensor that nothing downstream can flag.
• fix(distributed): registry accessors return HashMap order, so node routing and failover re-routing are not reproducible #1277, fixed by PR fix(distributed): give registry node accessors a defined order #1284 (merged). Four registry accessors (all_nodes, nodes_with_role, peer_addresses, topology_summary) returned HashMap values unordered into consumers that index positionally or tie-break on input order, reaching node selection on the primary request path.
• fix(distributed): eviction candidate sorts are stable, so HashMap order still picks which tied sequence is evicted #1286 (open) bundles three more, in eviction paths: src/distributed/tensor_parallel/cache_manager.rs:711, src/distributed/pipeline/cache_manager.rs:697, and src/distributed/request_tracker.rs:334.

The subtlety worth documenting most. Those last three all DO sort their candidate list, and are still nondeterministic, because slice::sort_by_key is a stable sort: entries that compare equal keep their input order, and the input order is hash order. A reader who sees a sort reasonably concludes the result is deterministic. It is not, unless the sort key is a total order over the elements. sort_unstable_by does not fix it either; it substitutes a different arbitrary tie order. That is the non-obvious rule this issue exists to write down.

Current Behavior

docs/code-guidelines.md (107 lines) has three sections: "File Size and Module Structure", "Shared Function Comments", and "JIT Kernel Cache Keys" (docs/code-guidelines.md:86-107). The last of those is exactly the shape this issue wants: a bug class the project kept hitting, written up with the mechanism, the symptom, the issues it produced (#1053, #1054), and a pointer to the script that enforces it. There is no section covering HashMap iteration order, so the seven instances above each had to be rediscovered from scratch, and one of them (#1276) is documented nowhere except in a closed PR body.

The file is reachable from CONTRIBUTING.md:3, CONTRIBUTING.md:14, .github/PULL_REQUEST_TEMPLATE.md:3, and docs/README.md:36, so a section added here is on the path a contributor already walks.

The repository also has three repo-specific static checks written in Python, all under scripts/ci/: check_kernel_dtype_keys.py (131 lines, plain text and regex, no AST), check_crate_versions.py, and check_cross_repo_refs.py. check_kernel_dtype_keys.py is wired to the kernel-dtype-keys job at .github/workflows/ci.yml:140-159 and to make verify-kernel-dtype-keys at Makefile:692-693, which is itself part of make verify (Makefile:705). So the precedent for "documented rule plus mechanical enforcement plus CI job" already exists and is worth following rather than inventing.

clippy.toml does not exist anywhere in this repository (confirmed by find . -name clippy.toml), so a disallowed-methods approach would mean introducing one.

Proposed Solution

Two parts. The first is cheap and clearly worth doing. The second needs a feasibility judgment that the implementer should make honestly rather than force.

Part 1: write the rule down (required)

Add a section to docs/code-guidelines.md, as a sibling to "JIT Kernel Cache Keys" and in the same shape (mechanism, why it is invisible, the instances as evidence, enforcement status). It should state:

• When a HashMap iteration result becomes ordered state, or feeds an order-sensitive consumer, the ordering has to be established explicitly at the point of iteration. Order-sensitive consumers include positional indexing, min_by_key and max_by_key (both return the FIRST extremum, so they tie-break on input order), a prefix taken via take or an early break or return, a loop-carried accumulator such as a seed advanced once per element, and anything documented as a priority order.
• A stable sort on a non-total key does not establish it. State the tie-break remedy directly, since all three forms are correct and the choice is stylistic: sort_by_key(|a| (a.primary, a.unique_id)), or sort_by(|a, b| a.primary.cmp(&b.primary).then_with(|| a.id.cmp(&b.id))). State that sort_unstable_by is not a remedy.
• RandomState is per map instance, not per process. Include the measured figure from the Problem section, because "randomized per process" is the wrong mental model and it is the one people arrive with: it suggests that a fixed environment gives a fixed order, and it does not.
• The regression-testing rule, which gets its own subsection because a test that misses it is worthless here. See Technical Considerations below for the evidence.
• Note that BTreeMap is the structural fix where lookups are not hot, and that switching costs O(1) get for O(log n), which is why fix(distributed): registry accessors return HashMap order, so node routing and failover re-routing are not reproducible #1277 kept its HashMap and sorted in the accessors instead.

Point at the seven instances as evidence rather than asserting the rule abstractly, the way the JIT section points at #1053 and #1054.

Part 2: decide whether a static check is feasible (decision required, implementation conditional)

Whether this class can be caught mechanically is a genuine open question, and the implementer should answer it with measurements rather than optimism. A general check is undecidable: whether an iteration order matters depends on the consumer, sometimes in another module. A narrow, high-signal heuristic might still pay for itself.

Evaluate a candidate heuristic against two populations, and report both numbers in the issue before writing any CI wiring:

1. Catch rate: run it against the pre-fix state of the seven known instances. Pre-fix trees are reachable at git show 930fd83e^:src/vision/detection/rt_detr_v2/sanitize.rs and equivalently for the other merged fixes (git log --format=%H --grep="#<pr>" -1 gives the merge commit); fix(distributed): eviction candidate sorts are stable, so HashMap order still picks which tied sequence is evicted #1286's three are still unfixed at main.
2. False-positive count: run it against the current tree and adjudicate every flag by hand.

If the false-positive rate makes it unusable, say so and ship only part 1. A noisy check that everyone learns to ignore is worse than a documented rule. Record the decision either way, in the guidelines section itself, so the next person does not re-derive it.

A prototype was written while filing this issue and its numbers are in Technical Considerations. They are offered as a starting point and a sanity bound, not as a specification: the implementer should re-derive them rather than trust them.

Scope

In scope:

• docs/code-guidelines.md: one new section, sibling to "JIT Kernel Cache Keys". This is the required deliverable.
• docs/README.md:36: extend the one-line summary of code-guidelines.md to mention the new section, matching how it already enumerates the file's other sections.
• A decision on part 2, recorded in the new guidelines section under an "Enforcement" heading the way docs/code-guidelines.md:105-107 does.
• Conditional on that decision going the other way: scripts/ci/check_hashmap_order.py (name at the implementer's discretion), a Makefile target next to verify-kernel-dtype-keys at Makefile:692, membership in the verify aggregate at Makefile:705, and a CI job modeled on kernel-dtype-keys at .github/workflows/ci.yml:140.

Out of scope:

• Fixing any instance. The four merged ones are done; the remaining three are fix(distributed): eviction candidate sorts are stable, so HashMap order still picks which tied sequence is evicted #1286. If the prototype surfaces new instances, file them separately rather than folding them in here; four candidates already surfaced during this issue's research and are listed in Technical Considerations.
• Introducing clippy.toml. Banning HashMap::values through disallowed-methods is not viable, since most uses in this tree are order-insensitive and legitimate (92 .values() and 116 .keys() call sites across 1,248 files), and a blanket ban would be suppressed at nearly every one.
• Migrating any map to BTreeMap or IndexMap. Mentioning the tradeoff in the guidelines is in scope; changing a type is not.

Implementation Notes

• Reuse: model the prose on docs/code-guidelines.md:86-107, which is the house style for a bug-class section, down to the "Why this matters" and "Enforcement" headings and the closing "Read the script rather than trusting this section." If a check is written, model it on scripts/ci/check_kernel_dtype_keys.py: standalone Python 3, no third-party imports, no Rust toolchain, scoped by a structural property of the file rather than a hand-maintained allowlist, exit non-zero with file:line on a finding. Model the CI job on .github/workflows/ci.yml:140-159, including its choice not to sit behind the changes path filter, for the same stated reason (no toolchain, runs in seconds, guards a silent defect).
• Constraints: docs/code-guidelines.md is contributor-facing and cited from four places; keep the new section additive and do not renumber or restructure the existing three. If a check is added to make verify, it must pass on main at the moment it lands, so any true positive it finds in the current tree has to be either fixed first (in a separate PR) or explicitly out of scope with the check narrowed accordingly. Note that make verify-clippy is currently red on main per fix(lint): verify-clippy is red on main from an err_expect, and no PR-time job runs clippy #1283, so do not use a green make verify as the acceptance signal; run the specific targets.
• Edge cases for the check, if written: a type alias hides the map type (WeightMap = HashMap<String, UniquePtr<MlxArray>> at src/lib/mlxcel-core/src/weights.rs:29 is the reason fix(rt-detr-v2): needs_sanitize returns on the first marker found in HashMap order, so its verdict is order-dependent #1276 is invisible to a file-local "is this identifier declared HashMap<" test, and it is the single biggest recall limit on any regex approach). BTreeMap and IndexMap receivers must not be flagged, since their iteration order is defined. Function parameters and generic bounds give no local type information. A method-chain continuation split across lines defeats a naive line-at-a-time regex; the prototype had to join continuation lines to see src/distributed/request_tracker.rs:334 at all. A collect() into HashSet or BTreeSet rather than Vec is order-insensitive by construction and must not be flagged.
• Error handling for the check, if written: exit 0 silently on a clean tree, exit 1 with one path:line per finding and a one-line explanation, matching check_kernel_dtype_keys.py. It must never crash on a file it cannot parse; on an unparseable file it should skip rather than fail, since a false red blocks every PR.

Acceptance Criteria

• docs/code-guidelines.md carries a new section describing the class, naming the seven instances by issue number as evidence, and stating the per-instance (not per-process) RandomState behavior with the measured figure.
• That section states the stable-sort subtlety explicitly, gives at least one concrete total-order remedy in a Rust code block, and says that sort_unstable_by is not a remedy.
• That section states the regression-testing rule: construct a fresh HashMap inside each iteration and loop at least 32 times, because a single call returns the right answer by luck a large fraction of the time.
• docs/README.md:36 mentions the new section, so the docs index stays accurate.
• A decision on the static check is recorded in that section: either implemented, with its measured catch rate against the seven known instances and its false-positive count against the current tree, or explicitly declined with the reason and both numbers that led to declining.
• (n/a, part 2 declined) If a check is implemented, it is wired to CI the way check_kernel_dtype_keys.py is (a job in .github/workflows/ci.yml, a verify-* target in the Makefile, and membership in verify), and running it against the pre-fix state of the instances that motivated it flags them.
• (n/a, part 2 declined) If a check is implemented, python3 scripts/ci/check_<name>.py exits 0 against main as it stands, with any true positive it finds either already fixed or explicitly excluded and the exclusion justified in the script's docstring.

Verification

# Part 1: the new section renders and the docs index matches it.
grep -n '^## ' docs/code-guidelines.md
grep -n 'code-guidelines' docs/README.md CONTRIBUTING.md .github/PULL_REQUEST_TEMPLATE.md

# Part 2, only if a check is implemented. Clean tree must be silent, exit 0.
python3 scripts/ci/check_<name>.py; echo "exit=$?"
make verify-<name>

# Catch rate: re-run it against the pre-fix state of a known instance.
mkdir -p /tmp/prefix-check/src/vision/detection/rt_detr_v2
git show 930fd83e^:src/vision/detection/rt_detr_v2/sanitize.rs > /tmp/prefix-check/src/vision/detection/rt_detr_v2/sanitize.rs
# expect a non-zero exit naming that file

# Nothing else may regress.
make verify-fmt

A pass looks like: grep shows a fourth ## section in docs/code-guidelines.md; make verify-fmt exits 0; and, if a check shipped, it exits 0 on main and non-zero on at least one reconstructed pre-fix file. make verify-clippy is red on main for an unrelated reason (#1283), so it is not part of this issue's gate.

Technical Considerations

The regression-testing rule, and why it needs stating. Three of the four merged fixes needed an in-process loop over freshly built maps to make their new tests fail against the unfixed code, and each landed on a different loop count for the same reason: ORDER_RESOLVE_ITERATIONS = 32 at src/lang_bias.rs:755, ITERATIONS = 64 at src/vision/detection/rt_detr_v2/sanitize.rs:388, ORDER_ITERATIONS = 64 at src/distributed/registry_tests.rs:257 and SELECTION_ITERATIONS = 32 at src/distributed/disaggregated/request_router_tests.rs:865. Every one of the four PRs was validated by demonstrating its new tests failing against the unfixed code first, and two of them recorded a pre-fix failure rate well under 100 percent: PR #1281's pre-fix run failed on 27 of 64 maps, and PR #1269's three ordering tests failed at iteration 0, iteration 0, and iteration 2. A single-shot test would have passed on the majority of runs and shipped nothing. PR #1266 is the exception and worth mentioning as such: it fixed the fixture rather than adding a loop test, and validated across 10 separate processes per precision mode, which is the equivalent when the state under test is process-scoped.

Prototype measurements for part 2. A ~60-line Python prototype in the shape of check_kernel_dtype_keys.py was run against src/ (1,248 .rs files). Rule A was: a Vec bound from a receiver whose last path segment is declared HashMap<...> somewhere in the same file, via .values(), .keys() or .iter(), then consumed within 15 lines by sort_by_key, sort_unstable_by_key, min_by_key, max_by_key, take, first, last, or a literal index. It required joining method-chain continuation lines first. Result: 9 flags total.

Flag	Verdict
src/distributed/tensor_parallel/cache_manager.rs:711	true positive, is #1286 instance 1
src/distributed/pipeline/cache_manager.rs:697	true positive, is #1286 instance 2
src/distributed/request_tracker.rs:334	true positive, is #1286 instance 3
src/distributed/registry.rs:195, :213	candidate, see below
src/server/prompt_cache/store.rs:294	flagged line is benign, but see below
src/distributed/pipeline/serving.rs:607	needs judgment: the collected Vec drives removals (order-insensitive) but also the order of the returned failed: Vec<FailedRequest>
src/tokenizer/mod.rs:368, src/tokenizer/tiktoken.rs:98	false positive, but only by a subtle argument

So rule A is 3 clean true positives, 2 clean false positives, and 4 flags that took a few minutes each to adjudicate. That is a workable ratio on volume, but its recall is the problem: it would have caught 3 of the 7 known instances and missed all four that were actually filed. #1265's consumer is a loop-carried seed with no sort or index in sight. #1267 never calls .keys() or .values() at all; it is for (code, value) in yaml_bias over an Option<HashMap<..>> serde field. #1276 is an early return inside a for key in weights.keys() loop, over a WeightMap type alias that no file-local type test resolves. #1277's accessor and its order-sensitive consumers are in different modules. Two narrower companion rules were also measured, "return or break inside a for over a HashMap view" (2 flags, both clean false positives: src/server/prompt_cache/trie.rs:418, which documents its traversal order as unspecified, and src/lib/mlxcel-core/src/cache/paged_pool_tests.rs:967, an order-insensitive assertion loop) and ".push() inside such a loop" (1 flag, the same trie site). Both are quiet but neither reaches #1276 or #1267, for the type-alias and no-view-call reasons above.

Candidates the prototype surfaced that this issue does not fix. File these separately if confirmed; they are listed here so the catch-rate evaluation has ground truth to check against, and because two of them are places a human already cleared.

• src/distributed/registry.rs:195 and :213 (nodes_at_stage, nodes_at_rank). PR fix(distributed): give registry node accessors a defined order #1284's scope table cleared both as "already sorted, unchanged". They sort by n.config.rank.unwrap_or(u32::MAX) and n.config.stage.unwrap_or(u32::MAX) respectively. ClusterConfig::validate rejects duplicate (stage, rank) pairs (src/distributed/config.rs:465), and both fields are Option<u32>, so the flag asks whether two PPTP nodes carrying None could collapse to the same u32::MAX key. Checked, and they cannot through a validated config: the same function unwraps both fields with ok_or_else first (src/distributed/config.rs:435-446), erroring with "is missing required 'stage' index" or "is missing required 'rank' index", so a PPTP node with either field unset never reaches the registry from config load. Registry::upsert_node performs no validation of its own, so a node arriving by some other ingress could in principle carry None, but that path was not traced and neither accessor has a non-test consumer. Recorded as a lint true positive whose underlying tie is not reachable today, not as a latent bug. The unwrap_or(u32::MAX) is defensive code, and giving it a total order is cheap insurance rather than a fix.
• src/server/prompt_cache/store.rs:315 and :336, src/server/responses_store.rs:243, src/server/conversation_store.rs:151. All four are LRU eviction via map.iter().min_by_key(|(_, e)| e.last_accessed) (or .last_used()) directly on a HashMap, with no intermediate Vec. Iterator::min_by_key returns the first minimum, so two entries sharing a timestamp are separated by hash order. How reachable that tie is was checked, and the answer bounds what this rule buys. All four keys are std::time::Instant (src/server/conversation_store.rs:48, src/server/responses_store.rs:52, src/server/prompt_cache/entry.rs:283), and each writer computes let now = Instant::now() once per call and stamps a single entry with it (conversation_store.rs:83,96, responses_store.rs:161,182). Two entries therefore take their stamps from two separate Instant::now() calls, which on the platforms this project targets resolve to nanoseconds and effectively never collide. So these are four true positives for the lint and zero live defects today: the pattern is genuinely fragile, and it would become real the moment the key changed to anything coarser (a seconds-granularity integer, a logical clock, or a value hoisted across several entries), but nothing is misbehaving now. That distinction should survive into whatever this issue produces, because "the check found four bugs" would be wrong and would cost the rule its credibility the first time someone looked. Rule A misses these entirely because there is no Vec; a companion rule scoped to min_by_key/max_by_key on a HashMap receiver would catch all four, and its only other hit in the tree was src/distributed/pipeline/partition_balance.rs:126, which is a slice and would be excluded by the receiver-type test. Note that src/server/responses_store.rs and src/server/conversation_store.rs are already being touched by fix(server): bound the responses and conversation stores by bytes, not just entry count #1248.

On the mental model. The reason this class survives review is that "HashMap iteration order is randomized" reads as a statement about the process, and people therefore reason that a given binary on a given machine sees a fixed order. It does not. Two maps constructed from identical input, in the same function, microseconds apart, iterate differently. Any guidelines text that does not correct this explicitly will be read as a warning about cross-machine reproducibility and filed as not applicable.