Apple proves Boolean query DAGs are P-complete, runs one in 0.8s

Apple’s machine learning group has published a paper proving that evaluating Boolean query graphs over an inverted index is P-complete, alongside an algorithm that ran one such query against 8.8 million documents in 0.8 seconds. The paper sits on Apple Machine Learning Research dated August 2026, and its third version landed on arXiv on 17 August.

The author is Amir Aavani of Apple Inc. He formalises a retrieval language called L_R, built on directed acyclic graphs rather than trees, then gives a logarithmic-space reduction from the Circuit Value Problem to its evaluation. That reduction is what earns the P-complete label, which puts the problem among the hardest still solvable in polynomial time.

That matters because AI agents keep compiling their reasoning into deeply nested Boolean constraints over text fields. The paper argues that fixed-dimension embedding spaces can’t reliably enforce strict logical exclusions, so the inverted index stays the layer that has to guarantee them. Both standard ways of evaluating those queries hit a wall.

Document-at-a-Time engines advance stateful iterators across posting lists, and Aavani bounds them by NC^1 formula evaluation. Term-at-a-Time engines materialise one node at a time instead, which costs universe-scale space the moment a negation appears.

Evaluation strategy	Where the paper says it breaks	Bound given
Document-at-a-Time (DAAT)	Re-convergent logic unrolled into a query tree	O(2^|Q|) time
Term-at-a-Time (TAAT)	Negation evaluated over the document universe	Ω(|U|) space
ComputePN (proposed)	Neither, per the paper’s analysis	O(|Q| · |U_active|) time

ComputePN gets around both by keeping a Positive-Negative dual representation of each result set and memoising shared gates in the DAG. To test it, Aavani ran a stress test on the MS MARCO passage corpus, which Microsoft’s own page puts at 8.8 million passages. An LLM acting as a heuristic query compiler wired together a 500-node Boolean DAG simulating parallel ripple-carry adders and a magnitude comparator.

Unrolled into a query tree, that circuit produced over 10,000 clauses, and there the existing engines stop. Apache Lucene’s IndexSearcher permits 1,024 clauses per query by default and throws an exception past that, so the unrolled version never executed. ComputePN evaluated the same logic natively as a DAG in 0.8 seconds, on what the paper describes only as standard hardware.

This test proves that the failure of standard engines on re-convergent logic is a fundamental algorithmic limit, not an implementation artifact.

Amir Aavani, Apple Inc., in the paper

Even so, the paper calls this a feasibility proof of concept, and the 0.8 second figure is worth reading that way. There’s no timing comparison against a working baseline, because the baseline didn’t run at all. Aavani also states that no canonical benchmark exists for re-convergent, non-monotonic Boolean DAGs, since BEIR and TREC were designed for flat keyword or semantic similarity queries.

The reach of the argument goes past search engines, though. PostgreSQL’s GIN, which the documentation expands as Generalized Inverted Index, does the same job inside a relational database, and Aavani cites it as one of the engines subject to the same limits. Teams weighing Postgres against a dedicated vector store are choosing between the same two families.

The pattern the paper attacks instead is fetch-and-filter, where an agent pulls the top results and applies the strict constraints in the application layer or the model’s context window. Aavani’s objection is recall, because valid documents can sit at rank 50,000 and never get fetched. That’s a familiar trade for anyone who has weighed a bigger context window against retrieval.

What to watch is whether anyone builds the benchmark Aavani says is missing. Until then a single sub-second run on one corpus stays a proof of concept, not a number other engines can be measured against.