# Approximating CKY with Transformers

arXiv: https://arxiv.org/abs/2305.02386 · HTML: https://mlsanity.com/paper/2305.02386/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 82 references that are in the map.
- First posted on arXiv 3 May 2023.

## Builds on (most cited first, 30 of 44)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Perceptual Losses for Real-Time Style Transfer and Super-Resolution](https://mlsanity.com/paper/1603.08155/) (2016)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [BERT Rediscovers the Classical NLP Pipeline](https://mlsanity.com/paper/1905.05950/) (2019)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Constituency Parsing with a Self-Attentive Encoder](https://mlsanity.com/paper/1805.01052/) (2018)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Multilingual Constituency Parsing with Self-Attention and Pre-Training](https://mlsanity.com/paper/1812.11760/) (2018)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Cramming: Training a Language Model on a Single GPU in One Day](https://mlsanity.com/paper/2212.14034/) (2022)
- [Grammar as a Foreign Language](https://mlsanity.com/paper/1412.7449/) (2014)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Efficient Second-Order TreeCRF for Neural Dependency Parsing](https://mlsanity.com/paper/2005.00975/) (2020)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [Characterizing Intrinsic Compositionality in Transformers with Tree Projections](https://mlsanity.com/paper/2211.01288/) (2022)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [Transition-based Parsing with Stack-Transformers](https://mlsanity.com/paper/2010.10669/) (2020)
- [Location Attention for Extrapolation to Longer Sequences](https://mlsanity.com/paper/1911.03872/) (2019)

## Built on by (most cited first, 3 of 3)

- [IsoBench: Benchmarking Multimodal Foundation Models on Isomorphic Representations](https://mlsanity.com/paper/2404.01266/) (2024)
- [How transformers learn structured data: insights from hierarchical filtering](https://mlsanity.com/paper/2408.15138/) (2024)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)

## Abstract (arXiv)

We investigate the ability of transformer models to approximate the CKY algorithm, using them to directly predict a sentence's parse and thus avoid the CKY algorithm's cubic dependence on sentence length. We find that on standard constituency parsing benchmarks this approach achieves competitive or better performance than comparable parsers that make use of CKY, while being faster. We also evaluate the viability of this approach for parsing under textitrandom PCFGs. Here we find that performance declines as the grammar becomes more ambiguous, suggesting that the transformer is not fully capturing the CKY computation. However, we also find that incorporating additional inductive bias is helpful, and we propose a novel approach that makes use of gradients with respect to chart representations in predicting the parse, in analogy with the CKY algorithm being a subgradient of a partition function variant with respect to the chart.