arXiv CSopen access

Kalypso: Relational LLM Serving

Kalypso: Relational LLM Serving Hojae Son

Md Ashraful Islam

Huy Gia Cao

UMass Amherst, USA Amherst, Massachusetts, USA [email protected]

UMass Amherst, USA Amherst, Massachusetts, USA [email protected]

UMass Amherst, USA Amherst, Massachusetts, USA [email protected]

Hui Guan

Marco Serafini

UMass Amherst, USA Amherst, Massachusetts, USA [email protected]

UMass Amherst, USA Amherst, Massachusetts, USA [email protected]

arXiv:2607.23815v1 [cs.DB] 26 Jul 2026

ABSTRACT 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.57× across diverse workloads, demonstrating that query-aware LLM serving can substantially improve the efficiency of semantic query execution.

1

INTRODUCTION

Large language models (LLMs) have emerged as a foundational abstraction for processing unstructured data in modern data management systems. Operators such as semantic filtering, extraction, ranking, and transformation can now be expressed declaratively over natural language inputs, allowing unstructured corpora to be queried and manipulated using relational-style operators [16, 19]. This shift enables a new class of data-intensive applications in analytics, retrieval-augmented reasoning, and agentic AI. To integrate LLM inference into query processing, recent semantic query processing systems (SQPSs) introduce semantic operators, which extend traditional relational algebra operators to encapsulate LLMinference with user-defined prompts [11, 14, 19, 22]. These operators act on tables whose rows may contain unstructured text fields—for example, product descriptions, clinical notes, or contract clauses—and each row’s content is serialized into an LLM prompt for processing. For example, a semantic filter can retain

products relevant to the natural-language query "{product.review} Does this review criticize battery life?" [18], while a semantic join can match patients to clinical trials using a natural-language predicate across tables [10]. Semantic queries combine multiple semantic operators into a query plan. The high cost of LLM inference represents the main bottleneck in the execution of semantic queries. SQPSs invoke inference requests on LLM models using LLM serving systems [1, 2, 13, 29, 33]. These systems optimize request scheduling, GPU memory management, and prefix caching through optimizations such as paged attention, prefix sharing, or continuous batching. However, they are request-centric: they see the workload as a sequence of separate inference requests and lack a high-level understanding of the semantic query. On the other hand, existing SQPS are aware of semantic queries but use this knowledge to reduce the number of LLM inference requests or introduce LLM model approximations rather than making LLM serving itself more efficient, which is the focus of this paper. Much prior work on semantic query execution has focused on reducing the number of expensive oracle LLM calls through cascaded execution with cheaper proxy models [6, 17, 19, 23], similaritybased pruning and pipeline decomposition [9, 11, 20, 22], request reordering to improve prefix sharing [15], and query optimization to find efficient plans [14, 21]. These techniques are effective but they still leave running inference on the LLM (or oracle LLM for implementations using cascading) as the major performance bottleneck. These optimizations are complementary to increasing LLM serving efficiency, and introduce a tradeoff between the accuracy of the query results and query running time, which is an orthogonal concern. In this paper, we propose relational LLM serving, an approach that optimizes LLM serving on tabular data by making it aware of the semantic query plan. A relational serving layer sits between SQPSs and the underlying request-centric inference engine: rather than issuing LLM requests independently, the SQPS delegates a query plan, and the serving layer decides which tuples enter which operators, when requests launch, and how KV-cache memory is allocated. This scheduling is an execution optimization that does not change query semantics or output accuracy. The key benefit of relational LLM serving is improving the KV cache hit rate through pipelining. Semantic operators process tuples by including them in the prompt of the associated LLM requests.

Son et al.

The prefill cost of computing KV cache entries for tuples is a major bottleneck in LLM serving for these workloads. By knowing the query plan, relational LLM serving systems can leverage pipelining opportunities, where an operator is invoked on intermediate tuples as soon as they are produced. When a tuple is processed by an operator and then immediately passed to the next operator, the corresponding KV cache prefix can be reused and it does not need to be recomputed. This is in contrast with the operator-at-a-time strategy common in existing SQPSs, which materialize intermediate results without using pipelining. This paper describes the design and implementation of Kalypso, the first relational LLM serving system. We start by defining an API for relational LLM serving. Recent SQPSs have proposed many efficient semantic operator semantics and implementations. Kalypso exposes a simple API to define semantic operator implementations and query plans that is general enough to support these optimizations, for example enabling the use of external proxy models or tools such as vector indexes, but also expressive enough to expose pipelining opportunities. Leveraging pipelining for semantic queries requires addressing a challenging and novel problem: online scheduling of dependent (pipelined) operators under bounded KV-cache capacity. To achieve high GPU utilization, a scheduler must process many tuples concurrently, which induces GPU memory pressure. If the scheduler runs too many upstream operator instances, memory pressure can evict cached prefixes before all its dependent downstream operators can reuse them. Conversely, if upstream operators run with too little parallelism, downstream operators may be starved for input, reducing GPU utilization. The right degree of parallelism is also influenced by data- and query-dependent factors, such as filter selectivity and join fanout, which are revealed only online, during query execution. Kalypso addresses this problem through adaptive memory-aware scheduling: it reserves a memory budget to each operator it launches, which is used to cache its prefix. It then uses memory utilization information to control how many operator instances can run concurrently without undesired prefix evictions. Making memory management robust is also challenging. The memory required by a semantic operator is not known statically, because LLM requests may generate a variable number of tokens. The memory allocation algorithm of Kalypso needs estimates of each operator’s memory demand for a tuple before executing it. Overestimating this demand reduces parallelism by reserving memory unnecessarily, whereas underestimating it may force an operator to be rerun with a larger allocation, and can cause unplanned evictions of prefixes. Kalypso also offers multiple options for pinning KV cache memory and introduces mechanisms for deadlock detection and recovery. We evaluate Kalypso on four semantic-query workloads spanning fact verification, biomedical entity matching, medical error correction, and contract entailment. Compared with request-centric execution in existing SQPSs, Kalypso reduces end-to-end query completion time by up to 4.57× while issuing a similar number of LLM calls. Controlled ablations isolate the effects of Kalypso’s key design choices. In summary, this paper makes the following contributions:

• We propose a new architecture (Section 3) and a general API for relational LLM serving that supports existing semantic operator implementations (Section 4). • We describe an adaptive scheduler for relational LLM serving, which supports pipelining and high parallelism while controlling cache evictions (Section 5). • We discuss memory management techniques such as memory estimation, pinning, and deadlock detection and recovery (Sections 6). • We compare the performance of Kalypso to existing SQPS, which rely on materialization and request-centric LLM serving systems (Section 7).

2 BACKGROUND AND MOTIVATION 2.1 Background Autoregressive LLM inference [27] consists of two phases. During prefill, the model processes all prompt tokens in parallel and materializes per-layer key-value (KV) tensors. During decode, the model generates one token at a time, attending over all previously computed KV tensors. To avoid recomputing these tensors at every step, inference engines store them in GPU memory as the KV cache. The KV cache grows linearly with sequence length and is often the primary memory bottleneck in LLM serving. Prefix caching. When multiple requests share an identical prompt prefix, the corresponding KV tensors are identical and can be computed once and reused, avoiding redundant prefill. Modern serving systems such as vLLM [13] and SGLang [33] support this through automatic prefix caching: if a new request’s prompt begins with the same tokens as a recently served request, the engine reuses the cached KV entries and only computes the novel suffix. However, this reuse is opportunistic: once a request completes, its KV-cache blocks become reclaimable and may be evicted at any time under memory pressure. There is no mechanism to guarantee that a prefix remains resident for a future request. vLLM memory model. Kalypso builds on vLLM [13], which manages KV-cache memory as a global pool of fixed-size blocks, analogous to virtual memory pages. Blocks are allocated from the pool when a request is admitted and returned when it completes; if insufficient blocks are available, new requests are deferred. Prefix sharing in semantic operators. Semantic operators naturally exhibit prefix sharing. When consecutive operators in a query plan are invoked on the same tuple, their prompts often begin with the same system instructions and tuple context. Only the trailing task instruction changes from one operator to the next. The KVcache entries for this shared prompt prefix are therefore valid for the downstream operator, as long as they remain resident in GPU memory. Figure 1 illustrates this structure for a filter → map query over a paper dataset. Let 𝑆 denote the system prompt and 𝐶 (𝑡) the paper text for tuple 𝑡. The filter prompt is [𝑆 | 𝐶 (𝑡) | 𝐼 filter ], where 𝐼 filter asks whether the paper is relevant to Alzheimer’s prevention. The downstream map prompt is [𝑆 | 𝐶 (𝑡) | 𝐼 map ], where 𝐼 map asks to extract the key points. The shared reusable prefix is therefore [𝑆 | 𝐶 (𝑡)]. The filter’s boolean output only determines whether the tuple reaches sem_map; it is not included in the map prompt.

