Efficient Iterative Retrieval with Heterogeneous Batching¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/illinoisdata/Orthrus
Area: Information Retrieval & RAG
Keywords: Iterative Retrieval, RAG Serving, Heterogeneous Batching, Incremental Pooling, Intra-Batch Scheduling
TL;DR¶
Addressing the severe GPU underutilization and computational bubbles caused by alternating embedding (compute-bound) and generation (memory-bound) workloads in iterative RAG, ORTHRUS enables heterogeneous batching within a unified inference loop through chunked embedding, incremental pooling, and workload-aware intra-batch scheduling.
Background & Motivation¶
Modern retrieval-augmented generation (RAG) applications increasingly transition from one-shot retrieval to multi-step iterative retrieval workflows. In scenarios such as multi-hop question answering or ambiguous query resolution, a system first embeds a user's initial query into dense vectors to search a vector database. When the retrieved documents prove insufficient or introduce follow-up ambiguities, a generative language model formulates new search queries, which are subsequently embedded to retrieve supplementary documents. This alternating cycle continues until sufficient supporting context has been gathered. Consequently, production serving backends are confronted with a heavily interleaved, mixed workload of embedding and generation requests.
Existing large language model (LLM) serving systems, such as vLLM, are designed to process embedding and generation workloads strictly in isolation through homogeneous batching. When deploying these workloads across multiple GPUs, operators typically resort to static GPU partitioning (for example, assigning dedicated GPUs exclusively to embedding and the remainder to generation). This coarse-grained separation suffers from two fundamental flaws: first, accurately predicting the optimal resource allocation ratio across dynamic, shifting query patterns is notoriously difficult, while dynamically repartitioning requires costly model weight reloading; second, embedding tasks are inherently compute-bound dense forward passes over entire inputs, whereas generation decode steps are memory-bound passes reading large Key-Value (KV) caches to predict a single token. Partitioning them onto separate GPUs inevitably produces computational bubbles, leaving embedding GPUs idle during generation-heavy phases and generation GPUs starved during embedding spikes. Furthermore, running two separate serving processes on the same GPU introduces kernel serialization and severe GPU memory fragmentation.
This paper tackles this fundamental tension by asking: can embedding and generation tasks be unified into a single model execution pass on the same GPU to complement each other's hardware bottlenecks? Core idea: build ORTHRUS, a serving system that performs heterogeneous batching within a unified inference loop by decomposing input texts via chunked embedding, maintaining streamable representations via incremental pooling, and dynamically arbitrating batch composition through an intra-batch scheduler that balances remaining token workloads without head-of-line blocking or model retraining.
Method¶
Overall Architecture¶
ORTHRUS targets workloads served either via shared-backbone architectures (e.g., a base LLM equipped with a LoRA adapter for embedding) or co-located multi-model deployments. The system operates on an iteration-level scheduling paradigm, decomposing each inference cycle into three tightly coupled, blocking stages: Schedule, Forward, and Emit. In the Schedule stage, generation decode tokens, generation prefill chunks, and embedding chunks are packed into a single batch. In the Forward stage, all batched tokens pass through the shared Transformer attention and feed-forward layers in a single pass. In the Emit stage, the hidden states diverge into dedicated, contiguous output paths: generation tokens proceed to the sampler to predict the next token and update the KV cache, while embedding tokens are routed to the incremental pooler to update running vector representations.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Mixed Request Queues<br/>Generation Queue Qg + Embedding Queue Qe"] --> B["Intra-Batch Scheduler (IBS)<br/>Prioritize In-Flight Decodes + Token-Proportional Credit"]
B --> C["Contiguous Batch Layout<br/>Grouped by Type to Eliminate Gather Overhead"]
C --> D["Unified Model Forward Pass<br/>Shared Transformer Attention & FFN"]
D --> E{"Parallel Output Processing"}
E -->|Generation Slice| F["Token Sampler<br/>Sample Next Token / Update KV Cache"]
E -->|Embedding Slice| G["Incremental Pooler<br/>Accumulate Sum & Weights Across Chunks"]
G -->|Final Chunk| H["Normalized Output Vector"]
Key Designs¶
1. Chunked Embedding with Incremental Pooling: Breaking Monolithic Passes into Balanced Steps
Standard embedding inference processes an entire sequence in a single forward execution. When an embedding input contains hundreds or thousands of tokens, executing it atomically monopolizes the GPU's compute cores, forcing concurrent single-token decode requests to wait and introducing noticeable latency spikes. To balance compute loads, ORTHRUS adapts incremental computation principles into chunked embedding. Given an input sequence of \(n\) tokens, the system splits it into \(K\) chunks of sizes \(c_1, c_2, \dots, c_K\) such that \(\sum_{k=1}^K c_k = n\), where each chunk size is bounded by a maximum chunk budget \(C\). In each scheduling iteration \(k\), the runner processes only the \(k\)-th chunk to produce hidden states \(H^{(k)} \in \mathbb{R}^{c_k \times d}\).
To eliminate the need to buffer hidden states across iterations, the incremental pooler maintains streaming accumulator states. For standard mean pooling and weighted-mean pooling (with token weights \(w_{k,j}\)), the pooler tracks an \(O(d)\) running sum \(S^{(k)}\) and weight total \(W^{(k)}\) across chunks:
initialized with \(S^{(0)} = 0\) and \(W^{(0)} = 0\). Upon completing the final chunk \(K\), the pooler outputs the final normalized embedding vector \(S^{(K)} / W^{(K)}\). Positional heads like CLS pooling retain only the initial vector \(H^{(1)}_1\), whereas last-token pooling retains the final token \(H^{(K)}_{c_K}\). Incremental pooling is algebraically equivalent to single-pass full pooling (up to negligible floating-point reduction-order variations), but grants the scheduler fine-grained flexibility to interleave embedding and generation without GPU stalls.
2. Contiguous Memory Tensor Layout: Zero-Copy Dispatched Execution
When mixing multiple heterogeneous request types within a single forward pass, interspersing them randomly within the batch tensor would require expensive gather operations, memory copies, or scattered kernel launches during output processing. To prevent kernel launch overhead and memory bus saturation, the ORTHRUS scheduler enforces that all requests within a batch are sorted and packed contiguously by type: in-flight decodes, prompt prefills, and embedding chunks each occupy adjacent tensor slices. Following the unified forward pass, downstream output operators (such as the sampler and the incremental pooler) directly execute on contiguous slices of the hidden state tensor, avoiding intermediate data staging entirely.
3. Intra-Batch Scheduling (IBS): Token-Workload-Aware Proportional Allocation
Iterative retrieval pipelines only finish when both the embedding and generation stages are completely satisfied; thus, static scheduling heuristics (such as hardcoded 1:2 request ratios) degrade whenever decode lengths vary dynamically, and basic First-Come-First-Served (FCFS) policies allow long-running generation decodes to starve short embedding queries. ORTHRUS introduces Intra-Batch Scheduling (IBS), satisfying three key operational requirements: proportional allocation, per-type FCFS, and the elimination of head-of-line blocking.
IBS operates in two phases. First, it unconditionally reserves capacity for in-flight generation requests currently in their autoregressive decode phase, leveraging vLLM's PagedAttention memory manager to avoid expensive KV cache swapping. Second, for the remaining token budget \(B\), the scheduler measures backlogs not by raw request counts, but by the aggregate sum of remaining tokens in each queue: \(w_e = \sum_{r \in Q_e} \text{tokens}(r)\) and \(w_g = \sum_{r \in Q_g} \text{tokens}(r)\). Persistent credit accumulators \(a_e\) and \(a_g\) track scheduling priority across iterations:
When a queue empties, its accumulator resets to zero. By incrementing accumulators by instantaneous token weights and decrementing by total outstanding work, the ratio of admitted embedding to generation tokens dynamically converges to \(w_e : w_g\), preventing starved queues and ensuring that lightweight embedding requests are never blocked behind prolonged generation loops.
Loss & Training¶
ORTHRUS is an inference-serving system architecture and requires no model retraining or parameter fine-tuning. It operates seamlessly over pre-trained weights and existing LoRA adapters (e.g., Mistral-7B unified with an e5-mistral-7b-instruct adapter for embeddings, or single unified retrieval-generation architectures). For deployments serving separate backbone models (e.g., OPT-1.3B for generation and GTR-T5-XL for embeddings), ORTHRUS supports unified queue scheduling and shared memory pooling within a single GPU instance.
Key Experimental Results¶
Main Results¶
Evaluations were conducted on a cluster of up to four NVIDIA A100-40GB GPUs using Mistral-7B combined with the e5-mistral-7b-instruct LoRA adapter. Workloads included controlled synthetic stress tests (128-token embeddings, 128-token prompt prefill with 512-token decodes) and the realistic iterative RAG benchmark Iter-RetGen evaluated on 2WikiMultihopQA (prompts averaging 500 tokens, decodes averaging 3000 tokens, and 1โ10 retrieved documents per query iteration).
Baselines included: - Dedicated: Task-specific GPU partitioning (e.g., Dedicated1:3 designates 1 GPU for embedding and 3 for generation); - Disagg-PD: Phase-specific disaggregation separating prefill and decode across GPU pools; - Unified-Homo: Single-GPU co-location with homogeneous batching (pure embedding or pure generation iterations); - Unified-Hetero: Single-GPU co-location with heterogeneous batching using naive FCFS scheduling; - ORTHRUS: Single-GPU heterogeneous batching governed by IBS.
The table below summarizes end-to-end request throughput (req/s) on Iter-RetGen across GPU counts:
| Method | 1 GPU (Embed / Gen) | 2 GPUs (Embed / Gen) | 4 GPUs (Embed / Gen) | 4-GPU Total Throughput Gain (vs. Dedicated) |
|---|---|---|---|---|
| Dedicated | N/A / N/A | 0.080 / 0.110 | 0.119 / 0.141 | Baseline (0.260 req/s) |
| Unified-Homo | 0.067 / 0.080 | 0.126 / 0.148 | 0.252 / 0.296 | +110.8% (0.548 req/s) |
| Disagg-PD | N/A / N/A | 0.118 / 0.140 | 0.276 / 0.327 | +131.9% (0.603 req/s) |
| ORTHRUS (Ours) | 0.075 / 0.088 | 0.142 / 0.166 | 0.288 / 0.336 | +140.0% (0.624 req/s) |
On 4 GPUs, ORTHRUS achieved an aggregate throughput of 0.624 req/sโa 2.40ร improvement over the Dedicated baseline (0.260 req/s)โwhile uniquely providing full serving capability on single-GPU configurations where static disaggregation is infeasible.
Ablation Study¶
To evaluate the packing efficiency of chunked embedding and assess whether incremental pooling introduces numerical divergence, the authors conducted two targeted ablations:
Table 1: Token Budget Packing Simulation (Token Budget \(B=256\), Max Chunk Size \(C=64\), 80% Gen / 20% Embed Workload)
| Configuration | Token Budget Fill (%) | Generation Throughput (req/s) | Embedding Throughput (req/s) | Total Throughput (req/s) | Note |
|---|---|---|---|---|---|
| Atomic Embedding (No Chunking) | 8.8% | 93.3 | 25.5 | 118.8 | Requests must fit atomically, leaving residual budgets idle |
| Chunked Embedding | 85.7% | 93.3 | 26.9 | 120.2 | Recovers unused token slots without degrading generation |
Table 2: Incremental Pooling Numerical Equivalence (Comparing Chunked vs. Single-Pass Embeddings across 250 Sequences)
| Pooling Head | Chunk Size \(C\) | Cosine Sim. Min | Cosine Sim. Mean | Relative L2 Error Mean | Relative L2 Error p99 |
|---|---|---|---|---|---|
| Mean Pooling | 256 | 0.9999512 | 0.9999844 | 0.005527 | 0.008995 |
| Mean Pooling | 512 | 0.9999555 | 0.9999861 | 0.005176 | 0.009478 |
| Mean Pooling | 1024 | 0.9999484 | 0.9999877 | 0.004820 | 0.008156 |
| CLS Pooling | 512 | 0.9999837 | 0.9999887 | 0.004908 | 0.005479 |
| Weighted Mean | 512 | 0.9999339 | 0.9999887 | 0.004493 | 0.009927 |
Key Findings¶
- Higher Throughput & Lower Tail Latency: On synthetic workloads, ORTHRUS delivers 1.28รโ4.52ร higher throughput than static GPU partitioning. On the 4-GPU Iter-RetGen RAG benchmark, ORTHRUS reduces end-to-end p99 latency by 55.8% compared to Dedicated (593.4s vs. 1342.0s).
- Elimination of Head-of-Line Blocking: Under a simulated worst-case burst (1,000 generations followed by 1,000 embeddings submitted simultaneously), ORTHRUS achieves 9% lower p99 generation latency and 16% lower p99 embedding latency. Furthermore, when generation decode lengths expand from 256 to 4,096 tokens (an 11ร surge in generation p99), embedding p99 latency varies by less than 7ms, demonstrating robust latency isolation.
- Sustained High GPU Utilization: Across three shifting workload phases (10%, 50%, and 90% embedding ratios), Dedicated1:3 yields an average GPU utilization of only 38%, whereas ORTHRUS maintains 79% utilization, finishing each phase 43% faster.
- Strict Algorithmic Fidelity: Incremental pooling achieves minimum cosine similarity exceeding 0.9999 and relative L2 errors below 1% across all heads, confirming that differences stem entirely from non-associative floating-point summation order rather than algorithmic drift.
Highlights & Insights¶
- Synergistic Co-Scheduling across Opposing Hardware Bottlenecks: By interleaving compute-bound embedding chunks with memory-bound autoregressive decoding passes within the exact same Transformer kernel execution, ORTHRUS saturates both compute units and memory bandwidth simultaneously.
- Incremental State Aggregation for Embeddings: While chunked prefill is well-established for generation prompts, applying streaming accumulators to embedding pooling heads removes the traditional requirement for atomic sequence execution in representation models.
- Token-Count-Aware Proportional Credit System: Arbitrating queues by remaining token work rather than raw request counts provides a principled, lightweight mechanism that guarantees proportional progress and starves neither short queries nor long decodes.
Limitations & Future Work¶
- Lack of Multi-GPU Model Sharding (TP/PP): ORTHRUS currently deploys one complete model replica per GPU (data parallelism). Scaling to models exceeding single-GPU memory requires integrating tensor or pipeline parallelism, where cross-GPU synchronization barriers could alter heterogeneous batch packing dynamics.
- Evaluated Model Scale: Experiments focus on open-weight models under 10 billion parameters (Mistral-7B, Qwen2-7B, LLaMA-3.1-8B). Larger models exhibit different compute-to-memory ratios and tighter KV cache budgets, requiring further scaling validation.
- Multi-Adapter Scheduling Complexity: In settings requiring diverse, concurrent LoRA adapters across both embedding and generation streams, adapter switching overhead within heterogeneous batches warrants further investigation.
Related Work & Insights¶
- vs vLLM / Orca / Sarathi-Serve: State-of-the-art LLM serving systems focus exclusively on autoregressive generation, executing embedding requests as isolated, atomic prefill passes; ORTHRUS bridges both workloads into a unified execution loop.
- vs DistServe / Mooncake (Prefill-Decode Disaggregation): Disaggregating prefill and decode across physically distinct GPU pools incurs significant network transfer overhead for KV caches in iterative loops; ORTHRUS proves that fine-grained single-GPU heterogeneous batching is superior for iterative RAG workloads.
- vs SLoRA / Punica: Multi-tenant LoRA serving systems optimize adapter swapping exclusively for generation tasks; ORTHRUS extends shared-backbone scheduling across fundamentally distinct NLP task paradigms.
Rating¶
- Novelty: โญโญโญโญโญ First system to break the physical isolation between embedding and generation serving via unified heterogeneous batching and incremental pooling.
- Experimental Thoroughness: โญโญโญโญโญ Extensive controlled ratio sweeps, real-world multi-hop iterative RAG benchmarks, multi-model/adapter rank generalizability tests, and rigorous numerical precision audits.
- Writing Quality: โญโญโญโญโญ Exceptionally clear framing of architectural bottlenecks, crisp formulation of streaming pooling, and lucid experimental validation.
- Value: โญโญโญโญโญ Critical engineering and algorithmic milestone for high-throughput, low-latency iterative RAG and LLM agent infrastructure.