💬 NLP

Principled and Scalable Diversity-Aware Retrieval via Cardinality-Constrained Binary Quadratic Programming

यह शोध पत्र RAG प्रणालियों में विविधता-जागरूक पुनर्प्राप्ति (diversity-aware retrieval) के लिए एक सिद्धांत-आधारित, स्केलेबल ढांचे को प्रस्तुत करता है, जो इस समस्या को एक कार्डिनैलिटी-प्रतिबंधित बाइनरी क्वाड्रेटिक प्रोग्राम के रूप में तैयार करता है और इसे एक नवीन फ्रैंक-वोल्फ-आधारित एल्गोरिदम के साथ हल करता है जो सैद्धांतिक गारंटी प्रदान करने के साथ-साथ प्रासंगिकता-विविधता ट्रेड-ऑफ और कम्प्यूटेशनल दक्षता दोनों में मौजूदा विधियों से बेहतर प्रदर्शन करता है।

मूल लेखक: Qiheng Lu, Nicholas D. Sidiropoulos

प्रकाशित 2026-04-06

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Qiheng Lu, Nicholas D. Sidiropoulos

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक शेफ हैं जो एक बहुत ही भूखे अतिथि (AI) के लिए एक विशाल, स्वादिष्ट दावत तैयार कर रहे हैं। अतिथि की एक विशेष मांग है: "मुझे कॉफी के इतिहास के बारे में सब कुछ बताओ।"

इस उत्तर को देने के लिए, आपको एक विशाल गोदाम (इंटरनेट) से सामग्री (जानकारी) इकट्ठा करने की आवश्यकता है।

समस्या: "दोहराव वाला पेंट्री" (The Redundant Pantry)

अतीत में, जब शेफ (AI सिस्टम) गोदाम में जाते थे, तो वे एक सरल नियम का उपयोग करते थे: "उन 10 वस्तुओं को उठाओ जिनमें कॉफी की सबसे अधिक महक आती है।"

समस्या यह है कि गोदाम डुप्लिकेट्स से भरा है। यदि आप कॉफी बीन्स के शीर्ष 10 बैग उठाते हैं, तो आपको एक ही ब्रांड के बिल्कुल एक जैसे 10 बैग मिल सकते हैं। आपने इथियोपिया में कॉफी के इतिहास, एस्प्रेसो मशीन के आविष्कार, या इटली में कॉफी शॉप की संस्कृति के बारे में कुछ नहीं सीखा है। आपने बस एक ही चीज़ के 10 बैग प्राप्त किए हैं।

इसे रेडंडेंसी (Redundancy) कहा जाता है। AI की दुनिया में, यह "मेमोरी स्पेस" (कॉन्टेक्स्ट विंडो) को बर्बाद करता है और अतिथि को विविधता के बिना भूखा छोड़ देता है।

पुराने समाधान: "लालची शेफ" और "भाग्यशाली पासा"

शोधकर्ताओं ने इसे दो तरीकों से ठीक करने की कोशिश की:

लालची शेफ (MMR): यह शेफ कॉफी का सबसे अच्छा बैग उठाता है, फिर आसपास देखता है और कहता है, "ठीक है, मैं उस ब्रांड का दूसरा बैग नहीं उठाऊंगा। मैं अगला सबसे अच्छा बैग उठाऊंगा जो उस जैसा बहुत अधिक समान नहीं है।"
- दोष: यह धीमा है। जैसे-जैसे अतिथि अधिक सामग्री (मान लीजिए 10 के बजाय 100 आइटम) मांगता है, शेफ को रुकना पड़ता है और पहले से टोकरी में मौजूद हर आइटम के साथ हर नए आइटम की तुलना करनी पड़ती है। इसमें बहुत समय लगता है।
भाग्यशाली पासा (DPP): यह शेफ एक जटिल गणितीय संभाव्यता खेल का उपयोग करके विविध सेट चुनता है।
- दोष: इसकी संभावनाओं की गणना करना अविश्वसनीय रूप से जटिल है। एक बड़े गोदाम के लिए, यह समुद्र तट पर रेत के प्रत्येक कण के लिए मौसम की भविष्यवाणी करने जैसा है। यह बहुत धीमा और ट्यून करने में कठिन है।

नया समाधान: "स्मार्ट ऑप्टिमाइज़र"

इस शोध पत्र के लेखक समस्या को देखने का एक नया तरीका प्रस्तावित करते हैं। वे इसे कार्डिनैलिटी-कंस्ट्रेंड बाइनरी क्वाड्रेटिक प्रोग्रामिंग (CCBQP) कहते हैं।

