Bisection Regression Trees: Recursive Binary Classification Cascades for Continuous Prediction

We present Bisection Regression Trees (BRT), a regression method that recursively partitions the target’s value space rather than its feature space. At every node, BRT asks a single binary question, is the target above or below the median value currently observed, delegates the answer to a standard probabilistic classifier, and combines both possible answers through the law of total expectation rather than committing to either one. We give a complete mathematical account of the design: an entropy argument for why the partition point is the median rather than the mean or the range midpoint, a derivation of the soft prediction rule from first principles, an empirical-Bayes shrinkage rule for leaf estimates, and five further configurable mechanisms (local leaf regressors, per-node feature subsampling, target jitter, temperature-scaled probabilities, and weighted-sample support) whose individual contributions we isolate by ablation. We describe an efficient batched prediction procedure and show it is asymptotically necessary, not merely convenient, for the method to be usable at scale. Across four regression datasets and five choices of node-level classifier, BRT closes most of the gap to gradient boosting machines and, in one configuration, exceeds a tuned XGBoost baseline outright. We close with a short case study applying the same construction to ordinal classification.