🤖 machine learning

Efficiently Representing Algorithms With Chain-of-Thought Transformers

यह शोध पत्र प्रदर्शित करता है कि चेन-ऑफ-थॉट ट्रांसफॉर्मर केवल पॉली-लॉगैरिद्मिक ओवरहेड के साथ वर्ड रैम एल्गोरिदम का कुशलतापूर्वक अनुकरण कर सकते हैं, जो ट्यूरिंग मशीन सिमुलेशन के लिए आवश्यक द्विघात (क्वाड्रेटिक) ओवरहेड से काफी बेहतर प्रदर्शन करता है।

मूल लेखक: Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

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

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

CC BY 4.0

मूल लेखक: Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

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

यहाँ शोध पत्र "Efficiently Representing Algorithms with Chain-of-Thought Transformers" का सरल भाषा और रचनात्मक उपमाओं (analogies) के साथ विवरण दिया गया है।

मुख्य समस्या: "टेप" बनाम "डेस्क"

कल्पना कीजिए कि आप एक जटिल गणित की समस्या हल करने की कोशिश कर रहे हैं।

पुराना तरीका (ट्यूरिंग मशीनें - Turing Machines):
एक ट्यूरिंग मशीन को एक ऐसे छात्र की तरह समझें जिसके पास केवल कागज की एक लंबी पट्टी (टेप) है। यदि उन्हें तीन पन्ने पहले लिखे गए किसी नंबर को देखना है, तो उन्हें उस नंबर को खोजने के लिए कागज पर कदम-दर-कदम पीछे तक शारीरिक रूप से चलना होगा। यदि वे 1,000 नामों की सूची को क्रमबद्ध (sort) करना चाहते हैं, तो उन्हें उस टेप पर हजारों बार आगे-पीछे चलना होगा। यह काम करता है, लेकिन यह अविश्वसनीय रूप से धीमा और उबाऊ है। इसी तरह अधिकांश पिछले कंप्यूटर विज्ञान सिद्धांतों ने सिद्ध किया था कि AI कैसे "सोच" सकता है।

असली तरीका (Word RAM):
अब, एक बड़े डेस्क और एक फाइलिंग कैबिनेट वाले छात्र की कल्पना करें। यह Word RAM मॉडल है। वे कैबिनेट से किसी भी फाइल को तुरंत उठा सकते हैं (रैंडम एक्सेस)। वे पूरे नंबरों पर एक साथ गणित कर सकते हैं, न कि बिट-दर-बिट। वास्तविक एल्गोरिदम (जैसे सूचियों को क्रमबद्ध करना या मानचित्र पर सबसे छोटा रास्ता खोजना) वास्तव में इसी तरह लिखे जाते हैं। यह बहुत तेज़ है।

प्रश्न:
हम जानते हैं कि "चेन-ऑफ-थॉट" (CoT) वाले AI मॉडल—जहाँ AI अपना उत्तर देने से पहले अपने तर्क के चरणों को लिखता है—उस धीमे "टेप" वाले छात्र का अनुकरण (simulate) कर सकते हैं। लेकिन क्या वे इस तेज़ "डेस्क" वाले छात्र का कुशलतापूर्वक अनुकरण कर सकते हैं? या क्या AI टेप की सुस्ती में फंस जाएगा, जिससे यह वास्तविक दुनिया के कार्यों के लिए बेकार हो जाएगा?

शोध पत्र का उत्तर: हाँ, लेकिन इसके लिए सही उपकरणों की आवश्यकता है

लेखक सिद्ध करते हैं कि हाँ, चेन-ऑफ-थॉट ट्रांसफॉर्मर इन तेज़, वास्तविक दुनिया के एल्गोरिदम का कुशलतापूर्वक अनुकरण कर सकते हैं। वे धीमे "टेप" के अवरोध (bottleneck) में नहीं फंसते हैं। हालाँकि, ऐसा करने के लिए, AI को कुछ विशिष्ट "ट्रिक्स" या आर्किटेक्चरल बदलावों की आवश्यकता होती है।

वे दिखाते हैं कि यह तीन अलग-अलग परिदृश्यों में काम करता है, जिन्हें हम AI द्वारा उपयोग किए जाने वाले तीन अलग-अलग प्रकार के "सोचने के पैड" (thinking pads) के रूप में देख सकते हैं:

1. "चौड़ा नोटबुक" (Polylog-Width Transformers)

उपमा: कल्पना कीजिए कि AI के पास एक नोटबुक है जो समस्या जितनी कठिन होती जाती है, उतनी ही चौड़ी होती जाती है। यदि समस्या बहुत बड़ी है, तो नोटबुक बहुत चौड़ी होगी।
यह कैसे काम करता है: AI अपनी मेमोरी की पूरी स्थिति को बाइनरी कोड (0 और 1) के रूप में पेज की चौड़ाई में लिख देता है। क्योंकि पेज पर्याप्त चौड़ा है, वह जानकारी को तेज़ी से देख सकता है।
लागत: यह कुशल है, लेकिन नोटबुक का आकार समस्या के आधार पर बदलता रहता है। यह "एक ही आकार सबके लिए" वाला उपकरण नहीं है।

2. "भूतिया स्क्रैचपैड" (Continuous CoT)

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

3. "मेमोरी सहायक" (Hybrid Transformer-RNN)

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

यह क्यों महत्वपूर्ण है ("ओवरहेड")

कंप्यूटर विज्ञान में, "ओवरहेड" का अर्थ है किसी कार्य को करने के लिए आवश्यक अतिरिक्त समय या प्रयास।

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

"बिट एक्सट्रैक्शन" (Bit Extraction) की चुनौती

एक प्रमुख बाधा जिसे लेखकों ने हल किया वह है बिट एक्सट्रैक्शन।

समस्या: गणित करने के लिए, AI को व्यक्तिगत बिट्स (0 और 1) को देखने की आवश्यकता होती है। लेकिन कुशल मॉडलों (जैसे घोस्टली स्क्रैचपैड) में, नंबर संकुचित सारांश के रूप में संग्रहीत होते हैं, न कि बिट्स की सूची के रूप में।
समाधान: लेखकों ने सिद्ध किया कि AI इन सारांशों से एक-एक करके बिट्स को "छील" (peel off) सकता है। यह एक सीलबंद लिफाफे (सारांश) होने जैसा है जिससे आप एक समय में एक अक्षर (बिट) निकाल सकते हैं, उसे पढ़ सकते हैं, और फिर पूरे लिफाफे को एक साथ खोले बिना अगले अक्षर के लिए लिफाफे को अपडेट कर सकते हैं।

सारांश

यह शोध पत्र एक सैद्धांतिक प्रमाण है कि AI तर्क (Chain-of-Thought) केवल एक दिखावा नहीं है; यह उन एल्गोरिदम जितना ही कुशल हो सकता है जिन्हें इंसान लिखते हैं।

पहले: हम जानते थे कि AI कंप्यूटर का अनुकरण कर सकता है, लेकिन केवल एक धीमे और बोझिल तरीके से (जैसे टेप वाला छात्र)।
अब: हम जानते हैं कि AI कंप्यूटर का कुशलतापूर्वक अनुकरण कर सकता है (जैसे डेस्क वाला छात्र), बशर्ते हम उसे सही उपकरण (चौड़े नोटबुक, अदृश्य स्याही, या मेमोरी सहायक) प्रदान करें।

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

तकनीकी सारांश: चेन-ऑफ-थॉट ट्रांसफॉर्मर के साथ एल्गोरिदम का कुशल प्रतिनिधित्व

समस्या विवरण
यद्यपि यह स्थापित है कि चेन-ऑफ-थॉट (CoT) ट्रांसफॉर्मर ट्यूरिंग पूर्ण (Turing complete) हैं—अर्थात किसी भी ट्यूरिंग मशीन (TM) का अनुकरण करने में सक्षम हैं—यह सैद्धांतिक सार्वभौमिकता व्यावहारिक एल्गोरिद्मिक कार्यों के लिए दक्षता की गारंटी नहीं देती है। एल्गोरिदम के लिए मानक जटिलता विश्लेषण 'वर्ड रैंडम एक्सेस मशीन' (Word RAM) मॉडल पर निर्भर करता है, जो रैंडम एक्सेस और $O(\log n)$ -बिट शब्दों पर यूनिट-कॉस्ट ऑपरेशंस की अनुमति देता है। इसके विपरीत, TMs में रैंडम एक्सेस का अभाव होता है, जिससे टेप पोजीशन को पार करने के लिए रैखिक समय (linear time) की आवश्यकता होती है। फलस्वरूप, एक Word RAM एल्गोरिदम का TM द्वारा अनुकरण करने में द्विघातीय ओवरहेड ( $O(t^2)$ ) आता है। यह शोध पत्र संबोधित करता है कि क्या CoT ट्रांसफॉर्मर सीधे Word RAM एल्गोरिदम का कुशलतापूर्वक अनुकरण कर सकते हैं, जिससे उनके पाठ्यपुस्तकीय जटिलता बाउंड्स (जैसे सॉर्टिंग के लिए $O(n \log n)$ ) से केवल पॉली-लॉग रिदम ओवरहेड तक ही मेल खा सके, न कि TM-आधारित अनुकरणों के द्विघातीय ओवरहेड तक।

