RandomForest best-first growth (max_leaf_nodes) picks a worse leaf-expansion order than sklearn #3771

Describe the bug

When max_leaf_nodes is set (best-first tree growth), a single onedal/sklearnex RandomForestClassifier tree reaches a worse training fit than the equivalent sklearn.ensemble.RandomForestClassifier tree for the same leaf budget, even with bootstrap=False, max_features=None, and max_bins=n_samples (so bootstrap sampling, feature subsampling, and histogram binning are all ruled out as causes).

With no leaf limit (grow to purity) or with a depth-first constraint (max_depth, min_samples_split), sklearnex and sklearn trees match essentially exactly. The discrepancy appears specifically when best-first growth is triggered by max_leaf_nodes.

This looks like a distinct issue from #3648 (which was about the regression random splitter's impurity weighting), this one affects RandomForest too (best splitter), and is in the best-first growth / leaf-selection logic shared by classification and regression.

To Reproduce

import numpy as np
from sklearn.datasets import make_classification
from sklearn.metrics import brier_score_loss, log_loss
import sklearn.ensemble
import sklearnex.ensemble

n_samples, n_features, n_informative = 1000, 20, 10
X, y = make_classification(
    n_samples=n_samples,
    n_features=n_features,
    n_informative=n_informative,
    n_redundant=0,
    n_classes=2,
    random_state=123,
)

def fit_eval(est):
    est.fit(X, y)
    p = est.predict_proba(X)[:, 1]
    return brier_score_loss(y, p), log_loss(y, p)

# every source of randomness removed: single tree, no bootstrap, no feature
# subsampling, and max_bins == n_samples so the CPU histogram is at full
# per-sample resolution.
common = dict(n_estimators=1, bootstrap=False, max_features=None, random_state=0)

for label, constraint in [
    ("unconstrained", {}),
    ("max_depth=4 (depth-first)", {"max_depth": 4}),
    ("min_samples_split=8 (depth-first)", {"min_samples_split": 8}),
    ("max_leaf_nodes=42 (best-first)", {"max_leaf_nodes": 42}),
]:
    b_skl, ll_skl = fit_eval(sklearn.ensemble.RandomForestClassifier(**common, **constraint))
    b_ex, ll_ex = fit_eval(
        sklearnex.ensemble.RandomForestClassifier(max_bins=n_samples, **common, **constraint)
    )
    print(f"{label}")
    print(f"  sklearn  : brier={b_skl:.4f} logloss={ll_skl:.4f}")
    print(f"  sklearnex: brier={b_ex:.4f} logloss={ll_ex:.4f}")

Expected behavior

For the depth-first-constrained and unconstrained cases, sklearnex already matches sklearn to floating-point precision — the same is expected for max_leaf_nodes, since it's still supposed to be growing the single best-first tree that maximizes impurity decrease per leaf used.

Actual behavior

unconstrained
  sklearn  : brier=0.0000 logloss=0.0000
  sklearnex: brier=0.0000 logloss=0.0000

max_depth=4 (depth-first)
  sklearn  : brier=0.1171 logloss=0.3738
  sklearnex: brier=0.1171 logloss=0.3738

min_samples_split=8 (depth-first)
  sklearn  : brier=0.0087 logloss=0.0248
  sklearnex: brier=0.0083 logloss=0.0238

max_leaf_nodes=42 (best-first)
  sklearn  : brier=0.0562 logloss=0.2136
  sklearnex: brier=0.0691 logloss=0.2325

The max_leaf_nodes case is consistently and substantially worse for sklearnex (≈+23% Brier, ≈+9% logloss here), while every depth-first case matches. avg_n_leaves is identical (42) in both cases — the shape of the tree differs (sklearnex trees come out shallower on average for the same leaf count across repeated runs), which points at the best-first leaf-expansion order rather than at individual split quality.

Root cause & fix

Traced to buildBestFirst/buildNode in cpp/daal/src/algorithms/dtrees/forest/df_train_dense_default_impl.i, shared by RandomForest/ExtraTrees, classification/regression. Two independent bugs, both now fixed.

[FIXED in #3772] Bug 1 — wrong leaf-selection priority formula. The priority used to rank pending leaves was computed as imp * item.totalWeights - impLeft * item.leftWeights - (item.totalWeights - item.leftWeights) * (imp - impLeft). This had two compounding issues: item.leftWeights was read before it was ever set for the split being evaluated (every freshly built WorkItem initializes it to 0.0), which collapses the formula to totalWeights * impLeft and ignores the right child (and its weight) entirely; and, independently, the right-child impurity was approximated as (imp - impLeft) instead of the actual computed value, which is only exact when the parent's impurity equals the weighted average of the children's — not true in general for Gini or variance impurity.

Bug 2 — leaf budget spent at the wrong time. Even with the formula fixed, a real (but smaller) gap to sklearn remained. The cause: buildBestFirst's leaf-count budget (remainingSplitNodes) was being spent at node-birth time — the instant a child is created, in a fixed left-then-right order, immediately after its parent is popped from the priority queue — instead of at node-selection (pop) time. This let a low-priority node consume the last available split slot simply by being evaluated first, even when a genuinely higher-priority node elsewhere in the frontier hadn't had its turn yet. sklearn's BestFirstTreeBuilder avoids this by re-checking its own budget fresh every time it pops a node, decrementing only on an actual commit-to-split. A structural tree diff confirmed this was a real, one-sided bug rather than floating-point noise: the nodes sklearn split that sklearnex left as leaves had ground-truth impurity_improvement 0.0029–0.0035, while the nodes sklearnex split instead (that sklearn left as leaves) had only 0.0017–0.0025. A Python simulation of both variants (birth-order-eager vs. pop-time-lazy budget checking) confirmed the lazy version reproduces sklearn's real tree for the repro above exactly (identical node count, leaf count, max depth, and full leaf-depth histogram), while the eager version reproduces sklearnex's actual buggy shape. PR with a proposed fix: #3773

Result: with both fixes applied, the max_leaf_nodes=42 case from the repro above now matches sklearn within ordinary cross-implementation floating-point noise (sklearn brier=0.056150413952262807 vs sklearnex brier=0.055019580618929476 — sklearnex is now marginally better, i.e. no longer a one-sided systematic miss), down from the original +23% gap reported above. Both PRs include a regression test (a small toy dataset each) that was numerically verified to fail on the corresponding pre-fix code and pass with the fix.

Environment

scikit-learn-intelex (importlib.metadata): 2026.1.0
daal4py._get__daal_link_version__():       20260100b'P'_20260601
scikit-learn:                              1.8.0
OS:                                        Linux-6.17.0-1032-oem-x86_64-with-glibc2.39 (Ubuntu)

Installed via pixi / conda, CPU only.