TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference

Durmus Karatay; Richard Newman

cs.LGOct 2, 2026

TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference

Authors: Durmus Karatay, Richard Newman

Organizations: Shopify

Abstract

Many prediction tasks evaluate a trained tree ensemble on groups of rows 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 ignores this input-side correlation. We present TreeWalker, which instantiates partial evaluation for grouped tree-ensemble inference: constant features are static, varying features dynamic. TreeWalker walks each tree once per group, partitions a row bitmask at varying splits, and skips empty subtrees via an unsplit shortcut. It reads standard LightGBM and XGBoost models; training is unchanged. 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ρ_G)$ . On Intel, TreeWalker is ${\sim}3\times$ faster than a row-independent traversal at the reference model size ( $T{=}500$ , $L{=}8$ ; $G{=}16$ for SUPPORT/FLCHAIN and empirical groups for Expedia) and $7.7$ -- $9.1\times$ faster at $G{=}128$ on the survival datasets; on Arm, $2.5$ -- $2.9\times$ and $5.5$ -- $6.0\times$ . On a scenario-analysis benchmark it is faster in all $16$ configurations on both machines. For f64 models, outputs match treelite GTIL up to tree-ordering roundoff; for f32 models, TreeWalker's f64 leaf accumulation is closer than native f32 to an exactly rounded reference on every audited row.

Figures & tables

Panel of Figure 1 — Figure 1: Worked example: a 4-row group with shared $x_{1}{=}2$ and varying $x_{5}{=}[2,4,7,9]$ . (a) Standard inference evaluates $x_{1}\leq 3$ four times and $x_{5}\leq 5$ four times. (b) TreeWalker evaluates the constant split once, carries the active-row mask $[1111]$ , and partitions it at the varying split into $[1100]$ and $[0011]$ before leaf accumulation.

Dataset	Evaluator	4	16	64	128	$G\to\infty$
		Group size $G$				Asymptote
SUPPORT	trace	0.674	0.432	0.361	0.351	0.334
SUPPORT	precompute (default)	0.507	0.226	0.154	0.143	0.125
FLCHAIN	trace	0.544	0.451	0.439	0.431	0.417
FLCHAIN	precompute (default)	0.420	0.213	0.153	0.140	0.125

Table 1: Per-row work ratio

W(\mathcal{F},X)/(G\cdot T\cdot L)

at the reference configuration (

T=500

L=8

, LightGBM, Intel) on the fixed-

G

datasets, swept across

G\in\{4,16,64,128\}

. The final column gives the Corollary 1 asymptote under this baseline:

(d_{v}+1)/L

for trace (with

d_{v}

estimated from partition_row_evals at

G=128

) and

1/L

for precompute (the leaf-write floor). Both evaluators decrease monotonically in

G

and approach their predicted limits. XGBoost numbers (not shown) are within

6\%

of LightGBM except SUPPORT trace at

G{=}64

(

13.5\%

higher). SUPPORT’s horizons of

64

and

128

hold

58

and

104

rows (§ 5.2 ). Expedia is excluded from this sweep because it has variable group sizes; it appears alongside the speedup grid in § 5 .

Dataset	Type	Groups	Rows/Group	Const Feat.	Vary Feat.	Const%
SUPPORT	Survival	1,774	Swept (1–104)	14	6	70%
FLCHAIN	Survival	1,304	Swept (1–1,008)	8	6	57%
Expedia	CTR	10,000	Variable (5–37)	10	11	48%

Table 2: Datasets. The constant fraction

|F_{c}|/(|F_{c}|+|F_{v}|)

is a feature-level proxy for shareable work; the realized work-share is captured by the path statistic

(d_{v}+1)/L

in Table 1 . The scenario-analysis dataset is described in § 5.6 .

Panel of Figure 2 — Figure 2: Algorithmic speedup across all $(T,L)$ combinations on Intel, for (a) FLCHAIN ( $G{=}16$ ), (b) SUPPORT ( $G{=}16$ ), and (c) Expedia (empirical groups). Each cell: arithmetic mean of the two framework-specific speedups. Darker = higher speedup.

