Pith. sign in

REVIEW 3 major objections 5 minor 30 references

Decision Trees That Remember: Gradient-Based Learning of Recurrent Decision Trees with Memory

T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims ReMeDe Trees, hard axis-aligned decision trees with a gated internal memory, can be trained end-to-end by backpropagation through time and reach perfect test accuracy on five synthetic memory tasks, matching LSTM baselines.

desk verdict ReMeDe Trees are a genuinely new recurrent DT architecture with a clear write-up; the proof of concept is real but thin, so it deserves conditional acceptance, not a desk reject. read the letter →

arxiv 2502.04052 v1 pith:UMOQTX5I submitted 2025-02-06 cs.LG

Sascha Marton , Moritz Schneider This is my paper · ORCID
classification cs.LG
keywords recurrentdecisiontreesinternalmemorybackpropagationthroughtimegradient-basedstraight-throughestimatorhardaxis-alignedsplitslong-termdependenciessequencemodeling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces ReMeDe Trees, a decision tree with a continuous internal memory that internal nodes can read and leaf nodes can update. The authors claim that, for the first time, such a hard, axis-aligned recurrent decision tree can be trained end-to-end using backpropagation through time, with the discrete split and gate decisions made differentiable by a straight-through estimator. On five synthetic tasks that require storing an initial value and recalling it when a later trigger appears, the model reaches perfect test accuracy, matching LSTM baselines and beating window-based and naive baselines. The significance is that a tree-based model, not a neural network, can handle long-term sequential dependencies while keeping the interpretable, axis-aligned structure of classical decision trees.

What carries the argument

The mechanism is the recurrent tree function itself. ReMeDe extends GradTree's arithmetic formulation $y = \sum_l \lambda_l L(x|l,\tau,\iota)$ to the joint input–memory space: the same tree computes both the output and the next memory state, with internal nodes allowed to split on any coordinate of $x_t$ or $m_{t-1}$. The memory update is an additive, gated write: a leaf's gate parameter $c_j$ is passed through a sigmoid and rounded to 0 or 1, then multiplied by $\tanh(W_j^x x_t)$; the straight-through estimator lets gradients flow through the rounding both in the splits and in this gate. This gives the tree a hard read/write memory whose contents condition future routing, which is what lets a fixed-depth tree solve tasks with variable delays.

What would settle it

Train a ReMeDe tree on the sign-retrieval task and inspect its memory state after the first timestep; if the stored value does not carry the sign of the initial input while the tree still predicts the correct sign at the trigger, then the model is solving the task without using its memory as claimed.

Watch

Extended reading notes

Core claim

The central claim is that Recurrent Memory Decision (ReMeDe) Trees, a single hard, axis-aligned decision tree operating on the augmented input $\tilde{x}_t = (x_t, m_{t-1})$, where $m_t$ is a continuous memory state, can be learned by gradient descent with backpropagation through time. Each leaf prescribes both an output and a gated memory update $m_t = m_{t-1} + \lfloor \psi_g(c_j)\rceil \psi(W_j^x x_t)$, with the rounding handled by a straight-through estimator in the backward pass. The paper reports perfect average test accuracy on all five proof-of-concept datasets, equal to the LSTM baseline, and shows a pruned tree with only 22 to 44 nodes that stores the sign of the first input and retrieves it at the trigger. The authors state this is the first approach to learn a memory-augmented recurrent decision tree using backpropagation through time.

Load-bearing premise

The whole method rides on the assumption that the approximated gradients used to bypass the tree's rounding steps are informative enough to train the memory, and that assumption is only tested on five small synthetic tasks.

Editorial extensions

