Hierarchical abstraction is a fundamental principle across many data modalities, enabling complex sequences to be represented compositionally at multiple levels. Learning such hierarchies directly from data, without explicit structural supervision, remains a central challenge in representation learning. We investigate whether meaningful hierarchical structure can emerge from compression alone. While autoencoders learn compressed representations through reconstruction, this objective does not necessarily favour meaningful compositional structure. We study this challenge through unsupervised grammar induction, where the underlying hierarchy can be evaluated explicitly. We introduce a hierarchical token-merging autoencoder that recursively combines adjacent tokens into increasingly abstract representations, compressing entire sequences through a variational information bottleneck. The model jointly learns representations and hierarchical structure by marginalising over possible binary trees using dynamic programming. To address training instability, we combine independently trained models through unsupervised consensus and distillation. Experiments on a synthetic, ambiguous grammar demonstrate the emergence of meaningful hierarchical structure without structural supervision. The resulting model achieves 93% grammatical parse-validity and 93% exact reconstruction on held-out sequences, compared with 42% parse-validity for the strongest trivial baseline. These findings establish a proof of concept for hierarchical token merging as a mechanism for unsupervised structure discovery and abstraction learning.
Figures & tables
Figure 1: The three-stage pipeline. The same architecture is used as the base model in Stage 1 and as the distilled model in Stage 3; only Stage 1 uses the chart, while Stage 3 trains on the fixed silver trees.
Figure 2: One chart cell for span (i,j) at split k . The two child spans are merged into a candidate parent, which the unmerger tries to invert; the negative squared error (“energy”) is the local score. The span score is the log-sum-exp over splits, and the highest-scoring split is stored as a back-pointer for parsing.
Overall
L=3
L=4
L=5
L=6
L=7
L=8
Random binary tree
0.150
0.500
0.256
0.137
0.094
0.046
0.027
Left-branching
0.007
0.000
0.000
0.000
0.000
0.000
0.000
Right-branching
0.416
1.000
0.800
0.360
0.320
0.240
0.080
Table 1: Baselines on the held-out set (137 surfaces). “Random” is the exact expected validity of a uniformly random binary tree, obtained by enumeration rather than sampling. Overall figures are averaged over surfaces.
Hyperparameter
Base model
Student
Embedding dimension
32
48
Hidden dimension
128
128
Learning rate
2×10−3
2×10−3
Training steps
2500
12000
Batch size
32
32
KL weight β
0.04
0.002
Table 2: Hyperparameters for the base models and the distilled student. Each pool trains 24 base models, of which the 8 with the highest peer agreement are selected; results are reported over seven independent pools. The KL weight is warmed up, so the base models, which stop at step 2500, end at β≈0.032 .
Aggregation
Base validity
Base recon.
Consensus
Student validity
Student recon.
Straight-through
0.552
0.147
0.985
0.989
0.943
Hard (argmax)
0.328
0.233
0.981
0.994
0.925
Soft (blend)
0.443
0.118
0.931
0.948
0.920
Table 3: Aggregation ablation. Twenty-four base models per mode on matched seeds and one data split, so initial weights and batch order are identical within each row and only the aggregation rule differs. Base-model figures are medians over the twenty-four models; consensus and student figures are for the pipeline built from them.
Figure 3: The seed lottery. Held-out parse-validity of the 24 base models in each of the four seed-varying pools (labelled by their seeds, so s52-75 is pool 52–75). The spread within a pool is wide even though the models differ only in random seed.
Models retained
2
4
6
8
10
12
16
20
24
Mean over pools
0.951
0.903
0.928
0.933
0.931
0.920
0.884
0.899
0.887
Worst pool
0.796
0.796
0.819
0.844
0.797
0.716
0.663
0.682
0.630
Table 4: Consensus validity against the number of models retained, ranked by peer agreement, over all seven pools. Unlike Figure 4 , which draws models at random, this adds them in decreasing order of peer agreement. K=8 is the value the pipeline uses.
Figure 4: Consensus validity against ensemble size when models are drawn at random, averaged over sixty draws per point, for the four seed-varying pools. Every pool improves with size, apart from one dip in pool 52–75, and the spread narrows. Compare Table 4 , where models are added in order of decreasing peer agreement and the consensus does not rise with size.
Pool
Consensus (all 24)
Consensus (top 8)
Student validity
Student recon.
Student gold-match
seed
52–75
0.630
0.887
0.868
0.971
0.483
76–99
0.990
0.985
0.989
0.943
0.517
100–123
0.969
0.867
0.839
0.925
0.443
124–147
0.981
0.953
0.960
0.937
0.512
mean
0.893
0.923
0.914
0.944
0.489
split
split 1
0.805
1.000
0.988
0.889
0.532
Table 5: Seven independent 24-model pools. The first four vary only the random seed on one data split; the last three redraw the data as well. The two consensus columns are the parse agreed over all 24 models and over the eight retained by peer agreement; both are measured on training surfaces. Student columns are held-out. Gold parses are used only to compute these numbers, never in training or selection.
L=3
L=4
L=5
L=6
L=7
L=8
Validity, pool 76–99
1.000
1.000
1.000
1.000
0.960
0.960
Validity, pool 124–147
1.000
1.000
1.000
0.929
0.920
0.920
Validity, pool 100–123
1.000
0.936
0.846
0.833
0.720
0.760
Reconstruction, pool 76–99
1.000
1.000
1.000
1.000
0.880
0.720
Right-branching baseline
1.000
0.800
0.360
0.320
0.240
0.080
Table 6: Distilled students by sentence length, held-out, for the three seed-varying pools that were measured this way. Both metrics degrade at lengths seven and eight. The right-branching baseline over the same lengths is given for comparison.
Figure 5: Cosine similarity between the nineteen word embeddings, ordered by category, for the best base model (held-out parse-validity 1.000) and the distilled student (0.989). The base model groups words by category; the student does not, yet both parse well. A sweep of the student’s KL weight (holding latent size fixed) does not reproduce the clustering, so it is a by-product of how the base models induce structure, not of the bottleneck and not a prerequisite for parsing.
Base
Restart, tight
Restart, loose
Continuous
Seed
Val.
Rec.
Val.
Rec.
Val.
Rec.
Val.
Rec.
54
0.897
0.092
0.862
0.649
0.851
0.649
0.868
0.724
74
0.994
0.172
0.966
0.644
0.805
0.621
0.948
0.615
93
1.000
0.057
0.328
0.851
0.328
0.713
0.799
0.718
134
1.000
0.167
1.000
0.713
0.989
0.615
0.994
0.638
Table 7: Four seeds that induce the grammar, each trained for 15,000 steps under three strategies that share the tight first 2500 steps and then differ in how training continues. Restart resets the learning rate to its maximum, continuous uses one smooth decay with no restart, and the loose arm drops the KL weight to 0.002. Base is the frozen base model. Reconstruction recovers with training but plateaus below the student’s 0.93, and no strategy keeps the grammar while reaching 0.93 reconstruction. Validity and reconstruction are held-out.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 6: The four networks of the base model, with layers and dimensions. The lifter maps each token id to a leaf latent through two embedding tables (a mean and a log-variance) and the reparameterisation trick. The merger is the encoder step, a two-layer perceptron with a ReLU that combines two child latents into a parent; it is applied bottom-up at every internal node of the tree. The unmerger is the decoder step and an approximate inverse of the merger, predicting the two children from a parent, applied top-down; its squared error against the true children is the one-step energy that also scores splits in the chart. The unlifter is a single linear layer that reads a recovered leaf latent back to a distribution over the vocabulary. A single merger and a single unmerger are shared across all tree depths.