इस फैंसी नाम से न डरें। इसे एक पूरी तरह से संतुलित रेसिपी के रूप में समझें।

उन्होंने एक ऐसा फॉर्मूला बनाया है जो प्रत्येक सामग्री के लिए दो प्रश्न एक साथ पूछता है:

यह कितना प्रासंगिक है? (क्या इसमें कॉफी की महक आती है?)
यह कितना अलग है? (क्या यह मेरे पास पहले से मौजूद कॉफी के प्रकार से अलग है?)

वे इन दोनों प्रश्नों को एक एकल "नॉब" (एक पैरामीटर जिसे $\theta$ कहा जाता है) के साथ संतुलित करते हैं।

नॉब को प्रासंगिकता (Relevance) की ओर घुमाएं, और आपको केवल सबसे लोकप्रिय कॉफी मिलेगी।
नॉब को विविधता (Diversity) की ओर घुमाएं, और आपको बीन्स, रोस्ट और ब्रूइंग विधियों का मिश्रण मिलेगा।
जादू उस स्वीट स्पॉट (Sweet Spot) को खोजने में है जहाँ आप सबसे दिलचस्प, गैर-दोहराव वाली कहानी प्राप्त कर सकें।

गुप्त सूत्र: "फ्रैंक-वोल्के" शॉर्टकट (The Frank-Wolfe Shortcut)

कठिन हिस्सा यह है कि सबसे अच्छे मिश्रण को खोजने के लिए सामग्रियों के हर संभावित संयोजन की जांच करना कंप्यूटर के लिए बहुत तेज़ी से करना गणितीय रूप से असंभव है (यह एक "NP-hard" समस्या है)। यह 100 सामग्रियों के हर संभावित संयोजन को चखकर सबसे अच्छा सूप खोजने जैसा है।

शोधकर्ताओं की सफलता एक गणितीय शॉर्टकट ("कंटीन्यूअस रिलैक्सेशन") है।

उपमा: कल्पना कीजिए कि आप एक पहाड़ी परिदृश्य पर उच्चतम बिंदु खोजने की कोशिश कर रहे हैं। आमतौर पर, आपको ऊबड़-खाबड़ चट्टानों (बाइनरी विकल्प: हाँ/नहीं, शामिल करें/बाहर निकालें) पर कदम-दर-कदम चलना पड़ता है।
ट्रिक: लेखकों ने परिदृश्य को एक सौम्य, निरंतर पहाड़ी में सुचारू (smooth) कर दिया है। उन्होंने एक विशिष्ट तकनीक (फ्रैंक-वोल्के एल्गोरिदम) का उपयोग करके इस चिकनी पहाड़ी से नीचे फिसलने का तरीका खोजा है जो यह गारंटी देता है कि वे बिना किसी घाटी में फंसे, सीधे एक "चट्टान" (सामग्रियों का एक वैध चयन) पर उतरेंगे।

यह क्यों मायने रखता है: गति और गुणवत्ता

यह शोध पत्र दिखाता है कि उनका तरीका पुराने तरीकों की तुलना में एक सुपरहीरो है:

यह तेज़ है: जबकि पुराना "लालची शेफ" अधिक सामग्री मांगने पर धीमा होता जाता है, यह नया तरीका तेज़ बना रहता है। यदि आप 100 सामग्रियां मांगते हैं, तो पुराना तरीका बहुत समय लेता है; नया तरीका बहुत कम समय लेता है। यह जंगल में पैदल चलने से हाई-स्पीड ट्रेन लेने जैसा है।
यह स्मार्ट है: यह लगातार जानकारी का एक बेहतर मिश्रण पाता है। यह केवल "शीर्ष 10" नहीं उठाता और उम्मीद नहीं करता; यह अधिकतम विविधता सुनिश्चित करने के लिए पूरी टोकरी की योजना सक्रिय रूप से बनाता है।
बेहतर उत्तर: जब उन्होंने इसे उत्तर उत्पन्न करने वाले एक AI के साथ परीक्षण किया, तो परिणाम बेहतर थे। AI भ्रमित (hallucinate) कम हुआ क्योंकि उसके पास काम करने के लिए तथ्यों का एक समृद्ध, अधिक विविध सेट था।

संक्षेप में

यह शोध पत्र AI को जानकारी चुनने का एक स्मार्ट, तेज़ और संतुलित तरीका देता है। समान प्रतियों का ढेर उठाने के बजाय, यह तथ्यों का एक विविध, उच्च-गुणवत्ता वाला पुस्तकालय बनाता है जो AI को बहुत बेहतर कहानी बताने में मदद करता है, और वह भी पलक झपकते ही गणित को हल करते हुए।

