Leaf-time exact attribution: remove the O(p²) explanation cost

[orgoca]

Problem

Exact pairwise attribution currently costs 1 + p + p(p−1)/2 full-ensemble traversals per row — roughly 8 ms at 23 features, 73 ms at 100. Live decisioning is fine at those numbers, but two things are not:

1. Full-book batch re-explanation. ~23 CPU-hours for 10M accounts at 23 features, growing quadratically with feature count.
2. Reason codes in the SQL export, which we omit entirely because generating O(p²) CASE expressions is impractical.

The approach

Attribution is additive over trees, and a tree only responds to features it splits on. For a depth-2 tree with feature set S (|S| ≤ 2), the complete contribution to every main effect and pairwise interaction needs at most 4 leaf lookups — one per subset of S baselined.

Aggregating per tree instead of per perturbation makes cost O(trees) and independent of feature count.

Crucially, integer addition is associative: regrouping the same sums produces bit-identical results. This is a pure refactor of traversal order, not a change to the quantities.

Why this is a safe change to make

• The committed determinism oracle (tests/data/reference_expected.json) pins every impact_int. If the fast path disagrees by one unit on one row, CI fails.
• The existing O(p²) implementation should not be deleted — move it into compileml.validate as an independent cross-check of the fast path. Two derivations of the same integers is a stronger audit story than one.

Acceptance criteria

• New per-tree path produces integers identical to the current implementation on the reference fixtures
• A property test over randomly generated artifacts asserts old == new
• Benchmark shows cost independent of p
• Old implementation retained as the validation cross-check
• No artifact schema change

Files

src/compileml/runtime/explain.py, src/compileml/validate/framework.py, benchmarks/run_benchmarks.py

Scope

Medium, and unusually well-protected by existing tests. Probably the highest-leverage performance work available — it also unblocks reason codes in the SQL and COBOL exports.