△ Mechanism confirmed, baseline not beaten 2026

Signed spectral attention

Implementation & benchmark of arXiv:2608.29265 — Signed random Fourier features for fast density estimation with indefinite kernels

Usefulness7/10

Difficulty5/10

Novelty7/10

Architecture Speedup Accuracy Scalability Attention Graph nn Inference speedup Probability Harmonic analysis Linear algebra Measure theory

Source paper: Signed random Fourier features for fast density estimation with indefinite kernels arXiv:2608.29265 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace a quadratic pairwise attention or graph aggregation kernel with a compact, translation-invariant indefinite kernel approximated by signed random Fourier features. The feature map preserves the kernel's negative spectral mass through a diagonal sign matrix, so the resulting linear-time aggregation can represent similarities that ordinary positive-definite random features cannot.

Formulas

$$\int_{\mathbb{R}^{d}}f(\boldsymbol{x})g(\boldsymbol{x})d\boldsymbol{x}=\mathbb{E}[g(\boldsymbol{X})],\qquad \frac{1}{M}\sum_{m=1}^{M}g(\boldsymbol{X}_m)$$

$$K(\boldsymbol{u})=\int_{\mathbb{R}^{d}}e^{i\boldsymbol{\omega}^{\top}\boldsymbol{u}}\widehat K(\boldsymbol{\omega})d\boldsymbol{\omega}=C\,\mathbb{E}_{\boldsymbol{\Omega}\sim q}\left[s(\boldsymbol{\Omega})\cos(\boldsymbol{\Omega}^{\top}\boldsymbol{u})\right],\quad q(\boldsymbol{\omega})=\frac{|\widehat K(\boldsymbol{\omega})|}{C},\quad C=\int|\widehat K(\boldsymbol{\omega})|d\boldsymbol{\omega}$$

$$\widehat K_M(\boldsymbol{x},\boldsymbol{y})=\frac{C}{M}\sum_{m=1}^{M}s_m\cos\!\left(\boldsymbol{\Omega}_m^{\top}(\boldsymbol{x}-\boldsymbol{y})\right)=\frac{C}{M}z(\boldsymbol{x})D z(\boldsymbol{y})^{\top}$$

$$\widetilde{V}=\frac{C}{M}Z D\left(Z^{\top}V\right),\qquad Z_{i,2m-1}=\cos(\boldsymbol{\Omega}_m^{\top}\boldsymbol{x}_i),\quad Z_{i,2m}=\sin(\boldsymbol{\Omega}_m^{\top}\boldsymbol{x}_i)$$

Mathematical statement

The paper starts from the Monte Carlo identity $\int f(\boldsymbol{x})g(\boldsymbol{x})d\boldsymbol{x}=\mathbb{E}[g(\boldsymbol{X})]$ and estimator $M^{-1}\sum_{m=1}^{M}g(\boldsymbol{X}_m)$, then applies it to a signed Fourier density. Let $K:\mathbb{R}^{d}\to\mathbb{R}$ be an even translation-invariant kernel, let $\widehat K(\boldsymbol{\omega})$ be its Fourier transform under the convention $K(\boldsymbol{u})=\int_{\mathbb{R}^{d}}e^{i\boldsymbol{\omega}^{\top}\boldsymbol{u}}\widehat K(\boldsymbol{\omega})d\boldsymbol{\omega}$, and assume $\int|\widehat K(\boldsymbol{\omega})|d\boldsymbol{\omega}=C<\infty$. Define $q(\boldsymbol{\omega})=|\widehat K(\boldsymbol{\omega})|/C$ and $s(\boldsymbol{\omega})=\operatorname{sign}(\widehat K(\boldsymbol{\omega}))\in\{-1,+1\}$. If $\boldsymbol{\Omega}_m\sim q$ independently, then $K(\boldsymbol{u})=C\mathbb{E}[s(\boldsymbol{\Omega})\cos(\boldsymbol{\Omega}^{\top}\boldsymbol{u})]$ for real even kernels. Using $\cos(a-b)=\cos a\cos b+\sin a\sin b$, define $z(\boldsymbol{x})=[\cos(\boldsymbol{\Omega}_1^{\top}\boldsymbol{x}),\sin(\boldsymbol{\Omega}_1^{\top}\boldsymbol{x}),\ldots,\cos(\boldsymbol{\Omega}_M^{\top}\boldsymbol{x}),\sin(\boldsymbol{\Omega}_M^{\top}\boldsymbol{x})]$. Then $K(\boldsymbol{x}-\boldsymbol{y})\approx (C/M)z(\boldsymbol{x})D z(\boldsymbol{y})^{\top}$, where $D$ is diagonal and repeats $s(\boldsymbol{\Omega}_m)$ twice. For values $V\in\mathbb{R}^{N\times r}$, all-pairs aggregation $AV$ with $A_{ij}=K(x_i-x_j)$ becomes $(C/M)Z D(Z^{\top}V)$ instead of an $N\times N$ product.

Implementation notes

