# Enhanced nonlinear quantum metrology with weakly coupled solitons and
particle losses

Alexander Alodjants  Institute of Advanced Data Transfer Systems, ITMO
University, St. Petersburg, 197101, Russia  Dmitriy Tsarev  Institute of
Advanced Data Transfer Systems, ITMO University, St. Petersburg, 197101,
Russia  The Vinh Ngo  Institute of Advanced Data Transfer Systems, ITMO
University, St. Petersburg, 197101, Russia  Ray-Kuang Lee  Physics Division,
National Center for Theoretical Sciences, Taipei 10617, Taiwan  Institute of
Photonics Technologies, National Tsing Hua University, Hsinchu 30013, Taiwan
<EMAIL_ADDRESS>
###### Abstract

The estimation of physical parameters with Heisenberg sensitivity and beyond
is one of the crucial problems for current quantum metrology. However,
unavoidable lossy effect is commonly believed to be the main obstacle when
applying fragile quantum states. To utilize the lossy quantum metrology, we
offer an interferometric procedure for phase parameters estimation at the
Heisenberg (up to $1/N$) and super-Heisenberg (up to $1/N^{3}$) scaling levels
in the framework of the linear and nonlinear metrology approaches,
respectively. The heart of our setup is the novel soliton Josephson Junction
(SJJ) system providing the formation of the quantum probe, i.e, the entangled
Fock ($N00N$-like) state, beyond the superfluid-Mott insulator quantum phase
transition point. We illustrate that such states are close to the optimal ones
even with moderate losses. The enhancement of phase estimation accuracy
remains feasible both for the linear and nonlinear metrologies with the SJJs,
and allows further improvement for the current experiments performed with
atomic condensate solitons with a mesoscopic number of particles.

Bose-Einstein Condensate, solitons, quantum metrology, $N00N$-state

††preprint: APS/123-QED††preprint: APS/123-QED

Modern quantum technologies pose fundamentally new requirements for schemes
and procedures of measurement, as well as the subsequent estimation of some
physical parameters, in the framework of metrology and sensorics tasks [1, 2].
Traditionally, such schemes are based on the interference of quantum states of
light and/or matter waves [3]. In particular, the high accuracy of quantum
optical measurements represents an extremely important problem for the
detection of gravitational waves, in which quantum states of light interfere
in specially designed optical Michelson interferometers [4, 5, 6]. Although
the atomic interferometers have been known for about 30 years (see e.g. [7]),
current experimental facilities open new perspectives for verification of
fundamental physical laws [8, 9, 10] as well as for sensorics and metrology in
real-world applications [11, 12, 13, 14]. Typically, such facilities exploit
Mach-Zehnder (MZ) interferometers based on ultracold atomic ensembles and
Bose-Einstein condensates (BEC) [16, 15, 17, 18, 19, 11]. In particular,
atomic MZ interferometer presumes certain operations (rotations) on the Bloch
sphere performed with effectively two-mode atomic systems, see Fig. 3 in [1].
Experimentally, such a system may be created using atomic Josephson junctions
obtained by an optical dipole trap, which provides a double-well potential for
condensate atoms [20, 21, 22]. Alternatively, it is also possible to use two
hyperfine atomic states, linearly coupled by two-photon transition [23]. In
both cases, the number of condensate atoms is about few hundreds for
preserving the collective behavior of condensate atoms [24].

The quantum approach in metrology presumes the so-called quantum Cramer-Rao
(QCR) bound for the root mean square error $\delta\phi$ of estimation of
arbitrary physical parameter $\phi$, i.e.,
$\delta\phi\geq\frac{1}{\sqrt{\nu}\sqrt{F_{Q}}}\equiv\frac{\delta\phi_{min}}{\sqrt{\nu}}$,
where $\nu$ is the number of experimental runs, $F_{Q}$ is the quantum Fischer
information (QFI) [25, 26].

Without loss of generality, the measurement and estimation procedure of
$\phi$-parameter proposes some state transformation described as
$\left|\Psi_{\phi}\right\rangle\equiv\left|\Psi(\phi)\right\rangle=e^{-i\phi(\hat{b}^{\dagger}\hat{b})^{k}}\left|\Psi\right\rangle$,
where $k$ is a positive integer number, $\left|\Psi\right\rangle$ is an
initial state that we prepare for the measurement, and $\hat{b}$
($\hat{b}^{\dagger}$) is the annihilation (creation) operator that
characterizes the quantum bosonic channel accumulating phase
$\varphi\equiv\phi(\hat{b}^{\dagger}\hat{b})^{k}$.

The best precision of the measurement,

$\delta\phi_{min}=\frac{1}{N^{k}},$ (1)

can be obtained with an ideal balanced maximally path-entangled two-mode
$N00N$-state,
$\left|\Psi\right\rangle\equiv\left|N00N\right\rangle=\frac{1}{\sqrt{2}}\left(\left|N\right\rangle_{a}\left|0\right\rangle_{b}+\left|0\right\rangle_{a}\left|N\right\rangle_{b}\right)$,
where $N$ is the total average number of particles.

The Heisenberg limit (HL) for Eq. (1) is obtained in the framework of the
linear metrology (LM) approach with $k=1$. The nonlinear metrology (NLM)
corresponds to the so-called super-Heisenberg limit (SHL) that may be obtained
for Eq. (1) at $k\geq 2$, [28, 29, 30, 31, 27].

Remarkably, losses play a decisive (destructive) role in the real-world
implementation of quantum-metrological schemes based on non-classical states
[32]. The losses especially affect the schemes, where $N00N$-states are
proposed to improve the parameters estimation accuracy. As a consequence, an
ideal (balanced) $N00N$-state quickly loses the HL advantage in the phase
estimation procedure even in the presence of insignificant losses in an
interferometer with small particle number $N=20$, cf. [33].

Alternatively, entangled Fock states may be more suitable for the quantum
metrology purposes in the presence of losses [34]. However, obtaining such
entangled states with a relatively large number of particles is still an open
problem both in theory and experiment. Thus, the strategy to achieve the
ultimate precision in the phase estimation within a real-world experiment
presumes:

(i) the preparation of the $N00N$-state or some other state that allows for
the measurement level close to Eq. (1) even in the presence of particle
losses, whcih should also be suitable for both linear and nonlinear metrology
schemes, and

(ii) the choices on the appropriate environment ($\phi$) and scheme, which
provide the maximal value for power degree $k$.

The aim of this work is to show how both these two problems addressed above
may be solved simultaneously by quantum solitons with a mesoscopic number of
particles, even in the presence of losses.

We prove in Sec. A of Supplementary Materials that, for the estimation of
phase parameter $\phi$ in terms of (ii), quantum bright solitons potentially
demonstrate a higher accuracy than purely Gaussian states or plane waves in
the same Kerr-like medium, see (S.3) in Supplementary Materials.

The scheme indicating the estimation procedure for phase parameter $\phi$ by
quantum bright solitons is plotted in Fig. 1. The procedure includes three
important steps. At the first stage we aim at the preparation of entangled
Fock ($N00N$-like) state $\left|\Psi\right\rangle$ that provides maximally
accessible accuracy for subsequent $\phi$-estimation in the presence of
losses. The two entangled modes here correspond to the two arms of MZ-
interferometer. At the second stage, a phase-shift $\phi$ between the arms and
the losses are accounted. In the framework of NLM it is possible to assume
that an additional medium provides a controlled nonlinear phase difference
$\phi$ between the solitons, which is accounted at the second stage. The
losses for the setup in Fig. 1 are introduced at the second stage by two
fictitious “beam splitters” (BSs), which provide a coupling of the setup with
the environment [33, 35]. At the third final step, the measurement and
$\phi$-parameter estimation are performed by including ideal particle
detection and outcome estimation [32].

Now, let us examine how we can prepare entangled soliton state
$\left|\Psi\right\rangle$ to achieve the maximal precision in the phase
estimation, $\delta\phi_{min}$. Here, we suggest the quantum soliton Josephson
junction (SJJ) device that represents two weakly coupled bright solitons. We
assume that each of the solitons may be described in the framework of the
single mode approximation. In this limit, the Hamiltonian for the SJJ-model
reads as

$\displaystyle\hat{H}_{SJJ}$ $\displaystyle=$ $\displaystyle\kappa
N\Bigg{\\{}-\frac{\Lambda}{2}\hat{z}^{2}-\frac{1}{2N}\Bigg{[}\sum_{k=0}^{\infty}C_{1/2}^{k}(-1)^{k}(1-0.21\hat{z}^{2})$
(2) $\displaystyle\times$
$\displaystyle\left(\hat{a}^{\dagger}\hat{b}+\hat{b}^{\dagger}\hat{a}\right)\hat{z}^{2k}+H.C.\Bigg{]}\Bigg{\\}},$

where
$\hat{z}\equiv\frac{1}{N}\left(\hat{b}^{\dagger}\hat{b}-\hat{a}^{\dagger}\hat{a}\right)$;
$\hat{a}$ and $\hat{b}$ ($\hat{a}^{\dagger}$ and $\hat{b}^{\dagger}$) are the
bosonic annihilation (creation) operators for two solitons modes, see [36] for
details. In Eq. (2), $\Lambda\equiv u^{2}N^{2}/16\kappa$ is a vital parameter
of the SJJ system that includes the nonlinear strength, $u$, coresponding to
the two-body atom scattering in the Born approximation, and $\kappa$
characterizing tunneling of particles between the solitons. The analysis of
the SJJ system without losses in the general case is performed in Ref. [36],
where Hamiltonian (2) clearly demonstrates the quantum “superfluid-Mott
insulator”-like phase transition occurring at some critical value
$\Lambda_{c}$.

Figure 1: Sketch on three step phase-parameter $\phi$ estimation procedure
with quantum soliton Josephson junction (SJJ) devise as a input state
preparation. Possible interaction with environment is provided by two
fictitious “beam splitters” $BS_{a}$ and $BS_{b}$ in quantum channels “a” and
“b”, respectively. See text for some details.

For the lossy quantum metrology scheme, the effect of the coupling with the
environment causes some number of particles to remove from each quantum
channel introducing extra (vacuum) noises. We model these losses by means of
the fictitious BS approach that presumes transmissivities of “a” and “b”
channels characterized by parameters $\eta_{a}$ and $\eta_{b}$
($\eta_{a,b}\leq 1$), respectively. Further, we suppose that channels “a” and
“b” are physically equivalent and $\eta_{a}\simeq\eta_{b}=\eta$. The resulting
quantum state in the lossy channel is a mixed state described by the density
matrix, cf. [33, 39],

$\rho=\sum_{l_{b}=0}^{N}\sum_{l_{a}=0}^{N-l_{b}}p_{l_{a},l_{b}}\left|\xi\right\rangle\left\langle\xi\right|,$
(3)

where
$\left|\xi\right\rangle=\frac{1}{\sqrt{p_{l_{a},l_{b}}}}\sum_{n=l_{b}}^{N-l_{a}}C_{l_{a},l_{b}}^{n}e^{in^{k}\phi}\left|N-n-
l_{a}\right\rangle_{a}\left|n-l_{b}\right\rangle_{b}$ is one of the possible
pure states of the system after $l_{a}$ and $l_{b}$ particle losses; and
$p_{l_{a},l_{b}}=\sum_{n=l_{b}}^{N-l_{a}}(C_{l_{a},l_{b}}^{n})^{2}\equiv\sum_{n=l_{b}}^{N-l_{a}}A_{n}^{2}B_{l_{a},l_{b}}^{n}$
is a normalization factor, see Supplementary Materials. In Eq. (3), we have
also traced out the modes $\left|l_{a}\right\rangle\left|l_{b}\right\rangle$.

In the presence of losses, the particle number distributions are broadened,
see (S.10-S.16) in Supplementary Materials. Obvious arguments tell us that the
broadening of the particle number distribution negatively affects the accuracy
of the $\phi$ phase parameter measurement. Actually, the uncertainty in the
phase parameter estimation occurs due to the quantum-mechanical fluctuations
in the particle number difference
$\delta\phi\simeq\left\langle(\Delta(N_{a}-N_{b}))^{2}\right\rangle^{-1/2}$.
In this case, we obtain $\delta\phi=[N(1+\eta(N\eta-1))]^{-1/2}$. Without any
losses (for $\eta=1$), $\delta\phi$ approaches $1/N$ corresponding to the HL
accuracy.

To be more specific, we examine the corresponding QFI, $F_{Q}$, in the
presence of losses for the setup in Fig. 1. In particular, accounting in Eq.
(3) the density matrix representation in diagonal form
$\rho=\sum_{i=1}^{s}\lambda_{i}\left|\psi_{i}\right\rangle\left\langle\psi_{i}\right|$,
where $\lambda_{i}$ and $\left|\psi_{i}\right\rangle$ are eigenvalues and
eigenstates of $\rho$, respectively ($s$ is the rank), we can establish QFI
as, cf. [37, 38]

