acceptodds
Under review as a conference paper at ICLR 2027

Depth Separations for Multi-Class Tree Cascades via Modular Addition

Abstract

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 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.

Primary area:
learning theory
Keywords:
Depth Separation, Deep Forest, Representation Complexity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9wPtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies when sequential composition makes tree models more efficient than growing a single tree or adding trees in parallel. The studied task is modular addition, cm,p(x)=∥x∥1 mod pc_{m,p}(x) = \lVert x \rVert_1 \bmod p over {0,…,p−1}m\{0,\dots,p-1\}^m.

There are three main results:

  1. A tree cascade represents the target exactly with (m−1)p2(m-1)p^2 leaves (Theorem 5).
  2. A single tree needs Ωp(pm)\Omega_p(p^m) leaves to do even slightly better than chance 1/p1/p (Theorem 6).
  3. For even pp, a plurality forest with error ϵ<1/2\epsilon < 1/2 needs 2Ω((1−2ϵ)m)2^{\Omega((1-2\epsilon)\sqrt{m})} leaves (Theorem 7). The proof reduces to binary parity and uses a voting-polynomial argument.

Experimentally, they compute optimal single trees on small domains via exact dynamic programming and train single trees, tree cascades, and random forests on a constructed 8-class distribution. Trained cascades reach near-perfect accuracy with far fewer leaves than the other models.

Critical strengths
  1. The authors show that the separation between cascades and single trees holds even for approximate predictions and multiple classes. A single tree needs exponentially many leaves to beat chance accuracy 1/p1/p by a fixed margin, while a cascade computes the target exactly with linearly many leaves. Previous work only cover binary labels with small error, so this shows the gap doesn’t come from requiring exact representation or binary labels.

  2. Theorem 7 extends the cascade–forest separation of Lyu et al. (2024) from exact representation to any error ϵ<1/2\epsilon < 1/2, and drops their restriction on the size of individual trees. This is the paper’s most significant new result, since it directly supports the claim that adding trees in parallel can’t replace sequential composition.

Critical weaknesses
  1. The forest result is limited to even pp and has a relatively weak bound. Theorem 7 only applies to even pp, and the proof relies on reducing the problem to binary parity. The forest result in this paper does not fully extend to the multi-class setting. The exponent 1−2ϵ12m\frac{1-2\epsilon}{12}\sqrt{m} is vacuous at realistic mm (about 4040 leaves at m=104m = 10^4). The tightness of this bound should be discussed.
Questions for authors
  1. The training setup (two fixed bits plus a parity of at most 8 bits, with a tuned prefix-length distribution) seems designed for cascades to succeed.I think the abstract’s claim that trained cascades “recover the running-residue representation” is not fully supported. Can you show results under a less tailored distribution? For example, without the prefix-length curriculum.
  2. Theorem 6.1 appears to follow from the Lemma 3 argument of Lyu et al. (2024), which gives the stronger bound pm(1−2ϵ)p^m(1-2\epsilon) for all ϵ<1/2\epsilon < 1/2. What is new in Theorem 6.1?
9 comments

Thank you for your comments. Below please find our responses.

W1 Even moduli and tightness of the forest bound

W1: The forest result is limited to even pp and has a relatively weak bound. Theorem 7 only applies to even pp, and the proof relies on reducing the problem to binary parity. The forest result in this paper does not fully extend to the multi-class setting. The exponent 1−2ϵ12m\frac{1 - 2 \epsilon}{12} \sqrt{m} is vacuous at realistic mm (about 4040 leaves at m=104m = {10}^{4}). The tightness of this bound should be discussed.

Thank you for raising these two points. The contribution of Theorem 7 is the persistence of the cascade–forest separation at positive error, as your review recognizes: for fixed even p∈2N+p\in2\mathbb{N}^+ and fixed 0⩽ϵ<1/20\leqslant\epsilon<1/2, hard-plurality forests satisfy

L⩾1−2ϵ8 2(1−2ϵ)m/12,L \geqslant \frac{1-2\epsilon}{8}\,2^{(1-2\epsilon)\sqrt{m}/12},

ruling out polynomial leaf complexity in mm while the cascade is exact with (m−1)p2(m-1)p^2 leaves.

