状态空间模型的并行扫描算法是如何工作的？

1. 循环结构的并行化需求

朴素循环结构逐时间步串行计算，无法利用现代硬件的并行能力，训练效率低下。并行扫描（Parallel Scan）算法通过将递推分解为可结合的前缀和运算，使循环结构能够在硬件上并行执行。

2. 选择性扫描（Selective Scan）

Mamba 引入的选择性机制使参数依赖输入，破坏了线性时不变性，无法直接用卷积。为此，Mamba 采用选择性扫描算法：将序列分块，块内做二次（类注意力）计算以利用硬件效率，块间传递 SSM 状态以维持整体线性复杂度。该算法在保持线性扩展的同时恢复了并行训练能力。

3. 硬件感知实现

Mamba 的实现进一步做了 IO 优化：不将庞大的状态矩阵写入 GPU 高带宽内存（HBM），而是在片上高速 SRAM 中完成扫描（recurrence）运算，大幅减少内存读写。官方实现报告，该高效扫描内核相比朴素的选择性循环实现可提速数十倍。