Junior Developer Implementation Guide: Issue #373

RAG Vector Search - Comprehensive Unit Testing

Overview

Test vector search algorithms and optimizations including similarity metrics, indexing strategies, approximate nearest neighbor (ANN) algorithms, and search performance. The implementations exist across document stores and retrieval components - ensure comprehensive testing.

For Beginners: What Is Vector Search?

The Core Problem

You have: 1 million documents, each represented as a 768-dimensional vector
You want: Find the 10 most similar documents to a query vector
Challenge: Computing similarity to ALL 1 million vectors is slow!

Vector Search = Fast Similarity Search

Naive Approach (Slow):

For each of 1,000,000 documents:
    Calculate similarity to query
Sort by similarity
Return top 10
Time: 5+ seconds

Optimized Vector Search (Fast):

Use index structure (HNSW, IVF, etc.)
Search only ~1% of documents
Return approximate top 10
Time: <100 milliseconds

Real-World Analogy

Library without index:

Check EVERY book one by one to find similar ones
Slow but perfectly accurate

Library with Dewey Decimal System:

Check only the relevant section
Fast but might miss a perfect match in wrong section
Good enough 99% of the time

Vector search uses "indices" (like Dewey Decimal) to quickly narrow down which vectors to check.

What EXISTS in the Codebase

Vector Search Components

Similarity Metrics (in StatisticsHelper<T>):

CosineSimilarity - Measures angle between vectors (most common)
EuclideanDistance - Straight-line distance
DotProduct - Inner product
ManhattanDistance - L1 distance
JaccardSimilarity - Set similarity

Index Structures (in document stores):

Flat Index - Brute force, exact but slow
IVF (Inverted File) - Partitions vector space
HNSW (Hierarchical Navigable Small World) - Graph-based ANN
LSH (Locality Sensitive Hashing) - Hash-based ANN

Search Strategies:

Exact Search - Check all vectors (slow, perfect)
Approximate Nearest Neighbor (ANN) - Check subset (fast, ~99% accurate)
Filtered Search - Apply metadata filters before/after vector search
Multi-Vector Search - Search with multiple query vectors

What's MISSING (This Issue)

Test Coverage Gaps

Similarity Metric Tests:

Correctness of similarity calculations
Edge cases (identical vectors, orthogonal vectors, zero vectors)
Numerical stability (very small/large values)
Performance benchmarks

Index Structure Tests:

Index building correctness
Search accuracy (recall@K)
Search speed
Index size/memory usage
Thread safety

Search Algorithm Tests:

Exact vs approximate accuracy comparison
Recall measurement (% of true top-K found)
Parameter tuning (nprobe, ef, M parameters)
Trade-offs (speed vs accuracy)

Integration Tests:

End-to-end search pipeline
Filtered search correctness
Large-scale performance

Step-by-Step Implementation

Step 1: Similarity Metric Tests

// File: tests/Helpers/SimilarityMetricTests.cs

using Xunit;
using AiDotNet.Helpers;
using AiDotNet.LinearAlgebra;

namespace AiDotNet.Tests.Helpers;

/// <summary>
/// Tests for vector similarity metrics.
/// </summary>
public class SimilarityMetricTests
{
    [Fact]
    public void CosineSimilarity_IdenticalVectors_Returns1()
    {
        // Arrange
        var vec = new Vector<double>(new[] { 1.0, 2.0, 3.0 });

        // Act
        var similarity = StatisticsHelper<double>.CosineSimilarity(vec, vec);

        // Assert
        Assert.Equal(1.0, similarity, precision: 5);
    }

    [Fact]
    public void CosineSimilarity_OrthogonalVectors_Returns0()
    {
        // Arrange
        var vec1 = new Vector<double>(new[] { 1.0, 0.0, 0.0 });
        var vec2 = new Vector<double>(new[] { 0.0, 1.0, 0.0 });

        // Act
        var similarity = StatisticsHelper<double>.CosineSimilarity(vec1, vec2);

        // Assert
        Assert.Equal(0.0, similarity, precision: 5);
    }

    [Fact]
    public void CosineSimilarity_OppositeVectors_ReturnsNegative1()
    {
        // Arrange
        var vec1 = new Vector<double>(new[] { 1.0, 2.0, 3.0 });
        var vec2 = new Vector<double>(new[] { -1.0, -2.0, -3.0 });

        // Act
        var similarity = StatisticsHelper<double>.CosineSimilarity(vec1, vec2);

        // Assert
        Assert.Equal(-1.0, similarity, precision: 5);
    }

