Relation-Constrained Decoding for Text Generation
Authors: Xiang Chen
Zhixian Yang
Xiaojun Wan
Venue: NeurIPS 2022 Accept (2022)
Keywords: constrained decoding
text generation

Abstract: The dominant paradigm for neural text generation nowadays is seq2seq learning with large-scale pretrained language models. However, it is usually difficult to manually constrain the generation process of these models. Prior studies have introduced Lexically Constrained Decoding (LCD) to ensure the presence of pre-specified words or phrases in the output. However, simply applying lexical constraints has no guarantee of the grammatical or semantic relations between words. Thus, more elaborate constraints are needed. To this end, we first propose a new constrained decoding scenario named Relation-Constrained Decoding (RCD), which requires the model's output to contain several given word pairs with respect to the given relations between them. For this scenario, we present a novel plug-and-play decoding algorithm named RElation-guided probability Surgery and bEam ALlocation (RESEAL), which can handle different categories of relations, e.g., syntactical relations or factual relations. Moreover, RESEAL can adaptively "reseal" the relations to form a high-quality sentence, which can be applied to the inference stage of any autoregressive text generation model. To evaluate our method, we first construct an RCD benchmark based on dependency relations from treebanks with annotated dependencies. Experimental results demonstrate that our approach can achieve better preservation of the input dependency relations compared to previous methods. To further illustrate the effectiveness of RESEAL, we apply our method to three downstream tasks: sentence summarization, fact-based text editing, and data-to-text generation. We observe an improvement in generation quality. The source code is available at https://github.com/CasparSwift/RESEAL. 

Relation-Constrained Decoding for Text Generation
Xiang Chen; Zhixian Yang. Xiaojun Wan Wangxuan Institute of Computer Technology. Peking University Center for Data Science, Peking University The MOE Key Laboratory of Computational Linguistics, Peking University casparēpku. edu. en, yangzhixian@sta pku. edu. en, munxiaojun@pkie edu
Abstract
The dominant paradigm for neural text generation nowadays is seq2seq learning with large-scale pretrained language models. However, is usually difficult to manually constrain the generation process of these models. Prior studies have introduced Lexically Constrained Decoding (LCDD) to ensure the presence of pre- specified words phrases in the output. However, simply applying lexical straints has no guarantee of the grammatical or semantic relations between words. Thus, more elaborate constraints new constrained decoding scenario named Delation-Constrainee Decoding (RCD), which requires the model's output to contain several given word pairs with respect to the given relations between them. For this scenario, we present a novel plug-and and- play decoding algorithm named RElation gellation-uided probability Surgery and bEam AI Alocation (RESEAL), which can handle different categories of relations, e.g., syn- tactical relations or factual relations. Moreover, RESEAL can adaptively "reseal" the relations to form high-quality sentence, which can be applied to the inference stage of any autoregressive text generation model. To evaluate our method, we first construct an RCD benchmark based dependency relations from treebanks with annotated dependencies. Experimental results demonstrate that our approach can achieve better preservation of the input dependency relations compared to previous methods. To further illustrate the effectiveness of RESEAL, we apply our method three downstream tasks: sentence summarization, fact-based text editing, and data-to-text generation. We observe an improvement in generation quality. The source code is available https: //gp::://iiiii gigttuu........ com/ /CmmsaaaSriftt/RESS...
needed. To this end, we first propose a
Introduction
Incorporating complex manual constraints into neural text generation is a challenging research topic. One of the most important manual constraints the relation constraint, i.c., to guarantee that two pre-specified words must appear in the generated text and keep the given relation between them. Such relation constraints have various applications. For instance, data-to-text generation [11, 10] and fact-based text editing [17] aim to ensure the presence of given facts (entities and relations between them) in the output. Moreover, in sentence summarization task [36], there are some key semantic relations that must be preserved ensure the fluency and factual constituency of the summaries.
The most prominent paradigm for text generation is seq2seq learning by finetuning the argeescale pretrained models [21, 34] and obtaining the outputs by beam search in autoregressive manner. However, this paradigm often fails to satisfy the complex constraints because there is no explicit mechanism to enforce these constraints. To tackle this problem, previous works [15, 16, 31] propose Lexically Constrained Decoding (LCD) to preserve some given keywords in the output. However,
Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Pock
[Dependency Placement)
Source Input (optional)
Relation Constraints: amad
phone
fancy
Relation Constraints:
phone
Fancy
Output:
What a fancy phone!
Decoding...
[Data-to-Text Goneration]
Decoding Time Step
Pui
amed
Relation Constraints:
Elliot See
Dallas
What fancy
phone
Identifier
Relation
0.99
Output:
Elliot See was born in Dallas.
Beams
phone
fancy
0.00
[Fact-Based Text Editing]
Draft (Input):
dessert.
Contiuu Dacoding...
Relation Constraints:
Bionico
Mexico
Target Output:
What fancy phone!
Output:
Bianico is dessert from Mexico.
The framework of our proposed RESEAL. Given the relation constraints (phone, amod, fancy), RESEAL operates the next-token probability Pvocab according to the probabilities prel produced by relation identifier. RESEAL will relatively maintain or reduce the Pvorab of those candidate words that meet the relation constraints in an adaptive way. In this case, the probability of "phone" is maintained since it can form an "amod" relation with "fancy". On the contrary, in another beam, the probability of "fancy" is cut down since will form a wrong relation "nsubj" with "phone". Note that "amod" denotes adjectival modifier and "nsubj" denotes nominal subject.
Figure I:
simply utilizing these lexical constraints still struggles to ensure the word relation constraints. Therefore, another form constrained decoding is needed to handle the relation constraints.
In this paper, we propose new constrained decoding scenario named Relation- Constrained Decoding (RCD). Specifically, we adopt the triplets (head, relation, tail) as the relation constraints. At the decoding stage, we aim to force the model output to include these relation constraints. The right part of Figure shows three instances for RCD with different relation types. an evident way, satisfying relation constraints requires satisfying corresponding lexical constraints. A straightforward solution to this problem to generate a set of candidate sentences using any LCD algorithm to ensure the keyword preservation, and then rerank them by the number of relation constraints they have met. However, this approach requires to first generate a number of whole sentences, which is inefficient and inflexible. To this end, we propose RESEAL (RElation-guided probability Surgery and bEam ALlocation), a Iilation-guide decoding algorithm for RCD that can dynamically adjust the choice of words during decoding. RESEAL modifies conventional LCD method, i.c., Dynamic Beam Allocation (DBA) algorithm [31], and incorporates a high-quality external relation identifier to identify the presence of relation constraints. As illustrated in the left part of Figure I. based on the relation identifier, RESEAL dynamically adjusts the probability of the candidate constrained words in the generation process?.
Among all categories of word relations, the dependency relation is most basic, standard and represen- tative which has various public available datasets for evaluation. Therefore, in this paper, we mainly focus on the dependency relation scenario of RCD. To illustrate the effectiveness of our proposed RESEAL, we construct benchmark from publicly available treebanks [39] that contain sentences and their dependency trees annotated by human. We randomly sample a subset of dependency triplets as the input constraints and regard the original sentences reference outputs. We call this task "Dependency Placement". Experiment results show that our method outperforms basclines and LCD methods on dependency coverage (the ratio of satisfied relation constraints for dependency). After that, to showcase the applicability of this work, we further explore some potential applications of RCD. We conduct extensive experiments three downstream tasks: sentence summarization (with dependency relations), fact-based text editing (with relations between two entities in the knowledge graph), and data-to-text generation (with relations extracted from knowledge bases). Across different tasks, we observe a consistent improvement over the strong baselines.
Note that the performance of relation identifier is crucial to the generation quality. It's not so difficult to train accurate relation identifier. We will further discuss this external dependence issue in Appendix D.3.

