SMat-Attention: Structured Long-Context Sequence Modeling

• Softmax attention offers token-level access at quadratic prefill and linear cache cost, while fixed-size recurrent states constrain long-context associative recall.Source: §1 · pp. 1–2
• SMat-Attention uses finite-field point-hyperplane incidence masks whose row-support VC dimension d controls long-range access; d = 1 recovers ordinary causal masking.Source: §1 · p. 2
• Chunkwise forward and backward algorithms compute the dense causal mask in O(T^(2-3/d) + T) work, linear for d ≤ 3.The prescribed mask has Θ(T^2) nonzero entries.Source: §1 · p. 2
• After a fixed distant prefix, decoding takes T-independent work per token with O(T^(1-1/d)) cached states.Source: §1 · p. 2
• Learned Mamba-2 and Gated DeltaNet extensions improve mean recall accuracy over native backbones in several tested settings and remain competitive on small-scale PG-19.Their learned four-read selector adds Θ(T^(2-1/d)) prefill work and O(T^(1-1/d)) work per decoded token.Source: §1 · p. 2

• Masked kernel attention normalizes the product of a mask and query-key kernel weights before applying those weights to values.Source: §2 · pp. 2–3
• With a finite nonnegative feature factorization, augmenting values with a constant coordinate carries the normalizer alongside the numerator, so mask components can be computed separately and summed before division.Source: §2 · p. 3
• A mask's VC dimension is the largest number of keys shattered by its row supports; causal prefixes have VC dimension 1, while an unconstrained T-row mask can reach floor(log T).Source: §2 · p. 3

3.1 CHUNKWISE SMAT-ATTENTION

• Chunkwise SMat-Attention takes O(T^(2-3/d)+T) work despite dense masks, and its backward pass has the same asymptotic cost.The chunkwise theorem assumes a nonnegative feature factorization and positive normalizers.Source: §3 · p. 3, §3.1 · pp. 5–6

3 SMAT-ATTENTION

• M(d) is causal and dense with Θ(T^2) nonzeros, has VC dimension d, and reduces to ordinary causal masking at d=1.Source: §3 · p. 4

3.1 CHUNKWISE SMAT-ATTENTION

• Implicit incidence tabulation costs O(T^(2-3/d)rp) work and uses O(T^(1-1/d)rp) words under the prescribed scaling.The algorithm pools distant states by profile, aggregates profiles into type states, and reuses each type state for queries of that type.Source: §3.1 · pp. 4–5

3.2 GATING

• Continuous gating preserves M(d)'s support and does not change training or decoding complexity.The key gate is already incorporated in the state written for each key.Source: §3.2 · p. 6

3.3 MEMORY-EFFICIENT DECODING

• After processing a fixed distant prefix, decoding takes O(rp) work per token from O(T^(1-1/d)rp) cached words, independent of T.The decoder keeps the distant type cache and one running state for recent tokens.Source: §3.3 · p. 6

3.4 RECURRENT ARCHITECTURES AND LEARNED ROUTING

• Learned routing extends profile memories to recurrent models, with a query-dependent selector choosing four types per head for summary reads.A learned hash assigns write profiles, while the selector learns which summaries to retrieve.Source: §3.4 · p. 7
• Learned selection scores Θ(T^(2-1/d)) cached-type candidates across the sequence, remaining subquadratic for fixed finite d≥2 and fixed model dimensions.The linear-time bound for d≤3 applies to hard routing, not learned selection.Source: §3.4 · p. 7

Experimental setup

• Controlled synthetic evaluations probe whether masks realize subset-selection patterns over resampled landmark payloads and whether content-based retrieval can recover multiple requested items from variable locations without fixed positional routing.Source: §4 · p. 8

Multi-key retrieval

• On multi-key retrieval, exact routing-pattern match improves at higher k as d increases.Table 1 reports exact-match percentages by marked-position count k, with resampled payloads and a three-seed mean.Source: Table 1 · p. 8

Multi-query associative recall

• For MQAR, SMat variants perform well at every tested width on both Mamba-2 and Gated DeltaNet.Table 2 reports final accuracy after 32 epochs as a three-seed mean and standard deviation.Source: §4 · p. 8, Table 2 · p. 9

Joint Context–Key Recall

• On joint context–key recall, d = 3 has the highest mean accuracy and lowest sample standard deviation among tested SMat settings on both backbones, outperforming native backbones in mean accuracy.It scores above Log-Linear on Gated DeltaNet and below it on Mamba-2.Source: §4 · p. 9, Table 3 · p. 9

