Hierarchical Bracketing Encodings for Dependency Parsing as Tagging
Ana Ezquerro ana.ezquerro, David Vilares david.vilares, Anssi Yli-Jyrä anssi.yli-jyra, Carlos Gómez-Rodríguez carlos.gomez, [-1cm] Universidade da Coruña, CITIC ( @udc.es ) · 2025
Read Hierarchical Bracketing Encodings for Dependency Parsing as Tagging by Ana Ezquerro ana.ezquerro, David Vilares david.vilares, Anssi Yli-Jyrä anssi.yli-jyra, Carlos Gómez-Rodríguez carlos.gomez, [-1cm] Universidade da Coruña, CITIC ( @udc.es ) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11693.txt.
Introduction
Ana Ezquerro, David Vilares, Anssi Yli-Jyrä, and Carlos Gómez-Rodríguez encode sentence trees as labels in a 2025 paper. Dependency parsing maps how words in a sentence depend on each other, forming a tree. A fast way to parse is to tag each word with a label that rebuilds the tree. The known four-bit encoding does this, but may waste labels.
The authors place that encoding inside a wider family based on nested brackets. They derive the best member of the family, which needs only twelve labels where the older one needs sixteen. Their version also stretches to tangled, non-projective trees in a compact way. Parsers using the new encodings matched rivals on a varied set of language treebanks.
Catalog record
| CREATOR | Ana Ezquerro ana.ezquerro, David Vilares david.vilares, Anssi Yli-Jyrä anssi.yli-jyra, Carlos Gómez-Rodríguez carlos.gomez, [-1cm] Universidade da Coruña, CITIC ( @udc.es ) |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11693
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hierarchical Bracketing Encodings for Dependency Parsing as Tagging Ana Ezquerro ana.ezquerro, David Vilares david.vilares, Anssi Yli-Jyrä anssi.yli-jyra, Carlos Gómez-Rodríguez carlos.gomez, [-1cm] Universidade da Coruña, CITIC ( @udc.es ) Abstract We present a family of encodings for sequence labeling dependency parsing, based on the concept of hierarchical bracketing. We prove that the existing 4-bit projective encoding belongs to this family, but it is suboptimal in the number of labels used to encode a tree. We derive an optimal hierarchical bracketing, which minimizes the number of symbols used and encodes projective trees using only 12 distinct labels (vs. 16 for the 4-bit encoding). We also extend optimal hierarchical bracketing to support arbitrary non-projectivity in a more compact way than previous encodings. Our new encodings yield competitive accuracy on a diverse set of treebanks. 1 Introduction Sequence labeling with contextualized representations enables efficient dependency parsers that function as taggers while achieving high or even state-of-the-art performance ( Amini et al. 2023 ; Gómez-Rodríguez et al. 2023 ) . This paradigm has two key aspects: a powerful sequence encoder—often a pre-trained model—and a linearization algorithm that transforms dependency trees into label sequences with a strict one-to-one mapping. Regarding linearizations, various strategies have been proposed. Early approaches represented a word’s head as an offset ( Strzyz et al. 2019 ; Lacroix 2019 ) , which could be absolute, relative to the dependent, or based on word properties. Another strategy is bracketing encodings ( Yli-Jyrä and Gómez-Rodríguez 2017 ; Strzyz et al. 2019 ) , where each word label encodes a set of incoming or outgoing arcs, unlike positional encodings that explicitly encode the head. A third approach, transition-based encodings Gómez-Rodríguez et al. 2020 , assigns labels to transition subsequences split by read (shift-like) transitions. These strategies suffer from an unbounded label space. Instead, recent work proposes fixed-space solutions. Amini et al. 2023 proposed hexatagging, a projective tree linearization with eight labels but requiring an intermediate representation. Gómez-Rodríguez et al. 2023 introduced 4- and 7-bit labels for projective and 2-planar trees, with bounded label spaces of 16 and 128 labels. This work introduces a new family of hierarchical bracketing encodings, based on rope cover Yli-Jyrä 2019b . We show that the existing 4-bit projective encoding is part of this family, but suboptimal in terms of compactness. We introduce and test its optimal counterpart, and show that both improve for non-projective trees with pseudoprojectivity. We also generalize the optimal bracketing to directly encode arbitrary non-projective trees. 2 Preliminaries Let w_{1}\ldots w_{n} be an input string. A dependency graph is a directed graph G=(V,E) where V=\{0,\ldots,n\} . An edge (i,j) in E is called a dependency from word w_{i} to w_{j} . w_{i} is the head or parent, w_{j} is the dependent. Index 0 is used for a dummy node used when we deal with trees. We use the notation i\rightarrow j to specify that such a dependency is a rightward arc (i.e., when i<j ) and i\leftarrow j when it is a leftward arc ( i>j ). When direction is not specified, we use (i,j) . Node k is a descendant of node i if there is a path from i to k . An arc (i,j) is said to cross the arc (k,l) if \min(i,j)<\min(k,l)<\max(i,j)<\max(k,l) or \min(k,l)<\min(i,j)<\max(k,l)<\max(i,j) . An arc (i,j) is said to cover arc (k,l) if \min(i,j)\leq\min(k,l)\leq\max(k,l)\leq\max(i,j) . A dependency graph is a tree if it has no cycles and every node has exactly one parent except for the dummy node 0 , which has no parent. A tree is projective if it has no crossing arcs. An equivalent definition (see Nivre 2006 ) will be more directly useful in some proofs: a dependency tree is projective if, for each arc (i,j) , all nodes located between i and j are descendants of either i or j . 3 Brackets and superbrackets 3.1 Bracketing encodings Bracketing encodings for dependency parsing are based on the idea of representing dependencies using symbols that behave as balanced brackets. In the earliest and most basic bracketing encoding Strzyz et al. 2019 ; Strzyz et al. 2020 , a right arc from a word w_{i} to w_{j} is encoded by including an opening bracket / in the label of w_{i} , which matches the corresponding closing bracket > in the label of w_{j} . Similarly, a left arc from w_{j} to w_{i} is represented by an opening bracket < in the label of w_{i} that matches a closing bracket \ in the label of w_{j} . The result is shown in Figure 1(a) , where the label associated with each given word contains one < (resp. > ) symbol per incoming arc from the right (left) and one / (resp. \ ) symbol per outgoing arc towards the right (left). To decode the brackets back into a tree, we read them from left to right, using a stack. When reading an opening bracket ( / or < ) in the label of a word w_{i} , we push it to the stack, associating it with the index i . When reading a closing bracket > in the label of w_{j} , we pop the matching bracket / from the top of the stack, check its associated index i , and create the right arc from w_{i} to w_{j} . Finally, when reading a closing bracket \ , we proceed analogously, popping a < from the top of the stack and creating a left arc. This decoding method will recover the original tree if it is projective (i.e., without crossing arcs), as the nested matching of brackets prevents them from being paired in any way that would create crossing arcs. 1 1 1 The original implementation in ( Strzyz et al. 2019 ; Strzyz et al. 2020 ) does not decode like this. It decodes using two separate stacks for left and right arcs, and then the coverage is extended to support crossing arcs in opposite directions. Here we assume projective decoding with a single stack for didactic reasons, as it helps us establish the relation to our novel encodings. Extensions for non-projectivity will be presented later. Extensions to support crossing arcs exist ( Strzyz et al. 2020 ) , but we will stick to projective trees in this section. (a) Non-hierarchical. 0 1 2 3 4 5 6 7 // > < < \\>/ < \< \> (b) Optimal hierarchical. 0 1 2 3 4 5 6 7 / > < < >/ < \ < > (c) Hierarchical (4-bit). 0 1 2 3 4 5 6 7 / > < < \>/ < \< \> \ast Figure 1: Example showing the same tree encoded with the standard (non-hierarchical) bracketing encoding (Figure 1(a) ), and hierarchical bracketing encodings (Figures 1(b) and 1(c) ). In the latter, structural arcs are shown in red and solid, whereas auxiliary arcs are black and dashed. Figure 1(b) corresponds to the optimal hierarchical bracketing where 0\rightarrow 4 , 4\to 7 and 6\to 5 are the structural arcs. Figure 1(c) corresponds to the 4-bit encoding. This encoding obtains good practical results, especially in low-resource setups ( Muñoz-Ortiz et al. 2021 ) . Yet, it has the disadvantage that it is unbounded in terms of label