🤖 AI

Evergreen: Efficient Claim Verification for Semantic Aggregates

Evergreen is an efficient system that verifies potentially hallucinated claims in semantic aggregates by compiling them into declarative queries executed on the same engine, utilizing tailored optimizations and semiring-based provenance to achieve high accuracy with significantly reduced cost and latency compared to existing baselines.

Original authors: Alexander W. Lee, Benjamin Han, Shayak Sen, Sam Yeom, Ugur Cetintemel, Anupam Datta

Published 2026-04-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander W. Lee, Benjamin Han, Shayak Sen, Sam Yeom, Ugur Cetintemel, Anupam Datta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but slightly overconfident, assistant (an AI) who reads thousands of restaurant reviews and writes you a summary. The assistant might say, "Everyone loved the chicken salad!" or "No one mentioned vegan options."

The problem? The assistant might be hallucinating. It might have just guessed, or it might have missed a few reviews that said the opposite. Checking if the assistant is telling the truth is hard because:

There are too many reviews to read them all at once (they don't fit in the AI's "memory").
The AI is bad at counting and logic (e.g., "Did most people like it?").
Reading every single review one by one to check the math is incredibly slow and expensive.

Enter "Evergreen."

Think of Evergreen as a super-efficient fact-checking system that treats the AI's summary like a math problem rather than a conversation. Instead of asking the AI to "think hard" about the whole dataset, Evergreen breaks the summary down into tiny, logical questions and solves them using a mix of smart shortcuts and a "checklist" approach.

Here is how it works, using some everyday analogies:

1. The "Detective's Checklist" (Turning Claims into Queries)

When the AI says, "Most people loved the service," Evergreen doesn't just ask the AI, "Is that true?" Instead, it translates that sentence into a strict logical query, like a detective's checklist:

Step 1: Find all reviews mentioning "service."
Step 2: Count how many are positive.
Step 3: Is that number greater than 50%?

By turning the vague sentence into a rigid set of steps, Evergreen can use a database engine (which is great at counting and sorting) to do the heavy lifting, only calling the AI when absolutely necessary to understand the meaning of a specific review.

2. The "Smart Shortcuts" (Optimizations)

The paper highlights that Evergreen is fast and cheap because it uses three main "tricks" to avoid doing unnecessary work:

Early Stopping (The "Stop at the First Clue" Rule):
If the claim is "At least one person complained," Evergreen scans the reviews. As soon as it finds one complaint, it stops immediately. It doesn't need to read the other 1,000 reviews to know the claim is true. Conversely, if the claim is "No one complained," it keeps scanning until it finds a single complaint to prove the claim false, or until it's statistically sure no one did. It saves massive amounts of time by not reading the whole book if the answer is found on page 10.
Relevance Sorting (The "Relevant Files First" Trick):
Imagine you are looking for a specific needle in a haystack. Instead of digging randomly, Evergreen uses a magnet to pull the most likely needles to the top of the pile first. It sorts the reviews so that the ones most likely to contain the answer (e.g., reviews with the word "complaint") are checked first. This makes the "Early Stopping" trick work even faster.
Confidence Sequences (The "Statistical Guessing Game"):
Sometimes, you don't need to check every review to know the answer. Evergreen uses a statistical method called "confidence sequences." Imagine you are tasting soup to see if it's salty enough. You don't need to drink the whole bowl; you just need to taste enough spoonfuls to be 99% sure. Evergreen tastes a few reviews, checks the math, and if the result is clear, it stops. If the math is still fuzzy, it takes a few more "tastes." This avoids wasting money on reading reviews that don't change the final verdict.

3. The "Receipt" (Citations and Provenance)

When Evergreen says "True" or "False," it doesn't just give a yes/no answer. It provides a receipt.

If the claim is true, it shows you the exact reviews that proved it (e.g., "Here are the 3 reviews where people said they loved the salad").
If the claim is false, it shows you the exact reviews that disproved it.

This is like a math teacher showing their work. It uses a special "provenance" system (a fancy way of tracking the source of every fact) to ensure the explanation is minimal and accurate. It doesn't show you 1,000 reviews; it shows you the minimum number needed to prove the point.

