4 and 7-bit Labeling for Projective and Non-Projective Dependency Trees
Authors: Carlos Gómez-Rodríguez
Diego Roca
David Vilares
Venue: EMNLP 2023 Main (2023)
Keywords: parsing
dependency parsing
sequence labeling
parsing as sequence labeling
encoding
TL;DR: We define bounded encodings for dependency parsing as sequence labeling, which are more compact and empirically outperform previous encodings.

Abstract: We introduce an encoding for parsing as sequence labeling that can represent any projective dependency tree as a sequence of 4-bit labels, one per word. The bits in each word's label represent (1) whether it is a right or left dependent, (2) whether it is the outermost (left/right) dependent of its parent, (3) whether it has any left children and (4) whether it has any right children. We show that this provides an injective mapping from trees to labels that can be encoded and decoded in linear time. We then define a 7-bit extension that represents an extra plane of arcs, extending the coverage to almost full non-projectivity (over 99.9% empirical arc coverage). Results on a set of diverse treebanks show that our 7-bit encoding obtains substantial accuracy gains over the previously best-performing sequence labeling encodings.

4 and 7-bit Labeling for Projective and Non-Projective Dependency Trees
Carlos Gómez-Rodriguez, Diego Roca and David Vilares
Universidade da Coruña, CITIC
Departamento de Ciencias de la Computación y Tecnologías de Información Campus de Elviña s/n, 15071
A Coruña, Spain
{carlos, gomez, d. rocal, david. vi vilares
Abstract
We introduce an encoding for syntactic pars- ing as sequence labeling that represent any projective dependency tree as sequence of 4-bit labels, one per word. The bits each word's label represent (I) whether it is a right or left dependent, (2) whether it is the outer- most (left/right) dependent of its parent, (3) whether it has any left children and (4) whether it has any right children. We show that this pro- vides injective mapping from trees labels that can be encoded and decoded in linear time. We then define 7-bit extension that represents extra plane of arcs, extending the coverage to almost full non-projectivity (over 99.9% em- pirical are coverage). Results on of diverse treebanks show that our 7-bit encoding obtains substantial accuracy gains over the previously best-performing sequence labeling encodings.
5
-ROOT-
It
should
continuc
to
be
defanged
V>+/
0100
0000
1111
0100
0000
1010
1100
Figure I: A dependency tree and its 4-bit encoding.
Contribution We present bounded sequence- labeling encoding that represents any projective dependency tree with 4 bits (i.e., 16 distinet labels) per word. While this requires one more bit than hexatagging, it is arguably more straightforward, as the bits directly reflect properties of each node in the dependency tree without an intermediate con- stituent structure, as hexatagging requires. Also, it has a clear relation to existing bracketing encod- ings, and has straightforward non-projective ex- tension using bits with almost full projjeeje coverage. Empirical results show that our encoding provides more accurate parsers than the existing unbounded bracketing encodings, which had the best previous results among sequence-labeling en- codings, although it underperforms hexatagging.
1 Introduction
Approaches that cast parsing sequence labeling have gathered interest as they are simple, fast (An- derson and Gómez-Rodrígue 2021), highly paral- lelizable (Amini and Cotterell, 2022) and produce outputs that are easy to feed to other tasks (Wang et al., 2019). Their main ingredient are the en- codings that map trees into sequences of one dis- crete label per word. Thus, various such encodings have been proposed both for constituency (Gómez- Rodríguez and Vilares, 2018; Amini and Cotterell, 2022) and dependency parsing (Strzyz al., 2019; Lacroix, 2019; Gómez-Rodríguez et al., 2020). Most such encodings have an unbounded label set, whose cardinality grows with sentence length. An exception for constituent parsing is tetratag- ging (Kitacy and Klein, 2020). For dependency parsing, to our knowledge, no bounded encodings were known. Simultancously to this work, Amini al. (2023) have just proposed one: hexatagging, where projective dependency trees represented by tagging each word with one of set of tags.'
Projective Encoding
Let Tn be a set of unlabeled dependency trees² for sentences of length n. A sequence-labeling encod- ing defines a function 3, Tn L", for label set L. Thus, each tree for sentence wi wn is encoded sequence of labels, I I... lns that assigns label L to each word wy. We define the 4-bil projective encoding as an encoding where T, is the set of projective depen-
used define the labels. However, the label for each word is composed two such atoms (one from a set of two, and other from a set of four) so there are eight possible labels per word. FFor simplicity, we ignore dependency labels in definitions. In the implementation, they are added as separate component to the label of each word, following common practice.
'The "hexa" in the name comes from a set of six atoms

---

dency trees, and we assign to each word w; label
Algorithm 1 To decode right ares in the 4-bit encoding.
4 bybybabs, such that by is a boolean as follows:
I:
function DECODERIGHTARCSS4...
2:
s + empty stack
3:
a f empty set of ares
bo true if w, is a right dependent, and false
4:
s.push(O)
& correpoonding to dummy root
if it is a left dependent. Root nodes are con- sidered right dependents for this purpose (i.c.,
5:
for i 4- to do if SE I; then a.addArc( s.peek( + i)
6:
7:
we assume that they are linked as dependents of a dummy root node wo located to the left).
8:
if E 4 then
9:
s:pop(
10:
end if end if
11:
bj is true iff w; is the outermost right (or left)
12:
if / E then
dependent of its parent node.
13:
s.push(i)
14:
end if
15:
end for
b2 (respectively, bą) is true iff w; has one or more left (right) dependents.
16: return
17:
end function
All combinations of the four bits are possible, so we have 16 possible labels.
created from the same head. Otherwise, we do not pop we expect more ares from the same origin. 3 Intuitively, this lets us generate all the possible non con-crossing combinations of right ares: the stack enforces projectivity (to cover a / label with a de- pendency we need to remove it from the stack, so crossing arcs from inside the covering dependency to its right are not allowed), and the distinction be- tween > with and without allows us to link a new node to any of the previous, non-covered nodes.
For easier visualization and comparison to ex- isting bracketing encodings, we will represent the values of bo as > (right dependent) or < (left depen- dent), b1 as * (true) or blank (false), and b2 and by respectively as \ and / (true) or blank (false). We will use these representations with set notation to make claims about a label's bits, e.g. >* E / means that label I has by 1, bi 1. Figure 1 shows a sample tree encoded with this method.
To decode left ares, we use symmetric algo- rithm DecodeLeftAres (not shown as it is analo- gous), which traverses the labels from right to left, operating on the elements \ and < rather than / and >; with the difference that the stack is not initial- ized with the dummy root node (as the arc origi- nating in it is a right arc). By the same reasoning as above, this algorithm can obtain all the possible non-crossing configurations of left ares, and hence the mapping is injective, The decoding trivially linear-time with respect to sequence length.
We will now show how to encode and decode trees, and prove that the encoding is a total, injec- tive map from projective trees to label sequences.
Encoding and Totality Encoding a tree is trivial: one just needs to traverse each word and apply the definition of each bit to obtain the label. This also means that our encoding from trees to labels is a total function, the labels are well defined for any dependency tree (and thus, for any projective tree).
A sketch of an injectivity proof can be based on showing that the set of right ares generated by Algorithm (and the analogous for left ares) is the only possible one that meets the conditions of the labels and does not have crossing ares (hence, we cannot have two projective trees with the same encoding). To prove this, we can show that at each iteration, the are added by line 7 of Algorithm is the only possible alternative that can lead to a legal projective tree (i.e., that s. peek () is the only possible parent of node i). This is true because (1)
Decoding and Injectivity Assuming a well- formed sequence of labels, we can decode it to a tree. We can partition the ares of any tree t E T, into a subset of left arcs, 4,. and subset of right ares, fr. We will decode these subsets separately. Algorithm shows how to obtain the ares of L,.
The idea of the algorithm is as follows: we read labels from left to right. When we find a label containing /, we know that the corresponding node will be source of one more right ares We push it into the stack. When we find label with >, we know that its node is the target of a right arc, so we link it to the / on top of the stack. Additionally, if the label contains *, the node is rightmost sibling, so we pop the stack because no more ares will be
"Note that, thus, the interpretation of the symbols and > is similar to that of the same symbols in the unbounded bracketing encoding by (Strzyz et al., 2019), but here the / symbol is acting as "superbracket" that matches several opposing brackets (Yli-Iyrä, 2017; Yli-Jyrä, 2019)

---

if we choose a parent to the left of s. s.peek (), then we cover s. peek () with dependency, while has not yet found all of its right dependents (as other- wise it would have been popped from the stack), so a crossing are will be generated later; (2) if we choose parent to the right of s. peek and to the left of i, its label must contain / (otherwise, by def- inition, it could not have right dependents) and not be the stack (as the stack is always ordered from left to right), so must have been removed from the stack due to finding all its right dependents, and adding one more would violate the conditions of the encoding; and finally (3) a parent to the right of i cannot be chosen as the algorithm is only consid- ering right arcs. Together with the analogous proof for the symmetric algorithm, we show injectivity.
42 0000
061183
2000006
0032200
1110000
I0r3000
Figure 2: A non-projective tree and its 7-bit encoding.
skip dependency creation when the stack is empty, ignore material left in the stack after decoding, break cycles and (if we require connectedness) attach any unconnected nodes to a neighbor.
3 Non-Projective Encoding
For wider coverage of non projective dependency trees (including the overwhelming majority of trees found in treebanks), we use the same technique as defined for unbounded brackets in (Strzyz et al., 2020): we partition dependency trees into two sub- sets (planes) of ares (details in Appendix D), and this lets us define 7-bit non-projective encoding by assigning each word wy a label 1 = (bo (b)...b)). where:
Coverage While we have defined and proved this encoding for projective trees, its coverage is ac- tually larger: it can encode any dependency forest (i.e., does not require connectedness) such that ares in the same direction do not cross (i.e., it can han- dle some non projjeeeee structures where arcs only cross in opposite directions, as the process of en- coding and decoding left and right ares is indepen- dent). This is just like in the unbounded bracketing encodings of (Strzyz et al., 2019), but this extra coverage is not very large in practice, and we will define a better non-projective extension later.
bb).
bybb can take values <0 (w, is a left dependent in the first plane), >0 (right dependent in the 1st planc), <1 or >1 (same for the 2nd plane).
b2 is true iff w, is the outermost right (or left) dependent of its parent (regardless of plane). We represent it as * if true or blank if false.
Non-surjectivity Just like other sequence- labeling encodings (Strzyz et al., 2019; Lacroix, 2019; Strzyz et al., 2020, inter alia), ours is not surjective: not every label sequence corresponds to a valid tree, so heuristics are needed to fix cases where the sequence labeling component generates an invalid sequence. This can happen regardless of whether we only consider a tree to be valid if it is projective, mentioned above. For example, a sequence where the last word is marked as a left child (<) is invalid in either case. Trying to decode invalid label sequences will result in trying to pop an empty stack or leaving material in the stack after finishing Algorithm I or its symmetric. In practice, we can
by (respectively, by) is true iff wy has one or more left (right) dependents in the first plane. We denote it as \0 (/0) if true, blank if false.
by and by are analogous to by and b4, but in the second plane, represented as \1 or /1.
we accept the extra coverage
Every 7- combination is possible, leading 128 distinct labels. Figure 2 shows an example of non-proje non-projective tree represented with this encoding.
The encoding is able to cover every possible dependency tree whose are set can be partitioned into two subsets (planes), such that ares with the same direction and plane do not cross.
'If we did not consider a dummy root, we would be able to cover planar trees, rather than just projective trees (as in the bracketing of (Strzyz et al., 2019)), but this would require an extra label for the sentence's ' synlactic root. Instead, we use a dummy root on the left and explicitly encade the are from it to the syntactic root, which is thus labeled as a right child instead of using an extra label. This simplifies the encoding, and the practical difference between the coverage of projectivity and planarity is small (Gómez-Rodrígucz and Nivre, 2013).
This immediately follows from defining the de- coding with set of four algorithms, two for de- coding left and right ares on the first plane (defined as Algorithm and its symmetric, but consider- ing only the symbols making reference to ares in the first plane) and other two identical decoding passes for the second plane. With this, injectivity

---

Treebank
B-2P
4bit
7bit
Treebank
B
B-2P
4bit
7bit
PTB
94.62
92.03
94.72
94.66
PTB
114
599.99
124
100
16
299.99
28
100
Russiancaa
87.84
87.36
88.04
89,58
Russiangso
104
99.76
166 2-59.9
16
99.51
>59.99
Fimnishrpt
92.45
92.37
92.19
92.74
Finnishror
121
99.72
172 299.99
16
99.35
68
249 99
Ane-Greeknewwx
71,84
71.76
67.63
75.36
Greekoveos
95.81
128
Chineseesn
85.23
Chinesecso
101
99.91
152
>49.99
16
99.84
46 >99.99
Hebrowans
90.25
90.21
90.81
90.58
Hehrewers
97
99.98
125
100
16
99:98
100
Tamilyss
63.65
61.68
65.16
68.69
Tamilyr
51
99.94
58
100
16
99.98
22
100
Uyghuruor
67.22
65.49
67.17
69.10
Uygharuer
78
99.43
150
299.99
16
83
58
>49 99
Wolofwir
75.04
74.59
76.24
75.57
Wotofarn
74
99.83
111
249999
16
06
46
249 99
Englishewr
91.03
91.30 30
89.48
91.78
Englishuwr
110
99.88
174
>99 99
16
99.75
63 >99.99
Macro average
81.92
81.12
81.68
83,08
Macro everape
99.43
165.9
59.92
16
58.62
56.2 59.92
Table 2: LAS for the linguistically- test sets
Table I: Number of labels (L) and coverage (C) for each treebank and encoding. B and B-2P are the baselines.
Treebank
B-2P
4bbt
7bit
Relanisianus::
85.21
86.83
56.77
88.23
Galicianneeau
78.32
77.94
81.54
81.22
Lihunnisngss
52.26
49.53
55.56
56.022
is shown in the same way as for the 4-bit encoding. Decoding is still linear-time.
Marathiurst
62.13
55.19
66.50
67.19
Old-Eatt-Slavinee
Welcheco
81.17
80.91
82.31
82,00
Tamilrm
63.65
61.68
65.16
65.69
Note that the set of trees covered by the encoding, described above, is a variant of the set of 2-Planar trees (Yli-Jyrä, 2003; Gómez-Rodrígun and Nivre, 2010), which are trees that can split into two planes such that arcs within the same plane do not cross, regardless of direction. Compared to 2- Planar trees, and just like the encodings in (Strzyz et al., 2020), our set is extended as it allows ares with opposite directions to cross within the same plane. However, it also loses some trees because the dummy root are is also counted when restricting crossings, whereas in 2- 2-Planar trees it is ignored.
Macro average
69.36
67.93
72.40
72.74
Table 3: LAS for the low-resource test sets
as predicted in theory. In particular, the 4-bit en- coding always uses its 16 distinct labels. The 7- encoding only needs its theoretical maximum of 128 labels for the Ancient Greek treebank (the most non- oon-rojectivve one). On average, uses around third as many labels as the 2-planar bracketing encoding, and half as many as the basic bracket- ing. Regarding coverage, the 7-bit encoding covers over 99.9% of arcs, like the 2-planar bracketing. The 4-bit encoding has lower coverage than ba- sic brackets: both cover all projective trees, but they differ coverage of non-projectivity (see Ap- pendix C for an explanation of the reasons). More detailed data (e.g. coverage and label set size for low-resource treebanks) is Appendix A.
4 Experiments
We compare our 4-bit and 7-bit encodings to their unbounded analogs, the bracketing (Strzyz et al., 2019) and 2-planar bracketing encodings (Strzyz et al., 2020) which overall are the best performing in previous work (Muñoz-Ortiz et al., 2021). We use MaChAmp (van der Goot et al., 2021) as a sequence labeling library, with default hyperparam- eters (Appendix B). We use ToB-RoBERTa (Con- neau et al., 2020) followed by two separate one- layered feed-forward networks, one for syntactic labels and another for dependency types. We eval- uate on the Penn Treebank Stanford Dependen- cies 3.3.0 conversion and on UD 2.9: set of saauuisttialll-divessss treebanks taken from (An- derson and Gómez- Rodríguz, 2020), and a low- resource set of 7 (Anderson et al., 2021). We con- sider multiple subsets of treebanks as a single sub- set could be fragile (Alonso-Alon Alonso et al., 2022).
Table 2 shows the models' performance in terms of LAS. The 4-bit encoding has mixed perfor- mance, excelling in highly projective treebanks like the PTB or Hebrew-HTB, but falling behind in non-projective ones like Ancient Greek, which is consistent with the lower non-projective coverage. The b-b encoding, however, does not exhibit this problem (given the almost total are coverage men- tioned above) and it outperforms both baselines for every treebank: the basic bracketing by 1.16 and the 2-planar one by 1.96 LAS points average. If we focus on low-resource corpora (Table 3). label set sparsity is especially relevant so compact-
Table compares the compactness of the encod- ings by showing the number of unique syntactic labels needed to encode the (unlabeled) trees in the training set (i.c. the label set of the first task). The new encodings yield clearly smaller label set sizes,
'In our setup, the basic bracketing encoding baseline beats the 2-planar baseline on average, contrary to the results in the papers that introduced them (cf. (Strzyz et al., 2020)). This likely owes to the architecture used: they used BiLSTMs. whereas we perform our experiments on more competitive architecture with XLM-RRBERTT.

---

ness further boosts accuracy, The new encodings obtain large improvements. the 7- one surpassing the best baseline by over average LAS points.
Treebank
4-bit
7-bit
64g
Mg-s
4-bit-s
7-bit-s
biafline
PTB
94.72
94.66
96.13
96.04
94.92
94.88
95.32
Russiancaa
68.04
89.58
91.83
90.95
88.78
90.18
90.17
Famnishrot
92.19
92.74
94.12
92.66
92.11
93.10
93.33
Ane-Greee
67.63
75.36
73.12
72.78
68.02
76.
79.81
Chinesersn
Hebrowins
90.81
90.58
92.82
91.27
90.81
91.05
91.88
4.1 Additional results: splitting bits and external parsers
Tamilyrs
65.16
65.69
78.33
76.32
66.99
67.19
67.52
Lygharupr
67.17
69.10
71.11
65.23
67.55
69.13
72.33
Wolofwrr
76.24
75.57
76,04
72.11
76.85
76.24
76.73
Englishswt
89.48
91.78
92.62
90.06
89 48
92.15
92.72
We perform additional experiments to test imple- mentation variants of our encodings, as well as to put our results into context with respect to non- sequence-labeling parsers and simultaneous work. In the previous tables, both for the 4-bit and 7-bit experiments, all bits were predicted as a single, atomic task. We contrast this with a multi-task version where we split certain groups of bits to be predicted separately. We only explore a pre- liminary division of bits. For the 4-bit encoding, instead of predicting label of the form the model predicts two labels of the form bybj and beby, respectively. We call this method 4-bit-s. For the 7-bit encoding, decided to predict the bits corresponding to each plane as a separate task, i.e.. bybybyby and bybghg. We call this method 7-bit-s. We acknowledge that other divisions could be bet- ter. However, this falls outside the scope of this paper.
Macro
81.68
83.08
85.35
83.47
82.15
83.62
84.85
Table 4: LAS comparison against related parsers, for the linguistically- test sets,
Treebank
4bit
7bi
4bil-s
Thit-s
biafline
Delarusianes:
86.77
88.23
89.14
89.01
87.01
88.52
93.83
Golicianeasia
81.54
81.22
82.03
81.94
81.97
81.31
86.81
Lichuaniatae
55.56
56.02
64.47
64.74
55.97
57.31
56.75
Maradignar.
66.50
67.19
75.00
74,66
66.92
67.57
61.22
Old-Fas--Slavieee
68.96
71.37
72.06
Watsheos
82.31
82.00
87.05
86.92
82.62
82.13
85 05
Tamilyra
65.16
78.33
77.91
65.
65.82
76.12
Macro average
72,40
72.74
78.19
78.07
72.68
73.07
75.97
Table 5: LAS comparison against related parsers, for the low-resource test sets.
beneficial, perhaps because the structure of the en- coding in bits with independent meanings naturally lends itself to multi-task learning). Second, on average, the best (multi-rask) version of our 7-bit encoding is about 1.7 points behind the 6tg and 1.2 behind biaffine state-of-the-art parsers in terms of LAS. However, the difference between versions with and without multi-task learning suggests that there might be room for improvement by investi- gating different splitting techniques. Additionally, in Appendix F, Table 14 compares the process- ing speeds of these parsers (on a single CPU). Appendix G, Tables 15 and 16 show how often heuristics are applied in decoding.
We additionally compare our results with other relevant models. As mentioned earlier, alongside this work, Amini et al. (2023) introduced a parsing- as-tagging method called hexatagging. In what follows, we abbreviate this method as 6tg. We implement 6tg under the same framework as our encodings for homogeneous comparison, and we predict these hexatags through two separate linear layers, one to predict the are representation and another for the dependency type. We also consider a split version, 6tg-s, where the two components of the are representation are predicted separately. For a better understanding of their method, we refer the reader to Amini et al. and Appendix F. Finally, we include a comparison against the biaffine graph- based parser by Dozat et al. (2017). For this, we trained the implementation in SuPar using xlm- roberta- large the encoder, which is often taken strong upper bound baseline.
Finally, Table 5 shows the external comparison on the low-resource treebanks, where our encod- ings lag further behind biaffine and especially 6tg. which surpasses 7-bit-s by over 5 points.
Conclusion
We have presented two new bracketing encod- ings for dependency parsing as sequence label- ing, which use a bounded number of labels. The 4-bit encoding, designed for projective trees, ex- cels in projective treebanks and low-resource se- tups. The 7-bit encoding, designed to accom- modate non-projectivity, clearly outperforms the best prior sequence-labeling encodings across a diverse set of treebanks. The source code is available at https:/ / /gi thub. com/Polifack/ CoDeLin/releases/tee wtteeeeessssee/ee///eeaa /1. 25.
Table 4 compares the performance of external parsers with our bit encodings. First, the results show that the choice of whether to split labels into components or not has considerable influence, both for 6tg (where splitting is harmful across the board) and for our encodings (where it is mostly
Chttps://gittae hatt:s///gthhuu...myyyagg/////se comryyaaaagcsppprsrrrrrr

---

Limitations
parsing evaluation. In Proceedings of the 29th Inter- national Conference on Computational Linguistics. pages 5345-5359, Gyeongju, Republic of Korea. In- ternttional Committee on Computational Linguistics.
In our experiments, we do not perform any hy- perparameter optimization or other task-specific tweaks to try to bring the raw accuracy figures as close as possible to state of the art. This is for sev- eral reasons: (1) limited resources, (2) the paper having a mainly theoretical focus, with the exper- iments serving to demonstrate that our encodings are useful when compared to alternatives (the base- lines) rather than chasing state-of-the-art accuracy. and (3) because believe that one of the primary advantages of parsing as sequence labeling is its ease of use for practitioners, as one can perform parsing with any off-the-shelf sequence labeling library, and our results directly reflect this kind of usage. We note that, even under such a setup, raw accuracies are remarkably good.
Afra Amini and Ryan Cotterell. 2022. On parsing as tagging. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 8884-8900, Abu Dhabi, United Arab Emirates. Association for Computational Linguisties.
Afra Amini, Tianyu I Liu, and Ryan Cotterell. 2023. Hex- atagging: Projective dependency parsing as tagging. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 1453-1464, Toronto, Canada. Association for Computational Linguistics.
Mark Anderson, Mathieu Dehouck, and Carlos Gómez- Rodríguez. 2021. A falta de pan. buenas tortas: The efficacy of predicted UPOS tags for low resource UD parsing. In Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Univer- sal Dependencies (IWP'I 2021), pages 78 83, Online. Association for Computational Linguisties.
Ethics Statement
This is a primarily theoretical paper that presents new encodings for the well-known task of depen- dency parsing. We conduct experiments with the sole purpose of evaluating the new encodings, and we use aublicly-available standard datasets that have long been in wide use among the NLP com- munity. Hence, we do not think this paper raises any ethical concern.
Mark Anderson and Carlos Distilling neural networks for greener and faster de- pendeney parsing. In Proceedings of the 16th Inter- national Conference on Parsing Technologies and the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies, pages 2-13, Online, Asso- ciation for Computational Linguisties.
2020.
Mark Anderson and Carlos Gómez- Rodriggz. 2021. A modest Pareto optimisation analysis of dependency parsers in 2021. In Proceedings of the 17th Interna- tional Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (IWPT 2021), pages 1 119- 130, Online. Association for Computational Linguis- tics.
Acknowledgments
This work has received funding by the Eu- ropean Research Council (ERC), under the Horizon Europe research and innovation pro- gramme (SALSA, grant agreement No 101 100615), ERDF/MICINN- (SCANNER-UDC, PID2020- L13230RB-C2I), Xunta de Galicia (ED43IC 2020/11), Grant GAP (PID2022-13990000A) funded by MCIN/AEI/1O, 1 13039/501 10001 1033/ and by ERDF "A way of making Europe", and Cen- tro de Investigación de Galicia "CITIC", funded by the Xunta de Galicia through the collaboration agreement between the Consellería de Cultura, Ed- ucación, Formación Profesional e Universidades and the Galician universities for the reinforcement of the research centres of the Galician University System (CIGUS).
Alexis Conneau, Kartikay Khandelwal. Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettle- moyer, and Veselin Stoyanov. 2020. Unsupervised cross-lingual representation learning at scale. In Pro- ceedings of the 58th Annual Meeting of the Asso- ciation for Computational Linguistics, pages 8440- 8451, Online. Association for Computational Lin- guistics.
Timothy Dozat, Peng Qi, and Christopher D. Manning. 2017. Stanford's graph-based neural dependency parser at the CoNLL 2017 shared task. In Proceed- ings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 20-30, Vancouver, Canada. Association for Computational Linguistics.
References
Carlos
and Joakim Nivre. 2010. A transition- parser for 2-planar dependency struc- tures. In Proceedings of the 48th Annual Meeting of
Iago Alonso-Alonso, David Vilares, and Carlos Gómez- Rodríguez. 2022. The fragility of multi-treehank

---

the Association for Computational Linguistics, pages 1492-1501, Uppsala, Sweden. Association for Com- putational Linguisties.
Conference the European Chapter of the Associa- tion for Computational Linguisties: System Demon- strations, pages 176-197, Online. Association for Computational Linguistics.
Carlos Gómez-RRddriguzz and Joakim Nivre. 2013. Divisible transition systems and multiplanar de- pendency parsing. Computational Linguistics, 39(4)7799-85.
Yufei Wang, Mark Johnson, Stephen Wan, Yifang Sun, and Wei Wang. 2019. How to best use syntax in semantic role labelling. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5338-5343, Florence, Italy. Asso- ciation for Computational Linguistics.
Carlos Komez-Rodrriuuez Michalina Strzyz, and David Vilares. 2020. A unifying theory of transition-bee based and sequence labeling parsing. In Proceedings of the 28th International Conference on Computational Linguistics, pages 3776-3793, Barcelona, Spain (On- line). International Committee Computational Lin- guistics.
Anssi Yli-Jyrä. 2017. Bounded-depth high-coverage search space for noncrossing parses. In Proceed- ings of the 13th International Conference on Finite State Methods and Natural Language Processing (FSMNLP 2017), pages 30-40, Umeå, Sweden. As- sociation for Computational Linguistics.
Carlos Gódez-Rodríguez and David Vilares. 2018. Constituent parsing as sequence labeling. In Proceed- ings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1314-1324, Brussels, Belgium. Association for Computational Linguistics.
Anssi Mikael Yli-Jyrä. 2003. Multiplanarity model for dependency structures treebanks. In TLT 2003. Proceedings of the Second Workshop on Treebanks and Linguistic Theories, volume 9 of Mathemati- cal Modelling in Physics, Engineering and Cognitive Sciences, pages 189-200, Växjö, Sweden. Växjö Uni- versity Press.
Nikita Kitaev and Dan Klein. 2020. Tetra-tagging: Word-synchronous parsing with linear-time inference. In Proceedings of the 58th Annual Meeting of the As- sociation for Computational Linguistics, pages 6255- 6261, Online. Association for Computational Lin- guistics.
Anssi Mikael Yli-Jyrä. 2019. How embed noncross- ing trees in universal dependencies treebanks in a low-complexity regular language. Journal of Lan- guage Modelling, 172):177-232.
Ophélic Lacroix. 2019. Dependency parsing as se- quence labeling with head- bead-based encoding and multi- task learning. In Proceedings of the Fifih Inter- national Conference on Dependency Linguistics (Depling. SyntaxFest 2019), pages 136-143, Paris, France. Association for Computational Linguistics.
A Further Data
Tables 6 and 7 show treebank statistics for the gen- eral and low- low-resource set of treebanks, respectively.
Alberto Muñoz-Orte Michalina Strzyz, and David Vi- lares. 2021. Not all linearizations are equally data- hungry in sequence labeling parsing. In Proceed- ings of the International Conference on Recent Ad- vances in Natural Language Processing (RANLP 2021), pages 978-988, Held Online. INCOMA Ltd.
Treebank
projective
1-planar
raacs
avg d
PTB
89.89%
59.83%
48.74%
2.295
Russiancao
93.87%
93.89%
49.03%
2.263
Pinnishypr
93.85%
93.88%
52 52.88%
2.365
Ane Greeknvone
37.66%
37.67%
52.81%
Chinesecsp
97. 75.75%
97.87%
63 63.67%
2.440
Hchrewere
96.26%
96.28%
49.21%
2.242
Tamilyrn
98.33%
98 93%
68.56%
2.262
Uyghuruor 95.02%
96.03%
64.31%
2,140
Wolofwrr
07.01%
97. 17%
48 21%
2.519
Michalina Strzyz, David Vilares, and Carlos Gómez- Rodríguez. 2019. Viable dependency parsing as se- quence labeling. In Proceedings of the 2019 Con- ference of the North American Chapter of the Asso- ciation for Computational Linguistics: Human Lan- guage Technologies, Volume 1 (Long and Short Pa- pers), pages 717-723, Minneapolis, Minnesota. As- sociation for Computational Linguistics.
Englishewr 97.47%
97.63%
57.18%
2.525
Table 6: Statistics for the pegguistiiclly--ivver set of
treebanks: percentage of projective trees, 1-planar trees, percentage of rightward arcs (r ares), and average de- pendency distance (avg d).
Treehank
projective
1-plonar
rares
avg
Michalina Strzyz, David Vilares, and Carlos Gómez- Rodríguez. 2020. Bracketing encodings for 2-planar dependency parsing. In Proceedings of the 28th Inter- national Conference on Computational Linguistics, pages 2472- 2484, Barcelona. Spain (Online). Inter- national Committee on Computational Linguistics.
Belarusiangs:
94 94.92%
95, 22%
46.92%
2.252
wal
$9.20%
53.02%
2.530
Lithunniangse
85.93%
86.69%
58.40%
2.321
Slaviaac
66.35%
Marathirraa
95 9255
96.35%
50.8%%
2.362
Welshees
98.24%
98.24%
43,948
2.324
Tamilyrs
98.33%
98.33%
68.56%
2.262
Table 7: Statistics for the low-resource set of treebanks: percentage of projective trees, 1-planar trees, percent- age of rightward ares (r arcs), and average dependency distance (avg d).
Rob van der Goot, Ahmet Üstün, Alan Ramponi, Ibrahim Sharaf, and Barbara Plank. 2021. Massive choice, ample tasks (MaChAmp): A toolkit for multi- task learning in NLP. In Proceedings of the 16th

---

Table shows the number of labels and the are coverage of each considered encoding for the low- resource treebank set of Anderson et al. (2021), in the same notation as in Table I. As can be seen in the table, the trends are analogous to those for the other treebanks (Table in the main text).
Treebank
B
B-2P
4bit
7bit
PTB
1316
1233
396
Russiangso
802
961
400
614
Finnishrpr
Ane Creekrenee
1469
2401
304
1167
Chinesecsu
321
Hehrewarm
754
798
317
357
Tumilrra
262
274
153
164
Uypharupr
553
683
353
WolofoTr
585
643
318
382
Englishawr
487
Mazro avernge
858.8
1040.9
348.4
536.7
Treebank
B-2P
4bit
7bil
1.
C
I.
C
C
C
Belarusianuse
133 99.53
228
>99.99
99.46
299.99
Table 11: Unique labels generated when encoding the
Galician
79 99.51
129
>99.99
16
99.52
60)
209199
training sets of the linguistically-dives set of treebanks,
Libuaniangse
98.82
Marathiueat
46 99.44
58
100
16 99.32
36
100
including dependency types as a component the la- bels.
Old-Rast-Slavieee
230
99.94
97.46
Welshen
53
99.90
71
100
99.93
100
Trm
99.82
58
100
99.84
100
Macro average
80.0
99.25
122.6
59.99
16
99.19
55.7
99.99
Trechank
B
R-2P
4bit
7blt
Belarusiamese
1136
1479
477
926
Table 8: Number of labels (L) and are coverage (C) for each low-resource treebank and encoding. and B-2P are the baselines.
Galician
Lithuanianase
398
432
256
306
Old-Eas Old-Eart-
910
1181
378
715
MarathiupAA
275
197
223
Webbhee
474
514
265
312
Tamilyrs
153
Macro average
566.7
681.7
285.1
431.7
Tables 9 and 10 show the coverage of the en- codings in terms of full trees, rather than ares (i.e., what percentage of the dependency trees in each treebank can be fully encoded and decoded back by each of the encodings).
Table 12: Unique labels generated when encoding the training sets of the low-resource set of treebanks, includ- ing dependency types as component of the labels.
B Hyperparameters
Treebank
B
B-2P
4bit
7bit
PTR
>59 99%
-599.99%
1007%
Russimeen
96, 96.94%
99.92%
95.65%
99.92%
We did perform hyperparameter search, but just
Pinnishror
99.43%
100%
99.35%
100%
Anc Greekipoess
72.25%
90.63%
50.48%
90.63%
used MaChAmp's defaults, which can be seen
100%
Hebreware
98. 201
99.89%
97.200
99.89%
Table 13.
Tamilrr
99.50%
100%
Uyghurave
97.80%
100%
97.19%
100%
Wolefwn
97.86%
99.95%
97.25%
99.95
Parameter
Value
Poglishewr
98.73%
99.98%
18%
99.98%
dropout
0.1
Maero average
96.01%
93.25%
0970
max imput length
128
Table 9: Full tree coverage for each encoding on the Inguussically-diverse set of treebanks.
batch size
8
training epochs
50
optimizer
adam
learning rate
0.0001
Treebank
B
B-2P
4bit
Thit
Belarusianus:
96.36%
99.95%
96.12%
99.95%
weight decay
0.01
Galicianpsttal
92.90%
99.80%
92.60%
99.80%
Libhuaiiaese
88.97%
99.62%
Old-Fact-Slavicee
72.15%
97.75%
72.05%
97.75%
Table 13: Hyperparameter settings
Marathioraa
97.63%
100%
97.42%
100%
Welsboco
58%
100%
98.88%
100%
Tamilyra
99.50%
100%
98.67%
100%
Macro average
92.34%
99.59%
92.12%
99.59%
C Coverage Differences
Table 10: Full tree coverage for each encoding on the low-resource set of treebanks.
is worth noting that, while the 7-bit encoding has exactly the same coverage as the 2-planar brack- eting encoding (see Tables 1, 8, 9, 10); the 4-bit encoding has less coverage than the basic bracket- ing. As mentioned in the main text, both have full coverage of projective trees, but there are subtle differences in how they behave when they are ap- plied to non-projective trees. We did not enumerate all of these differences in detail for space reasons. In particular, they are the following:
Tables 11 and 12 show the total number of labels needed to encode the training set for each encod- ing and treebank, when considering full labels (i.e., the number of combinations of syntactic labels and dependency type labels). This can be relevant for implementations that generate such combinations as atomic labels (in our implementation, label com- ponents are generated separately instead).

---

Contrary basic bracketing, the 4-bit encod- ing needs encode the are originating from the dummy root explicitly. This means that cannot encode non-pros non-projective, but planar trees where the dummy root are crosses a right are (or equivalently, the syntactic root is covered by right arc).
the following way: forbid plane p for the ares that cross a (its neighbors in the crossings graph), we forbid the other plane (x/) for the neighbors of its neighbors, plane for the neighbors those, and so on.
Plane assignment made by traversing arcs. For each new are a, we look at the restric- tions and assign it to the first plane allowed, otherwise to the second plane if allowed, and finally to plane if none is allowed (for non- 2-planar structures).
In the basic bracketing, a dependency involv- ing words Wi and wi (i < j) is not encoded in the labels of wy and uy, but in the labels of 1 and Wj (see (Strzyz et al., 2019)), as technique to alleviate sparsity (in the par- ticular case of that encoding, it guarantees that the worst-case number of labels linear, rather than quadratic, with respect to sentence length). In the 2-planar, 4- and 7-bit encod- ings, this is unneeded so dependencies are en- coded directly in the labels of the intervening words.
E
Hexatagging
Amini et al. (2023) use an intermediate representa- tion, called binary head trees, that acts as proxy between dependency trees and hexatags. These trees have structure akin to binary constituent trees in order to apply the tetra-tagging encoding (Kitaev and Klein, 2020). In addition, non-terminal intermediate nodes are labeled with 'L' 'R' based on whether the head of the constituent on its left or right subtree. We direct the reader to the pa- per for specifics. However, a mapping between projective dependency trees and this structure can be achieved by starting at the sentence's 's root and conducting depth-firs first traversal of the tree. The representation components for cach hexatag encode: (i) the original label corresponding the tetratag, and (ii) the value of the non-terminal sym- bol in the binary head tree.
Contrary to basic bracketing, in the 4-bit en- coding a single / or \ element is shared by several arcs. Thus, if an arc cannot be suc- cessfully encoded due to unsupported non- projectivity, the problem can propagate to sib- ling dependencies. In other words, due to being more compact, the 4-bit encoding has less redundancy than basic bracketing.
Plane Assignment
The 2-planar and 7-bit encodings need a strategy to partition trees into two planes. We used the second-plane-averss strategy based on restriction propagation on the crossings graph (Strzyz al., 2020). It can be summarized follows:
Speed comparison
Table 14 compares the speed of the models over an execution single CPU.? It is important to note that while SuPar is optimized parser, in this context, we used MaChAmp as a general sequence labeling framework without specific optimization for speed. With a more optimized model, practical processing speeds in the range of 100 sentences per second on CPU or 1000 on a consumer-gras -rrade GPU should be achievable (cf. the figures for sequence- labeling parsing implementations in (Anderson and Gómez Rodríguz, 2021))-
1. The crossings graph is defined as an undi- rected graph where each node corresponds to an are in the dependency tree, and there is an edge between nodes a and b if are crosses are b in the dependency tree.
2. Initially, both planes are marked as allowed for every are in the dependency tree.
3. The ares are visited in the order of their right endpoint, moving from left to right. Priority is given to shorter ares if they have a com- mon right endpoint. Once sorted, we iterate through the arcs.
G Non-Surjectivity in Decoding
As mentioned in the main text, all encodings ex- plored in this paper are non-surjective, meaning that there are label sequences that do not corre- spond to valid tree. In these cases, the labels
4. Whenever we assign an are a to a given plane p. we immediately propagate restrictions in
(Inte((R) Core(TM) 19-10920X CPU @ 3.50GHz.

---

Treebank
biaftine
4bit
7bit
Paan-Treebank
28.34
14.65
14.28
14:42
UD- Rursian-GSDD
25.15
14.27
14.63
14.30
FD--innish:
UD Ancient Creek Perseus
24.12
12.53
12.93
12.15
UD-Chinese-GSD
UD-Hehrew HTB
27.06
13.46
13.15
13.71
UD- Tami-aiill-n Tumil-TTB
29.19
11.98
12.17
12.67
UD-UUyhhu--UDT
18.01
18.93
UD: Wolef WTF
28.14
12.61
12.31
12.61
UD-Engllih--EN
Table 14: Speed (sentences per second) for the
linguistically-diver test sets.
Treehank
6gg
4-bit
7-hit
401%
43%
Russimeso
14.42%
19.34%
16.57%
Finnishype
3.75%
10.01%
8.84%
Anc Greeknaars
12.66%
20.08%
18.81%
22.065%
HebrewaTH
10.82%
16.76%
16. 79%
Tamilern
29.06%
36.12%
37.67%
Uyghurcuzz
18.1
22.19%
52%
WolofUrE
30.01%
42.15%
50.54 54%
Rnglishewr 401%
6.48%
Macro average
13022
20.92%
20.025
Table 15:
Percentage of in the linguistically- diverse test sets where the label sequence output by the tagger does not correspond ties need to be applied to deal with unconnected nodes, cycles or out-of-bounde indexes.
valid tree, and heuris-
are decoded using simple heuristics (c.g. skipping dependency creation if the stack is empty, ignoring material remaining in the stack after decoding, at- taching unconnected nodes and breaking cycles). Table 15 shows data about the number of trees in the test set such that the labels output by the tagger do not directly correspond to valid tree, and at least one of these heuristics has to be applied. Ta- ble 16 shows the same information in terms of the percentage of dependency ares that are affected by said heuristics.
Treebank
6g
4-bit
7-bit
PTB
0.531%
0.941%
0.566%
Russiancnn
0.930%
1479%
1.200%
Finniskune
0.291
0.987%
0.780%
Anc-Greskyesen
2.291%
Chineseesp
0,705%
1.622%
1.593%
Hebrewarn
Tamilyre
2,728%
3.819%
4.280%
Uyghun
2,052%
2.801%
2.191%
Wolnfwrr
1.853%
3.043%
3.868%
Englishewt
0.554
1.523%
0.726%
Macro averago
1.075%
1.947%
1.807%
Table 16:
Percentage of dependency arcs in the linguistically-dveer diverss sets where heuristics need to be applied to deal with unconnected nodes, cycles or out-of- out-of-bounds indexes.


Reviews:
[{"review_id": "FNwp4pFmQ6", "reviewer": "Reviewer_SmyL", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and useful suggestions. We plan to address them with the extra page which is provided if the paper is accepted, and will improve the paper:\n- Comparison to other types of dependency parsers, such as biaffine: we will include this in the camera-ready version if accepted, including also speed comparison.\n- Typo: will be fixed.\n- Statistics on non-surjectivity (cases where the input does not map to a valid tree and heuristics are needed): we think this is interesting and we will gather and include them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Parsing as tagging is a very promising technique for fast dependency parsing. This paper introduces a highly-intuitive and yet small and bounded label set that uses only 4 bits to label each word in a sentence. This label set is slightly larger than the 3-bit label set proposed by Amini et al. (2023), but is arguable more intuitive and native to describing dependency trees. The corresponding decoding algorithm is also easy to understand and seems straightforward to implement.\n* In addition to the 4-bit label set targeting at projective trees, the paper further introduces a 7-bit extension that covers 2-Planar non-projective trees which has over 99% empirical coverage on all tested treebanks (including Ancient Greek, which is highly non-projective).\n* The empirical results are quite promising. The parsers using the proposed 7-bit label set outperforms the baseline label sets by a wide margin. \n* The paper is quite well-written and very easy to follow. I especially appreciate the explanation on coverage (why the 4-bit label set works beyond projective trees, though designed for projective coverage).", "reasons_to_reject": "I don't see any strong reasons.\n\nA minor reason: the paper doesn't include comparisons with other types of dependency parsers (e.g,. the popular biaffine parser), so it is unclear whether the proposed approach performs lacks in accuracy as compared to those. It would also be helpful to include parsing speed comparisons, since fast inference should be a major selling point for parsing-as-tagging approaches. Though given the theoretical focus of this paper, I consider this point to be minor.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper proposes two novel labeling schemes for dependency parsing. With these label sets, parsing can be casted as a sequence labeling task. The first label set uses 4 bits per word describing whether the word is a left or right dependent, whether it is an outmost dependent, and whether the word has left or right dependents. The paper further proposes a 7-bit extension set that expands the coverage to 2-Planar non-projective trees. Experiments show that the proposed label sets support good coverage on a diverse set of treebanks, and higher parsing LAS scores than baseline labeling schemes.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "I recommend including speed comparisons with popular parsers, since this could be a major advantage of using parsing-as-tagging approaches.\n\nLine 066, I recommend changing b_i to b_j, since the index i has been used to describe word w_i.\n\nThe end of section 2 talks about what happens when the label set cannot be mapped to a valid tree. It would be interesting to include some statistics on how often this happens in empirical parsing experiments."}}, {"review_id": "wbu7ZhpVH6", "reviewer": "Reviewer_U1jy", "summary": "", "questions": "- I think the tree in Figure 2 can be parsed with the 4-bit schema and we do not necessarily **need** the 7-bit schema. Is that right? If yes, it would be helpful for the reader to replace that with an example that we actually need the 7-bit schema.\n- The plane assignment is not really understandable given only the context in section 3. Could you elaborate more on this point? ", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and useful suggestions. \n\nResponses to the reasons to reject (RR) and questions (Q):\n\n- RR1: As you mention, we perform greedy decoding and heuristically resolve cases where the sequence of tags does not directly map to a tree. We were especially interested in this case because it allows the user to use any off-the-shelf sequence labeling library without any special adjustments, and change such library without effort if e.g. better ones come out. We think this is interesting for practitioners and to make parsing more broadly applicable (this is mentioned briefly in the limitations section). However, the problem of designing a task-specific decoding algorithm that will take the properties of the problem into account to find the maximum-scoring tag sequence that corresponds to a valid tree is also very interesting, both from a theoretical point of view and to really squeeze the maximum possible accuracy from the framework, and we would like to tackle it in future work.\n- RR2: Yes, we believe this is a useful improvement to the paper and will provide the statistics in the extra page if the paper is accepted.\n- RR3: We will include this comparison with a state-of-the-art biaffine parser in the final version.\n- RR4: Indeed, the work was simultaneous. But we also thought that this would be interesting, so we had already started implementing hexatagging under the same framework as our encodings (for homogenous comparison) and hope to have the results ready to provide this comparison for the camera-ready version.\n- Q1: Yes, this is true – since the arcs that cross in the example are in opposite directions, the 4-bit encoding would suffice even if the tree is not projective. We will replace it with an example that really needs the 7-bit encoding.\n- Q2: In short, the plane assignment strategy that we used to partition arcs into planes for training works as follows (we will provide an explanation in the final version if the paper is accepted, and will extend the explanations of 2-planarity-related concepts in general): \n  1. The crossings graph is defined as an undirected graph where each node corresponds to an arc in the dependency tree, and there is an edge between nodes *a* and *b* if arc *a* crosses arc *b* in the dependency tree.\n  2. Initially, both planes are marked as allowed for every arc in the dependency tree.\n  3. Whenever we assign an arc a to a given plane *p*, we immediately propagate restrictions in the following way: we forbid plane *p* for the arcs that cross *a* (its neighbors in the crossings graph), we forbid the other plane (*p'*) for the neighbors of its neighbors, plane *p* for the neighbors of those, and so on.\n  4. Plane assignment is made by traversing arcs. For each new arc *a*, we look at the restrictions and assign it to the first plane if allowed, otherwise to the second plane if allowed, and finally to no plane if none is allowed (for non-2-planar structures).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper is very well written, and the proposed encoding of dependency trees to a sequence of tags is intuitive and easy to understand. Furthermore, their approach is arguably more interpretable than Hexatagging, as the tags directly correspond to the structure of the dependency tree (and not some intermediate constituency structure). The approach presented in the paper can also be generalized to parse non-projective trees.  ", "reasons_to_reject": "- If I understand correctly, at inference time the authors do greedy decoding and heuristically resolve cases where the outputted tag sequence is not valid. I am wondering if it would be possible to modify the decoding algorithm to find the maximum scoring tag sequence which is also a valid one (that can cost extra compute of course). \n- On the same note, the consequence of non-surjectivity on performance is not discussed in the paper. Can you provide some statistics on how many of the tags result in decoding errors and how this affects the overall performance of the parser?\n- It seems necessary to compare the performance to the state-of-the-art parser as a point of reference. The two baselines provided are both taggers.\n- [suggestion]: I understand that this work was probably done parallel to Hexatagging, but it would be helpful for practitioners if the authors could compare their method to Hexatagging for the camera-ready version.\n\n", "questions_to_authors": "- I think the tree in Figure 2 can be parsed with the 4-bit schema and we do not necessarily **need** the 7-bit schema. Is that right? If yes, it would be helpful for the reader to replace that with an example that we actually need the 7-bit schema.\n- The plane assignment is not really understandable given only the context in section 3. Could you elaborate more on this point? ", "paper_topic_and_main_contributions": "This paper offers a new approach for dependency parsing as tagging. The linearization results in 16 distinct tags for parsing projective trees and can be extended to 128 tags for parsing non-projective trees. The paper offers linear time algorithms to convert dependency trees to tags and tags to dependency trees. Comparison to 2 baselines (based on previous taggers with unbounded tag-set size) shows that their tagger achieves a very good performance while having a bounded tag set.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "whATD8Z1qX", "reviewer": "Reviewer_JxDe", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and suggestions to improve the paper. If the paper is accepted, it should be easy to address them with the extra page provided:\n- Speed and accuracy comparison with graph-based approaches: we agree that this is a useful addition and will include it.\n- Introduction to 2-planar trees: we agree that it can be difficult to understand without looking at the references in its current form. For space reasons, we were not able to provide more explanation in the 4-page version for submission. But with the extra page in the camera-ready version, we will expand the explanation and we believe it should be easy to follow, as these concepts are not very long or difficult to explain.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The proposed encoding scheme is interesting, much simpler than prior bracketing-based sequence labeling approach, yet obtaining better performance", "reasons_to_reject": "No major concerns were identified during the review. However, there are some minor concerns:\n\n- The proposed method is not surjective and requires heuristics during decoding.\n- The paper lacks a comparison of speed and performance with other state-of-the-art graph-based approaches, although this limitation is acknowledged in the limitations section.\n- In terms of presentation, it would be beneficial to include a brief introduction to 2-planar trees. Many readers, including myself, might not be familiar with this type of trees. As a result, understanding the heuristic decoding strategy in the 4-bit case through the use of a stack is clear. However, for the 8-bit case, it is not immediately evident, and additional clarification might be helpful.\n\n\n\n\n\n\n\n\n", "questions_to_authors": "", "paper_topic_and_main_contributions": "In this short paper, the authors investigated sequence labeling-based dependency parsers. They proposed innovative schemes to encode projective and 2-planar trees using 4 bits (i.e., 16 labels) and 7 bits (i.e., 128 labels), respectively. Evaluation on multilingual treebank data demonstrated the effectiveness of their approach.\n\n\n\n\n", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": " "}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a 4-bit labeling scheme for projective dependency parsing as sequence labeling and extends it to a 7-bit labeling scheme for non-projective dependency parsing.

All the reviewers are positive, believing that the proposed scheme is simpler and more intuitive than previous schemes, the experimental results are good, and the paper is well-written. They also provide some suggestions for improving the paper, e.g., comparison of speed, comparison with other types of parsers, and clarification of section 3, which the authors have promised to address in the camera-ready.
Decision: Accept-Main