ফ্ল্যাশ ইনফারেন্স: দীর্ঘ কনভোলিউশন সিকোয়েন্স মডেলের জন্য নিকট-রৈখিক সময় অনুমান এবং তার বাইরে

মৌলিক তথ্য

• পেপার আইডি: 2410.12982
• শিরোনাম: Flash Inference: Near Linear Time Inference for Long Convolution Sequence Models and Beyond
• লেখক: Costin-Andrei Oncescu, Sanket Purandare, Stratos Idreos, Sham Kakade (হার্ভার্ড বিশ্ববিদ্যালয়)
• শ্রেণীবিভাগ: cs.LG, cs.AI
• প্রকাশনার সময়: arXiv প্রিপ্রিন্ট, ২০২৪ সালের অক্টোবরে জমা দেওয়া, ২০২৫ সালের নভেম্বরে আপডেট (v2)
• পেপার লিংক: https://arxiv.org/abs/2410.12982

সারসংক্ষেপ

এই পেপারটি দীর্ঘ কনভোলিউশন সিকোয়েন্স মডেল (LCSMs) এর অনুমান পর্যায়ে দ্বিঘাত সময় জটিলতার সমস্যার সমাধানের জন্য ফ্ল্যাশ ইনফারেন্স ফ্রেমওয়ার্ক প্রস্তাব করে, যা নির্ভুল অনুমানের সময় জটিলতা $O(L\log^2L)$ এ হ্রাস করে। এই পদ্ধতিটি শিথিল বহুপদী ইন্টারপোলেশন (relaxed polynomial interpolation) দ্বারা অনুপ্রাণিত, যা টাইলিং কৌশলের উপর ভিত্তি করে মেমরি আন্দোলন হ্রাস করে এবং গণনা ভাগ করে। হায়েনা আর্কিটেকচারে পরীক্ষা-নিরীক্ষা দেখায় যে শেষ থেকে শেষ অনুমান ৭.৮ গুণ ত্বরান্বিত হয়েছে, এবং অবস্থান মিশ্রণ অংশ ১১০ গুণ ত্বরান্বিত হয়েছে।

গবেষণা পটভূমি এবং প্রেরণা

১. মূল সমস্যা

যদিও ট্রান্সফর্মার সিকোয়েন্স জেনারেশন মডেলে বিশাল সাফল্য অর্জন করেছে, তবে এর গণনামূলক খরচ সিকোয়েন্স দৈর্ঘ্যে দ্বিঘাতভাবে বৃদ্ধি পায় ($O(L^2)$), যা প্রশিক্ষণ এবং অনুমান উভয় পর্যায়ে বাধা সৃষ্টি করে। এই সমস্যা সমাধানের জন্য, গবেষকরা অনেক সাব-কোয়াড্রেটিক আর্কিটেকচার প্রস্তাব করেছেন, যার মধ্যে রয়েছে স্টেট স্পেস মডেল (SSMs) এবং দীর্ঘ কনভোলিউশন সিকোয়েন্স মডেল (LCSMs, যেমন হায়েনা)।

২. সমস্যার গুরুত্ব

• প্রশিক্ষণ দক্ষতা সমাধান হয়েছে: LCSMs FFT এর মাধ্যমে প্রশিক্ষণ সময়ে $O(L\log L)$ জটিলতা অর্জন করতে পারে
• অনুমান দক্ষতা সমাধান হয়নি: স্বয়ংক্রিয় অনুমানে, ইনপুট সিকোয়েন্স ধাপে ধাপে তৈরি হওয়ায়, FFT সরাসরি ব্যবহার করা যায় না, যার ফলে জটিলতা $O(L^2)$ এ হ্রাস পায়
• দীর্ঘ প্রসঙ্গ চাহিদা: বড় ভাষা মডেলগুলি ক্রমবর্ধমান দীর্ঘ প্রসঙ্গ প্রক্রিয়া করার সাথে সাথে, অনুমান দক্ষতা সমস্যা আরও বেশি বিশিষ্ট হয়ে ওঠে

৩. বিদ্যমান পদ্ধতির সীমাবদ্ধতা

• আনুমানিক পদ্ধতি (Massaroli et al. 2024): কনভোলিউশন ফিল্টারকে নিম্ন-মাত্রিক LTI SSM এ প্রজেক্ট করে, কিন্তু এটি শুধুমাত্র একটি আনুমানিক, এবং ব্যয়বহুল ডিস্টিলেশন প্রি-কম্পিউটেশন প্রয়োজন, ডেটা-নির্ভর ফিল্টার সমর্থন করে না
• পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গি: নিম্ন-মাত্রিক SSM এর জন্য দক্ষ হতে পারে, কিন্তু উচ্চ-মাত্রিক SSM (মাত্রা সিকোয়েন্স দৈর্ঘ্যের কাছাকাছি) এর জন্য এখনও অদক্ষ
• কাঠামো ব্যবহার পদ্ধতি: ফিল্টারকে নির্দিষ্ট কাঠামো থাকতে হবে (যেমন নিম্ন-র‍্যাঙ্ক LTI SSM), যা মডেল প্রকাশক্ষমতা সীমিত করে

৪. গবেষণা প্রেরণা

এই পেপারটির লক্ষ্য একটি নির্ভুল এবং সর্বজনীন অনুমান ত্বরণ ফ্রেমওয়ার্ক প্রদান করা, যা ফিল্টারের নির্দিষ্ট কাঠামোর উপর নির্ভর করে না, একই সাথে ডেটা-নির্ভর ফিল্টার সমর্থন করে।

মূল অবদান

১. প্রথম প্রায়-রৈখিক নির্ভুল অনুমান অ্যালগরিদম: LCSMs এর জন্য $O(L\log^2 L)$ সময় জটিলতার নির্ভুল অনুমান অ্যালগরিদম প্রস্তাব করে, যা আগের আনুমানিক পদ্ধতির তুলনায় নির্ভুল সিমুলেশন অর্জন করে

