Depth Separations for Multi-Class Tree Cascades via Modular Addition

A central advantage of deep learning is its ability to transform representations progressively across layers. Motivated by this principle, deep forest brings layer-wise representation learning to tree ensembles by passing predictions from one layer to the next. This raises a basic question: when does such sequential representation make tree-based models fundamentally more efficient than simply growing a tree or adding more trees in parallel? We study this question through modular addition, a simple task that is difficult to resolve by spatial partitioning but remarkably easy to summarize sequentially. Large tree regions inevitably mix different residues, forcing single trees to use increasingly fine partitions. Adding trees in parallel can create more partitions, but does not provide the same reusable summary. By contrast, a cascade only needs to propagate the running residue, compressing exponentially many input prefixes into only $p$ states. We prove that single trees require exponentially many leaves, and bounded-error forests remain stretched-exponentially large for even moduli, whereas a cascade computes the same target exactly with only linear complexity. Extensive experiments validate these theoretical findings, demonstrating that trained cascades recover the predicted running-residue representation and achieve near-perfect accuracy with substantially fewer leaves than single trees and random forests.