Advancing Decision Tree-Based Online Inference for Edge Computing

Decision trees (DTs) are attractive for edge computing due to their interpretability and modest computational cost. However, DT inference is typically implemented as a sequential, data-dependent traversal from root to leaf, which induces unpredictable branching and irregular memory accesses on microcontrollers. This limitation becomes critical in online inference, where sensor samples are generated continuously and must be classified with strict latency and energy budgets. We present SNAP (Speculative Node Anticipation Process), a DT traversal kernel designed for online inference at the edge. SNAP turns the traversal into a speculative procedure, selecting a candidate path from root to leaf and evaluating its split predicates in parallel using vector extensions. We implement SNAP using an ARM Cortex-M55 MCU with ARM Helium and evaluate it on different benchmarks. Compared to a state-of-the-art scalar baseline, SNAP achieves up to 59.92% lower latency.