Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective
Authors: Tianyu Liu
Afra Amini
Mrinmaya Sachan
Ryan Cotterell
Venue: EMNLP 2023 Main (2023)
Keywords: structured prediction
dependency parsing
coreference resolution
TL;DR: We show that most structured prediction problems in NLP can be solved in linear time and space by considering them as partial orderings of the tokens in the input string.

Abstract: Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language.
Such tasks, in general, require exhaustive pair-wise comparisons of tokens, thus having a quadratic runtime complexity in the length of the string.
We show that these exhaustive comparisons can be avoided, and, moreover, the complexity of such tasks can be reduced to linear by casting the relation between tokens as a partial order over the string.
Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
Each total order implies a set of arcs oriented from smaller to greater tokens, sorted by their predicted numbers.
The intersection of total orders results in a partial order over the set of tokens in the string, which is then decoded into a directed graph representing the desired linguistic structure.
Our experiments on dependency parsing and coreference resolution show that our method achieves state-of-the-art or comparable performance.
Moreover, the linear complexity and parallelism of our method double the speed of graph-based coreference resolution models, and bring a 10-times speed-up over graph-based dependency parsers.

Linear-Time Modeling of Linguistic Structure:
An Order-Theoretic Perspective
Tianyu Liu
Afra Amini
Mrinmaya Sachan
Ryan Cotterell
Itianyu.liu, afra. amini, mrinmaya. sachan, ryan.cotterell eine.e...chie....c.
ETHzüria
Abstract
dependency parsing, semantic parsing, and coref- erence resolution. These tasks involve predicting complex and hicrarchical output structures, making them inherently more challenging than their clas- sification or regression counterparts. This paper contributes a novel and generic framework for structured prediction with empirical evidence from dependency parsing and coreference resolution.
Tasks that model the relation between pairs of tokens in string are vital part of understand- ing natural language. Such tasks, general, require exhaustive pair-wise comparisons of tokens, thus having a quadratic runtime complexity the length of the string. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity of such tasks can be reduced to linear by casting the relation between tokens partial order over the string. Our method predicts real numbers for each token string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens the string. Each total order implics set of ares oriented from smaller to greater tokens, sorted by their predicted numbers. The intersection total orders results in partial order over the set tokens the string, which is then decoded into directed graph representing the desired linguistic structure. Our experiments on dependency parsing and coreference resolution show that method achieves state-of-the-art or comparable performance. Moreover, the linear complexity and parallelism of our method double the speed of graph- based coref- erence resolution models, and bring 10-times speed-up up over graph-based dependency parsers.
Many machine learning models for structured prediction score and predict graphs (McDonald et al., 2005; McDonald and Pereira, 2006), in which the vertices represent the tokens in the string and the edges represent the relations between them. One common strategy to model a graph is to de- compose it into smaller subgraphs that are tractable (Taskar et al., 2004; Smith, 2011, $2.2). For example, arc-factored models (Eisner, 1996) score graph only using the score of each constituent edge. However, even with such simplification, the computational costs of arc-factored models are superlinear. The reason is that one needs to exhaus- tively compute scores for all possible edges the graph, which, in general, requires at least quadratic number of computations with respect to the length of the string. Another common strategy employs weighted transition-basee systems (Knuth, 1965; Yamada and Matsumoto, 2003; Nivre, 2003). They decompose structures into transitions between intermediate model states and do offer linear-time algorithms. However, in general, predicting the transitions between states cannot be parallelized, which is another worrying limitation. The authors of this paper contend the limitations of both graph- based and transition-based models are frustrating in when researchers are processing longer and longer texts (Tay al., 2021).
https://github cwm/l comm/yytyyuh/prttiie
1 Introduction
Strings of tokens in natural language are not constructed arbitrarily. Indeed, which tokens co-occur within the same string is highly structured according to the rules of the language. Understand- ing such structures is critical to the comprehension of natural language. In natural language processing (NLP), many structured prediction tasks aim to automatically extract the underlying structure that dictates the relationship between the tokens in a string of text. Examples of such tasks include
From more abstract perspective, the mathemati- cal and algorithmic foundation on which structured prediction models rest can be regarded as a design choice. Graph- based and transition-basn based model- ing are both specific design choices. These design

---