Figure 3: Per-observation latency (

\mu

s) for each inference method at the reference configuration (

T{=}500

L{=}8

G{=}16

), on Intel. Error bars: p5–p95 over the cell’s

48

measurement blocks.

Figure 4: Algorithmic speedup vs. group width

G

(

T{=}500

L{=}8

, Intel). (a) FLCHAIN, (b) SUPPORT, (c) Expedia cohorts by size. Ribbons:

95\%

intervals.

$k$	$d_{v}$	Measured ratio	Predicted $(d_{v}+1)/L$	Speedup (Arm)	Speedup (Intel)
1	0.50	0.195	0.188	$9.2\times$	$15.2\times$
2	1.15	0.276	0.268	$8.4\times$	$12.8\times$
4	2.09	0.395	0.386	$7.4\times$	$10.3\times$
8	3.81	0.611	0.601	$6.2\times$	$8.1\times$

Table 3: Scenario analysis at

G{=}128

: measured trace-evaluator work ratio

W/(G\cdot T\cdot L)

against the Corollary 1 prediction under this baseline,

(d_{v}+1)/L

, and algorithmic speedup over the same-layout full walk. Work counters are identical on both architectures.

k

counts selected perturbed features.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

	Intel	Arm
GCE machine type	c4-standard-32	c4a-highmem-16
CPU	Xeon Platinum 8581C	Google Axion (Neoverse V2)
Frequency	2.3 GHz base, 3.1 GHz all-core turbo	3.0 GHz
Cores	16 (SMT disabled)	16
L1d / L1i (per core)	48 KiB / 32 KiB	64 KiB / 64 KiB
L2 (per core)	2 MiB	2 MiB

Appendix

Table 4: Hardware specifications. Per-core cache sizes; L3 shared. Both VMs in the same GCE zone, SMT disabled, at the all-core turbo frequency.

Package	Version	Role
Rust	1.97.1	TreeWalker + sweep_bench
GCC	15.2.0	Native libraries, tl2cgen, lleaves linking
LightGBM	4.7.0	Model training + native predict
XGBoost	3.4.1	Model training + native predict
treelite	4.7.2	Model export (binary) + GTIL reference
tl2cgen	1.0.0	Compiled predict baseline

Appendix

Table 5: Software versions (identical on both VMs).

Method	Description
LightGBM native	C API: PredictForMat or a loop of PredictForMatSingleRowFast ; CMake Release with -march=native
XGBoost native	C API: one PredictFromDense call or a one-row loop; CMake Release with -march=native
tl2cgen (LightGBM+XGBoost)	Compiled C trees via treelite (GCC -O3 -march=native ); its runtime or a loop of the generated predict
lleaves (LightGBM)	LLVM-compiled trees ( -O3 code generation for the host CPU; trees not inlined into the forest loop)
QuickScorer (LightGBM+XGBoost)	Bitvector-based predictor ( quickscorer-rs ), on the encoded Expedia variant and the five original-Expedia cells of LightGBM’s $T{=}50$ , $L{=}2$ model (Appendix D )
TreeWalker	Partial evaluation (this work)

Appendix

Table 6: Inference methods compared in § 5 . TreeWalker (full walk) uses TreeWalker’s data layout but evaluates rows independently, isolating partial evaluation from implementation differences. Each baseline with two interfaces is timed through the faster one per cell, chosen by an untimed probe.

Field	Type	Description
value	f64	Threshold, inline category bitset or bitset-pool offset, or leaf output
skip	i16	Tree-local index of the light child ( $-1$ = leaf)
varying_pred_id	u16	Index into varying-predicate array
feature	u16	Feature index
flags	u8	Bitfield: default_left, categorical, inline_cat, heavy_is_left, walkable, vary_type (2 bits: constant, increasing, decreasing, non-monotonic)
cat_n_words	u8	Bitset word count (categorical splits)

Appendix

Table 7: Node layout (16 bytes).

Term	Counter (proxy)	Source
$C(\tau,X)$	constant_steps	per-tree stats (exact)
$V(\tau,X)$	varying_splits	per-tree stats (exact)
$G$	group size	known (exact)
$Q_{\mathrm{pre}}$	precompute_row_evals $+$ partition_row_evals	per-group stats (proxy)
$\|T_{c}(\tau,X)\|$	offline replay against $(\tau,X)$	one-time post-process

Appendix

Table 8: Trace counters used to validate Theorem 1 componentwise.

C

V

G

are tracked exactly;

Q_{\mathrm{pre}}

is a row-evaluation proxy that misses the

G\log G

sort term and the predicate-set-size terms in Eq. ( 3 ).

Framework	$T$	$L$	TreeWalker ( $\mu$ s)	QuickScorer ( $\mu$ s)	QS/TW (Intel)	QS/TW (Arm)
LightGBM	50	2	5.38	3.44	$0.64$	$0.75$
LightGBM	500	4	67.13	61.22	$0.91$	$1.43$
LightGBM	1000	4	107.35	105.35	$0.98$	$1.61$
XGBoost	50	2	6.85	3.90	$0.57$	$0.69$
XGBoost	50	4	16.95	10.35	$0.61$	$0.88$
XGBoost	500	2	34.85	24.09	$0.69$	$0.77$

Appendix

Table 9: QuickScorer vs. TreeWalker on the encoded Expedia variant, in the

11

cells whose QuickScorer outputs validate. Latencies are Intel’s, in

\mu

s per session. QS/TW is QuickScorer’s latency divided by TreeWalker’s; values below

1

mean QuickScorer is faster. The two

0.98

ratios on Intel are within

\pm 2\%

Figure 5: Empirical convergence of the per-row work ratio

W(\mathcal{F},X)/(G\cdot T\cdot L)

vs. group size

G

(log scale) at the reference configuration (

T=500

L=8

, LightGBM) on the fixed-

G

datasets; the counts are the same on both machines. Solid lines: trace provisioning (no precompute). Dashed lines: precompute provisioning (default). Horizontal reference lines mark the limits under this baseline: the Corollary 1 asymptote

(d_{v}+1)/L

for trace (per-dataset, in matching color) and the structural leaf-write floor

1/L

for precompute (dataset-independent, the lowest line at

0.125

). Trace approaches its limit from above as row-dependent predicate work scales with

G

; precompute drops faster because its per-group provisioning cost is spread across more rows. Visualizes the data in Table 1 (§ 4.4 ).

Figure 6: Algorithmic speedup vs. tree depth

L

(

T{=}500

G{=}16

, Intel). On the survival datasets shallower trees yield higher speedup. Ribbons:

95\%

intervals.

Figure 7: Algorithmic speedup vs. ensemble size

T

(

L{=}8

G{=}16

, Intel). Ribbons:

95\%

intervals.

Figure 8: Intel vs. Arm algorithmic speedup for the

544

cells of the factorial grid (log-log). Points above the diagonal indicate higher Arm speedup; dashed line = parity.

Figure 9: Slowdown when each flag is disabled in isolation, in percent: the disabled latency over a research build of the kernel with every flag on, minus one (monotonic early-termination: against the build with precomputation off), at

T{=}500

L{=}8

on Intel. The research build is within

-4\%

+6\%

of production at the anchors.

G

is the reference

G{=}16

for SUPPORT, empirical sessions for Expedia, and

G{=}4

for FLCHAIN. Flags are sorted by the geometric mean slowdown over the three anchors. Bars: mean over the frameworks and both ablation runs, which agree within

0.9

percentage points.

$k$	$G$	Speedup (Arm)	Speedup (Intel)	Trace ratio	Predicted	Precompute ratio
1	4	$1.77\times$	$1.96\times$	0.413	0.188	0.351
1	16	$4.46\times$	$5.16\times$	0.245	0.188	0.183
1	64	$7.74\times$	$11.79\times$	0.202	0.188	0.140
1	128	$9.21\times$	$15.15\times$	0.195	0.188	0.133
2	4	$1.47\times$	$1.60\times$	0.502	0.268	0.359
2	16	$3.72\times$	$4.16\times$	0.329	0.268	0.186