कार्यप्रणाली
लेखक Word RAM प्रोग्रामों के प्रत्यक्ष अनुकरण के लिए CoT ट्रांसफॉर्मर का प्रस्ताव करते हैं, जो मध्यवर्ती TM अनुकरण को दरकिनार करते हैं। वे इस दक्षता को प्राप्त करने के लिए तीन अलग-अलग ट्रांसफॉर्मर सेटिंग्स का विश्लेषण करते हैं:

पॉलीलॉग-विड्थ ट्रांसफॉर्मर (Polylogarithmic-Width Transformers): यह सेटिंग $O(\log^2 n)$ चौड़ाई और राइटमोस्ट-यूनिक हार्ड अटेंशन (UHAT) वाले परिमित-परिशुद्धता (finite-precision) ट्रांसफॉर्मर का उपयोग करती है। मानों को रेसिडुअल स्ट्रीम में बाइनरी वेक्टर्स के रूप में दर्शाया जाता है। मेमोरी राइट्स को एड्रेस-वैल्यू पेयर्स के रूप में CoT ट्रांसक्रिप्ट में लॉग किया जाता है। मेमोरी रीड्स को इंडेक्स्ड अटेंशन मैकेनिज्म का उपयोग करके किया जाता है जो एक विशिष्ट एड्रेस के लिए सबसे हालिया राइट को पुनः प्राप्त करता है।
कंटीन्यूअस CoT (CCoT): यह सेटिंग फिक्स्ड-विड्थ, लॉग-प्रिसिजन ट्रांसफॉर्मर का उपयोग करती है जहाँ रीजनिंग स्टेप्स डिस्क्रीट टोकन्स के साथ निरंतर "सॉफ्ट टोकन्स" (रियल-वैल्यूड वेक्टर्स) उत्सर्जित करते हैं। यह मॉडल को डिस्क्रीट ट्रांसक्रिप्ट की चौड़ाई को बढ़ाए बिना डिकोडिंग स्टेप्स के दौरान निरंतर स्टेट (जैसे कि वैल्यूज के लेयर-नॉर्म हैश) बनाए रखने की अनुमति देता है।
हाइब्रिड ट्रांसफॉर्मर-RNN मॉडल: यह सेटिंग फिक्स्ड-विड्थ ट्रांसफॉर्मर के साथ एक लीनियर रिकरेंट न्यूरल नेटवर्क (RNN) लेयर को जोड़ती है। RNN घटक समय के चरणों (time steps) में वैल्यू रिप्रेजेंटेशन (लेयर-नॉर्म हैश) की निरंतरता को संभालने का कार्य करता है, जो निरंतर CoT के लिए एक व्यावहारिक विकल्प के रूप में कार्य करता है।

फिक्स्ड-विड्थ सेटिंग्स (2 और 3) में एक प्रमुख तकनीकी घटक के रूप में लेयर-नॉर्म हैश ( $\phi(v)$ ) का उपयोग किया गया है। यह प्रतिनिधित्व इनर प्रोडक्ट के माध्यम से सटीक समानता जांच (equality checks) की अनुमति देता है और एफाइन अपडेट्स (affine updates) का समर्थन करता है, जिससे बिट स्ट्रीम में वैल्यूज का सीरियलाइजेशन और डी-सीरियलाइजेशन संभव हो पाता है। लेखक एक "प्रतिबंधित" (restricted) Word RAM नॉर्मल फॉर्म भी पेश करते हैं, जो यह सुनिश्चित करता है कि स्टेप $s$ पर सभी मान $v \le s$ हों, जिससे बिट एक्सट्रैक्शन और डिवीजन ऑपरेशंस सरल हो जाते हैं।

प्रमुख योगदान
यह शोध पत्र सैद्धांतिक प्रमाण प्रदान करता है कि CoT ट्रांसफॉर्मर तीन विशिष्ट आर्किटेक्चर में पॉली-लॉग ओवरहेड के साथ Word RAM एल्गोरिदम का अनुकरण कर सकते हैं:

पॉलॉग-विड्थ सिमुलेशन (Theorem 1): $O(\log^2 n)$ चौड़ाई और राइटमोस्ट UHAT वाला एक परिमित-परिशुद्धता ट्रांसफॉर्मर एक फ्लैट Word RAM प्रोग्राम का अनुकरण कर सकता है। एक प्रोग्राम जो $t$ स्टेप्स चलता है और जिसका वर्ड साइज $w = \Theta(\log(n+t))$ है, उसके लिए सिमुलेशन को $O(t \cdot w^2) = O(t \log^2(n+t))$ CoT टोकन्स की आवश्यकता होती है। यदि इंस्ट्रक्शन सेट मल्टीप्लिकेशन, डिवीजन और मोड्यूलो को बाहर रखता है, तो ओवरहेड घटकर $O(t \cdot w) = O(t \log(n+t))$ हो जाता है।
कंटीन्यूअस CoT सिमुलेशन (Theorem 3): एक फिक्स्ड-विड्थ, लॉग-प्रिसिजन ट्रांसफॉर्मर जिसमें कंटीन्यूअस CoT है, किसी भी Word RAM प्रोग्राम को $O(t \cdot \kappa(w))$ डिकोडिंग स्टेप्स में अनुकरण कर सकता है, जहाँ $\kappa(w)$ एक Word RAM इंस्ट्रक्शन को निष्पादित करने की TM लागत है। फ्लैट इंस्ट्रक्शन सेट्स के लिए, यह सरल अंकगणित के लिए $O(t \log(n+t))$ और पूर्ण अंकगणित के लिए $O(t \log^2(n+t))$ प्रदान करता है।
हाइब्रिड मॉडल सिमुलेशन (Theorem 4): एक फिक्स्ड-विड्थ हाइब्रिड मॉडल (ट्रांसफॉर्मर + लीनियर RNN) कंटीन्यूअस CoT सेटिंग के समान $O(t \cdot \kappa(w))$ जटिलता प्राप्त करता है, जो यह दर्शाता है कि रिकरेंस, निरंतर सॉफ्ट टोकन्स के माध्यम से स्टेट बनाए रखने के लिए प्रतिस्थापन के रूप में कार्य कर सकता है।

परिणाम

दक्षता लाभ (Efficiency Gain): प्रस्तावित सिमुलेशन TM-आधारित CoT सिमुलेशन में होने वाले द्विघातीय ( $O(t^2)$ ) ओवरहेड को पॉली-लॉग ( $O(t \log^2 n)$ या $O(t \log n)$ ) में कम करते हैं।
टाइटनेस (Tightness): डिस्क्रीट CoT के लिए सरल अंकगणित के साथ, $O(t \log n)$ ओवरहेड सूचना-सैद्धांतिक निचली सीमा $\Omega(t \log n)$ से मेल खाता है, क्योंकि $w$ -बिट वर्ड को दर्शाने के लिए $\Omega(w)$ टोकन्स की आवश्यकता होती है।
इंस्ट्रक्शन सेट डिपेंडेंस: ओवरहेड Word RAM निर्देशों की जटिलता पर निर्भर करता है। "फ्लैट" इंस्ट्रक्शन सेट्स (नेस्टेड एक्सप्रेशंस के बिना) कुशल सिमुलेशन की अनुमति देते हैं। मल्टीप्लिकेशन, डिवीजन और मोड्यूलो ऑपरेशंस को $O(w)$ माइक्रो-स्टेप्स की आवश्यकता होती है, जिससे पोलॉग-विड्थ सेटिंग में प्रति-इंस्ट्रक्शन $O(w^2)$ ओवरहेड होता है, जबकि सरल अंकगणित (एडिशन, बिटवाइज ऑप्स) के लिए केवल $O(w)$ की आवश्यकता होती है।

महत्व
यह शोध पत्र जटिल कार्यों को हल करने के लिए रीजनिंग मॉडल्स को प्रशिक्षित करने के अनुभवजन्य अभ्यास (empirical practice) को सही ठहराता है, यह दिखाते हुए कि CoT ट्रांसफॉर्मर अपने मूलतम दक्षता के साथ पाठ्यपुस्तकीय एल्गोरिदम को निष्पादित कर सकते हैं। यह ट्रांसफॉर्मर की ट्यूरिंग पूर्णता और एल्गोरिद्मिक रीजनिंग के लिए आवश्यक व्यावहारिक दक्षता के बीच के अंतर को पाटता है। यह प्रदर्शित करके कि न्यूनतम आर्किटेक्चरल विस्तार (निरंतर CoT या RNN लेयर्स) फिक्स्ड-विड्थ ट्रांसफॉर्मर को कुशलतापूर्वक Word RAM का अनुकरण करने में सक्षम बनाते हैं, यह पेपर तर्क देता है कि पिछले TM-आधारित सिमुलेशन का द्विघातीय ओवरहेड, सिमुलेशन पद्धति का एक आर्टिफैक्ट था, न कि CoT ट्रांसफॉर्मर की कोई अंतर्निहित सीमा। यह कार्य स्थापित करता है कि CoT, कुछ आर्किटेक्चरल स्थितियों के तहत, एल्गोरिदम को उनके सामान्य पाठ्यपुस्तकीय रनटाइम के पॉली-लॉग फैक्टर तक अनुकरण करने की अनुमति देता है।