Thinking Slow about Latency Evaluation for Simultaneous Machine Translation

Introduction

Simultaneous machine translation begins translating the source sentence before it is finished, sacrificing some translation quality in order to reduce latency: the amount of time the target language consumer spends waiting for their translation while the source language speaker is speaking. The trade-off between latency and quality is central to simultaneous MT, making the accurate measurement of latency crucial. However, the community has yet to settle on a standard latency metric, especially for the intrinsic scenario, where we are working on source sentences with no timing information, and delay must be estimated based on the rate at which the MT system consumes source tokens. The underlying assumption of these intrinsic metrics is that the only appreciable source of latency in a simultaneous translation occurs when the system opts to wait to read the next source token.

Background

We are concerned with calculating latency for a previously-written source sentence, without further source-speaker timing information, as is necessary when evaluating on standard MT training, development or test sets. In this scenario, all timing information is derived from the rate at which source tokens are consumed by the MT system.

We adopt the notation of Ma et al. (2018), which in turn adopts a formalism popularized by Grissom II et al. (2014), where the simultaneous MT system consists of an agent that begins with an empty source sentence, and must select between read actions that reveal source tokens for use in translation, and write actions that produce target tokens, both operating one token at a time and from left to right. Let $\mathbf{x}$ and $\mathbf{y}$ be source and target sequences, and let $t$, $1\leq t\leq|\mathbf{y}|$, index the target sequence. Our primary data structure for calculating latency will be $g(t)$, a function that gives the number of source tokens read by the agent before writing target token $t$. Standard (non-simultaneous) MT systems have $\forall t$: $g(t)=|\mathbf{x}|$, as they read the entire source sequence before writing any target tokens.

Before the advent of neural machine translation, work on simultaneous MT tended to report either the latency of end-to-end systems in milliseconds Bangalore et al. (2012); Rangarajan Sridhar et al. (2013), or with method-specific metrics that are only loosely correlated with latency, such as the number of target tokens per source segment for segmentation-based approaches Rangarajan Sridhar et al. (2013); Oda et al. (2014). An interesting exception is Grissom II et al. (2014), who opt instead to measure latency and translation quality with a single metric, Latency BLEU, which averages BLEU scores (with brevity penalty) calculated on the (potentially empty) partial translations available after each source token is read.

Alongside the first strategies for neural simultaneous MT, Cho and Esipova (2016) introduced the Average Proportion (AP) metric, which averages the absolute source delay incurred by each target token:

Gu et al. (2017) use AP, and also introduce the position-wise latency metric Consecutive Wait (CW), which measures the number of consecutive reads between writes:

Though CW has not officially been extended to a metric of sentence-level latency, we note that Alinejad et al. (2018) report average-CW in response to the lack of sensitivity in AP.

where $\tau$ is the earliest timestep where the MT system has consumed the entire source sequence:

and $\gamma=|\mathbf{y}|/|\mathbf{x}|$ accounts for the source and target having different sequence lengths. This metric has the nice property that when $|\mathbf{x}|=|\mathbf{y}|$, a wait-$k$ system will achieve an AL of $k$. Furthermore, when $|\mathbf{y}|>|\mathbf{x}|$, $\gamma$ forces a wait-$k$ system to catch up, by occasionally writing multiple target tokens consecutively, in order to achieve an AL of $k$.

Differentiable Average Lagging

2 The consequences of free writes

a standard wait-4 system: read 4, write 1, read 1, write 4.

a similar system that delays the final read: read 4, write 4, read 1, write 1.

The two systems differ only in when they read the final token. The corresponding $g$ and $l$ values are shown in Table 2. Note that they have very similar $g$ values: identical for $t=1$ and 5, and differing only by 1 for $t=2$, 3 and 4.

3 Writing with costs

a wait-$k$ system should incur a lag of $k$, and

lag should account for sentence lengths when $|\mathbf{y}|\neq|\mathbf{x}|$,

while also consistently accounting for the cost of writing target tokens. Along the way, we will eliminate $\tau$, creating a metric that is differentiable.

$g_{d}^{\prime}(t)$ tracks how much source time has passed immediately before writing the target token $t$, mirroring the semantics of $g(t)$. The second term of the $\max$ represents a baseline minimum time: the amount of time that passed immediately before the previous target token, plus the cost of writing that token. The first term, which represents reading $g(t)$ source tokens, will not add any more delay to $g^{\prime}$, unless it exceeds the second term; that is, some source tokens are available to be read “for free” because that much source time has already passed.

where $g^{\prime}(t)=g^{\prime}_{\frac{1}{\gamma}}(t)$. Second, our ideal latency-free translator would finish speaking after $|\mathbf{y}|d=|\mathbf{y}|\frac{|\mathbf{x}|}{|\mathbf{y}|}=|\mathbf{x}|$ source units, perfectly in sync with our source speaker.Just like on Star Trek! Finally, $d=|\mathbf{x}|/|\mathbf{y}|$ ensures that $d<1$ when $|\mathbf{y}|>|\mathbf{x}|$, which is necessary to encourage the system to catch up by writing several tokens after a single read.

For a concept so simple as delay with consistent writing costs, our $g^{\prime}$ solution might seem unnecessarily complex. Unfortunately, a dependency on previous timesteps is necessary in order to maintain a memory of previously incurred delays, but there is an equivalent non-recurrent version, which expands the $\max$ to cover all earlier timesteps.

The equivalence of these two formulations can be proved by induction. The non-recurrent formulation makes a few properties of $g^{\prime}$ clear. The lower-bound $g^{\prime}(t)\geq(t-1)d$, which we leveraged earlier when building our ideal timing model, now stands out. This formulation also shows how we incur further delay on top of this base according to whatever previous read (modeled by $g(i)$) has gone the most over budget, where the budget is represented by $(i-1)d$. Once the budget has been exceeded, the $\max$ ensures that $g^{\prime}$ irrevocably incurs this delay for all future timesteps; delays can only increase as time passes.

Discussion

2 An empirical comparison

Conclusion

We have presented a modified version of Average Lagging dubbed Differentiable Average Lagging. By beginning with clear assumptions about how long it takes to write each target token, we have created a metric that is internally consistent in its treatment of timing, and which is also differentiable.

Acknowledgments

Thanks to Naveen Arivazhagan, Wolfgang Macherey and Gaurav Kumar for feedback on earlier versions of this work.

References