В статье Apple говорится, что сложные логические поисковые запросы являются P-полными

Что случилось

Apple Machine Learning Research опубликовала статью Амира Аавани о вычислительной сложности оценки глубоко вложенных немонотонных логических запросов по инвертированным индексам. В статье формализуется поисковый язык, основанный на направленных ациклических графах, утверждается, что его проблема оценки является строго P-полной, и вводится ComputePN, детерминированный алгоритм, использующий положительно-отрицательные представления и мемоизацию DAG.

Apple Machine Learning Research указывает, что статья опубликована в августе 2026 года, а ее автором является Амир Аавани. В статье рассматривается обход по инвертированному индексу — метод поиска, при котором термины указывают на содержащие их документы. Apple описывает проблему современных агентов ИИ, которые используют инфраструктуру поиска для сложных рабочих процессов нейросимволического рассуждения. По словам источника, эти рабочие процессы могут компилироваться в глубоко вложенные логические запросы, включающие немонотонную логику, включая отрицание. Таким образом, основное внимание в статье уделяется реализации структурированной логики поиска, а не новой языковой модели, агентскому продукту или функции поиска, ориентированной на потребителя.

В статье описываются два ограничения стандартных стратегий оценки. В нем говорится, что модели итераторов Document-at-a-Time с сохранением состояния структурно ограничены вычислением формулы NC^1 и могут столкнуться с экспоненциальным разрушением O(2^|Q|) в худшем случае, когда реконвергентная логика разворачивается в дерево. В нем говорится, что рекурсивные модели материализации «терм за раз» сталкиваются со штрафом пространства Ω(|U|), описываемым как универсальное сканирование, при оценке логического отрицания по всей вселенной документа. Это утверждения, содержащиеся в аннотации статьи. В предоставленном источнике не представлены примеры, трассировки рабочей нагрузки, эмпирические измерения или сравнение, показывающее, как часто в развернутых системах встречается наихудшая ситуация.

Apple утверждает, что формализует поисковый язык L_R, основанный на ориентированных ациклических графах, и доказывает, что обработка запросов на этом языке является строго P-полной. Затем он представляет ComputePN, описываемый как детерминированный алгоритм оценки с учетом разреженности. Этот метод отделяет логическое отрицание от материализации в масштабе вселенной посредством двойного представления положительно-отрицательно и использует встроенную мемоизацию DAG, поэтому повторяющиеся подвыражения не нужно многократно расширять.

Источник дает заявленную границу времени оценки O(|Q| · |U_active|), где обозначение относится к размеру запроса и активному набору документов. Он не включает реализацию алгоритма, исходный код, измеряемые константы или эксплуатационные требования.

В совокупности описание охватывает формальную постановку задачи, результат ее сложности и предлагаемый метод оценки. Язык поиска представлен ориентированными ациклическими графами, заявленная трудность касается вложенной логической логики, а ComputePN представлен как механизм обработки этой структуры. Положительно-отрицательное представление адресует отрицание, а мемоизация DAG обращается к повторяющимся подвыражениям. В источнике также указывается ограничение по размеру запроса и активному набору документов. Помимо заявленных характеристик конструкции и сложности, в поставляемом материале не указаны детали реализации, измеренные характеристики, производственное использование или внешняя проверка. Эти вопросы остаются отдельными от официальных заявлений статьи об оценке.

Подробности об источнике: machinelearning.apple.com ↗

Почему это важно

Если утверждения статьи справедливы для практических систем, они смогут прояснить, как поисковая инфраструктура должна выполнять сложную логику поиска, используемую в рабочих процессах ИИ-агентов. Источник утверждает, что ComputePN позволяет избежать двух известных затрат: экспоненциального расширения логики реконвергентных запросов и материализации всей вселенной документа для отрицания. Он не предусматривает производственных измерений, поэтому практический эффект остается непроверенным.

