# Subword Language Model for Query Auto-Completion

arXiv: https://arxiv.org/abs/1909.00599 · HTML: https://mlsanity.com/paper/1909.00599/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2019.

## Built on by (most cited first, 4 of 4)

- [Token Alignment via Character Matching for Subword Completion](https://mlsanity.com/paper/2403.08688/) (2024)
- [QUPID: Quantified Understanding for Enhanced Performance, Insights, and Decisions in Korean Search Engines](https://mlsanity.com/paper/2505.07345/) (2025)
- [Chat-Ghosting: A Comparative Study of Methods for Auto-Completion in Dialog Systems](https://mlsanity.com/paper/2507.05940/) (2025)
- [Router-Suggest: Dynamic Routing for Multimodal Auto-Completion in Visually-Grounded Dialogs](https://mlsanity.com/paper/2601.05851/) (2026)

## Abstract (arXiv)

Current neural query auto-completion (QAC) systems rely on character-level language models, but they slow down when queries are long. We present how to utilize subword language models for the fast and accurate generation of query completion candidates. Representing queries with subwords shorten a decoding length significantly. To deal with issues coming from introducing subword language model, we develop a retrace algorithm and a reranking method by approximate marginalization. As a result, our model achieves up to 2.5 times faster while maintaining a similar quality of generated results compared to the character-level baseline. Also, we propose a new evaluation metric, mean recoverable length (MRL), measuring how many upcoming characters the model could complete correctly. It provides more explicit meaning and eliminates the need for prefix length sampling for existing rank-based metrics. Moreover, we performed a comprehensive analysis with ablation study to figure out the importance of each component.