ltm-finding: strongest-path discovery infeasible on large arrayed models (element-level blowup) #647

Summary

LTM strongest-path loop discovery (discover_loops_with_graph in src/simlin-engine/src/ltm_finding.rs) does not complete in feasible time on large arrayed models. Discovery is the heuristic path the engine auto-flips to when a model's causal-graph SCC exceeds MAX_LTM_SCC_NODES = 50 (replacing exhaustive Johnson enumeration). On large arrayed models the discovery runs on the element-expanded causal graph, where the node count V reaches the tens of thousands, and it degenerates.

This is distinct from #540 (World3): #540 is the scalar, variable-level dense SCC case (variable-level SCC of 166 scalar nodes). This issue is the element-level expansion blow-up on arrayed models, with C-LEARN as a now-working fixture, and a different proposed fix (run discovery at variable granularity for large arrayed models). The two share a root mechanism (the strongest-path pruning fails when path-score products do not shrink) but have distinct fixtures, measurements, and remediation. Tracked under epic #488; related to #540 and #481.

Measurements (C-LEARN v77, test/xmutil_test_models/C-LEARN v77 for Vensim.mdl)

The LTM sim of C-LEARN produces:

• 171,498 result slots per step
• 152,116 element-level link-score columns (45,616 carrying finite non-zero values)

Per-timestep discovery cost explodes on "busy" timesteps:

• Timestep 1 finishes in ~0.04 s with 0 loops (near initial conditions, scores ~0).
• The first 5 timesteps together do not finish in > 5 minutes.
• The full 251-step run does not complete in 20+ minutes.

This persists after a constant-factor optimization: the IndexedSearch integer-indexed-graph + reusable-scratch refactor of the per-timestep DFS (correct, keeps all LTM tests passing, cross-checked against SearchGraph as an equivalence oracle). So the wall is algorithmic, not constant factors.

Root-cause hypothesis (being tested separately)

1. Wrong granularity. Discovery runs on the ELEMENT-expanded causal graph, so V (node count) is in the tens of thousands. The strongest-path algorithm is ~O(V^2) per stock per timestep, intractable at that scale.
2. Broken pruning. The DFS prunes via score < best_score, which assumes path-score products shrink as paths extend. C-LEARN has link scores >> 1 (e.g. the ~5.2e7 degenerate macro-internal scores), so products can GROW, defeating the pruning and pushing toward near-exhaustive path enumeration.

Proposed algorithmic redesign (the thing to track)

• For models above a size threshold, run discovery at VARIABLE level (the collapsed variable graph, small V) rather than element level, so O(V^2) is tractable.
• And/or repair the strongest-path pruning so it stays effective when link scores exceed 1 (e.g. prune on a normalized/relative score rather than a raw running product).
• The literature (docs/reference/ltm--loops-that-matter.md section 12.4) also notes discovery can be run at a subset of timesteps -- another lever.

Why it matters

Discovery is meant to be the tractable path for large models, but on a real arrayed model (C-LEARN) it does not finish at all. Any large arrayed model that auto-flips to discovery (SCC > MAX_LTM_SCC_NODES) will hang in the production analysis path. Correctness of the per-timestep DFS is fine; the issue is purely scalability/feasibility at element-expanded scale.

Components affected

• src/simlin-engine/src/ltm_finding.rs (discover_loops_with_graph, the per-timestep strongest-path DFS, IndexedSearch)
• docs/reference/ltm--loops-that-matter.md section 12 (algorithm reference)
• Phase-timing harness: src/simlin-engine/examples/clearn_discover.rs (env vars CLEARN_SKIP_DISCOVERY, CLEARN_DISCOVER_STEPS=N, CLEARN_CAP_SCORES)

How it was discovered

Diagnosed while profiling LTM discovery on C-LEARN v77 using the clearn_discover.rs phase-timing harness, after confirming the IndexedSearch constant-factor refactor did not move the wall.

References

• src/simlin-engine/src/ltm_finding.rs
• docs/reference/ltm--loops-that-matter.md section 12
• src/simlin-engine/examples/clearn_discover.rs
• Relates to epic epic: Loops that Matter (LTM) -- tracking known issues and improvements #488; related to ltm-finding: discovery mode (discover_loops) is intractable on World3 (390s / 22GB, no result) #540 (scalar World3 discovery intractability) and ltm-finding: SearchGraph clones Ident<Canonical> in per-timestep DFS hot path #481 (Ident clone in DFS hot path).