Inverted Dependency Indexing: What Makes O(k) Reactivity Possible

TL;DR: Instead of scanning the whole graph O(n), keep a reverse index from source → dependents. Cost becomes O(k) where k=|affected frontier|.

The Claim

cost(mutation) = O(k), not O(n)
T(Δp) = O(|Reach_D(p)| + C_eval)

What It Makes Possible

1. True O(k) reactivity — only affected chain recomputes
2. Faithful explain() — returns {expr, inputs, dependsOn, recomputed, sourcePath} not narrative
3. Low overhead — 0.0122ms → 0.0189ms (+0.007ms p95) for 3000 nodes, 300 iterations
4. Privacy-preserving — stealth scopes mask ●●●● origin: stealth but structure stays visible
5. Deterministic convergence — local segments reach consistency without global sync

Why It Matters

It makes me['!'].explain() possible: handing over the computation itself, not a self-generated account of it.

Sources

• Explain thesis: https://suign.github.io/Explain.html
• Equations: https://suign.github.io/Equations.html
• Kernel: https://github.com/neurons-me/.me

Glossary explainer of work by Sui Gn (@suign).