Optimizing search relevance at Instacart using hybrid retrieval

Vinesh Gudla11 Sep 2024

Problem

Instacart search builds a recall set, then ranks it. The recall set merges a fixed number of documents from text search with a fixed number from semantic (embedding) search. The catalog has over 1.4 billion items across 1500+ retailers (Q4 2023), so the number of relevant items per query varies a lot. Fixed quotas over-fetch when few items are relevant, which wastes compute and lowers precision. The better method also depends on how specific the query is.

Example from the article: the query "tofu" returns over 100 results at 99 Ranch Market (an Asian grocery retailer) but fewer than five at Costco.

Solution in brief

Compute query entropy from conversion logs and use it to set the recall size of each retrieval mechanism per query: low entropy gives a small set, high entropy a larger one. The authors are also testing rank-based and score-based list merging, without results yet.

Questions this case answers
  • How to size the candidate sets of two retrieval mechanisms per query when the number of relevant items varies widely across queries and catalogs
  • How to merge ranked lists from lexical and embedding retrieval into one candidate set without fixed per-source quotas
  • How to decide how many documents to fetch from text search and from semantic search for each query?
  • How to stop over-fetching candidates when a retailer has few relevant items for a query?

Tools and methods

  • Query entropy — query specificity from the distribution of converted documents
  • Adaptive recall threshold — clipped linear function of entropy that sets set size
  • PostgreSQL — text retrieval with GIN indexes and ts_rank scoring
  • FAISS — approximate-nearest-neighbor search over document embeddings (bi-encoder based on MiniLM-L3-v2)
  • Reciprocal Rank Fusion and convex combination — candidate ways to merge the two lists
  • pgvector — planned single store for both retrieval types
Continue reading — it's free

Google or a one-time email code. No password.