How AlloyDB ScaNN scales vector search to 10 billion vectors

Google's AlloyDB ScaNN index now scales vector search to 10 billion vectors, a major architectural enhancement featuring a four-level tree (preview) that reduces compute intensity and improves memory efficiency. The new design achieves query complexity of O(N^1/4) and uses balanced tree shape and sampling optimization to overcome previous bottlenecks at two- and three-level configurations.

To satisfy the demands of enterprise-grade agentic AI applications, underlying vector databases often struggle to scale effectively as modern use cases can scale to billions of vectors. As a fully managed PostgreSQL-compatible database service, AlloyDB https://docs.cloud.google.com/alloydb/docs/overview is engineered to handle demanding enterprise workloads. Combining Google's infrastructure with the reliability of commercial databases, it delivers high availability, scalability, and includes a cutting-edge analytical engine, optimal for agentic AI use cases. A key part of this is its ScaNN index https://docs.cloud.google.com/alloydb/docs/ai/create-scann-index , which now operates efficiently at a scale of 10 billion vectors. This was achieved through a major architectural enhancement: an innovative four-level tree preview https://docs.cloud.google.com/alloydb/docs/ai/create-scann-index four-level-tree-index paired with efficient memory usage . Scaling to a 10 billion vector workload presents significant memory and computational challenges. Previous AlloyDB ScaNN tree-based index was limited to two https://docs.cloud.google.com/alloydb/docs/ai/create-scann-index two-level-tree-index - or three https://docs.cloud.google.com/alloydb/docs/ai/create-scann-index three-level-tree-index -level tree configurations, and attempting to scale those structures led to several bottlenecks: Increased compute intensity: Larger tree structures demand significantly more operations for both index construction and query traversal. Memory constraints: The sampling processes required for 10 billion vectors can easily exceed the system's available memory capacity. The introduction of a four-level tree preview https://docs.cloud.google.com/alloydb/docs/ai/create-scann-index four-level-tree-index is the primary innovation in the recent AlloyDB ScaNN release. This architecture, illustrated in Figure 1, employs a top-down strategy to optimize the balance between accuracy and build efficiency. To maintain high performance and mitigate recall loss, the system integrates key enhancements such as Top-K branch, SOAR https://research.google/blog/soar-new-algorithms-for-even-faster-vector-search-with-scann/ :~:text=ScaNN%20is%20open%2Dsourced%20on%20GitHub%20and%20can%20be%20easily%20installed%20via%20Pip. , centroid adjustment https://arxiv.org/abs/1908.10396 and balanced tree shape. This design has two primary benefits: 1. Reduced compute intensity via hierarchical partitioning The four-level architecture drastically reduces compute intensity by using hierarchical partitioning to restrict the volume of vectors scanned during a query. Instead of traversing a flat or poorly segmented space, the multi-layered hierarchy narrows down the search path exponentially. Figure 2 illustrates the search spaces across different tree levels, demonstrating how structural layering optimizes traversal efficiency: Two-level: Utilizes coarse partitioning to guide queries, resulting in a basic search complexity of O N 1/2 Three-level: Introduces an intermediate layer to further subdivide clusters, narrowing exploration to O N 1/3 Four-level: Implements refined, highly granular partitions that optimize traversal efficiency down to O N 1/4 By dynamically expanding hierarchical layers as the dataset expands, AlloyDB ScaNN maintains ultra-low query latency and avoids computational scale walls from impacting performance. 2. Efficient memory usage Achieving a 10 billion vector scale requires high memory efficiency. AlloyDB ScaNN uses these strategies to maximize memory management performance: Balanced tree shape construction: The four-level tree utilizes a balanced configuration to circumvent memory limitations that restrict the size of training datasets. This balanced architecture effectively leverages reduced sampling sizes to construct high-fidelity tree partitions. Sampling optimization: When the system encounters memory limitations, it generates a condensed sampling set that considers performance and accuracy. By leveraging the innovative four-level tree architecture in our internal tests, we are able to achieve the following performance results: AlloyDB can scale to over 10 billion vectors with its ScaNN index. AlloyDB can deliver <= 51 ms p95 latency and 95% recall at 10 billion vectors with its ScaNN index. Experience AlloyDB ScaNN's four-level tree preview https://docs.cloud.google.com/alloydb/docs/ai/create-scann-index four-level-tree-index architecture today. You can deploy ScaNN for AlloyDB by following our quickstart guide https://cloud.google.com/alloydb/docs/quickstart/create-and-connect to set up an instance. For optimized, high-speed vector search, refer to the official ScaNN documentation https://docs.cloud.google.com/alloydb/docs/ai/create-scann-index . New users can also explore AlloyDB https://console.cloud.google.com/alloydb/create-trial-cluster? gl=1 qsd2cd up MQ..&gclid=CjwKCAjwooq3BhB3EiwAYqYoEh91xxGzv4xrmyMJJ BPfF4X8cv-I3kINwvnMI2pADozFQPsrHnaOhoCbioQAvD BwE&gclsrc=aw.ds through our 30-day free trial https://cloud.google.com/blog/products/databases/run-your-postgresql-database-in-an-alloydb-free-trial-cluster program. We can’t wait to hear about what you build