Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference (2020)

Abstract: We present a constituency parsing algorithm that, like a supertagger, works by assigning labels to each word in a sentence. In order to maximally leverage current neural architectures, the model scores each word’s tags in parallel, with minimal task-specific structure. After scoring, a left-to-right reconciliation phase extracts a tree in (empirically) linear time. Our parser achieves 95.4 F1 on the WSJ test set while also achieving substantial speedups compared to current state-of-the-art parsers with comparable accuracies.

## introduction recent progress in nlp, and practical machine learning applications more generally, has been driven in large part by increasing availability of compute. these advances are made possible by an ecosystem of specialized hardware accelerators such as gpus and tpus, highly tuned kernels for executing particular operations, and the ability to amortize computational costs across tasks through approaches such as pre-training and multitask learning. this places particular demands for a model to be efficient: it must parallelize, it must maximally use standard subcomponents that have been heavily optimized, but at the same time it must adequately incorporate task-specific insights and inductive biases. against this backdrop, constituency parsing stands as a task where custom architectures are prevalent and parallel execution is limited. stateof-the-art approaches use custom architecture components, such as the tree-structured networks of rnng @xcite or the per-span mlps in chart parsers @xcite . approaches to inference range from autoregressive generation, to cubic-time cky, to a* search -none of which are readily parallelizable. our goal is to demonstrate a parsing algorithm that makes effective use of the latest hardware. the desiderata for our approach are (a) to maximize parallelism, (b) to minimize task-specific architecture design, and (c) to lose as little accuracy as possible compared to a state-of-the-art highly-specialized model. to do this, we propose an algorithm that reduces parsing to tagging, where all tags are predicted in parallel using a standard model architecture such as bert @xcite . tagging is followed by a minimal inference procedure that is fast enough to schedule on the cpu because it runs in linear time with low constant factors (subject to mild assumptions). ## related work label-based parsing a variety of approaches have been proposed to mostly or entirely reduce parsing to a sequence labeling task. one family of these approaches is supertagging @xcite , which is particularly common for ccg parsing. ccg imposes constraints on which supertags may form a valid derivation, necessitating complex search procedures for finding a highscoring sequence of supertags that is self-consistent. an example of how such a search procedure can be implemented is the system of @xcite , which uses a * search. this search procedure is not easily parallelizable on gpu-like hardware, and has a worst-case serial running time that is exponential in the sentence length. @xcite propose a different approach that fully reduces parsing to sequence labeling, but the label set size is unbounded: it expands with tree depth and related properties of the input, rather than being fixed for any given language. there have been attempts to address this by adding redundant labels, where the model learns to switch between tagging schemes in an attempt to avoid the problem of unseen labels @xcite , but that only increases the label inventory rather than restricting it to a finite set. our approach, on the other hand, uses just 4 labels in its simplest formulation (hence the name tetra-tagging). shift-reduce transition systems a number of parsers proposed in the literature can be categorized as shift-reduce parsers @xcite @xcite . these systems rely on generating sequences of actions, which need not be evenly distributed throughout the sentence. for example, the construction of a deep right-branching tree might involve a series of shift actions (one per word in the sentence), followed by equally many consecutive reduce actions that all cluster at the end of the sentence. due to the uneven alignment between actions and locations in a sentence, neural network architectures in recent shift-reduce systems @xcite @xcite generally follow an encoder-decoder approach with autoregressive generation rather than directly assigning labels to positions in the input. our proposed parser is also transition-based, but there are guaranteed to be exactly two decisions to make between one word and the next. this fixed alignment allows us to predict all actions in parallel rather than autoregressively. chart parsing chart parsers fundamentally operate over span-aligned rather than word-aligned representations. for instance, the size of the chart in the cky algorithm @xcite @xcite is quadratic in the length of the sentence, and the algorithm itself has cubic running time. this is true for both classical methods and more recent neural approaches @xcite . the construction of a chart involves a non-trivial (quadratic) computation that is specialized to parsing, and implementing the cky algorithm on a hardware accelerator is a nontrivial and hardware-specific task. left-corner parsing to achieve all of our desiderata, we combine aspects of the previouslymentioned approaches with ideas drawn from a long line of work on left-corner parsing @xcite @xcite @xcite . much of past work highlights the benefits of a left-corner formulation for memory efficiency, with implications for psycholin- an example tree with the corresponding labels. the nonterminal nodes have been numbered based on an in-order traversal. ## method to introduce our method, we first restrict ourselves to only consider unlabeled full binary trees (where every node has either 0 or 2 children). we defer the discussion of labeling and non-binary structure to section 3.5. ## results our proposed parser is designed to rank syntactic decisions entirely in parallel, with inference reduced to a minimal linear-time algorithm. its neural architecture consists almost entirely of bert layers, with the only additions being two trainable projection matrices. to verify our approach, we train our parser on the penn treebank @xcite and evaluate its efficiency and accuracy when running on cloud tpu v3 hardware. in in figure 4 , we plot the parser's accuracy across different settings for the maximum stack depth. the f1 score rapidly asymptotes as the stack size limit is increased, which validates our claim that inference can run in linear time. ## conclusion we present a reduction from constituency parsing to a tagging task with two binary structural decisions and two labeling decisions per word. remarkably, probabilities for these tags can be estimated fully in parallel by a simple classification layer on top of a neural network architecture such as bert. we hope that this formulation can be useful as a simple and low-overhead way of integrating syntax into any neural nlp model, including for multi-task training and to predict syntactic annotations during inference. by reducing the task-specific architecture components to a minimum, our method can be rapidly adapted as new modeling techniques, efficiency optimizations, and hardware accelerators become available. code for our approach is available at github.com/nikitakit/tetra-tagging.