解读、编辑｜张意梅
审核｜蒲诗瑶
KDD 2026
论文题目：XGBoost: A Scalable Tree Boosting System
作者：Tianqi Chen，Carlos Guestrin
“我们的论文《XGBoost：一种可扩展的树提升系统》荣获了 KDD 2026 Test of Time Award（时间检验奖）。这一荣誉属于一路推动 XGBoost 项目发展至今的整个社区。”
——Tianqi Chen，2026 年 8 月 10 日
XGBoost 最初并非为了成为“明星项目”。读博期间，陈天奇因现有工具不便而自行编写了该程序。转折发生在 Kaggle 竞赛中，XGBoost 助力其团队登顶 Higgs Boson Challenge 排行榜。随后，随着 Python、R 等接口的加入，它从个人研究代码演变为数据科学界的通用工具。
2016 年，陈天奇与导师 Carlos Guestrin 在 KDD 发表论文，系统总结了其在效率、可扩展性及工程实现上的设计。十年后的今天，这篇论文荣获“时间检验奖”，印证了其设计的长远价值。
导读：一篇论文，十年后为何还能获奖？
2026 年，发表于 KDD 2016 的《XGBoost: A Scalable Tree Boosting System》获得KDD 2026 Test of Time Award（时间检验奖）。该奖项关注的并非发表当年的热度，而是工作在多年后是否仍持续影响研究与实践。
早在论文发表前，XGBoost 已在数据科学竞赛中迅速走红。据统计，2015 年 Kaggle Blog 发布的 29 个获胜方案中，17 个使用了 XGBoost；同年 KDD Cup 前十名队伍全部采用该技术。在门店销量预测、广告点击率预估等各类结构化数据任务中，XGBoost 均表现出极强竞争力。
XGBoost 为何能同时兼顾效果、速度与规模？论文给出的答案不仅是一组算法改进，更是一套将算法与系统协同优化贯穿始终的设计。实验显示，在特定单机任务上，XGBoost 比当时对照实现快一个数量级以上；借助外存与分布式设计，系统更可扩展至十亿级样本。这种“算法设计与硬件/系统约束共同考虑”的思路，正是其经得起时间检验的关键。
论文四大核心贡献包括：
（1）设计并实现了高度可扩展的端到端树提升系统；
（2）提出理论上严格证明的加权分位数草图（Weighted Quantile Sketch），高效计算候选分裂点；
（3）提出面向并行树学习的稀疏感知（Sparsity-aware）算法；
（4）提出用于外存计算的缓存感知块结构（Cache-aware Block Structure）。
树提升入门：一个正则化目标走天下
树集成模型：加法模型 + 回归树
XGBoost 的基座是梯度提升决策树（GBDT）。模型由 K 棵回归树（CART）组成，最终预测值是所有树输出之和：
ŷᵢ = φ(xᵢ) = Σₖ₌₁ᴷ fₖ(xᵢ)，fₖ ∈ F
其中每棵树 fₖ 由树结构 q（映射样本到叶子编号）与叶子权重 w 组成。与普通决策树不同，回归树叶子上存储的是连续分数而非类别。
图 1 | 树集成模型示意图
如图所示，两棵树共同对样本进行预测：tree1 依据规则将其落入权重 +2 的叶子，tree2 依据规则将其落入权重 +0.9 的叶子。最终预测值为两棵树叶子分数之和：y = 2 + 0.9 = 2.9。
正则化目标：对树复杂度直接罚款
XGBoost 训练时最小化的目标函数在传统损失之外增加了正则项，直接惩罚模型复杂度：
L(φ) = Σᵢ l(ŷᵢ, yᵢ) + Σₖ Ω(fₖ)
其中 Ω(f) = γT + ½λ‖w‖²
其中 T 为叶子数量，w 为叶子权重向量。γT 惩罚叶子过多，½λ‖w‖² 惩罚权重过大。正则化目标倾向于选择“简单而有效”的预测函数，避免过拟合。
结构分数：每棵树长什么样，一个分数说了算
树集成模型无法在欧氏空间中直接优化，只能逐轮贪心加树。论文对目标做二阶泰勒展开，对于固定结构的树，可解析求出叶子最优权重与对应目标值：
w*ⱼ = − Σᵢ∈Iⱼ gᵢ ⁄ (Σᵢ∈Iⱼ hᵢ + λ)
L̃* = −½ Σⱼ (Σᵢ∈Iⱼ gᵢ)² ⁄ (Σᵢ∈Iⱼ hᵢ + λ)+γT
该分数类似决策树中的不纯度指标，但适用于更广泛的目标函数，可直接衡量树结构的好坏。
图 2 | 结构分数（Structure Score）计算示意
评定树结构质量无需真正完成训练：只需将落在每个叶子上的样本的一阶梯度 gᵢ、二阶梯度 hᵢ 分别求和，套用评分公式即可。此外，作者还沿用了两项经典防过拟合技巧：Shrinkage（收缩）与列（特征）采样。
分裂查找算法：精确、近似与稀疏感知
精确贪心算法：穷举一切分裂点
树学习的关键是找到最佳分裂点。精确贪心算法枚举所有特征上的所有可能分裂点：先按特征值排序，再线性扫描累积梯度统计。单机版的 XGBoost、scikit-learn 与 R 的 gbm 都支持这一算法。
图 3 | 精确贪心分裂查找算法
当数据大到放不进内存或需要分布式训练时，精确枚举无法高效进行，这就需要近似算法。
近似算法：按分位数提出候选点
近似算法先按特征分布的分位数提出候选分裂点，把连续特征映射到候选点划分的桶中。根据提出候选点的时机分为两种变体：全局变体在树构建之初提出全部候选点；局部变体在每次分裂后重新提出。
图 4 | 近似分裂查找算法
图 5 | 不同分裂查找算法在 Higgs 10M 数据集上的测试 AUC 收敛对比
实验说明，合理选择近似精度可以在显著减少候选分裂点的同时保持接近精确算法的预测表现。
加权分位数草图（Weighted Quantile Sketch）是近似算法的理论基石。候选点的选取满足特定误差范围，其中秩函数按样本的二阶梯度 hᵢ 加权。论文提出的分布式加权分位数草图支持带权数据的合并与剪枝操作，并给出相应的理论精度保证。
稀疏感知算法：为缺失值学习默认方向
真实数据往往高度稀疏。XGBoost 为每个树节点学习一个默认方向：样本在分裂特征上缺失时，直接归入默认方向。
图 6 | 带默认方向的树结构示例
默认方向本身并非人工指定，而是由算法从数据中学习得到。关键改进在于分裂查找时只访问非缺失项，并分别枚举“缺失归左”与“缺失归右”两种方向，选择增益更大的方案。这使计算量能够随非缺失项数量而扩展。
图 7 | 稀疏感知算法在 Allstate-10K 数据集上的加速效果
在该高度稀疏数据集上，稀疏感知算法比不考虑稀疏性的朴素实现快 50 倍以上。
系统设计：为硬件而生的 Block 结构
列块结构：排序一次，反复复用
树学习中最耗时的环节是让数据保持有序。XGBoost 将数据存放在内存单元Block中：按压缩列（CSC）格式存储，且每列已按特征值预排序。这份排序在训练前只做一次，之后所有迭代复用。
图 8. 用于并行学习的块结构
数据按列存放于块中，块内每列按对应特征值排序。一次对块中某列的线性扫描即可枚举完该列所有分裂点。精确贪心算法把整个数据集放进单个块做线性扫描，且所有叶子的分裂查找统一进行。复杂度方面，精确算法从原始的 O(Kd‖x‖₀·log n) 降至 O(Kd‖x‖₀ + ‖x‖₀·log n)。
缓存感知：别让间接访存拖后腿
块结构按特征值排序访问，意味着梯度统计必须按行索引间接取用——这是非连续内存访问，会立即产生读写依赖。当梯度统计大到超出 CPU 缓存时，cache miss 会显著拖慢分裂查找。
图 9 | 引起流水线停顿的短程数据依赖
对精确贪心算法，XGBoost 采用缓存感知预取：每个线程分配内部缓冲区，把梯度统计先成批取入，再以 mini-batch 方式累积，把短依赖拉长以摊薄等待。
图 10 | 缓存感知预取在精确贪心算法中的效果
在千万级样本的大数据集上，缓存感知实现比朴素实现快约 2 倍。对近似算法，解决方案是选择合适的块大小，在缓存局部性与并行效率之间取得平衡。
外存计算：让单机也能处理超大规模数据
为了让一台机器的全部资源都被榨干，XGBoost 把数据分块存到磁盘，用独立线程预取到内存缓冲区，让计算与磁盘读取并行。两项技术进一步提升磁盘吞吐：
（1）块压缩（Block Compression）：按列压缩块，载入内存时由独立线程即时解压；
（2）块分片（Block Sharding）：将数据交替分片到多块磁盘，每块磁盘配一个预取线程，训练线程轮流从各缓冲区读取，成倍提升磁盘吞吐。
实验验证：从单机到 17 亿样本，XGBoost 如何扩展
XGBoost 以开源包形式实现，支持 Python、R、Julia 等语言，分布式版本基于 rabit 库的 allreduce 实现，可原生运行于 Hadoop、MPI 等平台。实验使用的数据集如下：
表 1｜实验数据集概览
单机分类与排序
表 2｜Higgs-1M 上精确贪心方法对比，500 棵树
在 Higgs-1M 分类任务的论文实验设置下，XGBoost 与 scikit-learn 的测试精度基本相当，而单棵树训练时间相差一个数量级以上。
表 3｜Yahoo! LTRC 学习排序对比，500 棵树
在 Yahoo! LTRC 学习排序实验中，XGBoost 相比对照系统训练更快，同时取得相当的排序效果。
外存实验：一台机器跑完 17 亿样本
图 11 | Criteo 数据集不同子集上的外存计算方法对比
朴素算法只能处理约 2 亿样本便耗尽磁盘空间；加入块压缩带来 3 倍加速；再分片到两块磁盘又获 2 倍加速。最终方案（压缩 + 分片）在单台 AWS c3.8xlarge 上处理完了全部 17 亿样本。
分布式实验：更少资源，更大规模
图 12 | 32 台 EC2 节点上各分布式系统在 Criteo 不同子集上的对比
在该实验配置下，XGBoost 的单轮迭代时间显著低于 Spark MLLib 及 H2O 优化版本；随着数据规模增加，Spark 受到内存容量限制后性能明显下降，而 XGBoost 借助外存计算继续扩展。
图 13 | XGBoost 在 Criteo 全量 17 亿样本上随机器数量的扩展性
仅用 4 台机器即可处理全部 17 亿样本；机器增多时性能近线性提升。
表 4｜主流树提升系统能力对比
可以看到，XGBoost 是当时唯一在六项能力上全部支持的系统。
结论与影响
这篇论文留下的不仅是一个工具，也是一套构建大规模机器学习系统的设计经验：缓存访问模式、数据压缩、分片与外存调度，都可能直接决定算法能否真正扩展到现实数据规模。将算法层面的设计与系统层面的优化结合起来，是 XGBoost 能够在有限计算资源下处理大规模数据的重要原因。
值得注意的是，树模型并非万能：在序列、视觉等非结构化数据任务中，深度模型通常更具优势。即便如此，XGBoost 所体现的“算法与系统协同设计”仍具有长期影响。直到今天，XGBoost 仍常被用作表格数据竞赛与生产任务中的强基线之一。
十年之后获得 KDD Test of Time Award，真正被“时间检验”的或许不只是 XGBoost 这个具体工具，更是论文背后的一个朴素原则：好的机器学习系统，不只要让算法在公式上成立，还要让它在真实硬件、真实数据规模和真实工程约束下跑得起来。
注：本文涉及的速度、扩展性与系统对比数据，除特别说明外，均指原论文在其当时硬件、软件版本、数据集与参数设置下报告的实验结果，不应直接外推为对现代实现或所有任务场景的普遍结论。
点击 阅读原文 查看原论文