1. Asymptotic tightness of Ω(2Θ(m))\Omega(2^{\Theta(\sqrt{m})}). In complexity terms, Ω(2Θ(m))\Omega(2^{\Theta(\sqrt{m})}) already establishes a super-polynomial separation from the O(m)\mathcal{O}(m) cascade, and we agree its asymptotic tightness should be discussed directly. At ϵ=0\epsilon=0, majority-vote forests require exponential size 2Ω(m)2^{\Omega(m)} on parity [2]. When ϵ∈(0,1/2)\epsilon\in(0,1/2), zero-error leaf counting no longer applies; our proof truncates trees to depth d=Θ(log⁡L)d=\Theta(\log L) and represents pairwise plurality voting as the sign of a degree-dd polynomial threshold function (PTF), invoking the bounded-error PTF degree bound d=Ω(m)d=\Omega(\sqrt{m}) of Aspnes et al. [1]. Because Θ(m)\Theta(\sqrt{m}) is tight for general PTF degree approximations of parity [1], any reduction treating depth-dd forests as general degree-dd PTFs encounters the m\sqrt{m} exponent, whereas not every low-degree PTF is realizable by a small plurality forest of axis-aligned trees. Whether the bounded-error forest lower bound can be strengthened from Ω(2Θ(m))\Omega(2^{\Theta(\sqrt{m})}) to Ω(2Θ(m))\Omega(2^{\Theta(m)}) remains an open problem, now stated explicitly in Section 4.3.

2. Multi-class plurality voting and even pp. Beyond prior results restricted to binary output (p=2p=2), exact representation (ϵ=0\epsilon=0), or per-tree size caps [2], Theorem 7 covers all even multi-class moduli p∈{4,6,8,…}p\in\{4,6,8,\ldots\} with unrestricted tree sizes and full pp-way voting in {0,…,p−1}\{0,\ldots,p-1\}. When ϵ>0\epsilon>0 and p⩾3p\geqslant3, trees can divert votes to third classes c∉{r0,r1}c\notin\{r_0,r_1\}, so multi-way argmax is not a single polynomial sign unless third-party votes are controlled. Embedding the order-22 subgroup {0,p/2}⩽Zp\{0,p/2\} \leqslant \mathbb{Z}_p via ϕx(b)i=(xi+(p/2)bi) mod p\phi_{\boldsymbol{x}}(\boldsymbol{b})_i=(x_i+(p/2)b_i)\bmod p partitions Zpm\mathbb{Z}_p^m into uniform cosets where the true label takes only two values {r(x),r(x)+p/2}\{r(\boldsymbol{x}),r(\boldsymbol{x})+p/2\}: votes for the other p−2p-2 classes never help the true class beat its antipodal competitor, isolating pairwise vote difference as a degree-dd sign polynomial. For odd pp, Zp\mathbb{Z}_p lacks an order-22 element and any nontrivial subproblem spans at least three residues, requiring multi-way PTF or Zp\mathbb{Z}_p-character techniques noted as an open direction in Section 4.3.

Empirically, even at p=8,m=10p=8, m=10, hard-plurality voting forests already require orders of magnitude more leaves than cascades across five seeds, as reported below.

Model (p=8,m=10p=8, m=10, Original Mixture, 5 Seeds)Aggregation RuleMean Total Leaves ↓\downarrowHard-Vote / Cascade Test Acc. (%) ↑\uparrow
Tree cascade (TC-7, Ours)Sequential state propagation112.0 ±\pm 0.099.96 ±\pm 0.01
Compact RF (⩽2,048\leqslant2{,}048-leaf cap, 9 trees)Hard plurality vote1,152.0 ±\pm 0.082.60 ±\pm 0.05
Fixed RF-29 (depth 15, d\sqrt{d} splits)Hard plurality vote158,859.4 ±\pm 6,259.191.81 ±\pm 0.36
Validation-selected RF (19 trees, all features)Hard plurality vote35,973.4 ±\pm 421.199.95 ±\pm 0.01

We have added the tightness and odd-pp discussions to Section 4.3 (pp. 6–7) of the revised paper. Thank you very much.

Q1 Removing short-prefix signal and testing the learned state

Q1: The training setup (two fixed bits plus a parity of at most 8 bits, with a tuned prefix-length distribution) seems designed for cascades to succeed.I think the abstract’s claim that trained cascades “recover the running-residue representation” is not fully supported. Can you show results under a less tailored distribution? For example, without the prefix-length curriculum.

Thank you for this insightful question. Following your suggestion, we ran five-seed controls (700,000700{,}000 train / 300,000300{,}000 test examples per seed) that (1) remove short prefixes completely (J=7J=7 fixed), (2) test untuned prefix distributions, (3) directly compare nonfinal predictions with running residues s4,…,s9s_4,\ldots,s_9, and (4) shuffle transmitted states across examples. Results are reported in the table below.

Training Distribution & Model (5 Seeds)Inference Leaves ↓\downarrowTest Accuracy (%) ↑\uparrowEqual-Cell Accuracy (%) ↑\uparrowNonfinal State Match s4s_4–s9s_9 (J>ℓJ>\ell, %)Post-Shuffle Acc. Across 6 Boundaries (%)
Original mixture — TC-7112.099.96 ±\pm 0.0199.95 ±\pm 0.0199.95 – 99.9849.96 – 50.08
Uniform J∈{0,…,7}J\in\{0,\ldots,7\} — TC-7112.099.94 ±\pm 0.0199.94 ±\pm 0.0299.94 – 99.96—
50:50 (Original + Fixed J=7J=7) — TC-7112.099.85 ±\pm 0.0299.84 ±\pm 0.0299.85 – 99.91—
Original mixture — No-state control16.067.50 ±\pm 0.0850.00 ±\pm 0.00——
Fixed J=7J=7 (no short prefixes) — TC-7109.250.02 ±\pm 0.1549.96 ±\pm 0.0549.96 – 50.0549.98 – 50.05
Fixed J=7J=7 — Validation-selected TC926.050.04 ±\pm 0.1149.99 ±\pm 0.10——
  1. Removing short prefixes (J=7J=7 fixed) vs. untuned prefix weights. Fixing J=7J=7 on every training example leaves fixed TC-7 (50.02±0.15%50.02\pm0.15\%), validation-selected cascades (50.04±0.11%50.04\pm0.11\%), single trees (50.07±0.07%50.07\pm0.07\%), and 511511-leaf histogram GBDT (50.25±0.13%50.25\pm0.13\%) near 50%50\%: the two low-order bits exceed 99.99%99.99\% accuracy, whereas pure 8-bit XOR has zero marginal single-coordinate Gini gain for greedy splits. The revised Abstract states this short-prefix condition explicitly. At the same time, tailored prefix probabilities are unnecessary: under uniform J∈{0,…,7}J\in\{0,\ldots,7\} or a 50:5050{:}50 mixture with fixed J=7J=7, the 112112-leaf cascade reaches 99.94±0.01%99.94\pm0.01\% and 99.85±0.02%99.85\pm0.02\%.
  2. Direct state agreement and causal shuffling. On original-distribution models, comparing raw predictions at all six nonfinal layers (ℓ=1,…,6\ell=1,\ldots,6) directly against the true residues s4,…,s9s_4,\ldots,s_9 (no label permutation) conditioned on J>ℓJ>\ell—where copying the final label yy gives only 50%50\%—yields 99.95%99.95\%–99.98%99.98\% five-seed mean agreement (and 99.96%99.96\%–99.98%99.98\% on an independent fixed-J=7J=7 test set, Table 11). Permuting the transmitted state across examples at any of the six boundaries drops final accuracy from 99.96%99.96\% to 49.96%49.96\%–50.08%50.08\% while preserving low-order bits (>99.99%>99.99\%), confirming that the cascade both recovers running residues and relies on them for prediction.

We have updated the Abstract and added these results to Appendix G.2 (Tables 10 and 11) of the revised paper. Thank you very much.

Q2 Theorem 6.1 and Lyu et al. (2024), Lemma 3

Q2: Theorem 6.1 appears to follow from the Lemma 3 argument of Lyu et al. (2024), which gives the stronger bound pm(1−2ϵ){p}^{m} ( 1 - 2 \epsilon ) for all ϵ<1/2\epsilon < 1 / 2. What is new in Theorem 6.1?

Thank you for identifying this connection. We agree with your assessment of the original first part. A direct extension of the leaf-counting argument of Lyu et al. [2, Lemma 3] gives L⩾pm(1−2ϵ)L\geqslant p^m(1-2\epsilon) for every p⩾2p\geqslant2 and ϵ<1/2\epsilon<1/2, whereas our connected-component proof unnecessarily lost a factor of mm: any nonsingleton leaf rectangle varies on at least one coordinate and is correct on at most half its inputs, so with SS singleton leaves on N=pmN=p^m points, correct predictions are at most S+(N−S)/2S+(N-S)/2, hence L⩾S⩾N(1−2ϵ)L\geqslant S\geqslant N(1-2\epsilon). We have replaced that proof and explicitly attributed the counting approach to Lyu et al. [2, Lemma 3].

Building on that argument, the revision strengthens the multiclass bound (p⩾3p\geqslant3). Writing N=pmN=p^m, we prove

L⩾N−⌊32⌊ϵN⌋⌋⩾N(1−32ϵ),p⩾3,0⩽ϵ<23.L \geqslant N - \left\lfloor \frac{3}{2}\left\lfloor \epsilon N \right\rfloor \right\rfloor \geqslant N\left(1 - \frac{3}{2}\epsilon\right), \qquad p \geqslant 3, \quad 0 \leqslant \epsilon < \frac{2}{3}.

