Pith. sign in

REVIEW 3 major objections 4 minor 28 references

This paper argues that evaluating Boolean query DAGs over an inverted index is P-complete, and that its ComputePN algorithm evaluates them in time proportional to the union of postings referenced by the query, provided complements are never

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 07:54 UTC pith:K5WVLTVP

load-bearing objection The P-completeness proof is a standard CVP restatement, and the headline sparsity bound has two unstated universe-scale steps, but the PN algebra is a clean idea with a credible core. the 3 major comments →

arxiv 2601.18747 v2 pith:K5WVLTVP submitted 2026-01-26 cs.IR cs.AIcs.CCcs.CLcs.DB

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

Amir Aavani This is my paper
classification cs.IR cs.AIcs.CCcs.CLcs.DB
keywords Boolean retrievalquery DAGP-completenessinverted indexnegationsparsity-aware evaluationpositive-negative representationcomputational complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tries to show that the problem of evaluating Boolean queries over an inverted index—where queries are directed acyclic graphs of AND, OR, and NOT—is complete for the complexity class P, meaning it is as hard as any polynomial-time problem. To make this theoretically hard task practical, it introduces ComputePN, an algorithm that keeps evaluated sets sparse by storing results in a dual positive/negative representation. If the main bound holds, any query that can be decided in polynomial time could be compiled into a query DAG and run directly on the index in time proportional to the documents actually touched by the query's terms, avoiding both exponential tree expansion and the universe-scale scan that standard negation requires.

Core claim

The paper proves that the query evaluation problem for L_R, the language of Boolean query DAGs over an inverted index, is P-complete: P-hard by reduction from the Circuit Value Problem, and in P by a naive materialization algorithm. The central practical discovery is ComputePN, which evaluates any such DAG while keeping materialized sets bounded by U_active, the union of posting lists of query terms, by pairing each set with a polarity flag (POS/NEG) so that negation simply flips the flag, and by memoizing DAG nodes. The claimed time bound is O(|V|·|U_active|), avoiding both the exponential unrolling of shared subexpressions and the universal scan penalty of disjunctive negation.

What carries the argument

The PN-Response: each node's result is a pair ⟨S, type⟩ where S is a set of doc IDs and type is POS or NEG, meaning the actual result is S or U\S. The evaluation algebra defines set operations on these pairs (intersection, union, difference with flipped flags) so negations are metadata flips and no materialized set ever exceeds the union of children. Combined with topological traversal and memoization, this is what the complexity bound rests on.

Load-bearing premise

The output-sensitive O(|V|·|U_active|) bound assumes complement sets like U\S are never actually materialized, yet the algorithm's own finalization and adaptive polarity steps explicitly construct such complements, which would cost Ω(|U|) work.

What would settle it

Run the algorithm on the query ¬T where term T appears in one document, over collections of increasing total size but with that one posting fixed; if wall-clock time grows with collection size, a universal scan is happening and the O(|U_active|) bound is false.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any problem in P can in principle be compiled into a query DAG and evaluated over an inverted index, so retrieval engines could perform arithmetic, comparison, and other logic natively rather than fetching large candidate sets.
  • Standard iterator-based engines cannot share DAG nodes without cloning, so re-convergent queries incur exponential tree expansion; the DAG-with-memoization model avoids that blowup.
  • Disjunctive negation like A∨¬B costs O(|A|+|B|) instead of Ω(|U|), removing the universal scan penalty for queries that include implications or exclusions.
  • The language stays below Turing-complete, so worst-case execution time remains polynomially bounded, which suits latency-critical retrieval systems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The paper's own algorithm description materializes U\S_root when the root is NEG, and builds negative leaves for high-frequency terms as ⟨U\I(t), NEG⟩; unless those complements are represented lazily, the strict O(|U_active|) bound only holds for positive-rooted queries over low-frequency terms.
  • A concrete test would be to run ComputePN with a negative root (e.g., ¬T) while growing corpus size but keeping T's posting list fixed; if runtime grows with corpus size, a universal scan is occurring and the output-sensitive claim fails.
  • The dual-representation idea could extend to other domains that mix sparse positive evidence with dense negative constraints, such as access-control filters or incremental view maintenance, where lazy complement sets might preserve sparsity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper formalizes a Boolean retrieval language L_R based on query DAGs over an inverted index, proves its decision problem P-complete via a LogSpace reduction from the Circuit Value Problem (Theorem 1, Section 3.2), and proposes ComputePN (Section 4), a memoized bottom-up evaluator that stores each sub-result as a Positive-Negative (PN) pair to avoid materializing complement sets during traversal. The central efficiency claim is Theorem 2 (Section 4.4): ComputePN evaluates any L_R query in O(|V|·|U_active|) time, where U_active is the union of posting lists of terms appearing in the query, thus avoiding both the DAAT tree-expansion blowup and the TAAT universal-scan penalty. The paper also sketches an LLM-based 'computational retrieval' architecture (Section 6) and reports a 0.8s stress-test execution of a 500-node arithmetic DAG on MS MARCO (Section 5.3).

Significance. The P-completeness argument is sound: the CVP reduction in Section 3.2 is a standard LogSpace construction, and the algebraic rules in Section 4.2 for combining PN-responses at internal nodes are correct and preserve sparsity. If the O(|V|·|U_active|) bound of Theorem 2 held, the work would be a meaningful theoretical contribution to executing complex Boolean logic natively over inverted indices, and the contrast with DAAT/TAAT limits is well motivated. However, the algorithm as specified does not achieve the claimed bound because two explicit steps—§4.3 root finalization and §4.5 Adaptive Leaf Polarity—materialize universe-scale complement sets. The main computational claim is therefore not established in the current form.

major comments (3)
  1. [§4.4 / Theorem 2] The proof of Theorem 2 relies on the invariant that for every node v, S_v ⊆ U_active. This invariant holds for the internal algebraic rules in §4.2, but it is broken by the algorithm's own finalization step in §4.3: if the root has type NEG, step 4 materializes U\S_root. For a query such as Q = ¬t with a rare term t, |U\S_root| = Θ(|U|), which can be arbitrarily larger than |U_active|. Thus the claimed O(|V|·|U_active|) bound is false for the algorithm as written, and the 'no universal scan' claim in the abstract fails for any NEG root whose answer is large.
  2. [§4.5 / Adaptive Leaf Polarity] Adaptive Leaf Polarity explicitly constructs negative leaves as ⟨U\I(t), NEG⟩ when |I(t)| > |U|/2. This materialized set is not a subset of U_active and computing it requires Ω(|U|) work, again outside the Theorem 2 bound. The paper presents this as a sparsity-preserving optimization, but it actually injects universe-scale data into the traversal and invalidates the induction in the proof: the base case S_leaf ⊆ U_active is violated. The same violation occurs even before considering root finalization, so the theorem's invariant is not maintained by the full algorithm.
  3. [§4.1–§4.4 / Output semantics] There is a conflation between computing a compressed PN-representation and materializing the actual result set. Definition 4.1 states that S_v is a 'materialized set', and §4.3 returns S_root or U\S_root as the final output. If the intended output is the PN-representation, the O(|V|·|U_active|) claim may be salvageable, but then the algorithm does not solve the stated retrieval problem of returning D(r,I) as a set. If the intended output is the set, any algorithm must spend Ω(|result|) time, and queries like ¬t have |result| = Ω(|U|); no output-sensitive bound w.r.t. U_active can hold. The manuscript should state which variant is being analyzed and adjust the theorem and abstract accordingly.
minor comments (4)
  1. [§2.2] Typo: 'The W AND Limitation' should be 'The WAND Limitation'.
  2. [§4.2] The cost of set operations is asserted as O(|S_L|+|S_R|), but the underlying data structure (sorted lists vs. bitmaps) is unspecified. This is fine for the asymptotic argument, but the practical claims in §5 depend on constant factors; a sentence on the assumed representation would help.
  3. [§5.3] The empirical validation is very thin: no hardware, index implementation, baseline runtime, or code is provided, and the single 0.8s measurement for a 500-node DAG does not by itself validate the theoretical bounds. If the empirical claim is to be retained, the setup and reproducibility details should be expanded.
  4. [§6.3] The phrase 'massively parallel SIMD memory' and the 'HyperNodes' concept are introduced without formal definition; while presented as a vision, the paper should clarify whether these are part of L_R or purely suggestive.

