🤖 machine learning

LLM Serving Optimization with Variable Prefill and Decode Lengths

यह शोध पत्र विषम अनुरोध लंबाई (heterogeneous request lengths) के साथ निश्चित KV-कैश बाधाओं (fixed KV-cache constraints) के तहत ऑफलाइन LLM सर्विंग शेड्यूलिंग की NP-हार्ड समस्या को संबोधित करने के लिए सॉर्टेड-F (Sorted-F) एल्गोरिदम का प्रस्ताव देता है, जो एक स्थिर-कारक सन्निकटन गारंटी (constant-factor approximation guarantee) प्राप्त करता है और मानक बेसलाइन की तुलना में एंड-टू-एंड विलंबता (end-to-end latency) को काफी कम करता है।

मूल लेखक: Meixuan Wang, Yinyu Ye, Zijie Zhou

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

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

CC BY 4.0

मूल लेखक: Meixuan Wang, Yinyu Ye, Zijie Zhou

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

कल्पना कीजिए कि आप एक बहुत ही व्यस्त, हाई-टेक किचन (AI सर्वर) के मैनेजर हैं। आपका काम ग्राहकों (यूजर्स) के लिए जितनी जल्दी हो सके उतनी जल्दी भोजन बनाना (जवाब जेनरेट करना) है।

इस किचन में, हर भोजन के दो भाग हैं:

तैयारी का काम (Prefill): रेसिपी को पढ़ना और सामग्री को काटना। यह तुरंत काउंटर की जगह घेर लेता है।
पकाना (Decode): वास्तव में व्यंजन को पकाना। यह स्टेप-बाय-स्टेप होता है, और जैसे-जैसे आप पकाते हैं, आप बर्तन को चूल्हे पर रखते रहते हैं, जो जगह घेरता रहता है।

बड़ी समस्या यह है कि आपके किचन में काउंटर की जगह निश्चित है (KV-कैश मेमोरी)। आप हर ऑर्डर को एक साथ काउंटर पर नहीं रख सकते; आपको तय करना होगा कि किसे जगह दी जाए और कब।

पुराना तरीका बनाम नई समस्या

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

लेकिन वास्तविक दुनिया में, ऑर्डर्स बिखरे हुए होते हैं।

ऑर्डर A: एक छोटी रेसिपी (कम तैयारी) लेकिन इसे पकने में बहुत समय लगता है (लंबा कुकिंग टाइम)। यह कम जगह लेता है लेकिन लंबे समय तक चूल्हे पर बना रहता है।
ऑर्डर B: एक विशाल रेसिपी (बहुत बड़ी तैयारी) लेकिन यह सेकंडों में पक जाती है (छोटा कुकिंग टाइम)। यह तुरंत काउंटर पर कब्जा कर लेती है लेकिन जल्दी खाली हो जाती है।

पेपर दिखाता है कि यदि आप इस अस्त-व्यस्त वातावरण में पुराने "शॉर्टेस्ट जॉब फर्स्ट" नियम पर टिके रहते हैं, तो आप एक बहुत बड़ी गलती कर सकते हैं। आप ऑर्डर A को चुन सकते हैं क्योंकि यह "छोटा" है, लेकिन यह काउंटर को लंबे समय तक ब्लॉक कर देता है, जिससे आप जल्दी खत्म होने वाले, अधिक जगह घेरने वाले ऑर्डर B को संभालने से रोक देता है। लेखक सिद्ध करते हैं कि यह पुराना तरीका बहुत खराब प्रदर्शन कर सकता है—गणितीय रूप से, इसका प्रदर्शन सबसे अच्छे संभावित शेड्यूल की तुलना में अनंत गुना बदतर हो सकता है।

समाधान: "F-मेट्रिक"

लेखक एक नया शेड्यूलिंग एल्गोरिदम प्रस्तावित करते हैं जिसे Sorted-F कहा जाता है। केवल यह देखने के बजाय कि खाना पकाने में कितना समय लगता है, यह एक नए स्कोर का उपयोग करता है जिसे F-मेट्रिक कहा जाता है।

F-मेट्रिक को एक "थ्रूपुट डेंसिटी" (Throughput Density) स्कोर के रूप में समझें। यह पूछता है: "उपलब्ध काउंटर स्पेस का उपयोग करते हुए हम प्रति इकाई समय में कितने भोजन तैयार कर सकते हैं?"

