- 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, over .
There are three main results:
- A tree cascade represents the target exactly with leaves (Theorem 5).
- A single tree needs leaves to do even slightly better than chance (Theorem 6).
- For even , a plurality forest with error needs 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
-
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 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.
-
Theorem 7 extends the cascade–forest separation of Lyu et al. (2024) from exact representation to any error , 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
- The forest result is limited to even and has a relatively weak bound. Theorem 7 only applies to even , 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 is vacuous at realistic (about leaves at ). The tightness of this bound should be discussed.
Questions for authors
- 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.
- Theorem 6.1 appears to follow from the Lemma 3 argument of Lyu et al. (2024), which gives the stronger bound for all . What is new in Theorem 6.1?
9 comments
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 ( train / test examples per seed) that (1) remove short prefixes completely ( fixed), (2) test untuned prefix distributions, (3) directly compare nonfinal predictions with running residues , and (4) shuffle transmitted states across examples. Results are reported in the table below.
| Training Distribution & Model (5 Seeds) | Inference Leaves | Test Accuracy (%) | Equal-Cell Accuracy (%) | Nonfinal State Match – (, %) | Post-Shuffle Acc. Across 6 Boundaries (%) |
|---|---|---|---|---|---|
| Original mixture — TC-7 | 112.0 | 99.96 0.01 | 99.95 0.01 | 99.95 – 99.98 | 49.96 – 50.08 |
| Uniform — TC-7 | 112.0 | 99.94 0.01 | 99.94 0.02 | 99.94 – 99.96 | — |
| 50:50 (Original + Fixed ) — TC-7 | 112.0 | 99.85 0.02 | 99.84 0.02 | 99.85 – 99.91 | — |
| Original mixture — No-state control | 16.0 | 67.50 0.08 | 50.00 0.00 | — | — |
| Fixed (no short prefixes) — TC-7 | 109.2 | 50.02 0.15 | 49.96 0.05 | 49.96 – 50.05 | 49.98 – 50.05 |
| Fixed — Validation-selected TC | 926.0 | 50.04 0.11 | 49.99 0.10 | — | — |
- Removing short prefixes ( fixed) vs. untuned prefix weights. Fixing on every training example leaves fixed TC-7 (), validation-selected cascades (), single trees (), and -leaf histogram GBDT () near : the two low-order bits exceed 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 or a mixture with fixed , the -leaf cascade reaches and .
- Direct state agreement and causal shuffling. On original-distribution models, comparing raw predictions at all six nonfinal layers () directly against the true residues (no label permutation) conditioned on —where copying the final label gives only —yields – five-seed mean agreement (and – on an independent fixed- test set, Table 11). Permuting the transmitted state across examples at any of the six boundaries drops final accuracy from to – while preserving low-order bits (), 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 for all . 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 for every and , whereas our connected-component proof unnecessarily lost a factor of : any nonsingleton leaf rectangle varies on at least one coordinate and is correct on at most half its inputs, so with singleton leaves on points, correct predictions are at most , hence . 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 (). Writing , we prove
This sharpens the coefficient from to and extends the nontrivial range from to . Using the consecutive-integer structure of threshold-tree leaves, we show that every leaf rectangle and label satisfy
If a side has at least three values (), fixing the other coordinates gives distinct residues along that side and hence the stronger estimate . Otherwise, after translation and removal of singleton coordinates, is a Boolean cube . Let count -bit assignments summing to , and let . For , the residues are distinct modulo , so
Together with , this gives , and summing over leaves yields the bound. The coefficient is optimal within uniform linear bounds ( errors): merging one consecutive block saves three leaves and makes two errors.
Across all 21 multiclass thresholds in Table 7 (and verified DP budgets), the strengthened integer bound matches the exact single-tree DP optimum, as illustrated below.
| Instance | Grid | Target Accuracy (Max Errors ) | Lemma 3 Extension | Revised Theorem 6.1 | Exact DP 1-Tree Optimum | Exact Cascade |
|---|---|---|---|---|---|---|
| 81 | 90% () | 65 | 69 | 69 | 27 | |
| 243 | 90% () | 195 | 207 | 207 | 36 | |
| 243 | 95% () | 219 | 225 | 225 | 36 | |
| 256 | 90% () | 206 | 219 | 219 | 48 | |
| 125 | 90% () | 101 | 107 | 107 | 50 | |
| 243 | 50% () | 1 (vacuous) | 62 | 62 | 36 |
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 for (while for Theorem 6.1 covers the entire above-chance range). Thank you very much.
Thank you for your comments. Below please find our responses.
W1 Even moduli and tightness of the forest bound
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+ and fixed 0⩽ϵ<1/2, hard-plurality forests satisfy
L⩾81−2ϵ2(1−2ϵ)m/12,
ruling out polynomial leaf complexity in m while the cascade is exact with (m−1)p2 leaves.
1. Asymptotic tightness of Ω(2Θ(m)). In complexity terms, Ω(2Θ(m)) already establishes a super-polynomial separation from the O(m) cascade, and we agree its asymptotic tightness should be discussed directly. At ϵ=0, majority-vote forests require exponential size 2Ω(m) on parity [2]. When ϵ∈(0,1/2), zero-error leaf counting no longer applies; our proof truncates trees to depth d=Θ(logL) and represents pairwise plurality voting as the sign of a degree-d polynomial threshold function (PTF), invoking the bounded-error PTF degree bound d=Ω(m) of Aspnes et al. [1]. Because Θ(m) is tight for general PTF degree approximations of parity [1], any reduction treating depth-d forests as general degree-d PTFs encounters the 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)) to Ω(2Θ(m)) remains an open problem, now stated explicitly in Section 4.3.
2. Multi-class plurality voting and even p. Beyond prior results restricted to binary output (p=2), exact representation (ϵ=0), or per-tree size caps [2], Theorem 7 covers all even multi-class moduli p∈{4,6,8,…} with unrestricted tree sizes and full p-way voting in {0,…,p−1}. When ϵ>0 and p⩾3, trees can divert votes to third classes c∈/{r0,r1}, so multi-way argmax is not a single polynomial sign unless third-party votes are controlled. Embedding the order-2 subgroup {0,p/2}⩽Zp via ϕx(b)i=(xi+(p/2)bi)modp partitions Zpm into uniform cosets where the true label takes only two values {r(x),r(x)+p/2}: votes for the other p−2 classes never help the true class beat its antipodal competitor, isolating pairwise vote difference as a degree-d sign polynomial. For odd p, Zp lacks an order-2 element and any nontrivial subproblem spans at least three residues, requiring multi-way PTF or Zp-character techniques noted as an open direction in Section 4.3.
Empirically, even at p=8,m=10, hard-plurality voting forests already require orders of magnitude more leaves than cascades across five seeds, as reported below.
We have added the tightness and odd-p discussions to Section 4.3 (pp. 6–7) of the revised paper. Thank you very much.