Performance

Fit quality, runtime, and memory use depend on the search method and the data. Measure complete fits on representative inputs and compare quality on held-out rows before changing the search policy.

Choose a split-search method

fit_tree and fit_boost accept the same split_search keyword:

Use exact search as the reference. Try local bins when threshold search is expensive, including multiclass fits. Hybrid search supports scalar scores.

using LinearTrees, Random, Statistics

rng = Xoshiro(8)
X = rand(rng, 600, 4)
y = sin.(6 .* X[:, 1]) .+ X[:, 2] .+ 0.1 .* randn(rng, 600)
train, valid = 1:450, 451:600
searches = (ExactSearch(), BinnedSearch(nbins = 64), HybridSearch(nbins = 64))

map(searches) do search
    tree = fit_tree(X[train, :], y[train]; split_search = search, max_depth = 4)
    error = predict(tree, X[valid, :]) .- y[valid]
    (search = nameof(typeof(search)), rmse = round(sqrt(mean(abs2, error)); digits = 3))
end

((search = :ExactSearch, rmse = 0.105), (search = :BinnedSearch, rmse = 0.105), (search = :HybridSearch, rmse = 0.105))

Local bins

BinnedSearch(nbins = 64, refine = true) builds bins from each node's rows. Tied values stay together. Candidate scores use weighted moments of the original values, so binning restricts thresholds without replacing features by bin centers.

Refinement searches the two bins beside the winning coarse boundary. It does not run when a constant or unsplit line wins. Small nodes use exact search. Set refine = false to omit refinement.

For Softmax, all score coordinates share one split. Candidate scores sum their coordinate objectives using the same diagonal-Hessian approximation as exact search. This also supports vector-valued Frozen targets and multiclass boosting. Bins count stored rows, while fitting and minimum leaf sizes use frequency weights. Replicating weighted rows can therefore change the bins.

classes = [row[1] > 0.5 ? 1 : row[2] > 0.5 ? 2 : 3 for row in eachrow(X)]
multiclass = fit_tree(X[train, :], classes[train], Softmax(3);
    split_search = BinnedSearch(nbins = 32), max_depth = 4)
probabilities = predict(multiclass, X[valid, :])
mean(argmax.(eachrow(probabilities)) .== classes[valid])

1.0

Global bins with local refinement

HybridSearch(nbins = 64) prepares bins from the training data once and reuses them as the tree grows. It refines the winning boundary using raw rows in its neighboring occupied bins. Small nodes use exact search.

For boosting, bins come from all positive-weight training rows and are reused across rounds. Row sampling selects from those bins. Validation data never determines bin boundaries.

Hybrid search avoids the full presort index used by exact and local-bin search. This can reduce memory use, but need not give the fastest fit. Its bin count must lie in 2:65535.

Both approximate methods can change node choices and predictions. Neither has an approximation-error bound. More bins allow more thresholds, but held-out accuracy need not improve monotonically.

Threads

Start Julia with multiple threads, then set how many a call may use:

julia --threads=auto --project

tree = fit_tree(X, y; nthreads = 4)
model = fit_model_tree(X, y; split_search = BinnedSearch(), nthreads = 4)
yhat = predict(tree, Xnew; nthreads = 4)

The default is Threads.nthreads(). Small workloads remain serial where threading would add overhead. More threads can increase scratch-memory use. Model trees parallelize binned feature scans on large nodes; exact scans stay serial. Use nthreads = 1 when an outer loop already parallelizes independent fits.

Reuse prediction storage

predict! fills a caller-provided output array:

tree = fit_tree(X[train, :], y[train]; max_depth = 4)
Xnew = X[valid, :]
out = Vector{Float64}(undef, size(Xnew, 1))
predict!(out, tree, Xnew)
round.(out[1:4]; digits = 3)

4-element Vector{Float64}:
  1.383
 -0.771
  1.561
 -0.314

For Softmax(K), use an n × K matrix. Storage reuse does not change the model or prediction scale.

Measure repeatable work

Separate compilation and data construction from timed fitting. BenchmarkTools is an optional benchmarking dependency:

using BenchmarkTools

fit_tree(X, y; nthreads = 1) # compile before measuring
@benchmark fit_tree($X, $y; nthreads = 1)

Inspect allocation counts and bytes as well as runtime. For boosted fits with sampling, create a fresh seeded RNG for each repetition. Reusing an advanced RNG changes the sampled trees between calls.

Wider inputs

The benchmark suite in bench/validation.jl compares nine fitting methods on nested row and predictor subsets. bench/VALIDATION.md records the data, validation policy, model budgets, and commands. It measures full fits, including the routing tree before a ridge refit, and records test error alongside cost.

For example, the 8,000-row, 32-predictor model-tree fixture gave these results on an Apple M4 Pro with Julia 1.13, one Julia thread, and one BLAS thread:

These are averages over two seeds, with three warmed timing samples per seed. All model trees used every predictor, depth 3, minimum leaf 40, and ridge penalty 1. The signal used four predictors and noise SD 0.2. Coarse search was 6.1 times faster here, while refinement used more memory. This synthetic result does not establish an accuracy ranking or a speedup on other datasets.

Diagnose a slow fit

The optional benchmark environment has a profiling runner for ordinary trees, boosting, continuous trees, prediction, and SHAP. Use one Julia thread when comparing search policies; the runner sets BLAS to one thread. The case filter avoids rerunning unrelated fits, and the output setting keeps generated profiles outside the checkout:

JULIA_NUM_THREADS=1 LT_PROFILE_CASES=7,8 \
    LT_PROFILE_OUT=/tmp/lineartrees-profiles \
    julia --project=bench bench/profile.jl

Cases 7 and 8 fit a 30-round boosted model and a four-split continuous tree on fixed synthetic data. Case 9 compares exact, refined, and coarse model-tree fits. Case 10 checks near-affine scoring with a small step beside a large linear signal. Cases 1–9 use StableRNGs seeds; case 10 preserves its original Xoshiro fixture, so compare it on the same Julia version. Each case records a BenchmarkTools median, total bytes and allocation count, a CPU profile, and a sampled allocation profile. The PProf flame graphs and their logs share the chosen output directory. Raw sampled bytes in an allocation profile are not a total-memory estimate; use the benchmark bytes for that. The synthetic cases locate expensive code paths, but do not measure accuracy or speed across datasets and machines.

Run bench/typecheck.jl in the same bench environment to check targeted JET inference for tree, boost, and continuous calls and write jet.txt and warntype.txt. It fails on a new report in a direct model call. Reports from the data-driven table, MLJ, and dictionary adapters are shown separately in jet.txt for inspection.