1 Introduction↩︎

A recurring theme in sequence modeling is the tension between parallel shortcut computation and recurrent state tracking. Shallow Transformers can simulate finite automata by composing transition functions in parallel [1], but shortcut solutions can be brittle under distribution shift and length extrapolation. Linear attention and gated recurrent attention move in the opposite direction: they maintain a fixed-size state that updates recurrently, which improves inference efficiency but constrains long-context retrieval and precise algorithmic memory.

Kimi Delta Attention (KDA) is a recent and strong example of this second direction. It maintains a matrix-valued memory state \[S_t=(I-\beta_t k_t k_t^*)\mathop{\mathrm{diag}}(\alpha_t)S_{t-1}+\beta_t k_t v_t^*, \label{eq:intro-kda}\tag{1}\] and obtains practical efficiency from a chunkwise WY-style representation of diagonal decay plus rank-one delta corrections [2]. KDA’s empirical success suggests a question that is both theoretical and systems-oriented:

Can we add algebraic phase/control dynamics to KDA-style recurrent memory without destroying the structured chunk kernel?

We answer this question for a restricted but hardware-friendly phase family. The proposed layer, Semidirect Fourier Delta Attention (SFDA), inserts a block-rotational control matrix before the delta correction. In real coordinates, \[S_t=(I-\beta_t k_tk_t^*)U_tD_tS_{t-1}+\beta_t k_tv_t^*, \label{eq:intro-sfda-real}\tag{2}\] where \(U_t\) is a direct sum of \(2\times2\) rotations and \(D_t\) is a positive block/diagonal decay. Under the identification \(\mathbb{R}^{2m}\simeq \mathbb{C}^m\), this becomes \[S_t=(I-\beta_t k_tk_t^*)\Lambda_tS_{t-1}+\beta_t k_tv_t^*, \qquad \Lambda_t=\mathop{\mathrm{diag}}(\alpha_t\odot e^{i\theta_t}). \label{eq:intro-sfda-complex}\tag{3}\] Thus the algebraic control is a learnable Fourier phase, while the delta correction remains rank one.

The nontrivial part is not the phase parameterization alone. If the phase-control matrix were dense, the kernel would collapse into dense \(d\times d\) products. The crucial design choice is to restrict \(U_tD_t\) to aligned \(2\times2\) rotation-decay blocks, equivalently a complex diagonal \(\Lambda_t\). Then every token transition has the form \[A_t=\Lambda_t-u_tw_t^*, \label{eq:intro-diag-rank-one}\tag{4}\] that is, phase-decay plus one rank-one delta correction.

1.0.0.1 Contributions.

This preprint formalizes the semidirect/Fourier automata idea as a theory-and-kernel framework for phase-controlled delta memory.

1. We define tied SFDA as the main architecture and a write-decoupled variant for exact automata constructions. KDA is recovered by setting \(U_t=I\), equivalently \(\theta_t=0\).

2. We prove that the phase-control part exactly implements bounded cyclic memory: rotations maintain modular counters and phase trackers with constant norm.

3. We prove a constructive left-to-right chunk-WY theorem. For \(P_t=A_tA_{t-1}\cdots A_1\) with \(A_t=\Lambda_t-u_tw_t^*\), the factors \(\Gamma_t,Y_t,M_t,W_t\) admit an explicit recursion. This is stronger than an existential closure theorem and is the main kernel theorem.

4. We prove an exact affine chunk transfer, including the additive write summary \[B_C=\sum_{i=1}^C A_{C:i+1}B_i,\] and show how to compute it by a zero-initial-state recurrence.

5. We characterize compact kernel-compatible expressivity inside a chunk: a length-\(C\) SFDA product is a structured phase/control product plus a rank-\(C\) correction. This proves compact exact realizations for product cyclic counters, dihedral phase-orientation memory, register/reset memories, and bounded stacks under the corresponding structured controls.

6. We give a reader-friendly finite-state theorem: every deterministic finite automaton is exactly realized by a generalized tied-write affine memory system after one-hot lifting. The construction sets the write coefficient to zero, so the erase-write coupling is not an expressivity obstruction for finite state machines. The remaining question is efficient compressed realization, not exact finite-state realizability.

7. We add an orbit-restricted tied-write compilation theorem. It shows when a decoupled write direction can be routed from a tied key using only the architecture’s structured control family, and it explicitly separates contribution routing from full-state compilation with scratch/protected channels.

8. We include the complex-to-real implementation, formal cost bounds, a numerical stability lemma, and a rank-growth discipline: rank grows only inside fixed chunks, not across the whole sequence.

The main empirical target is not merely to beat KDA on toy automata. The long-term systems target is to test whether the stronger SFDA linear layer can support a higher linear-to-global attention ratio, for example \(7{:}1\) or \(15{:}1\), while matching or exceeding a KDA-style \(3{:}1\) hybrid under equal compute.

2 Background↩︎

2.1 Automata, shortcuts, and recurrent memory↩︎

A finite semiautomaton \(\mathcal{A}=(Q,\Sigma,\delta)\) evolves by \[q_t=\delta(q_{t-1},\sigma_t),\qquad q_t\in Q,\;\sigma_t\in\Sigma.\] The per-symbol maps \(\delta(\cdot,\sigma)\) generate a finite transformation semigroup. Existing shortcut results show that Transformers can simulate any finite semiautomaton by parallel prefix composition in \(O(\log T)\) depth, and that some solvable semiautomata admit constant-depth shortcuts through Krohn–Rhodes-style decompositions [1]. However, those shallow shortcuts may fail to generalize to unseen lengths or shifted input distributions, motivating architectures with explicit recurrent state.

2.1.0.1 Finite automata as ordinary matrix recurrences.

No automata-theory background is needed for the finite-state expressivity theorem used later. If \(Q=\{q_1,\ldots,q_N\}\), encode state \(q_i\) by the one-hot vector \(e_i\in\mathbb{R}^N\). For each input symbol \(\sigma\), define a matrix \(P_\sigma\) by \[P_\sigma e_i=e_j\quad\text{whenever}\quad \delta(q_i,\sigma)=q_j. \label{eq:background-onehot}\tag{5}\] Then the automaton recurrence is exactly the linear recurrence \[s_t=P_{\sigma_t}s_{t-1}. \label{eq:background-linear-dfa}\tag{6}\] The matrices \(P_\sigma\) are deterministic one-hot transition matrices: each column has exactly one nonzero entry, but the matrix need not be invertible. For example, a reset transition can map many states to the same next state, so \(P_\sigma\) is not necessarily a permutation matrix. This elementary one-hot view is the only finite-automata fact required for the tied-write realization result in [sec:finite-state-main] [app:automata].

The algebraic object we use is a semidirect product \[N\rtimes H, \qquad (n_2,h_2)(n_1,h_1)=(n_2+h_2\cdot n_1,\;h_2h_1), \label{eq:semidirect-law}\tag{7}\] where \(H\) is a control group acting linearly on a memory monoid or vector space \(N\). This structure separates two operations: memory storage and control of how memory is transported.

2.2 KDA as affine recurrent memory↩︎

KDA updates a memory matrix \(S_t\in\mathbb{F}^{d\times d_v}\) by 1 . Abstractly, each token defines an affine map \[S\mapsto A_tS+B_t, \qquad A_t=(I-\beta_tk_tk_t^*)D_t, \qquad B_t=\beta_tk_tv_t^*, \label{eq:affine-token}\tag{8}\] where \(D_t=\mathop{\mathrm{diag}}(\alpha_t)\). Affine maps compose by \[(A_2,B_2)\circ(A_1,B_1)=(A_2A_1,\;A_2B_1+B_2). \label{eq:affine-law}\tag{9}\] Thus scanability is mathematically immediate. The hard part is efficiency: dense products \(A_2A_1\) cost \(O(d^3)\), so a useful architecture must preserve a diagonal-plus-low-rank structure inside chunks.

KDA is efficient because \(A_t\) is diagonal decay plus a rank-one correction. Its chunkwise formulation stores a compact WY-like representation of the product and uses triangular solves or UT-style transforms to avoid dense matrix products [2], [3]. Our goal is to add phase/control dynamics while preserving this same structural invariant.

