PaperlayerView exact revision on arXiv

Source-linked AI summary

Riccati State Space Models: Non-iterative Parallelization for Nonlinear Sequence Modeling

Mónika Farsang, Ramin Hasani, Daniela Rus, Radu Grosu

arXiv:2609.35441v1cs.LGcs.AI

TL;DR

Nonlinear recurrent models can express state-dependent dynamics, but generally lose the fixed-size compositional structure that allows a single parallel scan. RiccatiSSM uses input-conditioned Riccati dynamics with exact Möbius flows to retain that scan structure. Across long-sequence tasks, it achieves competitive predictive performance while reducing runtime relative to iterative LrcSSM.

  • Problem

    General nonlinear recurrences can have state-dependent dynamics, but their representations may grow under composition, limiting evaluation by a single fixed-size associative scan.

    Source: §1 · p. 1, §2.1 · p. 2

  • Method

    RiccatiSSM uses input-conditioned Riccati dynamics whose exact per-step flows are Möbius maps, composed through matrix multiplication for a single associative scan.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    22–33% lower end-to-end runtime than iterative LrcSSM under matched architectures, with competitive predictive performance across long-sequence classification, regression, and forecasting.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    RiccatiSSM demonstrates that state-dependent nonlinear dynamics can be exactly composable and evaluated with a single associative parallel scan.

    Source: §6 · p. 9

    RiccatiSSM is restricted to a second-order polynomial form with coefficients dependent on input rather than state, and additional constraints are needed for stability.

    Source: §4.5 · p. 8

Abstract

from arXiv · show

State space models (SSMs) achieve efficient sequence processing because their affine state updates are closed under composition and can therefore be evaluated with an associative parallel scan. Nonlinear recurrent models can provide richer, state-dependent dynamics, but generally lose this compositional structure: parallel evaluation then requires iterative methods that repeatedly linearize and scan the recurrence. We ask, what state-dependent nonlinear dynamics can be designed to remain exactly composable? We answer by introducing RiccatiSSM, a nonlinear SSM, in which each state dimension follows an input-conditioned Riccati differential equation. Its quadratic state dependence makes the local Jacobian explicitly state-dependent, while its exact per-step flow under piecewise-constant inputs is a M\"obius transformation. Since M\"obius maps are closed under composition and compose through $2\times 2$ matrix multiplication, the complete nonlinear state trajectory can be evaluated exactly with a single associative parallel scan, without iterative linearization. We further derive a constrained parameterization that ensures bounded, contractive dynamics, and avoids poles in the fractional-linear state update. Across long-sequence classification, regression, and forecasting tasks, RiccatiSSM achieves competitive predictive performance while reducing runtime by $22{-}33\%$ compared to the nonlinear LrcSSM under matched architectures. These results demonstrate that state-dependent nonlinear dynamics can retain exact composability and be evaluated efficiently within a single parallel scan.

1 INTRODUCTION

Affine SSMs support efficient parallel scans but do not provide state-dependent local dynamics, while general nonlinear recurrences typically require iterative linearization to recover parallelism. RiccatiSSM uses input-conditioned Riccati dynamics whose exact flows compose as Möbius maps, enabling one scan and bounded dynamics.

1 INTRODUCTION

  • DEER and LrcSSM recover parallel evaluation of nonlinear recurrences through repeated Newton-based linearization and scans, with iteration count determined by convergence.LrcSSM reduces the cost of each iteration through diagonal Jacobian design.Source: §1 · pp. 1–2
  • RiccatiSSM uses input-conditioned Riccati dynamics whose exact per-step flows are Möbius transformations, allowing the full nonlinear trajectory to be evaluated in one associative scan.The maps compose through 2 × 2 matrix multiplication, without Newton or fixed-point iterations.Source: §1 · p. 2
  • A constrained parameterization gives RiccatiSSM bounded, stable dynamics while retaining state-dependent local Jacobians and exact Möbius flow.The model is presented as a middle ground between affine SSMs and general nonlinear recurrent models.Source: §1 · p. 2
  • 22–33% lower runtime than iterative LrcSSM under matched architectures, with competitive predictive performance across long-sequence classification, regression, and forecasting tasks.The paper reports this comparison as a contribution across the evaluated task types.Source: §1 · p. 2

