# HONEYBEE: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning[Technical Report]

arXiv: https://arxiv.org/abs/2505.01538 · HTML: https://mlsanity.com/paper/2505.01538/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 2 May 2025.

## Builds on (most cited first, 13 of 13)

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Blended RAG: Improving RAG (Retriever-Augmented Generation) Accuracy with Semantic Search and Hybrid Query-Based Retrievers](https://mlsanity.com/paper/2404.07220/) (2024)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [High-Throughput Vector Similarity Search in Knowledge Graphs](https://mlsanity.com/paper/2304.01926/) (2023)
- [Qd-tree: Learning Data Layouts for Big Data Analytics](https://mlsanity.com/paper/2004.10898/) (2020)
- [HQANN: Efficient and Robust Similarity Search for Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2207.07940/) (2022)
- [The Impacts of Data, Ordering, and Intrinsic Dimensionality on Recall in Hierarchical Navigable Small Worlds](https://mlsanity.com/paper/2405.17813/) (2024)
- [Curator: Efficient Indexing for Multi-Tenant Vector Databases](https://mlsanity.com/paper/2401.07119/) (2024)
- [Dynamic Data Layout Optimization with Worst-case Guarantees](https://mlsanity.com/paper/2405.04984/) (2024)
- [LeaFi: Data Series Indexes on Steroids with Learned Filters](https://mlsanity.com/paper/2502.01836/) (2025)

## Built on by (most cited first, 3 of 3)

- [The Attack and Defense Landscape of Agentic AI: A Comprehensive Survey](https://mlsanity.com/paper/2603.11088/) (2026)
- [Permissioned LLMs: Enforcing Access Control in Large Language Models](https://mlsanity.com/paper/2505.22860/) (2025)
- [KadiAssistant: A conversational AI Agent for information retrieval in Kadi4Mat](https://mlsanity.com/paper/2605.18850/) (2026)

## Abstract (arXiv)

Enterprise deployments of vector databases require access control policies to protect sensitive data. These systems often implement access control through hybrid vector queries that combine nearest-neighbor search with relational predicates based on user permissions. However, existing approaches face a fundamental trade-off: dedicated per-user indexes minimize query latency but incur high memory redundancy, while shared indexes with post-search filtering reduce memory overhead at the cost of increased latency. This paper introduces HONEYBEE, a dynamic partitioning framework that leverages the structure of Role-Based Access Control (RBAC) policies to create a smooth trade-off between these extremes. RBAC policies organize users into roles and assign permissions at the role level, creating a natural ``thin waist`` in the permission structure that is ideal for partitioning decisions. Specifically, HONEYBEE produces overlapping partitions where vectors can be strategically replicated across different partitions to reduce query latency while controlling memory overhead. To guide these decisions, HONEYBEE develops analytical models of vector search performance and recall, and formulates partitioning as a constrained optimization problem that balances memory usage, query efficiency, and recall. Evaluations on RBAC workloads demonstrate that HONEYBEE achieves up to 13.5X lower query latency than row-level security with only a 1.24X increase in memory usage, while achieving comparable query performance to dedicated, per-role indexes with 90.4% reduction in additional memory consumption, offering a practical middle ground for secure and efficient vector search.