E (b, (a,e),
they
they'
read
read'
read'
read
they's
papers'
papers
oool'
they
cool
cool
cool'
T2
papers
papers'
read'
papers
cool'
read
they'
papers
cool
they
they
read
cool papers
E ((b,a)). (b, (d,,))
(;=((d,e), (d, (d, (B, (b,
(a) An example dependency structure. The root and labels omitted.
(b) The token-split struc-
(c) A realizer Fig. 1b with total orders such that E 81 n Hg. H4 and Flg contain the ares oriented from V (red nodes) to 4 (blue nodes) and from left right.
ture of Fig. la, which a partially ordered
Figure I: An overview of our method. To model a linguistic structure, represented as a directed graph in Fig. la, first convert it into token-split structure (see $3.4) in Fig. lb, which is partial order, to remove undesired transitivity. Then, 2 real numbers are predicted for each vertex in Fig. 1b. The positions of vertices in Fig. Ic in the inequalities indicate the real numbers the vertices are mapped to. The vertices are sorted twice accordingly, resulting in realizer (see Def. 3,8) of 2 total orderings, each possessing set of edges E1 and Ez. The exact set of desired edges in the original structure can be restored from the intersection of E1 and Eg (see $3.3). Some qualitative examples are included in App. J.
choices impose substantial inductive biases by con- fining the class of models available to be utilized to solve the task and set limits on the efficiency of the models. In this paper, we propose fresh design choice for structured prediction. Specifically, we propose an order-theoretic perspective to under- stand and model structures in NLP. Our approach can predict many structures in natural language in (N) time where N the length of the string and is easily parallelizable. The linear-time complexity means our method avoids comparing all O (N2) token pairs. The key innovation that enables this speed-up is the following: Rather than considering structures as graphs, we view them as partial orderings of the tokens in the strings.
show that our method achieves 96.1 labeled attach- ment score (LAS) and 97.1 unlabeled attachment score (UAS) by using intersection of only 2 total orders, 96.4 LAS and 97.4 UAS using intersec- tion of 4 total orders on the English Penn Treebank (Mareus et al., 1993). Furthermore, our method sets the new state of the art on Universal Dependen- cies 2.2 (Nivre et al., 2018), while being 10 times faster and more memory efficient than graph-based models. Our method also achieves 79.2 F1 score with only 4 total orders on the English OntoNotes coreference resolution benchmark (Pradhan et al., 2012), which is on par with the state of the art, while being twice as fast and using less memory.
Motivation
Concretely, we treat structured prediction as a regression task. Because the set of real numbers IR is naturally ordered by <, we use real numbers as the proxy for determining the partial order. We pre- dict K numbers for each token and sort the tokens K times accordingly. Two tokens are partially ordered by < if and only if they are ordered by in all of the K orders above. We further provide an efficiency guarantee based on the well-established result order theory that partial orders satisfying particular conditions can be represented as the intersection of as few as K = 2 total orders. We show that most structures in natural language, including trees, alignments, and set partitions, satisfy these conditions. This result enables to develop linear-time algorithm for predicting such structures. Fig. gives an illustrative example of our framework applied to dependency parsing, in which the structure being modeled is a tree.
We now provide high-level motivation for order-theoretic structured prediction.
2.1 Linearization Structure
The NLP literature abounds with linear-time struc- tured prediction models. Many are derived from the classical shift-reduce parsers (Knuth, 1965) from the compiler literature. One recent line of research has derived linear-time parsers by reducing parsing to tagging (Gómez- RodriggRd and Vilares, 2018; Strzyz et al., 2020; Kitaev and Klein, 2020; Amini et al., 2023, inter alia). In these methods, a finite set of tags C is chosen such that all structures for pars- ing string can be embedded in CN for string of length N. Tagging- based parsers often yield strong empirical performance in both constituency pars- ing and projective dependency parsing. natural question is, then, why do we need another method?
On dependency parsing, our experimental results
We give two motivations. The first linguistic

---

and the second mathematical. Linguistically, the underlying structures of natural language, e.g.. syntax, semantics, and discourse, are often not aligned with the surface form of a sequence due to the existence of displacement (Chomsky, 2015, Chapter 1, p. 44). The strong performance of aussing-as-tagginn schemes relies, in part, there being tight correspondence between the surface string and structure (Amini and Cotterell, 2022, Proposition 1). Mathematically, the maximum number of structures that a discrete tag sequence can represent is at most O((c)>) ) This set is simply not large enough to capture many structures of interest in NLP. For instance, the space of non-projective dependency trees of N tokens has cardinality of O (NN-22) (Cayley, 1889). There- fore, to parse non-projective dependency trees with tagging, the size of the tag set has grow with N. However, this implies performing a classification task with an infinite number of classes.
tree by predicting multiple total orders and inter- secting them. In terms of computation, predicting total orders only requires labeling each node with real numbers and then sorting, the complexity of which is linear under radix sort. On the other hand, an arc-factored model necessarily computes all O (N²) pair-wise scores for every pair of vertices to decide the existence of each edge.
Next, we generalize the intuitions gained from this example. In $3, we explore the class of graphs that can be efficiently represented with partial orders. In $4, we show how to learn the ordering efficiently with neural networks.
Order and Structure
In this section, we describe an order-thcoretic treat- ment for linguistic structure prediction. Specifi- cally, we treat the structure to be predicted as partially ordered set, i.e., transitive relation <. We begin by revisiting how linguistic structures are represented as graphs.
equipped with
2.2 An Illuminating Example
Order-theoretic approaches appear across computer science. For instance, it well-known that a binary tree can be uniquely restored from its inorder traversal and either the pre- or postorder traversal. Consider the following binary tree. Example 2.1 (Binary Tree).
3.1 Linguistic Structures as Directed Graphs
Let be an alphabet, i.e., a finite set of natural language tokens, and let w = W1 .......0 ux E Σ* be string. Linguistic structure prediction the task of ussigning a structure, c.g., a dependency tree, to given string w in natural language.
A wide range of linguistic structures are built upon the relations between pairs of tokens. Many structured prediction models are thus arc-factored, i.e., they predict the arcs between a pair of tokens and then combine them back into structures, which are our focus in this work. Formally, their major goal is model the homogeneous relation' the spanning node set V {wi, W2, WN) of sentence w W1 ... w (Kübler al., 2009). The output space is defined by the input itself, contrast to the external label spaces in other tasks such as classification or language generation.
Inorder: abodefg
Postorder: oobegfd
Figure 2: An example binary tree and partial order over the vertices induced by two total orders.
In a binary tree, vertex is left descendant of vertex y if and only if x is visited before y in both of the in- and postorder traversal. E.g., in Ex. 2.1, a is the left descendant of d and is visited before d in both the in- and postorder traversal.
Another way of stating the above fact is that a binary tree can be recovered from the combination of two total orders, the one induced by the inorder traversal and the one induced by the postorder traversal. Combining these two total orders yields partial order, i.c., left descendant, from which the left child of each vertex can be identified. This partial order shown on the right of Ex. 2.1. See App. B and (Knuth, 1997, $2.3.1, Ex. 7) for further discussion. In light of these observations, we con- ceive an order-theoretic treatment that constructs
Definition 3.1 (Structure). A structure over a string
W1W2 WN is a directed graph G (V, E), where V {wi, "2, ,WN), E C V x V is the set of arcs. A typed structure (V, F,, R) is a structure with F. C V R,
where R is a finite set of relation labels.
'A homogencous relation on set X' is binary relation hetween two clements in X'. can be equivalently represented with the set of edges in graph in which X' is the set of vertices.

---

Most linguistic structures are naturally sub- sumed under this definition. We give two examples of linguistic structure prediction tasks.
real numbers as a proxy to determine the partial ordering of tokens.
Definition 3.6 (Totally Ordered Structure). A partially ordered structure P = (V. is totally ordered if y V: VVrRyVy-a
Example 3.2 (Dependeney Parsing; Kübler et al., 2009, Def. 2.3). A dependency structure is structure = (V, E. R), where C V V x R. and R is the set of dependency relation types. If (z. y.r) E, then Vr + r, (z, $ E.
Due the transitivity of the ordering relation X, totally ordered structure of |V] elements always contains E (K) relations. Given a collec- tion of structures {(V. Bx) defined over the same set of vertices V, their intersection is also structure namelly (VKk)(K]Ex) where K E N. [K] der (1....,KK] The intersection of par- tially ordered structures remains partially ordered. We now cite a famous theorem from order theory.
Example 3.3 (Coreference Resolution). A coref- erence structure is structure 9 = (V, E, R), where E _ V x V R. and R = (r,r'), The re- lations r' represent the entity mention and coref- erence, respectively. We have (ar, y, r) E E if and
only if the textual span y in w is a mention of an entity. (2, r/) E EA (y1, 12, r') C E. if and only if the textual spans ø1 1/1 and 02 : y2 corefer.
Theorem 3.7 (Szpilrajn (1930)). Every partially ordered structure is contained in a totally ordered structure, i.e., for every partially ordered structure P (V.E.-) there exists a totally ordered structure T = (V, E,K) such that E C E.
3.2 From Directed Graphs to Partial Orders
Our treatment constructs linguistic structures with techniques from order theory. The key is to cast the relation between tokens as order, which is defined as follows.
Thm. 3.7 ensures that every partially ordered structure can be embedded in some totally ordered structure in the sense that the totally ordered struc- ture contains all the relations in the partially dered structure. More importantly, stronger result can be shown: Partially ordered structures can al- ways be represented as intersections of collection of totally ordered structures.
Definition 3.4 (Order; Hausdorff, 1914). An order over a set V is a relation <, such that the following hold for all n, U. E V:
(a) irreflexivity; fx;
(b) asymmetry:
y y xx;
(c) transitivity: x y y y z x z.
Natural language exhibits structural sparsity in that each token in string usually only interacts with very few other tokens with a particular relation. For instance, in dependency graph, there are no direct paths between most of the word pairs. Such sparsity, from thher-theoretic point of view, can be characterized by incomparability in a partially ordered set (Birkhoff, 1967, Chapter 1, p. 2).
Definition 3.8 (Realizer). Let P (V,E,<) be partially ordered structure. A realizer Rp of P is a sei of totally ordered structures .Tk] T2.
over V, i.e. each T (V, EK, *k), such that E = [keik] Ek. In other words, Vz, y E V, <z > NGE[K] x x+ Theorem 3.9 (Dushnik and Miller, 1941, Thm. 2.32). There exists a realizer Rp for every partially ordered structure P (V,VE, EV,
By analogy, we define the following partially ordered structure, which is a partially ordered set mathematically. Its elements are the tokens of a string, and its order encodes a linguistic structure.
A corollary of the above theorem is that the complexity of partially ordered structure can be characterized by its order dimension, which is defined as follows.
Definition 3.5 (Partially Ordered Structure). Let G (V, E) be structure. Define the following relation *: For x, y E V, x -> (z, ye E E. We call P = (V, <) a partially ordered structure if < satisfies Def. 3.4.
Definition 3.10 (Order Dimension; Dushnik and Miller, 1941). Let P (V, E.,) be a partially ordered structure. The order dimension Dp of is the cardinality of the smallest realizer P. P.
The essential theoretical foundation of our linguistic structure prediction framework is the classic result that partial orders can be represented by an intersection of total orders (Dushnik and Miller, 1941). It is this result that enables us to use
3.3 Efficiency Guarantees
In this section, we give an efficiency guarantee of thhoorthc structured prediction. These effi- ciency guarantees come from a series of results in

---

Definition 4.1 (Functional Realizer). A func- tional realizer of partially ordered structure P (V, F,xx is set of mappings Fo (1/ (1) ((()),, where O is the set of learnable order theory and lattice theory (Dushnik and Miller, 1941; Hiraguchi, 1955; Birkhoff,, 1967, inter alia). First, it is important to note that not all partially ordered structures can be represented as an inter- section of a constant number of totally ordered structures (Dushnik and Miller, 1941, Thm. 4.1).
(b) V v'nvo Ø; (c) E (..(v")))))
In other words, token-split structure maps the edges from the original structure, including self-loops, into a bipartite graph in which the edges are oriented from V Vo, An example is displayed in Fig. lb.
In fact, testing whether the order dimension of a partial order P is at most K, AK 2 3 is NP-
Given a token-split structure P = (V E, <), we can recover the original structure G = (V, E) from which P is induced using the following equation
complete (Yannakakis, 1982). However, we con- tend that most of the linguistic structures found in natural language processing (Smith, 2011) including trees, equivalence classes (i.e., set parti- tioning), and alignment (i.e., bipartite matching)- can be represented as the intersection of 2 totally ordered structures. We postulate that this is possi- ble due to their innate sparsity, i.c., token tends to only interact with few other tokens. These assumptions are formalized as follows.
E-((2,)) x" E EVV AV VO - (1)
Theorem 3.14. Token-split structures are partially ordered.
Proof. See App. C.I.
Remark 3.15 (Conversion between Structures and Partially Ordered Structures). Thm. 3.14 and Eq. (1) ensure that we convert back and forth between any structure under Def. 3.1 and a par- tially ordered structure. Specifically, they enable us to first convert a structure to a partially ordered structure, predict it order- cher-ehherre and then finally convert il back to a structure.
Assumption 3.11 (Sparsity). A class of linguis- tic structures G (V, E) over natural language strings w E E" with N |u| is called sparse if O(E)) = O(N).
Assumption 3.12 (Linguistic Structures are 2-dimensional). Structures in natural language can be represented as intersections of totally ordered structures.
A Neural Parameterization
We justify Assumptions 3.11-3.12 in App. D. Empirical evidence is also provided in $5, where 2- dimensional theoretee models are trained to tackle two linguistic structure prediction tasks with high performance.
In this section, we describe the core technical contribution of our work. We show how to model partially ordered structures with neural model. Specifically, we define a parameterized realizer of Def. 3.8 and objective function for training the realizer to model the token-split structures. We also give algorithms for efficient training and decoding.
3.4 Token-Split Structures
An obvious limitation of our formulation of linguis- tic structures as partial orders is that by Def. 3.4. partial order is transitive. In other words, æ < A y < implies x < z, which, however, does not hold in the structures characterized by the directed graph formalization in Def. 3.1. In addition, we note that our notation of structures generalizes cyclic graphs. However, partially ordered structures are inherently acyclic due to the transitivity of <. We now introduce the token-split structure, which enables cycles and removes redundant edges intro- duced by transitivity in partially ordered structures.
4.1 Neuralized Total Order
We now discuss parameterized neural network that induces partial orders as the intersection of several total orders.
parameters shared among (lk) and the order di- mension K E N is a hyperparameter of the realizer. IR, Vk E [K] maps each vertex in the input structure to a real number.
Definition 3.13 (Token-Split Structure). A token- split structure induced by a structure G = (V,E) is a structure P = (V, E.-)) such that
The realize element fo
c(k),
We overload Fo as a mapping Fo: V + R
(a) V de UU Vh, where V fx") x
V² vb= 1-bb-fah (a" |
defined Fo( ddt [10] ((()(()) (x). .. (((() (x)

---

The set of real numbers R is totally or- dered, in which the order is given by the (less than) relation.
The first term maximizes Fø(x, y) for x A y. while the second minimizes Fo y) for x yy Note that in the second term, we assume O( = O(N) in a linguistic structure following Assumption 3.11.
Each individual
((h) c Fo induces a total order Tk V, (.((z,))) z,yeV 50 (x)
e()) (w)).)))
4.3 An Efficient Algorithm
The functional realizer assigns K total orders (T1,7% 22. .Tx) to the input string. During de- coding, an edge from to y exists in P if and only if x <x y holds in T k, vk [K].
We remark that both training and decoding of the proposed model can be regarded as performing an aggregation for every token I E V.
Definition 4.2 (Aggregation). An @-aggregation given token x for pair-wise function Fg over the set V is an operation Dyev Fo(x,, y), where + is a commutative and associative operation over which real number addition + is distributive.
Implementing Def. 4.1 with neural networks is straightforward. To obtain f (x") and (8) (a"),
where x", x² are two vertices introduced by the token-split formulation (Def. 3.13) corresponding the same token wr in the input, apply two linear projections on the contextualized representation of x given by a pretrained model parameterized by 6.3 In total, 2K real numbers are predicted for each input token.
Aggregation is a common abstraction for com- puting the relation between a token and every other token. The aggregation operator is associa- tive and commutative, thus can be computed in parallel. The number of required computations is ((VV) for naïvely computing an aggregation of x. the first term of Eq. (3). In greedy decoding, we @-aggregate by computing min, Fe (x, y) to find the optimal relation are from each x. Naïvely, C- aggregating for every token V takes O ( (N2) in total, as each aggregand has complexity of O(N). However, the partial order we assigned over allows us to efficiently compute the aggregands.
4.2 Learning a Functional Realizer
To learn the functional realizers with a gradient- based procedure, we need a differentiable objective. In partially ordered structure P with functional realizer Fe ( s!(2)
During training, we @B-agrregaee using negative log-sum-exp, i.c., we compute - log E, exp(p=Fo(aa y)) for all x, to compute
_(K)). we have x- y if and only if ARE(K]] (5/²) (x) < ( (w))
We re-express this condition as follows:
max (g(()) ((()) (v)) (w)) < 0 (2) kc[K]
FO y)
We call Fe a pair-wise function. On the other hand,
have At y if and only if This condition
For K = 2, we can inspect Eq. (2) to see that
VÆE[K] (50 (f0)(z) (x) 2 ((k) (())
Fo (z, y) is equal to either f(") f0 (v) se (x) (2) (v)) We now define the following
can be re-expressed as Fo v) 2 0. Thus, empirically, the smaller Fo is, the more likely the relation x < y exists.
two subsets of V for ks (1,
Sx(x)= = {y Fo v) r (x) 1 (0)
We now define a training objective, which en- courages the model to make decisions that comply with the order constraints enforced by the struc- tures, described by Eq. (2). Given the token-split version P = (V, F, <) induced by the structure being modeled, we consider the following objective
(x)
Using this notation, we can write the following
Fo(x.v)
Fo(2,y)
(5a)
(2.))V2
zEV VCV
(1)) (x) (x)
(v)) (5b)
(1)
(()) = log Σ
exp - Fo v)+
T (E))
(2.
(3)
log Σ exp Fo
def C1
(N,))E
+
(2) (x) - (2) (v)
PIn this work, we assume f(() is injective, i.c., Vo. E V. V (x) * _(a) (y). See $8.4 for further discussion on the practicality of this assumption.
zCV SES2(w)
G2
'If w. consists of more than one subword due to tokeniza- tion, apply the projection the representation of the last subword.
We now give an efficient algorithm to compute G and, by symmetry, G2. Our first observation is that,

---

by distributivity, we can write
5 Experiments
= θ
(1=((x) (x) - 500000 (w)) (w))
(6a)
We report the experimental results on two represen- tative linguistic structure prediction problems in NLP, namely dependency parsing and coreference resolution. The graph-theoretic definitions of these tasks given in Examples 3.2 and 3.3. We first convert the linguistic structures to partially ordered (token-split) structures as described in $3.4, and then apply the neural method described in $4 to model the partially ordered structures.
VCV (ESI(x)
(x)
o (v)
(1)
(6b)
sEV
SCS1( (a)
(x)
Alone, this application of dynamic program- ming does not reduce the complexity from (N2) to O(N) as desired because the inner aggregand, DyESi(a) - ( (w), itself still takes ((N) time. However, we are able to compute (x))((2) (v) in amortized ((1) time due to Fredman's 's (1976, Eq. 1) algebraic trick.
5.1 Dependency Parsing
Modeling. Orders x are not typed in Def. 3.5. In other words, under Def. 3.5, all relations in partially ordered structure are of the same type. To model dependency type labels, we apply token-level classifier on the contextualized representation. During decoding, similar ure-factored models for dependency parsing, we keep the head word that minimizes Fo( v) for given I, i.c., argmingev Fo( For pretrained language models, we use XLNet-large-cased (Yang al., 2019) for PTB, bert-base-chinest for CTB, and bert-base-multiiinguullccaaa for UD.
The strategy is to sort' the vertices of the partially ordered structure according (22 (v).
to (2) f0
Thus, if we have S0
re (v)) - -10 (()
(x) _ (z),
(x), sim-
ple algebra reveals that f// (x) ())(
()) 1000)(00)))))))))))))))")) (g)) Thus, for given z, every ver- tex y that comes before x in the sorted order satis-
(v). Aggregating in this order enables intermediate results to be reused.
fies Fo u) 1 (v)
Algorithm Computing Gi when K 2.
Datasets. We conduct experiments on the En- glish Penn Treebank (PTB; Marcus et al., 1993), the Chinese Penn Treebank (CTB: Xue et al., 2005). and the Universal Dependencies 2.2 (UD; Nivre et al., 2018). Hyperparameter settings and dataset statisties are given in Apps. F.l and G.I.
1: procedure COMPLTE-G; (1) (2) .V)
2: U + sort V, key=fo (11) (22)
3:
G1, 81 t 0,0 0 is the zeno element of &
4:
for n = up to N:
q1 f (Un) + P =
(1)
5:
Accuracy. We report the experimental results in Tab. 1. The full results on UD are included in App. L.1. On PTB and UD, our method achieves state-of-the-arr performance compared with ((V2) (Yang and Tu, 2022), ON2)) (Mrini et al., 2020), and (N) (Amini al., 2023) meth- ods. Although Amini et al.'s 's's (2023) method has the same complexity as ours, is worth noting that our method is more general since it can handle non-projective dependencies without using pseudo- projectivization (Nivre and Nilsson, 2005).
6:
G - q1
7:
81 (== f0 (Un)
8: return G1
Likewise, if we sorted in reverse, i.e., according to (( (v) f 16 (v), the same manipulation yields that for a given x, every vertex that comes before in the reverse sorted order satisfies (v). (v)
Fo(a, y) = 1 (1² - The algorithm for computing G1 is given in Algorithm 1, which has O(N) computations in total. Moreover, if parallelized, it can be run in Olog N) time. For K > 2, we speculate that the aggregation algorithm can be done in O OKN log k- N). We leave this to future work. See App. E.2 for further discussion.
Efficiency. We evaluate the efficiency our method with two representative baseline models. As depicted in Tab. 2, we observe that our method with K = 2 is almost 10 times as fast as Biaff
nntpp:://huggingface caaecc...o/oleeeee
hnttp::/hhuggingfacecoom wttpeaacee...eeeaeeeeeeeeeeeee weseert-bsee-chieee
"As hefore, we take the complexity of sorting to he ((N) where we can apply radix sort as implemented by Pytorch.
hhttps:/hugggingaace.c

---

UD
assuming entity mentions are constituents (Liu et al., 2022). We experiment on the CoNLL-2012 English shared task dataset (OntoNotes; Pradhan et al., 2012). Hyperparameter settings and dataset statistics are given in Apps. F.2 and G.2.
Model
UAS
LASS
UAS
LASS
LAS
Zhou and Zhao
97.0
95.4
91.2
89.2
Mrini et al."
97.4
96.3
94.6
89.3
Chen and Manning
91.8
89.6
83.9
82.4
Dozat and Manning
95.7
94.1
89.3
88.2
91.8
Accuracy. The experimental results are dis- played in Tab. 3. Similar to the results for dependency parsing, intersection of total orders can already achieve reasonable performance on coreference resolution. This provides empirical evidence for our assertion in $3.3 that most structures in NLP can be represented as the intersection of at most 2 total orders. When K = 4, the performance of our method is comparable to Kirstain et al. (2021), which uses the same pretrained encoder biaffine product computation for token-pair scores.
Yang and Tu
97.4
95.8
93.3
92.3
91.9
Amini al.
97.4
96.4
93.2
91.9
91.8
Ours (K 2)
97.1
96.1
90.7
89.5
91.2
Ours (K = 4)
97.4
96.4
92.4
91.4
92.1
Table 1: Experimental results on PTB, CTB, and UD. indicates usage extra constimency annotation. is our re-implementation using the same pretrained en- coder as ours. K' is the dimension of the realizer used.
Speed (sent/s) f
Memory (GB)
and requires O (N2)
#token
Ours
Hexa
Biaff
Ours
Hexa
Biaff
32
3232
2916
493
1.7
2.9
Efficiency. We compare the efficiency of our method with Kirstain et al.'s (2021) method. It is worth noting that Kirstain et al. (2021) has already performed aggressive optimization in both the speed and memory footprint of coreference model- ing. Our method is still 2 times fast, achieving speed of 82.8 documents per second vs. 41.9, while using less memory, especially on long documents. The full efficiency statistics are given in App. H.
64
3332
3011
328
1.7
3.0
10.1
128
3182
2649
202
1.9
3.7
30.6
256
3314
3270
98
3.1
4.5
56.2
overall
3347
3176
338
1.7
3.0
10.6
Table 2: Speed and memory consumption comparison on PTB test set. We report results averaged over 3 The other
random runs of our method with settings and the results for Hexa and Biaff are taken from Amini et al. (2023, Tab. 3).
Avg. P
Avg. R
Avg. F1
Lee et al. (2017)
69.9
64.7
67.2
(Dozat and Manning, 2017), and consumes less memory than Hexa (Amini al., 2023), which is (NN in space complexity. We further include some qualitative examples using K = App. for a more intuitive picture of our method.
Kantor and Globerson
76.1
77.1
76.6
Joshi al. (2020)
80.1
78.9
79.6
Xu and Choi (2020)
80.3
79.5
79.9
Kirstain et (2021)
81.2
79.4
80.3
Ours (K = 2)
75.2
74.8
75.0
Ours (K'
79.3
79.0
79.2
5.2 Coreference Resolution
Modeling. Our method operates in two-stage manner accommodate the two relations in Ex. 3.3. First, it extracts list of entity mentions using the partial order induced by r (mention relation). other words, x 1 <> span w: y is an entity mention. Then, it models the partial order induced by r' (coreference relation) over the ex- tracted mentions. In other words, my - m2 <> mention my corefers to m2- To find the optimal coreferent antecedent for each mention m, keep m that minimizes Fo(m,m²) m').
Table 3: Experimental results on the OntoNotes bench-
mark. K is the dimension of the realizer.
Related Work
6.1 Structured Prediction
Structured prediction constitutes an important part of natural language processing. It involves the modeling interrelated variables or outputs with structural constraints. Some representative struc- tured prediction problems are sequence tagging (Church, 1988), dependency parsing (Kübler et al.. 2009), and coreference resolution (Stede, 2012).
The overall complexity of the coreference resolution model O(N), since the complexity the encoder used (Beltagy et al., 2020) and the number of valid mentions are both O(N),
More related work is included in App. A.

---

Structured prediction can often be formulated learning and inference of probabilistic graphical models (Smith, 2011, $2.2). The key idea to represent the probability distribution over the output space using a graph, in which each vertex corresponds to random variable, and each edge corresponds to a dependence relation between two random variables.
6.4 Parsing with Syntactic Distance
Shen et al. (2018a,) introduce constituent pars- ing scheme which is also based on the comparison of real numbers. In this scheme, neural model is trained to assign one real number, termed the syntactic distance, to the gap between every pair of neighboring tokens. To parse span into two sub-constituents, the gap with the largest syntactic distance within that span is chosen as the split point. Parsing can be done by recursively performing the above splitting procedure starting from given string. The algorithm has runtime complexity of ON log N), which is significantly more efficient than chart-based parsers with O (N2) complexity. However, this method does not generalize easily perform non-context-fres parsing, since it cannot handle the possible discontinuity of constituents. Moreover, the recursive splitting procedure restricts the output space of parse trees to be a subset of phrase-structure trees (Dyer et al., 2019).
6.2 Graph-Based Parsing
Graph-based parsers, arc-factored parsers, con- struct graphs by scoring all possible (Eisner, 1996; McDonald and Pereira, 2006) between each pair of words. At inference time, they use either maximum spanning tree (MST) finding algorithms (Chu and Liu, 1965; Edmonds, 1967; Tarjan, 1977), or the projective MST algorithm (Lisner, 1996) to build the valid dependency trees with maximum score. Kiperwasser and Goldberg (2016) present neural graph- based parser that uses the same kind of attention mechanism Bahdanau al. (2015) for computing are scores. Greedy decoding that independently assigns a head word to each word (Dozat and Manning, 2017) is also widely used as an approximation to exact inference algorithms.
Conclusion
In this paper, we propose an order-theoretic treatment linguistic structured prediction. Theoretical and empirical results show that most linguistic structure prediction problems can be solved in linear time and memory by framing them as partial orderings of the tokens in the input string, We demonstrate the effectiveness of our method on dependency parsing and coreference resolution, set- ting the new state-of-the-att accuracy in some cases and achieving significant efficiency improvements.
6.3 Tagging-Basd Based Parsing
Inspired by transition- based parsers (Knuth, 1965) and Bangalore and Joshi's (1999) seminal work on supertagging, one line of work uses pretrained models to parse dependency trees by inferring tags for each word in the input sequence. Li et al. (2018) and Kiperwasser and Ballesteros (2018) predict the relative position of the dependent with respect to head a sequence-to-sequene manner. Strzyz et al. (2019) give a framework for analyzing similar tagging schemes. Gódez-Rodrigue et al. (2020) infer a chunk of actions in transition-base system for each word in the sequence.
8 Limitations
8.1 Decoding Algorithms
This work does not provide algorithms for partic- ular structures or algorithms that ensure the well- formedness of structures, such as maximum span- ning trees and projective trees. It remains to be investigated whether existing constrained decod- ing algorithms for arc-factored models (Chu and Liu, 1965; Edmonds, 1967; Eisner, 1997, inter alia) have their counterparts in the trder-theoretic method. We would like explore decoding al- gorithms for structured prediction under order- theoretic formulation in future work.
For non-projective dependency parsing, Gómez- Rodríguez and Nivre (2010, 2013) show that ef- ficient parsers exist for 2-planar trees (Yli-Jyrä, 2003), a sub-class of non-projective trees whose ares can be partitioned into 2 sets while ares in the same set do not cross each other. Strzyz. et al. (2020) propose encoding scheme for 2-planar trees, enabling tagging-bast
parser for such trees. As mentioned in $2.1, to handle the entire set of non-projective trees, the size of the tag set has be unrestricted, which limits the efficiency and appli- cability of this series of approaches of approaches.
8.2 Interpretability
In our method, the interactions between tokens are not directly modeled as in graph- structured

---

prediction models, which makes it more difficult interpret the output of our model. In addition, we leave to future work the investigation of the total ordering metrics (see App. J) learned by the realizers in our method.
pretrained models. Therefore, we foresee no ethical concerns in this work.
Acknowledgments
We would like to thank Zhaofeng Wu, Clément Guerner, and Tim Vicira for their invaluable feed- back. We are grateful to the anonymous reviewers for their insightful comments and suggestions. Afra Amini is supported by ETH AI Center doctoral fel- lowship. MS acknowledges support from the Swiss National Science Foundation (Project No. 197155), Responsible Al grant by the Haslerstiftung; and an ETH Grant (ETH-19 21-1).
8.3 Hardness of Learning
Intuitively, it is harder to learn partial orders over strings than directly modeling the ares in graph, since our order-theoretic treatment has much fewer parameters when scoring token pairs. We also observed in our experiments that order-theoretic models take more training iterations to converge than arc-factored models.
For instance, consider the modeling of tree structure with N nodes with N - 1 ares using partial order, which implies N 11 constraints of the form < y and N2 2N 1 constraints of r ky. From a theoretical perspective, K = is sufficient to represent such a structure as shown in $3. other words, there always exist 2 total orders whose intersection satisfies the aforementioned N(N - 1) constraints. However, it might not be easy to find such orders in practice.
References
Kazimierz Adjukiewiez. 1935. Die syntaktische Kon- nexität. Studia Philosophica, 1:1-27.
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 Linguistics.
A realizer with K beyond 2 can more easily sat- isfy the constraints, especially of the form A y since there are more constraints of this form. allows more possibilities for VkE[K] (k) (x) 2
Afra Amini, Tianyu Liu, and Ryan Cotterell. 2023. Hex- atagging: Projective dependency parsing as tagging. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 1453-1464, Toronto, Canada. Association for Computational Linguistics.
(k) (w) (i.e., more choices of l to satisfy the ex- Bg pression). On the other hand, using small K
Ben Athiwaratkun and Andrew Gordon Wilson. 2018. On modeling hierarchical data via probabilistic order embeddings. In International Conference on Learn- ing Representations.
might make it harder to satisfy the constraints.
We plan to further investigate the hardness of learning a string partial order in future work.
Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Ben- gio. 2015. Neural machine translation by jointly learning to align and translate. In 3rd International Conference on Learning Representations, ICLR 2015.
8.4 Precision of floating-point numbers and numerical stability
Our method might be affected by the finite precision of floating-point numbers and numerical instability when applied to very long strings. Although we did not encounter such issues in our experiments (N < 4096 = 212), issues might arise when N > 65536 = 216 if bfloat16 or
K. A. Baker, C. Fishburn, and S. Roberts, 1972. Partial orders of dimension 2. Networks, 2(1):11-28
Srinivas Bangalore and Aravind K. Joshi. 1999. Su- pertagging: An approach to almost parsing. Compu- tational Linguistics, 25(2):237-265.
half precision is used. In such extreme cases, our assumption that Vk E [K], f injective cannot be fulfilled. Thus, not all totally ordered structures of N elements can be represented, and our method might not exhibit the desired behavior.
Yehoshua Bar-Hillel. 1953. A quasi-arithmetical nota- tion for syntactic description. Language, 29(1):47- 58.
Iz Beltagy, Matthew E. Peters, and Arman Cohan. 2020. Longformer: The long-document transformer. arXiv:2004.057.55
Ethics Statement
We do not believe the work presented here further amplifies biases already present in the datasets and
Jon Louis Bentley. 1979. Decomposable searching prob-
lems. Information Processing Letters, 8(5):244-251.

---

Jon Louis Bentley. 1980. Multidimensional divide-and- conquer. Commun. ACM, 23(():214-22)
Jack Edmonds. 1967. Optimum branchings. Journal of Research of the national Bureau of Standards B. 71(4):233-240.
Mark de Berg, Otfried Cheong, Mare van Kreveld, and Mark Overmars. 2008. Computational Geometry: Algorithms and Applications, 3rd edition. Springer- Verlag TELOS, Santa Clara, CA, USA.
Jason Eisner. 1997. Bilexical grammars and a cubic- time probabilistic parser. In Proceedings of the Fifth International Workshop on Parsing Technologies. pages 54-65, Boston/Cambridge, Massachusetts. USA. Association for Computational Linguistics.
Birkhoff. 1967. Lattice Theory, American Mathe- matical Society colloquium publications. American Mathematical Society.
Jason M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In COLING 1996 Volume I: The 16th International Conference Computational Linguistics.
Arthur Cayley, 1889. A theorem on trees. Quarterly Journal of Mathematics, 23:376-378.
Bernard Chazelle. 1988. A functional approach data structures and its use multidimensional searching. SIAM Journal on Computing, 17(3))427-466. 462.
Michael L. Fredman. 1976. New bounds on the com- plexity the shortest path problem. SIAM Journal on Computing, 5(1):88--9.
Beraad Chazelle. 1990a. Lower bounds for orthogonal range searching: I. The reporting case. Journal of the ACM, 37(2):200-212.
Carlos Kömez-Rodríguez Michalina Strzyz, and David Vilares. 2020. A unifying theory of transition-based and sequence labeling parsing. In Proceedings of the 28th International Conference on Computational Linguistics, pages 3776-3793, Barcelona, Spain (On- line). International Committee on Computational Lin- guistics.
Bernard Chazelle. 1990b. Lower bounds for orthogo- nal range searching: Part II. The arithmetic model. Journal of the ACM, 37(3):339-46;
Danqi Chen and Christopher Manning. 2014. fast and accurate dependency parser using neural networks. In Proceedings the 2014 Conference on Empirical Methods Natural Language Processing (EMNLP), pages 740-750, Doha, Qatar. Association for Com- putational Linguisties.
Carlos Gómez Rodriguez 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.
Noam Chomsky, 2015. The Minimalist Program, 20 edition. The MIT Press.
Carlos Rodriguez and Joakim Nivre. 2010. A transition- parser for 2-planar dependency struc- tures. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1492-1501, Uppsala, Sweden. Association for Com- putational Linguistics.
Yoeng-Jin Chu and Eseng-Hong Liu. 1965. On the shortest arborescence of a directed graph. Scientia Sinica, 14: 14:1399-1400.
Kenneth Ward Church. 1988. A stochastic parts pro- gram and noun phrase parser for unrestricted text. In Second Conference on Applied Natural Language Processing, pages 136-143, Austin, Texas, USA. As- sociation for Computational Linguistics.
Carlos Gódez-Rodriguez and Joakim Nivre. 2013. Divisible Transition Systems and Multiplanar De- pendency Parsing Computational Linguistics. 39(4):799-845.
Marie-Catherine de Marneffe and Christopher D. Man- ning. 2008. Stanford typed dependencies manual. Technical report, Technical report, Stanford Univer- sity.
F. Hausdorff. 1914. Grundzüge der Mengenlehre. Göschens Lehrbücheree/Grrupe I: Reine und Ange- wandte Mathematik Series. Veit & Company.
Timothy Dozat and Christopher D. Manning. 2017. Deep biaffine attention for neural dependency pars- Learning
Toshio Hiraguchi. 1955. On the dimension of orders. The Science Reports of the Kanazawa University, 4:1-20.
ing. In Sth International Conference Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings.
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural Computation, 985):7335
Ben Dushnik and E. W. Miller. 1941. Partially ordered sets. American Journal of Mathematics, 63(3);600- 610.
Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel Weld. Luke Zettlemoyer, and Omer Levy. 2020. Span- BERT: Improving pre-training by representing and predicting spans. Transactions of the Association for Computational Linguistics, 8:64-77.
Chris Dyer, Gābor Melis, and Phil Blunsom. 2019, A critical analysis biased parsers in unsupervised parsing. CoRR, abs/ 1at.1999999229

---

Ben Kantor and Amir Globerson. 2019. Coreference resolution with entity equalization. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 673-677, Florence, Italy, Association for Computational Linguistics.
Tianyu Liu, Yuchen Jiang, Ryan Cotterell, and Mrin- maya Sachan. 2022. A structured span selector. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies. pages 2629-2641, Seattle, United States. Association for Computational Linguistics.
Eliyabu Kiperwasser and Miguel Ballesteros. 2018. Scheduled multi-task learning: From syntax to trans- lation. Transactions of the Association for Computa- tional Linguistics, 6:225-240.
Ilya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. In International Confer- ence on Learning Representations.
Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional LSTM feature representations. Transactions of the A Association for Computational Linguistics, 4:313- 327.
Holbrook Mann MacNeille. 1937. Partially ordered sets. Transactions of the American Mathematical Society,
4263):416-460
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated cor- pus of English: The Penn Treebank. Computational Linguistics, 19(2)3133333
Yuval Kirstain, Ori Ram, and Omer Levy. 2021. Coref-
erence resolution without span representations. In Proceedings of the 59th Annual Meeting of the Asso- ciation for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 2: Short Papers), pages 14-19, Online. Association for Computational Linguistics.
Peter McCullagh. 1980. Regression models for ordinal data. Journal of the Royal Statistical Society. Series B (Methodological), 4202):109-142.
Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algo- rithms. In 11th Conference of the European Chap- ter of the Association for Computational Linguistics, pages 81-88, Trento, Italy. Association for Computa- tional Linguistics.
Nikita Kitaev and Dan Klein. 2020. Tetra-tagging: Word- sorrhhynchrooouu parsing with linear-time inference. Proceedings of the 58th Annual Meeting of the As- sociation for Computational Linguistics, pages 6255- 6261, Online. Association for Computational Lin- guistics.
Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajië. 2005. Non-projective dependency pars- ing using spanning tree algorithms. In Proceed- ings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523 530. Vancouver, British Columbia. Canada. Association for Computa- tional Linguistics.
Donald E. Knuth, 1965. On the translation of languages from left to right. Information and Control, 8(6):607- 639.
Donald F. Knuth. 1997. The Art of Computer Pro- gramming: Fundamental Algorithms, edition, vol- ume 1. Addison Wesley Longman Publishing Co., Inc., USA.
George A. Miller. 1994. WordNet: A lexical database for English. In Human Language Technology: Pro- ceedings of a Workshop held at Plainsboro, New Jersey, March 8-11, 1994.
Sandra Kübler, Ryan McDonald, and Joakim Nivre. 2009. Dependency Pursing. Springer Cham.
E. L. Lawler. 1978. Sequencing jobs minimize to- tal weighted completion time subject to precedence constraints. In B. Alspach, P. Hell, and D.J. Miller, editors, Algoritlmic Aspects of Combinatorics. vol- ume 2 of Annals of Discrete Mathematics, pages 75-90. Elsevier.
Khalil Mrini, Franck Demoncouut, Quan Hung Tran, Trung Bui, Walter Chang, and Ndapa Nakashole. 2020. Rethinking self-attention: Towards inter- pretability in neural parsing. In Findings of the As- sociation for Computational Linguistics: EMNLP 2020, pages 731-742, Online. Association for Com- putational Linguistics.
Kenton Lee, Lubeng He, Mike Lewis, and Luke Zettle- moyer. 2017. End-to-end neural coreference reso- lution. Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 188-197, Copenhagen. Denmark. Association for Computational Linguistics.
Joakim Nivre. 2003. An efficient algorithm for pro- jective dependency parsing. In Proceedings of the Eighth International Conference Parsing Tech- nologies, pages 149-160, Nancy, France.
Joakim Nivre, Mitchell Abrams, Zeljko Agié, Lars Ahrenberg, Lene Antonsen, Maria Jesus Aranz- abe, Gashaw Arutie, Masayuki Asahara, Luma Ateyah, Mohammed Attia, Aitziber Atutxa, Lies- beth Augustinus, Elena Badmaeva, Miguel Balles- teros, Esha Banerjee, Sebastian Bank, Verginica
Zuchao Li. Jiaxun Cai, Shexia He, and Hai Zhao. 2018. Seq2seq dependency parsing. In Proceedings of the 27th International Conference Computational Lin- guistics, pages 3203-3214. Santa Fe, New Mexico, USA. Association for Computational Linguistics.

