💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

यह शोध पत्र टेंसरयुक्त परिमित ऑटोमेटा (tensorized finite automata) और सर्किट गुणन के माध्यम से सुलभ, वैश्विक रूप से बाधित प्रस्तावों का निर्माण करके स्थानीय रूप से बाधित डिकोडिंग में पूर्वाग्रह को कम करने के लिए एक सामान्य दृष्टिकोण प्रस्तावित करता है, जो फंक्शन कॉलिंग और SQL जनरेशन जैसे कार्यों में कम कणों (particles) के साथ लक्ष्य वितरण की ओर तेजी से अभिसरण करने वाले कुशल अनुक्रमिक मोंटे कार्लो (Sequential Monte Carlo) सैंपलिंग को सक्षम बनाता है।

मूल लेखक: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

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

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

CC BY 4.0

मूल लेखक: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

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

कल्पना कीजिए कि आप एक बहुत ही रचनात्मक लेकिन थोड़े अराजक कहानीकार (एक लार्ज लैंग्वेज मॉडल) को एक ऐसी कहानी लिखना सिखाने की कोशिश कर रहे हैं जो एक बहुत ही सख्त नियम पुस्तिका, जैसे कि JSON कोड फॉर्मेट या एक विशिष्ट SQL डेटाबेस क्वेरी का पालन करती हो।

समस्या यह है कि कहानीकार भटकना पसंद करता है। यदि आप केवल कहते हैं, "नियमों को न तोड़ें," तो वे एक ऐसा वाक्य शुरू कर सकते हैं जो देखने में तो ठीक लगता है लेकिन अंत तक पहुँचते-पहुँचते असंभव हो जाता है।

यहाँ यह पेपर इस समस्या को हल करने का तरीका बताता है, सरल उपमाओं का उपयोग करते हुए:

1. पुराना तरीका: "अल्पदृष्टि वाला" मार्गदर्शक (LCD)

कल्पना कीजिए कि कहानीकार एक भूलभुलैया में चल रहा है। पुराना तरीका (जिसे Locally Constrained Decoding या LCD कहा जाता है) एक ऐसे मार्गदर्शक की तरह काम करता है जो केवल अगले कदम को देखता है।

यह कैसे काम करता है: यदि अगला कदम ऐसा दिखता है जिससे संभवतः दीवार टकरा सकती है, तो मार्गदर्शक उसे रोकता है।
दोष: मार्गदर्शक "मायोपिक" (अल्पदृष्टि वाला) है। वे कहानीकार को ऐसा रास्ता लेने दे सकते हैं जो अगले कदम के लिए सुरक्षित दिखता है लेकिन तीन कदम बाद एक डेड एंड (बंद रास्ते) की ओर ले जाता है। कहानीकार चलते रहते हैं, यह सोचकर कि वे ठीक हैं, केवल तभी एहसास होता है कि वे अंत में एक वैध कहानी पूरी नहीं कर सकते। उन्हें फिर से शुरुआत करनी पड़ती है या एक टूटी हुई कहानी बनानी पड़ती है।

2. नया तरीका: "ग्लोबल मैप" (GCD)

लेखक एक नया तरीका प्रस्तावित करते हैं जिसे Globally Constrained Decoding (GCD) कहा जाता है।

उपमा: केवल अगले कदम को देखने के बजाय, इस मार्गदर्शक के पास पूरे भूलभुलैया का एक पूर्ण मानचित्र (Complete Map) है और उसे पता है कि बाहर निकलने के लिए कितने कदम शेष हैं।
यह कैसे काम करता है: कहानीकार द्वारा कदम उठाने से पहले, मार्गदर्शक जाँच करता है: "यदि आप इस तरफ जाते हैं, तो क्या आप वास्तव में शेष कदमों के भीतर निकास तक पहुँच सकते हैं?"
परिणाम: यदि उत्तर "नहीं" है, तो मार्गदर्शक उस रास्ते को तुरंत ब्लॉक कर देता है। यह गारंटी देता है कि कहानीकार चाहे जो भी चुने, वे हमेशा एक वैध अंत तक पहुँचेंगे। यह एक ऐसे GPS की तरह है जो केवल वही मार्ग दिखाता है जो आपको समय पर आपकी मंजिल तक पहुँचाने की गारंटी देते हैं।

