Enhancing the Transformer Decoder with Transition-based Syntax

a Transformer decoder that generates a dependency tree as a sequence of parser transitions and re-encodes the tree it has built so far

Leshem Choshen, Omri Abend · CoNLL 2022 · 2022

• arXiv
• PDF
• HTML
• Hugging Face
• alphaXiv
• DOI
• ACL Anthology
• Semantic Scholar
• Publisher
• Code

In one sentence

A Transformer decoder that emits its output's Universal Dependencies tree as a sequence of arc-standard transitions and re-encodes the partially built graph — via a GCN or a dedicated parent-attention head — together with bidirectional attention over already-predicted tokens.

Abstract

Notwithstanding recent advances, syntactic generalization remains a challenge for text decoders. While some studies showed gains from incorporating source-side symbolic syntactic and semantic structure into text generation Transformers, very little work addressed the decoding of such structure. We propose a general approach for tree decoding using a transition-based approach. Examining the challenging test case of incorporating Universal Dependencies syntax into machine translation, we present substantial improvements on test sets that focus on syntactic generalization, while presenting improved or comparable performance on standard MT benchmarks. Further qualitative analysis addresses cases where syntactic generalization in the vanilla Transformer decoder is inadequate and demonstrates the advantages afforded by integrating syntactic information.

Questions this paper answers

can a translation model build a grammar tree of its own output while it writes the sentence?

how is a transition-based dependency parser embedded in a Transformer decoder for target-side syntax?

how do I make a Transformer decoder emit a dependency tree together with the translated sentence?

if I want target-side syntax in my Transformer NMT system, do I still need an RNN or a linearized tree?

Choshen and Abend's transition-based structural decoder generates target-side syntactic trees inside a Transformer decoder, rather than with an RNN or a string linearization as earlier target-side tree decoding did.
Holds for: As of publication in 2022; the authors state they are not aware of a prior Transformer architecture supporting target-side tree or graph structure.

The transition-based decoding framework of Choshen and Abend generates any graph structure for which a transition system exists, with Universal Dependencies via arc-standard used as the demonstrated machine-translation test case.
Holds for: Only projective UD parses were trained on and only UD was evaluated; fit to semantic formalisms is argued from the existence of their transition parsers, not measured.

does making a translation system aware of grammar on the output side help with the hard sentences?

do syntax-aware decoders improve accuracy on long-distance dependency and particle challenge sets in NMT?

how do I get a translation model to handle separable verb particles and long-range agreement correctly?

my model keeps dropping German verb particles and misplacing distant dependents, would target-side syntax fix that?

On the Choshen and Abend syntactic challenge sets, the medium Parent decoder improves over the vanilla Transformer in 18 of 20 target settings and 19 of 20 source settings. The medium GCN decoder improves in 20 of 20 target and 19 of 20 source settings.
Holds for: 4-layer, 256-dim models on En-De and De-En, WMT16 data; settings count BLEU and chrF+ on preposition-stranding, particle and reflexive phenomena in books and news domains, with training parses from UDPipe.

On the En-De target-side particle challenge set from books, the large Parent decoder reaches 8.37 BLEU and 33.78 chrF+ against the vanilla Transformer's 4.14 BLEU and 20.72 chrF+.
Holds for: One challenge set: En-De, target side, particle verbs, books domain, 6-layer models; the largest single gap reported among the challenge sets.

if I train a bigger translation model, does it learn the grammar it was missing anyway?

does the syntactic generalization gap between structure-aware and vanilla Transformer decoders close at 6 layers?

how do I close a grammar-generalization gap in translation, more layers or explicit target-side structure?

should I spend my compute on scaling my Transformer up rather than adding a syntactic decoder?

Scaling to a 6-layer model does not close the syntactic-generalization gap. The large Parent decoder still beats the vanilla Transformer in 18 of 20 challenge settings, with gains similar to or larger than at medium size.
Holds for: En-De only, 6 decoder/encoder blocks, embedding size 512, 150K training steps; only Parent and Vanilla were trained at this size, GCN was not.

At 6 layers on En-De the Parent decoder is only comparable to the vanilla Transformer on standard test sets, averaging 22.12 BLEU and 52.34 chrF+ against 22.39 BLEU and 52.47 chrF+. The same large Parent model still wins clearly on the syntactic challenge sets.
Holds for: En-De, newstest 2013-15, one large model per condition; Parent is ahead on 2013 and 2014 chrF+ and behind on 2015. No large GCN and no other language pair at this size.

does adding grammar to the output side cost anything on ordinary translation quality scores?

what BLEU and chrF+ do UD-based GCN and parent-attention decoders reach on newstest 2013-15 versus a vanilla Transformer?

how do I check whether a syntax-aware decoder hurts general translation quality before shipping it?

will switching to a syntactic decoder lower my BLEU on standard news test sets?

On newstest 2013-15 the UD-based GCN and Parent decoders beat the vanilla Transformer at medium size in every setting tested, by 0.7-1.1 average BLEU and 1-2.4 chrF+, on En-De, De-En and En-Ru.
Holds for: 4-layer models; En-De and De-En from WMT16, En-Ru from clean News Commentary. A sign test over the medium test sets finds GCN and Parent significantly better than vanilla.

At 6 layers on En-De the Parent decoder is only comparable to the vanilla Transformer on standard test sets, averaging 22.12 BLEU and 52.34 chrF+ against 22.39 BLEU and 52.47 chrF+. The same large Parent model still wins clearly on the syntactic challenge sets.
Holds for: En-De, newstest 2013-15, one large model per condition; Parent is ahead on 2013 and 2014 chrF+ and behind on 2015. No large GCN and no other language pair at this size.

is it enough to write the grammar into the output as extra tokens, or does the model have to read the structure back?

how does training on linearized transition sequences compare with re-encoding the generated graph in the decoder?

how do I decide between linearizing a parse into the target string and feeding the built graph back into the decoder?

can I skip the graph machinery and just train on a linearized parse string instead?

Training a vanilla Transformer on the linearized transition string lands consistently between the structure-unaware and the structure-aware decoders, showing that re-encoding the generated graph adds beyond merely emitting it as tokens.
Holds for: En-De and De-En medium models on newstest 2013-15 and the challenge sets; differences between ablations are described as small but consistent.

when a translation model reads back the tree it just built, which parts of that actually matter?

in a graph-convolutional decoder over self-generated dependencies, how much do gating and edge labels each contribute?

how do I trim a graph-convolutional syntactic decoder without losing its syntactic accuracy?

can I drop the dependency edge labels or the gates from my GCN decoder to save parameters?

Removing GCN gating hurts: the ungated variant scores below the unlabeled variant in 34 of 40 challenge settings. Dropping edge labels from the GCN has limited effect, and the unlabeled variant is as often as not better on the challenges.
Holds for: Medium GCN decoders on En-De and De-En, encoding the decoder's self-generated parse rather than an external one. Labels remain available as transition token embeddings even in the unlabeled GCN.

does letting a translation decoder look at words it has already guessed further ahead help at all?

what does bidirectional decoder self-attention over already-predicted tokens buy over a causal Transformer decoder, with no syntax?

how do I get a small translation gain without extra parameters or syntactic annotation?

is bidirectional attention in my decoder worth turning on if I add no syntax at all?

Bidirectional attention in the decoder alone (BiTran), with no syntax and no new parameters, gives a small but consistent gain over the vanilla Transformer of up to 0.28 BLEU and 0.42 chrF+. BiTran is better on 10 of 12 test scores per language pair and on 26 of 40 challenge settings.
Holds for: Medium models on En-De, De-En and En-Ru; adds no parameters or hyperparameters but blocks unidirectionality-based decoding speed-ups implemented in NEMATUS.

do the benefits of grammar-aware translation survive when the training data is scraped from the web and messy?

