多大模型并行分类时，如何最优分配查询以降本保准
Multi-LLM Query Optimization
- 用配对误差分解+切尔诺夫界构造可解近似目标函数
- 理论证明近似解与真实最优解差距随容错率缩小而趋近于零
- 提出高效算法可在可接受误差内找到可行查询分配方案
在并行部署多个大语言模型进行未知标签分类的场景中，如何在异构模型间最优分配查询仍缺乏系统理解。本文建立了一个鲁棒的离线查询规划问题，旨在最小化总查询成本，同时满足每种可能真实标签下的误差约束，确保可靠性。我们首先通过从最小权重集合覆盖问题的归约证明该问题为NP难。为克服不可解性，提出一种代理目标函数，结合多类误差的成对比较分解与切尔诺夫型集中不等式，所得代理函数在查询次数上具有闭式、可乘分离表达，并保证可行性。进一步证明该代理函数在优化层面渐近紧致：当误差容忍度趋于零时，代理最优成本与真实最优成本之比收敛于1，收敛速率明确为 $O\left(\log\log(1/α_{\min}) / \log(1/α_{\min})\right)$。最后设计了一种渐近全多项式时间近似方案（AFPTAS），可在 $(1+\varepsilon)$ 倍于代理最优值内返回一个可行查询计划。
原文摘要 · Abstract (English)
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 $O\left(\log\log(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。