If this is right

  • ReMeDe Trees can solve tasks that require storing information across a delay longer than any fixed input window, because the memory state compresses the past rather than truncating it.
  • The learned recurrent trees stay compact: after pruning, the proof-of-concept trees have between 20 and 44 nodes, which the authors argue supports interpretability and verifiability.
  • The training recipe transfers the standard neural toolkit, BPTT, gating, and straight-through gradients, to hard, axis-aligned trees, so the approach is not limited to the zero-order output used here.
  • Because the base tree is the GradTree model, the method can be combined with tree ensembles, which the authors name as a direct next step.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the same read/write memory idea could be lifted into any differentiable tree ensemble, so the key contribution is not the specific tree but the proof that hard threshold logic plus a memory state is trainable.
  • The straight-through gradient is the transfer risk; a natural stress test would be to scale sequence length and input dimension and observe whether ReMeDe retains the LSTM-matching accuracy reported here.
  • Because the splits are axis-aligned, a learned ReMeDe tree can in principle be audited as a state machine: tracing which memory thresholds cause writes and reads gives a human-readable account of the model's timing logic, unlike an RNN's distributed state.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces ReMeDe Trees, a recurrent decision-tree architecture that augments a hard, axis-aligned GradTree with a continuous internal memory vector. At each time step, the tree reads the input and the memory, produces an output from the selected leaf, and updates the memory using leaf-prescribed gating and a tanh-transformed linear input mapping. Training is end-to-end via backpropagation through time, with straight-through estimators used through the discrete split decisions and hard memory gates. The authors report perfect test accuracy on five synthetic delayed-sign-retrieval and sign-memory tasks, matching an LSTM baseline, and they visualize a learned minimal tree that stores and recalls a sign across a delay.

Significance. If taken at face value, the paper provides a useful proof of concept: it shows that a fully discrete-routing tree with a continuous memory can be trained by gradient descent and BPTT, without soft probabilistic routing or post-hoc binarization. The hand-traced example and the internal consistency across five trials (zero variance, matching LSTM) support the claim that the learned trees do implement the intended memory operations. The contribution is nevertheless narrow: the experiments are synthetic, short-lag, and not compared against a fixed-window baseline, so the paper does not yet establish practical advantages for long-term sequence modeling. The authors are appropriately careful in calling this a proof of concept, but the abstract and conclusion use language that goes beyond the evidence.

major comments (3)
  1. [Sec. 4.2, Table 1; Abstract; Sec. 6] The paper's central claim is that ReMeDe Trees 'learn long-term dependencies' and 'overcome the limitations of fixed-size memory windows', but the experiments use a fixed delay of 5 and a variable delay range [3,7] for PoC1-4, and PoC5 does not state its block or delay lengths. A maximum lag of 7 is not 'long-term' in any meaningful sense. Because the straight-through estimator's bias is injected at every time step and accumulates through the unfolded memory, this short-lag evidence does not support the long-horizon claim. Please either add experiments with substantially longer lags (e.g., 50-100 steps) or restrict the abstract and conclusion to the tested short-lag regime.
  2. [Sec. 4.2] The hyperparameter selection protocol is under-specified. Optuna is run for 60 trials to select learning rates, but the text never states whether a validation split is used; if the test set was used for selection, the reported 1.000 accuracies are not unbiased estimates of generalization. Please specify the train/validation/test split and report test performance for the model selected on validation.
  3. [Sec. 4.2] The motivating contrast with NARX/memory-window models is never tested. The authors state that 'it is clear' that a fixed-lookback model cannot solve the tasks, but this is an assertion; a concrete comparison with, e.g., GradTree using lag features or a standard NARX baseline would substantiate the claim that the recurrent memory is the source of the performance. This is particularly important because all five tasks are constructed so that a small memory suffices, making the successful learning less surprising.
minor comments (5)
  1. [Sec. 4.1, PoC5] The Sign Memory task does not specify the values of block length l and zero-block delay d used in the experiments; these values are needed to interpret Table 1 and to judge the actual lag.
  2. [Eq. (11)] The notation ⌊ψ_g(c_j)⌋ ψ(W^x_j x_t) is ambiguous about whether the rounding is applied componentwise and whether c_j is a scalar or a vector; please define all dimensions explicitly.
  3. [Table 2] The pruning procedure is described only as 'removing all redundant paths'; please specify the pruning rule and report standard deviations for the tree sizes.
  4. [Figure 2] The equations in the figure repeat computed values and mix variables in a way that is hard to follow; a cleaner legend or a separate table of the traced values would improve readability.
  5. [Sec. 4.2] The sentence 'We evaluate two recurrent architecture on our datasets' contains a grammar error; it should be 'two recurrent architectures'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: ReMeDe Trees extend a published base model and are evaluated on independent synthetic tasks.