यह बैच साइज (हम एक साथ कितने ऑर्डर काउंटर पर फिट कर सकते हैं) और कुकिंग टाइम (वे वहां कितनी देर तक रहते हैं) के बीच संतुलन बनाता है।
यह उन बैचों को प्राथमिकता देता है जो "कुशल" (efficient) हैं—यानी, वे उपलब्ध स्थान में बहुत सारा काम पैक करते हैं बिना किचन को बहुत लंबे समय तक जाम किए।

यह क्यों काम करता है

लेखक सिद्ध करते हैं कि यह नया तरीका गणितीय रूप से मजबूत है। सबसे खराब स्थितियों में भी, Sorted-F कभी भी पूर्णतः आदर्श शेड्यूल (जिसे गणना करना वास्तविक समय में बहुत जटिल है) से 48 गुना से अधिक खराब नहीं होगा। व्यवहार में, यह उससे कहीं बेहतर प्रदर्शन करता है, अक्सर सैद्धांतिक सर्वश्रेष्ठ के बहुत करीब होता है।

वास्तविक परीक्षण

उन्होंने वास्तविक डेटा पर इसका परीक्षण किया, जिसमें छोटे चैट संदेशों और लंबे दस्तावेज़ सारांशों का मिश्रण था।

परिणाम: Sorted-F पुराने तरीकों की तुलना में काफी तेज़ था।
अंतर्दृष्टि: सबसे बड़े लाभ तब हुए जब वर्कलोड मिश्रित था (कुछ छोटे, कुछ लंबे) और किचन लगभग भरा हुआ था। यदि सभी के ऑर्डर समान थे, तो पुराने तरीके ठीक थे। लेकिन जब ऑर्डर्स में बहुत अधिक भिन्नता थी, तो Sorted-F चमक उठा।

व्यावहारिक बदलाव

चूंकि हजारों ऑर्डर्स के लिए सटीक "F-मेट्रिक" बैच की गणना करना कठिन है, इसलिए उन्होंने विभिन्न स्थितियों के लिए सरल, तेज़ संस्करण भी प्रदान किए:

सटीक विधि (Exact Method): छोटे बैचों के लिए, सटीक स्कोर की गणना करें।
लोकल स्वैप (Local Swap): मध्यम बैचों के लिए, एक अच्छा अनुमान लगाएं और फिर सुधार के लिए ऑर्डर्स को इधर-उधर बदलें।
क्वांटाइल ग्रीडी (Quantile Greedy): बहुत बड़े बैचों के लिए, सबसे अच्छे उम्मीदवारों को चुनने के लिए एक त्वरित सांख्यिकीय शॉर्टकट का उपयोग करें।

उन्होंने इस तथ्य को भी संबोधित किया कि हमें हमेशा यह पता नहीं होता कि उत्तर कितना लंबा होगा। उन्होंने एक "सेफ्टी वाल्व" सिस्टम को एकीकृत किया जो एक आशावादी अनुमान के साथ शुरू होता है लेकिन वास्तविक समय में समायोजित होता है यदि कोई उत्तर उम्मीद से लंबा निकलता है, जिससे जगह बनाने के लिए कम कुशल ऑर्डर्स को बाहर निकाला जा सके।

मुख्य निष्कर्ष

यह पेपर कहता है: केवल यह न देखें कि AI का उत्तर लिखने में कितना समय लगता है। यह भी देखें कि लिखते समय वह कितनी मेमोरी का उपयोग करता है। "प्रेप स्पेस" और "कुकिंग टाइम" को F-मेट्रिक के साथ संतुलित करके, AI सर्वर मिश्रित वर्कलोड को बहुत अधिक कुशलता से संभाल सकते हैं, जिससे सभी के लिए प्रतीक्षा समय कम हो जाता है।

तकनीकी सारांश: परिवर्तनशील प्रिफिल और डिकोड लंबाई के साथ LLM सर्विंग अनुकूलन

1. समस्या विवरण और प्रेरणा
यह शोध पत्र एक निश्चित की-वैल्यू (KV) कैश मेमोरी बजट वाले एकल कंप्यूटेशनल वर्कर पर लार्ज लैंग्वेज मॉडल (LLM) के ऑफलाइन शेड्यूलिंग को संबोधित करता है। मुख्य चुनौती विषम अनुरोध लंबाई (heterogeneous request lengths) से उत्पन्न होती है, जहाँ अनुरोधों में विभिन्न प्रॉम्प्ट (प्रिफिल) आकार ( $s_i$ ) और प्रतिक्रिया (डिकोड) लंबाई ( $o_i$ ) होती है।

आधुनिक LLM सर्विंग में, इन्फरेंस दो चरणों में होता है: प्रिफिल (इनपुट प्रॉम्प्ट को प्रोसेस करना) और डिकोड (आउटपुट टोकन को ऑटोरेग्रेसिव रूप से जेनरेट करना)। डिकोड चरण के दौरान KV कैश मेमोरी की खपत रैखिक रूप से बढ़ती है क्योंकि प्रत्येक जेनरेट किया गया टोकन अतिरिक्त मेमोरी की आवश्यकता रखता है। जबकि पूर्ववर्ती कार्यों (जैसे जेलैट एट अल. 2025) ने समान इनपुट आकारों के लिए शेड्यूलिंग नीतियों को स्थापित किया था, यह शोध पत्र तर्क देता है कि समान इनपुट आकार की धारणा को हटाना समस्या के परिदृश्य को मौलिक रूप से बदल देता है। मिश्रित वर्कलोड (जैसे लघु संवादात्मक प्रॉम्प्ट और लंबी दस्तावेज़ सारांश का संयोजन) में, तत्काल मेमोरी उपलब्धता और भविष्य की डिकोड अवधि के बीच का ट्रेड-ऑफ जटिल हो जाता है। इसका उद्देश्य कुल एंड-टू-एंड लेटेंसी (TEL) को कम करना है, जिसे बैकलॉग कतार में सभी अनुरोधों के पूर्ण होने के समय के योग के रूप में परिभाषित किया गया है।

2. सैद्धांतिक चुनौतियाँ और नकारात्मक परिणाम
लेखक पहले सामान्यीकृत शेड्यूलिंग समस्या की जटिलता को स्थापित करते हैं:

NP-Hardness: वे प्रतिबंधित 3-पार्टिशन समस्या से रिडक्शन के माध्यम से यह सिद्ध करते हैं कि विषम इनपुट और आउटपुट लंबाई के साथ TEL को कम करना NP-hard है।
मानक नीतियों की विफलता: वे यह प्रदर्शित करते हैं कि मानक ह्यूरिस्टिक्स, जिनमें फर्स्ट-कम-फर्स्ट-सर्व (FCFS), शॉर्टेस्ट-आउटपुट-फर्स्ट (MC-SF), और कुल-आकार-आधारित प्राथमिकताएं शामिल हैं, जब इनपुट आकार भिन्न होते हैं तो अनबाउंडेड एप्रोक्सिमेशन रेश्यो से ग्रस्त होते हैं। विशेष रूप से, MC-SF अनिश्चित रूप से खराब प्रदर्शन कर सकता है क्योंकि यह डिकोड अवधि के सापेक्ष डिकोड द्वारा डाले गए मेमोरी दबाव को समझने में विफल रहता है।

3. कार्यप्रणाली: द सॉर्टेड-एफ (Sorted-F) एल्गोरिदम
इन चुनौतियों को संबोधित करने के लिए, शोध पत्र Sorted-F प्रस्तावित करता है, जो एक निरंतर-कारक (constant-factor) एप्रोक्सिमेशन गारंटी प्राप्त करने वाला शेड्यूलिंग एल्गोरिदम है। यह एल्गोरिदम दो चरणों में कार्य करता है:

चरण 1 (बैच निर्माण): एल्गोरिदम एक गुणवत्ता मीट्रिक $F(X)$ को न्यूनतम करने वाले व्यवहार्य बैचों को पुनरावृत्ति से चुनकर अनुरोधों की एक क्रमबद्ध सूची बनाता है। एक बैच $X$ के लिए, मीट्रिक को इस प्रकार परिभाषित किया गया है:
$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$
यह मीट्रिक बैच कार्डिनैलिटी ( $|X|$ ) और कुल डिकोड लागत ( $\sum o_i$ ) के बीच संतुलन बनाता है। $F(X)$ को कम करना "थ्रूपुट डेंसिटी" (औसत डिकोड समय प्रति अनुरोध) को अधिकतम करने के बराबर है। बराबरी (ties) को बड़े बैचों को प्राथमिकता देकर तोड़ा जाता है।
चरण 2 (निष्पादन): एल्गोरिदम डिस्क्रीट टाइम स्टेप्स पर शेड्यूल को निष्पादित करता है। यह लंबित (pending), सक्रिय (active), और नए स्वीकृत अनुरोधों के सेट को बनाए रखता है। प्रत्येक चरण में, यह क्रमबद्ध सूची से अनुरोधों को स्वीकार करता है, जो सक्रिय अनुरोधों के बढ़ते KV कैश उपयोग को ध्यान में रखते हुए डायनेमिक मेमोरी व्यवहार्यता जांच के अधीन होता है।

4. सैद्धांतिक गारंटी
लेखक सिद्ध करते हैं कि Sorted-F इष्टतम ऑफलाइन शेड्यूल के विरुद्ध अधिकतम 48 का निरंतर एप्रोक्सिमेशन रेश्यो प्राप्त करता है। प्रमाण में रूपांतरणों की एक श्रृंखला शामिल है:

सेपरेशन (Separation): गैर-ओवरलैपिंग बैचों को लागू करने के लिए शेड्यूल को रूपांतरित करना।
ग्रुपिंग (Grouping): बैचों को समूहों में एकत्रित करना जो मेमोरी को लगभग संतृप्त (saturate) करते हैं।
अलाइनमेंट (Alignment): टर्मिनल बैचों के भीतर रिस्पॉन्स लंबाई को संरेखित करना।
तुलना (Comparison): एक समान रूप से रूपांतरित इष्टतम शेड्यूल के विरुद्ध रूपांतरित Sorted-F शेड्यूल की तुलना करना।

5. व्यावहारिक कार्यान्वयन और सन्निकटन (Approximations)
चूंकि चरण 1 में सटीक बैच चयन कॉम्बिनेटोरियल रूप से कठिन है, इसलिए शोध पत्र विभिन्न स्केल रिजीम के लिए तीन व्यावहारिक सॉल्वर विकसित करता है:

एक्जैक्ट डायनेमिक प्रोग्रामिंग: एक $O(n^2M)$ एल्गोरिदम जो छोटे उदाहरणों ( $n \le 100$ ) के लिए उपयुक्त है।
लोकल स्वैप सर्च: एक ह्यूरिस्टिक जिसकी जटिलता $O(n^2)$ है जो मध्यम स्तर ( $n \le 500$ ) के लिए युग्मवार आदान-प्रदान (pairwise exchanges) के माध्यम से एक प्रारंभिक ग्रिडी समाधान को परिष्कृत करता है।
क्वांटाइल ग्रिडी सिलेक्शन: एक लीनियर-टाइम $O(n)$ ह्यूरिस्टिक जो आउटलेर्स को फ़िल्टर करने और क्षमता भरने के लिए सांख्यिकीय नमूनाकरण (statistical sampling) का उपयोग करता है, जो बड़े पैमाने पर तैनाती ( $n \ge 1000$ ) के लिए उपयुक्त है।

इसके अतिरिक्त, शोध पत्र Sorted-LP और LP-Swap पेश करता है, जो इंटीजर प्रोग्रामिंग फॉर्मूलेशन के लीनियर प्रोग्रामिंग (LP) रिलैक्सेशन से प्राप्त ह्यूरिस्टिक्स हैं। Sorted-LP, LP समाधान के अपेक्षित स्टार्ट टाइम्स का उपयोग करके अनुरोधों को क्रमबद्ध करता है, जबकि LP-Swap इस क्रमबद्धता को F-मीट्रिक-निर्देशित स्थानीय स्वैप के साथ जोड़ता है।

6. भविष्यवाणी अनिश्चितता को संभालना
यह पहचानते हुए कि आउटपुट लंबाई अक्सर ज्ञात होने के बजाय अनुमानित होती है, शोध पत्र एक एडेप्टिव रिफाइनमेंट रणनीति (चेन एट अल. 2025 से) को Sorted-F में एकीकृत करता है, जिसे Sorted-F+Amin कहा जाता है। यह दृष्टिकोण आशावादी लोअर-बाउंड भविष्यवाणियों के साथ शुरू होता है और वास्तविक जेनरेशन प्रगति के आधार पर अनुमानों को गतिशील रूप से अपडेट करता है। यदि मेमोरी ओवरफ्लो अनुमानित होता है, तो यह क्रमबद्ध निष्कासन (ordered eviction) का उपयोग करता है, जो गणना की बर्बादी को कम करने के लिए सबसे छोटे वर्तमान अनुमानों वाले अनुरोधों को पहले हटाता है।

7. प्रयोगात्मक परिणाम
लेखक LMSYS-Chat डेटासेट (लघु संवाद) और Arxiv लॉन्ग-डॉक्यूमेंट समराइजेशन डेटासेट को मिलाने वाले मिश्रित वर्कलोड पर अपने तरीकों का मूल्यांकन करते हैं।

प्रदर्शन: Sorted-F (लोकल स्वैप सर्च का उपयोग करके) बेसलाइन्स (FCFS, MC-SF, Sorted-LP) से लगातार बेहतर प्रदर्शन करता है। $n=2000$ के साथ 80/20 लघु/लंबा मिश्रण में, Sorted-F ने FCFS की तुलना में 4.87 $\times$ और MC-SF की तुलना में 2.09 $\times$ औसत लेटेंसी को कम किया।
ऑप्टिमलिटी गैप: छोटे सुलभ उदाहरणों पर, Sorted-F का प्रदर्शन LP रिलैक्सेशन लोअर बाउंड के 1.03–1.09 के भीतर रहा, जो इसके 48 के खराबतम मामले वाले सैद्धांतिक बाउंड से काफी बेहतर है।
संवेदनशीलता: विषम शेड्यूलिंग के लाभ मिश्रित वर्कलोड में सबसे अधिक स्पष्ट होते हैं जहाँ अनुरोध लंबाई में उच्च विचलन (dispersion) होता है। सजातीय (homogeneous) वर्कलोड में, सरल नीतियां तुलनीय प्रदर्शन करती हैं।
ऑनलाइन रिजीम: पॉइसन आगमन (Poisson arrivals) के साथ एक प्रारंभिक प्रयोग ने दिखाया कि एक रिसीडिंग-होराइजन वेरिएंट (Sorted-F-Online) ओवरलोडेड रिजीम (नॉर्मलाइज्ड लोड $\rho > 1$ ) में MC-SF और FCFS की तुलना में काफी बेहतर रहा, जिससे उच्च भार पर MC-SF की तुलना में औसत लेटेंसी में 40% तक की कमी आई।

8. महत्व और योगदान
शोध पत्र निम्नलिखित प्रमुख योगदानों का दावा करता है:

सैद्धांतिक लक्षण वर्णन: यह औपचारिक रूप से स्थापित करता है कि विषम प्रिफिल लंबाई LLM शेड्यूलिंग को NP-hard बनाती है और मानक प्राथमिकता नियमों को अप्रभावी बनाती है, जो नए दृष्टिकोणों की आवश्यकता को न्यायसंगत ठहराती है।
एल्गोरिदम डिज़ाइन: यह Sorted-F पेश करता है, जो इस सामान्यीकृत समस्या के लिए एक सिद्ध निरंतर-कारक एप्रोक्सिमेशन गारंटी वाला पहला एल्गोरिदम है।
व्यावहारिक स्केलेबिलिटी: यह विभिन्न तैनाती पैमानों के लिए अनुकूलित स्केलेबल ह्यूरिस्टिक्स (DP, लोकल स्वैप, क्वांटाइल ग्रिडी) के साथ-साथ LP-निर्देशित वेरिएंट प्रदान करता है।
अनुभवजन्य सत्यापन: यह प्रदर्शित करता है कि F-मीट्रिक-आधारित शेड्यूलिंग वास्तविक, मिश्रित वर्कलोड में लेटेंसी को काफी कम करती है और भविष्यवाणी अनिश्चितता एवं ऑनलाइन आगमन पैटर्न के तहत भी मजबूत रहती है।

शोध पत्र निष्कर्ष निकालता है कि विषम वर्कलोड संभालने वाले LLM सर्विंग सिस्टम के लिए मेमोरी-अवेयर शेड्यूलिंग महत्वपूर्ण है, विशेष रूप से जब वे KV-कैश क्षमता सीमाओं के करीब काम कर रहे हों।