Evergreen: Efficient Claim Verification for Semantic Aggregates

1. Probleemstelling

Met de opkomst van engines voor semantische queryverwerking (bijv. Snowflake Cortex AISQL) is semantische aggregatie uitgegroeid tot een primitieve operator. Dit stelt Large Language Models (LLM's) in staat om een relatie van tuples te reduceren tot een samenvatting of aggregaat in natuurlijke taal. Echter, deze door LLM's gegenereerde aggregaten bevatten vaak hallucinerende claims (bijv. "de meerderheid van de reviews is positief" terwijl dat niet zo is) die niet zijn verankerd in de onderliggende data.

Het verifiëren van deze claims is uitdagend vanwege vier hoofdfactoren:

1. Schaal: Relaties overschrijden vaak de contextvensters van LLM's (duizenden reviews = honderdduizenden tokens).
2. Complexiteit: Claims omvatten kwantoren (alle, sommige, meerderheid), groeperingen en vergelijkingen tussen groepen, wat een mix vereist van semantisch redeneren (tekst begrijpen) en symbolisch redeneren (tellen/vergelijken).
3. Kosten: Brute-force verificatie vereist het aanroepen van een LLM voor elke tuple, wat onbetaalbaar duur en traag is.
4. Uitlegbaarheid: Gebruikers vereisen citaten (bewijs) om het oordeel te vertrouwen, niet slechts een binair "waar/onwaar".

Bestaande benaderingen falen om dit holistisch aan te pakken: LLM-as-a-judge-methoden falen bij grote contexten; Retrieval-Augmented Generation (RAG) heeft moeite met gekwantificeerde claims over onafhankelijke tuples; en Program-based LLM's verleggen optimalisatie naar de LLM, wat leidt tot suboptimale prestaties.

2. Methodologie: Het Evergreen-systeem

Evergreen herformuleert claimverificatie als een taak voor semantische queryverwerking. In plaats van een LLM te vragen om een claim te "controleren", compileert Evergreen de claim tot een declaratieve semantische verificatiequery die wordt uitgevoerd door een query-engine.

A. Claim-decompositie en compilatie

1. Decompositie: Een LLM breekt het natuurlijke taal-aggregaat op in atomische claims en lost vage verwijzingen (bijv. voornaamwoorden) op met behulp van de originele context.
2. Logische mapping: Claims worden gemapt naar logische structuren:
   • Existentieel/Universeel: $\exists t, \forall t$
   • Cardinaal/Proportioneel: $\exists \ge k, \exists \ge \rho$
   • Ordinaal/Gesneld: Rangschikking van groepen of geneste kwantoren (bijv. "Alle locaties hebben >2 klachten").
3. Query-generatie: Claims worden gecompileerd tot een DataFrame-achtige API met standaard relationele operatoren (filter, map, aggregate) en semantische operatoren (prompt-gebaseerde LLM-aanroepen).
   • filter(prompt): Semantische filtering.
   • map(prompt): Semantische attribuutextractie.
   • aggregate: Gemapt naar kwantoren (bijv. bool_or $\to$ $\exists$, count_if $\to$ cardinaliteit).

B. Verificatie-bewuste optimalisaties

Evergreen introduceert specifieke optimalisaties om LLM-aanroepen te minimaliseren terwijl de correctheid behouden blijft:

1. Vroegtijdig stoppen: De query-engine gebruikt een iterator-model.
   • Voor $\exists$ (bijv. "sommige"), stopt het zodra één getuige is gevonden.
   • Voor $\forall$ (bijv. "alle"), stopt het zodra één tegenvoorbeeld is gevonden.
   • Voor cardinale/proportionele claims duwt het vergelijkingslogica naar beneden om te stoppen zodra de drempel wiskundig is bepaald, ongeacht de resterende tuples.
2. Relevantie-sortering: Om vroegtijdig stoppen effectief te maken, worden tuples vooraf gesorteerd op relevantie. Een LLM genereert een zoekopdracht op basis van de logica van de claim; tuples worden gerangschikt op basis van embedding-相似heid en trefwoordmatching zodat "getuigen" vroeg in de stream verschijnen.
3. Schatting met Confidence Sequences (CS): Voor gevallen waarin vroegtijdig stoppen onmogelijk is (bijv. het verifiëren dat een universele claim waar is), gebruikt Evergreen Anytime-Valid Confidence Sequences. In tegenstelling tot klassieke betrouwbaarheidsintervallen, staan CS's continue monitoring toe zonder de foutmarges te verhogen. Het systeem stopt met het nemen van steekproeven zodra het betrouwbaarheidsinterval bewijst dat de claim met hoge waarschijnlijkheid waar of onwaar is.
4. Algemeen-toepasbare optimalisaties:
   • Operator-fusie: Combineert meerdere semantische operatoren (bijv. filter + map) tot één enkele LLM-aanroep per tuple.
   • Similarity Filtering: Een lichtgewicht voorfilter met behulp van embeddings om duidelijk irrelevante tuples te verwijderen voordat de LLM wordt aangeroepen.
   • Prompt-caching: Hergebruikt LLM-antwoorden voor identieke prompts over verschillende claims.

C. Citaten via Semiring Provenance

Om uitleg te bieden, behandelt Evergreen citaten als data-provenance. Het maakt gebruik van semiring-provenance voor eerste-orde logica:

• Elke tuple wordt geannoteerd met tokens die aangeven of deze voldoet aan de formule van de claim.
• Het systeem leidt een minimale set tokens (monomials) af die het resultaat rechtvaardigen.
• Als een claim waar is, retourneert het de minimale set getuigen. Als onwaar, retourneert het de minimale set tegenvoorbeelden. Dit zorgt ervoor dat uitleg beknopt en wiskundig onderbouwd is.

3. Belangrijkste bijdragen

1. Logische formalisering: Identificeerde veelvoorkomende claimtypen in semantische aggregaten en mappete deze naar goed gedefinieerde logische structuren (existentieel, universeel, cardinaal, proportioneel, ordinaal, genest).
2. Declaratieve compilatie: Demonstreerde hoe natuurlijke taal-claims kunnen worden gecompileerd tot declaratieve semantische verificatiequeries, waarbij de optimalisatielast wordt verlegd van de LLM naar de query-engine.
3. Nieuwe optimalisaties: Introduceerde verificatie-specifieke technieken (Vroegtijdig stoppen, Relevantie-sortering, Schatting met Confidence Sequences) die kosten en latentie drastisch reduceren.
4. Formele provenance: Past semiring-provenance toe om citaten te formaliseren als minimale uitleg voor verificatieresultaten.
5. Uitgebreide evaluatie: Bouwde een benchmark van 16 diverse claims over real-world datasets van restaurantreviews om het systeem te evalueren.

4. Experimentele resultaten

Het systeem werd geëvalueerd op drie Yelp-datasets (elk 1,6k–1,8k tuples) tegenover baselines: LLM-as-a-judge (base_rm), Retrieval-Augmented Agent (rag_agent), en een Ongeoptimaliseerde Evergreen (evg_unopt).

• Kwaliteit vs. Kosten:
  • Sterke LLM's: Evergreen met een sterke LLM (Opus) behaalde F1 = 1,00 (perfecte verificatie) terwijl de kosten met 3,2$\times$ en de latentie met 4,0$\times$ werden verlaagd ten opzichte van de ongeoptimaliseerde versie.
  • Zwakke LLM's: Evergreen met een zwakke LLM (Llama 8B) presteerde beter dan een sterke LLM-as-a-judge-baseline (Opus) qua F1-score (0,89 vs. 0,82) bij 48$\times$ lagere kosten en 2,3$\times$ lagere latentie.
  • Vs. RAG-agent: Evergreen kwam overeen met of overtrof de kwaliteit van de RAG-agent met een zwakke LLM bij 63$\times$ lagere kosten en 4,2$\times$ lagere latentie.
• Ablatiestudie:
  • Vroegtijdig stoppen was de meest kritieke optimalisatie, met een kosten/latentie-reductie van 6,7$\times$.
  • Schatting (CS) en Prompt-caching zorgden voor besparingen van 2$\times$–2,7$\times$.
  • Het uitschakelen van optimalisaties degradeerde de prestaties over het algemeen aanzienlijk, wat de noodzaak van de neuro-symbolische aanpak bewijst.
• Robuustheid: Zelfs met zwakkere modellen behield Evergreen een hoge precisie van provenance (0,84–0,99), waardoor de geboden citaten betrouwbaar waren.

5. Betekenis

Evergreen vertegenwoordigt een significante verschuiving in hoe semantische datasystemen omgaan met betrouwbaarheid.

• Neuro-symbolische synergie: Het combineert effectief het semantische begrip van LLM's met de rigoureuze optimalisatie en logische redenering van database-query-engines.
• Schaalbaarheid: Het lost de "contextvenster"- en "kosten"-knelpunten op die momenteel het betrouwbare gebruik van LLM's in productie-data-analyse belemmeren.
• Vertrouwen: Door minimale, wiskundig onderbouwde citaten te bieden, gaat het voorbij aan "black box"-LLM-outputs, waardoor semantische aggregaten auditabel en betrouwbaar worden voor zakelijk gebruik.
• Toekomstige richting: Het ebt de weg voor "Semantische integriteitsbeperkingen", waarbij databasesystemen automatisch correctheid kunnen afdwingen op door LLM's gegenereerde inzichten.

Kortom, Evergreen demonstreert dat door claimverificatie te behandelen als een query-optimalisatieprobleem, systemen perfecte of bijna-perfecte verificatiekwaliteit kunnen bereiken voor een fractie van de kosten en latentie van huidige state-of-the-art LLM-gebaseerde benaderingen.