3. "स्मार्ट" मैप: संभाव्यता जोड़ना (P-GCD)

"ग्लोबल मैप" (GCD) डेड एंड से बचने में तो बेहतरीन है, लेकिन यह सभी वैध रास्तों को समान मानता है। इसे यह नहीं पता कि कहानीकार किस रास्ते को पसंद करता है या कौन सा रास्ता एक अच्छी कहानी होने की अधिक संभावना रखता है।

उपमा: कल्पना कीजिए कि कहानीकार के चलने का एक पसंदीदा तरीका है। बुनियादी मैप केवल कहता है, "यह रास्ता वैध है।" नया Probabilistic GCD (P-GCD) कहता है, "यह रास्ता वैध है, और यह वह रास्ता भी है जिसे कहानीकार सबसे अधिक पसंद करेगा।"
यह कैसे काम करता है: लेखक "ग्लोबल मैप" (नियमों) को एक "मेमोरी मॉडल" (कहानीकार के मस्तिष्क का एक सरलीकृत संस्करण) के साथ मिलाते हैं। वे इन दोनों को आपस में गुणा करते हैं।
परिणाम: मार्गदर्शक अब केवल बुरे रास्तों को रोकता ही नहीं है; बल्कि वह कहानीकार को उन रास्तों की ओर धीरे से धकेलता है जो वैध भी हैं और उच्च गुणवत्ता वाले भी हैं। यह कहानी सुनाने की प्रक्रिया को बहुत अधिक कुशल बनाता है।

4. "पार्टिकल" रेस (SMC)

इन तरीकों का परीक्षण करने के लिए, शोधकर्ता Sequential Monte Carlo (SMC) नामक एक तकनीक का उपयोग करते हैं।

उपमा: कल्पना कीजिए कि आप एक धुंधले जंगल में सबसे अच्छा रास्ता खोजने की कोशिश कर रहे हैं। एक व्यक्ति भेजने के बजाय, आप 100 "पार्टिकल्स" (एक्सप्लोरर्स/खोजकर्ताओं) का एक झुंड भेजते हैं।
पुराना तरीका: अल्पदृष्टि वाले मार्गदर्शक के साथ, आपको हजारों खोजकर्ताओं को भेजने की आवश्यकता होती है क्योंकि उनमें से कई खत्म होने से पहले ही रास्ता भटक जाते हैं या डेड एंड से टकरा जाते हैं।
नया तरीका: "ग्लोबल मैप" और "स्मार्ट मैप" के साथ, खोजकर्ता सही रास्ते पर रहते हैं। आपको सही रास्ता खोजने के लिए बहुत कम खोजकर्ताओं की आवश्यकता होती है क्योंकि मार्गदर्शक बुरे विकल्पों को जल्दी से छानने में बहुत बेहतर है।

5. "शेप-शिफ्टिंग" ट्रिक (Tensorization)

"मैप" को संभालने का एक तकनीकी चमत्कार इस पेपर का एक हिस्सा है।

समस्या: जटिल नियम (जैसे JSON स्कीमा) लाखों रास्तों वाले मैप बना सकते हैं। आमतौर पर, कंप्यूटर इन मैप्स को एक मानक प्रोसेसर पर प्रोसेस करने में अभिभूत हो जाते हैं।
समाधान: लेखकों ने इन जटिल मैप्स को गणितीय ब्लॉकों (Tensors) में बदल दिया जो आधुनिक ग्राफिक्स कार्ड्स (GPUs) पर पूरी तरह फिट बैठते हैं।
उपमा: यह कागज के विशाल, बिखरे हुए नक्शों के ढेर को एक कॉम्पैक्ट, हाई-स्पीड डिजिटल चिप में मोड़ने जैसा है जिसे एक सुपरकंप्यूटर तुरंत पढ़ सकता है। यह "ग्लोबल मैप" को बहुत जटिल नियमों के लिए भी पलक झपकते ही कैलकुलेट करने की अनुमति देता है।