Circularity Check

0 steps flagged

No significant circularity; self-citation [1] is motivational and not load-bearing, and the hardest issues in Theorem 2 are correctness gaps rather than derivation-by-construction.

full rationale

The main derivation chain is independent: Theorem 1 uses the standard external CVP P-completeness result (Ladner) to prove P-hardness with a one-document universe, and the upper bound is given by the naive TAAT polynomial-time algorithm. ComputePN's complexity claim is argued from an internal induction over the PN-algebra rather than from a fitted parameter or a prior uniqueness theorem. The only self-citation, [1] (Aavani et al.), appears in §4.1 as motivation ('This dual representation strategy is motivated by the optimization techniques used in Logic Program Grounding [1]'); no load-bearing theorem is imported from that citation. There is, however, a serious rigor gap in Theorem 2's proof: the invariant that all materialized sets stay inside U_active is contradicted by §4.3 step 4 (materializing U\S_root for a NEG root) and by §4.5 Adaptive Leaf Polarity (which builds ⟨U\I(t),NEG⟩). This makes the O(|V|·|U_active|) bound unproved for negative roots and high-frequency terms, and the 'no universal scan' claim vulnerable for those cases. That is a correctness/assumption problem, not a circularity: the bound is not obtained by re-labelling an input, fitting data, or importing the conclusion from a self-citation. No equation reduces to another by construction, so the circularity-specific score is low; the issues belong in a correctness review.

Axiom & Free-Parameter Ledger

1 free parameters · 5 axioms · 1 invented entities

The central claims rest on standard CVP completeness plus several domain assumptions about index representation, iterator statefulness, and symbolic complement handling. There are no fitted constants except the hand-picked adaptive-polarity threshold; the main unacknowledged gap is that two algorithm steps materialize universe-sized sets despite the stated sparsity guarantee.

free parameters (1)
  • Adaptive leaf polarity threshold = 1/2 · |U|
    Chosen in §4.5 to decide when to represent a leaf as a negative response; not fitted to data, but an arbitrary design constant affecting the algorithm's materialization behavior.
axioms (5)
  • standard math Circuit Value Problem is logspace-complete for P
    Used in Theorem 1 to prove P-hardness; standard result cited as [12].
  • domain assumption The input representation of the Retrieve problem encodes the universe U with size at least |U|
    Invoked in §3.3 to argue the naive O(|Q|·U) algorithm is polynomial; not guaranteed for a sparse inverted index where U can be much larger than the encoded postings.
  • domain assumption A stateful DAAT iterator cannot be shared across parents, forcing tree unrolling
    Underlies the claimed O(2^{|Q|}) tree-expansion bottleneck in §2.2/§5.1; this is a model of Lucene-style iterators, not a universal law for all conceivable iterator designs.
  • domain assumption Complement sets can be represented compactly without materializing U\S
    The PN semantics defines the result as U\S while claiming materialized sets stay inside U_active; the finalization and adaptive-leaf steps in §4.3/§4.5 contradict a fully symbolic treatment.
  • ad hoc to paper Any polynomial-time property over documents can be compiled into a query DAG of polynomial size
    Section 6 assumes an LLM can compile arbitrary arithmetic constraints into compact Boolean DAGs; no proof or size bound is given for realistic documents.
invented entities (1)
  • HyperNodes no independent evidence
    purpose: Macro-like computational gadgets (e.g., macroDotProductGE) that expand into Boolean logic subgraphs to compile vector/embedding operations inside L_R.
    Introduced in §6.4 as a proposed mechanism for vector emulation; no implementation or external falsifiable prediction is provided.

pith-pipeline@v1.3.0-alltime-deepseek · 13914 in / 17195 out tokens · 185390 ms · 2026-08-03T07:54:18.524585+00:00 · methodology

0 comments
read the original abstract

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 $\text{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 $\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 ($\mathcal{L}_R$) based on Directed Acyclic Graphs (DAGs) and prove that its evaluation problem is strictly \textbf{$\mathbf{P}$-Complete}. To make evaluation tractable, we introduce \texttt{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, \texttt{ComputePN} strictly bounds evaluation time to $O(|Q| \cdot |U_{\mathit{active}}|)$. This approach successfully evaluates $\mathbf{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.

Figures

Figures reproduced from arXiv: 2601.18747 by Amir Aavani.

Figure 1
Figure 1. Figure 1: The Tree-Expansion Bottleneck. Left: DAG execu [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 2 linked inside Pith

  1. [1]

    In: International Conference on Logic for Programming Artificial Intelligence and Reasoning

    Aavani, A., Tasharrofi, S., Unel, G., Ternovska, E., Mitchell, D.: Speed-up tech- niques for negation in grounding. In: International Conference on Logic for Programming Artificial Intelligence and Reasoning. pp. 13–26. Springer (2010)

    2010

  2. [2]

    Addison-Wesley, Reading, MA (1995)

    Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading, MA (1995)

    1995

  3. [3]

    Addison- Wesley (1999)

    Baeza-Yates, R.A., Ribeiro-Neto, B.A.: Modern Information Retrieval. Addison- Wesley (1999)

    1999

  4. [4]

    In: Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval

    Białecki, A., Muir, R., Ingersoll, G.: Apache lucene 4. In: Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 1005–1005 (2012)

    2012

  5. [5]

    In: Proceedings of the twelfth inter- national conference on Information and knowledge management

    Broder, A.Z., Carmel, D., Herscovici, M., Soffer, A., Zien, J.: Efficient query eval- uation using a two-level retrieval process. In: Proceedings of the twelfth inter- national conference on Information and knowledge management. pp. 426–434 (2003)

    2003

  6. [6]

    Software: Practice and Experience46(5), 709–719 (2016)

    Chambi, S., Lemire, D., Kaser, O., Godin, R.: Better bitmap performance with roaring bitmaps. Software: Practice and Experience46(5), 709–719 (2016)

    2016

  7. [7]

    Pearson (2010)

    Croft, W., Metzler, D., Strohmann, T.: Search Engines: Information Retrieval in Practice. Pearson (2010)

    2010

  8. [8]

    In: Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers)

    Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidi- rectional transformers for language understanding. In: Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers). pp. 4171–4186 (2019)

    2019

  9. [9]

    IEEE Transac- tions on Computers100(9), 948–960 (1972)

    Flynn, M.J.: Some computer organizations and their effectiveness. IEEE Transac- tions on Computers100(9), 948–960 (1972)

    1972

  10. [10]

    In: Proceedings of the 2023 Con- ference on Empirical Methods in Natural Language Processing

    Jiang, Z., Xu, F.F., Gao, L., Sun, Z., Liu, Q., Dwyer, J., Zhu, M., Zhang, M., Neubig, G.: Active retrieval augmented generation. In: Proceedings of the 2023 Con- ference on Empirical Methods in Natural Language Processing. pp. 7969–7992 (2023)

    2023

  11. [11]

    In: EMNLP (1)

    Karpukhin, V., Oguz, B., Min, S., Lewis, P.S., Wu, L., Edunov, S., Chen, D., Yih, W.t.: Dense passage retrieval for open-domain question answering. In: EMNLP (1). pp. 6769–6781 (2020)

    2020

  12. [12]

    In: ACM SIGACT News

    Ladner, R.E.: The circuit value problem is log space complete for p. In: ACM SIGACT News. vol. 7, pp. 18–20. ACM (1975)

    1975

  13. [13]

    In: Advances in Neural Information Processing Systems

    Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.t., Rocktäschel, T., Riedel, S., Kiela, D.: Retrieval-augmented gen- eration for knowledge-intensive NLP tasks. In: Advances in Neural Information Processing Systems. vol. 33, pp. 9459–9474 (2020)

    2020

  14. [14]

    Transactions of the Association for Computational Linguistics12, 157–173 (2024)

    Liu, N.F., Lin, K., Hewitt, J., Paranjape, A., Bevilacqua, M., Petroni, F., Liang, P.: Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics12, 157–173 (2024)

    2024

  15. [15]

    Cambridge University Press (2008)

    Manning, C.D., Raghavan, P., Schütze, H.: Introduction to Information Retrieval. Cambridge University Press (2008)

    2008

  16. [16]

    MIT Press, Cambridge, MA (1969)

    Minsky, M., Papert, S.: Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, MA (1969)

    1969

  17. [17]

    Founda- tions and Trends®in Information Retrieval13(1), 1–126 (2018)

    Mitra, B., Craswell, N.: An introduction to neural information retrieval. Founda- tions and Trends®in Information Retrieval13(1), 1–126 (2018)

    2018

  18. [18]

    ACM Transactions on Information Systems (TOIS)14(4), 349–379 (1996)

    Moffat, A., Zobel, J.: Self-indexing inverted files for fast text retrieval. ACM Transactions on Information Systems (TOIS)14(4), 349–379 (1996)

    1996

  19. [19]

    In: Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data

    O’Neil, P., Quass, D.: Quasidistributed Bit-Sliced index arithmetic. In: Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data. pp. 47–58 (1997)

    1997

  20. [20]

    In: Proceedings of the 8th International Symposium on Spatial and Temporal Databases (SSTD)

    Procopiuc, O., Agarwal, P.K., Arge, L., Vitter, J.S.: Bkd-Tree: A dynamic scalable kd-tree. In: Proceedings of the 8th International Symposium on Spatial and Temporal Databases (SSTD). pp. 46–65. Springer (2003)

    2003

  21. [21]

    Communications of the ACM18(11), 613–620 (1975)

    Salton, G., Wong, A., Yang, C.S.: A vector space model for automatic indexing. Communications of the ACM18(11), 613–620 (1975)

    1975

  22. [22]

    arXiv preprint arXiv:2208.03197 (2022)

    Shen, X., Vakulenko, S., Del Tredici, M., Barlacchi, G., Byrne, B., de Gispert, A.: Low-resource dense retrieval for open-domain question answering: A compre- hensive survey. arXiv preprint arXiv:2208.03197 (2022)

    Pith/arXiv arXiv 2022

  23. [23]

    arXiv preprint arXiv:2501.09136 (2025)

    Singh, A., Ehtesham, A., Kumar, S., Khoei, T.T.: Agentic retrieval-augmented generation: A survey on agentic rag. arXiv preprint arXiv:2501.09136 (2025)

    Pith/arXiv arXiv 2025

  24. [24]

    arXiv preprint arXiv:2508.21038 (2025)

    Weller, O., Boratko, M., Naim, I., Lee, J.: On the theoretical limitations of embedding-based retrieval. arXiv preprint arXiv:2508.21038 (2025)

    arXiv 2025

  25. [25]

    Morgan Kaufmann (1999)

    Witten, I.H., Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann (1999)

    1999

  26. [26]

    In: International Conference on Learning Representations (ICLR) (2023)

    Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., Cao, Y.: React: Syner- gizing reasoning and acting in language models. In: International Conference on Learning Representations (ICLR) (2023)

    2023

  27. [27]

    arXiv preprint arXiv:2506.14852 (2025)

    Zhang, Q., Wornow, M., Olukotun, K.: Cost-efficient serving of llm agents via test-time plan caching. arXiv preprint arXiv:2506.14852 (2025)

    arXiv 2025

  28. [28]

    Zhang, Z., Zhu, J., Zhou, W., Qi, X., Zhang, P., Li, H.: Boolquestions: Does dense retrieval understand boolean logic in language? In: Findings of the Association for Computational Linguistics: EMNLP 2024. pp. 2767–2779 (2024)

    2024