Many associative memories, meaning systems that recover a whole stored pattern from a partial or noisy cue, retrieve by solving a linear system. Examples are covariance-based predictive coding memories, delta-rule memories, and the recurrent state of linear-attention layers. Each time a new pattern is written, the matrix being "inverted" changes. Today an implementer has three choices. They can re-invert exactly after every write. They can let recurrent dynamics settle, which uses only multiplications but needs many steps. Or they can use a fixed-depth multiplication-only approximation. Elliptic-curve cryptographers faced the same choice decades ago. Their answer was to measure the inversion-to-multiplication cost ratio ($I/M$) on the actual hardware and decide when to defer the expensive inversion and absorb extra multiplications in its place. We propose to bring that discipline to associative memory. The schedule keeps an exact inverse as a checkpoint, corrects it between refreshes with cheap multiplication-only terms, and refreshes it only when the accumulated "multiplication tax" exceeds one inversion.
The core claim has two parts. For memories that are written online, the best refresh period follows a square-root law in the measured matrix-level $I/M$ ratio. The second part is specific to pattern completion, unlike general linear algebra: retrieval only has to land the state in the correct basin of attraction, not reach the exact fixed point. As a result, the number of correction terms needed is set by how well separated the stored patterns are, not by the matrix's condition number. If both hold, retrieval on matmul-heavy accelerators becomes markedly cheaper with no loss in completion accuracy. The schedule would also adapt by rule across hardware whose $I/M$ ratios differ, as CPUs, GPUs and mobile neural processing units (NPUs) do.
Where the idea comes from
The cryptographic side supplies the method. Projective coordinates defer the one modular inversion of a long point computation to the end, and pay extra multiplications at every step to do so. The engineering literature shows this is only a good trade when $I/M$ is high. Affine Pairings on ARM measured base-field $I/M$ of about 10.67 on a Cortex-A9 against 25.00 on x86-64. At the lower ratio, affine pairings beat projective ones (about 51 ms against over 55 ms on bn254). Batching 20 pairings with Montgomery's shared-inversion trick cut the per-pairing cost to 17 ms. An Analysis of Affine Coordinates for Pairing Computation shows the crossover moves with the field's structure, because tower-field inversion reduces to subfield multiplications plus a single base inversion.
The smart-card design in Implementing an efficient elliptic curve cryptosystem over GF(p) on a smart card uses mixed coordinates: base points are stored in the inversion-paid form, and the inner loop runs inversion-free. That is exactly the pattern we reuse. Our exact checkpoint inverse plays the role of the stored affine point, and the multiplication-only corrections play the role of the projective inner loop. We do not use curve arithmetic itself. The research file's Gap 1, pattern completion over curve point groups, conflicts with discrete-log hardness, and we set it aside.
On the memory side, three lines of work motivate or constrain the design. Recurrent predictive coding models for associative memory employing covariance learning stores patterns in a covariance/precision structure. It found that the explicit version, which inverts covariance directly, is numerically unstable on structured images. The implicit and dendritic versions avoid explicit inversion by letting recurrent dynamics settle, and they give stable retrievals. This is a constraint: naive exact inversion fails. It is also a motivation, because settling dynamics are an untuned multiplication-only inverse whose step count nobody has budgeted.
When Good Enough Is Optimal is the closest prior work. In Gated DeltaNet, a delta-rule associative state, it replaces sequential triangular inversion with a truncated Neumann series. A Neumann series approximates an inverse as $I + A + A^2 + \dots$, using only multiplications. The paper reports a 5.2× kernel speedup on 32×32 blocks and an 18.1–24.6% layer-level cycle reduction on a Snapdragon 8 Elite NPU, with essentially no accuracy loss. That work fixes truncation depth once, inverts afresh for every chunk, and never reuses an inverse across writes. We differ in three ways. We carry an exact inverse across many writes and correct it. We choose refresh period and correction depth from a measured $I/M$ ratio. And we tie depth to basin margin rather than to approximation error.
Hopfield-Fenchel-Young Networks shows sparse retrieval maps achieve exact retrieval in one iteration when the stored patterns are separated by enough margin. This supplies the theoretical hook for our margin-controlled depth claim.
Core Claim
Let $P_0^{-1}$ be an exact inverse computed at the last refresh, and let $\Delta_t$ be the sum of the $t$ low-rank writes since then. The corrected inverse is the truncated series
$$(P_0+\Delta_t)^{-1} \approx \sum_{j=0}^{k} (-P_0^{-1}\Delta_t)^{j} P_0^{-1},$$
which uses multiplications only. Here $k$ is the number of correction terms. Staleness $\|P_0^{-1}\Delta_t\|$ grows roughly linearly in $t$, so the depth needed grows with $t$. Suppose $q$ queries arrive per write and the cost per query is roughly proportional to staleness. Then one refresh period of length $T$ costs about $I + qMT^2/2$, where $I$ and $M$ are the measured costs of one inversion and one matrix multiply. Minimizing the cost per write gives
$$T^\ast = \sqrt{2I/(qM)}.$$
This is the square-root law, and it is the first falsifiable prediction. The second prediction is that the depth $k$ needed for correct completion is set by the separation margin of the stored patterns. Retrieval only has to put the state on the right side of the basin boundary, after which a nonlinear readout can snap it to the stored pattern. So $k$ should stay small, nearly flat in $t$, for well-separated memories. That would push $T^\ast$ well beyond what an approximation-error criterion would choose.
Research Program
We will build a single testbed of linear-solve associative memories under streaming writes. It includes Gaussian covariance memories, implicit covariance predictive coding networks, and delta-rule memories of the Gated DeltaNet type at chunk sizes 32 and 64. All are queried with occluded or noise-corrupted cues and followed by an optional sparse readout of the entmax/sparsemax kind.
First, we will measure matrix-level $I/M$ directly on a desktop CPU, a datacenter GPU and, if accessible, a mobile NPU, across dimensions 32 to 1024 and at fp32, bf16 and INT8. Here $I$ is a Cholesky or triangular solve and $M$ is a matmul of matching size. This is the cryptographic practice applied to a new operation.
Second, we will implement four retrieval strategies. The first refreshes exactly after every write; this is the "affine" policy. The second runs recurrent settling to a tolerance. The third uses fixed-depth Neumann as in Zhang et al. The fourth is the deferred-inverse schedule, with $T$ chosen by the square-root rule and $k$ chosen by a cheap margin estimate. The margin estimate is the gap between the top two readout scores, read off after each correction term.
Third, we will test the batching analogue of Montgomery's trick. All queries between refreshes share one checkpoint, so the inversion cost is amortized across a batch of retrievals. We will check whether early-exiting queries stall the batch, the risk flagged in the file's batching gap.
Baselines
The naive reference is a classical correlation (Hebbian outer-product) memory in the style of the Associatron, which needs no inversion. Alongside it we run "never refresh," which keeps the initial inverse forever. Together these show how much accuracy the covariance structure buys at all. It counts as beaten if the deferred schedule gives higher completion accuracy at equal or lower wall-clock cost.
The strongest inversion-handling competitor is the fixed-depth multiplication-only Neumann method of When Good Enough Is Optimal. Its reported 5.2× kernel speedup over forward substitution at 32×32 is the bar for speed claims. We will rerun it on the same memories, hardware and precision, sweeping its depth from 2 to 16 under the same tuning budget as our two parameters. Beating it means a lower measured cost per retrieval at matched completion accuracy, or higher accuracy at matched cost.
The strongest accuracy competitor that avoids inversion entirely is a sparse modern Hopfield memory (On Sparse Modern Hopfield Model) and its Fenchel-Young generalization (Hopfield-Fenchel-Young Networks). On a synthetic bit-pattern task at bag size 300, the sparse model kept about 99.7% accuracy where dense softmax fell to about 52.8%. HFY reports zero retrieval error on corrupted MNIST/CIFAR-10 where standard modern Hopfield networks retained residual error, though the file gives no numeric figure for that. These run on identical stored sets and cues.
We also run the implicit covariance predictive coding network settled to convergence. No reported numerical result was found on Lacuna for its retrieval error; the paper describes "visually perfect" retrievals.
Two ablations isolate the key ingredients. The first replaces margin-controlled depth with error-controlled depth, which tests the basin claim. The second replaces the square-root refresh rule with refresh periods tuned once on CPU and carried unchanged to other hardware, which tests whether $I/M$-awareness matters.
Why not just…?
Why not just factor once and reuse the factorization? For a static memory, this is correct and our method reduces to it. The question only arises when writes arrive online, as in continual learning or in a recurrent state updated every chunk. There, a stale factorization degrades retrieval, and the "never refresh" baseline measures exactly how much.
Why not just use fixed-depth Neumann as in the Gated DeltaNet work? This is the real threat. If the accuracy needed for completion is reached at small fixed depth for every staleness level, then reusing the checkpoint adds nothing. The depth-versus-staleness curves will settle it. If the accuracy-sufficient depth is flat in $t$ even without a checkpoint, we will report that Zhang et al.'s method already captures the gain. That would narrow our contribution to the hardware-adaptive choice of depth.
Why not drop covariance memories and use sparse Hopfield retrieval? If sparse Hopfield retrieval matches covariance memories on structured, correlated images, the inversion question becomes moot for those tasks. We therefore report accuracy before cost. We expect covariance memories to help most on correlated pixel data, where predictive coding work motivates precision weighting. We concede the point on any benchmark where they do not.
Proposed Experiments
Retrieval uses MNIST and grayscale CIFAR-10, as in the covariance predictive coding and HFY evaluations. Patterns are written in a stream of 1,000 to 10,000. Queries carry 25–75% occlusion or Gaussian noise, and the query-to-write ratio $q$ varies from 0.1 to 100. The metrics are exact-retrieval rate, pixel MSE, measured wall-clock time and energy per retrieval, and peak memory. Peak memory matters because the smart-card literature shows extra stored state is itself a cost.
The decisive checks are three. First, the empirical optimal refresh period should scale as $\sqrt{I/(qM)}$ across hardware and $q$. A slope far from one half on a log-log plot falsifies the cost model. Second, the depth needed for exact retrieval should track margin rather than condition number. We will vary the two independently by controlling pattern correlations. Third, an $I/M$-aware schedule should transfer across devices without retuning, while CPU-tuned constants degrade on the NPU. This mirrors the ARM-versus-x86 reversal seen in pairings.
A final transfer test inserts the deferred-inverse schedule into Gated DeltaNet chunk recurrence. We report WikiText perplexity against the Neumann baseline, which reported virtually no perplexity degradation, at matched cycle budgets.
References
- Affine Pairings on ARM
- An Analysis of Affine Coordinates for Pairing Computation
- Implementing an efficient elliptic curve cryptosystem over $GF(p)$ on a smart card
- Recurrent predictive coding models for associative memory employing covariance learning
- When Good Enough Is Optimal: Multiplication-Only Matrix Inversion Approximation for Quantized Gated DeltaNet
- Hopfield-Fenchel-Young Networks: A Unified Framework for Associative Memory Retrieval
- Information Processing Using a Model of Associative Memory
- On Sparse Modern Hopfield Model