Section 2
Findings
Enforcing access control inside an approximate retrieval query costs recall in proportion to how restrictive the role is — and widening the search does not buy it back.
An approximate index returns its nearest neighbours by distance. Only then does the access policy discard the rows the querying role may not see, and nothing refills the discarded slots. The narrower the role, the more of its top-k is spent on rows it will never be shown.
This is the one result on this site that does not wait on the golden set, because exact search is its own ground truth: run the same query without the approximation, under the same policy, and compare.
2.1 Recall falls with the breadth of the role
Five roles over the same 12 queries and the same corpus, at the default search width of ef_search =40. The only thing that changes between rows is how many of the 47 tenants the role may read.
| role | tenants | recall@10 vs exact | empty | ef 40 | ef 100 | ef 200 | ef 400 | ef 800 |
|---|---|---|---|---|---|---|---|---|
| all_tenants | 47/47 | 0.850 | 0 | 0.850 | 0.942 | 0.967 | 0.967 | 0.975 |
| analyst_broad | 35/47 | 0.842 | 0 | 0.842 | 0.933 | 0.950 | 0.950 | 0.975 |
| analyst_mid | 12/47 | 0.667 | 2 | 0.667 | 0.842 | 0.892 | 0.958 | 0.958 |
| analyst_narrow | 3/47 | 0.500 | 5 | 0.500 | 0.633 | 0.667 | 0.667 | 0.667 |
| single_tenant | 1/47 | 0.300 | 6 | 0.300 | 0.608 | 0.650 | 0.658 | 0.667 |
recall@10 against exact search under the identical policy · “empty” = queries returning nothing at all, of 12 · ef columns are the same measure at each search width
Produced by rls_demo.py · commit 341ea20 · 2026-08-25 · measured as zeroth_app (NOSUPERUSER, NOBYPASSRLS)
At the default width a role seeing all 47 tenants recalls 0.850 of what exact search returns. A role seeing 1 recalls 0.300 — and returns nothing at all for 6 of 12 queries, on which exact search under the same policy returns a full result set. The rows exist and the role is entitled to them; the index simply never reached them.
2.2 Widening the search plateaus below the ceiling
The obvious mitigation is to search wider and let the policy discard more. It works, partially, and then stops: the narrowest role climbs from 0.300 at ef_search =40 to 0.667 at 800 — a twentyfold increase in search width for a result that is still well short of the unrestricted figure, and paid for in latency on every query.
What this shows
- Post-filtering costs recall in proportion to how restrictive the role is: at the default ef_search=40, recall falls from 0.850 with all 47 tenants visible to 0.300 with one.
- Restricted roles return nothing at all for 6 of 12 queries even though exact search under the identical policy returns a full result set.
- Widening the search plateaus below the unrestricted ceiling. A single-tenant role tops out at 0.667 where an unrestricted one reaches 0.975, and 4 queries still return nothing at ef_search=800.
2.3 An earlier result that did not replicate
- An earlier measurement on a SYNTHETIC corpus found that raising ef_search from 40 to 800 changed nothing at all. That does not replicate here: recall for a single-tenant role moves from 0.300 to 0.667 and empty results fall from 6 to 4.
The synthetic corpus used generated tenant clusters that were almost perfectly separated (inter-tenant cosine 0.014), so a restricted role's nearest neighbours were entirely other tenants at any search width. Real documents share vocabulary, boilerplate and structure, so tenant regions overlap and a wider search does reach permitted rows. The separated case was the worst case, not the typical one.
The lesson generalises beyond this project: a synthetic corpus with cleanly separated tenants measures the worst case and reports it as the typical one. Real documents share vocabulary, boilerplate and structure, so the tenant regions of the embedding space overlap, and that overlap is what a wider search is able to exploit.
2.4 What follows from it
Widening the search buys recall back only up to a plateau, and costs latency to do it. Partitioning removes the problem rather than mitigating it: the index contains only permitted rows, so there is nothing to post-filter away.
What this does not establish
- That the answers were worse. This measures what the index lost against exact search, not answer quality. Whether a lost chunk mattered is a question for the golden set, and no such number is published yet.
- That the effect size transfers. It is a property of this corpus, this tenant assignment and this index configuration. A corpus whose tenants overlap more would lose less.
- That the figures are stable to three decimals. HNSW graph construction is not deterministic. Re-running this script moves these figures by a few points; the shape of the result is stable, the third decimal is not.
- A confidence interval. 12 queries is too few for one worth publishing, which is why the shape of the result is stated and the third decimal is not.
Index: hnsw m=16, ef_construction=64, built in 7.7s · top-k 10 · roles measured as zeroth_app (NOSUPERUSER, NOBYPASSRLS)