---

Barbu Mititelu, John Bauer, Sandra Bellato, Kepa Bengoetxea, Riyaz Ahmad Bhat, Erica Biagetti, Eck- hard Bick, Rogier Blokland, Victoria Bobicev, Carl Börstell, Cristina Bosco, Gosse Bouma, Sam Bow- man, Adriane Boyd, Aljoscha Burchardt, Marie Can- dito, Bernard Caron, Gauthier Caron, Gülşen Ce- biroglu Eryigit, Giuseppe G. A. Celano, Savas Cetin, Fabricio Chalub, Jinho Choi, Yongseok Cho, Jayeol Chun, Silvie Cinková, Aurélie Collomb, Cağri Çöl- tekin, Miriam Connor, Marine Courtin, Elizabeth Davidson,
manenko, Rudolf Rosa, Davide Rovati, Valentin Rosca, Olga Rudina, Shoval Sadde, Shadi Saleh, Tanja Samardžić, Stephanie Samson, Manuela San- guinetti, Baiba Saulite, Yamin Sawanakunanon, Nathan Schneider, Sebastian Schuster, Djamé Sed- dah, Wolfgang Seeker, Mojgan Seraji, Mo Shen, Atsuko Shimada, Muh Shohibussirr,, Dmiiryy Sichi- nava, Natalia Silveira, Maria Simi, Radu Simionescu, Katalin Simkó, Mária Simková, Kiril Simov, Aaron Smith, Isabela Soares- Soares-Bastos. Bastos. Antonio Stella, Milan Straka, Jana Strnadová, Alane Suhr, Umut Sulubacak, Zsolt Szántó, Dima Taji, Yuta Takahashi, Takaaki Tanaka, Isabelle Tellier, Trond Trosterud, Anna Trukhina, Reut Tsarfaty, Francis Tyers. Sumire Ue- matsu, Zdeňka Urešová, Larraitz Uria, Hans Uszkor- eit, Sowmya Vajjala, Daniel Niekerk, Gertjan van Noord, Viktor Varga, Veronika Vincze, Lars Wallin, Jonathan North Washington, Seyi Williams, Mats Wiren, Tsegay Woldemariam, Tak-sum Wong, Chunxiao Yan, Marat M. Yavrumyan, Zhuoran Yu, Zdenčk Žabokrtský, Amir Zeldes, Daniel Zeman, Manying Zhang, and Hanzhi Zhu. 2018. Universal dependencies 2.2. LINAT/CLARIAHL library the Institute of Formal and Applied Linguis- tics (ÚFAL), Faculty of Mathematics and Physics, Charles University.
de Marneffe, Valeria de Paiva, Arantza Diaz de Ilarrzza, Carly Dicker- son, Peter Dirix, Kaja Dobrovolje, Timothy Dozat, Kira Droganova, Puneet Dwivedi, Marhaba Eli, Ali Elkahky, Binyam Ephrem, Tomaž Erjavec, Aline Eti- enne, Richárd Farkas, Hector Fernandez Alcalde, Jen- nifer Foster, Cláudia Freitas, Katarina Gajdošová, Daniel Galbraith, Marcos Garcia, Moa Gärdenfors, Kim Gerdes, Filip Ginter, lakes Goenaga, Koldo Go- jenola, Memduh Gökuraak, Yoav Goldberg, Xavier Gómez Guinovart, Berta Gonzäles Saavedra, Matias Grioni, Normunds Grüzîtis, Bruno Guillaume, Cé- line Guillot-Barbanee Barbance. Nizar Habash, Jan Hajič, Jan Hajič jr., Linh Hà My. Na-Rae Han, Kim Harris, Dag Haug, Barbora Hladká, Jaroslava Hlaváčová, Florinel Hociung, Petter Hohle, Jena Hwang, Radu lon, Elena Irimia. Tomás Jelínek, Anders Johannsen, Fredrik Jargensen, Hüner Kaşıkara, Sylvain Kahane, Hiroshi Kanayama, Jenna Kanerva, Tolga Kayadelen, Vá- clava Kettnerová, Jesse Kirchner, Natalia Kotsyba, Simon Krek, Sookyoung Kwak, Veronika Laippala, Lorenzo Lambertino, Tatiana Lando, Septina Dian Larasati, Alexei Lavrentiev, John Lee. Phutong Lē Höng, Alessandro Lenci, Saran Lertpradit, Her- man Leung. Cheuk Ying Li. Josie Li, Keying Li, KyungTae Lim, Nikola Ljubešic, Olga Loginova, Oiga Lyashevskaya, Teresa Lynn, Vivien Macke- tanz, Aibek Makazhanov, Michael Mandl, Christo- pher Manning, Ruli Manurung, Cätälina Märän- duc, David Mareček, Katrin Marheinecke, Héctor Martínez Alonso, André Martins, Jan Mašek, Yuji Matsumoto, Ryan McDonald, Gustavo Mendonça, Niko Miekka, Anna Missilä, Cätälin Mititelu, Yusuke Miyao, Simonetta Montemagni, Amir More, Laura Moreno Romero, Shinsuke Mori, Bjartur Mortensen, Bohdan Moskalevskyi, Kadri Muischnek, Yugo Mu- rawaki, Kaili Müüriscp, Pinkey Nainwani, Juan Igna- cio Navarro Horñiacek, Anna Nedoluzhko, Gunta Nešpore-Berzkalne Luting Nguyên Thi, Huyèn Nguyēn Thj Minh. Vitaly Nikolaev, Rattima Nitisaroj. Hanna Nurmi, Stina Ojala, Adédayč Olúökun, Mai Omura, Petya Osenova, Robert Östling, Lilja Øvrelid, Niko Partanen, Elena Pascual, Marco Passarotti, Ag- nieszka Patejuk, Siyao Peng. -Aguuto Perez, Guy Perrier, Slav Petrov, Jussi Piitulainen, Emily Pitler, Barbara Plank, Thierry Poibeau, Martin Popel, Lauma Pretkalnipa. Sophie Prévost, Prokopis Proko- pidis, Adam Przepiórkowski. Tina Puolakainen, Sampo Pyysalo. Andricla Rääbis, Alexandre Rade- maker, Loganathan Ramasamy, Taraka Rama, Car- los Ramisch, Vinit Ravishankar, Livy Real, Siva Reddy, Georg Rehm, Michael RieBler, Larissa Ri- naldi, Laura Rituma, Luisa Rocha, Mykhailo Ro-
digital
Joakim Nivre and Jens Nilsson. 2005. Pseudo- projective dependency parsing. In Proceedings of the 43rd Annual Meeting of the Association for Com- putational Linguistics (ACL '05), pages 99-106, Ann Arbor, Michigan. Association for Computational Lin- guistics.
Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang. 2012. CoNLL- 2012 shared task: Modeling multilingual unrestricted coreference in OntoNotes. In Joint Conference on EMNLP and CoNLL Shared Task, pages 1-40, Jeju Island, Korea, Association for Computational Lin- guistics.
John Shawe-Taylor and Nello Cristianini. 2004. Kernel Methods for Pattern Analysis. Cambridge University Press.
Yikang Shen, Zhouhan Lin, Chin-Wei Huang, and Aaron Courville. 2018a. Neural language modeling by jointly learning syntax and lexicon. In Interna- tional Conference on Learning Representations.
Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessan- dro Sordoni, Aaron Courville, and Yoshua Bengio. 2018b. Straight to the tree: Constituency parsing with neural syntactic distance. In Proceedings of the 56th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 1171-1180, Melbourne, Australia. Association for Computational Linguistics.
N.A. Smith. 2011. Linguistic Structure Prediction. Syn- thesis digital library of engineering and computer science. Morgan & Claypool

---

M. Stede. 2012. Discourse Processing, Synthesis lec- tures on human language technologies. Morgan & Claypool.
for Computational Linguistics and the 10th Interna- tional Joint Conference on Natural Language Pro- cessing, pages 93-99, Suzhou, China. Association for Computational Linguistics.
Mark Steedman, 1987. Combinatory grammars and par- asitic gaps. Natural Language Linguistic Theory, 5(3):403-439.
Douglas B. West. 2018. Introduction Graph Theory. Pearson Modern Classics for Advanced Mathematics Series. Pearson.
Mark Steedman. 2000. The Syntactic Process. MIT Press, Cambridge, MA. USA.
Liyan Xu and Jinho D. Choi. 2020. Revealing the myth of higher-order inference in coreference resolution. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pages 8527-8533, Online. Association for Computa- tional Linguistics.
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.
Naiwen Xue, Fei Xia, Fu-dong Chiou, and Marta Palmer. 2005. The penn chinese treebank: Phrase structure annotation of large corpus. Natural Language En- gineering, 11(2):07-233,
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-244222 2484, Barcelona. Spain (Online). Inter- national Committee Computational Linguistics.
Hiroyasu Yamada and Yuji Matsumoto. 2003. Statis- tical dependency analysis with support vector ma- chines. In Proceedings of the Eighth International Conference on Parsing Technologies, pages 195-206, Nancy, France.
Edward Szpilrajn. 1930, Sur l'extension de l'ordre partiel. Fundamenta Mathematicae, 16(1):386-33)
Songlin Yang and Kewei Tu. 2022. projective dependency parsing. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 2188 2200, Dublin, Ireland. Association for Compu- tational Linguistics.
Robert Endre Tarjan. 1977. Finding optimum branch- ings. Networks, 7(1)255-35.
Ben Taskar, Dan Klein. Mike Collins, Daphne Koller, and Christopher Manning. 2004. Max-margin pars- ing. In Proceedings of the 2004 Conference on Em- pirical Methods in Natural Language Processing. pages 1-8, Barcelona, Spain. Association for Com- putational Linguistics.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Car- bonell, Russ R Salakhutdinov, and Quoc V Le. 2019. XI.Net: Generalized autoregressive pretraining for language understanding. In Advances Neural In- formation Processing Systems, volume 32. Curran Associates, Inc.
Yi Tay. Mostafa Dehghani. Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. 2021. Long range arena A benchmark for efficient transformers. In International Conference on Learning Representa- tions.
Mihalis Yannakakis. 1982 The complexity of the par- tial order dimension problem. SIAM Journal on Al- gebruic Discrete Methods, 3(3:331-3358
Anssi Mikael Yli-Jyrä. 2003. Multiplanarity-a model for dependency structures in treebanks. In TLT 2003, Proceedings of the Second Workshop on Treebanks and Linguistic Theories. Växjö University Press.
L. Tesnière. 1959. Élements de Syntaxe Structurale. C. Klincksieck.
Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler. 1979 The recognition of series parallel digraphs. In Proceedings of the Eleventh Annual ACM Sympo- sium on Theory of Computing, STOC page 1-12, New York, NY, USA. Association for Computing Machinery.
Zhang, Zhenghua Li, and Min Zhang. 2020. Effi- cient second-order TreeCRF for neural dependency parsing. In Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics. pages 3295-3305, Online. Association for Computa- tional Linguistics.
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. 2015. Order-embeddings of images and language. In International Conference on Learning Representations.
Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-base based and gransition-bases dependency parsing. ceedings of the 2008 Conference on Empirical Meth- ods in Natural Language Processing, pages 562-571, Honolulu, Hawaii. Association for Computational Linguistics.
Pro-
Xinyu Wang and Kewei Tu. 2020. Second-order neu- ral dependency parsing with message passing and end-to-end training. Proceedings of the 1st Con- ference of the Asia-Pacific Chapter of the Association

---

Junru Zhou and Hai Zhao. 2019. DeadeDriven Phrase Structure Grammar parsing on Penn Treebank. In Proceedings of the 57th Annual Meeting of the Asso- ciation for Computational Linguistics. pages 2396- 2408, Florence, Italy. Association for Computational Linguistics.

---

A Related Work
A.1 Ordinal Regression
Ordinal regression is a family of problems that involve ranking set of objects. Unlike classification, the label spaces in ordinal regression exhibit some natural ordering in its elements (McCullagh, 1980). For instance, in information retrieval, ranking model sorts set of documents typically according the document's relevance the query. Practically, ordinal regression either be tackled either regression classification by treating the ranks as real-values or the assignment particular rank value as a classification (Syawe-Taylor and Cristianini, 2004).
A.2 Order Embeddings of Lexicons
The notion of partial order has also been explored for learning word embeddings. The lexicons natural languages exhibit hierarchical structures according to the concepts that the words represent (Miller, 1994). For instance, 'cat' and "dog" are "animal', 'animal' and 'plant" are 'living thing'. Order embeddings (Vendrov ct al., 2015; Athiwaratkun and Wilson, 2018) propose to learn such property by learning embeddings that encode such partial order on the lexicon, resulting in improved performance on downstream tasks such image caption retrieval.
B An Order-Theoree Re-evaluation of $2.2
Inorder: abede f
Postorder: acbeg d
(a) The example binary tree in $2.2 and its traversal sequences.
9
(b) Partial order of $2.2 defined by the intersection in- and postorder. - represents relation A <11
(c) Partial order of $2.2 defined by the intersection of reversed in- and pos-
torder. A + B represents the relation A -22 B.
Figure 3: An order-theoretic re-evaluation Thm. B.I.
Theorem B.1 (A binary tree and its traversal; Knuth, 1997, $2.3.1, Ex. 7). Given the inorder and either the pre- or postorder traversal of the vertices in binary tree, the binary tree structure can be reconstructed.
Proof Sketch (order-theoreticc. Without loss of generality, explain the case of the combination of in- and postorder. V denotes the of vertices in the binary tree. First, the intersection of in- and postorder defines a partial order relation P1 (V, E1, For any vertices x, y in the binary tree, -1 y and only if left descendant of y. I.e., x either the left child or a descendant the left child of y (see Fig. 3b). Since r visited before visiting y in both inorder traversal and postorder traversal, if and only if x is the left descendant of y. The left child of each vertex in can be decoded from P, by finding

---

the child with the deepest subtree. Second, the intersection of reversed inorder and postorder defines a partial order relation P2 (V, E2, <2). For any 2 vertices x, y in the binary tree, z <2 y if and only if x is a right descendant of y (see Fig. 3c). Since x is visited before visiting y in both the reversed inorder traversal and postorder traversal, and only if x is the right descendant of y. The right child of each vertex in V can be decoded from P2 also by finding the child with the deepest subtree. Thus, the original binary tree can be reconstructed.
C Proofs on the Partially Ordered Properties of Structures
C.1 Proof Thm. 3.14
Theorem 3.14. Token-split structures are partially ordered.
Proof. We show that a token-split structure P = (v, E, <) structure defined in Def. 3.4.
satisfies all the properties of partially ordered
1. irreflexivity: By Def. (c), for x E V, x Ax.
2. asymmetry: Suppose that Ar, U, + y, s.t. X x A AyRa. By Definitions 3b) and 3.13 (c), x, y E
Ø. Thus, x z = y tx..
3. transitivity: < y A y < cannot hold by Def. (c). Since <y y implies x E AyE Vd, while x z implies E V A x E Vd, contradiction occurs due V nvv Ø by Def. 3.13 holds since the antecedent of the proposition is always false.
< y A =
Thus, token-split structures are partially ordered.
D Guarantees of Order Dimension of I Linguistic Structures
We justify the guarantees of order dimension of linguistic structures. One conventional way to characterize the dimension of partial orders is from a lattice-theoretic point of view. A basic result tells us that a partial order is 2-dimensional if and only if its complete lattice embedding has planar Hasse diagram (Baker et al., 1972). In other words, its complete lattice embedding be drawn on plane without any crossing edges.
Theorem D.1 (Baker et al., 1972 Thm. 4.1). Suppose P = VVE.+) is a partially ordered structure. Then the following are equivalent:
(a) D(P) S 2.
(b) The complete lattice embedding P has a planar Hasse diagram.
Remark D.2. MacNeille (1937) and Birkhoff (1967, Chapter 5) introduced the construction of complete lattice embeddings for any partial order. Although is difficult in practice to compute the complete lattice embedding for a partially ordered structure (MacNeille, 1937), Thm. D.I can still provide an empirical characterization of the class of structures that can be efficiently represented. According to Euler's s formula the average degree of a vertex in planar graph cannot exceed 6 (West, 2018, $6.1.23), which intuitively intersection of 2 totally ordered
forces the partially ordered structures that can be represented structures to be sparse enough-thus to have planar complete lattice embeddings.
Fortunately, this is often the case in natural language. Such phenomenon is closely related to what is termed valency by Tesnière (1959, Part Book D). The number of actants (i.e., arguments) needed to implement the function of word is a property of the word itself a constant that does not change with the context (ef. categories in categorial grammars (Adjukiewicz, 1935; Bar-Hillel, 1953; Steedman, 1987)). In natural language, the valency of a word is often a small constant. For instance, Steedman (2000, Chapter 3, fn. 10 and Chapter 8, 212) observes that the highest valency in the Dutch and English lexicon can be regarded as bounded by 4.
FF.g., the English word "give" may have the category (VP/NP)NP, meaning that it needs two NP categories to the right to form a VP. An example is the verb phruse "give me an apple", " in which "me" and "an apple" are noun phrases.

---

We refer interested readers MacNeille (1937) and Birkhoff (1967, Chapter 5) for the construction of complete lattice embeddings. Here, we give weaker but more practical efficiency guarantce, based on a method construct large partially ordered structures from smaller partially ordered structures.
Definition D.3 Beeriss-Paralle Partial Orders; Valdes al., 1979). A partially ordered structure is series-parallel if satisfies the following inductive definition:
(a) single-vertex structure with no edges is peries-paralles
(b) If partially ordered structures P1 = (V1, E1, <) and P2 = (V E2. <) are series-parallel, so is the partially ordered structures constructed by either of the following operations:
i. Parallel composition:
Pp (V1 U V2 E1 U E2, 3).
ii. Series composition:
P. - (V1 U 22, E U E2 (M1XN2), <). where Mi is the set of sinks P and N2 the set of sources 2f
Theorem D.4 (Series-paralley partially ordered structures 2-dimensional; Valdes al., 1979). The dimension of series series-parallel partially ordered structures most 2.
Thm. D.4 provides the guarantee that many structures in natural language processing can be represented the intersection of totally ordered structures. Since most structures of interest in NLP, such trees and forests (thereby alignments and set partitioning), can be subsumed under series-parallel partially ordered structures, therefore have an order dimension of most 2.
Proposition D.5 (Trees are 2-dimensional; Lawler, 1978). Directed tree partially ordered structures series-parallel. The order dimension of tree structures is most
Proposition D.6 (Forests are 2-dimensional). Forests are series-parallel. The order dimension of forest structures is most 2.
Proof. Forests are parallel compositions of trees. Thus, the proposition holds.
E Efficient Algorithm for O-Aggregation
E.1 Correctness of Algorithm 1
Algorithm 1 Computing G1 when K = 2.
1: procedure COMPLTE-G (1) (2)
1 V)
2: U sort V, key- -
3: G1 - 0,0 0 0 the element
4:
for n = up to N
5:
f1= / (Un) 81 D = p
Gi(U))
6:
G -= 91
7:
81 0= fø (Un)
8:
return G1
Proposition E.1. In Algorithm 1, G1 - Orev DyES)(2) (x) -z)
Proof. By induction, we show that upon finishing step n, 81 + DyESi (U+1)) - 10 (1)) G. b Oze(Ui,. U.. OyeSi(z) (fe)))
(z) (())(())
((2)) (v)) First, ST(Un) -UI,.... Un-1} holds discussed
in $4.3. When n = 1, we have $1 = (()) (U1). Gi = 0 == + Dyess(()) (w) (fo 10 (v))
18 "Sources and sinks refer to the vertices without incoming ares and without outgoing ares, respectively.