Appendix

Table 10: Full scenario-analysis sweep. Speedup is algorithmic speedup over the same-layout full walk. Work ratios are

W/(G\cdot T\cdot L)

under the trace and default (precompute) evaluators; the trace prediction under this baseline is

(d_{v}+1)/L

with

L=8

Rows per group	Intel	Arm
$256$	$1.17\times$ [ $1.13$ , $1.21$ ]	$1.19\times$ [ $1.14$ , $1.26$ ]
$512$	$1.22\times$ [ $1.15$ , $1.28$ ]	$1.20\times$ [ $1.13$ , $1.25$ ]
$1{,}008$	$1.19\times$ [ $1.07$ , $1.38$ ]	$1.12\times$ [ $1.07$ , $1.31$ ]

Appendix

Table 11:

128

-row chunks against whole groups on FLCHAIN: chunked latency over whole-group latency, median [min, max] over the

8

cells (

T\in\{500,2000\}

L\in\{8,16\}

, LightGBM and XGBoost) at each horizon.

Efficient Inference

Efficient inference reduces the compute, memory, latency, or energy needed to produce accurate predictions, posterior estimates, and decisions.

See all 109 papers

Vectorized Dynamic Histograms for Sparse Oblique Forests
Feb 27, 2026Ariel Lubonja, Jungsang Yoon, Haoyin Xu +6Gradient-Boosted Decision Trees Tabular ML
Johns Hopkins University Baltimore, Maryland, USA · Google Zurich, Switzerland
MotherTree: Meta-learning on synthetic data improves decision tree training
Oct 7, 2026Ziyuan Wang, Fredrik D. JohanssonDecision Tree Learning Meta-Learning
Chalmers University of Technology University of Gothenburg
EMA-FS: Accelerating GBDT Training via Gain-Informed Feature Screening
Jun 24, 2026Yan SongGradient-Boosted Decision Trees Tabular ML
PayPal, Inc.

Feb 27, 2026J/K move · Enter open · S save

Vectorized Dynamic Histograms for Sparse Oblique Forests

Ariel Lubonja, Jungsang Yoon, Haoyin Xu, Yue Wan+5

Johns Hopkins University Baltimore, Maryland, USA · Google Zurich, Switzerland

Gradient-Boosted Decision Trees Tabular ML Random Forest

Open paper AskPDF arXiv

Sparse oblique (SPO), part of the top-ranked configuration of Google's Yggdrasil Decision Forests (YDF), improve the accuracy while maintaining interpretability of Random Forests (RF) and Gradient Boosted Trees (GBT) by scanning a sparse linear combination of features instead of a single feature. Because projections are sampled at runtime, training is significantly slower, as pre-run optimizations such as presorting cannot be used. We overhaul SPO training in YDF, first by fixing inefficiencies in the released version, achieving 2-5x speedup, then by devising two novel methods, one aimed at GBTs and the other at RFs: (1) Hierarchical AVX2 and AVX-512-vectorized histogram filling speeds up typical GBT-depth trees by up to 1.6x in SPO-GBT and 2x for SPO-RF, and (2) runtime-dynamic histograms between vectorized histograms and exact splits, speeds up deeper, RF depth-typical trees (depths 16 to purity) by up to 1.6x with no detectable effect on accuracy. Our optimizations bring SPO-RF training time on par with YDF's axis-aligned RF. We extensively evaluate on 8 natural and 11 synthetic datasets of up to 10.5 million rows and 1.6 million features, from depth 6 to purity, and open-source the implementation.

Abstract

Efficient Inference

Explore similar work

Vectorized Dynamic Histograms for Sparse Oblique Forests

MotherTree: Meta-learning on synthetic data improves decision tree training

EMA-FS: Accelerating GBDT Training via Gain-Informed Feature Screening