神经符号代理的理论瓶颈
基于神经符号原理构建的现代AI代理，越来越多地将搜索基础设施用作外部记忆。在此过程中，推理链并非编译为简单的关键词集合，而是编译为带有否定与分支的深度嵌套布尔查询。这类查询对程序员来说显得自然，但对经典倒排索引而言，它们构成了严峻的挑战。
阿米尔·阿瓦尼近期在arXiv上发布的预印本（2601.18747，最新版本日期为2026年8月17日）表明，问题并不在于搜索引擎开发者的懈怠。作者将查询语言L_R形式化为有向无环图，并严格证明：在索引上评估此类查询是一个P-完全问题。换言之，在一般情况下，这一过程很难在多个核心上高效并行化——除非P类与NC类恰好相等，而大多数理论家认为这极不可能。
该研究同时涉及多个领域——信息检索、人工智能、计算复杂性理论、自然语言处理以及数据库。这并非偶然：问题正位于AI与经典搜索技术的交汇处。
两种传统方法及其弱点
当查询在倒排索引上执行时，通常采用两种策略之一：按文档迭代处理（Document-at-a-Time）或按词项物化中间列表（Term-at-a-Time）。每种方法都有自己的“难言之隐”。
- Document-at-a-Time依赖于带状态的迭代器，这些迭代器在排序后的文档列表中推进。事实证明，这类迭代器在结构上受限于NC¹电路类。如果查询逻辑中出现再汇聚分支——即图中多条路径汇聚到同一节点——将这些分支朴素地展开为树会导致指数爆炸：最坏情况下的复杂度达到O(2^{|Q|})，其中|Q|为查询规模。
- Term-at-a-Time试图以不同方式解决问题：每个查询节点被物化为文档列表。但要计算逻辑否定，这种方法必须了解整个文档全集|U|，才能知道哪些文档不在结果中。由此产生**Ω(|U|)**的代价——即所谓的全集扫描。在大型集合中，这意味着为了一个“非”而实际遍历整个数据库。
因此，两种经典方法各自能胜任有限角色，但在非单调的DAG查询上，它们要么受制于时间，要么受制于空间。此前人们一直认为，这是表达力所不可避免的代价。
ComputePN算法
阿米尔·阿瓦尼提出了一种迂回策略——确定性算法ComputePN，专门针对稀疏数据优化。核心思想在于将逻辑否定与全集物化分离开来。ComputePN并非构建“所有不存在的文档”的完整列表，而是利用每个节点的对偶表示：“正-负”二元组既存储进入结果的内容，也存储保证不进入结果的内容。
这种方法使得只需考虑活跃文档——即实际参与计算的文档。中间结果直接在查询图上进行记忆化，因此相同的子表达式不会被重复计算。最终复杂度估计为O(|Q| · |U_active|)，其中U_active为受影响文档的集合，而非整个全集。
在实践中，这意味着带有否定与汇聚分支的重型案例不再致命。如果真实集合规模庞大，但查询仅触及其中一小部分，ComputePN仍能保持高效。
这对搜索引擎和AI意味着什么
该研究的核心结论并非倒排索引的遍历在根本上无法加速。恰恰相反：作者展示了如何原生计算P-完全查询，同时避开两大陷阱——组合式树展开以及为求否定而扫描全部文档。
对于混合神经符号系统而言，这是一个重要信号。LLM代理生成的查询日益复杂，搜索后端必须能够在不发生灾难性退化的情况下为其提供服务。理论上的P-完全性仍然是对并行架构开发者的警示，但ComputePN表明，精巧的工程实现能够绕开最坏场景。
不过，在该算法进入生产系统之前，仍有大量工作要做。所提出的方案需要在真实搜索引擎层面精细处理对偶表示与记忆化。但该问题终于获得了严格的理论基础，这本身就意义重大：如今开发者至少知道自己面对的是何种复杂度，以及哪些技巧确实有效。
