Query Understanding & Expansion

The Big Picture

A user types "apple" into a search engine. Does she want information about the fruit, the technology company, or Apple Music? Without query understanding, retrieval systems cannot distinguish intent, leading to poor results.

Query understanding is the bridge between raw input and structured intent. It answers: What does this user actually need?

The Query Understanding Pipeline

Raw query flows through five stages:

1. Normalization & Cleaning: lowercase, remove extra whitespace, expand contractions
2. Intent Classification: Is this informational, navigational, transactional, or comparative?
3. Entity Recognition: Extract entities (product, brand, location, date)
4. Query Expansion: Add synonyms, related terms, and reformulations
5. Retrieval & Ranking: Use the enriched query to fetch and score documents

Three Core Problems

Query Taxonomy

Queries are not uniform. Different types require different retrieval strategies, ranking signals, and presentation formats.

Core Query Types

Informational Queries: User seeks knowledge or explanation. Examples: "how does gravity work", "Python list comprehension", "best practices for API design".

Navigational Queries: User seeks a specific page or resource. Examples: "GitHub login page", "TensorFlow documentation", "Stack Overflow Python tag".

Transactional Queries: User intends to complete a transaction. Examples: "buy iPhone 15", "book flight to Paris", "download Ubuntu ISO".

Comparative Queries: User compares two or more entities. Examples: "Python vs JavaScript", "Vue vs React", "DuckDB vs SQLite".

Local Queries: User seeks location-based results. Examples: "coffee near me", "best restaurants in Brooklyn", "car rental downtown".

Distribution: Power Law of Query Frequency

Queries follow a power-law distribution. A small number of "head" queries (1–2% of all queries) account for ~40% of traffic. A "long tail" of unpopular queries (the remaining 98%) account for the rest.

• Head Queries: High volume, low intent ambiguity, well-understood intent ("weather", "gmail login"). Simple heuristics work.
• Tail Queries: Low volume, high ambiguity, often specific or niche. Require deeper understanding. Benefit from entity extraction and expansion.

Spell Correction & Normalization

Users make mistakes. Typos, phonetic misspellings, autocorrect errors, OCR noise—all corrupt query meaning. Spell correction recovers intent before retrieval.

Sources of Query Noise

• Typos: "recieve" → "receive", "definately" → "definitely"
• Phonetic errors: "lite" → "light", "thru" → "through"
• OCR errors: "l" (letter L) → "1" (digit), "0" (digit) → "O" (letter)
• Autocorrect: "teh" → "the", "pubic" → "public" (often wrong)
• Keyboard proximity: "hoem" → "home", "wuick" → "quick"

Edit Distance (Levenshtein Distance)

Levenshtein distance measures the minimum number of single-character edits (insert, delete, replace) to transform one string into another.

Example: "recieve" → "receive"

• recieve → recive (delete 'e')
• recive → recieve (insert 'e') — 1 edit total

Norvig Spell Corrector

Classic probabilistic approach: Find the correction that maximizes P(correction | error).

Bayes rule: P(c|e) = P(e|c) × P(c) / P(e)

• P(c) = prior probability of candidate word (from corpus frequency)
• P(e|c) = error probability given the correct word (Levenshtein distance, keyboard proximity)
• Candidate set: all words within edit distance 1 or 2 of the error

Phonetic Matching

Soundex: Convert words to codes based on pronunciation. "Smith" and "Smythe" → both map to "S530".

Metaphone: More sophisticated phonetic algorithm, handles English phonemes better than Soundex.

Query Normalization

Before any analysis, normalize:

• Lowercase all text
• Remove extra whitespace and punctuation
• Expand contractions ("don't" → "do not", "it's" → "it is")
• Normalize unicode (decompose accents, handle emojis)
• Remove stop words (optional, context-dependent)

Query Segmentation

Some queries need word boundary detection. "cheapflightsparis" should become "cheap flights paris".

Approach: Dynamic programming + language model. Score each potential segmentation by likelihood of word sequence.

Intent Classification

Knowing query intent shapes downstream processing. An informational query needs a comprehensive article; a transactional query needs product pages; a navigational query needs exact matching.

Rule-Based Intent Signals

Simple heuristics work for many cases:

ML-Based Intent Classification

For more nuanced intent, train a classifier. Input: query tokens. Output: intent class (informational, transactional, navigational, local, comparative).

Feature engineering:

• Bag-of-words or TF-IDF vectors
• Presence of intent keywords (buy, how, near, etc.)
• Query length and linguistic patterns
• User historical behavior (session context)
• Click logs (which results do users click for this query?)

