mlsanityData to 14 Oct 2026

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

arXiv 2601.18747 ↗First posted 26 Jan 2026cs.IR cs.AI cs.CCcited by 1

On the map: LLM reasoning → Knowledge- and tool-augmented reasoning

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.

Key facts. Cited by 1 paper 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.

Builds on

10 of 35 references.

References · 10

  1. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,297
  2. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,170
  3. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  4. 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,824
  5. 2016MS MARCO: A Human Generated MAchine Reading COmprehension Datasetcited by 1,605
  6. 2019Passage Re-ranking with BERTcited by 645
  7. 2025On the Theoretical Limitations of Embedding-Based Retrievalcited by 104
  8. 2022Neural Approaches to Conversational Information Retrievalcited by 42
  9. 2022Low-Resource Dense Retrieval for Open-Domain Question Answering: A Comprehensive Surveycited by 14
  10. 2014Better bitmap performance with Roaring bitmapscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026SoK: Agentic Retrieval-Augmented Generation (RAG): Taxonomy, Architectures, Evaluation, and Research Directionscited by 8

Similar, not cited

Close in wording, no citation either way

  1. 2024A Categorization of Complexity Classes for Information Retrieval and Synthesis Using Natural Logic
  2. 2026OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning
  3. 2026Compute Allocation for Reasoning-Intensive Retrieval Agents
  4. 2026Rethinking Agentic RAG: Toward LLM-Driven Logical Retrieval Beyond Embeddings
  5. 2025Enhancing Retrieval Systems with Inference-Time Logical Reasoning
  6. 2026ROG: Retrieval-Augmented LLM Reasoning for Complex First-Order Queries over Knowledge Graphs
  7. 2026Breaking the Evaluation Paradox: Evaluating High-Entropy Search with Computationally Irreducible Constraints
  8. 2026Boolean queries are all you need? ↗