2 BACKGROUND AND MOTIVATION

Affine state updates compose in a fixed-size representation and support parallel scans, whereas general nonlinear updates generally do not. Möbius maps offer a nonlinear family closed under composition, motivating Riccati dynamics for exact scan-based evaluation.

2.1 PARALLEL SCANS AND STATE-DEPENDENT DYNAMICS

  • Affine updates combine a fixed-size representation of each step with an associative operator, enabling a parallel prefix scan with O(T) work and O(log T) parallel depth.The update is affine in the previous state even when its parameters depend on the current input.Source: §2.1 · p. 2
  • Composing general nonlinear updates can grow the representation—for example, degree-k polynomials can produce degree-k^2 maps—so one fixed-size associative scan is generally unavailable.DEER/ELK-style methods instead use Newton iterations, while RiccatiSSM restricts the update family to compose exactly in one step.Source: §2.1 · p. 2, Table 1 · p. 3

2.2 CLOSURE UNDER COMPOSITION

  • Fractional-linear, or Möbius, maps provide a nonlinear family with fixed-size representations whose compositions correspond to 2 × 2 matrix multiplication.Associativity makes a sequence of these maps exactly composable with a parallel prefix scan.Source: §2.2 · p. 3
  • Riccati differential equations generate fractional-linear flow maps, motivating a model whose exact discrete-time dynamics can be composed rather than approximated through repeated linearization.This connects the nonlinear dynamics to the composition-closed family needed for scan evaluation.Source: §2.2 · p. 3

3 RICCATI STATE SPACE MODEL

RiccatiSSM uses input-conditioned Riccati dynamics whose exact per-step flows are Möbius maps, enabling nonlinear state trajectories to be evaluated by an associative scan. Its parameterization also constrains the dynamics to remain bounded and contractive.

3 RICCATI STATE SPACE MODEL

  • RiccatiSSM builds a nonlinear sequence layer from input-conditioned Riccati dynamics, exact Möbius step maps, a parallel scan, and constrained coefficients.The construction proceeds from the vector field to a lifted linear system and projective state update.Source: §3 · p. 3

3.1 INPUT-DEPENDENT RICCATI DYNAMICS

  • The quadratic state term makes the local Jacobian state-dependent, while input-conditioned coefficients also let the local contraction rate vary with the input.When the quadratic coefficient is zero, the dynamics reduce to an input-varying linear ODE.Source: §3.1 · p. 4

3.2 PROJECTIVE LIFT AND EXACT DISCRETIZATION

  • Exact zero-order-hold integration of the Riccati ODE produces a Möbius update, while the projected state retains nonlinear, state-dependent dynamics.The lifted coordinates evolve linearly, and their ratio recovers the original state.Source: §3.2 · pp. 4–5

3.3 PARALLEL SEQUENCE EVALUATION

  • The Möbius updates compose through matrix multiplication, so one associative scan computes all prefix products and recovers every state without iterative approximation.For diagonal dynamics, the recurrence uses O(TD) work and O(log T) parallel depth; under zero-order hold, each step is integrated exactly.Source: §3.3 · p. 5

3.4 STABLE PARAMETERIZATION

  • A constrained parameterization gives the dynamics a bounded invariant interval and contractive transitions, avoiding poles associated with finite-time divergence.In the fractional-linear update, divergence corresponds to the denominator approaching zero.Source: §3.4 · p. 5

3.5 RELATION TO LIQUID DYNAMICS

  • Unlike LrcSSM’s saturating nonlinearities, RiccatiSSM represents state dependence through a quadratic term; the paper also derives a local second-order correspondence to LRC dynamics.The matched-dynamics analysis distinguishes local approximation error from the explicit-Euler discretization error used in LrcSSM.Source: §3.5 · p. 6

4 EXPERIMENTS

The experiments compare RiccatiSSM’s predictive performance and runtime with sequence-model baselines, then test parameterization choices and state the model’s scope restriction. Across classification, regression, and forecasting, results are competitive; a single-scan evaluation also reduces runtime relative to LrcSSM.

4.1 EXPERIMENTAL SETUP

  • The setup uses independent learned projections to produce constrained Riccati coefficients, with an LRC-tied alternative evaluated separately.Results are reported over five random seeds, with dataset, configuration, and hyperparameter details in Appendix C.Source: §4.1 · pp. 6–7

4.2 LONG-SEQUENCE BENCHMARK RESULTS

  • RiccatiSSM is competitive across six UEA classification datasets, improves over LrcSSM on SCP1 and MotorImagery, and shows greater seed variability on EigenWorms.EigenWorms runs range from 77.8% to 91.7%.Source: §4.2 · p. 7
  • RiccatiSSM achieves PPG-DaLiA MSE 7.15 ± 1.01 × 10−2 versus LrcSSM’s 10.89 ± 0.96 × 10−2.It remains competitive with LinOSS; Table 3 reports MSE averaged over five seeds.Source: §4.2 · p. 7, Table 3 · p. 7
  • On Weather forecasting 720 future steps from 720 past steps, RiccatiSSM obtains MAE 0.5681 versus LrcSSM’s 0.5888, remaining close to LinOSS.Table 4 reports mean absolute error for the 720-step prediction task.Source: §4.2 · p. 7, Table 4 · p. 7

4.3 RUNTIME AND PARALLEL-EVALUATION COST

  • RiccatiSSM reduces end-to-end runtime by 22−33% versus LrcSSM across three datasets, with the largest gap on longer EigenWorms sequences.Figure 2 compares time per step under the same architecture on an NVIDIA A100 GPU; RiccatiSSM uses one scan per layer while LrcSSM uses about three quasi-DEER iterations.Source: Figure 2 · p. 8, §4.3 · p. 8

4.4 ABLATIONS

  • Removing the input-dependent speed factor ε(u) increases test MSE by 1.3 × 10−2 on PPG-DaLiA.The ablation indicates that input-dependent modulation of the full Riccati dynamics is beneficial.Source: §4.4 · p. 8
  • The LRC-tied parameterization obtains MSE 8.47 ± 0.47 × 10−2, versus 7.15 ± 1.01 × 10−2 for the freely parameterized model.Retaining LRC-derived coefficient coupling is not necessary and is more restrictive than learning coefficients independently under stability constraints.Source: §4.4 · p. 8

4.5 LIMITATIONS

  • RiccatiSSM is restricted to a second-order polynomial form: coefficients depend on input rather than state, while state-dependent nonlinearity enters through quadratic curvature.The parameterization also requires constraints for stable dynamics.Source: §4.5 · p. 8

5 RELATED WORK

Prior work evaluates affine recurrences with associative scans and extends nonlinear sequence evaluation through iterative linearization. RiccatiSSM relates to liquid models and uses a temporal Möbius recurrence distinct from earlier representation and uncertainty-statistic applications.

Parallel evaluation of nonlinear recurrences

  • Affine state updates compose for associative scans, while DEER, Quasi-DEER, ELK, and related methods recover nonlinear parallelism through iterative linearization.Fixed-Point RNNs and successive-linearization approaches also formulate parallel evaluation through fixed points or iterative schemes.Source: §5 · p. 9

Liquid and continuous-time models

  • LTC and LRC models use state-dependent liquid dynamics; CfC integrates a step in closed form but retains sequential recursion, whereas RiccatiSSM has exact within-step discretization.LRC and LrcSSM use diagonal Jacobians and contraction-based gradient-stability guarantees.Source: §5 · p. 9

