Online Semantic Parsing for Latency Reduction in Task-Oriented Dialogue (2022)

Abstract: 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%–65% latency reduction depending on function execution time and allowed cost.

## introduction 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? 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) and-even harder-anticipating 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. 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 wait-k systems with fixed scheduling (ma et al., 2019), learned adaptive scheduling (arivazhagan et al., 2019), and re-translation (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 generalpurpose 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 taskoriented dialogue system (zettlemoyer and collins, 2009). each function invocation is represented by a node, whose label specifies the function, and whose outgoing foot_0 edges indicate its arguments, which may be constants or other function invocations. preliminaries formally, we represent a program as a labeled directed acyclic graph @xmath0, e), where each node @xmath1, and each directed edge u ℓ -→ @xmath2. 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 @xmath3, u 2 , . . . , u |u| ) and the context is also encoded as a sequence @xmath4, 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 @xmath5. 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 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] . foot_1 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. ## methods after each successive utterance prefix u 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. @xcite 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.2-3.3), and finally our heuristic for select (section 3.4). ## evaluation to quantify the latency improvements for online semantic parsing methods, we propose a new metric, final latency reduction. ## experimental setup data we make use of two recently released largescale conversational semantic parsing datasets, sm-calflow v2.0 (semantic machines et al., 2020) and the version of treedst (cheng et al., 2020) released by platanios et al. (2021). ## related work 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 program-and 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 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. ## conclusion 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 graphbased semantic parser-either trained to parse prefixes directly or combined with a pre-trained language model for utterance completion-followed 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.