TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference

Many prediction tasks evaluate a tree ensemble on row groups that share feature values: discrete-time survival models expand each patient into $G$ time steps, click-through-rate models score each item in a search session, and scenario analyses vary a few inputs while keeping others fixed. Standard tree-ensemble inference treats each row independently, ignoring this input-side correlation. We instantiate partial evaluation for grouped tree-ensemble inference: constant features are static, varying features dynamic. The algorithm walks each tree once per group, partitions a row bitmask at varying splits, and skips empty subtrees via an unsplit shortcut. We prove a structural work decomposition: per-tree work splits into the constant-projected subtree size $|T_c|$, $G$ leaf writes, and a predicate-mask provisioning cost $Q$. For the trace evaluator, per-row work approaches $(d_v+1)/(d+1)$ as $G\to \infty$, giving asymptotic speedup $1/(1-{\bar{\rho }}_G)$. Empirically, TreeWalker delivers $\sim 3\times$ algorithmic speedup over a row-independent traversal at the reference model size ($T=500$, $L=8$; $G=16$ for SUPPORT/FLCHAIN and empirical groups for Expedia), rising to $6.8$–$7.8\times$ at $G=128$ on the survival datasets. For f64 models, outputs match treelite GTIL up to tree-ordering roundoff; for f32 models, TreeWalker's f64 leaf accumulation is close to a Kahan-compensated reference than native f32 on $99.98\%$ of rows, with the remaining $0.02\%$ tied.