Möbius maps and parallel prefix

  • Möbius maps compose through 2 × 2 matrix multiplication, but RiccatiSSM applies the map to the state itself, unlike prior feature-map and uncertainty-statistic uses.The cited prior sequence recurrence applies the fractional-linear map to a linear-Gaussian model’s uncertainty statistic, not its hidden state.Source: §5 · p. 9

6 CONCLUSION

RiccatiSSM combines input-conditioned Riccati dynamics and a constrained parameterization to obtain exact single-scan nonlinear sequence evaluation. It achieves competitive predictive performance across long-sequence tasks while reducing runtime relative to iterative LrcSSM.

6 CONCLUSION

  • RiccatiSSM’s input-conditioned Riccati dynamics produce exact fractional-linear updates that compose through 2 × 2 matrix multiplication for a single associative scan.A constrained parameterization keeps the dynamics bounded and contractive while retaining state-dependent timescales.Source: §6 · p. 9
  • Across long-sequence classification, regression, and forecasting, RiccatiSSM achieves competitive predictive performance and reduces end-to-end runtime by 22−33% relative to iterative LrcSSM.The paper frames compositionally closed nonlinear dynamics as a middle ground between linear SSMs and general nonlinear recurrent models.Source: §6 · p. 9

A ADDITIONAL THEORETICAL RESULTS

The appendix establishes the algebraic and stability properties behind RiccatiSSM, then relates its quadratic dynamics to liquid models through a local Taylor correspondence. Its exact projective flow composes via matrix products, while constraints keep trajectories bounded and contractive.

A.1 STABLE PARAMETERIZATION

  • The constrained parameterization makes [−B, B] forward-invariant and transitions contractive, preventing poles and yielding a real-valued closed-form discretization.The coefficient construction retains a contraction margin across the interval.Source: §A.1 · pp. 12–13

A.2 PROJECTIVE LIFT OF RICCATI DYNAMICS

  • A Riccati trajectory is represented as x = p/q, where p and q evolve as a two-dimensional linear system when q remains nonzero.Common nonzero scaling of p and q leaves the projective state unchanged.Source: §A.2 · pp. 13–14

A.3 EXACT MATRIX EXPONENTIAL

  • Under zero-order hold, constant coefficients yield an exact matrix-exponential step; the constrained parameterization ensures its real hyperbolic branch.The stable constraints imply a positive discriminant and real, positive characteristic rate.Source: §A.3 · p. 14

A.4 COMPOSITION OF M ¨OBIUS UPDATES

  • Möbius updates compose through ordered matrix products, so all prefix products—and the full state sequence—are computed with one associative parallel scan.The composition order is P_t = M_t M_{t−1} · · · M_1.Source: §A.4 · p. 15

B RELATION TO LIQUID DYNAMICS

  • The projective lift preserves nonlinear Riccati state dynamics and state-dependent contraction rates, but input-only coefficients are required for scan closure.Making α, β, γ, or ε depend on the state would break closure under composition.Source: B RELATION TO LIQUID DYNAMICS · p. 15

B.1 SECOND-ORDER LOCAL CORRESPONDENCE

  • The quadratic Riccati field uniquely matches an LRC field’s value, slope, and curvature at x = 0, but this local correspondence does not imply global agreement.A globally bounded LRC field can differ from an unconstrained quadratic that develops a pole outside the local operating region; trained RiccatiSSM uses constraints to prevent this behavior.Source: §B.1 · pp. 15–16
  • A positive speed factor can be separated from the Riccati coefficients as a parameterization choice because only their products determine the vector field.The equivalent Riccati coefficients can be expressed for any chosen positive speed factor.Source: §B.1 · p. 15

B.2 MATCHED-DYNAMICS EXPERIMENT

