← Papers

A hierarchical routing system for LLMs maintains near-oracle accuracy while cutting compute costs by up to 42.9%, but early-stage model reasoning can raise or lower final performance by as much as ~19 percentage points.

Pyramid MoA: A Probabilistic Framework for Cost-Optimized Anytime Inference

Arindam Khaled · February 23, 2026

arxiv other medium evidence 7/10 relevance Full text usable extracted full text Source PDF

Structured author observations

Linked only from stored provider relations; the raw author line above is never matched by name.

Arxiv

Latest observation: July 30, 2026

Arindam Khaled unresolved corpus identity

Semantic Scholar

Latest observation: August 25, 2026

Arindam Khaled provider ID

Pyramid MoA uses a decision-theoretic router to escalate queries through a hierarchy of LLM agents, achieving near-oracle accuracy on multiple benchmarks while cutting compute by up to ~43% and revealing strong anchoring effects from earlier-stage agent reasoning.

Citation observations

Cumulative provider counts captured on specific dates; providers are never combined.

0 cumulative citations

Semantic Scholar · Observed August 25, 2026

View corpus context

We observe that LLM cascading and routing implicitly solves an anytime computation problem -- a class of algorithms, well-studied in classical AI, that improve solutions as additional computation is allocated. We formalize this connection and propose Pyramid MoA, a hierarchical Mixture-of-Agents architecture governed by a decision-theoretic router that escalates queries only when necessary. We establish a Probabilistic Anytime Property with provable monotonicity guarantees and derive a generalized escalation rule from Value of Computation theory that accounts for imperfect oracles, extending the Hansen-Zilberstein monitoring framework to stochastic LLM inference. On MBPP, the router intercepts 81.6% of bugs; on GSM8K/MMLU, the system nearly matches the 68.1% Oracle baseline while achieving up to 42.9% compute savings. The router transfers zero-shot to unseen benchmarks: matching Oracle accuracy on HumanEval (81.1%) and MATH 500 (58.0%) with significant cost reductions. We further discover a context-conditioned anchoring effect across four benchmarks: passing correct SLM reasoning improves Oracle accuracy by up to +19.2pp, while incorrect reasoning degrades it by up to -18.0pp, revealing a fundamental tension in hierarchical MoA architectures.

Summary

Main Finding

Pyramid MoA is a practical, decision-theoretic Mixture-of-Agents (MoA) architecture that treats multi-model LLM routing as an anytime-computation problem. By routing most queries to a cheap ensemble (Layer 1) and escalating only when a lightweight router predicts failure, the system (i) provably increases expected solution quality with depth under identifiable router conditions (Probabilistic Anytime Property), (ii) applies a generalized Value-of-Computation escalation rule that accounts for imperfect Oracles, and (iii) achieves substantial compute savings while preserving Oracle-level accuracy across multiple benchmarks and in zero-shot transfer.

Key Points

Conceptual contribution
- Recasts multi-model LLM cascading/routing as a probabilistic anytime computation + monitoring problem.
- Defines a Probabilistic Anytime Property: expected (distributional) accuracy is non-decreasing with computational depth (Theorem 1).
- Derives a generalized decision-theoretic escalation rule (Equation 5) that explicitly adds an “imperfection barrier” for imperfect Oracles in addition to the usual cost barrier.
Theoretical results
- Theorem 1 (Monotonicity Condition): Pyramid MoA yields expected improvement iff the Oracle’s accuracy on the router-escalated subset αL2(R) ≥ Layer-1 accuracy on that subset αL1(R). Improvement magnitude scales with escalation rate pR.
- Generalized escalation rule (single-step monitoring): Pfail > Cesc / Ucorrect + (1 − Poracle)
  - Left term = cost barrier (classical)
  - Right term = imperfection barrier (new): when Poracle < 1, this increases the Pfail threshold needed to escalate.
Architecture & routers
- Layer 1 (SLM ensemble): Llama-3.1-8B, Qwen2.5-7B, Gemma-2-9B.
- Layer 2 (Oracle): Llama-3.3-70B.
- Routers: XGBoost classifiers trained to estimate Pfail.
  - Consensus Router (MBPP/code): uses ensemble semantic agreement and output variance; prioritizes high recall (error-catching).
  - Anytime Router (GSM8K/math): uses token log-probs and candidate correctness signals; prioritizes precision/selectivity.
Empirical phenomena
- Performance profiles are typically concave: steep early accuracy gains for modest extra cost, flattening later—enabling efficient operating points (near-break-even and economy modes).
- Oracle imperfection is observable: some escalations can replace correct Layer-1 answers with incorrect Oracle answers; removing such harmful escalations can yield small accuracy recoveries.
- Context-conditioned anchoring: passing Layer-1 chains-of-thought/candidates to the Oracle improved Oracle accuracy by up to +19.2 pp when the Layer-1 reasoning was correct, but degraded it by up to −18.0 pp when Layer-1 reasoning was incorrect. This reveals a tension in context-aware hierarchical MoA.

Data & Methods

