Faster Kalman smoothing posed as a quadratic program

Find the most likely state trajectory of a noisy linear dynamical system from its measurements, faster than solving the equivalent quadratic program with CVXPY. The answer is what a Kalman smoother computes, so structure-exploiting recursions compete with general-purpose solvers.

Task

Given $A\in\mathbb{R}^{n\times n}$, $B\in\mathbb{R}^{n\times p}$, $C\in\mathbb{R}^{m\times n}$, measurements $y_0,\dots,y_{N-1}$, a known initial state $x_0$ and $\tau>0$, solve

$$\min_{x,w,v}\ \sum_{t=0}^{N-1}\big(\lVert w_t\rVert_2^2+\tau\lVert v_t\rVert_2^2\big)\quad\text{s.t.}\quad x_{t+1}=Ax_t+Bw_t,\quad y_t=Cx_t+v_t,$$

for $t=0,\dots,N-1$. In the benchmark $n=p=m=23$, $N=2n=46$ and $\tau=1$; $A$ is a standard normal matrix scaled to spectral radius just below 1, $B$ is 0.5 times a standard normal matrix, $C$ is standard normal, and the measurements are simulated with process and measurement noise of standard deviation 0.1. Output: $\hat x_0,\dots,\hat x_N$, $\hat w$ and $\hat v$. An output is accepted when the shapes are right, every entry is finite, the initial condition and each dynamics and measurement equation hold to $10^{-5}$ in Euclidean norm, and its objective is at most $J^\star(1+10^{-5})$, where $J^\star$ is the reference optimum. The reference solver is CVXPY with its default solver.

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

For Gaussian noise this quadratic program gives the maximum a posteriori state trajectory, the same estimate that a Kalman (1960) filter followed by a Rauch–Tung–Striebel (1965) backward pass computes in time linear in $N$. The task therefore measures how much a structure-aware recursion, or a banded linear solve of the optimality conditions, gains over a general-purpose modelling layer and solver.

Data and evaluation

• Instances: 100 test and 100 development instances from the task's generator at $n=23$ (23 states over 46 steps), in the AlgoTune dataset; the reference needs about 100 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: 85.80×, by the AlgoTuner agent driven by Gemini 3.1 Pro Preview, ahead of Gemini 3 Pro Preview (58.54×) and Claude Opus 4.5 (54.80×).
• 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 85.80× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing.
• A numerically stable square-root or banded-Cholesky implementation whose accuracy is reported alongside its speed.

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. Kalman. A new approach to linear filtering and prediction problems. Journal of Basic Engineering 82, 35–45 (1960). doi:10.1115/1.3662552
3. H. E. Rauch, F. Tung, C. T. Striebel. Maximum likelihood estimates of linear dynamic systems. AIAA Journal 3, 1445–1450 (1965). doi:10.2514/3.3166

Source

Imported from AlgoTune task kalman_filter, 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.