🤖 AI

Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice

यह शोधपत्र एक ज्योमेट्री-अवेयर ऑनलाइन शेड्यूलिंग फ्रेमवर्क प्रस्तावित करता है जिसमें स्मलेस्ट वॉल्यूम फर्स्ट (SVF) और 1-बिट SVF एल्गोरिदम शामिल हैं, जो पारंपरिक टाइम-सेंट्रिक ह्यूरिस्टिक्स की तुलना में की-वैल्यू (KV) कैश के डायनेमिक 2D मेमोरी फुटप्रिंट को अधिक प्रभावी ढंग से संबोधित करके सैद्धांतिक रूप से कॉम्पिटिटिव रेश्यो में सुधार करते हैं और व्यावहारिक रूप से LLM सर्विंग प्रदर्शन को बढ़ाते हैं।

मूल लेखक: Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

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

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

CC BY 4.0

मूल लेखक: Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

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

कल्पना कीजिए कि आप एक व्यस्त कॉफी शॉप चला रहे हैं। यह कोई साधारण कॉफी शॉप नहीं है; यह एक हाई-टेक कॉफी शॉप है जहाँ आपके द्वारा बनाई गई हर ड्रिंक को एक विशिष्ट मात्रा में काउंटर स्पेस (मेमोरी) की आवश्यकता होती है, जो उसे बनाने में बिताए गए समय के साथ बढ़ती जाती है।

लार्ज लैंग्वेज मॉडल्स (LLMs) की दुनिया में, इस "काउंटर स्पेस" को KV Cache कहा जाता है। हर बार जब AI एक शब्द (टोकन) बनाता है, तो उसे यह याद रखने के लिए थोड़ी और मेमोरी की आवश्यकता होती है कि उसने अभी क्या कहा था, ताकि वह बातचीत को जारी रख सके। यदि आपके पास काउंटर स्पेस खत्म हो जाता है, तो पूरी दुकान को रुकना पड़ता है।

समस्या: "शॉर्टेस्ट जॉब फर्स्ट" (Shortest Job First) की गलती

लंबे समय तक, कंप्यूटर सिस्टम इन अनुरोधों (requests) को Shortest Job First (SJF) नामक एक नियम का उपयोग करके प्रबंधित करते थे। तर्क सरल है: "यदि कोई ग्राहक एक त्वरित एस्प्रेसो ऑर्डर करता है, तो उसे पहले जाने दें क्योंकि यह तेज़ है। यदि कोई जटिल 20 मिनट वाली लाटे (latte) ऑर्डर करता है, तो उसे प्रतीक्षा करने दें।"

लेख तर्क देता है कि AI की दुनिया में, यह नियम वास्तव में गलत है। यहाँ इसका कारण दिया गया है:

जाल (The Trap): एक सामान्य दुकान में, एक छोटा ऑर्डर कम समय के लिए जगह घेरता है। लेकिन एक AI दुकान में, एक "छोटा" अनुरोध भी बहुत अधिक काउंटर स्पेस ले सकता है यदि ग्राहक एक लंबी कहानी सुनाने की जिद करे।
2D वास्तविकता: पेपर कहता है कि हमें दो आयामों (dimensions) को देखने की आवश्यकता है: समय (इसे पूरा होने में कितना समय लगता है) और स्थान (यह बढ़ते हुए कितनी मेमोरी खाता है)। पुराना नियम केवल समय को देखता था।
परिणाम: केवल "तेज़" कामों को प्राथमिकता देकर, सिस्टम अक्सर ऐसे अनुरोधों से भर जाता है जो शुरू होने में तो तेज़ हैं लेकिन सारी मेमोरी खा जाते हैं, जिससे बाकी सभी लोग रुक जाते हैं। यह ऐसा ही है जैसे किसी ग्राहक को एक छोटा एस्प्रेसो ऑर्डर करने देना, लेकिन वह तय करता है कि वह एक घंटे तक काउंटर पर बैठा रहेगा, जिससे बरिस्ता (barista) किसी और के लिए ड्रिंक बनाने में असमर्थ हो जाता है।

