سؤال مصاحبه

محاسبه‌ی حجم محاسبات اتنشن برای 100 توکن تولیدشده

Count the attention work for 100 generated tokens

  • سطح ۱: غربالگری
  • تخمین
  • ۶ دقیقه

یک دیکودر (decoder) با شروع از یک پرامپت خالی، 100 توکن را یکی پس از دیگری تولید می‌کند. تعداد وضعیت‌های توکنی را که هر حلقه برای پیشوند محاسبه می‌کند به دست آورید: یک حلقه‌ی ساده و یک حلقه که بردارهای کلید (key) و مقدار (value) توکن‌های قبلی را ذخیره (کش) می‌کند. سپس تعداد مقایسه‌های پرس‌وجو-کلید (query-key comparisons) باقی‌مانده در حالت استفاده از کش را بشمارید و مشخص کنید چه چیزی عمداً در کش ذخیره نمی‌شود.

اول خودتان جواب بدهید، بعد پاسخ را باز کنید.

پاسخ کوتاه

حلقه‌ی ساده در هر مرحله تمام توکن‌های پیشوند را دوباره از لایه عبور می‌دهد؛ بنابراین مجموع 1 به‌علاوه‌ی 2 به‌علاوه‌ی 3 تا 100 وضعیت توکن را محاسبه می‌کند که برابر با 5050 است و با مجذور طول توالی رشد می‌کند. با ذخیره‌ی کلیدها و مقادیر، در هر مرحله فقط وضعیت همان توکن جدید محاسبه می‌شود که در کل 100 وضعیت است. پرس‌وجوی جدید همچنان با تمام کلیدهای ذخیره‌شده مقایسه می‌شود، بنابراین حلقه‌ی مجهز به کش هم همان 5050 مقایسه‌ی پرس‌وجو-کلید را انجام می‌دهد: کش فقط محاسبه‌ی دوباره‌ی بردارهای کلید و مقدار را حذف می‌کند، نه مقایسه‌ها را. کش هیچ پرس‌وجویی را نگه نمی‌دارد؛ چون یک توکن گذشته دیگر هرگز سؤالی نمی‌پرسد و فقط تازه‌ترین توکن سؤال می‌پرسد.

پاسخ کامل

چرا می‌توان از پیشوند دوباره استفاده کرد؟

هر وضعیت پنهان (hidden state) یک توکن پیشوند، پس از محاسبه قطعی (deterministic) است و ماسک علّی (causal mask) تضمین می‌کند که هرگز به توکن‌های بعدی وابسته نباشد. بنابراین، کلید و مقدار توکن t در مرحله‌ی 1 + t دقیقاً همان مقادیری هستند که در مرحله‌ی t بودند. محاسبه‌ی مجدد آن‌ها هدر دادنِ محضِ منابع است.

دو حلقه

naive:   step t recomputes t token states       -> 1 + 2 + ... + N = N (N + 1) / 2
cached:  step t computes one new token state    -> N
cached:  its one query meets t stored keys      -> N (N + 1) / 2 comparisons

به ازای N برابر با 100، شمارش در حالت ساده 5050 وضعیت توکن و در حالت مجهز به کش 100 وضعیت است. کد این درس یک مثال 10 توکنی را اجرا می‌کند و در عوض، مقایسه‌های پرس‌وجو-کلید را می‌شمارد: خروجی شمارش برای هر دو حلقه یکسان است و تأیید می‌کند که خروجی‌ها با هم تطابق دارند. در 100 توکن، این مقایسه‌ها در هر دو حلقه مجموعاً به 5050 می‌رسد؛ پس خود مرحله‌ی اتنشن همچنان در هر مرحله با طول توالی رشد می‌کند. برای پاسخی با طول چند هزار توکن، تعداد وضعیت‌های توکن در روش ساده به چندین میلیون می‌رسد که بیشترشان تکراری‌اند.

چه چیزهایی ذخیره می‌شوند؟