यहाँ शोध पत्र "Principled and Scalable Diversity-Aware Retrieval via Cardinality-Constrained Binary Quadratic Programming" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र रिट्रीवल-ऑगमेंटेड जनरेशन (RAG) में एक महत्वपूर्ण बाधा को संबोधित करता है: रिट्रीव किए गए अनुच्छेदों (passages) की प्रासंगिकता (relevance) और सिमेंटिक विविधता (semantic diversity) के बीच का संतुलन।

समस्या: मानक top- $k$ रिट्रीवल प्रासंगिकता को अधिकतम करता है लेकिन अक्सर सिमेंटिक रूप से रेडंडेंट (redundant) अनुच्छेद लौटाता है (जैसे, लगभग समान समाचार लेख), जिससे लार्ज लैंग्वेज मॉडल्स (LLMs) की सीमित कॉन्टेक्स्ट विंडो व्यर्थ हो जाती है।
मौजूदा विधियों की सीमाएँ:
- मैक्सिमल मार्जिनल रेलिवेंस (MMR): एक ग्रीडी एल्गोरिदम है जिसमें नॉन-मोनोटोन सबमॉड्यूलर फंक्शन्स के लिए सैद्धांतिक एप्रोक्सिमेशन गारंटी का अभाव है। इसका रनटाइम रिट्रीव किए गए अनुच्छेदों की संख्या ( $k$ ) के साथ लीनियरली (linearly) स्केल होता है, जो बड़े $k$ के लिए एक बाधा बन जाता है।
- डिटरमिनेंटल पॉइंट प्रोसेसेस (DPP): एक प्रोबेबिलिस्टिक फ्रेमवर्क है जहाँ मैक्सिमम ए पोस्टेरिओरी (MAP) सबसेट खोजना NP-hard है। मौजूदा एप्रोक्सिमेशन्स में $k$ के संबंध में सुपर-लीनियर (super-linear) टाइम कॉम्प्लेक्सिटी होती है और वे कठिन-से-व्याख्या योग्य ट्रेड-ऑफ पैरामीटर्स से ग्रस्त होते हैं।
लक्ष्य: एक ऐसी विधि विकसित करना जो सैद्धांतिक गारंटियों, व्याख्या योग्य पैरामीटर्स और $k$ में सब-लीनियर (sub-linear) स्केलेबिलिटी के साथ प्रासंगिकता और विविधता को स्पष्ट रूप से संतुलित करे।

2. कार्यप्रणाली (Methodology)

A. समस्या का निरूपण (CCBQP)

लेखक विविधता-जागरूक रिट्रीवल को एक कार्डिनैलिटी-कंस्ट्रेंड बाइनरी क्वाड्रेटिक प्रोग्रामिंग (CCBQP) समस्या के रूप में निरूपित करते हैं।

उद्देश्य: $k$ $k$ अनुच्छेदों का एक उपसमुच्चय (subset) चुनना (जिसे बाइनरी वेक्टर $x$ $x$ द्वारा दर्शाया गया है) ताकि इसे अधिकतम किया जा सके:
$\max_{x \in \{0,1\}^n} \theta \cdot (k-1) \cdot c^T x + (1-\theta) x^T (I - EE^T) x$
- $c$ : क्वेरी के साथ कोसाइन सिमिलैरिटी (relevance scores)।
- $E$ : कैंडिडेट अनुच्छेदों का एम्बेडिंग मैट्रिक्स।
- $x^T (I - EE^T) x$ : विविधता टर्म (पेयरवाइज कोसाइन सिमिलैरिटी को दंडित करता है)।
- $\theta \in [0,1]$ : व्याख्या योग्य ट्रेड-ऑफ पैरामीटर।
- गुणांक $(k-1)$ प्रासंगिकता और विविधता पदों के स्केल को संरेखित (align) करता है।

B. सैद्धांतिक विश्लेषण और रिलैक्सेशन (Theoretical Analysis & Relaxation)

चूँकि CCBQP एक NP-hard समस्या है, लेखक एक नॉन-कॉन्वेक्स टाइट कंटीन्यूअस रिलैक्सेशन (non-convex tight continuous relaxation) प्रस्तावित करते हैं:

रिलैक्सेशन: बाइनरी कंस्ट्रेंट $x \in \{0,1\}^n$ को कंवेक्स हल (convex hull) $x \in [0,1]^n$ में रिलैक्स करें, जबकि कार्डिनैलिटी कंस्ट्रेंट $\mathbf{1}^T x = k$ को बनाए रखें।
टाइटनेस गारंटी: वे सिद्ध करते हैं कि यदि एक पेनल्टी पैरामीटर $\lambda \ge 2$ को ऑब्जेक्टिव में जोड़ा जाता है, तो रिलैक्स्ड समस्या का ग्लोबल मैक्सिमम, बाइनरी सॉल्यूशन के साथ मेल खाता है (Theorem 2.1)।
इंटीग्रल सॉल्यूशंस: इस यथार्थवादी धारणा के तहत कि पासज एम्बेडिंग्स पूरी तरह से एंटी-अलाइन्ड (anti-aligned) नहीं हैं (Assumption 2.2), वे सिद्ध करते हैं कि रिलैक्स्ड समस्या के सभी ग्लोबल मैक्सिमज़र्स इंटीग्रल (integral) हैं (Corollary 2.3)। यह पोस्ट-हॉक राउंडिंग की आवश्यकता को समाप्त कर देता है।
ऑप्टिमाइजेशन लैंडस्केप: वे एक "बेनाइन" (benign) लैंडस्केप स्थापित करते हैं जहाँ सभी नॉन-ऑप्टिमल स्टेशनरी पॉइंट्स पॉजिटिव कर्वेचर वाले स्ट्रिक्ट सैडल्स (strict saddles) हैं (Theorem 2.4)। यह सुनिश्चित करता है कि ग्रेडिएंट-आधारित विधियाँ स्थानीय मिनिमा/सैडल्स से आसानी से बाहर निकल सकें।

C. ऑप्टिमाइजेशन एल्गोरिदम (Frank-Wolfe)

लेखक रिलैक्स्ड समस्या को कुशलतापूर्वक हल करने के लिए एक विशेष फ्रैंक-वोल्डे (Frank-Wolfe) एल्गोरिदम डिजाइन करते हैं:

एक्सैक्ट लाइन सर्च: लिप्सचिट्ज़-आधारित एडेप्टिव स्टेप साइज़ (जो घने एम्बेडिंग मैट्रिसेस के बड़े आइजनवैल्यू के कारण धीमे होते हैं) के बजाय, वे अनुकूलतम स्टेप साइज़ $\gamma$ के लिए एक क्लोज्ड-फॉर्म समाधान निकालते हैं।
स्पैरसिटी एक्सेलरेशन (Sparsity Acceleration): हर इटरेशन में $O(nd) $मैट्रिक्स-वेक्टर मल्टीप्लिकेशन से बचने के लिए, वे सर्च डायरेक्शन की स्पैरसिटी का लाभ उठाते हैं। अपडेट$ E^T d^{(t)} $को$ E^T s^{(t)} - E^T x^{(t)} $के रूप में कंप्यूट किया जाता है, जहाँ$ s^{(t)} $एक$ k $-स्पार्स वेक्टर है। यह इस स्टेप की जटिलता को **$ O(kd)$** तक कम कर देता है।
जटिलता: प्रति-इटरेशन कुल जटिलता $O(nd) $द्वारा डोमिनेटेड है, लेकिन **वॉल-क्लॉक टाइम$ k $के साथ सब-लीनियरली स्केल होता है** क्योंकि भारी काम केवल$ k$ के माध्यम से स्पार्स टर्म पर निर्भर करता है।

3. मुख्य योगदान (Key Contributions)

सिद्धांतिक रूप से आधारित निरूपण: CCBQP फ्रेमवर्क पेश किया, जो एक व्याख्या योग्य ट्रेड-ऑफ पैरामीटर $\theta$ प्रदान करता है जो प्रासंगिकता और विविधता को संतुलित करता है।
सैद्धांतिक गारंटी: एक नॉन-कॉन्वेक्स कंटीन्यूअस रिलैक्सेशन की टाइटनेस को सिद्ध किया और स्थापित किया कि रिलैक्स्ड समस्या के ग्लोबल ऑप्टिमा हमेशा इंटीग्रल होते हैं (राउंडिंग की आवश्यकता नहीं)। प्रस्तावित एल्गोरिदम के लिए कन्वर्जेंस गारंटी प्रदान की।
स्केलेबल एल्गोरिदम: एक्सैक्ट लाइन सर्च और स्पैरसिटी-अवेयर अपडेट के साथ एक फ्रैंक-वोल्डे वेरिएंट विकसित किया, जो $k$ में सब-लीनियर स्केलिंग प्राप्त करता है, जो बेसलाइन्स (MMR और DPP) के लीनियर और सुपर-लीनियर स्केलिंग की तुलना में एक महत्वपूर्ण सुधार है।
अनुभवजन्य प्रभुत्व (Empirical Dominance): कई डेटासेट्स और रिट्रीवल साइज़ पर प्रासंगिकता-विविधता पारेटो फ्रंटियर (Pareto frontier) पर श्रेष्ठ प्रदर्शन प्रदर्शित किया।