This sharpens the coefficient from 22 to 3/23/2 and extends the nontrivial range from ϵ<1/2\epsilon<1/2 to ϵ<2/3\epsilon<2/3. Using the consecutive-integer structure of threshold-tree leaves, we show that every leaf rectangle R⊆{0,…,p−1}mR\subseteq\{0,\ldots,p-1\}^m and label rr satisfy

Nr(R)⩽∣R∣+23.N_r(R) \leqslant \frac{|R| + 2}{3}.

If a side has at least three values (⩽p\leqslant p), fixing the other coordinates gives distinct residues along that side and hence the stronger estimate ∣R∣/3|R|/3. Otherwise, after translation and removal of singleton coordinates, RR is a Boolean cube {0,1}k\{0,1\}^k. Let ck(r)c_k(r) count kk-bit assignments summing to r mod pr\bmod p, and let Mk=max⁡rck(r)M_k=\max_r c_k(r). For p⩾3p\geqslant3, the residues r,r−1,r−2r,r-1,r-2 are distinct modulo pp, so

ck+2(r)=ck(r)+2ck(r−1)+ck(r−2)⩽2k+Mk.c_{k+2}(r) = c_k(r) + 2c_k(r-1) + c_k(r-2) \leqslant 2^k + M_k.

Together with M0=M1=1M_0=M_1=1, this gives Mk⩽(2k+2)/3M_k\leqslant(2^k+2)/3, and summing over LL leaves yields the bound. The coefficient 3/23/2 is optimal within uniform linear bounds L⩾N−cEL\geqslant N-cE (EE errors): merging one consecutive 2×22\times2 block saves three leaves and makes two errors.

Across all 21 multiclass thresholds in Table 7 (and 1,8201{,}820 verified DP budgets), the strengthened integer bound matches the exact single-tree DP optimum, as illustrated below.

Instance (p,m)(p, m)Grid N=pmN=p^mTarget Accuracy (Max Errors EE)Lemma 3 Extension max⁡(1,N−2E)\max(1, N-2E)Revised Theorem 6.1 N−⌊32E⌋N-\lfloor\tfrac{3}{2}E\rfloorExact DP 1-Tree OptimumExact Cascade (m−1)p2(m-1)p^2
(3,4)(3, 4)8190% (E⩽8E\leqslant8)65696927
(3,5)(3, 5)24390% (E⩽24E\leqslant24)19520720736
(3,5)(3, 5)24395% (E⩽12E\leqslant12)21922522536
(4,4)(4, 4)25690% (E⩽25E\leqslant25)20621921948
(5,3)(5, 3)12590% (E⩽12E\leqslant12)10110710750
(3,5)(3, 5)24350% (E⩽121,ϵ≈0.50E\leqslant121, \epsilon\approx0.50)1 (vacuous)626236

We have updated Theorem 6.1, its attribution and proof in Section 4.2 and Appendix C, Figures 3 and 6–8, and Table 7; Theorem 6.2 additionally covers 2/3⩽ϵ<1−1/p2/3\leqslant\epsilon<1-1/p for p⩾4p\geqslant4 (while for p=3p=3 Theorem 6.1 covers the entire above-chance range). Thank you very much.

Reviewer_N4BEOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the problem of when does sequential representation make tree-based models fundamentally more efficient than simply growing a tree or adding more trees in parallel. Specifically, the paper investigate the learning problem of modular addition. Through theoretical proof and experimental results, the paper shows that for cascaded trees it take linear complexity of leaf nodes with respect to input dimensions to reach the required accuracy, whereas for single tree or random forest, the complexity is exponential with respect to the input dimension. This demonstrates the computational efficiency of the cascade representation in the modular addition task

Critical strengths
  1. The paper shows theoretically and experimentally the computational efficiency of cascaded tree representation in the modular sum task over single tree based on random forest based method.
Critical weaknesses
  1. The paper only proves the efficiency of cascaded tree representation on modular sum task, based on which it is difficult to claim the general efficiency of cascaded tree representation.
Questions for authors
  1. Since the paper only shows the efficiency of cascaded tree representation on a single task, it would be better if there is more discussion about the insight of the findings, such as how the cascaded tree's strength on modular sum could be extended to other tasks which have algorithmically similar structures.
2 comments

Thank you for your comments. Below please find our responses.

W1 & Q1 Scope beyond modular addition and extension to algorithmically related tasks

W1: The paper only proves the efficiency of cascaded tree representation on modular sum task, based on which it is difficult to claim the general efficiency of cascaded tree representation.
Q1: Since the paper only shows the efficiency of cascaded tree representation on a single task, it would be better if there is more discussion about the insight of the findings, such as how the cascaded tree's strength on modular sum could be extended to other tasks which have algorithmically similar structures.

Thank you for this constructive suggestion. The transferable insight of our study is to identify a compact state that summarizes the effect of the input history and can be reused in subsequent computation. In modular addition, two prefixes with the same running residue are interchangeable under every common continuation: although the number of prefixes grows as pip^i, only pp states are needed for the remaining computation, and a cascade explicitly carries that state forward.

This principle applies broadly to sequential processes of the form

si=T(si−1,xi),y=g(sm).s_i = T(s_{i-1}, x_i), \qquad y = g(s_m).

For finite-state sequence classification, sis_i can record the automaton state after the first ii symbols. For event-driven process monitoring, it can record the current mode of a system, with the next operation having a different effect depending on that mode. For symbolic transformations, it can record their accumulated composition (when a task has more internal states than output classes, the inter-layer channel must encode those states). Crucially, a second structural property is required for a depth separation: direct input partitioning must remain difficult. Boolean OR also has a two-state sequential update si=si−1∨xis_i=s_{i-1}\lor x_i, yet a single tree with m+1m+1 leaves computes it exactly by stopping at the first 11. Depth yields an exponential or super-polynomial separation when compact sequential state updates coincide with label mixing inside axis-aligned input rectangles (Theorems 6 and 7).

Appendix G.4 makes this extension rigorous beyond commutative modular addition. For an arbitrary finite group GG with q⩾2q\geqslant2 elements and m⩾2m\geqslant2, a threshold-tree cascade computes the ordered product x1⋯xmx_1\cdots x_m exactly with at most (m−1)q2(m-1)q^2 leaves. Conversely, in any nonsingleton leaf rectangle under uniform inputs on GmG^m, fixing all coordinates except one nonconstant coordinate xjx_j writes the output as gLxjgRg_L x_j g_R; by the left and right cancellation laws in GG, distinct coordinates xj≠xj′x_j\neq x'_j give distinct outputs gLxjgR≠gLxj′gRg_L x_j g_R\neq g_L x'_j g_R, so at most half of the leaf points share a label, yielding

L⩾qm(1−2ϵ),0⩽ϵ<1/2.L \geqslant q^m(1 - 2\epsilon), \qquad 0 \leqslant \epsilon < 1/2.

Taking the noncommutative group S3S_3 (q=6q=6 permutations) as an example, we constructed exact cascades for m=3,4,5m=3,4,5 and computed optimal single trees at m=3m=3 via exact endpoint-preserving DP. Results are summarized below.

Noncommutative S3S_3 Product (q=6q=6)Domain 6m6^mExact Cascade LeavesCascade AccuracySingle-Tree Acc. at Cascade BudgetSingle-Tree Leaves for ⩾95%\geqslant95\% / 100%100\%
m=3m=3 (x1x2x3∈S3x_1 x_2 x_3 \in S_3)21672100.00% (216/216)56.02% (121/216, exact DP)199 / 216 (exact DP)
m=4m=4 (x1⋯x4∈S3x_1 \cdots x_4 \in S_3)1,296108100.00% (1,296/1,296)⩽\leqslant 54.17% (analytic bound)⩾\geqslant 1,167 / 1,296 (bound)
m=5m=5 (x1⋯x5∈S3x_1 \cdots x_5 \in S_3)7,776144100.00% (7,776/7,776)⩽\leqslant 50.93% (analytic bound)⩾\geqslant 6,999 / 7,776 (bound)

We have expanded the scope discussion in Sections 1 and 6 and added the finite-group proof and S3S_3 verification to Appendix G.4 of the revised paper. Thank you very much.

We hope our response has addressed your concerns. If we have missed anything, please let us know.

AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewer N4BE,

Thank you very much for taking the time to carefully review our work and provide your constructive comments. Your feedback has been invaluable in helping us improve our work.

In response to your comments, we have included the following content:

  • We articulated the transferable mechanism behind the separation—compact sequential state reuse paired with axis-aligned label mixing (contrasting with Boolean OR)—and its applicability to finite-state sequences, event monitoring, and symbolic composition (Sections 1 and 6).
  • We generalized our exact (m-1)q^2-leaf cascade and exponential single-tree lower bound to ordered products in any finite group via group cancellation laws, verified via exact DP on the noncommutative group S_3 (Appendix G.4).
  • Besides, as suggested by Reviewers kAUk and 9wPt, we added five-seed comparisons against 511-leaf histogram GBDT (204,400 vs. 112 leaves) and regression random forests (Appendix G.3), tightened Theorem 6.1 for p >= 3 (Section 4.2, Appendix C), clarified Theorem 7 tightness (Section 4.3), and added five-seed state-shuffling diagnostics (Appendix G.2).

May we kindly ask if our response has addressed the issues you raised? If you still have any further questions or concerns, we would be more than happy to continue the discussion.

