Metraipolis › archive › dc_0dccfea7afca

TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference — arXiv:2610.03939

Source: arXiv
Original: https://arxiv.org/abs/2610.03939
License (as archived): CC0-1.0
Archived: 2026-10-06T05:29:13.576Z
SHA-256 of the archived text: dfcde4e03520fc0b6a4bbc5832130b00ccf7a3c94f26adb57be86cd182b60df7
Stable URL of this page: https://metraipolis.com/documento/dc_0dccfea7afca

How to cite

TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference — arXiv:2610.03939 — arXiv, https://arxiv.org/abs/2610.03939 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0dccfea7afca (Metraipolis archive dc_0dccfea7afca, sha256 dfcde4e03520fc0b6a4bbc5832130b00ccf7a3c94f26adb57be86cd182b60df7)

BibTeX

@misc{dc0dccfea7afca,
  title = {TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference — arXiv:2610.03939},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.03939},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0dccfea7afca; sha256 dfcde4e03520fc0b6a4bbc5832130b00ccf7a3c94f26adb57be86cd182b60df7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.03939. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Many inference workloads evaluate a trained 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 every item in a search session, and scenario analyses vary a few inputs while holding the rest fixed. Standard inference treats each row independently and repeats the shared work $G$ times. We present TreeWalker, which applies partial evaluation to grouped inference: constant features are static, varying features dynamic. It walks each tree once per group, partitions a row bitmask at varying splits, and skips empty subtrees. Training is unchanged: TreeWalker reads standard LightGBM and XGBoost models. 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 a $(d_v+1)/(d+1)$ fraction of a row-independent walk as $G \to \infty$. On Intel, TreeWalker is 2.5-3.2$\times$ faster than a row-independent traversal at the reference configuration ($T=500$, $L=8$) and 6.8-7.8$\times$ faster at $G=128$ on the survival datasets, with larger gains on Arm. On a scenario-analysis benchmark it is faster in all 16 configurations on both architectures. For f64 models, outputs match treelite's GTIL up to summation order; for f32 models, f64 accumulation is closer to a Kahan-compensated reference than native f32 on 99.98% of rows and never farther.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.PF, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Performance (cs.PF); Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2610.03939 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:25:05.314Z dalla pagina https://arxiv.org/list/cs.PF/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).