4. The Results: Stronger, Faster, Cheaper

The paper tested Evergreen on real restaurant review data. Here is what they found:

Accuracy: It got a perfect score (F1 = 1.00) when using a strong AI model, meaning it never made a mistake.
Cost & Speed: It was 3 to 4 times faster and 3 to 4 times cheaper than just asking the AI to read everything without these shortcuts.
The "Weak AI" Surprise: Even when using a much weaker, cheaper AI model, Evergreen performed better than a "strong" AI model trying to do the job alone. By letting the database engine handle the logic and counting, the AI only had to do the easy part (reading the text), which even a "dumb" AI could do well.

Summary

Evergreen is a system that stops AI from making up facts about large datasets. It does this by:

Turning vague AI summaries into strict logical questions.
Using smart shortcuts to stop reading as soon as the answer is found.
Providing a "receipt" of exactly which data points proved the answer.

It's like hiring a team of accountants (the database) to do the math and a single, efficient intern (the AI) to read the receipts, rather than asking one tired intern to do all the math and reading alone.

1. Problem Statement

With the rise of semantic query processing engines (e.g., Snowflake Cortex AISQL), semantic aggregation has become a primitive operator. This allows Large Language Models (LLMs) to reduce a relation of tuples into a natural language summary or aggregate. However, these LLM-generated aggregates often contain hallucinated claims (e.g., "the majority of reviews are positive" when they are not) that are not grounded in the underlying data.

Verifying these claims is challenging due to four main factors:

Scale: Relations often exceed LLM context windows (thousands of reviews = hundreds of thousands of tokens).
Complexity: Claims involve quantifiers (all, some, majority), groupings, and cross-group comparisons, requiring a mix of semantic reasoning (understanding text) and symbolic reasoning (counting/comparing).
Cost: Brute-force verification requires invoking an LLM for every tuple, which is prohibitively expensive and slow.
Explainability: Users require citations (evidence) to trust the verdict, not just a binary "true/false."

Existing approaches fail to address this holistically: LLM-as-a-judge methods fail on large contexts; Retrieval-Augmented Generation (RAG) struggles with quantified claims over independent tuples; and Program-based LLMs offload optimization to the LLM, leading to suboptimal performance.

2. Methodology: The Evergreen System

Evergreen reframes claim verification as a semantic query processing task. Instead of asking an LLM to "check" a claim, Evergreen compiles the claim into a declarative semantic verification query executed by a query engine.

A. Claim Decomposition & Compilation

Decomposition: An LLM breaks the natural language aggregate into atomic claims and resolves vague references (e.g., pronouns) using the original context.
Logical Mapping: Claims are mapped to logical structures:
- Existential/Universal: $\exists t, \forall t$
- Cardinal/Proportional: $\exists \ge k, \exists \ge \rho$
- Ordinal/Nested: Ranking groups or nested quantifiers (e.g., "All locations have >2 complaints").
Query Generation: Claims are compiled into a DataFrame-style API using standard relational operators (filter, map, aggregate) and semantic operators (prompt-based LLM calls).
- filter(prompt): Semantic filtering.
- map(prompt): Semantic attribute extraction.
- aggregate: Maps to quantifiers (e.g., bool_or $\to$ $\exists$ , count_if $\to$ cardinality).

B. Verification-Aware Optimizations

Evergreen introduces specific optimizations to minimize LLM calls while maintaining correctness:

Early Stopping: The query engine uses an iterator model.
- For $\exists$ (e.g., "some"), it stops as soon as one witness is found.
- For $\forall$ (e.g., "all"), it stops as soon as one counterexample is found.
- For cardinal/proportional claims, it pushes comparison logic down to stop once the threshold is mathematically determined regardless of remaining tuples.
Relevance Sorting: To make early stopping effective, tuples are pre-sorted by relevance. An LLM generates a search query based on the claim's logic; tuples are ranked by embedding similarity and keyword matching so that "witnesses" appear early in the stream.
Estimation with Confidence Sequences (CS): For cases where early stopping is impossible (e.g., verifying a universal claim is true), Evergreen uses Anytime-Valid Confidence Sequences. Unlike classical confidence intervals, CSs allow continuous monitoring without inflating error rates. The system stops sampling once the confidence interval proves the claim is true or false with high probability.
General-Purpose Optimizations:
- Operator Fusion: Combines multiple semantic operators (e.g., filter + map) into a single LLM call per tuple.
- Similarity Filtering: A lightweight pre-filter using embeddings to discard obviously irrelevant tuples before invoking the LLM.
- Prompt Caching: Reuses LLM responses for identical prompts across different claims.

C. Citations via Semiring Provenance

To provide explanations, Evergreen treats citations as data provenance. It utilizes semiring provenance for first-order logic:

Each tuple is annotated with tokens indicating whether it satisfies the claim's formula.
The system derives a minimal set of tokens (monomials) that justify the result.
If a claim is true, it returns the minimal set of witnesses. If false, it returns the minimal set of counterexamples. This ensures explanations are concise and mathematically grounded.

3. Key Contributions

Logical Formalization: Identified common claim types in semantic aggregates and mapped them to well-defined logical structures (existential, universal, cardinal, proportional, ordinal, nested).
Declarative Compilation: Demonstrated how to compile natural language claims into declarative semantic verification queries, shifting optimization burden from the LLM to the query engine.
Novel Optimizations: Introduced verification-specific techniques (Early Stopping, Relevance Sorting, Confidence Sequence Estimation) that drastically reduce cost and latency.
Formal Provenance: Applied semiring provenance to formalize citations as minimal explanations for verification results.
Comprehensive Evaluation: Built a benchmark of 16 diverse claims over real-world restaurant review datasets to evaluate the system.

4. Experimental Results

The system was evaluated on three Yelp datasets (1.6k–1.8k tuples each) against baselines: LLM-as-a-judge (base_rm), Retrieval-Augmented Agent (rag_agent), and an Unoptimized Evergreen (evg_unopt).

Quality vs. Cost:
- Strong LLMs: Evergreen with a strong LLM (Opus) achieved F1 = 1.00 (perfect verification) while reducing cost by 3.2 $\times$ and latency by 4.0 $\times$ compared to the unoptimized version.
- Weak LLMs: Evergreen using a weak LLM (Llama 8B) outperformed a strong LLM-as-a-judge baseline (Opus) in F1 score (0.89 vs. 0.82) at 48 $\times$ lower cost and 2.3 $\times$ lower latency.
- vs. RAG Agent: Evergreen matched or exceeded the RAG agent's quality with a weak LLM at 63 $\times$ lower cost and 4.2 $\times$ lower latency.
Ablation Study:
- Early Stopping was the most critical optimization, reducing cost/latency by 6.7 $\times$ .
- Estimation (CS) and Prompt Caching provided 2 $\times$ –2.7 $\times$ savings.
- Disabling optimizations generally degraded performance significantly, proving the necessity of the neuro-symbolic approach.
Robustness: Even with weaker models, Evergreen maintained high provenance precision (0.84–0.99), ensuring that the provided citations were reliable.

5. Significance

Evergreen represents a significant shift in how semantic data systems handle reliability.

Neuro-Symbolic Synergy: It effectively combines the semantic understanding of LLMs with the rigorous optimization and logical reasoning of database query engines.
Scalability: It solves the "context window" and "cost" bottlenecks that currently prevent the reliable use of LLMs in production data analytics.
Trustworthiness: By providing minimal, mathematically grounded citations, it moves beyond "black box" LLM outputs, making semantic aggregates auditable and trustworthy for enterprise use.
Future Direction: It paves the way for "Semantic Integrity Constraints," where database systems can automatically enforce correctness on LLM-generated insights.

In summary, Evergreen demonstrates that by treating claim verification as a query optimization problem, systems can achieve perfect or near-perfect verification quality at a fraction of the cost and latency of current state-of-the-art LLM-based approaches.