2025-11-17T17:13:12.426721

Cached Adaptive Token Merging: Dynamic Token Reduction and Redundant Computation Elimination in Diffusion Model

Saghatchian, Moghadam, Nickabadi

Diffusion models have emerged as a promising approach for generating high-quality, high-dimensional images. Nevertheless, these models are hindered by their high computational cost and slow inference, partly due to the quadratic computational complexity of the self-attention mechanisms with respect to input size. Various approaches have been proposed to address this drawback. One such approach focuses on reducing the number of tokens fed into the self-attention, known as token merging (ToMe). In our method, which is called cached adaptive token merging(CA-ToMe), we calculate the similarity between tokens and then merge the r proportion of the most similar tokens. However, due to the repetitive patterns observed in adjacent steps and the variation in the frequency of similarities, we aim to enhance this approach by implementing an adaptive threshold for merging tokens and adding a caching mechanism that stores similar pairs across several adjacent steps. Empirical results demonstrate that our method operates as a training-free acceleration method, achieving a speedup factor of 1.24 in the denoising process while maintaining the same FID scores compared to existing approaches.

academic

دمج الرموز المخزنة المكيفة: تقليل الرموز الديناميكي والقضاء على الحسابات الزائدة في نموذج الانتشار

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

معرّف الورقة: 2501.00946
العنوان: دمج الرموز المخزنة المكيفة: تقليل الرموز الديناميكي والقضاء على الحسابات الزائدة في نموذج الانتشار
المؤلفون: أميد ساغتشيان، عطيه غ. مقدم، أحمد نيكابادي (جامعة أمير كبير للتكنولوجيا)
التصنيف: cs.CV (رؤية الحاسوب)
تاريخ النشر: 1 يناير 2025 (نسخة arXiv المسبقة)
رابط الورقة: https://arxiv.org/abs/2501.00946
رابط الكود: https://github.com/omidiu/ca_tome

الملخص

أصبحت نماذج الانتشار طريقة واعدة لتوليد صور عالية الجودة وعالية الأبعاد. ومع ذلك، تواجه هذه النماذج تكاليف حسابية عالية وسرعة استدلال بطيئة، ويرجع ذلك جزئياً إلى التعقيد الحسابي التربيعي لآلية الانتباه الذاتي بالنسبة لحجم الإدخال. تقترح هذه الورقة طريقة دمج الرموز المكيفة المخزنة (CA-ToMe)، والتي تعالج هذه المشكلة من خلال حساب التشابه بين الرموز ودمج الرموز التي تتجاوز درجة تشابهها معامل الحد t. نظراً للأنماط المتكررة والتغييرات في تكرار التشابه الملاحظة في الخطوات المتجاورة، تعزز الطريقة أسلوب دمج الرموز من خلال تنفيذ حد تكيفي وإضافة آلية التخزين المؤقت. تُظهر النتائج التجريبية أن الطريقة، كطريقة تسريع خالية من التدريب، تحقق تسريعاً بمعامل 1.24 مرة في عملية إزالة الضوضاء مع الحفاظ على نفس درجة FID للطرق الموجودة.

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

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

تُظهر نماذج الانتشار أداءً ممتازاً في مهام توليد الصور، لكنها تواجه مشاكل جدية في الكفاءة الحسابية:

التكاليف الحسابية العالية: التعقيد التربيعي لآلية الانتباه الذاتي يؤدي إلى سرعة استدلال بطيئة
عملية إزالة الضوضاء المتسلسلة: لا يمكن موازاتها، وكل خطوة إزالة ضوضاء تتطلب حسابات متكررة
الحسابات الزائدة: توجد حسابات متكررة كبيرة بين الخطوات الزمنية المتجاورة

أهمية المشكلة

التأخير العالي لنماذج الانتشار يحد من استخدامها في التطبيقات التي تتطلب استدلالاً سريعاً
التكاليف الحسابية المرتفعة تجعل نشر النموذج صعباً، خاصة في البيئات محدودة الموارد
الطرق الموجودة للتسريع إما تتطلب إعادة تدريب أو تسبب خسائر كبيرة في الجودة

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