२. সর্বজনীন ফ্রেমওয়ার্ক সনাক্তকরণ: দ্রুত অনুমান সম্ভব করার মূল আর্কিটেকচার বৈশিষ্ট্য (অবদান ভিত্তি, প্রশ্ন-স্বাধীন) সনাক্ত করে, বিস্তৃত আর্কিটেকচার শ্রেণীর জন্য প্রযোজ্য ফ্ল্যাশ ইনফারেন্স ফ্রেমওয়ার্ক প্রস্তাব করে

३. ক্রস-লেয়ার সমান্তরালকরণ: টাইলিং কৌশল ব্যবহার করে অবস্থান মিশ্রণ অংশের প্রায় সম্পূর্ণ ক্রস-লেয়ার সমান্তরাল গণনা অর্জন করে

४. মেমরি অপ্টিমাইজেশন: টাইলিং পদ্ধতির মাধ্যমে ডেটা আন্দোলন উল্লেখযোগ্যভাবে হ্রাস করে, $\Omega(L^2)$ থেকে $O(L\log L)$ এ, ডেটা-স্বাধীন ফিল্টারের জন্য ২ গুণ সক্রিয়করণ সঞ্চয় সাশ্রয় করে

५. অভিজ্ঞতামূলক যাচাইকরণ: হায়েনা আর্কিটেকচারে শেষ থেকে শেষ ৭.৮ গুণ ত্বরণ, কনভোলিউশন অংশ ১১০ গুণ ত্বরণ অর্জন করে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

স্বয়ংক্রিয় সিকোয়েন্স জেনারেশন: প্রম্পট সিকোয়েন্স $x_1, \ldots, x_p$ দেওয়া, মডেলকে পরবর্তী টোকেন ধাপে ধাপে তৈরি করতে হবে। প্রতিটি অবস্থান $i$ এ, মডেল সমস্ত স্তরের মাধ্যমে সক্রিয়করণ $a^{[1,M]}_i$ গণনা করে, অবশেষে $a^M_i$ থেকে $x_{i+1}$ নমুনা করে।

মূল গণনা বাধা: প্রতিটি স্তর $\ell$ এবং প্রতিটি মাত্রার জন্য, গণনা করতে হবে: $z_t = \sum_{i=1}^{t} y_i \cdot \rho_{t-i}$

যেখানে $y$ ইনপুট সিকোয়েন্স, $\rho$ দৈর্ঘ্য $L$ এর কনভোলিউশন ফিল্টার। নিষ্পাপ বাস্তবায়ন $\Omega(L^2)$ সময় প্রয়োজন।

মডেল আর্কিটেকচার

১. সর্বজনীন আর্কিটেকচার সংজ্ঞা

মডেল $M$ স্তর নিয়ে গঠিত, প্রতিটি স্তরে রয়েছে:

• অবস্থান মিশ্রণ মডিউল (mixer): $\text{mixer}^\ell: \mathbb{R}^{L\times D} \to \mathbb{R}^{L\times D}$, বিভিন্ন অবস্থানের এমবেডিং ইন্টারঅ্যাক্ট করায়
• বৈশিষ্ট্য মিশ্রণ মডিউল (block): $\text{block}^\ell: \mathbb{R}^D \to \mathbb{R}^D$, MLP, স্তর স্বাভাবিকীকরণ ইত্যাদি অন্তর্ভুক্ত করে

সক্রিয়করণ গণনা: $a^\ell(x)_i = \text{block}^\ell(\text{mixer}^\ell(a^{\ell-1}(x))_i)$

२. LCSM নির্দিষ্ট সংজ্ঞা

LCSMs এর জন্য, mixer কনভোলিউশনের মাধ্যমে বাস্তবায়িত হয়: $\text{mixer}^\ell(y)_t = \sum_{i=1}^{t} y_i \odot \rho^\ell_{t-i}$

যেখানে $\odot$ হ্যাডামার্ড পণ্য, $\rho^\ell \in \mathbb{R}^{L\times D}$ ফিল্টার (সাধারণত নিম্ন-মাত্রিক প্যারামিটার $\theta$ দ্বারা উৎপন্ন: $\rho = f(\theta)$)।

মূল অ্যালগরিদম: শিথিল বহুপদী ইন্টারপোলেশন

१. তিনটি গণনা কৌশল

Lazy (অলস) পদ্ধতি:

• শুধুমাত্র প্রয়োজনে $z_t = \sum_{i=1}^{t} y_i \cdot \rho_{t-i}$ গণনা করে
• প্রতিটি অবস্থানে $O(t)$ অপারেশন প্রয়োজন, মোট জটিলতা $O(L^2)$

Eager (আগ্রহী) পদ্ধতি:

• যখন $y_t$ উপলব্ধ, অবিলম্বে সমস্ত ভবিষ্যত অবস্থানে এর অবদান গণনা করে
• $t$ তম পুনরাবৃত্তিতে $O(L-t)$ অপারেশন প্রয়োজন, মোট জটিলতা এখনও $O(L^2)$

Relaxed (শিথিল) পদ্ধতি (এই পেপার দ্বারা প্রস্তাবিত):

• অবদান স্থান টাইলে বিভক্ত করে, FFT ব্যবহার করে টাইল অবদান দক্ষতার সাথে গণনা করে
• মূল উদ্ভাবন: সুষম আয়তক্ষেত্রাকার টাইলিং পরিবর্তে সরু স্ট্রিপ

२. অবদান সমষ্টি সংজ্ঞা

$\tau(y, [l,r], \rho, [l',r'])$ কে $y_{[l,r]}$ এর $z_{[l',r']}$ এ সমষ্টিগত অবদান হিসাবে সংজ্ঞায়িত করুন: $\tau(y, [l,r], \rho, [l',r'])_t = \sum_{i=l}^{r} y_i \cdot \rho_{t-i}, \quad \forall l' \leq t \leq r'$

Lemma 1: FFT এর উপর ভিত্তি করে একটি অ্যালগরিদম বিদ্যমান, যা $O((L_1+L_2)\log(L_1+L_2))$ সময়ে $\tau$ গণনা করে, যেখানে $L_1 = r-l+1$, $L_2 = r'-l'+1$।

