[MT] GPU implementation of partition-based categorical split.#12305
Conversation
cleanup. work. bounds. impl. test. small cleanups. cleanups. cleanup. avoid calc. Python tests. naming. Apply suggestions from code review Co-authored-by: Copilot Autofix powered by AI <[email protected]> typing. cleanups. test. work on sort. sort. test. Fix finalize split. tests impl. note.
There was a problem hiding this comment.
Pull request overview
This PR extends XGBoost’s GPU multi-target (vector-leaf) histogram algorithm to support partition-based categorical splits (in addition to one-hot categorical splits), aligning GPU behavior more closely with the CPU categorical split capabilities and adding coverage + documentation for the vector-leaf ordering heuristic.
Changes:
- Implement partition-based categorical split evaluation for GPU vector-leaf (
MultiHistEvaluator), including category bitfield storage for chosen splits. - Update GPU histogram updaters to consume evaluator-provided categorical bitfields (instead of synthesizing one-hot bitfields manually).
- Add/expand CPU+GPU Python/C++ tests and documentation for mixed categorical split behavior and partition ordering for multi-output trees.
Reviewed changes
Copilot reviewed 20 out of 20 changed files in this pull request and generated 1 comment.
Show a summary per file
| File | Description |
|---|---|
| tests/python/test_updaters.py | Consolidates categorical OHE test cases by parameterizing (tree_method, multi_target). |
| tests/python/test_multi_target.py | Adds CPU test coverage for mixed categorical split behaviors in multi-target training. |
| tests/python-gpu/test_gpu_updaters.py | Expands GPU categorical tests, including bitfield boundary coverage for scalar/vector cases. |
| tests/python-gpu/test_gpu_multi_target.py | Adds GPU test coverage for mixed categorical split behaviors in multi-target training. |
| tests/python-gpu/test_gpu_data_iterator.py | Extends categorical OHE iterator tests to cover multi-target on GPU. |
| tests/cpp/tree/gpu_hist/test_row_partitioner.cu | Updates external-memory position encoding test to validate SamplePosition usage. |
| tests/cpp/tree/gpu_hist/test_multi_evaluate_splits.cu | Adds C++ unit test for categorical partition split evaluation in multi-target GPU evaluator. |
| src/tree/updater_gpu_hist.cuh | Wires categorical storage sizing + evaluator reset for multi-target GPU hist; uses evaluator-provided cats for tree expansion. |
| src/tree/updater_gpu_hist.cu | Uses evaluator-provided category bitfields for categorical split expansion (scalar GPU hist). |
| src/tree/updater_gpu_common.cuh | Adds MultiSplitCandidate::UpdateCat for partition-based categorical splits (vector-leaf path). |
| src/tree/gpu_hist/row_partitioner.cuh | Adjusts final position kernel to pass global row index to the finalization op and store into batch-local output span. |
| src/tree/gpu_hist/multi_evaluate_splits.cuh | Adds persistent device storage for categorical split bitfields and a host-copy accessor. |
| src/tree/gpu_hist/multi_evaluate_splits.cu | Implements histogram sorting + partition scan/eval for categorical splits in vector-leaf GPU evaluator. |
| src/tree/gpu_hist/evaluator.cu | Minor include/comment cleanup in scalar GPU evaluator compilation unit. |
| src/tree/gpu_hist/evaluate_splits.cuh | Adds cat_storage_size into shared inputs for multi-target evaluation kernels. |
| src/tree/gpu_hist/evaluate_splits.cu | Uses dh::WarpThreads() constant for block sizing. |
| python-package/xgboost/testing/updater.py | Refactors categorical OHE test helper to support multi-target consistently and asserts partition-vs-onehot expectations. |
| python-package/xgboost/testing/multi_target.py | Adds check_categorical_mixed to validate mixed numerical/OHE/partition splits for multi-output trees. |
| doc/tutorials/multioutput.rst | Documents the vector-leaf categorical partition ordering heuristic and limitations. |
| doc/tutorials/categorical.rst | Links categorical tutorial to the vector-leaf (multi-output) variant documentation. |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
Co-authored-by: Copilot Autofix powered by AI <[email protected]>
RAMitchell
left a comment
RAMitchell
left a comment
There was a problem hiding this comment.
Our split evaluation code is getting more and more complicated and starts to look like it needs a refactor.
|
|
||
| we have :math:`s_c = \alpha_c \lVert w_p \rVert_2`, so ordering the projected scores is | ||
| equivalent to ordering the scalar coefficients :math:`\alpha_c`. In general, however, it | ||
| is an approximation: category contrasts orthogonal to the parent update can be missed, |
|
One more from codex: P2 src/tree/gpu_hist/multi_evaluate_splits.cuh (line 89): AllocNodeCats makes node_cat_storage_size_ sticky after the first categorical dataset, but Reset (line 422) only resets need_sort_histogram_. Since each new DMatrix computes cat_storage_size from cuts_->MaxCategory() at src/tree/updater_gpu_hist.cuh (line 185), reusing the same GPU multi-target updater with a categorical dataset whose max category crosses a bitfield word boundary will hit CHECK_EQ(this->node_cat_storage_size_, storage_size) at src/tree/gpu_hist/multi_evaluate_splits.cuh (line 93). The scalar GPU evaluator resets its category storage from the current cuts each time, so this path should probably reset or recompute node_cat_storage_size_/split_cats_ during Reset. |
In general, we don't support swapping out a training matrix mid-session with different types of data (an increased number of categories is a change of type). |
Ref: #9043