Query Rewriting: HyDE, Multi-Query, and Decomposition

Query rewriting is the step that transforms a user's query before it reaches the retriever, so the search sees text closer to how the corpus is written. Without it, the retriever has to bridge the vocabulary gap on its own.

Take a user who types "what do we do when a transfer breaks halfway". The corpus contains a doc that says "AbortMultipartOnFail terminates an S3 multipart transfer and decrements the per-bucket retry quota on persistent failure". The query and the document share one word, "transfer". The user says "breaks halfway" where the doc says "persistent failure", so BM25 has little to match on, and the query vector lands nearer to generic transfer and quota docs. In this lesson's demo the hybrid retriever ranks the answer third, behind the transfer manager doc and the quota cooldown doc. The two-stage rerank from lesson 66 can salvage the answer if it sits in the top-N, but a document that never reaches the top-N is invisible to the reranker.

The fix is to rewrite the query before it touches the retriever. The 2023 paper "Precise Zero-Shot Dense Retrieval without Relevance Labels" (Gao et al.) introduced HyDE: ask an LLM to write the document that would answer the query, embed that hypothetical document, and use its embedding as the retrieval vector. The hypothetical document sits in the right region of the embedding space because it is written in the corpus's voice, which the query was not.

Two related techniques pair with HyDE. Multi-query expansion (the term Microsoft's GraphRAG used) generates N paraphrases of the query, retrieves with each, and merges. Decomposition (popularized as "subquery decomposition" in the 2024 Stanford DSPy work) splits "what happens when an upload fails and the retry budget is exhausted" into two questions: "how is an in-flight multipart upload aborted" and "what happens when the retry quota reaches zero". That gives two retrievals and one merged result, with both pieces of the answer within reach.

You will implement all three here and run them against the same fixture corpus.

HyDE in detail

HyDE (Hypothetical Document Embeddings) replaces the user's query vector with the vector of an LLM-written hypothetical document. The prompt is short:

You are a domain expert. Write a one-paragraph passage that answers the question
below. Use the same vocabulary and phrasing the documentation in this domain would
use. Do not refuse. Do not say you do not know.

Question: {user_query}

Passage:

As a factual answer, the LLM's passage is probably wrong, because the model has not seen your corpus. That is fine, since the retriever cares about token distribution and not correctness. The hypothetical passage contains the words "abort", "multipart", "bucket", "budget", because that is what a documentation passage on this topic would say. Embed it and the vector lands near the real passage. In this lesson's code the hypothetical's embedding feeds only the dense side: BM25 still runs on the original query text, and a plain retrieval on the original query joins the fusion as well.

In production, cap the hypothetical at two or three sentences. Longer ones collect noise, and shorter ones lose the lexical signal HyDE needs.

Multi-query expansion in detail

Multi-query expansion generates N paraphrases of the user's query, retrieves top-k for each (and for the original query, so N+1 retrievals), and merges the ranked lists with RRF (the same algorithm from lesson 65). The simplest prompt:

Rewrite the following question in {N} different ways. Each rewrite must preserve
the original intent. Number them 1 to {N}. Do not add explanations.

It is cheap, parallel, and deterministic. It wins when the user's phrasing is one of many equally valid ways to ask the question and some rewrite would have asked it better. It loses when the original was bad in a way that every rewrite inherits.

Decomposition in detail

Decomposition asks the LLM to split a question into sub-questions and retrieves per sub-question, because a single retrieval cannot satisfy a multi-faceted question. The prompt:

The following question may require information from multiple distinct topics.
Decompose it into a list of sub-questions. Each sub-question must be answerable
independently. If the question is already atomic, return it unchanged.

Question: {user_query}

Retrieve per sub-question, then merge. Decomposition fits questions with conjunctions, multi-clause comparisons, or two unrelated topics. It is the wrong tool for atomic questions, where the decomposer should hand back the single question and not invent fake sub-questions.

Why all three exist

They cover different gaps. HyDE bridges the query-corpus token gap, multi-query covers paraphrase variance, and decomposition covers multi-topic queries. A production system can run all three and pick a strategy per query (lesson 69's end-to-end system shows the selector).

A fourth technique, step-back prompting, runs the other way from decomposition. The LLM turns a narrow question into a more general one, you retrieve on the general question, and then you narrow back to the specifics. It helps when the query is too specific for any document to be phrased that way. This lesson does not implement it; exercise 2 adds it.

The mock LLM is a small set of lookup tables keyed on the lowercased user query with any trailing question mark removed, plus a fallback for queries it has not seen. That keeps everything offline. The tables cover:

• HyDE and multi-query: the same three queries ("what do we do when a transfer breaks halfway", "how is access control handled across user types", "how does the search service merge two retrievers"). Each has a written hypothetical passage and three paraphrases.
• Decomposition: two different queries ("what happens when an upload fails and the retry budget is exhausted", "how is authorization handled and how do policies get evaluated"), each with two sub-questions.

The demo's third query appears only in the decomposition table, so on that query HyDE and multi-query run on the fallbacks. For an unknown query the fallbacks are deterministic:

• HyDE writes every token of the query followed by its synonyms from a small synonym map.
• Multi-query produces three paraphrases by cyclic synonym swaps, replacing alternate tokens with a different synonym on each pass.
• Decomposition splits on " and ", or returns the query unchanged if it has none.

The shape of the mock matters more than its data. In production you swap the mock for a real model call and the retriever stays as it is.

code/main.py implements:

• MockLLM - the deterministic stand-in described above.
• HyDERewriter - calls the LLM to write the hypothetical document and returns a RewriteResult holding the hypothetical text and the query the retriever should use.
• MultiQueryRewriter - calls the LLM for N paraphrases and returns a list of queries.
• DecomposeRewriter - calls the LLM to decompose and returns sub-questions.
• retrieve_with_rewriter - takes a rewriter and a retriever, runs the rewrites, and fuses the results. The multi-query rewriter keeps the original query in its list, so it runs N+1 retrievals. HyDE runs two: one on the hypothetical's vector (with BM25 on the original text) and one plain retrieval on the original query. Decomposition runs one per sub-question and drops the original.
• A demo that runs the three rewriters plus a no-rewrite baseline on a three-query fixture and prints, for each, whether the gold document ranked first and where it landed.

The retriever shape comes from lesson 65 (hybrid BM25 + dense), with the same RRF fusion. The rewriter interface is the one new piece, and it is small.

Run it:

python3 code/main.py

The output is one row per strategy per query, with a gold@1 flag, the gold document's rank, and a marker on the strategy each query was designed to favor. Gold first, in the order no-rewrite, HyDE, multi-query, decompose:

• "what do we do when a transfer breaks halfway": no, no, yes, no. Multi-query wins. HyDE moves the gold doc from third to second but not to first, and decomposition finds nothing to split, so it matches the baseline.
• "how does the search service merge two retrievers": no, yes, no, no. HyDE wins, and the baseline buries the gold doc at rank 5.
• "what happens when an upload fails and the retry budget is exhausted": yes, no, yes, yes. Decomposition wins on paper, but plain retrieval and multi-query already rank the gold doc first, and HyDE drops it to second.

Each query's designed winner does hit gold first. The no-rewrite baseline loses on the first two queries and ties on the third.

HyDE gets corpus-specific identifiers wrong. The model invents a function name. If BM25 runs on the hypothetical text, its score on the right doc collapses, because the invented name is now a high-weight token that does not appear in the index. The demo avoids this by running BM25 on the original query, so only the dense side sees the invention. Either way, cap the hypothetical's length.

Multi-query rewrites converge. A weak model produces three near-identical paraphrases, the N retrievals return the same top-k, and the RRF merge is no better than a single retrieval. Add an explicit diversity instruction to the rewrite prompt and detect duplicates by Jaccard.

Decomposition over-splits. The decomposer turns an atomic question into a list. The retrievals all return the same document at a reduced rank, and the merge ends up worse than the original. Add a "are these sub-questions distinct enough" pass before fan-out.

Latency multiplies. HyDE costs one LLM call, then two retrievals. Multi-query costs one LLM call to generate N rewrites, then N+1 retrievals. Decomposition costs one LLM call to decompose, then M retrievals. The retrievals can run in parallel, so the LLM call sets the floor.

Production patterns:

• Pick a strategy per query by shape: short atomic queries get multi-query, complex multi-clause queries get decomposition, and jargon-heavy queries get HyDE.
• Cache the rewriter output by query hash, since many queries repeat.
• Run all three in parallel and fuse the three result sets with RRF. That costs three LLM calls and one fusion, and the quality is the union of all three strategies' coverage.

Lesson 69 wires this rewriter stage in front of the retriever from lesson 65 and the reranker from lesson 66. Lesson 68 evaluates how much recall the rewriter adds.

1. Implement RAG-Fusion (a 2024 variant of multi-query) where the rewriter's paraphrases are intentionally diverse, then the rerank step (lesson 66) picks the final list.
2. Add a fourth strategy: step-back prompting (ask the LLM for the more general question, retrieve on that, then narrow). Compare on the fixture.
3. Train the decomposer to recognize atomic queries by adding a "is the question atomic" head. Measure the over-split rate before and after.
4. Replace the mock LLM with a real model call. Measure the latency-per-strategy on your stack.
5. Add a confidence score per rewrite. Drop rewrites below the threshold. Measure the impact on recall.

• Gao, Ma, Lin, Callan, "Precise Zero-Shot Dense Retrieval without Relevance Labels" (HyDE), 2023
• Microsoft Research, "Multi-Query Expansion for Retrieval"
• Stanford DSPy, "Subquery Decomposition for Multi-Hop QA"
• LlamaIndex query transformations documentation
• Phase 11 lesson 07 - advanced RAG patterns
• Phase 19 lesson 65 - the retriever this rewriter feeds
• Phase 19 lesson 68 - the eval that measures the rewriter lift