Mamba expliqué : L'alternative efficace aux Transformers Mamba Explained: The Efficient Alternative to Transformers Mamba解説：Transformerの効率的な代替

🔍 Intuition :

🔍 Intuition:

🔍 直感：

Imaginez un système qui "se souvient" de son passé via un état caché $h(t)$. À chaque instant, cet état est mis à jour en fonction de l'état précédent (via $\mathbf{A}$) et de la nouvelle entrée (via $\mathbf{B}$). La sortie $y(t)$ est ensuite calculée à partir de cet état (via $\mathbf{C}$).

Imagine a system that "remembers" its past via a hidden state $h(t)$. At each moment, this state is updated based on the previous state (via $\mathbf{A}$) and the new input (via $\mathbf{B}$). The output $y(t)$ is then computed from this state (via $\mathbf{C}$).

隠れ状態$h(t)$を介して過去を「記憶」するシステムを想像してください。各瞬間、この状態は前の状態（$\mathbf{A}$経由）と新しい入力（$\mathbf{B}$経由）に基づいて更新されます。出力$y(t)$はこの状態（$\mathbf{C}$経由）から計算されます。

📖 Exemple concret :

📖 Concrete Example:

📖 具体例：

Pensez à lire une phrase mot par mot. Votre cerveau maintient un état mental (= $h(t)$) qui résume ce que vous avez lu jusqu'à présent. Quand vous lisez un nouveau mot (= $x(t)$), vous mettez à jour cet état mental en combinant votre compréhension actuelle avec le nouveau mot. Votre compréhension finale de la phrase (= $y(t)$) dépend de cet état mental accumulé. C'est exactement ce que fait un SSM !

Think about reading a sentence word by word. Your brain maintains a mental state (= $h(t)$) that summarizes what you've read so far. When you read a new word (= $x(t)$), you update this mental state by combining your current understanding with the new word. Your final understanding of the sentence (= $y(t)$) depends on this accumulated mental state. This is exactly what an SSM does!

文を一語ずつ読むことを考えてください。脳はこれまでに読んだ内容を要約する精神状態（= $h(t)$）を維持します。新しい単語（= $x(t)$）を読むと、現在の理解と新しい単語を組み合わせてこの精神状態を更新します。文の最終的な理解（= $y(t)$）は、この蓄積された精神状態に依存します。これがまさにSSMが行うことです！

🧮 Explication pédagogique :

🧮 Pedagogical Explanation:

🧮 教育的説明：

Pourquoi discrétiser ? Les ordinateurs ne peuvent pas travailler avec du temps continu. Ils traitent les données par étapes discrètes (token 1, token 2, token 3...). C'est comme passer d'un film (continu) à une série d'images fixes (discret).

Why discretize? Computers cannot work with continuous time. They process data in discrete steps (token 1, token 2, token 3...). It's like going from a movie (continuous) to a series of still images (discrete).

なぜ離散化するのか？ コンピュータは連続時間で動作できません。離散ステップ（トークン1、トークン2、トークン3...）でデータを処理します。これは映画（連続）から一連の静止画像（離散）に移行するようなものです。

Que signifie $\exp(\Delta \mathbf{A})$ ? C'est l'exponentielle matricielle, qui transforme la matrice d'évolution continue $\mathbf{A}$ en sa version discrète $\overline{\mathbf{A}}$. Le paramètre $\Delta$ (delta) est le pas de temps : plus $\Delta$ est petit, plus la discrétisation est précise (mais plus coûteuse en calcul).

What does $\exp(\Delta \mathbf{A})$ mean? It's the matrix exponential, which transforms the continuous evolution matrix $\mathbf{A}$ into its discrete version $\overline{\mathbf{A}}$. The parameter $\Delta$ (delta) is the time step: the smaller $\Delta$ is, the more accurate the discretization (but more computationally expensive).

$\exp(\Delta \mathbf{A})$とは何か？ これは行列指数で、連続進化行列$\mathbf{A}$を離散版$\overline{\mathbf{A}}$に変換します。パラメータ$\Delta$（デルタ）は時間ステップです：$\Delta$が小さいほど離散化は正確になります（ただし計算コストが高くなります）。

