Skip to content

Efficient Iterative Retrieval with Heterogeneous Batching

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/illinoisdata/Orthrus
Area: LLM Efficiency
Keywords: LLM serving, iterative RAG, heterogeneous batching, intra-batch scheduling, incremental pooling

TL;DR

Addressing the complementary nature of compute-bound embedding and memory-bound generation in iterative RAG, ORTHRUS introduces a unified inference loop with heterogeneous batching, chunked embedding with incremental pooling, and workload-aware intra-batch scheduling to eliminate static GPU partitioning bubbles, achieving 1.28ร—โ€“4.52ร— higher throughput and cutting end-to-end p99 latency by up to 55.8%.

Background & Motivation

Modern retrieval-augmented generation (RAG) pipelines are rapidly evolving from static single-turn retrieval into multi-step iterative retrieval (Iter-RetGen), where language models and embedding models alternate repeatedly to identify knowledge gaps, formulate sub-queries, and refine answers. However, contemporary serving systems such as vLLM are architected under the assumption of homogeneous executionโ€”either serving generation decodes or processing dense embedding forward passes in complete isolation. In multi-GPU clusters, current industry practice relies on coarse-grained static GPU partitioning (e.g., dedicating certain GPUs strictly to embeddings and others to generation) or running two independent server processes on the same GPU. These approaches struggle severely under dynamic, shifting workloads: optimal partitioning ratios cannot be anticipated in advance, dynamic repartitioning incurs costly model weight reloading overheads, and co-located processes suffer from severe GPU memory contention and scheduling thrashing.

The fundamental root cause of this low throughput and GPU underutilization lies in the diametrically opposed hardware execution characteristics of the two tasks. Generating text autoregressively is inherently memory-bound during its decoding phase: each decode step fetches substantial Key-Value (KV) cache state from high-bandwidth memory while executing very few arithmetic operations per token. Conversely, producing dense embeddings is intensely compute-bound: the entire text passage is ingested in a dense parallel forward pass through all Transformer layers and aggregated via pooling into a single vector, yielding high arithmetic intensity with minimal KV cache retention. When served in isolation or via naive homogeneous batches, lightweight generation tokens are forced to stall behind bulky embedding requests, creating substantial computational bubbles and starving compute cores or memory buses across the hardware.

ORTHRUS resolves this dilemma through a simple yet powerful realization: compute-bound embeddings and memory-bound generation decodes naturally complement each other's hardware bottlenecks, meaning co-scheduling them inside the same execution pass can fill each other's resource voids without contention. Core idea: build ORTHRUS, a serving engine that unifies embedding and generation within a single inference pass via chunked embedding with incremental pooling, governed by an intra-batch scheduler that dynamically allocates batch capacity in exact proportion to remaining token workloads to achieve high throughput and low tail latency.

Method

Overall Architecture

The core architecture of ORTHRUS unifies embedding and generation execution paths within a single Unified Runner, treating them as composable token streams rather than isolated workloads. The engine maintains distinct waiting queues for embeddings (\(Q_e\)) and generation requests (\(Q_g\)). Each scheduling iteration operates across three tightly integrated stages: 1. Schedule: The scheduler inspects in-flight request states and remaining queue backlogs to construct a heterogeneous batch composed of embedding chunks, generation prefill chunks, and single generation decode tokens. Requests of identical types are grouped contiguously in GPU memory to eliminate tensor shuffling overheads. 2. Forward: The combined batch executes a single joint forward pass across shared Transformer layers (attention and feed-forward networks). 3. Emit: Hidden states diverge cleanly according to request type: generation decode tokens pass into the sampler to produce subsequent tokens, while embedding chunks are consumed by the incremental pooler to stream intermediate pooling accumulators and emit the final vector upon chunk completion.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Mixed Workload Arrival<br/>Embedding Queue Qe & Generation Queue Qg"] --> B["Intra-Batch Scheduling IBS<br/>Token-workload proportional budget allocation"]
    B --> C["Batch Unit Construction<br/>Contiguous memory layout: Embed chunks + Prefill + Decode tokens"]
    C --> D["Unified Transformer Forward Pass<br/>Shared weights and joint Attention/FFN execution"]
    D --> E{"Request Output Path"}
    E -->|Generation Decode| F["Sampler<br/>Sample next token & append to KV Cache"]
    E -->|Embedding Chunk| G["Incremental Pooler<br/>Streaming accumulator update / Emit final vector"]

Key Designs

1. Chunked Embedding with Incremental Pooling: Breaking Monolithic Forward Passes for Fine-Grained Co-Scheduling Under traditional serving pipelines, an embedding request must be evaluated atomically in a single monolithic forward pass spanning the entire sequence. This all-or-nothing execution creates head-of-line blocking and severe internal fragmentation: whenever the residual batch token budget is smaller than the full sequence length, the embedding request cannot be admitted, leaving GPU capacity stranded. ORTHRUS borrows principles from incremental query processing to decompose an input of length \(n\) into \(K\) fine-grained chunks \(c_1, c_2, \dots, c_K\) of size at most \(C\), where \(\sum_{k=1}^K c_k = n\). At iteration \(k\), the forward pass computes hidden states \(H^{(k)} \in \mathbb{R}^{c_k \times d}\). For standard mean and weighted-mean pooling, the incremental pooler streams state updates across iterations using two running accumulators:

\[S^{(k)} = S^{(k-1)} + \sum_{j=1}^{c_k} w_{k,j} H^{(k)}_j, \quad W^{(k)} = W^{(k-1)} + \sum_{j=1}^{c_k} w_{k,j}, \quad S^{(0)}=0, W^{(0)}=0\]

Upon processing the final chunk \(K\), the pooler directly emits the exact embedding vector \(S^{(K)} / W^{(K)}\). For CLS or last-token pooling heads, the engine merely retains the first token of chunk 1 or the terminal token of chunk \(K\), requiring only \(O(d)\) persistent state per request. This formulation is algebraically identical to single-pass evaluation (differing only by negligible floating-point non-associativity) while providing the scheduler with sub-sequence granularity to fill remaining batch slots alongside single-token decodes.

2. Intra-Batch Scheduling (IBS): Workload-Aware Proportional Capacity Allocation Simple first-come-first-served (FCFS) policies or fixed heuristic ratios (such as 1:2) break down under dynamic iterative retrieval workloads where output lengths vary unpredictably per query, causing either generation starvation or embedding backlogs. IBS enforces three design criteria: proportional capacity matching instantaneous demand, per-type FCFS arrival ordering, and strict prevention of head-of-line blocking. IBS first reserves necessary token slots for in-flight generation decode steps to protect established KV caches from eviction. For the remaining token budget \(B\), IBS tallies the total outstanding token counts across both queues:

\[w_e = \sum_{r \in Q_e} \text{tokens}(r), \quad w_g = \sum_{r \in Q_g} \text{tokens}(r)\]

The scheduler tracks persistent scheduling credits \(a_e\) and \(a_g\) across iterations. At each selection step, both accumulators increment by their respective weights (\(a_e \leftarrow a_e + w_e, a_g \leftarrow a_g + w_g\)), and the scheduler admits a request (or chunk) from the queue with the larger accumulator, subsequently decrementing that accumulator by \(w_e + w_g\). This credit tracking guarantees that scheduled token ratios asymptotically converge to \(w_e : w_g\), completely preventing scheduler-induced starvation while dynamically adapting batch composition to shifting real-time demand.

3. Contiguous Memory Layout and Direct Kernel Dispatch: Eliminating Tensor Re-ordering Overhead Packing three distinct execution primitives (embedding chunks, prefill chunks, and single decode tokens) into a shared forward pass risks substantial memory thrashing if representations are randomly interleaved across the batch tensor, necessitating expensive gather/scatter memory copies before invoking task-specific downstream kernels. ORTHRUS resolves this by enforcing a canonical request ordering during batch formation: generation prefills are placed first, followed contiguously by embedding chunks, and concluding with single decode tokens. Consequently, the output hidden state tensor \(H\) consists of contiguous memory slices for each task category. Downstream componentsโ€”including the incremental pooler, token sampler, and KV cache update handlersโ€”operate directly on these contiguous tensor slices with zero intermediate copies or kernel launches.