does the chrF+ advantage of UD-based decoders hold when training English-Russian on full noisy crawled WMT20 data?

how do I know whether a syntax-aware decoder will still help if all I have is noisy crawled parallel text?

my only English-Russian data is noisy crawl, should I still expect a gain from a syntactic decoder?

Training En-Ru on the full noisy crawled WMT20 data shrinks the syntactic decoders' chrF+ advantage to about 1 point, against 1.5-2.5 points on cleaner data. BLEU becomes somewhat worse than with clean training data.
Holds for: En-Ru only, medium models, full WMT20 data after langID and alignment filtering versus clean News Commentary; described as preliminary, with more data rather than noise named as an alternative explanation.

can translation systems tell who did what to whom in German when the sentence puts the object first?

is a parent-attention decoder more robust than a vanilla Transformer on German OVS order with ambiguous case marking?

how do I test whether my German translations get subject-object roles right when word order is reversed?

my German output swaps subject and object on unusual word orders, would target-side syntax help?

On 99 hand-built German subject-verb-object sentences whose arguments can swap, the Parent decoder is more robust to the rare OVS order than the vanilla Transformer. A native-speaker annotator scored 13 vs 10 correct with both cases marked, 8 vs 5 with only the subject marked and 6 vs 6 with only the object marked.
Holds for: Medium En-De models, 99 templated sentences over small noun and verb lists, one annotator; only word-order correctness was scored, with other errors such as verb choice disregarded.

where should I start reading about generating grammar structure along with text, rather than parsing the input?

which work covers transition-based tree decoding for structure-aware generation instead of source-side syntax in NMT?

how do I find prior work on decoders that generate graphs and text jointly?

Choshen and Abend's transition-based structural decoder generates target-side syntactic trees inside a Transformer decoder, rather than with an RNN or a string linearization as earlier target-side tree decoding did.
Holds for: As of publication in 2022; the authors state they are not aware of a prior Transformer architecture supporting target-side tree or graph structure.

The transition-based decoding framework of Choshen and Abend generates any graph structure for which a transition system exists, with Universal Dependencies via arc-standard used as the demonstrated machine-translation test case.
Holds for: Only projective UD parses were trained on and only UD was evaluated; fit to semantic formalisms is argued from the existence of their transition parsers, not measured.

what is the better way for a translation model to reuse the tree it built, a graph network or a single attention head to the parent word?

how do GCN-based and parent-attention graph re-encoding compare on challenge sets and newstest BLEU in a syntactic decoder?

how do I choose between a graph convolution and parent attention for re-encoding a decoder's own dependency tree?

which re-encoding variant should I implement first for a syntactic decoder, the GCN or the parent head?

On the Choshen and Abend syntactic challenge sets, the medium Parent decoder improves over the vanilla Transformer in 18 of 20 target settings and 19 of 20 source settings. The medium GCN decoder improves in 20 of 20 target and 19 of 20 source settings.
Holds for: 4-layer, 256-dim models on En-De and De-En, WMT16 data; settings count BLEU and chrF+ on preposition-stranding, particle and reflexive phenomena in books and news domains, with training parses from UDPipe.

On newstest 2013-15 the UD-based GCN and Parent decoders beat the vanilla Transformer at medium size in every setting tested, by 0.7-1.1 average BLEU and 1-2.4 chrF+, on En-De, De-En and En-Ru.
Holds for: 4-layer models; En-De and De-En from WMT16, En-Ru from clean News Commentary. A sign test over the medium test sets finds GCN and Parent significantly better than vanilla.

Removing GCN gating hurts: the ungated variant scores below the unlabeled variant in 34 of 40 challenge settings. Dropping edge labels from the GCN has limited effect, and the unlabeled variant is as often as not better on the challenges.
Holds for: Medium GCN decoders on En-De and De-En, encoding the decoder's self-generated parse rather than an external one. Labels remain available as transition token embeddings even in the unlabeled GCN.

Claims and scope

• Choshen and Abend's transition-based structural decoder generates target-side syntactic trees inside a Transformer decoder, rather than with an RNN or a string linearization as earlier target-side tree decoding did.
  Scope: As of publication in 2022; the authors state they are not aware of a prior Transformer architecture supporting target-side tree or graph structure.
• The transition-based decoding framework of Choshen and Abend generates any graph structure for which a transition system exists, with Universal Dependencies via arc-standard used as the demonstrated machine-translation test case.
  Scope: Only projective UD parses were trained on and only UD was evaluated; fit to semantic formalisms is argued from the existence of their transition parsers, not measured.
• On the Choshen and Abend syntactic challenge sets, the medium Parent decoder improves over the vanilla Transformer in 18 of 20 target settings and 19 of 20 source settings. The medium GCN decoder improves in 20 of 20 target and 19 of 20 source settings. (Table 1 and Section 6.1)
  Scope: 4-layer, 256-dim models on En-De and De-En, WMT16 data; settings count BLEU and chrF+ on preposition-stranding, particle and reflexive phenomena in books and news domains, with training parses from UDPipe.
• Scaling to a 6-layer model does not close the syntactic-generalization gap. The large Parent decoder still beats the vanilla Transformer in 18 of 20 challenge settings, with gains similar to or larger than at medium size. (Section 6.1, Tables 4 and 6)
  Scope: En-De only, 6 decoder/encoder blocks, embedding size 512, 150K training steps; only Parent and Vanilla were trained at this size, GCN was not.
• On the En-De target-side particle challenge set from books, the large Parent decoder reaches 8.37 BLEU and 33.78 chrF+ against the vanilla Transformer's 4.14 BLEU and 20.72 chrF+. (Table 6)
  Scope: One challenge set: En-De, target side, particle verbs, books domain, 6-layer models; the largest single gap reported among the challenge sets.
• On newstest 2013-15 the UD-based GCN and Parent decoders beat the vanilla Transformer at medium size in every setting tested, by 0.7-1.1 average BLEU and 1-2.4 chrF+, on En-De, De-En and En-Ru. (Table 2 and Section 6.2)
  Scope: 4-layer models; En-De and De-En from WMT16, En-Ru from clean News Commentary. A sign test over the medium test sets finds GCN and Parent significantly better than vanilla.
• At 6 layers on En-De the Parent decoder is only comparable to the vanilla Transformer on standard test sets, averaging 22.12 BLEU and 52.34 chrF+ against 22.39 BLEU and 52.47 chrF+. The same large Parent model still wins clearly on the syntactic challenge sets. (Table 5)
  Scope: En-De, newstest 2013-15, one large model per condition; Parent is ahead on 2013 and 2014 chrF+ and behind on 2015. No large GCN and no other language pair at this size.
• Training a vanilla Transformer on the linearized transition string lands consistently between the structure-unaware and the structure-aware decoders, showing that re-encoding the generated graph adds beyond merely emitting it as tokens. (Section 6.3, Tables 2 and 9)
  Scope: En-De and De-En medium models on newstest 2013-15 and the challenge sets; differences between ablations are described as small but consistent.
• Removing GCN gating hurts: the ungated variant scores below the unlabeled variant in 34 of 40 challenge settings. Dropping edge labels from the GCN has limited effect, and the unlabeled variant is as often as not better on the challenges. (Section 6.3, Tables 7 and 8)
  Scope: Medium GCN decoders on En-De and De-En, encoding the decoder's self-generated parse rather than an external one. Labels remain available as transition token embeddings even in the unlabeled GCN.
• Bidirectional attention in the decoder alone (BiTran), with no syntax and no new parameters, gives a small but consistent gain over the vanilla Transformer of up to 0.28 BLEU and 0.42 chrF+. BiTran is better on 10 of 12 test scores per language pair and on 26 of 40 challenge settings. (Section 6.3, Tables 2, 7, 8 and 9)
  Scope: Medium models on En-De, De-En and En-Ru; adds no parameters or hyperparameters but blocks unidirectionality-based decoding speed-ups implemented in NEMATUS.