2.3 Relation to RoPE, SSMs, DPLR, and KDA↩︎

It is helpful to separate where rotations occur. Rotary positional embeddings rotate query/key features to encode relative position. SFDA instead rotates the recurrent memory transition itself: \[S_t=(I-\beta_tk_tk_t^*)\Lambda_tS_{t-1}+\beta_tk_tv_t^*.\] Thus SFDA phases are state-transition phases, not merely query/key positional phases.

SFDA differs from complex diagonal SSMs because it retains the delta-rule rank-one correction. It differs from KDA because the real diagonal decay is upgraded to complex phase-decay. It differs from unrestricted DPLR because the low-rank term is tied to the delta rule and therefore admits the constructive chunk-WY invariant.

2.4 Why arbitrary orthogonal control is not acceptable↩︎

A tempting extension is to replace \(D_t\) by a learned dense orthogonal matrix. That destroys the kernel: products of dense orthogonal matrices with rank-one corrections do not retain a cheap diagonal-plus-low-rank representation. We therefore restrict the control operator to block rotations \[U_t=\bigoplus_{j=1}^{d/2}R(\theta_{t,j}), \qquad R(\theta)= \begin{bmatrix} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{bmatrix}. \label{eq:block-rot}\tag{10}\] With paired channels interpreted as complex coordinates, \(U_tD_t\) is diagonal. This is the reason SFDA can add phase memory while retaining a KDA-like kernel path. The design is also aligned with the common interpretation of rotary positional encodings as products of \(2\times2\) rotations [4].

3 Semidirect Fourier Delta Attention↩︎

We now define the layer. Let \(x_t\in\mathbb{R}^{d_{\mathrm{model}}}\) be the token representation. For each head, projections produce \(q_t,k_t\in\mathbb{F}^d\), \(v_t\in\mathbb{F}^{d_v}\), a scalar step size \(\beta_t\in[0,1]\), channel-wise decay \(\alpha_t\in[0,1]^d\), and phase \(\theta_t\in[-\theta_{\max},\theta_{\max}]^d\) in complex coordinates. The main architecture in this paper is the tied SFDA recurrence \[\begin{align} S_t&=(I-\beta_tk_tk_t^*)\Lambda_tS_{t-1}+\beta_tk_tv_t^*, \label{eq:sfda}\\ \Lambda_t&=\mathop{\mathrm{diag}}(\alpha_t\odot e^{i\theta_t}). \nonumber \end{align}\tag{11}\] The output is \[o_t=S_t^*q_t.\] In real implementations, the complex multiplication by \(\lambda_{t,j}=\alpha_{t,j}e^{i\theta_{t,j}}\) is implemented by a \(2\times2\) rotation-decay block. No FFT is required.

3.0.0.1 Stable parameterization.

A simple implementation enforces the stability assumptions used later by \[\begin{align} \alpha_t&=\alpha_{\min}+(\alpha_{\max}-\alpha_{\min})\sigma(a_t),\qquad 0\le\alpha_{\min}\le\alpha_{\max}\le1,\tag{12}\\ \theta_t&=\theta_{\max}\tanh(b_t),\tag{13}\\ \beta_t&=\sigma(c_t),\tag{14}\\ k_t&=\tilde{k}_t/(\left\lVert \tilde{k}_t\right\rVert_2+\varepsilon).\tag{15} \end{align}\] Then \(\left\lVert \Lambda_t\right\rVert_2\le1\), \(0\le\beta_t\le1\), and \(\left\lVert k_t\right\rVert_2\le1\), so \(0\le\beta_t\left\lVert k_t\right\rVert_2^2\le1\).

3.0.0.2 Write-decoupled variant.

For controlled memory constructions it is sometimes useful to separate the erase direction from the write direction: \[S_t=(I-\eta_tk_tk_t^*)\Lambda_tS_{t-1}+\beta_tr_tv_t^*. \label{eq:sfda-decoupled-main}\tag{16}\] The tied model is recovered by setting \(r_t=k_t\) and \(\eta_t=\beta_t\). The main architecture and kernel theorems are stated for tied SFDA.

3.0.0.3 Generalized tied-write affine template.

The finite-state expressivity theorem in [sec:finite-state-main] [app:automata] uses a slightly more general proof template, \[z_t=(I-\beta_{\sigma_t}k_{\sigma_t}k_{\sigma_t}^*)\widetilde{A}_{\sigma_t}z_{t-1} +\beta_{\sigma_t}k_{\sigma_t}r_{\sigma_t}. \label{eq:general-tied-template}\tag{17}\] Here \(\widetilde{A}_\sigma\) is an unrestricted symbol-conditioned linear map. This template isolates the effect of tying erase and write through the same vector \(k_\sigma\). It is an expressivity proof model, not the hardware kernel. The kernel-compatible SFDA family restricts \(\widetilde{A}_\sigma\) to the phase-decay form \(\Lambda_\sigma\), which is what enables the chunk-WY recursion.

3.0.0.4 Single-step diagonal-plus-rank-one form.

The SFDA transition matrix in ?? can be written as \[A_t=\Lambda_t-u_tw_t^*, \qquad u_t:=\beta_t k_t, \qquad w_t:=\Lambda_t^*k_t. \label{eq:single-step-wy}\tag{18}\] Indeed, \(u_tw_t^*=\beta_tk_tk_t^*\Lambda_t\). This is the invariant that makes the structured kernel possible: diagonal/phase decay plus one rank-one correction.

4 Main Kernel Theorems↩︎

The kernel theorem has two layers. First, phase-decay plus low-rank correction is closed under composition. Second, for the single-step SFDA form \(A_t=\Lambda_t-u_tr_t^*\), there is an explicit left-to-right recursion for the factors. This turns the closure theorem into a constructive chunk algorithm.

4.1 Finite-state tied-write realization↩︎

The constructive WY theorem is a kernel result. Separately, the following theorem resolves the finite-state version of the tied-write expressivity concern. The statement is intentionally elementary: a finite automaton is just a machine with finitely many states, and one-hot vectors turn its state update into matrix multiplication.

4.2 Orbit-restricted tied-write routing↩︎

The one-hot theorem above uses unrestricted symbol-conditioned matrices \(\widetilde{A}_\sigma=P_\sigma\). This is useful for finite-state expressivity, but it is not yet a kernel theorem for the structured SFDA family. A sharper question is when the tied write direction can emulate a decoupled write direction while using only the control operators already available to the model.

Let \(k\) be a tied key and let \(\mathcal{G}\) be the structured control family, such as signed permutations, block rotations, or products of local rotations. The reachable write directions from \(k\) are its orbit \[\mathop{\mathrm{Orb}}_{\mathcal{G}}(k)=\{Rk:R\in\mathcal{G}\}.\] If a desired decoupled write direction \(w_\sigma\) lies in this orbit, then its write contribution can be routed from a tied write along \(k\). For a full affine update, one must also account for the erase term in the delta rule. The exact theorem in 16 states the needed protected-subspace condition: after the base transition, the carried memory must have zero projection onto the tied key. Under that condition, a tied write followed by the structured routing operator exactly realizes the decoupled write.

This result is intentionally restricted. Full orthogonal control is transitive on the sphere but not kernel-compatible in general; fixed \(2\times2\) block rotations preserve the chunk-WY structure but are not transitive on the full sphere. Thus the practical SFDA design question becomes a routing-capacity problem: can a kernel-compatible control family provide enough write-direction routing to improve KDA-style memory without destroying the block-WY kernel?

5 Compact Expressivity of Kernel-Compatible SFDA↩︎

The finite-state theorem in 4.1 shows exact one-hot realizability for a generalized tied-write template. That result is useful, but it does not answer the practical kernel question: which memory systems are represented compactly by the actual structured transition family \[A_t=\Lambda_t-u_tr_t^*, \label{eq:compact-primitive}\tag{19}\] where \(\Lambda_t\) is diagonal, block-phase, or another structured control operator that is cheap to multiply and apply? This section gives a positive, scoped answer. Kernel-compatible SFDA compactly represents three useful families: phase-group counters, register/reset memories, and bounded stacks under monomial or partial-permutation control. It also gives the precise rank budget explaining why chunk-WY is the correct computational invariant.

5.1 Rank budget: the exact compact class inside a chunk↩︎

5.1.0.1 Consequence.

13 explains why the paper uses chunk-bounded exactness. A fixed-rank global summary is impossible in general. The exact invariant is local: let the rank grow to \(C\) inside a chunk, apply the chunk transfer to the boundary state, and restart the rank budget in the next chunk.

5.2 Useful compactly representable memory systems↩︎

5.3 What this section proves↩︎

The compact expressivity picture is now precise:

• phase-only SFDA compactly represents finite abelian phase counters and oscillatory diagonal SSM-style filters;

• adding aligned reflections gives compact dihedral and orientation memory;

• the rank-one delta correction gives exact register/reset memories;

• adding cheap partial permutations gives bounded stacks and shift-register memories;

• arbitrary finite automata remain exactly realizable by one-hot lifting in the generalized template, but not necessarily compactly by \(\Lambda-u r^*\) transitions.

Thus the remaining empirical question is not whether SFDA can represent any finite state machine in principle, but whether these compact structured memories improve extrapolation and the KDA quality–efficiency frontier.

6 Chunk Algorithm, Cost, and Stability↩︎

The previous section proves exact constructive factorization. This section turns it into a kernel theorem. The central rule is simple: do not allow the WY rank to grow across the whole sequence. Let it grow only inside fixed chunks of length \(C\).

6.0.0.1 Applying a chunk transfer.

Given \(\mathcal{T}=(\Gamma,Y,W,M,B)\), the boundary update is \[S_{\mathrm{out}}=\Gamma S_{\mathrm{in}}-Y\bigl(M(W^*S_{\mathrm{in}})\bigr)+B. \label{eq:apply-transfer}\tag{20}\] If \(Y,W\in\mathbb{F}^{d\times C}\) and \(S\in\mathbb{F}^{d\times d_v}\), this costs \[\mathcal{O}(dd_v)+\mathcal{O}(dCd_v)+\mathcal{O}(C^2d_v)+\mathcal{O}(dCd_v), \label{eq:apply-cost}\tag{21}\] where \(\Gamma S\) is cheap because \(\Gamma\) is diagonal or block diagonal. For fixed \(C\in\{64,128,256\}\), the transfer application is linear in the state dimension up to a chunk-dependent factor.

6.0.0.2 Inter-chunk parallelism.

The boundary-state scan is exact and simple. It can be implemented recurrently over \(T/C\) chunks; this is often acceptable because \(T/C\ll T\). A fully parallel inter-chunk scan is possible using the affine law 9 , but exact composition doubles the low-rank size. Therefore there are three implementation choices:

6.0.0.3 Training-time enforcement.

The parameterization in 12 13 14 15 enforces \(\left\lVert \Lambda_t\right\rVert_2\le1\), \(0\le\beta_t\le1\), and \(\left\lVert k_t\right\rVert_2\le1\). The conditioning condition in 23 is not automatic; it should be monitored empirically through \(\left\lVert L\right\rVert_2\), triangular-solve residuals, or finite-precision agreement between recurrent and chunk paths.

6.0.0.4 Systems target.

The theorem above is a reference bound, not the final fused-kernel claim. The systems target is a Triton/CUDA implementation that avoids dense \(d\times d\) matrices, uses matrix multiplies for \(W^*S\), \(M(\cdot)\), and \(Y(\cdot)\), and empirically approaches KDA-like \(\mathcal{O}(TdC)\) behavior with small constants. That speed claim must be benchmarked; algebra alone does not prove it.

7 Basic Experiments↩︎

We report a small set of controlled experiments designed to test the algebraic mechanism isolated by the theory. These experiments are intentionally modest: they verify the exact chunk algebra numerically and test whether phase control helps on cyclic state tracking. They do not claim large-scale language-model improvements, hybrid-ratio gains, or fused-kernel speedups; those remain the next empirical stage.

7.0.0.1 Experiment A: constructed cyclic memory.

We first test a training-free mod-\(5\) counter. The target state is \[c_t = \sum_{i=1}^t a_i \pmod 5,\] and SFDA stores the counter in a two-dimensional phase block \[z_t = R(2\pi a_t/5) z_{t-1}.\] The decoder is calibrated at length \(128\) and then evaluated at longer lengths. This directly tests Proposition 4: a unit-modulus phase orbit can store a cyclic counter without norm drift. As a controlled baseline, we compare against the best real-diagonal decay model in the same low-dimensional counter setting. Real diagonal decay has no nontrivial bounded period-\(5\) orbit, so it should collapse toward chance as the length grows.

7.0.0.2 Experiment B: learned short-to-long counter.

We next train a minimal SFDA counter head at length \(48\) and evaluate on longer lengths. The baseline is the same architecture with the phase disabled, \(\theta_t\equiv 0\), corresponding to the real-decay KDA special case in this controlled setup. This experiment asks whether the learnable phase parameter can be found from data, and whether the learned phase extrapolates beyond the training length.

7.0.0.3 Results.

Figure 2 and Tables 3–4 show the expected separation. In the constructed setting, phase memory is exact at all tested lengths, whereas the real-diagonal baseline approaches chance level \(1/5\). In the learned setting, SFDA solves the train-length counter and extrapolates roughly four times beyond the training length before phase error accumulates. The phase-disabled baseline stays near chance. The gap between Experiment A and Experiment B suggests that the SFDA parameterization has the right representation, while training and phase calibration determine how far the learned model extrapolates.

7.0.0.4 Numerical theorem checks.

We also verify the algebra used by the kernel construction. The block-WY closure theorem, the constructive chunk-WY product, and the affine chunk transfer all match dense recurrent ground truth to numerical precision; see Appendix 18. These checks are not a substitute for fused-kernel benchmarking, but they guard against algebraic implementation mistakes before moving to a Triton/CUDA kernel.

8 Experiments↩︎

The theory in Sections 4–6 makes two kinds of falsifiable claims: (i) exact algebraic identities, including the constructive chunk-WY recursion, the affine chunk transfer, the KDA reduction, finite-state one-hot realizability, and the stability bound; and (ii) a mechanistic claim that phase control implements bounded cyclic memory that a real-only decay mechanism does not provide. We verify (i) numerically and test (ii) on small synthetic state-tracking tasks. These are proof-of-concept experiments; language-modeling, fused-kernel, and long-context claims remain future work, as discussed in Section 10 and Appendix 15.

8.1 Numerical verification of the theorems↩︎

We implement the SFDA recurrence, the dense single-step transition \[A_t=(I-\beta_t k_t k_t^\ast)\Lambda_t,\] and the constructive chunk-WY recursion of Theorem 6 in complex coordinates, and check each theorem against a brute-force ground truth on random inputs. Table 5 reports the residuals; all identities hold to numerical precision. ¹

8.2 State tracking and length extrapolation↩︎

8.2.0.1 Setup.

We compare tied SFDA against its \(\theta=0\) reduction, which is the KDA special case from Proposition 2. The comparison uses an equal-capacity design: identical architecture, identical projections, and identical parameter count; the two models differ only in whether the phase \(\theta_t\) is used or forced to zero. Each model is a single-layer, single-head recurrence with state width \(d=16\) and a linear readout (\(\sim 8.3\mathrm{k}\) parameters total). We train with AdamW using a cosine schedule, keep the best checkpoint by in-distribution validation accuracy, and report accuracy on the final quarter of positions, which are the positions that most require persistent state. All models train on length \(T_{\mathrm{train}}=32\) and are evaluated on \(T\in\{32,64,128,256\}\), i.e., up to \(8\times\) extrapolation. Results are means over two seeds.

8.2.0.2 Tasks.

We evaluate two small state-tracking tasks. First, the cyclic counter \(C_3\) asks the model to output the running sum modulo \(3\) of a stream of increments. Second, the reset counter \(C_3\) is the same task with an additional reset symbol that returns the state to \(0\). The reset operation is an idempotent memory transition, matching the register/reset family in Theorem 17. Chance accuracy is \(1/3\).

8.2.0.3 Results.

Table 6 and Figure 3 show a clean separation. On the pure cyclic counter, the \(\theta=0\) KDA reduction remains near chance at all tested lengths, including in-distribution. SFDA solves the task in-distribution and degrades only at longer extrapolation lengths, where learned phase calibration error accumulates. With a reset symbol bounding the effective horizon, SFDA extrapolates essentially perfectly to \(8\times\) the training length, while KDA plateaus around \(0.68\). This matches Proposition 4: phase is the mechanism that gives SFDA a bounded cyclic orbit.

8.2.0.4 Limitations of these experiments.

These are small-scale, mechanism-isolating tests, not the full empirical program needed for a systems-level ICML submission. The dihedral task \(D_3\), a reversible counter whose direction is flipped by a control symbol, remains hard at this scale: SFDA reaches only approximately \(0.47\) in-distribution, while KDA stays near chance. This indicates that learning conditional direction-reversal, while representable by the structured control theory in Theorem 15, may require more capacity or training than used here. We make no language-modeling, throughput, or long-context claims in this section. In particular, the hybrid-ratio target—SFDA at \(7{:}1\) or \(15{:}1\) versus KDA at \(3{:}1\)—and the fused Triton/CUDA kernel are left to future work; see Appendix 15 and Section 10.

9 Related Work↩︎

9.0.0.1 Efficient attention and fast-weight memory.

The Transformer architecture introduced softmax self-attention as a general sequence modeling primitive [5]. Linear attention rewrites attention as an associative recurrent memory, enabling constant-size autoregressive state and linear-time sequence processing [6]. This view is closely related to fast-weight memory: the recurrent state stores transient key–value associations and is updated online by Hebbian or delta-style rules [7]. Subsequent work improves the basic linear-attention state with gating, decay, and hardware-aware chunkwise parallelism [8]–[11]. Kimi Linear introduces KDA, a channel-wise gated delta-rule layer with a specialized DPLR/WY-style chunkwise algorithm and a 3:1 KDA-to-global-attention hybrid [2]. SFDA is complementary: rather than replacing KDA’s delta memory, it adds a phase-control operator and proves that the resulting transition still admits an exact chunk-local WY invariant.

9.0.0.2 State-space models, DPLR structure, and phase dynamics.

Structured state-space models use diagonal or diagonal-plus-low-rank operators to model long sequences efficiently [12]. Mamba and Mamba2 make state-space dynamics input-dependent and expose a duality between selective SSMs and attention-like computation [13], [14]. SFDA differs from static complex diagonal SSMs because the transition contains an input-dependent delta correction, and differs from unrestricted DPLR because the low-rank term is tied to the delta rule, preserving a chunk-WY kernel. The learned phase component is motivated by the empirical and theoretical importance of oscillatory state dynamics and negative/complex modes for state tracking [15].

9.0.0.3 Chunk-WY kernels and triangular transforms.

The algebraic core of KDA-like kernels is a compact representation of products of rank-one corrections. Classical WY representations compact products of Householder transformations [3], and later UT-style triangular transforms improve accumulation efficiency [16]. KDA adapts this philosophy to diagonal decay plus rank-one delta updates and benchmarks a faster specialized kernel than general DPLR [2]. Parallelizing delta-rule linear transformers over sequence length has also been studied directly in the linear-attention kernel literature [17], [18]. Our constructive theorem gives the corresponding invariant for phase-decay transitions \(A_t=\Lambda_t-u_tr_t^*\).

9.0.0.4 Position, phases, and rotations.

Rotary positional embeddings encode relative position through products of two-dimensional rotations applied to query/key features [4], [19]. Related Fourier positional methods study periodic extensions for length generalization [20]. SFDA uses rotations differently: phases act on the recurrent memory transition itself, so the phase variable is a state-transition mechanism rather than only a positional feature map.

9.0.0.5 Automata, shortcuts, and algebraic memory.

Transformers can simulate finite automata by composing transition maps in shallow parallel circuits, and solvable semiautomata admit particularly short Krohn–Rhodes-style shortcuts [1], [21], [22]. The earlier semidirect/Fourier automata preprint proposed using algebraic memory/control decompositions and Fourier phase representations for automaton simulation [23]. This paper converts that perspective into a kernel-compatible recurrent attention layer: cyclic and dihedral state tracking become exact phase-memory constructions, while general finite-state one-hot expressivity is stated separately for the generalized tied-write affine template.

9.0.0.6 Retrieval, copying, and hybrid architectures.

A central limitation of pure fixed-state sequence models is exact retrieval and copying over long contexts [24], [25]. Empirical studies of efficient language models emphasize the recall–throughput tradeoff [26], [27]. Hybrid models combine efficient recurrent or SSM layers with occasional full-attention layers to recover global selection capability [2], [28], [29]. SFDA’s intended empirical target is therefore not merely a toy counter improvement, but a better quality–efficiency frontier for such hybrids.

10 Limitations and Open Problems↩︎

This preprint deliberately avoids several overclaims.

10.0.0.1 No fixed-rank full-sequence theorem.

Exact composition increases WY rank additively. The theorem is chunk-bounded, not globally fixed-rank. Any global fixed-rank scan would require additional structure or approximate recompression.

10.0.0.2 Finite-state tied-write expressivity is solved; compact SFDA expressivity is characterized for useful families, not universally.

The appendix proves that every deterministic finite automaton, including every finite semidirect automaton, is exactly realized by a generalized tied-write affine template after one-hot lifting. This closes the finite-state expressivity objection. 5 further proves compact kernel-compatible realizations for product cyclic counters, dihedral phase-orientation memory, register/reset memory, and bounded stacks when the structured control family includes the corresponding rotations, reflections, or partial permutations. What remains open is a complete low-dimensional classification for arbitrary finite automata or arbitrary semigroup transitions under the strict phase-plus-rank-one family \(A_t=\Lambda_t-u_tw_t^*\).

10.0.0.3 Orbit-restricted tied-write routing is characterized, not solved in full generality.

Appendix 16 proves that tied writes can route decoupled write directions lying in the orbit of the tied key under the structured control family. The exact full-state theorem requires a scratch/protected channel or an orthogonality condition ensuring that the erase projection does not damage carried memory. Fixed block rotations are kernel-compatible but not transitive on the full sphere, so arbitrary one-step write-direction routing is not claimed. Richer routing, such as Givens products or full orthogonal control, increases expressivity but may weaken the simple chunk-WY kernel.

10.0.0.4 Constructive recursion is not yet a fused kernel.

The constructive chunk-WY recursion proves that the factors can be built exactly and locally. It does not by itself guarantee that a Triton/CUDA implementation matches KDA speed. The systems contribution still requires implementation, profiling, memory-traffic analysis, and comparison to KDA kernels.

10.0.0.5 No empirical superiority yet.

The package states the required experiments and target claims. It should not say SFDA beats Kimi Linear until the hybrid-ratio and throughput experiments have been run under fair compute.

11 Additional Proofs↩︎

11.1 Real block rotations and complex diagonal phases↩︎

11.2 Block-WY identity with dimensions↩︎

The closure theorem in 5 is valid over \(\mathbb{R}\) with transpose or over \(\mathbb{C}\) with conjugate transpose. For clarity, suppose \[\begin{align} Y_1,W_1&\in\mathbb{F}^{d\times r_1}, & M_1&\in\mathbb{F}^{r_1\times r_1},\\ Y_2,W_2&\in\mathbb{F}^{d\times r_2}, & M_2&\in\mathbb{F}^{r_2\times r_2}. \end{align}\] Then \(Y_{21},W_{21}\in\mathbb{F}^{d\times(r_1+r_2)}\) and \(M_{21}\in\mathbb{F}^{(r_1+r_2)\times(r_1+r_2)}\). The lower-left block \(-M_2W_2^*Y_1M_1\) has shape \(r_2\times r_1\), so the block matrix is well-typed.

11.3 Affine composition and chunk scans↩︎

11.4 Full proof of the constructive WY recursion↩︎

We prove 6 in detail. The base case \(t=1\) gives \[\Gamma_1=\Lambda_1, \qquad Y_1=u_1, \qquad W_1=r_1, \qquad M_1=[1],\] hence \(P_1=\Lambda_1-u_1r_1^*=\Gamma_1-Y_1M_1W_1^*\).

Assume \(P_{t-1}=\Gamma_{t-1}-Y_{t-1}M_{t-1}W_{t-1}^*\). Then \[\begin{align} P_t &=(\Lambda_t-u_tr_t^*)(\Gamma_{t-1}-Y_{t-1}M_{t-1}W_{t-1}^*)\\ &=\Lambda_t\Gamma_{t-1}-\Lambda_tY_{t-1}M_{t-1}W_{t-1}^*\nonumber\\ &\quad-u_tr_t^*\Gamma_{t-1}+u_tr_t^*Y_{t-1}M_{t-1}W_{t-1}^*. \label{eq:appendix-constructive-expand} \end{align}\tag{22}\] Using the proposed updates, \[\begin{align} Y_tM_tW_t^* &=\begin{bmatrix}\Lambda_tY_{t-1}&u_t\end{bmatrix} \begin{bmatrix} M_{t-1}&0\\ -r_t^*Y_{t-1}M_{t-1}&1 \end{bmatrix} \begin{bmatrix}W_{t-1}^*\\ r_t^*\Gamma_{t-1}\end{bmatrix}\\ &=\Lambda_tY_{t-1}M_{t-1}W_{t-1}^* -u_tr_t^*Y_{t-1}M_{t-1}W_{t-1}^*\nonumber\\ &\quad+u_tr_t^*\Gamma_{t-1}. \label{eq:appendix-constructive-lowrank} \end{align}\tag{23}\] Substituting 23 into \(\Gamma_t-Y_tM_tW_t^*\) with \(\Gamma_t=\Lambda_t\Gamma_{t-1}\) gives exactly 22 . Thus \(P_t=\Gamma_t-Y_tM_tW_t^*\) by induction.

12 Constructive Algorithm Details↩︎

This appendix expands the chunk-WY recursion in code-like form and records the implementation conventions needed for an arXiv preprint. Throughout, \(r_t\) denotes the right WY vector in \(A_t=\Lambda_t-u_tr_t^*\); it is not the attention value vector.

12.1 Left-to-right product convention↩︎

We use the left-to-right chunk product \[P_t=A_tA_{t-1}\cdots A_1.\] The convention matters because the factors in 6 are asymmetric. Reversing the product order changes the placement of \(\Gamma_{t-1}^*r_t\) and the lower-triangular structure of \(M_t\).

12.2 Base case and dimensions↩︎

At \(t=1\), \[\Gamma_1=\Lambda_1, \qquad Y_1=u_1, \qquad W_1=r_1, \qquad M_1=[1],\] so \[P_1=\Lambda_1-u_1r_1^*=\Gamma_1-Y_1M_1W_1^*.\] If \(Y_{t-1},W_{t-1}\in\mathbb{F}^{d\times(t-1)}\) and \(M_{t-1}\in\mathbb{F}^{(t-1)\times(t-1)}\), then \[r_t^*Y_{t-1}M_{t-1}\in\mathbb{F}^{1\times(t-1)}.\] Thus the update \[M_t= \begin{bmatrix} M_{t-1}&0\\ -r_t^*Y_{t-1}M_{t-1}&1 \end{bmatrix}\] is well typed. The negative sign is essential: it cancels the cross term generated by multiplying the new rank-one correction into the previous low-rank correction.

12.3 Reference pseudocode↩︎

The following pseudocode is intended as a reference implementation, not as the final optimized Triton kernel.

Gamma = identity_phase_or_diag()
Y = empty_matrix(d, 0)
W = empty_matrix(d, 0)
M = empty_matrix(0, 0)

for t in range(C):
    Lambda_t = phase_decay[t]          # diagonal or 2x2 block phase
    u_t = beta[t] * k[t]
    r_t = Lambda_t.conj().T @ k[t]     # elementwise for diagonal phase

    Gamma_old = Gamma
    Y_old, W_old, M_old = Y, W, M

    Gamma = Lambda_t @ Gamma_old
    Y = concat_cols(Lambda_t @ Y_old, u_t)
    W = concat_cols(W_old, Gamma_old.conj().T @ r_t)

    row = - r_t.conj().T @ Y_old @ M_old
    M = block([[M_old, zeros],
               [row,   ones]])

For diagonal complex \(\Lambda_t\), the multiplications \(\Lambda_tY\) and \(\Gamma^*r_t\) are elementwise over channels. For real block-rotation implementation, they are independent \(2\times2\) block multiplications.

12.4 Affine write term↩︎

The recurrent update is \[S_t=A_tS_{t-1}+B_t, \qquad B_t=\beta_tk_ta_t^*,\] where \(a_t\) is the attention value vector. Inside a chunk, \[S_C=A_{C:1}S_0+\sum_{i=1}^C A_{C:i+1}B_i.\] The additive summary can be computed without forming any dense \(A_{C:i}\) by running the same recurrence with \(\bar S_0=0\): \[\bar S_t=A_t\bar S_{t-1}+B_t, \qquad B_C^{\rm chunk}=\bar S_C.\]

12.5 Why rank remains bounded↩︎

For a chunk of size \(C\), the recursion stops at \(t=C\), so \(Y_C,W_C\in\mathbb{F}^{d\times C}\) and \(M_C\in\mathbb{F}^{C\times C}\). Across chunks, the recommended implementation does not compose \((Y,W,M)\) factors into a larger global factor. Instead it applies each chunk transfer to the boundary state: \[S_{j+1}=\Gamma_jS_j-Y_jM_j(W_j^*S_j)+B_j.\] This is exact and avoids full-sequence rank growth.

12.6 Optimization target↩︎

The reference construction materializes \(M\in\mathbb{F}^{C\times C}\) and costs \(\mathcal{O}(dC^2+C^3)\) per chunk. For \(C\le64\), this is a reasonable first implementation. The optimized kernel should avoid slow Python-level loops and instead:

1. compute phase prefix products by elementwise complex multiplication;

2. compute the within-chunk Gram-like matrix \(r_i^*\Gamma_{i-1:j-1}u_j\) using batched matrix multiplication;

3. construct or solve the triangular \(M\) system by forward substitution;

4. use Tensor-Core-friendly matmuls for \(W^*S\), \(M(\cdot)\), and \(Y(\cdot)\).

This is the code-level systems gap remaining after the theorem.

13 Kernel Details and Rank-Growth Discipline↩︎

13.1 What rank growth means↩︎

If a chunk summary has rank \(C\), composing two exact chunk summaries produces rank at most \(2C\) by 5. Repeating this across \(T/C\) chunks gives rank \(T\) in the worst case. This is not useful as a full-sequence kernel state.

The correct discipline is:

1. Build exact low-rank factors only inside chunks.

2. Store chunk summaries \(\mathcal{T}_j=(\Gamma_j,Y_j,W_j,M_j,B_j)\) with rank at most \(C\).

3. Apply each chunk summary to the boundary state; do not materialize a global \(YMW^*\).

13.2 Boundary-state scan↩︎

For chunk \(j\), \[S_{j+1}=\Gamma_jS_j-Y_jM_j(W_j^*S_j)+B_j.\] The operation uses matrix products with shapes \[\begin{align} W_j^*S_j&\in\mathbb{F}^{C\times d_v},\\ M_j(W_j^*S_j)&\in\mathbb{F}^{C\times d_v},\\ Y_jM_j(W_j^*S_j)&\in\mathbb{F}^{d\times d_v}. \end{align}\] Thus the dominant transfer cost is \(\mathcal{O}(dCd_v+C^2d_v)\) plus diagonal/block-diagonal multiplication by \(\Gamma_j\).

13.3 Potential optimized recurrence for factors↩︎

The closure theorem gives a correct but naive way to build \(Y,W,M\). An optimized kernel should avoid explicitly applying the generic closure formula at every step. The expected path is analogous to KDA:

1. compute phase prefix products \(\Gamma_{i\to j}=\prod_{t=i}^{j}\Lambda_t\) by elementwise complex multiplication;

2. compute pairwise inner products \(w_i^*\Gamma_{i+1\to j-1}u_j\) inside the chunk;

3. form a lower-triangular system for \(M\) or its inverse;

4. use batched matmuls for \(W^*S\), \(M(\cdot)\), and \(Y(\cdot)\).

This is the systems work that turns the theorem into a KDA-speed operator.

13.4 Numerical considerations↩︎

Phase factors have unit modulus, while decays satisfy \(0\le \alpha_{t,j}\le1\). Products can underflow for long chunks if decays are small. As in gated linear attention and KDA-style kernels, one may store log-decays and apply local renormalization inside chunks. The phase part can be stored either as \((\cos\theta,\sin\theta)\) or as complex half/bfloat16 pairs depending on hardware support.

13.5 Claim language for the paper↩︎

Safe claim:

The phase-augmented delta transition admits an exact block-WY representation within chunks. Since chunk size is fixed, rank growth is bounded inside each chunk. Chunk summaries can be applied to boundary states without dense transition matrices, preserving recurrent inference and enabling chunk-parallel training.

Unsafe claim:

The full sequence admits an exact fixed-rank low-rank correction independent of \(T\).

13.6 Derivation plan for the phase-augmented kernel↩︎

A useful way to read the kernel theorem is as a staged restriction of a dense affine scan.

13.6.0.1 Stage 1: phase decay only.

If \(A_t=\Lambda_t\) with \(\Lambda_t=\mathop{\mathrm{diag}}(\alpha_t\odot e^{i\theta_t})\), then \[A_tA_{t-1}\cdots A_1=\prod_{i=1}^{t}\Lambda_i,\] which is represented by elementwise complex multiplication. This is the reason for using aligned \(2\times2\) rotations rather than arbitrary dense orthogonal matrices.

13.6.0.2 Stage 2: one delta correction.

For \[A_t=\Lambda_t-u_tr_t^*,\] products remain diagonal/block-phase plus low-rank corrections. The \(M\) factor is needed because cross terms such as \(u_2r_2^*u_1r_1^*\) must be represented without expanding into dense matrices. This is exactly what the block-WY invariant stores.

13.6.0.3 Stage 3: chunk-bounded exactness.

The exact chunk theorem is \[A_CA_{C-1}\cdots A_1=\Gamma_C-Y_CM_CW_C^*.\] Since \(C\) is fixed, the rank is bounded by \(C\). The theorem should never be stated with \(C=T\) unless the intended cost is full-sequence rank growth.

13.6.0.4 Stage 4: boundary-state scan.

For the affine recurrence \(S_t=A_tS_{t-1}+B_t\), the chunk summary is \[\mathcal{T}_j=(\Gamma_j,Y_j,W_j,M_j,B_j),\] where \[S_{j+1}=\Gamma_jS_j-Y_jM_j(W_j^*S_j)+B_j.\] The recommended exact implementation does not compose low-rank factors across chunks. It scans boundary states. If full inter-chunk parallelism is needed, one may use superchunks or approximate recompression, but those are separate implementation choices.

13.7 Claim language for this preprint↩︎

The defensible kernel claim is:

The phase-augmented delta transition admits an exact block-WY representation within fixed-size chunks. Because the control is diagonal in complex coordinates, the chunk product can be represented by phase-prefix products plus rank-\(C\) correction factors. Chunk summaries can be applied to boundary states without materializing dense \(d\times d\) transition matrices.

The claim that still requires implementation evidence is:

A fused Triton/CUDA implementation reaches KDA-like throughput and memory traffic.

The claim that should not be made is:

The full sequence has an exact fixed-rank representation independent of \(T\).

13.8 Chunk-kernel implementation checklist↩︎

A reference implementation should follow the same rank discipline used by KDA-like chunk kernels: never set the chunk size equal to the full sequence length. Fix a small chunk length \[C\in\{64,128,256\}.\] Inside one chunk, construct \[A_{C:1}=A_CA_{C-1}\cdots A_1=\Gamma_C-Y_CM_CW_C^*,\] with \(Y_C,W_C\in\mathbb{F}^{d\times C}\) and \(M_C\in\mathbb{F}^{C\times C}\). The rank is therefore bounded by \(C\) inside the chunk and is never allowed to grow to \(T\).

For each chunk \(j\), store the transfer object \[\mathcal{T}_j=(\Gamma_j,Y_j,W_j,M_j,B_j),\] which acts on a boundary state by \[S_{j+1}=\Gamma_jS_j-Y_jM_j(W_j^*S_j)+B_j.\] This is the exact boundary-state scan. It avoids global low-rank composition and therefore avoids the rank-doubling problem that would arise from composing two rank-\(C\) summaries into rank \(2C\) summaries.

13.8.0.1 Reference per-chunk steps.

A first PyTorch/Triton prototype should implement the following operations:

1. form phase-decay blocks \(\Lambda_t=\mathop{\mathrm{diag}}(\alpha_t\odot e^{i\theta_t})\) or the equivalent real \(2\times2\) blocks;

2. build \(u_t=\beta_t k_t\) and \(r_t=\Lambda_t^*k_t\);

3. update \((\Gamma,Y,W,M)\) using 6;

4. compute the affine write summary by the zero-state recurrence \(\bar S_0=0\), \(\bar S_t=A_t\bar S_{t-1}+B_t\);

5. apply the transfer by \(W^*S\), then \(M(\cdot)\), then \(Y(\cdot)\), plus the cheap phase multiplication \(\Gamma S\).

The naive factor build is \(\mathcal{O}(dC^2+C^3)\) per chunk, while transfer application is \(\mathcal{O}(dCd_v+C^2d_v+dd_v)\). For small \(C\), this is a usable correctness kernel. A fused kernel should reduce memory traffic and approach KDA-style \(\mathcal{O}(TdC)\) behavior in practice, but that is an implementation benchmark rather than a theorem.

13.8.0.2 Exactness versus parallelism.

There are three ways to process multiple chunks:

14 Finite-State Expressivity and Automata Interpretation↩︎

This appendix gives the finite-state expressivity result in a way that does not assume automata-theory background. The main point is simple: a finite-state machine can always be represented by one-hot vectors, and its transition rule can always be represented by a deterministic matrix. Therefore, in the generalized tied-write affine template, the erase-write coupling is not an expressivity obstruction for finite automata: we can set the write coefficient to zero and use only the linear transition.

14.1 The bounded-overhead question↩︎

A central question raised by KDA and SFDA is whether tying the erase and write directions reduces expressive power. A write-decoupled affine memory system has transitions \[x_t=A_{\sigma_t}x_{t-1}+b_{\sigma_t}, \qquad x_t\in\mathbb{R}^d, \label{eq:app-decoupled-affine}\tag{24}\] where the additive write \(b_\sigma\) is independent of the linear transition \(A_\sigma\). A generalized tied-write system has transitions \[z_t=(I-\beta_{\sigma_t}k_{\sigma_t}k_{\sigma_t}^*) \widetilde{A}_{\sigma_t}z_{t-1} + \beta_{\sigma_t}k_{\sigma_t}r_{\sigma_t}, \qquad z_t\in\mathbb{R}^D. \label{eq:app-general-tied}\tag{25}\] Here the same vector \(k_\sigma\) controls both the erase direction and the write direction.

The theorem below answers the finite-state version of this question. It does not solve the stronger low-dimensional compression question for general continuous affine systems.

14.2 Finite automata as one-hot linear systems↩︎

A deterministic finite automaton consists of a finite set of states \[Q=\{q_1,\ldots,q_N\},\] a finite input alphabet \(\Sigma\), and for every input symbol \(\sigma\in\Sigma\), a transition map \[\delta_\sigma:Q\to Q.\] If the current state is \(q\) and symbol \(\sigma\) is read, the next state is \(\delta_\sigma(q)\).

14.2.0.1 One-hot encoding.

Encode state \(q_i\) by the standard basis vector \[\phi(q_i)=e_i\in\mathbb{R}^N.\] For each input symbol \(\sigma\), define the matrix \(P_\sigma\in\mathbb{R}^{N\times N}\) by \[P_\sigma e_i=e_j \quad\text{whenever}\quad \delta_\sigma(q_i)=q_j. \label{eq:app-Psigma}\tag{26}\] Thus \(P_\sigma\) is exactly the linear operator that implements the automaton transition in one-hot coordinates.

14.3 Exact generalized tied-write realization of finite automata↩︎

We now insert the one-hot linear recurrence into the generalized tied-write template 25 . For finite-state simulation, the tied erase-write constraint causes no obstruction, because we can disable the write channel.

14.3.0.1 Why the proof is so short.

The tied-write mechanism only matters when \(\beta_\sigma\neq0\). By setting \(\beta_\sigma=0\), both the erase term and the write term vanish, and the system becomes an ordinary linear recurrence. The finite automaton is already an ordinary linear recurrence after one-hot encoding. Hence the tied-write coupling is irrelevant for exact finite-state realization.

14.4 Finite semidirect automata↩︎

A finite semidirect automaton has state space \[Q=N\rtimes H,\] where \(N\) is a finite memory set and \(H\) is a finite control set. A state is a pair \(q=(n,h)\), where \(n\in N\) is the memory component and \(h\in H\) is the control component. A typical semidirect update has the form \[(n,h)\mapsto (n+\rho(h)a_\sigma,\;hh_\sigma), \label{eq:app-semidir-update}\tag{27}\] where \(a_\sigma\in N\), \(h_\sigma\in H\), and \(\rho(h)\) denotes the action of \(h\) on \(N\). The precise algebraic form is not needed for the theorem below. The only required fact is that \(N\rtimes H\) is finite.

14.5 What remains open after the solution↩︎

[thm:app-exact-tied-finite,cor:app-semidir-finite] solve the finite-state expressivity objection for the generalized tied-write template. The solution is exact and elementary. However, it should not be confused with two stronger claims.

14.5.0.1 Not a low-dimensional compression theorem.

The one-hot construction uses dimension equal to the number of reachable states: \[D=|Q|.\] If a memory system has exponentially many reachable states relative to a smaller continuous representation, one-hot lifting may be exponentially large. Therefore the theorem proves exact finite-state realizability, while the stronger question of efficient low-dimensional compilation remains separate.

14.5.0.2 Not a kernel-compatible SFDA universality theorem.

The proof uses unrestricted transition matrices \(\widetilde{A}_\sigma=P_\sigma\). The kernel-compatible tied SFDA transition has the much more structured form \[A_t=(I-\beta_tk_tk_t^*)\Lambda_t=\Lambda_t-u_tw_t^*,\] where \(\Lambda_t\) is diagonal or block-phase. This restriction is what makes the constructive chunk-WY kernel possible. The exact one-hot theorem therefore removes finite automata as an expressivity obstruction, but it does not say that every finite automaton admits a small phase-plus-rank-one SFDA realization.

14.5.0.3 Clean final interpretation.

The finite-state question is solved: tied-write coupling does not prevent exact one-hot realization. The remaining research problem is sharper and more useful for systems evaluation: can structured SFDA transitions give low-dimensional, hardware-efficient realizations that improve the KDA quality–efficiency frontier?

15 Experiment Protocol↩︎

15.1 Synthetic automata↩︎

15.2 Language modeling↩︎

Use at least three model scales if compute permits: 100M, 300M, and 1B parameters. Compare:

• full attention / MLA-style baseline;

• KDA hybrid at \(3{:}1\);

• SFDA hybrid at \(3{:}1\), \(7{:}1\), and \(15{:}1\);

• ablations: no phase, fixed phase, learned phase, random phase, phase without delta.

15.3 Kernel benchmarks↩︎

Report forward and backward time for \(T\in\{4k,16k,64k,128k\}\), chunk \(C\in\{64,128\}\), and \(d_k=d_v=128\). Include memory footprint and achieved TFLOP/s. The relevant comparison is not against dense DPLR only, but against the best available KDA kernel.

15.4 Long-context benchmarks↩︎

The final paper should include at least RULER, MRCR, RepoQA, LongBench v2, and a long-code benchmark. The hybrid-ratio result is the key table:

16 Tied-Write Compilation over Structured Control Orbits↩︎

This appendix gives a precise restricted statement of what tied-write SFDA can realize without appealing to arbitrary dense transition matrices. The key idea is an orbit condition: a tied write into a key direction \(k\) can be routed into another direction \(w\) when \(w\) is reachable from \(k\) by the structured control operators available to the architecture.

There is one important technical caveat. In the KDA/SFDA delta rule, a tied write is not a pure additive write. It also contains an erase projection. Therefore the full affine compilation theorem needs a protected-subspace assumption ensuring that the erase projection does not modify the carried memory. We state both the contribution-level routing lemma and the full affine theorem below.

16.1 Model classes↩︎

Let \(x\in\mathbb{R}^d\) denote a memory state. A decoupled structured affine update has the form \[x^+=G_\sigma x+w_\sigma r_\sigma, \label{eq:decoupled-update-orbit}\tag{28}\] where \(G_\sigma\in\mathbb{R}^{d\times d}\) is a structured transition operator, \(w_\sigma\in\mathbb{R}^d\) is a write direction, and \(r_\sigma\in\mathbb{R}\) is the scalar value being written. The write direction \(w_\sigma\) is independent of the direction used by the erase/read mechanism.

A tied-write delta step has the form \[z^+=(I-\beta_\sigma kk^\top)\widetilde{G}_\sigma z+\beta_\sigma k r_\sigma, \label{eq:tied-update-orbit}\tag{29}\] where the same vector \(k\) controls the erase direction and the write direction. This is the structural coupling present in KDA-style delta memory.

16.2 Structured control family and orbits↩︎

Let \(\mathcal{G}\subseteq\mathbb{R}^{d\times d}\) be the family of structured control operators allowed by the architecture. Examples include diagonal phase-decay matrices, block rotations, signed permutations, Givens rotations, or products of such operators.

For a fixed nonzero key \(k\in\mathbb{R}^d\), define its orbit under \(\mathcal{G}\) as \[\operatorname{Orb}_{\mathcal{G}}(k)=\{Rk:R\in\mathcal{G}\}. \label{eq:orbit}\tag{30}\] The orbit is the set of directions reachable from the tied key using only the structured control operators available to the model.

16.3 Contribution-level routing↩︎

16.3.0.1 Why this lemma is not yet a full update theorem.

A model applies \(R_\sigma\) to the state, not only to the newly written contribution. Moreover, the tied delta step also contains the erase term \((I-\beta kk^\top)\). The full theorem must account for both effects.

16.4 Restricted tied-write compilation theorem↩︎

16.4.0.1 Interpretation.

The theorem identifies the condition under which the tied-write constraint is harmless for a decoupled write. The desired write direction must be reachable from the tied key by the structured control family, and the carried memory must be protected from the erase projection. Thus the expressivity question becomes a routing problem plus a subspace-allocation problem: \[\text{How large is }\operatorname{Orb}_{\mathcal{G}}(k), \qquad \text{and how cheaply can protected write lanes be allocated?}\]

16.5 Direction routing for common control families↩︎

16.6 Consequence for SFDA↩︎

16.6.0.1 What this proves.

This appendix proves that tied-write coupling is not an obstruction for write directions reachable by the architecture’s own structured control operators, once the erase term is neutralized on the carried memory subspace.

16.6.0.2 What this does not prove.

This result does not prove that diagonal or fixed block-phase SFDA can realize all arbitrary write directions in \(O(1)\) microsteps. Fixed block rotations are generally not transitive on the full sphere. Full arbitrary direction routing requires either richer control operators, such as general orthogonal routing, or a sequence of multiple local rotations. Thus the remaining stronger question is whether a kernel-compatible SFDA control family can be made sufficiently expressive for practical routing while preserving the chunk-WY structure.

17 Compact Expressivity Proof Details and Review-Driven Additions↩︎

This appendix collects proof details and scope clarifications for 5. The goal is to state exactly what the kernel-compatible SFDA family can represent compactly, without collapsing the distinction between one-hot finite-state universality and low-dimensional structured realizations.

17.1 The primitive generator viewpoint↩︎

Fix a structured control family \(\mathcal{L}\). The linear part of one kernel-compatible SFDA microstep is \[A=\Lambda-ur^*,\qquad \Lambda\in\mathcal{L}.\] Thus the compact transition class with chunk budget \(C\) is the length-\(C\) word ball in the semigroup generated by structured controls and rank-one corrections: \[\mathsf{SFDA}_{\mathcal{L}}(d,C) := \left\{\prod_{t=1}^{C'}(\Lambda_t-u_tr_t^*):0\le C'\le C,\;\Lambda_t\in\mathcal{L}\right\}.\] The constructive WY theorem says that every element of this set has a computable summary \[P=\Gamma-YMW^*, \qquad \mathop{\mathrm{rank}}(P-\Gamma)\le C.\] The lower bound in 13 shows that this rank budget cannot generally be made independent of the number of distinct correction directions.

17.2 Readout for compact finite phase states↩︎

The compact phase realizations store discrete states as points on a torus. For example, \(C_m\) is stored as \[z_j=e^{2\pi i j/m},\qquad j\in\mathbb{Z}_m.\] This is an exact representation of the transition dynamics. To recover a symbolic label, one may use any finite classifier on the \(m\) separated points. A small MLP or nearest-phase classifier suffices because the set of possible hidden states is finite and separated by angle \(2\pi/m\). For products \(\prod_j C_{m_j}\), the readout can decode each coordinate separately or classify the product state jointly.

17.3 Why register memories are genuinely tied-SFDA, not only generalized-template systems↩︎

The register theorem uses the actual tied update. For register \(i\), \[S^+=(I-e_ie_i^*)S+e_ia^*.\] This is exactly tied SFDA with \(\Lambda=I\), \(\beta=1\), \(k=e_i\), and \(v=a\). The same key \(e_i\) erases and writes. The coupling is not harmful because a register update is precisely an erase-then-write operation.

17.4 Partial permutations and compatibility with the WY proof↩︎

The default implementation uses complex diagonal \(\Lambda_t\). However, the algebra of 6 only requires that \(\Lambda_t\) can be multiplied into \(\Gamma\), applied to \(Y\), and adjoint-applied to \(r_t\) efficiently. Partial permutations satisfy this requirement: multiplying or applying a sparse shift costs linear time in the number of nonzeros. Therefore bounded stacks and shift registers are not phase-only SFDA, but they are kernel-compatible generalized SFDA under a sparse-control family.

17.5 What would constitute a complete compact-expressivity classification?↩︎

A full classification would characterize all finite transformation semigroups whose transition matrices admit low-dimensional embeddings in \(\mathsf{SFDA}_{\mathcal{L}}(d,C)\) for small \(d\) and \(C\). This preprint does not claim such a classification. Instead, it proves positive results for common structured memories and a rank-budget theorem that gives the necessary computational invariant. In symbols, the paper proves useful sufficient inclusions such as \[\begin{align} \prod_{j=1}^{\ell}C_{m_j} &\subseteq \mathsf{SFDA}_{\mathcal{L}_{\mathrm{phase}}}(\ell,1),\\ D_m &\subseteq \mathsf{SFDA}_{\mathcal{L}_{\mathrm{ortho}}}(2,1),\\ \text{register memories with }d\text{ slots} &\subseteq \mathsf{SFDA}_{\mathcal{L}_{\mathrm{phase}}}(d,1),\\ \text{bounded stacks of depth }h &\subseteq \mathsf{SFDA}_{\mathcal{L}_{\mathrm{pp}}}(h,1), \end{align}\] where the notation suppresses the value width and finite readout. It does not prove that every finite automaton has a small representation in \(\mathsf{SFDA}_{\mathcal{L}}(d,C)\).

17.6 Review checklist incorporated into the main text↩︎

The current version incorporates the following review-driven corrections and additions:

1. a model hierarchy separating KDA, tied SFDA, kernel-compatible generalized SFDA, and the generalized tied-write proof template;

2. corrected finite-state theorem wording: one-hot finite-state realization is for the generalized tied-write affine template, not vanilla KDA;

3. rank-budget theorem for \(A_t=\Lambda_t-u_tr_t^*\) products;

4. no-global-fixed-rank lower bound;

5. constructive chunk-WY recursion in the main theory section;

6. prefix-output theorem for intra-chunk token outputs;

7. affine write-summary theorem and zero-state recurrence;

8. realification theorem mapping complex phases to \(2\times2\) real rotation-decay blocks;

9. stability and triangular-factor conditioning lemmas;

10. training-time parameterization constraints for \(\alpha_t,\theta_t,\beta_t,k_t\);

11. explicit relation to RoPE, SSMs, DPLR, and KDA;

12. orbit-routing theorem with protected-subspace erase neutralization;

13. compact cyclic, direct-product cyclic, dihedral, register/reset, and bounded-stack realization theorems;

14. exact chunk-parallelism wording: exact intra-chunk parallelism plus recurrent or scanned boundary propagation, not fixed-rank full-sequence closure;

15. full complexity accounting with value width \(d_v\);

16. a theorem-to-evidence map for experiments.

18 Details for Basic Experiments↩︎

18.0.0.1 Scope.

The experiments in Section 7 are designed to test the paper’s algebraic claims and the isolated phase-memory mechanism. They are not large-scale language-model experiments. In particular, they do not validate the hybrid SFDA-to-global-attention ratio, long-context language-model quality, or wall-clock speed of a fused Triton/CUDA kernel.

18.1 Numerical verification of algebraic identities↩︎

For each theorem check, we compare the structured implementation against dense matrix ground truth. Table 8 reports worst-case relative error across the tested random seeds and shapes.

18.1.0.1 Chunk-kernel sanity check.

For \(d_k=d_v=128\), the correction rank equals the chunk size \(C\) for \(C\in\{16,32,64,128\}\) in the generic random setting. Boundary-state transfer matches recurrent unrolling to approximately \(10^{-15}\). The naive build cost increases superlinearly in \(C\), consistent with the reference complexity \(O(d_kC^2+C^3)\). This motivates the paper’s chunk-bounded rank discipline: rank is allowed to grow within a chunk, but chunk summaries are not composed into a global fixed-rank object.

18.2 Constructed cyclic-memory separation↩︎

We construct a mod-\(5\) counter with state \[c_t = c_{t-1}+a_t \pmod 5.\] SFDA uses one real two-dimensional block to represent the complex phase \[z_t = \exp(2\pi i c_t/5).\] Equivalently, in real coordinates, \[z_t = R(2\pi a_t/5) z_{t-1}, \qquad R(\phi)= \begin{bmatrix} \cos\phi & -\sin\phi\\ \sin\phi & \cos\phi \end{bmatrix}.\] The decoder maps \(z_t\) to the nearest of the five phase prototypes. Since \(R(2\pi/5)^5=I\) and rotations preserve norm, this representation is exact up to floating-point error for arbitrary length.

The real-diagonal baseline is calibrated at the same initial length but lacks a nontrivial period-\(5\) bounded orbit. A real scalar or diagonal decay either contracts, expands, or flips signs along coordinates; it cannot rotate through five distinct phase states while preserving bounded norm. Therefore its best calibrated classifier approaches chance level on long random sequences.

18.3 Learned short-to-long counter↩︎

The learned experiment trains a minimal counter head at length \(48\) and evaluates without further tuning at lengths \(48,96,192,384,768\). The SFDA model learns a phase parameter and a decoder for the mod-\(5\) state. The KDA baseline is the same controlled model with phase disabled, \(\theta_t\equiv0\). This isolates whether the phase channel, rather than additional capacity, explains the cyclic tracking behavior.

The learned SFDA model reaches perfect train-length accuracy and remains perfect at length \(96\), then degrades gradually as small phase-estimation errors accumulate. This is consistent with the constructed experiment: the exact phase parameter has no intrinsic length drift, while a learned approximate phase can accumulate angular error over long horizons.

18.4 Reproducibility command block↩︎

The reference experiments can be reproduced with the following commands:

pip install numpy matplotlib torch
python3 verify_theorems.py
python3 exp_a_representational.py
python3 exp_b_learned.py
python3 plots_and_kernel.py

References↩︎

---

1. The cyclic phase check is reported in double precision. In single precision, the phase counter accumulates roughly \(10^{-4}\) round-off over \(T=5000\) steps, consistent with the theorem being exact and the observed error being numerical.↩︎