Batch Query Processing and Optimization for Agentic Workflows (Halo) — L2 #

1. TL;DR #

Halo treats a batch of same-template agentic workflows as one consolidated query-plan DAG, then solves query optimization + scheduling as a single GPU-worker-placement problem (beam search over a prefill/decode + cache-reuse cost model). Runtime adds adaptive batching, prefix-cache sharing, and on-the-fly context exchange. Up to 18.6× batch speedup, 4.7× online throughput, no quality loss.

2. 痛点 / 方法 / 结果 (Q1 / Q2 / Q3) #

Q1 — 痛点 (task scope). The task class is closed-ish batch analytics: thousands of related, template-structured agentic workflows (e.g. "investigate revenue for each of 100 stocks / SKUs / markets") issued at once. Interaction is multi-turn (multi-operator DAGs, self-loops) but the workload is offline batch (plus an online mini-batch mode); autonomy is a fixed, user- or planner-specified workflow graph, not open-ended browsing. The pain: existing LLM serving engines (vLLM, SGLang) optimize each call in isolation with no visibility into cross-call structure; multi-agent frameworks (LangGraph, AutoGen, AgentScope) orchestrate but defer performance to the serving layer; KV-reuse layers (LMCache, CacheGen) need a higher-level optimizer to decide what/when/where to cache. The result is massive redundancy — repeated prompts, overlapping contexts, concurrent duplicate work — and poor GPU utilization.

Q2 — 方法. View each workflow as a DAG of operators (one LLM invocation each); for $n$ batched queries sharing structure $G$, build a consolidated DAG that exposes shared computation. Then jointly formulate optimization + scheduling as a multi-GPU worker-placement problem: assign contiguous operator subsets to workers to minimize makespan (slowest-worker latency), scored by a cost model that discounts inference for KV-cache reuse, model-weight reuse, retrieval reuse, and data-parallel replication. A beam-search solver (Algorithm 1) approximates the NP-hard placement. The runtime (server-worker, pull-based) then executes with phase-aware adaptive batching, shared prefix cache, and a context-exchange layer that lets the backend (vLLM / Transformers) swap per operator.

核心技术壁垒: the single hardest-to-replicate insight is collapsing query optimization into worker placement over a consolidated batch DAG, driven by an empirically-profiled prefill/decode + reuse cost model — deliberately avoiding rule-based rewrites or a Volcano-style optimizer. The reuse discount coefficients ($\gamma_v,\sigma_v,\lambda_v,\beta$) are profiled offline, and the beam search stays tractable only because the branching factor is $m! $ with $m=|D|$ (number of GPUs, small). Getting near-optimal placement (optimality 1.00 vs 0.20–0.40 for RR/CoLoc/DP) out of a cheap heuristic is the crux.

Q3 — 结果. Across six workflows (W1–W6, on 2× H100 NVL): batch inference 2.0–18.6× over Transformers, 1.1–2.1× over vLLM/LMCache, up to 5.4×/5.5× over LangGraph/AgentScope. Online mini-batch throughput improves 1.2–4.7× over vLLM (up to 26.8 q/s). Scales to 20K queries, 100 operators, 16 GPUs, 1B–70B models. Output quality preserved (perplexity 10.01 vs 10.57 for LMCache).

3. 架构 / 方法图 #

Halo uses a classic declarative-systems architecture: Query Parser → Query Optimizer → Query Processor, over a CPU-resident server that dispatches jobs to GPU workers.

Paper's Figure 3, verbatim (caption: "Overview of Halo that efficiently processes batch agentic LLM workflows."). The parser turns each query into a DAG and builds one consolidated plan across the batch; the optimizer produces a resource-aware placement; the processor executes it with the serving optimizations. This is the "bring database query processing into agentic serving" thesis made concrete.

The motivating workload is an agentic revenue-investigation: a lead planner fans out to searcher / analyzer / connector / editor agents over partially overlapping contexts, replicated across markets and time frames.

Paper's Figure 1, verbatim (caption: "An example agentic workflow in which multiple LLM agents collaborate to analyze revenue data and provide decision support for businesses."). Notice the repeated retrieval-and-summarize calls over the same product-line pages — exactly the redundancy Halo's consolidated DAG and prefix cache target.

At scale these workflows become modular / collaborative / adaptive, with thousands of agents (Table 1 lists up to 10,000).

Paper's Figure 2, verbatim (caption: "Complex agentic workflows involve modular, collaborative, and adaptive processes."). This motivates why per-call optimization is insufficient: structural complexity and feedback loops demand plan-level coordination.

The agent loop / one turn (per-operator execution and its fallbacks):

Planning & reasoning. Planning style is a predetermined workflow graph (not ReAct / ToT); the "reasoning" is the optimizer's beam search over placements, not the agents' chain-of-thought. Decomposition is top-down: the user or planner LLM specifies $G$; Halo topologically sorts it and assigns operator subsets to workers, finishing a subset on all queries before moving on ("these operators will not be revisited" — no backtracking on placement). Budget is expressed as fixed GPU resources $|D|$ and the makespan objective. External tool/API calls are assumed to have fixed, known latency so the scheduler can slot them deterministically.

Memory model. Short-term = the context window / KV cache of an operator; the shared prefix cache holds precomputed hidden states for reused prefixes (system prompts, RAG contexts, few-shot exemplars); intermediate model state (cache snapshots) migrates between GPUs via NVLink or offloads to host DRAM under scheduler control. There is no persistent episodic trajectory store — this is a serving system, not an autonomous long-horizon agent.

4. 作者证明 #

This paper has 无形式化作者证明 — 仅实证 for the end-to-end system claims (speedups, quality). What it could have bounded — a competitive/approximation ratio for the beam-search placement vs the optimal makespan — is left empirical (measured "optimality" score instead). However, the paper does carry a formal complexity derivation for the solver (Appendix), so I run the 6 checks against that plus the cost/latency model.

Notation table:

方程物理意义:

• Objective: $$f^{*}=\arg\min_{f}T_{wc}(G,f), \quad T_{wc}(G,f)=\max_{d\in D}\sum_{\ell\in\ell^{d}}T(v_{\ell})$$ Find the operator→worker placement minimizing the makespan; the batch finishes when the slowest worker does.
• Assigned-cost per worker: $$C_{a}^{d}(f)=\sum_{v\in V_{f_{d}}}\gamma_{v}/k^{\beta}\cdot e_{v}+\sigma_{v}\cdot\lambda_{v}\cdot p_{v}$$ Inference cost discounted by parallelism decay $1/k^\beta$ and KV reuse $\gamma_v$, plus preparation cost discounted by model-weight reuse $\sigma_v$ and retrieval reuse $\lambda_v$.
• Remaining lower bound (admissible heuristic): $$C_{r}(f)=\frac{1}{m^{\beta}}\cdot\sum_{v\in Re(f)}e_{v}$$ Optimistic estimate assuming unassigned work is perfectly balanced across all $m$ workers; total beam score $Cost(f)=C_a(f)+C_r(f)$ is A*-flavored.
• Solver complexity: $$O\!\big(R\,w\,m!(\tau+\log w)\big), \quad R\in[\lceil k/m\rceil,\,k]$$ Factorial in $m$ (bijections of $m$ operators to $m$ workers per beam element) but tractable because $m=|D|$ is small.

6 minimum checks:

1. Dimensional/units — $C_a^d, C_r, Cost$ are all latencies (sum of $e_v,p_v$ scaled by dimensionless factors $\gamma,\sigma,\lambda,1/k^\beta,1/m^\beta$). Consistent: score has units of time, comparable to $T_{wc}$. ✔
2. Boundary — no reuse — set $\gamma_v=\sigma_v=\lambda_v=1$, $k=1$: $C_a^d=\sum(e_v+p_v)$, i.e. plain sequential per-worker latency. Recovers the naive cost. ✔
3. Boundary — single worker ($m=1$, $|D|=1$): only one $\ell^d$, $T_{wc}=\sum_v T(v)$ (full serial); ablation confirms disabling parallelism degrades W2 latency 62%. ✔
4. Monotonicity — reuse discounts — since $\gamma_v,\sigma_v,\lambda_v<1$ when reused, placing consecutive same-model operators on one worker strictly lowers $C_a^d$, matching the "assign consecutive operators to same worker" strategy. ✔
5. Admissibility of $C_r$ — the $1/m^\beta$ perfect-balance term is a lower bound on remaining work (real placement can't beat perfectly balanced load), so $Cost$ never overestimates the true optimal completion — beam pruning keeps promising branches. ✔ (heuristic, not proven admissible for $\beta\neq 1$; noted.)
6. Complexity self-consistency (Appendix) — main case ($r_t\ge m$): top-$m$ selection $O(r_t\log m)$ + $m!$ bijections × $w$ beam × $(\tau+\log w)$ scoring/selection per round × $R$ rounds ⇒ $O(R\,w\,m!(\tau+\log w))$. Padding case ($r_t

   Failure-mode note (agent-specific): the paper's implicit failure classes are placement suboptimality (addressed by beam search, measured via the optimality score) and serving inefficiency (idle GPU, redundant prefill — addressed by adaptive batching + prefix cache). The dominant lever by ablation is data parallelism (62%), then query optimization (60%). Halo is targeted squarely at the redundancy/placement class, not at task-success or reasoning-quality failures (those are held fixed by the exact-answer constraint).

   5. 实验与数据 #

   Batch inference (G1). Six workflows W1–W6 (multi-step retrieval, adversarial reasoning, multi-agent voting, multi-turn), up to 2,000 queries, 2× H100 NVL.

   

   Paper's batch-inference results figure (caption: "Comparison of the system performance across six workflows with different batch sizes."). Halo(t) beats Transformers 2.0–18.6×; Halo(v) beats vLLM/LMCache 1.1–2.1×; up to 5.4×/5.5× over LangGraph/AgentScope. The reader should notice Halo(t) sometimes beats vLLM-based baselines — surprising, and attributed to efficient context exchange rather than memory management.

   Online serving (G2). Poisson arrivals, input rate swept $[0.1, 100]$ q/s, mini-batch buffering; metric = max sustained throughput.

   

   Paper's online-serving figure (caption: "System throughput at different input query rates over six different agentic workflows."). Halo(v) reaches 0.15–26.8 q/s (1.2–4.7× over vLLM); Halo(t) 0.07–1.2 q/s (1.4–4.2× over Transformers). Note the ~180× workflow-dependent variance (W1 26.8 vs W5 0.15) — throughput is dominated by generation length, not the optimizer.

   Scalability (G4). Batch size 2K→20K, operator count →100, iterations 1/5/10/20, worker count →16.

   

   Paper's scalability figure (caption: "Scaling experiment on batch size (a), operator count (b) number of iteration (c) and worker count (d) for Halo vs LMCache."). Halo maintains $<0.5×$ LMCache latency across the batch-size range and scales nearly linearly to 16 GPUs, whereas LMCache's default tensor parallelism plateaus (or regresses on consumer 5090s). Multi-turn gains grow ~4×→7× as rounds increase (Halo leverages NVLink).

   Ablation & optimality (G3). On W2, each disabled component costs latency; a separate study measures placement optimality vs RR/CoLoc/DP.

   Config	Avg Latency	Loss
   Halo(t) - Full	80.37	–
   w/o Data Parallelism	130.29	62%
   w/o Query Optimization	128.35	60%
   w/o Cache Reuse	121.61	51%
   w/o Adaptive Batching	106.68	33%
   w/o Query Ordering	84.66	5%

   Paper's Table 3 (ablation). Data parallelism and query optimization are the load-bearing components; query ordering is nearly free offline (5%) but worth up to 34% online — a notable offline/online gap. (Text says cache-reuse 50%, table says 51% — minor internal inconsistency.)

   Method	Optimality	Lat@50	Lat@250	Lat@1000	Lat@2000
   Halo	1.00	76.24	126.34	305.39	552.32
   RR	0.20	83.34	163.32	459.25	888.52
   CoLoc	0.40	81.76	144.14	448.73	872.97
   DP	0.30	97.05	139.68	319.36	577.18

   Paper's Table 4 (optimality & latency). Halo hits optimality 1.00 across query sizes vs 0.20–0.40 for the heuristics. But notice: raw data parallelism (DP) closes to within ~4% at 2000 queries (577.18 vs 552.32) despite a 0.30 optimality score — Halo's edge narrows at very large batches where replication dominates.

   Case study & GPU utilization (G1 qualitative).

   

   Paper's GPU-profile figure (caption: "GPU memory and utilization profiles over normalized execution time. Top: GPU memory usage comparison. Bottom: GPU compute usage comparison."). Memory-usage AUC 0.79 (Halo) vs 0.44 (Transformers) — ~2×; compute AUC 0.89 (Halo) vs 0.69 (LMCache). Adaptive batching keeps GPUs busy where the Transformers baseline over-reserves memory up front. In the W4 five-operator plan, Halo cuts init 127.1s→54.7s (44%, ops 3–4 drop ~22s→~0s via model reuse) and end-to-end 436.6s→328.8s (24.7%), while improving perplexity (10.01 vs 10.57).

   6. 论证链 #

   Step	Claim	Support (paper-internal)
   1	Batch agentic workflows contain heavy redundancy (repeated prompts, overlapping contexts, concurrent duplicates) that per-call serving cannot see.	§1–§2.1 running example (revenue investigation, TradingAgents ×100 symbols); prior-art gap table (vLLM/SGLang isolate calls, frameworks defer to serving).
   2	Redundancy is exploitable if the batch is expressed as one consolidated query-plan DAG of operators with reuse-aware costs.	§2.2 operator/DAG formalism ($v:[m(I,p,\phi)]_z\to O$, $G=(V,E)$); reuse rationale (shared prefixes, overlapping inputs).
   3	Optimization + scheduling can be collapsed into a single makespan-minimizing worker-placement problem rather than rule-based rewrites.	§3.1 $f^*=\arg\min T_{wc}$; NP-hardness → beam-search solver (Algorithm 1) inspired by JellyBean.
   4	A profiled cost model with KV/model/retrieval reuse discounts makes the beam search near-optimal.	§3.2 $C_a^d, C_r, Cost$; offline-profiled $\gamma,\sigma,\lambda,\beta$; Fig. 4 KV transfer ~1 order of magnitude faster than recompute.
   5	The placement is realized efficiently at runtime via adaptive batching, prefix cache, and swappable-backend context exchange.	§3.3 server-worker, phase-aware batching (ORCA/vLLM-inspired), shared prefix cache, on-the-fly context exchange.
   6	The full stack yields large empirical speedups without quality loss, and each component contributes measurably.	§4.2 (2.0–18.6×), §4.3 (1.2–4.7×), §4.4 ablation (62/60/51/33/5%) + optimality 1.00, §4.6 quality (PPL 10.01 vs 10.57).

   7. 实现 cross-reference #

   Artifact: https://github.com/mlsys-io/Halo_demo (demo repo referenced in the paper; full file:line mapping [实现未公开] in this note — the L1 source did not include repository line citations, and the paper labels the parser and several parts as prototype/orthogonal).

   Key implementation details (agent- & serving-specific tricks easy to miss):

   • Backend hot-swap via context exchange (核心技术壁垒 realized): the executor standardizes intermediate state (prompts + KV-cache tensors) at operator boundaries, so vLLM or Transformers can be swapped per operator or per step. This is what lets a single plan mix heterogeneous models (1B SLM → 70B decision model) on the same workers — the enabling mechanism behind cross-model KV/model reuse discounts. [实现未公开 — 具体接口层未给出行号]
   • 关键实现细节 #1 — length-aware offline ordering: in batch mode, tasks are sorted by total token length $L_{\text{prompt}}+L_{\text{response}}$ to form homogeneous batches, reducing stragglers. Easy to miss because it yields only ~5% offline but is a distinct code path from the SLO-priority online ordering (up to 34%).
   • 关键实现细节 #2 — asynchronous cache paging: background threads prefetch upcoming activation caches over PCIe/NVLink and evict stale ones under scheduler control, so GPU memory is "ready just in time" and GPUs stay compute-dedicated while CPUs handle logistics. This is the concrete source of the 2× memory-utilization AUC in Fig. 12.
   • Data-parallel activation condition: operator replication (data parallelism) fires only when $|V_r|<|D|$ and the operator is compute-heavy — a subtle guard that prevents wasteful model replication when there are enough ready operators to fill workers.