Locally Coherent, Globally Incoherent: Bounding Compositional Incoherence in Multi-Component LLM Agents¶

🕒 Published (v1): 2026-05-28 17:58 UTC · Source: Arxiv · Venue: ICML 2026 · link

Why this paper was selected

ICML; formal bounds on compositional incoherence in multi-component LLM agents

Ask a follow-up

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

TL;DR¶

Multi-component LLM agents that route sub-questions to specialists can violate basic probability axioms at the system level even when every component is individually coherent — a regime the paper calls locally coherent, globally incoherent. The authors formalize this via the compositional residual $\varepsilon^\star$ (the $L^2$ distance from the composed quote to the joint coherent polytope), characterize exactly when local coherence suffices via a product-structure dichotomy, and provide a deterministic Boyle–Dykstra repair plus an anytime-valid sequential coherence monitor. Empirically, $\varepsilon^\star > 0$ on 33–94% of 1,876 ensemble cliques across a four-LLM panel.

Problem¶

Existing coherence tools — self-consistency, conformal prediction, per-component calibration — operate on individual model outputs and are blind to cross-component logical constraints. When a planner routes probability assessment across specialists (e.g., one LLM quotes $P(\text{Republican})=0.6$, another quotes $P(\text{Democrat})=0.6$), the assembled joint quote can exceed unit mass or violate partition constraints, creating a Dutch-book exposure that is strictly inter-component in origin. No prior work provides a runtime, distribution-free, instance-wise certificate of system-level coherence under this composition pattern.

Method¶

Compositional residual. For a composed quote $\hat{p} = A(\Pi_1 \hat{p}^{(1)}, \ldots, \Pi_k \hat{p}^{(k)})$ (where each $\Pi_a$ is per-component Joint-Coherent Decoding, i.e., $L^2$ projection onto the local coherent polytope $M_a$), define: $$\varepsilon^\star(\hat{p}) := \left\| A(\Pi_1 \hat{p}^{(1)}, \ldots, \Pi_k \hat{p}^{(k)}) - \Pi^\star\!\left(A(\Pi_1 \hat{p}^{(1)}, \ldots, \Pi_k \hat{p}^{(k)})\right) \right\|_2$$ where $M^\star$ is the joint coherent polytope enforcing both local and cross-component coupling constraints $\mathcal{C}$.

Product-structure dichotomy (Theorem 3.3). Under owner-selected aggregation (each joint coordinate owned by one component), local coherence guarantees global coherence for all inputs if and only if $M^\star = M^{\boxtimes}$ (the joint polytope factorizes as a Cartesian product of lifted local polytopes). Whenever $M^\star \subsetneq M^{\boxtimes}$, locally coherent forecasts realizing $r \in M^{\boxtimes} \setminus M^\star$ exist and yield $\varepsilon^\star > 0$.

Dutch-book exposure bound (Corollary 3.5). $\text{Exposure}^\star \leq \sqrt{m^\star}\,\varepsilon^\star$ under the unit-stake LMSR, with zero per-component exposure by construction.

Magnitude prediction (Corollary 3.9). Under uniform i.i.d. owner-selection and a single binding halfspace with normal $a_R$: $$\mathbb{E}_\sigma[(\varepsilon^\star)^2] = \kappa_R \cdot \frac{a_R^\top D\, a_R}{\|a_R\|_2^2}$$ where $D = \text{diag}(\Sigma_\Pi)$ is the diagonal of the inter-specialist covariance; $\kappa_R = 1$ for equality constraints, $\kappa_R \approx \tfrac{1}{2}$ for inequality constraints with $\bar{\Pi}$ on the boundary. This is computable from the panel covariance before any routing.

Hierarchical repair (Theorem 3.10). Boyle–Dykstra cyclic $L^2$ projection over $\{M^{\uparrow}_a\} \cup \{C\}$ converges to $\Pi^\star$, driving $\varepsilon^\star$ to the QP solver floor (OSQP, primal residual $\leq 1.5\times10^{-16}$ on closed-form relations).

Sequential monitoring. The e-process $E_t(\lambda) = \prod_{s=1}^t \exp\!\left(\lambda(\varepsilon^{\star 2}_s - m^\star_s/(4K_s)) - \lambda^2 m^\star_s/(2K_s)\right)$ is an $\mathcal{F}_t$-supermartingale under $H_0$ (joint coherence); the stopping rule $\tau_\alpha = \inf\{t : E_t(\lambda) \geq 1/\alpha\}$ controls Type-I error at level $\alpha$ at any stopping time (Ville's inequality).

Key Contributions¶

Runtime, distribution-free certificate $\varepsilon^\star$ of system-level probabilistic coherence, computable from composed output and declared coupling constraints alone.
Product-structure dichotomy (Theorem 3.3): necessary and sufficient condition for local coherence to guarantee global coherence under owner-selected aggregation.
Closed-form Dutch-book exposure bound $\sqrt{m^\star}\,\varepsilon^\star$ (Corollary 3.5) grounded in the finite-state FTAP.
Rayleigh-quotient magnitude prediction (Corollary 3.9) from panel covariance, predictable pre-routing.
Hierarchical Boyle–Dykstra repair (Theorem 3.10) that deterministically eliminates $\varepsilon^\star$ while preserving specialist routing.
Anytime-valid e-process coherence monitor with Type-I error control at any stopping time.
Empirical evaluation on 1,876 ensemble cliques across four relation classes and a four-LLM mid-tier panel, with reproducibility manifest.

Results¶

$\varepsilon^\star > 0$ on 94% (partition), 66% (negation), 43% (disjunction), 33% (conjunction) of 1,876 ensemble cliques; all positive residuals are cross-component (zero per-component residual by construction).
Mean $\varepsilon^\star$: 0.118 (partition), 0.058 (conjunction); mean exposure bound $\sqrt{m^\star}\varepsilon^\star = 0.137$ under naive composition.
Hierarchical JCD reduces mean exposure bound to $1.7\times10^{-14}$, matching the no-composition single-LLM reference (Figure 2b).
Rayleigh-quotient prediction matches observed $\mathbb{E}_\sigma[(\varepsilon^\star)^2]$ within 7% on three of four relation classes (Table 1); conjunction under-shoots at $0.83\times$, predicted by Corollary 3.9's interior-$\bar{\Pi}$ regime.
Per-clique Pearson correlation between prediction and observation: 0.69–0.89 across relation classes.
Regret under proportional allocation: $+0.115$ nats/bet under naive composition; collapses to $+0.006$ when bettors themselves coherentise.
All three intuitive LLM-side mitigations — retrieval augmentation, partition-aware prompting, aggregator-LLM — fail or regress (specific numbers in appendices; text states they each "fail or regress").
Frontier-panel rerun (§5.5) and same-model decoupling control confirm the failure is structural (isolation-induced), not a capability gap between models.

Limitations¶

Evaluation is a controlled routing simulation, not end-to-end deployed agents; the planner-discretion harness ($n=20$) and routing-protocol ladder ($n=100$) are small stand-ins.
The coupling set $\mathcal{C}$ must be explicitly declared by the system owner; recovering implicit $\mathcal{C}$ from agent transcripts is left to future work.
Magnitude prediction assumes a single binding halfspace and requires the panel covariance to be computable before routing; multi-halfspace cases (Fréchet polytopes) need iterative OSQP.
The $\kappa_R \approx \tfrac{1}{2}$ symmetric-panel approximation for inequality constraints can degrade (conjunction empirical $\kappa \approx 0.83 \cdot \tfrac{1}{2}$).
Repair via Boyle–Dykstra requires knowledge of $M^\star$, which presupposes all logical coupling relations across components are known at composition time.
The anytime-valid test requires choosing $\lambda$; calibration of $\lambda$ to the budgeted exposure is outside scope.

Relevance to Agentic AI / LLM Agents¶

This paper directly targets a structural failure mode in the specialist-routing pattern that underpins most multi-agent LLM architectures: sub-agents or tools that handle only a portion of a joint query can produce locally valid but globally incoherent probability estimates, creating exploitable Dutch-book arbitrage at the system level. The compositional residual $\varepsilon^\star$ gives practitioners a runtime diagnostic requiring only the declared coupling constraints and composed output — no access to model internals — making it immediately applicable to deployed orchestration frameworks. The finding that all three obvious LLM-side mitigations (retrieval, partition-aware prompting, aggregator-LLM) fail or regress implies the fix must be at the aggregation layer, not the prompt layer, which has direct architectural implications for multi-agent system design. The product-structure dichotomy (Theorem 3.3) also provides a principled design criterion: if cross-agent coupling constraints prevent $M^\star = M^{\boxtimes}$, system-level incoherence is unavoidable without post-hoc repair.