Live Coding Interview Prep

Course Content

Live Coding Interview Prep

7 sections · 50 lessons

Implement query expansion for better retrieval results.

What you need to know

The vocabulary mismatch problem: a user types "reset my password", the help article is titled "Credential recovery procedure". Keyword search finds nothing, and even embeddings can rank it low. Expansion fixes the query side.

  • Recall is the share of relevant documents you found. Precision is the share of what you returned that is relevant. Expansion adds words, which finds more (recall up) but can pull in off-topic results (precision down).
  • LLM expansion — a model writes 3 alternative phrasings. Good for short or vague questions. Costs one model call.
  • Pseudo-relevance feedback (PRF) — assume the top few results of a first search are relevant, and borrow their frequent terms. Cheap and classic, but if the first search was wrong, PRF drifts further off topic.
  • HyDE (a related trick) — ask the model to write a hypothetical answer and embed that instead of the question, because answers look more like documents than questions do.
Python
import refrom collections import Counterfrom collections.abc import Callable_BULLET = re.compile(r"^\s*(?:[-*•]|\d+[.)])\s*")def llm_expand(query: str, llm_fn: Callable[[str], str], n: int = 3) -> list[str]:    """Return [query] plus up to n cleaned, de-duplicated paraphrases."""    if not query.strip():        return [query]    reply = llm_fn(        f"Rewrite the search query below as {n} alternative queries using different "        f"wording and likely document phrasing. One per line, no numbering.\n\nQuery: {query}"    )    out, seen = [query], {query.strip().lower()}    for line in reply.splitlines():        variant = _BULLET.sub("", line).strip().strip('"')        if variant and variant.lower() not in seen:            seen.add(variant.lower())            out.append(variant)        if len(out) == n + 1:            break    return outSTOPWORDS = {"the", "a", "an", "and", "or", "of", "to", "in", "is", "for", "on",             "with", "how", "what", "why", "does", "do", "from", "after", "my"}def prf_expand(query: str, top_docs: list[str], extra_terms: int = 3) -> str:    """Pseudo-relevance feedback: append the most frequent new terms of the top hits."""    counts: Counter[str] = Counter()    for doc in top_docs:        words = re.findall(r"[a-z]{3,}", doc.lower())        counts.update(list(dict.fromkeys(w for w in words if w not in STOPWORDS)))    have = set(re.findall(r"[a-z]+", query.lower()))    new = [w for w, _ in counts.most_common() if w not in have][:extra_terms]    return " ".join([query, *new])

The tricky parts:

  • Cleaning model output. Models often number their lines ("1. reset password") even when told not to. The _BULLET regex strips -, *, •, 1. and 1) prefixes; stripping quotes handles "forgot password".
  • Counting each term once per document (dict.fromkeys) so one long document cannot dominate. Using dict.fromkeys rather than a set also keeps first-seen order, which makes ties in most_common deterministic — a set of strings iterates in a different order in every Python process.
  • The original query stays at index 0. It is the one variant guaranteed to be on topic.

Complexity: LLM expansion is one model call plus one retrieval per variant (run them concurrently). PRF is one extra retrieval plus O(T) over the T tokens in the top documents, and O(V log V) to rank the V distinct terms.

A real-life example

LLM expansion with a stub model that numbers its lines and repeats itself:

Python
fake_llm = lambda _: "1. reset password\n- forgot my password\nRESET PASSWORD\n\"credential recovery\""print(llm_expand("reset password", fake_llm))# ['reset password', 'forgot my password', 'credential recovery']

Line by line: 1. reset password loses its number and is a duplicate of the original, so it is skipped; - forgot my password is kept; RESET PASSWORD is a case-insensitive duplicate, skipped; the quoted line is unquoted and kept.

PRF on two first-pass hits:

Python
hits = ["Credential recovery: open the login page and choose Forgot password.",        "Password recovery emails expire after 15 minutes."]print(prf_expand("reset password", hits, extra_terms=2))# reset password recovery credential

recovery appears in both documents (count 2) and password is already in the query, so recovery comes first; credential is the first count-1 term. With extra_terms=3 the next term is open — noise, which is exactly how PRF lowers precision.

On a bank's help centre, expanding "UPI money stuck" with "pending transaction" and "amount debited not credited" is what lets it find the dispute-process article.

Follow-up questions to expect

  • "When should you not expand?" — When the query is already precise: an error code, an order id, a product SKU. Expansion dilutes it. A simple rule: skip expansion when the query contains a long number or code.
  • "How do you merge the results of the variants?" — Retrieve for each variant and fuse with reciprocal rank fusion, never by concatenating lists or comparing raw scores across queries.
  • "How do you prove it helped?" — Recall@10 on a labelled set with and without expansion, plus latency. If recall moves by less than a point, the extra call is not worth it.