# The P-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs

arXiv: https://arxiv.org/abs/2601.18747 · HTML: https://mlsanity.com/paper/2601.18747/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 26 Jan 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 10 of 10)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [Passage Re-ranking with BERT](https://mlsanity.com/paper/1901.04085/) (2019)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [Neural Approaches to Conversational Information Retrieval](https://mlsanity.com/paper/2201.05176/) (2022)
- [Low-Resource Dense Retrieval for Open-Domain Question Answering: A Comprehensive Survey](https://mlsanity.com/paper/2208.03197/) (2022)
- [Better bitmap performance with Roaring bitmaps](https://mlsanity.com/paper/1402.6407/) (2014)

## Built on by (most cited first, 1 of 1)

- [SoK: Agentic Retrieval-Augmented Generation (RAG): Taxonomy, Architectures, Evaluation, and Research Directions](https://mlsanity.com/paper/2603.07379/) (2026)

## Abstract (arXiv)

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 NC1 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 Omega(|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 (LR) based on Directed Acyclic Graphs (DAGs) and prove that its evaluation problem is strictly textbfP-Complete. To make evaluation tractable, we introduce textttComputePN, 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, textttComputePN strictly bounds evaluation time to O(|Q| · |U_mathitactive|). 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.