With matched local vector fields, RiccatiSSM’s exact quadratic flow tracks the continuous LRC dynamics more closely than LrcSSM’s Euler update does. The comparison separates quadratic-approximation error from integration error.

B.2 MATCHED-DYNAMICS EXPERIMENT

  • The experiment matches Taylor coefficients from the implemented LRC field at each input frame to isolate differences in vector fields from parameterization and training.The coefficients are obtained by automatic differentiation.Source: §B.2 · p. 16
  • Four systems distinguish field-approximation error from integration error by comparing full LRC and matched quadratic fields under RK4, Euler, and exact zero-order-hold integration.LrcSSM-RK4 is the high-accuracy reference; RiccatiSSM-ZOH exactly integrates the held-input quadratic field.Source: §B.2 · p. 16
  • 1.7 · 10−5 relative RMSE over 512 steps separates RiccatiSSM-ZOH from LrcSSM-RK4, versus 7.2·10−3 error for LrcSSM-Euler against LrcSSM-RK4.The quadratic truncation error is roughly two orders of magnitude smaller than the explicit-Euler error.Source: §B.2 · p. 16

B.3 REACHABLE CONSTRAINT-COEFFICIENT SPACE

The matched-dynamics trajectories remain close, while the LRC-tied coefficient parameterization reaches a narrower region than the free Riccati parameterization.

B.3 REACHABLE CONSTRAINT-COEFFICIENT SPACE

  • RiccatiSSM-ZOH closely matches both LrcSSM trajectories, indicating that Euler integration—not quadratic truncation—dominates the discretization error.The comparison uses matched Taylor coefficients and white-noise input.Source: Figure 3 · p. 17
  • The LRC-tied parameterization occupies a strictly smaller reachable (γ, α/αmax) region than the free variant, with compressed stability and curvature coefficients.The figure reports distributions sampled over 500k random initializations; the LRC-tied outputs are compressed by double-squashing through circuit nonlinearities.Source: §B.3 · pp. 16–17, Figure 4 · p. 17

C ADDITIONAL EXPERIMENTAL DETAILS

The experimental details describe the hyperparameter search and model-selection procedure for classification, PPG-DaLiA, and Weather.

C ADDITIONAL EXPERIMENTAL DETAILS

  • The grid search spans learning rates {10−5, 10−4, 10−3}, hidden dimensions {16, 64, 128}, state-space dimensions {16, 64, 256}, and 2, 4, or 6 blocks.Weather instead uses a random search over the same ranges.Source: C ADDITIONAL EXPERIMENTAL DETAILS · pp. 17–18
  • For each dataset, the selected configuration has the highest mean validation accuracy across five data splits generated with the same random seeds as the reported baselines.Weather uses a random hyperparameter search rather than the dataset-specific selection procedure described for the others.Source: C ADDITIONAL EXPERIMENTAL DETAILS · p. 18
  • Table 7 reports the best-performing hyperparameter configuration selected for each dataset.Source: C ADDITIONAL EXPERIMENTAL DETAILS · p. 18, Table 7 · p. 18

C.1 RUNTIME

RiccatiSSM has low runtimes across the reported best-performing configurations, but those configurations can differ in architecture and model size. On SCP1 and Ethanol, it is slower than LrcSSM in comparisons that are not architecture-matched.

C.1 RUNTIME

  • RiccatiSSM achieves low runtimes across the reported best-performing configurations.The configurations are selected separately for each dataset.Source: §C.1 · p. 18
  • RiccatiSSM is slower than LrcSSM on SCP1 and Ethanol, but these comparisons are not architecture-matched.The selected RiccatiSSM configurations use six layers, versus two for LrcSSM.Source: §C.1 · p. 18
  • Table 8 reports runtime in seconds for 1,000 training steps using each model’s best configuration.Its model values are taken from Rusch and Rus (2025) and Farsang and Grosu (2025).Source: Table 8 · p. 18

Related papers

Loading 2609.35441v1…