マルチLLM問合せ最適化

要旨: 未知の真のラベルを分類するために、複数の大規模言語モデル（LLM）を並列に投入することは一般的な実践である。しかし、異質なモデル間でクエリを最適に配分する問題はいまだ十分に理解されていない。本論文では、あらゆる可能な真のラベルに対して信頼性を保証する状態ごとの誤り制約を満たしつつ、総クエリコストを最小化する頑健なオフライン・クエリ計画問題を定式化する。まず、この問題が最小重み集合被覆問題からの帰着によりNP困難であることを示す。 この非可解性を克服するために、多クラス誤りをユニオンバウンド分解し、さらにペアワイズ比較にチェルノフ型の集中（concentration）境界を組み合わせることで代理目的関数（サロゲート）を構築する。その結果得られるサロゲートは、クエリ数に関して乗法的に分離可能な閉形式の表現を持ち、実行可能性を保存する（feasibility-preserving）ことが保証される。さらに、このサロゲートが最適化レベルで漸近的にタイトであること、すなわち誤差許容が縮むにつれてサロゲート最適コストと真の最適コストの比が1に収束することを示す。収束率は明示的に O\left(\log\log(1/\alpha_{\min}) / \log(1/\alpha_{\min})\right) である。最後に、漸近的完全多項式時間近似スキーム（AFPTAS）を設計し、サロゲート最適解に対して (1+\varepsilon) 倍の範囲で、サロゲート実行可能なクエリ計画を返す。