Méthode ZOH : "Zero-Order Hold" signifie qu'on maintient la valeur d'entrée constante pendant chaque intervalle de temps $\Delta$. C'est la méthode la plus simple et la plus utilisée pour discrétiser un SSM.

ZOH Method: "Zero-Order Hold" means we keep the input value constant during each time interval $\Delta$. It's the simplest and most commonly used method to discretize an SSM.

ZOH法： 「ゼロ次ホールド」とは、各時間間隔$\Delta$の間、入力値を一定に保つことを意味します。これはSSMを離散化する最も単純で最も一般的に使用される方法です。

📊 Interprétation :

📊 Interpretation:

📊 解釈：

Cette équation $h_t = \overline{\mathbf{A}} h_{t-1} + \overline{\mathbf{B}} x_t$ est une récurrence : pour calculer l'état au temps $t$, on combine l'état précédent $h_{t-1}$ (mémoire) avec la nouvelle entrée $x_t$ (information fraîche). C'est similaire à un RNN, mais avec une structure mathématique plus riche issue de la théorie du contrôle !

This equation $h_t = \overline{\mathbf{A}} h_{t-1} + \overline{\mathbf{B}} x_t$ is a recurrence: to compute the state at time $t$, we combine the previous state $h_{t-1}$ (memory) with the new input $x_t$ (fresh information). It's similar to an RNN, but with a richer mathematical structure from control theory!

この方程式$h_t = \overline{\mathbf{A}} h_{t-1} + \overline{\mathbf{B}} x_t$は再帰です：時刻$t$の状態を計算するために、前の状態$h_{t-1}$（記憶）と新しい入力$x_t$（新鮮な情報）を組み合わせます。これはRNNに似ていますが、制御理論からのより豊かな数学的構造を持っています！

🧮 Explication pédagogique :

🧮 Pedagogical Explanation:

🧮 教育的説明：

Que signifie "projection linéaire" ? C'est simplement une multiplication matricielle : $s_{\mathbf{B}}(x_t) = \mathbf{W}_B \cdot x_t$ où $\mathbf{W}_B$ est une matrice de poids apprise. Le modèle apprend à transformer l'entrée $x_t$ en paramètres $\mathbf{B}_t$, $\mathbf{C}_t$, et $\Delta_t$ adaptés à cette entrée spécifique.

What does "linear projection" mean? It's simply a matrix multiplication: $s_{\mathbf{B}}(x_t) = \mathbf{W}_B \cdot x_t$ where $\mathbf{W}_B$ is a learned weight matrix. The model learns to transform the input $x_t$ into parameters $\mathbf{B}_t$, $\mathbf{C}_t$, and $\Delta_t$ adapted to that specific input.

「線形射影」とは何か？ これは単なる行列乗算です：$s_{\mathbf{B}}(x_t) = \mathbf{W}_B \cdot x_t$、ここで$\mathbf{W}_B$は学習された重み行列です。モデルは入力$x_t$をその特定の入力に適応したパラメータ$\mathbf{B}_t$、$\mathbf{C}_t$、$\Delta_t$に変換することを学習します。

Pourquoi $\Delta_t$ varie ? Le pas de temps $\Delta_t$ contrôle la "vitesse" à laquelle le modèle intègre les nouvelles informations. Un $\Delta_t$ grand signifie "cette information est importante, intègre-la rapidement". Un $\Delta_t$ petit signifie "cette information est moins importante, garde plutôt la mémoire actuelle". C'est comme ajuster votre niveau d'attention en lisant !

Why does $\Delta_t$ vary? The time step $\Delta_t$ controls the "speed" at which the model integrates new information. A large $\Delta_t$ means "this information is important, integrate it quickly". A small $\Delta_t$ means "this information is less important, keep the current memory instead". It's like adjusting your attention level while reading!

なぜ$\Delta_t$が変化するのか？ 時間ステップ$\Delta_t$は、モデルが新しい情報を統合する「速度」を制御します。大きい$\Delta_t$は「この情報は重要なので、すぐに統合する」ことを意味します。小さい$\Delta_t$は「この情報はあまり重要ではないので、現在の記憶を保持する」ことを意味します。これは読書中に注意レベルを調整するようなものです！

Fonction softplus : $\tau_{\Delta}(x) = \log(1 + e^x)$ garantit que $\Delta_t$ est toujours positif (car un pas de temps négatif n'aurait pas de sens physique). C'est une version "lisse" de la fonction ReLU.

Softplus function: $\tau_{\Delta}(x) = \log(1 + e^x)$ ensures that $\Delta_t$ is always positive (since a negative time step wouldn't make physical sense). It's a "smooth" version of the ReLU function.

Softplus関数： $\tau_{\Delta}(x) = \log(1 + e^x)$は$\Delta_t$が常に正であることを保証します（負の時間ステップは物理的に意味がないため）。これはReLU関数の「滑らかな」バージョンです。

💡 Pourquoi c'est révolutionnaire ?

💡 Why is this revolutionary?

💡 なぜこれが革命的なのか？

En rendant $\mathbf{B}_t$, $\mathbf{C}_t$, et $\Delta_t$ dépendants de l'entrée, Mamba peut :

By making $\mathbf{B}_t$, $\mathbf{C}_t$, and $\Delta_t$ input-dependent, Mamba can:

$\mathbf{B}_t$、$\mathbf{C}_t$、$\Delta_t$を入力依存にすることで、Mambaは次のことができます：

• Filtrer les informations : ignorer les tokens non pertinents (via $\mathbf{B}_t$ petit)
• Filter information: ignore irrelevant tokens (via small $\mathbf{B}_t$)
• 情報をフィルタリング：無関係なトークンを無視（小さい$\mathbf{B}_t$経由）
• Se concentrer sur l'important : amplifier les tokens importants (via $\mathbf{C}_t$ grand)
• Focus on important: amplify important tokens (via large $\mathbf{C}_t$)
• 重要なものに焦点を当てる：重要なトークンを増幅（大きい$\mathbf{C}_t$経由）
• Adapter la résolution temporelle : $\Delta_t$ grand = oublier rapidement, $\Delta_t$ petit = mémoriser longtemps
• Adapt temporal resolution: large $\Delta_t$ = forget quickly, small $\Delta_t$ = remember long
• 時間解像度を適応：大きい$\Delta_t$ = 素早く忘れる、小さい$\Delta_t$ = 長く記憶

🧮 Explication pédagogique :

🧮 Pedagogical Explanation:

🧮 教育的説明：

Que signifie "$\overline{\mathbf{A}}_t$ et $\overline{\mathbf{B}}_t$ changent à chaque pas de temps" ? Contrairement aux SSM classiques où ces matrices sont fixes, ici elles sont recalculées pour chaque token en fonction de $\Delta_t$ et $\mathbf{B}_t$ qui varient. C'est ce qui donne la sélectivité, mais cela rend le calcul plus complexe.

What does "$\overline{\mathbf{A}}_t$ and $\overline{\mathbf{B}}_t$ change at each time step" mean? Unlike classic SSMs where these matrices are fixed, here they are recomputed for each token based on $\Delta_t$ and $\mathbf{B}_t$ which vary. This is what gives selectivity, but it makes computation more complex.

「$\overline{\mathbf{A}}_t$と$\overline{\mathbf{B}}_t$が各時間ステップで変化する」とはどういう意味か？ これらの行列が固定されている古典的なSSMとは異なり、ここでは変化する$\Delta_t$と$\mathbf{B}_t$に基づいて各トークンごとに再計算されます。これが選択性を与えますが、計算をより複雑にします。

Pourquoi ne peut-on plus utiliser la convolution rapide ? La convolution rapide (FFT) fonctionne quand les poids sont constants. Avec des poids qui changent ($\overline{\mathbf{A}}_t$, $\overline{\mathbf{B}}_t$), on doit calculer la récurrence séquentiellement : $h_1 \rightarrow h_2 \rightarrow h_3 \rightarrow \ldots$. C'est potentiellement lent !

Why can't we use fast convolution anymore? Fast convolution (FFT) works when weights are constant. With changing weights ($\overline{\mathbf{A}}_t$, $\overline{\mathbf{B}}_t$), we must compute the recurrence sequentially: $h_1 \rightarrow h_2 \rightarrow h_3 \rightarrow \ldots$. This is potentially slow!

なぜ高速畳み込みを使用できなくなるのか？ 高速畳み込み（FFT）は重みが一定のときに機能します。変化する重み（$\overline{\mathbf{A}}_t$、$\overline{\mathbf{B}}_t$）では、再帰を順次計算する必要があります：$h_1 \rightarrow h_2 \rightarrow h_3 \rightarrow \ldots$。これは潜在的に遅いです！

Solution : Scan parallèle hardware-aware : Mamba utilise un algorithme de scan parallèle (comme prefix-sum) optimisé pour les GPU. Au lieu de calculer séquentiellement, il divise le travail en blocs parallèles. C'est comme avoir plusieurs personnes qui lisent différentes parties d'un livre simultanément, puis combinent leurs compréhensions. Cela maintient la complexité O(n) tout en étant rapide en pratique !

Solution: Hardware-aware parallel scan: Mamba uses a parallel scan algorithm (like prefix-sum) optimized for GPUs. Instead of computing sequentially, it divides the work into parallel blocks. It's like having multiple people reading different parts of a book simultaneously, then combining their understandings. This maintains O(n) complexity while being fast in practice!

解決策：ハードウェア対応並列スキャン：MambaはGPU向けに最適化された並列スキャンアルゴリズム（prefix-sumのような）を使用します。順次計算する代わりに、作業を並列ブロックに分割します。これは複数の人が本の異なる部分を同時に読み、その後理解を組み合わせるようなものです。これにより、実際には高速でありながらO(n)の複雑度を維持します！

🔑 Les avantages clés de Mamba :

🔑 Key Advantages of Mamba:

🔑 Mambaの主な利点：

• Complexité linéaire O(n) : 5x plus rapide que les Transformers sur les longues séquences
• Linear complexity O(n): 5x faster than Transformers on long sequences
• 線形複雑度O(n)：長いシーケンスでTransformerより5倍高速


• Mémoire constante O(1) : pas besoin de stocker toute la séquence (contrairement à l'Attention qui nécessite O(n²))
• Constant memory O(1): no need to store the entire sequence (unlike Attention which requires O(n²))
• 一定メモリO(1)：シーケンス全体を保存する必要がない（O(n²)を必要とするAttentionとは異なり）


• Sélectivité : se concentre dynamiquement sur les informations importantes
• Selectivity: dynamically focuses on important information
• 選択性：重要な情報に動的に焦点を当てる


• Performances comparables : rivalise avec les Transformers sur de nombreuses tâches
• Comparable performance: rivals Transformers on many tasks
• 同等のパフォーマンス：多くのタスクでTransformerに匹敵


• Hardware-aware : optimisé pour les GPU modernes
• Hardware-aware: optimized for modern GPUs
• ハードウェア対応：最新のGPU向けに最適化

🔍 Composants clés :

🔍 Key Components:

🔍 主要コンポーネント：

• Convolution 1D : Capture les dépendances locales (comme dans les CNN)
• 1D Convolution: Captures local dependencies (like in CNNs)
• 1D畳み込み：局所的な依存関係を捉える（CNNのように）


• SSM sélectif : Capture les dépendances longue distance avec complexité linéaire
• Selective SSM: Captures long-range dependencies with linear complexity
• 選択的SSM：線形複雑度で長距離依存関係を捉える


• Gating (GLU) : Contrôle le flux d'information (inspiré des LSTM)
• Gating (GLU): Controls information flow (inspired by LSTMs)
• ゲーティング（GLU）：情報フローを制御（LSTMに触発）


• Connexion résiduelle : Facilite l'entraînement de réseaux profonds
• Residual connection: Facilitates training of deep networks
• 残差接続：深いネットワークのトレーニングを容易にする

🧮 Explication pédagogique : O(n) vs O(n²)

🧮 Pedagogical Explanation: O(n) vs O(n²)

🧮 教育的説明：O(n) vs O(n²)

Que signifie O(n²) pour les Transformers ? L'Attention calcule la similarité entre chaque paire de tokens. Pour $n$ tokens, il y a $n \times n = n^2$ paires. Par exemple, pour 1000 tokens, cela fait 1 million de calculs ! Pour 10 000 tokens, c'est 100 millions de calculs ! La complexité explose quadratiquement.

What does O(n²) mean for Transformers? Attention computes similarity between every pair of tokens. For $n$ tokens, there are $n \times n = n^2$ pairs. For example, for 1000 tokens, that's 1 million computations! For 10,000 tokens, it's 100 million computations! Complexity explodes quadratically.

TransformerのO(n²)とは何を意味するか？ Attentionはすべてのトークンペア間の類似性を計算します。$n$トークンの場合、$n \times n = n^2$ペアがあります。例えば、1000トークンの場合、100万回の計算です！10,000トークンの場合、1億回の計算です！複雑度は二次的に爆発します。

Que signifie O(n) pour Mamba ? Mamba traite chaque token une seule fois de manière séquentielle (via le scan parallèle). Pour 1000 tokens, c'est 1000 calculs. Pour 10 000 tokens, c'est 10 000 calculs. La complexité croît linéairement, ce qui est beaucoup plus efficace pour les longues séquences !

What does O(n) mean for Mamba? Mamba processes each token only once sequentially (via parallel scan). For 1000 tokens, that's 1000 computations. For 10,000 tokens, it's 10,000 computations. Complexity grows linearly, which is much more efficient for long sequences!

MambaのO(n)とは何を意味するか？ Mambaは各トークンを（並列スキャンを介して）順次一度だけ処理します。1000トークンの場合、1000回の計算です。10,000トークンの場合、10,000回の計算です。複雑度は線形に増加し、長いシーケンスに対してはるかに効率的です！

Exemple concret : Imaginez que vous devez comparer tous les étudiants d'une classe entre eux (Transformers). Dans une classe de 30 élèves, cela fait 30×30 = 900 comparaisons. Maintenant imaginez que vous devez juste noter chaque élève individuellement (Mamba) : seulement 30 évaluations ! La différence devient énorme quand la classe grandit.

Concrete example: Imagine you need to compare all students in a class with each other (Transformers). In a class of 30 students, that's 30×30 = 900 comparisons. Now imagine you just need to grade each student individually (Mamba): only 30 evaluations! The difference becomes huge as the class grows.

具体例： クラスのすべての生徒を互いに比較する必要があると想像してください（Transformers）。30人の生徒のクラスでは、30×30 = 900回の比較になります。今度は各生徒を個別に評価するだけでよいと想像してください（Mamba）：わずか30回の評価です！クラスが大きくなるにつれて差は巨大になります。

Mémoire O(1) vs O(n²) : Les Transformers doivent stocker la matrice d'attention complète (toutes les paires de tokens), ce qui nécessite O(n²) mémoire. Mamba ne stocke que l'état caché de taille fixe $N$, indépendamment de la longueur de la séquence ! C'est pourquoi Mamba peut traiter des séquences de 1 million de tokens là où les Transformers saturent la mémoire.

Memory O(1) vs O(n²): Transformers must store the complete attention matrix (all token pairs), which requires O(n²) memory. Mamba only stores the hidden state of fixed size $N$, independent of sequence length! This is why Mamba can process sequences of 1 million tokens where Transformers saturate memory.

メモリO(1) vs O(n²)： Transformerは完全なAttention行列（すべてのトークンペア）を保存する必要があり、O(n²)メモリが必要です。Mambaはシーケンス長に関係なく、固定サイズ$N$の隠れ状態のみを保存します！これがMambaがTransformerがメモリを飽和させる100万トークンのシーケンスを処理できる理由です。