We propose a new end-to-end model that treats AMR parsing as a series of dual decisions on the input sequence and the incrementally constructed graph. At each time step, our model performs multiple rounds of attention, reasoning, and composition that aim to answer two critical questions: (1) which part of the input sequence to abstract; and (2) where in the output graph to construct the new concept. We show that the answers to these two questions are mutually causalities. We design a model based on iterative inference that helps achieve better answers in both perspectives, leading to greatly improved parsing accuracy. Our experimental results significantly outperform all previously reported SMATCH scores by large margins. Remarkably, without the help of any large-scale pre-trained language model (e.g., BERT), our model already surpasses previous state-of-the-art using BERT. With the help of BERT, we can push the state-of-the-art results to 80.2% on LDC2017T10 (AMR 2.0) and 75.4% on LDC2014T12 (AMR 1.0). Abstract Meaning Representation (AMR) (Ba-narescu et al., 2013) is a broad-coverage semantic formalism that encodes the meaning of a sentence as a rooted, directed, and labeled graph, where nodes represent concepts and edges represent relations (See an example in Figure 1). AMR parsing is the task of transforming natural language text into AMR. One biggest challenge of AMR parsing is the lack of explicit alignments between nodes (con-cepts) in the graph and words in the text. This characteristic not only poses great difficulty in concept  The work described in this paper is substantially supported by grants from the Research Grant Council of the Hong Kong Special Administrative Region, China (Project Code: 14204418) and the Direct Grant of the Faculty of Engineering, CUHK (Project Code: 4055093). prediction but also brings a close tie for concept prediction and relation prediction. While most previous works rely on a pre-trained aligner to train a parser, some recent attempts include: modeling the alignments as latent variables (Lyu and Titov, 2018), attention-based sequence-to-sequence transduction models (Barzdins and Gosko, 2016; Konstas et al., 2017; van Noord and Bos, 2017), and attention-based sequence-to-graph transduction models (Cai and Lam, 2019; Zhang et al., 2019b). Sequence-to-graph transduction models build a semantic graph incrementally via spanning one node at every step. This property is appealing in terms of both computational efficiency and cognitive modeling since it mimics what human experts usually do, i.e., first grasping the core ideas then digging into more details (Banarescu et al., 2013; Cai and Lam, 2019). Unfortunately, the parsing accuracy of existing works including recent state-of-the-arts (Zhang et al., 2019a,b) remain unsatisfactory compared to human-level performance, 1 especially in cases where the sentences are rather long and informative, which indicates substantial room for improvement. One possible reason for the deficiency is the inherent defect of one-pass prediction process; that is, the lack of the modeling capability of the interactions between concept prediction and relation prediction, which is critical to achieving fully-informed and unambiguous decisions. We introduce a new approach tackling AMR parsing, following the incremental sequence-to-graph transduction paradigm. We explicitly characterize each spanning step as the efforts for finding which part to abstract with respect to the input sequence , and where to construct with respect to the partially constructed output graph . Equivalently, 1 The average annotator vs. inter-annotator agreement (SMATCH ) was 0.83 for newswire and 0.79 for web text according to Banarescu et al. (2013). we treat AMR parsing as a series of dual decisions on the input sequence and the incrementally constructed graph. Intuitively, the answer of what concept to abstract decides where to construct (i.e., the relations to existing concepts), while the answer of where to construct determines what concept to abstract. Our proposed model, supported by neural networks with explicit structure for attention, reasoning, and composition, integrated with an iterative inference algorithm. It iterates between finding supporting text pieces and reading the partially constructed semantic graph, inferring more accurate and harmonious expansion decisions progressively. Our model is aligner-free and can be effectively trained with limited amount of labeled data. Experiments on two AMR benchmarks demonstrate that our parser outperforms the previous best parsers on both benchmarks. It achieves the best-reported SMATCH scores (F1): 80.2% on LDC2017T10 and 75.4% on LDC2014T12, surpassing the previous state-of-the-art models by large margins. On a coarse-grained level, we can categorize existing AMR parsing approaches into two main classes: Two-stage parsing (Flanigan et al., 2014; Lyu and Titov, 2018; Zhang et al., 2019a) uses a pipeline design for concept identification and relation prediction, where the concept decisions precede all relation decisions; One-stage parsing constructs a parse graph incrementally. For more fine-grained analysis, those one-stage parsing methods can be further categorized into three types: Transition-based parsing (Wang et al., 2016; Damonte et al., 2017; Ballesteros and Al-Onaizan, 2017; Peng et al., 2017; Guo and Lu, 2018; Liu et al., 2018; Wang and Xue, 2017; Naseem et al., 2019) processes a sentence from left-to-right and constructs the graph incrementally by alternately inserting a new node or building a new edge. Seq2seq-based parsing (Barzdins and Gosko, 2016; Konstas et al., 2017; van Noord and Bos, 2017; Peng et al., 2018) views parsing as sequence-to-sequence transduction by some linearization of the AMR graph. The concept and relation prediction are then treated equally with a shared vocabulary. The third class is graph-based parsing (Cai and Lam, 2019; Zhang et al., 2019b), where at each time step, a new node along with its connections to existing nodes are jointly decided, either in order (Cai and Lam, 2019) or in parallel (Zhang et al., 2019b). So far, the recip-The boy must not go The boy must not go obligate-01 boy go-02 ARG2 A RG 0 p o l a r i t y obligate-01 ? rocal causation of relation prediction and concept prediction has not been closely-studied and well-utilized. There are also some exceptions staying beyond the above categorization. Peng et al. (2015) introduce a synchronous hyperedge replacement grammar solution. Pust et al. (2015) regard the task as a machine translation problem, while Artzi et al. (2015) adapt combinatory categorical grammar. Groschwitz et al. (2018); Lindemann et al. (2019) view AMR graphs as the structure AM algebra. Our approach is inspired by the deliberation process when a human expert is deducing a semantic graph from a sentence. The output graph starts from an empty graph and spans incrementally in a node-by-node manner. At any time step of this process, we are distilling the information for the next expansion. We call it expansion because the new node, as an abstract concept of some specific text fragments in the input sentence, is derived to complete some missing elements in the current semantic graph. Specifically, given the input sentence and the current partially constructed graph, we are answering two critical questions: which part of the input sequence to abstract, and where in the output graph to construct the new concept. For instance, Figure 1(a) and (b) show two possible choices for the next expansion. In Figure 1(a), the word boy is abstracted to the concept boy to complement the subject information of the event go-02 . On the (Current Graph) (Input Sequence) The boy wants the girl to believe him. other hand, in Figure 1(b), a polarity attribute of the event go-2 is constructed, which is triggered by the word not in the sentence. We note that the answer to one of the questions can help answer the other. For instance, if we have decided to render the word not to the graph, then we will consider adding an edge labeled as polarity , and finally determine its attachment to the existing event go-2 (rather than an edge labeled ARG0 to the same event go-2 , though it is also present in the golden graph). On the other hand, if we have decided to find the subject ( ARG0 relation) of the action go-02 , we are confident to locate the word boy instead of function words like not or must, thus unambiguously predict the right concept boy . Another possible circumstance is that we may make a mistake trying to ask something that is not present in the sentence (e.g., the destination of the go-02 action). This attempt will be rejected by a review of the sentence. The rationale is that literally we cannot find the destination information in the sentence. Similarly, if we mistakenly propose to abstract some parts of the sentence that are not ready for construction yet, the proposal will be rejected by another inspection on the graph since that there is nowhere to place such a new concept. We believe the mutual causalities, as described above, are useful for action disambiguation and harmonious decision making, which eventually result in more accurate parses. We formulate AMR parsing as a series of dual graph-sequence decisions and design an iterative inference approach to tackle each of them. It is sort of analogous to the cognition procedure of a person, who might first notice part of the important information in one side (graph or sequence), then try to confirm her decision at the other side, which could just refute her former hypothesis and propose a new one, and finally converge to a conclusion after multiple rounds of reasoning. Formally, the parsing model consists of a series of graph expansion procedures { G 0  . . .  G i  . . . } , starting from an empty graph G 0 . In each turn of expansion, the following iterative inference process is performed: y it = g ( G i , x it ) , x i t +1 = f ( W, y i t ) , where W, G i are the input sequence and the current semantic graph respectively. g (  ) , f (  ) seek where to construct (edge prediction) and what to abstract (node prediction) respectively, and x it , y it are the t -th graph hypothesis (where to construct) and t -th sequence hypothesis (what to abstract) for the i -th expansion step respectively. For clarity, we may drop the superscript i in the following descriptions. Figure 2 depicts an overview of the graph-sequence iterative inference process. Our model has four main components: (1) Sequence Encoder, which generates a set of text memories (per token) to provide grounding for concept alignment and abstraction; (2) Graph Encoder, which generates a set of graph memories (per node) to provide grounding for relation reasoning; (3) Concept Solver, where a previous graph hypothesis is used for concept prediction; and (4) Graph Solver, where a previous concept hypothesis is used for relation prediction. The last two components correspond to the reasoning functions g (  ) and f (  ) respectively. The text memories can be computed by Sentence Encoder at the beginning of the whole parsing while the graph memories are constructed by Graph Encoder incrementally as the parsing progresses. During the iterative inference, a semantic representation of current state is used to attend to both graph and text memories (blue and red arrows) in order to locate the new concept and obtain its relations to the existing graph, both of which subsequently refine each other. Intuitively, after a first glimpse of the input sentence and the current graph, specific sub-areas of both sequence and graph are revisited to obtain a better understanding of the current situation. Later steps typically read the text in detail with specific learning aims, either confirm-ing or overturning a previous hypothesis. Finally, after several iterations of reasoning steps, the refined sequence/graph decisions are used for graph expansion. As mentioned above, we employ a sequence encoder to convert the input sentence into vector representations. The sequence encoder follows the multi-layer Transformer architecture described in Vaswani et al. (2017). At the bottom layer, each token is firstly transformed into the concatenation of features learned by a character-level convolutional neural network (charCNN, Kim et al., 2016) and randomly initialized embeddings for its lemma, part-of-speech tag, and named entity tag. Additionally, we also include features learned by pre-trained language model BERT (Devlin et al., 2019). 2 Formally, for an input sequence w 1 , w 2 , . . . , w n with length n , we insert a special token BOS at the beginning of the sequence. For clarity, we omit the detailed transformations (Vaswani et al., 2017) and denote the final output from our sequence encoder as { h 0 , h 1 , . . . , h n }  R d , where h 0 corresponds the special token BOS and serves as an overall rep-2 We obtain word-level representations from pre-trained BERT in the same way as Zhang et al. (2019a,b), where subtoken representations at the last layer are averaged. resentation while others are considered as contextualized word representations. Note that the sequence encoder only needs to be invoked once, and the produced text memories are used for the whole parsing procedure. We use a similar idea in Cai and Lam (2019) to encode the incrementally expanding graph. Specifically, a graph is simply treated as a sequence of nodes (concepts) in the chronological order of when they are inserted into the graph. We employ multi-layer Transformer architecture with masked self-attention and source-attention, which only allows each position in the node sequence to attend to all positions up to and including that position, and every position in the node sequence to attend over all positions in the input sequence. 3 While this design allows for significantly more parallelization during training and computation-saving incremen-tality during testing, 4 it inherently neglects the edge information. We attempted to alleviate this problem by incorporating the idea of Strubell et al. (2018) that applies auxiliary supervision at attention heads to encourage them to attend to each node's parents in the AMR graph. However, we did not see performance improvement. We attribute the failure to the fact that the neural attention mechanisms on their own are already capable of learning to attend to useful graph elements, and the auxiliary supervision is likely to disturb the ultimate parsing goal. Consequently, for the current graph G with m nodes, we take its output concept sequence c 1 , c 2 , . . . , c m as input. Similar to the sequence encoder, we insert a special token BOG at the beginning of the concept sequence. Each concept is firstly transformed into the concatenation of feature vector learned by a char-CNN and randomly initialized embedding. Then, a multi-layer Transformer encoder with masked self-attention and source-attention is applied, resulting in vector representations { s 0 , s 1 , . . . , s m }  R d , where s 0 represents the special concept BOG and serves as a dummy node while others are considered as contextualized node representations. 3 It is analogous to a standard Transformer decoder (Vaswani et al., 2017) for sequence-to-sequence learning. 4 Trivially employing a graph neural network here can be computationally expensive and intractable since it needs to re-compute all graph representations after every expansion. At each sequence reasoning step t , the concept solver receives a state vector y t that carries the latest graph decision and the input sequence memories h 1 , . . . , h n from the sequence encoder, and aims to locate the proper parts in the input sequence to abstract and generate a new concept. We employ the scaled dot-product attention proposed in Vaswani et al. (2017) to solve this problem. Concretely, we first calculate an attention distribution over all input tokens:  t = softmax (( WQ y t ) TWK h 1: n  d k ) , where { WQ , WK }  R d k  d denote learnable linear projections that transform the input vectors into the query and key subspace respectively, and d k represents the dimensionality of the subspace. The attention weights  t  R n provide a soft alignment between the new concept and the tokens in the input sequence. We then compute the probability distribution of the new concept label through a hybrid of three channels. First,  t is fed through an MLP and softmax to obtain a probability distribution over a pre-defined vocabulary: MLP (  t ) = ( WV h 1: n )  t + y t (1) P (vocab) = softmax ( W (vocab) MLP (  t ) + b (vocab) ) , where WV  R d  d denotes the learnable linear projection that transforms the text memories into the value subspace, and the value vectors are averaged according to  t for concept label prediction. Second, the attention weights  t directly serve as a copy mechanism (Gu et al., 2016; See et al., 2017), i,e., the probabilities of copying a token lemma from the input text as a node label. Third, to address the attribute values such as person names or numerical strings, we also use  t for another copy mechanism that directly copies the original strings of input tokens. The above three channels are combined via a soft switch to control the production of the concept label from different sources: [ p 0 , p 1 , p 2 ] = softmax ( W (switch) MLP (  t )) , where MLP is the same as in Eq. 1, and p 0 , p 1 and p 2 are the probabilities of three prediction channels respectively. Hence, the final prediction probability of a concept c is given by: P ( c ) = p 0  P (vocab) ( c ) + p 1  ( (cid:88) i  L ( c )  t [ i ]) + p 2  ( (cid:88) i  T ( c )  t [ i ]) , where [ i ] indexes the i -th element and L ( c ) and T ( c ) are index sets of lemmas and tokens respectively that have the surface form as c . At each graph reasoning step t , the relation solver receives a state vector x t that carries the latest concept decision and the output graph memories s 0 , s 1 , . . . , s m from the graph encoder, and aims to point out the nodes in the current graph that have an immediate relation to the new concept (source nodes) and generate corresponding edges. Similar to Cai and Lam (2019); Zhang et al. (2019b), we factorize the task as two stages: First, a relation identification module points to some preceding nodes as source nodes; Then, the relation classifica-tion module predicts the relation type between the new concept and predicted source nodes. We leave the latter to be determined after iterative inference. AMR is a rooted, directed, and acyclic graph. The reason for AMR being a graph instead of a tree is that it allows reentrancies where a concept participates in multiple semantic relations with different semantic roles. Following Cai and Lam (2019), we use multi-head attention for a more compact parsing procedure where multiple source nodes are simultaneously determined. 5 Formally, our relation identification module employs H different attention heads, for each head h , we calculate an attention distribution over all existing node (including the dummy node s 0 ):  ht = softmax ( ( W Qh x t ) TW Kh s 0: m  d k ) . Therefore, different heads may points to different nodes at the same time. Intuitively, each head represents a distinct relation detector for a particular 5 This is different to Zhang et al. (2019b) where an AMR graph is converted into a tree by duplicating nodes that have reentrant relations. set of relation types. For each attention head, it will point to a source node if certain relations exist between the new node and the existing graph, otherwise it will point to the dummy node. An example with four attention heads and three existing nodes (excluding the dummy node) is illustrated in Figure 3. As described above, the concept solver and the relation solver are conceptually two attention mechanisms over the sequence and graph respectively, addressing the concept prediction and relation prediction separately. The key is to pass the decisions between the solvers so that they can examine each other's answer and make harmonious decisions. Specifically, at each spanning step i , we start the iterative inference by setting x 0 = h 0 and solving f ( G i , x 0 ) . After the t -th graph reasoning, we compute the state vector y t , which will be handed over to the concept solver as g ( W, y t ) , as: y t = FFN ( y ) ( x t + ( WV h 1: n )  t ) , where FFN ( y ) is a feed-forward network and WV projects text memories into a value space. Similarly, after the t -th sequence reasoning, we update the state vector from y t to x t +1 as: x t +1 = FFN ( x ) ( y t + H (cid:88) h =1 ( W Vh s 0: n )  ht ) , where FFN ( x ) is a feed-forward network and W Vh projects graph memories into a value space for each head h . After N steps of iterative inference, i,e., x 0  f ( G i , x 0 )  y 1  g ( W, y 1 )  x 1      f ( G i , x N  1 )  y N  g ( W, y N )  x N , we finally employ a deep biaffine classifier (Dozat and Manning, 2016) for edge label prediction. The Algorithm 1 AMR Parsing via Graph (cid:28) Sequence Iterative Inference Input: the input sentence W = ( w 1 , w 2 , . . . , w n ) Output: the corresponding AMR graph G // compute text memories 1: h 0 , h 1 , . . . , h n = SequenceEncoder(( BOS , w 1 , . . . , w n )) // initialize graph 2: G 0 = ( nodes = { BOG } , edges =  ) // start graph expansions 3: i = 0 4: while True do 5: s 0 , . . . , s i = GraphEncoder( G i ) // the graph memories can be computed *incrementally* 6: x 0 = h 0 // iterative inference 7: for t  1 to N do 8: y t = f ( G i , x t  1 ) // Seq. classifier uses a biaffine function to score each label, given the final concept representation x N and the node vector s 1: m as input. The resulted concept, edge, and edge label predictions will added to the new graph G i +1 if the concept prediction is not EOG , a special concept that we add for indicating termination. Otherwise, the whole parsing process is terminated and the current graph is returned as final result. The complete parsing process adopting the iterative inference is described in Algorithm 1. Our model is trained with the standard maximum likelihood estimate. The optimization objective is to maximize the sum of the decomposed step-wise log-likelihood, where each is the sum of concept, edge, and edge label probabilities. To facilitate training, we create a reference generation order of nodes by running a breadth-first-traversal over target AMR graphs, as it is cognitively appealing (core-semantic-first principle, Cai and Lam, 2019) and the effectiveness of pre-order traversal is also empirically verified by Zhang et al. (2019a) in a depth-first setting. For the generation order for sibling nodes, we adopt the uniformly random order and the deterministic order sorted by the relation frequency in a 1 : 1 ratio at first then change to the deterministic order only in the final training steps. We empirically find that the deterministic-after-random strategy slightly improves performance. During testing, our model searches for the best output graph through beam search based on the log-likelihood at each spanning step. The time complexity of our model is O ( k | V | ) , where k is the beam size, and | V | is the number of nodes. Datasets Our evaluation is conducted on two AMR public releases: AMR 2.0 (LDC0217T10) and AMR 1.0 (LDC2014T12). AMR 2.0 is the latest and largest AMR sembank that was extensively used in recent works. AMR 1.0 shares the same development and test set with AMR, while the size of its training set is only about one-third of AMR 2.0, making it a good testbed to evaluate our model's sensitivity for data size. 6 Implementation Details We use Stanford CoreNLP (Manning et al., 2014) for tokenization, lemmatization, part-of-speech, and named entity tagging. The hyper-parameters of our models are chosen on the development set of AMR 2.0. Without explicit specification, we perform N = 4 steps of iterative inference. Other hyper-parameter settings can be found in the Appendix. Our models are trained using ADAM (Kingma and Ba, 2014) for up to 60K steps (first 50K with the random sibling order and last 10K with deterministic order), with early stopping based on development set performance. We fix BERT parameters similar to Zhang et al. (2019a,b) due to the GPU memory limit. During testing, we use a beam size of 8 for the highest-scored graph approximation. 7 AMR Preand Post-processing We remove senses as done in Lyu and Titov (2018); Zhang et al. (2019a,b) and simply assign the most frequent sense for nodes in post-processing. Notably, 6 There are a few annotation revisions from AMR 1.0 to AMR 2.0. 7 Our code is released at https://github.com/ jcyk/AMR-gs . most existing methods including the state-the-of-art parsers (Zhang et al., 2019a,b; Lyu and Titov, 2018; Guo and Lu, 2018, inter alia) often rely on heavy graph re-categorization for reducing the complexity and sparsity of the original AMR graphs. For graph re-categorization, specific subgraphs of AMR are grouped together and assigned to a single node with a new compound category, which usually involves non-trivial expert-level manual efforts for hand-crafting rules. We follow the exactly same preand post-processing steps of those of Zhang et al. (2019a,b) for graph re-categorization. More details can be found in the Appendix. Ablated Models As pointed out by Cai and Lam (2019), the precise set of graph re-categorization rules differs among different works, making it dif-ficult to distinguish the performance improvement from model optimization and carefully designed rules. In addition, only recent works (Zhang et al., 2019a,b; Lindemann et al., 2019; Naseem et al., 2019) have started to utilize the large-scale pre-trained language model, BERT (Devlin et al., 2019; Wolf et al., 2019). Therefore, we also include ablated models for addressing two questions: (1) How dependent is our model on performance from handcrafted graph re-categorization rules? (2) How much does BERT help? We accordingly implement three ablated models by removing either one of them or removing both. The ablation study not only reveals the individual effect of two model components but also helps facilitate fair comparisons with prior works. Main Results The performance of AMR parsing is conventionally evaluated by SMATCH (F1) metric (Cai and Knight, 2013). The left block of Table 1 shows the SMATCH scores on the AMR 2.0 test set of our models against the previous best approaches and recent competitors. On AMR 2.0, we outperform the latest push from Zhang et al. (2019b) by 3.2% and, for the first time, obtain a parser with over 80% SMATCH score. Note that even without BERT, our model still outperforms the previous state-of-the-art approaches using BERT (Zhang et al., 2019b,a) with 77.3%. This is particularly remarkable since running BERT is computationally expensive. As shown in Table 2, on AMR 1.0 where the training instances are only around 10K, we improve the best-reported results by 4.1% and reach at 75.4%, which is already higher than Model G. R. BERT SMATCH fine-grained evaluation Unlabeled No WSD Concept SRL Reent. most models trained on AMR 2.0. The even more substantial performance gain on the smaller dataset suggests that our method is both effective and data-efficient. Besides, again, our model without BERT already surpasses previous state-of-the-art results using BERT. For ablated models, it can be observed that our models yield the best results in all settings if there are any competitors, indicating BERT and graph re-categorization are not the exclusive key for our superior performance. Fine-grained Results In order to investigate how our parser performs on individual sub-tasks, we also use the fine-grained evaluation tool (Da-monte et al., 2017) and compare to systems which reported these scores. 8 As shown in the right block of Table 1, our best model obtains the highest scores on almost all sub-tasks. The improvements in all sub-tasks are consistent and uniform (around 2%  3%) compared to the previous state-of-the-art performance (Zhang et al., 2019b), partly confirm-ing that our model boosts performance via consolidated and harmonious decisions rather than fix-ing particular phenomena. By our ablation study, 8 We only list the results on AMR 2.0 since there are few results on AMR 1.0 to compare. it is worth noting that the NER scores are much lower when using graph re-categorization. This is because the rule-based system for NER in graph re-categorization does not generalize well to unseen entities, which suggest a potential improvement by adapting better NER taggers. Effect of Iterative Inference We then turn to study the effect of our key idea, namely, the iterative inference design. To this end, we run a set of experiments with different values of the number of the inference steps N . The results on AMR 2.0 are shown in Figure 4 (solid line). As seen, the performance generally goes up when the number of inference steps increases. The difference is most noticeable between 1 ( no iterative reasoning is performed) and 2, while later improvements gradually diminish. One important point here is that the model size in terms of the number of parameters is constant regardless of the number of inference steps, making it different from general over-parameterized problems. For a closer study on the effect of the inference steps with respect to the lengths of input sentences, we group sentences into three classes by length and also show the individual results in Figure 4 (dashed lines). As seen, the iterative inference helps more for longer sentences, which confirms our intuition that longer and more complex input needs more reasoning. Another interesting observation is that the performance on shorter sentences reaches the peaks earlier. This observation suggests that the number of inference steps can be adjusted according to the input sentence, which we leave as future work. Effect of Beam Size We are also interested in the effect of beam size during testing. Ideally, if a model is able to make accurate predictions in the first place, it should rely less on the search algorithm. We vary the beam size and plot the curve in Figure 6. The results show that the performance generally gets better with larger beam sizes. However, a small beam size of 2 already gets the most of the credits, which suggests that our model is robust enough for time-stressing environments. Visualization We visualize the iterative reasoning process with a case study in Figure 5. We illustrate the values of  t ,  t as the iterative inference progresses. As seen, the parser makes mistakes in the first step, but gradually corrects its decisions and finally makes the right predictions. Later reasoning steps typically provide a sharper attention distribution than earlier steps, narrowing down the most likely answer with more confidence. Speed We also report the parsing speed of our non-optimized code: With BERT, the parsing speed of our system is about 300 tokens/s, while without BERT, it is about 330 tokens/s on a single Nvidia P4 GPU. The absolute speed depends on various implementation choices and hardware performance. In theory, the time complexity of our parsing algorithm is O ( kbn ) , where k is the number of iterative steps, b is beam size, and n is the graph size (num-ber of nodes) respectively. It is important to note that our algorithm is linear in the graph size. We presented the dual graph-sequence iterative inference method for AMR Parsing. Our method constructs an AMR graph incrementally in a node-by-node fashion. Each spanning step is explicitly characterized as answering two questions: which parts of the sequence to abstract, and where in the graph to construct. We leverage the mutual causalities between the two and design an iterative inference algorithm. Our model significantly advances the state-of-the-art results on two AMR corpora. An interesting future work is to make the number of inference steps adaptive to input sentences. Also, the idea proposed in this paper may be applied to a broad range of structured prediction tasks (not only restricted to other semantic parsing tasks) where the complex output space can be divided into two interdependent parts with a similar iterative inference process to achieve harmonious predictions and better performance.
objective objective result result result result result abstain abstain abstain abstain abstain other abstain abstain abstain abstain objective result abstain method abstain objective abstain method objective abstain abstain other other other other other other other other other other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain method abstain abstain method abstain other abstain abstain method abstain method abstain method abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain method abstain abstain other abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain abstain abstain method method abstain method other abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain method abstain method method method method abstain method method method method abstain other abstain abstain method abstain abstain abstain method abstain method abstain abstain result abstain result abstain result abstain abstain result result abstain result abstain result abstain abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain method result abstain objective