Model: Logistic regression, SVM, or random forest. For deeper learning, BERT fine-tuning on labeled query-intent pairs.

BERT-Based Intent Classification

Pre-trained BERT captures contextual intent better than bag-of-words. Fine-tune on a labeled dataset:

• Input: [CLS] query tokens [SEP]
• Use [CLS] token's hidden state as query representation
• Add a classification head on top: MLP → softmax → intent label

Typical F1-score: 0.85–0.92 on benchmark datasets.

Multi-Label Intent

Queries can have multiple intents: "buy cheap flights from NYC to London" = transactional + local (NYC, London). Use sigmoid + binary cross-entropy loss instead of softmax.

Cross-reference: See bert_guide.html for detailed BERT architecture and fine-tuning.

Named Entity Recognition (NER)

Extract structured information: product names, brands, locations, dates, people, organizations. NER transforms unstructured query text into structured query filters.

Entity Types

• Product/Service: "iPhone 15", "MacBook Pro", "Ubuntu 24.04"
• Brand: "Apple", "Microsoft", "TensorFlow"
• Location: "NYC", "Paris", "Silicon Valley"
• Date/Time: "2024", "March", "next week"
• Person: "Steve Jobs", "Elon Musk"
• Organization: "Google", "MIT", "OpenAI"

BIO Tagging Scheme

Sequence labeling: Each token gets a tag.

• B-X: Beginning of entity type X
• I-X: Inside (continuation) of entity type X
• O: Outside any entity

Example: "Python 3.11 release notes"

Python    → B-PRODUCT
3.11      → I-PRODUCT
release   → O
notes     → O

BERT-Based NER

Fine-tune BERT for token classification. Each token's hidden state is classified into BIO tags.

Architecture:

• BERT encoder → hidden states for each token
• Classification head on each token: MLP → softmax over BIO tags
• Loss: cross-entropy on BIO label sequence
• F1-score on benchmark: 0.88–0.95

Entity Linking

Map extracted entities to knowledge graph IDs for structured search.

Example: "NYC" → Q60 (Wikidata ID for New York City). Then filter results by coordinates or administrative region.

Query NER Impact on Retrieval

"Python 3.11 release notes" → extract {product: "Python", version: "3.11"}. Then:

• Filter documents: must mention Python and version ≥ 3.11
• Boost documents with exact version match
• Demote outdated Python 2 docs

Cross-reference: See bert_guide.html for token classification and sequence tagging.

Query Expansion: Synonyms & Thesaurus

User types "car"; docs say "automobile". Without expansion, lexical matching (BM25) fails. Query expansion adds synonyms and related terms to bridge vocabulary gaps.

Vocabulary Gap Problem

Example: "GPU" vs "graphics processor" vs "CUDA device". A document might use any of these terms. Original query misses relevant docs.

Solution: Expand query with synonyms before retrieval, or reweight terms based on semantic similarity.

Rule-Based Synonym Lists

Curated dictionaries: "car" → ["automobile", "vehicle", "sedan", "sedan"].

Pros: Fast, precise, domain-specific. Cons: Manual effort, incomplete coverage, doesn't scale.

WordNet

Lexical database: words organized by meaning. Hierarchical synonyms, hypernyms, hyponyms.

Example: "dog" → synonyms: ["canine", "canis"], hypernyms: ["animal", "mammal"].

Usage: For each query term, fetch all synonyms, add to query with lower weight.

Distributional Semantics (Word2Vec, GloVe)

"Words are defined by their context." Words with similar contexts have similar meanings.

Word2Vec: Train a neural network to predict context words from a target word (Skip-gram) or vice versa (CBOW).

Similarity: Cosine distance in embedding space. "car" and "automobile" have high cosine similarity.

Query expansion: For each query term, find K nearest neighbors in embedding space. Add them to query.

import gensim
model = gensim.models.Word2Vec.load('word2vec_model')
query = "car rental"
expanded = []
for term in query.split():
    expanded.append(term)
    similar = model.most_similar(term, topn=3)
    expanded.extend([word for word, _ in similar])
# expanded = ["car", "automobile", "vehicle", "sedan",
#             "rental", "rent", "hire", "lease"]

Selective Expansion

Not all query terms should be expanded:

• Expand rare terms. "car" might be too common; "autonomous" is rarer, benefits from expansion.
• Skip proper nouns. "Steve Jobs" should not expand to "work person".
• Skip high-confidence terms. Terms already well-represented in index.

Expansion Weighting

Original terms get higher weight than expansions. Modified query:

Original: "car rental" → BM25 score S

Expanded: "car^2 rental^2 automobile rental^0.5 vehicle^0.5" → higher score for docs with exact terms, lower for synonyms.