Thank you again for your time and effort.

Best regards,

Authors of Submission 41928

Reviewer_kAUkOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper analyzes the problem of modular addition with classification trees and forests. Specifically, 3 types of models are considered: single trees, forests where prediction is a majority voting, and tree cascades where the first tree outputs a class and the subsequent trees get the previous trees output as input along with input features. The paper provides theoretical approximation complexity analysis of those 3 class of models by showing how much the complexity of the model grows to fit this problem. Tree cascades show polynomial complexity while single trees need to be exponentially large and forests grow stretched-exponentially. The paper also performs experiments to validate the theoretical analysis.

Critical strengths

The paper considers a well-defined theoretical problem and shows rigorous complexity analysis of the single trees, forests and tree cascades. Though I need not go through the proofs, intuitively the results make sense.

Critical weaknesses

The paper is only focused on the modular addition problem solved through a classification task. By construction, tree cascades are well-favored for this task. Therefore, it is difficult to extend the results of this paper beyond this modular addition problem. For general supervised learning tasks, it is not clear whether tree cascades are guaranteed to have more learning capacity than let's say gradient boosting decision trees.

Questions for authors

In practice, if one treats this as a regression task, how would a regression forest be different than tree cascades?

3 comments

Thank you for your comments. Below please find our responses.

W1 Generality beyond modular addition and comparison with GBDT

W1: The paper is only focused on the modular addition problem solved through a classification task. By construction, tree cascades are well-favored for this task. Therefore, it is difficult to extend the results of this paper beyond this modular addition problem. For general supervised learning tasks, it is not clear whether tree cascades are guaranteed to have more learning capacity than let's say gradient boosting decision trees.

Thank you for raising this point. We do not claim universal superiority over GBDT on arbitrary supervised tasks; rather, the broader question addressed by the paper is which computational structure lets depth reduce representation size. In modular addition, depth makes exponentially many input prefixes collapse to a small set of states that preserve everything needed for subsequent prediction. Passing that state to the next layer allows the computation to be reused. Theorems 6 and 7 show that, in their respective error ranges and model classes, direct partitioning and parallel voting still require exponential and stretched-exponential leaf complexity when approximation is allowed. Together with the compact cascade construction, these bounds quantify the representational benefit of state reuse.

The same state-reuse question arises when classifying an event sequence by its resulting system state or composing symbolic transformations, where an intermediate representation summarizes the effect of earlier inputs. Appendix G.4 provides a concrete extension: ordered products in finite groups, including noncommutative groups, admit a compact (m−1)q2(m-1)q^2-leaf cascade and, under uniform inputs with fixed group size q⩾2q\geqslant2 and fixed error ϵ<1/2\epsilon<1/2, an exponential single-tree lower bound L⩾qm(1−2ϵ)L\geqslant q^m(1-2\epsilon).

GBDT raises an instructive architectural distinction. Standard GBDT trains trees sequentially, but at prediction time its trees evaluate the original features and contribute additive scores. A cascade instead passes a preceding prediction as an input to the next tree, distinguishing sequential training from prediction-time state reuse. Because Theorem 7 analyzes hard-plurality voting, we evaluated validation-selected CART trees, probability-averaging random forests, and histogram GBDT empirically on the eight-class, 1,0241{,}024-cell learning distribution of Section 5.2 (distinct from the uniform full grid in the representation theorems). Hyperparameters were selected via 3030 Optuna trials on two development seeds and frozen before evaluation on five confirmation seeds. Because the initial histogram GBDT search hit its 6363-leaf cap per tree, we ran a second validation search raising the cap to 511511 leaves per tree on five fresh seeds with paired cascade controls; the leaf count of the 511511-leaf histogram GBDT model includes all eight class-specific trees at every boosting round (50×8×511=204,40050\times8\times511=204{,}400). Results (mean ±\pm sample SD) are reported below.

Cohort (5 seeds)ModelMean Total Leaves ↓\downarrowLeaf RatioTest Acc. (%) ↑\uparrowEqual-Cell Acc. (%) ↑\uparrow
InitialTree cascade (TC-7, Ours)112.01.0$\times$99.96 ±\pm 0.0199.95 ±\pm 0.01
InitialSingle tree (CART)1,816.416.2$\times$99.92 ±\pm 0.0199.78 ±\pm 0.02
InitialClassification RF (prob. avg.)35,973.4321.2$\times$99.95 ±\pm 0.0199.84 ±\pm 0.01
InitialHistogram GBDT (⩽63\leqslant63/tree)25,200.0225.0$\times$92.52 ±\pm 0.1874.46 ±\pm 0.67
Larger leaf capPaired fixed TC-7 (Ours)112.01.0$\times$99.97 ±\pm 0.0199.95 ±\pm 0.02
Larger leaf capHistogram GBDT (⩽511\leqslant511/tree)204,400.01,825.0$\times$98.97 ±\pm 0.1798.35 ±\pm 0.29