---

since Si( 2. Assume that our statements hold for - j. when j 1, it is straightforward
that = ① (CSI(UsH2) -0 (2)) For C1, we have
G1 = +
( (a) 10 (v)) @
10 (U)+)) +
1 (v))
(7a)
=-(Ui,- ,2) (ESI(z)
(ESI(U,+1)
( (x) (1)(
+
(U)+t)) -1 (v)
(11)
(7b)
=E U3 (x)
(ESI(U))1)
1000) (x) (00((())
(7c)
=E 3 (E)((r)
Thus, the claims hold for n = + 1, establishing the induction step.
Proposition E.2. Algorithm runs in (NN) time and space. With parallel computing, Algorithm runs in Olog N) span.
Proof. The sorting step in line 2 can be exccuted in (NN) time and space. The for loop in lines 4 to 7 runs in (NN) time and space. In total, Algorithm 1 runs in (NN time and space. Computing 81 in each step is a sum of f (Un), which can be done in (log N) span with parallel computing. Q1, G in each step be computed in (1) in parallel following the computation of all 81. Thus, the total span of Algorithm is Olog.N) N)
E,2 Order Dimension K > 2
Finding all y V such that x < y in partial order for given V requires efficiently finding all y that satisfy A (k)) (x) < <f (k) (v)). We remark that this problem bears resemblance to orthogonal
range searching in K K-ddimensional space (Berg et al., 2008, Chapter 5), i.e., for given we aim to find
(v), all y such that (w), fe (())(()))))))))))))) (v).... .1 _ (w)) is within the range (x), oo) x (.) (x), x0) x x (fR (x), oo). This problem can be naively solved in (log"~1 N + E) using a range tree (Bentley, 1979, 1980; Chazelle, 1988, 1990a,b), where e is the cardinality of query results, as opposed to are-factored models in which solving the same problem takes ONN) computations.
(w))
For ff-aggregation, more efficient algorithm which makes use of (K-11)dimmnsionne range trees can be designed. In future work, show that computing the complexity of (B-aggregation for all e V can be further reduced OKKN log xog-- K-2 NN) by applying Fredman's 's (1976) trick which we used in Algorithm 1. Extending the notation in $4.3, the set of all vertices V can be partitioned into K subsets Si (x),... Sx(x)) for each V. where Sa(x) = {y y E V A Fo(x.v) (k) (x) 16 (1)). + vEV Fo(x, v) can be decomposed into @-aggregation of K terms.
G(x)) def
vo(
(8a)
VCV
G(x)
+
Fo(
(8b)
kE[K]
yESu
del
('(((r))
We leave to future work showing that computing each Gx(a)) takes O (log" 2 2N).
F Hyperparameter Settings
F1 Dependency Parsing
For pretrained language models, we use "LNet--arge-casee!! (Yang et al., 2019) for PTB. bert-base-chinese" for CTB, and bert--ase-mmlliingggll---ss for UD. We set the dimen- sion of POS tag embedding to 256 for all experiments. On top of concatenated pretrained representations
"https://huggiii http://hwggnnnecccc.oooo/tetaare
htt.e/aacce.ccceeeeeeeeeeeeeeeee "httpss://uugiiggface cw/bertt seweert-baee-hineee
#https://huggingfe co/bert- base passe-multilinusss

---

and POS embedding, we use 3-layer BiLSTM (Hochreiter and Schmidhuber, 1997) with hidden size of 768 for base-sized models (bert-base-chinese on CTB and hert-multilingual and 1024 for large-sized models (xInet-large-casee on PTB). apply dropout with a rate of 0.33 to the concatenated embedding layer, between LSTM layers, and before the linear projection layer of the realizer. We employ A (Loshchilov and Hutter, 2019) with a learning rate of 2c- 5 for pretrained LMs and 1e-4 for POS embedding, BiLSTM, and linear projection during training. The gradient clipping threshold is set to 1.0. The batch size for training is 32. The number of training epochs is 50.
on UD)
F.2 Coreference Resolution
We use Longformerr-lrge-caasee (Beltagy et al., 2020) as the pretrained encoder. We use the same hy- perparameter settings as Kirstain al. (2021). We use AdamW with learning rate of 1c for pretrained LM and 3e- for the linear projection during training, with 5600 linear warmup steps. Training documents are batched into batches with maximum 5000 tokens in total. The number of training epochs is 129.
Datasets
G.1 Dependency Parsing
Preprocessing. We follow previous work (Kiperwasser and Goldberg, 2016; Dozat and Manning, 2017) derive the dependency annotations from the treebank annotations using the Stanford Dependency con- verter v3.3.0 (de Marneffe and Manning. 2008). During evaluation, punctuations are omitted. Following Amini al. (2023), we provide gold part-of-speech tags to the model during training and decoding.
Splits. The dataset splits are consistent with previous work. For PTB, we follow the standard split of Marcus et al. (1993), resulting in 39,832 sentences for training. 1,700 for development, and 2,416 for testing, For CTB, we follow the split of Zhang and Clark (2008), resulting in 16,091 sentences for training. 803 for development, and 1,910 for testing. For UD, we follow previous work (Zhang et al., 2020; Yang and Tu, 2022) and use the standard splits of the following corpora for experiments: BG-btb, CA-ancora, CS-pdt, DE-gsd, EN-ewt, ES ES-ancor, FR-gsd, IT-isdt, NL-alpino, NO-rrt, RO-Ir,, RU-syntagrus.
Licenses. The PTB and CTB datasets are licensed under LDC User Agreement. The UD dataset is licensed under the Universal Dependencies License Agreement.
G.2 Coreference Resolution
Preprocessing. We experiment on the CoNLL-2012 English shared task dataset (OntoNotes; Pradhan et al., 2012). We follow the preprocessing procedure of (Kirstain et al., 2021). During training and decoding, the speaker information is provided to the model.
Splits. The OntoNotes dataset contains 2,802 documents for training, 343 for validation, and 348 for testing, We use this official split following previous work (Lee et al., 2017; Kirstain et al., 2021).
Licenses.
The OntoNotes dataset is licensed under LDC User Agreement.
H Efficiency Evaluation
HL Dependency Parsing
For efficiency evaluation, BERT-large-cased
used as the pretrained encoder for our method with K = 2, hexatagger (Hexa; Amini et al., 2023), and biaffine model (Biaff). We use the English PTB test set and truncate or pad the input sentences to the control length. The results are averaged over 3 random runs on the same server with one Nvidia A100-80GB GPU. The other experimental settings are kept the same (i.e., the version of PoTch and transformers. FP32 precision, batching).
H.2 Coreference Resolution
"hhttps:/huuggingfaae http://iinnaaac.cccaleaaaaaaa coraalleeai/looffforer---rrr
/https://hugginngface
"https://huggingfface cw/all/aaaaeeeeeeeeoooeeoooe htt//alleaaiiiaaeeeeeeeeaaaaaaea col/allenni/llggforrebbaaaaa

---

Speed (doc/s) f
Memory (GB) 4
Doe length
Ours (K 4)
Kirstain et al.
Ours (K' 4)
Kirstain et al.
512
72.5
35.7
7.3
7.4
1024
54.3
26.7
7.3
7.4
2048
33.8
15.9
9.4
9.5
4096
19.3
17.8
21.0
overall
82.8
41.9
7.3
7.4
Table 4: Comparison of speed and memory consumption on OntoNotes test set using Longformer- base pretrained encoder. Results are averaged over 3 random runs on the same server with one Nvidia A100-80GB GPU using BERT-large encoder. We use a batch size of 32 documents.
We compare the efficiency of our order-theoretic method with baseline coreference resolution model. The full results are given in Tab, 4. the OntoNotes coreference resolution benchmark, our method is twice as fast as Kirstain et al.'s is (2021) model while using less memory, especially on long documents. It is worth noting that Kirstain et al. (2021) has already performed aggressive optimization in both the speed and memory footprint of coreference modeling. Le., they abandon the computation for textual span representations and entity-pair representations, and use biaffine scorers to compute coreference scores.
I Additional Experimental Results
L.1 Dependency Parsing
We report additional experimental results on the UD dependency parsing dataset in Tab. 5. On average, our model has state-of-the-ard performance and outperforms all other baseline models on 5 languages.
bg
ca
es
de
en
it
no
m
Avg.
Zhang et (2020)
90.77
91.29
91.54
80.46
87.32
90.86
87.96
91.91
88.62
91.02
86.90
93.33
89.33
Wang and Tu (2020)
90.53
92.83
92.12
81.73
89.72
92.07
88.53
92.78
90.19
91.88
85.88
92.67
90.07
+BERT
Wang and Tu (2020)
91.30
93.60
92.09
82.00
90.75
92.62
89.32
93.66
91.21
91.74
86.40
92.61
90.61
Dozat and Manning (2017)
90.30
92.65
85,98
91.13
93.78
91.77
94.72
91.04
94.21
87.24
94.53
91.82
Yang and Tu (2022)
91.10
92.57
85.87
91.32
93.84
91.69
94.78
91.65
94.28
87.48
94.45
91.96
Amini (2023)
85.18
90.85
94.72
91.89
87.54
91.86
ours (K 2)
92.81
93.26
92.52
83.33
90.38
92.55
89.83
93.82
91.29
93.61
87.40
94.
91.24
ours (K- 4)
93.82
94.23
93.03
84.68
91.40
93.62
90.95
94.59
92.58
94.22
88.45
94.40
92.16
Table 5: LAS scores on the test sets of 12 languages in UD. Our method with an order dimension of K achieves competitive performance in all languages, being state-of-the-art languages and average.
J Qualitative Examples
We present some qualitative examples from the PTB development set and one non non-projective example using our method with a 2-dimensional realizer, with their ground truth annotations on the right in Figures 4-9. For a more intuitive and compact exhibition, we plot the 2 total orders output by our model in 2- 2-dimensional plane. Each axis corresponds
of the 2 orders. The relation x < encoded by A (k) (x:) < f (u) is equivalent to being located below and to the left of y. Tokens V and 1/b are represented by x and respectively. The line segments between x and are the extracted dependency relations. In each of the plots, every x (token in V") except for the root is connected to a (token in /\),, which indicates x is the modifier of o The roots (about, moving, ready, had, adds, bought represented by x) are not connected to any other word.

---

works
30
20
ddvrtising see
10
advertising
0
ksr
about'
-10-
to
about
-2
see re AF
-30
We'
20
40
We 're about to see if advertising works
Figure 4: We 're about to see if advertising works
20
1aster
even even
moving
moving
faster
-2
page
they*
-00
mme
This
-60
RAB Had
0
20
40
60
80
This time around they 're moving even faster
Figure S: This time around, they 're moving even faster
0
ready
ready
tine were
-20
firms
40
the the
time
This
-80
This
20
40
60
80
100
This time
the firms
ready
Figure 6; This time the firms ready

---

of
a ahead
40
Lime
time
F
about
20
think'
it
0
had
to
had
WR
Ne'
-0
-20
0
20
40
We had to think about ahead of time
Figure 7: We had to think about it ahead of time
revisited
1987'
10
0
syisited
adds'
isn This -10-
adds
-20
29pte
-30-
He
20
40
He adds
This isn
1987 revisited
Figure 8: He adds, " This isn 1987 revisited
bought
0
bought
-10
John yesterday
John'
-20
regar'
-30
yesterday
-40
which is'
usich
10
20
30
40
John bought yesterday which red
Figure 9; A sentence with projective dependency structure: John bought yesterday which is red


Reviews:
[{"review_id": "iFJYOoGCMO", "reviewer": "Reviewer_JosL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "We appreciate the reviewer for the valuable feedback.   \nWe have corrected the typos. In the revised manuscript, we will improve the clarity and rigor of the definitions of concepts.", "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": "This paper is quite convincing, and its approach is nothing like anything I've seen before in the structured prediction literature.", "reasons_to_reject": "I see no red flags here.", "questions_to_authors": "", "paper_topic_and_main_contributions": "They explore a different paradigm for building structured prediction systems. Rather than directly learning a quadratic mapping where the domain is the spans of an input sentence, they leverage results from the mathematical literature about partial and total orders to express structured prediction problems using a more tractable representation. First, they observe that many structured prediction problems can be expressed as a partial ordering of vertices of a bipartite graph (a so-called \"token-split structure\"), where each token has one vertex in each partition. Then, they leverage literature that shows that partial orders can always be represented as an intersection of total orders, and observe that for many structure prediction tasks, the relevant partial orders can be represented as an intersection of 2 total orders.\n\nFrom here, they realize that this means we can train structured prediction models by having a neural network learn total orders whose intersection is the partial order corresponding to the structure. The results (on dependency parsing and coref resolution) are strongly competitive with state-of-the-art approaches. However, the representations are linear (rather than quadratic or worse) in the sentence length, and thus asymptotically more efficient.", "excitement": 5, "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": "Sec 2: Not sure you strictly need a reference for the fact that the space of real numbers is infinite.\nFootnote 1: A homogeneous relation on a set X is a binary relation over element pairs of X?\nDef 4.5: I feel like the statement of the definition could be improved.\nDef 4.9: I wouldn't put \"The intersection of tosets is a poset\" as part of definition. It doesn't seem definitional.\nDef 4.11: \"a set of toset\" => \"a set of tosets\"\n"}}, {"review_id": "D6oS2lMbYK", "reviewer": "Reviewer_esuW", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "We thank the reviewer for the valuable feedback. We will carefully address the concerns in the revised manuscript.    \nSpecifically, regarding the suggested references, we will include (Shen et al., 2018ab [6,7]) in the related work section and further discuss the usage of “learning-to-rank” style losses for structured prediction.", "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": "- This paper demonstrates excellent writing, as seen in Section 3 Motivating Example, which immediately conveys the key idea to the reader.\n\n- The paper is built on a solid theoretical foundation and presents an elegant approach.\n\n- The proposed model has wide applicability across various NLP structured prediction tasks. The authors thoroughly evaluate their elegant model in two significant tasks: dependency parsing and coreference resolution, achieving competitive or even state-of-the-art performance.\n\n\n\n\n", "reasons_to_reject": "None that I can see.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This research aims to address the challenges of time and space complexity in NLP structured prediction problems. The authors propose an elegant linear-time-and-space algorithm that utilizes the partial order of a string. They demonstrate that by intersecting multiple total orders, the desired structures of interest, including important NLP structures like set partitions, trees, and alignments, can be recovered.\n\nAdditionally, the authors use neural networks to parameterize posets/total orders and introduce a \"learning-to-rank\"-like loss function for training. This approach leads to competitive or state-of-the-art performance in two classic NLP structured prediction tasks: dependency parsing and coreference resolution.\n\n\n\n\n", "excitement": 5, "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": {"Missing_References": "In section 5.2, since the proposed loss function bears resemblance to the 'pairwise learning-to-rank loss', it would be beneficial to include some discussions in the related work section. Additionally, I would like to mention a previous work that utilized the 'learning-to-rank' loss for constituency parsing (Straight to the Tree: Constituency Parsing with Neural Syntactic Distance, https://aclanthology.org/P18-1108.pdf). \n\n\n\n\n"}}, {"review_id": "94U6cVCCSh", "reviewer": "Reviewer_uTtf", "summary": "", "questions": "As mentioned above: if there is a theoretical guarantee that k=2 is enough for trees, why does k=4 perform better? And if k=4 performs better (regardless of the reason), why not make it even larger?", "limitations": "", "rating": 5, "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": "We appreciate the reviewer for the valuable feedback, which we believe will greatly improve our paper. We address the concerns in the review and propose revisions to our paper regarding them below.\n\n1. Regarding the suggested references in Sec. 2 and Sec. 7:  \n    *  We will extend Sec. 2 with more thorough literature by including the suggested references on linearizing dependency trees (Strzyz et al., 2020 [5]). \nIn Sec. 7, we will further discuss the line of work on the multiplanarity of dependency trees (Yli-Jyrä, 2003 [9]; Gómez-Rodríguez & Nivre, 2010 [3]; Strzyz et al., 2020 [5]; inter alia) and its relevance to our work.    \n    *  We will add a new subsection in Sec. 7 discussing the usage of “learning-to-rank” and the mapping between real number sequences and structures (Shen et al., 2018ab [6,7]).\n\n\n2. Regarding the experiment on PTB with gold POS tags:  \n    *  In our experiment, we reproduced (Mrini et al., 2020) using the released script which might not be in accord with the paper in some detail. Specifically, https://github.com/KhalilMrini/LAL-Parser/blob/master/src_joint/dep_reader.py#L67 takes the 5th column from a CoNLL-U formatted PTB as input, which corresponds to the language-specific POS tag (XPOS) [1] rather than predicted POS tag. We used the **same [PTB data](https://github.com/KhalilMrini/LAL-Parser/tree/master/data)** as the repo of (Mrini et al., 2020) and the **same columns** as model inputs in the experiments in Table 1, and achieved comparable or better performance.   \nWhen not using any POS tags on PTB, our model gets 95.5 LAS, 97.1 UAS using $k=2$, 95.7 LAS, 97.3 UAS using $k=4$, which is also comparable with the SOTA without POS tags. In the revised version, we will report dependency parsing results with both gold tags and no tags and further clarify the experimental settings.  \n    *  In addition, we will also cite the suggested references (Yasunaga et al., 2018 [8]; Anderson and Gómez-Rodríguez, 2020 [1]) and include discussions on the possible impact of using or not using gold POS tags.\n\n3. Regarding order dimension $ k $:  \n    *  Consider modeling a tree structure with $N$ nodes with $N-1$ arcs using partial order, which implies $ N - 1 $ constraints of the form $ x \\prec y’$ and $ N^2 -2N+1 $ constraints of $ x \\nprec y’ $.  \nFrom a theoretical perspective, $k = 2$ is sufficient to represent such a structure as shown in Sec. 4. I.e., there always exist 2 total orders whose intersection satisfies the aforementioned $N(N-1)$ constraints. However, it might not be the easiest to learn with a limited number of training data.    \n&nbsp;  \nIncreasing $k$ beyond 2 can **facilitate the satisfaction of constraints**, especially of the form $x \\nprec y’$---since there are more constraints in this form. It allows more possibilities for $\\bigvee_{i\\in [k]} f_i(x) \\ge f_i(y’)$ (i.e., more choices of $i$ to satisfy the expression). We conclude that this accounts for the increase in performance when increasing $k$ from 2 to 4.   \nIn our preliminary experiments, we found using $k > 4$ does *not* bring improvements to dependency parsing, and only brings *marginal* improvements to coreference resolution, from 79.2 F1 ($k=4$) to 79.6 F1 ($k=8$). Thus, we did not choose $k$ that is greater than 4. \n    *  In the revised version, we will include a discussion on how both theoretical and practical factors affect the performance of a parser. Furthermore, we will extend the “Hardness of Learning” subsection in the Limitations by including the above example.  \n\n4. Regarding suggestions on improvements for presentation\n    *  We have carefully corrected the typos.   \n    *  We will restructure the experimental settings by moving important details to the main text to improve clarity. The first column of Table 2 refers to the set of sentences of the lengths.\n    *  We will include non-projective sentences from the **UD** dataset as qualitative examples in App. J, as the versions of PTB and CTB we use for evaluation are projective.\n\n\n\n[1] https://universaldependencies.org/format.html  \n[2] Mark Anderson and Carlos Gómez-Rodríguez. 2020. On the Frailty of Universal POS Tags for Neural UD Parsers.  \n[3] Carlos Gómez-Rodríguez and Joakim Nivre. 2010. A Transition-Based Parser for 2-Planar Dependency Structures.  \n[4] Carlos Gómez-Rodríguez and Joakim Nivre. 2013. Divisible Transition Systems and Multiplanar Dependency Parsing.  \n[5] Michalina Strzyz, David Vilares, and Carlos Gómez-Rodríguez. 2020. Bracketing Encodings for 2-Planar Dependency Parsing.  \n[6] Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio. 2018. Straight to the Tree: Constituency Parsing with Neural Syntactic Distance.  \n[7] Yikang Shen, Zhouhan Lin, Chin-wei Huang, and Aaron Courville. 2018. Neural Language Modeling by Jointly Learning Syntax and Lexicon.   \n[8] Michihiro Yasunaga, Jungo Kasai, and Dragomir Radev. 2018. Robust Multilingual Part-of-Speech Tagging via Adversarial Training.  \n[9] Anssi Mikael Yli-Jyrä. 2003. Multiplanarity - a model for dependency structures in treebanks.", "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 contribution of the paper is highly original, proposing a generic method that can be applied to various structured prediction problems and, as far as I know, differs from the existing approaches in the literature.\n\nThe method works well empirically, as shown in the experiments. This is not only in terms of accuracy, but it is also very efficient.\n\nThe paper establishes interesting connections to parts of the discrete mathematics literature that are not well-known by the NLP community, while being clearly written and understandable without prior exposure to that literature.", "reasons_to_reject": "Dependency parsing experiments are done with gold PoS tags. This makes the comparison in Table 1 misleading, as most of the parsers included there use predicted PoS tags. For example, from a quick look at Table 1 it would seam that the k=4 system is tied with Mrini et al., but Mrini et al. uses predicted PoS tags. The advantage gained from using gold with respect to predicted PoS tags is well attested in the literature (Yasunaga et al., 2018, yasunaga-etal-2018-robust; Anderson and Gómez-Rodríguez, 2020, anderson-gomez-rodriguez-2020-frailty)\n\nOne aspect is unclear: according to Propositions 4.16 and 4.17, trees and forests can be represented as intersections of only two posets. Therefore, k=2 should be enough for full-coverage dependency parsing. However, experiments are made with k=2 and k=4, with k=4 obtaining better results. Why does this happen? If k=2 is sufficient, one wouldn't expect introducing extra complexity into the model should be beneficial.", "questions_to_authors": "As mentioned above: if there is a theoretical guarantee that k=2 is enough for trees, why does k=4 perform better? And if k=4 performs better (regardless of the reason), why not make it even larger?", "paper_topic_and_main_contributions": "This paper presents a new approach to structured prediction problems in NLP whose output is in the form of a directed graph. The method is based on representing the directed graph as a partial order on a \"token-split\" set (a set where each input token is included twice, once as a potential source of outgoing arcs and once as a target of incoming arcs). This partial order can, in turn, be represented as the intersection of k total orders (in particular, for the cases of trees and forests, it is shown by referring to order-theoretic results that k=2 is enough). To use this in practice, a neural model is trained to generate 2k real numbers per token. These numbers uniquely determine the k total orders for the token-split set, and thus can be used to recover the tree or forest. Experiments are performed on dependency parsing and coreference resolution, showing competitive results and remarkable efficiency.", "excitement": 5, "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": {"Justification_for_Ethical_Concerns": "N/A"}, "extra_text": {"Missing_References": "I found the framing in Section 2 somewhat narrow. Some linearization schemes are cited, and then lack of coverage is mentioned as a drawback. But this is because the particular approaches that are cite are those that prioritize compactness over coverage (they have a constant time number of tags, but are limited to projective trees/continuous constituency trees). There are other linearization approaches with the converse priority which are not cited, e.g. (Strzyz et al., 2020, strzyz-etal-2020-bracketing) or some of the encodings in the papers cited in Section 7.3, it seems like both kinds should be mentioned, especially given the fact that the coverage vs. compactness tradeoff is explicitly mentioned in said Section 2.\n\nAnother paper that I believe should be cited is (Shen et al., 2018, shen-etal-2018-straight): although their method does not seem related to this one, it has in common that a parse tree is represented via a sequence of real numbers.", "Typos_Grammar_Style_and_Presentation_Improvements": "In Table 2, the exact meaning of #token is unclear: I suppose it refers to sentence length, but what exactly: the set of sentences of exactly that length, the set of sentences with length <= that, buckets [1,32], [33, 64]...?\n\nline 273: missing \"such\" in \"such that\"\n\nline 486: missing s in \"linear projections\"\n\nline 676: \"empirical experiments\" is redundant\n\nline 1193: redundancy \"set... is set to\"\n\nSince the method supports non-projective trees, it would be nice to include a non-projective tree example in Appendix J. \n\nIn the experimental section, the UD treebanks used and the hardware used in the efficiency measures should be moved to the main text; apart from being clear about the use of gold PoS tags and its impact in comparisons as mentioned above."}}]

Author rebuttal:

Meta-review: This paper presents an original, efficient, and state-of-the-art (SOTA) paradigm for computing structured representations of natural language inputs. The work uses the concept of a partial order of a string to represent the relations in a bipartite graph. In particular, the authors propose that by generating several total orders of the string and combining them, they can recover the desired relations in the output graph. The study initially introduces a robust and engaging theoretical demonstration of the foundational aspects of the approach. Subsequently, it implements a functional neural model that achieves highly impressive results in the domains of dependency parsing and coreference resolution. 

There is unanimous consensus among the reviewers regarding the acceptance of this paper. They clearly acknowledge its novelty and significance within the field. It's an elegant approach with a strong theoretical foundation and wide applicability across various NLP tasks and structured prediction problems, making it a standout contribution.

The reviewers suggest minor changes, including providing a more comprehensive overview of the related previous work, along with other minor technical suggestions, which can be easily addressed in the camera-ready version of the paper.
Decision: Accept-Main