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

Abstract

Large Language Models (LLMs) face a persistent trade-off between inference cost and reasoning capability. While "Oracle" models (e.g., Llama-3.3-70B) achieve state-of-the-art accuracy, they are prohibitively expensive for high-volume deployment. Smaller models (e.g., 7-9B parameters) are cost-effective but struggle with complex tasks. We observe that the emerging practice of LLM cascading and routing implicitly solves an anytime computation problem -- a class of algorithms, well-studied in classical AI, that produce valid solutions immediately and improve them as additional computation is allocated. In this work, we formalize this connection and propose "Pyramid MoA", a hierarchical Mixture-of-Agents architecture governed by a decision-theoretic router that dynamically escalates queries only when necessary. We establish a Probabilistic Anytime Property, proving that expected solution quality is monotonically non-decreasing with computational depth under identifiable conditions on router precision. We derive a generalized escalation rule from Value of Computation theory that accounts for imperfect oracles, extending the classical monitoring framework of Hansen and Zilberstein to stochastic LLM inference. On the MBPP code generation benchmark, the Consensus Router intercepts 81.6% of bugs. On the GSM8K/MMLU mathematical reasoning benchmark, the system matches the Oracle baseline of 68.1% accuracy while enabling up to 18.4% compute savings at a balanced operating point. Crucially, the router transfers zero-shot to unseen benchmarks: on HumanEval it achieves 81.1% accuracy (matching the Oracle) with 62.7% cost savings in economy mode, and on the highly complex MATH 500 benchmark it preserves the 58.0% Oracle ceiling. The framework acts dynamically: serving as an aggressive cost-cutter for low-entropy tasks and a strict safety net for high-entropy tasks.