Semantic query engines evaluate natural‑language filters with a large language model (LLM), and each evaluation incurs a costly oracle call. Existing optimizers face a dilemma: cheap proxy cascades often miss precision and recall targets, finite‑sample guarantees save little, and all methods discard the oracle's labels after the query finishes.
We introduce SemViews, a certified semantic filter. SemViews first orders tuples using signals that require no oracle calls—labels left by earlier queries (semantic views), a local embedding, and a helper model's score. It then refines that order with labels that must be paid for anyway, and certifies the answer with fresh stratified oracle samples.
The certification guarantees that, for any workload and catalog, the answer meets user‑specified precision and recall targets with probability at least $1-\delta$. Thus a stale or misleading view may increase oracle calls but never harms accuracy.
In replay experiments on four workloads using 725,000 recorded oracle labels, SemViews meets both targets on 99.63% of queries while saving 28%–45% of oracle calls. The only prior method in our study with the same guarantee requires 1.32×–1.71× as many calls.
When the same question is asked in different wording, views cut calls by a further 27%–36%, with both targets met on at least 99.8% of such queries; similarity caches and entailment‑based reuse achieve the targets on only 17%–47% of queries.
Review