Compositional Online Learning for Semantic Data Processing Systems

Paweł Liskowski; Fuheng Zhao; Benjamin Han; Anupam Datta; Dimitris Tsirogiannis

cs.DBAug 27, 2026

Compositional Online Learning for Semantic Data Processing Systems

Authors: Paweł Liskowski, Fuheng Zhao, Benjamin Han, Anupam Datta, Dimitris Tsirogiannis

Organizations: Snowflake Inc.

Abstract

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$ .

Figures & tables

Panel of Figure 1 — Figure 1: The pipelined online-learning pattern. Phase 1 predicts the next decision and dispatches a background trainer step. Phase 2 issues the LLM call, which hides the trainer’s compute. Phase 3 records the outcome into the optimizer’s state. § 4 instantiates this at per-call cadence (one gradient step per LLM call). § 5 instantiates it at per-batch cadence (calibration fit and threshold solve on a doubling schedule).

Layer	Decision granularity	Learner update cadence	Artifact / state	Instance
Response caching	per-call	none (memoization)	exact-match response cache	AISQL response cache (§ 2.3 )
Filter ordering	per-call	online per-call	selectivity model + DP solver	Larch (§ 4 )
Cascade routing	per-row	online per-batch	calibrated GAM probability map	GAMCAL (§ 5 )
Prompt caching	per-call	none (memoization)	prefix cache + affinity map	future direction (§ 8.1 )
Model substitution	per-batch	one-shot at compile time	distilled student net	future direction (§ 8.1 )
Prompt structure	per-call	online per-batch	prompt template / rewriting rules	future direction (§ 8.1 )

Table 1: The layered design space. Three rows are populated by the AISQL instantiation: response caching (§ 2.3 ), filter ordering (§ 4 ), and cascade routing (§ 5 ). The remaining four rows name LLM-bound research directions revisited in § 8.1 . AQP-style layers populate analogous decisions at relational latency and are discussed in § 7 rather than in this LLM-bound design space.

Dataset	PZ	Quest	Larch-Sel
GovReport	21.3%	33.6%	5.1%
PubMed	26.1%	29.5%	6.5%
BigPatent	28.3%	29.7%	3.6%

Table 2: Token-overhead percentages relative to the per-row optimal lower bound on the Mix workload (50% AND, 50% OR) across three datasets [ 20 ] . Lower is better.

Dataset	SUPG-SP (LOTUS)	SUPG-IT	GAMCAL
ArXiv	55.6%	61.9%	61.6%
BoolQ	69.7%	58.2%	29.3%
IMDB	69.9%	69.1%	68.4%
MMLU	67.4%	62.9%	43.9%
NYT	21.9%	22.4%	17.0%
SST-2	28.6%	31.6%	21.2%

Table 3: Minimum delegation rate

d

required to reach

F_{1}\geq 0.95

across all six benchmarks [ 21 ] . Lower is better. Bold marks the best algorithm per row. GAMCAL leads on five of six datasets, often by a wide margin.

Configuration	$\bar{e}$	$p_{\text{deleg}}$	Cost (rel.)
Baseline (no optimization)	5.0	1.0	1.00
+ Filter ordering alone	$\approx 1.25$	1.0	$\approx 0.25$
+ Cascade routing alone	5.0	$\approx 0.30$	$\approx 0.35$
Both learning components (upper bound)	$\approx 1.25$	$\approx 0.30$	$\approx\mathbf{0.0875}$ ( $11.4\times$ )

Table 4: Cost relative to the no-optimization baseline at

m=5

and

c_{\text{proxy}}/c_{\text{oracle}}=0.05

. The two-component upper bound is

11.4\times

under § 6.2 ’s independence assumption and matched-precondition calibration (

D_{1}=D_{1}^{\star}

in the sense of § 6.1 ). § 6.4 catalogs cross-component interactions that lower the realistic figure to roughly

8\times

LLM Routing

Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.

See all 355 papers

Jul 26, 2026

Kalypso: Relational LLM Serving

Large language models are increasingly used as semantic operators for filtering, extracting, ranking, joining, and transforming unstructured data. Existing semantic query processing systems invoke request-centric LLM serving systems that are unaware of the query plan, leaving substantial performance opportunities unused. This paper introduces relational LLM serving, an abstraction that makes LLM serving aware of semantic query structure while preserving query semantics and output accuracy. The key opportunity is pipelined execution across semantic operators: when intermediate tuples flow directly from one operator to the next, their KV-cache state can be reused instead of recomputed. We present Kalypso, a relational LLM serving system that exposes an API for semantic query plans and executes them using an adaptive, memory-aware scheduling algorithm. Kalypso addresses a new online scheduling problem in which pipelined operator execution is coupled with GPU memory pressure management to reuse KV-cache state in the serving engine before eviction. Its scheduler continuously adjusts memory allocations to balance upstream parallelism, downstream progress, and GPU utilization. Our evaluation shows that Kalypso improves query completion time over baselines using request-centric LLM serving, with speedups up to 4.57x across diverse workloads, demonstrating that query-aware LLM serving can substantially improve the efficiency of semantic query execution.

Hojae Son, Md Ashraful Islam, Huy Gia Cao +2

UMass Amherst, USA

LLM Serving LLM Inference Scheduling LLM Inference Serving KV-Cache Reuse

Ask PDF

Aug 30, 2025

Access Paths for Efficient Ordering with Large Language Models

In this work, we present the LLM ORDER BY semantic operator as a logical abstraction and conduct a systematic study of its physical implementations. First, we propose several improvements to existing semantic sorting algorithms and introduce a semantic-aware external merge sort algorithm. Our extensive evaluation reveals that no single implementation offers universal optimality on all datasets. From our evaluations, we observe a general scaling relationship between sorting cost and the ordering quality for comparison-based algorithms. Building on these insights, we design a budget-aware optimizer that utilizes heuristic rules, LLM-as-Judge evaluation, and consensus aggregation to dynamically select the near-optimal access path for LLM ORDER BY. In our extensive evaluations, our optimizer consistently achieves ranking accuracy on par with or superior to the best static methods across all benchmarks. We believe that this work provides foundational insights into the principled optimization of semantic operators essential for building robust, large-scale LLM-powered analytic systems.

Fuheng Zhao, Jiayue Chen, Yiming Pan +7

Snowflake · University of Chicago · 3UC Los Angeles +1

Large Language Model-Guided Optimization

Ask PDF

Mar 5, 2026

Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm

Large language models (LLMs) are increasingly used for semantic query processing over large corpora. A set of semantic operators derived from relational algebra has been proposed to provide a unified interface for expressing such queries, among which the semantic filter operator serves as a cornerstone. Given a table T with a natural language predicate e, for each tuple in the relation, the execution of a semantic filter proceeds by constructing an input prompt that combines the predicate e with its content, querying the LLM, and obtaining the binary decision. However, this tuple-by-tuple evaluation necessitates a complete linear scan of the table, incurring prohibitive latency and token costs. Although recent work has attempted to optimize semantic filtering, it still does not break the linear LLM invocation barriers. To address this, we propose Clustering-Sampling-Voting (CSV), a new framework that reduces LLM invocations to sublinear complexity while providing error guarantees. CSV embeds tuples into semantic clusters, samples a small subset for LLM evaluation, and infers cluster-level labels via two proposed voting strategies: UniVote, which aggregates labels uniformly, and SimVote, which weights votes by semantic similarity. Moreover, CSV triggers re-clustering on ambiguous clusters to ensure robustness across diverse datasets. The results conducted on real-world datasets demonstrate that CSV reduces the number of LLM calls by 1.28-355x compared to the state-of-the-art approaches, while maintaining comparable effectiveness in terms of Accuracy and F1 score.

Nan Hou, Kangfei Zhao, Jiadong Xie +1

The Chinese University of Hong Kong · Beijing Institute of Technology · HKUST (Guangzhou)

LLM Inference Acceleration Semantic Search

Ask PDF

Abstract

LLM Routing

Explore similar work

Kalypso: Relational LLM Serving

Access Paths for Efficient Ordering with Large Language Models

Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm