Bitmap indexing for authorization decisions: why data shape wins

At a glance

What this is: Cerbos describes how a rewritten authorization rule index moved from policy-shaped maps to bitmap-based filtering, then to a custom bitmap that improved latency and memory behaviour.

Why it matters: IAM and platform teams should care because the same performance and structure tradeoffs show up whenever policy evaluation, NHI governance, or access decisions must run inline.

By the numbers:

• The standard evaluator microbenchmark improved from 43.8 µs to 6.6 µs after the index rewrite and custom bitmap work.

👉 Read Cerbos' engineering post on rewriting authorization index performance

Context

Authorization performance is not just a code optimisation problem. When policy evaluation sits in the request path, the shape of the index determines whether access decisions stay fast enough to use inline or become too expensive to trust in production.

The core issue here is policy indexing, not policy logic. Cerbos shows how a system can preserve the same authorization semantics while changing the underlying data structure from nested maps to bitmaps, which matters for any programme that depends on low-latency decisions across application, workload, or service identities.

Key questions

Q: How should teams decide whether an authorization index is too expensive for inline evaluation?

A: Teams should look for three signals: rising allocation rates, growing garbage-collector time, and candidate-set filtering that creates multiple temporary structures per request. If the evaluator is still logically correct but the service spends more time preparing to decide than deciding, the index is too expensive for the path it serves.

Q: Why does data-shape fit matter so much in policy evaluation systems?

A: Data-shape fit matters because authorization engines are not just rule interpreters, they are query systems. If the index mirrors the wrong shape, the engine pays duplication and intersection costs on every request. A structure that matches real binding cardinality and dimension density will usually outperform a more sophisticated structure that fits the wrong workload.

Q: What do security teams get wrong about bitmap-based authorization indexes?

A: They often focus only on intersection speed and ignore the memory model beneath it. A bitmap can be very fast in a microbenchmark and still create load problems if it allocates too often or uses a representation designed for a much larger universe than the one actually in production.

Q: Should organisations optimise authorization engines before changing policy design?

A: Yes, but only after you separate policy logic from index cost. If the policy model is sound but the evaluator is burning CPU on allocation, the right move is to change the data structure or storage pattern first. If the policy itself is too complex, no index will fully hide that cost.

Technical breakdown

Rule-table design and why policy-shaped indexes stall

A rule table is an indexing layer that stores authorization rules in a form the evaluator can scan efficiently. Cerbos started with policy-shaped storage, then expanded rules into a relational-style table so it could query across resource, role, action, and other dimensions uniformly. That solved shape, but the index still duplicated rules across dimensions and created intermediate maps during intersections. The result was fast enough for a while, yet allocator pressure grew as policy sets expanded.

Practical implication: if authorization latency is creeping up, inspect the index shape before tuning the policy engine itself.

Bitmap intersections and candidate reduction

A bitmap index represents each dimension value as a set of binding IDs, with bits set when a binding matches that value. Evaluation becomes a series of bitmap AND operations that narrow the candidate set before any rule payload is checked. This works because set intersection is cheaper than repeatedly building temporary maps, especially when the query touches multiple dimensions. Cerbos found that the bitmap approach removed a large amount of per-request allocation and turned most of the work into tight word-level operations.

Practical implication: map high-cardinality rule filters to bitmap-style candidate reduction when request volume is high.

Why a custom bitmap beat roaring at sustained load

Roaring bitmaps are designed for large sparse sets, but Cerbos discovered its binding sets were relatively small. That made roaring’s container hierarchy more complex than the workload needed. The custom bitmap used two slices, one for bits and one metadata layer that quickly ruled out empty intersections. That simpler design reduced memory overhead, made pooling straightforward, and improved sustained throughput by cutting garbage-collector pressure after the initial roaring rewrite had already improved microbenchmarks.

Practical implication: benchmark both latency and throughput, because the best microbenchmark structure may still lose under real GC load.

Breaches seen in the wild

• Schneider Electric credentials breach — exposed credentials gave attackers access to Schneider Electric Jira, exfiltrating 40GB.
• LiteLLM PyPI package breach — LiteLLM PyPI supply chain attack, credentials stolen from users.

Read our 52 NHI Breaches Analysis report for a comprehensive view of breaches impacting Non-Human Identities including AI Agents.

NHI Mgmt Group analysis

Authorization indexing is now an identity-control problem, not just a performance problem. Once authorization decisions sit in the request path, the index becomes part of the control plane for human and non-human identities alike. If the evaluator cannot answer quickly, teams either widen cache windows, relax enforcement, or move checks out of band. The practical implication is that performance debt can become governance debt.

Policy-shaped data structures create hidden friction in NHI and service-account governance. When the same access shape repeats across tenants, workloads, or API consumers, duplicated rule state multiplies operational cost and makes change harder than it should be. That is an OWASP-NHI style lesson in structural fit: the problem is not only who gets access, but how many times the platform must represent the same entitlement. Practitioners should treat index design as part of entitlement hygiene.

