Subword Language Model for Query Auto-Completion

1 Introduction

• Long character sequences make neural QAC slow and inaccurate under limited computation, motivating shorter query representations.QAC systems must respond as users enter characters, so latency is an important practical requirement.Source: §1 · p. 1
• Subword language models shorten sequences and decoding steps, while stochastic subword regularization samples multiple segmentations to address ambiguity from noisy data.The authors describe this as their first application of subword regularization to language modeling.Source: §1 · p. 1
• Because a QAC prefix may end inside a token, its segmentation can differ from the target query and make the ground-truth completion less likely.This mismatch is especially likely to affect deterministic segmentation such as BPE.Source: §1 · p. 1
• Retrace decoding goes back a few characters and constrains generated candidates to match those retraced characters; stochastic models also use approximate marginalization to rerank candidates.The method approximates summation over possible segmentations using beam-search output rather than only taking the argmax.Source: §1 · p. 2
• Mean recoverable length (MRL) measures how many upcoming characters can be completed correctly, avoiding prefix-length sampling required by MRR and PMRR.The paper also conducts ablation and model analysis using MRL, MRR, and PMRR.Source: §1 · p. 2

2 Related Work

• Traditional most-popular-completion methods retrieve observed queries matching a prefix, whereas neural methods can generalize to unseen prefixes.Traditional methods may rerank extracted candidates with features, but cannot generate previously unseen queries.Source: §2 · p. 2
• Word-level models shorten sequences but face larger vocabularies, data sparsity, out-of-vocabulary queries, and difficulty handling incomplete final tokens.These constraints matter in search's open-vocabulary setting.Source: §2 · p. 2
• Word-character hybrids use a character decoder for unknown words, but word boundaries can be vague and queries can contain typos, grammatical errors, and spacing errors.The authors argue these issues hinder word-level processing for QAC.Source: §2 · p. 2
• Some hybrid models add word embeddings at boundaries, but their decoding remains character-level and the word signal is sparse.The cited approaches include Park and Chiba (2017) and Fiorini and Lu (2018).Source: §2 · pp. 2–3
• Generating a subword can be interpreted as parallel decoding of its constituent characters, linking the approach to non-autoregressive machine translation.The authors suggest their methods could be used in non-autoregressive NMT and vice versa.Source: §2 · p. 3

3 Subword Language Model

• A subword language model assigns each token a probability conditioned on preceding tokens, with tokens represented as characters or character concatenations.A token sequence maps to a query by concatenating its tokens, and query probability sums over segmentations that produce it.Source: §3 · p. 3

3.1 Segmentation

• BPE segments deterministically from left to right, while subword regularization samples segmentations; marginalizing all segmentations is intractable for long sequences.The number of possible segmentations grows exponentially, and hidden states vary with prior tokenization.Source: §3.1 · p. 3

3.2 Training

• Training estimates query likelihood gradients by sampling segmentations from the segmentation model instead of the expensive posterior over segmentations.This heuristic distribution is learned before language-model training; the objective equals average negative log-likelihood only for deterministic segmentation.Source: §3.2 · p. 3

4 Decoding

• Beam search approximates the most likely completion by decoding a token sequence and concatenating its tokens, but the search space is intractable and predictions can be suboptimal.The basic approach segments the prefix, encodes it with the language model, and decodes from that representation.Source: §4 · p. 4

4.1 Retrace Algorithm

• Retrace starts decoding a few characters before the prefix ends and constrains the next token to cover the retraced characters plus a new character.The maximum retrace distance L limits considered cases; R0 uses no retracing, while R∞ considers every possible retrace step.Source: §4.1 · p. 4, Figure 1 · p. 4

4.2 Reranking Method by Approximate Marginalization

• For stochastic segmentation, reranking candidates after summing probabilities of duplicate tokenizations can improve their ordering, assuming beam outputs dominate omitted sequences.Figure 1 illustrates retracing with prefix “res,” segmentation boundaries, and generated sequences for case Rr.Source: §4.2 · p. 4, Figure 1 · p. 4

5.1 MRR and PMRR

• MRR and PMRR require synthetic prefix-length sampling, and differences in sampling can make evaluation results inconsistent even on the same test dataset.PMRR is described as adding little information beyond MRR because it has a similar tendency.Source: §5.1 · p. 5

5.2 Recoverable Length

• MRL averages the number of characters before the first point where the target query disappears from the completion candidates, eliminating prefix-length selection.It also measures how many characters can be predicted correctly at once for additive QAC, without depending on candidate order.Source: §5.2 · p. 5

6.1 Data

• The AOL experiments use time-based splits, with the final week as test data and the preceding week as validation; nearly half of test queries are unseen.Training, validation, and test sets contain 17,521,031, 1,521,971, and 1,317,632 queries, respectively.Source: §6.1 · p. 5

6.2 Implementation Details

• The same model size is used for character and subword variants to make the comparison fair, despite potential gains from larger models.The models differ in segmentation; the LSTM has hidden size 600 and input embedding size 100.Source: §6.2 · p. 6

6.3 Decoding Results

• MPC is fast and strong overall but cannot predict unseen queries, uses substantial memory, and performs worse than language models on overall scores.It performs better for previously seen queries; combining frequency-based and neural approaches is proposed as a practical trade-off.Source: §6.3 · p. 7
• Subword models remain close to character-model MRR and PMRR, with less than 0.02-point drops; SR has higher PMRR for unseen queries.Table 1 reports that subword models are faster than the character baseline.Source: Table 1 · p. 6, §6.3 · p. 7
• Up to 2.5 times faster than the character baseline, subword models retain minimal performance loss on both CPU and GPU.They also reduce decoding length to less than half by generating multiple characters at once.Source: §6.3 · p. 7
• Retracing produces a large improvement for BPE, whose models perform poorly without it; step 2 is nearly as effective as unlimited retracing.Most subwords are no longer than three characters, while retracing increases decoding length and slows speed.Source: §6.3 · p. 7
• Approximate-marginalization reranking adds a small, orthogonal improvement, raising MRR but lowering PMRR; it runs after beam search and adds little time.Its effect could improve with a larger beam size.Source: §6.3 · p. 7

6.4 Analysis on Evaluation Metrics

• MRL preserves method ordering across query-length changes, while MRR and PMRR depend more strongly on the test data's length distribution.MRR and PMRR fall quickly as queries lengthen; longer prefixes improve completion performance.Source: §6.4 · p. 8

7 Future Work

• Training and decoding approximations deteriorate subword-model accuracy; knowledge distillation from character models is proposed as one possible remedy.The student could learn to match an estimate of query probability to the teacher model's estimate.Source: §7 · p. 8
• Jointly learning segmentation with the language model is an alternative to fixed pretrained segmentation, but fast beam-search decoding remains nontrivial.A conditional semi-Markov assumption permits exact marginalization using dynamic programming.Source: §7 · pp. 8–9
• Real deployment requires more advanced data structures and parallel algorithms to improve speed and meet memory limits.Adaptive runtime control of computation is also identified as helpful.Source: §7 · p. 9

• Up to 2.5 times faster decoding speed came with less than 0.02 point drop of MRR and PMRR versus the character-level baseline.Source: §8 · p. 9
• The subword model is presented as an attractive QAC alternative especially when latency matters, although hyperparameter optimization, decoding search, and neural architectures still have room for improvement.Source: §8 · p. 9
• Mean recoverable length (MRL) is proposed as a source of information for QAC research alongside conventional rank-based evaluation metrics.Source: §8 · p. 9