परिणामों का सारांश

इस पेपर का परीक्षण तीन वास्तविक दुनिया के कार्यों पर किया गया:

फंक्शन कॉलिंग: यह सुनिश्चित करना कि AI कंप्यूटर फंक्शन्स को सही फॉर्मेट (जैसे JSON) के साथ कॉल करे।
कीवर्ड जनरेशन: यह सुनिश्चित करना कि एक कहानी में विशिष्ट शब्द शामिल हों।
SQL जनरेशन: डेटाबेस क्वेरी लिखना जो सिंटैक्स के अनुसार सही हो।

निर्णय:

विश्वसनीयता: नया तरीका गारंटी देता है कि कहानी शब्द सीमा के भीतर सही ढंग से समाप्त होगी, जबकि पुराना तरीका अक्सर फिनिश लाइन पर विफल हो जाता है।
दक्षता: समान गुणवत्ता के परिणाम प्राप्त करने के लिए, नए तरीके को पुराने तरीके की तुलना में काफी कम "एक्सप्लोरर्स" (पार्टिकल्स) की आवश्यकता होती है।
गति: हालांकि "स्मार्ट मैप" (P-GCD) अधिक कंप्यूटिंग पावर लेता है, फिर भी यह व्यावहारिक रूप से तेज़ है, और "ग्लोल मैप" (GCD) पुराने तरीके के लगभग उतना ही तेज़ है।

संक्षेप में, यह पेपर AI को एक "ग्लोबल मैप" और एक "स्मार्ट नज़" (स्मार्ट संकेत) देता है ताकि वह बिना रास्ता भटके, समय बर्बाद किए या टूटा हुआ कोड बनाए, सख्त नियमों का पालन कर सके।

तकनीकी सारांश: सुलभ प्रस्तावों के माध्यम से स्थानीय रूप से बाधित डिकोडिंग में पूर्वाग्रह को कम करना

समस्या विवरण

लार्ज लैंग्वेज मॉडल्स (LLMs) अक्सर ऐसे आउटपुट उत्पन्न करने में विफल रहते हैं जो तार्किक या संरचनात्मक बाधाओं (constraints), जैसे कि JSON स्कीमा, वैध SQL क्वेरी, या विशिष्ट फंक्शन-कॉलिंग प्रारूपों का सख्ती से पालन करते हैं। हालांकि इंस्ट्रक्शन ट्यूनिंग और प्रेफरेंस ऑप्टिमाइजेशन ने सामान्य संरेखण (alignment) में सुधार किया है, फिर भी वे "कठोर" बाधाओं को लागू करने के लिए अविश्वसनीय बने हुए हैं।

मौजूदा दृष्टिकोण दो प्राथमिक सीमाओं का सामना करते हैं:

रिजेक्शन सैंपलिंग (Rejection Sampling): हालांकि यह निष्पक्ष (unbiased) है, लेकिन जटिल बाधाओं के लिए यह कम्प्यूटेशनल रूप से अव्यवहार्य है क्योंकि इसमें स्वीकृति दर अत्यंत कम होती है।
लोकलली कंस्ट्रेंड डिकोडिंग (Locally Constrained Decoding - LCD): यह मानक दृष्टिकोण प्रत्येक चरण पर उन टोकन को मास्क करता है जो तुरंत बाधा का उल्लंघन करते हैं। हालांकि, यह दो गंभीर दोषों से ग्रस्त है:
- पूर्वाग्रह (Bias): यह भविष्य की वैधता पर विचार किए बिना टोकन को संकुचित (myopically) रूप से मास्क करके मॉडल के अंतर्निहित वितरण को विकृत कर देता है, जिससे सैंपलिंग बायस पैदा होता है।
- समाप्ति गारंटी का अभाव (No Termination Guarantee): LCD केवल स्थानीय वैधता सुनिश्चित करता है। एक अनुक्रम (sequence) लंबे समय तक स्थानीय रूप से वैध रह सकता है (जैसे, JSON में एक खुला हुआ ब्रैकेट) लेकिन एक निश्चित टोकन बजट $n$ के भीतर बाधा को पूरा करने में विफल हो सकता है।

