# Adaptive NGMRES for implicit neural inference

- ID: 898
- Canonical URL: https://synthcore.org/idea/898/adaptive-ngmres-for-implicit-neural-inference
- API JSON: https://synthcore.org/api/idea/898.json
- API Markdown: https://synthcore.org/api/idea/898.md
- Verification status: unverified
- Source: [arXiv:2607.14268](https://arxiv.org/abs/2607.14268)
- Category: dynamics
- Solves: speedup, stability
- ML areas: ssm, inference-speedup, training-dynamics
- Math tags: optimization, dynamical-systems, linear-algebra, numerical-analysis
- Ratings: usefulness 6/10; difficulty 5/10; novelty 4/10

## Idea description

Replace the plain fixed-point iteration of an implicit neural layer with nonlinear GMRES residual minimization over a short history of iterates. Use the measured residual reduction from each least-squares problem to increase depth when acceleration is effective, and restart or reduce depth when the predicted gain disappears.

## Mathematical statement

The paper's NGMRES update is $x_{k+1}=q(x_k)+\sum_{i=0}^{m_k}\beta_i^{k+1}(q(x_k)-x_{k-i})$, where $q$ is the fixed-point map, $x_k$ is the current iterate, $m_k=\min\{k,m\}$ is the available history depth, and $\beta_i^{k+1}$ are obtained by minimizing the norm of a linear combination of residual differences. For a neural fixed point, define $g(x)=q(x)-x$ and $r_k=g(x_k)$. The residual-minimization problem is $\beta^*=\arg\min_\beta\left\|g(q(x_k))+\sum_{i=0}^{m_k}\beta_i[g(q(x_k))-g(x_{k-i})]\right\|_2$. Define the empirical residual ratio $\rho_k=\|r_{k+1}\|_2/(\|r_k\|_2+\epsilon)$ and ratio gain $G_k=\rho_k^{\mathrm{plain}}-\rho_k^{\mathrm{NGMRES}}$, where $\rho_k^{\mathrm{plain}}=\|g(q(x_k))\|_2/(\|r_k\|_2+\epsilon)$. The paper identifies this least-squares gain as the acceleration mechanism and shows that the linear convergence factor predicted by the optimization problem is at most one; consequently, persistent negative gain or residual growth can be used as a practical signal for restarting or damping.

## Key formulas

- $$x_{k+1}=q(x_k)+\sum_{i=0}^{m_k}\beta_i^{k+1}\left(q(x_k)-x_{k-i}\right),\qquad m_k=\min\{k,m\}.$$
- $$\beta^{k+1}=\arg\min_{\beta}\left\|g(q(x_k))+\sum_{i=0}^{m_k}\beta_i\left(g(q(x_k))-g(x_{k-i})\right)\right\|_2.$$
- $$\rho_k^{\mathrm{plain}}=\frac{\|g(q(x_k))\|_2}{\|g(x_k)\|_2+\epsilon},\qquad \rho_k^{\mathrm{NGMRES}}=\frac{\|g(x_{k+1})\|_2}{\|g(x_k)\|_2+\epsilon},\qquad G_k=\rho_k^{\mathrm{plain}}-\rho_k^{\mathrm{NGMRES}}.$$
- $$x_{k+1}\leftarrow (1-\alpha_k)q(x_k)+\alpha_k\left[q(x_k)+\sum_i\beta_i^{k+1}(q(x_k)-x_{k-i})\right],\qquad \alpha_k=\operatorname{clip}\left(\frac{\|g(q(x_k))\|_2}{\|g(x_{k+1}^{\mathrm{candidate}})\|_2+\epsilon},0,1\right).$$

## Implementation notes

(1) Integration point: apply this to the latent-state solve of an implicit layer or Deep Equilibrium model, rather than to ordinary feed-forward activations. Given parameters and input $u$, define the layer map $q_\theta(x;u)$ and solve $x=q_\theta(x;u)$ at inference time. After every map evaluation, store at most the last $m=5$ states and residuals in detached buffers to limit memory use.

(2) Pseudocode:
```text
x = x0
state_history = []
residual_history = []
for k in 0..K-1:
    y = q_theta(x, u)
    gy = q_theta(y, u) - y
    if len(state_history) == 0:
        candidate = y
    else:
        # Construct residual-difference matrix from stored states.
        A[:, i] = gy - residual_history[i]
        b = -gy
        beta = solve_least_squares(A, b, ridge=1e-6)
        candidate = y + sum_i beta[i] * (y - state_history[i])
    plain_residual = norm(y - x)
    candidate_residual = norm(q_theta(candidate, u) - candidate)
    if candidate_residual > plain_residual:
        x_new = y
        restart_history()
    else:
        x_new = candidate
    gain = plain_residual - candidate_residual
    update_history(x, x_new, y - x, gy)
    if gain is negative for two consecutive iterations:
        restart_history()
    elif gain is positive for two consecutive iterations and depth < 5:
        depth += 1
    x = x_new
```
The implementation should solve the paper's displayed least-squares problem directly using residual vectors $g(y)$ and $g(x_{k-i})$; use a small ridge term for rank-deficient history matrices. Recompute the candidate residual only for acceptance and controller decisions, and use damping $x_{k+1}=(1-\alpha)y+\alpha\,candidate$ if the undamped candidate is unstable.

(3) Compute the least-squares coefficients and residual-ratio gain exactly; no unknown theorem constants are needed. Estimate empirical quantities from residual norms: gain $G_k$, convergence ratio $\rho_k$, accepted history depth, restart frequency, damping frequency, number of fixed-point evaluations, and wall-clock time. Compare adaptive depth against fixed-depth NGMRES, Anderson acceleration, and plain Picard iteration.

(4) First cheap experiment: use a 2-4 layer Deep Equilibrium MLP on MNIST or CIFAR-10 with identical forward and backward tolerances. Measure iterations and wall-clock time to reach residual tolerance $10^{-5}$ while verifying unchanged classification accuracy. A successful result is at least 25% fewer fixed-point evaluations at equal accuracy, with no increase in failed or divergent solves. Also test a deliberately noncontractive initialization; the adaptive restart rule should produce a higher convergence rate than plain Picard iteration.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.