id
flops/ssm-decode-cost-o1-vs-attention-on
Arithmetic intensity
The per-token decode cost of an SSM layer is O(1) in sequence length, while attention is O(n). For an SSM layer with state size N and inner dimension d_inner, each decode step does: (1) input projection: 2*d_inner*hidden flops, (2) state update: 2*d_inner*N flops (the B_t@C_t product), (3) output projection: 2*d_inner*hidden flops. The state is d_inner*N elements, read and written once per step: 2*d_inner*N*2 bytes. So AI = (2*d_inner*hidden + 2*d_inner*N + 2*d_inner*hidden) / (2*d_inner*N*2) = (2*hidden/N + 1 + 2*hidden/N) / 2. For Nemotron-H-8B (hidden 4096, d_inner 8192, N=128): AI = (2*4096/128 + 1 + 2*4096/128) / 2 = (64 + 1 + 64) / 2 = 64.5 flop/byte. This is well above the H100 ridge point (~295), so SSM decode is compute-bound at batch 1, unlike attention decode which is memory-bound. The catch: the state is per-sequence, so at batch B the total state memory is B * num_ssm_layers * d_inner * N * 2 bytes. For Nemotron-H-8B at batch 256: 256 * 48 * 8192 * 128 * 2 = 25.8 GiB. This is the opposite of KV cache, which grows with context length but amortizes across the batch dimension in the sense that paged KV can pack multiple sequences into shared pages.
Scales with
batch_size (state memory is per-sequence, does NOT amortize with batch)context_length (NOT at all for SSM layers — this is the defining property)ssm_state_size N (the constant that determines servability)expand ratio (d_inner = expand * hidden)num_ssm_layersstate_dtype (bf16 vs fp8)
Hardware parameters
parameterpeak_flopseffectThis is well above the H100 ridge point (~295), so SSM decode is compute-bound at batch 1, unlike attention decode which is memory-bound.basisrecordedvalues_fornvidia-h100-sxm,nvidia-b200,amd-instinct-mi300x,nvidia-a100-80gb-sxm4
Workarounds
Batch the state update across sequences so the state GEMM gets a real M dimensionfp8 state to halve the per-sequence costDo not page or evict the state — it is fixed-size, allocate contiguouslyCache the state across turns of multi-turn conversationsUse chunkwise/SSD formulation for prefill to get tensor-core efficiency
notes
The O(1) per-token decode cost is the defining advantage of SSMs over attention. For attention, each decode step must attend to all previous tokens: O(n) per token, O(n^2) total. For SSMs, the state summarizes all previous tokens in a fixed-size vector: O(1) per token, O(n) total. The constant-state size in bytes per sequence per layer is d_inner * N * 2 (for bf16). This is the number that determines whether the model is servable: at some batch size, the total state memory exceeds available HBM. The tensor-core mismatch (see ssm-sequential-scan-tensor-core-mismatch) means the FLOP efficiency is worse than attention, but the memory advantage is real and grows with context length. At 128K context, a pure-attention model's KV cache is 128K * num_layers * num_kv_heads * head_dim * 2 * 2 bytes, while an SSM's state is num_layers * d_inner * N * 2 bytes regardless of context.
HARDWARE-PARAMETER ROWS ADDED 2026-10-05 (schema authority pass, agent w5-schema). `affected_by_hardware` names PRODUCTS (accelerator record ids); these rows name the hardware QUANTITIES that move this class's cost, which had nowhere to live until flop.hardware_parameters was added in this commit. Every effect below is lifted verbatim from this record's own existing prose and no figure here is new - `magnitude` reproduces numbers the record already quoted. `basis` is 'unverified' where the effect was asserted with nothing concrete behind it, rather than being dressed up. The rows were pulled out of free-text notes; they are not a change to what this record claims.