इन मुद्दों को संबोधित करने के लिए, सिक्वेंशियल मोंटे कार्लो (SMC) फ्रेमवर्क प्रस्तावित किया गया है, जो LCD को एक प्रपोजल डिस्ट्रीब्यूशन (proposal distribution) के रूप में उपयोग करता है और लक्षित वितरण (target distribution) की ओर बढ़ने के लिए पार्टिकल्स को री-वेट (re-weight) करता है। हालाँकि, SMC की अभिसरण दर (convergence rate) प्रपोजल की गुणवत्ता द्वारा बाधित होती है; LCD एक कमजोर प्रपोजल है क्योंकि इसमें भविष्य के वैध पूर्णता (completions) के बारे में संभाव्य जानकारी का अभाव है और यह सीमित बजट के भीतर बाधा संतुष्टि की गारंटी नहीं देता है।

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

लेखक $p_{lm}(\cdot \mid C)$ से बाधित वितरण से SMC सैंपलिंग के लिए सुलभ प्रस्ताव (tractable proposals) और पोटेंशियल फंक्शन्स (potential functions) बनाने के लिए एक सामान्य दृष्टिकोण प्रस्तावित करते हैं। मुख्य नवाचार बाधाओं को 'फाइनाइट ऑटोमेटा' (Finite Automata) के रूप में प्रस्तुत करना और कुशल GPU निष्पादन के लिए टेंसर ऑपरेशंस का लाभ उठाना है।

1. ग्लोबली कंस्ट्रेंड डिकोडिंग (Globally Constrained Decoding - GCD)

GCD, LCD की तुलना में बेहतर है क्योंकि यह सुनिश्चित करता है कि प्रत्येक उत्पन्न टोकन शेष टोकन बजट $n$ के भीतर एक वैध पूर्णता की ओर ले जा सके।

टेंसरइज्ड फाइनाइट ऑटोमेटा (Tensorized Finite Automata): फाइनाइट ऑटोमेटा (FA) के रूप में एनकोडेड बाधाओं (विशेष रूप से NFAs और DFAs) को टेंसरइज्ड रिप्रेसेंटेशन (ट्रांजिशन मैट्रिसेस $T_{out}, T_{in}$ और एमिशन मैट्रिक्स $B_f$ ) में संकलित किया जाता है। यह GPU पर कुशल निष्पादन की अनुमति देता है।
फॉरवर्ड-बैकवर्ड इन्फरेंस (Forward-Backward Inference):
- फॉरवर्ड प्रोसेस: यह प्रेक्षित प्रीफिक्स $x_{1:t-1}$ के बाद सुलभ FA अवस्थाओं (states) के सेट की गणना करता है।
- बैकवर्ड प्रोसेस: यह गणना करता है कि क्या कोई अवस्था ठीक $n-t$ चरणों में एक स्वीकार्य अवस्था तक पहुँच सकती है।
ग्लोबल मास्किंग: एक टोकन केवल तभी अनुमत है यदि वह ऐसी अवस्था की ओर ले जाता है जो शेष बजट के भीतर एक वैध निरंतरता (continuation) को सक्षम करती है। यह गारंटी देता है कि लंबाई $n$ वाला कोई भी अनुक्रम जो GCD के तहत उत्पन्न होता है, बाधा $C$ को संतुष्ट करता है।

2. प्रोबेबिलिस्टिक ग्लोबली कंस्ट्रेंड डिकोडिंग (Probabilistic GCD - P-GCD)

जबकि GCD बाधा संतुष्टि की गारंटी देता है, इसका मास्क बाइनरी (वैध/अवैध) है और यह LLM के तहत वैध पूर्णता की संभावना को अनदेखा करता है। P-GCD इसे संभाव्य जानकारी को एकीकृत करके संबोधित करता है।

