arXiv:2602.04430v3 Announce Type: replace Abstract: Semantic data systems enable querying over both structured and unstructured data using LLMs, but a central challenge is navigating the performance-accuracy trade-off when selecting among alternative strategies for executing semantic operators. In this paper, we present Stretto, a new execution engine for semantic query processing that combines a novel optimizer with a rich set of physical execution strategies for semantic operators. Unlike prior work, Stretto provides global - rather than per-operator - accuracy guarantees while optimizing query performance. To this end, Stretto formulates query planning as a constrained optimization problem and employs a gradient-based optimizer to jointly select operator implementations and allocate error budgets across the full query plan. Furthermore, to enable diverse execution choices, Stretto introduces a new technique that builds on KV-cache compression to realize a spectrum of physical execution strategies for semantic operators with controllable runtime-accuracy trade-offs. Experimental results demonstrate that Stretto outperforms state-of-the-art systems while consistently satisfying quality guarantees.