Definition
Plain language
A way to speed up sequence computations by combining results in parallel chunks instead of one at a time.
As stated in the literature
A parallel-prefix-sum algorithm that computes cumulative results of an associative operation in logarithmic depth, used in state-space models for parallel training.
Why it matters: It's the algorithmic trick that lets modern state-space models like Mamba train as fast as transformers despite being recurrent in nature.
For example, computing a running sum of a million numbers in log-many parallel steps instead of one-by-one is an associative scan.
Heard on the show
“State-space models can use a parallel-prefix-sum trick called an associative scan — but only because their recurrence is linear.”Episode 032 — A Sticky-Note for Every Layer: Letting Transformers Remember What They Were Just Thinking