HMM डिस्टिलेशन (HMM Distillation): LLM के वितरण को एक हिडन मार्कोव मॉडल (HMM) द्वारा अनुमानित किया जाता है, जो पूर्व कार्य (Zhang et al., 2023) का अनुसरण करता है।
सर्किट मल्टीप्लिकेशन (Circuit Multiplication): टेंसरइज्ड FA (जिसे एक अनॉर्मलाइज्ड HMM के रूप में देखा जाता है) को डिस्टिल्ड HMM के साथ सर्किट मल्टीप्लिकेशन एल्गोरिदम का उपयोग करके गुणा किया जाता है। यह FAs और HMMs की साझा बीजगणितीय संरचना का लाभ उठाता है।
प्रोडक्ट डिस्ट्रीब्यूशन (Product Distribution): परिणामी प्रोडक्ट डिस्ट्रीब्यूशन $p_{prod}$ FA के कठोर तार्किक बाधाओं और LLM की संभाव्य प्राथमिकताओं दोनों को कैप्चर करता है।
प्रपोजल और पोटेंशियल (Proposal and Potential):
- प्रपोजल ( $q_{pgcd}$ ): यह $p_{prod}$ से प्राप्त बाधित अगले-टोकन की संभावना का उपयोग करके प्रत्येक चरण पर LM वितरण को रीवेट करता है।
- पोटेंशियल ( $\phi_{pgcd}$ ): यह SMC में पार्टिकल्स को LM की प्रीफिक्स संभावना और बाधा संतुष्टि के संबंध में HMM के लुक-अहेड (look-ahead) अनुमान के गुणनफल द्वारा वेट देता है।

3. कुशल कार्यान्वयन (Efficient Implementation)

लेखक बड़े क्रोनेकर-प्रोडक्ट मैट्रिसेस को स्पष्ट रूप से प्रकट करने से बचने के लिए टेंसर-नेटवर्क ऑपरेशंस (विशेष रूप से क्रोनेकर-वेक आइडेंटिटी) का उपयोग करते हैं। यह ट्रांजिशन स्टेप्स की कम्प्यूटेशनल लागत को $O((HE)^2)$ से घटाकर $O(H^2E + HE^2)$ कर देता है (जहाँ $H$ HMM का हिडन साइज है और $E$ FA एज काउंट है), जिससे कुशल ऑटोरेग्रेसिव जनरेशन संभव होता है।

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

GCD और P-GCD फ्रेमवर्क: ग्लोबली कंस्ट्रेंड डिकोडिंग और प्रोबेबिलिस्टिक GCD का परिचय, जो SMC के लिए सुलभ प्रस्ताव और पोटेंशियल प्रदान करते हैं जो टोकन बजट के भीतर बाधा संतुष्टि की गारंटी देते हैं।
GPUs पर टेंसरइज्ड ऑटोमेटा: कुशल GPU-नेटिव इन्फरेंस के लिए फाइनाइट ऑटोमेटा (NFAs सहित) को टेंसराइज़ करने वाला पहला प्रस्ताव, जो Outlines और XGrammar जैसे मौजूदा फ्रेमवर्क की CPU-बाउंड सीमाओं को दूर करता है।
NFA सपोर्ट: यह प्रदर्शित करना कि जटिल बाधाओं (जैसे वेरिएबल पैरामीटर्स के साथ फंक्शन कॉलिंग) के लिए NFAs, DFAs की तुलना में घातीय रूप से अधिक संक्षिप्त (succinct) हो सकते हैं, जिससे यह दृष्टिकोण वास्तविक दुनिया के एजेंटिक अनुप्रयोगों के लिए स्केलेबल बनता है जहाँ DFA निर्माण मेमोरी ओवरफ्लो का कारण बन सकता है।
SMC के साथ एकीकरण: यह दिखाना कि (P-)GCD, LCD-आधारित प्रस्तावों की तुलना में SMC अभिसरण को काफी तेज करता है, जिसके लिए बहुत कम पार्टिकल्स की आवश्यकता होती है।

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

लेखकों ने तीन बेंचमार्क पर (P-)GCD का मूल्यांकन किया: xLAM (फंक्शन कॉलिंग), CommonGen (कीवर्ड-आधारित जनरेशन), और Spider (टेक्स्ट-टू-SQL)।

