Cardinality-Constrained Binary Quadratic Programming（CCBQP）による原則的かつスケーラブルな多様性認識リトリーバル

arXiv cs.CL / 2026/4/6

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

本論文はRAGにおける多様性認識のパッセージ検索を扱い、先行手法が理論的保証と、検索集合サイズkが増大する際のスケーラビリティの点で課題を抱えていることを指摘する。
多様性に配慮した検索を、階数（cardinality）に制約を課した2次の二値計画法（CCBQP）として定式化し、関連性と意味的多様性のトレードオフを明示的に制御する解釈可能なパラメータを導入する。
著者らは非凸なタイトな連続緩和と、Frank–Wolfeに基づくアルゴリズムを開発し、ランドスケープ解析および収束保証を含める。
実験により、提案手法が関連性—多様性のパレートフロンティア上でベースラインより改善し、さらに大幅な速度向上を達成することが示される。

Abstract

多様性を考慮した検索は、Retrieval-Augmented Generation（RAG）にとって不可欠ですが、既存手法には理論的保証がなく、取得するパッセージ数

k

が増えるとスケーラビリティの問題に直面します。本研究では、多様性検索を、台数制約付き二次二値計画（CCBQP）として定式化することで、妥当性のある枠組みを提案します。解釈可能なトレードオフ用パラメータにより、関連性と意味的多様性の両者を明示的に釣り合わせます。組合せ最適化における近年の進展に着想を得て、非凸なタイト連続緩和と、ランドスケープ解析および収束保証を伴う Frank--Wolfe に基づくアルゴリズムを開発します。大規模な実験により、提案手法は関連性—多様性のパレートフロンティア上で一貫してベースラインを上回り、さらに大幅な高速化も達成することを示します。