🤖 machine learning

The Kalman Evolve: Closing the Gap in Kalman Filtering via Interpretable Algorithm Discovery

The paper introduces "Kalman Evolve," a framework that leverages large language models to discover interpretable, non-affine modifications to the Kalman filter's update structure, thereby closing the performance gap in nonlinear sensing scenarios where traditional parameter tuning fails.

Original authors: Vasileios Saketos, Ming Xiao

Published 2026-05-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Vasileios Saketos, Ming Xiao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to track a runaway balloon in a windy park. You have a map and a compass (your "model"), and you get occasional glimpses of the balloon through a telescope (your "observations").

For decades, the best way to guess where the balloon is next was a mathematical tool called the Kalman Filter. Think of this tool as a very smart, very fast calculator. It works perfectly if the wind blows in a straight line and your telescope is perfect. It takes your last guess, adds the new glimpse, and gives you a new, better guess.

The Problem: The World is Messy
In the real world, things aren't perfect.

The Wind: The wind might swirl in crazy, non-straight patterns (nonlinear dynamics).
The Telescope: Sometimes your telescope measures distance in a weird way, like a radar that only hears how fast the balloon is moving toward or away from you, not exactly where it is (Doppler radar).
The Result: The standard calculator (Kalman Filter) gets stuck. It tries to draw a straight line through a curve. No matter how much you tweak the settings (like telling it "the wind is stronger" or "the telescope is shaky"), it can't fix the fact that its logic is too simple for the messy reality. It's like trying to fix a square peg in a round hole by just pushing harder on the peg.

The Solution: "Kalman Evolve"
The authors of this paper, Vasileios Saketos and Ming Xiao, built a new system called Kalman Evolve. Instead of just tweaking the settings of the old calculator, they asked a super-smart AI (a Large Language Model, or LLM) to rewrite the calculator's code itself.

Here is how they did it, using a simple analogy:

1. The "Evolution" Lab

Imagine a gym where you are training a runner.

The Old Way: You tell the runner, "Run 10% faster" or "Wear lighter shoes." You are just adjusting parameters.
The New Way (Kalman Evolve): You tell the runner, "Change your running style. Maybe lean forward more when you turn, or take shorter steps when the ground is bumpy." You are changing the structure of how they run.

The authors used an AI to act as a coach. They gave the AI a list of the best running styles they had so far and asked it to "mutate" them—create new, slightly different versions of the code.

2. The "Interpreter"

Usually, when AI writes code, it's a "black box." It works, but no human understands why.

The Paper's Trick: They forced the AI to write code that still looked like the original Kalman Filter. It kept the same basic steps (Predict -> Update), but it added small, clever "gates" or "switches" inside the math.
The Result: The new algorithm is still readable by humans. It's like taking a standard car engine and adding a smart turbo that kicks in only when you hit a bump. You can still see how the engine works, but it handles the bumps much better.

3. The Proof: Real-World Tests

They tested this new "evolved" calculator on three tough challenges:

Doppler Radar: Tracking objects using speed measurements (like police radar).
LiDAR: Self-driving cars using laser sensors to see distance and angles.
Pedestrian Tracking: Following people walking in crowded streets (MOT20 dataset).

The Results:
In every test, the "Evolved" version beat the standard calculator and even beat the "tuned" version (where humans just adjusted the settings).

It reduced errors by up to 12%.
It didn't need to be a slow, heavy computer program; it ran just as fast as the original.
It worked better than complex "Deep Learning" neural networks, which often require massive amounts of data and are hard to understand.

The Big Takeaway

The paper argues that we don't always need to throw away old, reliable tools and replace them with mysterious AI black boxes. Instead, we can use AI to evolve our old tools, making them smarter and more flexible while keeping them simple, fast, and understandable.

In short: They used an AI to rewrite the rules of a classic math game, creating a version that wins more often in the messy, real world, without losing the simplicity that made the original game great.

Technical Summary: The Kalman Evolve

Problem Statement

The Kalman Filter (KF) remains the cornerstone of state estimation, offering an optimal solution under assumptions of linear dynamics, Gaussian noise, and known noise covariances. However, in realistic sensing environments—such as Doppler radar and LiDAR—observations are often inherently nonlinear functions of the underlying state. In these scenarios, the standard KF update, restricted to affine transformations of the measurement residual, fails to capture the structure of the optimal estimator.

While extensions like the Extended Kalman Filter (EKF) and Unscented Kalman Filter (UKF) attempt to handle nonlinearity via local linearization or sigma-point approximations, they rely on known system models and lack data-driven adaptability. Conversely, data-driven approaches like Neural Kalman Filters (e.g., KalmanNet) often function as black boxes, require substantial training data, and may underperform classical methods. Furthermore, existing optimization methods, such as the Optimized Kalman Filter (OKF), focus solely on tuning noise parameters ( $Q$ and $R$ ) but remain confined to the class of affine estimators. The authors argue that this structural limitation prevents these methods from overcoming fundamental performance gaps caused by model mismatch, even when parameters are perfectly tuned.

Methodology: Kalman Evolve

To address the joint challenges of parameter uncertainty and structural limitations, the authors propose Kalman Evolve, a framework that discovers improved filtering algorithms by optimizing both noise parameters and the update structure simultaneously. The approach consists of two main stages:

Parameter Calibration: The process begins by estimating the process and measurement noise covariances ( $Q$ and $R$ ) using either least-squares estimation or the Optimized Kalman Filter (OKF). This establishes a well-calibrated, competitive baseline.
LLM-Guided Evolutionary Search: Building on the calibrated baseline, the framework employs an evolutionary search guided by Large Language Models (LLMs).
- Structured Prior: The LLM (specifically DeepSeek 16B) acts as a structured prior over the space of interpretable program transformations.
- Search Process: Inspired by AlphaEvolve, the search operates across four independent "islands" (parallel GPU workers). In each cycle, the LLM samples candidate algorithms from a database, receives a problem specification and two parent algorithms as a prompt, and generates mutations or combinations.
- Fitness Evaluation: Candidates are evaluated based on a loss function (typically Root Mean Squared Error, RMSE) on training data. The database is updated with the top-performing candidates.
- Preservation of Structure: Crucially, the search is constrained to preserve the recursive form of the Kalman Filter. The discovered algorithms modify the update step (e.g., via non-affine gating mechanisms or adaptive rescaling) while maintaining the core predict-update decomposition and the semantic roles of the innovation and Kalman gain.

Key Contributions

The paper makes four primary contributions:

Theoretical Suboptimality of Affine Estimators: The authors provide analytical proofs (Corollaries 1 and 2) demonstrating that affine estimators are structurally suboptimal under common nonlinear sensing models, specifically Doppler radar and LiDAR. Even with linear dynamics and Gaussian priors, geometric dependencies in observations (e.g., radial or angular measurements) induce a posterior mean that is intrinsically nonlinear.
Joint Optimization Framework: They introduce a unified framework that jointly optimizes noise parameters and the update structure, enabling the discovery of interpretable, non-affine extensions of the Kalman Filter.
Empirical Superiority: Across synthetic and real-world benchmarks, the discovered algorithms consistently outperform strong baselines, including the Optimized Kalman Filter (OKF), achieving up to a 12% reduction in RMSE.
Reproducibility: The authors release code and the discovered algorithms to support further research in interpretable algorithmic discovery.

Experimental Results

The framework was evaluated on three distinct benchmarks:

Doppler Radar Tracking: Evaluated on five scenarios ranging from simplified ("Toy") to complex ("Free" motion with acceleration and turns). Kalman Evolve (KE) consistently outperformed OKF. Improvements were marginal in simple settings (~0.4%) but grew to 11–12% in complex regimes involving acceleration and nonlinear motion.
LiDAR-Based Localization: Tested on synthetic driving trajectories and the real-world NCLT dataset. KE improved over OKF by approximately 5% in state estimation and 6% in next-state prediction on synthetic data, and by 2–3% on the noisy NCLT dataset, demonstrating transferability beyond synthetic environments.
Pedestrian Tracking (MOT20): Focused on next-state prediction for pedestrians. KE reduced test RMSE by 8% relative to OKF with high statistical significance ( $p < 10^{-6}$ ). Notably, KE demonstrated superior data efficiency, maintaining low error with small training sets where OKF performance was more variable.

In all cases, the discovered algorithms maintained computational costs comparable to the standard Kalman Filter, as the inference overhead was minimal. Deep learning baselines (LSTM, KalmanNet) generally underperformed the model-based approaches, particularly in the LiDAR and MOT20 settings.

Significance and Claims

The paper posits that the performance gap in nonlinear state estimation is not merely a parameter tuning issue but a structural one. By optimizing the structure of the Kalman filter itself, rather than just its parameters, Kalman Evolve offers a practical and interpretable path to improved state estimation.

The authors emphasize that their approach bridges the gap between model-based efficiency and data-driven adaptability. Unlike black-box neural networks, the discovered algorithms retain the recursive, interpretable form of the classical filter, introducing simple, data-dependent mechanisms (such as gating or adaptive rescaling) to handle model mismatch. The work suggests that combining classical model-based structures with LLM-driven discovery is a promising direction for developing high-performance, interpretable algorithms for real-world sensing problems where assumptions of linearity and Gaussianity are frequently violated.