Результат имеет значение, поскольку он устанавливает формальную границу вокруг проблемы, связанной Apple с поиском ИИ-агента. Агентам, которые объединяют результаты поиска с символическими условиями, может потребоваться нечто большее, чем простое сопоставление ключевых слов: они могут выражать вложенные пересечения, объединения и исключения, логика которых естественным образом образует граф с общими подвыражениями. Представление в виде графа может сохранить это совместное использование, а расширение дерева может его дублировать. Если ComputePN работает так, как заявлено, статья предлагает принципиальный способ оценить такую ​​логику без автоматической оплаты ни стоимости экспоненциального расширения, ни стоимости материализации всей вселенной. Потенциальная практическая польза наиболее актуальна для систем, в которых взаимодействуют сложность запроса, размер корпуса и разреженность.

Отказ от сканирования каждого документа может уменьшить нагрузку на память для запросов с большим количеством отрицаний, а запоминание общих узлов DAG может предотвратить повторную работу. Заявленная привязка также фокусируется на наборе активных документов, а не на всей вселенной, что может быть важно для выборочных запросов. Эти выводы следуют из алгоритмической конструкции, описанной Apple, а не из продемонстрированного улучшения продукта. Источник сообщает об отсутствии снижения задержки, увеличения пропускной способности, экономии затрат, энергопотребления или результатов для пользователей.

Эта статья имеет важное значение как исследовательский вклад, но ее общественное влияние все еще остается неопределенным. Он не объявляет о выпуске продукта и не сообщает, что Apple интегрировал ComputePN в службу поиска, ориентированную на клиентов. Также не установлено, что существующие поисковые системы или агентские платформы используют именно тот язык запросов, который смоделирован в статье. Никакого независимого подтверждения в поставляемом материале не содержится. Практическая ценность будет зависеть от того, соответствует ли формальная модель производственным нагрузкам, приемлемы ли константы алгоритма и как он ведет себя, когда запросы, индексы и активные наборы большие или сильно взаимосвязаны.

Что посмотреть дальше

Следующим важным доказательством является реализация и сравнительный анализ: реальные графики запросов, размеры корпуса, количество активных документов, задержка, использование памяти и сравнение с существующими системами «документ за раз» и «термин за раз». Источник не идентифицирует программное обеспечение, API, развертывание, место проведения экспертной оценки или внедрение в поисковые системы или продукты искусственного интеллекта.

Первый вопрос заключается в том, преобразуются ли заявленные преимущества сложности в измеряемую производительность системы. Полезные данные последующего наблюдения будут включать в себя эталонные корпуса, процедуры генерации запросов, распределение глубины DAG и реконвергенции, размеры юниверса документа, размеры активного набора, пиковую память и сквозную задержку. Сравнения должны включать базовые показатели как для документа за раз, так и для каждого термина, а также состязательные случаи, включающие повторяющиеся подвыражения и широкое отрицание. Текущий источник предоставляет асимптотические утверждения, но не содержит ни одного из этих измерений.

Второй вопрос заключается в том, существует ли ComputePN как полезное программное обеспечение. Страница Apple не содержит ссылок на репозиторий, пакет, API, техническую реализацию или инструкции по воспроизведению результатов. В нем также не указывается, можно ли добавить этот метод к установленным механизмам с инвертированным индексом, требует ли он нового макета индекса или поддерживает ли он обновления, ранжирование, фильтрацию, распределенное выполнение или параллельные запросы. Эти упущения не позволяют из этого источника оценить готовность к развертыванию или совместимость с существующими стеками извлечения.

Третий вопрос — валидация и область применения. На странице работа указана как опубликованная статья, но не указана конференция, журнал, процесс рецензирования или внешнее тиражирование. Будущие раскрытия должны прояснить точный язык поиска, предположения, лежащие в основе представления активного документа, и поведение положительно-отрицательной структуры при плотных или почти универсальных совпадениях. Также будет важно посмотреть, действительно ли системы ИИ-агентов генерируют описанные типы логических запросов DAG, и повышает ли предлагаемый метод надежность или устанавливает только теоретический путь оценки.

Сопутствующие руководства и викторины