REVIEW 3 major objections 4 minor
The $\mathbf{P}$-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs
T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read 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
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The PN-Response: each node's result is a pair $\langle S, \text{type}\rangle$ where $S$ is a set of doc IDs and type is POS or NEG, meaning the actual result is $S$ or $U \setminus 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.
What would settle it
Run the algorithm on the query $\neg 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_{\text{active}}|)$ bound is false.
Extended reading notes
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_{\text{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|\cdot |U_{\text{active}}|)$, avoiding both the exponential unrolling of shared subexpressions and the universal scan penalty of disjunctive negation.
Load-bearing premise
The output-sensitive $O(|V|\cdot |U_{\text{active}}|)$ bound assumes complement sets like $U \setminus S$ are never actually materialized, yet the algorithm's own finalization and adaptive polarity steps explicitly construct such complements, which would cost $\Omega(|U|)$ work.
Editorial extensions
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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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.
- [§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)
- [§2.2] Typo: 'The W AND Limitation' should be 'The WAND Limitation'.
- [§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.
- [§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.
- [§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
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.
Assumptions & free parameters
free parameters (1)
- Adaptive leaf polarity threshold =
1/2 · |U|
assumptions (5)
- standard math Circuit Value Problem is logspace-complete for P
- domain assumption The input representation of the Retrieve problem encodes the universe U with size at least |U|
- domain assumption A stateful DAAT iterator cannot be shared across parents, forcing tree unrolling
- domain assumption Complement sets can be represented compactly without materializing U\S
- ad hoc to paper Any polynomial-time property over documents can be compiled into a query DAG of polynomial size
invented entities (1)
-
HyperNodes
Cite this review
Pith. "Pith review of The $\mathbf{P}$-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs." pith.science (2026). https://pith.science/paper/K5WVLTVP
@misc{pith2026260118747,
author = {Pith},
title = {Pith review of: The $\mathbfP$-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs},
year = {2026},
howpublished = {\url{https://pith.science/paper/K5WVLTVP}},
note = {Machine review of arXiv:2601.18747}
}
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
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.