engine: init runlist ordering is nondeterministic for an init-time algebraic cycle through a synthetic-module stock output

[bpowers]

Summary

The init-phase dependency runlist can be nondeterministic (HashMap-iteration-order dependent) when a model has a genuine init-time algebraic cycle that passes through a synthetic-module stock output. This is the init-phase analogue of the dt-phase ordering bug fixed in commit eeace429 ("engine: chain-break stock submodel-output deps in the dt runlist"), which only repaired the dt phase and explicitly left the init phase carrying the edge.

This is a latent correctness bug: the model compiles (cycle detection reports has_cycle == false), but the chosen init order is HashMap-iteration-order dependent and can place a module before its own input, producing nondeterministic / incorrect initial values.

Mechanism

A synthetic module is treated as a sink by the init-phase cycle relation -- init_walk_successors (src/simlin-engine/src/db_dep_graph.rs, the if info.is_module { return Vec::new(); } early-return) returns no successors for a module. But the ordering data follows the real edge module -> input (module·output references are collapsed to the bare module name by normalize_deps, and the module carries its input src as a direct dep).

In the dt phase this same shape was resolved by chain-breaking the stock-submodel-output dependency: a stock's dt value does not depend on its inputs within the same step, so the spurious reader -> module edge can be dropped. See commit eeace429 and the legacy gate model.rs::module_output_deps.

In the INIT phase that chain-break is NOT valid: a stock's INIT value is a real init dependency. init_walk_successors's own rustdoc (db_dep_graph.rs ~143-153) documents this asymmetry deliberately -- "a Stock is NOT an init-phase sink", "no stock filter and no stock sink (a stock-targeted init dep is a real init dependency, kept)". So the edge cannot simply be removed the way it was in the dt phase.

The result:

• Cycle detection never sees a cycle, because init_walk_successors makes the module a sink -> has_cycle == false -> the model compiles.
• But the init ordering data (the initial_deps field consumed by the topo_sort_str closure, db_dep_graph.rs ~2149, called for the initials runlist at ~2311) still has the module -> input edge plus, in the cyclic shape, a reader -> module edge that closes an ordering cycle invisible to detection.
• topo_sort_str then breaks that ordering cycle arbitrarily -- and, as the dt-phase commit message documents for the analogous case, "arbitrarily" means HashMap-iteration dependent. The module can be emitted before its own input helper => nondeterministic init runlist => potentially nondeterministic / incorrect initial values.

The dt-phase commit message states the boundary explicitly: "Only dt_deps is filtered; the init phase keeps the edge (a stock's init value is computed during init, so it is a real init dependency)." That correctly preserves init correctness for the non-cyclic case, but leaves the cyclic-shape ordering soundness gap open.

Scope / trigger

• Triggered by a model with a non-init-broken feedback through a synthetic-module stock output -- e.g. a SMOOTH / SAMPLE IF TRUE module whose input feeds back to a reader of the module's stock output, where the feedback is NOT broken by ACTIVE INITIAL or an explicit init value.
• C-LEARN's emissions_with_stopped_growth does not trigger it, because its feedback is init-broken by ACTIVE INITIAL (so t0 always matched). That is why the C-LEARN residual work did not surface it.
• No known in-repo model triggers it today, so there is currently no failing test -- it is a latent soundness gap, not an observed regression.

Why it matters

• Correctness / determinism: for the specific cyclic shape above, the salsa init runlist ordering is not a function of the model alone -- it depends on HashMap iteration order. Two runs (or two compilations) of the same model can produce different init orderings and therefore different initial values, one of which is wrong.
• It is a general defect in the init-phase ordering analysis for module/macro stock outputs, not specific to any one model.

Components affected

• src/simlin-engine/src/db_dep_graph.rs:
  • build_var_info -- where the dt-phase chain-break fix landed (and where an init-phase resolution would need to live, with different semantics).
  • init_walk_successors -- the init-phase cycle relation that makes a module a sink (so detection misses the cycle) while ordering data keeps the module -> input edge.
  • the initial_deps VarInfo field and the topo_sort_str closure (~2149, invoked for the initials runlist ~2311) -- where the arbitrary, HashMap-order-dependent tie-break happens.
• Contrast with the dt-phase fix in commit eeace429 and the legacy model.rs::module_output_deps gate.

Possible approaches for resolution

The dt-phase fix (drop the edge) cannot be reused, because the init edge is a genuine dependency. Candidate directions (need design discussion, not papered over):

• Make the init ordering consistent with what init detection assumes: since init_walk_successors already treats the module as a sink, ensure the init-phase ordering graph either (a) does not carry a back-edge that closes an ordering cycle detection cannot see, or (b) makes any such residual cycle a detected CircularDependency rather than a silently arbitrary tie-break -- whichever is the correct semantics for "stock init value feeds back through a synthetic-module output". The key invariant to restore: the set of edges topo_sort_str orders on must be exactly the set the cycle detector walked, so a real init cycle is reported and a non-cycle is deterministically ordered.
• Whatever the fix, it must be a general structural fix keyed on the module-stock-output-in-an-init-cycle shape, and should land with a regression fixture exhibiting a non-init-broken SMOOTH/SAMPLE IF TRUE feedback whose init order is currently HashMap-dependent (mirroring the inline-MDL dt-phase regression added in eeace429).

Context / lineage

Discovered during C-LEARN residual Phase 3 Task 5 (branch clearn-residual), which fixed only the dt-phase analogue (commit eeace429). The init-phase gap is out of scope for that task and is a candidate for a dedicated fix or a Phase 4 follow-up.

Severity: latent correctness bug (nondeterministic / incorrect init values for a specific cyclic shape); no known in-repo model triggers it today, but it is a real soundness gap in the salsa init runlist ordering.

[bpowers]

Correction: the "no known in-repo model triggers it" claim is FALSIFIED -- C-LEARN is a concrete reproducer

The issue body currently states (Scope / trigger, and Severity):

No known in-repo model triggers it today, so there is currently no failing test -- it is a latent soundness gap, not an observed regression.

That is no longer true. The C-LEARN model (test/xmutil_test_models/C-LEARN v77 for Vensim.mdl) deterministically triggers this init-phase ordering nondeterminism. It was found while profiling C-LEARN's run phase, not during the original dt-phase work.

The triggering shape in C-LEARN

C-LEARN has a cross-element cumulative init recurrence:

Depth at Bottom[lower] = INITIAL(Depth at Bottom[upper] + Layer Depth[lower])

Each layer's init value depends on the layer above it, and the recurrence is realized through synthetic init helpers. This is precisely the "init-time algebraic cycle through a synthetic-module stock output" shape this issue describes -- and unlike emissions_with_stopped_growth (whose feedback is init-broken by ACTIVE INITIAL, which is why the C-LEARN residual work never surfaced this), this recurrence is not init-broken, so its init ordering is genuinely subject to the HashMap-iteration-order tie-break.

Symptom

The depth_at_bottom slots receive a per-process permutation of their layer->value assignment: the values 300 / 700 / 1300 / 1600 / 2000 permute among the depth_at_bottom slots, and which value lands in which slot varies on every process invocation. The wrong init values then propagate through all 251 saved timesteps.

This is HashMap-iteration order from the per-process RandomState seed, not a threading race: it reproduces with RAYON_NUM_THREADS=1. The NaN count is stable (12299 NaNs), so it is not NaN-payload noise either -- only the depth_at_bottom-derived slots differ between runs.

Why the test suite never caught it

depth_at_bottom is in tests/simulate.rs's EXPECTED_VDF_RESIDUAL carve-out (src/simlin-engine/tests/simulate.rs:1597, the carve-out tracked under #591), so simulates_clearn never compares those slots against Ref.vdf. The nondeterminism is therefore invisible to the integration test today -- it sits entirely inside the carved-out residual.

Reproducer (first-hand verified)

cargo build --release -p simlin-engine --example clearn_profile
RAYON_NUM_THREADS=1 ./target/release/examples/clearn_profile   # run several times

Each run prints a result_fingerprint line. The fingerprint (an FNV-1a-style fold over all saved result bits, computed outside the timing loop) changes across runs -- the low 4 bytes are stable, the high 4 bytes vary -- and only the depth_at_bottom-derived slots differ. Six consecutive runs here (single-threaded), all with identical slot/step geometry (5726 slots/step x 251 steps):

run 1: result_fingerprint: afa6a1ba7346a804
run 2: result_fingerprint: ba6461ba7346a804
run 3: result_fingerprint: afa6a1ba7346a804
run 4: result_fingerprint: afa6a1ba7346a804
run 5: result_fingerprint: ba6461ba7346a804
run 6: result_fingerprint: ba6461ba7346a804

(The clearn_profile.rs example already documents this caveat inline at the result_fingerprint computation and attributes it to this issue; see src/simlin-engine/examples/clearn_profile.rs ~lines 268-278.)

Consequences for this issue

• The "latent / no observed trigger" framing should be updated: this is now an observed, deterministically reproducible nondeterminism in a real in-repo model, not just a theoretical soundness gap.
• C-LEARN can serve as (or seed) the regression fixture this issue calls for, alongside the minimal inline SMOOTH/SAMPLE IF TRUE fixture. Note that C-LEARN alone is unsuitable as the only regression guard: it is #[ignore]d for runtime and its depth_at_bottom slots are carved out of the comparator, so a guard built on it would need to assert init-ordering determinism directly (e.g. fingerprint stability across compilations) rather than rely on the VDF comparison.
• The EXPECTED_VDF_RESIDUAL carve-out for depth_at_bottom (C-LEARN: residual Ref.vdf numeric divergence after element-cycle-resolution (SAMPLE UNTIL / INIT-:NA: / numeric tail / NaN-vs-NA) #591) is currently masking this; once the init ordering is made deterministic, the depth_at_bottom residual should be re-evaluated to see whether it can leave the carve-out.

Discovered during C-LEARN run-phase profiling (the clearn_profile example), 2026-05-20.

[bpowers]

The nondeterminism half is FIXED by e24b0080; the deeper soundness gap remains

Updating disposition as part of C-LEARN-residual Phase 4.

Fixed: the observable nondeterminism

Commit e24b0080 ("engine: make simulation runlist ordering deterministic") closes the nondeterminism half of this issue. The init runlist ordering is now a deterministic function of the model, not the per-process RandomState/HashMap-iteration seed. Concretely:

• C-LEARN's depth_at_bottom cross-element cumulative init recurrence (Depth at Bottom[lower] = INITIAL(Depth at Bottom[upper] + Layer Depth[lower])) -- the concrete reproducer from the earlier comment -- no longer permutes its per-layer values across runs.
• clearn_residual_exactness now passes deterministically (re-run twice in Phase 4, byte-identical: 3482 idents matched; 21 live residual bases vs 21 excluded both times). Before, depth_at_bottom was in the carve-out and its slots permuted per process.
• With the deterministic ordering, depth_at_bottom now matches Ref.vdf and was pruned from EXPECTED_VDF_RESIDUAL in Phase 4.

Remaining: the deeper soundness gap

The structural gap this issue describes is not fully closed. The init-phase cycle relation (init_walk_successors) still treats a synthetic module as a sink, so a genuine init-time algebraic cycle through a synthetic-module stock output can be invisible to cycle detection while the ordering data still carries the closing edge. e24b0080 made the tie-break deterministic, but the invariant this issue calls for -- "the set of edges topo_sort_str orders on must be exactly the set the cycle detector walked, so a real init cycle is reported (CircularDependency) and a non-cycle is deterministically ordered" -- is the part that still needs a general structural fix.

In other words: a deterministic-but-still-arbitrary ordering of an undetected init cycle could, on a different model shape, deterministically pick a wrong order rather than a nondeterministic one. The determinism fix removes the run-to-run variation; it does not yet make every such init cycle a detected error.

Recommendation

Keep this issue open for the soundness gap, but downgrade the severity note from "nondeterministic/incorrect init values" to "init-phase ordering may silently order an undetected init cycle". The regression fixture this issue asks for (a non-init-broken SMOOTH/SAMPLE IF TRUE feedback whose init cycle should be a detected CircularDependency) is still the right next step.