💬 NLP

Incremental BPE Tokenization

यह शोध पत्र एक नवीन इंक्रीमेंटल बाइट पेयर एनकोडिंग (BPE) टोकनाइजेशन एल्गोरिदम पेश करता है जो $\mathcal{O}(n \log^2 t)$ की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी प्राप्त करता है, जो Hugging Face के टोकनाइज़र और tiktoken जैसी मौजूदा लाइब्रेरीज़ की तुलना में 3x तक की गति वृद्धि के साथ कुशल स्ट्रीमिंग प्रोसेसिंग को सक्षम बनाता है।

मूल लेखक: Shenghu Jiang, Ruihao Gong

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

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

CC BY 4.0

मूल लेखक: Shenghu Jiang, Ruihao Gong

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

कल्पना कीजिए कि आप एक लंबी किताब पढ़ रहे हैं, लेकिन शब्द दर शब्द पढ़ने के बजाय, आप इसे "बाइट दर बाइट" (टेक्स्ट के सबसे छोटे डिजिटल निर्माण खंडों) पढ़ रहे हैं। आपका लक्ष्य इन बाइट्स को सार्थक टुकड़ों में समूहित करना है जिन्हें "टोकन" कहा जाता है ताकि कंप्यूटर उन्हें समझ सके। इस प्रक्रिया को टोकेनाइजेशन (tokenization) कहा जाता है, और इसे करने का सबसे लोकप्रिय तरीका बाइट पेयर एनकोडिंग (Byte Pair Encoding - BPE) है।

BPE को लेगो (Lego) के खेल की तरह समझें। आप व्यक्तिगत ईंटों (बाइट्स) से शुरुआत करते हैं। खेल के नियम कहते हैं: "यदि आप देखते हैं कि दो विशिष्ट ईंटें अक्सर एक-दूसरे के बगल में होती हैं, तो उन्हें एक बड़ी, कस्टम ईंट बनाने के लिए आपस में जोड़ दें।" आप ईंटों को आपस में जोड़ते रहते हैं, जोड़ों को जोड़कर बड़ी संरचनाएं बनाते रहते हैं, जब तक कि आपके पास छोटे ईंटों और बड़ी, कस्टम-निर्मित संरचनाओं का मिश्रण न हो जाए।

समस्या: "इंतज़ार-और-देखो" की बाधा (The "Wait-and-See" Bottleneck)

वर्तमान में, अधिकांश कंप्यूटर प्रोग्राम जो यह लेगो गेम खेलते हैं, वे ऑफलाइन होते हैं। वे पूरी दीवार को जोड़ने से पहले टेक्स्ट का पूरा पेज मांगते हैं।

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

समाधान: "इन्क्रीमेंटल" बिल्डर (The "Incremental" Builder)

इस शोध पत्र के लेखक लेगो गेम खेलने का एक नया, स्मार्ट तरीका प्रस्तावित करते हैं। वे इसे इन्क्रीमेंटल BPE टोकेनाइजेशन (Incremental BPE Tokenization) कहते हैं।

पूरी ट्रक की डिलीवरी का इंतजार करने के बजाय, उनका एल्गोरिदम जैसे ही प्रत्येक नई बाइट आती है, ईंटों को आपस में जोड़ देता है।

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

मुख्य विशेषताएं और लाभ

1. गति और स्थिरता (The "No Meltdown" Guarantee)

दावा: पुराने तरीके कभी-कभी धीमे हो जाते हैं या क्रैश हो जाते हैं यदि टेक्स्ट में अजीब पैटर्न (जैसे एक पंक्ति में दस लाख "a" अक्षर) हों। नया तरीका एक बुलेटप्रूफ जैकेट की तरह है; यह गारंटी देता है कि यह कभी धीमा नहीं होगा, चाहे टेक्स्ट कितना भी अजीब क्यों न हो।
परिणाम: यह वर्तमान उद्योग मानक (Hugging Face के टोकेनाइज़र) की तुलना में 3 गुना तक तेज़ है और "पैथोलॉजिकल" (अजीब) इनपुट को बिना धीमे हुए संभालता है, जबकि OpenAI का tiktoken इसमें फंस सकता है।

2. स्ट्रीमिंग आउटपुट (The "Eager" Chef)

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

3. ड्रॉप-इन रिप्लेसमेंट (Drop-in Replacement)

दावा: यह नया एल्गोरिदम एक प्लग-एंड-प्ले अपग्रेड के रूप में डिज़ाइन किया गया है। आपको अपना पूरा AI सिस्टम फिर से बनाने की आवश्यकता नहीं है; आप बस पुराने टोकेनाइजेशन टूल को इस नए टूल से बदल देते हैं, और यह बिल्कुल उसी तरह काम करता है लेकिन बहुत अधिक तेज़ी से।

