Many structured inputs are trees whose nodes can have arbitrarily many children. Examples include dependency parses, where one verb can govern a dozen words, and program syntax trees, where one block can hold many statements. A cheap way to learn from such trees is a tree echo state network. This is a recurrent network whose internal weights are random and never trained. It computes a state for each node bottom-up from that node's label and its children's states, and only a final linear layer is fit, in closed form. The obstacle is width. Summing many child states makes the input to a node grow with its number of children, which can break the stability these untrained networks depend on. The textbook fix from trained tree models is to binarize the tree. The left-child right-sibling encoding rewrites any tree so that each node points to its first child and to its next sibling. Doing so turns every wide node into a chain of siblings. Under fixed contractive dynamics, though, a chain of length $n$ shrinks early siblings' information by roughly a factor $\sigma^n$. The binarization that solves the fan-in problem therefore creates a memory problem.
We propose to treat the two edge types of a binarized tree as different dynamical directions. The "down to first child" step should stay contractive, so that the network still forgets far-away structure and remains stable. The "across to next sibling" step should be close to an isometry, built from an orthogonal mixing term borrowed from edge-of-stability echo state networks, so that a wide node's children are carried along without decay. If this works, a reservoir with untrained weights handles trees of any fan-out with accuracy that stays flat as width grows. Each training run would still cost minutes rather than the hours needed to backpropagate through tree structure.
Core Claim
Our claim is that, for untrained tree reservoirs, how a tree is binarized matters less than which spectral regime each binarized edge type is given. An isotropic reservoir on a left-child right-sibling tree will lose recall of early siblings roughly geometrically in the sibling position. An anisotropic reservoir, with a contractive child step and a near-isometric sibling step, will hold recall nearly constant across sibling positions while keeping depth-wise forgetting. As a result it will match or beat both child-sum pooling and fixed-arity position matrices on real tasks where fan-out is large. The claim is falsifiable at the level of a single curve: recall of the $k$-th child's label from its parent's state, plotted against $k$.
Position Relative to Prior Work
The method's starting point is the tree echo state network of TreeESN: a Preliminary Experimental Analysis and its journal form Tree Echo State Networks. That work computes node states bottom-up, using either one random matrix per child position up to a fixed maximum arity or a plain sum over children. It studies a single contraction coefficient and compares root versus mean-of-nodes readouts on alkane boiling points. It never binarizes, and its trees have out-degree at most four, so the width regime we target was not tested. ITAmoji 2018: Emoji Prediction via Tree Echo State Networks motivates the proposal. It applied the same model to wide, unbounded-degree dependency trees of Italian tweets with raw multi-child aggregation, which is exactly the setting where fan-in variance should hurt, and it reported no analysis of that effect. Graph Echo State Networks generalizes the recurrence to arbitrary graphs with symmetric neighbor sums. That design deliberately ignores the ordered, asymmetric child/sibling relations we exploit.
On the binarization side, Tree-to-tree Neural Networks for Program Translation supplies the encoding. It uses left-child right-sibling binarization so a trained binary Tree-LSTM can read variable-degree program trees. In that setting, learned gates can absorb whatever the long sibling chains do to the signal, so the dynamical cost of binarization never surfaced. Left-factored binarization, as used in Dependency Parser for Chinese Constituent Parsing, is the main alternative layout. It inserts synthetic intermediate nodes that carry no label, whereas left-child right-sibling keeps a one-to-one correspondence between binary nodes and real nodes. We compare the two layouts but expect the regime of each edge, not the layout itself, to drive the result.
On the reservoir side, Edge of stability echo state networks supplies the mechanism. It mixes a nonlinear reservoir update with an orthogonal linear term, which pushes the update's sensitivity spectrum toward the unit circle, and it reports short-term memory capacity of 98.43 out of 100 against 30.40 for a standard leaky network. We apply that mixing to one edge type only. Chasing the Echo State Property constrains the design and also supplies an evaluation tool. It shows empirically that strong input can keep reservoirs stable well beyond the classical spectral-radius-below-one rule. That means a well-tuned isotropic reservoir with a large coefficient is a serious competitor, and the paper's empirical stability index lets us measure stability rather than assume it.
Research Program
Write $c(v)$ for the first child of node $v$ and $s(v)$ for its next sibling, both in the original ordered tree. In the left-child right-sibling tree, the state $x_v$ summarizes $v$'s subtree together with all later siblings' subtrees, and missing neighbors contribute a zero state. We compute
$$x_v = \beta \tanh\big(W_{in} u_v + \sigma_c W_c\, x_{c(v)} + \sigma_s W_s\, x_{s(v)}\big) + (1-\beta)\, O\, x_{s(v)}.$$
Here $u_v$ is the node's label embedding, and $W_{in}, W_c, W_s$ are fixed random matrices with unit spectral radius. $\sigma_c$ and $\sigma_s$ are the child and sibling scaling coefficients, $O$ is a fixed random orthogonal matrix, and $\beta \in (0,1]$ sets how close the sibling step is to an isometry. Setting $\beta = 1$ and $\sigma_c = \sigma_s$ recovers an isotropic binarized tree reservoir, which is our central ablation.
The sensitivity of $x_v$ to its sibling-chain predecessor is $\beta D W_s \sigma_s + (1-\beta) O$, where $D$ is the diagonal of $\tanh$ derivatives. For small $\beta$ its singular values lie near one, following the edge-of-stability argument. The sensitivity to the first child is scaled by $\beta\sigma_c$. Consequently, information from a leaf at depth $d$ should be attenuated mainly by a factor on the order of $(\beta\sigma_c)^d$, and only weakly by its sibling position. We will derive a sufficient condition on $(\sigma_c, \beta)$ for the network to depend only on bounded-depth suffixes of the tree, which is the tree analogue of the echo state property. Because the near-isometric sibling step weakens any worst-case guarantee, we will also report the empirical stability index of Chasing the Echo State Property, computed over pairs of random initial leaf states.
We will build three pieces. The first is the model above, running in batched form. Left-child right-sibling trees can be evaluated level by level, which follows the pairwise-merge scheduling idea of Massively Parallel Dynamic Programming on Trees. The second is a tree memory capacity probe, a direct analogue of sequential memory capacity. A ridge readout on a node's state must reconstruct the label of the descendant at each (relative depth, sibling position) pair, and capacity is the summed squared correlation. The third is a readout study. Because left-child right-sibling has no virtual nodes, mean pooling over real nodes is well defined. For the left-factored layout we will compare pooling over all nodes against pooling over real nodes only. This directly answers the readout question that TreeESN: a Preliminary Experimental Analysis leaves open.
Baselines
The naive reference point is a flat echo state network on the token sequence in surface order, with the same reservoir size and the same ridge readout. To make the flat model as strong as possible, we use the edge-of-stability variant of Edge of stability echo state networks, so that "structure helps" is not confused with "memory helps". If our model does not beat this baseline on parsed text, tree structure is not paying for itself in the reservoir setting.
The strongest existing reservoir method is the original tree echo state network of TreeESN: a Preliminary Experimental Analysis, run in both of its forms. The first form uses position-specific random matrices up to a maximum arity, with children beyond that arity summed into the last slot. The second uses child sum, which is the configuration family used for ITAmoji. Its reported results are a mean absolute error of 2.60°C on Alkanes with mean state mapping, against 1.74 for the trained graph network baseline in the same paper. On ITAmoji, ITAmoji 2018: Emoji Prediction via Tree Echo State Networks reports a Macro-F1 of 19.24, but that figure belongs to a 13-model ensemble that includes a character LSTM, not to a single tree reservoir. We will therefore re-run single tree reservoirs ourselves and treat 19.24 only as context. For the Stanford Sentiment Treebank, we found no reported reservoir result on Lacuna.
The key-ingredient ablation is the isotropic binarized reservoir: the same left-child right-sibling trees, $\beta = 1$, one shared scaling coefficient, and that coefficient searched up to values well above one, as Chasing the Echo State Property licenses. We also run a degree-normalized child-mean reservoir, which removes fan-in variance without binarizing. As a trained reference, not a cost-matched competitor, we include the Tree-LSTM of Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks. On the Stanford Sentiment Treebank it reports 51.0% fine-grained sentence accuracy for the constituency model, against 46.4% for a sequential LSTM.
All reservoir models share one setup. They use the same reservoir sizes (1,000 and 5,000 units), the same label embeddings, the same ten random seeds, and the same ridge readout with regularization chosen on a validation split. Each model gets an identical budget of 100 random-search trials over its own hyperparameters. The anisotropic model's extra hyperparameters ($\beta$, $\sigma_s$) therefore come out of its own budget rather than as free extras. "Beating" a baseline means a mean improvement larger than two seed standard deviations on the primary metric. On the wide-tree tasks, it also means a statistically flatter accuracy-versus-fan-out curve.
Why not just…?
Why not just flatten the input and use a sequential reservoir? Trained models give strong evidence that structure matters. Tree-LSTMs beat sequential LSTMs on fine-grained sentiment (51.0% against 46.4% in Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks), and tree encoding helped program translation in Tree-to-tree Neural Networks for Program Translation. That evidence comes from trained models, however, and an edge-of-stability sequential reservoir already has near-maximal memory capacity. The flat baseline above is designed to settle the question directly in the untrained setting. Our synthetic tasks, where the target depends on a head-to-dependent relation that sits far apart in the surface order, should separate the two models sharply.
Why not just sum or average the children without binarizing? This is the real threat. Averaging removes the fan-in variance that motivates binarization, and for genuinely unordered dependents it may be enough. It cannot represent child order, however, and Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks found that order-aware child handling beats child-sum on ordered constituency trees. We expect child-mean to tie us on order-insensitive targets and lose on order-sensitive ones. The synthetic suite includes both kinds, so a tie everywhere would refute our claim's practical value.
Why not just binarize and tune one large coefficient? Chasing the Echo State Property suggests a strongly driven isotropic reservoir might preserve sibling information well enough. If it did, the anisotropy would be unnecessary. The isotropic ablation with an extended coefficient range tests exactly this. Our prediction is that any single coefficient faces a trade-off: one large enough to keep early siblings also stops forgetting across depth, which shows up as a lower empirical stability index and worse accuracy on deep trees. That trade-off is visible in the two-dimensional (depth, sibling position) memory map.
Why not just train a Tree-LSTM? When accuracy is all that matters, a trained model probably wins, and we report it as an upper reference. The question here is what accuracy is achievable at closed-form training cost. ITAmoji 2018: Emoji Prediction via Tree Echo State Networks reports training a 5,000-unit tree reservoir on 200,000 trees in 25 minutes without parallelization. We report wall-clock time and accuracy together, and we report how much of the gap to the trained model is closed.
Proposed Experiments
The decisive check is synthetic. We generate random ordered trees with controlled fan-out $n$ from 2 to 32 and depth from 2 to 10. Labels are drawn from a small alphabet. Targets are either the label of the $k$-th child of the root (order-sensitive) or the count of a label among the root's children (order-insensitive). The anisotropic model should hold first-child recall near constant as $n$ grows. The isotropic binarized model should decay with $k$. Child-mean should fail the order-sensitive target but match on counting. Alongside accuracy, we report the tree memory capacity map and the empirical stability index.
On real data, ITAmoji is the natural wide-tree test. We report Macro-F1 per single model, stratified by the maximum fan-out of each tweet's dependency tree. If width is the real bottleneck, the anisotropic model's advantage should grow with fan-out. The Stanford Sentiment Treebank gives a built-in control. Its native constituency trees are already binary, so binarization and anisotropy should matter little there. Dependency parses of the same sentences are wide, so they should show the effect. This within-dataset contrast is cleaner than any cross-dataset comparison. Alkanes, where out-degree is at most four, checks that we do not regress against the reported 2.60°C mean absolute error in the narrow regime. Finally, we compare left-child right-sibling against left-factored layouts under identical anisotropic dynamics, with and without virtual nodes in the readout. This tests whether the layout matters once each edge type has the right regime.
The proposal fails if the regularization-matched isotropic or child-mean baselines produce the same flat fan-out curves. It also fails if the gains on dependency trees vanish once trees are stratified by fan-out.
References
- TreeESN: a Preliminary Experimental Analysis
- Tree Echo State Networks
- ITAmoji 2018: Emoji Prediction via Tree Echo State Networks
- Graph Echo State Networks
- Tree-to-tree Neural Networks for Program Translation
- Dependency Parser for Chinese Constituent Parsing
- Edge of stability echo state networks
- Chasing the Echo State Property
- Massively Parallel Dynamic Programming on Trees.
- Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks