💻 computer science

KATANA: A Fast, Low-Power Mapping of Kalman Filters onto Edge NPUs for Real-Time Tracking

This paper presents KATANA, an optimization framework that maps Linear and Extended Kalman Filters onto commercial Neural Processing Units (NPUs) in AI-PC SoCs using algebraic graph rewrites to achieve real-time, low-power multi-object tracking with up to 97.9% energy reduction compared to CPU implementations.

Original authors: Bodhisatwa Kundu, Anish Rooj, Sumit Saha, Abhradeep Sarkar, Arghadip Das, Arnab Raha, Mrinal K. Naskar

Published 2026-06-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Bodhisatwa Kundu, Anish Rooj, Sumit Saha, Abhradeep Sarkar, Arghadip Das, Arnab Raha, Mrinal K. Naskar

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 the pilot of a high-speed drone or a self-driving car. Your vehicle needs to constantly guess where objects (like other cars, birds, or missiles) are going, even when the sensors are a bit fuzzy. To do this, it uses a mathematical "calculator" called a Kalman Filter. This calculator is the brain's way of saying, "I saw the object here a split second ago, and based on how fast it was moving, it's probably there now."

For decades, this calculator has been running on the vehicle's main brain (the CPU). But the main brain is busy doing everything else: steering, talking to the driver, and playing music. Asking it to do the tracking math slows everything down and drains the battery.

Recently, computer chips (like the new Intel "Core Ultra" chips) have added a special, tiny helper engine called an NPU (Neural Processing Unit). Think of the NPU as a specialized assembly line designed to do massive amounts of math very quickly and very quietly (low power). However, this assembly line is built for a specific type of work (like recognizing faces in photos), and the Kalman Filter is a different kind of math puzzle. Because the puzzle doesn't fit the assembly line perfectly, the NPU sits idle, and the main brain still has to do the heavy lifting.

Enter KATANA.

The researchers behind KATANA asked a simple question: "Can we reshape the Kalman Filter puzzle so it fits perfectly onto this idle assembly line?"

They didn't build new hardware. Instead, they invented a clever set of "translation rules" (which they call algebraic graph rewrites) to repackage the math. Here is how they did it, using simple analogies:

1. The "Subtract-to-Add" Trick

The Problem: The Kalman Filter often needs to subtract numbers. The NPU's assembly line is built for adding and multiplying, not subtracting. Forcing it to subtract is like asking a fast-food worker to stop and hand-craft a burger bun; it slows the whole line down.
The KATANA Fix: They pre-calculated the "negative" version of the numbers they needed to subtract. Instead of saying "Take 5 and subtract 2," they changed the recipe to "Take 5 and add negative 2." Now, the NPU can just keep adding, which is its superpower.

2. The "No-Reshaping" Rule

The Problem: Sometimes the math requires changing the shape of the data (like turning a flat list into a 3D block). The NPU hates doing this on the fly; it has to pause and ask a slower helper chip (the DSP) to do it.
The KATANA Fix: They flattened and fixed the shapes before the math even started. It's like pre-cutting all the vegetables into perfect cubes before you start cooking, so the chef never has to stop chopping.

3. The "Group Hug" (Batching)

The Problem: If you are tracking 200 different objects, the old way was to ask the NPU to solve one object, then stop, then solve the next. This is like a bus driver stopping at every single house to drop off one person. It's inefficient.
The KATANA Fix: They packed all 200 objects into one giant, organized block (a "block-diagonal" matrix). Now, the NPU solves all 200 at once in a single burst. It's like the bus driver dropping off 200 people in one go because they are all sitting in the same row.

The Results: A Super-Efficient Engine

When they tested this on real hardware (Intel's latest chips), the results were impressive:

Speed: The NPU became a speed demon. It could track hundreds of objects simultaneously, reaching over 400 updates per second for simple tracking and 223 updates per second for complex tracking.
Battery Life: This is the big win. The NPU did the work using about 98% less energy than the main CPU. It's the difference between running a marathon in a heavy winter coat (CPU) versus a lightweight racing suit (NPU).
Freedom for the Main Brain: Because the NPU took over the tracking, the main CPU and the graphics card were left free to handle other tasks, like recognizing faces or rendering 3D maps.

The Bottom Line

The paper shows that you don't need to build expensive, custom chips to make drones and robots smarter and more battery-efficient. By simply reorganizing the math to fit the "assembly line" that is already sitting inside our new computers, we can make real-time tracking faster, cheaper, and much more energy-efficient.

In short: KATANA is a software trick that wakes up a sleeping helper engine, teaches it a new language, and lets it do the heavy lifting so the main brain can rest.

Technical Summary: KATANA – A Fast, Low-Power Mapping of Kalman Filters onto Edge NPUs

Problem Statement
Real-time state estimation is the core of modern tracking systems, ranging from defense applications (radar, missile guidance, counter-UAV) to civilian edge deployments (autonomous driving, robotics). These systems operate under strict constraints: measurements must be fused within milliseconds to close the control loop, and total compute must fit within tight battery and thermal envelopes. Currently, Linear and Extended Kalman Filters (LKF, EKF)—the dominant estimators for these tasks—execute almost exclusively on CPUs or custom FPGA/ASIC accelerators. CPU execution serializes multi-object tracking (MOT), limiting throughput, while custom accelerators increase design cycles and silicon area. Although modern AI-PC System-on-Chips (SoCs), such as the Intel Core Ultra Series 1 and 2, integrate low-power Neural Processing Units (NPUs) alongside CPUs and GPUs, these NPUs remain idle during non-neural workloads. The central challenge is that NPUs are optimized for dense multiply-accumulate (MAC) dataflows; standard Kalman filter operations involving subtraction, reshaping, and transposing often force execution onto scalar Digital Signal Processors (DSPs) or require costly context switches, negating the NPU's efficiency benefits.

Methodology
The paper presents KATANA, a novel NPU-aware optimization framework designed to map LKF and EKF algorithms onto commercial AI-PC NPUs without custom silicon. The approach involves authoring filters in PyTorch, exporting to ONNX, and compiling via Intel OpenVINO 2024.5. To ensure 100% of operations execute on the NPU's Data Processing Unit (DPU) matrix engine, KATANA applies three specific algebraic graph rewrites prior to compilation:

Subtract-to-Add Reformulation: The innovation update ( $y_k = z_k - H\hat{x}_{k|k-1}$ ) and other subtraction-heavy steps are reformulated by precomputing a negative-projection matrix ( $H_{neg} = -H$ ). This converts subtractions into additions ( $y_k = z_k + H_{neg}\hat{x}_{k|k-1}$ ), allowing the entire critical path to utilize DPU-native GEMM and Add operations, eliminating DSP-bound subtraction.
Static-Shape Tensor Fusion: Dynamic shape operations (Reshape, Unsqueeze, Squeeze) and Transposes, which typically trigger DSP or DMA fallbacks, are eliminated. The batch axis is lowered to static 1-D and 2-D shapes, and all transposed matrices ( $F^T, H^T, H_{neg}^T$ ) are precomputed and folded into the graph as constants.
Block-Diagonal Batched Parallelization: To address multi-object tracking, $N$ independent filters are packed into a single inference call. System, measurement, noise, and gain matrices are expanded into block-diagonal forms. This saturates the DPU's MAC pipeline by increasing operand width, amortizing dispatch overhead while maintaining numerical independence between filters.

Key Contributions

First Cross-Platform Characterization: The paper provides the first comprehensive evaluation of LKF and EKF inference across CPU, GPU, and NPU on two consecutive generations of shipping AI-PC silicon (Intel Core Ultra Series 1 and Series 2).
First End-to-End NPU Mapping: It demonstrates the first successful mapping of classical signal-processing estimators (LKF/EKF) onto a commercial NPU, achieving full DPU utilization.
Algorithmic Rewrites: The introduction of the three graph rewrites (subtract elimination, static-shape fusion, and block-diagonal batching) that enable 100% DPU execution, removing the need for custom accelerators.
Real-Time Validation: The framework is validated on a live video stream, demonstrating that NPU-resident filters can operate within strict latency budgets while leaving CPU and GPU resources free for detection and downstream analytics.

Results
Experiments conducted on Intel Core Ultra Series 1 and Series 2 platforms yielded the following results:

Throughput: On the Series 2, the optimized batched EKF (processing 200 filters) achieves 223.35 FPS, while the LKF reaches 408.73 FPS. This represents a significant throughput increase over CPU and GPU baselines in the batched regime.
Power and Energy: The optimized NPU pipeline operates within a sustained active power envelope of 13.43 W (EKF) and 14.05 W (LKF). Compared to the CPU implementation on the same workload, this delivers a 97.9% reduction in dynamic energy.
Latency: In a live 30 FPS tracking scenario, the optimized single-instance filters consume less than 1% of the 33 ms frame budget (approx. 0.18–0.19 ms per update), confirming their suitability for always-on tracking without monopolizing the SoC.
Compute Breakdown: Profiling confirms that the optimization rewrites successfully migrate work from DSP and DMA paths to the DPU, with the final batched configurations showing ~95% (LKF) and ~80% (EKF) of execution time dominated by DPU MatMul operations.

Significance
The paper claims that KATANA demonstrates that classical signal-processing pipelines can be re-targeted to existing AI-PC NPUs without the need for dedicated accelerators or custom silicon. By leveraging the "otherwise-idle" NPU, the system achieves a "double dividend": it avoids the area and design-cycle costs of custom hardware while keeping the CPU and GPU free for their primary general-compute and graphics workloads. This enables real-time, low-power tracking on edge platforms where every watt of compute directly impacts mission duration or operational range. The work establishes that with appropriate algorithm-level restructuring, NPUs can effectively serve as general-purpose matrix engines for non-neural, recursive estimators.