به ازای هر لایه و هر هد (head)، دو لیستِ در حال رشد: کلیدها و مقادیر همه‌ی توکن‌هایی که تا این لحظه آمده‌اند.

class KVCache:
    def append(self, layer, head, k, v):
        self.K[layer][head].append(k)
        self.V[layer][head].append(v)

حافظه‌ی مصرفی به‌صورت خطی با طول متن تولیدشده رشد می‌کند؛ این بهایی است که برای محاسبه نکردنِ مجدد پیشوند می‌پردازید.

چرا پرس‌وجوها ذخیره نمی‌شوند؟

پرس‌وجوی هر توکن فقط یک بار استفاده می‌شود: در همان مرحله‌ای که آن توکن، تازه‌ترین توکن است. پس از آن، دیگران همیشه به دنبال این توکن می‌گردند و خودش دیگر هرگز جستجوگر نیست. ذخیره‌سازی پرس‌وجوها فقط حافظه هدر می‌دهد و هیچ سودی ندارد.

چه چیزی از بین نمی‌رود؟

فرایند تولید توکن همچنان ترتیبی (سریال) است: مرحله‌ی t به توکنِ مرحله‌ی 1 - t نیاز دارد. این درس به این مسئله مالیات خودبازگشتی (Autoregressive Tax) می‌گوید. فرایند آموزش با پردازش هم‌زمان کل توالی در یک مرحله‌ی ماسک‌شده از آن فرار می‌کند؛ اما فرایند استنتاج نمی‌تواند.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 1: هم‌زمان با ادامه‌ی فرایند تولید، چه چیزی در حافظه رشد می‌کند؟ پاسخ مورد انتظار: کلیدها و مقادیر ذخیره‌شده، به ازای هر لایه و هر هد؛ یک ورودی به ازای هر توکنِ تولیدشده.
  • سطح 2: چرا کلید یک توکن پیشوند بعد از رسیدن توکن‌های جدید همچنان معتبر است؟ پاسخ مورد انتظار: ماسک علّی یعنی وضعیت پنهان آن فقط به توکن‌های قبلی وابسته بوده است؛ بنابراین توکن‌های بعدی نمی‌توانند تغییری در آن ایجاد کنند.
  • سطح 2: یک کلمه را در وسط پرامپت ویرایش می‌کنید. چه بر سر کش می‌آید؟ پاسخ مورد انتظار: همه‌چیز از آن موقعیت به بعد نامعتبر می‌شود و باید از نو محاسبه شود؛ بخش قبل از آن معتبر باقی می‌ماند.
  • سطح 3: چه زمانی گلوگاه اتنشن به جای محاسبات، وابسته به ترافیک جابه‌جایی حافظه می‌شود؟ پاسخ مورد انتظار: وقتی ماتریس امتیاز N در N آن‌قدر بزرگ شود که جابه‌جایی آن در حافظه بخش غالب کار باشد؛ این درس این نقطه را حدود 2K توکن و فراتر از آن در نظر می‌گیرد.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «کش، وزن‌های اتنشن را نگه می‌دارد.» کش کلیدها و مقادیر را ذخیره می‌کند؛ وزن‌ها در هر مرحله از روی پرس‌وجوی جدید دوباره محاسبه می‌شوند.
  • «کش باعث صرفه‌جویی در حافظه می‌شود.» حافظه مصرف می‌کند و در محاسبات صرفه‌جویی می‌آورد؛ این تبادلِ حافظه در ازای محاسبه نکردن مجدد بردارهای کلید و مقدار است.
  • «پرس‌وجوها هم باید ذخیره شوند.» پرس‌وجوی یک توکنِ گذشته دیگر هرگز استفاده نمی‌شود.

کجای دوره آموزش داده می‌شود

درس کش کلید-مقدار (KV cache) هر دو حلقه را می‌شمارد و درس مدل‌سازی علّی زبان (causal language modeling) توضیح می‌دهد که چرا فرایند تولید ترتیبی است.