Natural Language Modeling

• Across 16K and 32K contexts, SMat variants achieve slightly lower NLL than similarly sized Mamba-2; at larger scale, their perplexity is roughly the same as the baselines.The larger-scale PG-19 runs use 16-layer models, a 16K context, and 750M training tokens.Source: §4 · p. 9

Conclusion

• SMat-Attention uses VC dimension d to control long-range routing richness, with provably subquadratic training and constant-time decoding for hard-routing masks.Learned extensions inherit these bounds up to a subquadratic selector term.Source: §5 · p. 9

Future work

• The analysis focuses on structured finite features and fixed-horizon decoding; adaptive routing, dynamic contexts, and larger-scale language models remain future directions.Some empirical variants already add learned routing and memory updates.Source: §5 · p. 9

AI use

• Generative AI tools assisted literature searches, coding, results presentation, manuscript editing, figure design, and validation of mathematical claims.The authors state that AI assistance was used in these research and writing activities.Source: AI USE STATEMENT · p. 10

Author responsibility

• The authors take full responsibility for verifying the correctness and originality of the manuscript’s material.This responsibility includes theoretical claims, results, code, and figures.Source: AI USE STATEMENT · p. 10

Evaluation scope

• The evaluation uses synthetic tasks and the PG-19 corpus to measure long-range context processing in language models.The work studies tradeoffs among memory, expressiveness, and computation across attention representations.Source: ETHICS STATEMENT · p. 10

Risks

• The proposed models retain standard language-model bias, privacy, and misuse risks; attention alone provides no safeguard against them.The statement also notes that efficiency gains may lower the cost of processing potentially sensitive text.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

• Section 3 specifies the mask construction and attention algorithms, including forward-pass pseudocode and implicit incidence tabulation.Proofs of theoretical claims are in Appendices C–F.Source: REPRODUCIBILITY STATEMENT · p. 10
• Section G describes the experimental tasks, datasets, synthetic-data generation, model configurations, training, evaluation, and computing hardware.Source: REPRODUCIBILITY STATEMENT · p. 10
• The paper provides an anonymous link to the implementation and documentation for running the experiments.Source: REPRODUCIBILITY STATEMENT · p. 10

A BROADER IMPACTS

• SMat-Attention may lower deployment energy and hardware requirements, while cheaper processing also lowers barriers to handling sensitive text and retains language-model risks.The paper also describes its explicit access-complexity parameter as a possible aid to analysis of retrieval and information use.Source: A BROADER IMPACTS · p. 15

B RELATED WORK

• Fixed-size recurrent attention states offer efficient inference but create a capacity–recall tradeoff when tasks require access to many independent context items.Kernelized attention permits finite-dimensional recurrent states; SMat-Attention instead changes the causal support over which supplied finite nonnegative features interact.Source: B RELATED WORK · pp. 15–16
• Efficient sequence models exploit structure in their mixing matrices, including lower-triangular, Toeplitz-like, and input-dependent semiseparable forms.Structured state-space duality relates SSM recurrences to semiseparable matrix multiplication, while masked finite-feature attention extends to several mask families.Source: B RELATED WORK · pp. 15–16
• Log-Linear Attention uses O(log T) dyadic-bucket summaries; SMat-Attention instead uses overlapping geometric access patterns and guarantees T-independent decoding after a fixed, known distant prefix.The stated SMat cache uses O(T^(1−1/d)) feature states.Source: B RELATED WORK · p. 16
• VC dimension measures set-system richness, and prior matrix-vector results motivate using it to quantify access complexity.The paper says its point–hyperplane incidence construction obtains a sharper specialized algorithm.Source: B RELATED WORK · p. 16
• SMat-Attention’s mask is dense, so its speedup comes from reuse across shared profiles and query types, not simply from deleting edges.The method combines intrachunk computation with algebraic reuse; for d ≥ 3 its hyperplane routing yields structured unions of cells rather than single hash or cluster buckets.Source: B RELATED WORK · p. 16

C AUXILIARY LEMMAS

• For a mask with matrix-vector multiplication cost fM(T), the auxiliary lemma gives general masked kernel attention work O((fM(T) + T)rdv).Source: C AUXILIARY LEMMAS · p. 17

D VC DIMENSION OF THE CAUSAL INCIDENCE MASKS