Domain-Specific Synonyms

Medical domain: "heart attack" = "myocardial infarction" = "MI". Critical for medical search where synonyms are technical.

Travel domain: "flight" = "air ticket" = "booking".

Build custom thesauruses from domain corpora or expert knowledge.

Cross-reference: See dense_retrieval_guide.html for semantic similarity and embedding-based retrieval.

Pseudo-Relevance Feedback (PRF)

Key insight: Assume top-K initial results are relevant. Extract terms from them. Re-query with original + extracted terms. Improves recall on verbose or ambiguous queries.

Rocchio Algorithm

Classic vector-space PRF. Expand query toward relevant docs, away from irrelevant.

Formula: q_expanded = α × q_original + β × centroid(top_K_docs) - γ × centroid(bottom_M_non_relevant)

• α ≈ 1.0 (weight original query)
• β ≈ 0.75 (weight relevant centroid, positive feedback)
• γ ≈ 0.15 (weight non-relevant centroid, negative feedback, often omitted)

Example: Query "Python programming", top-3 results mention "Django", "Flask", "async/await". q_expanded pulls toward these high-frequency terms.

RM3 (Relevance Model 3)

Probabilistic alternative to Rocchio. Model P(w | R) where R = pseudo-relevant docs.

Uses KL-divergence to measure term importance in relevant set.

Advantage over Rocchio: Theoretically grounded, better term weighting.

PRF Risks: Topic Drift

Problem: If top-K initial results are wrong, PRF amplifies error. Query "apple" retrieves Apple Inc. docs → expansion adds "iPhone", "Tim Cook" → query drifts away from fruit.

Mitigation:

• Use only highest-confidence results for feedback (threshold)
• Cap feedback term contribution (limit β)
• Use cross-encoder to filter pseudo-relevant docs before extraction
• Log and monitor topic drift

Neural PRF with Cross-Encoder

Filter pseudo-relevant docs using a cross-encoder before term extraction:

1. Initial retrieval: BM25 or dense retriever
2. Re-rank top-K with cross-encoder: score(query, doc)
3. Keep only docs with score > threshold
4. Extract expansion terms from filtered set
5. Re-query

This reduces noise from incorrect initial results.

Neural Query Rewriting

Deep learning models reformulate queries to improve clarity, add missing context, or align with document language.

Seq2Seq Query Rewriting

Task: Given messy query, generate cleaner version.

Example:

• "flights paris cheap" → "cheap flights to Paris"
• "python how install" → "how to install Python"
• "best laptop gaming under 1000" → "best gaming laptop under $1000"

Architecture: Seq2seq encoder-decoder with attention. Encoder processes noisy query tokens; decoder generates rewritten tokens.

Training: Pairs of (original, rewritten) queries. Source: session logs (users often reformulate their own queries).

T5 / GPT-Based Rewriters

Leverage pre-trained language models. Fine-tune on query rewrite pairs.

T5 prompt: "Rewrite this query for clarity: flights paris cheap"

Output: "cheap flights to Paris"

Requires smaller fine-tuning dataset, often works better than training seq2seq from scratch.

Query2Query: Learning from Sessions

User often reformulates own query across a session: "python" → "python 3.11" → "python 3.11 release date".

Train rewriter on (previous_query, reformulated_query) pairs from session logs. Learn implicit user refinement patterns.

HyDE (Hypothetical Document Embeddings)

Insight: Better to compare query embeddings to document embeddings in a shared space. But queries and documents have different statistical properties.

Solution: LLM generates a hypothetical document matching the query, then embed and retrieve similar real docs.

Example:

query = "how to install Python 3.11"
# LLM generates hypothetical answer
hyp_doc = """
Python 3.11 is the latest stable release.
To install, visit python.org and download
the installer for your OS. Run the installer
and follow prompts. Verify with `python --version`.
"""
# Embed hypothesis and retrieve similar docs
hyp_embedding = embed(hyp_doc)
similar_docs = retrieve_by_embedding(hyp_embedding)

Query Decomposition

Complex queries: "best free Python IDE with debugging for beginners" is hard to match as-is.

Decomposition: Break into sub-queries:

• "best Python IDE"
• "free Python IDE"
• "Python IDE with debugging"
• "Python IDE for beginners"

Retrieve and aggregate results, re-rank by relevance to original query.

Cross-reference: See rag_patterns_guide.html for RAG and query-document alignment.

Contextual & Personalized Query Understanding

Query meaning depends on context: user history, session, location, time. Same query has different intent in different contexts.

Session Context

Example: Query sequence: "programming tutorial" → "Python" → "list comprehension".

Last query "Python" in isolation is ambiguous (fruit or language). But in session context, it's clearly the programming language.

Approach: Encode session history (previous 3–5 queries) as context. Use it to disambiguate current query.

Model: BERT-based context encoder. Input: [previous_queries] + [CLS] + [current_query]. Output: intent or expanded query.

User Personalization

History-based: User who frequently queries "Python ML" + "PyTorch" is likely interested in deep learning. Boost relevant results.

Search for "model": In ML user context → PyTorch models. In fashion user context → clothing models.

Location Context

Query: "weather"

Without location: Ambiguous. With location (from device GPS or IP geo): "weather in NYC" → show NYC forecast.

Implementation: Append location to query or filter results by geographic proximity.

Time Context

Query: "news"

Interpretation: Recent news. Boost results from today/yesterday. Demote old news.

Time-sensitive entities: "president" means current president, not historical.

Conversational Search & Co-Reference Resolution

Example dialogue:

User: "Which countries are in Southeast Asia?"
System: [retrieves list]
User: "Tell me about their economies."
        ↑ "their" = Southeast Asian countries

Challenge: Resolve "their", "it", "that one" to previous entities.

Approach: Parse coreference, replace pronouns with entities from context.

Query Difficulty & Failure Analysis

Not all queries are equally easy. Identify hard queries, understand failure modes, improve incrementally.

Query Difficulty Signals

• High CTR: Users click results → query is easy, results are good
• Low CTR: Users don't click → results are poor OR query is ambiguous
• Zero results: Hard query, rare terms, out-of-corpus vocabulary
• High reformulation rate: Users keep refining → original query is unclear
• Short dwell time: Users click but leave quickly → results don't satisfy
• Query length: Long queries (5+ words) are often harder than short queries

Query Difficulty Prediction

Train a classifier to predict difficulty before retrieval:

• Features: Query length, entity count, presence of rare terms, historical CTR
• Label: Easy (CTR > 0.3), Medium (CTR 0.1–0.3), Hard (CTR < 0.1)
• Model: Logistic regression or XGBoost

Use case: For hard queries, apply extra processing (expansion, spelling correction, entity extraction). For easy queries, use simpler fast path.

Failure Mode Analysis

Query Log Analysis

Mining search logs reveals patterns:

• Identify zero-result queries (most damaging to UX)
• Find high-reformulation queries (users give up)
• Detect emerging topics (spike in new queries)
• Monitor intent distribution over time

A/B Testing Query Understanding

Test: Enable query expansion vs. control (no expansion).

Metrics:

• Click-through rate (CTR): higher is better
• Mean reciprocal rank (MRR): position of first click
• Success rate: at least one relevant result clicked
• Reformulation rate: lower is better

Duration: Run 1–2 weeks to accumulate sufficient traffic and account for temporal patterns.

Python Implementation

End-to-end query understanding pipeline. Uses numpy and pandas only (no heavy dependencies).

SpellCorrector Class

import numpy as np
from collections import Counter

class SpellCorrector:
    def __init__(self, corpus_file):
        """Load word frequencies from corpus."""
        self.word_freq = Counter()
        with open(corpus_file, 'r') as f:
            for line in f:
                words = line.lower().split()
                self.word_freq.update(words)

    def levenshtein_distance(self, s1, s2):
        """Compute Levenshtein edit distance."""
        m, n = len(s1), len(s2)
        dp = np.zeros((m+1, n+1), dtype=int)
        for i in range(m+1):
            dp[i, 0] = i
        for j in range(n+1):
            dp[0, j] = j

        for i in range(1, m+1):
            for j in range(1, n+1):
                cost = 0 if s1[i-1] == s2[j-1] else 1
                dp[i, j] = min(
                    dp[i-1, j] + 1,      # delete
                    dp[i, j-1] + 1,      # insert
                    dp[i-1, j-1] + cost  # replace
                )
        return dp[m, n]

    def candidates(self, word, max_dist=2):
        """Find words within edit distance."""
        return [w for w in self.word_freq
                if self.levenshtein_distance(word, w) <= max_dist]

    def correct(self, word):
        """Find best correction (highest frequency)."""
        if word in self.word_freq:
            return word
        candidates = self.candidates(word)
        if not candidates:
            return word  # No correction found
        best = max(candidates, key=lambda w: self.word_freq[w])
        return best

IntentClassifier Class

class IntentClassifier:
    def __init__(self):
        self.intent_keywords = {
            'informational': ['how', 'what', 'why', 'explain', 'guide'],
            'transactional': ['buy', 'price', 'order', 'download', 'book'],
            'navigational': ['login', 'home', 'official', 'github', 'docs'],
            'local': ['near', 'near me', 'in', 'located'],
            'comparative': ['vs', 'better than', 'difference', 'comparison']
        }

    def classify(self, query):
        """Rule-based intent classification."""
        query_lower = query.lower()
        intent_scores = {intent: 0 for intent in self.intent_keywords}

        for intent, keywords in self.intent_keywords.items():
            for keyword in keywords:
                if keyword in query_lower:
                    intent_scores[intent] += 1

        if max(intent_scores.values()) == 0:
            return 'informational', 0.5  # default

        best_intent = max(intent_scores, key=intent_scores.get)
        confidence = intent_scores[best_intent] / len(query.split())
        return best_intent, min(confidence, 1.0)

QueryExpander Class

class QueryExpander:
    def __init__(self, synonyms_dict):
        """synonyms_dict: {word: [list of synonyms]}"""
        self.synonyms = synonyms_dict

    def expand(self, query, max_expansions=3):
        """Expand query with top-K synonyms per term."""
        terms = query.lower().split()
        expanded = list(terms)

        for term in terms:
            if term in self.synonyms:
                syns = self.synonyms[term][:max_expansions]
                expanded.extend(syns)

        return ' '.join(expanded)

# Example usage
synonyms = {
    'car': ['automobile', 'vehicle', 'sedan'],
    'cheap': ['affordable', 'inexpensive', 'budget'],
    'flight': ['ticket', 'air travel', 'journey']
}
expander = QueryExpander(synonyms)
print(expander.expand('cheap flights'))
# Output: cheap flights affordable inexpensive budget ticket air travel journey

PRFExpander Class (Rocchio)

class PRFExpander:
    def __init__(self, documents_bm25_scores):
        """documents: list of {id, text, bm25_score}"""
        self.documents = documents_bm25_scores

    def expand_rocchio(self, query, top_k=3, alpha=1.0, beta=0.75):
        """Rocchio expansion."""
        # Assume self.documents are already ranked by BM25
        relevant_docs = self.documents[:top_k]

        # Simple term frequency in relevant docs
        rel_terms = Counter()
        for doc in relevant_docs:
            words = doc['text'].lower().split()
            rel_terms.update(words)

        # Top expansion terms
        expansion_terms = rel_terms.most_common(5)

        # Reweighted query (in practice, would use TF-IDF vectors)
        expanded = f"{query} " + " ".join([t for t, _ in expansion_terms])
        return expanded

QueryPipeline Class

class QueryPipeline:
    def __init__(self, spell_corrector, intent_classifier,
                 query_expander, prf_expander):
        self.spell = spell_corrector
        self.intent = intent_classifier
        self.expander = query_expander
        self.prf = prf_expander

    def process(self, query, use_expansion=True, use_prf=False):
        """End-to-end query processing."""
        # 1. Normalize
        query = query.strip().lower()

        # 2. Spell correction
        corrected_terms = [self.spell.correct(t) for t in query.split()]
        corrected = ' '.join(corrected_terms)

        # 3. Intent classification
        intent, confidence = self.intent.classify(corrected)

        # 4. Entity recognition (simplified, not shown)
        # entities = self.ner.extract(corrected)

        # 5. Query expansion
        if use_expansion:
            final_query = self.expander.expand(corrected)
        else:
            final_query = corrected

        # 6. PRF (requires initial retrieval results)
        if use_prf:
            final_query = self.prf.expand_rocchio(final_query)

        return {
            'original': query,
            'corrected': corrected,
            'intent': intent,
            'confidence': confidence,
            'expanded': final_query
        }

# Example
corrector = SpellCorrector('corpus.txt')
classifier = IntentClassifier()
expander = QueryExpander(synonyms)
prf = PRFExpander([])
pipeline = QueryPipeline(corrector, classifier, expander, prf)
result = pipeline.process('cheap flihts to paris')
print(result)

Test with Sample Queries

test_queries = [
    'how to lean python',          # typo + informational
    'buy cheap flights paris',     # transactional + local
    'github login',                # navigational
    'python vs javascript',        # comparative
    'restarants near me'           # typo + local
]

for query in test_queries:
    result = pipeline.process(query)
    print(f"Query: {result['original']}")
    print(f"  Corrected: {result['corrected']}")
    print(f"  Intent: {result['intent']} (conf: {result['confidence']:.2f})")
    print(f"  Expanded: {result['expanded']}")
    print()

Cross-references: bm25_inverted_index_guide.html, dense_retrieval_guide.html, hybrid_search_reranking_guide.html.