फंक्शन कॉलिंग (xLAM):
- (P-)GCD ने समान संख्या में पार्टिकल्स पर LCD की तुलना में काफी उच्च सटीकता प्राप्त की।
- P-GCD, GCD की तुलना में ग्राउंड-ट्रुथ डिस्ट्रीब्यूशन (रिजेक्शन सैंपलिंग) तक तेजी से पहुँचा, जो संभाव्य जानकारी के लाभ को उजागर करता है।
- बाधा संतुष्टि (Constraint Satisfaction): GCD और P-GCD ने सभी पार्टिकल बजटों में 100% बाधा संतुष्टि दर प्राप्त की, जबकि LCD मध्यम बजट (जैसे JSON के लिए ~95%) पर भी बाधाओं को पूरा करने में विफल रहा।
- दक्षता (Efficiency): LCD और GCD ने मामूली ओवरहेड (1.08× और 1.10× स्लोडाउन) दर्ज किया। HMM गणनाओं के कारण P-GCD धीमा था (3.11× से 10.2×), लेकिन फिर भी व्यवहार्य बना रहा।
कीवर्ड जनरेशन (CommonGen): प्रपोजल और पोटेंशियल दोनों के रूप में P-GCD का उपयोग करने से LCD की तुलना में BLEU स्कोर और अभिसरण गति में महत्वपूर्ण सुधार हुआ।
टेक्स्ट-टू-SQL (Spider): GCD और P-GCD ने विभिन्न पार्टिकल बजटों में, विशेष रूप से मध्यम मानों पर, LCD की तुलना में निष्पादन सटीकता (execution accuracy) में सुधार किया।
NFA बनाम DFA: प्रयोगों ने पुष्टि की कि जटिल स्कीमा (जैसे वेरिएबल-लेंथ फंक्शन पैरामीटर्स) के लिए, NFAs आकार में रैखिक रूप से बढ़ते हैं जबकि DFAs घातीय रूप से बढ़ते हैं। Spider SQL ग्रामर के लिए, DFA निर्माण के परिणामस्वरूप टोकन स्तर पर आउट-ऑफ-मेमोरी (OOM) त्रुटियां हुईं, जबकि NFA व्यवहार्य (~32k स्टेट्स) बना रहा।

महत्व और दावे (Significance and Claims)

पेपर का दावा है कि लोकली कंस्ट्रेंड डिकोडिंग पर्याप्त सैंपलिंग बायस पेश करती है और सीमित टोकन बजट के भीतर बाधा संतुष्टि की गारंटी देने में विफल रहती है। (P-)GCD का प्रस्ताव देकर, लेखक एक ऐसा समाधान प्रदान करते हैं जो:

वैधता की गारंटी देता है: यह सुनिश्चित करता है कि लंबाई $n$ वाला कोई भी उत्पन्न अनुक्रम बाधा को संतुष्ट करता है, जिससे LCD के फेल्योर केस समाप्त हो जाते हैं।
पूर्वाग्रह को कम करता है: संभाव्य जानकारी (P-GCD के माध्यम से) और ग्लोबल लुकअहेड को शामिल करके, प्रपोजल लक्षित कंडीशनल डिस्ट्रीब्यूशन का बेहतर अनुमान लगाते हैं।
दक्षता में सुधार करता है: SMC फ्रेमवर्क में, (P-)GCD, LCD-आधारित दृष्टिकोणों की तुलना में बहुत कम पार्टिकल्स के साथ लक्षित वितरण तक अभिसरण करता है, जिससे उच्च-गुणवत्ता वाले बाधित जनरेशन की कम्प्यूटेशनल लागत कम हो जाती है।

यह कार्य खुद को उन अनुप्रयोगों के लिए विश्वसनीय, बाधा-संतुष्ट जनरेशन की दिशा में एक मौलिक कदम के रूप में स्थापित करता है जिनमें सख्त संरचनात्मक पालन (जैसे फंक्शन कॉलिंग और कोड जनरेशन) की आवश्यकता होती है, जो लॉजिकल बाधाओं (ऑटोमेटा के माध्यम से) और संभाव्य मॉडलिंग (HMM के माध्यम से) को एक GPU-कुशल तरीके से एकीकृत करता है।