System
- Layer 1 ensemble (SLMs): Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct, Gemma-2-9B.
- Layer 2 Oracle: Llama-3.3-70B-Instruct.
- Router model: XGBoost classifier per domain; features vary by domain:
  - Code (Consensus Router): ensemble semantic agreement, output length variance, candidate mean logprob, etc.
  - Math (Anytime Router): average/min token log-prob, candidate correctness indicators, confidence scores.
- Routing threshold t decides Pfail > t → escalate.
Benchmarks and evaluation
- MBPP (code generation) — N=156 holdout (router t=0.4).
  - Consensus Router recall: 81.6% (caught 62/76 buggy snippets).
  - Feature importance: semantic agreement & length variance most predictive; self-confidence least predictive.
- HumanEval (zero-shot transfer of MBPP-trained router).
  - Baseline Match: matched Oracle accuracy 81.1% while reducing Oracle calls.
  - Economy mode: 73.2% accuracy with 62.7% compute savings vs running 70B on all queries.
- GSM8K/MMLU (math reasoning) — N=1,053; threshold sweep results:
  - Oracle (70B) accuracy: 68.1%.
  - Near break-even (t≈0.15): 67.8% accuracy with 3.3% compute savings.
  - Economy mode (t≈0.35): 63.2% accuracy with 42.9% compute savings.
  - Router recall on holdout: 78.5% (detected 204/260 errors).
- MATH 500 (OOD hard math, zero-shot from math router):
  - Preserves Oracle ceiling: 58.0% accuracy (at baseline match).
  - Efficiency mode: 40.2% accuracy with 59.0% compute savings.
- Empirical verification (t=0.4): For MBPP, HumanEval, GSM8K/MMLU, MATH 500, measured αL2(R) > αL1(R) across escalated subsets (gaps ranging +10.9 to +43.6 percentage points), satisfying Theorem 1.
Metrics reported
- Accuracy (task-specific correct rate).
- Escalation rate pR (fraction of queries sent to Oracle).
- Compute savings (relative to always-running Oracle).
- Router recall and feature importance analyses.
- Performance profiles (accuracy vs threshold and compute).
Context-aware experiments
- Oracle was given Layer-1 candidate answers / chain-of-thought as context in follow-up experiments. Observed anchoring effects (both beneficial and harmful per correctness of Layer-1 reasoning).

Implications for AI Economics

Operational cost-efficiency
- Pyramid MoA provides a principled way to reduce average per-query inference cost by routing only a small, high-value fraction to expensive Oracles without sacrificing expected accuracy. This translates to lower marginal costs for high-volume deployments.
- Performance profiles enable operators to pick operating points that balance cost and accuracy (e.g., near-break-even vs economy mode), supporting cost-capacity trade-offs and pricing decisions.
Value-of-computation & procurement
- The generalized escalation rule reframes purchasing/escrow decisions: the decision to pay for Oracle compute depends not only on cost but also on Oracle reliability (Poracle). When Oracles are imperfect, the effective value of extra compute falls—this affects how much buyers should be willing to pay for additional inference.
- Providers and clients can use the framework to quantify when it is economically rational to run larger models vs accept cheaper-layer answers.
Product & market design
- Tiered offerings become more economically attractive: sellers can price high-capacity models and sell routing-as-a-service (or strategies) to extract value from cheaper SLMs plus small fractions of Oracle usage.
- Third-party routers or routing policies (model-agnostic, API-compatible) become valuable middleware: operators may pay for robust Pfail estimators that yield predictable savings across tasks.
- The demonstration of zero-shot transfer of routers suggests routers can generalize across related task families, increasing their commercial utility.
Incentives & strategic behavior
- Model-imperfection barrier implies manufacturers of large models may have incentives to improve not only average accuracy but worst-case/conditional accuracy on difficult subsets to increase the practical value of escalation.
- On the buyer side, investing in better Pfail estimators (data, labels) yields outsized returns because improved routing increases the realized benefit from the Oracle.
Risks & design cautions
- Context-conditioned anchoring warns that sending Layer-1 outputs as context to Oracles can systematically bias (improve or harm) Oracle outputs. Economically, naive context-passing may reduce expected value and lead to costly degradations; routers or contracts should consider whether Oracles receive prior outputs.
- The framework depends on accurate Pfail estimation. Miscalibrated routers can either waste Oracle compute or harm accuracy—both have direct cost/quality consequences.
- The approach is evaluated in two-tier (single escalation) settings; deeper pyramids need further sequential decision treatment and may change cost/benefit calculations.

Overall, Pyramid MoA provides a formal, empirically validated pathway to lower inference costs for LLM workloads while controlling accuracy loss, and it surfaces key economic levers (cost ratio, Oracle reliability, routing quality) that organizations can optimize for deployment, procurement, and product design.

Assessment