Kalypso : Relational LLM Serving Filter Prompt - Is the paper relevant to Alzheimer's prevention? Map Prompt - Extract the key points.

KALYPSO Query Parser

System Prompt

sem_filter

Filter Prompt

System Prompt

KV Memory Monitor

True / False

Query API sem_map

LLM Engine

This paper explains Alzheimer....

Map Prompt

Data

Scheduler

Query

KV Cache Manager

enqueue

rebalance

Stage

Shared Prefix

Executor

Ops

Memory Estimator Deadlock Monitor

LLM Scheduler

Query Plan

Figure 1: Prompt structure for a filter → map query.

Throughput

SemOp_1 SemOp_2

40

1.5

30

1.0

20

0.5

10 0

2.0

Throughput (tuples/sec)

Runtime (s)

50

10

30

50

70

# Tuples

90

110

130

0.0

Figure 2: When the input table exceeds available GPU KVcache memory, downstream operators incur cache misses and must recompute the prefix. If the shared prefix remains cached, the map reuses its KV-cache state and only prefills the map-specific suffix.

2.2

Motivation

The importance of KV cache hits. Existing SQPSs execute queries operator-at-a-time, materializing intermediate results between operators. This design leads to KV-cache evictions under memory pressure, forcing downstream operators to recompute prefixes. We now quantify the impact of these cache misses on end-to-end query execution time. We run a semantic filter on Lotus using Llama-3.2-3B on an NVIDIA A16 GPU (16 GB). Each tuple is padded to 750 tokens, consuming approximately 84 MB of KV-cache memory per tuple (112 KB/token × 750 tokens). After model weights and runtime overheads, roughly 6 GB remains for KV cache, enough to hold at most ∼70 tuples simultaneously. With this setup, we run a query consisting of two concatenated filters on the same table, varying the number of tuples in the table. We adopt the approach of Lotus, which executes the first operator on the entire table and fully materializes the intermediate table before executing the second operator. The results are reported in Figure 2. The first operator prefills the KV cache for each input tuple, so its running time scales linearly as the number of tuples increases. When the table has fewer than 70 tuples, the second operator does not need to execute the prefill again because it hits the KV cache, so its running time is minimal. However, if the table is larger than 70 tuples, the LLM serving system starts evicting tuples before the first operator completes, inducing cache misses for the second operator. The second operator now needs to execute

Figure 3: Kalypso architecture. Kalypso sits between the query client and the LLM engine. Solid arrows indicate data flow; dashed arrows indicate scheduling control. prefill on the tuple again and takes the same time as the first one, which results in a spike in end-to-end running time and a drop in throughput. Using an MRU eviction policy instead of the default LRU would improve cache hits only by a constant factor, whose impact in the end-to-end query runtime decreases as the size of the table increases. The challenge of memory-aware pipelining. The experiment above shows that an operator-at-a-time execution strategy cannot achieve prefix reuse under memory pressure. Pipelining operators— scheduling the downstream operator on a tuple promptly after the upstream produces it — can potentially exploit the serving engine’s opportunistic prefix caching, but it needs to strike a balance between multiple objectives. High GPU utilization requires processing many tuples concurrently, which introduces high memory pressure. In this regime, the serving engine must evict cached blocks to admit new requests. Reliable cross-operator reuse therefore requires a memory-aware scheduler, which controls operator launches based on the available memory to consume reusable prefixes before memory pressure evicts them. Admitting too many upstream tasks increases memory pressure and can evict reusable prefixes, while admitting too few upstream tasks can generate too little work for downstream progress. This is the challenging scheduling problem we address in this paper.

3

OVERVIEW OF KALYPSO

We now give an overview of Kalypso, a relational LLM serving system that executes semantic queries and maximizes cross-operator KV-cache reuse. The main components are shown in Figure 3. Kalypso acts as a layer between the query client, which could be a SQPS like Lotus, and an LLM engine, such as vLLM. The query client specifies a query plan consisting of semantic operators. These are implemented by the SQPS as user-defined functions (UDFs) through Kalypso’s API. Operators invoke LLM requests through Kalypso’s Executor, which acts as a wrapper to keep track of request completions and context (see Section 4). Kalypso’s scheduler coordinates pipelined query execution by launching operators, which are organized into pipelined fragments called stages. The scheduler is memory-aware: it uses GPU memory occupancy information from the underlying LLM engine to decide which operators to launch concurrently, control memory pressure, and ensure that cached prefixes are not evicted while

Son et al.

Table 1: Characteristics of common semantic operators and their execution properties. 𝑀 (·, 𝑙) denotes LLM evaluation under natural-language specification 𝑙, and 𝐺 (·, 𝑙) denotes label generation for classification. Operator

Description

Logical Definition

sem_filter(l) sem_map(l) sem_join(l) sem_classify(l) sem_agg(l) sem_topk(l,k)

Select tuples satisfying a language predicate Transform each tuple via a language instruction Join two relations via language predicate Assign category labels to each tuple Aggregate multiple tuples using a language reducer Select top-𝑘 tuples according to language ranking

{𝑡 ∈ 𝑇 | 𝑀 (𝑡, 𝑙 ) = 1} {𝑀 (𝑡, 𝑙 ) | 𝑡 ∈ 𝑇 } { (𝑡𝑖 , 𝑡 𝑗 ) | 𝑀 ( (𝑡𝑖 , 𝑡 𝑗 ), 𝑙 ) = 1} { (𝐺 (𝑡, 𝑙 ) ) | 𝑡 ∈ 𝑇 } 𝑀 ( {𝑡 1 , . . . , 𝑡𝑛 }, 𝑙 ) Top𝑘 (𝑇 , 𝑙 )

Pipelining

Predicate

CP

Y Y Y Y N N

Y N Y N N N

N N Y N N N

they are still being consumed. Kalypso’s scheduler acts as an admission control system for operators, while the actual execution of LLM requests is scheduled on the GPU by the LLM engine (see Section 5). The system includes additional components to manage memory. The memory estimator is used to predict the number of tokens required to run an operator on a tuple. Optionally, this information can be used to pin GPU memory in the LLM engine’s KV cache manager. The deadlock manager ensures progress when pinning introduces deadlocks (see Section 6). This architecture allows Kalypso to execute semantic queries as memory-aware pipelines: the scheduler continuously launches new operators as memory becomes available, supporting pipelining and keeping GPU utilization high throughout query execution while avoiding undesired cache evictions.

A Cartesian Product (CP) operator combines tuples from a left and a right table. The execution of the actual Cartesian product must be performed by calling a Kalypso procedure. This gives the system control over the scheduling of downstream operators, as we will describe. The left-side table must be either a static input table or the output of another operator, since Kalypso supports pipelining on the left side of Cartesian products. The right-side table is another static input table. This allows implementing joins as a CP operator followed by a filter operator.

4

Cascading, vector indexes, and other optimizations. Defining operators as UDFs allows a wide range of efficient operator implementations that are common in SQPSs. For example, filter operators may be implemented as a cascade of a cheaper proxy LLM and a more expensive oracle LLM, which is invoked only if the proxy has low confidence in its decision. Operator UDFs can also use external tools besides LLMs, such as embedding models or vector indexes. The API also supports optimized join implementations that avoid full Cartesian products, which are expensive. CP operators can optionally include a UDF that takes each left-side tuple and returns a smaller subset of right-side tuples to be joined. The UDF can be used, for example, to integrate a vector index as a cheaper proxy implementation of a join, an implementation that we call Indexed Cartesian Product (ICP). Suppose that the tuples in the right-side table of the join are indexed using a vector index or vector database. The UDF can use each left-side tuple as a query to the vector index. Then, the UDF can use the response to select the rightside tuples that should be joined with the left-side tuple. The final Cartesian product between the tuples is executed by Kalypso.

KALYPSO API

The Kalypso API can be used by SQPSs such as Lotus to register their semantic operators and their implementations with Kalypso. Query clients can then submit query plans using these operators to Kalypso, which takes care of their execution. Implementing semantic operators. With Kalypso, SQPSs implement each operator as a User-Defined Function (UDF). The UDF logic is opaque to Kalypso, except that the LLM requests it serves must be invoked through a wrapper. Kalypso requires each operator implementation to declare an execution contract specifying three properties, which are essential for scheduling query execution: (1- Pipelining) can the operator be pipelined or it is blocking? (2- Predicate) can the operator prune its input tuple, interrupting downstream processing for that tuple? (3Cartesian Product) does the operator join tuples from two tables? Table 1 classifies semantic operators introduced in [19] according to Kalypso’s API. A pipelining operator takes one tuple as input and produces at most one tuple as output. For example, semantic filter and map operators are pipelining. Operators that are not pipelining are treated as blocking: Kalypso materializes their entire input table before executing them. Aggregation and top-𝑘 are examples of blocking operators because they combine data from multiple tuples. A predicate operator returns a boolean value indicating whether its output should be forwarded to downstream operators. If the predicate prunes a tuple, the memory caching its prefix can be freed. Operators that are not predicates always forward their output to the dowstream operator. Semantic filter operators are a common example of predicate operators.