• Training En-Ru on the full noisy crawled WMT20 data shrinks the syntactic decoders' chrF+ advantage to about 1 point, against 1.5-2.5 points on cleaner data. BLEU becomes somewhat worse than with clean training data. (Section 6.4 and Table 10)
  Scope: En-Ru only, medium models, full WMT20 data after langID and alignment filtering versus clean News Commentary; described as preliminary, with more data rather than noise named as an alternative explanation.
• On 99 hand-built German subject-verb-object sentences whose arguments can swap, the Parent decoder is more robust to the rare OVS order than the vanilla Transformer. A native-speaker annotator scored 13 vs 10 correct with both cases marked, 8 vs 5 with only the subject marked and 6 vs 6 with only the object marked. (Table 3 and Section 6.5)
  Scope: Medium En-De models, 99 templated sentences over small noun and verb lists, one annotator; only word-order correctness was scored, with other errors such as verb choice disregarded.

Common misreadings

• Improving syntactic challenge sets did not translate into higher standard benchmark scores at every model size: at 6 layers on En-De the Parent decoder is only comparable to the vanilla Transformer on newstest 2013-15, while still winning on the challenge sets.
• The finding that dropping GCN edge labels barely changes results is not evidence that syntactic labels are useless: the labels still enter the model as transition token embeddings, and in this GCN they only affect a bias term.
• The structural decoder does not consume a parse produced by an external parser at inference time; it generates the dependency tree itself as transitions and conditions on the tree it has built. External UDPipe parses are used to create training targets.
• The syntactic decoders are not shown to be a universal win: on full noisy crawled En-Ru data the chrF+ advantage narrows to about 1 point and BLEU is somewhat worse.
• Bidirectional decoder attention is not free in practice: although it adds no parameters or hyperparameters, it rules out decoding speed-ups that rely on unidirectional masking.

Terminology in this paper

Bidirectional Transformer (BiTran)

A Transformer decoder whose attention mask lets a token's representation attend to all tokens generated so far, including ones after its own position, instead of only to preceding positions.

Parent decoder

A syntax-aware Transformer decoder that dedicates one of its 8 attention heads to attend only to the self-generated dependency parent(s) of the current token, plus the token itself, adding no parameters.

GCN decoder

A syntax-aware Transformer decoder in which 2 labeled, gated graph convolutional layers sit above the embedding layer and encode the dependency graph the decoder has generated so far.

Structural transitions

Vocabulary items added to the target side of an NMT model that build a dependency tree, adapting arc-standard parsing by replacing Shift with a subword-generating action and keeping Left-Arc and Right-Arc with 45 UD labels, for 90 new tokens.

Syntactic challenge sets

Subsets of books and newstest corpora, filtered by a parser, in which two or more non-consecutive source or target words correspond to a single word in the other language, covering preposition stranding, particle verbs and reflexives.

Source versus target challenge direction

A challenge set is 'source' when the lexical long-distance dependency appears in the input sentence and 'target' when it appears in the reference translation.

How to cite

@inproceedings{DBLP:conf/conll/ChoshenA22,author       = {Leshem Choshen and
                  Omri Abend},
  editor       = {Antske Fokkens and
                  Vivek Srikumar},
  title        = {Enhancing the Transformer Decoder with Transition-based Syntax},
  booktitle    = {Proceedings of the 26th Conference on Computational Natural Language
                  Learning, CoNLL 2022, Abu Dhabi, United Arab Emirates (Hybrid Event),
                  December 7-8, 2022},
  pages        = {384--404},
  publisher    = {Association for Computational Linguistics},
  year         = {2022},
  url          = {https://doi.org/10.18653/v1/2022.conll-1.27},
  doi          = {10.18653/V1/2022.CONLL-1.27},
  timestamp    = {Fri, 12 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/conf/conll/ChoshenA22.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

References

See the full reference list in the paper.