Source-linked AI summary
Compositional Online Learning for Semantic Data Processing Systems
Paweł Liskowski, Fuheng Zhao, Benjamin Han, Anupam Datta, Dimitris Tsirogiannis
TL;DR
Semantic data processing systems face dominant LLM costs, but their long round-trips can hide CPU-side learner updates. This paper develops compositional online learning at the LLM call boundary and instantiates it in Cortex AISQL. The two learning components yield an 11.4× upper bound under independence and a realistic figure near 8× after cross-component interactions.
Problem
Semantic data processing systems need to optimize expensive per-row LLM calls, while prior systems study components separately or use learners designed for relational-latency regimes.
Method
The paper combines execution-time components across decision granularity and learner update cadence, hiding trainer updates inside subsequent LLM round-trips.
Results
11.4× is the analytical upper bound under independence, reduced to roughly 8× by three cross-component interactions on a representative conjunction-filter workload.
Takeaways & Limitations
The framework makes compositional online optimization feasible at the LLM call boundary and provides cost semantics for combining its learning components.
Takeaways & Limitations
The guarantee is only as strong as the weakest component, and cache effects remain outside the displayed decomposition because hit rates can vary with workload interactions.
Abstract
from arXiv · showhide
An LLM call in a semantic data processing system is expensive enough to dominate query cost, yet slow enough to hide a CPU-side learner's update behind its round-trip. In production, LLM compute accounts for $80-90\%$ of query cost, and each call costs $10^5-10^7\times$ a relational predicate. The latency window inverts a design constraint of classical adaptive query processing, where online learners had to stay lightweight to avoid dominating the predicates they optimize. At LLM latency, per-call gradient steps and per-batch threshold solves fit inside the round-trip. We develop compositional online learning at the LLM call boundary: a framework for combining online-learning components in semantic data processing systems. Each component makes execution-time decisions and refines its learned artifacts online. The design space spans two axes, decision granularity and learner update cadence, and the components share a single learning pattern that hides each trainer step inside the next LLM round-trip. A production case study in Cortex AISQL composes three components: a memoization layer, an online per-call filter-ordering learner, and an online per-batch cascade-routing learner. A conditional cost decomposition assigns each learning component to a distinct factor of per-row LLM cost. Under independence, the two learning components compose multiplicatively to an $11.4\times$ upper bound on a representative conjunction-filter workload. Self-selection at the cascade boundary, sample-budget shrinkage, and selectivity-estimation drift reduce it to a realistic figure near $8\times$.
1 Introduction
Semantic data processing systems face dominant LLM costs, creating a latency regime where CPU-side online learning can run during LLM round-trips. The paper asks how multiple such online-learning components compose and instantiates a framework in Cortex AISQL.
- Motivation: 80–90% of total query cost comes from LLM compute, while each call costs 10^5–10^7× a relational predicate.A million-row AI FILTER can trigger up to a million LLM calls, with end-to-end latency measured in hours.
- Motivation: The LLM round-trip is wide enough to hide a CPU-side learner update instead of placing it on the critical path.Each call takes hundreds of milliseconds, allowing learner computation to fit inside the round-trip.
- Open Problem: The composition question remains open because prior semantic-query and adaptive-query systems study components in isolation or operate at different latency scales.Existing approaches optimize individual components offline, at compile time, or with learners designed for relational latencies.
- Case Study: Cortex AISQL composes response caching, per-call filter ordering, and per-batch cascade routing as a production case study.The two learning components target distinct cost factors and are analyzed through a composition theory.
- Framework: The framework organizes compositional online learning around decision granularity, learner update cadence, and a shared pattern for hiding trainer updates inside LLM round-trips.This makes online per-call gradient steps and online per-batch threshold fits feasible at scale.
- Results: 11.4× is the analytical upper bound under independence, while three cross-component interactions reduce the realistic figure to roughly 8×.The result is reported for a representative conjunction-filter workload.
2 The Framework: Online-Learning Composition at the LLM Call Boundary
The framework exploits LLM latency to run online learners concurrently with calls, organizing components by decision granularity and update cadence. Its pipeline buffers supervision, updates learned artifacts, and composes caching, filter ordering, and cascade routing across distinct cost factors.
- Latency Window: LLM latency is 10^5–10^7× relational predicate cost, making per-call gradients, per-batch threshold fits, and combinatorial planning passes feasible.CPU work that fits in a few milliseconds can hide inside the LLM round-trip.
- Pipelined Pattern: Each online component predicts a decision, trains concurrently with the next LLM call, and records the outcome for the next update.The three-phase cycle keeps the trainer one round behind supervision without blocking execution.
- Update Cadence: Per-call cadence supports lightweight updates such as a single gradient, whereas per-batch cadence can hide heavier Bayesian or constrained-optimization updates.The two cadences are not interchangeable because their available latency windows differ.
- Update Cadence: Hiding is necessary for synchronous per-call refits but mainly smooths latency for infrequent per-batch refits.Typical per-batch schedules yield O(log n) update events per query; caching instead uses exact memoization.
- Layered Design Space: The design space crosses decision granularity—per-call, per-row, or per-batch—with learner cadence: online, compile-time, offline, or none.Response caching, filter ordering, and cascade routing occupy three instantiated cells.
- AISQL Instantiation: Larch targets expected LLM-evaluated predicates per row at online per-call cadence, while GAMCAL targets oracle delegation at online per-batch cadence.The two factors are formalized in the conditional per-row cost decomposition.
- Composition: The two learning components compose multiplicatively under independence, while caching suppresses both components on exact-match hits.Cache effects require conditioning because hit rates can vary with predicate position and row subpopulation.
3 The Cortex AISQL Substrate
Cortex AISQL embeds native semantic operators in relational SQL, invoking LLMs over rows or row pairs within declarative queries. Its optimizer must handle unknown semantic-operator cost and selectivity at runtime.
- Semantic Operators: Cortex AISQL provides six native semantic operators spanning filtering, classification, generation, aggregation, summarization, and joins.Each invokes an LLM on every qualifying row or row pair and composes with relational operators.
- Semantic Operators: AI FILTER, AI CLASSIFY, AI COMPLETE, AI AGG, AI SUMMARIZE AGG, and AI JOIN cover per-row, aggregation, generation, and row-pair workloads.The framework’s two learning components target AI FILTER and therefore generalize to per-row semantic predicates.
- Optimization Challenge: Semantic operators have unknown compile-time cost and selectivity because model and infrastructure determine cost, while natural-language predicates lack histograms.AISQL addresses these unknowns through cost-aware compile-time placement and runtime adaptation.
4 Filter Ordering
Larch performs online filter ordering by updating per-predicate selectivity estimates after each LLM outcome and solving the remaining AND/OR tree for a low-cost evaluation order. Its per-document signal reduces token-cost overhead substantially without startup sampling.
- Motivation: Filter ordering changes evaluation cost but not truth values because AND and OR are commutative; short-circuiting determines how many predicates are evaluated.Per-row pass probabilities make the best order depend on the individual row rather than only population averages.
- Larch-Sel: The shared selectivity MLP transfers information across predicates from the first evaluation onward.All predicates use the same model weights rather than learning separate models.
- Larch-Sel: Larch combines an online per-predicate selectivity estimator with an exact dynamic-programming solver over the AND/OR expression tree.The solver uses current selectivity estimates to choose the minimum-cost evaluation order for each partially evaluated tree.
- Larch-Sel: O(n·3^n) is the per-document runtime of Larch-Sel’s dynamic-programming recurrence, approximately 590K operations at n=10.The recurrence computes the minimum expected cost under current selectivity estimates.
- Online updates: 7 ms is the approximate CPU time for each selectivity-model training step, hidden during the next predicate’s hundreds-of-milliseconds LLM call.The pipeline is one step stale, using round t observations during training in round t+1.
- Results: Up to 19× lower token-cost overhead is reported for Larch-Sel relative to Palimpzest and Quest, with typical Mix-workload reductions of 4–8×.Larch-Sel learns per-document selectivity from calls already required by the query, avoiding the 5% startup sampling cost paid by those baselines.
5 Cascade Routing
GAMCAL routes rows through a proxy-or-oracle cascade using calibrated thresholds learned online from oracle labels. It improves the delegation–quality trade-off across diverse benchmarks, especially when proxy scores are poorly calibrated.
- Cascade design: GAMCAL partitions rows with low and high proxy-score thresholds, rejecting low scores, accepting high scores, and delegating the uncertain region to the oracle LLM.The proxy runs on every row at low cost, while oracle calls dominate cascade cost.
- Calibration: GAMCAL fits a Generalized Additive Model that maps raw proxy scores to calibrated true-positive probabilities before selecting thresholds.Threshold selection minimizes a cost-quality objective balancing F1 degradation against the delegation rate.
- Calibration: GAMCAL adds Gaussian uncertainty to the GAM mean prediction, sending poorly calibrated score regions toward exploration in the uncertain routing region.Its calibrator and thresholds refit on a doubling schedule, limiting retraining events to O(log n) per query.
- Online updates: Online batch-scale refits run concurrently with oracle calls and are installed for the next batch, leaving routing one batch behind the available labels.At roughly 4,000 rows per batch, the aggregate oracle window absorbs the CPU GAM fit and threshold solve.
- Results: F1 = 0.95 is exceeded at the best operating point on every one of six benchmarks spanning classification, filtering, and join workloads.The reported benchmark set includes six workloads and evaluates the best operating point for each.
- Results: Up to 58% fewer oracle calls are required than LOTUS’s single-pass SUPG cascade to reach F1 ≥0.95, with GAMCAL leading on five of six benchmarks.ArXiv is the exception because its proxy is already well calibrated.
6 Composition Across Learning Components
The paper formalizes sequential composition for online-learning components by matching distributions across components and weighting downstream cost by upstream fan-out. Applied to Larch and GAMCAL, the decomposition gives an 11.4× upper bound under independence and a realistic figure near 8× after cross-component interactions.
- Sequential composition: Sequential composition combines component triples when the downstream precondition matches the upstream-produced distribution, with cost c1(D0) + ϕ1(D0)·c2(D1).The upstream fan-out weights the downstream component’s expected per-input cost.
- Larch and GAMCAL: Larch forwards expected evaluated predicates to GAMCAL, whose per-predicate cost is cproxy + pdeleg(D1)·coracle.Larch has zero direct LLM cost, while GAMCAL’s delegation rate is evaluated on Larch’s actual postcondition.
- Cost decomposition: Larch reduces expected predicate evaluations per row, while cascade routing reduces oracle delegation; under independence, these reductions compose multiplicatively.The two components target distinct factors of the per-row LLM cost, with proxy cost included in the cascade factor.
- Cost assumptions: The conjunction decomposition assumes uniform per-call costs, independent predicate selectivities, and conditioning on cache misses.Cache hits remain outside the displayed model, while expected predicate evaluations generalize to AND/OR trees through a dynamic-programming recurrence.
- Analytical case study: 11.4× is the upper bound for the representative workload under independence and matched-precondition calibration.The workload uses N = 10^6 rows, m = 5 predicates, and cproxy/coracle ≈ 0.05; the optimized product is 0.0875× baseline.
7 Related Work
Related systems generally use offline or compile-time learning, while classical adaptive query processing operates online only at relational latency. Cortex AISQL fills the online per-call and online per-batch cells in the LLM-bound design space.
- Design-space comparison: Cortex AISQL is the only described system occupying both online per-call and online per-batch cells in the LLM-bound regime.Other LLM-bound systems use one-shot or offline cadences, while classical AQP operates online at relational latency.
- Classical AQP: Classical adaptive query processing uses online learners at relational latency, where sub-microsecond predicate costs constrain learner footprint.These techniques transfer conceptually, but the LLM latency window permits substantially larger learner updates.
- Filter ordering: Prior LLM-aware filter-ordering systems learn population-level selectivities during sampling and freeze them before execution, unlike Larch’s online per-call refinement.Larch occupies a cadence previously left empty by the cited filter-ordering systems.
- Cascade routing: Prior cascade systems calibrate offline or at compile time, whereas GAMCAL extends cascade routing to online per-batch cadence.The cited prior systems fit calibration sets or proxy classifiers before deployment and then freeze them.
8 Discussion
The discussion extends the framework toward joint controllers, cross-query learning, future optimization layers, and unified quality contracts. It also identifies open directions and scope boundaries for composing these components in production.
- The framework leaves four directions open: expanding the design surface, tightening composition, extending learning across queries, and reconciling heterogeneous quality semantics.
- Future Layers in the Design Space: Future layers such as model substitution, prompt structure, and adaptive batching introduce decisions coupled through shared prompt, model, and batch choices.
- Joint optimization across components: A joint controller could exploit interactions by adapting cascade training to Larch’s selected stream, shrinking samples after short-circuiting, and filtering gradient signals by cascade regions.
- Cross-query learning: Cross-query learning could preserve selectivity histories, calibration curves, and distilled cost models, but must address prompt and data drift, template rebinding, and isolation boundaries.
- Quality contracts in production: Production quality contracts span hard guarantees, calibrated trade-offs, and best-effort refinement, so the composed system’s guarantee is the weakest component guarantee.
9 Conclusion
The paper presents latency-window-aware compositional online learning for semantic data systems, using caching, filter ordering, and cascade routing at different update cadences. Its composition analysis gives an 11.4× independent upper bound and a realistic figure near 8×, while motivating empirical and architectural extensions.
- The framework uses the LLM round-trip to hide CPU-side learner updates, enabling online optimization at the LLM call boundary.
- Filter ordering reduces predicates evaluated per row, cascade routing reduces oracle escalations, and response caching avoids repeated calls through exact memoization.
- 11.4× is the analytical upper bound for total cost reduction under independence on a representative conjunction-filter workload.
- Roughly 8× is the realistic reduction after three structural cross-component interactions affect the independent composition estimate.
- Future work includes empirical validation at scale, cross-query learning, joint controllers, and additional layers in the design space.