समाधान: "स्मॉलैस्ट वॉल्यूम फर्स्ट" (Smallest Volume First - SVF)

लेखक एक नया नियम प्रस्तावित करते हैं जिसे Smallest Volume First (SVB) कहा जाता है। यह पूछने के बजाय कि "यह कितना तेज़ है?", वे पूछते हैं, "यह अनुरोध अपने पूरे जीवनकाल में कुल कितना काउंटर स्पेस घेरेगा?"

एक सामान भरने वाले ट्रक की कल्पना करें:

पुराना तरीका (SJF): आप सबसे पहले छोटे डिब्बे लोड करते हैं, इस उम्मीद में कि वे फिट हो जाएंगे।
नया तरीका (SVF): आप हर वस्तु का कुल "आयतन" (volume) (ऊंचाई × चौड़ाई × गहराई) की गणना करते हैं और उन वस्तुओं को लोड करते हैं जो कुल मिलाकर सबसे कम जगह लेती हैं।

ऐसा करके, सिस्टम उन अनुरोधों को जल्दी से खाली कर देता है जो कुल मेमोरी फुटप्रिंट में "छोटे" हैं। यह बड़े अनुरोधों के लिए जल्दी शुरू होने हेतु जगह खाली कर देता है, जिससे पूरा सिस्टम अटकने से बच जाता है।

"वन-बिट" (One-Bit) ट्रिक (1-bit SVF)

यह भविष्यवाणी करना कि बातचीत में ठीक कितना समय लगेगा, कठिन है। यह अनुमान लगाने जैसा है कि कोई ग्राहक बोलने से पहले ठीक कितने शब्द बोलेगा। पेपर एक चतुर शॉर्टकट पेश करता है जिसे 1-bit SVF कहा जाता है।

सटीक शब्दों की संख्या बताने के बजाय, सिस्टम बस एक सरल प्रश्न पूछता है: "क्या यह एक छोटा अनुरोध है या एक लंबा अनुरोध?" (हाँ/नहीं)।

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

इस पेपर ने क्या सिद्ध किया

लेखकों ने केवल यह अनुमान नहीं लगाया कि यह काम करेगा; उन्होंने इसे सिद्ध करने के लिए गणित का उपयोग किया:

गणित: उन्होंने दिखाया कि सबसे खराब स्थितियों में (जैसे ग्राहकों की अचानक भीड़), उनकी नई विधि पुराने "Shortest Job First" तरीके की तुलना में गारंटी से बहुत बेहतर है। उन्होंने गणितीय गारंटी को पूर्णतः आदर्श होने से 48 गुना बदतर होने के बजाय केवल 5 गुना बदतर तक सीमित कर दिया।
परीक्षण: उन्होंने वास्तविक AI मॉडल (Llama-3.1) पर vLLM नामक एक लोकप्रिय सिस्टम का उपयोग करके इसका परीक्षण किया।
- परिणाम: नए तरीके ने AI को सभी के लिए तेज़ बना दिया, विशेष रूप से सबसे धीमी अनुरोधों के लिए (टेल लेटेंसी को कम करके)।
- दक्षता (Efficiency): "1-bit" वाला संस्करण अविश्वसनीय रूप से हल्का था, जिसने सिस्टम में लगभग शून्य देरी जोड़ी जबकि यह बहुत अच्छा प्रदर्शन कर रहा था।

सारांश

सरल शब्दों में, यह पेपर कहता है: AI अनुरोधों को केवल इस आधार पर न आंकें कि वे कितनी जल्दी समाप्त होते हैं। उन्हें इस आधार पर आंकें कि वे चलते समय कितना "मेमोरी स्पेस" घेरते हैं। "Smallest Volume First" रणनीति को अपनाकर, और यहाँ तक कि एक सुपर-सिंपल "छोटा बनाम लंबा" अनुमान का उपयोग करके, हम AI चैटबॉट्स को तेज़, सुचारू और भारी लोड के तहत क्रैश होने से बचाने में सक्षम बना सकते हैं।

तकनीकी सारांश: LLM सर्विंग के लिए ज्योमेट्री-अवेयर ऑनलाइन शेड्यूलिंग

समस्या विवरण

इंटरैक्टिव परिदृश्यों में लार्ज लैंग्वेज मॉडल्स (LLMs) की तैनाती एक महत्वपूर्ण बाधा का सामना करती है: की-वैल्यू (KV) कैश के डायनेमिक मेमोरी फुटप्रिंट का प्रबंधन। पारंपरिक शेड्यूलिंग समस्याओं के विपरीत, जहाँ जॉब का आकार स्थिर होता है, LLM इन्फरेंस में एक अद्वितीय 2D स्थानिक-कालिक ज्यामितीय विकास (2D spatio-temporal geometric growth) दिखाई देता है।

मेमोरी-टाइम कपलिंग: ऑटो-रिग्रेसिव डिकोडिंग में, निष्पादन समय (execution time) मेमोरी विस्तार के साथ रैखिक रूप से जुड़ा होता है; प्रत्येक उत्पन्न टोकन KV कैश के फुटप्रिंट को बढ़ाता है।
कंटीन्यूअस बैचिंग डायनेमिक्स: आधुनिक इंजन (जैसे vLLM) कंटीन्यूअस बैचिंग का उपयोग करते हैं, जहाँ अनुरोधों के पूरा होने और नए अनुरोधों के प्रवेश के साथ ही प्रत्येक डिकोडिंग स्टेप के बाद समवर्ती बैच का आकार गतिशील रूप से बदलता रहता है।

मौजूदा शेड्यूलिंग ह्यूरिस्टिक्स, जो मुख्य रूप से शॉर्टेस्ट जॉब फर्स्ट (SJF) पर आधारित हैं, शास्त्रीय समय-केंद्रित मॉडलिंग में निहित हैं। वे ज्यामितीय वास्तविकता को पकड़ने में विफल रहते हैं। हालिया सैद्धांतिक कार्य [10] ने प्रदर्शित किया है कि इन विशिष्ट ज्यामितीय बाधाओं के तहत, SJF एक अनबाउंडेड वर्स्ट-केस कॉम्पिटिटिव रेश्यो (unbounded worst-case competitive ratio) प्रदान करता है, जो शास्त्रीय शेड्यूलिंग सिद्धांत और आधुनिक LLM इन्फरेंस की भौतिक वास्तविकताओं के बीच एक मौलिक अंतर पैदा करता है।

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

लेखक एक ज्योमेट्री-अवेयर ऑनलाइन शेड्यूलिंग (Geometry-Aware Online Scheduling) फ्रेमवर्क का प्रस्ताव करते हैं जो प्राथमिकता मीट्रिक को 1D निष्पादन समय से बदलकर 2D मेमोरी वॉल्यूम में स्थानांतरित कर देता है।

कोर एल्गोरिदम: स्मॉलेस्ट वॉल्यूम फर्स्ट (SVF)

निष्पादन समय को अलग करने के बजाय, SVF किसी अनुरोध के पूरे जीवनचक्र के दौरान मेमोरी खपत के इंटीग्रल (integral) का मूल्यांकन करता है। प्रॉम्प्ट लंबाई $s_i$ और आउटपुट लंबाई $o_i$ वाले एक अनुरोध $r_i$ के लिए, वॉल्यूम $v_i$ को इस प्रकार परिभाषित किया गया है:
$v_i = s_i \cdot o_i + \frac{o_i^2 + o_i}{2}$
यह फॉर्मूला अनुरोध द्वारा घेरे गए कुल "मेमोरी-टाइम" क्षेत्र को मात्रात्मक रूप से दर्शाता है। SVF एक स्ट्रिक्टली ग्रीडी पॉलिसी के रूप में कार्य करता है, जो अनुरोधों को $v_i$ के बढ़ते क्रम में सॉर्ट करता है। इसका कार्यान्वयन दो प्रक्रियाओं में विभाजित है: एक बैकग्राउंड प्रेडिक्टर जो आउटपुट लंबाई जानने के लिए अनुरोधों को बैच करता है, और एक शेड्यूलर जो KV कैश क्षमता तक पहुँचने तक उच्चतम-प्राथमिकता (सबसे छोटा वॉल्यूम) वाले अनुरोधों को रनिंग बैच में शामिल करता है।

लाइटवेट वेरिएंट: 1-बिट SVF

कंप्यूटेशनल ओवरहेड को कम करने के लिए, लेखक 1-बिट SVF पेश करते हैं। यह वेरिएंट सटीक लंबाई भविष्यवाणी के स्थान पर एक बाइनरी क्लासिफायर का उपयोग करता है जो अनुरोधों को "शॉर्ट" ( $m=0$ ) या "लॉन्ग" ( $m=1$ ) के रूप में वर्गीकृत करता है।

यह प्रत्येक क्लास के लिए एक ग्लोबल प्रॉक्सी लेंथ $O_m$ असाइन करता है।
प्रॉक्सी वॉल्यूम की गणना $\hat{v}_i = s_i \cdot O_m + \frac{O_m^2 + O_m}{2}$ के रूप में की जाती है।
यह डिज़ाइन केवल एक बिट सूचना निकालकर भी स्पैटियो-टेम्पोरल शेड्यूलिंग गारंटी को सुरक्षित रखता है।

सैद्धांतिक योगदान

यह शोध पत्र अनुभवजन्य परीक्षण-और-त्रुटि (trial-and-error) से आगे बढ़कर औपचारिक गारंटी के साथ एक कठोर गणितीय आधार प्रदान करता है:

टाइटन्ड वर्स्ट-केस बाउंड्स (बर्स्ट अराइवल्स):
- ज्ञात आउटपुट लंबाई के साथ बर्स्ट अराइवल मॉडल के तहत SVF के लिए, लेखक सिद्ध करते हैं कि वर्स्ट-केस कॉम्पिटिटिव रेशो (CR) CR $\le$ 5 है। यह पिछले साहित्य [10] में पाए गए CR $\le$ 48 के मुकाबले काफी बेहतर है।
- यह प्रमाण एक नवीन "मैक्रोस्कोपिक सर्टिफिकेट" पद्धति का उपयोग करता है, जो दिखाता है कि प्रत्येक ब्लॉक्ड स्टेप एक सक्रिय मेमोरी मास $> M/2$ को इंगित करता है, जो सीधे एल्गोरिदम के वेटिंग टाइम को ऑप्टिमल ऑफलाइन शेड्यूल के लोअर बाउंड के साथ जोड़ता है।
- 1-बिट SVF के लिए, कॉम्पिटिटिव रेश्यो $O(T)$ द्वारा सीमित है, जहाँ $T$ अधिकतम मॉडल लेंथ है, जो यह सिद्ध करता है कि न्यूनतम जानकारी के साथ भी सिस्टम अत्यधिक लोड के तहत स्थिर रहता है।
स्टोकेस्टिक बाउंड्स (पॉइसन अराइवल्स):
- पॉइसन अराइवल प्रोसेस के तहत, पेपर अपेक्षित कॉम्पिटिटिव रेश्यो को व्युत्पन्न करता है।
- SVF $E[CR] \le 1 + \frac{4}{(1-\mu)(1-\rho)}$ प्राप्त करता है, जहाँ $\mu$ लेंथ के ज्यामितीय वितरण से संबंधित है और $\rho$ सिस्टम यूटिलाइजेशन है।
- दिखाया गया है कि 1-बिट SVF का प्रदर्शन ह्रास एक "वोल्यूमेट्रिक डिस्टॉर्शन पेनल्टी" $\epsilon$ द्वारा नियंत्रित होता है, जो वर्गीकरण थ्रेशोल्ड के साथ तेजी से घटता है, जिससे दीर्घकालिक स्थिरता सुनिश्चित होती है।

प्रायोगिक परिणाम

इस दृष्टिकोण को vLLM के भीतर एक प्लग-एंड-प्ले लेयर के रूप में लागू किया गया था और Llama-3.1-8B और Llama-3.1-70B मॉडल्स पर LMSYS-Chat और LongBench वर्कलोड का उपयोग करके मूल्यांकन किया गया।

लेटेंसी रिडक्शन: SVF ने सभी बेंचमार्क में लगातार सबसे कम औसत और टेल (P95) लेटेंसी प्राप्त की, जो FCFS, SJF और यहाँ तक कि Oracle-SJF (जिसके पास लंबाई का पूर्ण भविष्य ज्ञान है) को भी मेमोरी-इंटेंसिव परिदृश्यों (LongBench) में पछाड़ दिया।
थ्रूपुट: SVF ने SJF की तुलना में उच्च थ्रूपुट बनाए रखा। 1-बिट SVF ने प्रतिस्पर्धी थ्रूपुट और लेटेंसी प्राप्त की, और अक्सर टेल लेटेंसी मेट्रिक्स में SJF से बेहतर प्रदर्शन किया।
ओवरहेड: प्रेडिक्शन ओवरहेड नगण्य था। फुल-लेंथ प्रेडिक्टर ने एंड-टू-एंड लेटेंसी का अधिकतम 0.06% ही उपयोग किया, जबकि 1-बिट क्लासिफायर ने $\le$ 0.01% का उपयोग किया।
फेयरनेस (Fairness): शास्त्रीय ग्रीडी ह्यूरिस्टिक्स के विपरीत जो लंबे जॉब्स को भूखा (starve) रखते हैं, SVF की ज्योमेट्री-अवेयर ग्रीडीनेस तेजी से बाउंडेड KV कैश मेमोरी को रिलीज करती है, जिससे ग्लोबल हेड-ऑफ-लाइन ब्लॉकिंग टूटती है और बड़े अनुरोधों के लिए फेयरनेस में सुधार होता है।

महत्व और दावे

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

पैराडाइम शिफ्ट: यह क्षेत्र को लीगेसी 1D टाइम-सेंट्रिक ह्यूरिस्टिक्स से 2D ज्योमेट्री-अवेयर प्रायोरिटाइजेशन की ओर ले जाता है, जो शास्त्रीय शेड्यूलिंग सिद्धांत और LLM इन्फरेंस मैकेनिक्स के बीच मौलिक बेमेल को संबोधित करता है।
सैद्धांतिक उन्नति: कॉम्पिटिटिव रेश्यो को 48 से घटाकर 5 करने और एक नवीन प्रमाण पद्धति पेश करके, यह सार्वभौमिक संरचनात्मक गारंटी प्रदान करता है जो किसी भी आर्बिट्ररी और एडवर्सरियल वर्कलोड डिस्ट्रीब्यूशन पर लागू होती है।
व्यावहारिक व्यवहार्यता: शेड्यूलर की "प्लग-एंड-प्ले" प्रकृति, 1-बिट वेरिएंट की अत्यधिक दक्षता के साथ मिलकर, यह प्रदर्शित करती है कि कठोर गणितीय अनुकूलन को बिना किसी भारी ओवरहेड के उच्च-प्रदर्शन वाले इन्फरेंस इंजनों में निर्बाध रूप से एकीकृत किया जा सकता है।

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