Apple Paper sier at komplekse boolske søk er P-fullstendig

Hva skjedde

Apple Machine Learning Research publiserte en artikkel av Amir Aavani om beregningskompleksiteten ved å evaluere dypt nestede, ikke-monotone boolske spørringer over inverterte indekser. Oppgaven formaliserer et gjenfinningsspråk basert på rettet asykliske grafer, hevder at evalueringsproblemet er strengt P-Complete, og introduserer ComputePN, en deterministisk algoritme som bruker positive-negative representasjoner og DAG-memoisering.

Apple Machine Learning Research viser artikkelen som publisert i august 2026, med Amir Aavani som forfatter. Oppgaven tar for seg invertert-indeks-traversal, en søketeknikk der termer peker på dokumenter som inneholder dem. Apple rammer problemet rundt moderne AI-agenter som bruker søkeinfrastruktur for komplekse, nevro-symbolske resonnementarbeidsflyter. I følge kilden kan disse arbeidsflytene kompileres til dypt nestede boolske spørringer som inkluderer ikke-monotonisk logikk, inkludert negasjon. Oppgavens fokus er derfor utførelse av strukturert gjenfinningslogikk, ikke en ny språkmodell, agentprodukt eller forbrukervendt søkefunksjon.

Oppgaven beskriver to grenser i standard evalueringsstrategier. Det står at stateful Document-at-a-Time iterator-modeller er strukturelt avgrenset av NC^1 formelevaluering og kan møte et verste tilfelle O(2^|Q|) eksponentiell eksplosjon når rekonvergent logikk rulles ut i et tre. Den sier at rekursive Term-at-a-Time materialiseringsmodeller står overfor en Ω(|U|) romstraff, beskrevet som en universell skanning, når de evaluerer logisk negasjon over hele dokumentuniverset. Dette er påstander fremsatt av papirets abstrakt. Den medfølgende kilden gir ikke eksempler, arbeidsbelastningsspor, empiriske målinger eller en sammenligning som viser hvor ofte det verste mønsteret oppstår i distribuerte systemer.

Apple sier at det formaliserer et gjenfinningsspråk, L_R, basert på dirigerte asykliske grafer og beviser at evaluering av spørringer på dette språket er strengt P-Complete. Den introduserer deretter ComputePN, beskrevet som en deterministisk, sparsitetsbevisst evalueringsalgoritme. Metoden skiller logisk negasjon fra materialisering i universell skala gjennom en positiv-negativ dobbel representasjon og bruker naturlig DAG-memoisering slik at gjentatte underuttrykk ikke trenger å utvides gjentatte ganger.

Kilden gir en påstått evalueringstidsgrense for O(|Q| · |U_active|), der notasjonen refererer til spørringsstørrelsen og det aktive dokumentsettet. Den inkluderer ikke algoritmens implementering, kildekode, målte konstanter eller driftskrav.

Til sammen dekker beskrivelsen papirets formelle problemstilling, dets kompleksitetsresultat og den foreslåtte evalueringsmetoden. Gjenfinningsspråket er representert med rettede asykliske grafer, den angitte vanskeligheten gjelder nestet boolsk logikk, og ComputePN presenteres som mekanismen for å håndtere den strukturen. Den positive-negative representasjonen adresserer negasjon, mens DAG-memoisering adresserer gjentatte underuttrykk. Kilden angir også en grense når det gjelder spørringsstørrelse og det aktive dokumentsettet. Utover de angitte design- og kompleksitetspunktene, etablerer ikke det leverte materialet implementeringsdetaljer, målt ytelse, produksjonsbruk eller ekstern validering. Disse spørsmålene forblir atskilt fra papirets formelle påstander om evaluering.

Kildedetaljer: machinelearning.apple.com ↗

Hvorfor det betyr noe

Hvis papirets påstander holder i praktiske systemer, kan de avklare hvordan søkeinfrastruktur skal utføre kompleks gjenfinningslogikk brukt i AI-agent arbeidsflyter. Kilden hevder ComputePN unngår to kjente kostnader: eksponentiell utvidelse av rekonvergent spørringslogikk og materialisering av hele dokumentuniverset for negasjon. Den gir ingen produksjonsmålinger, så den praktiske effekten forblir ubekreftet.

