fastforest

Fast approximate random-forest regression in Rust, with Python bindings.

Across six numeric and mixed-data regressions, fastforest is fastest to fit and predict in every completed comparison while retaining competitive accuracy. Both forests use 50 trees and otherwise use their default hyperparameters:

_{Bold is best for that dataset and metric. Results use one fixed 80/20 split on a 16-core Apple M4 Max; fit includes preprocessing and FastForest's adaptive pilot. See Benchmarking for details and reproduction instructions.}

Benchmarking

The table compares 50-tree FastForest and sklearn random forests with default sklearn HistGBM. Each dataset uses the same reproducible 80/20 split. FastForest's adaptive default selected 90% of features for SGEMM and Diamonds and 60% for California Housing, Allstate, and Diabetes. Concrete retained the 75% fallback because its training split has fewer than 8,000 rows.

For mixed data, sklearn RF uses median imputation plus missing indicators for numeric columns, one-hot encoding through 20 categorical levels, and target encoding above 20. HistGBM uses native categoricals through its 255-level limit and target encoding above that. Fit timing includes model construction, schema inspection, preprocessing, and fitting, but excludes process startup and inter-process transfer. Prediction timing includes input transformation. Every model/dataset combination has a 180-second limit; sklearn RF reached it on Allstate. The SGEMM target is the log-transformed mean runtime.

Install the development dependencies and release build, then reproduce one dataset with:

pip install -e '.[dev]'
maturin develop --release
python tools/accuracy.py --dataset california

Available datasets are sgemm, california, concrete, diamonds, allstate, and diabetes. Run FastForest alone with --ff_only, or reproduce the complete table with:

for dataset in sgemm california concrete diamonds allstate diabetes; do
  python tools/accuracy.py --dataset "$dataset"
done

Install

pip install fastforest

Usage

import numpy as np
from fastforest import FastForest

rng = np.random.default_rng(42)
X = rng.random((1_000, 6))
y = 4*X[:, 0] - 2*X[:, 1] + X[:, 5]

model = FastForest(seed=42, oob=True).fit(X, y)
predictions = model.predict(X[:5])
oob_predictions = model.oob_prediction_
oob_counts = model.oob_counts_

X may contain numeric values, numeric strings, ordinary strings, and configured missing values. y is converted to contiguous float32; it must have one finite value per row.

Data preparation

FastForest fits a deterministic schema for every input column:

1. Non-missing values are parsed as float32 when every value can be parsed and are otherwise treated as strings. Numeric columns sort numerically and other columns sort lexically. Numeric columns whose values are all integral retain that metadata so analysis displays them with no decimal places.
2. A column with more than max_dummy_cardinality distinct values is replaced during training by its zero-based rank in that sort order. A column with cardinality c <= max_dummy_cardinality becomes c-1 boolean dummy features; the least-common value is omitted as the all-zero case. Frequency ties are resolved deterministically by sort order. max_dummy_cardinality defaults to 4.
3. The default missing value is the empty value. Override it per column with missing_values, using column names or indexes. When training contains a missing value, FastForest adds <column>_missing and fills the value feature with the observed median. A column containing no training missing values rejects missing values during prediction rather than silently inventing an imputation rule. Entirely missing columns are discarded.

X = np.array([
    ["18", "red",   ""],
    ["42", "blue",  "3.5"],
    ["31", "green", "2.0"],
], dtype=object)

model = FastForest(missing_values={2: ""}).fit(X, [1, 4, 3])

Ranking is a compact training representation, not a prediction-time requirement for numeric columns. After fitting, rank cutoffs are converted back to native numeric boundaries, so seen and unseen numeric values are compared directly without a rank lookup. Nonnumeric values are mapped through their fitted lexical ordering. An unseen low-cardinality value naturally receives all-zero dummies; an unseen high-cardinality value receives its insertion rank. Missing checks and median routing are retained only for columns that contained missing training values.

Schema fitting and inference transformation run natively in Rust and parallelize independent columns with Rayon. Python only adapts NumPy and data-frame column buffers and retains display metadata for the analysis API. Pandas categorical columns pass their integer codes and vocabulary directly rather than being expanded into Python object arrays.

Generated ranks, dummies, and missing indicators remain internal. Feature importance, explanations, and partial-dependence results aggregate them back to the original column and display its original values. Fitted interpretations are available in model.column_info_.

For reproducible sklearn comparisons on the same raw dataframe, sklearn_preprocessor implements the policy used by the benchmark: numeric median imputation with missing indicators, one-hot encoding through 20 categorical levels, target encoding above 20, and removal of empty columns.

from sklearn.ensemble import RandomForestRegressor
from sklearn.pipeline import make_pipeline
from fastforest import sklearn_preprocessor

preprocess = sklearn_preprocessor(X_train, missing_values={"age":"?"})
model = make_pipeline(preprocess, RandomForestRegressor(n_estimators=50, n_jobs=-1))
model.fit(X_train, y_train)

Install the optional dependencies with pip install 'fastforest[sklearn]'.

Algorithm

Each tree draws min(floor(bootstrap_fraction * n_rows), bootstrap_max) training rows, with replacement when replacement=True and otherwise without it. When bootstrap_fraction=None, it resolves to 0.8 with OOB enabled and 1 otherwise. Fractions above 1 are supported with replacement; without replacement the maximum is 1. Pass bootstrap_max=None to disable the cap. At each node, the default histogram splitter:

1. A node with fewer than min_node_size rows, or whose first max_node_samples sampled targets are equal, becomes a leaf.
2. A random contiguous window containing at most max_node_samples of the node's shuffled rows is selected.
3. The tree randomly selects floor(max_features * n_features) feature units, with a minimum of one. Encoded features are independent units except that every numeric value feature and its missingness indicator form one atomic unit.
4. For each selected feature, the sampled rows are sorted by their encoded rank and every distinct observed boundary is evaluated. The split that most improves size-weighted negative sample standard deviation is selected, subject to the sampled child-size minimum.
5. Every terminal leaf predicts the mean target of all training rows that reached it, including leaves where candidate evaluation found no useful split.

The defaults are 50 trees, minimum node size 4, all rows capped at 40,000 without replacement, histogram splitting over 75% of feature units, at most 320 evaluated rows per node, and unregularized leaf means. Enabling OOB changes the default sampling fraction to 0.8 so every row can receive held-out predictions. Preprocessing and trees build in parallel over columns and trees respectively, while batch predictions run in parallel over rows. Supplying seed makes the fitted forest deterministic regardless of parallel scheduling.

For more than 8,000 training rows, adaptive=True selects a feature fraction of 0.6 or 0.9 while keeping max_node_samples=320. It draws one fixed 8,000-row pilot sample and fits max(2*n_threads, 32) trees per candidate, sampling 50% of the pilot rows without replacement in each tree. Candidates use matching seeds and in-bag rows and are compared by mean squared OOB error; an exact tie favors 0.6. The selected pair is available as adaptive_choice_, and both (max_features, max_node_samples, oob_mse) results are in adaptive_scores_. Set adaptive=False to use workbench.max_features directly.

Tree-building workbench

Workbench keeps interchangeable tree-building choices separate from the forest parameters. Its defaults reproduce the histogram algorithm above; the original random-cutoff search remains available for experiments and comparisons:

from fastforest import FastForest,Workbench

alternate = Workbench(
    splitter="random",
    max_features="sqrt",
    leaf_regularization=0,
)
model = FastForest(workbench=alternate, seed=42).fit(X, y)

splitter="histogram" is the production default. It randomly selects max_features, builds sparse target-statistic histograms from the node evaluation window, and checks every observed boundary for those features. splitter="random" proposes random (feature, value) cutoffs, deduplicates them, and evaluates them on the same kind of node window. Its candidate count is controlled by min_candidate_rows, candidate_attempt_factor, and cutoff_divisor. max_features accepts "sqrt", "all", a fraction in (0, 1], or a positive feature count and is ignored by the random splitter.

leaf_regularization shrinks each terminal full-node mean towards its parent node mean, treating the value as a number of parent pseudo-rows. Zero selects the unregularized production mean. Split search and leaf regularization are independent, so every splitter, feature selection, and regularization combination can be tested without adding branches to the forest API.

The focused sweep tool takes comma-separated workbench grids. Random splitting ignores the histogram-only max_features grid rather than running duplicate configurations:

python tools/sweep.py --dataset california \
  --splitters random,histogram --max_features sqrt,0.5,all \
  --leaf_regularizations 0,2,8,32

Out-of-bag predictions

OOB calculation is opt-in with oob=True. After fitting:

• oob_prediction_ contains each training row's mean prediction from trees that did not sample that row.
• oob_counts_ contains the number of contributing trees.
• A row with no contributing tree has count zero and prediction NaN.
• Sampling without replacement at bootstrap_fraction=1.0 leaves no OOB rows, so all counts are zero and predictions are NaN.

Both attributes are None when OOB is disabled.

Model analysis

FastForest includes NumPy-only analysis tools. Data frames are accepted and supply feature names automatically; arrays use x0, x1, and so on. Plot methods import matplotlib only when called.

Importance

Use validation-set permutation importance by default. It measures the drop in model score after shuffling a feature without retraining:

importance = model.feature_importance(X_valid, y_valid)
importance.sorted()
importance.plot()

Correlated features can substitute for one another and therefore look individually unimportant. Permute them together to measure their joint importance:

importance = model.feature_importance(X_valid, y_valid,
    features={"location": ["latitude", "longitude"]})

model.drop_column_importance(X_train, y_train, X_valid, y_valid) performs the slower complementary analysis: it refits the forest without each feature. It accepts the same features groups. model.split_importance() returns the nearly free, normalized training-time split-gain measure, but permutation or grouped permutation is preferable because split importance is biased by the available cutoffs and correlated predictors.

Individual predictions and uncertainty

explanation = model.explain(X_valid[:3])
explanation.row(0)   # (feature, observed value, contribution), strongest first
explanation.plot(0)

tree_predictions = model.predict_trees(X_valid)
prediction_std = model.predict_std(X_valid)

For every row, prediction = bias + contributions.sum(). Contributions telescope through each tree's decision path and are then averaged across trees. They explain this forest's computation, not causality; correlated features can redistribute contributions between themselves.

Partial dependence and ICE

year = model.partial_dependence(X_train, "year_made")
year.plot()                   # average PDP plus individual conditional-expectation lines
year.plot(centered=True)
year.plot(clusters=5)         # representative centered ICE curves

interaction = model.partial_dependence(X_train, ["year_made", "sale_year"])
interaction.plot()

enclosure = model.partial_dependence(X_train,
    {"enclosure": ["enclosure_ac", "enclosure_erops", "enclosure_orops"]})

Partial dependence repeatedly replaces the selected feature values and averages the resulting predictions. ICE retains the individual prediction lines. These plots describe the fitted model rather than a causal intervention, and highly correlated features can produce unrealistic synthetic rows.

Collinearity and redundancy

from fastforest import feature_dependence,feature_relations

relations = feature_relations(X_train)
relations.groups(threshold=0.2)
relations.plot()
relations.plot_dendrogram()

dependence = feature_dependence(X_train)
dependence.predictability     # validation R² for predicting each feature from the others
dependence.plot()             # which other features provide that predictive information

feature_relations uses tie-aware Spearman correlation and average linkage implemented directly with NumPy. feature_dependence detects nonlinear redundancy by treating each feature in turn as a target, fitting a small forest from the remaining features, and measuring grouped prediction and permutation dependence.

Development

The project is locally installed with maturin until it joins the aai-ws workspace:

maturin develop
cargo test
pytest -q

For performance work, build the extension in release mode and run the benchmark:

maturin develop --release
python tools/bench.py

Compare accuracy and timings against sklearn's random forest and histogram GBM on one fixed California Housing split:

python tools/accuracy.py

Use --dataset concrete for the smaller Concrete Compressive Strength regression dataset, or --dataset sgemm for the 241,600-row SGEMM GPU Kernel Performance dataset. Every dataset uses one reproducible 80/20 split. Each model/dataset combination runs in an isolated process with a three-minute timeout; process startup and input transfer are excluded from reported timings.

Use --ff_only with --min_node_size, --bootstrap_fraction, --bootstrap_max, --replacement, --max_node_samples, and --cutoff_divisor for focused FastForest experiments. These spellings come directly from the call_parse function parameters.