The P-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs
AuthorsAmir Aavani
The P-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs
AuthorsAmir Aavani
Modern AI agents increasingly rely on search infrastructure to execute complex, neuro-symbolic reasoning workflows. These workflows often compile into deeply nested, non-monotonic Boolean queries over text fields. However, standard query evaluation strategies over inverted indices face severe theoretical limits when handling these structures. Stateful iterator models (Document-at-a-Time) are structurally bounded by NC^1 formula evaluation, suffering a worst-case O(2^|Q|) exponential blowup in query complexity when unrolling re-convergent logic. Conversely, recursive materialization models (Term-at-a-Time) incur an Ω(|U|) space complexity penalty (the Universal Scan) when evaluating logical negation over the document universe.
In this paper, we establish the theoretical boundaries of executing complex logic natively over an inverted index. We formalize a retrieval language (L_R) based on Directed Acyclic Graphs (DAGs) and prove that its evaluation problem is strictly P-Complete. To make evaluation tractable, we introduce ComputePN, a deterministic, sparsity-aware evaluation algorithm. By decoupling logical negation from universe-scale materialization via a novel Positive-Negative dual representation, and utilizing native DAG memoization, ComputePN strictly bounds evaluation time to O(|Q| · |U_active|). This approach successfully evaluates P-Complete queries natively over the index, avoiding both the combinatorial tree-expansion bottleneck and the universal scan penalty, laying the formal foundation for computational retrieval.
Toward a Theory of Evaluability
November 10, 2026research area Methods and Algorithmsconference NeurIPS
Machine learning models, particularly large foundation models, are increasingly evaluated along multiple axes that are relevant for their usage. In addition to accuracy measures appropriate for the specific task of interest, measures capturing safety, calibration and fairness properties are often of interest. The classical approach to these problems assumes that the test set has been held out from the training process, an assumption that is…
Faster Retrieval for Better, More Efficient RAG
November 5, 2026conference ICML
Maximum inner product search (MIPS) sits at the core of recommendation systems, search, and retrieval-augmented generation (RAG). Given a query vector, MIPS systems search within a database of millions of candidate key vectors for the one that best matches the query. The original data point associated with that best-matching key is then used to handle the query: in RAG, the document that is best suited to answer the question is typically prefixed…