Source-linked AI summary
The Stretto Execution Engine for LLM-Augmented Data Systems
Gabriele Sanmartino, Matthias Urban, Paolo Papotti, Carsten Binnig
TL;DR
LLM-augmented data systems lack both global query-level quality guarantees and sufficiently fine-grained runtime–accuracy choices. Stretto combines constrained gradient-based optimization with compressed KV-cache operators to address these gaps, and reports reliable guarantees alongside improved performance over existing systems.
Problem
LLM-augmented data systems lack global quality guarantees and expose coarse physical choices that leave gaps along the runtime–quality curve.
Method
Stretto jointly selects and parameterizes semantic operators while allocating error budgets under global precision and recall constraints, using compressed KV caches to create fine-grained physical choices.
Results
Stretto reliably provides global quality guarantees and significantly outperforms existing systems across the reported evaluation.
Takeaways & Limitations
A query optimizer can use inference internals such as compressed KV caches to navigate dense cost–quality trade-offs in LLM-native data processing.
Takeaways & Limitations
Stretto currently focuses on semantic filter and map operators; semantic group-by and aggregation operations are not supported.
Abstract
from arXiv · showhide
LLM-augmented data systems enable semantic querying over structured and unstructured data, but executing queries with LLM-powered operators introduces a fundamental runtime-accuracy trade-off. In this paper, we present Stretto, a new execution engine that provides end-to-end query guarantees while efficiently navigating this trade-off in a holistic manner. For this, Stretto formulates query planning as a constrained optimization problem and uses a gradient-based optimizer to jointly select operator implementations and allocate error budgets across pipelines. Moreover, to enable fine-grained execution choices, Stretto introduces a novel idea on how KV-caching can be used to realize a spectrum of different physical operators that transform a sparse design space into a dense continuum of runtime-accuracy trade-offs. Experiments show that Stretto outperforms state-of-the-art systems while consistently meeting quality guarantees.
1 INTRODUCTION
Stretto addresses two gaps in LLM-augmented data systems: missing end-to-end quality guarantees and coarse physical operator choices. It combines holistic constrained optimization with KV-cache-enabled operators to navigate runtime–accuracy trade-offs more finely.
- The Missing Pieces: Existing systems may optimize operators locally, ignoring error propagation and the quality of final query results.Local guarantees can therefore produce suboptimal pipeline decisions.
- The Missing Pieces: Global quality targets can be wastefully split across operators when some filters are easier than others.The paper’s medical example illustrates reallocating error budgets toward harder operators.
- The Missing Pieces: Coarse choices such as small versus large models leave a granularity gap between runtime and quality.Smaller models may miss targets, while the next option can be an order of magnitude more expensive.
- Our Approach: Stretto formulates planning as constrained optimization that minimizes global execution cost subject to end-to-end precision and recall constraints.Its optimizer models interactions among operators and dynamically reallocates error budgets.
- Our Approach: Compressed KV caches create multiple physical implementations that systematically trade runtime for accuracy.Offline compression produces a ladder of reusable KV-cache profiles for multimodal data.
- Contributions: Stretto’s contributions combine holistic gradient-based optimization, KV-cache-enabled operators, and systematic evaluation across datasets and queries.The reported evaluation includes a 42% speed-up on SemBench.
2 STRETTO OVERVIEW
Stretto translates multimodal queries into logical plans, globally optimizes their semantic operators, and executes cascades of physical operators. Its KV-cache-based design expands sparse model choices into a dense, navigable runtime–quality space.
- Overview: Stretto represents multimodal queries as logical plans containing relational and semantic operators with tunable physical implementations.Semantic filters may use LLM-based or embedding-based implementations.
- Global Optimization: The optimizer jointly optimizes semantic operators instead of decomposing a global quality target into independent per-operator constraints.This avoids overly conservative and costly plans.
- Global Optimization: Gradient-based optimization allocates allowable error across operators while optimizing model choices and continuous parameters together.Thresholds can affect the models required by downstream operators.
- Physical Execution: Physical plans can cascade increasingly expensive operators, forwarding unsure tuples to more accurate operators after cheaper operators process easy cases.This reduces the load on high-cost models.
- Navigable Search Space: Precomputed compressed KV caches expose fine-grained runtime–accuracy choices and are reused across queries on a dataset.Query-agnostic compression supports reusable profiles across semantic operators.
- Navigable Search Space: Stretto’s search space combines model sizes, KV-cache compression ratios, and other operator variants to systematically navigate cost and result quality.This contrasts with prior spaces dominated by small-versus-large models and limited cascades.
3 GLOBAL OPTIMIZATION
Stretto’s optimizer selects and parameterizes physical plans under probabilistic global quality guarantees. It uses sampling, Bayesian bounds, continuous relaxation, gradient-based search, and operator reordering to minimize execution cost.
- Optimization Goal: The optimizer selects models, thresholds, KV-cache compression ratios, and operator ordering to minimize cost under global quality constraints.The physical plan is chosen from a mixed discrete and continuous search space.
- Formal Guarantees: Stretto compares optimized plans with a golden highest-quality plan and evaluates uncertainty using sampled data from the input distribution.The golden plan provides the reference for quality metrics.
- Formal Guarantees: Bayesian credible intervals provide probabilistic guarantees that true precision and recall exceed user-specified targets.The stated framework uses 95% confidence and applies targets at the query level.
- Optimization Challenges: Mixed discrete model choices and continuous thresholds make purely combinatorial or local optimization unsuitable for global targets.A threshold for one operator can affect model selection for another operator.
- Gradient-Based Optimization: Gradient descent allocates stricter quality targets to operators where quality improvements are cheaper instead of splitting targets evenly.The approach uses estimated cost–quality changes to guide model replacement and budget allocation.
- Optimization Procedure: The optimization procedure pulls up semantic operators, profiles them on samples, applies gradient-based optimization, and reorders selected operators.Profiling records selectivity, runtime, and outputs for available physical operators; guarantees are enforced through Bayesian bounds.
4 DETAILS OF QUERY OPTIMIZATION
Stretto optimizes semantic-operator pipelines by continuously exploring physical plans while estimating runtime, precision, and recall against a gold pipeline. It uses Bayesian bounds and gradient descent to select operators and satisfy end-to-end quality constraints.
- Pipeline model: A semantic filter is implemented as a cascade of physical operators, each using a distinct model, KV-cache compression ratio, or simpler implementation.Operators process tuples sequentially and pass only unsure tuples to later operators.
- Cost estimation: Stretto estimates pipeline cost from operator per-tuple costs and the number of tuples remaining unsure after earlier operators.Operators are intended to be ordered by increasing cost so that expensive operators process fewer tuples.
- Quality estimation: Pipeline precision and recall are estimated by comparing the optimized plan with a gold pipeline using true positives, false positives, and false negatives on a sample.The gold pipeline uses the most expensive operator for all input items.
- Statistical guarantees: Repeated gradient-based exploration makes ordinary confidence intervals invalid because repeated tests introduce optimism bias, while broad corrections become overly conservative.Stretto therefore uses a Bayesian approach for estimating quality bounds during optimization.
- Continuous relaxation: Continuous relaxation replaces discrete operator-selection indicators with pick factors in [0, 1], making operator choices and tuple outcomes differentiable during optimization.The temperature is gradually reduced to zero before execution so deployed operators make discrete decisions.
- Constrained optimization: The optimizer minimizes a loss combining cost with precision and recall penalties, activating quality penalties when the current pipeline violates its targets.Adam optimization is used while requiring the constraint losses to reach zero after optimization.
5 KV CACHE–ENABLED OPERATORS
Stretto turns precomputed KV caches into interchangeable physical implementations for semantic filters and maps. Multiple model and compression profiles expose runtime–quality trade-offs while requiring explicit management of storage and modality differences.
- Offline caching: Stretto precomputes KV caches for text and images, then loads selected model–compression profiles at query time to bypass the expensive prefill phase.The profiles are reused across queries on the dataset.
- Profile selection: Operators differ in their tolerance for cache compression, so Stretto maintains multiple profiles with distinct cost and quality characteristics.Simple filters can tolerate more aggressive compression than extraction workloads.
- Cache management: The cache repository is curated by evaluating model–ratio profiles and pruning dominated options to cover relevant quality–efficiency trade-offs within a disk budget.Image workloads tolerate more aggressive compression because their visual tokens have higher spatial redundancy than text tokens.
- Physical operators: Each KV-cache profile creates a separate physical implementation of the same logical operator, enlarging the search space for explicit quality–cost trade-offs.The KV cache–enabled operators support semantic filters and maps.
- Execution effects: Aggressive compression reduces cache footprint and enables larger batches, resulting in lower latency when processing the full dataset.
6 EXPERIMENTS
Stretto is evaluated across five multimodal datasets and 300 queries, testing global quality guarantees, runtime, KV-cache trade-offs, and optimization strategies. It reliably meets targets while using fine-grained operators and global error-budget allocation to find efficient plans.
- Accuracy and Runtime: Stretto is the only evaluated method that reliably provides global quality guarantees.Lotus fails to meet recall and precision targets for 6.4% and 7.6% of queries, while Abacus lacks statistical guarantees.
- Accuracy and Runtime: Stretto finds faster guaranteed plans than Lotus on all datasets, with order-of-magnitude speedups observed on Movies.Stretto searches across compressed operators, combines operators, and can reorder cascades to apply cheap pre-filters first.
- KV Cache–enabled Operators: KV-cache compression creates a runtime–quality continuum: more aggressive compression reduces execution time while lowering quality.The trend is consistent across visual and text modalities, and the resulting configurations can be pruned during pre-computation.
- KV Cache–enabled Operators: 1.36 speedup is achieved at the 0.9 Recall / 0.9 Precision target when compressed operators are added, relative to precomputed uncompressed KV caches.Across all datasets, speedups are especially large for low targets; Movies reaches 4.6 at the lowest target and 2.75 at the strictest target.
- Global vs. Local Optimization: Global optimization meets targets with fast plans, whereas equal target splitting raises costs and independence assumptions can sacrifice guarantees.At 0.9 recall and precision, equal splitting takes 1.2 times as long as Stretto; independence can produce faster plans but more target failures.
7 RELATED WORK
Related work addresses guarantees, cost–accuracy optimization, KV-cache efficiency, and LLM serving, but Stretto combines end-to-end guarantees with KV-cache-aware physical operators.
- Approximate query processing provides statistical guarantees under sampling, but LLM-native pipelines require task-level precision and recall guarantees.
- Cost-Qual… MOAR optimizes semantic-operator pipelines through logical and prompt-level rewrites for cost and accuracy.
- Stretto differs by targeting end-to-end pipeline guarantees and expanding the physical design space with KV-cache-aware operators.
- Prior KV-cache work primarily reduces inference memory or time, whereas Stretto treats compressed caches as reusable physical representations and optimizer cost-quality knobs.
- LLM serving systems optimize batching, memory management, and cache reuse for inference, rather than treating KV caches as persistent query-system representations.
8 CONCLUSION
Stretto optimizes semantic-operator pipelines under global quality constraints using gradient-based planning and compressed KV-cache physical operators. The evaluation reports substantial gains while showing that exposing inference internals enables scalable LLM-native data processing.
- Stretto optimizes semantic-operator pipelines under global quality constraints with a gradient-based optimizer that minimizes cost while satisfying user-defined bounds.
- Compressed KV caches become persistent, reusable physical representations that expose a dense ladder of cost-quality trade-offs.
- The evaluation reports that Stretto significantly outperforms existing systems.
- The conclusion identifies exposing inference internals such as KV caches to the query optimizer as essential for scaling LLM-native data processing.