Scaling Graph-Based Dependency Parsing with Arc Vectorization and Attention-Based Refinement
Nicolas Floquet, Joseph Le Roux, Nadi Tomeh, Thierry Charnois · 2025
Read Scaling Graph-Based Dependency Parsing with Arc Vectorization and Attention-Based Refinement by Nicolas Floquet, Joseph Le Roux, Nadi Tomeh, Thierry Charnois (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-09451.txt.
Introduction
Floquet, Le Roux, Tomeh, and Charnois present a new design for graph based dependency parsing, the task of mapping how words in a sentence depend on each other. Standard parsers score word links and their labels in two separate stages, which can bottleneck the flow of information. Their 2025 paper merges both steps into a single network.
The design builds explicit vectors for each possible word link, and both the link and its label are scored from those vectors. Added transformer layers let links interact, which mimics higher order patterns between words. Tests on two standard datasets, PTB and UD, show the model beating top parsers on both accuracy and speed.
Catalog record
| CREATOR | Nicolas Floquet, Joseph Le Roux, Nadi Tomeh, Thierry Charnois |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-09451
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scaling Graph-Based Dependency Parsing with Arc Vectorization and Attention-Based Refinement Nicolas Floquet, Joseph Le Roux, Nadi Tomeh, Thierry Charnois Abstract We propose a novel architecture for graph-based dependency parsing that explicitly constructs vectors, from which both arcs and labels are scored. Our method addresses key limitations of the standard two-pipeline approach by unifying arc scoring and labeling into a single network, reducing scalability issues caused by the information bottleneck and lack of parameter sharing. Additionally, our architecture overcomes limited arc interactions with transformer layers to efficiently simulate higher-order dependencies. Experiments on PTB and UD show that our model outperforms state-of-the-art parsers in both accuracy and efficiency. 1 Introduction Recent graph-based dependency parsers have adopted a standard architecture ( Kiperwasser and Goldberg, 2016 ; Dozat and Manning, 2017 ) extended by Zhang et al. (2020) . These models consist of two-pipelines: one pipeline scores arcs, and the other scores their labels. Each pipeline uses independent models to generate specialized head and dependent representations from word embeddings, followed by a biaffine scoring model. We investigate the scalability of this widely-used architecture. Our motivation stems from the observation that not all model architectures scale efficiently with increased parameters. For example, transformer-based language models exhibit predictable scaling laws, where performance consistently improves with more parameters ( Kaplan et al., 2020 ) . In contrast, other architectures, e.g . CNNs, require careful scaling across multiple dimensions ( Tan and Le, 2019 ) . Similar observations have been made in computer vision ( Dosovitskiy et al., 2021 ) . Our empirical results show that simply increasing the number of parameters in the standard parsing model does not improve performance. We hypothesize that the core issue lies in the indirect representation of arcs. The model encodes the entire space of possible arcs through word vectors and biaffine scoring, which limits its ability to handle increased complexity. Furthermore, using two scoring networks restricts information flow between arc selection and labeling tasks. We propose a novel architecture that explicitly constructs vector representations for each arc. By unifying arc scoring and labeling tasks within a single network, our approach enables more effective parameter sharing and enhances scalability. Additionally, to facilitate interaction between arc representations and efficiently simulate higher-order models, we employ transformer layers augmented with a differentiable filtering mechanism. This design captures dependencies between arcs while maintaining computational and memory efficiency. 2 Model 2nd Order Extension Refinement Loc and CRF2o s_{ij}\in\mathbb{R} {\bm{l}}_{ij}\in\mathbb{R}^{\mathcal{L}} s_{ijk}\in\mathbb{R} Biaffine {\bm{M}}\in\mathbb{R}^{a\times a} Biaffine {\bm{\mathsfit{L}}}\in\mathbb{R}^{c\times\mathcal{L}\times c} Triaffine {\bm{\mathsfit{C}}}\in\mathbb{R}^{d\times d\times d} Arc H Arc M Rel H Rel M Sib H Sib M Sib S Contextual Embedding \dots\quad w_{j}\quad\dots \ldots\quad w_{i} w_{k}\quad\ldots {\bm{h}}_{i}\in\mathbb{R}^{a} {\bm{m}}_{j}\in\mathbb{R}^{a} {\bm{h}}_{i}\in\mathbb{R}^{c} {\bm{m}}_{j}\in\mathbb{R}^{c} {\bm{h}}_{i}\in\mathbb{R}^{d} {\bm{m}}_{j}\in\mathbb{R}^{d} {\bm{s}}_{k}\in\mathbb{R}^{d}\quad {\bm{e}}_{i}\in\mathbb{R}^{b} {\bm{e}}_{j}\in\mathbb{R}^{b} {\bm{e}}_{k}\in\mathbb{R}^{b} ArcLoc P T s_{ij}\in\mathbb{R} {\bm{l}}_{ij}\in\mathbb{R}^{\mathcal{L}} Arc Scoring MLP Rel Scoring MLP P\times Transformer Layers Biaffine {\bm{\mathsfit{R}}}\in\mathbb{R}^{d\times r\times d} Head MLP Mod MLP Contextual Embedding \dots \ldots\quad w_{i} w_{j}\quad\ldots {\bm{e}}_{i}\in\mathbb{R}^{b}\quad \quad{\bm{e}}_{j}\in\mathbb{R}^{b} {\bm{v}}^{P}_{ij}\in\mathbb{R}^{r} {\bm{v}}^{0}_{ij}\in\mathbb{R}^{r} {\bm{h}}_{i}\in\mathbb{R}^{d}\quad \quad{\bm{m}}_{j}\in\mathbb{R}^{d} Figure 1: Illustration of both models. Left: standard model with 2 (resp. 3) pipelines for Loc (resp. CRF2O ) with shared word embeddings. Right: our proposal with a single pipeline and optionally P transformers. We review the standard biaffine parser (Figure 1 , left) and then highlight the key differences of our arc-centric approach (Figure 1 , right). Prior to parsing, from an input sentence x_{0}x_{1}\dots x_{n} , where x_{0} is the dummy root and \forall 1\leq i\leq n , x_{i} corresponds to the i^{\text{th}} token of the sentence, models start by computing contextual embeddings {\bm{e}}_{0},{\bm{e}}_{1},\dots,{\bm{e}}_{n} . This can be implemented in various ways, e.g . with averaged layers from pretrained dynamic word embeddings. These contextual embeddings are further specialized for head and modifier roles using two feed-forward (FFN) transformations. This results in two sets of word representations, {\bm{h}}_{0},{\bm{h}}_{1},\dots,{\bm{h}}_{n} for heads and {\bm{m}}_{0},{\bm{m}}_{1},\dots,{\bm{m}}_{n} for modifiers. 2.1 Standard Model We present the local and first-order models as introduced in Dozat and Manning (2017) and refer readers to Zhang et al. (2020) for higher-order extensions. The first-order scoring function decomposes the score of a parse tree as the sum of the scores of its arcs, if they form a valid tree ( i.e . rooted in x_{0} , connected and acyclic) and can be implemented as a CRF where arc variables are independently scored but connected to a global factor asserting well-formedness constraints. This CRF can be trained efficiently and inference is performed with well-known algorithms. Still, learning imposes to compute for each sentence its partition , the sum of the (exponentiated) scores of all parse candidates. While being tractable, this is an overhead compared to computing arc scores independently without tree-shape constraints. Hence, several recent parsers, e.g . Dozat and Manning (2017) which called this model local , simplify learning by casting it as a head-selection task for each word, i.e . arc score predictors are trained without tree constraints. In all cases, tree CRF or head selection, evaluation is performed by computing the optimal parse Eisner (1997) ; Tarjan (1977) . Arc Scores are computed by a biaffine function: 1 1 1 We ignore bias for the sake of notation. for arc x_{i}\to x_{j} , Dozat and Manning (2017) set arc score to s_{ij}={\bm{h}}_{i}^{\top}{\bm{M}}{\bm{m}}_{j} with trainable {\bm{M}} . For embeddings of size d , {\bm{M}} has dimensions d\times d . Arc Labeling is considered a distinct task: at training time arc labeling has its own loss and at prediction time most systems use a pipeline approach where first a tree is predicted, and second each predicted arc is labeled. 2 2 2 We remark that Zhang et al. (2021) learn the two separately and merge them at prediction time. Labeling is also implemented with a biaffine: for arc x_{i}\to x_{j} , the label logit vector is {\bm{l}}_{ij}={{\bm{h}}_{i}}^{\top}{\bm{\mathsfit{L}}}{\bm{m}}_{j} , with trainable {\bm{\mathsfit{L}}} . For word vectors of size d and for a system with \mathcal{L} possible arc labels, {\bm{\mathsfit{L}}} has dimension d\times\mathcal{L}\times d . While we noted them {\bm{h}} and {\bm{m}} , these specialized word embeddings are given by FFNs different from the ones used for arc scores. This model relies on two biaffine functions, one for arc scores returning a scalar per arc, and one for labelings returning for each arc a vector of label scores. Parameter sharing between them is limited to word embeddings {\bm{e}} . 2.2 Single Pipeline Model Our models differ architecturally in two ways: (i) an intermediate vector representation is computed for each arc and (ii) both arc and labeling scores are derived from this single arc representation. For arc x_{i}\to x_{j} we compute vector representation {\bm{v}}_{ij} . Again, we use a biaffine function outputting a vector similarly to arc labeling in standard models: {\bm{v}}_{ij}={\bm{h}}_{i}^{\top}{\bm{\mathsfit{R}}}{\bm{m}}_{j} for a trainable tensor {\bm{\mathsfit{R}}} with dimensions d\times r\times d , where r is the size of the arc vector representation {\bm{v}}_{ij} , and is a hyperparameter to be fixed, as is the word embedding size. We recover arc score s_{ij} and arc labeling {\bm{l}}_{ij} from {\bm{v}}_{ij} by FFNs: s_{ij}=F_{s}({\bm{v}}_{ij}) and {\bm{l}}_{ij}=F_{l}({\bm{v}}_{ij}) . Note that there is only one biaffine function, and one specialization for head and modifiers. Finally, remark that this change does not impact the learning objective: parsers are trained the same way. 2.3 Refining with Attention Arc vectors obtained as above can read information from sentence tokens via contextual embeddings.