Bird
Raised Fist0

Vector Search and Approximate Nearest Neighbor - FAISS, HNSW

SYSTEM-DESIGNhardInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Vector Search and Approximate Nearest Neighbor - FAISS, HNSW
Efficiently retrieve nearest neighbors using vector search techniques.
system-designhardFreq: very_highRanking & Retrieval
Prerequisites:EmbeddingsK-Nearest Neighbors
🎯
Problem Framing
Business Objective

Maximize user engagement by providing relevant content recommendations.

ML Objective

Retrieve top-k nearest neighbors for a given query vector to maximize relevance.

Constraints
  • P99 latency < 100ms for retrieval
  • Handle 10,000 QPS
  • Scalable to 1 billion vectors
  • Cold start for new items
  • Compliance with data privacy regulations
Clarifying Questions
  • What is the expected scale of the vector database?
  • Are there any specific latency requirements?
  • How often do new items get added to the system?
  • What is the acceptable trade-off between accuracy and speed?
  • Are there any specific privacy concerns with the data?
Out of Scope
✗ Exact nearest neighbor search
✗ Non-vector data types
✗ Non-scalable solutions
📊
Offline Metrics
Recall@k: Measures the fraction of relevant items retrieved in the top-k results, important for ensuring relevant recommendations.
NDCG@10: Normalized Discounted Cumulative Gain at 10, which weights top results more heavily, ensuring high relevance in top positions.
📈
Online Metrics
CTR: Click-through rate of recommended items, directly tied to user engagement.
Average session duration: Measures how long users stay engaged with the content.
⚖️
Trade-offs

High recall might increase latency, affecting CTR negatively if users experience delays.

💼
Business Metric

Overall user engagement measured by CTR and session duration.

🗄️
Data Sources
  • User interaction logs (clicks, views) - real-time
  • Content metadata (tags, categories) - daily updates
  • User profiles (demographics, preferences) - weekly updates
🏷️
Data Properties
Labeling Strategy

Implicit feedback from user interactions (clicks, views) to infer relevance.

Data Volume

Approximately 100 million interactions per day, 10 TB of data per month.

Freshness

Real-time updates for interaction logs, T-1 day for content metadata.

⚠️
Data Challenges
  • Sparse labels due to implicit feedback
  • Position bias in click data
  • Cold start for new users and items
  • Distribution shift as new content types are introduced
🔧
Key Features
embedding
User embedding
Captures user preferences and behavior patterns.
embedding
Item embedding
Represents content characteristics for similarity search.
numerical
Interaction history
Provides context on user engagement with similar items.
categorical
Content metadata
Enhances item representation with additional context.
numerical
Temporal features
Accounts for time-based trends in user behavior.
⚡
Feature Engineering Notes
Real-time vs Batch

User embeddings need real-time updates, while item embeddings can be pre-computed.

Feature Store

Required

🐍
Feature Snippet
Python
def compute_user_embedding(user_id, interaction_history):
    # Example function to compute user embedding
    embedding = model.encode(interaction_history)
    return embedding
🤖
Model Selection
Baseline

Brute-force exact nearest neighbor search

Proposed Model

HNSW (Hierarchical Navigable Small World) for approximate nearest neighbor search

HNSW provides a good balance between speed and accuracy, suitable for large-scale vector search with low latency requirements.
✗
Alternatives Rejected
Too slow for large-scale data due to exact search nature.
Less accurate compared to HNSW, leading to lower recall.
🏋️
Training Strategy

Offline training to generate embeddings, with periodic updates as new data arrives.

🚀
Serving Infrastructure
LatencyP99 < 100ms end-to-end
Throughput10,000 QPS
ArchitectureTwo-stage: initial retrieval using HNSW, followed by re-ranking using a lightweight model.
CachingCache popular queries with a TTL of 5 minutes, invalidate on data updates.
FallbackUse cached results or a rule-based system if the model is unavailable.
📡
Data Drift Signals
Shift in user embedding distribution
Change in item embedding distribution
Variation in interaction patterns over time
📉
Model Drift Signals
Decrease in Recall@k
Drop in NDCG@10
CTR decline over time
🔔
Alerting & Retraining
Retraining Trigger

Recall@k drops below 80% of baseline performance.

Alerting Strategy

On-call alerts for significant metric drops, automated logs for data distribution changes, auto-recovery by switching to cached results.

🎯
Interview Angles
  • How do you handle the trade-off between speed and accuracy in vector search?
  • What strategies do you use to mitigate cold start problems?
  • How do you ensure data privacy compliance in this system?
⚠️
Common Mistakes
Ignoring the latency constraints in model selection.
Overlooking the importance of caching strategies.
Failing to address cold start issues adequately.
Not considering data privacy regulations.
📌
Key Decisions
  • Choosing HNSW for its balance of speed and accuracy.
  • Implementing a two-stage retrieval and ranking architecture.
  • Designing a robust caching strategy to handle high QPS.

Practice

(1/5)
1. For a Guardrails System in LLMs, which metric is most appropriate to evaluate the effectiveness of content moderation?
easy
A. F1 Score
B. Precision
C. Recall
D. Accuracy

Solution

  1. Step 1: Understand the importance of balance

    F1 Score balances precision and recall, crucial for content moderation.

  2. Step 2: Eliminate wrong options

    Accuracy doesn't account for class imbalance, precision alone ignores false negatives, and recall alone ignores false positives.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    F1 Score balances precision and recall. [OK]
Hint: F1 Score balances precision and recall. [OK]
Common Mistakes:
2. For a RAG system focused on improving user satisfaction, which metric should be prioritized?
easy
A. Precision
B. Recall
C. User Engagement Rate
D. F1 Score

Solution

  1. Step 1: Align metrics with business objectives.

    User satisfaction is best measured by user engagement, reflecting how users interact with the system.

  2. Step 2: Eliminate wrong options.

    Precision, recall, and F1 score are technical metrics that don't directly measure user satisfaction.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    User satisfaction = engagement. [OK]
Hint: User satisfaction = engagement. [OK]
Common Mistakes:
3. When designing a recommendation system to avoid filter bubbles, which approach is more suitable for ensuring content freshness?
medium
A. Popularity-based recommendations
B. Static content lists
C. User-based collaborative filtering
D. Time-decay models

Solution

  1. Step 1: Evaluate each approach's impact on freshness

    Time-decay models prioritize recent content, enhancing freshness.

  2. Step 2: Eliminate wrong options

    Static content lists (A) do not adapt over time. User-based collaborative filtering (C) and popularity-based recommendations (D) may reinforce existing preferences, not freshness.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Time-decay models prioritize recent content [OK]
Hint: Time-decay models prioritize recent content [OK]
Common Mistakes:
4. When choosing between pairwise and listwise approaches for a ranking task, which scenario favors the listwise approach?
medium
A. When the ranking task requires optimizing the entire list's order
B. When the ranking task involves a large number of items
C. When computational resources are limited
D. When the goal is to optimize for individual item relevance

Solution

  1. Step 1: Identify the scenario where listwise is beneficial.

    Listwise approaches are best when optimizing the entire list's order is crucial.

  2. Step 2: Eliminate wrong options.

    Pairwise is better for individual relevance, and listwise can be resource-intensive, making A and B incorrect.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Listwise = full list optimization [OK]
Hint: Listwise = full list optimization [OK]
Common Mistakes:
5. As a vision-language model scales to handle 10x more data, which component is most likely to become a bottleneck first?
hard
A. Cross-modal attention layer
B. Model training time
C. Data preprocessing pipeline
D. Inference latency

Solution

  1. Step 1: Consider the impact of scaling data

    Handling 10x more data increases the load on data preprocessing significantly.

  2. Step 2: Identify the first bottleneck

    Data preprocessing often becomes a bottleneck before training or inference as it needs to handle and prepare large volumes of data efficiently.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Scaling data stresses preprocessing first. [OK]
Hint: Scaling data stresses preprocessing first. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard