ADR-268: Capability-Gated ANN Search

Status: Proposed
Date: 2026-06-25
Author: Nightly Research Agent
Branch: research/nightly/2026-06-25-capability-gated-ann
Crate: crates/ruvector-capgated
Related: ADR-227 (Proof-Gated Writes), ADR-240 (Coherence-HNSW), ADR-256 (Hybrid Search)

---

Context

RuVector stores vectors that represent memory, knowledge, and agent state. In multi-agent deployments — and increasingly in enterprise RAG pipelines — the right to retrieve is not uniform. An agent managing user A's memory should not be able to recall user B's embeddings, even if they are geometrically close. A security-cleared retrieval pipeline should not surface classified embeddings to uncleared queriers.

Current state of the ecosystem:

• ADR-227 (proof-gated writes): vectors can only be written if the writer presents a valid proof token. There is no symmetric read-time access control.
• ACORN / Milvus RBAC / Qdrant payload-filter: these systems filter after ANN search — meaning the ANN engine first retrieves candidates from the full corpus, then drops unauthorised ones. This wastes distance computations and, more importantly, leaks the existence of nearby vectors to any observer who can count results or measure latency.
• pgvector / Weaviate class-level permissions: access control is at the collection or class level, not per-vector.

None of these systems embed access control into the retrieval index at the per-vector granularity. For agent memory, this matters: a single index may hold memories belonging to hundreds of different agent sessions, each of which should be isolated.

---

Decision

Introduce crates/ruvector-capgated as a standalone Rust crate implementing capability-gated ANN search: each stored vector carries a CapMask (64-bit bitset of required capabilities) and each query presents a CapMask (held capabilities). A result is returned only if the querier holds all required bits.

Three retrieval variants are implemented and benchmarked:

Variant	Strategy	Recall@10	Mean Latency	QPS
PostFilter	Compute all distances, discard unauthorised	100%	494 μs	2,023
EagerMask	Skip distance computation for unauthorised	100%	175 μs	5,728
CapGraph	k-NN graph walk, ef-bounded exploration	90.6%	289 μs	3,466

(Numbers from n=5,000 × 64-dim, 37.5% access ratio, 200 queries, release build on x86_64.)

The public API is the CapGatedIndex trait:

pub trait CapGatedIndex {
    fn insert(&mut self, id: usize, vector: Vec<f32>, required: CapMask);
    fn search(&self, query: &[f32], k: usize, holder: CapMask) -> Vec<SearchResult>;
    fn name(&self) -> &'static str;
}

This trait shape should survive into production.

---

Consequences

Positive

• Per-vector read access control: the only RuVector system to enforce capability checks at vector granularity during retrieval.
• EagerMask is strictly better than PostFilter at low access ratios: at 12.5% access ratio, EagerMask is 7.9× faster than PostFilter while achieving identical recall.
• CapGraph achieves sub-linear recall potential: graph-based traversal visits only ef=300 nodes out of 5,000 to find 90.6% of ground-truth results.
• No external dependencies: zero-dep pure Rust, WASM-safe.
• Composable with existing RuVector primitives: CapMask can wrap any inner ANN backend (HNSW, LSM-ANN, PQ-ADC).

Negative / Risks

• CapGraph build is O(n²·d): the brute-force k-NN graph build in this PoC takes 2.3 s for n=5,000. Production requires incremental insertion (HNSW- style) or an approximate k-NN graph (RNG, random projection).
• Graph traversal leaks access patterns: in the "transparent traversal" model, unauthorised node coordinates are implicitly traversed (but not returned). A timing side-channel could reveal existence. A "strict isolation" model (only expand authorised nodes) closes this but degrades recall further.
• CapGraph recall degrades with low access ratio: at 12.5% access, recall@10 is 0.869; at 37.5% it is 0.906. This is expected — the graph is built on the full corpus and the authorised subgraph may be disconnected.
• 64-bit cap space only: the current CapMask is a fixed 64-bit integer. For >64 roles, a variable-length bitset or hierarchical capability tree is needed.

---

Alternatives Considered

1. Post-hoc SQL-style WHERE filter (status quo)

All major vector databases (Qdrant, pgvector, Milvus, Weaviate) perform access control as a post-retrieval filter. This is simple but: (a) wastes distance computation on unauthorised vectors, (b) requires k' >> k candidates to guarantee k authorised results, (c) leaks the existence of unauthorised neighbours via timing.

Rejected: misses the EagerMask speedup at low access ratios; no index-level isolation.

2. Separate index per access group

Maintain one HNSW/LSM index per capability group. A querier with 3 caps holds 3 separate indices.

Rejected: memory cost is O(n × 2^caps) in the worst case; search requires merging multiple indices; impractical for fine-grained capabilities.

3. Encrypted vector retrieval (homomorphic / SEAL)

Encrypt vectors before storing; query against encrypted corpus.

Rejected: 3–6 orders of magnitude slower; no practical Rust SEAL binding with HNSW; out of scope for this nightly. Worth a separate ADR as a long-term research direction.

4. Capability-aware quantization (cap bits in PQ codes)

Embed capability bits directly into PQ codes; filter at the codebook-lookup stage.

Interesting future direction: would enable compressed + access-controlled retrieval in one pass. Documented as a "next" item.

---

Implementation Plan

Phase 1 (this PR)

• crates/ruvector-capgated: trait, CapMask, Oracle, PostFilter, EagerMask, CapGraph with batch_build.
• Benchmark binary with acceptance tests.
• ADR, research document, gist.

Phase 2 (production hardening)

• Replace O(n²) graph build with incremental HNSW-style insertion.
• Variable-length CapMask for >64 capabilities.
• Integrate EagerMask as a filter layer in ruvector-core's query pipeline.
• MCP tool wrapper: vector_memory_search(query, capability_token).
• Proof-gate integration: writes require proof, reads require capability token.

Phase 3 (research)

• Capability-aware PQ quantization.
• Strict isolation mode with recall characterisation.
• Timing side-channel analysis and mitigation.
• Distributed capability-gated search with ruFlo workflow.

---

Benchmark Evidence

Hardware: x86_64 Linux
Rust: 1.94.1
Command: cargo run --release -p ruvector-capgated --bin benchmark

Scenario: high-access (37.5% authorised)

Variant	Mean(μs)	p50(μs)	p95(μs)	QPS	Recall@10	Pass
PostFilter	494	493	552	2,023	1.000	✓
EagerMask	175	167	206	5,728	1.000	✓
CapGraph	289	281	329	3,466	0.906	✓

Scenario: low-access (12.5% authorised)

Variant	Mean(μs)	p50(μs)	p95(μs)	QPS	Recall@10	Pass
PostFilter	450	456	487	2,221	1.000	✓
EagerMask	57	54	74	17,548	1.000	✓
CapGraph	295	288	358	3,396	0.869	✓

Key observation: EagerMask provides the best latency when access ratio is low, as it skips distance computation for unauthorised vectors entirely.

---

Failure Modes

1. Access ratio → 0%: all variants degrade gracefully; PostFilter and EagerMask return empty results immediately; CapGraph returns empty after exhausting ef budget.
2. Capability token forgery: CapMask is a plain u64 in this PoC. Production requires cryptographic signing (integrate with ADR-227 proof-gate) to prevent queriers from self-asserting capabilities.
3. Graph disconnection: if authorised vectors form isolated clusters in the proximity graph, CapGraph may miss them entirely. Mitigation: increase ef_multiplier; ensure n_entry_points covers the authorised subgraph.
4. Capability inflation: if a querier holds all 64 bits (CapMask::ALL), all vectors are accessible — equivalent to no access control. Applications must not hand out ALL-capable tokens unless intentional.

---

Security Considerations

• This PoC does not provide cryptographic access control. Any caller can construct any CapMask and pass it to search. Production must gate token creation behind a proof-gate (ADR-227) or a signed JWT / capability cert.
• Timing side-channels: EagerMask and PostFilter latency is proportional to the authorised fraction, leaking the fraction to a timing observer. For high- sensitivity deployments, constant-time execution is required.
• CapGraph traversal leakage: the graph walk visits unauthorised nodes as bridge nodes. Strict isolation (expand only authorised nodes) prevents this at a recall cost.

---

Migration Path

1. Add ruvector-capgated as a dependency in ruvector-core.
2. Wrap existing HnswIndex with a CapGatedWrapper<HnswIndex> using the EagerMask strategy.
3. Expose via ruvector-server as POST /search with capability_token field.
4. Wire into MCP tool surface as vector_memory_search(query, token).

---

Open Questions

1. Should CapMask be variable-length (e.g. Vec<u64>) to support >64 roles?
2. Should proof-gate verification (ADR-227) be composable with CapMask in a single call?
3. Is the strict-isolation CapGraph worth implementing as a separate variant for high-security deployments?
4. Can capability bits be embedded in PQ codebooks for compressed + gated search?
5. What is the right ef_multiplier trade-off for production use (latency vs recall)?