✗ Failed on benchmark 2026

Implicitly padded FFT convolution

Implementation & benchmark of arXiv:2608.14497 — Hybrid Dealiasing and Implicit Packing for Real Convolutions

Usefulness7/10

Difficulty7/10

Novelty6/10

Memory Speedup Memory Cnn Ssm Inference speedup Memory Harmonic analysis Linear algebra Numerical analysis

Source paper: Hybrid Dealiasing and Implicit Packing for Real Convolutions arXiv:2608.14497 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace explicit zero-padding before FFT convolution by the paper's mixed-radix decomposition, which injects zeros through bounded tile sums and never allocates the padded input. The resulting transform is mathematically identical to the length-M transform of the explicitly padded signal, while reducing temporary storage and potentially memory bandwidth.

Formulas

$$j=tm+s,\quad t=0,\ldots,p-1,\quad s=0,\ldots,m-1,\qquad k=q\ell+r,\quad \ell=0,\ldots,m-1,\quad r=0,\ldots,q-1.$$

$$F_{q\ell+r}=\sum_{s=0}^{m-1}\zeta_m^{\ell s}\zeta_{qm}^{rs}\sum_{t=0}^{p-1}\zeta_q^{rt}f_{tm+s},\qquad \zeta_N=e^{2\pi i/N}.$$

$$f_{tm+s}=\frac{1}{qm}\sum_{r=0}^{q-1}\zeta_q^{-tr}\zeta_{qm}^{-sr}\sum_{\ell=0}^{m-1}\zeta_m^{-s\ell}F_{q\ell+r}.$$

$$Y=\operatorname{IFFT}_M\!\left(\operatorname{FFT}_M(f_{\mathrm{implicit\ pad}})\odot\operatorname{FFT}_M(g_{\mathrm{implicit\ pad}})\right),\qquad M\ge L+K-1.$$

Mathematical statement

Let f={f_j}_{j=0}^{L-1} be an input of length L, let M>=L be the desired transform length, choose m in N, and define p=ceil(L/m) and q=ceil(M/m). Reindex input indices as j=tm+s with t=0,...,p-1 and s=0,...,m-1, and frequency indices as k=q ell+r with ell=0,...,m-1 and r=0,...,q-1. With zeta_N=exp(2 pi i/N), the paper's implicit zero-padded transform is F_{q ell+r}=sum_s zeta_m^{ell s} zeta_{qm}^{rs} sum_t zeta_q^{rt} f_{tm+s}, where f_{tm+s}=0 whenever tm+s>=L. Thus the zero padding is represented by a predicate inside the tile sum rather than by a materialized array. The inverse is f_{tm+s}=(1/(qm)) sum_r zeta_q^{-tr} zeta_{qm}^{-sr} sum_ell zeta_m^{-s ell}F_{q ell+r}. For convolution of f and g, choose M>=L+K-1, compute both implicit transforms, multiply spectra pointwise, and inverse-transform.

Implementation notes

Integrate this in the FFT convolution path of a long 1D CNN, temporal SSM, or neural-operator layer, specifically where the framework currently executes pad(x, (0,M-L)) followed by FFT. Given input length L and kernel length K, choose M as a convenient FFT length satisfying M>=L+K-1, and choose a tile size m that is friendly to the target CPU or GPU. Store only the original tensor x[B,C,L]. For each tile coordinate (t,s), load x[...,tm+s] if tm+s<L and otherwise use zero. For each r, compute U[r,s]=sum_t exp(2 pi i r t/q) x[t,m,s], multiply by exp(2 pi i r s/(qm)), and perform the m-point transform over s to obtain F[q*ell+r]. Apply the same operation to the kernel, multiply spectra, and use the inverse transform. A compact kernel outline is: for r: for s: U[r,s]=sum_t twiddle_q[r,t]*x[t*m+s] if t*m+s<L; V[r,s]=twiddle_qm[r,s]*U[r,s]; F[q*ell+r]=sum_s twiddle_m[ell,s]*V[r,s]. Cache twiddle tables and fuse valid-index masking with loads. The identity and scaling come from the paper; tile size, fusion, and backend choice are empirical. First test B=8, Cin=Cout=32, L in {4096,16384}, and K in {257,1025} in a Conv1d language-model block. Compare against explicit padded rFFT, requiring relative forward error below 1e-5 and gradient error below 1e-4. Success is at least 1.2x lower peak temporary memory and a wall-clock improvement at equal numerical output and training loss.

Verification

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Significantly worse ✗

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 a readable mixed-radix implicitly padded DFT/IDFT and convolution MVP. The mechanism manifested: across 23 transform cases, maximum relative DFT error was 4.05e-14 and inverse error 1.88e-14; across 27 convolution cases, maximum error was 2.56e-14. The predicted storage reduction was observed at 2-4x for the tested lengths, but this unoptimized NumPy implementation was slower than explicit FFT convolution, so no wall-clock win was demonstrated.

Agent confidence: 9/10

Baseline: Explicit padded NumPy FFT spectrum timing: 0.000290s, 0.000523s, and 0.000744s for (L,K)=(257,65),(1025,257),(2049,513).
Idea: Implicit mixed-radix NumPy timing: 0.000779s, 0.002540s, and 0.005845s on the same cases; relative transform/convolution errors <=4.05e-14; analytical explicit-padding-storage / tile-buffer-storage ratio 2-4x.

Limitations: Only CPU NumPy was tested; no CUDA kernel, fused masking, autograd/gradient check, CNN/SSM training loss, peak allocator memory measurement, or large B,C workload was evaluated. The MVP allocates tile and einsum intermediates, so its measured memory behavior is an analytical tile-buffer comparison rather than a production peak-memory benchmark.

How to run: python3 run_experiment.py

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

Significantly WORSE than the tuned baseline (+37.6%, p=0.0081, wins 0 / 8 paired seeds).

Benchmark: Long_1d_convolution
Model: cnn_small
Paired seeds: 8
Baseline mean: 0.3525
Idea mean: 0.485
Effect (Δ): 0.1325 (+37.6%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±14.9%
Mechanism: Not confirmed ✗
Practical effect: Hurts
Baseline tuning: swept over 3 configs

Limitations:

The built-in vision track uses Conv2d and does not directly exercise long 1D FFT convolution, so a local custom track was used as required. Wall-clock and peak allocator memory were not measured in this stage-2 run. The failed mechanism signature indicates that the current torch mixed-radix implementation needs correction before interpreting storage or training results.

How to run: python3 stage2_bench.py

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

Stage 2 — Benchmark Sep 1, 2026 latest Failed ✗

Agent confidence: 10/10

Implemented a local custom long-1D convolution classification track and an end-to-end matched baseline/implicit-FFT CNN comparison using the required benchmark utilities. Across 8 paired seeds, the implicit system was significantly worse: test error 0.4850 versus 0.3525, paired delta +0.1325, permutation p=0.0081. The trained-model mechanism signature also failed, with observed relative operator error 1.0826 versus predicted 0, so the claimed transfer was not demonstrated.

Baseline: Best explicit-padding FFT baseline: mean test error 0.35250, std 0.02773, lr=0.01. Sweep means: lr=0.001 -> 0.43125, lr=0.003 -> 0.43875, lr=0.01 -> 0.35875.
Idea: Best implicit-padding system: mean test error 0.48500, std 0.03382, lr=0.01, m=8. Idea sweep means: lr=0.001 -> 0.48500, lr=0.003 -> 0.48625, lr=0.01 -> 0.47875.
Mechanism signature: Predicted relative operator error 0; observed relative operator error 1.08260; predicted storage ratio 2.0; trained-system output gap 1.05474; confirmed=false.
Paired comparison: delta_mean=+0.13250, idea_wins=0/8, permutation_p=0.0081, verdict=idea worse (significant).

Benchmark result