Standard conversational semantic parsing maps a complete user utterance into an executable program, after which the program is executed to respond to the user. This could be slow when the program contains expensive function calls. We investigate the opportunity to reduce latency by predicting and executing function calls while the user is still speaking. We introduce the task of online semantic parsing for this purpose, with a formal latency reduction metric inspired by simultaneous machine translation. We propose a general framework with first a learned prefix-to-program prediction module, and then a simple yet effective thresholding heuristic for subprogram selection for early execution. Experiments on the SMCalFlow and TreeDST datasets show our approach achieves large latency reduction with good parsing quality, with a 30%63% latency reduction depending on function execution time and allowed cost. In task-oriented dialogue systems, a software agent typically translates a user's intent into a program, executes it to query information sources (e.g., find a person in the user's contact list) or effect external actions (e.g., schedule a meeting or send an email), then communicates the results back to the user. If an agent waits to begin this process until the user finishes speaking, there is a noticeable lag before the user receives a response. The complex intents in the datasets SMCalFlow (Semantic Machines et al., 2020) and TreeDST (Cheng et al., 2020), for example, can be slow to execute, nesting up to 7 slow function calls that cannot be parallelized. Inspired by simultaneous machine translation, we ask: How much can latency be reduced by interpreting and executing early, before the user finishes speaking? Work performed during a research internship at Microsoft Semantic Machines. In general, an agent could begin speculatively executing any subprogram at any instant while a user is speaking, based on partial results from automatic speech recognition (ASR) and the current state of execution. Take Figure 1 for a hypothetical example. If partial programs can be identified while the user is still speaking, they can be pre-executed and the final response to the user could be expedited. This is an online decision problem: decisions to invoke particular functions on particular arguments can be made before all information has arrived. Thus, we refer to it as online semantic parsing . This requires spotting user intents that have already been expressed (without the help of aligned training data) andeven harderanticipating user intents that have not been expressed yet. To assess an online semantic parser, we propose reporting the reduction in latency of the agent's final response (relative to an offline agent), as measured by real or simulated execution of the function calls. We propose two approaches. Our first system is built on a neural graph-based semantic parser, which is specially trained to parse an incomplete utterance into a full program. Our second system is a pipeline that uses a language model (LM) to predict how a user will finish the incomplete utterance, and then parses the predicted completed utterance. In either case, a subprogram is selected for execution as soon as the semantic parser predicts that it has a high probability of being in the correct parse. Experiments on both SMCalFlow and TreeDST datasets show that both approaches achieve high latency reduction with a small number of excess function calls. We make three main contributions: First, we propose a new task for online semantic parsing and a realistic evaluation metric for latency reduction. Second, we present a neural graph-based semantic parser that matches or surpasses the state-of-the-art on SMCalFlow and TreeDST, and extend it to support two novel approaches to map utterance prefixes to programs. Third, we show our approaches achieve estimated latency reductions of 30%63%, setting up a good benchmark for future explorations. Simultaneous Translation Our task is inspired by the online version of machine translation (MT), known as simultaneous MT , which aims to translate a source sentence in real time into a target language (Wahlster, 1993). The latency of such a system is assessed by counting how many source tokens it has observed before it produces the first, second, third, etc. target token. These counts are aggregated into an overall latency metrica measure either of waiting, such as Average Proportion (AP) (Cho and Esipova, 2016) and Consecutive Wait (CW) (Gu et al., 2017), or of lagging (in comparison with an ideally paced system), such as Average Lagging (AL) (Ma et al., 2019) and Differentiable Average Lagging (DAL) (Cherry and Foster, 2019; Arivazhagan et al., 2019). We discuss the relationship of our proposed metric to DAL and other existing metrics in Section 4.3. Approaches to simultaneous MT include explicit source word prediction (Grissom II et al., 2014), discrete decision sequence modeling with reinforcement learning (Satija and Pineau, 2016; Gu et al., 2017), latency-controllable waitk systems with fixed scheduling (Ma et al., 2019), learned adaptive scheduling (Arivazhagan et al., 2019), and retranslation (Arivazhagan et al., 2020a,b). Executable Programs as Semantic Graphs Semantic parsing maps natural language to structured meaning representations (MRs) that can be executed or reasoned about. These include general-purpose MRs (Clark and Curran, 2007; Banarescu et al., 2013), database queries (Tang and Mooney, 2001; Zettlemoyer and Collins, 2005; Yu et al., 2018), and source code in general-purpose programming languages (Yin and Neubig, 2017), etc. Despite formal differences, these representations can generally be represented as graphs. We will focus on the dataflow graph (Semantic Machines et al., 2020), which represents an executable program in response to a user's utterance in a task-oriented dialogue system (Zettlemoyer and Collins, 2009). Each function invocation is represented by a node, whose label specifies the function, and whose outgoing 1 edges indicate its arguments, which may be constants or other function invocations. Preliminaries Formally, we represent a program as a labeled directed acyclic graph G = ( V, E ) , where each node v  V represents a function invocation or a constant value, and each directed edge u (cid:96)  v  E represents that v fills the (cid:96) argument of the function u . Positional arguments are given edge labels arg0 , arg1 , etc. We use graph and program interchangeably hereon. In task-oriented dialogue systems, an executable program G is generated in response to a user utterance u with possible context c from the dialogue history. The utterance is a token sequence u = ( u 1 , u 2 , . . . , u | u | ) and the context is also encoded as a sequence c = ( c 1 , c 2 , . . . , c | c | ) . We use u [ m ] to denote the m th prefix presented to the online system, and t m to denote the time at which it is presented. t denotes the time at which the complete utterance u is presented. In our experiments, each u [ m ] is some prefix of the gold utterance u . A real system could use the noisy partial outputs returned by an ASR system from successively longer speech prefixes. Each partial ASR output u [ m ] is returned at some time t m  R . It may append one or more words to the previous output u [ m  1] , and may also revise some words. An offline system models p ( G | c , u ) , predicting the program only after the user utterance u has been fully received. But our online system aims 1 Our description has reversed the edge directions from Semantic Machines et al. (2020). to simultaneously parse u as the user utters it, so as to pre-execute subprograms to reduce the final response time. Our setting differs from simultaneous MT in an important way: we currently do not show the user any output until their utterance is complete. So speculatively executing a predicted subprogram, silently, does not commit to using it in the final result. Our parse of u [ m  1] therefore does not constrain our parse of u [ m ] . 2 Indeed, in this work, we re-parse each prefix from scratch. We distinguish between the time or times at which a function invocation is selected by the system for execution, the time it is actually executed , and the time it returns . A selected function invocation is not actually executed until its arguments have returned from execution. But by that point, the system may have deselected it (and so will not execute it), since the system's predictions may have changed based on additional input. After each successive utterance prefix u [ m ] , we perform the following two steps (see Figure 2): 1. propose : Predict the complete graph G from only the current prefix u [ m ] and context c . 2. select : Select the graph nodes (function invocations) that are worth executing at this time. This is an update that replaces the former list of selected nodes; so any formerly selected nodes that were still waiting for their arguments have lost their chance to execute until they are selected again. 3 In the first step, we currently search for the single most probable G . More generally, one could construct an estimate of the distribution p ( G | c , u [ m ] ) . In the second step, we select nodes that are probably correct, using a heuristic approximation to their marginal probability. In future work, selecting a node should also consider the predicted execution cost and the predicted effect on overall latency. An alternative design would collapse propose and select into a single step that directly predicts some graph fragments to execute. But as gold fragments are not defined, this would require a more complicated training objective. Predicting complete programs may also yield more accurate fragments, by making latent structure explicit. We first describe our general approach for graph prediction (Section 3.1), followed by two different approaches for propose (Section 3.23.3), and finally our heuristic for select (Section 3.4). We encode any graph G as a sequence a = ( v 1 , e 1 , v 2 , e 2 , . . . , v | V | , e | E | ) . Each element of a can be regarded as an action that adds a node or a sequence of edges to the graph. Note that the subgraphs selected in Section 3.4 below will not necessarily correspond to contiguous substrings of a . This representation is borrowed from the action-pointer mechanism in Zhou et al. (2021a), but they are operating with graph-utterance alignments in a transition-based model, whereas we develop a more general alignment-free model. Each v k is a node, representing a constant value or function invocation, while each e k is a subsequence that lists all edges between v k and earlier nodes. At training time, graphs are converted to action sequences to enable us to train a sequence-to-sequence model. At inference time, the model outputs the action sequence, from which the graph can be constructed. In our action sequence representation, each node and each edge in G corresponds to one token in a , with the only exception being string literals, which can span multiple action tokens. A token of a string literal can appear directly as an action or can be copied from the j th token of the source via a special COPYINPUT ( j ) action. The details of the formulation of the action sequence and the model parametrization can be found in Appendix A. For an offline parser, the model learns p ( G | c , u ) = (cid:81) | a | n =1 p ( a n | c , u , a 1: n  1 ) , where the input to the encoder is the concatenation of the context and the full utterance. We call this standard setup FULLTOGRAPH . The FULLTOGRAPH model achieves very strong performance when trained and tested on the standard offline benchmark (see Table 1). We could simply run this trained model on utterance prefixes for our propose step, but that would suffer from a train-test mismatch. Thus, we replace it with a PREFIXTOGRAPH model p ( G | c , u [ m ] ) that we explicitly train to map from each prefix of u to the complete graph. Every (( c , u ) , G ) pair in the original training data is multiplied into many training pairs (( c , u [ m ] ) , G ) . Notice that we always use 1556 B D C E A B (A,B) D (B,D) E (B,E) C (C,E) (A,C) A B D E D E A B (A,B) D (B,D) E (A,E) A actions full utterance: offline graph B C X A B (A,B) D (B,D) X (B,X) C (A,C) E (C,E) A Z actions actions utterance prefix: 2 utterance prefix: 1 graph graph selection selection Y D C E A Y (A,Y) D (Y,D) E (Y,E) C (C,E) (A,C) Z (Z,C) A actions utterance prefix: 3 graph selection Figure 2: Our framework for simultaneous semantic parsing. the full graph as the target, rather than attempting to predict only the part of the graph that aligns to the prefix. Hence our method requires no alignment. It tries to predict any function calls that are likely given the prefix, even if they have not been explicitly mentioned yet. A problem with this setup is that the target graph is often unreachable because it contains string literals that have not been seen yet. This happens when the gold action sequence includes COPYINPUT ( j ) and j is a position beyond the current prefix. To handle such cases, we modify the target action sequence to instead copy the final position of the prefix, where we have appended a special MASK token as a placeholder for all future tokens. Such a modified training example is shown in the second row of Figure 3. In this way, we disable hallucination of free text by the model, while keeping the graph structure intact with the MASK placeholder. Alternatively, propose can first predict the full utterance from the prefix, and use FULLTOGRAPH to parse this completed utterance. 4 Specifically, we 4 To avoid training-test mismatch, we could have retrained FULLTOGRAPH to predict the gold graphs from these noisily fine-tune a pretrained BART model (Lewis et al., 2020) so that it can map an utterance prefix (ter-minated with the MASK symbol, just as in BART's pre-training recipe) to the full utterance (freely hallucinating content words). As before, the training data includes one example for each prefix of each utterance, so the fine-tuning objective is to maximize the sum of log p ( u | c , u [ m ] ) over all prefixes u [ m ] of all utterances u . Let  G m be the graph proposed from u [ m ] . We wish to execute only its probable subgraphs. Recall that we predicted  G m by attempting to maximize (cid:81) | a | n =1 p ( a n | c , u [ m ] , a 1: n  1 ) (approach 1) or p ( u | c , u [ m ] )  (cid:81) | a | n =1 p ( a n | c , u , a 1: n  1 ) (ap-proach 2). The probability of a subgraph could be obtained by marginalizing over all possible action sequences (and also all completions u in approach 2), which could be approximated by sampling from the models. For simplicity and efficiency, we instead approximate the probability of a subgraph of  G m by the product of the conditional probabilities of the predicted actions that actually built that subgraph 5 that is, each subgraph of the predicted  G m was built by a subset of the predicted actions a . This essentially approximates the marginal probability of the relevant action subsequence by its conditional probability given preceding actions. In practice we found that this simplified heuristic works relatively well, with action-level likelihoods completed utterances, instead of from the gold utterances. However, this learning problem might be too difficult. Instead, we will consider the uncertainty of completion during select . 5 In approach 2, this includes the probabilities of the predicted unseen tokens of u . We cannot limit to the tokens that contributed to the subgraph because all tokens potentially did so: we do not have an alignment. Thus, when p ( u | c , u [ m ] ) is small, all subgraphs will be regarded as uncertain. being decently calibrated (Section 6.4). We then select the nodes v   G m such that the subgraph rooted at v has probability above a constant threshold  . 6 There are three exceptions: (1) Of course we do not select any node whose subgraph we have previously executed (after predicting and selecting it from a previous prefix). That is unnecessary: we already know the result or are waiting for it. (2) Until the utterance is complete, we do not select any nodes whose function invocations have side effects, as they are unsafe to pre-execute. (In particular, we do not show final results to the user.) (3) But once the utterance is complete, we select all unexecuted nodes of the final predicted graph,  G , since now they are both safe and necessary to execute. To quantify the latency improvements for online semantic parsing methods, we propose a new metric, final latency reduction. We assume that functions can be executed, in parallel, as soon as their arguments are available. Given a graph G , any node v  G is the root of an executable subgraph. Let g ( v ) be the time that this subgraph is selected. 7 Let e ( v )  0 be the time it takes to execute just the function at v on its given arguments. 8 The return time r ( v ) of node v is r ( v ) = max[ g ( v ) , max w  children ( v ) r ( w )] + e ( v ) (1) where children ( v ) is the set of nodes that return the arguments of v . This is a recursive definitiona node can only be executed after it is selected and all its children (if any) have finished executingand 6 As Section 3 noted, this strategy is not optimal. All subgraphs with the same probability do have the same risk of being useless work, but they do not all represent the same amount of useless work: some incorrect subgraphs require more computation. And they have the same probability of being useful work, but they are not all equally useful : some correct subgraphs can be postponed for longer without affecting the overall latency, because they will run more quickly or will not be needed as soon. In both cases, it would be appropriate to raise the subgraph's threshold and wait for more evidence that the subgraph is actually correct. 7 More precisely, the final time that this happens; it may have previously been selected but not executed (section 3). 8 e ( v ) could be modeled as a random variable with some distribution learned from data, so that FLR becomes a random variable whose expectation we would report. In our simulated experiments we model it by a constant  for all slow function calls, and 0 otherwise. so r ( v )  r ( w ) for w  children ( v ) . The program G finishes executing at time 9 r ( G ) = max v  G r ( v ) (2) We assume that our own system's computation time is negligible, so g ( v ) = t m if the subgraph rooted at v was predicted and selected from u [ m ] . In our fully simulated experiments, we set t m = m , which measures time in units of input tokens. These practices follow the simultaneous machine translation literature (Cho and Esipova, 2016; Gu et al., 2017; Ma et al., 2019; Cherry and Foster, 2019). In Section 5, we will also explore using real-time measurements to define t m . We compute the time at which the system completes executing the gold graph G  , namely r ( G  ) . Thus, the system cannot achieve a good completion time simply by predicting a small graph. The system's final latency is r ( G  )  t . Note that r ( G  )  t , since at least the root node that shows final results to the user has to wait until the utterance is complete (section 3.4). If the system's final prediction  G (cid:54) = G  , then there may be nodes v  G  whose subgraph was never executed. Then r ( G  )  r ( v ) =  , properly speakingbut we keep it finite by defining g ( v ) = t for these nodes v . That is, for purposes of latency evaluation, we generously consider the worst case for v  G  to be that v is selected for execution when the utterance is complete (rather than that v is never executed). We also compute a baseline: r o ( G  ) is the completion time r ( G  ) achieved by the offline parser, which is a batch system that sees no prefixes before seeing the full utterance at time t . It is found by setting g ( v ) = t for all v  G  in equations (1)(2). We now define our final latency reduction FLR = r o ( G  )  r ( G  )  0 (3) An oracle system would have g ( v ) = 0 for all v  G  , achieving the best possible final latency of max( r o ( G  )  t, t ) and the best possible FLR of min( t, r o ( G  )  t ) . This is the FLR upper bound. FLR focuses on how much sooner the user can see results from the target program after the user has finished speaking. This is different from simultaneous MT, whose focus is how far the target is lagging behind while the user is speaking. Therefore, instead of measuring the average over different subprograms, our metric attends to the final completion of the whole program. This allows flexibility in execution order, compared to the translation scenario, where target generation always follows a linear order. We share with other simultaneous generation applications the assumption that the model inference time is negligible, compared to slower spoken input and program execution (which may involve system and database interactions). Separate from the final form of our FLR metric, our latency measurement of subprogram return time r ( v ) can be seen as a generalization of the target time measurement in DAL (Cherry and Foster, 2019) for simultaneous MT. Our program execution time is analogous to the target speaking time in DAL, but DAL operates in a narrower spectrum with a linear chain structured target, and a fixed constant estimate for the target speaking rate. Data We make use of two recently released large-scale conversational semantic parsing datasets, SMCalFlow v2.0 (Semantic Machines et al., 2020) and the version of TreeDST (Cheng et al., 2020) released by Platanios et al. (2021). Table 1 and Appendix B provide statistics about the datasets. Model Training We use the training splits of these datasets to train our FULLTOGRAPH , PREFIXTOGRAPH , and LMCOMPLETE models, and evaluate them on the corresponding validation data. From each training example ( u , G ) , we extract prefixes of different relative lengths, obtaining ( u 0% , G ) , ( u 10% , G ) , . . . , ( u 90% , G ) , ( u 100% , G ) . 10 The prefix-graph pairs of the same percentage length are then stacked to form different training sets, denoted as { prefix0%, prefix10%, . . . , prefix90%, prefix100% } . The FULLTOGRAPH parser is trained only using the prefix100% data. For our PREFIXTOGRAPH parser, we experiment with training on different mixtures of the prefix datasets, to quantify the effect on parsing accuracy. For LMCOMPLETE we train on all pairs ( u (cid:48) , G ) where u (cid:48) is a prefix of u of any length (not limited to the above percentages). Model Details All of our parsers are based on the Transformer architecture (Vaswani et al., 2017), adapted to the graph action sequence (see Appendix A). The LMCOMPLETE is based on fine-tuning the pre-trained BART large model (Lewis et al., 2020). One turn of dialogue history is included as the context c . We use greedy decoding for all models. See more details in Appendix E. 11 Model Evaluation We directly evaluate the parsers FULLTOGRAPH and PREFIXTOGRAPH using exact match accuracy (Semantic Machines et al., 2020; Cheng et al., 2020; Platanios et al., 2021). We also report a finer-grained metric, graph tuple match (Anderson et al., 2016): the F1 score of the set of labeled nodes and labeled edges in the predicted parse. We evaluate LMCOMPLETE using BLEU score (Papineni et al., 2002). Online Parsing Evaluation For online parsing, we simulate the program execution procedure described in Section 4.1, presenting the system with all prefixes of u in order: that is, u [ m ] = ( u 1 , . . . , u m ) . We experiment with different probability thresholds  . For each  , we report the benefit of our approach as FLR, versus the cost as the number of excess function calls (on top of gold). When computing FLR, we consider two defi-nitions of t m : an intrinsic one with everything measured by the number of source tokens ( t m = | u [ m ] | ) , and an extrinsic one with real utterance speaking times in milliseconds. For the latter we recorded human speech data and timing information of the ASR output for 300 randomly sampled examples from SMCalFlow data. 12 When computing FLR, we also assume e ( v ) =  for all slow function nodes v , 13 and sweep over the constant  to see its effects, where  is measured either in number of source tokens or in milliseconds. We evaluated our offline parser FULLTOGRAPH and utterance completion model LMCOMPLETE on all prefixes of all utterances in validation data. The parser achieves state-of-the-art accuracy on both validation sets. Completing the sentences using our fine-tuned BART model achieves a rather high corpus BLEU score, much higher than if we do not complete them. These models provide a strong foundation for our online parsing methods. In Figure 4 we plot the PREFIXTOGRAPH parser performance when tested on different prefix lengths, 14 with models trained with different mix-14 tures of the prefix training sets. Parsing performance of course degrades for shorter prefixes, but degrades most rapidly for the offline parser (the pre-fix100% curve). Gradually mixing in shorter prefix data does not affect offline parsing results much (the scores at prefix length 100%, on the top-right), but significantly lifts the curve for earlier prefixes, making the parser better at anticipating . The trend is more obvious under the graph tuple match metric, suggesting that PREFIXTOGRAPH succeeds at predicting useful subgraphs from short prefixes. We obtain FLR vs. cost tradeoff curves by varying the threshold  in our method. Results on the two datasets are shown in Figure 5 under the intrinsic source-timing setup, and results with extrinsic source-timing are shown in Figure 6. The offline approach, FULLTOGRAPH , operates with no latency reduction and no extra calls. The ideal system would have high latency reduction with few excessive function calls, thus the upper left region is desired. We compare our proposed methods with the baseline that directly applies the offline parser on utterance prefixes, which under-performs our methods across all evaluation setups. Between the PREFIXTOGRAPH 15 and LMCOMPLETE + FULLTOGRAPH approaches, we observe that: 1) on SMCalFlow the latter performs better in most cost regions, but on TreeDST they are much closer; 2) when the function execution time  is longer, PREFIXTOGRAPH tends to show more advantages in low-cost regions, which is perhaps due to the fact that its early prediction is better when the execution time dominates the source speaking time. Results are similar with the real utterance timing information. Overall, we reduce the final latency by 30%63%. In fast execution regimes, we obtain 50%65% of the best possible reduction (achieved by the oracle), and 30%50% in slow execution regimes. Although the FLR metric does not consider model inference time, the LMCOMPLETE + FULLTOGRAPH approach does have higher inference time, since it requires two steps per prefix. PREFIXTOGRAPH Parsing Example In Figure 7, we show the model log-probabilities of individual actions. In (a), the model guesses a complete program structure, but one that finds the next event 15 We show results of the model trained with prefix30%+ data, as different training setups result in similar curves. instead of finding the supervisor's name. The uncertainty of this guess is reflected in the low probabilities of the actions, and our simple thresholding heuristic can filter out the incorrect subgraphs. But once the new word supervisor arrives in (b), the model anticipates the correct program even before seeing the final tokens, and all actions have higher scores. Appendix F traces a complete example. Action-level Probability Calibration In Figure 8 we plot the actual probability of a node's being in the true graph against the (binned) model probability of the action that predicted it. Perfectly calibrated model probabilities would fit the dotted diagonal. Ours are slightly overconfident, likely because they are conditional (on action history), whereas we are treating them as marginal. But they roughly follow the true likelihoods, which empirically justifies our use of action-level probabilities to assess subgraph probabilities. 16 Latency Reduction per Function We inspect the absolute latency reduction (allowing an earlier finish time than the user utterance) for each function type in Figure 9. The largest gains are obtained for RecipientWithNameLike and FindManager , likely because invocations of these functions tend to have less structure, often having a string literal as their only argument. An incremental algorithm for computing the function f updates f ( x ) efficiently each time x grows. In this spirit, incremental parsing updates a partial parse or parse chart each time a new word arrives (e.g. Earley, 1970; Huang and Sagae, 2010; Ambati et al., 2015; Damonte et al., 2017). An online algorithm may commit to possibly suboptimal decisions before it has seen all the input, as in simultaneous MT or online sequence-to-sequence transduction (Jaitly et al., 2016; Yu et al., 2016). By analogy, an online parser might be expected to start printing the parse early. However, when we speak of online semantic parsing in this paper, we really mean online semantic interpretation parsing into a program and executing that programand our algorithm starts executing early. It commits early to incurring execution costs, but not to any parse (we rapidly reparse each prefix from scratch) nor to any output 0 1 2 3 4 5 Time Unit FindEventWrapperWithDefaults Yield DeletePreflightEventWrapper DeleteCommitEventWrapper CreatePreflightEventWrapper CreateCommitEventWrapper RecipientWithNameLike UpdatePreflightEventWrapper UpdateCommitEventWrapper FindManager EventAttendance RecipientAvailability FindReports F un c t i o n C a ll offline latency latency reduction Figure 9: Average latency reduction in SMCalFlow from PREFIXTOGRAPH parsing, when  = 1 token and  allows 3 excessive calls. Ma et al. (2019) directly trained a model to generate from source prefixes for simultaneous MT. However, they used a prefix-to-prefix paradigm whereas we trained a prefix-to-full model, in which more aggressive anticipation is not blocked by target reordering. Also, we allow updating the target history by reparsing at each prefix. We masked the unseen source with copying to avoid excessive hallucination in program prediction. Arivazhagan et al. (2020b) adopted a similar idea but only used a crude heuristic to mask the last k target tokens. More recently, Deng et al. (2021) also explored parsing an utterance prefix into a full program (in their case an SQL query). They focus on saving user effort in formulating questions, while we focus on reducing latency. Accordingly, our task does not stop at predicting the full program; we also decide which subprograms to execute and when. We propose a new task, online semantic parsing, with an accompanying formal evaluation metric, final latency reduction. We show that it is possible to reduce latency by 30%63% using a strong graph-based semantic parsereither trained to parse prefixes directly or combined with a pre-trained language model for utterance completionfollowed by a simple heuristic for subgraph selection. Our general framework can work with different types of parsers and executable semantic representations. In future work, the subgraph selection decisions could be made by a learned model that considers the cost and benefit of each call, instead of using a fixed threshold. The parser could also condition on the execution status, instead of operating separately. Our paper describes an enabling technology that can expedite a dialogue system's response for a better user experience. It could also assist people who have trouble interacting with the system by reducing their effort in completing the query utterance. Caution must be taken when pre-executing program calls before the user intent is fully revealed, as there may be an unacceptable cost to mistakenly executing state-changing programs (for example, sending emails or scheduling meetings) without user confirmation. In this work, we only pre-execute safe function calls, which retrieve or compute information without changing the state of the environment. Another concern, if training on real user data, is leaking private information to other users. This is especially pressing when predicting with incomplete intent, as the model is encouraged to hallucinate, and may hallucinate information that it has memorized from other users' data. For PREFIXTOGRAPH , we use an explicit MASK token for unrevealed future tokens, and force the model to copy MASK to the predicted program instead of freely generating text. We could easily completely remove the model's ability to hallucinate free text. LMCOMPLETE , on the other hand, can and will leak text from the training data directly into an utterance completion, which can then be copied into a string literal in the predicted program. Thus PREFIXTOGRAPH may be closer to suitable for production use.
abstain abstain objective objective objective result abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain objective objective objective method abstain abstain objective objective result objective other other objective other other other other method other abstain other method other other method other abstain other other other other abstain other objective other abstain abstain abstain other other method abstain abstain abstain method abstain method abstain abstain abstain abstain method method abstain abstain method abstain method abstain method abstain abstain method abstain method method abstain method abstain method abstain abstain abstain method method abstain method abstain abstain method method abstain method abstain method abstain method abstain method abstain abstain method method method method method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain method abstain abstain abstain abstain method objective result abstain result abstain abstain abstain abstain method abstain method other method abstain method method abstain abstain method method method abstain abstain method method method method method method method method method method abstain abstain result abstain abstain abstain abstain abstain abstain result abstain abstain abstain objective result abstain abstain result abstain result abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other other other other abstain other method method abstain other other method method objective result abstain abstain abstain abstain abstain abstain method abstain abstain method method abstain abstain