2025-11-13T04:07:09.837900

Optimal Quantization for Matrix Multiplication

Ordentlich, Polyanskiy
Recent work in machine learning community proposed multiple methods for performing lossy compression (quantization) of large matrices. This quantization is important for accelerating matrix multiplication (main component of large language models), which is often bottlenecked by the speed of loading these matrices from memory. Unlike classical vector quantization and rate-distortion theory, the goal of these new compression algorithms is to be able to approximate not the matrices themselves, but their matrix product. Specifically, given a pair of real matrices $A,B$ an encoder (compressor) is applied to each of them independently producing descriptions with $R$ bits per entry. These representations subsequently are used by the decoder to estimate matrix product $A^\top B$. In this work, we provide a non-asymptotic lower bound on the mean squared error of this approximation (as a function of rate $R$) for the case of matrices $A,B$ with iid Gaussian entries. Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error for any (non-random) pair of matrices $A$, $B$ in terms of only Frobenius norms $\|\bar{A}\|_F, \|\bar{B}\|_F$ and $\|\bar{A}^\top \bar{B}\|_F$, where $\bar{A},\bar{B}$ are versions of $A,B$ with zero-centered columns, respectively. For iid Gaussian matrices our quantizer achieves the lower bound and is, thus, asymptotically optimal. A practical low-complexity version of our quantizer achieves performance quite close to optimal. In addition, we derive rate-distortion function for matrix multiplication of iid Gaussian matrices, which exhibits an interesting phase-transition at $R\approx 0.906$ bit/entry, showing necessity of Johnson-Lindestrauss dimensionality reduction (sketching) in the low-rate regime.
academic

मैट्रिक्स गुणन के लिए इष्टतम परिमाणन

मूल जानकारी

  • पेपर ID: 2410.13780
  • शीर्षक: Optimal Quantization for Matrix Multiplication
  • लेखक: Or Ordentlich (Hebrew University of Jerusalem), Yury Polyanskiy (MIT)
  • वर्गीकरण: cs.IT cs.AI cs.CL cs.LG math.IT
  • प्रकाशन समय: अक्टूबर 2024 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2410.13780

सारांश

यह पेपर बड़े पैमाने पर मैट्रिक्स गुणन की परिमाणन समस्या का गहन अध्ययन करता है। पारंपरिक सदिश परिमाणन के विपरीत, इस अनुसंधान का लक्ष्य मैट्रिक्स को स्वयं अनुमानित करना नहीं है, बल्कि उनके मैट्रिक्स गुणनफल को अनुमानित करना है। दो वास्तविक मैट्रिक्स A, B दिए गए हैं, एनकोडर प्रत्येक मैट्रिक्स को स्वतंत्र रूप से संपीड़ित करता है, प्रत्येक प्रविष्टि R बिट्स का उपयोग करके वर्णित है, फिर डिकोडर इन संपीड़ित प्रतिनिधित्वों का उपयोग करके मैट्रिक्स गुणनफल A⊤B का अनुमान लगाता है। पेपर स्वतंत्र समान वितरण गॉसियन प्रविष्टियों वाले मैट्रिक्स के मामले के लिए अनुमानित माध्य वर्ग त्रुटि की गैर-स्पर्शोन्मुख निचली सीमा प्रदान करता है, नेस्टेड जाली पर आधारित सार्वभौमिक परिमाणक का निर्माण करता है, और R≈0.906 बिट्स/प्रविष्टि पर एक दिलचस्प चरण संक्रमण खोजता है, जो निम्न कोड-दर स्थिति में Johnson-Lindenstrauss आयाम न्यूनीकरण तकनीक की आवश्यकता को दर्शाता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

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

व्यावहारिक आवश्यकताएं

बड़े भाषा मॉडल के लिए, लेखकों ने आवश्यक परिमाणन दर का अनुमान लगाया है:

  • उत्पादन चरण में, CPU को संगणना संसाधनों का पूर्ण उपयोग करने के लिए 1-3 बिट्स/प्रविष्टि की परिमाणन दर की आवश्यकता है
  • पूर्व-भरण चरण में, तेज़ GPU पर चलने वाले छोटे LLM के लिए, लगभग 11.7 बिट्स/प्रविष्टि की परिमाणन दर की आवश्यकता है

मौजूदा विधियों की सीमाएं

  1. शास्त्रीय सदिश परिमाणन: मैट्रिक्स A और B को सीधे स्वतंत्र रूप से परिमाणित करना, फिर परिमाणित मैट्रिक्स का गुणनफल की गणना करना, O(n²) की त्रुटि का कारण बनता है
  2. स्केच विधि: हालांकि निष्पक्ष अनुमान प्रदान करते हैं, लेकिन विचरण अभी भी O(n²) है
  3. निर्धारणीय परिमाणक: गोलाकार सतह पर सदिशों के लिए Ω(n²) की निचली सीमा मौजूद है

मुख्य योगदान

  1. सैद्धांतिक निचली सीमा: iid गॉसियन प्रविष्टियों वाले मैट्रिक्स के लिए मैट्रिक्स गुणन परिमाणन की गैर-स्पर्शोन्मुख निचली सीमा प्रदान करता है
  2. सार्वभौमिक परिमाणक: नेस्टेड जाली पर आधारित सार्वभौमिक परिमाणक का निर्माण करता है, किसी भी मैट्रिक्स के लिए स्पष्ट त्रुटि गारंटी के साथ
  3. स्पर्शोन्मुख इष्टतमता: सिद्ध करता है कि प्रस्तावित परिमाणक iid गॉसियन मैट्रिक्स के लिए निचली सीमा को प्राप्त करता है, इसलिए स्पर्शोन्मुख रूप से इष्टतम है
  4. चरण संक्रमण घटना: R≈0.906 बिट्स/प्रविष्टि पर चरण संक्रमण खोजता है, निम्न कोड-दर में आयाम न्यूनीकरण की आवश्यकता को प्रकट करता है
  5. व्यावहारिक एल्गोरिथ्म: इष्टतमता के करीब प्रदर्शन के साथ कम जटिलता वाला कार्यान्वयन प्रदान करता है

विधि विवरण

कार्य परिभाषा

मैट्रिक्स A ∈ R^(n×a) और B ∈ R^(n×b) दिए गए हैं, लक्ष्य एनकोडर f₁: R^(n×a) → 2^(naR) और f₂: R^(n×b) → 2^(nbR) तथा डिकोडर g को डिज़ाइन करना है ताकि:

E∥A⊤B−g(f1(A),f2(B))∥F2E\|A^⊤B - g(f_1(A), f_2(B))\|_F^2

न्यूनतम हो, जहां प्रत्येक मैट्रिक्स प्रविष्टि R बिट्स का उपयोग करके वर्णित है।

मुख्य फलन Γ(R)

पेपर महत्वपूर्ण दर-विकृति फलन को परिभाषित करता है:

1 - \left(1 - (2 \cdot 2^{-2R^*} - 2^{-4R^*})\right) \frac{R}{R^*} & R < R^* \\ 2 \cdot 2^{-2R} - 2^{-4R} & R \geq R^* \end{cases}$$ जहां R* ≈ 0.906 निश्चित बिंदु समीकरण R = ½log₂(1 + 4R ln 2) का समाधान है। ### नेस्टेड जाली परिमाणन योजना #### 1. आंतरिक गुणनफल परिमाणन (मूल निर्माण खंड) गोलाकार सतह पर ρ-सहसंबद्ध सदिश U, V के लिए, नेस्टेड जाली Λc ⊂ Λf का उपयोग करके परिमाणन: **एनकोडिंग प्रक्रिया**: - U और V को क्रमशः स्वतंत्र डिदर सदिश Z₁, Z₂ जोड़ें - सूक्ष्म जाली Λf को परिमाणित करें - मोटे जाली Λc में कोसेट प्रतिनिधित्व आउटपुट करें **डिकोडिंग प्रक्रिया**: - कोसेट से परिमाणित बिंदु पुनः प्राप्त करें - डिदर हटाएं - आंतरिक गुणनफल अनुमान की गणना करें #### 2. मैट्रिक्स गुणन परिमाणन **पूर्व-प्रसंस्करण चरण**: 1. **शून्य केंद्रीकरण**: Ā = A - (1/n)1·1^⊤A, B̄ = B - (1/n)1·1^⊤B की गणना करें 2. **मानदंड परिमाणन**: प्रत्येक स्तंभ के माध्य और मानदंड को उच्च परिशुद्धि से वर्णित करें 3. **यादृच्छिक घूर्णन**: Ā और B̄ को समान ऑर्थोगोनल मैट्रिक्स S लागू करें **परिमाणन चरण**: - घुमाए गए प्रत्येक स्तंभ पर आंतरिक गुणनफल परिमाणक लागू करें - समय साझाकरण पैरामीटर κ और MMSE स्केलिंग पैरामीटर α का उपयोग करें ### तकनीकी नवाचार बिंदु 1. **डिदर तकनीक**: परिमाणन त्रुटि को इनपुट से स्वतंत्र बनाता है, निर्धारणीय परिमाणक की O(n²) त्रुटि से बचता है 2. **नेस्टेड जाली संरचना**: सीमित कोड-दर प्रदान करते हुए अच्छे परिमाणन प्रदर्शन को बनाए रखता है 3. **समय साझाकरण**: निम्न कोड-दर में आयाम न्यूनीकरण के माध्यम से इष्टतमता प्राप्त करता है 4. **यादृच्छिक घूर्णन**: किसी भी सदिश को गोलाकार समान वितरण में परिवर्तित करता है, विश्लेषण को सुविधाजनक बनाता है ## प्रायोगिक सेटअप ### सैद्धांतिक सत्यापन प्रयोग **डेटा उत्पादन**: - मैट्रिक्स A, B ∈ R^(n×n), प्रविष्टियां iid N(0,1) - n = 3 × 2¹¹ **कार्यान्वयन विवरण**: - मूल जाली: D₃ जाली (3-आयामी) - नेस्टेड अनुपात: q = 6 - लुकअप टेबल आकार: < 64KB (L1 कैश में फिट हो सकता है) - प्रभावी कोड-दर: ≈ 3.015 बिट्स/प्रतीक ### तुलना विधियां - 3-बिट स्केलर परिमाणक (ℓ∞ सामान्यीकरण) - सैद्धांतिक निचली सीमा Γ(R) ## प्रायोगिक परिणाम ### मुख्य परिणाम **प्रदर्शन तुलना**: - प्रस्तावित विधि: 1/n³ ∥Â⊤B - A⊤B∥²F ≈ 0.0593 - 3-बिट स्केलर परिमाणन: ≈ 0.1668 (लगभग 3 गुना अंतर) - सैद्धांतिक निचली सीमा: Γ(3.015) = 0.0304 **मुख्य निष्कर्ष**: 1. D₃ जाली पर आधारित योजना स्केलर परिमाणन से काफी बेहतर है 2. प्रदर्शन सैद्धांतिक इष्टतम के करीब है (लगभग 2 गुना अंतर) 3. n की वृद्धि के साथ, प्रदर्शन अंतर और भी कम हो जाएगा ### जटिलता विश्लेषण **एनकोडिंग जटिलता**: O(n log n) (तेज़ Hadamard रूपांतर का उपयोग करके) **डिकोडिंग जटिलता**: O(1) (लुकअप टेबल का उपयोग करके) **भंडारण ओवरहेड**: प्रत्येक परिमाणक को स्केलिंग कारक वर्णित करने के लिए O(log n) अतिरिक्त बिट्स की आवश्यकता है ## संबंधित कार्य ### यादृच्छिक रैखिक बीजगणित - **Monte Carlo मैट्रिक्स गुणन (MCMM)**: अनुमान के लिए पंक्तियों का यादृच्छिक नमूनाकरण - **स्थानीय संवेदनशील हैशिंग (LSH)**: कोसाइन समानता के लिए निम्न-आयामी स्केच - **सीमाएं**: सापेक्ष त्रुटि ∥A∥²F∥B∥²F/∥A⊤B∥²F के साथ बढ़ता है ### तंत्रिका नेटवर्क परिमाणन - **प्रशिक्षण के बाद परिमाणन**: OPTQ, GPTQ आदि विधियां - **घूर्णन तकनीकें**: QuIP, QuaRot Hadamard रूपांतर का उपयोग करते हैं - **जाली परिमाणन**: QUIP# भार परिमाणन के लिए E₈ जाली का उपयोग करता है ### सूचना सिद्धांत - **वितरित संपीड़न**: रैखिक फलन संगणना के लिए संपीड़न - **कोडबुक डिज़ाइन**: Voronoi कोड और नेस्टेड जाली कोड ## निष्कर्ष और चर्चा ### मुख्य निष्कर्ष 1. **इष्टतमता**: iid गॉसियन मैट्रिक्स के लिए, प्रस्तावित योजना सूचना-सैद्धांतिक निचली सीमा को प्राप्त करती है 2. **सार्वभौमिकता**: किसी भी मैट्रिक्स के लिए स्पष्ट प्रदर्शन गारंटी है 3. **चरण संक्रमण घटना**: R* ≈ 0.906 बिट्स/प्रविष्टि एक महत्वपूर्ण सीमा है 4. **व्यावहारिकता**: कम जटिलता वाला कार्यान्वयन सैद्धांतिक प्रदर्शन के करीब है ### सीमाएं 1. **साझा यादृच्छिकता**: एनकोडर और डिकोडर को यादृच्छिक बीज साझा करने की आवश्यकता है 2. **मैट्रिक्स शर्त**: मैट्रिक्स प्रविष्टियों को सीमित होना आवश्यक है (M = n^(10^22000)) 3. **उच्च-आयामी जाली**: सैद्धांतिक इष्टतमता के लिए उच्च-आयामी "अच्छी" जाली की आवश्यकता है, व्यावहारिक में निम्न-आयामी जाली का उपयोग किया जाता है 4. **निर्धारणीय योजना**: यह स्पष्ट नहीं है कि क्या यादृच्छिकता की आवश्यकता न होने वाली इष्टतम निर्धारणीय योजना मौजूद है ### भविष्य की दिशाएं 1. **बहु-मैट्रिक्स गुणनफल**: k>2 मैट्रिक्स के गुणनफल तक विस्तार 2. **अन्य दूरी मेट्रिक्स**: KL विचलन आदि गैर-MSE मेट्रिक्स 3. **निर्धारणीय परिमाणक**: साझा यादृच्छिकता की आवश्यकता न होने वाली योजनाओं की खोज 4. **गहन नेटवर्क अनुप्रयोग**: वास्तविक LLM में तैनाती और अनुकूलन ## गहन मूल्यांकन ### लाभ 1. **सैद्धांतिक कठोरता**: ऊपरी और निचली सीमा सहित संपूर्ण सूचना-सैद्धांतिक विश्लेषण प्रदान करता है 2. **व्यावहारिक मूल्य**: LLM अनुमान में वास्तविक बाधा समस्या को हल करता है 3. **तकनीकी नवाचार**: जाली परिमाणन, यादृच्छिक घूर्णन और समय साझाकरण को चतुराई से संयोजित करता है 4. **सार्वभौमिकता**: विशिष्ट मैट्रिक्स वितरण धारणा पर निर्भर नहीं है ### कमियां 1. **जटिलता**: सैद्धांतिक विश्लेषण काफी जटिल है, व्यावहारिक कार्यान्वयन को कई तकनीकी घटकों की आवश्यकता है 2. **स्थिरांक कारक**: हालांकि स्पर्शोन्मुख रूप से इष्टतम है, सीमित नमूने में स्थिरांक बड़े हो सकते हैं 3. **हार्डवेयर अनुकूलन**: विभिन्न हार्डवेयर प्लेटफॉर्म के लिए कार्यान्वयन को अनुकूलित करने की आवश्यकता है 4. **विस्तारशीलता**: दो मैट्रिक्स से कई मैट्रिक्स के गुणनफल तक विस्तार गैर-तुच्छ है ### प्रभाव **सैद्धांतिक योगदान**: - मैट्रिक्स गुणन परिमाणन के लिए सूचना-सैद्धांतिक आधार स्थापित करता है - चरण संक्रमण घटना और आयाम न्यूनीकरण की आवश्यकता को प्रकट करता है - इस क्षेत्र के लिए महत्वपूर्ण सैद्धांतिक बेंचमार्क प्रदान करता है **व्यावहारिक अनुप्रयोग**: - LLM परिमाणन के लिए नई सैद्धांतिक मार्गदर्शन प्रदान करता है - बाद के कार्य NestQuant ने वास्तविक LLM पर SOTA प्रदर्शन प्राप्त किया है - हार्डवेयर त्वरक डिज़ाइन के लिए सैद्धांतिक आधार प्रदान करता है ### लागू परिदृश्य 1. **बड़े भाषा मॉडल अनुमान**: भार और सक्रियण का संयुक्त परिमाणन 2. **किनारे कंप्यूटिंग**: मेमोरी-सीमित वातावरण में मैट्रिक्स संचालन 3. **वितरित संगणना**: संचार-सीमित मैट्रिक्स गुणन 4. **वैज्ञानिक संगणना**: बड़े पैमाने पर संख्यात्मक रैखिक बीजगणित समस्याएं ## संदर्भ पेपर 44 संबंधित संदर्भों का हवाला देता है, जो सूचना सिद्धांत, जाली सिद्धांत, यादृच्छिक रैखिक बीजगणित और तंत्रिका नेटवर्क परिमाणन सहित कई क्षेत्रों के महत्वपूर्ण कार्यों को शामिल करता है। विशेष ध्यान देने योग्य हैं: - Zamir की जाली एन्कोडिंग पुस्तक सैद्धांतिक आधार प्रदान करती है - Erez और Zamir का नेस्टेड जाली पर अग्रणी कार्य - OPTQ, QuIP आदि जैसी हाल की LLM परिमाणन विधियां - यादृच्छिक मैट्रिक्स सिद्धांत और गोलाकार ज्यामिति के संबंधित परिणाम --- **समग्र मूल्यांकन**: यह सिद्धांत और व्यावहार दोनों पर महत्वपूर्ण योगदान वाला एक उत्कृष्ट पेपर है, जो मैट्रिक्स गुणन परिमाणन समस्या के लिए एक ठोस सूचना-सैद्धांतिक आधार प्रदान करता है, और इष्टतमता के करीब एक व्यावहारिक एल्गोरिथ्म प्रदर्शित करता है। यह कार्य बड़े पैमाने पर मशीन लर्निंग सिस्टम में परिमाणन तकनीकों को समझने और सुधारने के लिए महत्वपूर्ण है।