LLMs and Generative AI › Embeddings and Vector Search › Day 261

Hands-on lab — Day 261: Semantic Similarity Search

Commands

Setup

pip install -r requirements/requirements.txt

Run

python3 examples/semantic_similarity_search_lib.py

Test

./tests/run_tests.sh

File tree

conftest.py
examples/semantic_similarity_search_lib.py
examples/test_semantic_similarity_search_lib.py
expected-output/examples-run.txt
expected-output/FIELDS.md
expected-output/measured-values.txt
expected-output/starter-run.txt
expected-output/test-run.txt
metadata.yml
README.md
requirements/requirements.txt
security.md
starter/semantic_similarity_search_lib.py
starter/test_semantic_similarity_search_lib.py
tests/run_tests.sh
tests/test_semantic_similarity_search_lib.py
troubleshooting.md

Lab README

Lesson

Day number: 261 of 365. Course: Course06-SS02 (LLMs and Generative AI - Retrieval and Customization). Topic: Semantic Similarity Search, Exact k-NN, Vectorized BLAS, and Top-K Heaps.

Purpose

Build and test a high-performance Exact k-NN Semantic Search Engine in Python. Implement vectorized matrix dot product retrieval, Top-K bounded selection with np.argpartition, and metadata pre-filtering.

Learning objectives

  • Implement vectorized matrix-vector dot product scoring across normalized vector databases.
  • Optimize Top-K extraction using np.argpartition to avoid $O(N \log N)$ sorting bottlenecks.
  • Implement structured metadata pre-filtering over vector corpora.
  • Measure search latency scaling across collections up to 50,000 vectors.

Prerequisites

  • Day 260 (What Embeddings Are).
  • Python 3.11+ with NumPy and Pytest.

Supported operating systems

  • macOS (Apple Silicon / Intel)
  • Linux (Ubuntu, Debian, Fedora, Arch)
  • Windows 11 / WSL2

Hardware requirements

  • 1+ CPU cores.
  • 1 GB RAM.
  • 100 MB disk space.

Required software

  • Python 3.11 or newer.
  • pip package manager.
  • virtualenv or venv module.

Free and open-source options

NumPy and Python standard libraries are open source.

Installation

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements/requirements.txt

File structure

  • starter/semantic_similarity_search_lib.py: Student scaffold file.
  • examples/semantic_similarity_search_lib.py: Complete reference implementation.
  • tests/test_semantic_similarity_search_lib.py: Pytest automated validation suite.
  • expected-output/: Verified output logs and baseline values.

How to run

Execute the reference demonstration script:

python3 examples/semantic_similarity_search_lib.py

What the commands do

  • Builds in-memory vector index.
  • Normalizes vectors and executes query dot products.
  • Runs unit test assertions.

Expected output

k-NN Demo Executed. Top Match: 0 with score 0.9950

Validation steps

  1. Verify dot product matches cosine similarity on unit-normalized vectors.
  2. Confirm Top-K extraction returns exact descending ranked order.
  3. Validate metadata filtering excludes non-matching tags.
  4. Ensure all unit test assertions pass.

Tests

Run the test runner script:

./tests/run_tests.sh

Cleanup

find . -type d -name "__pycache__" -exec rm -rf {} +
find . -type d -name ".pytest_cache" -exec rm -rf {} +

Troubleshooting

  • Zero division warning: Ensure zero-length vectors have their norm defaulted to 1.0.

Security notes

All computations execute locally in memory.

Extension exercises

  1. Implement a batch query search method executing matrix-matrix multiplications (np.dot(Q, D.T)).
  2. Measure latency differences between float32 and float16 tensors.

Expected output

FIELDS.md

# Expected Output Fields: Day 261

- `k-NN Demo`: Status of k-NN search execution.

examples-run.txt

k-NN Demo Executed. Top Match: 0 with score 0.9950

measured-values.txt

k-NN Demo: Success
Top Match: 0
Score: 0.9950

starter-run.txt

Starter scaffold executed. Ready for student implementation.

test-run.txt

============================= test session starts ==============================
collected 4 items

tests/test_semantic_similarity_search_lib.py::test_exact_knn_search PASSED      [ 25%]
tests/test_semantic_similarity_search_lib.py::test_filtered_search PASSED       [ 50%]
tests/test_semantic_similarity_search_lib.py::test_empty_engine_handling PASSED [ 75%]
tests/test_semantic_similarity_search_lib.py::test_top_k_larger_than_corpus PASSED [100%]

============================== 4 passed in 0.35s ===============================

Source files

conftest.py (585 bytes)
"""Make this lab importable when the suite runs.

pytest puts the test file's own directory on sys.path, not the lab root, so a
test that does `from examples.<module> import ...` -- or imports a module that
lives in examples/ directly -- fails without this. Putting it here rather than
in run_tests.sh means a bare `pytest` from the lab root works too.
"""

import os
import sys

LAB = os.path.dirname(os.path.abspath(__file__))
for candidate in (LAB, os.path.join(LAB, "examples")):
    if os.path.isdir(candidate) and candidate not in sys.path:
        sys.path.insert(0, candidate)
examples/semantic_similarity_search_lib.py (2966 bytes)
import numpy as np
from typing import List, Dict, Any, Tuple

class ExactKNNSearchEngine:
    def __init__(self, dimension: int):
        self.dimension = dimension
        self.vectors: np.ndarray = np.empty((0, dimension), dtype=np.float32)
        self.metadata: List[Dict[str, Any]] = []

    def add_documents(self, vectors: np.ndarray, metadatas: List[Dict[str, Any]]) -> None:
        if len(vectors) == 0:
            return
        norms = np.linalg.norm(vectors, axis=1, keepdims=True)
        norms[norms == 0] = 1.0
        normalized_vecs = vectors / norms
        
        self.vectors = np.vstack([self.vectors, normalized_vecs]) if self.vectors.size else normalized_vecs
        self.metadata.extend(metadatas)

    def search(self, query_vec: np.ndarray, top_k: int = 5) -> List[Tuple[Dict[str, Any], float]]:
        if len(self.vectors) == 0:
            return []
        
        q_norm = np.linalg.norm(query_vec)
        q_unit = query_vec / (q_norm if q_norm > 0 else 1.0)

        scores = np.dot(self.vectors, q_unit)
        k = min(top_k, len(scores))
        
        if k == len(scores):
            top_indices = np.argsort(scores)[::-1]
        else:
            partition_idx = np.argpartition(scores, -k)[-k:]
            top_indices = partition_idx[np.argsort(scores[partition_idx])[::-1]]

        return [(self.metadata[idx], float(scores[idx])) for idx in top_indices]

    def search_with_filter(self, query_vec: np.ndarray, filter_key: str, filter_val: Any, top_k: int = 5) -> List[Tuple[Dict[str, Any], float]]:
        matching_indices = [
            idx for idx, meta in enumerate(self.metadata)
            if meta.get(filter_key) == filter_val
        ]
        if not matching_indices:
            return []
        
        sub_vectors = self.vectors[matching_indices]
        q_norm = np.linalg.norm(query_vec)
        q_unit = query_vec / (q_norm if q_norm > 0 else 1.0)
        
        scores = np.dot(sub_vectors, q_unit)
        k = min(top_k, len(scores))
        
        if k == len(scores):
            top_sub_indices = np.argsort(scores)[::-1]
        else:
            partition_idx = np.argpartition(scores, -k)[-k:]
            top_sub_indices = partition_idx[np.argsort(scores[partition_idx])[::-1]]

        return [(self.metadata[matching_indices[idx]], float(scores[idx])) for idx in top_sub_indices]

def run_knn_demo():
    engine = ExactKNNSearchEngine(dimension=4)
    vecs = np.array([
        [1.0, 0.0, 0.0, 0.0],
        [0.0, 1.0, 0.0, 0.0],
        [0.7, 0.7, 0.0, 0.0]
    ], dtype=np.float32)
    metas = [{"id": 0, "cat": "A"}, {"id": 1, "cat": "B"}, {"id": 2, "cat": "A"}]
    engine.add_documents(vecs, metas)
    
    query = np.array([1.0, 0.1, 0.0, 0.0], dtype=np.float32)
    results = engine.search(query, top_k=2)
    print(f"k-NN Demo Executed. Top Match: {results[0][0]['id']} with score {results[0][1]:.4f}")
    return results

if __name__ == "__main__":
    run_knn_demo()
examples/test_semantic_similarity_search_lib.py (1787 bytes)
import pytest
import numpy as np
from examples.semantic_similarity_search_lib import (
    ExactKNNSearchEngine
)

def test_exact_knn_search():
    engine = ExactKNNSearchEngine(dimension=3)
    vecs = np.array([
        [1.0, 0.0, 0.0],
        [0.0, 1.0, 0.0],
        [0.9, 0.1, 0.0]
    ], dtype=np.float32)
    metas = [{"doc_id": "doc1"}, {"doc_id": "doc2"}, {"doc_id": "doc3"}]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 0.0, 0.0], dtype=np.float32)
    results = engine.search(query, top_k=2)

    assert len(results) == 2
    assert results[0][0]["doc_id"] == "doc1"
    assert np.isclose(results[0][1], 1.0)
    assert results[1][0]["doc_id"] == "doc3"

def test_filtered_search():
    engine = ExactKNNSearchEngine(dimension=2)
    vecs = np.array([
        [1.0, 0.0],
        [0.9, 0.1],
        [0.0, 1.0]
    ], dtype=np.float32)
    metas = [
        {"id": 0, "tag": "prod"},
        {"id": 1, "tag": "dev"},
        {"id": 2, "tag": "prod"}
    ]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 0.0], dtype=np.float32)
    # Search only 'dev' tag
    results = engine.search_with_filter(query, filter_key="tag", filter_val="dev", top_k=5)
    assert len(results) == 1
    assert results[0][0]["id"] == 1

def test_empty_engine_handling():
    engine = ExactKNNSearchEngine(dimension=4)
    query = np.array([1.0, 0.0, 0.0, 0.0])
    results = engine.search(query, top_k=5)
    assert results == []

def test_top_k_larger_than_corpus():
    engine = ExactKNNSearchEngine(dimension=2)
    vecs = np.array([[1.0, 0.0], [0.0, 1.0]], dtype=np.float32)
    metas = [{"id": 0}, {"id": 1}]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 1.0])
    results = engine.search(query, top_k=10)
    assert len(results) == 2
metadata.yml (439 bytes)
lesson_id: D261
day: 261
kind: lab
languages:
  - python
setup_commands:
  - 'pip install -r requirements/requirements.txt'
run_commands:
  - 'python3 examples/semantic_similarity_search_lib.py'
test_commands:
  - './tests/run_tests.sh'
cleanup_commands:
  - 'find . -type d -name "__pycache__" -exec rm -rf {} +'
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-30'
executed_on: 'macos-arm64'
requirements/requirements.txt (41 bytes)
torch>=2.2.0
numpy>=1.26.0
pytest>=8.0.0
starter/semantic_similarity_search_lib.py (846 bytes)
import numpy as np
from typing import List, Dict, Any, Tuple

class ExactKNNSearchEngine:
    def __init__(self, dimension: int):
        self.dimension = dimension
        self.vectors: np.ndarray = np.empty((0, dimension), dtype=np.float32)
        self.metadata: List[Dict[str, Any]] = []

    def add_documents(self, vectors: np.ndarray, metadatas: List[Dict[str, Any]]) -> None:
        # TODO: Add and L2-normalize document vectors
        pass

    def search(self, query_vec: np.ndarray, top_k: int = 5) -> List[Tuple[Dict[str, Any], float]]:
        # TODO: Vectorized dot product and Top-K retrieval
        pass

    def search_with_filter(self, query_vec: np.ndarray, filter_key: str, filter_val: Any, top_k: int = 5) -> List[Tuple[Dict[str, Any], float]]:
        # TODO: Metadata pre-filtering followed by exact search
        pass
starter/test_semantic_similarity_search_lib.py (1787 bytes)
import pytest
import numpy as np
from examples.semantic_similarity_search_lib import (
    ExactKNNSearchEngine
)

def test_exact_knn_search():
    engine = ExactKNNSearchEngine(dimension=3)
    vecs = np.array([
        [1.0, 0.0, 0.0],
        [0.0, 1.0, 0.0],
        [0.9, 0.1, 0.0]
    ], dtype=np.float32)
    metas = [{"doc_id": "doc1"}, {"doc_id": "doc2"}, {"doc_id": "doc3"}]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 0.0, 0.0], dtype=np.float32)
    results = engine.search(query, top_k=2)

    assert len(results) == 2
    assert results[0][0]["doc_id"] == "doc1"
    assert np.isclose(results[0][1], 1.0)
    assert results[1][0]["doc_id"] == "doc3"

def test_filtered_search():
    engine = ExactKNNSearchEngine(dimension=2)
    vecs = np.array([
        [1.0, 0.0],
        [0.9, 0.1],
        [0.0, 1.0]
    ], dtype=np.float32)
    metas = [
        {"id": 0, "tag": "prod"},
        {"id": 1, "tag": "dev"},
        {"id": 2, "tag": "prod"}
    ]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 0.0], dtype=np.float32)
    # Search only 'dev' tag
    results = engine.search_with_filter(query, filter_key="tag", filter_val="dev", top_k=5)
    assert len(results) == 1
    assert results[0][0]["id"] == 1

def test_empty_engine_handling():
    engine = ExactKNNSearchEngine(dimension=4)
    query = np.array([1.0, 0.0, 0.0, 0.0])
    results = engine.search(query, top_k=5)
    assert results == []

def test_top_k_larger_than_corpus():
    engine = ExactKNNSearchEngine(dimension=2)
    vecs = np.array([[1.0, 0.0], [0.0, 1.0]], dtype=np.float32)
    metas = [{"id": 0}, {"id": 1}]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 1.0])
    results = engine.search(query, top_k=10)
    assert len(results) == 2
tests/run_tests.sh (227 bytes)
#!/usr/bin/env bash
set -euo pipefail
echo "========================================"
echo "Running Day 261 Lab Test Suite"
echo "========================================"
pytest tests/ -v
echo "All tests passed successfully."
tests/test_semantic_similarity_search_lib.py (1787 bytes)
import pytest
import numpy as np
from examples.semantic_similarity_search_lib import (
    ExactKNNSearchEngine
)

def test_exact_knn_search():
    engine = ExactKNNSearchEngine(dimension=3)
    vecs = np.array([
        [1.0, 0.0, 0.0],
        [0.0, 1.0, 0.0],
        [0.9, 0.1, 0.0]
    ], dtype=np.float32)
    metas = [{"doc_id": "doc1"}, {"doc_id": "doc2"}, {"doc_id": "doc3"}]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 0.0, 0.0], dtype=np.float32)
    results = engine.search(query, top_k=2)

    assert len(results) == 2
    assert results[0][0]["doc_id"] == "doc1"
    assert np.isclose(results[0][1], 1.0)
    assert results[1][0]["doc_id"] == "doc3"

def test_filtered_search():
    engine = ExactKNNSearchEngine(dimension=2)
    vecs = np.array([
        [1.0, 0.0],
        [0.9, 0.1],
        [0.0, 1.0]
    ], dtype=np.float32)
    metas = [
        {"id": 0, "tag": "prod"},
        {"id": 1, "tag": "dev"},
        {"id": 2, "tag": "prod"}
    ]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 0.0], dtype=np.float32)
    # Search only 'dev' tag
    results = engine.search_with_filter(query, filter_key="tag", filter_val="dev", top_k=5)
    assert len(results) == 1
    assert results[0][0]["id"] == 1

def test_empty_engine_handling():
    engine = ExactKNNSearchEngine(dimension=4)
    query = np.array([1.0, 0.0, 0.0, 0.0])
    results = engine.search(query, top_k=5)
    assert results == []

def test_top_k_larger_than_corpus():
    engine = ExactKNNSearchEngine(dimension=2)
    vecs = np.array([[1.0, 0.0], [0.0, 1.0]], dtype=np.float32)
    metas = [{"id": 0}, {"id": 1}]
    engine.add_documents(vecs, metas)

    query = np.array([1.0, 1.0])
    results = engine.search(query, top_k=10)
    assert len(results) == 2

Troubleshooting

Common Issues

  1. Dimension mismatch in np.dot:
    • Cause: Query vector dimension does not match corpus matrix dimension.
    • Fix: Assert query_vec.shape[0] == self.dimension before dot products.

Security notes

Security Guidance

  • Restrict metadata filter fields to prevent unauthorized data access across tenant partitions.