Apple Paper Says Complex Boolean Search Queries Are P-Complete

發生了什麼事

Apple Machine Learning Research published a paper by Amir Aavani on the computational complexity of evaluating deeply nested, non-monotonic Boolean queries over inverted indexes. The paper formalizes a retrieval language based on directed acyclic graphs, claims its evaluation problem is strictly P-Complete, and introduces ComputePN, a deterministic algorithm using positive-negative representations and DAG memoization.

Apple Machine Learning Research lists the paper as published in August 2026, with Amir Aavani as its author. The paper addresses inverted-index traversal, a search technique in which terms point to documents containing them. Apple frames the problem around modern AI agents that use search infrastructure for complex, neuro-symbolic reasoning workflows. According to the source, those workflows can compile into deeply nested Boolean queries that include non-monotonic logic, including negation. The paper's focus is therefore the execution of structured retrieval logic, not a new language model, agent product, or consumer-facing search feature.

The paper describes two limits in standard evaluation strategies. It says stateful Document-at-a-Time iterator models are structurally bounded by NC^1 formula evaluation and can face a worst-case O(2^|Q|) exponential blowup when reconvergent logic is unrolled into a tree. It says recursive Term-at-a-Time materialization models face an Ω(|U|) space penalty, described as a universal scan, when evaluating logical negation over the full document universe. These are claims made by the paper's abstract. The supplied source does not provide examples, workload traces, empirical measurements, or a comparison showing how often either worst-case pattern occurs in deployed systems.

Apple says it formalizes a retrieval language, L_R, based on directed acyclic graphs and proves that evaluating queries in this language is strictly P-Complete. It then introduces ComputePN, described as a deterministic, sparsity-aware evaluation algorithm. The method separates logical negation from universe-scale materialization through a Positive-Negative dual representation and uses native DAG memoization so repeated subexpressions do not need to be expanded repeatedly.

The source gives a claimed evaluation-time bound of O(|Q| · |U_active|), where the notation refers to query size and the active document set. It does not include the algorithm's implementation, source code, measured constants, or operational requirements.

Taken together, the description covers the paper’s formal problem statement, its complexity result, and the proposed evaluation method. The retrieval language is represented with directed acyclic graphs, the stated difficulty concerns nested Boolean logic, and ComputePN is presented as the mechanism for handling that structure. The positive-negative representation addresses negation, while DAG memoization addresses repeated subexpressions. The source also states a bound in terms of query size and the active document set. Beyond those stated design and complexity points, the supplied material does not establish implementation details, measured performance, production use, or external validation. Those questions remain separate from the paper’s formal claims about evaluation.

來源詳情: machinelearning.apple.com ↗

為什麼這很重要

If the paper's claims hold in practical systems, they could clarify how search infrastructure should execute complex retrieval logic used in AI-agent workflows. The source claims ComputePN avoids two known costs: exponential expansion of reconvergent query logic and materializing the entire document universe for negation. It provides no production measurements, so the practical effect remains unverified.

The result matters because it puts a formal boundary around a problem Apple connects to AI-agent retrieval. Agents that combine search results with symbolic conditions may need more than simple keyword matching: they may express nested intersections, unions, and exclusions whose logic naturally forms a graph with shared subexpressions. A graph representation can preserve that sharing, while a tree expansion can duplicate it. If ComputePN works as claimed, the paper offers a principled way to evaluate such logic without automatically paying either the exponential expansion cost or a full-universe materialization cost. The potential practical benefit is most relevant to systems where query complexity, corpus size, and sparsity interact.

Avoiding a scan of every document could reduce memory pressure for negation-heavy queries, while memoizing shared DAG nodes could prevent repeated work. The claimed bound also focuses on the active document set rather than the entire universe, which could be important for selective queries. These implications follow from the algorithmic design described by Apple, not from a demonstrated product improvement. The source reports no latency reduction, throughput increase, cost saving, energy result, or user outcome.

The paper is consequential as a research contribution, but its public impact is still uncertain. It does not announce a product launch or say that Apple has integrated ComputePN into a customer-facing search service. It also does not establish that existing search engines or agent platforms use the exact query language modeled in the paper. No independent confirmation is included in the supplied material. The practical value will depend on whether the formal model matches production workloads, whether the algorithm's constants are acceptable, and how it behaves when queries, indexes, and active sets are large or highly interconnected.

接下來看什麼

The important next evidence is implementation and benchmarking: real query graphs, corpus sizes, active-document counts, latency, memory use, and comparisons with existing Document-at-a-Time and Term-at-a-Time systems. The source does not identify software, an API, a deployment, a peer-review venue, or adoption by a search or AI product.

The first question is whether the claimed complexity advantages translate into measured system performance. Useful follow-up evidence would include benchmark corpora, query-generation procedures, distributions of DAG depth and reconvergence, document-universe sizes, active-set sizes, peak memory, and end-to-end latency. Comparisons should include both Document-at-a-Time and Term-at-a-Time baselines, along with adversarial cases involving repeated subexpressions and broad negation. The current source supplies asymptotic claims but none of those measurements.

The second question is whether ComputePN exists as usable software. Apple’s page does not link to a repository, package, API, technical implementation, or instructions for reproducing the results. It also does not state whether the method can be added to established inverted-index engines, whether it requires a new index layout, or whether it supports updates, ranking, filtering, distributed execution, or concurrent queries. Those omissions make it impossible from this source to assess deployment readiness or compatibility with existing retrieval stacks.

The third question is validation and scope. The page names the work as a published paper but does not identify a conference, journal, review process, or external replication. Future disclosures should clarify the precise retrieval language, the assumptions behind the active-document representation, and the behavior of the positive-negative structure under dense or nearly universal matches. It will also be important to see whether AI-agent systems actually generate the kind of Boolean query DAGs described, and whether the proposed method improves reliability or only establishes a theoretical evaluation path.

相關指引和測驗