३. টাইলিং কৌশল (অ্যালগরিদম ১)

for i = 1 to L-1:
    U ← সর্ববৃহৎ ২ এর শক্তি যা i কে বিভক্ত করে
    z_i += y_i * ρ_0  # লাল ঘর: সরাসরি নির্ভরতা
    z[i+1:i+U] += τ(y, [i-U+1, i], ρ, [i+1, i+U])  # ধূসর ব্লক: আগ্রহী গণনা
    return z_i
    unlock y_{i+1}

মূল বৈশিষ্ট্য:

• $i$ তম পুনরাবৃত্তিতে, প্রান্ত দৈর্ঘ্য $U$ এর ধূসর ব্লক গণনা করে ($U$ হল $i$ কে বিভক্ত করার সর্ববৃহৎ ২ এর শক্তি)
• লাল ঘর বর্তমান অবস্থানের সরাসরি নির্ভরতা পরিচালনা করে
• ধূসর ব্লক আগাম অংশ ভবিষ্যত অবদান গণনা করে

জটিলতা বিশ্লেষণ (Proposition 1):

• দৈর্ঘ্য $2^q$ এর ব্লকের জন্য, $2^{P-1-q}$ বার আহ্বান ($L=2^P$)
• মোট সময়: $\sum_{q=0}^{P-1} 2^{P-1-q} \cdot O(2^q \log 2^q) = O(L\log^2 L)$
• মেমরি: $O(L)$ (শিখর সর্ববৃহৎ ব্লক দ্বারা নির্ধারিত)

LCSM অনুমান অ্যালগরিদম (অ্যালগরিদম २)

অ্যালগরিদম १ কে বহু-স্তর বহু-মাত্রায় প্রসারিত করুন:

for i = 1 to L-1:
    U ← সর্ববৃহৎ २ এর শক্তি যা i কে বিভক্ত করে
    for ℓ = 1 to M:  # স্তর জুড়ে
        b^ℓ_i += a^{ℓ-1}_i ⊙ ρ^ℓ_0  # লাল ঘর
        a^ℓ_i = block^ℓ(b^ℓ_i)
        b^ℓ[i+1:i+U] += τ(a^{ℓ-1}, [i-U+1, i], ρ^ℓ, [i+1, i+U])  # ধূসর ব্লক
    a^0_{i+1} = sampler(a^M_i)

জটিলতা (Proposition २):

• Mixer অংশ: $O(MDL\log^2 L)$
• Block অংশ: $LM$ বার আহ্বান (সাধারণত $O(MLD^2)$)
• সক্রিয়করণ সঞ্চয়: $O(MLD)$

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. ক্রস-লেয়ার সমান্তরালকরণ (অ্যালগরিদম ३)

ধূসর ব্লক গণনা সমস্ত স্তর জুড়ে সমান্তরাল করা যায়:

for i = 1 to L-1:
    for ℓ = 1 to M:
        লাল ঘর প্রক্রিয়া করুন (অবশ্যই ক্রমিক)
    parallel for ℓ = 1 to M:
        ধূসর ব্লক প্রক্রিয়া করুন (সমান্তরাল করা যায়)

সুবিধা:

• ছোট ব্লক (৮७.५% ব্লক আকার ≤४) সাধারণত মেমরি বিলম্ব দ্বারা সীমাবদ্ধ, সমান্তরালকরণ মেমরি ব্যান্ডউইথ সম্পূর্ণ করতে পারে
• বড় ব্লক FFT ব্যবহার করে বাস্তবায়িত, গণনা-নিবিড়, সমান্তরালকরণ থ্রুপুট উন্নত করে

२. মেমরি অপ্টিমাইজেশন

• ডেটা আন্দোলন: $\Omega(L^2)$ থেকে $O(L\log L)$ এ (গড়ে প্রতি পুনরাবৃত্তি $\log L$ অবস্থান অ্যাক্সেস)
• সক্রিয়করণ পুনর্ব্যবহার: অবস্থান $i$ এ $a^\ell_i$ এর স্থান ব্যবহার করে $b^\ell_i$ সঞ্চয় করুন (পরে $b^\ell_i$ প্রয়োজন নেই)
• FFT প্রি-কম্পিউটেশন: $\log L$ বিভিন্ন ব্লক আকারের জন্য কনভোলিউশন কার্নেলের DFT প্রি-কম্পিউট করুন, ১.५ গুণ গণনা সাশ্রয় করুন

३. সার্কুলার কনভোলিউশন কৌশল

• মান FFT কনভোলিউশন ४U দৈর্ঘ্যের FFT প্রয়োজন (আউটপুট দৈর্ঘ্য ३U-१)
• এই পেপার শুধুমাত্র २U দৈর্ঘ্যের সার্কুলার কনভোলিউশন প্রয়োজন (আগ্রহের পরিসীমা $[U, 2U-1]$ সার্কুলার দ্বারা প্রভাবিত নয়)

४. ডেটা-নির্ভর ফিল্টার সম্প্রসারণ (পরিশিষ্ট B)

টাইলিং কৌশল সংশোধন করে (অ্যালগরিদম ५), $\rho$ ডেটার উপর নির্ভর করে এমন ক্ষেত্রে সমর্থন করে, খরচ २ গুণ গণনা।

সর্বজনীন ফ্রেমওয়ার্ক: ফ্ল্যাশ ইনফারেন্স

আর্কিটেকচার বৈশিষ্ট্য

P.१ অবদান-ভিত্তিক (Contribution-based): Mixer অবদান সমষ্টি কাজের মাধ্যমে: $\text{mixer}(y)_i = \text{read}(\text{agg}(\text{cont}(y,1,i), \ldots, \text{cont}(y,i,i)))$

যেখানে:

• $\text{cont}: \mathbb{R}^D \times \mathbb{N} \times \mathbb{N} \to \mathcal{X}$: অবদান ফাংশন
• $\text{agg}: \mathcal{X}^* \to \mathcal{X}$: সহযোগী সমষ্টি ফাংশন
• $\text{read}: \mathcal{X} \to \mathbb{R}^D$: পড়া ফাংশন

