Block-Local Adversaries for Linear Recurrent Sequence Models

Adversarial training makes a network robust to small worst-case input changes. It does this by repeatedly searching for a damaging perturbation and then training on it. The search is the expensive part: each of its K steps needs a full forward and backward pass through the network, so robust training typically costs 10 to 40 times more than ordinary training. For long-sequence models such as state-space models and linear recurrent units, every one of those passes runs over thousands of time steps. These models share one structural fact that the adversarial training literature has not exploited. They are built from linear recurrences, state updates of the form $h_t = A h_{t-1} + B x_t$ with no nonlinearity between steps, interleaved with position-wise nonlinear layers. Because each recurrence is linear, its effect on an input perturbation is a fixed linear operator. Both that operator and its transpose can be computed as a parallel scan of logarithmic depth.

We propose to run the inner adversarial search only through the first few blocks of such a model. The gradient flowing in from the rest of the network is frozen, the clean activations are cached, and the perturbation's effect is propagated through each linear recurrence additively. This move does not exist in prior work. It also yields a sharp prediction: the existing first-layer version of this idea (YOPO) does nothing useful on these models, because a frozen gradient on a purely linear first layer makes the inner search collapse to a single sign step. The method we propose instead places the frozen gradient after the first nonlinearity. In data-dependent models such as Mamba, that point sits right after the input-dependent discretization, which theory flags as the fragile component. The cheap multi-step search therefore spends its effort exactly where single-step attacks are thought to miss.

Core Claim

YOPO (You Only Propagate Once) treats a network as a discrete dynamical system and observes that the input perturbation couples directly only to the first layer. It runs one full pass, freezes the gradient of the loss with respect to the first layer's output (call it $p$), and then updates the perturbation several times through the first layer alone. On CIFAR-10 with a Wide ResNet-34 it reports 47.98% robust accuracy under PGD-20, against 47.04% for PGD-10 training, at about a 4x speedup. YOPO's authors flag the method's dependence on a cheap first layer as a limitation. Exploring Adversarial Robustness of Deep State Space Models ran YOPO and Free-AT on S4, DSS, S5, Mamba and Mega, but treated them as black boxes. It does not analyze where the frozen gradient should sit in a recurrent architecture.

Our claim is that, in a linear recurrent block, the right cut point is determined by where the first nonlinearity occurs, and that the linearity of the recurrence makes a deeper cut cheap. Write the first $k$ blocks as $g_k$ and the frozen adjoint at their output as $p_k$. If the first block's input-to-recurrence map is a time-invariant linear operator $K_1$, the operator realized by a linear recurrent unit's diagonal scan, then the first block's pre-nonlinearity activation satisfies

$$z_1(x+\delta) = z_1(x) + K_1 \delta,$$

where $z_1(x)$ is cached from the clean pass. The inner ascent direction is then

$$\nabla_\delta \langle p_k, g_k(x+\delta)\rangle = K_1^{\top}\, J(\delta)^{\top} p_k,$$

where $J(\delta)$ is the Jacobian of everything between $z_1$ and the cut, evaluated at the current perturbation. $K_1^{\top}$ is the same diagonal recurrence run backward in time with conjugated eigenvalues. It is therefore a reverse parallel scan with $O(\log L)$ depth over sequence length $L$.

Two consequences follow. First, if the cut sits at $z_1$ (YOPO's layer-1 cut), $J$ is the identity and the gradient no longer depends on $\delta$. The $\ell_\infty$ inner maximum is then exactly $\epsilon\,\mathrm{sign}(K_1^{\top}p)$, and all of YOPO's inner iterations reduce to one FGSM step. That is a testable explanation for why layer-1 decoupling would add nothing on these models. Second, if the cut sits after the first pointwise nonlinear layer or a few blocks deeper, each inner step costs one forward scan of the update $K_1\Delta\delta$, the pointwise layers, and one reverse scan. That is roughly $k/D$ of a full pass for a $D$-block model.

For Mamba-style models, where the transition $A_t$ is computed from the input, $z_1$ is no longer linear in $\delta$, and the input-dependent step size lies inside the cheap region. Qi et al. show that this data-dependent discretization can become ill-conditioned under worst-case inputs. Our block-local search is a multi-step adversary aimed at precisely that mechanism, and its cost does not scale with depth.

Research Program

We will build the method, which we call block-local adversarial training, on two model families. The first is a linear recurrent unit stack following Resurrecting Recurrent Neural Networks for Long Sequences: diagonal complex eigenvalues $\lambda = \exp(-\nu + i\theta)$ followed by position-wise gated layers. This is the time-invariant case where the identities above hold exactly. The second is a Mamba-style data-dependent model, where the cheap region contains the input-dependent discretization.

The implementation caches the clean activations of blocks $1..k$, freezes $p_k$ from one full pass, and runs $n$ inner steps through the cheap region. The forward and reverse scans reuse the model's existing scan kernel. Every $r$ inner steps it refreshes $p_k$ with a full pass, and it then performs one weight update on the final perturbation. As in YOPO, the weight gradients accumulated during the inner steps are also used. The schedule variables are the cut depth $k$, the number of inner steps $n$, and the refresh interval $r$.

The analytic part of the work will verify the layer-1 collapse, both formally and numerically. It will also characterize how the alignment between the frozen-adjoint ascent direction and the true full-network gradient decays with $k$ and $n$. That alignment is the quantity that decides whether the cheap inner steps are worth their cost.

The scan-as-backprop view of Scaling Back-propagation by Parallel Scan Algorithm supplies the method's computational premise: an adjoint through a linear chain is itself a scan. We use that only for the recurrence's transpose and do not adopt its sparse-Jacobian machinery. Sequential Parallel Duality in Prefix Scannable Models motivates a possible later extension to scannable attention, but the Transformer-PSM model is out of scope here.

Baselines

The naive reference point is standard training with no adversary, at 1x cost. It fixes clean accuracy and the floor for robust accuracy. We will also report plain PGD evaluation of these models, which Towards Evaluating the Robustness of Visual State Space Models suggests will be near collapse for scanned vision models, particularly under high-frequency perturbations.

The robustness ceiling is multi-step PGD adversarial training (PGD-10) on the same architectures. It is the most expensive method, and it is the one that cheap methods try to match. The strongest cheap competitor is Fast-AT from Fast is better than free: one FGSM step from a uniform random start, with a cyclic learning rate and early stopping on a PGD validation set. On 2D CIFAR-10 that paper reports 45% robust accuracy against PGD in 6 minutes. We also include Free-AT from Adversarial training for free!, which reports about 46% under PGD-20 on CIFAR-10 in about 13 hours, and YOPO with its original layer-1 cut. Those CIFAR numbers come from convolutional networks. For S4, DSS, S5 or Mamba under PGD-AT, Free-AT or YOPO we found no reported raw accuracy numbers on Lacuna, so every baseline will be rerun here. Qi et al. report only relative gains for their Adaptive Scaling module: more than 3% clean and more than 2% robust accuracy on S4 and DSS, and +4.1% clean / +3.97% robust for DSS under TRADES.

For fairness, all methods share the same architecture, data, and $\epsilon$. Each method gets the same hyperparameter-search budget, measured in GPU-hours, over its own step size and schedule. Comparisons are reported both at matched epochs and at matched wall-clock. The Adaptive Scaling module is architectural and orthogonal to the training method, so it is applied to every method in a secondary run instead of being treated as a competitor.

The key ablation compares cut depth $k=0$, the linear cut, with $k\geq 1$. If $k=0$ performs like Fast-AT and $k\geq 1$ does better, then placing the cut after the first nonlinearity is the active ingredient. A second ablation removes activation caching and incremental scan updates. This isolates how much of the speed comes from linearity rather than from simply truncating depth.

We count the method as beating the baselines if it meets two conditions on at least two benchmarks. First, it matches PGD-10 robust accuracy to within one point at no more than a third of PGD-10's wall-clock. Second, it exceeds Fast-AT's robust accuracy at no more than 1.5x Fast-AT's cost, with no catastrophic-overfitting collapses in runs where Fast-AT collapses.

Why not just…?

Why not just use Fast-AT? This is the real threat. Fast-AT already costs about two passes per update, so no method can be much cheaper than it, and its random start may suffice for time-invariant models. Our layer-1 analysis even predicts that, for those models, a linear-cut adversary is equivalent to an FGSM-type step. The case for our method therefore rests on two measurable claims: deeper cuts reduce catastrophic overfitting across learning rates and step sizes, and on data-dependent models multi-step block-local search finds discretization-driven failures that a single step misses. We will test the first claim by sweeping step sizes over five seeds and counting collapses. We will test the second by comparing the conditioning of the step-size and transition values under Fast-AT and block-local perturbations. If Fast-AT matches us on the linear recurrent unit, we will report the method as useful only for data-dependent models.

Why not just use off-the-shelf Free-AT or YOPO? Qi et al. already ran both on state-space models, and pure models still hit the error floor their theory predicts. That establishes that running these methods unchanged does not fix the architectural weakness. For YOPO specifically, our analysis predicts that its inner loop is redundant on linear first layers. The $k=0$ ablation tests this directly. Free-AT's minibatch replay also lowers clean accuracy as the replay count grows, and we will measure that cost on long sequences.

Why not just add attention or Adaptive Scaling instead of changing the training method? Qi et al. report that adding attention, as in Mega, produces a 40% gap between training and test robust accuracy. Attention also brings back quadratic cost. Adaptive Scaling is cheap, but it changes the architecture, not the cost of training. We therefore treat it as complementary and test whether its gains add to ours.

Proposed Experiments

The primary benchmarks are the sequential-image tasks used by Qi et al.: sequential MNIST, sequential CIFAR-10, and flattened Tiny-ImageNet. These allow direct comparison with their setting. To test the regime where sequence length makes cost matter, we add the continuous-pixel tasks from Long Range Arena. These are Image (1,024 to 3,072 steps), Pathfinder (1,024 steps), and Path-X (16,000 steps), on which the linear recurrent unit reports 94.2% clean accuracy. We use $\ell_\infty$ perturbations on pixels. Evaluation uses PGD-50 with several random restarts, plus an adaptive attack that targets the step-size values of the data-dependent model.

The metrics are clean accuracy, robust accuracy, wall-clock time and pass count to a target robust accuracy, the gap between training and test robust accuracy, and the rate of catastrophic overfitting across seeds. The decisive checks are three. The first is whether robust accuracy rises from $k=0$ to $k\geq1$ at nearly constant cost. The second is whether the cosine alignment between the frozen-adjoint and true gradients predicts that gain. The third is whether, on Path-X, the method's time to reach PGD-10's robust accuracy grows more slowly with $L$ than PGD-10's own training time. A negative result on the first check would refute the core claim.