---

To sum up, the contributions of our work are three-fold: (i) We propose Decoding (RCD), a scenario for constrained text generation, and construct its benchmarks. To the best of our knowledge, we are the first to study this problem. (ii) We design RESEAL, decoding algorithm that can generate high-quality sentences that meet relation constraints. (iii) The experimental results on the RCD task and downstream tasks including sentence summarization, fact-based text editing and data-to-text generation show the effectiveness of RESEAL.
2 Problem Formulation
In this section, we first formulate the Relation-Constraine Decoding (RCD) problem. For the text generation tasks, given an input sequence X (21,
where the input sequence length, I; E Vs and Vs is the source vocabulary, the model generates a sequence Y (y1, 1/2 ..... VM ) where M the output sequence length, Y/ E Vy and Vy the target vocabulary. The conditional probability of Y given X and model parameter can be calculated as follows:
p P
II p(yllve,,
Eq. usually acts as an objective for beam search, In this paper, we denote each relation constraint as triplet (h, r. T), where h is the head, T is the tail, and is the relation between them. Given an unordered relation constraints set = {(h,, Pt, T2) where is the number of constraints and lu, Ti E V7, we aim to make the output Y satisfy the constraints in C' as much possible. For the model's 'ss output Y, we denote C"(Y)= = {(hf, r/. T/ be the relation triplets of Y, and then we propose to jointly optimize Eq. 1 and |C' CYY) as novel objective for RCD.
3 Methodology
Algorithm gives an overview of RESEAL. To start the decoding, the decoder input is initial- ized with a single (BOS) token. At each time step
Algorithm 1 RESEAL (overview)
Input: Max sequence length N, beam size kt relation constraints C, relation identifier R, poe_input..
t, the model maintains the b-best candidate sen- tences, where i is the beam size. The decoder produces the distribution Pvocab (w Blcce, X; 0) for each token w in the target vocabulary VT (line 3). Each candidate has different Pvocab re- spectively to produce &|Vr] candidates, then we select top-k candidates from them by the mulative log probability (line 5). The decoding
Output: Output sequence.
1: Initialize & candidates and dec inputs
for time step in [1, N] do
3: Pracab <- MODEL(EnC MMODELienc_jpputs inputs, dec dec_ inputs)
4:
5 P-ROP_RURGRRRR SURGERY(Peaaa,, candidates, C, R)
5:
candidates + RG RG_ TopK(p candidates, C))
have finished i sentences then break
7:
ends when candidates contain & finished sen- tences (line 6-7). Different from the standard beam search, RESEAL follows two-step ap- proach as follows:
8:
return candidate with highest score
Step 1: Probability Surgery (line 4) RESEAL operates the produced probability distributions according to the result of relation identifier, which serves as an explicit signal to guarantee the presence of relation constraints.
Step 2: Reldtion-Guided Top-K (line 5) To satisfy lexical constraints, we replace the standard Top-K operation by the one used in DBA [31]. Furthermore, to satisfy relation constraints, RESEAL dynamically allocates beam by the results of relation identifier instead of the number of satisfied lexical constraints used in DBA.
If removing line 4 and replacing line 5 with normal Top-K, RESEAL is equivalent to the standard beam search. We will describe the aforementioned two steps in detail in the rest of this section.
3.1 Probability Surgery
Algorithm 2 (line 1-6) shows the process of probability surgery. At time step during decoding, the model predicts the next token probability Pvocab (ur y<ee 0)) To provide an external signal to guar- antee the presence of relation constraints, calculate another probability distribution Pret (wlyww C*)
3

---

Algorithm 2 Probability Surgery and RG-Top-K
I: function PROB SURGERY(Peean, candidates, C, R)
2:
for all candidate in candidates do for all unmet lexical constraints u of candidate do
3:
4:
sent
seeieanceeeeeeneeeeeeeeee (i.e., y<+) w Get prmas Prype by
sent, and then calculate paa pra (wrly C) by Eq.
Calculate and normalize p by p( (ullee,, X, C;0) o ((paauyyets C)) (vocus(wllyee X; X;0). 0).
return f of every candidate
7:
function RG Tor candidates, C) candidates +
8:
caterrat___aiiitte____eeee b______b______b by_D, candidates)
9:
Initialize relation_ counts, bank, and gruned__cndidaate
10:
for all candidate in candidates do
11:
Get ni, which is the number of correct relation constraints in this candidate.
12:
Update
and add the candidate to bank
13:
bank_sizee sizes +- Bcam_Allocctte_by DwA((relation_couuug for j in [0, [C1] do
14:
15:
Add top-K K candidates in bank j to canidddaanddatess, where K bank_sizes]j]
return pruned_ caaddidatss
by the external relation identifier. The Prel (w C) indicates the probability that the token w satisfies the relation constraints C' given previous decoding result yea. The core idea of our proposed probability surgery is combine Pvocab and pret together to produce augmented distribution p. and then use p instead of Pvocab to choose the words.
We first give formal definition of Pret (wlyee y-ct: C). The Prol depends on two factors: (1) the transition probability Pirans (yj. yt), the probability that yj is the head of ys. (2) the relation type probability Plype (Vj, r. vi). the probability that the relation between yi and yj falls in type r. Both Prans and Ptype can be obtained during decoding by a relation identifier. For dependency relations, the relation identifier can be left-to-right dependency parser [9] to better fit the left-to-right manner of autore- gressive decoding. For relations between entities, the relation identifier can be any relation extraction model. The function of relation identifier is predict the head of yt, which produces series of Prrans (Mj, 3:). Additionally, the relation identifier also predict the relation types, which produces a series of Pupe (B) r. yt). Note that yj is not the head of yss Paype (3/, r. 3/) for all types r.
Given the incomplete output sequence y<r = (y1, .... in C. Let Chead (w, t), Cual (w, t) denote the subset of
.... Yt-1) at time step and the next token w.
we choose the relation constraints related relation constraints C' at time step where the w serves as the head or the tail, respectively:
Chead (w, 1) = {ww v) (w, v.y) E ECANC Bec), Ve E V7. Cuail (ur, t) (,, r,) (w) E ECA yeth, Vu VT.
(2)
We can calculate Pret (wllee C*) as follows?:
(welw/yee C)
[reans (M. y) + Prypew, (w, r. [)]++ +
[Peans 16) + Piypo y, r,00]]
Zun
(uimull Opestimn)
where Zw.t = 21 Chead (w, t)] + [w, t)]] is a normalizing factor. Consequently, the augmented distribution can be calculated as follows:
M(wlyee, X, C) g(phawwyyee C)) Pvocab (wryeee X;0),
where g [0, 1] - (0, 1] a gate function to transform Pee to weight of Pvecab. We aim to increase the weight when the Piet increases, so g cannot be monotonically decreasing function. Moreover, the output of this function should not be exactly zero, because assigning zero probability will make the log-likelihood of the whole sentence be negative infinite. Based on these requirements, inspired
NNote that ( (wyye,, C) = if Chead w. t) Can (w, t) = 0. Apart from that, we use additive form of instead of multiplicative manner, we further discuss this in Appendix A.

---

by Schick et al. [37], we adopt this parameterized form of in this paper:
fe- P(a- if Prel < P
g(Pie))
11
(5)
otherwise
where X, p are the hyperparameters and À > 0, p E (0, 1]. controls the decay of output value. p is threshold for the probability. We fix p 0.5 in this paper. If the Pret of word is greater than or equal to this pre-specified threshold p. it confident enough to consider w satisfies the relation constraints. Thus we set (Prel) 1 for this situation preserve the Pvocab of On the contrary, when Pret is close to 0, ((ret) will be close to relatively small value e^ which indicates that the model will be less likely to choose the words violating relation constraints.
3.2 Relation-Guided Top-K
To ensure the presence of lexical constraints, we adopt the Top- K operation in DBA [31]. DBA firstly generates a set of candidates and then selects l of them through beam allocation. The candidate set generated by DBA (line 8) is the union of three sets: (1) the normal Top- K tokens, (2) all unsatisfied lexical constraints, and (3) the single-best token for each hypothesis groups together the candidates with the same number of satisfied lexical constraints into some banks and selects a different number of candidates from different banks. The candidates with fewer lexical constraints will have more chances to be selected. However, the original DBA is not aware of the relations between words. Since we have already processed the candidate sentences by relation identifier in probability surgery, we now use the processed result to guide the bank allocation. As illustrated in Algorithm 2, we propose to use the number of correct relation constraints i-th candidates (line 10-12) to divide the banks, rather than the number of satisfied lexical constraints used by DBA. This modification can jointly consider both lexical and relation constraints, because one relation constraint is equivalent two lexical constraints and their relation.
the beam. After that, DBA
4 Experiments on Dependency Placement
There are many kinds of word relations in natural language, so it is necessary to showcase the performance of our proposed RESEAL on different relations. Since syntactic dependency structures serve as the principle of how words are combined to form sentences, dependency relations can be the most basic and important for text generation. Thus, in this section, we mainly focus on the dependency relation scenario of RCD, and evaluate RESEAL on the Dependency Placement task. Besides, we will conduct extensive experiments on three downstream tasks in Section
4.1 Task and Dataset
We first define Dependency Placement task: given the constraints C of dependency relations, output fluent sentence Y which appropriately places these constraints. The model input X is optional, which can be single (BOS) token, or a sequential transformation of C' to provide necessary information. We then construct the dataset for dependency placement task from the English-EWT [39] corpus*. which contains 16,621 I sentences with dependency annotations and standard train/dev/test set split. For each sentence with m words, we randomly sample n dependency triplets ((h, Ts. T)) as the given constrains C, where n < m. The original sentences serve as references. We refer to this dataset as Beglish--ET-Dery. More details about English-EWTT-D. EWT-Dep can be found in Appendix B.
4.2 Evaluation Metrics
In this section, we discuss the appropriate metrics for the dependency placement task to evaluate an RCD algorithm (including but not limited to our proposed RESEAL). Simply using the automatic evaluation to compare the system outputs with the references is not suitable, because there are too many sentences that can be the correct answer given several dependencies. We mainly focus on whether the relation constraints are satisfied when examining an RCD algorithm. To this end, the output sentences should be processed again by an accurate external parser". This parser should
'httpa:/ httpa//////ivvaaaalee www.iverraaleeeeeeee weweeaaadeddeeeeeeees.... org/
Another choice is to process the outputs by human, which too expensive.
5

---

Table I: Evaluation result for dependency placement task. "Reference" denotes evaluating the ground truth sentences, which can be viewed as an approximated upper bound this task. Despite that the BLEU-4 and METEOR is not so accurate to evaluate this task, still provide it for reference only.
Stanza
spaCy
Method
BLEU-41
METEOR
PPL.
Word%
UCt
LCt
UC1
LCt
Base [21]
80.52
69.69
81.04
71.02
11.92
20.12
865.40
97.11
Rerank 20)
84.32
74.86
84.04
74.93
11.66
20.18
346.44
99.88
CGMH [26]
39.46
25.70
37.50
24.69
1.47
14.50
2341.83
96.20
X-MCMC [13]
51.78
37.36
52.30
37.99
4.62
17.04
513.18
99.86
X-MCMC-C [13]
58.17
44.90
58.90
46.23
6.39
17.65
557.58
99.88
DBA [31]
79.54
67.39
79.78
68.47
11.47
20.12
318.67
99.82
DDBA [25]
79.22
68.72
79.96
70.11
12.22
20.12
796.76
97.01
NeuroLogic [24]
82.47
71.72
83.03
72.87
12.23
20.13
436.27
98.93
RESEAL
86.45
79.26
86.73
80.66
12.62
20.40
260.80
99.60
Reference
86.80
81.49
90.50
86.49
100.00
100.00
527.35
100.00
preferably be different from the one used in an RCD algorithm, which can better examine the generalization ability across the parsers. In this paper, we use two widely-used dependency parsers provided by Stanza [32] and spaCy" for evaluation. Let ((i) denote the relation constraints of i-th output yt)) in test set. Let C' (*))(+)) denote the dependency relation triplets obtained by the external parser. Let ((() and (0) denote the sets we omit the dependency relation of C++) and ()) Similar to the unlabeled/labeled attachment score (UAS/LAS) used in dependency parsing, can define the unlabeled/labeled coverage (UC/L.C as follows:
UC Σ, (W()) n W
LC = Σ, 100 (C((())
(6)
Σ, [
E
Moreover, report the BLEU-4 [30], METEOR [2], GPT-2 [33] perplexity (PPL) and word coverage (the proportion of lexical constraints that are satisfied).
4.3 Baselines
Since there are no existing work about dependency placement, we design some straightforward baselines to compare with our method:
Base: Use BART large [21] as the backbone, and then functune it on English-EWT-Dep. The
input is the concatenation of the triplets of C' separated by special token #. For example, if
C' = {(h,, 71, TT), (h22, r2, T2)], ), the input sequence = hr#f1 #T,, #2. The target
output is the reference. During decoding,
standard beam search with beam size h: 20.
CGMH [26]: Use MCMC sampling to generate sentence by modifying it. We use BERT [6]
to produce its replacement probability, and GPT-21arge [33] as its language model.
X-MCMC [13]: Improve CGMH by using XLNet [46]. X-MCMC-C adds a classifier to instruct the X-MCMC models where and how to modify the candidate sentences.
DBA [31]: Use DBA algorithm to decode on the Base model with beam size i 20.
DDBA [25]: denoised variant of DBA by filtering noisy constraints.
NouroLogic [24]: A LCD algorithm which support complex lexical constraints Conjunctive Normal Form (CNF).
Rerank: Preserve all & sentences generated by DBA, and select the sentence that satisfies the most relation constraints using left-to-right parser [9].
We report the results when applying RESEAL to the Base. More details can be found in Appendix C.
"attps://explosiion ai/blog/ud http://ardbecccheeeeeeee -oo-poarrrt---------eojooett
2#project

---

Table 2: Result of ablation study for dependency placement task. We remove single component from the full algorithm to study the individual effect. "w/o prob" denotes without probability surgery (but still with RG-Top-K), "w/o RG-Top-K" denotes using the way of original DBA to allocate beam (but still with probability surgery). "word+rel" denotes using the number of satisfied lexical and (dependency) relation constraints allocate beam.
Stanza
spaCy
Method
BLEU-41
METEOR
PPL.
Word%
UC1
LC
UC1
LCt
RESEAL
86.45
79.26
86.73
80.66
12.62
20.40
260.80
99,60
w/o prob
81.70
70.91
82.12
72.21
11.83
20.19
256.88
99.80
w/o RG-Top-K
82.12
74.27
83.03
75.49
11.89
20.21
361.96
99.76
word+rel
82.40
74.51
83.34
75.42
11.08
19.81
452.50
99.72
56-
10
PM
310
90-
84.
UC
300
290
70
270
65
Methed
76
200
Reference
70
230
10
size
lambda
Figure 2: The result when altering the value of X and beam size k.
4.4 Discussion
Results Table 1 shows the results for dependency placement, We find that the sampling-based method [13, 26] can achieve better word coverage, but the low UC/LC scores demonstrate that they fail to enforce the relation constraints. RESEAL achieves best UC/LC among all the methods with significant decline of the PPL and competitive word coverage. Specifically, RESEAL gains an improvement of 1.15 on BLEU-4 and 11.87% 11..7%//..999 19% (Stanza/spaCy) on LC compared to DBA. These results illustrate the weakness of existing LCD algorithms to correctly place the multiple relation constraints. Some LCD methods (DBA, DDBA, NeuroLogiic) would forcibly add the unsatisfied lexical constraints into the candidate word set. This is the key ensuring the presence of lexical constraints. However, doing this fails to consider the relations between words, thus would make the generated sentence less fluent. Apart from that, RESEAL outperforms Rerank on almost all the metrics. An intrinsic reason for this may be that RESEAL can dynamically adjust the word selection according to the parsing result during decoding, but Rerank not make choice until finishing all the sentences.
Ablation Study Table 2 shows the results of ablation study. We observe a decrease of 0.79 on BLEU-4 and 8.35% /8.45% (Stanza/spaCyy) on LC by removing probability surgery. We also observe decrease of 0.73 on BLEU-- and 4.99% 1.7% (Stanza/spaC)) on I.C by removing RG-Top-K. Probability surgery enables the tokens with correct dependencies to enter the candidate set. RG-Top-K dynamically allocates the beam according to the parsing result to satisfy more relation constraints. These two components are both crucial. Furthermore, we find that adopting another beam allocation strategy ("word+rel" in Table 2) also hurt the performance.
Impact Hyperparameters For the dependency placement task, the performance would benefit from a larger beam size, which is consistent with the observations of Post and Vilar [31]. The left of Figure shows the labeled coverage (LC) as function of beam size by different methods on the test set. We observe that RESEAL can achieve better LCC scores with smaller beam sizes when compared with Rerank. Apart from that, the decay factor À introduced in Section 3.1 another important hyperparameter of RESEAL. We investigate its influence the model performance. Figure 2 shows
7

---

Table 3: Evaluation result for sentence summarization experiments.
Gigaword RG-2
DUC2004
MSR-ATC
Methods
RG-1
RG-L
RG-1
RG-2
RG-L
RG-1
RG-2
RG-L
SEASS [49]
46.86
24.58
43.53
29.21
9.56
25.51
25.75
10.63
22.90
Keyword [22]
47.14
25.06
44.39
SemSum [18]
31.00
11.11
26.94
33.82
17.08
30.62
BART [21]
50.14
27.37
46.69
31.38
11.43
27.51
40.39
22.09
35.32
BART+RESEAL
50.73
27.84
47.18
32.67
11.63
28.38
43.77
25.28
37.78
BART+RESEAL (gold)
53.74
31.00
48.99
35.53
12.41
28.68
69.42
41.76
51.71
Table 4: Examples with RESEAL and other baselines. The dependency relation constraints are (thought, ccomp, 's) and ('s, nsubj, charges).
Method
Generated Sentences
Base
thought the charges would 5,000, but they were $ 10,000. thought the charges would be $ 10,000, but it's $ 20,000. thought they were going to charge me, but there's no charges. thought there's some charges, but wrong. I always thought there's no custom charges for gifts.
DBA
Rerank
RESEAL
Ref.
the results when varying À from to 10 based on the validation set. If we set as a relatively large value (> 4). the performance of RESEAL tends to be stable. Specifically, À 0 is equivalent to removing probability surgery (from Eq. 5), which will result in worse performance.
Case Study Table 4 shows the sentences generated by all listed methods for dependency placement task. The Base model may omit some lexical constraints. DBA and Rerank satisfy all the lexical constraints, but they cannot correctly handle the relations between them. Rerank may generate sentences with repetitions (e.g., the word "charge"). RESEAL can produce sentences that are close to the grammatical structure of the references.
More Discussions In Appendix we discuss the limitations of RESEAL, including the impact of dependency parsers, time complexity and external dependence issue. In Appendix E, we provide more cases for dependency placement task. In Appendix F, we discuss the social impact of this work.
Experiments on Downstream Tasks
To further explore the effectiveness of our proposed RESEAL, we conduct experiments on the three downstream tasks: sentence summarization, fact-based text editing, and data-to-text generation. Intuitively, RESEAL can aid these tasks. For the sentence summarization, RESEAL may help to preserve the important relations in the source sentence. For the rest two tasks, RESEAL can help to incorporate the given factual relations.
5.1 Sentence Summarization
Dataset We conduct experiments on English Gigaword dataset [36], which contains about 3.8M training sentence pairs. We use the validation and test set provided by Zhou et al. [49] with 8,000 and 2,000 sentence pairs, respectively. Following previous work, we also evaluate our model on the test set of DUC2004 [29] (with 500 input sentences) and MSR-ATC [42] (with 785 input sentences).
first need to obtain reasonable dependency triples to construct relation constraints. In this paper, we train a vanilla BERT- base-uncased [6] model to predict which dependencies should be present in the target output. Firstly, we parse the sentences in the dataset by the left-to-right parser [9]. Then we use the intersection of dependencies of source and target sentences the ground truth to train the dependency predictor. For each triplet (h, r, T), we concatenate the contextual embedding of ht T and label embedding of perform binary classification. More details can be found in Appendix C.2.
Dependency Prediction To apply RESEAL to sentence summarization,

---

Table 5: Evaluation result of WebEdit dataset.
Methods
BLEU-4
SARI
KEEP
ADD
DELETE
DncDectiitor [17]
71.03
69.59
89.49
43.82
75.48
FactEditor [17]
75.68
72.20
91.84
47.69
77.07
Seq2Seq
82.96
73.74
93.62
64.56
63.05
Seq2Seq RESSEAL RESEAL
84.12
78.33
96.07
69.63
69.29
Results Following previous work [18, 49], we report ROUGE Fl [23] Gigaword and MSR- ATC, and ROUGE recall on DUC2004. Table show the results. BART consistently outper- forms the previous models without pretraining across different datasets. Over the strong BART baseline, RESEAL can achieve better ROUGE scores on all datasets with predicted relation constraints. We also investigate the upper bound of BART+RESEAL by using the gold relation constraints, which shows that there is room for improvement with more accurate dependency predictors.
Table 6: Evaluation result for WebNLG test set.
Methods
BLEU-4
Castro Ferreira al. [4]
51.68
Moryossef et al. [27]
47.24
Zhao al. [48]
52.78
Harkous et al. [12]
52.90
Nan al. [28]
45.89
T5-small [34]
56.34
T5-small RESEAL
56.87
T5- [34]
59.17
T5 15--base + RESEAL
59.59
5.2 Fact-Based Text Editing
Dataset Fact-based Text Editing is a novel task proposed by Iso al. [17]. Given some triplets (facts) from knowledge graphs and draft text, this task aims to revise the draft text to contain these facts. We adopt the WebEdit dataset provided by Iso al. [17], which contains 18 K/23K/2/2 instances as train/valid/test set. Note that this dataset can be viewed as natural scenario for RCD because both the relation constraints (facts) and model input (draft text) are provided. More importantly, based on the results of error analysis, the models trained on this dataset still suffer from missing facts and incorrect relations (see "Qualitative evaluation" section in [17]). RESEAL may alleviate these problems by explicitly enforcing facts and relations.
5.3 Data-to-Text Text Generation
Models and Results For the relation identifier, we train a simple BiLSTM [14] encoder with biaffine attention [8] the training set of WebEdit (See Appendix C.3.1 for more details). We use EncDecEditor and FactEditor reported by Iso al. [17] as our baseline models. EncDecEditor an encoder-decokd model based on LSTM, with two separate encoders for facts and drafts and decoder for generating revised texts. FactEditor shares the same encoders with EncDecEditor but has novel decoder that doesn't 't follow the conventional autoregressive decoding manner. Thus only apply RESEAL to the EncDecEditor, For fair comparison, we do not use pretrained models and keep the same architecture setting EncDecEditor. However, the source code and the training details of EncDecEditor are unreleased, thus we reimplement EncDecEditor using our own training configuration (See Appendix C.3.2). We denote this model Seq2Seq. Table 5 shows the experiment results of WebEdit. Following Iso et al. [17], we report the BLEU-4 and SARI [45] score (the average F1-score for keep, add and delete operations). Owing the difference of training settings, Seq2seq can achieve significant improvement on BLEU-4 (+7.28) and SARI (+1 1544 compared to FactEditor. Based on this result, we further adopt RESEAL on Seq2Seq and then observe substantial improvement on BLEU-4 (+1.16) and SARI (+4.59). The above results demonstrate that RESEAL can achieve better facts and relations preservation over the strong Seq2Seq baseline.
Dataset Data-to-text generation another direct application for RESEAL. In this paper, we adopt WebNLG dataset [11] which provides facts as inputs and sentences containing these facts as outputs. We use the data provided by Ribeiro et al. [35] which contains 18, 18.102/872/1,86. instances train/valid/test set. Each test instance has 1-3 references.
Models and Results For WebNLG dataset, the setting of the relation identifier is the same as that for WebEdit. Table 6 shows the experiment results of WebNLG dataset. We adopt our RESEAL

---

T5 [34] and report the BLEU-4 score for evaluation. We observe an improvement of 0.53 BLEU-4 on T5-small and 0.42 BLEU-4 on T5-base. The detailed experimental settings can be found in Appendix C.4.
6 Related Work
Lexically Constrained Decoding (LCD) Prior explorations for LCD can be summarized into four categories. The first line of studies has proposed some model-agnostic methods which only modify the decoding process. They independent from the training. Hokamp and Liu [15] propose the grid beam search (GBS) algorithm, modification to beam search to impose the lexical constraints. Post and Vilar [31] propose the dynamic beam allocation (DBA) algorithm with less time complexity. Vectorized DBA [16] and Denoised DBA [25] are two different DBA variants. The second line of studies requires some modifications to the training process. Augmenting the training data with the lexical constraints is a general approach [5, 7, 40]. Another branch of previous works focuses on adding additional structure to the model [41, 43, 44]. The fourth line of studies applies Markov Chain Monte Carlo (MCMC) to constrained text generation in refinement manner [13, 26, 38]. Different from these methods, we do not only focus the isolated lexical constraints. We propose to adopt relation constraints to consider the relationship between words.
Dependency-Guiee Guided Generation Dependency is natural way to represent the syntactic or semantic relations between words, so it can be used to guide the text generation. There are few works exploring this. Filippova and Strube [10] propose to compress the dependency graph to guide the sentence fusion. Akoury et al. [1] propose to predict a chunked syntactic parse tree and then generate tokens conditioned the parse. Jin et al. [18] encode the dependency relations by graph encoder to improve sentence summarization. Casas et al. [3] propose a language model where the generation driven by the expansion over the dependency parse tree. Yang and Wan [47] propose a dependency modeling objective to incorporate dependency knowledge. However, one drawback of these methods the limitation of interpretability and controllability since they only the dependency latent variable during training, and cannot explicitly control the generation at the inference stage.
7 Conclusion
In this paper, we explore the more complex definition constraints. We propose RESEAL, a novel algorithm for RCD, which can be applied to the decoder of different models to preserve specific relation constraints. We examine two different experiment settings of RCD:: dependency placement and downstream tasks. For dependency placement, we construct the benchmark for dependency placement, and the experiment results show the strength of RESEAL for satisfying relation constraints. Furthermore, we apply RESEAL to three downstream tasks as extended experiments for practical applications. Extensive experiments demonstrate the effectiveness and universality of our method.
Decoding (RCD), a new decoding scenario with
Acknowledgment
This work was supported by National Key R&D Program of China (2021 1002YYRE YFF099150))) National Science Foundation of China (No. 160339,, State Key Laboratory of Media Convergence Production Technology and Systems and Key Laboratory of Science, Technology and Standard in Press Industry (Key Laboratory of Intelligent Press Media Technology). We appreciate the anonymous reviewers for their helpful comments. Xiaojun Wan is the corresponding author.
References
[1] Nader Akoury, Kalpesh Krishna, and Mohit lyyer. Syntactically supervised transformers for faster neural machine translation. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages I 1269-1281, Florence, Italy, 2019. Association for Computational Linguistics. doi: 10. 18653/v1/119-111 112.. URL https: : //tp//aaaaaa aclanthology org/P19-1122. 10
10

---

[2] Satanjeev Banerjee and Alon Lavie. METEOR: An automatic metric for MT evaluation with improved correlation with human judgments. Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, pages 65-72, Ann Arbor, Michigan, 2005. Association for Computational Linguisties. URL. https:/ ac aallnnhoooggy org/w055 255/W055000. 6
[3] Noe Casas, José A. R. Fonollosa, and Marta R. Costa-jussà. Syntax-driven iterative expansion language models for controllable text generation. In Proceedings of the Fourth Workshop on Structured Prediction for NLP, pages 1-10, Online, 2020. Association for Computational Linguistics. doi:
1ptp: URL hatp::::/aalaathhllgogooo wrg.:yoorrr/20
8pnlp-1.1. 10
[4] Thiago Castro Ferreira, Chris van der Lee, Emiel van Miltenburg, and Emiel Krahmer. Neural data-to-text generation: A comparison between pipeline and end-to-end architectures. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 552-562, Hong Kong, China, 2019. Association for Computational Linguistics. doi: 10.18653/w1/D1--11 1052. URL https: http//aaaaaantooooooo/e
org/D19-1050 9
[5] Guanhua Chen, Yun Chen, Yong Wang, and Victor O. K. Li. Lexical-constrainn--aaaa neural machine translation via data augmentation. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 3587- 3593. ijcai.org, 2020. doi: 10.24963/jccai220004999 URL https://doi. org 24963/ ijcai 200000/496 10
[6] Jacob Devlin, Ming- wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages 4171 Minneapolis, Minnesota, 2019. Association for Computational Linguisties. doi: 10. 10.18653/v1/N11914222 URL https: htt///ccaaanhhoooeec wwwpchoooog.ooo/N1999 org/N19- 1423. 6, 8, 18
[7] Georgiana Dinu, Prashant Mathur, Marcello Federico, and Yaser Al-Onaizan. Training neural machine translation to apply terminology constraints. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3063-3068, Florence, Italy, 2019. Association for Computational Linguistics. doi: 1t.18653/w1/19.1.1 1294. URL https: /aallanthlloyyy.o.... www.orgg/.... P19 1294. 10
[8] Timothy Dozat and Christopher D. Manning. Deep biaffine attention for neural dependency parsing- In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https://openrreveen net//oormm
9, 18, 20
[9] Daniel Fermández-Gonzátn and Carlos Gómez-Rodríguez. Left-to-right dependency parsing with pointer networks. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 710-716, Minncapolis, Minnesota, 2019. Association for Computational Linguistics. doi: 10.18653/v1/NI 1076. URL https: aclaathooonohoggyyy.ooo N0g/ 4, 6, 8, 20
[10] Katja Filippova and Michael Strube. Sentence fusion via dependency graph compression. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 177-185, Honolulu, Hawaïi, 2008. Association for Computational Linguistics. URL attps://aclanthonn wwwggy...rgDooo. www//oo-- 1019. 10
[11] Claire Gardent, Anastasia Shimorina, Shashi Narayan, and Laura Perez-Beltrachini. Creat- ing training corpora for nlg miero-planning. In 55th annual meeting of the Association for Computational Linguistics (ACL), 2017. 1,
[12] Hamza Harkous, Isabel Groves, and Amir Saffari. Have your text and use it too! end-to-end neural data-to-text generation with semantic fidelity. Proceedings of the 28th International Conference Computational Linguistics, pages 2410-2424, Barcelona, Spain (Online), 2020.
11

---

International Committee on Computational Linguistics. doi: 10. 10.18655/w1/2020ooolngg 11.
URL https://acllanthologg wwg/2020.........oo coling mesiinggmiin... 218.
[13] Xingwei He and Victor OK Li. Show me how revise: Improving lexically constrained sentence generation with xlnet. In Proceedings of AAAI, pages 12989-1299) 2021. 6, 7, 10
[14] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98))
1735-1780, 1997. 9, 18
[15] Chris Hokamp and Qun Liu. Lexically constrained decoding for sequence generation using grid beam search. In Proceedings of the 55th Annual Meeting of the Association for Compulational Linguistics (Volume I: Long Pupers). pages 1535-1546, Vancouver, Canada, 2017. Association for Computational Linguistics. doi: 10. 118655//1//11-11I/ org/P17-1141. 1, 10
uttpttts: /aabpa/ooo//llahhoooogy
[16] Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. Improved lexically constrained decoding for translation and monolingual rewriting. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long and Short Papers). pages 339-850, Minneapolis, Minnesota, 2019. Association for Computational Linguistics. doi: 111.865/11/NN11110 URL https: hatpp:://aaaaatttaai /alaanhoooano org/N19-1090 1, 10
[17] Hayate Iso, Chao Qiao, and Hang Li. Fact-based Text Editing. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 171-182, Online, 2020. Association for Computational Linguistics. doi: 101186653/11202.aa/ main. 17. URL https:/ /aae::/allllaa acl anthology org/ org/2020 2020. acl-main. 17. 1, 9, 18, 19
[18] Hanqi Jin, Tianming Wang, and Xiaojun Wan. Semsum: Semantic dependency guided neural abstractive summarization. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 8026-8033. AAAI Press, 2020. URL https: /aaai.aa.... org/ j/ssssssss/// //iidxinn...///ee php/ AAAI/ htw.///rriceeeeee/////ee.
8, 10
[19] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL. http: //tp://aaiia aa//iixiiivv///////ee//eaaaa org/ abs/ 14121112220 6980. 17, 18, 19
[20] Rémi Lebret, David Grangier, and Michael Auli. Neural text generation from structured data with application to the biography domain. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1213-1213, Austin, Texas, 2016. Association for Computational Linguistics. doi: 10. 11653//1//D16--- 128. URI. https: latteps://aalaatiie acc aclanthology.
org/D16-1128.
[21] Mike Lewis. Yinhan Liu, Naman Goyal. Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. BART: Denoising sequence-to -ee-uueeeeeeeeeeeeeeeeee pre- training for natural language generation, translation, and comprehension. In Proceedings of the 58th Annual Meeting of the Association for Computational I Linguistics, pages 7871-7880, aan55///11102....mmmmm......m.. URL htttt::s//aaaathollggg... wwwpchhoooggooooooooooooooo org//og////// 20200.220..a0 aa1 mmain. 1, 6,6,8 8, 17
Online, 2020. Association for Computational Linguistics. doi:
[22] Haoran Li, Junnan Zhu, Jiajun Zhang, Chengqing Zong, and Xiaodong He. Keywords-guide abstractive sentence summarization. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Seoond Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 8196-8203, AAAI 8
Press, 2020. URL https: titps://aaail. http//aaaa..r//jj//////// http///xs////ix.//////// php/ http://atieeeeeieiiee/eaaeaeeeee
[23] Chin-Yer Lin. ROUGE: A package for automatic evaluation of summaries. In Text Summa- rization Branches Out, pages 74-81, Barcelona, Spain, 2004. Association for Computational Linguistics. URL https /aa/aclaanttt aalpaaaaannntoooo... org/w04-1003
12

---

[24] Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula. and Yejin Choi. NouroLogic decoding: (un)supervised neural text generation with predicate logic constraints. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages 4288-4299 Online, 2021. Association for Computational Linguistics. doi: 10. (0.18653/v1/2005 mannn-m URL
https: https///aaaaaathhoooooo org 20211021..22 maacl-main. 339.
[25] Yuning Mao, Wenchang Ma. Deren Lei, Jiawei Han, and Xiang Ren. Extract, denoise and enforce: Evaluating and improving concept preservation for text-to-text generation. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Pro- cessing, pages 3063-5074 Online and Punta Cana, Dominican Republic, 2021. Associa- tion for Computational Linguistics. doi: 10.1 8653/v1/20221 http:////122..mmmmmaam...oo emnlp-main.413. URL https: / //aclanthology org/ 22221.122222222
momlp-main 413. 6, 10
[26] Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: constrained sentence generation by metropolis-hastime sampling. In The Thirty-This Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances Artificial Intelligence, EAAl 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pages 6834 6842. AAAI httph:t////oot org/
Press, 2019. doi: 10. 10.9/6a0/ htta//aai.v33301.. 13300..3311634, 00.011.33018880 6, 7, 10
/ttg////.//// 100 1609/aaa!
[27] Amit Moryossef, Yoav Goldberg, and Ido Dagan. Step-by-step: Separating planning from realization in neural data-to-text generation. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages 2267-2277, Minneapolis, Minnesota, 2019. Association for Computational Linguistics. doi: 1..18653/11NN19-122 URL https: // /aaclanthology. .rg....rg.. org/ 1119-1238
[28] Linyong Nan, Dragomir Radev, Rui Zhang, Amrit Rau, Abhinand Sivaprasad, Chiachun Hsieh, Xiangru Tang, Aadit Vyas, Neha Verma, Pranav Krishna, Yangxiaokang Liu, Nadia Irwanto, Jessica Pan, Faiaz Rahman, Ahmad Zaidi, Mutethia Mutuma, Yasin Tarabar, Ankit Gupta, Tao Yu, Yi Chern Tan, Xi Victoria Lin, Caiming Xiong, Richard Socher, and Nazneen Fatema Rajani. DART: Open-domain structured data record to text generation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 432-447, Online, 2021. Association for Computational Linguistics. doi: 10.18653/ maccl maacl- URL https: /aa///aaaaaaaalaaaaeeaeaaaa org/ 2021.
37.
[29] Paul Over, Hoa Dang, and Donna Harman. Due in context. Information Processing Manage- ment, 2007.
[30] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for au- tomatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311-318, Philadelphia, Pennsylvania, USA, 2002. Association for Computational Linguistics. doi: 10.3 10.3115/1073033.107333 URL org/Po22 1040. 6
[31] Matt Post and David Vilar. Fast lexically constrained decoding with dynamic beam allocation for neural machine translation. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pages 1314-1324, New Orleans, Louisiana, 2018. Association for Computational Linguistics. doi: 10. 10.186///1//N88-11199 URL https: / https://aclanthaat http///caaantooo...... Arg/N18-1199. 1, 2, 3, 6, 10
[32] Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. Stanza: A python natural language processing toolkit for many human languages. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics System Demonstrations, pages 101-108, Online, 2020. Association for Computational Linguistics. doi: 10. 18.18653/v1 2020.acl-ar acll-demo..1. 14. URL https: / ht///claann// http:///aaaaaahloaa/ee/ org/ 202002200.o2 acl- demos. 14. 6. 20
13

---

[33] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 2019. 6
[34] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1-67, 2020. 1, 9, 10, 19
[35] Leonardo F. R. Ribeiro, Martin Schmitt, Hinrich Schütze, and Iryna Gurevych. Investigating pretrained language models for graph-to-text generation. In Proceedings of the 3rd Workshop on Natural Language Processing for Comversational AI, pages 21 2-1-227, Online, 2021. Association for Computational Linguistics. doi: 10.18653/v http://1111211../1o1oooeo 1.20. URL https://
acl aclanthology
ht/222221.11cooaaaaii. 1..0. 9
[36] Alexander M. Rush, Sumit Chopra, and Jason Weston. A neural attention model for abstractive sentence summarization. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 379-389, Lisbon, Portugal, 2015. Association for Com- putational Linguistics. doi: 10.18653/v1/D15--1 1044. URL
org/
015-1044. 1,8
[37] Timo Schick, Sahana Udupa, and Hinrich Schütze. Self-diagnosis and self deff-debiasing; A proposal for reducing corpus-base based bias NLP. Transactions of the Association for Computational Linguistics, 2:1408-14222 2021.
doi: 10.1162/tacl_, a a_00434. URL https: http///aaaaaatloo/ooooo
org/2021. ta..02...acc111. 1..
[38] Lei Sha. Gradient-guided unsupervised lexically constrained text generation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 8692-8703, Online, 2020. Association for Computational Linguistics. doi: 10.18653/v1/200 emilp-main.700 URL https: http:////aaaaaaahaaaaeeee org emnlp-maing maim.mi..... 701. 10
[39] Natalia Silveira, Timothy Dozat, Matie-Cat de Marneffe, Samuel Bowman, Miriam Connor, John Bauer, and Chris Manning. A gold standard dependency corpus for English. In Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC'14) 14), pages 2897-2904, Reykjavik, Iceland, 2014. European Language Resources Associ- ation (ELRA). URL http:// //www//wwww.// Irec- conf. org/ proceedingg/1ree221///pp Paper .dd.. 5,5
[40] Kai Song, Yue Zhang, Heng Yu, Weihua Luo, Kun Wang, and Min Zhang. Code-switching for enhancing NMT with pre-specified translation. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers). pages 4499,499, Minneapolis, Minnesota, 2019. Association for Computational Linguisties. doi: 1118865//1//NN111I1 URI. https: /acl/alaanaa aallatooooooyy wwtg/N19-100 1044. 10
[41] Kai Song, Kun Wang, Heng Yu, Yue Zhang, Zhongqiang Huang, Weihua Luo, Xiangyu Duan, and Min Zhang. Alignment-enhanced transformer for constraining NMT with pre- specified translations. In The Shhirty-Fourte AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirt--ecood Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 8886-8893. AAAI Press, 2020. URL https://ant http://aaaaaa.///////o// www.////////////////////o/ hinis////dxd.//eeeeeee/ee php/ hhtp/AAA/arttileee
10
[42] Kristina Toutanova, Chris Brockett, Ke M. Tran, and Saleema Amershi. A dataset and evaluation metrics for abstractive compression of sentences and short paragraphs. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 340-350, Austin. Texas, 2016. Association for Computational Linguistics. doi: 10.18653/v1/D16- 1033. URL https: / /tcl/alaantttt http:///aaaaaaoogr/o/o/om org/D16 1033.
[43] Yufei Wang, Ian Wood, Stephen Wan, Mark Dras, and Mark Johnson. Mention flags (MF): Constraining transformer- maased text generators. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Pupers), pages 103-113, Online, 2021. Association for Computational Linguistics. doi: 10.18653/v1/021 accl- Ion-- URL. https: //aclanteee aaclanthology.....om org/ 20tp/221..a a0l.aaccl-a.............l..cllla aaclllone 9. 10
14

---

[44] Yufei Wang, Can Xu, Huang Hu, Chongyang Tao, Stephen Wan, Mark Dras, Mark Johnson, and Daxin Jiang. Neural rule-execution tracking machine for transformer-bas based text generation. Advances in Neural Information Processing Systems, 34, 2021. 10
[45] Wei Xu, Courtney Napoles, Ellie Pavlick, Quanze Chen, and Chris Callison Buroch. Optimizing statistical machine translation for text simplification. Transactions of the Association for Computational Linguisties, 4:401-4155 2016. doi: 10.1162/tacl a a000107. URL https:// //
aclanthology.ore
1029.
[46] Zhilin Yang. Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc Le. Xlnet: Generalized autoregressive pretraining for language understanding. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 5754-5764 2019. URL https: htttt:////:/p//oeeeeteee http//poocceeeeee///ee/ neur ips. cc/paper/ 2019 /ttpa///..aaeeeeeeea0066e6eeeee. Absttett.bbttt.t........ html. 6
[47] Zhixian Yang and Xiaojun Wan. Dependeney- based mixture language models. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pages 7758-7773, Dublin, Ireland, 2022. Association for Computational Linguistics. doi: 10. 12218663/11/2022accllloo 535. 10
URL httptsss//aaaaaattolgg.../ org/2022 2022 acl long.
[48] Chao Zhao, Marilyn Walker, and Snigdha Chaturvedi. Bridging the structural gap be- tween encoding and decoding for data-to-text generation. In Proceedings of the 58th An- nual Meeting of the Association for Computational Linguistics, pages 2481-2491, Online, 2020. Association for Computational Linguistics. doi: 10. 12688//1120020.cllmmm.a 224. URL
org/ 2wwgg/22...e0 2020 acl main. 224.
[49] Qingyu Zhou, Nan Yang, Furu Wei, and Ming Zhou Selective encoding for abstractive sentence summarization. In Proceedings of the 55th Annual Meeting of the Association for Computationnl Linguistics (Volume 1: Long Pupers), pages 1 1095-1 104, Vancouver, Canada, 2017. Association for Computational Linguistics. doi: 10. 10.11665//1/11171101 URL https: //aclanthology.rrg .rg./.og/ii. org//17-1111111...11111 8,9
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO]] to [Yes], [No] or [N/A]. You are strongly encouraged to include a justification your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section 4.
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix D
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix F
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
15

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix C
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4 and Section 5
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] See Section 4 and Appendix B
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "szJ7d0e99Sm", "reviewer": "Reviewer_brwW", "summary": "This paper proposes a new paradigm in constrained text generation called relation-constrained decoding (RCD). RCD ensures that the tokens in the constraint set are adhered to (lexically constrained decoding) while decoding from NLG models without compromising on the underlying \"relation\" between the tokens. To address RCD, the paper presents a decoding time algorithm called RESEAL that can handle different types of relations (syntactic, factual, or entity based). On top of the standard evaluation, the paper also highlights results on 3 NLG tasks that help understand the RCD paradigm's applicability. \n\nImplementation of RESEAL involves two main strategies, probability surgery, and relation-guided lexical decoding. ", "questions": "1. Line 102: Based on the formulation the candidates are just getting re-ranked. How is the signal guaranteeing the presence of relation constraint?\n2. Line 130: Why is 2 needed in the denominator?\n3. Table 2: Shouldn't w/o prob = DBA? Why is the result different from DBA (Table 1)?\n4. Line 225: What is the word+rel strategy?\n\nTypo: \nLine 111: Line 1-7 -> Line 1-6", "limitations": "The paper highlights some of the limitations in section 5.1(results) and societal impacts in the appendix.\n\nLimitation: The model needs performance depends on access to a good relation identifier. The errors in the relation-identifier propagate into the model. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well written and easy to understand.\n2. Comprehensive evaluation of a variety of NLG tasks.\n3. Good results against competitive baselines.\n4. Fact-based editing is an elegant application of this paradigm.\n\nWeaknesses:\n1. Dependence upon a suitable relation identifier is a prerequisite. In most cases, it won't be easy to obtain/train. Thereby limiting the applicability of RCD to very simplistic tasks. In most cases, a lexically constrained decoding paradigm is sufficient.\n2. Evaluation on newer and robust NLG evaluators like BERTScore, and BLEURT is missing.\n3. No human evaluation of results.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rgv-zMfw3nP", "reviewer": "Reviewer_KEQA", "summary": "This paper presents a way to incorporate \"relation constraints\" in decoding. For example, given the constraint triplet: (phone, amod, fancy), the decoding process will attempt to generate a sentence with that includes words \"phone\" and \"fancy\" while also satisfying an \"amod\" relation based on a relation predictor (e.g. \"This is a fancy phone\"). This is an extension of the lexically-constrained decoding problem, though it seems that the relation constraints here are only satisfied probabilistically. ", "questions": "- In Table 1, it seems that some of the lexically-constrained decoding methods (e.g. DBA) are worse than Base. Is that expected? \n- Are there speed comparisons between proposed method and the simple Rerank baseline? \n- Can you provide some example sentences of your decoder vs DBA in the main part of the paper? This may help motivate the use of relations. \n- It seems to me that the relations in the decoder are always predicted. It is a hidden variable, so it is somewhat different in nature to the words in the lexical constraints, which are observed. If you have a poor relation predictor, can it fool your decoder into believing that the constraints are satifised? ", "limitations": "Appendix E writes: \"... our proposed methods may be used to generate more human-like fake text. However, the impacts are more apparent when considering deployed applications, while our proposed methods as the methodologies can not have any direct negative societal impacts.\" \n\nI am actually not sure what you are saying here. Do you mean that as a general technique, this does not have direct negative social impact, because the fault is with the application that uses this technique? I guess I see your point partly but I think the paragraph can be modified to say things in a better way. If your method is so good it makes it more difficult to detect fake text, isn't that a direct negative impact compared to other methods? ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrength\n- This is an interesting problem. Techniques that give us more control of the decoding process is generally a nice contribution to the field. I am not aware of previous work that incorporates relations. \n\nWeakness: \n- While relation contraints are interesting, it is not immediately clear in what applications they are helpful. Various tasks and results are shown, but I don't see intuitively why the relation constraint is important. For example, given the constraint triplet: (phone, amod, fancy), would a simple lexically-constraint decoder that uses (phone, fancy) produce those words in the right order anyway (due to a strong language model)? In contrast, would your relation-constrained decoder produce these words in the wrong order but still labeled with the right head-child dependency relation (due to a poor relation predictor)? Similarly, for the summarization problem, why do relations help? Perhaps the Data-to-Text and Fact-based Text editing tasks are easier to motivate, but the paper doesn't dedicate enough prose explaining these tasks. \n\n- The proposed method is difficult to understand. I think I got it after several readings, but there may be ways to improve especially the understanding of the general purpose of line 4 and 5 in Algo 1. One suggestion is to elaborate on the left part of Figure 1 (which explains line 4 at least). ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OjxYfxOZGao", "reviewer": "Reviewer_bPF5", "summary": "The paper is under the theme of constrained decoding, which incorporates predefined rules into a generated sentence. Compared with previous approaches mainly applied to words or phrases, the authors focus on the relations among them, which are called as Relation-Constrained Decoding (RCD). In terms of this setting, they introduce a model, RESEAL, that contains two special modules: RElation-guided probability Surgery and bEam ALlocation, which respectively modify the emission probabilities from the decoder and utilize the constraint information to guide the candidate selection of beam search.", "questions": "1, May you put some case studies to show how your model works in practice?\n2, Eq. (3) only considers past information; What about the future? Does this scoring style have a bias in this sense?\n3, It seems that applying p_{rel) in every decoding step is not reasonable. Could you explain more about this, especially the intuition of g?", "limitations": "I've mentioned previously in 'Strengths And Weaknesses': 1) No big difference between the proposed model and DBA except that the former applies external knowledge to change the emission probabilities of the decoder, which is a bit trivial; 2) the reliance of the introduced model on external knowledge.\n\nWill improve my score if the authors can address my concerns.\n", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: \n1) well-defined problem that is worth investigation;\n2) experiments on many tasks, which seems to be solid.\n\nCons:\n1) the writing of Sec. 3 needs to be polished. Also please don't use python codes in your Algorithm 2;\n2) the model seems to be incremental to DBA and is not flexible since it resorts to external knowledge (e.g., a well-trained dependency parser); I also think the authors should even clarify the external dependence issue in the introduction, which is the main problem we are facing in the NLP industry.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2kmjN6Byaiz", "reviewer": "Reviewer_hFXg", "summary": "The paper describes a model for text generation, based on target dependency relations that should be in the output.\nThe word-level output probabilties are modified to increase the likelihood of generating words that match the target relation.\nDuring beam decoding, the candidate construction method also takes the target relations into account.\nEvaluation is performed on several datasets, formulating the task as text generation based on dependency relations.", "questions": "It is currently unclear how many dependencies are given as input to the model. And if they are not all the dependencies, then how are they chosen.\n\nTable 8 in the appendix seems to have some issues. The dependencies in the first row do not match the sentences.\n", "limitations": "There is a very brief discussion of computational complexity in the appendix. There could be a much more thorough discussion on the limitations of the system, the task, the evaluation metrics and text generation based on dependencies in general.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The model is interesting.\nThe paper is well written and clear.\nThe specific method of modifying the output probabilities based on the given relations can be useful.\nResults are demonstrating the benefit of the proposed model over the chosen baselines.\n\nThe work is presented as a completely novel task. However, it does not sufficiently address existing work on data-to-text generation. \nIn data-to-text, the task is very similar - generation text based on relation tuples. \nWhile data-to-text systems do not typically restrict themselves to only dependency relations, they could definitely be applied on this task.\nTherefore, work in this area should be covered under related research and relevant baselines should be used for comparison.\nThere is currently a very minimal section for evaluation on a data-to-text dataset, but only a very generic model (not designed for data-to-text) is used as a baseline.\n\nThere is a nice section on dependency-guided generation, which has the same goal as the proposed task. However, none of the listed previous work seem to be reported as a baseline.\n\nThe proposed evaluation metrics are interesting for diagnostics but overall not very convincing.\nIt is claimed that overlap-based metrics are not appropriate and parser-based metrics are used instead. \nThis doesn't really reflect how readable the sentence is at all. \nFor a high score, the model could just linearise the triplets that are provided as input, without producing a coherent sentence. \nThe UC and LC metrics only measure recall, not precision, so there is no penalty for generating loads of different relations in the output.\nSimilarly, the Word% metric could just copy over the model input into the output in order to get a 100% score.\nBLEU 1-4 should be reported, along with METEOR. One BLEU is currently reported but it is unclear which one it is. BLEU-1 would not be sufficient to measure sentence quality.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept