Exact Factorisation and Fast Computation of Invertible Constant-Q Transforms
Facundo Franchino, Eloi Moliner, Vesa Välimäki
eess.SP, cs.SD, eess.AS, math.NA
2026-09-24
Flash-CQT fuses selection, windowing and reordering into a fixed routing table inside per-band CUDA kernels: 2-8x faster CQT round trips, 36% less workspace, ~130 dB SNR.
Audio models mostly start from a time-frequency representation. The STFT uses one window for every band, so resolution is uniform across the spectrum. Musical pitch works differently: equal intervals are equal frequency ratios, which is why the constant-Q transform (CQT) spaces its bands geometrically and scales each window inversely with its centre frequency. Narrow low-frequency bands resolve nearby partials; short high-frequency windows track fast changes. The nonstationary Gabor transform (NSGT) construction makes the CQT exactly invertible, so analysed, edited, or model-generated coefficients map back to a waveform, and the transform is linear and differentiable. On paper it is an ideal front end for audio generation, source separation, and timbre transfer.
GPU efficiency is where that falls apart. Each band of an invertible CQT carries a different number of time coefficients over a fixed duration, so the coefficient arrays are ragged. Existing implementations run the operator as separate library calls: one long FFT, then per-band gathers and windowing, then short inverse FFTs of band-dependent length. Each call is a separate kernel launch with its own temporary buffers, and padding the ragged bands to a common length wastes arithmetic and storage. nnAudio gives differentiable analysis without an exact inverse; the invertible implementations are slow. In a training loop this runs every iteration, so the overhead compounds.
The contribution is an exact factorisation that collapses everything between the two Fourier stages into one fixed map, so routing and each band's short inverse FFT run inside a single CUDA kernel and the intermediate band spectra never touch global memory.
Three design choices carry the weight:
Theorem 1 bounds the arithmetic structure: with radices capped at r, depth is at most τr(L) + 1 + max τr(Mλ). For the shipped configuration (L = 32,768 = 32³) that is 3 + 1 + 3 = 7 layers with block width at most 64, and the paper argues seven layers are also necessary under this structure. The bound governs arithmetic, not kernel launches or runtime optimality.
The CUDA implementation fixes a slice of N = 65,536 samples at 44.1 kHz: nine octaves, 152 positive-frequency bands, three resolutions at 8/16/32 bands per octave. One 256-thread block per band and batch element uses at most 16.25 KiB of shared memory. Longer signals go through 50%-overlapping slices with a Tukey transition window, which keeps memory bounded and allows streaming.
All numbers are from an A100 in FP32. The baseline is the same operator written in PyTorch on cuFFT, with identical windows, native coefficient lengths, and sidebands and no zero padding, so every difference comes from the implementation:
| Method | Reconstruction SNR (dB) | Peak workspace (MB/signal) | Round trip B=1 (ms) | Step with backward B=1 (ms) |
| STFT (reference) | 133.1 | 4.3 | 0.051 | 0.838 |
| CQT baseline | 126.8 | 4.2 | 0.601 | 10.003 |
| Flash-CQT | 129.8 | 2.6 | 0.116 | 1.969 |
Under CUDA graph replay, round trips are 2.1 to nearly 8 times faster across batch sizes on A100 (5.2× at B=1) and 2.0 to 6.0 on V100. In eager mode with backpropagation, speedups reach 2.2–5.3 on A100 and 1.7–3.0 on V100. Against the STFT reference, the proposed CQT costs 2.3 times the STFT round-trip time at B=1 and reaches parity near B=16; with backward, the baseline costs 12 times the STFT at B=1 while Flash-CQT costs 2.35 (4.3 versus 1.9 at B=128). Peak temporary workspace drops 36–38%. Reconstruction sits at 129.8 dB, about 3×10⁻⁷ relative error, a few times FP32 machine epsilon, i.e. round-off rather than algorithmic loss. Adjoint gradients agree with autograd at 130.05 and 129.48 dB.
One honest nuance: at B=128 the native eager STFT round trip (1.39 ms) is faster than the proposed CQT (1.66 ms). Flash-CQT approaches STFT cost at large batches but does not beat it.
For anyone training audio models, this moves the invertible CQT from 12× the STFT's cost to roughly 2×. Diffusion-based audio generation, source separation, bandwidth extension, and timbre transfer all need log-frequency coefficients that map back to waveforms, and the front end is no longer an excuse. CQT-based losses and discriminators benefit from the fused analysis kernels and exact gradients even without invertibility.
The honest framing: this is systems work. The operator is unchanged, the math contribution is proving the in-between steps form an exact fixed map, and the gains come from eliminating data movement between kernels. That pays off most where the transform runs millions of times, which is exactly the training setting.
The authors state the main ones themselves. The fast kernels are specialised to the N = 65,536 slice; shorter signals need fewer low bands or lower Q, and either way new kernels. Effects on full model training and a comparison against a matched cuFFTDx implementation remain open. The depth bound concerns arithmetic structure, not runtime. Other painless NSGTs such as auditory filterbanks should work in principle, but fan-out and performance there are unverified.
Two more things stand out on a close read. Slicing with a transition window supports streaming over long recordings, but the paper reports no evaluation of slice-boundary artefacts. And everything is measured on two GPUs with a single band layout; a different configuration means regenerating routing tables and kernels, so this is less flexible than a general-purpose library.