Prompt format and prefix sharing. Kalypso enables prefix sharing by scheduling dependent pipelined operators before the relevant cached prefixes are evicted. It is up to the SQPS’s operator implementations to format tuples and, more generally, the prompts to the LLM in a way that maximizes prefix sharing opportunities among pipelined operators, as shown in the example of Figure 1.

Queries. At query execution time, Kalypso receives static left-deep query plans. It schedules the execution of the operators in the plan to maximize GPU utilization, KV-cache hits, and prefix sharing. It then returns the output of the query to the client.

5

SCHEDULING

We now describe how Kalypso schedules query execution and LLM inference calls to achieve pipelining and KV-cache reuse.

Kalypso : Relational LLM Serving Cartesian product: iterate over A' tuples

output stage 4 op6

a1

op1

a2

op1

stage 3 op4 X stage 2 op3

C

scheduler deque & scan table A

stage 1

op2

a'1

task 1.2

X op2

scan table B, concat with a'1

task 1.1

blocking op

op2

a3

op1

op2

scheduler enqueues Queue (a' b ) 1, * , (a'3, b*) deque

task 1.3 B

Cartesian product: iterate over (A', B)' tuples

a'3

op1

scan table C, concat with (a'1,b2)'

task 2.1 a'1,b1

op3

a'1,b2

op3

scheduler Queue enqueues (a'1,b2,c*)

task 2.2

task 4.1

task 3.1 (a'1,b2)',c1

op4

scheduler launches a'1b'2c* on Stage 3

scheduler launches a'1b* on Stage 2

op6

d'1

blocking op

deque

(a'1,b2)'

d1

d1

task 4.j

task 3.k (a'1,b2)',ck

op4

dk

dj

op6

d'j

A Query Plan

Stage 1: Bounded parallelism on multiple A tuples

Stage 2: Bounded parallelism on multiple B tuples

Stage 3: Bounded parallelism on multiple C tuples

Stage 4: new stage on new pipeline

Figure 4: Executing a semantic query plan with pipelining.

5.1

Executing Query Plans

The query plan is processed by the query parser, which groups operators into pipelines (separated by blocking operators) and further into stages within each pipeline (separated by Cartesian products such as joins). Each stage is a sequence of one or more operators that execute sequentially on a tuple—for example, a filter followed by a map. Running a stage on one tuple constitutes a task, the atomic scheduling unit. Consider the left-deep query plan on the left of Figure 4 as a running example. The plan has four stages: the first three constitute one pipeline, the fourth in is a separate pipeline. Tuples flow within tasks and across stages of the same pipeline without materialization: downstream tasks are scheduled to reuse the upstream task’s prefix through the serving engine’s prefix cache. The scheduler runs multiple tasks concurrently—each task executes a stage on one input tuple. In the first stage, the scheduler scans table 𝐴 and launches three tasks. Task 1.1 takes tuple 𝑎 1 and produces 𝑎 1′ (extending the tuple with generated content); task 1.2 filters out 𝑎 2 ; task 1.3 similarly takes 𝑎 3 and produces 𝑎 3′ . When a task completes, its output is either materialized, if the task belongs to the final stage of a pipeline, or pushed into a queue for the next stage’s Cartesian product. The Cartesian product combines output tuples with a right-side table to create dependent tasks. In Figure 4, 𝑎 1′ enters the queue for the second stage; the Cartesian product combines it with tuples from table 𝐵, producing tasks 2.1 and 2.2 as dependent tasks of task 1.1. These dependent tasks are launched by the scheduler. Figure 4 says that the queue contains the outputs of the tasks. The rest of the paper, including Figure 5 and 6 and the scheduling algorithm, say that the queue contains the new tasks.

5.2

Memory-Aware Scheduling

The query execution framework described previously and illustrated in the example of Figure 4 still needs a scheduling algorithm to decide which task should be launched and when. To enable prefix reuse, the scheduler should leverage pipelining, that is, prioritize launching dependent downstream tasks can reuse the KV-cache state of a completed task without recomputation. For example, in Figure 4, after completing task 1.1, the scheduler should prioritize launching its dependent tasks. However, simply prioritizing dependent tasks is not sufficient to achieve high cache hit

rates: ideally, all dependent tasks should be launched before memory pressure evicts the prefix for 𝑎 1′ . If the scheduler launches too many concurrent tasks, it could create memory pressure that could lead to the eviction of the prefix for 𝑎 1′ before the dependent tasks execute. Therefore, besides doing basic pipelining, the scheduler also needs to control the launching of tasks, and their associated memory pressure, in order to control the timing of cache evictions. Kalypso’s scheduler times the launching of tasks based on memory availability, so that cached prefixes that are still needed by dependent tasks don’t need to be evicted. It controls memory availability by keeping track of the size of the cached prefixes that are still needed. It also bounds the amount of memory each task is allowed to use, using a memory estimator, and optionally offers support for memory pinning, as we discuss in Section 6.

5.3

The Kalypso Scheduling Algorithm

Pipelined execution creates a unique online scheduling problem because KV-cache reuse couples operator dependencies with GPU memory pressure. This makes it challenging to achieve high parallelism. When a tuple crosses an operator boundary, Kalypso must reserve memory and admit downstream operators while avoiding that memory pressure evicts the reusable prefix. Admitting too many early-stage tasks can exhaust memory and limit parallelism for downstream stages, while admitting too few can leave downstream stages without enough input to keep the GPU busy. We now illustrate this problem and introduce the insights that motivate the Kalypso scheduling algorithm by first discussing three baseline algorithms: a simple sequential algorithm, which creates minimal memory pressure but underutilizes the GPU, a parallel depth-first algorithm, which can starve upstream operators and reduce pipeline throughput, and a parallel breadth-first algorithm, which can saturate KV-cache capacity by admitting too much upstream work. Each algorithm addresses some aspects of the scheduling problem but also reveals some of its challenges. We then combine these insights and ideas in the Kalypso scheduling algorithm. Sequential depth-first execution. The simplest way to execute queries would be for the scheduler to launch tasks sequentially in a nested loop, completing each task and its dependents before moving on to maximize prefix reuse. This, however, would run at most one LLM request at any point in time, which is not sufficient to fully utilize GPU resources. In Figure 4, this policy runs task 1.1, then tasks 2.1 and 2.2, and then all task 3.x instances dependent on

Son et al. Cartesian product: iterate over A' tuples task 2.1

scheduler

task 2.2 scheduler scan table A

task 1.1

No pending tasks

Stage 1

Queue

task 2.m

Stage 2: Starving, Previous stage does not spawn enough dependent tasks

Figure 5: A parallel depth-first policy can starve downstream stages. task 2.2, one for each tuple in table 𝐶. When the next operator is blocking, such as SemTopK or SemAgg, the pipeline stalls until that operator has consumed its dependent inputs and produced output. After this barrier, task 4.x starts a new single-stage pipeline using the available memory capacity. Although simple, this policy keeps at most one task active and underutilizes the GPU. Therefore, the Kalypso scheduler launches multiple tasks in parallel, but keeping high GPU utilization has some challenges, as we now discuss. Parallel depth-first execution and starvation. A natural extension of the sequential depth-first policy is to parallelize the last stage of a pipeline by assigning it a large static memory budget and launching as many tasks as possible within that budget. This strategy tries to finish dependent tasks as soon as possible: once an upstream task has produced downstream tasks, it launches many parallel last stage tasks so that the upstream tuple’s reusable prefix can be consumed quickly and then evicted. The limitation of this policy is that it can starve the later stages. Figure 5 illustrates this effect in a two-stage pipeline. In the figure, task 1.1 has just completed and all dependent tasks of tasks 1.1 are immediately launched in parallel, leaving the queue empty. When these tasks complete, the earlier stage runs task 1.2 in isolation, since only the last stage is parallelized, which underutilizes GPU resources. Meanwhile, the last stage is starving because it has no work to do. This policy minimizes the amount of memory dedicated to caching prefixes, freeing up the rest of the memory for running a large number of last-stage tasks. However, it can underfeed the pipeline since upstream stages are not given enough memory budget run tasks in parallel and produce downstream work. Parallel breadth-first execution and saturation. A solution to the problem of starvation is to statically allocate more memory to the first stage so that it can run multiple parallel tasks. This breadth-first strategy admits more upstream tasks concurrently, exposing parallelism and creating a larger pool of dependent downstream work and avoiding starvation. However, if these static memory budgets are not tuned carefully, this policy can saturate the KV-cache budget with admitted upstream work. Figure 6 illustrates this effect: many early-stage tasks are admitted because the stage has a large budget. When they complete, the queue fills up and the reusable prefixes stay cached until all their dependent tasks are completed. This constraints the amount of memory available

for launching later-stage tasks. Thus, breadth-first parallelism increases the supply of work, but it can overcommit memory to early stages and block progress at later stages. The need for adaptive scheduling. The starvation and saturation examples show that no fixed allocation of stage memory budgets is robust across semantic query workloads. The right budget split depends on properties such as operator selectivity and join fanout, i.e., how many right-side tuples join with each left-side tuple. With high selectivity, few tuples survive, or with low fanout, each tuple creates little downstream work, so the later stages starve for ready tasks; with low selectivity and high fanout, many tuples survive and create large amounts of downstream work, so admitted upstream work can saturate the KV-cache budget. Kalypso therefore adapts stage budgets online, shifting budget toward earlier stages when the pipeline is starved for new downstream work and toward later stages when admitted upstream work is saturating the KV-cache budget. We now detail how Kalypso detects these conditions and reassigns budget across stages during execution. The Kalypso scheduling algorithm. The previous algorithms show why the scheduling algorithm of Kalypso has three goals: (1) avoid starvation, where later stages run out of ready dependent tasks because upstream stages do not receive enough budget, (2) avoid saturation, where upstream stages fill up the KV-cache and leave too little budget for downstream tasks to make progress, and (3) adapting online to the characteristics of different queries and datasets. To achieve these goals, the scheduler assigns a dynamic memory budget to each stage, tracking per-stage queue pressure to determine when new tasks can be launched, and adapts these budgets online by rebalancing across operators. Algorithm 1 illustrates the scheduling algorithm for a single pipeline. Each stage maintains a waiting task queue per-stage (tasks awaiting to be launched) and a running task set (tasks with reserved budget currently executing). The algorithm iterates until the query is completed, so there are no more waiting or running tasks. In each iteration, the scheduler (1) admits waiting tasks whose stage has available memory given its budget, (2) processes any completed task, and (3) rebalances stage budgets. The Launch procedure checks each stage’s waiting queue and launches tasks only when the stage has enough remaining budget. The check is done by the memory manager, which keeps track of how much memory has been allocated to each task in each stage. The Complete procedure deals with completed tasks. First, as discussed in Section 5.2, each task is run with a maximum amount of tokens it can generate (details in Section 6). If the task generates more tokens, it is interrupted by the LLM serving engine. In this case, the scheduler reruns the task with an increases token amount (lines 24-27). If the task completed successfully and it did not include a predicate operator that filtered its input, the scheduler continues query execution. If the stage is not the last stage in the pipeline and ends with a Cartesian product, the scheduler executes the Cartesian product to create dependent children tasks, taking the right-side table tuples as input, and enqueues them for the next stage (lines 29-33). The Cartesian product can optionally execute a UDF to select a subset of tuples from the right-side table to join. The memory manager keeps track of the dependencies between tasks and uses this information to release the memory for

Kalypso : Relational LLM Serving Cartesian product: iterate over A' tuples

Algorithm 1 Kalypso’s Scheduling Algorithm (Single Pipeline). 1 procedure Schedule (stages) 2 running ← ∅ , out ← [ ] 3 firstStage ← stages[0] 4 tasks ← firstStage.inputTable ( ) 5 firstStage.waiting.enqueue (tasks) 6 while stages.hasWaitingTasks ( ) or running ≠ ∅ do 7 Launch (stages, running) 8 for each (stage, task, result ) ∈ running.completedTasks ( ) do 9 running.delete (task) 10 Complete (stage, task, result ) 11 Rebalance (stages) 12 return out 13 procedure Launch (stages, running) 14 for each stage ∈ stages do 15 while stage.waiting ≠ ∅ do 16 task ← stage.waiting.peek ( ) 17 if memoryManager.admit (stage, task) then 18 task ← stage.waiting.dequeue ( ) 19 memoryManager.allocateMemory (stage, task) 20 running.add (task) 21 launchWorker (task) 22 else break 23 procedure Complete (stage, task, result ) 24 if result.retry ( ) then 25 task.updateBudget (result ) 26 stage.waiting.enqueue (task) 27 return 28 if result.filtered ( ) = false then 29 if stage ≠ stages.lastStage ( ) then 30 nextStage ← stages[stage.id + 1] 31 childrenTasks ← ExecuteCP (result, nextStage.inputTable () ) 32 nextStage.waiting.enqueue (childrenTasks) 33 memoryManager.trackDependency (task, children) 34 else 35 out.append (result ) 36 if result.filtered ( ) = true or stage = stages.lastStage ( ) then 37 memoryManager.releaseMemory (task) 38 procedure Rebalance (stages) 39 for each stage ∈ stages do 40 if memoryManager.isSaturated (stage) and stage ≠ stages[0] then 41 memoryManager.transferMem(from=stage, to=stages.lastStage () ) 42 for 𝑖 ∈ [stages.lastStage ( ).id, 1] do 43 stage = stages[𝑖 ] 44 prevStage = stages[𝑖 − 1] 45 if memoryManager.isStarving (stage) 46 and not memoryManager.isStarving (prevStage) then 47 memoryManager.transferMem(from=stage, to=prevStage)

the parent task only when all the children tasks have completed. If the stage is the last stage in the pipeline, the result is appended to the materialized output (lines 34-35). Finally, if a task has been filtered or it belongs to the last stage, the memory of the task is released, possibly together with the budget of the parent tasks if all the other sibling tasks have completed too (lines 36-37). The Rebalance procedure adaptively rebalances memory budgets among stages. The budget for each stage is always larger than minBudget𝑠 , which is the amount of memory required to execute one task and keep its prefix cached. This ensures that the query can make progress at each stage without requiring evictions. Initially, all stages except the last are assigned a budget equal to minBudget𝑠 , while the last stage is assigned all the remaining memory. Rebalancing is triggered whenever a stage is detected to be starving or saturated based on the size of its waiting queue.

scheduler task 1.2 task 2.3 (A'1 x B3) task 2.4 (A'1 x B4)

scheduler scan table A

task 2.5 (A'1 x B5)

task 1.(n-1)

task 2.1 task 2.2 Stage 2: Saturated, Stage budget is not enough to consume pending tasks

task 2.n'(A'1 x Bm)

task 1.n

pending tasks

Stage 1: Bounded parallelism on multiple A tuples

Queue

Figure 6: A parallel breadth-first policy can saturate the KVcache budget. The memory manager keeps a low and high queue threshold for each stage 𝑠, initialized as: budget𝑠 budget𝑠 high𝑠 = 𝛼 · , low𝑠 = 𝛽 · , minBudget𝑠 minBudget𝑠 where budget𝑠 is the current memory budget assigned to 𝑠 and 𝛼, 𝛽 ∈ (0, 1) are configurable static parameters with 𝛼 > 𝛽. The memory manager then classifies the stage 𝑠 as starving if the size of its waiting queue is smaller than low𝑠 or saturated if it is larger than high𝑠 . Rebalance uses these states to transfer budget between stages. If a stage is saturated (lines 40-41), this is an indication that its downstream stages cannot consume tuples at a sufficient rate, making tasks queue up. Like in the example of Figure 6, the solution is to transfer memory from the saturated stage to the last stage. This helps complete dependent tasks faster, evict cached prefixes, and use the budget that is now available to launch more waiting tasks. The first stage is always saturated by design, so the algorithm does not apply this rule to it. The memory manager transfers memory that has been just freed up by completed tasks. If a stage is starving (lines 42-47), this means that the upstream tasks cannot produce enough tasks so they need a larger budget. Therefore, the stage transfer its budget to the upstream task, similar to the situation depicted in Figure 5. It could happen that the upstream stage is also starving, in which case the algorithm recursively transfers memory from downstream stages to upstream ones until it finds a non-starving stage.

6

MEMORY MANAGEMENT

In Kalypso, each task is assigned a maximum amount of tokens it can use, which is used to determine when it can be launched. The previous discussion assumed, for simplicity, that memory estimation was perfect. We now describe how the memory estimator component of Kalypso predicts the expected memory usage of a task and how Kalypso deals with incorrect estimates. We also discuss dealing with deadlocks that can arise with explicit pinning. Token bound estimation. Compared to traditional LLM serving workloads, relational workloads make it easier to predict the number of tokens generated by each LLM request, for multiple reasons. Semantic operators often issue prefill-heavy requests, which

Son et al.

generate few tokens or no tokens at all. This is for example the case with filter operators, which have to output a binary value, and classifiers, which are used for aggregations and group-by operators. More in general, semantic operators repeatedly execute the same instruction on many input tuples. The number of generated tuples per requests depends on the instruction and can be predicted through online monitoring, which is the approach used by Kalypso. We base our memory estimator on these insights. For each stage, Kalypso keeps a peak token usage bound for an entire task execution. The user can decide whether to specify a static token bound for an operator, as is common for filter operators, or delegate the estimation of the bound to Kalypso, which is useful for map-like operators that generate variable-length output. For the latter case, Kalypso monitors completed requests and records the ratio of generated output tokens to input (prompt) tokens. The scheduler uses the calibrated 99th percentile of this outputto-input token ratio as the token bound for future invocations of the same operator. This estimate keeps the bound conservative enough to cover most requests while avoiding the loss of parallelism caused by reserving memory for the worst case. If an LLM request terminates because it reaches its bound, Kalypso interrupts the task, increases the bound for the task, and re-enqueues it. Explicit and virtual pinning. A core principle of Kalypso is to manage memory and schedule task launches to avoid evicting prefixes that are still needed. Kalypso offers two mechanisms to control evictions. The first is explicit pinning to prevent eviction of cached prefixes that will be reused by dependent tasks. This requires pinning support by the underlying LLM serving system. The second is virtual pinning, which is a best-effort alternative: the scheduler implicitly controls evictions by controlling which operators are launched and how much memory they use, assuming that the KV cache system uses an LRU eviction policy, and without explicit pinning. The Kalypso scheduling algorithm works with both variants. Kalypso offer both options because virtual pinning has some advantages over explicit pinning: it does not require operators to implement a pinning logic or LLM serving systems to support pinning, and avoids memory deadlocks, a problem we now discuss. In our evaluation, we found that virtual pinning achieves only slightly lower performance than explicit pinning. Deadlock detection, avoidance, and recovery. Explicit pinning can induce deadlocks when upstream tasks retain memory needed by downstream tasks, but that pinned memory cannot be released until the downstream tasks complete. In this setting, progress at one stage can depend on memory held by another stage, creating a circular wait across the pipeline. A similar situation can arise when the system retries interrupted tasks that exceeded their token bound. These tasks can further reduce the memory available to admit downstream work and can lead to deadlock. The Kalypso scheduling algorithm mitigates the risk of deadlocks by limiting how many concurrent tasks are launched. Deadlocks, however, can still occur, so the system detects them by periodically querying the internal scheduler of the LLM serving engine and checking if there are waiting LLM requests but no running requests. Upon detection, Kalypso unpins all memory and temporarily switches to virtual pinning, making it possible for the LLM engine to evict KV cache entries as needed. In our experiments, we only observed deadlocks during stress-tests.

7

EVALUATION

We evaluate Kalypso from two complementary perspectives. First, we compare against existing semantic-operator systems [14, 19] to measure end-to-end latency and LLM invocation cost under comparable semantic tasks. Second, we study Kalypso’s internal execution knobs, including pipelined versus blocking execution, adaptive memory budgeting, virtual versus explicit pinning, and outputtoken budget estimation, to understand which system mechanisms drive the observed performance differences.

7.1

Experimental Setup

Baseline systems. We compare our Kalypso system with two baseline SQPSs that use request-centric LLM serving with operatorat-a-time execution. We configure all systems to use vLLM as the underlying LLM engine. • Lotus (v1.1.4) [19] proposes efficient implementations of those operators based on cascading: it first runs a cheap proxy implementation, which could use embedding similarity or a cheaper LLM model, and falls back to a more expensive reference LLM-based implementation if the proxy has low confidence. Lotus runs user-defined query plans. • Palimpzest (v1.5.3) [14], unlike Lotus, lets users specify a plan and then uses a query optimizer to improve it by reordering operators and selecting efficient implementations. These systems focus on operator implementations and query optimization, which are complementary to Kalypso’s serving-layer optimizations. System configuration. All systems use the same operator implementations and manually-optimized query plan and oracle model (Llama-3.3-70B-Instruct) for each workload, isolating the effect of the serving layer. We detail the workload implementations in Section 7.2. For Lotus and Palimpzest, we use the default maximum batch size of 64. For all systems, we set a static maximum token bound of 8 for predicate LLM calls, such as filter and join operators. This avoids cases where an LLM non-deterministically produces many extra tokens for an otherwise short operator output. For Palimpzest, we disable reasoning_effort to remove few-shot reasoning prompts that would otherwise make Palimpzest prompts longer, ensuring a fair comparison of serving performance. For Lotus and Kalypso, we evaluate also proxy operator implementations that use a smaller LLM than the default LLM. We configure them to use a separate vLLM instance running the Llama-3.1-8B model, which is small enough to fit in one GPU. We do not use Kalypso to optimize LLM serving for the small model. We set the 𝛼 and 𝛽 parameters used by Kalypso for rebalancing (see Section 5.3) to 1 and 0.5 respectively. We use virtual pinning by default. Hardware and software configuration. We run all experiments on a server with 4× NVIDIA RTX Pro 6000 GPUs (96 GB of HBM), and AMD EPYC 9575F Processor CPU with 8 cores and 300GB of RAM. All systems we evaluate run on top of vLLM v0.13.0rc4, with Automatic Prefix Caching (APC) enabled and the Llama-3.370B-Instruct model distributed across all GPUs using tensor parallelism and the Triton attention backend. By default, we assign 90% of the total GPU memory to vLLM. We configure vLLM to

Kalypso : Relational LLM Serving

Table 2: Summary of Workloads.

the retrieved evidence with the claim. The final sem_filter operator verifies the claim based on the evidence. It uses a small LLM as a proxy model, falling back to the oracle model if the proxy is not confident. For Lotus, this implementation yields 183.3 oracle fallbacks over 1,000 claims. The Kalypso implementation has 243.6 oracle fallbacks. Palimpzest does not support merging the results of an index search into a single tuple so we don’t include it in the evaluation of this workload. Overall, this plan consists of a singlestage pipeline with three operators.

# LLM calls Workload

Data

Avg. tok. Lotus Palimp

Kalypso

FEVER

Claims 1,000 Wikipedia 5,416,568

# Tuples

11.8 126.0

1,183

-

1,243 (0)

MEDEC

Patients

1,000

397.1

2,098

2,338

2,143 (21)

BioDEX

Articles Reactions

500 11,271

2,680.1 6.3

6,881

-

7,016 (0)

Contract NLI

Contracts Hypotheses

607 17

2,145.3 36.8

17,445 16,370 17,342 (167)

make query execution as deterministic as possible across multiple runs, following vLLM’s reproducibility guidance [28]. We set VLLM_ENABLE_V1_MULTIPROCESSING=0, which makes offline scheduling deterministic. We use greedy decoding with temperature 0, top-𝑝 1.0, frequency penalty 0.5, and repetition penalty 1.3 to disable sampling and reduce repetitive generations. This does not completely eliminate non-determinism [3, 30], so we also run each experiment three times and report average measurements.

7.2

MEDEC medical error detection and correction. 1 2 3 4 5 6 7 8

The MEDEC workload [4] captures medical error detection and correction on clinical notes through three subtasks: predicting whether the note contains a medical error, identifying the sentence that contains the error when one is present, and generating a corrected version of that sentence. We use a 1,000-patient sample from the MEDEC dataset. We implement the query plan described in [4]: a sem_filter operator performs error detection, the first sem_map operator identifies the erroneous sentence ID, and the second one generates the corrected sentence. The Lotus implementation uses a cascading implementation with a smaller proxy LLM for the first filter. We found that the behavior of the small LLM is highly nondeterministic for this workload, resulting in a high variance of oracle LLM calls across different runs. Therefore, to ensure fairness, we use cascading only for Lotus and disable it for Kalypso. Although Palimpzest discusses cascades as a possible optimization, it does not yet implement the threshold-based fallback logic needed for these cascades, so we use an oracle-only implementation for Palimpzest too. This plan has three operators and a single stage.

Workloads and Implementations

We consider four workloads that exercise different operator combinations, including both multi-operator multi-stage pipelines and single-stage pipelines. We reimplement the same operator semantics on top of Kalypso’s API, including Lotus’ proxies where applicable. Our goal is to stress-test the performance of LLM serving and to show that it is possible to implement diverse operators and queries on top of Kalypso’s API. A summary of the workloads and their datasets is shown in Table 2. We also report the average number of tokens per tuple and the average number of oracle LLM requests generated by the implementations in different systems, without considering proxy LLM calls for cascading implementations. The numbers are slightly different across systems due to the inherent non-determinism of AI-based query execution. The number in brackets for Kalypso are the number of retried LLM requests due to incorrect memory estimations. For the two workloads taken from the Lotus paper, FEVER and BioDEX, we follow the implementations described in [19]. FEVER fact verification. 1 2 3 4 5 6 7 8

claims.sem_map( "Generate two concise Wikipedia search queries." ).index_search( index_table=wikipedia_collection, top_k=5 ).sem_filter( "Based on retrieved Wikipedia content, is the claim supported?", cascade=True )

FEVER is a fact verification workload, where each claim is checked against evidence taken from Wikipedia [25]. We sample 1,000 FEVER claims, as done in the Lotus paper [19], and use that same query plan for all systems. For each claim, the sem_map operator generates two concise search queries, which are issued to a ColBERT index search built over a 5M-document Wikipedia corpus to retrieve candidate evidence passages. This retrieval step is implemented as a tuple-independent index_search operator, which concatenates

notes_df.sem_filter( "Answer true if any numbered sentence in the patient note " "is medically inconsistent." ).sem_map( "Identify the numbered sentence that contains the medical error." ).sem_map( "Generate the corrected version of the erroneous sentence." )

BioDEX biomedical reaction matching. 1 2 3 4 5 6 7 8

articles.sem_map( "Extract adverse drug reaction labels described for the patient." ).sem_join( right_table=reactions, icp=True ).sem_filter( icp_predicate="Does the article describe this adverse drug reaction?", cascade_low_threshold=low, cascade_high_threshold=high )

The BioDEX workload matches each biomedical article with the adverse drug reactions it describes [7]. The set of reactions is taken from a large database. For all systems, we use the query plan and the operator implementations described in [19]. Given a biomedical article, the sem_map operator extracts adverse drug reaction labels described in the article. The sem_join is implemented as an Index Cartesian Product (ICP) operator that retrieves matching candidate reactions from the reaction table using a vector index lookup with the intfloat/e5-base-v2 embedding model. The join then outputs all pairs of articles and retrieved candidate reactions, together with the vector distance between the two. The following sem_filter operator uses a proxy implementation that

Son et al.

Latency (s)

300 200

1000

1.00x

1.49x

0

1.00x

1.54x

500

100

0

FEVER

1000

0.88x

Lotus

Kalypso

1.29x

6000 1.00x 3000

500 0

MEDEC

1.00x

2.05x

4.57x

BioDEX

0

ContractNLI

Palimpzest

Figure 7: End-to-end latency and speedup across workloads. checks the vector distance of each pair. Pairs with distances above a high threshold are rejected, those below a low threshold are accepted, and uncertain candidates between the two thresholds fall back to the oracle model. We follow this implementation for both Lotus and Kalypso. Palimpzest does not support distance-based index search so we don’t include it in the evaluation. This plan consists of three operators and two stages, divided by the ICP operator. ContractNLI contract entailment. 1 2 3 4 5 6 7 8 9 10

contracts.sem_filter( "Is this document a valid contract or agreement text " "with enough clauses to evaluate confidentiality obligations?" ).sem_join( right_table=hypotheses, "Given the contract and hypothesis, " "does the contract entail the hypothesis?" ).sem_map( "Explain briefly why the contract entails the hypothesis, " "citing the relevant obligation or clause." )

ContractNLI [12] is a document-level contract entailment workload: given a contract and a proposed legal statement (hypothesis), decide whether the contract supports (entails) that statement. The sem_filter operator removes documents that are not valid contracts or do not contain enough substantive content to evaluate confidentiality obligations. The sem_join operator is a full Cartesian Product (CP) that pairs each remaining contract with each hypothesis, followed by a semantic filter that checks whether the contract entails that statement using an LLM. The final sem_map operator generates a concise explanation citing the relevant clause or obligation. For Lotus, we consider a cascading implementation with a smaller proxy LLM implementations for the first filter operators. Like for MEDEC, we the small LLM shows a highly nondeterministic behavior that is hard to consistently reproduce, so we use an oracle-only implementation for Kalypso. We do the same for Palimpzest because it does not support cascading. This plan has three operators and two stages, separated by the CP operator.

7.3

End-to-End Query Completion Time

Figure 7 summarizes the end-to-end query latency of Kalypso and the baseline semantic-query systems across the four workloads. Kalypso reduces latency for all workloads by executing semantic operators as a pipeline and by reusing KV-cache state across dependent operator calls, while the baselines execute operators one at a time and materialize intermediate results between operators. LLM-call counts are similar across systems, as shown in Table 2,

so the speedup comes primarily from execution efficiency and depends on workload structure. Overall, the benefit depends on how much dependent LLM work can be pipelined and how often downstream operators reuse the same tuple prefix. For FEVER, Kalypso reduces latency from 258.1s for Lotus to 172.6s, a 1.49× speedup. Palimpzest does not support this workload, as we described previously. The workload has no Cartesian product, so the entire memory budget is allocated to one stage. Kalypso improves latency by pipelining the map, retrieval, and filter operators and by preserving reusable KV-cache state across the dependent LLM operators. It controls concurrent task launches to ensure that each task can complete without having its KV cache state evicted. MEDEC also has no Cartesian product and, compared to Fever, it has more downstream operators that can reuse the prefix computed by the first operator. The speedups of pipelining grow accordingly, reducing latency from 714.6s for Lotus and 808.2s for Palimpzest to 464.3s, corresponding to 1.54× and 1.74× speedups. It is worth noting that Kalypso only uses an oracle LLM, unlike Lotus which uses a cheaper but potentially unreliable proxy model for the filter. BioDEX is a two-stage workload. We cannot run Palimpzest on this workload, as described previously. Kalypso reduces latency from 910.3s to 703.4s (1.29×) by pipelining and reusing the prefixes for the articles across the ICP join and the final filter. Articles are long, averaging 2,680 tokens, which boosts speedups by increasing the benefit of prefix caching and reuse. Gains are bounded by the use of a proxy implementation for the final filter operator, which skips LLM invocations in some cases based on the vector distances. Although the ICP join can create many second-stage tasks, the size of the right-hand reaction tuples averages only 6.3 tokens. Extra memory in this stage is therefore less effective. ContractNLI is a two-stage workload combining long contract inputs, averaging 2,145 tokens, with 17 hypotheses per contract. The long contract prefix can be reused by the join predicate and the final sem_map. Kalypso preserves this large reusable state across stage boundaries, avoiding repeated prefill work. Against the lowerlatency Palimpzest baseline, Kalypso reduces latency from 2,373.4 to 1,062.4, a 2.23× speedup. Compared with Lotus, the speedup is 4.57×. This is despite the fact that Kalypso only uses an oracle LLM, whereas Lotus uses a proxy LLM for the filter operator.

Kalypso : Relational LLM Serving

FEVER Fact Verification 260

Runtime (s)

MEDEC

BioDEX Classification

1000

240 220 200

1000

800

900

600

800

180

0.9 0.8 0.7 0.6 0.5

0.9 0.8 0.7 0.6 0.5 Lotus

Kalypso

700

ContractNLI

6000 4500 3000 1500

0.9 0.8 0.7 0.6 0.5 Palimpzest

0

0.9 0.8 0.7 0.6 0.5

Execution Policy Ablations Runtime (s)

2000

Blocking

Pipelined

1500 1000 500

1940

1.83x 506 1.20x 421

602 1.30x 464

946 1.34x 703

1062

0

FEVER MEDEC BioDEX ContractNLI Figure 9: Latency for Kalypso in blocking mode (operatorat-a-time, no cross-operator KV-cache reuse or pinning) vs. pipelined mode (default). Blocking vs. pipelined execution. To isolate the benefit of pipelined query execution over blocking, we modify Kalypso to execute operators in a blocking, operator-at-a-time manner. In this variant, each operator runs over the full input before the next operator begins. As a result, downstream operators can no longer inherit pinned KV-cache state from upstream execution and may need to recompute the same tuple prefix instead of reusing it. Figure 9 shows that pipelined execution is faster on all four workloads, improving latency by 1.20–1.83× over blocking execution. Across workloads, the gains reflect both pipeline overlap and cross-operator prefix reuse. The speedup trends are consistent with the results shown previously. These results therefore capture both sources of improvement in Kalypso’s execution policy: pipelining increases overlap across operators, and memory-aware scheduling preserves reusable KV-cache state long enough for downstream operators to benefit from it. Speeups are larger for workloads where pipelined tuples are larger and pipelines consist of more operators. Impact of scheduling algorithms. Kalypso uses an adaptive algorithm to allocate memory budgets across stages. We now show that a simpler static per-stage budget cannot consistently achieve similar performance across multiple workloads, as motivated in Section 5.3. We use BioDEX and ContractNLI because they are multi-stage workloads and compare adaptive budgeting against static two-stage memory-allocation ratios. In each static-ratio baseline, the scheduler assigns a constant fraction of the available KVcache budget to the first stage and the remainder to the second stage throughout the query. We sweep the fixed split across the ratios shown in Figure 10. All these baselines still rely on the same

0.6 vLLM memory Runtime (s)

7.4

0.9 vLLM memory Runtime (s)

Figure 8: Effect of GPU memory utilization on end-to-end latency across workloads.

BioDEX

1500 1000

723

705

500 0

1:9

3:7

Stage budget ratio

BioDEX

1500 1000

785

724

500 0

ContractNLI 2400 2068 1800 1555 1654 1017 1116 898 1200 1163 1176 Adaptive 1062 Adaptive 703 600 0 5:5 7:3 9:1 1:9 3:7 5:5 7:3 9:1

1:9

3:7

Stage budget ratio

ContractNLI 2827 3200 2400 900 1004 1761 1600 1165 1190 1593 Adaptive 704 Adaptive 1185 800 0 5:5 7:3 9:1 1:9 3:7 5:5 7:3 9:1

Stage budget ratio

1362

Stage budget ratio

Figure 10: End-to-end latency under fixed two-stage memory-allocation ratios and adaptive budgeting at 0.9 and 0.6 vLLM memory utilization. memory-aware scheduling approach introduced by Kalypso: they organize operators in tasks and launch them only when memory is available, based on their estimated token bound. Figure 10 shows that no single static ratio is best across workloads. The results also confirm that both starvation and saturation can impact system performance negatively. ContractNLI performs best with a 10%–90% allocation across the first and second stage, while BioDEX performs best with a 30%–70% allocation. The best split therefore depends on workload-specific properties such as tuple size, selectivity, join fanout, and the amount of downstream work created by each stage. The impact of these factors is difficult to know before execution and can change as the query progresses. Adaptive budgeting avoids choosing this ratio ahead of time: it remains better than the best static allocation on both workloads by shifting memory toward the stage that is currently limiting pipeline progress. We repeated the experiment after reducing the memory available to vLLM to 60% and found similar results. The best runtime across static allocation ratios varies, and the adaptive strategy remains the best. Virtual vs. explicit pinning. The default for this paper’s evaluation is to use virtual pinning, which preserves reusable prefixes

Son et al.

Virtual

Explicit

800 400

703 685 421 401

1100

1062 1054

464 516

Latency (s)

Latency (s)

1200

900 700 639 500

0

FEVER

MEDEC

BioDEX ContractNLI

Figure 11: Latency with virtual pinning and explicit pinning. through scheduling and admission control, rather than explicit pinning, which requires KV-cache pinning support from the LLM serving engine. We now compare the two variants. Implementing explicit pinning required only modest changes to vLLM, totaling around 200 LoC across core vLLM components responsible for KV-cache management, block allocation, and request state. These changes prevent pinned KV-cache blocks from being evicted until they are explicitly unpinned by Kalypso’s scheduler. Figure 11 compares explicit pinning against virtual pinning. The two modes have similar performance across workloads: explicit pinning is slightly faster on FEVER, BioDEX, and ContractNLI, while virtual pinning is faster on MEDEC. This result suggests that virtual pinning is sufficient to capture the main scheduling benefit without requiring explicit KV-cache pinning support from the serving engine. Explicit pinning can still be used as an optional backend feature when the serving engine provides it. Token bound sensitivity. Kalypso assigns a token bound to all LLM requests, which is the basis of memory-aware scheduling. Its memory estimator avoids both overly conservative and overly optimistic bounds. A worst-case budget reduces concurrency, while a very small budget can create retry overheads. We evaluate output-token budget sensitivity on MEDEC by setting the GPU memory utilization limit to 0.9, which is the default, and 0.6, which induces additional memory pressure. As described in Section 6, the scheduler must reserve KV-cache memory before knowing how many tokens a generative operator will actually produce. Figure 12 shows that conservative and overly large fixed budgets substantially increase latency because the scheduler admits fewer concurrent requests. At the other extreme, with a one-token generation budget, the scheduler allocates memory for each request’s prefix, which includes data and instructions, and only one extra token. The scheduler admits more concurrent requests, speeding up prefills, but it also needs to retry most requests. The first execution of a request is fast, since it generates only one token. For most requests, the subsequent retry execution finds the prefix still in the cache. However, since re-executions use larger budgets, some prefixes might have been evicted. Kalypso’s token budgeting achieves the best latency in the sweep without requiring the user to know the workload’s output-token distribution in advance.

1051

0.6 vLLM memory 0.9 vLLM memory 698

508

565 495

598 500

540

1

500

1k

2k

746

799

606 0.6 Kalypso 507s 0.9 Kalypso 495s

4k

Fixed output-token budget

8k

Figure 12: Latency under fixed output-token budgets. The dashed line shows Kalypso’s default token budgeting. Resource sensitivity. We now stress the memory-management component of Kalypso: as less KV-cache memory is available, cached prefixes are more likely to be evicted unless the scheduler preserves them for downstream operators. We vary the GPU memory budget available to vLLM across five settings: 0.9, 0.8, 0.7, 0.6, and 0.5, corresponding to approximately 190.6, 152.6, 114.6, 76.6, and 38.6 GB of KV-cache capacity. Figure 7 summarizes the highmemory setting, while Figure 8 shows that Kalypso remains fast and robust as the KV-cache budget shrinks. Across all five memory settings, Kalypso is faster than the baselines on every workload. The advantage is stable on FEVER and BioDEX, where reducing the budget does not substantially change the relative ordering. Under stronger memory pressure, Kalypso also avoids the large slowdowns seen in the baselines: on MEDEC, reducing the budget from 190.6 GB to 38.6 GB increases Kalypso’s latency by only 9% (464.3s to 507.3s), compared with 44% for Lotus and 29% for Palimpzest. ContractNLI shows the same robustness at larger scale: Kalypso stays below 1348.3s across the sweep, while Palimpzest remains above 2296.5s and Lotus remains above 4854.0s.

8

RELATED WORK

LLM Serving Systems. Modern LLM serving systems optimize the execution of independent inference requests. Orca introduces iteration-level scheduling and selective batching [29]; vLLM improves KV-cache memory efficiency through PagedAttention [13]; and Sarathi reduces prefill–decode interference through chunked prefills [1]. DistServe disaggregates prefill and decode across separately provisioned GPUs [34], while Llumnix dynamically migrates requests among model instances to improve load balance and isolation [24]. These systems schedule requests without visibility into the semantic query plan. Kalypso leverages these optimizations by runing on top LLM serving systems. It uses operator dependencies to pipeline execution and coordinate KV-cache retention across related requests. Prefix-Aware LLM Serving. Several LLM serving systems exploit repeated prompt prefixes to avoid recomputing KV-cache state. SGLang uses RadixAttention to organize cached prefixes in a radix tree for structured and multi-turn language-model programs [33], while vLLM supports automatic prefix caching for requests with

Kalypso : Relational LLM Serving

shared prompt prefixes [13]. Prompt-caching mechanisms similarly reuse attention state for stable prompt components such as system messages, templates, and long context documents [8]. These system support prefix reuse opportunistically among requests visible to them, as long as the relevant prefixes remain in they KVcache. However, they do not control the higher-level workload that generates these requests, and therefore cannot actively restructure query execution to maximize cross-operator prefix reuse. Kalypso relies on these systems’ prefix reuse capabilities to optimize pipelining.

[5]

[6]

[7]

Optimizing Semantic Operator Implementations. Prior work reduces expensive LLM calls using model cascades and proxy models [6, 19, 23, 31]. For semantic joins, feature decomposition extracts relevant fields once per record and rewrites the join condition as a logical expression over inexpensive feature comparisons, replacing quadratic pairwise LLM evaluation while providing statistical precision and recall guarantees [32]. Block-based joins instead place batches from both inputs in each prompt, reducing the quadratic number of pairwise LLM invocations, although batching can degrade output accuracy [26]. Other systems organize document chunks for prompt-cache discounts [23] or fuse semantic operators in streaming query plans [5], but they do not account for the serving engine memory pressure, parallelism, and scheduling. Kalypso complements them by optimizing the LLM serving layer.

9

CONCLUSION

We presented Kalypso, a query-aware execution system for semantic queries that bridges semantic query processing and LLM serving. Existing semantic query systems execute operator invocations in a query-agnostic manner, missing opportunities for crossoperator prefix reuse and incurring unnecessary KV-cache eviction and recomputation under memory pressure. By characterizing operators according to their execution behavior, Kalypso identifies pipelining opportunities, executes query plans as stages and tasks, and manages KV-cache state through memory-aware admission control. These mechanisms enable Kalypso to turn semantic query plans into memory-aware execution pipelines that preserve reusable prefixes across operators under bounded GPU memory.

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

REFERENCES [1] Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. 2024. Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). USENIX Association, Santa Clara, CA, 117–134. https://www.usenix.org/ conference/osdi24/presentation/agrawal [2] Reza Yazdani Aminabadi, Samyam Rajbhandari, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Olatunji Ruwase, Shaden Smith, Minjia Zhang, Jeff Rasley, et al. 2022. Deepspeed-inference: enabling efficient inference of transformer models at unprecedented scale. In SC22: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 1–15. [3] Berk Atıl, Sarp Aykent, Alexa Chittams, Lisheng Fu, Rebecca J. Passonneau, Evan Radcliffe, Guru Rajan Rajagopal, Adam Sloan, Tomasz Tudrej, Ferhan Ture, Zhe Wu, Lixinyu Xu, and Breck Baldwin. 2025. Non-Determinism of “Deterministic” LLM System Settings in Hosted Environments. In Proceedings of the 5th Workshop on Evaluation and Comparison of NLP Systems, Mousumi Akter, Tahiya Chowdhury, Steffen Eger, Christoph Leiter, Juri Opitz, and Erion Çano (Eds.). Association for Computational Linguistics, Mumbai, India, 135– 148. doi:10.18653/v1/2025.eval4nlp-1.12 [4] Asma Ben Abacha, Wen-wai Yim, Yujuan Fu, Zhaoyi Sun, Meliha Yetisgen, Fei Xia, and Thomas Lin. 2025. MEDEC: A Benchmark for Medical Error Detection

[17]

[18]

[19]

[20]

[21]

and Correction in Clinical Notes. In Findings of the Association for Computational Linguistics, ACL 2025, Vienna, Austria, July 27 - August 1, 2025. Association for Computational Linguistics, 22539–22550. https://aclanthology.org/ 2025.findings-acl.1159/ Shu Chen, Deepti Raghavan, and Uğur Çetintemel. 2025. Continuous Prompts: LLM-Augmented Pipeline Processing over Unstructured Streams. arXiv:2512.03389 [cs.DB] https://arxiv.org/abs/2512.03389 Yeounoh Chung, Rushabh Desai, Jian He, Yu Xiao, Thibaud Hottelier, YvesLaurent Kom Samo, Pushkar Khadilkar, Xianshun Chen, Sam Idicula, Fatma Ozcan, Alon Halevy, and Yannis Papakonstantinou. 2026. 100x Cost & Latency Reduction: Performance Analysis of AI Query Approximation using Lightweight Proxy Models: [Experiments & Analysis]. Proceedings of the ACM on Management of Data 4, 3 (May 2026), 1–23. doi:10.1145/3802002 Karel D’Oosterlinck, François Remy, Johannes Deleu, Thomas Demeester, Chris Develder, Klim Zaporojets, Aneiss Ghodsi, Simon Ellershaw, Jack Collins, and Christopher Potts. 2023. BioDEX: Large-Scale Biomedical Adverse Drug Event Extraction for Real-World Pharmacovigilance. In Findings of the Association for Computational Linguistics: EMNLP 2023, Houda Bouamor, Juan Pino, and Kalika Bali (Eds.). Association for Computational Linguistics, Singapore, 13425–13454. doi:10.18653/v1/2023.findings-emnlp.896 In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandelwal, and Lin Zhong. 2024. Prompt cache: Modular attention reuse for low-latency inference. Proceedings of Machine Learning and Systems 6 (2024), 325–338. Guoyu Hu, Shaofeng Cai, Tien Tuan Anh Dinh, Zhongle Xie, Cong Yue, Gang Chen, and Beng Chin Ooi. 2025. HAKES: Scalable Vector Database for Embedding Search Service. Proceedings of the VLDB Endowment 18, 9 (May 2025), 3049–3062. doi:10.14778/3746405.3746427 Qiao Jin, Zifeng Wang, Charalampos S. Floudas, Fangyuan Chen, Changlin Gong, Dara Bracken-Clarke, Elisabetta Xue, Yifan Yang, Jimeng Sun, and Zhiyong Lu. 2024. Matching patients to clinical trials with large language models. Nature Communications 15, 1 (2024), 9074. doi:10.1038/s41467-024-53081-z Saehan Jo and Immanuel Trummer. 2024. Thalamusdb: Approximate query processing on multi-modal data. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–26. Yuta Koreeda and Christopher Manning. 2021. ContractNLI: A Dataset for Document-level Natural Language Inference for Contracts. In Findings of the Association for Computational Linguistics: EMNLP 2021, Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (Eds.). Association for Computational Linguistics, Punta Cana, Dominican Republic, 1907–1919. doi:10.18653/v1/2021.findings-emnlp.164 Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles. 611–626. Chunwei Liu, Matthew Russo, Michael Cafarella, Lei Cao, Peter Baile Chen, Zui Chen, Michael Franklin, Tim Kraska, Samuel Madden, Rana Shahout, et al. 2025. Palimpzest: Optimizing ai-powered analytics with declarative query processing. In Proceedings of the Conference on Innovative Database Research (CIDR). 2. Shu Liu, Asim Biswal, Amog Kamsetty, Audrey Cheng, Luis Gaspar Schroeder, Liana Patel, Shiyi Cao, Xiangxi Mo, Ion Stoica, Joseph E. Gonzalez, and Matei Zaharia. 2025. Optimizing LLM Queries in Relational Data Analytics Workloads. In Eighth Conference on Machine Learning and Systems. https://openreview.net/ forum?id=R7bK9yycHp Shicheng Liu, Jialiang Xu, Wesley Tjangnaka, Sina Semnani, Chen Yu, and Monica Lam. 2024. SUQL: Conversational Search over Structured and Unstructured Data with Large Language Models. In Findings of the Association for Computational Linguistics: NAACL 2024, Kevin Duh, Helena Gomez, and Steven Bethard (Eds.). Association for Computational Linguistics, Mexico City, Mexico, 4535– 4555. doi:10.18653/v1/2024.findings-naacl.283 Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, M Waleed Kadous, and Ion Stoica. 2025. RouteLLM: Learning to Route LLMs from Preference Data. In The Thirteenth International Conference on Learning Representations. https://openreview.net/forum?id= 8sSqNntaMr Olga Ovcharenko, Matthias Boehm, and Sebastian Schelter. 2026. SemPipes: Optimizable Semantic Data Operators for Tabular Machine Learning Pipelines. arXiv:2602.05134 [cs.LG] doi:10.48550/arXiv.2602.05134 VLDB Demo 2026. Liana Patel, Siddharth Jha, Melissa Pan, Harshit Gupta, Parth Asawa, Carlos Guestrin, and Matei Zaharia. 2025. Semantic Operators and Their Optimization: Enabling LLM-Based Data Processing with Accuracy Guarantees in LOTUS. Proceedings of the VLDB Endowment 18, 11 (2025), 4171–4184. Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin Leyton-Brown, and Yoav Shoham. 2023. In-context retrieval-augmented language models. Transactions of the Association for Computational Linguistics 11 (2023), 1316–1331. Matthew Russo and Tim Kraska. 2026. Deep Research is the New Analytics System: Towards Building the Runtime for AI-Driven Analytics. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). arXiv:2509.02751.

Son et al.

[22] Shreya Shankar, Tristan Chambers, Tarak Shah, Aditya G Parameswaran, and Eugene Wu. 2025. DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing. Proceedings of the VLDB Endowment 18, 9 (2025), 3035–3048. [23] Shreya Shankar, Sepanta Zeighami, and Aditya Parameswaran. 2026. Task Cascades for Efficient Unstructured Data Processing. In Proceedings of the 2026 ACM SIGMOD International Conference on Management of Data. arXiv:2601.05536 [cs.DB] https://arxiv.org/abs/2601.05536 [24] Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, and Wei Lin. 2024. Llumnix: Dynamic Scheduling for Large Language Model Serving. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). https://arxiv.org/abs/2406.03243 [25] James Thorne, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal. 2018. FEVER: a Large-scale Dataset for Fact Extraction and VERification. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), Marilyn Walker, Heng Ji, and Amanda Stent (Eds.). Association for Computational Linguistics, New Orleans, Louisiana, 809–819. doi:10.18653/v1/N18-1074 [26] Immanuel Trummer. 2025. Implementing Semantic Join Operators Efficiently. arXiv:2510.08489 [cs.DB] doi:10.48550/arXiv.2510.08489 [27] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention Is All You Need. In Advances in Neural Information Processing Systems, Vol. 30. [28] vLLM Project. 2026. Reproducibility - vLLM. https://docs.vllm.ai/en/latest/ usage/reproducibility/

[29] Gyeong-In Yu, Jeongmin Jeong, Gyuhong Kim, Soojeong Shin, and Byung-Gon Kim. 2022. Orca: A Distributed Serving System for Transformer-Based Generative Models. 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22) (2022), 521–538. [30] Jiayi Yuan, Hao Li, Xinheng Ding, Wenya Xie, Yu-Jhe Li, Wentian Zhao, Kun Wan, Jing Shi, Xia Hu, and Zirui Liu. 2026. Understanding and Mitigating Numerical Sources of Nondeterminism in LLM Inference. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. https://openreview. net/forum?id=Q3qAsZAEZw [31] Sepanta Zeighami, Shreya Shankar, and Aditya Parameswaran. 2026. Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees. In Proceedings of the 2026 International Conference on Management of Data. arXiv:2509.02896 [cs.DB] doi:10.48550/arXiv.2509.02896 To appear. [32] Sepanta Zeighami, Shreya Shankar, and Aditya Parameswaran. 2026. Featurized-Decomposition Join: Low-Cost Semantic Joins with Guarantees. Proceedings of the VLDB Endowment (2026). arXiv:2512.05399 [cs.DB] doi:10.48550/arXiv.2512.05399 To appear. [33] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody H Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. 2024. Sglang: Efficient execution of structured language model programs. Advances in neural information processing systems 37 (2024), 62557–62583. [34] Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. 2024. DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). https: //arxiv.org/abs/2401.09670