4. प्रयोगात्मक परिणाम (Experimental Results)

विधि का मूल्यांकन ASQA और QAMPARI डेटासेट्स पर किया गया, जहाँ कैंडिडेट पूल $n > 2 \times 10^6$ और रिट्रीवल साइज़ $k \in \{25, 50, 100\}$ था।

रिट्रीवल क्वालिटी (Pareto Frontier): प्रस्तावित विधि लगातार MMR और DPP से बेहतर प्रदर्शन करती है, जो एक दिए गए इंट्रा-लिस्ट एवरेज डिस्टेंस (ILAD) विविधता मेट्रिक के लिए उच्च रिकॉल (Recall) प्राप्त करती है। यह ग्रीडी लोकल निर्णय लेने के बजाय ग्लोबल स्तर पर ट्रेड-ऑफ को ऑप्टिमाइज़ करती है।
दक्षता (Efficiency):
- $k=100$ के लिए, MMR और DPP को $>850$ ms की आवश्यकता होती है।
- प्रस्तावित विधि लेटेंसी को 40–180 ms तक कम कर देती है।
- स्पीडअप: व्यावहारिक शासन ( $\theta \ge 0.5$ ) में MMR की तुलना में 2.4× से 22.9× स्पीडअप प्राप्त करता है।
जेनरेशन क्वालिटी: Llama-3.1-8B का उपयोग करके एंड-टू-एंड प्रयोगों ने दिखाया कि विविधता-जागरूक रिट्रीवल, मानक top- $k$ $k$ की तुलना में जेनरेशन क्वालिटी (F1 स्कोर) में सुधार करता है।
- नोट: अत्यधिक विविधता ( $\theta$ बहुत कम होना) ग्राउंडिंग फैक्ट्स को हटाकर प्रदर्शन को नुकसान पहुँचा सकती है, लेकिन मध्यम विविधता ( $\theta \approx 0.8-0.9$ ) निरंतर सुधार प्रदान करती है।
- $k$ को 25 से 50 तक बढ़ाने से रिकॉल में सुधार हुआ लेकिन सूचना ओवरलोड के कारण प्रिसिजन (precision) गिर गया; विधि इन बाधाओं के अनुकूल अच्छी तरह से ढलती है।

5. महत्व (Significance)

यह कार्य आधुनिक RAG सिस्टम की एक प्रमुख सीमा के लिए एक सैद्धांतिक रूप से आधारित और कम्प्यूटेशनल रूप से कुशल समाधान प्रदान करता है।

स्केलेबिलिटी: जैसे-जैसे LLM कॉन्टेक्स्ट विंडोज़ बढ़ती हैं, लीनियर या सुपर-लीनियर टाइम पेनल्टी के बिना बड़ी संख्या में विविध अनुच्छेदों ( $k$ ) को रिट्रीव करने की क्षमता महत्वपूर्ण है। यह विधि बड़े पैमाने पर विविधता-जागरूक रिट्रीवल को रियल-टाइम में संभव बनाती है।
मजबूती (Robustness): यह सिद्ध करके कि कंटीन्यूअस रिलैक्सेशन इंटीग्रल सॉल्यूशंस देता है, यह विधि उन हेयुरिस्टिक राउंडिंग स्टेप्स से बचती है जो अक्सर अन्य ऑप्टिमाइजेशन-आधारित रिट्रीवल दृष्टिकोणों में प्रदर्शन को कम कर देते हैं।
व्यावहारिकता: व्याख्या योग्य पैरामीटर $\theta$ अभ्यासकर्ताओं को विशिष्ट अनुप्रयोग आवश्यकताओं (जैसे, तथ्यात्मक कवरेज बनाम व्यापक विषय कवरेज को प्राथमिकता देना) के आधार पर अपने सिस्टम को आसानी से ट्यून करने की अनुमति देता है।

संक्षेप में, यह शोध पत्र विविधता-जागरूक रिट्रीवल को एक अनुमानित (heuristic), धीमी प्रक्रिया से एक मजबूत सैद्धांतिक गारंटी वाले सिद्धांत-आधारित ऑप्टिमाइजेशन समस्या में बदल देता है।