Paper deep dive
DocQAC: Adaptive Trie-Guided Decoding for Effective In-Document Query Auto-Completion
Rahul Mehta, Kavin R, Indrajit Pal, Tushar Abhishek, Pawan Goyal, Manish Gupta
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 6/21/2026, 11:11:15 AM
Summary
The paper introduces DocQAC (Document Query Auto-Completion), a novel task and framework for in-document search. Unlike traditional WebQAC, DocQAC leverages document-specific context (content, titles, and local query history) to provide precise, contextually grounded query suggestions. The authors propose an adaptive trie-guided decoding framework that uses an adaptive penalty mechanism to steer encoder-decoder models (like T5 and BART) toward high-quality, document-relevant completions. This approach effectively balances the high recall of trie-based methods with the generative flexibility of Large Language Models (LLMs), outperforming larger models like LLaMA-3 and Phi-3 in efficiency and precision for seen-query settings. The work also introduces a new benchmark dataset derived from ORCAS, enriched with query-document pairs and relevance labeling via GPT-4.
Entities (10)
Relation Signals (4)
DocQAC → isevaluatedon → ORCAS
confidence 100% · We evaluate our method on a newly introduced DocQAC benchmark derived from ORCAS
GPT-4 → usedfor → Relevance Labeling
confidence 100% · We use GPT-4 as a binary relevance classifier to evaluate whether each query-document pair is relevant or not
DocQAC → uses → Adaptive Trie-Guided Decoding
confidence 100% · To address this setting, we propose a novel adaptive trie-guided decoding framework
Adaptive Trie-Guided Decoding → improves → T5
confidence 90% · When applied to encoder-decoder models like T5 and BART, our trie-guided framework outperforms strong baselines
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Query auto-completion (QAC) has been widely studied in the context of web search, yet remains underexplored for in-document search, which we term DocQAC. DocQAC aims to enhance search productivity within long documents by helping users craft faster, more precise queries, even for complex or hard-to-spell terms. While global historical queries are available to both WebQAC and DocQAC, DocQAC uniquely accesses document-specific context, including the current document's content and its specific history of user query interactions. To address this setting, we propose a novel adaptive trie-guided decoding framework that uses user query prefixes to softly steer language models toward high-quality completions. Our approach introduces an adaptive penalty mechanism with tunable hyperparameters, enabling a principled trade-off between model confidence and trie-based guidance. To efficiently incorporate document context, we explore retrieval-augmented generation (RAG) and lightweight contextual document signals such as titles, keyphrases, and summaries. When applied to encoder-decoder models like T5 and BART, our trie-guided framework outperforms strong baselines and even surpasses much larger instruction-tuned models such as LLaMA-3 and Phi-3 on seen queries across both seen and unseen documents. This demonstrates its practicality for real-world DocQAC deployments, where efficiency and scalability are critical. We evaluate our method on a newly introduced DocQAC benchmark derived from ORCAS, enriched with query-document pairs. We make both the DocQAC dataset (this https URL) and code (this https URL) publicly available.
Tags
Links
- Source: https://arxiv.org/abs/2604.18257v1
- Canonical: https://arxiv.org/abs/2604.18257v1
Trouble viewing inline? Open PDF directly →
Full Text
61,347 characters extracted from source content.
Expand or collapse full text
by DocQAC: Adaptive Trie-Guided Decoding for Effective In-Document Query Auto-Completion Rahul Mehta mehtarahul@microsoft.com Microsoft Corporation HyderabadIndia Indian Institute of TechnologyKharagpurIndia , Kavin R V kavinrv13@gmail.com Indian Institute of Technology KharagpurKharagpurIndia , Indrajit Pal pal.indrajit99@gmail.com IndependentBengaluruIndia , Tushar Abhishek tabhishek@microsoft.com Microsoft Corporation HyderabadIndia , Pawan Goyal pawang.iitk@gmail.com Indian Institute of Technology KharagpurKharagpurIndia and Manish Gupta gmanish@microsoft.com Microsoft Corporation HyderabadIndia (2026) Abstract. Query auto-completion (QAC) has been widely studied in the context of web search, yet remains underexplored for in-document search, which we term DocQAC. DocQAC aims to enhance search productivity within long documents by helping users craft faster, more precise queries, even for complex or hard-to-spell terms. Unlike traditional WebQAC systems, DocQAC can leverage rich document context, having access not only to the partially typed user query and global historical queries, but also the content of the current document itself, and crucially, the document-specific history of user query interactions. To address this setting, we propose a novel adaptive trie-guided decoding framework that uses user query prefixes to softly steer language models toward high-quality completions. Our approach introduces an adaptive penalty mechanism with tunable hyperparameters, enabling a principled trade-off between model confidence and trie-based guidance. To efficiently incorporate document context, we explore retrieval-augmented generation (RAG) and lightweight contextual document signals such as titles, keyphrases, and summaries. When applied to encoder–decoder models like T5 and BART, our trie-guided framework outperforms strong baselines and even surpasses much larger instruction-tuned models such as LLaMA-3 and Phi-3 in seen-query settings. This demonstrates its practicality for real-world DocQAC system deployments, where efficiency and scalability are critical. We evaluate our method on a newly introduced DocQAC benchmark derived from ORCAS, enriched with query–document pairs. We make both the DocQAC dataset111Dataset- https://bit.ly/3IGEkbH and code222Code- https://github.com/rahcode7/DocQAC publicly available. In-Document Search, Trie-Guided Decoding, Query Auto Completion, Large Language Models, Retrieval Augmented Generation †journalyear: 2026†copyright: c†conference: Proceedings of the 49th International ACM SIGIR Conference on Research and Development in Information Retrieval; July 20–24, 2026; Melbourne, VIC, Australia†booktitle: Proceedings of the 49th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’26), July 20–24, 2026, Melbourne, VIC, Australia†doi: 10.1145/3805712.3809644†isbn: 979-8-4007-2599-9/2026/07†ccs: Computing methodologies Natural language processing†ccs: Information systems Query suggestion Document Prefix WebQAC output DocQAC output https://en.wikipedia.org/wiki/Paris fr freejobalert, freepik, free games, free fire max, from tv series, friends, friendship quotes, freecell, frank lampard, free job alert 2025 france capital, france tourism, france history, france landmarks, france culture, france travel guide, france famous cities, france eiffel tower, france paris attractions, france paris museums https://en.wikipedia.org/wiki/Brad_Pitt a amazon, adobe acrobat, anydesk, australia vs india, amazon prime, allahabad, aiden markram, american airlines, amitabh bachchan, alice in borderland american actor, academy awards, angelina jolie, angelina jolie husband, aniston, alcoholism, academy award nominations, angelina jolie and brad pitt relationship, autobiography of brad pitt, a river runs through it https://history.house.gov/People/Office/Speakers-List/ spea speaker, speak no evil, speak, speaking, speaker cleaner, speak now, spear, speaker test, speaker cleaning, spearmint tea speaker of the house, speaker of the house history, speaker of house of representatives, speaker history, speakers of the us house, speakers, speaker henry clay, speaker of the house current status, speaker of the house duties, speaker of the house responsibilities Table 1. Examples of top few results from WebQAC versus DocQAC systems. 1. Introduction Query Auto Completion (QAC) is the first service with which search users interact, offering ranked query suggestions based on the partially typed user query (which we call a prefix). Traditionally, the most common approach to solving this task involves utilizing highly efficient trie-based data structures (Hsu and Ottaviano, 2013) with techniques like Most Popular Completions (MPC) (Bar-Yossef and Kraus, 2011). Recently, deep learning-based approaches that utilize sequence-to-sequence models trained on historical queries have been employed to generate high-quality completions (Lee et al., 2021; Mustar et al., 2020; Wang et al., 2020; Jiang and Wang, 2018). We will refer to such QAC systems for Web search as WebQAC systems. 1.1. Motivation While QAC has been extensively studied in the context of web search (WebQAC), where suggestions are driven by global popularity and historical query logs, there has been surprisingly no research dedicated to QAC for in-document search. We term this under-explored task as Document Query Auto-Completion (DocQAC). DocQAC systems can help users in (a) reducing search time by predicting and suggesting search terms, which in turn helps quickly find relevant information within long documents, and (b) improving search accuracy by minimizing typographical errors, especially for documents with rare and orthographically challenging terms. Overall, a DocQAC system can enhance user productivity, ensure that users are using the correct terminology and phrases, and assist users who may not be familiar with the exact terms or keywords to use, making it easier for them to navigate and locate specific information without having to sift through long documents. The extra document context in DocQAC systems brings an additional challenge. How do you best leverage this document context and associated metadata? How do you handle long documents? 1.1.1. Difference between DocQAC and WebQAC A DocQAC system differs from a WebQAC system in several fundamental ways. • Intent locality: In WebQAC, user intent is often navigational (finding a specific website, e.g., “youtube”) or broad information. In DocQAC, user intent is tightly coupled to the current document and is exploratory in nature. As a result, globally frequent queries are often irrelevant, while rare or document-specific terms become critical for accurate completion. • Vocabulary shift: Documents frequently contain named entities, domain-specific phrases, and long-tail terminology that do not appear frequently in global query logs. • Contextual Grounding: The same prefix may require radically different completions depending on the document being viewed. Unlike WebQAC, which prioritizes global consensus, DocQAC requires local contextual grounding: suggestions must be relevant to the specific content of the document at hand. This capability is critical for enhancing productivity in long-form document consumption, aiding users in navigating dense technical texts, and mitigating orthographic errors for rare, document-specific terms. Table 1 illustrates this gap. For identical prefixes, WebQAC systems produce globally popular suggestions that are largely irrelevant to the document context, while a DocQAC system must surface completions grounded in the document’s content and semantics. 1.1.2. Use Cases of DocQAC A DocQAC system can appear in document interaction tools like Adobe Acrobat’s in-document search, text editors, IDEs, and enterprise document management systems. Here, users frequently write short prefixes to locate sections, entities, or phrases within a document. For example, when navigating long PDFs, reviewing technical documentation, or searching policy and legal documents. DocQAC auto-completion in these scenarios improves efficiency by suggesting contextually relevant, document-specific terms during query formulation. 1.2. Core Contributions Figure 1. DocQAC Dataset Construction Pipeline (detailed in Section 4). A document D in ORCAS has clicked queries Q. Query Augmentation augments D with non-clicked queries Q′Q which are similar to Q. Relevance Labeling filters queries in Q and Q′Q that are irrelevant to D. Click Popularity Estimation estimates pseudo-counts for Q′Q queries. Finally we create dataset splits. Overall, we make the following main contributions in this paper. • Formalization of the DocQAC Task: We formalize document specific Query Auto-Completion (DocQAC) as a distinct problem paradigm, differentiating it from standard WebQAC by its strict faithfulness constraints and “cold-start” document challenges. To support this, we also release a dataset benchmark for the DocQAC task. • Trie-Guided Inference Time Decoding Framework: We develop a novel adaptive trie-guided decoding framework to softly bias encoder-decoder language model generation toward valid completions without adding new parameters. This method resolves the “generative drift” problem inherent in standard LLMs by dynamically pruning tokens that do not appear in the document’s query log or body. • Efficiency and Performance Gains: We demonstrate that small, guided encoder-decoder models (e.g., T5-Small, BART-Base) significantly outperform unguided Large Language Models (LLaMA-3, Phi-3). This establishes a new state-of-the-art for efficient, latency-constrained query completion. • Understanding effect of Context Representations: We also perform detailed ablation studies to understand the role of document context, such as using document title and URL tokens, summaries or keyphrases extracted from documents. To facilitate further research in this direction, we make the datasetLABEL:dataFN and codeLABEL:codeDataFN publicly available. 2. Related Work 2.1. Autocompletion Methods 2.1.1. Trie-Based Methods Given a prefix, the MPC model, proposed in (Bar-Yossef and Kraus, 2011), extracts a limited number (k) of completions from a character-trie structure (also referred to as the main trie) built using a corpus of past queries. 2.1.2. Generative Methods QueryBlazer (Kang et al., 2021) is a fully generative, low-latency query auto-completion method that is capable of leveraging both previously encountered queries and generating completions for new, unseen queries. At inference time, the user’s query prefix is input into the subword encoder as a sequence of characters. The encoder then produces all potential top-k subword sequences that can be generated from the partial input provided. Deep learning methods like Hierarchical RNN Encoder-decoder (Song et al., 2017) with pointer generator (Dehghani et al., 2017), GRUs with user and time representations (Fiorini and Lu, 2018) and Transformer-based hierarchical encoder (Yin et al., 2020) have also been studied. While showing suggestions it is important to not show defective suggestions and prefixes. To avoid defects, researchers have used LSTMs for inappropriate query suggestion detection (Yenala et al., 2017), A* search and Markov noisy channel models for online spell correction (Duan and Hsu, 2011), and character RNNs (Wang et al., 2018). There have also been attempts to generate effective QAC suggestions (Maurya et al., 2023; Maheswaran et al., 2024a, b; Mandal et al., 2026, 2026). 2.2. DocQAC-like systems Unfortunately, there has been no work on the DocQAC problem which we study in this paper. There have been some attempts on type-ahead completions for Teams (Trajanovski et al., 2021) and email composition systems like GMail (Chen et al., 2019) and Outlook (Trajanovski et al., 2021), which help users to compose, whereas DocQAC helps the users in finding information (Navigation). Further, existing WebQAC methods cannot be trivially adapted for the DocQAC task since it involves careful modeling of the additional document context. Our proposed system can be effectively integrated with in-document search systems like KTRL+F (Oh et al., 2024) to enhance their functionality. 2.3. Constrained Decoding Recent studies on constrained decoding have focused on constraining the output of language models, primarily using hard constraints. Early methods such as grid beam search (Hokamp and Liu, 2017) and dynamic beam allocation (Post and Vilar, 2018) introduced mechanisms to enforce the inclusion of specific words or phrases in the generated text. In parallel, grammar-based decoding approaches (Geng et al., 2023) have emerged as another direction for structured generation. However, such hard constraint mechanisms often limit the generative flexibility of models, making them less suitable for open-ended tasks such as WebQAC or DocQAC, where a balance between adherence and fluency is crucial. Recently, prefix trie-based methods (Chan et al., 2025) have been explored to improve beam search efficiency during decoding. Although, there exists work on utilizing tries in constrained generation in other tasks of information retrieval (De Cao et al., 2021; Bevilacqua et al., 2022) ,no prior work exists that applies an adaptive penalty schedule at decoding-time on trie constrained generation.In document-level QAC, such adaptive constraints become even more meaningful where the document context encoded in the trie naturally guides generation, allowing the model to generate plausible and context-aligned completions while maintaining the advantages of neural generation. 3. DocQAC Problem Formulation Let V be the vocabulary of all terms and D be a corpus of documents. Given a query prefix p consisting of a sequence of tokens (w1,…,wk)(w_1,…,w_k), the goal of Query Auto-Completion (QAC) is to generate the optimal completion suffix s such that the full query q=p⊕sq=p s maximizes the posterior probability. Existing WebQAC (Global Optimization): Standard WebQAC operates in an “open-world” setting where the objective is to maximize the likelihood of q given the prefix p and the global user search history ℋglobalH_global. Mathematically, this approximates the marginal probability over all possible latent contexts (or documents d): (1) qweb∗=argmaxq∈∗P(q∣p,ℋglobal)q^*_web= *argmax_q ^*P(q p,H_global) Consequently, WebQAC systems are biased toward “head” queries that are frequent across the entire corpus, often ignoring specific document contexts. The support of the distribution is effectively the entire vocabulary V, meaning any plausible string has non-zero probability (P>0P>0). DocQAC (Conditional Constrained Optimization): In contrast, DocQAC is a “closed-world” task where the completion is strictly conditioned on a specific observed document dcurrd_curr as well as the global user search history for this document HcurrH_curr. The objective changes to maximizing the conditional probability: (2) qdoc∗=argmaxq∈∗P(q∣p,dcurr,ℋcurr)q^*_doc= *argmax_q ^*P(q p,d_curr,H_curr) Unlike WebQAC, where unseen queries are smoothed, DocQAC treats suggestions outside the document’s scope as hallucinations. This fundamental shift requires models to suppress the global token popularity and exclusively rely on the local likelihood P(q∣p,dcurr)P(q p,d_curr), necessitating the trie-guided constrained decoding approach proposed in this work. 4. DocQAC Dataset We utilize the ORCAS (Craswell et al., 2020) dataset which contains 1.4M documents and 10M distinct real-world user queries. We illustrate our dataset construction process in Fig. 1 and describe it in this section. Obtaining Frequency Counts and Initial Preprocessing. We perform the following preprocessing steps: (1) We retain queries that are at least 3 characters long. (2) We remove duplicate query-document (QD) pairs. (3) We retain documents with more than 10 queries but fewer than 500 queries to ensure a balanced representation. (4) We choose only those query-document pairs where the document exists in the TREC dataset333https://msmarco.z22.web.core.windows.net/msmarcoranking/msmarco-docs.tsv.gz. Thus, we obtain document text content from the TREC dataset. Next, we create train/validation/test dataset splits while considering the temporal aspects of the dataset. To do this, we look up the (query, document) pairs from the ORCAS dataset against Bing logs from Jul-Aug 20224, and prepare the training splits from a 30 day window, a validation split from a 4-day window, and a test set from a 10-day period. This process also helps us obtain the number of times a document was clicked for a given query which in turn is helpful in ranking suggestions for QAC. Query Augmentation via Similar Queries. To augment the ORCAS dataset, for each unique clicked query Q, we start by collecting 100 most similar queries Q′Q from Bing query logs (Jul-Aug 2022444We use an older time point to match timeline of original queries in ORCAS.) using cosine similarity over DeBERTa-v3-base555https://huggingface.co/microsoft/deberta-v3-base embeddings. To ensure the quality and relevance of these similar queries for the DocQAC task, we applied a series of rigorous filtering steps. First, to create a publicly shareable dataset, we retained only those similar queries that appeared verbatim within the content of some document in the collection. Second, we remove any similar queries that were near-duplicates (Levenshtein distance ≤ 1) or if they were already part of clicked queries in ORCAS for the same document. Relevance Labeling. A critical component of our dataset is the relevance label for each query-document pair. We use GPT-4666https://cdn.openai.com/papers/gpt-4.pdf as a binary relevance classifier to evaluate whether each query-document pair is relevant or not, going beyond historical clicks. This helps in removing false positives due to user behavior patterns or popularity biases. Overall, this leads to significant enhancement to the dataset where 48.79% are the original clicked queries Q and the remaining are similar queries Q′Q . Click Popularity Estimation. As query and document click counts are not available for these similar queries (since they did not directly lead to clicks to the documents), we estimate them based on our original dataset as follows. For a similar query Q′Q , we identify its top-5 closest matches from the existing queries Q in our dataset (which have frequency counts), and calculate a weighted average of their historical click counts, where the weight is the cosine similarity between the similar query Q′Q and its top-5 most similar queries. A similar methodology was used to assign click counts to a similar query Q′Q for a document by using counts of top-5 closest clicked queries of that document. Test Dataset Creation. Within the test set, we create 4 distinct test splits based on the presence of test set queries and documents in the training dataset. Specifically, if both the query and the document are present in both the training and test sets, we call this subset the “seen query-seen document (S)” test set. Conversely, if neither the query nor the document appears in the training set, the corresponding subset is labeled as the “unseen query-unseen document (U)” test set. Additionally, we define two other splits: the “unseen query-seen document (US)” test set, where the query is absent from the training set but the document is present, and the “seen query-unseen document (SU)” test set, where the query is seen during training but the document is not. Each split in the test set contains 3,000 (query, document) pairs. Table 2 shows the statistics of various subsets of our dataset. For each (query, document) pair in the train set, a sample is created in the dataset by randomly choosing a split point within the query. We refer to the string to the left (right) of the split point in the query as the prefix (suffix or completion). Thus, each sample consists of a prefix and a document as input and the goal is to generate the suffix. Dataset Docs (Query, Doc) Pairs Prefixes Avg Query Len Train 22,453 316,813 Dynamic 17.1 Validation 7,266 31,682 Dynamic 16.8 Test-Seen Q Seen D 2,611 3,000 53,862 19.0 Test-Seen Q Unseen D 712 3,000 52,678 18.5 Test-UnSeen Q Seen D 2,485 3,000 54,145 20.5 Test-Unseen Q UnSeen D 1,068 3,000 52,488 17.1 Table 2. Dataset Statistics for different Dataset Splits. Length is in characters. “Dynamic” implies that query in the (query, doc) pair is split into prefix and suffix by choosing a random split point in every batch. 5. Methods for DocQAC We follow various modeling strategies for DocQAC that gives a complete view at the spectrum of trade-off between accuracy and latency. We investigate several ML and DL approaches for the task, including trie-based methods, QueryBlazer, and neural language models. Figure 2. Input Representations and DocQAC Methods 5.1. DocQAC Tries To improve the coverage of main trie, we design an alternative method that utilizes a suffix-trie to handle prefixes with no matches in the main trie of the training queries. Specifically, we experiment with three different tries. • Global Query Trie: All the queries of all the training documents are indexed into a single global trie. Given a test prefix and a document, the completions are selected using MPC from this global trie. • Document Content (or DocC) Tries: We build a DocC trie for each document by utilizing the ngrams of the document text. • Document Query (or DocQ) Tries: We build a DocQ trie for each document using the document-specific subset of historical queries. Among our 4 test sets, DocQ tries cannot be made for test sets with unseen documents. 5.2. Neural Language Models We also experiment with popular Transformer-based models for generating DocQAC suggestions. Specifically, we use the BART-base (Lewis et al., 2019) and T5-small (Roberts et al., 2019) encoder-decoder models. Among Large Language models, we experiment with 2 models : Phi-3.5 (Abdin et al., 2024) and LLaMA-3.2 (Dubey et al., 2024) by LoRA-finetuning them on our training datasets. Particularly, we use google-t5/t5-small, facebook/bart-base, meta-llama/Llama-3.2-3B-Instruct and microsoft/phi-3.5-mini-instruct checkpoints. Refer Appendix B for hyperparameters. The prefix and the completion constitute the source and target sequences, respectively, for these models. While training both the models, each training query is split stochastically into prefix and suffix. During inference, we use beam search to generate a ranked list of completions. 6. Trie-Guided Decoding Our analysis of performance of various methods reveals the following trade-off: trie-based methods excel at recall but fail at generalization, while generative language models excel at generalization but often lack relevance and precision. In “seen query, seen document (S)” scenarios, traditional trie-based approaches perform exceptionally well, as the task is primarily one of recall from a known set of queries. However, their rigidity becomes a critical failure point in “unseen query, seen document (US)” cases, where they are fundamentally unable to generate novel queries that are not present in their pre-compiled structure. Conversely, LMs demonstrate strong performance on unseen query test sets by leveraging their generative capabilities to formulate novel, contextually relevant queries. However, their limitation is a lack of reliable grounding. In “seen query, unseen document (SU)” scenarios, an LM may fail to suggest a known, popular query, instead generating a fluent but less effective alternative. To address this, we propose an adaptive trie-guided mechanism that biases the model’s generation toward trie-conforming completions while retaining flexibility for contextual adaptation. At each decoding step, we compute a bias term that is subtracted from the logits of tokens which do not match with the completions in the trie. This bias is annealed over time according to the length of the prefix and the diversity of the beam index, controlled by 3 hyperparameters: Initial bias, α and β. α controls decay with respect to prefix length. A higher α reduces the trie’s influence as prefix length increases. β controls decay with respect to beam depth. annealed_bias=initial_bias⋅e−α⋅length⋅e−β⋅beam_depthannealed\_bias=initial\_bias· e^-α·length· e^-β·beam\_depth This encourages higher-ranked beams to follow the trie more strictly while allowing diversity in lower-ranked beams. Further, we also introduce an initial bias, which is a large initial penalty to strongly prioritize trie-conforming tokens at early decoding steps. Figure 3. Illustration of Trie-Guided LLM vs Unguided LLM for a sample user prefix in DocQAC setting. Figure 3 showcases the difference between a Trie Guided LLM vs an unguided LLM with an example. Our trie constrained system can validates if a query exists in a trie and updates its decoding process while inferencing, thereby helping the user in getting to the actual completion faster. The formal pseudocode for our constrained decoding strategy is presented in Algorithm 1. Input: Language model ℳM, prefix p, trie rT_r, beam size K, initial bias b0b_0, decay parameters α,βα,β, maximum decoding steps T Output: Top-K query completions Initialize beam set ℬ0←pB_0←\p\ for t=1t=1 to T do Initialize candidate set ←∅C← for each beam bi∈ℬt−1b_i _t-1 do Compute logits t←ℳ(bi)z_t (b_i) Retrieve valid next tokens i←r.ValidNextTokens(bi)V_i _r. ValidNextTokens(b_i) Compute annealed bias δi=b0⋅e−α⋅|bi|⋅e−β⋅rank(bi) _i=b_0· e^-α·|b_i|· e^-β·rank(b_i) for each token v in vocabulary do if v∉iv _i then t[v]←t[v]−δiz_t[v] _t[v]- _i end if end for t←Softmax(t)p_t← Softmax(z_t) Expand beam bib_i using top tokens from tp_t Add expanded beams to C end for Prune C to top-K beams to form ℬtB_t end for Return ℬTB_T Algorithm 1 Soft Trie-Guided Decoding Tokenization Mismatch Problem. A core challenge in applying trie-based guidance to language models for tasks like query suggestion is the mismatch between the granularity of user inputs, which is at character level, while the language model decodes at a subword level. Note that tries are built at a subword level to support such guidance. We build a serialized BytesTrie for fast lookup during decoding. Given a prefix of a seen query, we need to ensure that its tokenization should match with a path in the trie. The last few characters of a partial token should also match with a node in the trie. For example, for the query “machine learning”, it is important to have “machine lea” also in the trie although tokenization of the original query just leads to two tokens “machine” and “learning”. Hence, for each query q of the training dataset D, we generate all possible character-level prefix-suffix splits for all the queries, tokenize prefix and suffix separately, and store the overall tokenized string in the trie. However, at test time, this could lead to multiple redundant prefix path matches in the trie for super-strings. For example, consider a new query “machine learning goals” and prefix is “machine learning”. This would match several paths in the trie including “machine lea rning”, “machine learn ing” etc. To avoid a match with multiple paths in the trie, at trie creation time, we mark the transition from prefix to suffix by inserting a unique separator token (e.g., [SEP_SPLIT]) between the last prefix and first suffix token IDs. At test time, we match the path corresponding to prefix+[SEP_SPLIT] against the trie. 7. Utilizing Document Context for DocQAC We evaluate our models discussed in Section 5, using different approaches to incorporate document context. Specifically, we experiment with short input representations, longer document representations and retrieval augmented generation based approaches. For trie-based methods and QueryBlazer, we use the document content to rerank top 100 suggestions using cosine similarity based on sentence-BERT (msmarco-distilbert-base-v4) embeddings. 7.1. Short Input To quantify the improvements obtained using the document context, we experiment with a Prefix Only (P) setting and Title + URL + Prefix (P+TU) setting - with document title and URL as input context. 7.2. Longer Document Representations We experiment with three different longer document representations: document text, keyphrases (KPs) and summaries. • Title + URL + Document + Prefix (P+TUD): We pass trimmed document content as input. Given our model’s maximum context length of 512 tokens, we allocate a maximum of 32 tokens each for the title and URL and 352 tokens for document context and rest for the prefix and system prompt. • Title + URL + KPs + Prefix (P+TUK): We use YAKE (Campos et al., 2020) to extract keyphrases with a maximum n-gram length of three, and we limit the number of extracted phrases to fifty. • Title + URL + Summary + Prefix (P+TUS): For this, we utilize ChatGPT 3.5 Turbo777https://chat.openai.com/chat with 16,134 context window and generate offline summaries of up to 300 words and pass as representative document context 7.3. Retrieval Augmented Generation (RAG) • RAG using current document: In this setting, for a given query prefix, we utilize only the current document to extract relevant chunks. The relevant chunks are retrieved and ranked using sparse or dense similarity metrics as follows. – Sparse Retrieval (Sparse RAG). We retrieve top k (=20) sentences from the documents with highest BM25 (Robertson et al., 2009) similarity between the prefix and sentences. – Dense Retrieval (Dense RAG). We split each document into fixed-size (200 characters) chunks with some overlap (30 characters) between two neighboring chunks. We index chunks using all-mpnet-base-v2 (Reimers, 2019) embeddings and FAISS (Douze et al., 2024). Next, we use the vector similarity between the full prefix and chunks to extract extract top k (=20) chunks. • RAG using related documents (Rel+Dense RAG): Given the current document, we first obtain top 10 similar documents from the training set based on top similarity scores using msmarco-distilbert-base-v4 document embeddings and FAISS. msmarco-distilbert-base-v4 has been trained on the MS MARCO dataset, the same dataset from which our documents are derived. Set Model Input MRR nDCGα BLEUrr SBMRR PPN PRN TES S DocQ tries P 0.738 0.277 0.477 0.803 0.820 0.824 0.889 S DocQ tries P + TUS 0.688 0.274 0.472 0.778 0.814 0.826 0.889 S DocQ tries Sparse RAG 0.688 0.274 0.471 0.777 0.813 0.826 0.889 S DocQ tries P + TUD 0.686 0.273 0.471 0.776 0.813 0.826 0.889 S DocQ tries Dense RAG 0.686 0.273 0.471 0.776 0.813 0.826 0.889 S DocQ tries Rel + Dense RAG 0.686 0.273 0.471 0.775 0.813 0.826 0.889 S DocQ tries P + TUK 0.680 0.273 0.470 0.770 0.812 0.826 0.889 S DocQ-Guided BART P + TUK 0.720 0.080 0.349 0.793 0.692 0.790 0.896 SU Global-Guided BART P + TUK 0.711 0.078 0.296 0.778 0.664 0.730 0.880 SU LLaMA-3.2 P + TUS 0.462 0.088 0.277 0.668 0.740 0.691 0.813 SU Global-Guided T5 Sparse RAG 0.706 0.076 0.299 0.779 0.674 0.737 0.882 SU Global-Tries P + TUS 0.525 0.156 0.309 0.595 0.664 0.665 0.625 US Phi-3.5 P + TU 0.401 0.052 0.282 0.557 0.710 0.670 0.756 US LLaMA-3.2 P + TUD 0.381 0.077 0.283 0.548 0.724 0.658 0.730 US Phi-3.5 P + TUS 0.392 0.052 0.280 0.554 0.714 0.667 0.760 US LLaMA-3.2 P + TU 0.400 0.070 0.285 0.562 0.711 0.668 0.728 U Phi-3.5 P + TU 0.461 0.059 0.279 0.628 0.729 0.693 0.809 U LLaMA-3.2 P + TUS 0.442 0.085 0.280 0.615 0.743 0.680 0.792 U Phi-3.5 Sparse RAG 0.456 0.061 0.283 0.629 0.730 0.695 0.809 U Phi-3.5 P + TUS 0.452 0.060 0.278 0.625 0.736 0.693 0.821 U LLaMA-3.2 Dense RAG 0.452 0.084 0.285 0.624 0.731 0.686 0.785 U LLaMA-3.2 P + TUK 0.458 0.080 0.283 0.629 0.729 0.688 0.789 Table 3. Model and input combinations that result in at least one best metric value for any of the 4 test sets. Set Model Input MRR nDCGα BLEUrr SBMRR PPN PRN TES S BART P + TUK 0.486 0.059 0.286 0.649 0.672 0.707 0.750 SU BART P + TUK 0.440 0.054 0.259 0.615 0.663 0.703 0.697 SU T5 Sparse RAG 0.425 0.051 0.260 0.617 0.677 0.710 0.685 S DocQ-Guided BART P + TUK 0.720 0.080 0.349 0.793 0.692 0.790 0.896 SU Global-Guided BART P + TUK 0.711 0.078 0.296 0.778 0.664 0.730 0.880 SU Global-Guided T5 Sparse RAG 0.706 0.076 0.299 0.779 0.674 0.737 0.882 Table 4. Comparison of unguided vs. Trie-guided decoding (Ours). Dashed line separates the two groups. Set Model Input MRR nDCGα BLEUrr SBMRR PPN PRN TES S Phi-3.5 P + TUK 0.450 0.058 0.293 0.643 0.724 0.696 0.829 S LLaMA-3.2 P + TUK 0.446 0.079 0.296 0.645 0.724 0.689 0.791 SU Phi-3.5 P + TUK 0.476 0.061 0.277 0.676 0.724 0.706 0.842 SU LLaMA-3.2 P + TUK 0.477 0.083 0.279 0.676 0.725 0.699 0.808 SU Phi-3.5 Sparse RAG 0.467 0.085 0.278 0.667 0.729 0.697 0.808 SU LLaMA-3.2 Sparse RAG 0.473 0.063 0.279 0.670 0.730 0.706 0.833 S DocQ-Guided BART P + TUK 0.720 0.080 0.349 0.793 0.692 0.790 0.896 SU Global-Guided BART P + TUK 0.711 0.078 0.296 0.778 0.664 0.730 0.880 SU Global-Guided T5 Sparse RAG 0.706 0.076 0.299 0.779 0.674 0.737 0.882 Table 5. Comparison of large models (Phi-3.5, LLaMA-3.2) with our Trie-Guided models (T5 and BART). Dashed line separates the two groups. Input MRR α BLEURR SBMRR PPN PRN TES MRR α BLEURR SBMRR PPN PRN TES S, DocQ tries US, LLaMA-3.2 P 0.738 0.277 0.477 0.803 0.820 0.824 0.889 0.245 0.061 0.229 0.325 0.669 0.572 0.499 P+TU 0.687 0.274 0.470 0.776 0.815 0.825 0.889 0.400 0.070 0.285 0.562 0.711 0.668 0.728 P+TUD 0.686 0.273 0.471 0.776 0.813 0.826 0.889 0.388 0.072 0.283 0.551 0.713 0.663 0.724 P+TUK 0.680 0.273 0.470 0.770 0.812 0.826 0.889 0.387 0.071 0.283 0.552 0.707 0.664 0.714 P+TUS 0.688 0.274 0.472 0.778 0.814 0.826 0.889 0.381 0.077 0.283 0.548 0.724 0.658 0.730 Sparse RAG 0.688 0.274 0.471 0.777 0.813 0.826 0.889 0.388 0.074 0.284 0.550 0.713 0.662 0.716 Dense RAG 0.686 0.273 0.471 0.776 0.813 0.824 0.889 0.384 0.075 0.285 0.546 0.711 0.660 0.714 Rel+Dense RAG 0.686 0.273 0.471 0.775 0.813 0.826 0.889 0.370 0.067 0.281 0.543 0.696 0.659 0.697 SU, Global-Guided T5 U, LLaMA-3.2 P 0.384 0.042 0.221 0.463 0.593 0.636 0.552 0.241 0.060 0.210 0.318 0.665 0.568 0.487 P+TU 0.538 0.059 0.267 0.675 0.662 0.714 0.771 0.460 0.078 0.282 0.626 0.730 0.688 0.789 P+TUD 0.552 0.060 0.270 0.690 0.662 0.718 0.788 0.449 0.080 0.281 0.619 0.734 0.685 0.792 P+TUK 0.549 0.060 0.268 0.686 0.664 0.715 0.787 0.458 0.080 0.283 0.629 0.729 0.688 0.789 P+TUS 0.528 0.058 0.264 0.672 0.669 0.711 0.805 0.442 0.085 0.280 0.615 0.743 0.680 0.792 Sparse RAG 0.708 0.076 0.299 0.779 0.674 0.737 0.882 0.453 0.082 0.282 0.624 0.732 0.686 0.792 Dense RAG 0.554 0.061 0.270 0.695 0.667 0.718 0.807 0.452 0.084 0.285 0.624 0.731 0.686 0.785 Rel+Dense RAG 0.553 0.060 0.268 0.688 0.667 0.717 0.798 0.446 0.076 0.280 0.617 0.716 0.685 0.769 Table 6. Results with different input representations, for the best performing model for each of the 4 test sets. 8. Evaluation Metrics We categorize our metrics for DocQAC into 2 categories and evaluate top 10 suggestions for each prefix on these metrics. 8.1. Primary Metrics We prioritize the evaluation metrics that directly quantify the success of the system in meeting the user’s core objective: finding the correct document content with minimal physical effort. Typing Effort Saved (TES): In DocQAC scenarios (e.g., technical manuals, legal briefs, medical records), users often search for long, complex, or hard-to-spell domain-specific terms. The TES metric, inspired by (Trajanovski et al., 2021), is computed as TES=1−No. of typed charactersQuery LengthTES=1- No. of typed charactersQuery Length. Unlike ranking metrics which evaluate a static list, TES simulates the dynamic, end-to-end user interaction (typing → looking → selecting). It answers the most critical practical question: “Did this system actually make the query creation faster for users?” In our DocQAC settings, saving keystrokes is the ultimate goal. Mean Reciprocal Rank (MRR): As DocQAC is a navigation task, where the goal is to locate a specific string instantly, the rank of the first correct answer is paramount. In auto-completion, users rarely scan beyond the top 1 or 2 results. MRR strictly penalizes any system that buries the correct answer lower in the list. 8.2. Secondary Metrics These metrics are valuable for understanding why a model succeeds or fails, and for diagnosing specific error types (e.g., hallucination vs. drift) and can be used as a set of secondary metrics. Semantic Match (SBMRR): SBMRR gives credit for understanding the user’s intent, even if the exact string matching failed. This helps researchers understand if a model is “smart but imprecise” (high SBMRR, low MRR). Instead of lexical match, we find a semantic match between the reference query and its auto-completions. We use a transformer based model, Sentence-BERT (Reimers, 2019) (all-MiniLM-L6-v2) to compute both the query and suggestions’ representations. We consider a match if the semantic similarity is ≥ 0.9. Partial Match Metrics (PPN and PRN): To diagnose failure modes beyond binary success, we employ Partial Precision (PPN) and Partial Recall (PRN) NDCG. PPN penalizes “hallucinated suffixes” (e.g., suggesting “Data Lake” instead of “Data Base”) by measuring how much of the suggestion is valid. Conversely, PRN identifies “truncation errors” (e.g., stopping at “Machine” instead of “Machine Learning”) by measuring how much of the target phrase was captured, ensuring models balance precision with completeness. Diversity and N-gram Overlap (α-NDCG, BLEURR): Clarke et al. (Clarke et al., 2008) defined the α metric for evaluating diversity. For example, in a coding document, the prefix “pro” might match “process”, “program”, and “protect”. A bad model might fill the top 10 slots with just variations of one word (“process”, “processing”, “processed”). α-NDCG penalizes this redundancy. BLEURR acts as a “soft” MRR by weighting n-gram overlap by reciprocal rank. In DocQAC, it rewards models for capturing document-specific vocabulary, which distinguishes useful “near-misses” from completely irrelevant hallucinations. 9. Results 9.1. Overall Results For each of the 4 test sets, Table 3 shows the model and input combinations that result in at least one best metric value. All results are reported on the 4 DocQAC test sets, each containing approximately 52,000-53,000 prefix-query pairs (see Table 2). We observe that for S set, DocQ tries perform the best for all metrics except TES. Our guided decoding approach, leveraging DocQ tries, achieves the highest TES with BART-Base, outperforming DocQ tries, LLaMA-3.2 (3B), and Phi-3.5 (3B). For SU set, the DocQ tries are not available. In this setting, our BART model with KPs as input and Global Tries for guided decoding, provides the best MRR. T5 model with Sparse RAG as input and Global Tries for guided decoding achieves the highest TES and PPN. For US and U, LLaMA-3.2 and Phi-3.5 lead to the best aggregated results. 9.1.1. Best Guided vs Unguided counterparts Table 4 compares the 3 best performing guided decoding models (from Table 3) with their unguided counterparts. Across all metrics, the guided methods consistently outperform the unguided ones. For example, for the BART model, applying guided decoding yields a 48.1% improvement in MRR (from 0.486 to 0.720) and a 19.4% increase in TES (from 0.750 to 0.896) for S test set. We observe similar gains for SeenQ-SeenD for both BART and T5 models. For T5 with Sparse RAG as input, applying guided decoding leads to 66% improvement in MRR alone (from 0.425 to 0.706) and 27.7% improvement in TES (from 0.685 to 0.882). 9.1.2. Best Guided Fine Tuned (BART and T5) vs Instruction Fine Tuned (Phi-3.5 and LLaMA) Table 5 shows comparison between our three best-performing guided decoding models with large models with the same input. Notably, both the T5- and BART-based models, when enhanced with trie decoding, consistently and substantially outperform the instruction fine-tuned LLaMA-3.2, while being approximately 52.5× smaller (T5) and 23× smaller (BART). Global DocC DocQ QB T5 T5 Guided BART BART Guided Phi LLaMA DocQ Global DocQ Global 3.5 3.2 P 8 10 11 0.2 66 73 118 63 73 190 494 905 P+TU 31 36 30 38 62 71 113 58 66 194 748 983 P+TUD 33 38 35 37 71 73 123 64 72 197 1246 1156 P+TUS 28 33 31 31 64 73 116 65 74 206 1331 1138 P+TUK 29 34 30 31 66 72 118 66 74 204 1153 1114 Sparse RAG 32 38 34 40 76 88 127 74 84 211 1162 1103 Dense RAG 71 84 63 77 99 107 150 97 111 239 1203 1105 Rel+Dense RAG 277 325 231 290 226 240 287 228 240 366 1344 1134 Table 7. Latency (in ms) per sample. T5, BART, Phi-3.5 and LLaMA-3.2 latencies are on GPU. Others on CPU. Figure 4. Performance Comparison across metrics for varying prefix lengths. Left to right: S DocQ tries (P), SU Global-Guided T5 (Sparse RAG), US LLaMA-3.2 (P+TU), U LLaMA-3.2 (P+TUK). Note TES cannot be computed for this experiment. <|im_start|>system [system](#instructions) # Task Given a document, the following query was retrieved by an information retrieval (IR) system as a potential query a user might type for searching for content within the document. Your task is to accurately classify whether the query is truly relevant to the document or not. # Input Document: ‘body’ Query: ‘Query’ id : ‘id’ docid : ‘docid’ # Output Provide your classification judgement of the query relevance for the document STRICTLY in the following JSON format: ‘query_relevance’: bool, ‘id’: string, ‘Query’: string, ‘docid’: string # The query is relevant (true) if: – The document contains specific information that directly answers the query. – The document provides background knowledge, explanations, or context that meaningfully relates to the query. – The document discusses entities, topics, or events explicitly mentioned in the query. – A user who issued this query would find the document useful or informative in addressing their information need. # The query is not relevant (false) if: – The document does not address the topic, entities, or intent expressed in the query. – The content is too vague, general, or off-topic to satisfy the query’s information needs. – There is no logical or semantic connection between the query and the document content. – The document might mention some terms from the query, but in a completely unrelated context. <|im_end|> Figure 5. The system prompt used for document-query relevance classification using GPT4 S SU US U Title . Francis I of France the third month of the year Walt Whitman URL http://w.keybr.com/ https://en.wikipedia.org/wiki/Francis_I_of_France http://w.timeanddate.com/calendar/months/ https://en.wikipedia.org/wiki/Walt_Whitman Query speed typing practice king francis of france the third month of the year poems of walt whitman Prefix spe king the thi poems o DocQ tries (P) speed test practice, speed and eliminates, speed stayed, speed, speed test, speed for each, speed for every, speed for, speed stayed at Trie cannot be created Trie returned no matches due to log sparsity Trie cannot be created Phi-3.5 (P+TUK) speed typing, speed of typing, speed in typing, speed to type, speed for typing, speed keybr, speeds of typing, speed keyboard, speed of keyboard typing, speed typ king francis, king francis i, king francis of france, king francis the first, king of france, king francis 1, king francis i, kings of france, king french, king francis 1st the thirteen months, the thirty days, the thirteenth month, the thirteen month, the this month, the thirteen, the third month, the thirty one days poems of walt whitman, poems of whitman, poems of walt, poems on walt whitman, poems of walter whitman, poems of walt whittman, poems on leaves of grass, poems of, poems of walt w, poems of walt watson LLaMA-3.2 (P+TUK) speed typing, speed type, speed of typing, speed typing test, speed typing practice, spell typing, spell typer, spell type, speed of type, spell keybr king francis, king francis i, kings of france, king frances, king francisco, king francois, king frances i, kings francis, kings francis i, kings of franc the third month, the thirteenth month, the this month, the this month is, the this months, the third month of, the thirteens, the thirtieth, the third poems of walt whitman, poems of whitman, poems of walt whitan, poems of walt whiman, poems of walter whitman, poems of walt whitmans, poems of whitman’s, poems of whitmans DocQ-Guided BART (P+TUK) speed typing practice, speed typing wpm, speed of your typing, speed of the keyboard, speed of a keyboard, speed of your keyboard, speed typing.com, speed of typing x, speed practice for keyboard, speed of a computer Trie cannot be created the third month of the year, the thir month september, the this month of the year, the thist month of the year, the things of the year, the thin months of the year, the this month, the third months of the year, the thir seasons of the year, the thingths of the year Trie cannot be created Global-Guided BART (P+TUK) speed of typing, speed typing, speed of a computer, speed typing practice, speed checks, speak and type, speed website, speed of audio, speed up your computer, speed type game kings of france, king francis of france, kings in france, king henry viii, king francis, king henry vii, king if england, kings, king of france timeline, kings uk the third person, the things of the year, the third month of the year, the thingths of the year, the third months of the year, the thing months of the year, the thir month september, the things in the year, the thirds of the year, the this month of the year poems of walt whitman, poems of walt whitman books, poems of walt walt breath, poems of walt walt Whitman, poems of walt walt, poems of walt rhodea, poems of walt rhodeo, poems of walt walt rock, poems of walt chattman, poems of walt walt cod BART (P+TUK) speed your typing, speed of typing, speed to type, speed of your typing, speed typing, speed writers, speed of the keyboard, speed of a keyboard, speed of your keyboard, speed your keyboard kings of france, king of france, king francis viii, king and queen of france, king francis i, king francis of france, king’s death of france, king’s history of france, king francis the great, kings of france list the third month of the year, the thir month september, the this month of the year, the thist month of the year, the things of the year, the thin months of the year, the this month, the third months of the year, the thir seasons of the year, the thingths of the year poems of walt whitman, poems of walt walt, poems of walt, poems of walt codman, poems of walt norfolk, poems of walt washington, poems of walt potman, poems of walt whitman books, poems of walt walt breath, poems of walt marshall Table 8. Sample predictions from our best models comparing guided and unguided models. 9.2. Ablation Studies 9.2.1. Analysis of input representations We present impact of each input representation in Table 6. For S set, the best models are with DocQ tries with various inputs followed by our guided decoding models BART and then T5 with various inputs. For SU set, our global trie-guided T5 model with Sparse RAG has the highest TES, and global trie-guided BART with keyphrases as input has the best MRR. Notably, these models outperform global tries by a large margin. For US set, LLaMA-3.2 and Phi-3.5 with title and URL perform the best in all metrics except PRN. For U set, LLaMA-3.2 and Phi-3.5, with either the title and URL, or both title and URL along with a document or summary as context, achieve the best results. Also, for both US and U set, we observe the next best models to be BART and T5; tries perform the worst. Thus, for unseen queries, leveraging neural LMs is recommended. 9.3. Other Analysis 9.3.1. Varying Prefix Length Analysis We assess performance of DocQAC models in these prefix length categories: 1-5, 6-10, 11-15, 16-20 and 20+ characters. Fig. 4 shows results for our best models across all the 4 test sets. We observe that for each set across all metrics, results improve as the prefix length increases. We believe this is because longer prefixes provide the best clues for the models to predict accurate suggestions. 9.3.2. Qualitative Analysis Table 8 shows predictions for 4 samples (one from each test set) across all models, for best guided models and their unguided counterparts. We observe that DocQ tries cannot predict anything for 3 of these samples due to query log sparsity for those documents. For the S sample, we observe that all guided models are able to correctly show query suggestion matching the user input query while their unguided counterparts are unable to do so for the prefix “spe” for the given query “speed typing practice”. In the SU scenario, the guided decoding models of BART are able to complete the prefix “king” by leveraging Global Tries. In the U case, we observe that providing additional context like Sparse RAG to T5 and keyphrases to BART helped with getting the correct suggestion. 9.3.3. Latency Analysis Table 7 reports latency across various methods computed using batch size of 1. Latency for neural LMs is on GPUs while for other models, we report latency on CPUs. Clearly, neural models have high latency compared to tries or QB. Our guided decoding models are highly practical for real-world deployment too. They incur only a modest 12 ms latency increase for T5 Guided DocQ + Sparse RAG (from 76 ms to 88 ms) for unguided vs guided scenarios, while remaining ∼ 15x faster than both LLaMA-3.2 3B and Phi-3.5 3B. Similarly, DocQ-Guided BART + (P+TUK) model incurs a latency of increase of just 8 ms (from 66 to 74 ms) while remaining 15 times faster than LLaMA-3.2 3B and Phi-3.5 3B. Lastly, Global-Guided BART + (P+TUK) model adds a latency of 138 ms on top of unguided version, but still being 5.5 times faster than LLaMA3 and Phi3. Although these models have not been optimized using any of the popular optimization methods like FasterTransformers or TensorRT-LLM, their latencies are already low enough to be deployed in practical settings. These results demonstrate that developing specialized decoding algorithms is a highly effective and resource-efficient alternative to simply scaling up model size. 10. Conclusion In this paper, we propose a novel task of DocQAC for in-document query auto completions. We also release the newly created DocQAC benchmark dataset. We conduct extensive experiments by integrating various strategies, including RAG, using document summaries as context for LLMs, and combining these approaches with traditional methods such as tries. We establish strong baselines for these techniques and further evaluate larger language models like LLaMA and Phi-3. Building on this, we introduce a novel adaptive trie-guided decoding framework that enhances the performance of language models like T5 and BART by guiding their outputs rather than imposing hard constraints. Our results demonstrate that this approach significantly outperforms the established baselines and even surpasses large instruction-tuned models. Overall, our findings showcase the potential of adaptive trie-guided decoding as a practical and efficient method for controlled language generation, and encourage further research in context-aware and nuanced text generation. Appendix A Query Document Relevance Classifier We utilize GPT4 with the system prompt as shown in Fig. 5 to classify whether the query is relevant for a document or not. Appendix B Hyper-parameter Settings Compute: Experiments were performed on a machine with 8 NVIDIA V100 GPUs for training neural models. For CPU-based experiments, we used an AMD Ryzen 9 7900X3D 12-Core Processor (4.40 GHz) with 64GB RAM. T5 and BART: For T5, we use batch size=24,learning rate=1e-4,epochs=30,maximum input length=512, AdamW. For inference, we set beam size=25,max output length=48. For BART,we use 8 for document content (RAG, Summary, and KPs) and 18 for other experiments. Phi-3.5 and Llama-3.2: Both models are fine-tuned using LoRA (Hu et al., 2021) for all linear layers (lora_r=16, lora_alpha=32,lora_dropout=0.05), with AdamW,learning rate=5e-5,fp16 precision, max len=512,batch size=4 and epochs=5. Inference uses beam search with beam size=10, length penalty=1.0, and a 40-token output limit. Trie-Guided Decoding: We perform extensive hyperparameter tuning across α∈0.05,0.1,0.2,0.5α∈\0.05,0.1,0.2,0.5\, β∈0.05,0.1,0.2,0.5β∈\0.05,0.1,0.2,0.5\, bias∈20,30,40bias∈\20,30,40\. For DocQ tries based guided decoding, we use (P+Sparse RAG), while for global-tries based guided decoding, we use (P+TUD) and run for S and SU settings as they are the best performing models. With global tries, the best performance on both S and SU is obtained with α=0.1α=0.1, β=0.05β=0.05, and bias=40bias=40. In contrast, for DocQ trie-guided decoding, the optimal configuration is α=0.1α=0.1, β=0.2β=0.2, and bias=40bias=40 on S, while α=0.5α=0.5, β=0.2β=0.2, and bias=20bias=20 performs best on SU. References M. Abdin, J. Aneja, H. Awadalla, A. Awadallah, A. A. Awan, N. Bach, A. Bahree, A. Bakhtiari, J. Bao, H. Behl, et al. (2024) Phi-3 technical report: a highly capable language model locally on your phone. arXiv preprint arXiv:2404.14219. Cited by: §5.2. Z. Bar-Yossef and N. Kraus (2011) Context-sensitive query auto-completion. In W, p. 107–116. Cited by: §1, §2.1.1. M. Bevilacqua, G. Ottaviano, P. Lewis, S. W. Yih, S. Riedel, and F. Petroni (2022) Autoregressive search engines: generating substrings as document identifiers. In Advances in Neural Information Processing Systems, Vol. 35, p. 31668–31683. Cited by: §2.3. R. Campos, V. Mangaravite, A. Pasquali, A. Jorge, C. Nunes, and A. Jatowt (2020) YAKE! keyword extraction from single documents using multiple local features. Information Sciences 509, p. 257–289. Cited by: 2nd item. B. J. Chan, J. Cheng, M. X. Huang, C. Chen, and H. Huang (2025) Efficient beam search for large language models using trie-based decoding. arXiv preprint arXiv:2502.00085. Cited by: §2.3. M. X. Chen, B. N. Lee, G. Bansal, Y. Cao, S. Zhang, J. Lu, J. Tsay, Y. Wang, A. M. Dai, Z. Chen, et al. (2019) Gmail smart compose: real-time assisted writing. In 25th KDD, p. 2287–2295. Cited by: §2.2. C. L. Clarke, M. Kolla, G. V. Cormack, O. Vechtomova, A. Ashkan, S. Büttcher, and I. MacKinnon (2008) Novelty and diversity in information retrieval evaluation. In 31st SIGIR, p. 659–666. Cited by: §8.2. N. Craswell, D. Campos, B. Mitra, E. Yilmaz, and B. Billerbeck (2020) ORCAS: 18 million clicked query-document pairs for analyzing search. arXiv preprint arXiv:2006.05324. Cited by: §4. N. De Cao, G. Izacard, S. Riedel, and F. Petroni (2021) Autoregressive entity retrieval. In ICLR, Note: Spotlight External Links: Link Cited by: §2.3. M. Dehghani, S. Rothe, E. Alfonseca, and P. Fleury (2017) Learning to attend, copy, and generate for session-based query suggestion. In 2017 CIKM, p. 1747–1756. Cited by: §2.1.2. M. Douze, A. Guzhva, C. Deng, J. Johnson, G. Szilvasy, P. Mazaré, M. Lomeli, L. Hosseini, and H. Jégou (2024) The faiss library. arXiv preprint arXiv:2401.08281. Cited by: 2nd item. H. Duan and B. Hsu (2011) Online spelling correction for query completion. In W, p. 117–126. Cited by: §2.1.2. A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Yang, A. Fan, et al. (2024) The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §5.2. N. Fiorini and Z. Lu (2018) Personalized neural language models for real-world query auto completion. In NAACL-HLT, p. 208–215. Cited by: §2.1.2. S. Geng, M. Josifoski, M. Peyrard, and R. West (2023) Grammar-constrained decoding for structured nlp tasks without finetuning. arXiv preprint arXiv:2305.13971. Cited by: §2.3. C. Hokamp and Q. Liu (2017) Lexically constrained decoding for sequence generation using grid beam search. arXiv preprint arXiv:1704.07138. Cited by: §2.3. B. Hsu and G. Ottaviano (2013) Space-efficient data structures for top-k completion. In 22nd W, p. 583–594. Cited by: §1. E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen (2021) Lora: low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685. Cited by: Appendix B. J. Jiang and W. Wang (2018) RIN: reformulation inference network for context-aware query suggestion. In 27th ACM International Conference on Information and Knowledge Management, p. 197–206. Cited by: §1. Y. M. Kang, W. Liu, and Y. Zhou (2021) QueryBlazer: efficient query autocompletion framework. In WSDM, p. 1020–1028. Cited by: §2.1.2. D. Lee, Z. Hu, and R. K. Lee (2021) Improving text auto-completion with next phrase prediction. In Findings of the Association for Computational Linguistics: EMNLP 2021, p. 4434–4438. Cited by: §1. M. Lewis, Y. Liu, N. Goyal, M. Ghazvininejad, A. Mohamed, O. Levy, V. Stoyanov, and L. Zettlemoyer (2019) BART: denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. arXiv preprint arXiv:1910.13461. Cited by: §5.2. A. Maheswaran, K. K. Maurya, M. Gupta, and M. S. Desarkar (2024a) DAC: quantized optimal transport reward-based reinforcement learning approach to detoxify query auto-completion. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 608–618. Cited by: §2.1.2. A. Maheswaran, K. K. Maurya, M. Gupta, and M. S. Desarkar (2024b) DQAC: detoxifying query auto-completion with adapters. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, p. 108–120. Cited by: §2.1.2. A. Mandal, S. Mishra, B. Santra, T. Abhishek, P. Goyal, and M. Gupta (2026) Chat-ghosting: methods for auto-completion in dialog systems. In Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), p. 4502–4528. Cited by: §2.1.2. K. K. Maurya, M. S. Desarkar, M. Gupta, and P. Agrawal (2023) TRIE-nlg: trie context augmentation to improve personalized query auto-completion for short and unseen prefixes. DMKD 37 (6), p. 2306–2329. Cited by: §2.1.2. A. Mustar, S. Lamprier, and B. Piwowarski (2020) Using bert and bart for query suggestion. In Joint Conference of the Information Retrieval Communities in Europe, Vol. 2621. Cited by: §1. H. Oh, H. Shin, M. Ko, H. Lee, and M. Seo (2024) KTRL+ f: knowledge-augmented in-document search. In NAACL-HLT, p. 2416–2436. Cited by: §2.2. M. Post and D. Vilar (2018) Fast lexically constrained decoding with dynamic beam allocation for neural machine translation. arXiv preprint arXiv:1804.06609. Cited by: §2.3. N. Reimers (2019) Sentence-bert: sentence embeddings using siamese bert-networks. arXiv preprint arXiv:1908.10084. Cited by: 2nd item, §8.2. A. Roberts, C. Raffel, K. Lee, M. Matena, N. Shazeer, P. J. Liu, S. Narang, W. Li, and Y. Zhou (2019) Exploring the limits of transfer learning with a unified text-to-text transformer. Google, Tech. Rep.. Cited by: §5.2. S. Robertson, H. Zaragoza, et al. (2009) The probabilistic relevance framework: bm25 and beyond. Foundations and Trends® in Information Retrieval 3 (4), p. 333–389. Cited by: 1st item. J. Song, J. Xiao, F. Wu, H. Wu, T. Zhang, Z. M. Zhang, and W. Zhu (2017) Hierarchical contextual attention recurrent neural network for map query suggestion. TKDE 29 (9), p. 1888–1901. Cited by: §2.1.2. S. Trajanovski, C. Atalla, K. Kim, V. Agarwal, M. Shokouhi, and C. Quirk (2021) When does text prediction benefit from additional context? an exploration of contextual signals for chat and email messages. In NAACL-HLT, p. 1–9. Cited by: §2.2, §8.1. P. Wang, J. Z. Kolter, V. Mohan, and I. S. Dhillon (2018) Realtime query completion via deep language models. Cited by: §2.1.2. S. Wang, W. Guo, H. Gao, and B. Long (2020) Efficient neural query auto completion. In 29th ACM International Conference on Information & Knowledge Management, p. 2797–2804. Cited by: §1. H. Yenala, M. Chinnakotla, and J. Goyal (2017) Convolutional bi-directional lstm for detecting inappropriate query suggestions in web search. In PAKDD, p. 3–16. Cited by: §2.1.2. D. Yin, J. Tan, Z. Zhang, H. Deng, S. Huang, and J. Chen (2020) Learning to generate personalized query auto-completions via a multi-view multi-task attentive approach. In KDD, p. 2998–3007. Cited by: §2.1.2.