Quadratic-budget Toeplitz long-range layer
Implementation & benchmark of arXiv:2608.13182 — On Toeplitz determinants with slow Fourier decay
Source paper: On Toeplitz determinants with slow Fourier decay arXiv:2608.13182 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace a dense translation-invariant interaction matrix with a positive-definite Toeplitz kernel K_n(e^f) whose log-spectrum is parameterized by a small number of Fourier coefficients with 1/|k| decay. Use the paper's explicit quadratic term as a spectral-volume budget, allowing long-range structure while discouraging uncontrolled determinant growth and ill-conditioning. Subtracting this term from a log-determinant regularizer leaves a residual intended to capture higher-order deviations from the analytically controlled baseline.
Formulas
Mathematical statement
For a symbol a=e^f on the unit circle, the Fourier coefficients are f_k=(2\\pi)^(-1)\\int_0^{2\\pi} f(e^{i\ heta})e^{-ik\ heta}d\ heta, and the Toeplitz matrix is T_n(a)=(a_{j-k})_{j,k=1}^n. The assumption limsup_{k to plus or minus infinity} |k||f_k|<infinity permits f_k=O(1/|k|). The central finite-size contribution is Q_n(f)=\\sum_{k=1}^{\\infty}\\min(k,n)f_kf_{-k}; for real-valued f, f_{-k}=\\overline{f_k}, so Q_n(f)=\\sum_{k>=1}\\min(k,n)|f_k|^2>=0. Parameterize f with f_0 and truncated coefficients c_1,...,c_K, impose f_{-k}=\\overline{c_k}, and define a(theta)=exp(f(theta)). The adapted residual is R_n(f)=log det T_n(e^f)-nf_0-Q_n(f). The paper's result says that Q_n accounts for possible growth with n while each fixed higher-order coefficient remains bounded, motivating a penalty on R_n rather than directly suppressing all spectral energy. The supplied coefficient estimate is sum of absolute coefficients at order m <= (4e)^m/sqrt(2pi m), which is useful as a conservative truncation diagnostic.
Implementation notes
(1) Integration point: insert this as a translation-invariant mixing layer between transformer blocks, or use it in place of a depthwise convolution or SSM mixing operator. For sequence length n, learn a real Fourier log-symbol f(theta)=f_0+2 Re sum_{k=1}^K c_k exp(i k theta), with c_k=u_k/(k+epsilon)^p and p near 1. Set f_{-k}=conjugate(c_k), which makes a(theta)=exp(f(theta)) positive and gives a Hermitian positive-definite Toeplitz matrix under standard nondegeneracy conditions. (2) Pseudocode: initialize u[1:K] and f0; evaluate f on an FFT grid; set a=exp(f); inverse FFT to obtain the Toeplitz diagonals; apply T_n(a) through a circulant embedding and FFT. Compute Q=sum_{k=1}^K min(k,n)*abs(c_k)^2. During small-model experiments estimate L=log det T_n(a) by Cholesky. For larger models estimate L with stochastic Lanczos quadrature using Rademacher probes z_r, approximating z_r^T log(T_n(a)) z_r. Add lambda*(L-n*f0-Q)^2, or lambda*max(0,abs(L-n*f0-Q)-tau)^2, to the task loss. (3) Q is computed exactly from learned coefficients; FFT coefficients, log-determinants, and eigenvalue extrema are numerical estimates. (4) First experiment: train a 4-layer, 256-dimensional sequence model on Long Range Arena or synthetic copy and addition tasks at lengths 512, 1024, and 4096. Compare dense attention, depthwise convolution, an unconstrained Toeplitz layer, and the proposed regularized layer at matched hidden size and measured FLOPs. Test K in {16,32,64}, with and without the penalty. Success means lower long-context validation loss, fewer gradient spikes, a larger minimum eigenvalue, and substantially lower memory than dense attention; report loss versus wall-clock time and whether the regularizer controls exploding log-volume.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.