Resultatet er viktig fordi det setter en formell grense rundt et problem Apple kobler til AI-agenthenting. Agenter som kombinerer søkeresultater med symbolske forhold kan trenge mer enn enkel søkeordsamsvar: de kan uttrykke nestede skjæringspunkter, fagforeninger og ekskluderinger hvis logikk naturlig danner en graf med delte underuttrykk. En grafrepresentasjon kan bevare den delingen, mens en treutvidelse kan duplisere den. Hvis ComputePN fungerer som hevdet, tilbyr papiret en prinsipiell måte å evaluere slik logikk uten automatisk å betale verken eksponentiell ekspansjonskostnad eller en full-universets materialiseringskostnad. Den potensielle praktiske fordelen er mest relevant for systemer der spørringskompleksitet, korpusstørrelse og sparsomhet samhandler.

Å unngå skanning av hvert dokument kan redusere minnetrykket for negasjonstunge spørringer, mens memorering av delte DAG-noder kan forhindre gjentatt arbeid. Den påståtte bindingen fokuserer også på det aktive dokumentsettet i stedet for hele universet, noe som kan være viktig for selektive søk. Disse implikasjonene følger av det algoritmiske designet beskrevet av Apple, ikke fra en demonstrert produktforbedring. Kilden rapporterer ingen latensreduksjon, gjennomstrømningsøkning, kostnadsbesparelse, energiresultat eller brukerresultat.

Artikkelen er konsekvent som et forskningsbidrag, men dens offentlige innvirkning er fortsatt usikker. Den kunngjør ikke en produktlansering eller sier at Apple har integrert ComputePN i en kundevendt søketjeneste. Den fastslår heller ikke at eksisterende søkemotorer eller agentplattformer bruker det eksakte søkespråket som er modellert i avisen. Ingen uavhengig bekreftelse er inkludert i det leverte materialet. Den praktiske verdien vil avhenge av om den formelle modellen samsvarer med produksjonsarbeidsbelastninger, om algoritmens konstanter er akseptable, og hvordan den oppfører seg når spørringer, indekser og aktive sett er store eller sterkt sammenkoblet.

Hva du skal se neste

Det viktige neste beviset er implementering og benchmarking: ekte spørringsgrafer, korpusstørrelser, antall aktive dokumenter, latens, minnebruk og sammenligninger med eksisterende Document-at-a-Time og Term-at-A-Time-systemer. Kilden identifiserer ikke programvare, et API, en distribusjon, et sted for fagfellevurdering eller adopsjon av et søk eller AI-produkt.

Det første spørsmålet er om de påståtte kompleksitetsfordelene oversettes til målt systemytelse. Nyttig oppfølgingsbevis vil omfatte referansekorpora, prosedyrer for generering av spørringer, distribusjoner av DAG-dybde og rekonvergens, størrelser på dokumentunivers, aktive settstørrelser, toppminne og ende-til-ende-latens. Sammenligninger bør inkludere både Document-at-a-Time og Term-at-A-Time baselines, sammen med motstridende saker som involverer gjentatte underuttrykk og bred negasjon. Den nåværende kilden gir asymptotiske påstander, men ingen av disse målingene.

Det andre spørsmålet er om ComputePN eksisterer som brukbar programvare. Apple sin side lenker ikke til et depot, pakke, API, teknisk implementering eller instruksjoner for å reprodusere resultatene. Det står heller ikke om metoden kan legges til etablerte inverterte indeksmotorer, om den krever et nytt indeksoppsett, eller om den støtter oppdateringer, rangering, filtrering, distribuert utførelse eller samtidige spørringer. Disse utelatelsene gjør det umulig fra denne kilden å vurdere distribusjonsberedskap eller kompatibilitet med eksisterende gjenfinningsstabler.

Det tredje spørsmålet er validering og omfang. Siden navngir arbeidet som en publisert artikkel, men identifiserer ikke en konferanse, et tidsskrift, en gjennomgangsprosess eller en ekstern replikering. Fremtidige avsløringer bør avklare det nøyaktige gjenfinningsspråket, forutsetningene bak representasjonen av aktivt dokument og oppførselen til den positiv-negative strukturen under tette eller nesten universelle treff. Det vil også være viktig å se om AI-agentsystemer faktisk genererer den typen boolske spørrings-DAGer som er beskrevet, og om den foreslåtte metoden forbedrer påliteligheten eller bare etablerer en teoretisk evalueringsbane.

Relaterte guider og quizer