On Eliciting Syntax from Language Models via Hashing

Yiran Wang, Masao UtiyamaEMNLP 2024 · DOI

Introduction

Presented at EMNLP 2024, this research explores the intersection of deep learning and classical linguistics, specifically how to extract latent grammatical structures from large pre-trained language models (PLMs) like BERT and RoBERTa. The authors introduce Parserker2, a method utilizing contrastive hashing and an enhanced "first-order" CKY algorithm to induce syntactic trees from raw text. This approach allows for high-quality unsupervised parsing in approximately 30 minutes on a single GPU, representing a significant efficiency gain over previous state-of-the-art methods.

The Challenge of Unsupervised Parsing

Unsupervised parsing, or grammar induction, involves identifying the hierarchical structure of a sentence—such as identifying noun phrases—without human-annotated treebanks. While modern PLMs excel at next-word prediction, their internal representation of grammar is often latent and unstructured. Previous attempts to elicit this syntax using binary hashing were "zero-order," meaning the model's score for a span only considered its endpoints, ignoring internal split points. This lack of structural awareness hindered the learning of meaningful hierarchies in unsupervised settings.

Methodology: Parserker2

The authors propose three primary technical innovations to address these limitations:

  1. First-order Bit-level CKY: The classic Cocke-Kasami-Younger (CKY) algorithm is upgraded to a first-order version. In this setup, the score for a span depends on its internal split point. By considering the average representation of the two resulting sub-trees rather than just the span's endpoints, the model is forced to account for internal structure.
  2. Unsupervised Contrastive Hashing: Without gold labels, the model uses the text itself as a signal. Identical spans within a batch are treated as "positive pairs," and the model is trained to assign them similar binary hash codes.
  3. The $\ell_{min}$ Loss Function: To overcome weak signals in massive PLM vocabularies, the authors introduce a "strong alignment" loss. This targets the "farthest" positive pairs—those the model is most uncertain about—and pulls them together while preventing the model from collapsing into trivial solutions.
The Parserker2 pipeline: from raw text through a PLM and hash layer to induced syntactic trees.

Key Insights: Hashing as Categorization

A significant finding is that the resulting binary codes (visualized as hex codes like 7EBB or 5E50) effectively function as discovered syntactic categories. Spans that align with human-labeled "Noun Phrases" naturally cluster with similar hash codes. This unified binary space encodes both the lexical meaning of words and their syntactic roles within the sentence.

Visualization of the CKY chart and span scoring mechanism.

Evaluation and Results

The model was evaluated on the Penn Treebank (PTB) for English and the Chinese Treebank 5.1 (CTB). Standard preprocessing was applied to ensure comparability with existing literature.

  • State-of-the-Art Performance: On the English PTB, Parserker2 achieved an F1 score of 62.4 using RoBERTa, rivaling more complex probing methods.
  • Robustness in Chinese: The model reached an F1 of 48.5 on the CTB, significantly outperforming previous explicit grammar models that often struggle with Chinese syntax.
  • Efficiency: Training completes in roughly 30 minutes, a massive improvement over traditional unsupervised parsers that often require days.
  • Bit-rate Efficiency: Lexical and syntactic information is preserved effectively using only 16 to 44 bits.

Limitations and Future Directions

Despite its successes, the authors note several areas for future work. The optimal number of bits ($K$) currently requires manual tuning for different datasets. Additionally, the use of simple linear averaging for sub-tree representations is a speed-oriented compromise; non-linear mappings might capture more complex nuances. Finally, the scalability of this hashing approach to truly "Large" Language Models (LLMs) remains to be explored.

Summary updated

BibTeX
@inproceedings{wang2024eliciting,
  author = {Yiran Wang and Masao Utiyama},
  title = {{On Eliciting Syntax from Language Models via Hashing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.emnlp-main.479},
}
Figure