# Multi-LLM Query Optimization

arXiv: https://arxiv.org/abs/2603.24617 · HTML: https://mlsanity.com/paper/2603.24617/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 24 Mar 2026.

## Builds on (most cited first, 19 of 19)

- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate](https://mlsanity.com/paper/2305.19118/) (2023)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [Mixture-of-Agents Enhances Large Language Model Capabilities](https://mlsanity.com/paper/2406.04692/) (2024)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Language Model Cascades: Token-level uncertainty and beyond](https://mlsanity.com/paper/2404.10136/) (2024)
- [Harnessing Multiple Large Language Models: A Survey on LLM Ensemble](https://mlsanity.com/paper/2502.18036/) (2025)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing](https://mlsanity.com/paper/1406.3824/) (2014)
- [When Does Confidence-Based Cascade Deferral Suffice?](https://mlsanity.com/paper/2307.02764/) (2023)
- [LLM-Ensemble: Optimal Large Language Model Ensemble Method for E-commerce Product Attribute Value Extraction](https://mlsanity.com/paper/2403.00863/) (2024)
- [Towards Optimizing the Costs of LLM Usage](https://mlsanity.com/paper/2402.01742/) (2024)
- [Beyond Majority Voting: LLM Aggregation by Leveraging Higher-Order Information](https://mlsanity.com/paper/2510.01499/) (2025)
- [Exact Exponent in Optimal Rates for Crowdsourcing](https://mlsanity.com/paper/1605.07696/) (2016)
- [Agentic Multi-Source Grounding for Enhanced Query Intent Understanding: A DoorDash Case Study](https://mlsanity.com/paper/2603.01486/) (2026)
- [Do Mixed-Vendor Multi-Agent LLMs Improve Clinical Diagnosis?](https://mlsanity.com/paper/2603.04421/) (2026)
- [Exploiting the Randomness of Large Language Models (LLM) in Text Classification Tasks: Locating Privileged Documents in Legal Matters](https://mlsanity.com/paper/2512.08083/) (2025)

## Built on by (most cited first, 1 of 1)

- [Designing Agentic AI Workflow Portfolios under Imperfect Selection and Compute Cost](https://mlsanity.com/paper/2609.18126/) (2026)

## Abstract (arXiv)

Deploying multiple large language models (LLMs) in parallel to classify an unknown ground-truth label is a common practice, yet the problem of optimally allocating queries across heterogeneous models remains poorly understood. In this paper, we formulate a robust, offline query-planning problem that minimizes total query cost subject to statewise error constraints which guarantee reliability for every possible ground-truth label. We first establish that this problem is NP-hard via a reduction from the minimum-weight set cover problem. To overcome this intractability, we develop a surrogate by combining a union bound decomposition of the multi-class error into pairwise comparisons with Chernoff-type concentration bounds. The resulting surrogate admits a closed-form, multiplicatively separable expression in the query counts and is guaranteed to be feasibility-preserving. We further show that the surrogate is asymptotically tight at the optimization level: the ratio of surrogate-optimal cost to true optimal cost converges to one as error tolerances shrink, with an explicit rate of Oleft(loglog(1/αmin) / log(1/αmin)right). Finally, we design an asymptotic fully polynomial-time approximation scheme (AFPTAS) that returns a surrogate-feasible query plan within a (1+varepsilon) factor of the surrogate optimum.