$\displaystyle F_{Q}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{s}\Bigg{(}\frac{1}{\lambda_{i}}\left(\frac{\partial\lambda_{i}}{\partial\phi}\right)^{2}$
(4) $\displaystyle+$ $\displaystyle
4\lambda_{i}\left\langle\psi_{i}^{\prime}\Big{|}\psi_{i}^{\prime}\right\rangle-\sum_{j=1}^{s}\frac{8\lambda_{i}\lambda_{j}}{\lambda_{i}+\lambda_{j}}\left|\left\langle\psi_{i}\Big{|}\psi_{j}^{\prime}\right\rangle\right|^{2}\Bigg{)},$

where
$\left|\psi_{i}^{\prime}\right\rangle\equiv\frac{\partial}{\partial\phi}\left|\psi_{i}\right\rangle$.

Numerical calculation of QFI defined in Eq. (4) and performed in the case of
NLM for large $N$ represents a non-trivial computational task. In this work,
we restrict ourselves by studying only the upper bound of the QFI, denoted as
$\tilde{F}_{Q}$ ($F_{Q}\leq\tilde{F}_{Q}$), which reads

$\tilde{F}_{Q}=4\left[\sum_{n=0}^{N}n^{2k}A_{n}^{2}-\sum_{l_{b}=0}^{N}\sum_{l_{a}=0}^{N-l_{b}}\frac{\left(\sum_{n=l_{b}}^{N-l_{a}}n^{k}C_{l_{a},l_{b}}^{n}\,{}^{2}\right)^{2}}{\sum_{n=l_{b}}^{N-l_{a}}C_{l_{a},l_{b}}^{n}\,{}^{2}}\right],$
(5)

where $A_{n}$ is $C_{l_{a},l_{b}}^{n}$ coefficient taken at $l_{a},l_{b}=0$
[33, 39].

In Fig. 2 we establish the minimal error (maximal accuracy) for the phase
estimation (represented in the logarithmic scale) as a function of the
normalized particle number $N$. The upper (solid) curves correspond to the LM
limit obtained at $k=1$ for Eq. (2). The nonlinear phase estimation with
solitons is established by the lower (dashed) curves plotted at $k=3$. The
intermediate (black dashed) curve establishes SHL $\propto 1/N^{2}$ obtained
with $k=2$. These limits are discussed in Ref. [27] and correspond to the
phase estimation by means of usual Kerr-like medium with “plane waves”. The
SJJ environment generates a two-mode Fock state with a particular
superposition given by the coefficients $A_{n}$ that are dependent on
$\Lambda$ parameter and defined in the Supplementary Material. For the optimal
state (OS, the brown curve in Fig. 2), we optimize the numerical QFI $F_{Q}$
(5) over all such two-mode Fock state superpositions.

Figure 2 exhibits two important features, which are relevant to the quantum
metrology performed with bright solitons. First, the absolute value of phase
estimation accuracy is minimal with the coupled solitons even in the presence
of losses and for coherent probes (the blue dashed curve in Fig. 2) in
comparison to other metrological approaches beyond the HL available now (see
the lower shadow region in Fig. 2 and cf. [27]).

Second, the phase estimation with the initially prepared SJJ-system
establishes the best accuracy for both linear and nonlinear metrological
purposes in comparison to relevant $N00N$-states (see the red curves in Fig.
2). For that, in the vicinity of the phase transition point we require
$N=N_{0}$ particles (see the yellow curve in Fig. 2). Moreover, the minimal
value of the estimated phase parameter is close to the results obtained with
the so-called optimal states (OS), which may be found for the lossy metrology
by the QFI numerical optimization procedure, cf. [33]. A particular value of
$N_{0}$ is determined from the experimental facilities, which are used for the
SJJ-device design. The particle number involved in Fig. 2 is assumed to be
$N_{0}=100$.

Figure 2:  The logarithmic plot of the best accuracy $\delta\phi_{min}$ of
phase estimation based on the SJJ as a function of the normalized number of
particles $N/N_{0}$. The parameters used are $N_{0}=100$,
$\eta_{a}=\eta_{b}=0.95$. The upper shadow region depicts the area between the
SIL and HL for $k=1$. The lower shadow region corresponds to the area between
the NIL and SHL at $k=3$, see Eq. (1). See more detail in text. Figure 3: The
best accuracy $\delta\phi_{min}$ of the phase estimation based on the SJJ vs.
transmissivity $\eta_{a}=\eta_{b}\equiv\eta$ of the fictitious BSs for the
linear metrology ($k=1$) and nonlinear one (the inset, $k=3$) with $N=100$
particles. See more detail in text.

The upper black line in Fig. 2 corresponds to the limiting case, i.e. the
standard interferometric limit (SIL), and characterizes the phase estimation
procedure with initially prepared coherent atomic wave packets. The SIL reads
as $\delta\phi_{SIL}=1/\sqrt{\eta N}$, it can be obtained from Eq. (5) at
$k=1$ and represents the generalization of the SQL in the presence of particle
losses, see Eq. (S.25) in Supplementary Materials, cf. [39]. Similarly, one
can define the nonlinear interferometric limit (NIL), $\delta\phi_{NIL}$,
which occurs in the framework of the nonlinear metrology approach. Setting
$k=3$ in Eq. (5) for the coherent atomic wave packets we can obtain
$\delta\phi_{NIL}=1/\sqrt{\eta N^{5}}$.

In Fig. 3, we represent the accuracy $\delta\phi_{min}={\tilde{F}_{Q}}^{-1/2}$
versus the channel transmissivity, $\eta$-parameter, for the linear ($k=1$)
and nonlinear ($k=3$) metrology phase estimation procedures, respectively. The
NLM peculiarities are given in the inset of Fig. 3.

At $\eta=1$ all the curves start at the points representing the accuracy of
the lossless metrology with the SJJs at correspondent $\Lambda$. For the SJJ-
device in the Mott-insulator regime, at $\Lambda\geq 2.1$, the accuracies of
the linear and nonlinear metrology match the HL ($\delta\phi_{min}=1/N$) and
SHL ($\delta\phi_{min}=1/N^{3}$), respectively. In the presence of losses,
$\delta\phi_{min}$ grows depending on the value of $\Lambda$-parameter, which
is relevant to the performance of the SJJs as a device for probe state
preparation in Fig. 1. The curves with various $\Lambda$ in Fig. 3 correspond
to the crossover region from the superfluid ($\Lambda=2$) to Mott-insulator
($\Lambda=2.1$) regimes that take place in the SJJ system.

Remarkably, in the LM case the difference between $F_{Q}$ and $\tilde{F}_{Q}$
for the SJJ model is more than satisfactory excluding the phase transition
point. Only less than 0.5% discrepancy can be seen before the phase transition
and less than 4% after the phase transition. At the phase transition point,
the difference between $F_{Q}$ and $\tilde{F}_{Q}$ reaches 60 %. In the
presence of losses it happens in the vicinity of the inflection point with
$\eta\lesssim 0.9$, see Fig. 3. At this point, $F_{Q}$ behaves more sharply
than $\tilde{F}_{Q}$. Notice, the plots in Fig. 2 are represented for
$\eta=0.95$, which corresponds to vanishing discrepancy between $F_{Q}$ and
$\tilde{F}_{Q}$.

From Fig. 3 (the red and blue curves), it is clearly seen that at moderate
values of $\eta$ the phase estimation accuracy approaches $\delta\phi_{SIL}$
for the SJJ system close to the superfluid regime, $\Lambda<\Lambda_{c}$. The
behaviour of $\delta\phi_{min}$ beyond critical point $\Lambda\geq\Lambda_{c}$
is determined by the properties of entangled Fock states at the input of the
setup in Fig. 1 in the presence of losses. Even at $\Lambda=2.1$ (the magenta
curves in Fig. 3), accuracy $\delta\phi_{min}$ approaches the one obtained for
the ideal $N00N$-state,
$\delta\phi_{min}=\delta\phi_{\eta}=1/N^{k}\eta^{N/2}$, see Eq. (S.21) in
Supplementary Materials. Strictly speaking, use of such states in metrology is
justified (for a given particle number $N$) if the transmissivity of quantum
channels satisfies condition $\eta\geq\eta_{c}\equiv e^{-2k/N}$. Notably, in
the NLM case with solitons ($k=3$), reasonable value $\eta_{c}=0.9$ of
$\eta$-parameter leads to the mesoscopic number of particles $N\simeq 57$
required to achieve a high precision phase estimation. In the LM domain [39]
the same particle number requires essentially higher $\eta_{c}\simeq 0.97$
transmissivity of the quantum channels.

However, in the presence of significant losses ($\eta<<\eta_{c}$) the
entangled Fock or $N00N$-states are not applicable, and the spin-squeezed
states with $\Lambda<\Lambda_{c}$ demonstrate the accuracy better than the
SIL. The best accuracy for $\eta<0.9$ is provided by the borderline state with
$\Lambda=\Lambda_{c}$ due to the existence of planar spin-squeezing in the
entangled Fock modes (cf. Ref. [36]), see the yellow curve in Fig. 3.

In Fig. 3, we also compare the results with the OS (the brown curves). As
seen, the results with the OS and the states provided by the SJJ are close to
each other in the regions where $0<\eta\leq 0.3$ and $0.9<\eta\leq 1$, which
correspond to the high and low losses limits, respectively. The difference
between the optimal and SJJ states is notable at intermediate values of $\eta$
close to inflection points, see Fig. 3. Such a behaviour takes place due to
the phase-transition effect that occurs abruptly and evokes a rapid quantum
state transformation.

Let us estimate $\eta_{c}$ parameter for the current experiments with atomic
solitons observed in $\mathrm{{}^{7}Li}$ condensate possessing $N=5000$ number
of atoms, cf. [42, 43, 40, 41]. To be more specific, we discuss here one-body
losses, which correspond to exponential decay law $e^{-\gamma t}$ of the
condensate particle number within the rate window $\gamma\simeq 0.1\div 0.01$
$s^{-1}$. Obviously, the critical value of parameter $\eta_{c}$ corresponds to
critical time scale $t_{c}=2k/\gamma N$ that limits the observation of the
phase estimation with a soliton $N00N$-like state. The maximal value of
$t_{c}$ may be obtained for the NLM setup, $t_{c}=12\div 120$ $ms$ ($k=3$); it
is comparable with the typical atomic soliton observation and soliton
collision time scales in the experiments [42, 43, 40, 41]. However, we expect
sufficient improvement in the measurement and phase estimation procedure at
the time scales obeying condition $t<<t_{c}$. The enhancement of $t_{c}$
represents a non-trivial experimental task; it requires essential reduction of
particle number $N$, cf. [36]. At the same time, we must increase parameter
$u$ to keep the value of $\Lambda$ at a certain level providing the bright
soliton formation and interaction beyond the phase transition point, see Fig.
3. The latter may be achieved with the improvement of the Feshbach resonance
technique [44]. We hope that the observation of the SJJ system with mesoscopic
number of atoms ($N\simeq 100\div 1000$) will represent the core for new
generation experiments with atomic solitons.

In conclusion, by utilizing the soliton Josephson Junction system as a quantum
probe, we propose the interferometric procedure for the appropriate phase
parameters estimation at the Heisenberg (up to $1/N$) and practically unique
super-Heisenberg (up to $1/N^{3}$) scaling levels in the framework of linear
and nonlinear metrology approaches, respectively. Counter-intuitively,
operating near the quantum phase transition point helps to sustain the
accuracy of the phase estimation even in the presence of particle losses. With
the QFI, we reveal main features of such a quantum metrology. Our results
contribute to further improvement of the current experiments performed with
atomic condensate solitons containing a mesoscopic number of particles.

## Acknowledgement

This work was financially supported by the Grant of RFBR, No 19-52-52012. RKL
was supported by the Ministry of Science and Technology of Taiwan (No
108-2923-M-007-001-MY3. and No 109-2112-M-007-019-MY3).

