BOHM: Zero-Cost Hierarchical Attribution for Compound AI Systems¶

🕒 Published (v1): 2026-05-19 19:38 UTC · Source: Arxiv · link

Why this paper was selected

Zero-cost Shapley attribution for compound AI without expensive coalition re-evaluation

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

BOHM (Byproduct-Of-Hierarchy Method) is a zero-cost attribution method for compound AI systems that derives hierarchical component credit directly from the routing weights a system already maintains, requiring no additional coalition evaluations. Leaf attribution is the path product of root-to-leaf routing weights; level-$k$ attribution is the induced distribution over depth-$k$ nodes. It provides multi-resolution attribution simultaneously at every level of a hierarchy, which flat methods like SHAP structurally cannot.

Problem¶

Shapley-based attribution (SHAP) for compound AI systems requires evaluating a coalition value function $v(S)$ for arbitrary component subsets $S$, which is infeasible when components are black-box APIs, opaque endpoints, or agentic orchestrators that concentrate deployed routing on a small tool subset — since $v(S)$ for undeployed subsets must be obtained by re-prompting a different orchestrator than the one in deployment. Additionally, SHAP requires $O(2^N)$ exact or $O(MN)$ approximate evaluations and produces only a flat per-leaf attribution vector, with no native multi-level decomposition.

Method¶

Given a rooted tree $T$ of depth $D$ over $N$ leaf components, each router $v$ maintains a weight simplex $\mathbf{w}_v(t) \in \Delta^{b_v}$ updated online by a multiplicative-weights adaptive routing substrate.

Leaf attribution is the path product: $$a_j(t) = \prod_{\ell=0}^{D-1} w_{v_\ell,\, \text{child}(v_\ell, j)}(t)$$

Level-$k$ attribution assigns to each node $u$ at depth $k$: $$a_u^{(k)}(t) = \prod_{\ell=0}^{k-1} w_{v_\ell,\, \text{child}(v_\ell, u)}(t)$$

These form a probability distribution over $V_k$ by the simplex property. The hierarchical attribution tree $\mathcal{A}(t)$ is $T$ with each router annotated by its current $\mathbf{w}_v(t)$; leaf attribution factors as a product of local attributions along each root-to-leaf path. No additional computation is needed beyond reading existing weight state. Formal properties — efficiency (proved by induction on tree depth), monotonicity, symmetry, and weak suppression — are inherited from the substrate's single-selector equilibrium.

Key Contributions¶

Zero-cost hierarchical attribution: BOHM reads routing weights already maintained during operation, incurring no marginal evaluation cost.
Multi-resolution decomposition: all depth levels are attributed simultaneously from a single weight snapshot; flat methods require separate computations per level.
Formal property set: efficiency, monotonicity, symmetry, weak suppression proved; additivity deliberately not satisfied (it is a coalition-value axiom, not a path-product one).
Diagnostic interpretation of BOHM–SHAP disagreement: divergence between the two methods is structurally predicted by whether the deployed router's top pick is empirically optimal, making disagreement itself informative about routing quality.
Applicability to opaque components: BOHM is computable wherever routing state exists, including black-box and third-party components where $v(S)$ cannot be evaluated.

Results¶

LiveCodeBench (18 LLMs, 3-level [3,3,2] hierarchy, 880 problems): BOHM achieves Kendall $\tau = 0.928$ (Spearman $\rho = 0.986$) vs. SHAP's $\tau = 0.980$ ($\rho = 0.988$), at 9,000× fewer coalition evaluations per seed (BOHM reuses 880 operational rounds; SHAP requires 7.92M cached-matrix lookups).
US Census hierarchy (475 leaves / PUMAs, 4 levels, 50,000 rounds): BOHM recovers ground-truth quality rankings simultaneously at all levels — seed-averaged $\tau = 0.722$ at division level ($p = 0.006$), $\tau = 0.686$ at PUMA level ($p < 10^{-6}$), $\tau = 0.533$ at state level.
Multi-driver agentic study (5 drivers × 7 benchmarks, 35 cells, ∼112,000 subset-conditioned routes): Deployed routing is heavily concentrated — top-share median 0.65, 30/35 cells at top-share $\geq 0.50$. Cell-level $\tau(\text{BOHM}, \text{SHAP})$ ranges from $-0.80$ to $+1.00$; cells where deployed top-pick = empirically best tool yield mean $\tau = +0.22$ ($n=9$) vs. $\approx +0.01$ ($n=26$), $\Delta = +0.21$.
On cells with opaque components BOHM achieves $\tau = 1.000$ (Appendix A.5); SHAP is structurally unavailable there.

Limitations¶

Noisy under small quality gaps between components (the routing substrate requires sufficient signal to converge).
Sensitive to hierarchy design: performance varies across hierarchy structures (Appendix A.13); mis-grouped hierarchies degrade $\tau$.
Does not satisfy Shapley's additivity axiom; BOHM and SHAP answer categorically different questions and should not be conflated.
Restricted to stateful, input-unconditioned routing weights; does not extract attribution from token-conditional gating in standard MoE architectures or prompt-conditioned agent routing.
Cannot recover counterfactual lifts that interventional SHAP can (e.g., a ~30pp counterfactual improvement in the GLM–LCB example is invisible to BOHM).
Per-seed $\tau$ is high-variance at small $N$ (e.g., $N=4$ regions); seed-averaging is required for reliable signal.

Relevance to Harnesses / Meta-Harnesses¶

BOHM directly targets the multi-component harness architecture — specifically the "agentic harness" studied in Section 5.4, where a driver orchestrator selects among tools per problem, which is the canonical meta-harness topology. The central insight is that any harness already maintaining adaptive routing weights has attribution for free: BOHM turns the harness's own weight state into a structured, multi-resolution diagnostics object with zero overhead, enabling harness builders to monitor which sub-components are trusted and at what granularity without instrumenting extra evaluation passes. The BOHM–SHAP divergence study empirically characterizes when deployed routing in a harness is suboptimal, providing a concrete signal for harness reconfiguration. For researchers designing or analyzing multi-agent or tool-routing harnesses, BOHM offers both a practical attribution primitive and a diagnostic lens on routing quality.