Paper Typeother Evidence Strengthmedium — The paper combines theoretical guarantees (Probabilistic Anytime Property and a Value-of-Computation-based escalation rule) with empirical evaluation across several standard benchmarks (MBPP, GSM8K, MMLU, HumanEval, MATH). This provides substantive, multi-faceted evidence of the approach's effectiveness, but results are limited to benchmark tasks, specific model/agent choices, and reported summary metrics without causal claims or field validation, which constrains confidence in broader claims. Methods Rigorhigh — The authors formalize the anytime-computation connection, derive escalation rules from decision theory extending prior monitoring frameworks, provide monotonicity guarantees, and evaluate on multiple established benchmarks including zero-shot transfer tests; these theoretical derivations plus cross-benchmark experiments indicate strong methodological rigor, though replication details and sensitivity across model families are not reported in the summary. SampleEvaluation uses several standard NLP/code/math benchmarks: MBPP (programming problems), GSM8K (grade-school math), MMLU (multitask language understanding), HumanEval (code generation), and MATH 500 (advanced math problems). The system is a hierarchical Mixture-of-Agents (Pyramid MoA) with a decision-theoretic router and multiple LLM agents (SLMs and higher-quality oracles); metrics reported include bug interception rate, accuracy relative to an oracle baseline, zero-shot transfer performance, and compute savings. Themesproductivity innovation GeneralizabilityBenchmarks are academic tasks (math/code/QA) and may not reflect performance in real-world, noisy, multi-turn applications., Results likely depend on the specific LLM families, model sizes, prompts, and cost/latency assumptions used; transfer to other models is uncertain., Compute-savings estimates depend on assumed pricing/latency models and may not hold under different infrastructure or batching regimes., Anchoring/interaction effects observed with LLM agents may vary with task distribution, agent diversity, or human-in-the-loop setups., Scalability to very large agent pools, interactive systems, or adversarial inputs is not demonstrated.

Claims (13)

Claim	Direction	Outcome	Confidence & Evidence	Details
LLM cascading and routing implicitly solves an anytime computation problem -- a class of algorithms ... that improve solutions as additional computation is allocated. Other	positive	mapping of LLM cascading/routing to anytime computation problem (ability to improve solutions with additional compute)	Reading fidelity high Study strength medium	not reported 0.12
We propose Pyramid MoA, a hierarchical Mixture-of-Agents architecture governed by a decision-theoretic router that escalates queries only when necessary. Other	positive	query escalation behavior (escalates queries only when necessary)	Reading fidelity high Study strength medium	not reported 0.12
We establish a Probabilistic Anytime Property with provable monotonicity guarantees. Other	positive	monotonic improvement of solution quality as computation increases (Probabilistic Anytime Property)	Reading fidelity high Study strength high	not reported 0.2
We derive a generalized escalation rule from Value of Computation theory that accounts for imperfect oracles, extending the Hansen-Zilberstein monitoring framework to stochastic LLM inference. Other	positive	escalation decision rule accounting for imperfect/stochastic oracles	Reading fidelity high Study strength medium	not reported 0.12
On MBPP, the router intercepts 81.6% of bugs. Error Rate	positive	percentage of bugs intercepted by the router	Reading fidelity high Study strength medium	81.6% of bugs 0.12
On GSM8K/MMLU, the system nearly matches the 68.1% Oracle baseline. Output Quality	positive	system accuracy relative to Oracle baseline (≈68.1%) on GSM8K/MMLU	Reading fidelity high Study strength medium	nearly matches the 68.1% Oracle baseline 0.12
On GSM8K/MMLU, the system achieves up to 42.9% compute savings. Organizational Efficiency	positive	compute savings (reduction in compute cost)	Reading fidelity high Study strength medium	up to 42.9% compute savings 0.12
The router transfers zero-shot to unseen benchmarks: matching Oracle accuracy on HumanEval (81.1%). Output Quality	positive	accuracy on HumanEval (zero-shot transfer matching Oracle)	Reading fidelity high Study strength medium	matching Oracle accuracy on HumanEval (81.1%) 0.12
The router transfers zero-shot to unseen benchmarks: matching Oracle accuracy on MATH 500 (58.0%). Output Quality	positive	accuracy on MATH 500 (zero-shot transfer matching Oracle)	Reading fidelity high Study strength medium	matching Oracle accuracy on MATH 500 (58.0%) 0.12
The router transfers zero-shot to unseen benchmarks while achieving significant cost reductions. Organizational Efficiency	positive	zero-shot transfer accuracy and associated cost reductions	Reading fidelity medium Study strength medium	significant cost reductions (not numerically specified in excerpt) 0.07
Passing correct SLM reasoning improves Oracle accuracy by up to +19.2 percentage points across four benchmarks. Output Quality	positive	change in Oracle accuracy when correct SLM reasoning is passed (improvement)	Reading fidelity high Study strength medium	+19.2pp 0.12
Incorrect SLM reasoning degrades Oracle accuracy by up to -18.0 percentage points across four benchmarks. Output Quality	negative	change in Oracle accuracy when incorrect SLM reasoning is passed (degradation)	Reading fidelity high Study strength medium	-18.0pp 0.12
This context-conditioned anchoring effect reveals a fundamental tension in hierarchical Mixture-of-Agents (MoA) architectures. Other	mixed	tension/trade-off between passing intermediate agent reasoning and overall Oracle performance	Reading fidelity high Study strength speculative	not reported 0.02