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

التكميم الأمثل لضرب المصفوفات

المعلومات الأساسية

  • معرّف الورقة: 2410.13780
  • العنوان: التكميم الأمثل لضرب المصفوفات
  • المؤلفون: Or Ordentlich (جامعة العبرية في القدس)، Yury Polyanskiy (معهد ماساتشوستس للتكنولوجيا)
  • التصنيف: 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 في حالات معدل الترميز المنخفض.

خلفية البحث والدافع

تعريف المشكلة

مع ظهور الشبكات العصبية العميقة ونماذج اللغة الكبيرة، أصبح ضرب المصفوفات عنق الزجاجة الرئيسي في الحسابات. غالباً ما تكون أجهزة الحوسبة الحديثة محدودة بعرض النطاق الترددي للذاكرة وليس بقدرة الحوسبة. لذلك، أصبح ضغط المصفوفات بشكل فقدان لتقليل نقل الذاكرة مشكلة مهمة.

الاحتياجات العملية

بالنسبة لنماذج اللغة الكبيرة، قدّر المؤلفون معدل التكميم المطلوب:

  • في مرحلة التوليد، يحتاج المعالج إلى معدل تكميم 1-3 بت/عنصر للاستفادة الكاملة من موارد الحوسبة
  • في مرحلة ملء البيانات المسبقة، بالنسبة لنماذج اللغة الصغيرة التي تعمل على وحدات معالجة الرسومات السريعة، يلزم معدل تكميم يبلغ حوالي 11.7 بت/عنصر

قيود الطرق الموجودة

  1. التكميم المتجهي الكلاسيكي: يؤدي التكميم المستقل المباشر للمصفوفات A و B ثم حساب حاصل ضرب المصفوفات المكممة إلى خطأ O(n²)
  2. طرق الرسم: على الرغم من توفيرها تقديرات غير متحيزة، إلا أن التباين لا يزال O(n²)
  3. المكممات الحتمية: توجد حدود سفلية Ω(n²) للمتجهات على الكرة

