Can Stretto Optimize Accuracy and Performance in LLM-Augmented Data Systems?

A global target replaces per-operator accuracy targets

Semantic data systems run queries that mix ordinary database operators with semantic operators such as LLM-based filters, maps and joins. These operators have a design space that classical operators do not: a filter can use a small or a large model, an embedding-similarity threshold, or a compressed cache variant, and each choice changes both runtime and result quality. The paper's starting claim is that existing systems handle this runtime-accuracy trade-off locally. Lotus, for example, optimizes each operator in isolation and guarantees quality per operator, which ignores how errors accumulate along a pipeline. Abacus works at the query level but explores plans with heuristics and offers no statistical guarantee on result quality.

Stretto's alternative is to reason about accuracy end-to-end. A user states a required quality level for the final result, such as a global recall of 0.9, and the optimizer must find a plan that meets it. The paper motivates this with a medical retrieval scenario: a researcher wants patients with abnormal lung scans and a textual COVID-19 diagnosis, and cares about the recall of the returned set, not about the accuracy of any intermediate filter. That reframing matters because a plan that looks safe operator by operator can still miss the end-to-end target once several selective stages are chained.

Planning becomes a constrained optimization problem

Stretto formulates query planning as a constrained optimization problem and solves it with a gradient-based optimizer. The optimizer jointly selects operator implementations and allocates error budgets across the full query plan, so the accuracy allowed at one stage depends on what the remaining stages are expected to contribute. This is the mechanism behind the global guarantee: the target is a budget to be divided, not a fixed per-operator setting.

The paper also reorders operators. It uses dynamic programming over subsets of physical operators, tracking for each subset the minimum execution cost and the number of tuples still flowing to each logical operator. Executing an operator costs in proportion to the tuples it processes, and the remaining tuple counts are updated by that operator's selectivity. Because a selective filter placed early shrinks the input to later, more expensive LLM calls, the ordering decision and the implementation decision interact, which is why they are handled inside one optimization rather than in separate passes.

Compressed KV caches create a spectrum of operators

To give the optimizer something to choose between, Stretto introduces a technique built on KV-cache compression. In autoregressive LLM decoding, the KV cache stores intermediate attention state; Stretto treats a materialized, compressed cache as a reusable physical representation of the base items, so the same prefill work can be shared across operators and queries instead of being repeated. Compression ratio then becomes a knob that produces a spectrum of physical execution strategies with controllable runtime-accuracy trade-offs.

The experiments instantiate this concretely. Smaller models are Llama-3.1 8B and Llava-Next 8B, larger ones are the 70B/72B variants, and the optimizer can also choose compressed-cache operators: Llava-Next 8B at compression ratio 0.9 and Llava-Next 72B at 0.99 for images, Llama-3.1 8B and 70B both at 0.8 for text. Under the strict storage budget assumed in most experiments, these operators cost 100 GB on the largest text dataset, Email, and 88 GB on the largest image dataset, Artwork. The uncompressed largest models serve as the golden models, so the guarantee is stated relative to the best available model rather than to human ground truth unless labels are supplied.

Guarantees are checked against a golden plan on a sample

The guarantee is statistical, not a proof about every possible input. During profiling, Stretto records operator outputs on a data sample and simulates candidate cascades on that sample. It compares a cascade's output with the output of the golden cascade, which runs the most expensive operator on all items, and counts true positives, false positives and false negatives to compute precision and recall. If human labels are available, they replace the golden plan in those counts.

Because the sample is small, the observed metrics can shift on the full dataset. Stretto therefore computes Bayesian lower bounds on precision and recall from a Beta posterior with an uninformative Beta(1,1) prior, using the regularized incomplete beta function. The optimizer then works with these lower bounds, so a plan is accepted only if its pessimistic estimate still clears the target. The evaluation reads this directly: the accuracy plots show achieved divided by target, and a method meets its statistical guarantee when the entire boxplot, whose lower whisker is the 95% credible level, sits above 1.0.

Stretto meets targets where baselines miss them

The benchmark covers five datasets: Artwork with 1000 images plus tabular data, Rotowire with 728 basketball reports, Email with 1000 Enron corporate emails, Movie with 10,000 text reviews, and E-Commerce with 1000 images and descriptions. Since the datasets contain too few queries, the authors generate 60 to 80 queries per dataset from six templates each, with one to four semantic operators per query. Baselines are the Pareto-Cascades optimizer from Abacus and the SupG optimizer from Lotus, both integrated into Stretto's own system to isolate optimizer behavior. Lotus receives the global target split evenly into per-operator targets, and its cascades are limited to an uncompressed 8B model followed by the golden model.

On accuracy, Stretto is described as the most reliable of the three, meeting the target overall, while the baselines' achieved-to-target distributions fall below 1.0 in places. On runtime, which includes profiling, optimization and execution of all queries, Stretto outperforms Lotus on all datasets. The comparison is deliberately narrow: Abacus cannot statistically guarantee quality targets and cannot tune continuous parameters such as thresholds, so those are fixed at defaults, and systems without an exposed optimizer, such as the original Palimpzest and ThalamusDB, are excluded as baselines.

The optimizer drives most of the gain, compression adds more

An ablation separates the two contributions. Removing optimization and comparing against full Stretto without compressed-cache operators, the mean speedup is 5.34× at a precision/recall target of 0.5, 2.60× at 0.7 and 1.71× at 0.9, with a maximum of 32.09× and 83% of cases above 1.01× across all targets. Adding the compressed-cache operators on top of the optimized plan gives a further mean speedup of 1.91× at 0.5, 1.47× at 0.7 and 1.07× at 0.9, reaching up to 22.85×. The paper reports that the KV operators add speedups of up to 22× when the targets leave enough room for them to be used.

The pattern is the decision-relevant part: the looser the target, the more room the optimizer has to substitute cheaper or compressed operators, and the larger the gain. At a 0.9 target the compression step contributes little on average, because few compressed variants can satisfy such a tight bound. This is a trade-off the user controls through the target, not a fixed property of the engine.

Assuming operator independence fails as pipelines grow

A separate experiment varies the number of semantic operators in the plan. Stretto meets both precision and recall targets with two, three and four operators, while a variant that assumes operators are independent stops meeting them at four operators, missing the precision target in 7.4% of cases and the recall target in 6.7%. The independence assumption is only slightly faster than global optimization with more operators, and in most cases not faster at all. Runtime grows roughly linearly with operator count, because more operators mean more execution and profiling work, and longer pipelines tend to be more selective, which pushes the optimizer toward more conservative operator choices.

The paper also tests what happens when the guarantee is anchored to human labels instead of the golden plan, using 15 queries across the five datasets. Optimizing against golden-plan labels and evaluating against human labels still meets the target in most cases, so the best model is a decent proxy, though failures are somewhat more frequent because human labels are stricter. When optimizing against human labels, a target can be genuinely unreachable if even the largest model is not good enough; in that case Stretto refuses to execute the query and the user must lower the target or change the best model. When the optimizer does claim a plan meets a human-label target, the paper reports that it does so with high probability.

The target tightness decides the payoff

The paper's own priority is that exposing inference internals, specifically the KV cache, to the query optimizer is what makes LLM-native data processing scale, and its results support a sharper reading: the value of Stretto's joint planning is largest when the quality target is loose enough to permit aggressive substitution, and it narrows as the target approaches what the best model alone can deliver. At a 0.9 precision/recall target, the optimizer still contributes a mean 1.71× speedup, but the compression layer adds only 1.07× on average.

That split is the practical threshold. A user who needs a tight guarantee should expect the gain to come mainly from choosing and ordering operators, with compressed caches rarely usable; a user who can accept a 0.5 target can let the optimizer exploit both levers and see mean speedups above 5× from optimization alone. The guarantee itself is bounded by its reference point: it is stated against the golden plan unless human labels are supplied, and the paper notes that extending Stretto to further modalities and operators such as semantic aggregation remains future work.

Sources used in this answer