Skip to content

[MT] CPU implementation of partition-based categorical split.#12299

Merged
trivialfis merged 14 commits into
dmlc:masterfrom
trivialfis:mt-part-cat
Jul 14, 2026
Merged

[MT] CPU implementation of partition-based categorical split.#12299
trivialfis merged 14 commits into
dmlc:masterfrom
trivialfis:mt-part-cat

Conversation

@trivialfis

@trivialfis trivialfis commented Jul 13, 2026 •
edited
Loading

Copy link
Copy Markdown
Member

Ref: #9043

The following datasets are from UCI, categorical features are forced to use partition-based splits. The comparison is between scalar trees (one tree per target) and vector leaf.

solar_flare: train=1111, eval=278, features=10, outputs=3, rounds=128
  vector: 0.171 seconds, train-rmse=0.33245, eval-rmse=0.61139
  scalar: 0.162 seconds, train-rmse=0.33220, eval-rmse=0.63445
  eval-rmse chg (sc-vl): +0.02306, perf (sc/vl): 0.949783378134431

connect_4: train=54045, eval=13512, features=42, outputs=3, rounds=128
  vector: 0.698 seconds, train-mlogloss=0.33800, eval-mlogloss=0.39686
  scalar: 0.757 seconds, train-mlogloss=0.32513, eval-mlogloss=0.39425
  eval-mlogloss chg (sc-vl): -0.00260, perf (sc/vl): 1.0852552151512045

nursery: train=10368, eval=2592, features=8, outputs=5, rounds=128
  vector: 0.269 seconds, train-mlogloss=0.00328, eval-mlogloss=0.00366
  scalar: 0.306 seconds, train-mlogloss=0.00150, eval-mlogloss=0.00217
  eval-mlogloss chg (sc-vl): -0.00148, perf (sc/vl): 1.136013098815361

car_evaluation: train=1382, eval=346, features=6, outputs=4, rounds=128
  vector: 0.132 seconds, train-mlogloss=0.00585, eval-mlogloss=0.02363
  scalar: 0.158 seconds, train-mlogloss=0.00654, eval-mlogloss=0.02614
  eval-mlogloss chg (sc-vl): +0.00251, perf (sc/vl): 1.1940488904701243

poker_hand: train=820008, eval=205002, features=10, outputs=10, rounds=128
  vector: 17.451 seconds, train-mlogloss=0.28009, eval-mlogloss=0.28601
  scalar: 18.357 seconds, train-mlogloss=0.20474, eval-mlogloss=0.21644
  eval-mlogloss chg (sc-vl): -0.06958, perf (sc/vl): 1.0518899940441868

covertype: train=464809, eval=116203, features=12, outputs=7, rounds=128
  vector: 8.470 seconds, train-mlogloss=0.28692, eval-mlogloss=0.30212
  scalar: 8.356 seconds, train-mlogloss=0.24970, eval-mlogloss=0.27284
  eval-mlogloss chg (sc-vl): -0.02928, perf (sc/vl): 0.9864787202957024

The two features Wilderness_Area and Soil_Type in the covtype are recovered from OHE results.

We might run into issues with zero-weight parent nodes, and there are fallback strategies, but I don't want to make things too complicated at the moment, it's an approximation anyway.

@trivialfis trivialfis mentioned this pull request Jul 13, 2026
Open
48 tasks
@trivialfis
trivialfis requested a review from Copilot July 13, 2026 18:38
Copilot AI reviewed Jul 13, 2026
View reviewed changes

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull request overview

This PR extends the CPU multi-target histogram split evaluator to support partition-based categorical splits (in addition to one-hot), and adds/adjusts tests to validate the new behavior across configurations.

Changes:

  • Implement partition-based categorical split enumeration for HistMultiEvaluator (multi-target CPU hist).
  • Refactor and expand C++ unit tests to cover both one-hot and partition categorical splits (including missing-value behavior).
  • Adjust Python categorical OHE test logic to conditionally run the partition-based comparison depending on device + multi-target support.

Reviewed changes

Copilot reviewed 3 out of 3 changed files in this pull request and generated 2 comments.

File Description
tests/cpp/tree/hist/test_evaluate_splits.cc Refactors multi-target evaluator test setup into a fixture and adds a new partition-split test.
src/tree/hist/evaluate_splits.h Adds partition-based categorical split support to HistMultiEvaluator and small style/type tweaks.
python-package/xgboost/testing/updater.py Updates typing for device and gates partition-based check by device/multi-target support.
Comments suppressed due to low confidence (1)

src/tree/hist/evaluate_splits.h:168

  • The partition-split doc comment still contains a typo ("pseudo-cateogry") and awkward grammar, which makes the description harder to follow. Please correct the spelling/wording while you’re touching this block.
   * @brief Enumerate with partition-based splits.
   *
   * The implementation is different from LightGBM. Firstly we don't have a
   * pseudo-cateogry for missing value, instead of we make 2 complete scans over the
   * histogram. Secondly, both scan directions generate splits in the same

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

Comment thread src/tree/hist/evaluate_splits.h Outdated
Comment thread tests/cpp/tree/hist/test_evaluate_splits.cc
RAMitchell
RAMitchell approved these changes Jul 14, 2026
View reviewed changes

@RAMitchell RAMitchell left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do you think we can refine the variable naming around n_targets? It has a complicated meaning because n_targets can be 1 while the model output targets can be > 1. What if you use leaf_n_targets in the context of vector leaf?

Its not really documented in the code or elsewhere that this projection is a heuristic as compared to the scalar exact solution. I'd like to leave something to future developers as to how we got here.

Whats nice about the projection used is that if n_targets=1 you get the same ordering (or the reverse ordering if parent weight is negative) of the scalar sorting. So this projection is a generalisation of the scalar case (if weight is not zero).

So if weight zero you just get the default ordering right? That seens reasonable. Although it breaks the generalisation above.

@trivialfis

trivialfis commented Jul 14, 2026 •
edited
Loading

Copy link
Copy Markdown
Member Author

Do you think we can refine the variable naming around n_targets?

We can make more verbose names across the codebase.

Whats nice about the projection used is that if n_targets=1 you get the same ordering

Yeah, we can recover the single-target sorting, and we can interpret the projection in a meaningful way

Its not really documented in the code or elsewhere that this projection is a heuristic as compared to the scalar exact solution. I'd like to leave something to future developers as to how we got here.

I will write the document with all the math once we have the complete implementation.

So if weight zero you just get the default ordering right?

Yes, that's the stable_sort.

@trivialfis
trivialfis merged commit 30b750d into dmlc:master Jul 14, 2026
81 checks passed
@trivialfis
trivialfis deleted the mt-part-cat branch July 14, 2026 10:09
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

Copilot code review Copilot Copilot left review comments
@RAMitchell RAMitchell RAMitchell approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@trivialfis @RAMitchell