Allocation pressure is a control-plane risk because it changes what “fast enough” means. Cerbos showed that a technically correct evaluator can still become operationally fragile if every request creates throwaway candidate sets. Under load, garbage collection can dominate the actual authorization logic, which means the access control system is spending its budget on memory churn instead of decisions. The implication is that request-path authorization needs design review at the same seriousness as policy review.

Data structure fit should be judged against the actual binding population, not abstract best practice. Roaring bitmaps are excellent engineering for large sparse universes, but they were the wrong default for a few tens of thousands of bindings with modest density. This is the named concept here: identity decision-path fit, the degree to which the evaluator’s representation matches the size and shape of the identity graph it serves. Practitioners should validate fit against production-scale entitlement patterns before standardising on a data structure.

Inline authorisation must be measured as a sustained service, not a benchmark headline. Cerbos improved its microbenchmark first, then found the real bottleneck under load and fixed that second. That sequence is typical of mature authorization engineering: the meaningful question is not whether the first rewrite was faster, but whether the final system stays stable when traffic and policy cardinality rise together. Teams should measure both request latency and throughput under realistic load.

From our research:

• The average estimated time to remediate a leaked secret is 27 days, despite 75% of organisations expressing strong confidence in their secrets management capabilities, according to The State of Secrets in AppSec.
• From our research: Organisations maintain an average of 6 distinct secrets manager instances, creating fragmentation that undermines centralised control, according to The State of Secrets in AppSec.
• Forward pivot: For the lifecycle side of this problem, see Ultimate Guide to NHIs , Lifecycle Processes for Managing NHIs for how governance breaks down when entitlements, rotation, and offboarding are not aligned.

What this signals

Identity decision-path fit: the closer your authorization index matches the real binding shape of your environment, the less operational drag it creates. That matters across service accounts, application identities, and human access flows, because the evaluator is part of the control plane and not just an implementation detail.

Cerbos’ rewrite is a reminder that programme maturity often shows up in the invisible layers. If you are still carrying duplicated entitlement state, the next improvement is less likely to come from a new policy rule and more likely to come from a better representation of the same policy truth, aligned with the NIST Cybersecurity Framework 2.0 and the request-path discipline in NIST SP 800-207 Zero Trust Architecture.

For practitioners

• Profile allocator behaviour in the request path Measure how much CPU is going to map creation, candidate intersection, and garbage collection before changing policy logic. If allocation dominates, treat the index as the problem and not the policy set itself.
• Model policy data by binding shape, not policy count Count unique routing tuples, duplicated payloads, and dimension cardinality so you can see whether your current representation is duplicating the same entitlement state across tenants or workloads.
• Test candidate reduction under realistic policy density Benchmark the engine with production-like role, action, and resource distributions. A structure that wins on sparse microbenchmarks may still lose when the policy set is smaller, denser, or more repetitive.
• Separate latency testing from throughput testing Run short benchmark loops and sustained load tests as different exercises. The first tells you whether the evaluator is fast in isolation, while the second shows whether GC pressure or memory churn will surface in production.

Key takeaways

• The main lesson is not that bitmaps are faster, but that authorization performance depends on whether the index matches the actual shape of the policy data.
• The scale signal is clear: the engine moved from allocator-heavy intersections to a custom bitmap path that improved both microbenchmarks and sustained throughput.
• Teams that want inline authorization to stay reliable should measure allocation, GC, and candidate-set shape before they assume policy logic is the bottleneck.

Key terms

• Policy Decision Point: A Policy Decision Point is the component that answers whether a requested action is allowed. In practice, it evaluates policies against an identity, action, and resource context, then returns a decision fast enough for the application to enforce inline.
• Bitmap Index: A bitmap index represents matching records as bits in a compact array. In authorization systems, each bit can stand for a binding or entitlement, allowing fast set operations that reduce candidates before the engine evaluates rule payloads.
• Garbage-Collector Pressure: Garbage-collector pressure is the runtime cost created by frequent allocations and object churn. In access-control systems, it matters because repeated temporary structures can consume CPU that should be spent on decisions, lowering throughput under production load.
• Candidate Set: A candidate set is the subset of rules that still might apply after an initial filter. Authorization engines shrink this set before checking conditions, and the efficiency of that shrink step often determines whether the evaluator stays usable at scale.

Deepen your knowledge

Authorization indexing and policy-path performance are covered in our NHI Foundation Level course, the industry's only accredited NHI security programme. If you are building governance for inline decisions across workloads or service identities, it is worth exploring.

This post draws on content published by Cerbos: an engineering post on rewriting authorization indexing for faster authorization decisions. Read the original.