Source-linked AI summary
Efficient Natural Language Response Suggestion for Smart Reply
Matthew Henderson, Rami Al-Rfou, Brian Strope, Yun-hsuan Sung, Laszlo Lukacs, Ruiqi Guo, Sanjiv Kumar, Balint Miklos, Ray Kurzweil
TL;DR
The paper addresses response suggestion for human-to-human conversations, where end-to-end systems must learn language and perform a useful task. It uses feed-forward neural networks and efficient vector search, achieving higher quality than the original sequence-to-sequence system with a small fraction of its computation and latency.
Problem
Response suggestion in human-to-human conversations requires end-to-end systems to learn language and perform a useful task, while rule-based systems are brittle and slow to extend.
Method
The method scores input-response consistency with feed-forward neural networks over n-gram representations and uses factorized dot products with efficient approximate search over precomputed response vectors.
Results
The Smart Reply production system achieved higher quality than the original sequence-to-sequence system with a small fraction of the computation and latency.
Takeaways & Limitations
The approach provides a minimal, efficient, and scalable implementation for ranking-based applications without generating novel responses.
Takeaways & Limitations
The system does not address generation of novel responses and required language-model score boosting because biased negative sampling produced overly specific, often long suggestions.
Abstract
from arXiv · showhide
This paper presents a computationally efficient machine-learned method for natural language response suggestion. Feed-forward neural networks using n-gram embedding features encode messages into vectors which are optimized to give message-response pairs a high dot-product value. An optimized search finds response suggestions. The method is evaluated in a large-scale commercial e-mail application, Inbox by Gmail. Compared to a sequence-to-sequence approach, the new system achieves the same quality at a small fraction of the computational requirements and latency.
1 INTRODUCTION
The paper investigates efficient end-to-end response suggestion using feed-forward networks with n-gram representations, motivated by the cost and mismatch of Seq2Seq models for ranking fixed responses. It evaluates the approach in Inbox by Gmail using anonymized email data and live user interactions.
- Motivation: End-to-end response suggestion must learn language and produce useful responses in human-to-human conversations.The paper frames response suggestion as an end-to-end task with additional challenges for dialog systems, including robust interaction and consistency across turns.
- Motivation: Seq2Seq models are generalized but can be slow and complicated to train, and require extra normalization when ranking fixed response sets.Their generative formulation introduces a mismatch with Smart Reply’s fixed candidate set.
- Approach: The proposed hierarchy represents sequences with feed-forward vector computations and implicit n-grams, avoiding the need for LSTM long-term sequence encoding.The paper states that feed-forward networks are faster than LSTMs for training and inference because LSTM computation scales with sequence length.
- Evaluation: Networks built on n-gram embeddings are computationally inexpensive relative to recurrent and convolutional encoders.The paper also reports training on anonymized Gmail data and evaluating suggestions with Inbox by Gmail users.
- Approach: The method scores fixed candidate responses through final dot products, allowing response-side precomputation and framing suggestion as a search problem.Deep layers and delayed input-response combination encourage implicit semantic representations.
2 PROBLEM DEFINITION
Smart Reply processes received emails through triggering, response selection, and diversification, while this paper focuses on efficiently selecting responses from a fixed candidate set. The proposed feed-forward model uses factorized dot products and approximate search over precomputed response vectors.
- Candidate responses: The system selects from millions of common messages in a fixed response set rather than generating novel responses.Response selection searches the set for the top N scoring candidates.
- Smart Reply pipeline: Smart Reply first decides whether to show suggestions, then selects responses, and finally diversifies the displayed set.The triggering model determines whether suggestions should be given; response selection and diversification follow.
- Proposed selection model: A feed-forward neural network with factorized dot products enables highly efficient and accurate approximate search over precomputed response vectors.The paper presents this as the response-selection alternative to the baseline sequence-to-sequence search.
- Smart Reply pipeline: Diversification removes redundant suggestions and uses response labels to ensure affirmative and negative alternatives are represented when appropriate.This stage occurs after response selection.
3 BASELINE SEQUENCE-TO-SEQUENCE SCORING
The baseline models the probability of a response sequence conditioned on an input sequence with an LSTM encoder-decoder. At inference, beam search retrieves likely responses from the fixed candidate set through its prefix trie.
- Baseline model: The baseline response-selection model is an LSTM recurrent neural network implementing sequence-to-sequence learning.It computes conditional probabilities over response sequences given input sequences.
- Sequence scoring: The input email is tokenized into a word sequence, and the LSTM computes conditional probabilities over response tokens.The response sequence is conditioned on the complete input and previously generated response tokens.
- Training: Training maximizes the log-probability of observed email-response pairs under P(y | x).The training data consists of a large collection of emails and responses.
- Inference: At inference, beam search is restricted to the prefix trie of the fixed response set to find likely candidate responses.The stated search time complexity is O(|x| + b|y|), where b is beam width.
4 FEEDFORWARD APPROACH
The paper replaces generative response selection with feed-forward scoring models that represent emails and responses using n-gram embeddings, enabling efficient fixed-candidate ranking through dot products and approximate search. A hierarchical quantization method preserves retrieval quality while substantially accelerating search.
- Scoring models: Feed-forward scoring learns to rank potential responses directly instead of learning a generative model.The response-selection task models P(y | x), while feed-forward networks assign scores to candidate responses.
- Scoring models: N-gram embeddings are summed into fixed-dimensional representations that are fast to compute while retaining semantic and limited word-order information.The resulting bag-of-n-grams representation Ψ(x) is learned jointly with the neural network parameters.
- Dot-product scoring: The dot-product model factorizes scoring into input-only and response-only vectors, allowing response representations to be precomputed and suggestions to be found by high-dot-product search.This factorization also enables efficient matrix-multiplication training with multiple negatives.
- Multiple features: Multiple-feature models use feature-specific subnetworks and combine their representations hierarchically; the dot-product variant retains efficient vector search and multiple-negative training.Its final score remains a dot product between an input vector and a response vector, although vector arithmetic may constrain feature representations.
- Efficient search: Hierarchical quantization combines vector quantization, learned rotation, and product quantization to approximate response embeddings for maximum inner-product search.The approach targets the high-recall retrieval requirement of Smart Reply while exploiting precomputed response vectors.
- Efficient search: 99.89% recall is achieved with a speed-up factor over 10 for top-30 retrieval, outperforming the cited approximate-search baselines.Recall is measured against exhaustive search, which provides 100% recall at a speed-up factor of 1.
5 EVALUATION
The evaluation uses large-scale anonymized Gmail data, offline ranking tests, and online Smart Reply experiments to compare successive architectures with the Seq2Seq baseline. The system improves efficiency through dot-product scoring, staged or hierarchical search, and training changes while preserving or improving suggestion quality.
- Data and evaluation: Offline evaluation ranks the correct response among 99 random competitors and reports precision at 1 (P@1), which correlates with online model quality.The evaluation uses a set of 100 responses containing one correct response and 99 incorrect responses.
- Offline evaluation: Joint scoring is stronger at equal batch size but scales quadratically, whereas dot-product scoring uses linear forward passes and a single K by K matrix multiply, enabling larger batches and more accurate models.The joint model captures complex cross-features, while dot-product models trade some pairwise modeling for computational scalability.
- Offline evaluation: Multiple-negative training reduces P@1 error by 20% relative to sigmoid-loss classification across conversational datasets, including a Smart Reply increase from 47% to 58%.The reported Smart Reply example uses a different version of the Smart Reply data.
- Online evaluation: A two-pass system using fast dot-product retrieval followed by joint rescoring provides a 50x speedup over exhaustive joint scoring.The first pass ranks responses using precomputed response vectors; the second pass searches the M-best list with the more accurate joint model.
- Online evaluation: Later iterations raised conversion above Seq2Seq, preserved quality while increasing speed 5 times, and then doubled speed again with hierarchical quantization search without compromising quality.The final system produces better-quality suggestions than Seq2Seq with a small percentage of its computation and latency.
6 CONCLUSIONS
The paper presents a feed-forward response-scoring architecture that supports efficient runtime search over potential responses. In live Smart Reply experiments, it achieved higher quality than the original sequence-to-sequence system using a small fraction of the computation and latency, while remaining limited to ranking fixed response sets.
- 6 CONCLUSIONS: A hierarchy of deep feed-forward networks over simple n-gram representations scores the consistency between input messages and potential responses.The architecture separates input reading from precomputing representations of possible responses.
- 6 CONCLUSIONS: Separate input and response representations enable a highly efficient runtime search.
- 6 CONCLUSIONS: Live production experiments produced a system with higher quality than the original sequence-to-sequence system and a small fraction of its computation and latency.
- 6 CONCLUSIONS: The method ranks a fixed set of response suggestions rather than generating novel responses.