Paper deep dive
Kalypso: Relational LLM Serving
Hojae Son, Md Ashraful Islam, Huy Gia Cao, Hui Guan, Marco Serafini
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.57x across diverse workloads, demonstrating that query-aware LLM serving can substantially improve the efficiency of semantic query execution.
Tags
Links
- Source: https://arxiv.org/abs/2607.23815v1
- Canonical: https://arxiv.org/abs/2607.23815v1
Trouble viewing inline? Open PDF directly →
Full Text
83,402 characters extracted from source content.
Expand or collapse full text
Kalypso: Relational LLM Serving Hojae Son UMass Amherst, USAAmherstMassachusettsUSA hojaeson@umass.edu , Md Ashraful Islam UMass Amherst, USAAmherstMassachusettsUSA mdashrafulis@umass.edu , Huy Gia Cao UMass Amherst, USAAmherstMassachusettsUSA hcao@umass.edu , Hui Guan UMass Amherst, USAAmherstMassachusettsUSA huiguan@cs.umass.edu and Marco Serafini UMass Amherst, USAAmherstMassachusettsUSA marco@cs.umass.edu 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. †copyright: none 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 (Patel et al., 2025; Liu et al., 2024). 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 LLM-inference with user-defined prompts (Patel et al., 2025; Liu et al., 2025a; Jo and Trummer, 2024; Shankar et al., 2025). 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?” (Ovcharenko et al., 2026), while a semantic join can match patients to clinical trials using a natural-language predicate across tables (Jin et al., 2024). 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 (Kwon et al., 2023; Zheng et al., 2024; Yu et al., 2022; Agrawal et al., 2024; Aminabadi et al., 2022). 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 (Patel et al., 2025; Shankar et al., 2026; Chung et al., 2026; Ong et al., 2025), similarity-based pruning and pipeline decomposition (Jo and Trummer, 2024; Shankar et al., 2025; Hu et al., 2025; Ram et al., 2023), request reordering to improve prefix sharing (Liu et al., 2025b), and query optimization to find efficient plans (Liu et al., 2025a; Russo and Kraska, 2026). 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. 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 (Vaswani et al., 2017) 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 (Kwon et al., 2023) and SGLang (Zheng et al., 2024) 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 (Kwon et al., 2023), 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 KV-cache entries for this shared prompt prefix are therefore valid for the downstream operator, as long as they remain resident in GPU memory. Figure 1. Prompt structure for a filter → map query. Diagram showing a filter followed by a map on the same context. The filter and map prompts share the system prompt and context prefix, while the operator-specific instruction changes. Figure 1 illustrates this structure for a filter → map query over a paper dataset. Let S denote the system prompt and C(t)C(t) the paper text for tuple t. The filter prompt is [S∣C(t)∣Ifilter][S C(t) I_filter], where IfilterI_filter asks whether the paper is relevant to Alzheimer’s prevention. The downstream map prompt is [S∣C(t)∣Imap][S C(t) I_map], where ImapI_map asks to extract the key points. The shared reusable prefix is therefore [S∣C(t)][S C(t)]. The filter’s boolean output only determines whether the tuple reaches sem_map; it is not included in the map prompt. 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. Figure 2. When the input table exceeds available GPU KV-cache memory, downstream operators incur cache misses and must recompute the prefix. Line plot showing downstream operator runtime increasing sharply after the working set exceeds available KV-cache memory. 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 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. Figure 3. Kalypso architecture. Kalypso sits between the query client and the LLM engine. Solid arrows indicate data flow; dashed arrows indicate scheduling control. Relational LLM Serving System Architecture. Table 1. Characteristics of common semantic operators and their execution properties. M(⋅,l)M(·,l) denotes LLM evaluation under natural-language specification l, and G(⋅,l)G(·,l) denotes label generation for classification. Operator Description Logical Definition Pipelining Predicate CP sem_filter(l) Select tuples satisfying a language predicate t∈T∣M(t,l)=1\t∈ T M(t,l)=1\ Y Y N sem_map(l) Transform each tuple via a language instruction M(t,l)∣t∈T\M(t,l) t∈ T\ Y N N sem_join(l) Join two relations via language predicate (ti,tj)∣M((ti,tj),l)=1\(t_i,t_j) M((t_i,t_j),l)=1\ Y Y Y sem_classify(l) Assign category labels to each tuple (G(t,l))∣t∈T\(G(t,l)) t∈ T\ Y N N sem_agg(l) Aggregate multiple tuples using a language reducer M(t1,…,tn,l)M(\t_1,…,t_n\,l) N N N sem_topk(l,k) Select top-k tuples according to language ranking Topk(T,l)Top_k(T,l) N N N 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 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. 4. 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? (3- Cartesian Product) does the operator join tuples from two tables? Table 1 classifies semantic operators introduced in (Patel et al., 2025) 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-k 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. 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. 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. 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 right-side tuples that should be joined with the left-side tuple. The final Cartesian product between the tuples is executed by Kalypso. 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. Figure 4. Executing a semantic query plan with pipelining. Execution timeline illustrating pipelined stages, dependent tasks, and cache-aware scheduling under memory pressure across a semantic query plan. 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 A and launches three tasks. Task 1.1 takes tuple a1a_1 and produces a1′a _1 (extending the tuple with generated content); task 1.2 filters out a2a_2; task 1.3 similarly takes a3a_3 and produces a3′a _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, a1′a _1 enters the queue for the second stage; the Cartesian product combines it with tuples from table B, 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 a1′a _1. If the scheduler launches too many concurrent tasks, it could create memory pressure that could lead to the eviction of the prefix for a1′a _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 task 2.2, one for each tuple in table C. 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. Figure 5. A parallel depth-first policy can starve downstream stages. Timeline showing a parallel depth-first scheduling policy that repeatedly prioritizes later-stage tasks, causing earlier-stage tasks to wait and reducing the supply of future downstream work. 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 Kalypso’s Scheduling Algorithm (Single Pipeline). 1 procedure Schedule()(stages) 2 ←∅running← , ←[]out←[\ ] 3 ←[0]firstStage [0] 4 ←.()tasks .inputTable() 5 ..()firstStage.waiting.enqueue(tasks) 6 while .ℎ()stages.hasWaitingTasks() or ≠∅running≠ do 7 Launch(,)(stages,running) 8 for each (,,)∈.()(stage,task,result) .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 do 15 while .≠∅stage.waiting≠ do 16 ←..()task .waiting.peek() 17 if .(,)memoryManager.admit(stage,task) then 18 ←..()task .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 .lastStage() then 30 ←[.+1]nextStage [stage.id+1] 31 ℎ←(,.())childrenTasks (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 do 40 if .()memoryManager.isSaturated(stage) and ≠[0]stage [0] then 41 .(=,=.())memoryManager.transferMem(from=stage,to=stages.lastStage()) 42 for i∈[.().,1]i∈[stages.lastStage().id,1] do 43 =[i]stage=stages[i] 44 =[i−1]prevStage=stages[i-1] 45 if .()memoryManager.isStarving(stage) 46 and not .()memoryManager.isStarving(prevStage) then 47 .(=,=)memoryManager.transferMem(from=stage,to=prevStage) Pseudocode for the scheduler main loop, task admission, and adaptive stage-budget rebalancing. Algorithm 5.3 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 5.3-5.3). 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 5.3-5.3). 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 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 5.3-5.3). 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 5.3-5.3). The Rebalance procedure adaptively rebalances memory budgets among stages. The budget for each stage is always larger than sminBudget_s, 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 sminBudget_s, 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. The memory manager keeps a low and high queue threshold for each stage s, initialized as: ℎs=α⋅s,s=β⋅s,high_s=α· budget_sminBudget_s, _s=β· budget_sminBudget_s, where sbudget_s is the current memory budget assigned to s and α,β∈(0,1)α,β∈(0,1) are configurable static parameters with α>βα>β. The memory manager then classifies the stage s as starving if the size of its waiting queue is smaller than slow_s or saturated if it is larger than ℎshigh_s. Figure 6. A parallel breadth-first policy can saturate the KV-cache budget. Timeline showing a parallel breadth-first scheduling policy that admits too many early-stage tasks, fills memory with reserved prefix memory, and leaves insufficient capacity for downstream tasks. Rebalance uses these states to transfer budget between stages. If a stage is saturated (lines 5.3-5.3), 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 5.3-5.3), 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 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 output-to-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 (Patel et al., 2025; Liu et al., 2025a) 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 output-token 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 operator-at-a-time execution. We configure all systems to use vLLM as the underlying LLM engine. • Lotus (v1.1.4) (Patel et al., 2025) 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) (Liu et al., 2025a), 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) to 11 and 0.50.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.3-70B-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 make query execution as deterministic as possible across multiple runs, following vLLM’s reproducibility guidance (vLLM Project, 2026). We set VLLM_ENABLE_V1_MULTIPROCESSING=0, which makes offline scheduling deterministic. We use greedy decoding with temperature 0, top-p 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 (Atıl et al., 2025; Yuan et al., 2026), so we also run each experiment three times and report average measurements. 7.2. 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 (Patel et al., 2025). Table 2. Summary of Workloads. # LLM calls Workload Data # Tuples Avg. tok. Lotus Palimp Kalypso FEVER Claims Wikipedia 1,000 5,416,568 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) Figure 7. End-to-end latency and speedup across workloads. Four bar plots showing end-to-end latency for FEVER, MEDEC, BioDEX, and ContractNLI. Each bar is annotated with speedup relative to Lotus. FEVER fact verification. 1 claims.sem_map( 2 "Generate two concise Wikipedia search queries." 3 ).index_search( 4 index_table=wikipedia_collection, top_k=5 5 ).sem_filter( 6 "Based on retrieved Wikipedia content, is the claim supported?", 7 cascade=True 8 ) FEVER is a fact verification workload, where each claim is checked against evidence taken from Wikipedia (Thorne et al., 2018). We sample 1,000 FEVER claims, as done in the Lotus paper (Patel et al., 2025), 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 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 single-stage pipeline with three operators. MEDEC medical error detection and correction. 1 notes_df.sem_filter( 2 "Answer true if any numbered sentence in the patient note " 3 "is medically inconsistent." 4 ).sem_map( 5 "Identify the numbered sentence that contains the medical error." 6 ).sem_map( 7 "Generate the corrected version of the erroneous sentence." 8 ) The MEDEC workload (Ben Abacha et al., 2025) 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 (Ben Abacha et al., 2025): 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 non-deterministic 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. BioDEX biomedical reaction matching. 1 articles.sem_map( 2 "Extract adverse drug reaction labels described for the patient." 3 ).sem_join( 4 right_table=reactions, icp=True 5 ).sem_filter( 6 icp_predicate="Does the article describe this adverse drug reaction?", 7 cascade_low_threshold=low, cascade_high_threshold=high 8 ) The BioDEX workload matches each biomedical article with the adverse drug reactions it describes (D’Oosterlinck et al., 2023). The set of reactions is taken from a large database. For all systems, we use the query plan and the operator implementations described in (Patel et al., 2025). 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 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 contracts.sem_filter( 2 "Is this document a valid contract or agreement text " 3 "with enough clauses to evaluate confidentiality obligations?" 4 ).sem_join( 5 right_table=hypotheses, "Given the contract and hypothesis, " 6 "does the contract entail the hypothesis?" 7 ).sem_map( 8 "Explain briefly why the contract entails the hypothesis, " 9 "citing the relevant obligation or clause." 10 ) ContractNLI (Koreeda and Manning, 2021) 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 non-deterministic 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. Figure 8. Effect of GPU memory utilization on end-to-end latency across workloads. Line plots comparing Lotus, Palimpzest, and Kalypso latency across FEVER, MEDEC, BioDEX, and ContractNLI workloads. 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 lower-latency 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. 7.4. Execution Policy Ablations Figure 9. Latency for Kalypso in blocking mode (operator-at-a-time, no cross-operator KV-cache reuse or pinning) vs. pipelined mode (default). Grouped bar plot comparing blocking and pipelined execution latency across FEVER, MEDEC, BioDEX, and ContractNLI. 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. 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. Two-by-two bar plots comparing fixed stage-budget ratios and adaptive budgeting on BioDEX and ContractNLI at 0.9 and 0.6 vLLM memory utilization. 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 KV-cache 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 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 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. Figure 11. Latency with virtual pinning and explicit pinning. Grouped bar plot comparing virtual pinning and explicit pinning. Explicit pinning is slightly faster on FEVER, BioDEX, and ContractNLI, but slower on MEDEC. 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. Latency under fixed output-token budgets. The dashed line shows Kalypso’s default token budgeting. Line plot showing latency under fixed output-token budgets and Kalypso’s default token budgeting, which is lower than every fixed budget in the sweep. 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. 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 high-memory 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 (Yu et al., 2022); vLLM improves KV-cache memory efficiency through PagedAttention (Kwon et al., 2023); and Sarathi reduces prefill–decode interference through chunked prefills (Agrawal et al., 2024). DistServe disaggregates prefill and decode across separately provisioned GPUs (Zhong et al., 2024), while Llumnix dynamically migrates requests among model instances to improve load balance and isolation (Sun et al., 2024). 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 (Zheng et al., 2024), while vLLM supports automatic prefix caching for requests with shared prompt prefixes (Kwon et al., 2023). Prompt-caching mechanisms similarly reuse attention state for stable prompt components such as system messages, templates, and long context documents (Gim et al., 2024). These system support prefix reuse opportunistically among requests visible to them, as long as the relevant prefixes remain in they KV-cache. 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. Optimizing Semantic Operator Implementations. Prior work reduces expensive LLM calls using model cascades and proxy models (Patel et al., 2025; Shankar et al., 2026; Chung et al., 2026; Zeighami et al., 2026a). 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 (Zeighami et al., 2026b). 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 (Trummer, 2025). Other systems organize document chunks for prompt-cache discounts (Shankar et al., 2026) or fuse semantic operators in streaming query plans (Chen et al., 2025), 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 cross-operator 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. References A. Agrawal, N. Kedia, A. Panwar, J. Mohan, N. Kwatra, B. Gulavani, A. Tumanov, and R. Ramjee (2024) Taming Throughput-Latency tradeoff in LLM inference with Sarathi-Serve. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), Santa Clara, CA, p. 117–134. External Links: ISBN 978-1-939133-40-3, Link Cited by: §1, §8. R. Y. Aminabadi, S. Rajbhandari, A. A. Awan, C. Li, D. Li, E. Zheng, O. Ruwase, S. Smith, M. Zhang, J. 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, p. 1–15. Cited by: §1. B. Atıl, S. Aykent, A. Chittams, L. Fu, R. J. Passonneau, E. Radcliffe, G. R. Rajagopal, A. Sloan, T. Tudrej, F. Ture, Z. Wu, L. Xu, and B. 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, M. Akter, T. Chowdhury, S. Eger, C. Leiter, J. Opitz, and E. Çano (Eds.), Mumbai, India, p. 135–148. External Links: Link, Document, ISBN 979-8-89176-305-0 Cited by: §7.1. A. Ben Abacha, W. Yim, Y. Fu, Z. Sun, M. Yetisgen, F. Xia, and T. Lin (2025) MEDEC: a benchmark for medical error detection and correction in clinical notes. In Findings of the Association for Computational Linguistics, ACL 2025, Vienna, Austria, July 27 - August 1, 2025, p. 22539–22550. External Links: Link Cited by: §7.2. S. Chen, D. Raghavan, and U. Çetintemel (2025) Continuous prompts: llm-augmented pipeline processing over unstructured streams. External Links: 2512.03389, Link Cited by: §8. Y. Chung, R. Desai, J. He, Y. Xiao, T. Hottelier, Y. Kom Samo, P. Khadilkar, X. Chen, S. Idicula, F. Ozcan, A. Halevy, and Y. 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), p. 1–23. External Links: ISSN 2836-6573, Link, Document Cited by: §1, §8. K. D’Oosterlinck, F. Remy, J. Deleu, T. Demeester, C. Develder, K. Zaporojets, A. Ghodsi, S. Ellershaw, J. Collins, and C. Potts (2023) BioDEX: large-scale biomedical adverse drug event extraction for real-world pharmacovigilance. In Findings of the Association for Computational Linguistics: EMNLP 2023, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, p. 13425–13454. External Links: Link, Document Cited by: §7.2. I. Gim, G. Chen, S. Lee, N. Sarda, A. Khandelwal, and L. Zhong (2024) Prompt cache: modular attention reuse for low-latency inference. Proceedings of Machine Learning and Systems 6, p. 325–338. Cited by: §8. G. Hu, S. Cai, T. T. A. Dinh, Z. Xie, C. Yue, G. Chen, and B. C. Ooi (2025) HAKES: scalable vector database for embedding search service. Proceedings of the VLDB Endowment 18 (9), p. 3049–3062. External Links: ISSN 2150-8097, Link, Document Cited by: §1. Q. Jin, Z. Wang, C. S. Floudas, F. Chen, C. Gong, D. Bracken-Clarke, E. Xue, Y. Yang, J. Sun, and Z. Lu (2024) Matching patients to clinical trials with large language models. Nature Communications 15 (1), p. 9074. External Links: Document Cited by: §1. S. Jo and I. Trummer (2024) Thalamusdb: approximate query processing on multi-modal data. Proceedings of the ACM on Management of Data 2 (3), p. 1–26. Cited by: §1, §1. Y. Koreeda and C. Manning (2021) ContractNLI: a dataset for document-level natural language inference for contracts. In Findings of the Association for Computational Linguistics: EMNLP 2021, M. Moens, X. Huang, L. Specia, and S. W. Yih (Eds.), Punta Cana, Dominican Republic, p. 1907–1919. External Links: Link, Document Cited by: §7.2. W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica (2023) Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles, p. 611–626. Cited by: §1, §2.1, §2.1, §8, §8. C. Liu, M. Russo, M. Cafarella, L. Cao, P. B. Chen, Z. Chen, M. Franklin, T. Kraska, S. Madden, R. Shahout, et al. (2025a) Palimpzest: optimizing ai-powered analytics with declarative query processing. In Proceedings of the Conference on Innovative Database Research (CIDR), p. 2. Cited by: §1, §1, 2nd item, §7. S. Liu, J. Xu, W. Tjangnaka, S. Semnani, C. Yu, and M. Lam (2024) SUQL: conversational search over structured and unstructured data with large language models. In Findings of the Association for Computational Linguistics: NAACL 2024, K. Duh, H. Gomez, and S. Bethard (Eds.), Mexico City, Mexico, p. 4535–4555. External Links: Link, Document Cited by: §1. S. Liu, A. Biswal, A. Kamsetty, A. Cheng, L. G. Schroeder, L. Patel, S. Cao, X. Mo, I. Stoica, J. E. Gonzalez, and M. Zaharia (2025b) Optimizing LLM queries in relational data analytics workloads. In Eighth Conference on Machine Learning and Systems, External Links: Link Cited by: §1. I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica (2025) RouteLLM: learning to route LLMs from preference data. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §1. O. Ovcharenko, M. Boehm, and S. Schelter (2026) SemPipes: optimizable semantic data operators for tabular machine learning pipelines. Note: VLDB Demo 2026 External Links: 2602.05134, Document Cited by: §1. L. Patel, S. Jha, M. Pan, H. Gupta, P. Asawa, C. Guestrin, and M. Zaharia (2025) Semantic operators and their optimization: enabling llm-based data processing with accuracy guarantees in lotus. Proceedings of the VLDB Endowment 18 (11), p. 4171–4184. Cited by: §1, §1, §4, 1st item, §7.2, §7.2, §7.2, §7, §8. O. Ram, Y. Levine, I. Dalmedigos, D. Muhlgay, A. Shashua, K. Leyton-Brown, and Y. Shoham (2023) In-context retrieval-augmented language models. Transactions of the Association for Computational Linguistics 11, p. 1316–1331. Cited by: §1. M. Russo and T. 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), Note: arXiv:2509.02751 Cited by: §1. S. Shankar, T. Chambers, T. Shah, A. G. Parameswaran, and E. Wu (2025) DocETL: agentic query rewriting and evaluation for complex document processing. Proceedings of the VLDB Endowment 18 (9), p. 3035–3048. Cited by: §1, §1. S. Shankar, S. Zeighami, and A. Parameswaran (2026) Task cascades for efficient unstructured data processing. In Proceedings of the 2026 ACM SIGMOD International Conference on Management of Data, External Links: 2601.05536, Link Cited by: §1, §8. B. Sun, Z. Huang, H. Zhao, W. Xiao, X. Zhang, Y. Li, and W. Lin (2024) Llumnix: dynamic scheduling for large language model serving. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), External Links: Link Cited by: §8. J. Thorne, A. Vlachos, C. Christodoulopoulos, and A. 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), M. Walker, H. Ji, and A. Stent (Eds.), New Orleans, Louisiana, p. 809–819. External Links: Link, Document Cited by: §7.2. I. Trummer (2025) Implementing semantic join operators efficiently. External Links: 2510.08489, Document, Link Cited by: §8. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin (2017) Attention is all you need. In Advances in Neural Information Processing Systems, Vol. 30. Cited by: §2.1. vLLM Project (2026) Reproducibility - vllm. External Links: Link Cited by: §7.1. G. Yu, J. Jeong, G. Kim, S. Shin, and B. Kim (2022) Orca: a distributed serving system for transformer-based generative models. 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), p. 521–538. Cited by: §1, §8. J. Yuan, H. Li, X. Ding, W. Xie, Y. Li, W. Zhao, K. Wan, J. Shi, X. Hu, and Z. Liu (2026) Understanding and mitigating numerical sources of nondeterminism in LLM inference. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, External Links: Link Cited by: §7.1. S. Zeighami, S. Shankar, and A. Parameswaran (2026a) Cut costs, not accuracy: llm-powered data processing with guarantees. In Proceedings of the 2026 International Conference on Management of Data, Note: To appear External Links: 2509.02896, Document Cited by: §8. S. Zeighami, S. Shankar, and A. Parameswaran (2026b) Featurized-decomposition join: low-cost semantic joins with guarantees. Proceedings of the VLDB Endowment. Note: To appear External Links: 2512.05399, Document, Link Cited by: §8. L. Zheng, L. Yin, Z. Xie, C. Sun, J. Huang, C. H. Yu, S. Cao, C. Kozyrakis, I. Stoica, J. E. Gonzalez, et al. (2024) Sglang: efficient execution of structured language model programs. Advances in neural information processing systems 37, p. 62557–62583. Cited by: §1, §2.1, §8. Y. Zhong, S. Liu, J. Chen, J. Hu, Y. Zhu, X. Liu, X. Jin, and H. 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), External Links: Link Cited by: §8.