The $\mathbf{P}$-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs

What Happened

A new arXiv paper establishes that evaluating Boolean query DAGs over inverted indexes—the core operation behind many modern search and retrieval systems—is P-complete. This formal result proves that inverted index traversal for complex, nested Boolean queries cannot be efficiently parallelized or significantly accelerated in the worst case, as P-complete problems are inherently sequential under standard complexity assumptions.

The paper specifically addresses the growing trend of AI agents compiling neuro-symbolic reasoning workflows into deeply nested, non-monotonic Boolean queries over text fields. As these workflows become more sophisticated, the underlying query structures grow in complexity, pushing against fundamental computational limits.

Why It Matters

This finding has immediate practical consequences for AI infrastructure. Modern retrieval-augmented generation (RAG) systems, agentic search pipelines, and knowledge graph query engines all rely on inverted indexes as their backbone. The P-completeness result means that as these systems scale to handle more complex reasoning tasks, they cannot simply throw more parallel hardware at the problem to achieve linear speedups.

The paper’s focus on non-monotonic Boolean queries is particularly significant. Monotonic queries (e.g., simple AND/OR combinations) have well-known optimization strategies. Non-monotonic operators—such as negation, difference, or set subtraction—break many traditional pruning and caching techniques, forcing the query evaluator to process larger portions of the index.

For AI practitioners building agentic systems that chain multiple retrieval steps, this creates a hard ceiling: each additional reasoning step that compiles into a non-monotonic query adds complexity that cannot be amortized away through parallelism alone.

Implications for AI Practitioners

Query design becomes a first-class optimization target. Teams building neuro-symbolic systems must now treat query compilation as seriously as model architecture. Converting non-monotonic operations into monotonic equivalents where possible, or restructuring reasoning chains to avoid deeply nested negations, could yield disproportionate performance gains. Index architecture requires rethinking. Traditional inverted indexes optimized for flat Boolean queries may need structural changes. Pre-computed partial results, materialized views, or hybrid vector-Boolean indexes could help bypass the worst-case complexity, though these come with storage and maintenance trade-offs. Latency budgets must account for query complexity. AI agents that dynamically generate queries should include query complexity estimation as a routing signal. Simple queries can use fast paths; complex ones may need dedicated resources or fallback strategies. Parallelism is not a silver bullet. While some parallelism helps, the P-completeness result suggests diminishing returns. Practitioners should focus on algorithmic improvements—better pruning, query rewriting, and caching—rather than assuming more GPUs or CPU cores will solve the problem.

Key Takeaways

• Boolean query DAG evaluation over inverted indexes is P-complete, meaning it cannot be efficiently parallelized in the worst case.
• Non-monotonic queries (with negation, difference) are the primary driver of complexity, not simple AND/OR combinations.
• AI practitioners must treat query compilation as a critical optimization lever, not just an implementation detail.
• Infrastructure teams should invest in query rewriting, caching, and hybrid index architectures rather than relying solely on hardware scaling.