برگشتیم به کلاس خودمان
#طراحی_الگوریتم پیشرفته 🤓
♻️پیچیدگی زمانی KV Cache یکی از دلایل اصلی استفاده گسترده از آن در LLMها است.

●فرض کنید طول دنباله فعلی برابر با n توکن باشد.

حالت الف) بدون KV Cache

برای تولید توکن شماره n+1
مدل باید برای تمام n توکن قبلی:

Query

Key

Value


را دوباره محاسبه کند.

سپس Attention را روی همه آنها اجرا کند.

هزینه تولید یک توکن جدید تقریباً:
O(n^2)


است، زیرا ماتریس Attention ابعاد ِ n×n دارد.

اگر بخواهیم کل دنباله n توکنی را به صورت اتورگرسیو (autoregressive) تولید کنیم:

O(1)+O(2^2)+O(3^2)+...+O(n^2)


یعنی در مجموع:
O(n^3)
حالت ب )با KV Cache
کلید/مقدار ها ی توکن های قبلی ذخیره شده اند

برای توکن جدید فقط:
۱_کوئری جدید محاسبه می‌شود
۲_ کلید/مقدار جدید ساخته می‌شود
۳_ و کلید های ذخیره شده با تمام کوئری های جدید مقایسه می شوند
برای تولید یک #توکن جدید (n)O عملیات Attention لازم است.

چرا؟

زیرا Query جدید باید با (n)Key قبلی ضرب شود:


Qnew.K^T
که طول آن n است.

هزینه کل تولید متن

اگر بخواهیم n توکن تولید کنیم:
O(1)+O(2)+O(3)+...+O(n)

که برابر است با:
O(n^2)
مقایسه

💶 هزینه هر توکن جدید/ هزینه تولید n توکن

بدون KV Cach \(O(n^2)\ \(O(n^3)\)

با KV Cache \(O(n)\) \(O(n^2)\)

پیچیدگی حافظه

KV Cache
رایگان نیست و هزینه دارد!

برای هر توکن باید Key و Value ذخیره شود.

اگر طول کانتکست \(n\) باشد:


Memory = O(n)


(در عمل ضربدر تعداد لایه‌ها، هدرها و ابعاد مدل)

بنابراین:
●معیار بدون Cache با Cache
زمان بیشتر/ کمتر
حافظه کمتر /بیشتر
و همیشه در این میان باید یک مصالحه را پذیرفت ! بسیار شبیه زندگی است این Trade off ،بده‌بستان است هندی ها می‌گویند :
اییک_ دوجِه کِه لی‌ی‌ِه یعنی :" یکی،فدای دیگری"
شما زمان را می‌خواهید یا حافظه را؟

🧐یک مثال شهودی سرِ کلاسی
فرض کنید 10,000 توکن قبلاً تولید شده‌اند.

❌بدون KV Cache
برای توکن بعدی:
10,000 توکن دوباره از همه لایه‌ها عبور می‌کنند.
♻️با KV Cache
برای توکن بعدی:
فقط یک توکن جدید از لایه‌ها عبور می‌کند.
اما باید با 10,000 Key ذخیره‌شده Attention بگیرد.
به همین دلیل هزینه از:
O(n^2)
به O(n) برای هر گام کاهش می‌یابد.

این کاهش مرتبه پیچیدگی، یکی از مهم‌ترین عواملی است که باعث شده مدل‌هایی مانند GPT، Claude، Gemini و Llama بتوانند متن را به‌صورت بلادرنگ (real-time) تولید کنند.

بقول شاعر : من از آنروز که بیگ‌اُیِ تو‌ ام آزادم...

♻️تذکره‌تن:
منبر ام تمام...والسلام علیکم وَ لگد شیطان رجیم تا زانو در حلق خوک کله‌زرد احمقی که گفته ایرانی‌ها در تأسیسات هسته ای شان همزمان ! مواد مخدر هم پرورش می‌داده‌اند!😅 و توضیح نداد با کشوری به این وسعت که اگر بین دو تپه ماهورش هزاران هکتار خشخاش بکارید با پهپاد هم نمی توان انرا پیدا کرد چرا باید کسی مواد مخدر و ترياک را ببرد در سایت هسته‌ای پرورش بدهد😇
💩 قطعا عقل و شعور این مرتیکه ی خراب، زائل شده قطعا و دنیا تا دو سال و عَن‌دی دیگر باید این پی‌پی گنده ی ۱۶۰ کیلویی متعفن را تحمل کند
#LLMs
#ترم_جدید ۴۰۵_۴۰۶ مبارک
#Algorithms
@toobabigdatascience