सारांश

सरल शब्दों में, यह शोध पत्र AI टेक्स्ट प्रोसेसिंग के लिए एक सुपर-एफिशिएंट, रियल-टाइम लेगो बिल्डर प्रस्तुत करता है।

पुराना तरीका: पूरे टेक्स्ट का इंतजार करें, फिर सब कुछ एक साथ बनाएं। (धीमा, देरी की संभावना)।
नया तरीका: जैसे ही हर एक अक्षर आए, थोड़ा-थोड़ा निर्माण करें। (तेज़, स्थिर, और AI को आपके टाइप करते समय ही जवाब देने की अनुमति देता है)।

लेखकों ने गणितीय रूप से सिद्ध किया है कि यह विधि तेज़, विश्वसनीय है, और मौजूदा नियमों के साथ पूरी तरह से काम करती है कि AI टेक्स्ट को कैसे समझता है, जो आधुनिक भाषा मॉडलों के लिए महत्वपूर्ण गति वृद्धि प्रदान करता है।

तकनीकी सारांश: इंक्रीमेंटल बीपीई (BPE) टोकनाइज़ेशन

समस्या विवरण

आधुनिक लार्ज लैंग्वेज मॉडल (LLM) पाइपलाइनें टोकनाइज़ेशन के लिए भारी रूप से बाइट पेयर एनकोडिंग (BPE) पर निर्भर करती हैं। हालाँकि, वर्तमान अत्याधुनिक कार्यान्वयन (जैसे, Hugging Face के tokenizers और OpenAI के tiktoken) मुख्य रूप से ऑफलाइन प्रक्रियाओं के रूप में डिज़ाइन किए गए हैं। उन्हें पूर्ण टोकनाइज़ेशन उत्पन्न करने के लिए पूरे इनपुट अनुक्रम या पूर्व-खंडित (pre-segmented) चंक को पूरी तरह से देखे जाने की आवश्यकता होती है। यह वास्तुशिल्प सीमा टोकनाइज़ेशन और मॉडल प्री-फिलिंग को समवर्ती (concurrently) के बजाय क्रमिक रूप से (sequentially) निष्पादित करने के लिए मजबूर करती है, जिससे स्ट्रीमिंग और लॉन्ग-कॉन्टेक्स्ट इन्फरेंस परिदृश्यों में विलंबता (latency) उत्पन्न होती है।

इसके अलावा, मौजूदा कार्यान्वयन अक्सर पूरे इनपुट पर मर्ज (merges) का चयन करने के लिए हीप-आधारित प्रायोरिटी क्यू (priority queues) पर निर्भर करते हैं, जिसके परिणामस्वरूप वे स्वाभाविक रूप से ग्लोबल होते हैं और बाइट-दर-बाइट अपडेट के लिए अनुकूलित करना कठिन होता है। जबकि कुछ उपकरण मर्ज लागत को सीमित करने के लिए रेगुलर एक्सप्रेशन (regex)-आधारित प्री-सेगमेंटेशन का उपयोग करते हैं, यह दृष्टिकोण भंगुर (brittle) हो सकता है, जिससे पैथोलॉजिकल इनपुट (जैसे, अत्यधिक वर्ण पुनरावृत्ति) पर प्रदर्शन में गिरावट आती है या स्टैक एग्जॉशन (stack exhaustion) हो सकता है, जहाँ कुछ उपकरण $O(n^2)$ व्यवहार प्रदर्शित करते हैं।

कार्यप्रणाली

लेखक इंक्रीमेंटल बीपीई टोकनाइज़ेशन के लिए एक नया एल्गोरिदम प्रस्तावित करते हैं जो वास्तविक समय में इनपुट टेक्स्ट के प्रत्येक प्रीफ़िक्स (prefix) के लिए बीपीई टोकनाइज़ेशन परिणामों को बनाए रखता है। यह दृष्टिकोण BPE की संरचनात्मक विशेषताओं पर आधारित है और कई प्रमुख एल्गोरिथमिक नवाचार पेश करता है:

1. संरचनात्मक आधार

प्रीफ़िक्स निरंतरता (Prefix Consistency): यह देखते हुए कि एक वैध BPE टोकनाइज़ेशन को स्वतंत्र रूप से ट्रंकेट किया जा सकता है, एल्गोरिदम एक बढ़ते हुए स्ट्रिंग के टोकनाइज़ेशन को एक छोटे प्रीफ़िक्स के पिछले वैध टोकनाइज़ेशन के विस्तार के रूप में मॉडल करता है, न कि पुन: गणना (re-computation) के रूप में।
लास्ट टोकन ( $\theta(s)$ ): एल्गोरिदम वर्तमान स्ट्रिंग $s$ के "लास्ट टोकन" को बनाए रखने पर ध्यान केंद्रित करता है। पूर्ण टोकनाइज़ेशन को अंतिम टोकनों के अनुक्रम द्वारा स्पष्ट रूप से एनकोड किया जाता है, जिसे बैकट्रैकिंग के माध्यम से प्राप्त किया जा सकता है।
सक्सेसर फॉरेस्ट (Successor Forest) और सफिक्स-सक्सेसर ट्री (Suffix-Successor Tree): शब्दावली (vocabulary) को कैनोनिकल टोकन में सामान्यीकृत किया जाता है, जो एक सक्सेसर फॉरेस्ट नामक टोपोलॉजिकल संरचना बनाता है। किसी भी इनपुट के लिए, नए लास्ट टोकन के लिए खोज स्थान एक सफिक्स-सक्सेसर ट्री तक सीमित होता है, जो सभी संभावित सफिक्स टोकन को व्यवस्थित करता है।

2. मोनोटोनिक पाथ प्रॉपर्टी (The Monotonic Path Property)

एक मुख्य सैद्धांतिक योगदान मोनोटोनिक पाथ प्रॉपर्टी है, जो यह स्थापित करता है कि किसी भी इनपुट स्ट्रिंग के लिए, अंतिम टोकन के रूप में कार्य करने में सक्षम सफिक्स टोकन का सेट सफिक्स-सक्सेसर ट्री के भीतर एक एकल, निरंतर पथ बनाता है। यह पथ रूट (एटॉमिक टोकन) पर एंकर होता है और वास्तविक लास्ट टोकन $\theta(s)$ तक विस्तृत होता है। यह प्रॉपर्टी खोज स्थान को पूरे ट्री से घटाकर एक एकल पथ तक सीमित कर देती है, जिससे कुशल सत्यापन संभव होता है।

3. एल्गोरिथमिक कार्यान्वयन

इंक्रीमेंटल अपडेट प्रक्रिया में दो मुख्य चरण शामिल हैं:

सर्च स्पेस की पहचान: पर्सिस्टेंट स्क्वायर-रूट टाइलिंग के साथ संवर्धित अहो-कोरासिक ऑटोमेटन (Aho–Corasick automaton) का उपयोग करके, एल्गोरिदम $O(1)$ समय में सबसे लंबे सफिक्स टोकन $\tau(sc)$ की पहचान करता है, जो बाउंडिंग सफिक्स-सक्सेसर ट्री को परिभाषित करता है।
पाथ एक्सटेंशन सर्च: मोनोटोनिक पाथ पर सबसे गहरे वैध नोड को खोजने के लिए, एल्गोरिदम एक प्रीकंप्यूटेड सेंट्रॉइड सर्च ट्री (CST) का उपयोग करता है जिसकी ऊंचाई $O(\log |\tau|)$ है। प्रत्येक चरण में, यह DFS लीनियराइजेशन इंटरवल्स का उपयोग करके प्रीफ़िक्स लास्ट-टोकन कंडीशन (पहुंच क्षमता और प्रायोरिटी डोमिनेंस की जांच) को सत्यापित करता है। यह एल्गोरिदम को $O(\log |\tau|)$ समय में वैध पथ की दिशा निर्धारित करने की अनुमति देता है।

4. ईगर आउटपुट मैकेनिज्म (Eager Output Mechanism)

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

मुख्य योगदान

एल्गोरिथमिक जटिलता: प्रस्तावित एल्गोरिदम प्रत्येक इनपुट बाइट को $O(\log_2 t)$ की सख्त वर्स्ट-केस टाइम कॉम्प्लेक्सिटी के साथ प्रोसेस करता है, जहाँ $t$ अधिकतम टोकन लंबाई है। इसके परिणामस्वरूप $n$ लंबाई के इनपुट के लिए कुल जटिलता $O(n \log_2 t)$ होती है।
स्ट्रीमिंग क्षमता: यह विधि मानक BPE चरणों के लिए एक ड्रॉप-इन रिप्लेसमेंट के रूप में कार्य करती है, जो आसपास के प्रीप्रोसेसिंग चरणों की शुद्धता को बदले बिना स्ट्रीमिंग सेटिंग्स में कुशल आंशिक टोकनाइज़ेशन सक्षम करती है।
ईगर आउटपुट: ईगर आउटपुट मैकेनिज्म वास्तविक समय की स्ट्रीमिंग और मॉडल इन्फरेंस के साथ पाइपलाइनिंग की अनुमति देता है, जिससे सीमाओं के समाधान होते ही टोकन तुरंत उत्सर्जित होते हैं।
मजबूती (Robustness): मौजूदा उपकरणों के विपरीत जो पैथोलॉजिकल इनपुट पर $O(n^2)$ जटिलता में गिरावट दिखा सकते हैं, यह दृष्टिकोण स्थिर प्रदर्शन गारंटी बनाए रखता है।
फुल-प्रीफ़िक्स सपोर्ट: एल्गोरिदम स्वाभाविक रूप से उन परिदृश्यों का समर्थन करता है जिनमें सभी प्रीफ़िक्स के टोकनाइज़ेशन तक पहुंच की आवश्यकता होती है (जैसे, "फिल-इन-द-मिडल" कार्य या टोकन हीलिंग), बिना किसी ह्यूरिस्टिक ट्रंकेशन या पुन: गणना के।

परिणाम

लेखकों ने अपने एल्गोरिदम को Rust में लागू किया और इसकी तुलना Hugging Face के tokenizers और OpenAI के tiktoken से की।

थ्रूपुट (Throughput): इंक्रीमेंटल दृष्टिकोण Hugging Face के टोकनाइज़र्स की तुलना में $\sim 3\times$ तक एंड-टू-एंड स्पीडअप प्राप्त करता है, विशेष रूप से उन परिदृश्यों में जिनमें रेगुलर एक्सप्रेशन-आधारित प्री-टोकनाइज़ेशन की कमी है (जैसे, CodeLlama)।
पैथोलॉजिकल इनपुट पर विलंबता: अत्यधिक पुनरावृत्ति वाले इनपुट पर, tiktoken $O(n^2)$ जटिलता के अनुरूप थ्रूपुट गिरावट दिखाता है। इसके विपरीत, प्रस्तावित विधि स्थिर थ्रूपुट बनाए रखती है, जो ऐसे पैथोलॉजिकल मामलों में महत्वपूर्ण विलंबता कमी प्रदर्शित करती है।
ईगर आउटपुट ओवरहेड: ईगर आउटपुट मैकेनिज्म गैर-ईगर इंक्रीमेंटल संस्करण की तुलना में एंड-टू-एंड थ्रूपुट में लगभग 10% का ओवरहेड पेश करता है, जिसे लेखक एक ऐसा खर्च मानते हैं जिसे उन सिस्टमों में अमॉर्टाइज (amortize) किया जा सकता है जहाँ टोकनाइज़ेशन को I/O या इन्फरेंस के साथ पाइपलाइन किया जाता है।

महत्व और दावे

यह शोध पत्र प्रदर्शित करता है कि मानक BPE के साथ सटीक सिमेंटिक कम्पैटिबिलिटी बनाए रखते हुए BPE टोकनाइज़ेशन को सख्त वर्स्ट-केस गारंटी के साथ इंक्रीमेंटली किया जा सकता है।

लेखक दावा करते हैं कि उनका कार्य सैद्धांतिक औपचारिकताओं (जो प्रीफ़िक्स स्थिरता का सुझाव देते हैं) और व्यावहारिक इंजीनियरिंग (जो ग्लोबल, ऑफलाइन प्रोसेसिंग पर निर्भर रही है) के बीच के अंतर को पाटता है। $O(n \log_2 t)$ जटिलता के साथ एक एल्गोरिदम प्रदान करके, यह कार्य सक्षम बनाता है:

कम विलंबता (Reduced Latency): टोकनाइज़ेशन को मॉडल इन्फरेंस के साथ पूरी तरह से पाइपलाइन करने की अनुमति देकर, जो स्ट्रीमिंग इन्फरेंस में अनुक्रमिक बाधा को हटा देता है।
सिस्टम मजबूती (System Robustness): वर्तमान टोकनाइज़र्स की $O(n^2)$ कमजोरियों का फायदा उठाने वाले एल्गोरिथमिक जटिलता हमलों (जैसे, तैयार किए गए इनपुट के माध्यम से Denial-of-Service) के जोखिम को कम करके।
पाइपलाइन अनुकूलन: उन प्री-सेगमेंटेशन चरणों को एल्गोरिथमिक रूप से अनावश्यक बनाकर जो केवल ग्लोबल BPE लागत को सीमित करने के लिए डिज़ाइन किए गए हैं, जिससे स्वच्छ और अधिक कुशल पाइपलाइन डिज़ाइन संभव होता है।

लेखक निष्कर्ष निकालते हैं कि उनका दृष्टिकोण सख्त एल्गोरिथमिक गारंटी को व्यावहारिक विलंबता लाभों में अनुवादित करके अधिक मजबूत, उत्तरदायी और ऊर्जा-कुशल LLM पाइपलाइनों के लिए मार्ग प्रशस्त करता है।