full rationale

The paper's central claim is that a hard, axis-aligned decision tree with an internal memory state can be trained end-to-end with backpropagation through time and can solve the five synthetic sign-memory tasks. I traced the derivation chain and found no step where a prediction is equivalent to an input by construction. The memory update in Eq. (11) is a genuinely new formulation: mt = mt-1 + floor(psi_g(cj)) psi(W_j^x xt), with cj and W_j^x both produced by tree inference. This is an architectural proposal, not a renamed fit. The straight-through estimator used through the rounding and hardmax operations is inherited from GradTree (Marton et al., 2024a), but that citation is used as a training substrate, not as evidence that ReMeDe succeeds; the paper's own experiments provide the support for the memory-extension claim. The synthetic datasets are designed to require memory beyond a fixed window, but that is task construction rather than a logical loop: the model still has to learn the correct routing and memory-write behavior from data. There is a self-citation to GradTree as the base method, and the paper also cites GRANDE in the future-work section, but neither citation asserts the paper's central result. The reported accuracies are empirical outcomes, not identities derived from the data-generation formulas. The absence of a separate validation split in the Optuna tuning is a methodological concern, not a circularity concern. Overall, no load-bearing step reduces to its own inputs, and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The central claim rests on a training pipeline inherited from the self-cited GradTree method, on an unproved straight-through gradient assumption, and on self-designed synthetic tasks. The model's only genuinely new architectural entity is the internal memory vector. Most numerical choices (depth, memory size, learning rates) are set by hand or tuned without a reported validation split, which limits the external grounding of the proof-of-concept.

free parameters (4)
  • Tree depth = 6
    Fixed by the authors for all tasks to keep the model compact; no derivation or selection criterion is given.
  • Memory dimension = 5
    Fixed at 5 hidden state dimensions; chosen by hand and not ablated.
  • Learning rate (per task) = not reported
    Optimized with Optuna (60 trials) for each task; the chosen values are not listed, and no validation split is described.
  • LSTM hidden units and dropout = 32, 16, dropout unspecified
    Baseline architecture chosen by the authors; only the learning rate was tuned.
assumptions (4)
  • domain assumption The straight-through estimator provides useful gradients through the rounding in Eq. (4) and Eq. (11).
    The learning procedure depends on gradient flow through discrete splits and hard gates; this is an empirical assumption without formal guarantees.
  • standard math Backpropagation through time over the unrolled tree computes gradients of the soft surrogate loss correctly.
    Section 3 says training uses BPTT; this assumes the computation graph can be unrolled and the chain rule applies.
  • domain assumption The five synthetic data procedures in Section 4.1 are adequate evidence that the model can handle long-term dependencies.
    The proof-of-concept claim rests entirely on these self-designed tasks; no real-world benchmark is used.
  • ad hoc to paper A fully grown tree of depth 6 with a 5-dimensional memory can represent all five target functions.
    Depth and memory size are fixed without capacity analysis or ablation.
invented entities (1)
  • Internal memory vector m_t in R^5
    purpose: Stores a compressed summary of past inputs and conditions both the split decisions and the output at each time step.
    This is the new architectural latent state introduced by ReMeDe. There is no falsifiable external prediction attached to it beyond the trained model's behavior, so independent evidence is absent.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Decision Trees That Remember: Gradient-Based Learning of Recurrent Decision Trees with Memory." pith.science (2026). https://pith.science/paper/UMOQTX5I

@misc{pith2026250204052,
  author       = {Pith},
  title        = {Pith review of: Decision Trees That Remember: Gradient-Based Learning of Recurrent Decision Trees with Memory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UMOQTX5I}},
  note         = {Machine review of arXiv:2502.04052}
}
read the original abstract

Neural architectures such as Recurrent Neural Networks (RNNs), Transformers, and State-Space Models have shown great success in handling sequential data by learning temporal dependencies. Decision Trees (DTs), on the other hand, remain a widely used class of models for structured tabular data but are typically not designed to capture sequential patterns directly. Instead, DT-based approaches for time-series data often rely on feature engineering, such as manually incorporating lag features, which can be suboptimal for capturing complex temporal dependencies. To address this limitation, we introduce ReMeDe Trees, a novel recurrent DT architecture that integrates an internal memory mechanism, similar to RNNs, to learn long-term dependencies in sequential data. Our model learns hard, axis-aligned decision rules for both output generation and state updates, optimizing them efficiently via gradient descent. We provide a proof-of-concept study on synthetic benchmarks to demonstrate the effectiveness of our approach.

Figures

Figures reproduced from arXiv: 2502.04052 by the authors.

Figure 1
Figure 1. Minimal Recurrent Decision Tree Example This figure shows an exemplary ReMeDe tree applied to a sign recognition task. The task is to memorize the sign of x ∈ (−0.5, 0.5) at the first position and predict it (-1 or 1) when a trigger value (1) appears, while intermediate positions hold zeros plus small noise. The figure depicts the minimal ReMeDe tree solving this task. At the root node, the tree checks whether the t… view at source ↗
Figure 2
Figure 2. ReMeDe Tree Update Visualization This figure shows an ReMeDe tree trained to a sign recognition task. The task is to memorize the sign of x ∈ (−0.5, 0.5) at the first position and predict it (-1 or 1) when a trigger value (1) appears, while intermediate positions hold zeros plus small noise [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 20 canonical work pages

  1. [1]

    Optuna: A next-generation hyperparameter optimization framework

    Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp.\ 2623--2631, 2019

    2019

  2. [2]

    Learning Decision Trees Recurrently Through Communication

    Stephan Alaniz, Diego Marcos, Bernt Schiele, and Zeynep Akata. Learning decision trees recurrently through communication, 2021. URL https://arxiv.org/abs/1902.01780

    work page Pith review arXiv 2021

  3. [3]

    Linear model decision trees as surrogates in optimization of engineering applications

    Bashar L Ammari, Emma S Johnson, Georgia Stinchfield, Taehun Kim, Michael Bynum, William E Hart, Joshua Pulsipher, and Carl D Laird. Linear model decision trees as surrogates in optimization of engineering applications. Computers & Chemical Engineering, 178: 0 108347, 2023

    work page 2023

  4. [4]

    o ppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, G \

    Maximilian Beck, Korbinian P \"o ppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, G \"u nter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xlstm: Extended long short-term memory. arXiv preprint arXiv:2405.04517, 2024

    arXiv 2024

  5. [5]

    Classification and regression trees

    Leo Breiman. Classification and regression trees. Routledge, 2017

    work page 2017

  6. [6]

    Prediction of financial time series with recurrent lolimot (locally linear model tree)

    Hossein Chegini and Caro Lucas. Prediction of financial time series with recurrent lolimot (locally linear model tree). In 2010 The 2nd International Conference on Computer and Automation Engineering (ICCAE), volume 2, pp.\ 592--596, 2010

    work page 2010

  7. [7]

    Learning online smooth predictors for realtime camera planning using recurrent decision trees

    Jianhui Chen, Hoang M Le, Peter Carr, Yisong Yue, and James J Little. Learning online smooth predictors for realtime camera planning using recurrent decision trees. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.\ 4688--4696, 2016

    work page 2016

  8. [8]

    Xgboost: A scalable tree boosting system

    Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp.\ 785--794, 2016

    work page 2016

Show all 30 references
  1. [9]

    The role of decision tree representation in regression problems--an evolutionary perspective

    Marcin Czajkowski and Marek Kretowski. The role of decision tree representation in regression problems--an evolutionary perspective. Applied soft computing, 48: 0 458--475, 2016

    2016

  2. [10]

    Finding structure in time

    Jeffrey L Elman. Finding structure in time. Cognitive science, 14 0 (2): 0 179--211, 1990

    1990

  3. [11]

    The vanishing gradient problem during learning recurrent neural nets and problem solutions

    Sepp Hochreiter. The vanishing gradient problem during learning recurrent neural nets and problem solutions. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 6 0 (02): 0 107--116, 1998

    1998

  4. [12]

    Soft decision trees

    Ozan Irsoy, Olcay Taner Y ld z, and Ethem Alpayd n. Soft decision trees. In Proceedings of the 21st international conference on pattern recognition (ICPR2012), pp.\ 1819--1822. IEEE, 2012

    2012

  5. [13]

    Sdtr: Soft decision tree regressor for tabular data

    Haoran Luo, Fan Cheng, Heng Yu, and Yuqi Yi. Sdtr: Soft decision tree regressor for tabular data. IEEE Access, 9: 0 55999--56011, 2021

    2021

  6. [14]

    Gradtree: Learning axis-aligned decision trees with gradient descent

    Sascha Marton, Stefan L \"u dtke, Christian Bartelt, and Heiner Stuckenschmidt. Gradtree: Learning axis-aligned decision trees with gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp.\ 14323--14331, 2024 a

    2024

  7. [15]

    Grande: Gradient-based decision tree ensembles for tabular data

    Sascha Marton, Stefan L \"u dtke, Christian Bartelt, and Heiner Stuckenschmidt. Grande: Gradient-based decision tree ensembles for tabular data. In The Twelfth International Conference on Learning Representations, 2024 b

    2024

  8. [16]

    Tree-structured recurrent switching linear dynamical systems for multi-scale modeling

    Josue Nassar, Scott W Linderman, Monica Bugallo, and Il Memming Park. Tree-structured recurrent switching linear dynamical systems for multi-scale modeling. arXiv preprint arXiv:1811.12386, 2018

    2018 arXiv

  9. [17]

    Nonlinear dynamic system identification

    Oliver Nelles. Nonlinear dynamic system identification. Springer, 2020

    2020

  10. [18]

    Basis function networks for interpolation of local linear models

    Oliver Nelles and Rolf Isermann. Basis function networks for interpolation of local linear models. In Proceedings of 35th IEEE conference on decision and control, volume 1, pp.\ 470--475. IEEE, 1996

    1996

  11. [19]

    Resurrecting recurrent neural networks for long sequences, 2023

    Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences, 2023. URL https://arxiv.org/abs/2303.06349

    2023 arXiv

  12. [20]

    Catboost: unbiased boosting with categorical features

    Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. Catboost: unbiased boosting with categorical features. Advances in neural information processing systems, 31, 2018

    2018

  13. [21]

    J Ross Quinlan. C4. 5: programs for machine learning. Elsevier, 2014

    2014

  14. [22]

    Tree-rnn: Tree structural recurrent neural network for network traffic classification

    Xinming Ren, Huaxi Gu, and Wenting Wei. Tree-rnn: Tree structural recurrent neural network for network traffic classification. Expert Systems with Applications, 167: 0 114363, 2021

    2021

  15. [23]

    Long short-term memory

    J \"u rgen Schmidhuber, Sepp Hochreiter, et al. Long short-term memory. Neural Comput, 9 0 (8): 0 1735--1780, 1997

    1997

  16. [24]

    Backpropagation through time: what it does and how to do it

    Paul J Werbos. Backpropagation through time: what it does and how to do it. Proceedings of the IEEE, 78 0 (10): 0 1550--1560, 1990

    1990

  17. [25]

    Experimental analysis of the real-time recurrent learning algorithm

    Ronald J Williams and David Zipser. Experimental analysis of the real-time recurrent learning algorithm. Connection science, 1 0 (1): 0 87--111, 1989

    1989

  18. [26]

    Understanding straight-through estimator in training activation quantized neural nets, 2019

    Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Understanding straight-through estimator in training activation quantized neural nets, 2019. URL https://arxiv.org/abs/1903.05662

    2019 arXiv

  19. [27]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

  20. [28]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  21. [29]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  22. [30]

    < 9˄ v !'_Xqz*0j#qͨܠ y z7-ygɊ k 6?<Ws˿? ?W;Ρ r oP ]|y4VR &e41 gu Qx&]k( 화FLO] 3G>qgb o ^? r ܵ=wq ._xftA[!W4v 5_o xO :L r|0 ,: x꾸U_s; mj;1=xŞ7 TX ;[;J ȞK y'< 2k|

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

    1971

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.