## References

  * [1] L. Pezzè, A. Smerzi, M. K. Oberthaler, R. Schmied, and P. Treutlein, “Quantum metrology with nonclassical states of atomic ensembles,” Rev. Mod. Phys. 90, 035005 (2018).
  * [2] C. L. Degen, F. Reinhard, and P. Cappellaro, “Quantum sensing”, Rev. Mod. Phys. 89, 035002 (2017).
  * [3] J. P. Dowling and K. P. Seshadreesan, “Quantum Optical Technologies for Metrology, Sensing, and Imaging,” J. Light. Tech. 33, 2359-2370 (2015).
  * [4] J. Aasi, J. Abadie, B. Abbott et al., “Enhanced sensitivity of the LIGO gravitational wave detector by using squeezed states of light,” Nature Photon 7, 613 (2013).
  * [5] Y. Zhao, N. Aritomi, E. Capocasa et al., “Frequency-dependent squeezed vacuum source for broadband quantum noise reduction in advanced gravitational-wave detectors,” Phys. Rev. Lett. 124, 171101 (2020).
  * [6] L. McCuller, C. Whittle, D. Ganapathy et al., “Frequency-Dependent Squeezing for Advanced LIGO,” Phys. Rev. Lett. 124, 171102 (2020).
  * [7] M. Kasevich and S. Chu, “Atomic interferometry using stimulated Raman transitions.” Phys. Rev. Lett. 67, 181–184 (1991).
  * [8] D. N. Aguilera, H. Ahlers, B. Battelier, A. Bawamia, et al, “STE-QUEST—test of the universality of free fall using cold atom interferometry,” Class. Quantum Grav. 31, 115010 (2014).
  * [9] H. Muntinga, H. Ahlers, M. Krutzik, A. Wenzlawski, et al, “Interferometry with Bose-Einstein Condensates in Microgravity”, Phys. Rev. Letts. 110, 093602 (2013).
  * [10] M.D. Lachmann, H. Ahlers, D. Becker, et al, “Ultracold atom interferometry in space”, Nature Communications, 12, 1317 (2021).
  * [11] K. Bongs, M. Holynski, J. Vovrosh, et al. “Taking atom interferometric quantum sensors from the laboratory to real-world applications.” Nature Rev. Phys. 1, 731–739 (2019).
  * [12] R. Geiger, V. Ménoret, G. Stern, et al. “Detecting inertial effects with airborne matter-wave interferometry.” Nature Commun. 2, 474 (2011).
  * [13] A. Hinton, M. Perea-Ortiz, J. Winch, et al. “A portable magneto-optical trap with prospects for atom interferometry in civil engineering.” Phil. Trans. R. Soc. A, 375 20160238 (2017).
  * [14] Y. Bidel, N. Zahzam, C. Blanchard, et al. “Absolute marine gravimetry with matter-wave interferometry.” Nature Commun. 9, 627 (2018).
  * [15] C. Gross, T. Zibold, E. Nicklas, J. Esteve, and M. K. Oberthaler, “Nonlinear atom interferometer surpasses classical precision limit,” Nature, 464, 1165 (2010).
  * [16] D. Becker, M.D. Lachmann, S.T. Seidel, et al. “Space-borne Bose–Einstein condensation for precision interferometry.” Nature 562, 391 (2018).
  * [17] H. Lee, P. Kok, and J. P. Dowling, “A quantum Rosetta stone for interferometry,” J. Mod. Opt. 49, 2325 (2002).
  * [18] M. Hauth, C. Freier, V. Schkolnik, A. Peters, H. Wziontek, and M. Schilling, “Atom interferometry for absolute measurements of local gravity”, Proceedings of the International School of Physics ”Enrico Fermi” 188, 557 (2014).
  * [19] D. V. Tsarev, S. M. Arakelyan, Y.-L. Chuang, R.-K. Lee, and A. P. Alodjants, “Quantum metrology beyond Heisenberg limit with entangled matter wave solitons,” Opt. Exp. 26, 19583 (2018).
  * [20] R. Gati, R., M. Albiez, J. Fölling et al., “Realization of a single Josephson junction for Bose–Einstein condensates,” Appl. Phys. B 82, 207 (2006).
  * [21] M. Albiez, R. Gati, J. Fölling et al., “Direct Observation of Tunneling and Nonlinear Self-Trapping in a Single Bosonic Josephson Junction,” Phys. Rev. Lett. 95, 010402 (2005).
  * [22] G. Mazzarella, L. Salasnich, A. Parola, and F. Toigo, “Coherence and entanglement in the ground state of a bosonic Josephson junction: From macroscopic Schrödinger cat states to separable Fock states,” Phys. Rev. A 83, 053607 (2011).
  * [23] W. Muessel, H. Strobel, D. Linnemann, et al, “Twist-and-turn spin squeezing in Bose-Einstein condensates”. Phys. Rev. A, 92 023603 (2015).
  * [24] J. R. Anglin and A. Vardi, “Dynamics of a two-mode Bose-Einstein condensate beyond mean-field theory,” Phys. Rev. A 64, 013605 (2001).
  * [25] G. Tóth and I. Apellaniz, “Quantum metrology from a quantum information science perspective,” J. Phys. A: Math. Theor. 47, 424006 (2014).
  * [26] R. Demkowicz-Dobrzański, M. Jarzyna, and J. Kołodyński, “Quantum limits in optical interferometry,” Prog. in Opt. 60, 345 (2015).
  * [27] D. Maldonado-Mundo and A. Luis, “Metrological resolution and minimum uncertainty states in linear and nonlinear signal detection schemes,” Phys. Rev. A 80, 063811 (2009).
  * [28] M. Beau and A. del Campo, “Nonlinear Quantum Metrology of Many-Body Open Systems,” Phys. Rev. Lett. 119, 010403 (2017).
  * [29] M. Napolitano and M. W. Mitchell, “Nonlinear metrology with a quantum interface,” New J. Phys. 12, 09301 (2010).
  * [30] J. Cheng, “Quantum metrology for simultaneously estimating the linear and nonlinear phase shifts,” Phys. Rev. A 90, 063838 (2014).
  * [31] A. Luis, “Quantum limits, nonseparable transformations, and nonlinear optics,” Phys. Rev. A 76, 035801 (2007).
  * [32] N. Thomas-Peter, B. J. Smith, A. Datta, L. Zhang, U. Dorner, and I. A. Walmsley, “Real-World Quantum Sensors: Evaluating Resources for Precision Measurement,” Phys. Rev. Lett. 107, 113603 (2011).
  * [33] U. Dorner, R. Demkowicz-Dobrzansk, B. J. Smith, J. S. Lundeen, W. Wasilewski, K. Banaszek, and I. A. Walmsley, “Optimal quantum phase estimation,” Phys. Rev. Lett. 102, 040403 (2009).
  * [34] S. D. Huver, C. F. Wildfeuer, and J. P. Dowling, “Entangled Fock states for robust quantum optical metrology, imaging, and sensing,” Phys. Rev. A 78, 063828 (2008).
  * [35] M. Bohmann, J. Sperling, and W. Vogel, “Entanglement and phase properties of noisy NOON states,” Phys. Rev. A 91 042332 (2015).
  * [36] D. V. Tsarev, A. P. Alodjants, T. V. Ngo, and R.-K. Lee, “Mesoscopic quantum superposition states of weakly-coupled matter-wave solitons,” New J. Phys. 22, 113016 (2020).
  * [37] J. Liu, X.-X. Jing, W. Zhong, and X.-G. Wang, “Quantum Fisher information for density matrices with arbitrary ranks,” Commun. Theo. Phys. 61, 45 (2014).
  * [38] S. L. Braunstein, and C.M. Caves, “Statistical distance and the geometry of quantum states,” Phys. Rev. Lett. 72, 3439 (1994).
  * [39] R. Demkowicz-Dobrzanski, U. Dorner, B. J. Smith, J. S. Lundeen, W. Wasilewski, K. Banaszek, and I. A. Walmsley, “Quantum phase estimation with lossy interferometers,” Phys. Rev. A 80, 013825 (2009).
  * [40] L. Khaykovich, F. Schreck, G. Ferrari, T. Bourdel, J. Cubizolles, L. D. Carr, Y. Castin, and C. Salomon, “Formation of a Matter-Wave Bright Soliton,” Science 296, 1290 (2002).
  * [41] J. H. Nguyen, P. Dyke, D. Luo, B. A. Malomed, and R. G. Hulet, “Collisions of matter-wave solitons,” Nature Phys. 10, 918 (2014).
  * [42] P. G. Kevrekidis, D. J. Frantzeskakis, and R. Carretero-González, Emergent Nonlinear Phenomena in Bose–Einstein Condensates, (Springer-Verlag, 2008).
  * [43] K. E. Strecker, G. B. Partridge, A. G. Truscott, and R. G. Hulet, “Formation and propagation of matter-wave soliton trains,” Nature 417, 150 (2002).
  * [44] C. Chin, R. Grimm, P. Julienne, and E. Tiesinga, “Feshbach resonances in ultracold gases,” Rev. Mod. Phys. 82, 1225 (2010).

## Supplementary materials: Enhanced nonlinear quantum metrology with weakly
coupled solitons and particle losses

###  .1 Quantum bright solitons as a tool for nonlinear metrology applications
in the single mode approximation

Let us prove that the quantum bright solitons provide the best accuracy in
terms of (ii). We assume that the medium ($\phi$) supports the formation of
the bright matter-wave soliton described by wave function

$\psi(x,t)=\frac{N\sqrt{u}}{2}\operatorname{\textrm{sech}}\left[\frac{Nux}{2}\right]e^{i\frac{N^{2}u^{2}}{8}t},$
$None$

where $u$ characterizes the Kerr-like nonlinearity of the medium. Now, we have
$\psi(x,t)$ obeying the normalization condition, $\int|\psi|^{2}dx=N$, where
$N=\langle\hat{N}\rangle$ is the average particle number. If the particle
number is not too large, we are able to examine the single (quantum) mode
approximation typically used for Gaussian wave packets [S1, S2, 24].

Consider a classical Hamilton function

$H=\int dx\psi^{*}(x,t)\left(-\frac{1}{2}\frac{\partial^{2}}{\partial
x^{2}}-\frac{u}{2}|\psi(x,t)|^{2}\right)\psi(x,t),$ $None$

where $\psi(x,t)$ is the wave function ansatz of the bright soliton with the
dimensionless variables $x$ and $t$. Substituting $\psi(x,t)$ into $H$, one
can obtain $H=-\frac{u^{2}}{24}N^{3}$.

The quantum version of the Hamilton function is the Hamiltonian operator that
reads as

$\hat{H}_{\phi}=\phi\hat{N}^{3}\equiv\phi(\hat{b}^{{\dagger}}\hat{b})^{3},$
$None$

where $\phi~{}\equiv-\frac{u^{2}}{24}$ is the phase parameter suitable for the
estimation procedure. Operators $\hat{b}$ and $\hat{b}^{{\dagger}}$ are the
annihilation and creation operators characterizing soliton quantum properties
in the single mode approximation, see Fig. 1.

Thus, from Eq. (S.3) it is clear that instead of $k=2$, which is valid for
Gaussian states, the implementation of the quantum solitons in the setup of
Fig. 1 provides the maximally accessible Kerr-like phase shift in the medium
possessing degree $k=3$ in $\hat{H}$ in respect to the particle number
$\hat{N}=\hat{b}^{{\dagger}}\hat{b}$.

###  .2 Quantum SJJ-model as a tool for state preparation

In this work we consider the soliton Josephson Junction (SJJ) model introduced
in Ref. [36]. A fully quantum description of the SJJ is given by the
Hamiltonian operator in Eq. (2). We establish initial state $|\Psi\rangle$ of
the SJJ in two-mode Fock basis $|N-n\rangle_{a}|n\rangle_{b}$ as

$|\Psi\rangle=\sum_{n=0}^{N}A_{n}|N-n\rangle_{a}|n\rangle_{b},$ $None$

where time-dependent coefficients $A_{n}$ fulfill stationary Schrödinger
equation

$i\frac{dA_{n}(\tau)}{d\tau}=\langle N-n,n|\hat{H}|\Psi(\tau)\rangle$ $None$

and obey normalization condition $\sum_{n=0}^{N}|A_{n}|^{2}=1$; throughout
this work we use effective dimensionless time $\tau=\kappa Nt$.

Substituting Eq. (2) into Eq. (S.4) for unknown coefficients $A_{n}(\tau)$ we
obtain

$i\dot{A}_{n}=\alpha_{n}A_{n}+\beta_{n}A_{n+1}+\beta_{n-1}A_{n-1},$ $None$

where we introduce the following notations:

$\alpha_{n}=-\frac{\Lambda}{2}\left(\frac{2n}{N}-1\right)^{2},$
$\beta_{n}=-\frac{1}{N^{2}}\Bigg{(}\left[1-0.21\left(\frac{2n}{N}-1\right)^{2}\right](n+1)\sqrt{(N-n)(N-n-1)}+\left[1-0.21\left(\frac{2(n+1)}{N}-1\right)^{2}\right](N-n)\sqrt{n(n+1)}\Bigg{)}.$
$None$

In this work, by following Ref. [36], we find $A_{n}$ numerically, by
considering stationary solution of Eq. (S.6) with Eq. (S.7), which is
$A_{n}(\tau)=A_{n}e^{-iE_{n}\tau}$, where $E_{n}$ specifies the eigenenergy
spectrum for Hamiltonian (2).

Practical implementation of the proposed SJJ-model is evident from Fig. 1. Two
tunnel-coupled bright solitons with mesoscopic number of particles ($N=5000$
and less) can be achieved within the atomic optics domain [40-43]. In this
case we can speak about matter-wave solitons of atomic BEC possessing negative
scattering length.

On the other hand, tunnel-coupled bright solitons may be obtained in photonics
by means of optical pulse propagation in narrow band-gap semiconductor
materials, see e.g. [S3]. The recent progress achieved with exciton polariton
solitons in planar AlGaAs waveguides with quantum wells allows to speak about
the creation of an on-chip SJJ device based on the photonics platform, cf.
[S4].

In the current paper, we study the atomic BEC soliton platform. In Eqs. (2),
(S.4)-(S.7) we use dimension-less parameter $u=2\pi|a_{sc}|/a_{\perp}$ that
characterizes Kerr-like (focusing) nonlinearity, $a_{sc}<0$ is the s-wave
scattering length for attractive particles, $a_{\perp}$ is the characteristic
trap scale, and $m$ is the particle mass, cf. [36]. Notably, critical particle
number $N_{c}$, at which the condensate collapses, for $\mathrm{{}^{7}Li}$ BEC
solitons is $N_{c}=0.67a_{\perp}/|a_{sc}|$ implying $5.2\times 10^{3}$
particles in the soliton, [42]. Thereby, $N_{c}$ represents the upper physical
bound for the particle number that limits the quantum metrology scheme in Fig.
1 with atomic solitons possessing negative scattering length.

###  .3 Soliton-based Interferometer with losses

Consider the scheme of quantum metrology plotted in Fig. 1 in the presence of
particle losses. For our purposes we take state (S.4) as initial and then take
into account the losses in two arms of the interferometer via the fictitious
BS approach. This approach represents a powerful tool for modelling the
coupling of quantum macroscopic superposition states with the environment.
After two BSs the “input” two-mode Fock state in (S.4) transforms into (cf.
[39])

$\left|N-n\right\rangle_{a}\left|n\right\rangle_{b}\rightarrow\sum_{l_{b}=0}^{N}\sum_{l_{a}=0}^{N-l_{b}}\sqrt{B_{l_{a},l_{b}}^{n}}\left|N-n-
l_{a}\right\rangle_{a}\left|n-l_{b}\right\rangle_{b}\left|l_{a}\right\rangle\left|l_{b}\right\rangle,$
$None$

where $l_{a}$ and $l_{b}$ are the numbers of particles lost from “a” and “b”
channels, respectively. We have no interest in the lost particles here, so
further we trace out states $\left|l_{a}\right\rangle\left|l_{b}\right\rangle$
for simplicity. In (S.8) we also introduce coefficient

$B_{l_{a},l_{b}}^{n}=\left(\begin{array}[]{c}N-n\\\
l_{a}\end{array}\right)\left(\begin{array}[]{c}n\\\
l_{b}\end{array}\right)\eta_{a}^{N-n}(\eta_{a}^{-1}-1)^{l_{a}}\eta_{b}^{n}(\eta_{b}^{-1}-1)^{l_{b}},$
$None$

where $\eta_{a}$ and $\eta_{b}$ ($\eta_{a,b}\leq 1$) are the transmissivities
of BSs in channels “a” and “b”, respectively. We examine the physically
identical arms “a” and “b” of the interferometer setting
$\eta\equiv\eta_{a}\simeq\eta_{b}$.

To take into account the phase-shift $\phi$ in Fig. 1 we apply transformation
$\hat{U}_{\phi}$ to state (S.4), which leads to replacement
$\left|N-n\right\rangle_{a}\left|n\right\rangle_{b}\rightarrow
e^{in^{k}\phi}\left|N-n\right\rangle_{a}\left|n\right\rangle_{b}$. Then, we
can represent density matrix $\rho$ for the final state after particle losses
as it is given in Eq. (3), cf. Fig. 1.

At first, let us examine the influence of particle losses occurring in the
interferometer by considering the ideal $N00N$-state

$\left|N00N\right\rangle=\left(\left|N,0\right\rangle+\left|0,N\right\rangle\right)/\sqrt{2},$
$None$

at the input of the interferometer in Fig. 1. It occurs in the SJJ system
without losses far beyond critical point $\Lambda_{c}$ [36]. In this limit, we
suppose formally $k=0$ in Eq. (3); the coefficients approach to

$A_{n}=\begin{cases}\frac{1}{\sqrt{2}}\textrm{, if }n=0,N;\\\ 0\textrm{, if
}0<n<N.\end{cases}$ $None$

Substituting Eq. (S.11) into Eq. (3), one can obtain the density matrix for
the $N00N$-state after losses as

$\rho=\eta^{N}\left|N00N\right\rangle\left\langle
N00N\right|+\frac{1}{2}\sum_{l_{a}=1}^{N}B_{l_{a},0}^{0}\left|N-l_{a},0\right\rangle\left\langle
N-l_{a},0\right|+\frac{1}{2}\sum_{l_{b}=1}^{N}B_{0,l_{b}}^{N}\left|0,N-l_{b}\right\rangle\left\langle
0,N-l_{b}\right|.$ $None$

Then, taking into account Eq. (S.9) one can write

$\rho=\eta^{N}\left|N00N\right\rangle\left\langle
N00N\right|+\frac{1}{2}\sum_{n_{a}=0}^{N-1}p_{n_{a}}\left|n_{a},0\right\rangle\left\langle
n_{a},0\right|+\frac{1}{2}\sum_{n_{b}=0}^{N-1}p_{n_{b}}\left|0,n_{b}\right\rangle\left\langle
0,n_{b}\right|,$ $None$

where $n_{a}=N-l_{a}$ and $n_{b}=N-l_{b}$ are the numbers of particles
remained in the arms of the interferometer and

$p_{n}=\left(\begin{array}[]{c}N\\\ n\end{array}\right)\eta^{n}(1-\eta)^{N-n}$
$None$

is a binomial distribution function of the density matrix diagonal elements.

As seen from (S.13), the particle losses transform the $N00N$-state into a
two-mode Fock states mixture with binomial distribution (S.14). Notice, in
(S.13) only the term with $n=N$ (the case when no particles are lost) is
maximally path-entangled. For $\eta\rightarrow 1$ and $N>>1$ and finite
$N(1-\eta)$, binomial distribution (S.14) can be approximated by the
Poissonian one

$p_{n}^{Poisson}=\frac{\left(N(1-\eta)\right)^{N-n}}{(N-n)!}e^{-N(1-\eta)}.$
$None$

Finally, at $N(1-\eta)>>1$ one can use the approximation of (S.15) by the
Gaussian distribution

$p_{n}^{Gauss}=\frac{1}{\sqrt{2\pi
N(1-\eta)}}e^{-\frac{(n-N\eta)^{2}}{2N(1-\eta)}}.$ $None$

The distribution in Eq. (S.16) possesses width $\sigma=2\sqrt{N(1-\eta)}$ with
mean particle number $\bar{n}=N\eta$. For example, if $\eta=0.8$, then
$\bar{n}=80$ and $\sigma\approx 9$.

###  .4 Phase-estimation bounds with quantum solitons

In the presence of phase-shift $\phi$ in the scheme shown in Fig. 1, the QFI
for pure states
$\rho=\left|\Psi(\phi)\right\rangle\left\langle\Psi(\phi)\right|$ is defined
as

$F_{Q}=4\left[\left\langle\Psi^{\prime}(\phi)\Big{|}\Psi^{\prime}(\phi)\right\rangle-\left|\left\langle\Psi^{\prime}(\phi)\Big{|}\Psi(\phi)\right\rangle\right|^{2}\right],$
$None$

where
$\left|\Psi^{\prime}(\phi)\right\rangle=\frac{\partial}{\partial\phi}\left|\Psi(\phi)\right\rangle$.
For mixed state (3) it can be estimated as

$F_{Q}\leq\tilde{F}_{Q}=\sum_{l_{b}=0}^{N}\sum_{l_{a}=0}^{N-l_{b}}p_{l_{a},l_{b}}F_{Q}\left[\left|\xi(\phi)\right\rangle\left\langle\xi(\phi)\right|\right],$
$None$

where
$F_{Q}\left[\left|\xi(\phi)\right\rangle\left\langle\xi(\phi)\right|\right]$
is (S.17) with the state defined as (cf. (3))

$\left|\xi\right\rangle=\frac{1}{\sqrt{p_{l_{a},l_{b}}}}\sum_{n=l_{b}}^{N-l_{a}}C_{l_{a},l_{b}}^{n}e^{in^{k}\phi}\left|N-n-
l_{a}\right\rangle_{a}\left|n-l_{b}\right\rangle_{b}.$ $None$

Notice, for pure states used in (S.18) we have $F_{Q}=\tilde{F}_{Q}$.

Then, substituting Eq. (S.19) into Eq. (S.18) for the upper bound of the QFI
$\tilde{F}_{Q}$ we obtain Eq. (5). The corresponding density matrix given in
Eq. (3) for the input $N00N$-state has the form

$\rho(\phi)=\eta^{N}\left|N00N\right\rangle\left\langle
N00N\right|+\frac{1}{2}\sum_{n=0}^{N-1}p_{n}\left[\left|n,0\right\rangle\left\langle
n,0\right|+\left|0,n\right\rangle\left\langle 0,n\right|\right],$ $None$

where
$\left|N00N\right\rangle=\left(\left|N,0\right\rangle+e^{in^{k}\phi}\left|0,N\right\rangle\right)/\sqrt{2}$
and $p_{n}$ obeys (S.14).

The first term in (S.20) contains the off-diagonal elements carrying the
information about the $\phi$-parameter. At the same time, the sum in (S.20)
consists only of the main-diagonal elements. This occurs due to the initially
maximal entangled $N00N$-state collapsing into a Fock-state, when a single
particle is lost, c.f. [35]. QFI upper bound (5) in this case reads as

$\tilde{F}_{Q}=N^{2k}\eta^{N}.$ $None$

Equation (S.21) allows to estimate the initial total particle number,
$N_{min}$, which provides the minimal error for the $\phi$-measurement with
the $N00N$-state in the presence of losses. Such precision requires the
maximal value of $\tilde{F}_{Q}$ that we can find form condition
$\partial\tilde{F}_{Q}/\partial N=0$. In this case from (S.21) we obtain the
equation for $N_{min}$:

$N_{min}=-\frac{2k}{\ln{\eta}}.$ $None$

As example, for the lossy interferometer with $\eta=0.9$, Eq. (S.22) provides
limitations for the particle number $N_{min}\simeq 19$ and $N_{min}\simeq 57$
for $k=1$ and $k=3$, respectively, cf. [33].

Eq. (S.21) also provides the precision of the phase estimation:

$\delta\phi_{\eta}=\frac{1}{\sqrt{\eta^{N}}N^{k}}$ $None$

with the input $N00N$-state in the presence of losses. As seen from (S.23), at
$\eta\rightarrow 1$, $\delta\phi_{\eta}$ reaches the HL, $\delta_{HL}=1/N$,
and SHL, $\delta_{SHL}=1/N^{3}$, for $k=1$ and $k=3$, respectively.

On the other hand, the SIL and NIL for the setup in Fig. 1 may be obtained
numerically by means of the binomial distributed initial state

$\left|\Psi\right\rangle=\frac{1}{\sqrt{2^{N}}}\sum_{n=0}^{N}\sqrt{\left(\begin{array}[]{c}N\\\
n\end{array}\right)}e^{i\phi n^{k}}|N-n\rangle_{a}|n\rangle_{b}$ $None$

In the presence of losses for (S.24) one can obtain

$\delta\phi_{k}\propto 1/\sqrt{\eta}N^{k-1/2}.$ $None$

The numerical simulations reveal that for $k=1$ Eq. (S.25) matches the SIL,
$\delta\phi_{1}=\delta\phi_{SIL}\equiv 1/\sqrt{\eta N}$, cf. [31]. On the
other hand, for $k\geq 1$ (S.24) provide the scaling of NIL, for example
$\delta\phi_{3}\propto\delta\phi_{NIL}\equiv 1/\sqrt{\eta N^{5}}$.

## References

  * [1] J. I. Cirac, M. Lewenstein, K. Mølmer, and P. Zoller, “Quantum superposition states of Bose-Einstein condensates,” Phys. Rev. A 57, 1208 (1998).
  * [2] A. S. Parkins and D. F. Walls, “The physics of trapped dilute-gas Bose–Einstein condensates,” Phys. Rep. 303, 1-80 (1998).
  * [3] S. G. Lee, B. P. McGinnis, R. Jin, J. Yumoto, G. Khitrova, H. M. Gibbs, R. Binder, S. W. Koch, and N. Peyghambarian, “Subpicosecond switching in a current injected GaAs/AlGaAs multiple quantum well nonlinear directional coupler,” Appl. Phys. Lett. 64, 454 (1994).
  * [4] P. M. Walker, L. Tinkler, D. V. Skryabin, A. Yulin, B. Royall, I. Farrer, D. A. Ritchie, M. S. Skolnick, and D. N. Krizhanovskii, “Ultra-low-power hybrid light–matter solitons,” Nature Commun. 6, 8317 (2015).


# Contextual Biasing with the Knuth-Morris-Pratt Matching Algorithm

Weiran Wang &Zelin Wu &Diamantino Caseiro &Tsendsuren Munkhdalai &Khe Chai Sim
&Pat Rondon &Golan Pundak &Gan Song &Rohit Prabhavalkar &Zhong Meng &Ding Zhao
&Tara Sainath &Yanzhang He &Pedro Moreno Mengibar
Google
<EMAIL_ADDRESS>
###### Abstract

Contextual biasing refers to the problem of biasing the automatic speech
recognition (ASR) systems towards rare entities that are relevant to the
specific user or application scenarios. We propose algorithms for contextual
biasing based on the Knuth-Morris-Pratt algorithm for pattern matching. During
beam search, we boost the score of a token extension if it extends matching
into a set of biasing phrases. Our method simulates the classical approaches
often implemented in the weighted finite state transducer (WFST) framework,
but avoids the FST language altogether, with careful considerations on memory
footprint and efficiency on tensor processing units (TPUs) by vectorization.
Without introducing additional model parameters, our method achieves
significant word error rate (WER) reductions on biasing test sets by itself,
and yields further performance gain when combined with a model-based biasing
method.

##  1 Introduction

Recent years have seen a tremendous explosion in voice user interfaces (VUIs),
like voice search, assistant, and control applications. The success of VUI-
based applications depends on the ability of the underlying Automatic Speech
Recognition (ASR) system to properly transcribe phrases that are contextually
relevant to the speaker, the listener, or both. Examples of contextually-
relevant phrases include names of the speaker’s contacts and geographically-
close points of interest. Contextually-relevant phrases are inherently hard to
recognize because they represent instances of domain shift. For example,
generally, it is much more likely for a single user to speak the name of one
of their contacts than for any given contact name to occur in a given training
data set; indeed, a given name or phrase may not appear at all in an ASR
system’s training set in the case of unorthodox spellings (Ke$ha) or novel
words (COVID-19). Further, contextually-relevant phrases may not be known
until inference time, e.g., as the user of a voice assistant can add contact
names any time before speaking.

ASR _contextual biasing_ is a set of techniques which enables ASR systems to
recognize contextually-relevant words without retraining. Contextual biasing
can generally be grouped into model-based and inference-based approaches.
Model-based methods typically incorporate a biasing component into an end-to-
end (E2E) ASR system (Graves, 2012; Chorowski et al., 2015; Chan et al.,
2016a), which takes in biasing contexts as additional input to the E2E model.
An attention mechanism (Vaswani et al., 2017) is typically used to condition
the model outputs on biasing contexts (Munkhdalai et al., 2021; Chang et al.,
2021; Han et al., 2022) (see Sec 3 for more discussions).

The more classical inference-based approach, dating back to the pre-E2E era,
injects biasing contexts to boost decoding scores for the words or phrases in
the biasing contexts to increase the probability of recognizing those words
(Aleksic et al., 2015; Hall et al., 2015). A compact search graph, based on
Weighted Finite State Transducers (WFSTs, Mohri et al., 2002), is built to
encompass the set of biasing phrases, and incorporated into the normal search
graph which then transduces acoustic model outputs to word-level hypotheses.
Weights are distributed along edges of the biasing search graph, so that when
the acoustic model output extends the matching of the phrases, a bonus score
is added to the hypothesis to help it survive beam search and increase its
likelihood of becoming the top hypothesis. The approach was later extended to
E2E models (Zhao et al., 2019) where bonuses are incorporated at subword
level. While E2E ASR systems have greatly simplified modeling and deployment,
and that most components are readily implemented on GPU or TPU to enjoy
parallel processing, FST-based biasing poses significant challenges for an
efficient TPU-based implementation, due to their inherent sparse nature
(adjacency matrices for FSTs are typically very sparse).

##### Our contributions

In this work, we propose a TPU-friendly implementation of search-based
biasing, leveraging the equivalence between the biasing FST and the efficient
matching algorithm by Knuth et al. (1977), with careful considerations on
memory complexity and efficiency through vectorization. Our algorithms can be
incorporated into the beam search of any ASR system, in both the on-the-fly
rescoring and shallow fusion manner. On large voice search datasets, our
method achieves significant word error rate (WER) reductions on biasing test
sets by itself, without introducing additional model parameters. And when
plugged into a model-based biasing method, namely neural associative memory
(NAM, Munkhdalai et al., 2021), our method leads to further improved biasing
accuracy. Our method enables learning with the discrete structure of ASR
biasing, and can be potentially useful for other sequence transduction tasks.

##  2 Our Method

An intuitive and classical idea for biasing is to check iteratively, at each
beam search step, if the suffixes of partial hypotheses are partially or fully
matching any of the biasing phrases, and give score bonuses to those with
matches. This helps a partial hypotheses to survive beam search pruning, if it
has the potential to develop into a full match of a biasing phrase. In this
section, we develop the algorithms for efficiently performing pattern matching
for multiple biasing phrases, and properly assigning biasing bonus for each
beam search expansion, based on the classical KMP algorithm for string/pattern
matching. We review the classical algorithm in Sec 2.1, describe its usage for
biasing in Sec 2.2, discuss the two variants for beam search in Sec 2.3, and
an extension in Sec 2.4.

##### Notations

Below we use ${\mathcal{P}}$ to denote the pattern sequence to be
searched/matched, and ${\mathcal{T}}$ to denote the sequence to be searched
from; both are strings in the context of the classical matching algorithm or
token sequences in the context of speech recognition. The length of
${\mathcal{P}}$ is denoted $len({\mathcal{P}})$. We use ${\mathcal{P}}[i]$ to
denote the element at (0-based) index $i$, and use
${\mathcal{P}}[s,\dots,t]:=\left[{\mathcal{P}}[s],{\mathcal{P}}[s+1],\dots,{\mathcal{P}}[t]\right]$
to denote the sub-sequence of ${\mathcal{P}}$ with start index $s$ and end
index $t$. Two sequences are equal if they have the same length and
corresponding elements match for all indices.

###  2.1 The Knuth-Morris-Pratt matching algorithm

For searching the occurrences of a string ${\mathcal{P}}$ of length $m$ within
another string ${\mathcal{T}}$ of length $n$, the most naive solution is
perhaps to loop over the set of indices $j=0,1,\dots,n-m$, and check if the
sub-string ${\mathcal{T}}[j,\dots,j+m-1]={\mathcal{P}}$, which requires
another loop over the elements of ${\mathcal{P}}$. Clearly, this algorithm has
a worse-case time complexity of ${\mathcal{O}}(mn)$. There exists, however, a
much more efficient linear-time Knuth-Morris-Pratt (KMP) matching algorithm
(Knuth et al., 1977) for this problem, with a worse case complexity of
${\mathcal{O}}(m+n)$. We extract two major components out of KMP below, which
are used for efficiently maintaining status of matching, as needed by biasing.

####  2.1.1 The failure function

The key insight behind the KMP algorithm is to not waste comparisons: if
during matching we have a partial matching of length $i$ and
${\mathcal{T}}[j]\neq{\mathcal{P}}[i]$, then instead of moving back to index
$j-i+1$ for ${\mathcal{T}}$ and moving back to index $0$ for ${\mathcal{P}}$,
and restarting the matching (by checking whether
${\mathcal{T}}[j-i+1,\dots,j-i+m]={\mathcal{P}}$), we may continue by
comparing ${\mathcal{T}}[j]$ against ${\mathcal{P}}[\pi(i)]$ with some
$\pi(i)<i$, without backtracking in ${\mathcal{T}}$. Here $\pi(i)$ specifies
the index of the _potential_ next match in ${\mathcal{P}}$ when we have a
mismatch for ${\mathcal{P}}[i]$, and is called the _failure function_.

The failure function is originally defined as follows (Cormen et al., 2001):
set $\pi(0)=-1$, and for $i=1,\dots,m-1$,

$\displaystyle\pi(i)=\max\;\left\\{k<i:\;{\mathcal{P}}[0,\dots,k-1]={\mathcal{P}}[i-k,\dots,i-1]\right\\}.$

That is, for $i>0$, $\pi(i)$ is the length of the longest proper prefix that
matches a proper suffix of the sequence ${\mathcal{P}}[0,\dots,i-1]$; the
value is $0$ if no such prefix exists. The special value $-1$ indicates that
there is no possible match starting at the current index of ${\mathcal{T}}$
and we must move to the next index to restart matching: if
${\mathcal{T}}[j]\neq{\mathcal{P}}[0]$, we must move to index $j+1$ in
${\mathcal{T}}$ to compare again with ${\mathcal{P}}[0]$.

To see why this definition helps save unnecessary comparisons, consider the
scenario where we have a partial match of length $i>0$, but then the mismatch
${\mathcal{T}}[j]\neq{\mathcal{P}}[i]$ occurs. Since
${\mathcal{T}}[j-i,\dots,j-1]={\mathcal{P}}[0,\dots,i-1]$, we must have

$\displaystyle{\mathcal{T}}[j-\pi(i),\dots,j-1]={\mathcal{P}}[i-\pi(i),\dots,i-1]={\mathcal{P}}[0,\dots,\pi(i)-1].$

Therefore, without backtracking in ${\mathcal{T}}$, we already have a partial
match of length $\pi(i)<i$, and we then check if
${\mathcal{T}}[j]={\mathcal{P}}[\pi(i)]$ to determine whether we can extend
the partial match; in case of further mismatch, we repeat the process and
backtrack to $\pi(\pi(i))$, $\pi^{3}(i)$,…, etc, until we reach $-1$.

The failure function we use in this work, denoted as $\bar{\pi}(\cdot)$, is
based on the above definition, and has an additional “shortcut” logic (Aho &
Corasick, 1975): for $i=1,\dots,m-1$,

$\displaystyle\bar{\pi}(i)=\left\\{\begin{array}[]{c@{\hspace{2em}}l}\bar{\pi}(\pi(i))\hfil\hskip
20.00003pt&\text{if}\;{\mathcal{P}}[\pi(i)]={\mathcal{P}}[i],\qquad\text{(shortcut)}\\\
\pi(i)\hfil\hskip 20.00003pt&\text{otherwise.}\end{array}\right.$

The rationale behind the shortcut is that, as we are backtracking due to
${\mathcal{T}}[j]\neq{\mathcal{P}}[i]$, in the case of
${\mathcal{P}}[\pi(i)]={\mathcal{P}}[i]$ we deduce
${\mathcal{T}}[j]\neq{\mathcal{P}}[\pi(i)]$, and thus $\pi(i)$ cannot be the
next possible match and we shall keep backtracking. We provide the algorithm
for computing $\bar{\pi}(\cdot)$ in Algorithm 4 (Append A). The time
complexity for building the failure function of a pattern with length $m$ is
${\mathcal{O}}(m)$.

An example of search pattern and its failure function is as follows.

(4)

Algorithm 1 Forward a search pattern with an input token.

${\mathcal{P}}$ with length $m$ and failure function $\Pi$, current partial
matching length $i$, new token $x$.

Updated partial matching length $q$, and if we obtain a full match, after
consuming $x$.

procedure Forward(${\mathcal{P}},i,x$)

$full\\_match\leftarrow False$

if ${\mathcal{P}}[i]=x$ then

$q\leftarrow i+1$

if $q=m$ then $\triangleright$ Full match

$full\\_match\leftarrow True,\quad q\leftarrow 0$

end if

else

$k\leftarrow\Pi[i]$

while $k>=0$ and ${\mathcal{P}}[k]\neq x$ do $\triangleright$ Determinization
loop

$k\leftarrow\Pi[k]$

end while

$q\leftarrow k+1$ $\triangleright$ Either $k=-1$ or ${\mathcal{P}}[k]=x$

end if

return ($q$, $full\\_match$)

end procedure

####  2.1.2 The forward function

With the failure function defined above, we can define a forward function.
Given the matching state, defined as the current partial matching length $i$
(i.e., we have matched ${\mathcal{P}}[0,\dots,i-1]$ so far, and $i$ is the
next index to match in ${\mathcal{P}}$), and a new token $x$ from the string
${\mathcal{T}}$ to be searched, the forward returns the updated partial
matching length (the new position in ${\mathcal{P}}$ to match), after
_consuming_ $x$. Here by “consuming” we mean either we have a match for $x$
and we move to $i+1$ in ${\mathcal{P}}$, or we determine that it is impossible
to match $x$ and restart the matching; in both cases we move beyond $x$ in
${\mathcal{T}}$. The logic is sketched in Algorithm 1.

The complexity of this algorithm mainly lies in the “determinization loop”,
where we keep backtracking until we find a match of $x$ in ${\mathcal{P}}$;
when no such match is possible, we end up with $k=-1$ out of the loop, and
restart matching at the next token in ${\mathcal{T}}$. Additionally, we check
whether we obtain a full match of ${\mathcal{P}}$ after matching token $x$, in
which case we also restart matching at the next token in ${\mathcal{T}}$ (we
are not interested in overlapping matches of patterns in this work).

If we add another loop on top of Algorithm 1 over the tokens in
${\mathcal{T}}$, we recover the KMP search algorithm, which has a time
complexity of ${\mathcal{O}}(n)$ after the failure function is computed (with
${\mathcal{O}}(m)$ complexity). Note how similar is the determinization loop
of Algorithm 1 to the inner loop of Algorithm 4; in fact the latter can be
seen as searching ${\mathcal{P}}$ over itself.

We can design a finite state automaton (FSA) ${\mathcal{A}}({\mathcal{P}})$
with $m$ states, where state $i=0,\dots,m-1$ denotes the state for partially
matching $i$ tokens of ${\mathcal{P}}$, and the forward function provides the
transition function for this automaton, i.e., for an arc that starts at state
$i$ with input $x$, it ends at the state specified by
$\texttt{FORWARD}({\mathcal{P}},i,x)$. With the determinization loop, each
transition consumes a non-epsilon token on its edge, ensuring that
${\mathcal{A}}({\mathcal{P}})$ is deterministic and epsilon-free. See Cormen
et al. (2001, Chapter 32.4) for more detailed discussions on the equivalence
between KMP and FSA.

One could run Algorithm 1 for all $x$ in the vocabulary (all characters in the
alphabet in the case of string matching) for $i=0,\dots,m-1$; this yields a
table of size $m\times|V|$ where $|V|$ is the vocabulary size. While we could
in principle use this table for biasing, the memory cost may be too high when
we have on the level of thousands or more patterns to search, each with some
number of tokens (up to $16$ in our experiments), while $V$ is also in the
thousands (4096 for our ASR system). It is therefore much more memory
efficient to store the failure function which only takes ${\mathcal{O}}(m)$
memory, and we pay the cost of determinization loop. For any $x$, the number
of times we have to backtrack in the determinization loop is bounded by

$\displaystyle\gamma({\mathcal{P}})=\max_{i}\;e_{i},\quad\text{where}\;e_{i}\;\text{is
the integer satisfying}\;\pi^{e_{i}}(i)=-1.$ (5)

As an example, for the pattern in (4), we have $\gamma({\mathcal{P}})=3$ with
maximum achieved at $i=7$.

Algorithm 2 Compute bonus score of a token extension.

Biasing phrases $\\{{\mathcal{P}}^{b}\\}_{b=1}^{B}$, current partial matching
lengths ${\mathcal{I}}=(i^{1},\dots,i^{B})$, new token $x$.

Updated partial matching lengths, and biasing bonus.

procedure ComputeBonus($\\{{\mathcal{P}}^{b}\\}_{b=1}^{B},{\mathcal{I}},x$)

$any\\_match\leftarrow False$ $\triangleright$ Track if there is any full
match

for $b=1,\dots,B$ do

$u^{b},\;match^{b}\leftarrow\text{FORWARD}({\mathcal{P}}^{b},i^{b},x)$

if $match^{b}$ then

$any\\_match\leftarrow True$

$v^{b}\leftarrow len({\mathcal{P}}^{b})$ $\triangleright$ For full match, use
pattern length for computing potential

else

$v^{b}\leftarrow u^{b}$

end if

end for

$bonus\leftarrow\mu(v^{1},\dots,v^{B})-\mu(i^{1},\dots,i^{B})$

if $any\\_match$ then

$u^{b}\leftarrow 0$ for $b=1,\dots,B$ $\triangleright$ In case of any full
match, restart matching for all phrases

end if

return ($(u^{1},\dots,u^{B}),\;bonus$)

end procedure

###  2.2 contextual biasing with KMP

For biasing in ASR, each utterance is associated with $B$ biasing phrases,
denoted as $({\mathcal{P}}^{1},\dots,{\mathcal{P}}^{B})$, and we attempt to
match all of them at each beam search step. Another task is to assign a
_bonus_ , either positive or negative, to each new token expansion proposed by
beam search. We achieve this goal by defining a _potential_ function based on
the state of matching.

For each phrase ${\mathcal{P}}^{b}$, $b=1,\dots,B$, we first define a
_scoring_ function for partial matching of length $i$ (i.e., we have matched
${\mathcal{P}}^{b}[0,\dots,i-1]$ so far). In this work, we simply parameterize
the function to be linear in $i$:

$\displaystyle f({\mathcal{P}}^{b},i)=i\cdot\delta,\qquad\text{for}\quad
i=0,\dots,\,len({\mathcal{P}}^{b}),$

where $\delta\geq 0$ is the per-token bonus and is a hyper-parameter to be
tuned. It is future work to explore more sophisticated scoring functions for
biasing phrases.

Let the partial matching lengths for the $B$ biasing phrases be
${\mathcal{I}}=(i^{1},\dots,i^{B})$. We define the potential function as the
maximum scoring function over phrases:

$\displaystyle\mu(i^{1},\dots,i^{B})=\max_{b=1,\dots,B}\,f({\mathcal{P}}^{b},i^{b}).$

After consuming a new token $x$ for each biasing phrase with the forward
function, the partial matching lengths are updated, based on which we compute
the new potential function; the difference between the potentials is the bonus
for $x$. We sketch this algorithm in Algorithm 2. We additionally track if we
finish matching any phrase fully, in which case we restart matching for all
phrases as we do not want overlapping matches. Note it is possible that $x$
extends matching for multiple phrases, especially if these phrases share
prefix. If the hypothesis was partially matching a phrase and then becomes
non-matching after consuming a new token, the previously added biasing bonus
is canceled (Zhao et al., 2019).

To summarize, we maintain a total of $B$ integers as states for tracking the
progress on each phrase. Consuming a new token and computing its bonus boils
down to running the forward function. We vectorize the for-loop in Algorithm
2, and compute the forward functions for all $B$ phrases in parallel, which
further reduces to looking up the failure function table and running the
determinization loop in parallel. Therefore, the time complexity for Algorithm
2 is ${\mathcal{O}}(\bar{\gamma}B)$, where
$\bar{\gamma}=\max_{b=1,\dots,B}\,\gamma({\mathcal{P}}^{b})$ with the $\gamma$
function defined in (5). Note $\gamma$ is a worse-case bound for the number of
iterations in the determinization loop.

###  2.3 Integrating biasing into beam search

Algorithm 3 Beam search with KMP biasing.

ASR model. Biasing phrases $\\{{\mathcal{P}}^{b}\\}_{b=1}^{B}$. Beam size $K$.
Number of biasing expansion $F$.

Top $K$ hypotheses.

procedure BeamSearchWithBiasing($\\{{\mathcal{P}}^{b}\\}_{b=1}^{B},K,F$)

${\mathcal{H}}\leftarrow\\{(h,s,{\mathcal{I}})\\}$ where $h$ is empty with
score $s=0$, ${\mathcal{I}}$ contains biasing states of all zeros.

for $step=1,2,\dots,$ do

${\mathcal{G}}\leftarrow\\{\\}$ $\triangleright$ ${\mathcal{G}}$ is buffer for
storing intermediate hypotheses

for $(h,s,{\mathcal{I}})\in{\mathcal{H}}$ do

Conditioned on $h$, compute top $F$ expansions
$\\{(x_{1},s_{1}),\dots,(x_{F},s_{F})\\}$ with ASR model, where $x_{k}$ is
token id and $s_{k}$ is its model score

for $k=1,\dots F$ do

$h^{\prime}\leftarrow\text{Append}(h,x_{k}),\;s^{\prime}\leftarrow s+s_{k}$
$\triangleright$ Extend previous hypothesis by a token  Option I (Shallow
Fusion):
${\mathcal{I}}^{\prime},\;bonus\leftarrow\texttt{ComputeBonus}(\\{{\mathcal{P}}^{b}\\}_{b=1}^{B},{\mathcal{I}},x_{k}),\quad
s^{\prime}\leftarrow s^{\prime}+bonus$

${\mathcal{G}}\leftarrow{\mathcal{G}}\cup\\{(h^{\prime},s^{\prime},{\mathcal{I}}^{\prime})\\}$

end for

end for

${\mathcal{H}}\leftarrow\text{Prune}({\mathcal{G}},K)$ $\triangleright$ Prune
to top $K$ hypotheses  Option II (On-the-fly Rescoring):
${\mathcal{G}}\leftarrow\\{\\}$ for $(h,s,{\mathcal{I}})\in{\mathcal{H}}$ do
$\triangleright$ There are exactly $K$ hypotheses in ${\mathcal{H}}$
$x\leftarrow h[-1]$ $\triangleright$ Retrieve the last token
${\mathcal{I}}^{\prime},\;bonus\leftarrow\texttt{ComputeBonus}(\\{{\mathcal{P}}^{b}\\}_{b=1}^{B},{\mathcal{I}},x),\quad
s^{\prime}\leftarrow s+bonus$
${\mathcal{G}}\leftarrow{\mathcal{G}}\cup\\{(h,s^{\prime},{\mathcal{I}}^{\prime})\\}$
end for ${\mathcal{H}}\leftarrow{\mathcal{G}}$

end for

return ${\mathcal{H}}$

end procedure

We propose two ways to incorporate biasing bonus computation into beam search,
with trade offs between accuracy and efficiency. We collectively refer to them
as _KMP biasing_.

  * •

Shallow fusion. In this approach, we perform biasing before pruning: for each
hypothesis, we consider a number of top expansions according to the ASR model
scores, and compute biasing bonus for each of them, which are combined with
ASR scores used for pruning; this is similar to the shallow fusion approach
for applying language models to ASR inference (Gulcehre et al., 2015;
Chorowski & Jaitly, 2017; Zhao et al., 2019).

  * •

On-the-fly (OTF) rescoring. In this approach, after expansions and pruning, we
compute biasing bonuses for the expansion tokens of surviving hypotheses, and
incorporate the bonus into the total score of each hypothesis, to influence
future steps. Note this is different from offline rescoring, which only
modifies total scores for re-ranking final hypotheses.

The two approaches are sketched in Algorithm 3. Let the beam size be $K$,
which is the number of hypotheses maintained at the end of each beam search
step. If we consider $F$ expansions for biasing, the complexity of shallow
fusion is ${\mathcal{O}}(\bar{\gamma}KFB)$ per beam search step. Typically the
biasing accuracy improves with $F$, at the cost of heavier computation. On the
other hand, since we consider a total of $K$ expansions in on-the-fly biasing,
its time complexity is ${\mathcal{O}}(\bar{\gamma}KB)$, cheaper than shallow
fusion biasing by a factor of $F$. As we have multiple hypotheses, each of
which considers multiple extensions, our implementation of ComputeBonus is
parallelized in the (hyp, extension, phrase) combination dimension. The
failure functions are computed for all phrases once before beam search starts.
One can implement the loops using the while statement, and table lookups using
gather or einsum functions provided by tensor-based learning platforms.

###  2.4 Boosting biasing strength with prefixes

In many applications, the biasing phrase frequently follows a set of prefixes
(also known as carrier phrases). For example, when using smart devices to
initiate communication, the user typically speakers “call”, “text”, or “send a
message to” before the contact name. It is natural to bias the ASR system more
heavily towards the user’s contact list, conditioned on recognizing such
prefixes (Zhao et al., 2019). A naive way to extend our method to leverage
prefixes is to augment the original biasing phrases (contact names in the
above use case) with all combinations of prefix and biasing phrase (“call
John”, “text Joe”, etc). If we have $C$ prefixes and $B$ biasing phrases, this
approach leads to $B+CB$ phrases, significantly increasing the cost of KMP
biasing.

We propose an alternative and more time efficient approach, with minimal cost
increase in state maintenance. For each new token, we perform matching for
both prefixes and biasing phrases simultaneously (although the hypothesis
receives no bonus from matching prefixes), with a time complexity of
${\mathcal{O}}(C+B)$. If a new token is not extending the partial matching of
any biasing phrase, but leads to a full matching of some prefix, we restart
matching of biasing phrases for the extended hypothesis, which is marked as
prefix-matching for all biasing phrases. And if a hypothesis is prefix-
matching for some biasing phrase, we boost the scoring function of partial
matches _of that biasing phrase_ by a factor $\lambda>1$. A hypothesis stays
prefix-matching if it was prefix-matching, and the new token extends the
partial matching of the same biasing phrase. Compared with the case without
prefixes, we pay an additional cost of maintaining the states of partial
matching lengths for prefixes, with a memory cost of ${\mathcal{O}}(C)$, and
whether each hypothesis is prefix-matching for each biasing phrase, with a
memory cost of ${\mathcal{O}}(B)$. We sketch the implementation in Algorithm 5
(Appendix B).

Our approach can be interpreted in the WFST framework, as having one FST for
the set of prefixes and another for the set of biasing phrases, and we transit
from the prefix FST to biasing FST when detecting full match of some prefix,
so that the two FSTs are concatenated.

##  3 Related works

##### WFST-based biasing

Initial WFST (Mohri et al., 2002) approaches to contextual ASR (Aleksic et
al., 2015; Hall et al., 2015) performed on-the-fly rescoring (Hori et al.,
2007) during beam-search, for classical ASR systems that use a CLG decoder
graph (Mohri et al., 2008). The contextual phrases are encoded separately from
the CLG in a word-level deterministic WFST with failure transitions. Arbitrary
word-level rescoring functions can be used, including CLG score replacement
and various forms of interpolation. In Vasserman et al. (2016), the approach
was extended to efficiently handle dynamic classes, by encoding non-terminal
labels in the contextual models. Classes are dynamically inserted in the CLG
graph, instead of being inserted in the contextual WFST, avoiding its
exponential growth during determinization. Search errors caused by the late
integration of contextual models at word labels were reduced by Williams &
Aleksic (2017).

Later End-to-End (E2E) ASR systems most often do not have an external LM and
require an alternative WFST approach that uses shallow fusion (Zhao et al.,
2019) instead of on-the-fly rescoring. In this approach, the contextual
information is encoded as a subword-level deterministic WFST with failure
transitions, which is used to directly modify the acoustic scores, before
pruning is done by beam-search. The search space of E2E ASR systems tends to
be sparser than the search space of classic ASR systems, so earlier
integration is necessary to reduce search errors.

WFST contextual modeling can also be approached as a lattice-augmentation
problem (Serrino et al., 2019; Huang et al., 2020). These techniques identify
spans in the word lattice where rare entities are likely to occur and search
for acoustically confusable alternatives that are contextually relevant. The
span identification and fuzzy matching are done using flexible and efficient
WFST-based techniques.

We note that FSTs are good at encoding domain knowledge and complex matching
rules compactly. While they can be represented as graph with sparse adjacency
matrices, in general FSTs are not efficient to use on TPUs which are optimized
for dense operations. Our work is one step towards incorporating FST
functionalities into a TPU-friendly implementation.

##### Model-based biasing

Context can be utilized by adding trainable parameters to the ASR model and
performing model-based biasing (Fu et al., 2023; Harding et al., 2023; Xu et
al., 2023). Learning such parameters in an end-to-end fashion was first
considered in the CLAS model (Pundak et al., 2018), that augmented the LAS
(Chan et al., 2016b) decoder with a suitable attention mechanism. CLAS is
trained by sampling random n-grams (playing to role of bias phrases) from the
reference transcripts. CLAS sampling was later improved in Alon et al. (2019)
by emphasizing proper nouns, and considering hard phonetically-similar
distractors (anti-bias terms). A notable drawback from CLAS is that the full-
context nature of the decoder limits it to non-streaming applications.

The above limitation was addressed in Neural Associative Memory (NAM,
Munkhdalai et al., 2021), a streaming model-based biasing method that utilizes
an external associative memory module (Munkhdalai et al., 2019; Ramsauer et
al., 2020) as an intermediate representation of biasing contexts, and is
augmenting the RNN-T architecture. Given a trained ASR model, let
${\mathbf{x}}$ be audio feature sequence extracted by the encoder, and
${\mathbf{y}}$ be the label sequence. NAM learns a modified conditional
probability $p({\mathbf{y}}|{\mathbf{x}}+\Delta)$ by incorporating into ASR
model an additional feature sequence $\Delta$. To compute $\Delta$, NAM
utilizes an additional text encoder to extract embeddings of biasing phrases
$\\{{\mathcal{P}}^{b}\\}_{b=1}^{B}$, which are used to construct the
associative memory, and another Multi-Head Attention (Vaswani et al., 2017)
module that uses ${\mathbf{x}}$ as query and the associative memory as keys
and values, whose output context vector becomes $\Delta$. Essentially, the
attention module is used to detect the presence of biasing phrases in the
audio. NAM is trained as part of the E2E model (typically with the base ASR
model frozen), so that the likelihood of ground truth, including the biasing
phrase present in the audio, is maximized. At inference time, NAM introduces a
biasing strength parameter $s\geq 0$ to control the effect of external biasing
phrases (Wu et al., 2023), and uses
$p({\mathbf{y}}|{\mathbf{x}}+s\cdot\Delta)$ for decoding. Given that NAM
injects biasing information at the encoder output, while KMP biasing works at
beam search, they can be complimentary to each other, as is observed in our
experiments.

##  4 Experiments

We use a large RNN-Transducer (RNN-T, Graves, 2012) as our base ASR model. Our
training set contains 520M utterances of English voice search queries; the
total amount of audio is 490K hours. A small percentage of the training data
is human transcribed while the rest is pseudo-labeled by a teacher (Hwang et
al., 2022). We tokenize training transcripts, as well as biasing phrases,
using a word-piece model (Schuster & Nakajima, 2012) with an inventory of 4096
tokens. All acoustic and text training data is anonymized and adheres to
Google AI Principles (Google, 2023).

We use 128-dimensional log Mel-filterbank energies, extracted from 32ms window
and 10ms shift, as frontend features. After two 2D-convolution layers, both
with strides 2, the resulting feature sequence has a frame rate of 40ms and
becomes the input to a conformer encoder (Gulati et al., 2020). The encoder
consists of 16 Conformer layers of attention dimension 1536, where each
attention module has 8 heads, and each feedforward network has a hidden
dimension of 6144. The RNN-T decoder uses a $|V|^{2}$ embedding prediction
network (Botros et al., 2021), which computes text features based on two
previous non-blank tokens. The ASR model has a total of 870M parameters. For
decoding, we perform label synchronous beam search with beam size $K=8$. RNN-T
has a special blank token which indicates non-emission and does not alter
decoder and biasing states. The word error rate (WER) of our RNN-T system on
an in-house test set of voice search queries is 3.8%.

##### Evaluation

We use both voice-assistant based real-audio data and TTS synthetic data as
described in Munkhdalai et al. (2023) for evaluation. The real-audio test-set
Contact-Tag contains 7.6K utterances focusing on contact recognition (i.e.,
call $CONTACTS), each utterance is associated with 265 biasing entities and
one of which is the true contact. The TTS data contains three categories: 1.
Anti-Biasing: Utterances simulating general voice-assistant traffic (e.g.,
what’s the weather), we use a super-set of that used in Munkhdalai et al.
(2023) containing 10K utterances; 2. With-Prefix: 2.6K utterances with
patterns such as: open $APPS, call $CONTACT, play $SONG; 3. Without-Prefix:
1.3K Utterances with prefix-less patterns such as $APPS, $CONTACTS, or $SONGS.
The real-audio test set is anonymized and adheres to Google AI Principles
(Google, 2023).

The utterances are associated with up to 3K biasing entities in total, and the
maximum number of tokens in a biasing phrase is 16. With-Prefix and Without-
Prefix evaluate in-domain performance (one of the biasing entities appears in
the transcript truth), while Anti-Biasing evaluates out-of-domain performance
(biasing entities are irrelevant to the transcript truth). In general, a
larger set of biasing entities leads to more confusion in the ASR model and
worse WER. We tune the hyper-parameters of methods based on averaged WERs on
Anti-Biasing and With-Prefix; Without-Prefix and Contact-Tag are treated as
test sets.

Table 1: WER (%) results obtained by KMP biasing. Dataset | KMP Biasing
---|---
OTF Rescoring | Fusion $F=10$ | Fusion $F=50$ | Fusion $F=4096$
$\delta=2.4$ | $\delta=2.2$ | $\delta=2.3$ | $\delta=2.3$
Anti-Biasing, without-biasing WER: 1.7
$B=150$ | 1.7 | 1.7 | 1.7 | 1.7
$B=600$ | 1.8 | 1.8 | 1.8 | 1.8
$B=3000$ | 2.1 | 2.2 | 2.3 | 2.3
With-Prefix, without-biasing WER: 9.6
$B=150$ | 4.1 | 3.7 | 2.6 | 2.4
$B=600$ | 4.5 | 4.0 | 2.9 | 2.7
$B=3000$ | 5.1 | 4.6 | 3.8 | 3.6
Without-Prefix, without-biasing WER: 20.9
$B=150$ | 7.9 | 7.7 | 5.5 | 4.8
$B=600$ | 8.4 | 8.0 | 5.8 | 5.3
$B=3000$ | 10.1 | 9.6 | 7.9 | 7.4
Contact-Tag, without-biasing WER: 14.7
$B=265$ | 8.7 | 8.3 | 7.8 | 7.7

###  4.1 Results by KMP biasing

We first present the results of KMP biasing by itself, without combining with
NAM or score boosting by prefixes. In both the OTF rescoring and shallow
fusion modes, we tune the hyper-parameter $\delta$ which is the biasing bonus
per token along phrases. We observe that, as we increase $\delta$, WERs on
biasing sets first decrease, then stay low for a range of values, and
eventually increase. We provide WER curves of varying $\delta$ in Figure 1
(Appendix C) for both modes.

We provide WERs together with the optimal $\delta$ in Table 1, for OTF-
rescoring and three settings of $F$ for shallow fusion. Our method achieves
significant WER reduction over the base ASR model on all biasing sets, e.g.,
by 50% to over 70% relative on the With-Prefix set with $B=150$ phrases, while
not degrading the Anti-Biasing set by much. We observe that shallow fusion
consistently outperforms OTF rescoring as expected, and in general large $F$
leads to better WER. From $F=50$ to the full vocabulary size $4096$,
improvements start to saturate and we find $F=50$ to offer a good balance
between accuracy and efficiency and use it in the experiments below.

Table 2: WER (%) results obtained by NAM + KMP biasing. $s$ denotes NAM biasing strength, $\lambda$ denotes score boosting factor with prefixes. Dataset | NAM | NAM ($s=0.5$) + KMP biasing | NAM ($s=0.5$) + KMP w. boost
---|---|---|---
OTF Rescoring | Fusion $F=50$ | OTF Rescoring | Fusion $F=50$
$s=0.6$ | $\delta=0.6$ | $\delta=0.8$ | $\delta=0.6,\lambda=2.0$ | $\delta=0.9,\lambda=1.5$
Anti-Biasing, without-biasing WER: 1.7
$B=150$ | 1.9 | 1.9 | 2.0 | 1.9 | 2.1
$B=600$ | 2.1 | 2.1 | 2.3 | 2.1 | 2.3
$B=3000$ | 2.2 | 2.2 | 2.4 | 2.2 | 2.5
With-Prefix, without-biasing WER: 9.6
$B=150$ | 1.5 | 1.0 | 0.9 | 0.9 | 0.8
$B=600$ | 1.8 | 1.3 | 1.2 | 1.0 | 0.9
$B=3000$ | 2.8 | 2.2 | 2.1 | 1.9 | 1.7
Without-Prefix, without-biasing WER: 20.9
$B=150$ | 1.8 | 0.9 | 0.8 | 1.0 | 0.8
$B=600$ | 2.1 | 1.2 | 1.0 | 1.3 | 1.0
$B=3000$ | 4.0 | 3.1 | 2.5 | 3.1 | 2.3
Contact-Tag, without-biasing WER: 14.7
$B=265$ | 3.8 | 3.5 | 3.4 | 3.1 | 3.0

###  4.2 Combining KMP biasing with model-based biasing

Given that KMP biasing is applied during beam search and is agnostic to the
base ASR model, one may wonder if its performance gain is additive to that of
a strong model-based biasing method. We train a state of the art NAM model on
top of our base model, and its performance with normal beam search is provided
in Table 2 (left column). We observe that model-based biasing does achieve
superior results by itself, especially on Without-Prefix and Contact-Tag.

We then perform KMP biasing on top of NAM, and the results are given in Table
2 (mid columns). We find it better to slightly tune down the biasing strength
of NAM when combing it with KMP biasing, and now the optimal $\delta$ is much
smaller than those used in Section 4.1, as the output of NAM already contains
strong biasing information. Nonetheless, KMP provides additional 20%–40%
relative WER improvements over NAM across With-Prefix and Without-Prefix, and
8%–10% relative improvements on Contact-Tag, with small degradation on Anti-
Biasing.

###  4.3 Boosting KMP with prefixes

Finally, we verify the effectiveness of prefixes and Algorithm 5 on top of NAM
+ KMP biasing. We provide three prefixes {call, open, play} as additional
inputs to KMP biasing while NAM only uses biasing phrases as before. For With-
Prefix and Contact-Tag, each test utterance comes from one of App, Contact,
and Song domains, and so it contains one of the prefix while the other two act
as distractors; Without-Prefix does not contain prefixes before biasing
phrases by design.

We fix NAM biasing strength to $s=0.5$, tune the score boosting factor
$\lambda$ over {1.5, 2.0, 2.5}, and search $\delta$ locally around the optimal
values found in Section 4.2. Final results are shown in Table 2 (right
columns). We obtain further gains on With-Prefix and Contact-Tag, while not
degrading much on other sets. In particular, we achieve a final 21% relative
WER reduction on Contact-Tag with shallow fusion over NAM itself. We also
observe that OTF rescoring prefers a larger $\lambda$ than shallow fusion, as
it has less chance to be confused by mis-recognized prefixes and wrongly
boosted bonuses. It is future work to conduct full-fledged experiments with
more complex prefixes.

##  5 Conclusions

We have proposed a TPU-friendly implementation of pattern-matching based
biasing, and demonstrated the effectiveness of its variants on large-scale
voice search queries. Our method achieves significant WER reduction on biasing
sets without introducing additional learning parameters, and is complementary
to a strong model-based biasing method. There are several directions for
future research. To scale up our method to more than thousands of biasing
phrases, we may study deep integration with NAM+ (Munkhdalai et al., 2023),
which performs a quick filtering of a large amount of unlikely biasing phrases
before conducting more careful search over the remaining ones. Our current
implementation has used a fixed per-token score, and it is straightforward to
incorporate an external neural language model for improved bonus computation
(Le et al., 2021). Finally, our on-TPU implementation enables training with
matching-based biasing, and it is an interesting research question to design a
suitable learning objective for further performance gain.

## References

  * Aho & Corasick (1975) Alfred V. Aho and Margaret J. Corasick.  Efficient string matching: An aid to bibliographic search.  _Communications of the ACM_ , 1975.
  * Aleksic et al. (2015) Petar Aleksic, Mohammadreza Ghodsi, Assaf Michaely, Cyril Allauzen, Keith Hall, Brian Roark, David Rybach, and Pedro Moreno.  Bringing contextual information to google speech recognition.  In _Interspeech_ , 2015.
  * Alon et al. (2019) Uri Alon, Golan Pundak, and Tara N Sainath.  Contextual speech recognition with difficult negative training examples.  In _ICASSP_ , pp. 6440–6444. IEEE, 2019.
  * Botros et al. (2021) R. Botros, T.N. Sainath, Robert David, Emmanuel Guzman, Wei Li, and Yanzhang He.  Tied & reduced RNN-T decoder.  In _Interspeech_ , 2021.
  * Chan et al. (2016a) W. Chan, N. Jaitly, Q. V. Le, and O. Vinyals.  Listen, attend and spell: A neural network for large vocabulary conversational speech recognition.  In _ICASSP_ , 2016a.
  * Chan et al. (2016b) William Chan, Navdeep Jaitly, Quoc Le, and Oriol Vinyals.  Listen, attend and spell: A neural network for large vocabulary conversational speech recognition.  In _ICASSP_ , 2016b.
  * Chang et al. (2021) Feng-Ju Chang, Jing Liu, Martin Radfar, Athanasios Mouchtaris, Maurizio Omologo, Ariya Rastrow, and Siegfried Kunzmann.  Context-aware transformer transducer for speech recognition.  In _Automatic Speech Recognition and Understanding Workshop (ASRU)_ , 2021.
  * Chorowski & Jaitly (2017) Jan Chorowski and Navdeep Jaitly.  Towards better decoding and language model integration in sequence to sequence models.  In _Interspeech_ , 2017.
  * Chorowski et al. (2015) Jan Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, KyungHyun Cho, and Yoshua Bengio.  Attention-based models for speech recognition.  _CoRR_ , 2015.
  * Cormen et al. (2001) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  _Introduction to Algorithms_.  2nd edition, 2001.
  * Fu et al. (2023) Xuandi Fu, Kanthashree Mysore Sathyendra, Ankur Gandhe, Jing Liu, Grant P Strimel, Ross McGowan, and Athanasios Mouchtaris.  Robust acoustic and semantic contextual biasing in neural transducers for speech recognition.  In _ICASSP_ , 2023.
  * Google (2023) Google.  Artificial Intelligence at Google: Our Principles, 2023.  URL https://ai.google/principles/.
  * Graves (2012) A. Graves.  Sequence transduction with recurrent neural networks.  In _ICML Workshop on Representation Learning_ , 2012.
  * Gulati et al. (2020) A. Gulati, J. Qin, C.-C. Chiu, et al.  Conformer: Convolution-augmented Transformer for Speech Recognition.  In _Interspeech_ , 2020.
  * Gulcehre et al. (2015) Caglar Gulcehre, Orhan Firat, Kelvin Xu, Kyunghyun Cho, Loic Barrault, Huei-Chi Lin, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  On using monolingual corpora in neural machine translation.  _arXiv:1503.03535_ , 2015.
  * Hall et al. (2015) Keith Hall, Eunjoon Cho, Cyril Allauzen, Françoise Beaufays, Noah Coccaro, Kaisuke Nakajima, Michael Riley, Brian Roark, David Rybach, and Linda Zhang.  Composition-based on-the-fly rescoring for salient n-gram biasing.  In _Interspeech_ , 2015.
  * Han et al. (2022) Minglun Han, Linhao Dong, Zhenlin Liang, Meng Cai, Shiyu Zhou, Zejun Ma, and Bo Xu.  Improving end-to-end contextual speech recognition with fine-grained contextual knowledge selection.  In _ICASSP_ , 2022.
  * Harding et al. (2023) Philip Harding, Sibo Tong, and Simon Wiesler.  Selective biasing with trie-based contextual adapters for personalised speech recognition using neural transducers.  2023\.
  * Hori et al. (2007) Takaaki Hori, Chiori Hori, Yasuhiro Minami, and Atsushi Nakamura.  Efficient WFST-based one-pass decoding with on-the-fly hypothesis rescoring in extremely large vocabulary continuous speech recognition.  _IEEE Transactions on Audio, Speech, and Language Processing_ , 15(4):1352–1365, 2007.
  * Huang et al. (2020) Rongqing Huang, Ossama Abdel-hamid, Xinwei Li, and Gunnar Evermann.  Class LM and word mapping for contextual biasing in end-to-end asr.  In _Interspeech_ , 2020.
  * Hwang et al. (2022) Dongseong Hwang, Khe Chai Sim, Zhouyuan Huo, and Trevor Strohman.  Pseudo label is better than human label.  In _Interspeech_ , 2022.
  * Knuth et al. (1977) Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt.  Fast pattern matching in strings.  _SIAM Journal on Computing_ , 6(2), 1977.
  * Le et al. (2021) Duc Le, Mahaveer Jain, Gil Keren, Suyoun Kim, Yangyang Shi, Jay Mahadeokar, Julian Chan, Yuan Shangguan, Christian Fuegen, Ozlem Kalinli, Yatharth Saraf, and Michael L. Seltzer.  Contextualized streaming end-to-end speech recognition with trie-based deep biasing and shallow fusion.  In _Interspeech_ , 2021.
  * Mohri et al. (2002) Mehryar Mohri, Fernando Pereira, and Michael Riley.  Weighted finite-state transducers in speech recognition.  _Computer Speech and Language_ , 2002.
  * Mohri et al. (2008) Mehryar Mohri, Fernando Pereira, and Michael Riley.  _Speech Recognition with Weighted Finite-State Transducers_ , pp. 559–584.  2008\.
  * Munkhdalai et al. (2019) Tsendsuren Munkhdalai, Alessandro Sordoni, Tong Wang, and Adam Trischler.  Metalearned neural memory.  _Advances in Neural Information Processing Systems_ , 2019.
  * Munkhdalai et al. (2021) Tsendsuren Munkhdalai, Khe Chai Sim, Angad Chandorkar, Fan Gao, Mason Chua, Trevor Strohman, and Françoise Beaufays.  Fast contextual adaptation with neural associative memory for on-device personalized speech recognition.  _arXiv preprint arXiv:2110.02220_ , 2021.
  * Munkhdalai et al. (2023) Tsendsuren Munkhdalai, Zelin Wu, Golan Pundak, Khe Chai Sim, Jiayang Li, Pat Rondon, and Tara N. Sainath.  Nam+: Towards scalable end-to-end contextual biasing for adaptive asr.  In _IEEE Spoken Language Technology Workshop (SLT)_ , 2023.
  * Pundak et al. (2018) Golan Pundak, Tara N Sainath, Rohit Prabhavalkar, Anjuli Kannan, and Ding Zhao.  Deep context: end-to-end contextual speech recognition.  In _IEEE spoken language technology workshop (SLT)_ , 2018.
  * Ramsauer et al. (2020) Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Thomas Adler, Lukas Gruber, Markus Holzleitner, Milena Pavlović, Geir Kjetil Sandve, et al.  Hopfield networks is all you need.  _arXiv preprint arXiv:2008.02217_ , 2020.
  * Schuster & Nakajima (2012) Mike Schuster and Kaisuke Nakajima.  Japanese and korean voice search.  In _ICASSP_ , 2012.
  * Serrino et al. (2019) Jack Serrino, Leonid Velikovich, Petar Aleksic, and Cyril Allauzen.  Contextual recovery of out-of-lattice named entities in automatic speech recognition.  In _ICASSP_ , 2019.
  * Vasserman et al. (2016) L. Vasserman, B. Haynor, and P. Aleksic.  Contextual Language Model Adaptation using Dynamic Classes.  _SLT_ , 2016.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Williams & Aleksic (2017) Ian Williams and Petar Aleksic.  Rescoring-aware beam search for reduced search errors in contextual automatic speech recognition.  In _Interspeech_ , 2017.
  * Wu et al. (2023) Zelin Wu, Tsendsuren Munkhdalai, Pat Rondon, Golan Pundak, Khe Chai Sim, and Christopher Li.  Dual-Mode NAM: Effective Top-K Context Injection for End-to-End ASR.  In _Interspeech_ , 2023.
  * Xu et al. (2023) Tianyi Xu, Zhanheng Yang, Kaixun Huang, Pengcheng Guo, Ao Zhang, Biao Li, Changru Chen, Chao Li, and Lei Xie.  Adaptive contextual biasing for transducer based streaming speech recognition.  _arXiv preprint arXiv:2306.00804_ , 2023.
  * Zhao et al. (2019) Ding Zhao, Tara N. Sainath, David Rybach, Pat Rondon, Deepti Bhatia, Bo Li, and Ruoming Pang.  Shallow-Fusion End-to-End Contextual Biasing.  In _Interspeech_ , 2019.

##  Appendix A Building the failure function

We provide the pseudo code for building the failure function in Algorithm 4.

Algorithm 4 Building failure function $\bar{\pi}$ for a single pattern.

Search pattern ${\mathcal{P}}$ of length $m$

Failure function $\bar{\pi}$ stored in array $\Pi$

$\Pi[0]\leftarrow-1$

$k\leftarrow 0$ $\triangleright$ Index of next possible match

for $i=1,\dots,m-1$ do

if ${\mathcal{P}}[i]={\mathcal{P}}[k]$ then

$\Pi[i]\leftarrow\Pi[k]$ $\triangleright$ Shortcut

else

$\Pi[i]\leftarrow k$ $\triangleright$ $\Pi[i]\leftarrow\pi(i)$

while $k\geq 0$ and ${\mathcal{P}}[i]\neq{\mathcal{P}}[k]$ do

$k\leftarrow\Pi[k]$

end while

end if

$k\leftarrow k+1$ $\triangleright$ Loop invariance: $k=\pi(i+1)$ at end of
each for-loop

end for

##  Appendix B KMP biasing with prefixes

In Algorithm 5 we provide the implementation of bonus computation with a set
of prefixes. The new scoring function is defined as

$\displaystyle\mu_{\lambda}((i^{1},m^{1}),\dots,(i^{B},m^{B}))=\max_{b=1,\dots,B}\,\lambda^{\text{int}(m^{i})}\cdot
f({\mathcal{P}}^{b},i^{b}),$

where $\lambda>1$ is the score multiplier that is effective immediately after
matching a prefix, and $\text{int}(m)$ converts the boolean variable $m$ into
integer, i.e., $int(m)=1$ if $m=True$ and $0$ otherwise.

Algorithm 5 Compute bonus score of a token extension with prefixes.

Prefixes $\\{{\mathcal{R}}^{c}\\}_{c=1}^{C}$, current partial matching lengths
for prefixes ${\mathcal{J}}=(j^{1},\dots,j^{C})$. Biasing phrases
$\\{{\mathcal{P}}^{b}\\}_{b=1}^{B}$, current partial matching lengths for
biasing phrases. ${\mathcal{I}}=(i^{1},\dots,i^{B})$. Current prefix matching
mask ${\mathcal{M}}=(m^{1},\dots,m^{B})$, biasing bonus multiplier $\lambda$,
new token $x$.

Updated partial matching lengths, updated prefix matching mask, and biasing
bonus.

procedure
ComputeBonus($\\{{\mathcal{P}}^{b}\\}_{b=1}^{B},{\mathcal{I}},\\{{\mathcal{R}}^{c}\\}_{c=1}^{C},{\mathcal{M}},x$)

$prev\\_score\leftarrow\mu_{\lambda}((i^{1},m^{1}),\dots,(i^{B},m^{B}))$

$match\\_any\\_bias\leftarrow False$

for $b=1,\dots,B$ do

$u^{b},\;match^{b}\leftarrow\text{FORWARD}({\mathcal{P}}^{b},i^{b},x)$

if $match^{b}$ then

$match\\_any\\_bias\leftarrow True$

$v^{b}\leftarrow len({\mathcal{P}}^{b})$ $\triangleright$ For full match, use
pattern length for computing potential

$ext^{b}\leftarrow True$ $\triangleright$ $ext$ tracks if $x$ extends matching
for ${\mathcal{P}}^{b}$

else

$v^{b}\leftarrow u^{b}$

if $u^{b}>i^{b}$ then

$ext^{b}\leftarrow True$

else

$ext^{b}\leftarrow False$

end if

end if

$m^{b}\leftarrow(m^{b}\And ext^{b})$ $\triangleright$ Update prefix-matching
status

end for

$updated\\_score\leftarrow\mu_{\lambda}((v^{1},m^{1}),\dots,(v^{B},m^{B}))$

$bonus\leftarrow updated\\_score-prev\\_score$

$match\\_any\\_prefix\leftarrow False$

for $c=1,\dots,C$ do $\triangleright$ Try to consume $x$ with prefixes

$n^{c},\;match^{c}\leftarrow\text{FORWARD}({\mathcal{R}}^{c},j^{c},x)$

if $match^{c}$ then

$match\\_any\\_prefx\leftarrow True$

end if

end for

for $b=1,\dots,B$ do

$restart^{b}\leftarrow match\\_any\\_prefix\And(\text{not}\;ext^{b})$

if $restart^{b}$ then $\triangleright$ Restart matching of ${\mathcal{P}}^{b}$
after fully matching prefix

$u^{b}\leftarrow 0,\;m^{b}\leftarrow True$ $\triangleright$ Cancel current
partial matching of ${\mathcal{P}}^{b}$

end if

end for

if $match\\_any\\_bias$ then

$n^{c}\leftarrow 0$ for $c=1,\dots,C$

$u^{b}\leftarrow 0,\;m^{b}\leftarrow False$ for $b=1,\dots,B$

end if

return
($(n^{1},\dots,n^{C}),\;(u^{1},\dots,u^{B}),\;(m^{1},\dots,m^{B}),\;bonus$)

end procedure

##  Appendix C WER of KMP biasing for varying $\delta$

We provide WER curves of varying $\delta$ in Figure 1 for both OTF rescoring
and shallow fusion options.

Figure 1: WER versus $\delta$ for KMP biasing in both OTF rescoring and
shallow fusion ($F=50$) modes, on the With-Prefix set.