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

Kalypso: Relational LLM Serving
Jul 26, 2026Hojae Son, Md Ashraful Islam, Huy Gia Cao +2LLM Serving LLM Inference Scheduling
UMass Amherst, USA
Access Paths for Efficient Ordering with Large Language Models
Aug 30, 2025Fuheng Zhao, Jiayue Chen, Yiming Pan +7Large Language Model-Guided Optimization
Snowflake · University of Chicago · 3UC Los Angeles +1
Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm
Mar 5, 2026Nan Hou, Kangfei Zhao, Jiadong Xie +1LLM Inference Acceleration Semantic Search
The Chinese University of Hong Kong · Beijing Institute of Technology · HKUST (Guangzhou)

Jul 26, 2026J/K move · Enter open · S save

Kalypso: Relational LLM Serving

Hojae Son, Md Ashraful Islam, Huy Gia Cao, Hui Guan+1

UMass Amherst, USA

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

Open paper AskPDF arXiv

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.

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