المساهمات الأساسية

  1. الحدود النظرية السفلية: توفير حدود سفلية غير متقاربة لتكميم ضرب المصفوفات للمصفوفات ذات العناصر الغاوسية المستقلة والموزعة بشكل متطابق
  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: **عملية الترميز**: - إضافة متجهات اهتزاز مستقلة Z₁ و Z₂ إلى U و V على التوالي - التكميم إلى الشبكة الدقيقة Λf - إخراج تمثيل المجموعة الجانبية في الشبكة الخشنة Λc **عملية فك التشفير**: - استرجاع نقطة التكميم من المجموعة الجانبية - إزالة الاهتزاز - حساب تقدير الضرب الداخلي #### 2. تكميم ضرب المصفوفات **خطوات المعالجة المسبقة**: 1. **إزالة المركز**: حساب Ā = A - (1/n)1·1^⊤A، B̄ = B - (1/n)1·1^⊤B 2. **تكميم المعايير**: وصف عالي الدقة لمتوسط كل عمود ومعياره 3. **الدوران العشوائي**: تطبيق نفس المصفوفة المتعامدة S على Ā و B̄ **خطوات التكميم**: - تطبيق مكمم الضرب الداخلي على كل عمود مُدار - استخدام معاملات المشاركة الزمنية κ ومعاملات تحجيم MMSE α ### نقاط الابتكار التقني 1. **تقنية الاهتزاز**: جعل خطأ التكميم مستقلاً عن المدخلات، مما يتجنب خطأ O(n²) للمكممات الحتمية 2. **بنية الشبكات المتداخلة**: توفير معدل ترميز محدود مع الحفاظ على أداء تكميم جيدة 3. **المشاركة الزمنية**: تحقيق الأمثلية في معدل الترميز المنخفض من خلال تقليل الأبعاد 4. **الدوران العشوائي**: تحويل المتجهات التعسفية إلى توزيع موحد على الكرة، مما يسهل التحليل ## إعداد التجارب ### تجارب التحقق النظري **توليد البيانات**: - المصفوفات A, B ∈ R^(n×n)، العناصر iid N(0,1) - n = 3 × 2¹¹ **تفاصيل التطبيق**: - الشبكة الأساسية: شبكة D₃ (ثلاثية الأبعاد) - نسبة التداخل: 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. الأداء قريبة من الأمثلية النظرية (فجوة حوالي مرتين) 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. **مقاييس المسافة الأخرى**: مقاييس غير MSE مثل تباعد KL 3. **المكممات الحتمية**: استكشاف المخططات التي لا تتطلب مشاركة عشوائية 4. **تطبيقات الشبكات العميقة**: النشر والتحسين في نماذج اللغة الكبيرة الفعلية ## التقييم المتعمق ### المميزات 1. **الصرامة النظرية**: توفير تحليل معلومات نظري كامل، بما في ذلك الحدود العليا والدنيا 2. **القيمة العملية**: حل مشكلة الاختناق الفعلية في استدلال نماذج اللغة الكبيرة 3. **الابتكار التقني**: دمج ذكي لتكميم الشبكات والدوران العشوائي والمشاركة الزمنية 4. **العمومية**: لا تعتمد على افتراضات توزيع مصفوفة محددة ### أوجه القصور 1. **التعقيد**: التحليل النظري معقد إلى حد ما، والتطبيق العملي يتطلب مكونات تقنية متعددة 2. **معاملات ثابتة**: على الرغم من الأمثلية المقاربة، قد تكون المعاملات في العينات المحدودة كبيرة 3. **التكيف مع الأجهزة**: يتطلب تحسين التطبيق لمنصات أجهزة مختلفة 4. **قابلية التوسع**: التوسع من مصفوفتين إلى ضرب مصفوفات متعددة ليس تافهاً ### التأثير **المساهمات النظرية**: - إنشاء أساس نظرية المعلومات لتكميم ضرب المصفوفات - الكشف عن ظاهرة الانتقال وضرورة تقليل الأبعاد - توفير معيار نظري مهم لهذا المجال **التطبيقات العملية**: - توفير إرشادات نظرية جديدة لتكميم نماذج اللغة الكبيرة - حققت الأعمال اللاحقة NestQuant أداء SOTA على نماذج اللغة الكبيرة الفعلية - توفير أساس نظري لتصميم معجلات الأجهزة ### السيناريوهات المعمول بها 1. **استدلال نماذج اللغة الكبيرة**: التكميم المشترك للأوزان والتنشيطات 2. **الحوسبة الطرفية**: عمليات المصفوفات في البيئات المحدودة بالذاكرة 3. **الحوسبة الموزعة**: ضرب المصفوفات المحدود بالاتصالات 4. **الحسابات العلمية**: مشاكل الجبر الخطي الرقمي الكبيرة الحجم ## المراجع تستشهد الورقة بـ 44 مرجعاً ذا صلة، تغطي مجالات متعددة بما في ذلك نظرية المعلومات ونظرية الشبكات والجبر الخطي العشوائي وتكميم الشبكات العصبية. من بين الأعمال الجديرة بالاهتمام بشكل خاص: - مؤلف Zamir عن ترميز الشبكات يوفر الأساس النظري - العمل الرائد لـ Erez و Zamir حول الشبكات المتداخلة - طرق تكميم نماذج اللغة الكبيرة الحديثة مثل OPTQ و QuIP وغيرها - النتائج ذات الصلة في نظرية المصفوفات العشوائية والهندسة الكروية --- **التقييم الإجمالي**: هذه ورقة ممتازة لها مساهمات مهمة من الناحية النظرية والعملية، حيث توفر أساساً معلوماتياً صارماً لمشكلة تكميم ضرب المصفوفات، وتعرض خوارزمية عملية قريبة من الأمثلية. يحمل هذا العمل أهمية كبيرة لفهم وتحسين تقنيات التكميم في أنظمة التعلم الآلي الكبيرة الحجم.