Raising the per-tree leaf limit improves histogram GBDT accuracy from 92.52%92.52\% to 98.97%98.97\% (reflecting additive scores and 255255-bin splitting), while the 112112-leaf cascade reaches slightly higher accuracy with 321×321\times to 1,825×1{,}825\times fewer leaves. We have added these results and protocols to Appendices G.1, G.3 (Table 12), and G.4. Thank you very much.

Q1 Regression forests versus tree cascades

Q1: In practice, if one treats this as a regression task, how would a regression forest be different than tree cascades?

Thank you for this question. A regression random forest averages real-valued predictions from parallel trees over the original features, whereas our cascade trains Gini classification trees that propagate a discrete intermediate prediction in {0,…,7}\{0,\ldots,7\} to the next tree.

We tested the residue target y∈{0,…,7}y\in\{0,\ldots,7\} directly by training regression random forests with MSE loss, selecting hyperparameters by validation MSE (3030 Optuna trials on two development seeds), and decoding classes on five confirmation seeds via c^=clip⁡(⌊y^+1/2⌋,0,7)\hat{c}=\operatorname{clip}(\lfloor\hat{y}+1/2\rfloor,0,7). Under this stated decoder, any classification error requires squared error at least 1/41/4, giving Pr⁡(c^≠c)⩽4 MSE\Pr(\hat{c}\neq c)\leqslant4\,\mathrm{MSE}. Results across the original distribution (unconstrained and ⩽2,048\leqslant2{,}048-leaf compact budget) and fixed-J=7J=7 retraining are reported below (— denotes that TC-7 is a discrete classifier rather than a continuous regressor).

Training DistributionModel (Validation Criterion)Mean Total Leaves ↓\downarrowUnscaled Test MSE ↓\downarrowTest Accuracy (%) ↑\uparrowEqual-Cell Accuracy (%) ↑\uparrow
Original mixtureTree cascade (TC-7, classif.)112.0 ±\pm 0.0—99.96 ±\pm 0.0199.95 ±\pm 0.01
Original mixtureRegression RF (best val. MSE)36,318.4 ±\pm 457.40.0079 ±\pm 0.000899.66 ±\pm 0.0299.00 ±\pm 0.05
Original mixtureRegression RF (⩽2,048\leqslant2{,}048 leaves)1,152.0 ±\pm 0.01.7694 ±\pm 0.006557.90 ±\pm 0.226.19 ±\pm 0.09
Fixed J=7J=7 (no short prefixes)Tree cascade (TC-7, classif.)109.2 ±\pm 3.8—50.02 ±\pm 0.1549.96 ±\pm 0.05
Fixed J=7J=7 (no short prefixes)Regression RF (best val. MSE)152.0 ±\pm 0.04.0002 ±\pm 0.0001<< 0.01<< 0.01
  1. Accuracy vs. leaf complexity on the modular residue. On the original distribution, the MSE-selected regression forest fits the residue accurately (99.66%99.66\% decoded accuracy, MSE 0.00790.0079), using 36,318.436{,}318.4 leaves (324×324\times the 112112-leaf cascade); under a compact 1,1521{,}152-leaf budget, its equal-cell accuracy drops to 6.19%6.19\%. Predicting the unwrapped sum ∑i=1mxi\sum_{i=1}^m x_i and then applying an exact  mod  p\bmod\,p operator would change both the regression target and the output operator: on the discrete grid, an additive tree model can represent the unwrapped sum with mpmp leaves because the external  mod  p\bmod\,p operator supplies the wrap-around. Learning the residue directly with fixed rounding keeps that burden inside the ensemble.
  2. Interaction of MSE and rounding on fixed J=7J=7. With fixed J=7J=7, the MSE-selected forest has MSE 4.00024.0002 and decoded accuracy below 0.01%0.01\%: recovering only the low-order bits r0∈{0,1,2,3}r_0\in\{0,1,2,3\} makes the midpoint r0+2r_0+2 between {r0,r0+4}\{r_0,r_0+4\} optimal under MSE (22=42^2=4), whereas rounding the midpoint predicts neither class. Because the complete input determines the target, for the fitted forest, this experiment measures the recovery of that deterministic target under MSE.

We have added these regression comparisons to Appendix G.3 and Table 12 of the revised paper. Thank you very much.

We hope our response has addressed your concerns. If we have missed anything, please let us know.

AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewer kAUk,

Thank you very much for taking the time to carefully review our work and provide your constructive comments. Your feedback has been invaluable in helping us improve our work.

In response to your comments, we have included the following content:

  • We clarified prediction-time state reuse vs. additive GBDT scoring and added five-seed comparisons with 511-leaf histogram GBDT (Appendices G.1, G.3, Table 12): our 112-leaf cascade (TC-7) achieves 99.97% accuracy vs. 98.97% using 204,400 leaves (1,825x more) for GBDT.
  • We extended the cascade construction and exponential single-tree lower bound beyond modular addition to ordered products in arbitrary finite groups, including noncommutative S_3 with exact DP verification (Appendix G.4).
  • We evaluated MSE regression random forests on the residue target (Appendix G.3, Table 12), showing they require 324x more leaves (36,318.4) for 99.66% accuracy and drop to 6.19% equal-cell accuracy under a compact 1,152-leaf budget.
  • Besides, as suggested by Reviewers N4BE and 9wPt, we tightened Theorem 6.1 (p >= 3) with attribution to Lyu et al. (2024) (Section 4.2, Appendix C), discussed Theorem 7 tightness and odd-p extensions (Section 4.3), and added five-seed short-prefix and state-shuffling diagnostics (Appendix G.2).

May we kindly ask if our response has addressed the issues you raised? If you still have any further questions or concerns, we would be more than happy to continue the discussion.

Thank you again for your time and effort.

Best regards,

Authors of Submission 41928

Comments on the paper

1 comment

Summary of Revisions and Main Contribution

We thank all three reviewers for your careful reading and suggestions. Below we summarize our main revisions, followed by point-by-point responses. The revision develops the central insight of the paper: reusing a compact intermediate state can make depth more efficient than adding trees in parallel. We have clarified this mechanism in the Introduction and Discussion, strengthened the theoretical analysis, and expanded the experimental evidence in three directions. Additions and changes in the revised manuscript are marked in red.

  1. Structural scope beyond modular addition. Appendix G.4 extends the cascade construction and single-tree separation to ordered products in any nontrivial finite group, including noncommutative groups. Using S3S_3 as an example makes the mechanism concrete: a compact partial product can be reused across layers, whereas the left and right cancellation laws in a group (gLxjgR≠gLxj′gRg_L x_j g_R \neq g_L x'_j g_R for xj≠xj′x_j \neq x'_j) limit the accuracy of any constant-label nonsingleton leaf. This extension identifies compact state updates and label variation under the cancellation law as the structural ingredients behind the single-tree separation.

  2. Stronger analysis and precise attribution. We attribute the argument underlying the original Theorem 6.1 to Lyu et al. (2024, Lemma 3), replace its proof, and strengthen the multiclass bound to L⩾pm(1−32ϵ)L\geqslant p^m(1-\tfrac{3}{2}\epsilon) for p⩾3p\geqslant3. Its integer form and matching constructions certify all 21 reported multiclass thresholds in Table 7. In Section 4.3, we also clarify the asymptotic tightness of Theorem 7 (Ω(2Θ(m))\Omega(2^{\Theta(\sqrt{m})}) versus the open exponential regime Ω(2Θ(m))\Omega(2^{\Theta(m)})) and the role of the even-modulus condition.

  3. Stronger comparisons and direct tests of state learning. Appendix G adds standard classification and regression random forests with validation-selected hyperparameters, histogram GBDT evaluated with per-tree leaf limits up to 511511, and five-seed distribution controls and state diagnostics. On the original distribution, the paired cascade uses 112112 leaves at 99.97%99.97\% accuracy, compared with 204,400204{,}400 leaves at 98.97%98.97\% for histogram GBDT (⩽511\leqslant511 leaves per tree). Direct state comparisons and boundary state shuffling confirm the recovery and use of running residues, while prefix-distribution controls identify the short-prefix training signal stated explicitly in the revised abstract.

Main Contribution: The paper explains a mechanism by which sequential reuse of compact states yields a depth separation that survives approximation. For modular addition, pip^i possible prefixes can be summarized by only pp running residues: prefixes with the same residue give the same final answer under every common continuation, and a cascade passes this sufficient state to its next layer. Theorems 5, 6, and 7 answer whether direct input partitioning or parallel voting can achieve comparable efficiency without state propagation. On the uniform grid with m⩾2m\geqslant2, the cascade is exact with (m−1)p2(m-1)p^2 leaves. For fixed pp, a single tree needs exponentially many leaves for any fixed accuracy advantage over chance 1/p1/p. For even pp and fixed error ϵ<1/2\epsilon<1/2, hard-plurality forests need stretched-exponentially many leaves, showing that the separation persists at positive error. Together with our learning diagnostics, these results connect sequential representation efficiency to the recovery and use of running-residue states by trained cascades.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.