From Partial to Strictly Incremental Constituent Parsing (2024)

Abstract: We study incremental constituent parsers to assess their capacity to output trees based on prefix representations alone. Guided by strictly left-to-right generative language models and tree-decoding modules, we build parsers that adhere to a strong definition of incrementality across languages. This builds upon work that asserted incrementality, but that mostly only enforced it on either the encoder or the decoder. Finally, we conduct an analysis against non-incremental and partially incremental models.

## introduction incremental nlp aims to learn and adapt partial representations as information unfolds. however, with the rise of bidirectional lstms @xcite and transformers @xcite , recent research has focused on non-incremental solutions. these models process the full input for contextualization before they start generating any output. therefore, this approach does not capture the progressive unfolding of input over time, giving the sense that all of it is available all of a sudden @xcite . this is not an issue for most nlp tasks, but it is relevant for others, such as real-time nlp, e.g., instant machine translation or real-time speech. furthermore, work on incremental processing holds relevance in interdisciplinary research, especially where computer science, linguistics, and cognitive studies intersect. while some studies have addressed the challenge of outputting incremental structured representations -for various definitions of incrementality @xcite @xcite -analyses of trees remain limited, more notably since the popularization of deep learning, and are mostly partially incremental approaches. in this context, @xcite , one of the first neural parsing models, was also an incremental network based on sigmoid belief networks. this generative model broke down the probability of a structure into probabilities for individual derivation decisions, each influenced by previous decision history. however, the computation was expensive and its evaluation was restricted to sentences of up to 15 tokens in the english penn treebank @xcite . for shift-reduce constituent parsing, @xcite proposed an incremental model with minimal features, focusing on only three sentence positions to predict the next action. however, input sentences were contextualized using bidirectional lstms, thus relying on non-incremental encoders and effectively considering all upcoming words; a strategy that was later widely adopted by most neural syntactic parsing architectures, but that does not adhere to a definition of strong incrementality. more recently, @xcite introduced a span-based model that incrementally encodes input sentences into discrete elements using vectors from gpt-2 mapped into a codebook. despite this, it relied on bidirectional transformers and a cyk architecture @xcite for decoding these vectors into trees. complementarily, @xcite proposed an incremental decoder based on graph neural networks. although they referred to their parser as strongly incremental, sentences were encoded with bidirectional architectures like bert or xlnet @xcite . incrementality has been also explored for other parsing formalisms. @xcite developed an almost fully incremental parser for combinatory categorical grammars (ccg), relying on elmo embeddings @xcite and a bidirectional lstm for these predictions. later, a genuinely fully incremental ccg parser was introduced @xcite , using only elmo's forward pass and a leftto-right lstm, addressing biases in incremental ccg parsing. in the field of dependency parsing, incrementality has been a focus since the pre-neural era @xcite @xcite , with some models rivaling non-incremental ones. recently, @xcite found that with current neural architectures, incremental models for dependency parsing are less effective than bidirectional approaches. however, incorporating human-like reading strategies, such as brief delays, can significantly enhance performance, particularly in languages with leftward dependencies. ## incremental constituent parsing let @xmath0, ..., w n ) be a sequence of tokens such that w @xmath1, we are interested in learning a function that can map w into a constituent tree t . different from previous work, we are interested in modeling this function as an strictly incremental model. under this setup, the decision at time step i is based only on the prefix w 1 ...w i+k . it creates a partial tree, t i , where each word w i is added at its time step i, in a monotonic way. the delay parameter, k, mimics human reading processes, allowing for a slight look ahead to the upcoming words. human parsing is believed to be very swift, with latencies as short as 250 milliseconds @xcite . in this work, we will study both zero and small positive delays, i.e., @xmath2, 2]. next, we review our encoders ( §2.1) and decoders ( §2.2). ## conclusion this paper introduced a set of strictly incremental encoder-decoder constituent parsers, using generative language models and two types of decoders: one based on parsing as tagging, and the other on transition-based parsing with partial graph neural network representations. we tested the models in a diverse multilingual setting and also simulated human reading processes with positive delays of a few upcoming words. the results suggest that a significant portion of future challenges may be centered on the encoding side, and in how different phrases might be affected by the absence of bidirectionality. in this context, exploring research lines to inform the decoder, such as speculative real-time generation of next tokens in real time, could be a valuable step to explore parsing methods closer to human reading processes.