উদাহরণ:

• LCSMs: $\mathcal{X}=\mathbb{R}^D$, $\text{agg}=\sum$, $\text{cont}(y,i,j)=y_i\odot\rho_{j-i}$
• Self-attention: $\mathcal{X}=\mathbb{R}^D\times\mathbb{R}$, $\text{cont}(y,i,j)=(v_i\cdot e^{\langle k_i,q_j\rangle}, e^{\langle k_i,q_j\rangle})$, $\text{read}(v,w)=v/w$

P.२ প্রশ্ন-স্বাধীন (Query-independent): $\text{cont}(y,i,j)$ $y_{[i+1,L]}$ এর উপর নির্ভর করে না (LCSMs সন্তুষ্ট করে, ট্রান্সফর্মার করে না)

সর্বজনীন অ্যালগরিদম (অ্যালগরিদম ४)

ধরুন অ্যালগরিদম $\mathcal{A}$ বিদ্যমান যা $T(L_1, L_2)$ সময়ে ব্লক অবদান গণনা করতে পারে: $\mathcal{A}(y, [l,r], [l',r']) = \text{agg}(\text{cont}(y,l,p), \ldots, \text{cont}(y,r,p))$

Theorem २: P.१ এবং P.२ এর অধীনে, প্রতিটি স্তর সম্পাদন করে:

• $L-१$ বার $\mathcal{A}$ আহ্বান (দৈর্ঘ্য $२^q$ এর $२^{P-१-q}$ বার আহ্বান)
• মোট সময়: $\sum_{q=0}^{P-1} 2^{P-1-q} T(2^q, 2^q)$
• ক্রস-লেয়ার সমান্তরালকরণ: ধূসর ব্লকের কোন ডেটা নির্ভরতা নেই, সমান্তরাল করা যায়

পরীক্ষা সেটআপ

ডেটাসেট এবং কনফিগারেশন

দুটি পরীক্ষা সেটআপ: १. হায়েনা আর্কিটেকচার: প্রকৃত LCSM মডেল २. সিন্থেটিক সেটআপ: সরলীকৃত LCSM (blocks MLP+GELU, sampler শব্দ যোগ করে)

হাইপারপ্যারামিটার স্ক্যান:

• ব্যাচ আকার $B \in \{1,2,4,8\}$
• স্তর সংখ্যা $M \in \{18, 36\}$
• এমবেডিং মাত্রা $D \in \{256, 768, 864\}$
• সিকোয়েন্স দৈর্ঘ্য $L$: মেমরি ধারণ করতে পারে এমন সর্ববৃহৎ २ এর শক্তি ($२^{१५}$ থেকে $२^{१८}$)

হার্ডওয়্যার: NVIDIA H१०० এবং A१०० GPU

ওয়ার্মআপ এবং গড়: २ বার ওয়ার্মআপ, ४ বার চালানো গড় নিন

তুলনা পদ্ধতি

Baseline: १. Lazy: নিষ্পাপ অবস্থান-দ্বারা-অবস্থান গণনা २. Eager: সমস্ত ভবিষ্যত অবদান আগাম গণনা করুন ३. Lazy NP / Eager NP: অ-সমান্তরাল সংস্করণ (ক্রস-লেয়ার সমান্তরালকরণ ব্যবহার করে না)

এই পেপারের $\tau$ বাস্তবায়ন (७ প্রকার, ४ প্রকার Pareto সামনে): १. Conv१D: PyTorch ডিফল্ট १D কনভোলিউশন কার্নেল (স্পষ্ট প্যাডিং প্রয়োজন) २. Flash Conv१D: FlashFFTConv এর ফিউজড কার্নেল ३. FFT: PyTorch নেটিভ FFT কনভোলিউশন (DFT→উপাদান-বুদ্ধিমান গুণ→IDFT) ४. FlashFFT: FlashFFTConv এর ফিউজড FFT কার্নেল ५. Hybrid: ব্লক আকারের উপর ভিত্তি করে গতিশীলভাবে সর্বোত্তম বাস্তবায়ন নির্বাচন করুন

মূল্যায়ন মেট্রিক্স

• শেষ থেকে শেষ সময়: সমস্ত $L$ টোকেন তৈরির মোট সময়
• Mixer সঞ্চিত সময়: শুধুমাত্র অবস্থান মিশ্রণ অংশের সময়
• প্রতি-টোকেন সময়: একক টোকেনের গড় প্রজন্ম সময়
• ত্বরণ অনুপাত: Lazy (সমান্তরাল সংস্করণ) এর তুলনায় গুণ উন্নতি

বাস্তবায়ন বিবরণ

প্রকৌশল অপ্টিমাইজেশন: १. CUDA Graphs: একক টোকেন প্রজন্মের সমস্ত কার্নেল সময়সূচী গ্রাফ হিসাবে রেকর্ড করুন, পরবর্তী পুনরুৎপাদন CPU ওভারহেড হ্রাস করতে (१०-२०% উন্নতি) २. FFT প্রি-কম্পিউটেশন: $\log_2(L)-१$ ব্লক আকারের জন্য কনভোলিউশন কার্নেলের DFT প্রি-কম্পিউট করুন ३. FlashFFT প্রি-কনফিগারেশন: বিভিন্ন ব্লক আকারের জন্য প্রি-ইনিশিয়ালাইজ কনফিগারেশন হার্ডওয়্যার কর্মক্ষমতা সর্বাধিক করতে ४. ডান প্যাডিং: বাম প্যাডিং এর পরিবর্তে ডান প্যাডিং ব্যবহার করুন, অর্ধেক গণনা সময় হ্রাস করুন ५. সার্কুলার কনভোলিউশন: সার্কুলার কনভোলিউশন সম্পত্তি ব্যবহার করে FFT দৈর্ঘ্য অর্ধেক করুন

পরীক্ষা ফলাফল

প্রধান ফলাফল

१. হায়েনা আর্কিটেকচার (টেবিল १, চিত্র २)

Mixer অংশ ত্বরণ (Lazy এর তুলনায়):