Key Experimental Results

Main Results

The authors evaluated ORTHRUS on up to four NVIDIA A100-40GB GPUs across representative open-weight LLMs (Mistral-7B, Qwen2-7B, LLaMA-3.1-8B with e5-mistral-7b-instruct LoRA adapter) and a realistic multi-step RAG benchmark (Iter-RetGen on 2WikiMultihopQA with average prompt lengths of 500 tokens, average decodes of 3000 tokens, and 1โ€“10 retrieved documents per turn).

Evaluated baselines included Dedicated (disjoint GPU pools for embed/gen), Disagg-PD (prefill/decode disaggregation), Unified-Homo (co-located same-GPU with homogeneous batching), Unified-Hetero (heterogeneous batching with FCFS), and ORTHRUS (heterogeneous batching with IBS).

Benchmark / Workload Setup Evaluated Metric ORTHRUS (Ours) Baseline (Dedicated / Unified-Homo) Relative Advantage / Gain
4ร—A100 Real RAG (Iter-RetGen) E2E Request Throughput (req/s) 0.624 (Emb 0.288 / Gen 0.336) Dedicated: 0.260 / Unified-Homo: 0.548 2.40ร— higher throughput vs. Dedicated (+140%)
4ร—A100 Real RAG (Iter-RetGen) E2E p99 Latency (s) 593.4 Dedicated: 1342.0 / Unified-Homo: 700.6 55.8% lower p99 latency vs. Dedicated
1ร—A100 Real RAG (Iter-RetGen) E2E p99 Latency (s) 573.9 Unified-Homo: 673.4 (Disagg unsupported) 14.8% lower p99 latency on single-GPU
Dynamic 3-Phase Workload (1:9โ†’5:5โ†’9:1) Average GPU Utilization 79.0% Dedicated1:3: 38.0% +41 pp higher utilization, completes 43% faster
Controlled 5:5 Mix (Mistral-7B) Throughput (Emb / Gen req/s) 25.32 / 26.24 Dedicated: 12.54 / 11.97 Throughput doubled across both tasks (2.02ร— / 2.19ร—)
Controlled 9:1 Mix (Mistral-7B) Throughput (Emb / Gen req/s) 58.80 / 7.00 Dedicated: 15.64 / 1.49 3.76ร— embedding gain, 4.70ร— generation gain

Ablation Study

Ablations verified: (1) token packing efficiency under chunked vs. atomic embeddings; (2) mathematical fidelity of incremental pooling across pooling heads; (3) scheduling fairness and queue latency under IBS.

Experimental Configuration Target Metric Measured Value / Behavior Analytic Conclusion
Batch Packing: Atomic Embedding Token Budget Fill / Embed Throughput 8.8% budget fill / 25.5 req/s Monolithic sequences fail to fit residual budgets, stranding hardware capacity
Batch Packing: Chunked (C=64) Token Budget Fill / Embed Throughput 85.7% budget fill / 26.9 req/s Token packing efficiency surges nearly 10ร— without degrading generation throughput (93.3 req/s)
Incremental Pooling: Mean Head Min Cosine Sim / Relative L2 Error CosSim \(\ge\) 0.999948 / L2 \(\le\) 0.0095 Fully equivalent to single-pass pooling; differences solely from floating-point reduction order
Incremental Pooling: CLS / Last-Token Min Cosine Sim / Relative L2 Error CosSim \(\ge\) 0.999983 / L2 \(\le\) 0.0055 Exact positional state retention with zero numerical drift
Scheduler Policy: FCFS vs. IBS Embedding p99 Latency (1000 Gen+1000 Emb) IBS: 73 s vs. FCFS: 87 s IBS eliminates head-of-line blocking, cutting embedding tail latency by 16% and gen p99 by 9%
Disjoint Models (OPT-1.3B + GTR-T5) Single-GPU Serving Gain Emb Throughput +22.9%, Gen Throughput +20.2% Co-scheduling provides solid gains even when architectures do not share backbones

Key Findings

  • Complementary Resource Exploitation: Profiling confirms that pure embedding saturates GPU arithmetic units (85.3% compute) while consuming little memory bandwidth (36.5%), whereas generation decodes saturate memory bus throughput (90.5%) while underutilizing compute cores (75.5%). Heterogeneous batching co-locates these demands, lifting overall utilization from 38% to 79%.
  • Hyperparameter Robustness: Sweeping chunk size \(C \in [128, 1024]\) and per-iteration token budget \(B \in [2048, 8192]\) produces less than 1% variance in aggregate throughput, demonstrating that ORTHRUS does not require delicate hyperparameter tuning.
  • SLA Tail Latency Isolation: Scaling generation decode length from 256 to 4096 tokens increases generation p99 latency from 7.06s to 79.68s (>11ร— increase). Concurrently, embedding p99 latency remains bounded between 53.09ms and 59.92ms (<7ms drift), proving that IBS successfully shields latency-sensitive embeddings from decode monopolization.

Highlights & Insights

  • Zero-Retraining System-Level Unification: ORTHRUS achieves dramatic throughput and latency gains strictly through inference engine abstractions on top of vLLM v0.92, preserving existing PagedAttention memory layouts and model checkpoints without retraining.
  • Incremental Pooling as a Computational Leveler: Breaking monolithic embedding sequences into streamable chunks transforms heavy batch operations into uniform token chunks, converting compute-bound embeddings into an elastic "gap filler" for memory-bound decoding slots.
  • Credit-Based Fairness under Dynamic Workloads: Intra-Batch Scheduling replaces brittle static ratios with persistent credit accumulation scaled by outstanding token counts, providing theoretical starvation-freedom and seamless adaptability.

Limitations & Future Work

  • Multi-GPU Parallelism Scalability: The current implementation scales via independent model replicas across GPUs (up to 4 A100s). Scaling across distributed clusters requiring Tensor Parallelism (TP) or Pipeline Parallelism (PP) introduces cross-node synchronization barriers whose interplay with heterogeneous batching remains unexamined.
  • Sensitivity to Backbone Sharing: Optimal hardware utilization benefits are achieved when embedding and generation share a foundational model backbone (e.g., via LoRA adapters). While disjoint models benefit from co-scheduling, they cannot share a unified forward matrix multiplication.
  • Decoupled Vector Search Execution: ORTHRUS optimizes model-side serving exclusively and treats vector database retrieval (ANN search) as an external system. Tighter co-design between memory-resident vector indices and model execution loops remains an open avenue.
  • vs vLLM / Orca / Sarathi-Serve: State-of-the-art serving frameworks pioneered iteration-level scheduling and chunked prefilling for autoregressive generation, but treat embedding as a foreign workload; ORTHRUS integrates embedding into the native iteration loop.
  • vs DistServe / Mooncake (PD Disaggregation): Disaggregated serving separates prefill and decode across dedicated GPU clusters via network KV transfer, which is infeasible or wasteful on single-GPU or small-scale setups; ORTHRUS achieves lower latency and higher throughput by harmonizing complementary phases within local GPU memory.
  • vs SLoRA / Punica: Multi-tenant LoRA systems manage concurrent adapter execution for generative tasks; ORTHRUS demonstrates that adapter multiplexing across divergent task paradigms (embedding vs. generation) unlocks substantial hardware synergies.

Rating

  • Novelty: โญโญโญโญโญ Pioneering heterogeneous batching and incremental pooling to unify embedding and generation serving.
  • Experimental Thoroughness: โญโญโญโญโญ Comprehensive evaluation spanning multiple open LLMs, real multi-hop QA RAG benchmarks, and detailed ablations.
  • Writing Quality: โญโญโญโญโญ Rigorous motivation, lucid architectural exposition, and clear mathematical formulation.
  • Value: โญโญโญโญโญ Highly actionable and immediate blueprint for industrial serving of modern agentic and iterative RAG architectures.