طرق تقليل خطوات الأخذ العينات عادة ما تتطلب إعادة تدريب أو استخدام حلالات عددية معقدة
طرق قص الرموز تؤدي إلى فقدان المعلومات وانخفاض الأداء
دمج الرموز التقليدي (ToMe) يستخدم معدل دمج ثابت، وغير قادر على التكيف مع التغييرات في توزيع التشابه عبر الخطوات الزمنية والطبقات المختلفة

الدافع للبحث

بناءً على ملاحظة ظاهرتين رئيسيتين:

وجود تغييرات كبيرة في توزيع تشابه الرموز عبر الخطوات الزمنية والطبقات المختلفة
إظهار أزواج الرموز بين خطوات الاستدلال المتجاورة تشابهاً عالياً جداً

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

اقتراح آلية حد تكيفية: تعديل استراتيجية الدمج ديناميكياً وفقاً لتوزيع تشابه الرموز، بدلاً من معدل الدمج الثابت
تصميم آلية التخزين المؤقت: الاستفادة من التشابه بين الخطوات المتجاورة، وتخزين أزواج الرموز مؤقتاً لتقليل الحسابات المتكررة
تحقيق التسريع الخالي من التدريب: يمكن تطبيق الطريقة مباشرة على النماذج المدربة مسبقاً دون الحاجة إلى إعادة تدريب
تحقيق مقايضة أفضل بين الجودة والسرعة: مقارنة بطريقة ToMe الأساسية، تحقق سرعة استدلال أسرع مع الحفاظ على جودة الصورة

شرح الطريقة بالتفصيل

تعريف المهمة

الإدخال: تسلسل الرموز في عملية إزالة الضوضاء من نموذج الانتشار الإخراج: عملية استدلال معجلة من خلال دمج تكيفي وتحسين التخزين المؤقت القيود: الحفاظ على عدم انخفاض جودة الصورة المولدة بشكل كبير

معمارية النموذج

1. آلية دمج الرموز التكيفية

تستخدم طريقة ToMe التقليدية نسبة ثابتة r لدمج الرموز، بينما تقدم CA-ToMe حد تشابه t:

الفكرة الأساسية:

تقسيم الصورة إلى مناطق خطوة بحجم sx × sy
اختيار رمز الزاوية العلوية اليسرى من كل منطقة خطوة كرمز هدف
حساب تشابه جيب التمام بين رموز المصدر والرموز الهدف
دمج فقط أزواج الرموز التي يتجاوز تشابهها الحد t

تحليل المزايا:

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

2. تصميم آلية التخزين المؤقت

بناءً على تحليل مسافة جاكار، تم اكتشاف تشابه عالي في أزواج الرموز بين الخطوات المتجاورة:

$JaccardDistance(A_n, A_{n+1}) = 1 - \frac{|A_n \cap A_{n+1}|}{|A_n \cup A_{n+1}|}$

حيث An تمثل مجموعة جميع أزواج الرموز المصدر-الهدف في الخطوة n.

استراتيجية التنفيذ:

تعيين نقاط تفتيش (checkpoints)، وحساب مصفوفة التشابه فقط في خطوات زمنية محددة
إعادة استخدام أزواج الرموز المحسوبة مسبقاً في خطوات غير نقاط التفتيش
تقليل كبير في تكلفة حساب مصفوفة التشابه المتكررة

نقاط الابتكار التقني

الديناميكية التكيفية: تعديل استراتيجية الدمج تلقائياً وفقاً لتوزيع التشابه، تجنب قيود المعاملات الثابتة
تحسين البعد الزمني: الاستفادة من الزيادة في الخطوات الزمنية، وتقليل كمية الحسابات من خلال التخزين المؤقت
التطبيق الانتقائي على مستوى الطبقة: تطبيق التحسينات بشكل خاص على الطبقات العليا كثيفة الحسابات في U-Net (D1 و U1)
عدم الحاجة إلى إعادة التدريب: كطريقة تسريع قابلة للتوصيل والتشغيل، يمكن تطبيقها مباشرة على النماذج الموجودة

إعداد التجربة

مجموعات البيانات

مجموعة بيانات ImageNet-1k: توليد 2000 صورة بدقة 512×512 (صورتان لكل فئة، إجمالي 1000 فئة)
مجموعة التحقق: استخدام 5000 صورة من مجموعة التحقق من ImageNet-1k لحساب درجة FID
قالب المطالبة: "A high-quality photograph of a classname."

مقاييس التقييم

FID (مسافة جاكار الاستقرائية): المقياس الرئيسي لقياس جودة الصور المولدة
وقت الاستدلال: متوسط الوقت لتوليد 2000 صورة
PSNR: نسبة الذروة إلى الضوضاء، قياس جودة إعادة البناء على مستوى البكسل
SSIM: مؤشر التشابه الهيكلي، تقييم التوافق المكاني والهيكلي

طرق المقارنة

الأساس: Stable Diffusion v1.5 الأصلي
ToMe: طريقة دمج الرموز التقليدية (r=50%)

تفاصيل التنفيذ

الأجهزة: وحدة معالجة رسومات Tesla V100S
خطوات الانتشار: 50 خطوة أخذ عينات PLMS
مقياس CFG: 7.5
حجم الخطوة: ثابت 2×2
الطبقات المطبقة: تطبيق فقط على طبقات D1 و U1 في U-Net

نتائج التجربة

النتائج الرئيسية

النموذج	FID	متوسط الوقت (ثانية)	معامل التسريع
الأساس	33.66	7.61±0.001	1.0×
ToMe	34.16	6.39±0.006	1.19×
CA-ToMe	34.05	6.09±0.001	1.24×

الاكتشافات الرئيسية:

حقق CA-ToMe أسرع سرعة استدلال (6.09 ثانية)
درجة FID (34.05) أفضل من ToMe (34.16)، قريبة من الأساس (33.66)
حقق أفضل توازن بين السرعة والجودة

تحليل معامل الحد

معامل الحد t	FID	متوسط الوقت (ثانية)	PSNR	SSIM
0.4	35.28	6.07±0.007	27.90	0.191
0.5	35.46	6.07±0.004	27.909	0.208
0.6	35.56	6.10±0.005	27.908	0.218
0.7	34.30	6.23±0.002	27.910	0.234
0.8	33.80	6.58±0.004	27.904	0.239
0.9	33.42	6.92±0.003	27.907	0.238

الملاحظات:

التغيير في نطاق الحد 0.4-0.6 صغير نسبياً، لأن معظم درجات تشابه الرموز ≥0.6
يوفر الحد 0.7 أفضل توازن بين الجودة والسرعة
تحسن الحدود الأعلى الجودة لكن تقلل السرعة

مقارنة تكوينات التخزين المؤقت

التكوين	إعدادات نقاط التفتيش	الوقت (ثانية)	FID
التكوين 1	0,1,2,3,5,10,15,25,35	6.18±0.02	36.14
التكوين 2	0,10,11,12,15,20,25,30,35,45	6.13±0.001	34.33
التكوين 3	0,8,11,13,20,25,30,35,45,46,47,48,49	6.09±0.001	34.05

يُظهر التكوين 3 أفضل أداء، متسقاً مع تحليل مسافة جاكار، مع تعيين نقاط تفتيش أكثر في الخطوات 8 و 11 و 13 والخطوات النهائية.

تجارب الاستئصال

من خلال مقارنة مساهمة المكونات المختلفة:

الحد التكيفي فقط: تحسين جودة الصورة مقارنة بمعدل الدمج الثابت
آلية التخزين المؤقت فقط: تقليل كبير في وقت الحساب
CA-ToMe الكامل: دمج كلا التقنيتين يحقق أفضل أداء

الأعمال ذات الصلة

طرق تسريع نماذج الانتشار

تقليل خطوات الأخذ العينات:
- طرق التعلم بنقل المعرفة 26,51,28
- الأخذ العينات الضمني 32
- حلالات المعادلات التفاضلية المتقدمة 52,33
- معظمها يتطلب إعادة تدريب
تقليل الحساب في كل خطوة:
- طرق التكمية 31,36
- تقليل الرموز 21,40,41,43,44
- تقنيات التخزين المؤقت 24,37,38,39
- قابلة للتوصيل والتشغيل، بدون إعادة تدريب

تقنيات تقليل الرموز

قص الرموز: حذف الرموز غير المهمة مباشرة، قد يؤدي إلى فقدان المعلومات
دمج الرموز: دمج الرموز المتشابهة، الحفاظ على اكتمال المعلومات
- ToMe 21: استخدام معدل دمج ثابت
- CA-ToMe في هذه الورقة: حد تكيفي + آلية تخزين مؤقت

تقنيات التخزين المؤقت

تستهدف طرق التخزين المؤقت الموجودة مكونات مختلفة:

تخزين الانتباه المتقاطع مؤقتاً 38
تخزين مشفر U-Net مؤقتاً 39
تخزين الميزات المتقدمة مؤقتاً 24

تطبق هذه الورقة لأول مرة التخزين المؤقت على حساب التشابه في دمج الرموز.

الاستنتاجات والنقاش

الاستنتاجات الرئيسية

الحد التكيفي يحل بفعالية قيود معدل الدمج الثابت، وتعديل استراتيجية الدمج ديناميكياً وفقاً لتوزيع التشابه
آلية التخزين المؤقت تستفيد من الزيادة بين الخطوات الزمنية، مما يقلل بشكل كبير من الحسابات المتكررة
طريقة CA-ToMe تحقق تسريعاً بمعامل 1.24 مرة مع الحفاظ على جودة الصورة أو تحسينها قليلاً
الخاصية الخالية من التدريب تجعل الطريقة ذات فائدة عملية وقابلية توسع جيدة

القيود

ضبط معامل الحد: يتطلب تعديل الحد الأمثل لنماذج ومهام مختلفة
نطاق التطبيق المحدود: يستهدف بشكل أساسي نماذج الانتشار بمعمارية U-Net
تكلفة التخزين المؤقت: يتطلب ذاكرة إضافية لتخزين معلومات أزواج الرموز المخزنة مؤقتاً
قيود الطبقة: التطبيق فقط على الطبقات العليا، قد يفوت فرص التحسين في الطبقات الأخرى

الاتجاهات المستقبلية

تعلم الحد التلقائي: تطوير طرق لتحديد الحد الأمثل تلقائياً
التوسع إلى معماريات أخرى: التكيف مع معماريات نماذج انتشار جديدة مثل DiT
استراتيجيات تخزين مؤقت أكثر دقة: آليات تخزين مؤقت تكيفية بناءً على المحتوى
تحسينات الأجهزة: تحسينات التنفيذ الموجهة للأجهزة المحددة

التقييم المتعمق

المزايا

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

أوجه القصور

تحليل نظري غير كافٍ: نقص التوجيه النظري لاختيار الحد التكيفي
نطاق التجارب محدود: التحقق فقط على ImageNet، نقص التقييم على مجموعات بيانات ومهام أخرى
طرق مقارنة قليلة: المقارنة الأساسية مع ToMe، نقص المقارنة مع طرق تسريع أخرى
تقييم جودة أحادي: الاعتماد الأساسي على مقياس FID، نقص التقييم البشري والمقاييس الأخرى

التأثير

المساهمة الأكاديمية: توفير أفكار وطرق جديدة لتسريع نماذج الانتشار
القيمة العملية: يمكن تطبيقها مباشرة على نماذج الانتشار الموجودة، مع آفاق تطبيق واسعة
قابلية التكرار: توفير تنفيذ كود كامل، مما يسهل التكرار والتوسع
الإلهام: يمكن لأفكار التكيف والتخزين المؤقت أن تلهم المزيد من الأبحاث ذات الصلة

السيناريوهات المطبقة

البيئات محدودة الموارد: أجهزة محمولة وحوسبة الحافة وغيرها
التطبيقات في الوقت الفعلي: تطبيقات تفاعلية تتطلب توليد صور سريع
النشر على نطاق واسع: تقليل تكاليف الحساب والتأخير على الخادم
نماذج البحث الأولية: توفير مكونات أساسية لتقنيات تسريع أخرى

المراجع

تستشهد هذه الورقة بـ 54 مرجعاً ذا صلة، تشمل بشكل أساسي:

النظرية الأساسية لنماذج الانتشار 1,2,3
تطبيقات توليد الصور 4,5,18,19,20
تقنيات التسريع 24,25,26,27,28
طرق معالجة الرموز 21,40,41,43,44
تقنيات التخزين المؤقت 24,37,38,39

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