详细内容或原文请订阅后点击阅览
倒排索引遍历的 P 完备性：论评估布尔查询 DAG 的复杂性
现代人工智能代理越来越依赖搜索基础设施来执行复杂的神经符号推理工作流程。这些工作流程通常编译成对文本字段的深度嵌套、非单调布尔查询。然而，在处理这些结构时，倒排索引的标准查询评估策略面临着严格的理论限制。有状态迭代器模型（一次文档）在结构上受到 NC^1 公式评估的限制，在展开重新收敛逻辑时，查询复杂性会遭受最坏情况的 O(2^|Q|) 指数爆炸。相反，递归物化模型......
来源:Apple机器学习研究现代人工智能代理越来越依赖搜索基础设施来执行复杂的神经符号推理工作流程。这些工作流程通常编译成对文本字段的深度嵌套、非单调布尔查询。然而，在处理这些结构时，倒排索引的标准查询评估策略面临着严格的理论限制。有状态迭代器模型（一次文档）在结构上受到 NC^1 公式评估的限制，在展开重新收敛逻辑时，查询复杂性会遭受最坏情况的 O(2^|Q|) 指数爆炸。相反，在评估文档宇宙上的逻辑否定时，递归物化模型（Term-at-a-Time）会产生 Ω(|U|) 空间复杂度损失（通用扫描）。
在本文中，我们建立了通过倒排索引本地执行复杂逻辑的理论边界。我们形式化了一种基于有向无环图（DAG）的检索语言（L_R），并证明其评估问题是严格的 P-Complete。为了使评估易于处理，我们引入了 ComputePN，这是一种确定性、稀疏性感知的评估算法。通过通过新颖的正负双重表示将逻辑否定与宇宙尺度的物化解耦，并利用原生 DAG 记忆，ComputePN 将评估时间严格限制为 O(|Q| · |U_active|)。这种方法成功地评估了索引上的 P-Complete 查询，避免了组合树扩展瓶颈和通用扫描惩罚，为计算检索奠定了正式基础。