Hierarchical Token Merging with Recursive Autoencoders for Unsupervised Grammar Induction

Abstract

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Computation & Language / NLP

• arXiv preprint · 19 October 2026

  Cognitive Maps in Large Language Models

  Albert Qin, Jonathan Cohen and Gautam Reddy
• arXiv preprint · 20 October 2026

  The Router Already Knows

  Andrew Bistras and Marty Johnson
• arXiv preprint · 19 October 2026

  Text Dominance in Paralinguistic Conflict: Tracing Suppression Through Audio LLM Circuits

  Ankur Banerjee, Vishnu Guntakala, Danity Pike and 3 others
• arXiv preprint · 20 October 2026

  Harness Self-Evolution for Long-Horizon Terminal Agents

  Ruhan Wang, Yucheng Shi, Zongxia Li and 6 others
• arXiv preprint · 19 October 2026

  Curriculum Learning Teaches LLMs Long-Horizon Implicit Reasoning, Up To A Limit

  Jimson Huang, Maxwell Nickell, Ruowang Zhang and 1 other

All new papers in Computation & Language / NLP