• সর্বোচ্চ ११०×: $B=1, M=18, D=864, L=2^{17}$
• গড় ६४-११०×: বিভিন্ন কনফিগারেশনে ধারাবাহিক উল্লেখযোগ্য ত্বরণ
• Eager/Lazy baseline: মাত্র ०.५४× (প্রকৃতপক্ষে আরও ধীর, কারণ অপ্টিমাইজ করা হয়নি)

শেষ থেকে শেষ ত্বরণ (টেবিল २):

• সর্বোচ্চ ७.८×: $B=8, M=18, D=864, L=2^{15}$
• গড় ३-८×: শেষ থেকে শেষ উন্নতি অ-mixer অংশ (MLP ইত্যাদি) দ্বারা সীমাবদ্ধ
• সময় বিয়োজন (চিত্র २a): mixer প্রধান অবস্থান থেকে গৌণ অংশে হ্রাস পায়

প্রতি-টোকেন প্রতিক্রিয়া সময় (চিত্র २c):

• কম বৈচিত্র্য: ९३.७५% টোকেন ব্লক আকার ≤८ ব্যবহার করে, সময় স্থিতিশীল
• অনুপ্রবেশকারী স্পাইক: বড় ব্লক গণনায় প্রদর্শিত (কিন্তু ফ্রিকোয়েন্সি কম)

२. সিন্থেটিক সেটআপ (টেবিল ३-४, চিত্র ३)

Mixer ত্বরণ:

• Hybrid: ८०-१२४×
• একক বাস্তবায়ন: Flash Conv१D (५.५-६.५×), FlashFFT (३१-५६×), FFT (७४-११९×)
• Conv१D (দ্বিঘাত জটিলতা): এখনও ५-६× ত্বরণ (টাইলিং দ্বারা আনা গাণিতিক শক্তি যাচাই করে)

শেষ থেকে শেষ ত্বরণ:

• Hybrid: ३.८-११.६×
• CUDA Graphs প্রভাব: CUDA Graphs ছাড়া শেষ থেকে শেষ মাত্র १.६×, ব্যবহার করার পরে ८× এ পৌঁছায়

Pareto সর্বোত্তম বক্ররেখা (চিত্র ३a):

• বিভিন্ন ব্লক আকারে, বিভিন্ন $\tau$ বাস্তবায়ন সর্বোত্তম
• ছোট ব্লক (U≤४): Flash Conv१D সর্বোত্তম (মেমরি বিলম্ব সীমাবদ্ধ)
• মধ্য ব্লক (४<U≤६४): FlashFFT সর্বোত্তম
• বড় ব্লক (U>६४): FFT সর্বোত্তম (গণনা-নিবিড়)

অ্যাবলেশন পরীক্ষা

१. ক্রস-লেয়ার সমান্তরালকরণ প্রভাব

• Lazy NP vs Lazy: ०.७६-०.९१× (সমান্তরালকরণ १०-३०% উন্নতি)
• Eager NP vs Eager: ०.४९-०.५३× (সমান্তরালকরণ প্রায় २ গুণ উন্নতি)
• এই পেপারের পদ্ধতি: ছোট ব্লক প্রভাবশালী, সমান্তরালকরণ প্রভাব উল্লেখযোগ্য

२. $\tau$ বাস্তবায়ন তুলনা (চিত্র ३b)

• Hybrid সর্বদা সর্বোত্তম বা কাছাকাছি সর্বোত্তম
• FFT বেশিরভাগ ক্ষেত্রে Hybrid এর কাছাকাছি (পার্থক্য <२०%)
• Flash Conv१D যদিও $O(L^2)$, তবুও Lazy/Eager এর চেয়ে ५ গুণ দ্রুত (মেমরি বান্ধব)

३. সময় বিয়োজন (চিত্র ३c, চিত্র ४)

• অ-কনভোলিউশন অংশ: সমস্ত পদ্ধতিতে সামঞ্জস্যপূর্ণ (CUDA Graphs নিশ্চিত করে)
• কনভোলিউশন অংশ: Hybrid সমস্ত baseline এর চেয়ে উল্লেখযোগ্যভাবে ভাল

কেস বিশ্লেষণ

সঞ্চিত mixer সময় বক্ররেখা (চিত্র २b, চিত্র ३b):

• Lazy/Eager: রৈখিক বৃদ্ধি (ঢাল ধ্রুবক)
• এই পেপারের পদ্ধতি: লগারিদমিক বৃদ্ধি (ঢাল হ্রাস পায়)
• ক্রসওভার পয়েন্ট: প্রায় १००-१००० টোকেনে, তারপরে সুবিধা উল্লেখযোগ্য

পরীক্ষা আবিষ্কার

१. তত্ত্ব এবং অনুশীলন সামঞ্জস্যপূর্ণ: $O(L\log^2 L)$ জটিলতা পরীক্ষায় উল্লেখযোগ্য ত্বরণ হিসাবে প্রতিফলিত হয় २. মেমরি ব্যান্ডউইথ গুরুত্ব: Flash Conv१D যদিও দ্বিঘাত জটিলতা, তবুও মেমরি অ্যাক্সেস অপ্টিমাইজেশনের মাধ্যমে ५ গুণ ত্বরণ অর্জন করে ३. গতিশীল নির্বাচন প্রয়োজনীয়: কোন একক $\tau$ বাস্তবায়ন সমস্ত ব্লক আকারে সর্বোত্তম নয়, Hybrid কৌশল গুরুত্বপূর্ণ ४. CPU ওভারহেড উল্লেখযোগ্য: CUDA Graphs শেষ থেকে শেষ ত্বরণ १.६× থেকে ८× এ উন্নীত করে ५. সমান্তরালকরণ সুবিধা: ছোট ব্লক প্রভাবশালী (८७.५%), ক্রস-লেয়ার সমান্তরালকরণ প্রভাব উল্লেখযোগ্য

সম্পর্কিত কাজ

१. ট্রান্সফর্মার বিকল্প আর্কিটেকচার

• SSMs: Mamba (নির্বাচনী SSM), S४ (কাঠামোগত SSM)
• LCSMs: Hyena, H३, CKConv, FlexConv
• অন্যান্য: Mega (চলমান গড় গেটেড মনোযোগ)

२. দ্রুত অনুমান পদ্ধতি

• পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গি: SSM এর পুনরাবৃত্তিমূলক ফর্ম ব্যবহার করে, সময় $O(LD')$ ($D'$ অবস্থা মাত্রা)
• আনুমানিক পদ্ধতি:
  • Massaroli et al. २०२४: নিম্ন-মাত্রিক LTI SSM এ ডিস্টিল করুন (আনুমানিক, ডেটা-নির্ভর সমর্থন করে না)
  • এই পেপার: নির্ভুল, ডেটা-নির্ভর সমর্থন করে
• কাঠামো ব্যবহার:
  • প্রসারিত কনভোলিউশন (Paine et al. २०१६): রৈখিক সময়, নির্দিষ্ট কাঠামো প্রয়োজন
  • এই পেপার: কোন কাঠামো অনুমান নেই

३. সমান্তরাল কাজ

• Agarwal et al. २०२४ (FutureFill): অনুরূপ অ্যালগরিদম, রৈখিক গতিশীল সিস্টেমে ফোকাস
• এই পেপারের সুবিধা: ডেটা-নির্ভর ফিল্টার সমর্থন করে, সিস্টেম-স্তরের অপ্টিমাইজেশন আরও সম্পূর্ণ

४. FFT এবং কনভোলিউশন

• van der Hoeven १९९७: শিথিল বহুপদী ইন্টারপোলেশন তত্ত্ব ভিত্তি
• FlashFFTConv: দক্ষ FFT কনভোলিউশন বাস্তবায়ন

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. তাত্ত্বিক অবদান: LCSMs এর জন্য প্রথম $O(L\log^2 L)$ নির্ভুল অনুমান অ্যালগরিদম २. সর্বজনীন ফ্রেমওয়ার্ক: মূল বৈশিষ্ট্য (অবদান-ভিত্তিক, প্রশ্ন-স্বাধীন) সনাক্ত করে, বিস্তৃত আর্কিটেকচারে প্রযোজ্য ३. অভিজ্ঞতামূলক যাচাইকরণ: হায়েনায় শেষ থেকে শেষ ७.८× ত্বরণ, mixer অংশ ११०× ত্বরণ ४. সিস্টেম অপ্টিমাইজেশন: ক্রস-লেয়ার সমান্তরালকরণ, মেমরি অপ্টিমাইজেশন, গতিশীল বাস্তবায়ন নির্বাচন ইত্যাদি প্রকৌশল অবদান

সীমাবদ্ধতা

१. ডেটা-নির্ভর ফিল্টার: যদিও তাত্ত্বিকভাবে সমর্থিত, তবুও २ গুণ গণনা প্রয়োজন, পরীক্ষা সম্পূর্ণভাবে যাচাই করা হয়নি २. মেমরি প্রয়োজন: এখনও সমস্ত সক্রিয়করণ $O(MLD)$ সঞ্চয় প্রয়োজন (বনাম পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গির $O(MD')$) ३. প্রযোজ্য পরিসীমা:

• ট্রান্সফর্মারে প্রযোজ্য নয় (প্রশ্ন-স্বাধীন সন্তুষ্ট করে না)
• অতি নিম্ন-মাত্রিক SSM ($D' \ll \log^2 L$) এর জন্য, পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গি আরও ভাল হতে পারে ४. প্রম্পট পর্যায়: দীর্ঘ প্রম্পটে, প্রি-ফিলিং (prefill) এখনও সময় প্রভাবশালী, এই পেপারের অপ্টিমাইজেশন স্বয়ংক্রিয় প্রজন্মের আপেক্ষিক সুবিধা সীমিত ५. হার্ডওয়্যার নির্ভরতা: ত্বরণ প্রভাব GPU মেমরি ব্যান্ডউইথ বৈশিষ্ট্যের উপর নির্ভর করে

ভবিষ্যত দিকনির্দেশনা

१. আর্কিটেকচার ডিজাইন: ফ্ল্যাশ ইনফারেন্স প্রয়োজনীয়তা সন্তুষ্ট করে এমন নতুন উচ্চ-মানের আর্কিটেকচার ডিজাইন করুন २. কারণীয় ডেটা-নির্ভর ফিল্টার: কীভাবে ফিল্টার ডেটা-নির্ভর করতে পারে একই সাথে কারণীয়তা বজায় রাখে (Arora et al., Karami & Ghodsi ইতিমধ্যে সম্ভাবনা দেখিয়েছে) ३. হাইব্রিড পদ্ধতি: পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গি (ছোট অবস্থা মাত্রা) এবং কনভোলিউশন দৃষ্টিভঙ্গি (বড় অবস্থা মাত্রা) একত্রিত করুন ४. আরও আর্কিটেকচার: অন্যান্য ফ্রেমওয়ার্ক বৈশিষ্ট্য সন্তুষ্ট করে এমন মডেলে প্রসারিত করুন (যেমন কিছু মনোযোগ ভেরিয়েন্ট) ५. বিতরণকৃত অনুমান: মাল্টি-GPU/মাল্টি-নোড পরিস্থিতিতে অপ্টিমাইজেশন

গভীর মূল্যায়ন

শক্তি

१. তাত্ত্বিক কঠোরতা

• জটিলতা বিশ্লেষণ সম্পূর্ণ: Lemma १ থেকে Theorem २ পর্যন্ত, প্রমাণ শৃঙ্খল স্পষ্ট
• সর্বজনীন ফ্রেমওয়ার্ক বিমূর্তকরণ: P.१ এবং P.२ বৈশিষ্ট্য বিমূর্তকরণ উপযুক্ত, LCSMs অন্তর্ভুক্ত করে এবং অপ্রযোজ্য ক্ষেত্রে বাদ দেয় (যেমন ট্রান্সফর্মার)
• গাণিতিক সরঞ্জাম নির্বাচন: শিথিল বহুপদী ইন্টারপোলেশন তত্ত্ব প্রয়োগ চতুর

२. পদ্ধতি উদ্ভাবনী

• টাইলিং কৌশল: সুষম আয়তক্ষেত্রাকার টাইলিং (বনাম সরু স্ট্রিপ) মূল অন্তর্দৃষ্টি
• ক্রস-লেয়ার সমান্তরালকরণ: ধূসর ব্লক কোন নির্ভরতা নেই সনাক্ত করে, ঐতিহ্যগত স্তর-ক্রমিক সম্পাদন সীমা অতিক্রম করে
• গতিশীল বাস্তবায়ন নির্বাচন: Hybrid কৌশল হার্ডওয়্যার বৈশিষ্ট্যের গভীর বোঝাপড়া প্রতিফলিত করে

३. পরীক্ষা সম্পূর্ণতা

• বহু-মাত্রিক মূল্যায়ন: শেষ থেকে শেষ, mixer, প্রতি-টোকেন সময়
• প্যারামিটার স্ক্যান ব্যাপক: २१ কনফিগারেশন সমন্বয় (B, M, D, L)
• অ্যাবলেশন পরীক্ষা বিস্তৃত: ७ প্রকার $\tau$ বাস্তবায়ন, সমান্তরাল বনাম অ-সমান্তরাল, CUDA Graphs প্রভাব
• দুটি সেটআপ: প্রকৃত Hyena + সিন্থেটিক (অপ্রাসঙ্গিক কারণ বাদ দেয়)

४. প্রকৌশল অবদান

• সিস্টেম-স্তরের অপ্টিমাইজেশন: CUDA Graphs, FFT প্রি-কম্পিউটেশন, সার্কুলার কনভোলিউশন ইত্যাদি ব্যবহারিক কৌশল
• ওপেন-সোর্স সম্ভাবনা: অ্যালগরিদম বর্ণনা বিস্তারিত, পুনরুৎপাদন সহজ
• মেমরি বিশ্লেষণ: পরিশিষ্ট D/E মেমরি ব্যবহারের সূক্ষ্ম আলোচনা

५. লেখার স্পষ্টতা

• ভিজ্যুয়ালাইজেশন চমৎকার: চিত্র १ এর টাইলিং চিত্র স্বজ্ঞাত
• প্রতীক সামঞ্জস্যপূর্ণ: সম্পূর্ণ পাঠ প্রতীক সিস্টেম স্পষ্ট
• পরিশিষ্ট সম্পূর্ণ: সম্প্রসারণ আলোচনা, প্রমাণ, অতিরিক্ত পরীক্ষা সংগঠিত

অপূর্ণতা

१. পরীক্ষা সীমাবদ্ধতা

• কোন প্রকৃত মডেল প্রশিক্ষণ: র‍্যান্ডম ইনিশিয়ালাইজড ওজন ব্যবহার করে, মডেল গুণমানে প্রভাব যাচাই করা হয়নি
• শেষ থেকে শেষ তুলনা অনুপস্থিত: Mamba ইত্যাদি অন্যান্য দক্ষ আর্কিটেকচারের সাথে তুলনা করা হয়নি
• প্রম্পট পর্যায় বিশ্লেষণ অপর্যাপ্ত: দীর্ঘ প্রম্পট পরিস্থিতিতে প্রকৃত সুবিধা সম্পূর্ণভাবে অন্বেষণ করা হয়নি
• ডেটা-নির্ভর ফিল্টার অপরীক্ষিত: অ্যালগরিদম ५ শুধুমাত্র তাত্ত্বিক আলোচনা, কোন পরীক্ষা যাচাইকরণ নেই

२. পদ্ধতি সীমাবদ্ধতা

• মেমরি ওভারহেড: $O(MLD)$ সক্রিয়করণ সঞ্চয় দীর্ঘ সিকোয়েন্স/বহু-স্তরে এখনও বাধা হতে পারে
• শিখর মেমরি: সর্ববৃহৎ ব্লক অতিরিক্ত $O(LD)$ স্থান প্রয়োজন (যদিও ক্রমিক প্রক্রিয়াকরণের মাধ্যমে হ্রাস করা যায়)
• প্রযোজ্যতা সীমিত:
  • ট্রান্সফর্মারে প্রযোজ্য নয় (প্রধান আর্কিটেকচার)
  • LCSMs নিজেই ট্রান্সফর্মারের মতো গুণমান নাও হতে পারে
  • আর্কিটেকচার নির্দিষ্ট বৈশিষ্ট্য সন্তুষ্ট করতে হবে

३. তাত্ত্বিক বিশ্লেষণ

• ধ্রুবক কারণ: $O(L\log^2 L)$ এ ধ্রুবক বড় হতে পারে (পরীক্ষা দেখায় ছোট ব্লকে FFT সর্বোত্তম নয়)
• সর্বোত্তমতা: $\log^2 L$ নিম্ন সীমা কিনা প্রমাণিত নয়
• মেমরি জটিলতা ট্রেড-অফ: সময়-মেমরি Pareto সীমানার গভীর বিশ্লেষণ অনুপস্থিত

४. তুলনা অপর্যাপ্ত

• আনুমানিক পদ্ধতির সাথে: Massaroli et al. এর গুণমান-গতি ট্রেড-অফ পরীক্ষা তুলনা অনুপস্থিত
• পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গির সাথে: কখন পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গি আরও ভাল তার পরিমাণগত বিশ্লেষণ অপর্যাপ্ত (শুধুমাত্র গুণগত আলোচনা $D' \in O(\log^2 L)$)
• কাঠামো ব্যবহার পদ্ধতির সাথে: প্রসারিত কনভোলিউশন ইত্যাদি নির্দিষ্ট কাঠামো পদ্ধতির সাথে তুলনা অনুপস্থিত

প্রভাব

१. একাডেমিক অবদান

• যুগান্তকারী: LCSMs এর জন্য প্রথম প্রায়-রৈখিক নির্ভুল অনুমান
• তাত্ত্বিক গভীরতা: শিথিল বহুপদী ইন্টারপোলেশন এবং সিকোয়েন্স মডেল অনুমান সংযোগ
• ফ্রেমওয়ার্ক মূল্য: সর্বজনীন বৈশিষ্ট্য সনাক্তকরণ ভবিষ্যত আর্কিটেকচার ডিজাইন নির্দেশনা দিতে পারে

२. ব্যবহারিক মূল্য

• অবিলম্বে প্রয়োগযোগ্য: Hyena ইত্যাদি বিদ্যমান মডেল সরাসরি প্রয়োগ করতে পারে
• প্রকৌশল অনুপ্রেরণা: সিস্টেম অপ্টিমাইজেশন কৌশল (CUDA Graphs ইত্যাদি) স্থানান্তরযোগ্য
• সীমাবদ্ধতা: LCSMs বাস্তব প্রয়োগে ট্রান্সফর্মারের মতো জনপ্রিয় নয়, সরাসরি প্রভাব সীমিত করে

३. পুনরুৎপাদনযোগ্যতা

• অ্যালগরিদম স্পষ্ট: সিউডোকোড বিস্তারিত, বাস্তবায়ন সহজ
• পরীক্ষা বিবরণ: হাইপারপ্যারামিটার, হার্ডওয়্যার কনফিগারেশন স্পষ্ট
• ওপেন-সোর্স সম্ভাবনা: কোড প্রকাশ উল্লেখ করা হয়নি, তবে বর্ণনা পুনরুৎপাদনের জন্য যথেষ্ট
• হার্ডওয়্যার নির্ভরতা: সমস্ত ফলাফল যাচাই করতে উচ্চ-শেষ GPU (H१००/A१००) প্রয়োজন

প্রযোজ্য পরিস্থিতি

१. আদর্শ পরিস্থিতি

• দীর্ঘ সিকোয়েন্স প্রজন্ম: $L > १०^४$, জটিলতা সুবিধা স্পষ্ট
• স্বয়ংক্রিয় প্রজন্ম প্রভাবশালী: উৎপন্ন টোকেন সংখ্যা প্রম্পট দৈর্ঘ্যের চেয়ে অনেক বেশি
• LCSM আর্কিটেকচার: প্রশিক্ষিত Hyena ইত্যাদি মডেল
• উচ্চ-শেষ হার্ডওয়্যার: GPU মেমরি ব্যান্ডউইথ উচ্চ, সমান্তরালকরণ সমর্থন করে

२. অপ্রযোজ্য পরিস্থিতি

• ছোট সিকোয়েন্স: $L < १०००$, ধ্রুবক ওভারহেড সুবিধা অফসেট করতে পারে
• দীর্ঘ প্রম্পট ছোট প্রজন্ম: প্রি-ফিলিং প্রভাবশালী, স্বয়ংক্রিয় অপ্টিমাইজেশন সুবিধা সীমিত
• ট্রান্সফর্মার মডেল: প্রশ্ন-স্বাধীন বৈশিষ্ট্য সন্তুষ্ট করে না
• অতি নিম্ন-মাত্রিক SSM: $D' \ll \log^2 L$, পুনরাবৃত্তিমূলক দৃষ্টিভঙ্গি আরও ভাল

३. সম্ভাব্য সম্প্রসারণ

• হাইব্রিড আর্কিটেকচার: ট্রান্সফর্মার + LCSM স্তর (আংশিক স্তর এই পদ্ধতি প্রয়োগ করুন)
• আনুমানিক ভেরিয়েন্ট: এই পেপারের নির্ভুল পদ্ধতি এবং নিম্ন-র‍্যাঙ্ক আনুমানিক একত্রিত করুন
• অন্যান্য মোডালিটি: অডিও, ভিডিও প্রজন্ম (কনভোলিউশন আরও সাধারণ)

মূল রেফারেন্স (গুরুত্বপূর্ণ সাহিত্য)

१. van der Hoeven, J. (१९९७). Lazy multiplication of formal power series. ISSAC. তাত্ত্বিক ভিত্তি २. Poli, M. et al. (२०२३). Hyena hierarchy: Towards larger convolutional language models. প্রধান প্রয়োগ বস্তু ३. Massaroli, S. et al. (२०२४). Laughing hyena distillery: Extracting compact recurrences from convolutions. NeurIPS. আনুমানিক পদ্ধতি তুলনা ४. Gu, A. & Dao, T. (२०२३). Mamba: Linear-time sequence modeling with selective state spaces. SSM সম্পর্কিত কাজ ५. Fu, D. Y. et al. (२०२३). FlashFFTConv: Efficient convolutions for long sequences with tensor cores. বাস্তবায়ন ভিত্তি ६. Agarwal, N. et al. (२०२४). FutureFill: Fast generation from convolutional sequence models. সমান্তরাল কাজ

সামগ্রিক মূল্যায়ন: এটি একটি চমৎকার পেপার যেখানে তত্ত্ব এবং অনুশীলন ঘনিষ্ঠভাবে সংযুক্ত। তাত্ত্বিকভাবে, এটি LCSMs অনুমানের জন্য প্রথম প্রায়-রৈখিক নির্ভুল অ্যালগরিদম এবং সর্বজনীন ফ্রেমওয়ার্ক প্রদান করে; ব্যবহারিকভাবে, সিস্টেম-স্তরের অপ্টিমাইজেশনের মাধ্যমে উল্লেখযোগ্য ত্বরণ অর্জন করে। প্রধান সীমাবদ্ধতা হল LCSMs নিজেই বাস্তব প্রয়োগে ট্রান্সফর্মারের মতো জনপ্রিয় নয়, এবং ডেটা-নির্ভর ফিল্টারের পরীক্ষা যাচাইকরণ অপর্যাপ্ত। এই কাজ সিকোয়েন্স মডেল অনুমান অপ্টিমাইজেশনে নতুন দৃষ্টিভঙ্গি প্রদান করে, বিশেষত ভবিষ্যত আর্কিটেকচার ডিজাইনের জন্য নির্দেশনামূলক। মডেল দক্ষতা, সিকোয়েন্স মডেলিং এবং সিস্টেম অপ্টিমাইজেশনে আগ্রহী গবেষকদের জন্য সুপারিশ করা হয়।