• Affine hyperplanes in Fq^D have VC dimension exactly D, with the standard basis shattered by witness hyperplanes over every finite field.The proof shows each basis vector belongs to a witness hyperplane exactly when its index is in the selected subset.Source: D VC DIMENSION OF THE CAUSAL INCIDENCE… · pp. 17–18
• Theorem 3.1 establishes that M(d) is causal, has unit diagonal, recovers the lower-triangular mask at d = 1, and has VC dimension d despite Θ(T^2) nonzeros.Source: D VC DIMENSION OF THE CAUSAL INCIDENCE… · p. 18
• The mask’s VC upper bound follows by separating recent and distant columns: recent supports are nested prefixes, while distant-row supports are also prefixes.Affine dependence rules out excessive shattering by recent rows, and the nested distant supports cannot realize the required incomparable traces.Source: D VC DIMENSION OF THE CAUSAL INCIDENCE… · pp. 18–19
• The lower bound selects d landmark columns whose profiles are basis vectors and uses witness hyperplanes to realize every subset of those columns.Source: D VC DIMENSION OF THE CAUSAL INCIDENCE… · p. 19
• For k = 4 positively weighted reads, the cross-block mask has VC dimension at most 25D − 1, and the full mask’s dimension is bounded by the cross-block dimension plus two.Source: D VC DIMENSION OF THE CAUSAL INCIDENCE… · p. 19
• The complexity bounds depend on the prescribed field-size scaling: fixed q keeps the number of profiles fixed as T grows, whereas the chosen scaling grows profile and type tables.Other q choices can preserve mask VC dimension while changing profile-cell counts, token sharing, and computational cost.Source: D VC DIMENSION OF THE CAUSAL INCIDENCE… · p. 19

E CHUNKING PROOFS

• Theorem 3.2 gives chunkwise attention computation under a nonnegative finite-feature factorization and positive normalizers, with matching asymptotic cost for the backward pass.The forward bound combines O(T^(2−3/d)rp) tabulation with O(Trp + Tc(r + p)) remaining work.Source: E CHUNKING PROOFS · pp. 20–21
• Profile and type reuse reduces tabulation work to O(T^(2−3/d)rp) by collapsing repeated query types and key profiles.Each collapsed incidence contributes a state addition; the three reductions each save a factor Θ(T^(1/d)).Source: E CHUNKING PROOFS · pp. 20–21
• Pooling, per-type contractions, chunk summaries, and scans take O(Trp), while local dense tiles add O(Tc(r + p)) work.Source: E CHUNKING PROOFS · p. 21
• The backward pass reverses the grouped reductions and broadcasts, while chunkwise causal tiles and prefix scans have corresponding adjoints.The proof states each backward step matches the forward step’s arithmetic shape.Source: E CHUNKING PROOFS · pp. 21–22
• Scalar per-token gates preserve the stated complexity bound and require O(T) additional space.Source: E CHUNKING PROOFS · p. 22
• The stated gated lemmas cover additive kernel attention with optional scalar decay, not the delta-rule recurrence used in the Gated DeltaNet extension.Source: E CHUNKING PROOFS · p. 22

Fixed-horizon decoding

• With fixed total length T known in advance, decoding after the distant block takes O(rp) time per token, independent of T, from O(T^1−1/drp) cached words.The bound assumes the hypotheses of Theorem 3.2 and that the distant/recent boundary is known.Source: F DECODING AND HORIZON-FREE DECODING · p. 23

Decoding algorithm

• After consuming the distant block, decoding aggregates profile memories into type summaries, discards intermediate profiles, and maintains one running state for recent tokens.For the scalar-gated variant, the recurrent state update is gated and the type-summary read uses a maintained scalar factor.Source: F DECODING AND HORIZON-FREE DECODING · p. 23

Horizon-free decoding

• The stepped-window mask fixes geometry from Tmax and advances its boundary in cdc-sized steps, so one mask supports any sequence length, including T > Tmax.Its recent window spans cdc to 2cdc tokens while older blocks continue to enter the incidence branch.Source: F DECODING AND HORIZON-FREE DECODING · p. 23, Figure 6 · p. 24

Length generalization

• For uniform-layout MQAR through eight times training length, the quarter-length window is the only schedule whose accuracy rises with evaluation length and whose spread does not.The rebuilt oracle ends at 81.8 against 51.9 for the kept boundary.Source: Table 5 · p. 26

Recall relative to the boundary

