Decision trees and tree ensembles (such as Random Forests and Gradient Boosted Decision Trees) are remarkably effective for tabular data, reinforcement learning policies, and interpretable control. They route data through explicit, human-readable conditional logic. However, this explicit routing introduces a fundamental mathematical challenge: traditional decision trees are inherently non-differentiable.
To understand why, consider how a standard decision tree makes a choice. A node splits data using a hard threshold function:
$$\text{Route}(x) = \begin{cases} \text{Left} & \text{if } x_i \le \theta \\ \text{Right} & \text{if } x_i > \theta \end{cases}$$
If you plot the output of this routing function against the input feature $x_i$, you get a step function—a flat line, a sudden vertical jump at $\theta$, and another flat line. The derivative (gradient) of a flat line is exactly zero everywhere, and the derivative at the threshold $\theta$ is undefined.
Because the gradients are zero almost everywhere, standard gradient-based optimization algorithms (like backpropagation or stochastic gradient descent) receive no signal on how to adjust the thresholds or feature selections. This non-differentiability forces traditional tree algorithms, such as CART, to rely on greedy, top-down heuristics to build trees one node at a time. Greedy construction often misses globally optimal structures and prevents trees from being integrated directly into end-to-end deep learning pipelines.
To bridge this gap, a major research direction focuses on creating differentiable relaxations of decision trees, allowing them to be optimized globally using gradients while preserving their structural advantages.
Continuous Relaxations: The Smooth Path
The most common way to make a decision tree differentiable is to replace the "hard" threshold functions at each node with "soft," continuous routing functions. Instead of sending a data point 100% to the left or 100% to the right, a soft node routes a fraction of the data point to both branches using a sigmoid or softmax function:
$$\text{Route}_{\text{soft}}(x) = \sigma(\alpha(x_i - \theta))$$
Here, $\sigma$ is the sigmoid function, and $\alpha$ is a scaling parameter that controls the steepness of the split. When $\alpha$ is small, the split is highly smooth and probabilistic; as $\alpha \to \infty$, the function converges back to a hard step function. Because the sigmoid function is smooth, it provides meaningful gradients that can flow backward through the tree structure during training.
This continuous relaxation allows researchers to build hybrid architectures that combine the representation learning of deep neural networks with the structural inductive biases of decision trees. For instance, Sergei Popov et al. developed Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data (NODE), which uses differentiable oblivious trees to achieve state-of-the-art deep learning performance on tabular datasets. Similarly, Kuan-Yu Chen proposed DOFEN: Deep Oblivious Forest ENsemble to leverage relaxed tree structures for explicit sparse feature selection.
By smoothing the decision boundaries, these models can be trained end-to-end alongside neural layers via backpropagation, a capability also explored by Wei Shen et al. in Label Distribution Learning Forests and Jie Zhu et al. in Deep Embedding Forest: Forest-based Serving with Deep Embedding Features.
Training Hard Trees with Soft Gradients
While soft trees are mathematically convenient for training, they lose a key benefit of traditional trees during inference: computational efficiency. A hard decision tree only evaluates a single path from root to leaf, executing in logarithmic time. A soft tree, by contrast, must evaluate every path probabilistically, which scales exponentially with tree depth. Furthermore, soft routing destroys the crisp, deterministic interpretability of standard "if-then" logic.
To achieve the best of both worlds—gradient-based optimization during training and hard execution during inference—researchers use mathematical operators that bypass the non-differentiability of hard thresholds.
One prominent approach is the Straight-Through (ST) estimator. During the forward pass of training, the model uses a hard threshold to route data deterministically. During the backward pass, the algorithm ignores the non-differentiable step function and computes gradients as if it had used a smooth sigmoid relaxation.
Sascha Marton demonstrated the power of this approach with GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent, showing that straight-through gradients allow for the joint, global optimization of all tree parameters simultaneously, outperforming classical greedy algorithms. The authors extended this mechanism to reinforcement learning in Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization (SYMPOL), enabling agents to learn strict, axis-aligned tree policies directly through policy gradient methods without sacrificing performance.
Similarly, Ajaykrishna Karthikeyan et al. developed Dense Gradient Trees in Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent, combining overparameterization with quantization-aware updates to optimize hard trees even under limited, black-box bandit feedback.
Differentiable Approximations for Post-Hoc Tasks
The non-differentiability of tree structures does not just complicate model training; it also hinders downstream tasks that rely on analyzing a model's decision surface.
A prime example is the generation of counterfactual explanations. A counterfactual explanation answers the question: "What is the minimal change required to an input vector to flip the model's prediction?" (e.g., how much must an applicant's income increase to get a loan approved?).
In a differentiable model like a neural network, finding a counterfactual is straightforward: you start at the input point and use gradient descent to walk down the model's loss surface until you cross the decision boundary. In a standard tree ensemble, however, the decision surface is a jagged, discontinuous staircase. The gradient is zero everywhere, leaving gradient-based optimizers stranded.
To resolve this, Ana Lučić et al. introduced FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles. Instead of modifying the underlying tree ensemble, FOCUS constructs a differentiable, probabilistic approximation of the pre-trained forest. This smooth surrogate model exists purely to provide meaningful gradients, allowing standard gradient-based optimization to efficiently locate optimal counterfactuals.
When researchers choose not to rely on smooth approximations for these post-hoc tasks, they must instead abandon gradients entirely and turn to exact discrete optimization frameworks, such as the mixed-integer linear programming methods proposed by Miguel Á. Carreira-Perpiñán et al. in Counterfactual Explanations for Oblique Decision Trees: Exact, Efficient Algorithms.
Global Optimization Without Gradients
An alternative philosophy argues that if decision boundaries are fundamentally non-differentiable, we should change the optimization framework rather than smoothing the model. This branch of work seeks to escape greedy top-down construction by formulating global optimization strategies that respect the discrete nature of trees.
Arman Zharmagambetov et al. utilize an approach called Tree Alternating Optimization (TAO). Instead of computing gradients, TAO decomposes the non-convex, non-differentiable global tree optimization problem into a sequence of local, discrete subproblems. By optimizing the nodes alternatingly, it avoids the suboptimality of greedy splitting.
The authors demonstrated the versatility of this non-gradient global optimization strategy across multiple paradigms, applying it to graph-based regularization in Semi-Supervised Learning with Decision Trees: Graph Laplacian Tree Alternating Optimization and to the creation of highly compact, accurate ensembles in Smaller, more accurate regression forests using tree alternating optimization.
Key Foundational Work
Finding Multivariate Splits in Decision Trees Using Function Optimization (1994) — contributed 1 concept elements to this direction.
Classifier Ensemble with Unlabeled Data (2009) — contributed 1 concept elements to this direction.