TL;DR
This paper introduces the "Neural Search Space" (NSS) for Gboard's decoder, replacing traditional N-gram language models with more powerful Neural Network LMs (NN-LMs) to improve suggestion quality. By dynamically constructing the search space at runtime and optimizing for latency, they achieve significant reductions in word modification rates while keeping latency increases acceptable.
What Problem Does This Paper Address?
Mobile keyboards like Gboard rely on statistical decoding to correct errors from "fat finger" typing and provide helpful suggestions (word completion, next word prediction, etc.). The core of this decoding process involves a search space built using language models (LMs). Traditionally, Gboard used N-gram LMs, which are limited in their ability to capture long-range context and suffer from sparsity issues, especially under device memory constraints. This limitation hinders the potential of more advanced Neural Network LMs (NN-LMs), which excel at understanding longer contexts but are computationally expensive and difficult to integrate directly into the existing FST-based decoder. The paper aims to bridge this gap by enabling the use of NN-LMs within Gboard's decoder without a complete overhaul, thereby improving suggestion quality and user experience.
Methods
The paper proposes a "Neural Search Space" (NSS) that replaces the N-gram LM with a Neural Network LM (NN-LM). The key innovation lies in dynamically constructing the search space at runtime by converting NN-LM outputs into a Finite State Transducer (FST) format. This involves:
- Runtime FST Construction: Instead of a static N-gram FST, the system dynamically builds an FST based on the NN-LM's predictions for the current context. This is achieved through two main algorithms:
UpdateLM(for initializing the search space) andExtendLM(for extending it during typing). - FST Structure Redesign: The FST structure is adapted to handle NN-LM outputs, including mechanisms for Out-Of-Vocabulary (OOV) words by falling back to a larger unigram state.
- Dynamic Inference: To address the challenge of scoring multi-word candidates with NN-LMs, a dynamic inference mechanism is introduced. This involves expanding the FST based on likely target words, allowing for more accurate scoring of longer sequences.
- Latency Optimizations: To mitigate the inherent latency increase from NN-LM inference and dynamic FST construction, several optimizations are employed:
- Arc Pruning: Lower probability arcs are pruned to reduce the FST size.
- Dynamic Inference Pruning: Thresholds are used to limit which states are expanded during dynamic inference.
- Customized FST Implementation: A more efficient FST data structure is developed to handle frequent updates and resets, improving performance.
Datasets
The paper does not explicitly mention specific datasets used for training the NN-LM. However, it states that the NN-LM is trained via Federated Learning (FL) on user data from Gboard, preserving user privacy. The evaluation is conducted using live experiments on "uniform random samples of the eligible Gboard populations" across various languages (en-US, en-GB, es-ES, pt-PT, es-US).
Key Insights and Ideas
- NN-LMs are powerful for context: The core insight is that NN-LMs, with their ability to capture long-range context, can significantly improve the quality of keyboard suggestions compared to traditional N-gram models.
- Dynamic FST construction is key: The paper demonstrates that it's feasible to integrate these powerful NN-LMs into a production system by dynamically constructing the search space (FST) at runtime, rather than relying on static, pre-built models.
- Latency is the main hurdle, but manageable: While NN-LMs introduce latency, the paper shows that through careful optimization (pruning, dynamic inference control, custom FST), this latency can be kept within acceptable bounds, especially on higher-end devices.
- Higher-end devices benefit more: The improvements in WMR and WPM are more pronounced on higher-end devices, suggesting that hardware capabilities play a significant role in realizing the full potential of such advanced models.
- Hybrid approaches are promising: The paper hints at future work exploring hybrid systems that leverage both FSTs and neural models, suggesting that a complete replacement of FSTs with neural decoders might not be immediately feasible due to existing system complexity and debugging challenges.
Key Results
Live experiments on various languages showed:
- Reduced Word Modified Ratio (WMR): NSS reduced WMR by 0.26% to 1.19% across languages, indicating significantly fewer user corrections needed.
- Increased Typing Speed (WPM): WPM consistently improved, suggesting that the latency cost did not negatively impact user experience.
- Acceptable Latency Increase: Latency increased in the range of 17% to 28% for "ALL" devices, with higher-end devices experiencing smaller increases (e.g., 12.89% for es-US on 6G+ devices).
- Device Dependency: Higher-end devices showed greater improvements in WMR and WPM with smaller latency increases.
Limitations and Future Work
Limitations:
- Latency on lower-end devices: While acceptable, the latency increase is still a concern, particularly for lower-end devices.
- OOV handling: While addressed by falling back to unigrams, the handling of truly out-of-vocabulary words might still be a challenge.
- NN-LM vocabulary size: The NN-LM has a limited vocabulary (30k words) compared to the full lexicon (170k words), requiring mechanisms to bridge this gap.
Future Work:
- Integrating Transformer models: Exploring the use of more powerful Transformer models within NSS, potentially with parameter constraints to manage computational cost.
- Leveraging richer context: Incorporating signals like application domain, country, time, and user history to further enhance context awareness.
- Exploring SentencePiece LMs: Using subword tokenization (SentencePiece) to improve handling of OOV words and provide better language representation.
- Neural Decoders: Investigating the replacement of FST-based decoders with purely neural decoders, while acknowledging current challenges in quality gap and debugging.
- Hybrid approaches: Running neural models in parallel with the FST system and merging their suggestions to leverage the strengths of both.
Summary updated