Incrementally Computing 7B Permission Checks

Auth0 Fine-Grained Authorization (FGA) expanded its offerings with the FGA Permissions Index, a precomputed authorization index that turns frequent permission checks into simple indexed lookups, and Auth0 FGA chose Feldera to accelerate development of the index. The Permissions Index incrementally computes all access grants implied by a permission when a relationship changes, so the cost of a permission change depends only on the portion of the graph that changes rather than the graph's total size. The optimization targets RAG-based AI agent workflows, where a single agent question can require thousands of permission checks against large, interconnected permission graphs.

Ask an AI agent one question and it might need thousands of permission checks before it answers correctly In Retrieval-Augmented-Generation RAG -based workflows, an agent wants to retrieve all relevant objects from a database, but before any of those objects can be sent to the agent, they must be checked against the current authorization policy, which determines what the user and thus the agent is allowed to see. While evaluating the policy one object at a time is possible, it can quickly become a bottleneck for large, interconnected permission graphs. To address this scaling expectation, Auth0 Fine-Grained Authorization FGA recently expanded its offerings to include the FGA Permissions Index . The FGA Permissions Index precomputes important authorization decisions, turning frequent authorization checks into simple indexed lookups. What is Auth0 FGA? A relationship-based access control ReBAC system, like Auth0 FGA, works by remembering relationships - who has access to what, and why. For example, consider a question like “Which Google Drive folders does Alice’s agent have access to?” As you add more users, objects, and relationships between them, FGA builds a large graph of interconnected relationships. Checking whether a user has access to an object means finding one path through that graph that connects the two. If you want to find all the objects a user or agent has access to, you have to traverse every path and remember all the routes that exist. This is often an expensive set of operations for large, interconnected permission graphs. The key innovation behind the FGA Permissions Index is it flips the work of an authorization check upside down: “What if you could do the expensive work before when permissions change, not after when someone checks access?” The Permissions Index cleverly calculates all these possible relationships in advance. When a new relationship is added to FGA, the Permissions Index quickly incrementally computes all access grants implied by the permission and saves them as direct paths. The result is that access lookups become constant. FGA and Incremental View Maintenance Precomputed indexes are not new. The database concept called Incremental View Maintenance IVM makes this possible by continuously updating an index as users join and leave groups, objects change owners, and relationships are added, removed, or modified. The key architectural challenge within the FGA Permissions Index is maintaining real-time freshness for deeply nested, fine-grained authorization graphs that change every millisecond That is why Auth0 FGA chose Feldera to accelerate development of the Permissions Index. Feldera is backed by the mathematical promises of DBSP https://www.feldera.com/blog/best-research-paper-vldb-2023 , which enables it to evaluate complex, recursive access schemas over massive datasets efficiently and with a finite amount of state. With Feldera, the cost to compute a permission change depends only on the portion of the graph that changes, not on the graph’s total size The result is a new authorization optimization that combines fast query-time lookups with continuously updated permissions—exactly what modern AI and search workloads expect. An example Auth0 FGA Policy Consider an example Auth0 FGA policy that governs a simple file system with users, groups, and objects: - Users can be members of groups - Groups can own objects - Objects can be nested inside parent entities - Members of a group have write access can view to objects owned by the group and all recursive subobjects model schema 1.1 type user type agent type group relations define member: user, agent type object relations define owner: group define parent: object define can view: member from owner or can view from parent With great power comes great computational complexity Centralized authorization policies are powerful, yet computationally demanding. To answer an authorization request, FGA traverses the entire permissions graph to find a chain of relationships that determines whether the requested operation is allowed. The next figure shows an example authorization graph for the above policy. The pink path shows the relationship chain the engine traverses to determine that user alice has view access to the secrets object. The Auth0 FGA engine can evaluate even complex authorization policies in milliseconds. However, modern search and AI workloads increasingly issue authorization checks in bulk at extremely high rates, pushing any request-by-request evaluation model to its limits. One example is Search With Permissions https://docs.fga.dev/integration/advanced/search-with-permissions . Consider a query over a large corpus of data that returns the top 20 results. Before any result can be shown, filtered, or sorted, it must first be checked against the authorization policy to determine if the user has access. If most or all of those results are filtered out, the system must either return fewer relevant results or fetch and evaluate another batch. The first option degrades result quality; the second increases latency and places additional load on the search engine. The challenge becomes even greater with AI agents performing RAG-style retrieval over private datasets. Agents acting on behalf of a user must only observe data that the user is authorized to access. At scale, agentic workloads can generate thousands of authorization checks per second. Good algorithm design can make each graph traversal faster, but it cannot eliminate it altogether. To optimize throughput for these massive check-heavy workloads, Auth0 FGA built upon its core authorization engine to provide an ultra-fast, precomputed Permissions Index. Scaling by Precomputing Every Authorization Decision The Permissions Index is a calculated trade-off that shifts latency from query time to write time. Instead of waiting to evaluate every authorization request on demand, it precomputes authorization decisions in advance. Authorization checks then become simple index lookups instead of graph traversals. The idea is inspired by Google Zanzibar’s Leopard Index, which describes an implementation of a semi-offline, precomputed authorization decision engine. For the graph above, the Permissions Index precomputes the following permissions: user:alice can view object:test-root user:alice can view object:src user:alice can view object:api user:alice can view object:secrets agent:alice-agent can view object:test-root agent:alice-agent can view object:src agent:alice-agent can view object:api agent:alice-agent can view object:secrets user:carol can view object:prod-root user:carol can view object:deploy user:carol can view object:db Note: The Permissions Index thus complements the existing Auth0 FGA APIs. The Permissions Index is helpful in handling initial authorization checks in “hot path” scenarios, but FGA remains the source of truth for writes and critical checks. Check the “cache” of the Permissions Index first, and fall back to FGA if the index is not fresh enough. The combination is a more secure-by-default platform that can provide dramatically lower per-query latency, higher throughput, and significantly more predictable tail latencies under heavy load. Keeping the index fresh at scale with Feldera The real challenge with precomputing indexes is keeping the index up to date, which we tackle with Feldera and incremental view maintenance . In a large system, the authorization graph is constantly changing: Users join and leave groups, objects are created and deleted, and permissions are granted and revoked. A single update can change many derived authorization decisions, invalidating part of the Permissions Index. When a small change happens, we only need to update the affected part of the index instead of wastefully recomputing the entire index from scratch periodically. Let’s say the user moves the secrets object from the test-root to the prod root directory. The engine revokes two previously computed authorization decisions from the index and inserts a new permission instead: DELETE: user:alice can view object:secrets DELETE: agent:alice-agent can view object:secrets INSERT: user:carol can view object:secrets Feldera is well-suited for the above logic. It takes a SQL program consisting of tables and views, and continuously and incrementally updates the views as the input data changes: Expressive. FGA programs can be compiled to Feldera SQL using a straightforward mechanical transformation. In addition to standard SQL, Feldera supports mutually recursive views, which makes it possible to encode recursive FGA rules, such as inherited permissions through nested objects. We show an example of this transformation below. Fully incremental. Feldera evaluates queries incrementally end-to-end. Intuitively, it recomputes only the records affected by an input change and never falls back to a full recomputation. This makes update latency predictable even as the authorization graph grows. Larger than memory. Feldera maintains its internal state in persistent storage and uses memory as a cache. This allows it to process workloads whose state is much larger than available RAM, including multi-terabyte datasets on machines with only a few GiB of memory. Fast at scale. Feldera is designed for programs with many nested views operating over very large datasets. It can process high update rates while maintaining low-latency derived results, making it a good fit for continuously updated authorization indexes. Consistent. The output of a Feldera pipeline precisely reflects all inputs processed by the pipeline. It never exposes partial or inconsistent states. For the Permissions Index, this means users can determine when a change to the authorization graph has been fully evaluated and applied to the index. The following program shows how the FGA policy from our running example can be encoded in Feldera SQL: CREATE TABLE users id BIGINT NOT NULL PRIMARY KEY ; CREATE TABLE agents id BIGINT NOT NULL PRIMARY KEY ; CREATE TABLE groups id BIGINT NOT NULL PRIMARY KEY ; -- Object hierarchy. parent id models the parent relation between objects. CREATE TABLE objects id BIGINT NOT NULL PRIMARY KEY, parent id BIGINT ; -- member user, group — users and agents belonging to groups. CREATE TABLE members id BIGINT NOT NULL PRIMARY KEY, user id BIGINT NOT NULL, group id BIGINT NOT NULL ; -- owner object, group — groups that own objects. CREATE TABLE object owner object id BIGINT NOT NULL, group id BIGINT NOT NULL ; DECLARE RECURSIVE VIEW can view user id BIGINT NOT NULL, object id BIGINT NOT NULL ; CREATE MATERIALIZED VIEW can view AS -- can view: member from owner — a group member can view objects owned by the group. SELECT members.user id, object owner.object id FROM members JOIN object owner ON members.group id = object owner.group id UNION ALL -- can view: can view from parent — read access on a object inherits to its children. SELECT can view.user id, objects.id AS object id FROM can view JOIN objects ON can view.object id = objects.parent id ; The following diagram shows how Feldera is used to compute the Permissions Index. A Feldera pipeline incrementally evaluates the authorization policy by transforming a stream of changes to the authorization graph into a stream of changes to the Permissions Index. The pipeline definition is generated by converting the FGA model to a SQL program similar to the one above. Feldera represents both its inputs and outputs as streams of changes. It ingests updates to the authorization graph from FGA and outputs updates to the index. On startup, the pipeline ingests the entire contents of the authorization graph and computes the first set of updates that represent the initial Permissions Index contents. After that, the pipeline proceeds in smaller increments, converting new authorization graph changes into Permissions Index updates in real time. The pipeline annotates permission changes with freshness markers that let users measure end-to-end update latency and determine when a specific authorization graph change has been fully processed and reflected in the Permissions Index. The pipeline runs as a separate Kubernetes pod, providing strong isolation between workloads that belong to different tenants. Results To get a sense of the numbers, here are some initial results. The strength of incremental computation is clear: Feldera maintains a complex index of permissions on a single node and applies updates with sub-second latency, without recomputing the index from scratch. Directly assigned relations tuple change 4.5B+ Derived relations 5.4B+ Permissions index size 7.1B+ End-to-end index update latency Avg 194.57ms Max 5.46s Feldera pipeline resources Max used memory 58GB Max used storage 11.8TB Try it The Auth0 FGA Permissions Index is currently in Early Access . For more information: - Read Auth0’s announcement blog https://auth0.com/blog/auth0-fga-permissions-index-early-access/ - View our permissions index documentation https://docs.fga.dev/permissions-index/fga-permissions-index - Get started here https://docs.fga.dev/permissions-index/getting-started Learn More Feldera’s unique capabilities come from its foundation in DBSP, a mathematical framework for incremental computation. Just as relational algebra provides the foundation for conventional databases, DBSP provides a foundation for incremental query processing. The DBSP paper won the Best Paper Award at VLDB 2023, and the Feldera team develops an open-source implementation of DBSP as part of the Feldera project: