A Second-Order Complexity Analysis of Attention and State-Space Models

Standard analyses of sequence models characterize efficiency primarily in terms of sequence length, such as quadratic-time attention or linear-time state-space models. We show that sequence-length complexity alone does not determine the resources needed to evaluate a model at a prescribed accuracy. We develop a second-order complexity analysis of attention and selective state-space operators, explicitly accounting for approximation accuracy, input regularity, representation, and effective memory. For representative attention and selective state-space operators, we derive matching deterministic sampling bounds that distinguish the cost of resolving a signal from the amount of history required. Even a stable state-space operator requires exponentially many point queries in the requested accuracy bits on bounded Lipschitz inputs, while quantitative smoothness and stability certificates enable polynomial-time evaluation under fixed resource bounds. We introduce precision locality: the shortest recent context sufficient to recover the full-history output without a cached summary of earlier inputs. On arbitrary bounded token sequences, certified contractive selective scans admit context lengths logarithmic in inverse error at fixed contraction and magnitude bounds, whereas uniform attention requires nearly the entire sequence at high accuracy. We construct evaluators with certified context lengths and numerical precision budgets, including explicit conditions for Mamba’s selective recurrence. We further prove that approximating persistent statistics over growing horizons requires weaker contraction, larger state magnitudes, or stronger amplification. These results connect precision-dependent evaluation costs with long-range approximation limits and provide a mathematical basis for analyzing the balance between forgetting and persistent memory.