(1) Integration point: implement a linear attention or graph-message-passing layer. Project each token or node to $x_i=W_xh_i$ and $y_j=W_yh_j$, optionally divide both by a learned bandwidth $\ell$; use the signed radial interaction $K(x_i-y_j)$ instead of forming softmax logits. The value tensor is $V=W_vH$. Keep a separate positive normalization, such as $n_i=\sum_j|\widehat K_M(x_i-y_j)|+\epsilon$, rather than dividing by a signed sum. (2) Pseudocode: sample $M$ frequencies $\Omega_m\sim q(\omega)=|\widehat K(\omega)|/C$ and set $s_m=\operatorname{sign}(\widehat K(\Omega_m))$; construct $Z_x=[\cos(X\Omega),\sin(X\Omega)]$ and $Z_y=[\cos(Y\Omega),\sin(Y\Omega)]$; compute $U=(C/M)Z_y^\top V$, replace it by $DU$ with $D=\operatorname{diag}(s_1,s_1,\ldots,s_M,s_M)$, and return $Z_x(DU)$. For cross-attention, use distinct query and key matrices but the same sampled frequencies. (3) What comes from the mathematics: the signed measure, the $C/M$ Monte Carlo scaling, the duplicated cosine/sine factorization, and the sign insertion are fixed by the formulas. Estimate $C$ and sample $q$ numerically for the chosen kernel; for Kuttner-Golubov kernels $K(u)=(1-\|u\|^\alpha)^\beta\mathbf{1}_{\{\|u\|\le1\}}$, obtain $\widehat K$ by numerical radial Fourier integration or a precomputed lookup table, then use rejection sampling with proposal $p_0$ and envelope $B$ accepting $\omega$ with probability $|\widehat K(\omega)|/(Bp_0(\omega))$. (4) First experiment: train a 6-layer, 8-head transformer on CIFAR-10 treated as 196 image patches, and compare standard softmax attention, ordinary positive RFF attention, and signed attention at equal feature width and measured FLOPs. Start with $M\in\{32,64,128\}$ and the parabolic kernel. Measure validation accuracy, wall-clock time, memory, and approximation error against exact pairwise aggregation on a small batch. Success is lower memory and superlinear sequence-length scaling with no more than 1 percentage point accuracy loss; a stronger result is faster loss descent or improved accuracy from the compact negative lobes at equal FLOPs.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

Built signed random Fourier feature kernel and factorized linear aggregation for an analytically tractable indefinite Gaussian-mixture kernel. The mechanism manifested: signed RMSE scaled with observed slope -0.475 versus predicted -0.5, bias was near zero (0.0037 at M=512), while unsigned features converged to a nonzero RMSE floor of 0.6308. The small NumPy aggregation benchmark was slower than exact aggregation at N=220 because feature overhead dominated.

Agent confidence: 9/10

Baseline: Positive-only RFF: RMSE 0.6805 at M=16 and 0.6312 at M=512, with predicted asymptotic floor 0.6308; exact aggregation median 0.00589 s.
Idea: Signed RFF: RMSE 0.3300 at M=16 and 0.0613 at M=512, observed M^-0.475 scaling and bias 0.0037; signed factorized aggregation relative error median 0.1889 at N=220,M=128, median 0.01137 s.

Limitations: Only a one-dimensional analytic kernel and NumPy toy aggregation were tested; no learned transformer, CIFAR-10 accuracy, GPU implementation, positive normalization, FLOP accounting, or large-sequence scaling study was performed.

How to run: python3 signed_spectral_attention.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.29265) Sep 2, 2026

Ahead of the baseline (-0.0326 metric points) but not statistically significant (p=0.0673, wins 7 / 8 paired seeds).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0
Idea mean: 0.6471
Effect (Δ): -0.0326 (n/a; negative = idea better)
Wins: 7 / 8 paired seeds
p-value: 0.0673 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Confirmed ✓
Practical effect: No effect
Baseline tuning: swept over 6 configs

Limitations:

Only the sequence track was tested. The run used 400 training samples, 200 test samples, 6 epochs, and a tiny one-block transformer; wall-clock speed, memory, and FLOP scaling were not measured. The baseline used a six-configuration sweep over learning rate and temperature; the idea used a three-configuration learning-rate sweep at M=32, with all idea learning rates included in the baseline union grid.

How to run: python3 signed_attention_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 2, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented signed spectral attention as an end-to-end replacement for self-attention on the structurally matched sequence forecasting track. The trained-model mechanism signature confirmed the predicted M^-0.5 approximation scaling (observed slope -0.5046) and lower signed than unsigned kernel approximation error. The task MSE improved from 0.6797 to 0.6471, but the paired permutation test gave p=0.0673, so there was no statistically significant win.

Baseline: Softmax transformer attention; tuned best configuration lr=0.001, temperature=1.0; full 8-seed MSE mean 0.6796555296, std 0.0592304113.
Idea: Signed RFF attention; best configuration M=32, lr=0.003; full 8-seed MSE mean 0.6470961496, std 0.0759496206.
Mechanism signature: Trained-model signed approximation RMSE: M=8 0.4599075, M=16 0.3563229, M=32 0.2284983; observed slope -0.5045800 versus predicted -0.5; unsigned RMSE at M=32 0.3878027; confirmed=true.
Paired delta: -0.0325593799, 7/8 idea wins, permutation p=0.0673.

Benchmark result