🤖 machine learning

GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding

تقدم هذه الورقة البحثية GPTQ-2D، وهو خوارزمية ذات تعقيد زمني تكعيبي تقوم بكفاءة بعملية التقريب التكيفي ثنائي الجوانب على المصفوفات من خلال معالجة المدخلات بالتوازي على طول الأقطار المضادة، مما يقلل التعقيد الحسابي من الزمن الرباعي الذي تتطلبه طرق التجهيز الشعاعي القياسية مع إنتاج نتائج متطابقة.

المؤلفون الأصليون: Jiale Chen, Torsten Hoefler, Dan Alistarh

نُشر 2026-07-30

📖 6 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Jiale Chen, Torsten Hoefler, Dan Alistarh

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول تعبئة برج ضخم ومتذبذب من مكعبات "جينجا" (Jenga) في صندوق مرتب وصلب. في عالم الذكاء الاصطناعي، هذه "المكعبات" هي أرقام داخل جدول بيانات ضخم (مصفوفة) تُعلم الكمبيوتر كيف يفكر. ولجعل هذه الحواسيب تعمل بشكل أسرع وتستهلك طاقة أقل، يحاول المهندسون تقليص هذه الأرقام إلى أعداد صحيحة بسيطة، وهي عملية تُعرف بـ "الكمية" (quantization). لكن هنا تكمن المشكلة: إذا قمت فقط بقطع الكسور العشرية بشكل عشوائي، سينهار البرج، ويبدأ الكمبيوتر في ارتكاب أخطاء سخيفة.

لإصلاح ذلك، يستخدم العلماء حيلة ذكية تسمى "التقريب التكيفي" (adaptive rounding). فكر في الأمر كأنه لعبة أحجار الدومينو؛ عندما تسقط حجراً واحداً (تقرب رقماً)، فإن ذلك يخلق تذبذباً طفيفاً. وبدلاً من تجاهل هذا التذبذب، يقوم التقريب التكيفي بالتقاطه ودفعه للأمام إلى حجر الدومينو التالي في الخط، مع تعديله قليلاً ليبقى الخط بأكği مستقيماً. هذه الطريقة، المعروفة باسم GPTQ، كانت نجماً ساطعاً لسنوات، لكنها تعمل بشكل جيد فقط عندما تكون أحجار الدومينو مرتبة في خط واحد طويل. ومع ذلك، فإن نماذج الذكاء الاصطناعي الحديثة تشبه شبكة ضخمة ثنائية الأبعاد من أحجار الدومينو، حيث يؤثر إسقاط حجر واحد على جيرانه جهة اليمين وجهة الأسفل أيضاً. ومحاولة إصلاح هذه الشبكة ثنائية الأبعاد باستخدام طريقة "الخط الواحد" القدية تشبه محاولة فك عقدة عن طريق السحب من طرف واحد فقط؛ إنها تعمل، لكنها تستغرق وقتاً طويلاً جداً وتدخل في حلقة مفرغة أبطأ بأربع مرات مما ينبغي.

يقدم هذا البحث طريقة جديدة لفك تلك العقدة، تسمى GPTQ-2D. اكتشف المؤلفون، جيالي تشين، وتورستن هوفلر، ودان أليستاره، أنك لست بحاجة إلى سحب أحجار الدومينو واحداً تلو الآخر في خط طويل. بدلاً من ذلك، يمكنك الإمساك بصفوف قطرية كاملة من أحجار الدومينو وإصلاحها جميعاً في وقت واحد. ومن خلال إدراكهم أن "التذبذب" الناتج عن كتلة واحدة ينتقل فقط للأسفل ولليمين، وجدوا طريقاً مختصراً يسمح لهم بمعالجة الشبكة بأجزاء ضئيلة من الوقت. لقد أثبتوا رياضياً أن هذه الطريقة الجديدة تنتج نفس البرج المثالي تماماً كما تفعل الطريقة القديمة البطيئة، لكنها تفعل ذلك في زمن "تكعيبي" (وهو سريع) بدلاً من الزمن "التكعيبي الرابع" (وهو بطيء للغاية). وهذا يعني أنه يمكننا الآن تقليص هذه الأدمغة الضخمة للذكاء الاصطعي بشكل أكثر كفاءة دون كسرها، مما يجعل الذكاء الاصطناعي القوي متاحاً للاستخدام على الأجهزة اليومية.

قصة اللغز ذي الجانبين

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

لكن في عالم الذكال الاصطناعي الحقيقي، يكون "الأشخاص" مرتبين في شبكة، مثل لوحة الشطرنج. والآن، إذا أسقط شخص في المنتصف عملة معدنية، فيجب مشاركة هذا الوزن مع كل من يقف تحته وكل من يقف إلى يمينه. إذا حاولت إصلاح هذه الشبكة عبر المرور بكل مربع على حدٍ، (النهج "المتجهي")، فستجد نفسك تقوم بقدر هائل من العمل المكرر. الأمر يشبه محاولة تنظيف غرفة كاملة عن طريق مسح كل بوصة من الأرض، حتى الأجزاء التي نظفتها بالفعل، مراراً وتكراراً. توضح الرياضيات أن هذا يستغرق وقتاً طويلاً جداً، حيث ينمو بسرعة كبيرة لدرجة أنه إذا ضاعفت حجم الشبكة، فإن العمل يتضاعف أربع مرات (أو أكثر).

نظر مؤلفو هذا البحث إلى هذه الشبكة وأدركوا شيئاً سحرياً: "التذبذب" أو الخطأ الناتج عن أي مربع واحد ينتقل فقط في اتجاه محدد — للأسفل ولليمين. هذا يخلق رسماً بيانياً للتبعية يشبه الدرج. إذا نظرت إلى الشبكة قطرياً (من أعلى اليمين إلى أسفل اليسار)، فسترى أن جميع المربعات الموجودة على نفس الخط القطري مستقلة عن بعضها البعض. إنها لا تؤثر على بعضها البعض!

هذه هي لحظة "وجدتها!". نظرًا لأنها مستقلة، يمكنك تقريب جميع الأرقام في خط قطري واحد في نفس الوقت، مثل موجة تضرب الشاطئ. هذا هو جوهر GPTQ-2D.

سحر المخزن المؤقت "الكسول"

إذاً، كيف جعلوا هذا سريعاً؟ في الطريقة القديمة "البطيئة"، في كل مرة تقوم فيها بإصلاح رقم، تذهب فوراً لتحديث كل مربع في المستطيل الضخم الموجود أسفله وإلى يمينه. هذا الكثير من العمل غير المجدي.

خوارزمية GPTQ-2D الجديدة "كسولة" أكثر بكثير (بطريقة جيدة). فبدلاً من تحديث المستطيل بالكامل فوراً، تقوم فقط بدفع الخطأ للأسفل في عمودها الخاص وعبر صفها الخاص، تاركة "ملاحظة" في مخزن مؤقت (buffer). الأمر يشبه المعلم الذي، بدلاً من الذهاب إلى مكتب كل طالب لتصحيح خطأ، يكتفي بكتابة التصحيح على مكتب الطالب نفسه وعلى مكتب الطالب الذي بجانبه من جهة اليمين. الطلاب في نهاية الخط سيرون هذه الملاحظات في النهاية ويصلحون أنفسهم.

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

تثبت الورقة البحثية أن هذا النهج القطري الكسول ينتج نفس النتيجة تماماً كالطريقة القديمة التي تتم خطوة بخطوة. إنه ليس مجرد تقريب؛ بل هو ضمان رياضي. يوضح المؤلفون أنه سواء قمت بإصلاح أحجار الدومينو واحداً تلو الآخر أو في موجات قطرية، فإن البرج النهائي سيقف تماماً كما هو.

لماذا يهم هذا؟

الورقة البحثية لا تفترض فقط أن هذا أسرع؛ بل قامت بالحسابات لإثبات ذلك. بالنسبة لشبكة مربعة (حيث يتساوى عدد الصفوف مع عدد الأعمدة)، تستغرق الطريقة القديمة وقتاً يتناسب مع حجم الشبكة مرفوعاً للقوة الرابعة ( $O(m^2n^2)$ ). أما طريقة GPTQ-2D الجديدة، فتستغرق وقتاً يتناسب مع حجم الشبكة مرفوعاً للقوة الثالثة ( $O(m^3)$ ).

للتوضيح: إذا كان لديك شبكة بمقاس 1,000 في 1,000، فإن الطريقة القديمة تبذل عملاً أكثر بمليار مرة مما تفعله الطريقة الجديدة. لقد خفضت الطريقة الجديدة تكلفة إصلاح شبكة ثنائية الجوانب لتصبح في نفس مستوى إصلاح خط بسيط ذي جانب واحد.

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

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

ملخص تقني لورقة "GPTQ-2D: التقريب التكيفي ثنائي الجانب من الدرجة التكعيبية"

1. بيان المشكلة

تتناول الورقة مشكلة التقريب التكيفي ثنائي الجانب، وهي تعميم للتقريب المصفوفي أحادي الجانب القياسي المستخدم في طرق التكميم مثل GPTQ (Frantar et al., 2023) وخوارزمية باباي لأقرب مستوٍ (Babai, 1986).

الحالة أحادية الجانب: بالنظر إلى مصفوفة حقيقية $X \in \mathbb{R}^{m \times n}$ ومصفوفة أساس ثابتة غير منفردة $A \in \mathbb{R}^{m \times m}$ ، الهدف هو إيجاد مصفوفة صحيحة $Z$ تقلل من $\|A(Z - X)\|_F^2$ . يتم حل ذلك بطريقة جشعة عبر معالجة المدخلات بترتيب ثابت (مثل ترتيب الأعمدة)، ونشر أخطاء التقريب عبر مصفوفة تغذية راجعة مثلثية. تعمل هذه الطريقة بزمن قدره $O(m^2 \max(m, n))$ (تكعيبي للمصفوفات المربعة).
الحالة ثنائية الجانب: تقدم الورقة مصفوفة أساس ثانية ثابتة وغير منفردة $B \in \mathbb{R}^{n \times n}$ تعمل من جهة اليمين، مما يغير الهدف إلى:
$\|A(Z - X)B\|_F^2 = \|(B^\top \otimes A)(\text{vec}(Z) - \text{vec}(X))\|_2^2$
حيث يرمز $\otimes$ إلى حاصل الضرب كرونيكر (Kronecker product). وبينما يمكن حل ذلك عن طريق تحويل المصفوفة إلى متجه بطول $mn $وتطبيق التقريب التكيفي أحادي البعد القياسي، فإن مصفوفة غرام الناتجة هي$ H \otimes G $(حيث$ H=BB^\top $و$ G=A^\top A $). إن إجراء مسح مباشر عبر جميع الإحداثيات$ mn $يستلزم تعقيداً زمنياً قدره$ O(m^2 n^2)$ (رباعي للمصفوفات المربعة)، وهو أمر باهظ حسابياً للمصفوفات الكبيرة.

التحدي الأساسي يكمن في تحقيق نفس مسار التقريب لنهج المتجه أحادي البعد ولكن بتعقيد حسابي مخفض، بحيث يطابق التكلفة التكعيبية للحالة أحادية الجانب بشكل مثالي.

2. المنهجية

يقترح المؤلفون GPTQ-2D، وهي خوارزمية تستغل البنية المحددة لحاصل الضرب كرونيكر لتقليل التعقيد من رابع إلى تكعيبي.

رؤى نظرية رئيسية:

بنية التغذية الراجعة لكرونيكر: مصفوفة التغذية الراجعة للمشكلة المتجهية هي $F = U^\top \otimes L$ ، حيث $L$ و $U$ هما عوامل مثلثية دنيا وعليا وحيدة مستخرجة من معكوسات مصفوفات غرام $G$ و $H$ .
تحديثات الرتبة الواحدة (Rank-One Updates): خطأ التقريب عند المدخل $(i, j)$ يولد تحديث تغذية راجعة من الشكل $L_{:,i} E_{ij} U_{j,:}$ . هذا عبارة عن تحديث من الرتبة الواحدة مدعوم فقط على المستطيل السفلي الأيمن $\{i, \dots, m\} \times \{j, \dots, n\}$ .
استقلال القطر المضاد: نظرًا لأن التحديث الناتج عن $(i, j)$ يؤثر فقط على المدخلات $(p, q)$ حيث $p \ge i$ و $q \ge j$ ، فإن المدخلات الواقعة على نفس القطر المضاد ( $i+j = s$ ) مستقلة عن بعضها البعض. ويمكن معالجتها بالتوازي بمجرد اكتمال معالجة جميع الأقطار المضادة السابقة.

النهج الخوارزمي:

المسح عبر القطر المضاد: بدلاً من المسح بترتيب الأعمدة أو الصفوف، تعالج الخوارزمية المصفوفة عبر $m+n-1$ مرحلة، تقابل الأقطار المضادة.
الانتشار الكسول (خدعة "المخزن المؤقت"):
- التنفيذ الساذج للمسح عبر القطر المضاد سيظل يتطلب عملاً قدره $O(m^2 n^2)$ لأن تطبيق تحديث الرتبة الواحدة $L_{:,i} E_{ij} U_{j,:}$ يمس بكتلة كبيرة من المصفوفة بكثافة.
- تتجنب GPTQ-2D ذلك عبر الحفاظ على مخزن مؤقت مساعد $C = LE$ .
- عندما يتم تقريب مدخل $(i, j)$ ، يتم نشر الخطأ $E_{ij}$ فقط على طول عموده المحدد (عبر $L$ ) وصفه (عبر $U$ ) فوراً.
- يتم تأجيل "كتلة" تحديث المستطيل. تقوم الخوارزمية بدفع الخطأ لأسفل العمود في المخزن المؤقت $C$ ، ولاحقاً، يتم دفع قيم المخزن باتجاه اليمين على طول الصفوف.
- تضمن استراتيجية "الدفع" هذه تحديث كل مدخل مرة واحدة بالضبط لكل تبعية، مما يقلل تكلفة المسح إلى $O(mn \max(m, n))$ .
التنفيذ المجزأ (Blocked Implementation): لتحسين الأداء العملي على الأجهزة المتوازية، قدم المؤلفون نسخة مجزأة (الخوارزمية 4). تعالج هذه النسخة $w$ من الأقطار المضادة في آن واحد، حيث تجمع الأخطاء في كتلة وتقوم بتفريغها إلى بقية المصفوفة باستخدام ضرب مصفوفات شبيهة بالنطاق (band-like)، على غرار تحديثات الكتل الكسولة في GPTQ.

3. المساهمات الرئيسية

الصياغة: أعادت الورقة صياغة تقريب المصفوفة ثنائي الجانب كتقريب متجه تحت مقياس كرونيكر، وأثبتت أن التغذية الراجعة الناتجة هي من الرتبة الواحدة وقابلة للفصل.
تقليل التعقيد: أثبتت أن المشكلة ثنائية الجانب يمكن حلها في زمن قدره $O((\max(m, n))^3)$ ، مما يطابق التكلفة التقاربية لـ GPTQ أحادية الجانب، بدلاً من التكلفة $O(m^2 n^2)$ للمسح المتجهي المباشر.
التكافؤ التام: يثبت المبرهنة 2 أن GPTQ-2D تنتج المصفوفة المقربة المطابقة تماماً لخوارزمية التقريب التكيفي أحادي البعد المطبقة على المدخل المتجهي، بشرما تم استخدام قاعدة لكسر التعادل (tie-breaking rule) حتمية.
عدم التغير في الترتيب: أثبتت الورقة (المبرهنة 1) أن التقريب التكيفي ثابت تجاه ترتيب المعالجة، طالما أن الترتيب يحترم تبعات التغذية الراجعة (أي ترتيب طوبولوجي لمخطط التبعية). وهذا يبرر المسح المتوازي عبر القطر المضاد.

4. النتائج وتحليل التعقيد

التعقيد الزمني:
- التحليل (Factorization): حساب تحليلات LDL لمعكوسات مصفوفات غرام يستغرق $O((\max(m, n))^3)$ .
- المسح (Sweep): يستغرق مسح التقريب $O(mn \max(m, n))$ .
- الإجمالي: بالنسبة للمصفوفات المربعة ( $m=n$ )، يبلغ التعقيد الإجمالي $O(m^3)$ ، وهو تحسن كبير عن $O(m^4)$ للنهج الكثيف المباشر.
التوازي: تدعم الخوارزمية التوازي بشكل طبيعي عبر $m+n-1$ مرحلة. وضمن كل مرحلة (القطر المضاد)، يمكن معالجة جميع المدخلات في وقت واحد.
الذاكرة: مساحة التخزين العاملة هي $O((\max(m, n))^2)$ للعوامل و $O(mn)$ لمخازن المسح المؤقتة.

5. الأهمية والادعاءات

تضع الورقة GPTQ-2D ليس كمنافس لـ GPTQ أحادي الجانب، بل كامتداد ضروري للسيناريوهات التي تتطلب مقاييس ثنائية الجانب (مثل مصفوفات هسيان ذات عامل كرونيكر في التكميم).

امتداد لـ GPTQ: يذكر المؤلفون أن التقريب أحادي الجانب هو الحالة الخاصة عندما تكون $B=I$ . وتوسع GPTQ-2D هذه القدرة لتشمل الحالة ثنائية الجانب دون تحمل زيادة في التكلفة الحسابية قدرها $\Theta(\min(m, n))$ .
الفائدة العملية: صُممت الخوارزمية لتكون بديلاً جاهزاً (drop-in replacement) لخطوة التقريب في الطرق ثنائية الجانب الموجودة مثل YAQA (Tseng et al., 2026). وبينما تستخدم YAQA أيضاً مسحات القطر المضاد، إلا أن تنفيذها المرجعي يستخدم ضرب المصفوفات الكثيفة، مما ينتج عنه تعقيد رباعي. توفر GPTQ-2D نفس مسار التقريب مع تعقيد تكعيبي، مما يجعلها قابلة للتطبيق في التطبيقات واسعة النطية.
النطاق المحدود: تتجنب الورقة صراحةً تقديم ادعاءات حول الأمثلية العالمية (مشيرة إلى أن إيجاد أقرب نقطة شبكية بالضبط هو مسألة NP-hard) وتركز حصرياً على كفاءة مسار التقريب التكيفي الجشع المحدد بواسطة المقياس. هي لا تقترح تطبيقات جديدة بل تعمل على تحسين التكلفة الحسابية لصيغ التقريب التكيفي ثنائي الجانب الموجودة.