• At evaluation length 8192, the quarter-length window holds about 95% accuracy for gaps 256–3072 while the kept boundary falls to about 34%; at D = 0, it scores 27.1%.At D = 0 the fixed-boundary variants score 35.4% and 36.1%; the table notes that performance near the boundary depends on the window schedule.Source: Table 6 · p. 26

G TRAINING DETAILS AND ADDITIONAL RESULTS

• Every arm within a table shares its data order, schedule, and precision; runs use Adam-family optimization, gradient clipping at 1.0, and one GPU per run.Learning rates use warmup and cosine decay except for subset routing and multi-key subset recall, which use a constant rate.Source: G TRAINING DETAILS AND ADDITIONAL… · p. 27, Table 8 · p. 27

G.1 EXTENSION DETAILS

• The extensions fix the distant/recent boundary and geometry independently of token content, and use a short causal convolution to form write-side representations.The convolution uses zero padding and depthwise convolution with L = 4, allowing a write address to use nearby preceding content; later queries do not revise it.Source: §G.1 · pp. 27–28
• Learned write profiles use a discrete hash with jointly learned projection parameters and a straight-through estimator; each token writes to one profile, with a surrogate gradient during backpropagation.The geometric incidence matrix remains fixed, and the auxiliary balance loss discourages concentration in individual coordinate bins rather than requiring uniform joint-profile occupancy.Source: §G.1 · p. 28
• Queries use either a hyperplane through their hash point or a learned top-four selector, and both routing variants remain causal because summaries contain only earlier distant positions.The top-four selector receives gradients through selected scores but not through the selected indices; Mamba-2 uses additive memory updates, while Gated DeltaNet incorporates delta-rule transitions.Source: §G.1 · pp. 28–29

Subset routing

• Subset-routing exact-pattern match improves at higher k as d increases; the table reports T = 1024, one layer, 1500 steps, and means over three seeds.Payloads are resampled each batch and evaluation uses fresh payloads.Source: Table 9 · p. 30

End-to-end cost

• From 16K to 64K, SMat training steps grow 3.7–4.3× versus 15.4× for softmax; prefill at 256K is 210–300× faster, and decoding is 51× faster.At d ≤ 3 the hard route is linear end to end; SMat prefill matches DeltaNet and is faster than Gated DeltaNet at 256K, while its unfused training is slower than optimized kernels.Source: §G.2 · p. 30, Table 10 · p. 31

Multi-key subset recall

• Multi-key subset recall scores exact-support match, and memory-matched linear attention tests whether SMat’s advantage is simply due to keeping a larger state.A query counts as correct only when the retrieved support equals the requested key set; all 54 linear-baseline runs finish within 0.0012 nats of the constant-prior loss.Source: §G.2 · p. 31
• Softmax outcomes are bimodal: runs that escape the constant-prior plateau reach at least 99%, while some seeds remain on the plateau within the 12K-step budget.The large standard deviations record whether runs escaped; other tested warmup and learning-rate settings did no better.Source: §G.2 · p. 32, Table 12 · p. 32
• When a linear head predicts the hyperplane direction from the query, SMat scores 99.9, 60.1, and 44.6% at d = 3 for k = 1, 2, and 3; at d = 4 it scores 100.0, 74.2, and 59.2%.The table’s SMat results instead use rule-chosen directions that select a shared hyperplane for requested keys when one exists; the baselines have no equivalent mechanism.Source: Table 11 · p. 31, §G.2 · p. 32

Learned Mamba-2–SMat recall

• On multi-key subset recall, baseline Mamba-2 scores zero exact-support accuracy; learned Mamba-2–SMat succeeds mainly at k = 1 for d = 2, improves k = 2 for d = 3, and is near-perfect across settings for d = 4.The reported pattern qualitatively matches the original multi-key recall results as geometric dimension increases.Source: §G.2 · p. 32, Table 14 · p. 32

Additional recall experiments

• The MQAR and joint context-key recall experiments use distinct retrieval setups and report evaluations across key–value loads or context-key configurations.MQAR uses the Zoology training mixture and held-out examples; joint context-key recall reports final-test accuracy averaged equally across five binding loads and three seeds.Source: §G.2 · p. 33, Table 15 · p. 33

Language modeling

• PG-19 is evaluated with per-token negative log-likelihood on 16K-byte windows, and each Table 16 model configuration uses a single training seed.The table caption identifies NLL after 300M tokens and validation perplexity after 750M tokens at 16K context; lower is better.Source: §G.2 · p. 34, Table 16 · p. 34