Faster upfirdn: upsample, filter and downsample long signals

Resample long signals by inserting zeros, filtering with a short FIR filter and keeping every $d$-th sample, faster than SciPy's polyphase implementation. This operation is the building block of rational sample-rate conversion in audio, communications and measurement systems.

Task

Each instance is a list of four problems $(h,x,u,d)$: a filter $h$ of length 8 and a signal $x$ of length $32n$, $128n$, $512n$ or $2048n$ (one problem each), with independent standard normal entries, and factors $u$ and $d$ drawn from $\{1,2,4,8\}$; in the benchmark $n=2582$, so the longest signal has 5,287,936 samples. For each problem compute

$$y[k]=\sum_{j=0}^{7}h[j]\,\tilde x[kd-j],\qquad \tilde x[m]=\begin{cases}x[m/u]&\text{if }u\text{ divides }m,\\0&\text{otherwise,}\end{cases}$$

for every output index that scipy.signal.upfirdn(h, x, up=u, down=d) returns. The outputs are accepted when every shape matches the reference and $\sum_i\lVert y_i-y_i^{\mathrm{ref}}\rVert_2\big/\sum_i\lVert y_i^{\mathrm{ref}}\rVert_2\le10^{-6}$. The reference solver is scipy.signal.upfirdn.

Score: the reference's run time divided by the candidate's, averaged over the test instances; it is 1 if any output fails the check, and speed-ups below 1 count as 1. Higher is better.

Background

Upsampling, filtering and downsampling in one pass is the core of multirate signal processing (Crochiere and Rabiner, 1981). SciPy's upfirdn uses a polyphase scheme that skips the inserted zeros: per output sample it costs $O(N/P)$ for a filter of length $N$ and upsampling factor $P$, against $O(NQ)$ for the direct approach with downsampling factor $Q$.

Data and evaluation

• Instances: 100 test and 100 development instances from the task's generator at $n=2582$, in the AlgoTune dataset; the reference needs about 116 ms per instance on the authors' machine.
• Evaluation code: the AlgoTune harness (./algotune.sh evaluate in the repository), which runs the task's checker on every output.
• Hardware: speed-ups depend on the machine, so reference and candidate are timed in the same environment. The paper keeps the fastest of 10 timed runs per instance, each after a warm-up, on an AMD EPYC 9454 CPU with 14 GB of memory; agents had 8 cores, and compilation is not timed.

What is known

• Best on the AlgoTune leaderboard as of 2026-10-20: 2.18×, by the AlgoTuner agent driven by Claude Opus 4.6, ahead of DeepSeek R1 (1.13×) and GPT-5 (1.11×).
• Only one model's run exceeds 1.2×; the next best are 1.13× and 1.11×, so most attempts barely beat SciPy here.
• Press et al. (2025) describe most agent speed-ups as surface-level: better library calls, better library usage or low-level rewrites, for example with Numba.

What would count as progress

• A solver beating 2.18× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing.
• A reproduction of the best run on a second machine, showing that its gain is not specific to one CPU.
• A memory-bandwidth estimate for the longest signal, showing how close the best solver is to the hardware limit.

References

1. O. Press, B. Amos, H. Zhao, et al. AlgoTune: Can language models speed up general-purpose numerical programs? NeurIPS 2025. arXiv:2507.15887
2. R. E. Crochiere, L. R. Rabiner. Interpolation and decimation of digital signals: a tutorial review. Proceedings of the IEEE 69, 300–331 (1981). doi:10.1109/PROC.1981.11969
3. P. Virtanen et al. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods 17, 261–272 (2020). doi:10.1038/s41592-019-0686-2

Source

Imported from AlgoTune task upfirdn1d, curated by Ori Press and the AlgoTune contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.