# ListOps: A Diagnostic Dataset for Latent Tree Learning

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

## Key facts

- Cited by 129 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2018.

## Built on by (most cited first, 30 of 129)

- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Mega: Moving Average Equipped Gated Attention](https://mlsanity.com/paper/2209.10655/) (2022)
- [Pretrained Transformers as Universal Computation Engines](https://mlsanity.com/paper/2103.05247/) (2021)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)
- [Long-Short Transformer: Efficient Transformers for Language and Vision](https://mlsanity.com/paper/2107.02192/) (2021)
- [Luna: Linear Unified Nested Attention](https://mlsanity.com/paper/2106.01540/) (2021)
- [Going Beyond Linear Transformers with Recurrent Fast Weight Programmers](https://mlsanity.com/paper/2106.06295/) (2021)
- [A Practical Survey on Faster and Lighter Transformers](https://mlsanity.com/paper/2103.14636/) (2021)
- [Flowformer: Linearizing Transformers with Conservation Flows](https://mlsanity.com/paper/2202.06258/) (2022)
- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [Megalodon: Efficient LLM Pretraining and Inference with Unlimited Context Length](https://mlsanity.com/paper/2404.08801/) (2024)
- [Relative Positional Encoding for Transformers with Linear Complexity](https://mlsanity.com/paper/2105.08399/) (2021)
- [Efficient Long Sequence Modeling via State Space Augmented Transformer](https://mlsanity.com/paper/2212.08136/) (2022)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Never Train from Scratch: Fair Comparison of Long-Sequence Models Requires Data-Driven Priors](https://mlsanity.com/paper/2310.02980/) (2023)
- [SwitchHead: Accelerating Transformers with Mixture-of-Experts Attention](https://mlsanity.com/paper/2312.07987/) (2023)
- [PolaFormer: Polarity-aware Linear Attention for Vision Transformers](https://mlsanity.com/paper/2501.15061/) (2025)
- [Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems](https://mlsanity.com/paper/2109.15142/) (2021)
- [Linear Complexity Randomized Self-attention Mechanism](https://mlsanity.com/paper/2204.04667/) (2022)
- [Bridging Discrete and Backpropagation: Straight-Through and Beyond](https://mlsanity.com/paper/2304.08612/) (2023)
- [Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representation](https://mlsanity.com/paper/2305.19798/) (2023)
- [Improving Transformers with Probabilistic Attention Keys](https://mlsanity.com/paper/2110.08678/) (2021)
- [FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention](https://mlsanity.com/paper/2108.02347/) (2021)
- [Online learning of long-range dependencies](https://mlsanity.com/paper/2305.15947/) (2023)

## Abstract (arXiv)

Latent tree learning models learn to parse a sentence without syntactic supervision, and use that parse to build the sentence representation. Existing work on such models has shown that, while they perform well on tasks like sentence classification, they do not learn grammars that conform to any plausible semantic or syntactic formalism (Williams et al., 2018a). Studying the parsing ability of such models in natural language can be challenging due to the inherent complexities of natural language, like having several valid parses for a single sentence. In this paper we introduce ListOps, a toy dataset created to study the parsing ability of latent tree models. ListOps sequences are in the style of prefix arithmetic. The dataset is designed to have a single correct parsing strategy that a system needs to learn to succeed at the task. We show that the current leading latent tree models are unable to learn to parse and succeed at ListOps. These models achieve accuracies worse than purely sequential RNNs.