    [Fact]
    public void CosineSimilarity_NormalizedVectors_ComputesCorrectly()
    {
        // Arrange - Unit vectors
        var vec1 = new Vector<double>(new[] { 0.6, 0.8, 0.0 });  // Length = 1
        var vec2 = new Vector<double>(new[] { 0.0, 0.6, 0.8 });  // Length = 1

        // Act
        var similarity = StatisticsHelper<double>.CosineSimilarity(vec1, vec2);

        // Assert
        // dot product = 0*0.6 + 0.6*0.8 + 0.8*0 = 0.48
        Assert.Equal(0.48, similarity, precision: 5);
    }

    [Fact]
    public void CosineSimilarity_WithZeroVector_HandlesGracefully()
    {
        // Arrange
        var vec1 = new Vector<double>(new[] { 1.0, 2.0, 3.0 });
        var vec2 = new Vector<double>(new[] { 0.0, 0.0, 0.0 });

        // Act & Assert
        // Should either return 0 or throw ArgumentException
        // Depends on implementation choice
        var similarity = StatisticsHelper<double>.CosineSimilarity(vec1, vec2);
        Assert.True(similarity == 0.0 || double.IsNaN(similarity));
    }

    [Fact]
    public void CosineSimilarity_WithVeryLargeValues_RemainsStable()
    {
        // Arrange
        var vec1 = new Vector<double>(new[] { 1e100, 2e100, 3e100 });
        var vec2 = new Vector<double>(new[] { 1e100, 2e100, 3e100 });

        // Act
        var similarity = StatisticsHelper<double>.CosineSimilarity(vec1, vec2);

        // Assert - Should still be 1.0 despite large values
        Assert.Equal(1.0, similarity, precision: 3);
    }

    [Fact]
    public void EuclideanDistance_IdenticalVectors_Returns0()
    {
        // Arrange
        var vec = new Vector<double>(new[] { 1.0, 2.0, 3.0 });

        // Act
        var distance = StatisticsHelper<double>.EuclideanDistance(vec, vec);

        // Assert
        Assert.Equal(0.0, distance, precision: 5);
    }

    [Fact]
    public void EuclideanDistance_KnownCase_ComputesCorrectly()
    {
        // Arrange
        var vec1 = new Vector<double>(new[] { 0.0, 0.0 });
        var vec2 = new Vector<double>(new[] { 3.0, 4.0 });

        // Act
        var distance = StatisticsHelper<double>.EuclideanDistance(vec1, vec2);

        // Assert
        // sqrt(3^2 + 4^2) = sqrt(25) = 5.0
        Assert.Equal(5.0, distance, precision: 5);
    }

    [Fact]
    public void DotProduct_IdenticalVectors_ReturnsSquaredNorm()
    {
        // Arrange
        var vec = new Vector<double>(new[] { 1.0, 2.0, 3.0 });

        // Act
        var dotProduct = StatisticsHelper<double>.DotProduct(vec, vec);

        // Assert
        // 1^2 + 2^2 + 3^2 = 14
        Assert.Equal(14.0, dotProduct, precision: 5);
    }

    [Fact]
    public void DotProduct_OrthogonalVectors_Returns0()
    {
        // Arrange
        var vec1 = new Vector<double>(new[] { 1.0, 0.0, 0.0 });
        var vec2 = new Vector<double>(new[] { 0.0, 1.0, 0.0 });

        // Act
        var dotProduct = StatisticsHelper<double>.DotProduct(vec1, vec2);

        // Assert
        Assert.Equal(0.0, dotProduct, precision: 5);
    }

    [Fact]
    public void SimilarityMetrics_WithMismatchedDimensions_ThrowsArgumentException()
    {
        // Arrange
        var vec1 = new Vector<double>(new[] { 1.0, 2.0, 3.0 });
        var vec2 = new Vector<double>(new[] { 1.0, 2.0 });

        // Act & Assert
        Assert.Throws<ArgumentException>(() =>
            StatisticsHelper<double>.CosineSimilarity(vec1, vec2));

        Assert.Throws<ArgumentException>(() =>
            StatisticsHelper<double>.EuclideanDistance(vec1, vec2));
    }

    [Fact]
    public void CosineSimilarity_Performance_HandlesLargeVectors()
    {
        // Arrange
        var dimension = 1536;  // OpenAI embedding size
        var vec1 = new Vector<double>(Enumerable.Range(0, dimension).Select(i => (double)i).ToArray());
        var vec2 = new Vector<double>(Enumerable.Range(0, dimension).Select(i => (double)(i + 1)).ToArray());

        // Act
        var stopwatch = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 0; i < 10000; i++)
        {
            _ = StatisticsHelper<double>.CosineSimilarity(vec1, vec2);
        }
        stopwatch.Stop();

        // Assert
        Assert.True(stopwatch.ElapsedMilliseconds < 1000,
            $"10K cosine similarity calculations took {stopwatch.ElapsedMilliseconds}ms (should be < 1s)");
    }
}

Step 2: Index Structure Tests

// File: tests/RetrievalAugmentedGeneration/VectorSearch/IndexTests.cs

using Xunit;
using AiDotNet.RetrievalAugmentedGeneration.VectorSearch;

namespace AiDotNet.Tests.RetrievalAugmentedGeneration.VectorSearch;

/// <summary>
/// Tests for vector search index structures.
/// </summary>
public class VectorIndexTests
{
    [Fact]
    public void FlatIndex_ExactSearch_FindsAllTrueNeighbors()
    {
        // Arrange
        var index = new FlatIndex<double>(dimension: 128);

        // Add 1000 random vectors
        var vectors = GenerateRandomVectors(count: 1000, dimension: 128);
        index.AddBatch(vectors);

        // Query vector
        var query = GenerateRandomVector(dimension: 128);

        // Act - Flat index is exact, so it's our ground truth
        var results = index.Search(query, k: 10);

        // Assert
        Assert.Equal(10, results.Count);

        // Results should be sorted by distance
        for (int i = 0; i < results.Count - 1; i++)
        {
            Assert.True(results[i].Distance <= results[i + 1].Distance);
        }
    }

    [Fact]
    public void HNSWIndex_ApproximateSearch_AchievesHighRecall()
    {
        // Arrange
        var exactIndex = new FlatIndex<double>(dimension: 128);
        var hnswIndex = new HNSWIndex<double>(dimension: 128, M: 16, efConstruction: 200);

        var vectors = GenerateRandomVectors(count: 10000, dimension: 128);

        exactIndex.AddBatch(vectors);
        hnswIndex.AddBatch(vectors);

        var query = GenerateRandomVector(dimension: 128);

        // Act
        var exactResults = exactIndex.Search(query, k: 10);
        var hnswResults = hnswIndex.Search(query, k: 10, efSearch: 50);

        // Assert - Calculate recall@10
        var exactIds = new HashSet<int>(exactResults.Select(r => r.Id));
        var hnswIds = new HashSet<int>(hnswResults.Select(r => r.Id));

        var recall = (double)hnswIds.Intersect(exactIds).Count() / exactIds.Count;

        // HNSW should achieve >95% recall
        Assert.True(recall >= 0.95, $"Recall@10 = {recall:F3}, expected >= 0.95");
    }

    [Fact]
    public void HNSWIndex_WithHigherEfSearch_BetterRecall()
    {
        var index = new HNSWIndex<double>(dimension: 128, M: 16, efConstruction: 200);
        var vectors = GenerateRandomVectors(count: 10000, dimension: 128);
        index.AddBatch(vectors);

        var query = GenerateRandomVector(dimension: 128);

        // Act
        var lowEfResults = index.Search(query, k: 10, efSearch: 20);
        var highEfResults = index.Search(query, k: 10, efSearch: 200);

        // Higher efSearch should find results closer (or equal) to query
        // (In practice, measure against ground truth)
    }

    [Fact]
    public void IVFIndex_WithProperNprobe_GoodRecallSpeedTradeoff()
    {
        // IVF (Inverted File) partitions vector space into clusters
        var index = new IVFIndex<double>(dimension: 128, nlist: 100);

        var vectors = GenerateRandomVectors(count: 10000, dimension: 128);
        index.AddBatch(vectors);

        var query = GenerateRandomVector(dimension: 128);

        // Act - Search with different nprobe values
        var stopwatch1 = System.Diagnostics.Stopwatch.StartNew();
        var results1 = index.Search(query, k: 10, nprobe: 1);  // Fast, lower recall
        stopwatch1.Stop();

        var stopwatch2 = System.Diagnostics.Stopwatch.StartNew();
        var results2 = index.Search(query, k: 10, nprobe: 10);  // Slower, higher recall
        stopwatch2.Stop();

        // Assert
        // Higher nprobe should take more time but find better results
        Assert.True(stopwatch2.ElapsedMilliseconds >= stopwatch1.ElapsedMilliseconds);
    }

    [Fact]
    public void Index_ThreadSafe_ConcurrentSearches()
    {
        var index = new HNSWIndex<double>(dimension: 128, M: 16, efConstruction: 100);
        var vectors = GenerateRandomVectors(count: 1000, dimension: 128);
        index.AddBatch(vectors);

        // Act - Concurrent searches
        var tasks = Enumerable.Range(0, 100).Select(i => Task.Run(() =>
        {
            var query = GenerateRandomVector(dimension: 128);
            var results = index.Search(query, k: 5);
            return results.Count;
        })).ToArray();

        Task.WaitAll(tasks);

        // Assert - All searches completed without errors
        Assert.All(tasks, task => Assert.True(task.IsCompletedSuccessfully));
    }

    private List<Vector<double>> GenerateRandomVectors(int count, int dimension)
    {
        var random = new Random(42);  // Fixed seed for reproducibility
        var vectors = new List<Vector<double>>();

        for (int i = 0; i < count; i++)
        {
            var data = new double[dimension];
            for (int j = 0; j < dimension; j++)
            {
                data[j] = random.NextDouble();
            }
            vectors.Add(new Vector<double>(data));
        }

        return vectors;
    }

    private Vector<double> GenerateRandomVector(int dimension)
    {
        return GenerateRandomVectors(1, dimension)[0];
    }
}

Step 3: Search Algorithm Tests

// File: tests/RetrievalAugmentedGeneration/VectorSearch/SearchAlgorithmTests.cs

using Xunit;
using AiDotNet.RetrievalAugmentedGeneration.VectorSearch;

namespace AiDotNet.Tests.RetrievalAugmentedGeneration.VectorSearch;

public class SearchAlgorithmTests
{
    [Fact]
    public void ExactSearch_AlwaysFindsOptimalResults()
    {
        // Exact search is ground truth - test it thoroughly
    }

    [Fact]
    public void ANNSearch_RecallVsSpeedTradeoff()
    {
        // Measure recall@K for different speed settings
        // Plot recall curve: recall@1, recall@5, recall@10, etc.
    }

    [Fact]
    public void FilteredSearch_AppliesFiltersBeforeSearch()
    {
        // Pre-filtering: Filter first, then search
        // Post-filtering: Search first, then filter
        // Test both approaches
    }

    [Fact]
    public void MultiVectorSearch_CombinesResults()
    {
        // Search with multiple query vectors
        // Aggregate results (max score, average, RRF, etc.)
    }
}

Testing Strategy

Coverage Targets

Similarity metrics: 95%+
Index structures: 85%+
Search algorithms: 80%+

Key Metrics to Test

Accuracy:

Recall@K: % of true top-K results found
Precision@K: % of returned results that are actually top-K

Performance:

Queries Per Second (QPS): Search throughput
Latency (p50, p95, p99): Response time percentiles
Index build time: Time to construct index
Memory usage: RAM consumption

Common Pitfalls

Pitfall 1: Not Testing Recall

Wrong:

var results = index.Search(query, k: 10);
Assert.Equal(10, results.Count);  // Only checks count!

Correct:

var exactResults = flatIndex.Search(query, k: 10);
var annResults = hnswIndex.Search(query, k: 10);

var exactIds = exactResults.Select(r => r.Id).ToHashSet();
var annIds = annResults.Select(r => r.Id).ToHashSet();

var recall = (double)annIds.Intersect(exactIds).Count() / exactIds.Count;

Assert.True(recall >= 0.95, $"Recall = {recall}, expected >= 0.95");

Pitfall 2: Ignoring Numerical Stability

Wrong:

// Test only with well-behaved values

Correct:

[Fact]
public void CosineSimilarity_WithVerySmallValues_Stable()
{
    var vec1 = new Vector<double>(new[] { 1e-100, 2e-100 });
    var vec2 = new Vector<double>(new[] { 1e-100, 2e-100 });

    var similarity = StatisticsHelper<double>.CosineSimilarity(vec1, vec2);

    Assert.True(similarity > 0.99, "Should handle very small values");
}

Testing Checklist

Similarity Metrics

Index Structures

Search Algorithms

Next Steps

Implement all similarity metric tests (30+ methods)
Implement index structure tests (50+ methods)
Implement search algorithm tests (40+ methods)
Achieve 80%+ coverage
Create performance benchmark suite
Document recall/speed trade-offs

Resources

Vector Search Algorithms

HNSW: Hierarchical Navigable Small World graphs
IVF: Inverted file index (clustering-based)
LSH: Locality Sensitive Hashing
Product Quantization: Compression for large scale

Similarity Metrics

Cosine: Best for normalized embeddings
Euclidean: Best for absolute distances
Dot Product: Fast, works for normalized vectors

Benchmarking

ANN-Benchmarks: Standard benchmark suite
Recall@K: Primary accuracy metric
QPS: Primary speed metric

Good luck! Vector search optimization is crucial for RAG performance at scale. These tests ensure both accuracy and speed!

Uh oh!

[Test Coverage] Implement Tests for RAG Vector Search #373

Description

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions