Lexical Search

Lexical search operates on the principle of exact or morphological term matching. It retrieves documents containing the query words themselves or their linguistic variants (e.g., 'run', 'running', 'ran').

• Core Mechanism: Algorithms scan an inverted index, a data structure mapping each unique term to a list of documents containing it.
• Limitation: It cannot understand synonyms or conceptual meaning without explicit expansion rules. A search for 'automobile' will not match a document only containing the term 'car' unless a synonym dictionary is applied.

Not all matches are equal. Lexical search uses statistical models to rank documents by estimated relevance.

• TF-IDF (Term Frequency-Inverse Document Frequency): Scores a document based on:
  • Term Frequency (TF): How often a term appears in the document.
  • Inverse Document Frequency (IDF): How rare the term is across the entire corpus. Common words (e.g., 'the', 'is') are downweighted.
• BM25 (Best Matching 25): A state-of-the-art probabilistic extension of TF-IDF. It improves upon it by introducing non-linear term frequency saturation and document length normalization, preventing very long documents from dominating results. BM25 is the modern benchmark for keyword search performance.

The inverted index is the fundamental, high-performance data structure that enables fast lexical search at scale.

• Structure: It is a dictionary where each key is a unique vocabulary term (a 'token'). The value for each term is a postings list—a sorted list of document identifiers (DocIDs) where that term appears, often with positional information and term frequencies.
• Query Execution: For a query like 'vector database', the system:
  1. Looks up 'vector' and 'database' in the index.
  2. Retrieves their respective postings lists.
  3. Performs a fast set intersection (for AND queries) or union (for OR queries) on the lists.
  4. Scores the resulting documents using BM25 or similar. This structure allows for sub-second retrieval over billions of documents.

Lexical search supports precise, Boolean-like control over result sets through specific query syntax.

• Boolean Operators: AND, OR, NOT (or -) for logical combinations (e.g., python AND (tutorial OR guide) NOT java).
• Phrase Search: Quoting terms ("neural network") requires the exact phrase to appear in sequence.
• Proximity Search: Finding terms within a specified distance of each other (e.g., "transformer model"~5).
• Wildcards & Prefixes: Using * for wildcard matching (comp* matches 'computer', 'computation') or ? for single character substitution.
• Fielded Search: Restricting search to specific metadata fields (title:"attention is all you need").

Before indexing, raw text undergoes a text analysis or tokenization pipeline to normalize terms. This standardization is critical for consistent matching.

• Steps typically include:
  1. Tokenization: Splitting text into individual words/tokens.
  2. Lowercasing: Converting all characters to lowercase.
  3. Stop Word Removal: Filtering out extremely common words (e.g., 'a', 'the', 'and').
  4. Stemming/Lemmatization: Reducing words to their root form (e.g., 'running' → 'run', 'better' → 'good').
  5. Character Filtering: Removing punctuation, HTML tags, or diacritics (accents). The specific pipeline configuration directly impacts recall and precision.

Lexical search has distinct advantages and limitations compared to semantic search (vector-based).

• Key Strengths:
  • Precise Matching: Excellent for known-item search, codes, IDs, and exact phrases.
  • Explainability: Results are directly traceable to term occurrences; scoring is transparent.
  • Speed & Efficiency: Inverted index lookups are extremely fast and computationally cheap.
  • Terminology-Sensitive: Ideal for domains with rigid, specific vocabularies (e.g., legal, technical documentation).
• Key Limitations:
  • Vocabulary Mismatch: Fails on synonyms, paraphrasing, and conceptual search.
  • No Semantic Understanding: Cannot grasp intent or context behind the words. This is why modern hybrid search systems combine lexical precision with semantic understanding.

TF-IDF is a statistical weighting scheme that evaluates the importance of a word to a document within a collection. It is the product of two metrics:

• Term Frequency (TF): How often a term appears in a document.
• Inverse Document Frequency (IDF): A measure of how common or rare the term is across the entire corpus.

A high TF-IDF score indicates a term is frequent in a specific document but rare in the overall collection, suggesting it is a strong keyword for that document. It powers classic vector space models where queries and documents are compared as sparse vectors.

BM25 is a probabilistic ranking function and the de facto standard algorithm for modern keyword search. It refines TF-IDF by introducing non-linear term frequency saturation and document length normalization.

Key mechanisms:

• Term Frequency Saturation: The benefit of additional occurrences of a term diminishes after a certain point.
• Length Normalization: Penalizes or rewards documents based on how their length compares to the average document length in the collection.
• Tunable Parameters: Includes constants k1 (term frequency scaling) and b (length normalization impact) for fine-tuning.

BM25 is robust, efficient, and forms the lexical component in most hybrid search systems.

Boolean retrieval is a model where documents are retrieved based on exact matches to query terms combined with logical operators AND, OR, and NOT. It uses an inverted index for efficient lookups.

Example Query: "vector AND database NOT graph" retrieves documents containing both "vector" and "database" but excludes any containing "graph".

Characteristics:

• Provides precise, deterministic control over result sets.
• Does not rank results by relevance; all matching documents are considered equally relevant.
• Often used as a foundational filtering layer in more complex search pipelines.

An inverted index is the fundamental data structure that enables fast lexical search. It maps each unique term (or token) in a corpus to a postings list of documents containing that term.

Structure:

• Dictionary: A lookup table of all unique terms.
• Postings Lists: For each term, a sorted list of document identifiers (DocIDs), often with additional data like term positions or frequencies.

Operations:

• Intersection (AND): Finds common DocIDs across multiple postings lists.
• Union (OR): Merges DocIDs from multiple lists.
• Difference (NOT): Removes DocIDs from one list present in another. This structure allows sub-second retrieval from collections containing billions of documents.

These techniques improve recall by matching documents containing variations of the query terms.

Stemming: A crude heuristic process that chops off word endings to reduce words to a common root form (e.g., "searching", "searched", "searches" → "search"). Algorithms like the Porter Stemmer are commonly used.

Lemmatization: A more sophisticated linguistic process that uses vocabulary and morphological analysis to return the base or dictionary form of a word (e.g., "better" → "good").

Query Expansion: Augmenting the original query with synonyms or related terms from a thesaurus (e.g., "car" also searches for "automobile") to capture relevant documents that don't contain the exact query keyword.

In lexical search, documents and queries are often modeled as sparse vectors in a high-dimensional space where each dimension corresponds to a unique term from the corpus.

How it works:

1. The vocabulary of the entire corpus defines the vector space (e.g., 100,000+ dimensions).
2. A document vector has non-zero values only for the terms it contains, weighted by schemes like TF-IDF.
3. Relevance is calculated using similarity measures between these sparse vectors, such as the cosine similarity.

This contrasts with dense vector representations used in semantic search, where dimensions encode latent semantic features and every dimension has a value.

BM25 (Best Matching 25) is a probabilistic ranking function that serves as the modern state-of-the-art algorithm for keyword-based lexical search. It improves upon older models like TF-IDF by incorporating document length normalization and term frequency saturation, preventing very long documents from dominating results.

• Key Mechanism: Scores documents based on the frequency of query terms, penalizing terms that appear too frequently across the entire corpus (inverse document frequency).
• Use Case: The foundational scoring algorithm for sparse retrieval in search engines like Elasticsearch and OpenSearch.

Sparse retrieval is a search paradigm where queries and documents are represented as high-dimensional, sparse vectors, such as bag-of-words models weighted by TF-IDF or BM25. Relevance is calculated using lexical matching metrics.

• Contrast with Dense Retrieval: Uses explicit term matching rather than learned semantic embeddings.
• Efficiency: Inverted indexes allow for extremely fast lookup of documents containing specific terms.
• Limitation: Suffers from the vocabulary mismatch problem, where different words with the same meaning (synonyms) are not matched.

Hybrid search is a retrieval technique that combines results from both semantic (vector) and keyword-based (lexical) searches to improve overall recall and precision. It mitigates the weaknesses of each approach alone.

• Typical Workflow: A single query is executed concurrently against a vector index (for semantic meaning) and a lexical index (for exact term matching).
• Result Fusion: The ranked lists from each system are merged using techniques like Reciprocal Rank Fusion (RRF) or score fusion.
• Benefit: Captures both conceptual relevance and precise keyword matches, providing more robust results.

Metadata filtering is the application of constraints based on structured attributes—such as author, timestamp, category, or status—to restrict the scope of a search query. It is often used in conjunction with lexical or vector search.

• Implementation: Uses Boolean filters (AND, OR, NOT) to create precise inclusion/exclusion criteria.
• Performance: Efficient execution relies on database indices like bitmap indexes and optimization via filter pushdown.
• Use Case: Finding all documents about "machine learning" (lexical search) that were published in 2023 and are tagged as "tutorials" (metadata filters).

Reciprocal Rank Fusion (RRF) is a popular, score-agnostic method for merging ranked lists from different retrieval systems (e.g., lexical and vector) in a hybrid search setup. It promotes documents that rank well consistently across multiple lists.

• Formula: A document's final score is the sum of 1 / (k + rank) for each list it appears in, where k is a constant (often 60).
• Advantage: Does not require calibrated relevance scores from disparate systems, making it simple and robust.
• Result: Effectively combines the recall of different retrieval methods into a single, high-quality ranked list.

A Query Domain-Specific Language (DSL) is a specialized syntax for expressing complex search queries that combine vector similarity, lexical matching (BM25), and Boolean metadata filtering in a single declarative statement.

• Function: Allows developers to precisely define search intent, e.g., find vectors similar to X WHERE category = 'A' AND (date > Y OR priority = 'high').
• Examples: Used in vector databases like Weaviate, Pinecone, and Qdrant.
• Benefit: Provides a unified interface for constructing sophisticated, optimized multi-stage retrieval pipelines.