Parrot: Efficient Serving of LLM based Applications with Semantic Variable

Source

Title: Parrot: Efficient Serving of LLM-based Applications with Semantic Variable
arXiv: https://arxiv.org/abs/2405.19888
HTML v1: https://arxiv.org/html/2405.19888v1
PDF v1: https://arxiv.org/pdf/2405.19888v1
TeX Source v1: https://arxiv.org/e-print/2405.19888v1
DOI: https://doi.org/10.48550/arXiv.2405.19888
Venue: OSDI 2024, pages 929-945
USENIX: https://www.usenix.org/conference/osdi24/presentation/lin-chaofan
Microsoft Research: https://www.microsoft.com/en-us/research/publication/parrot-efficient-serving-of-llm-based-applications-with-semantic-variable/
Code/Project: https://github.com/microsoft/ParrotServe
Authors: Chaofan Lin, Zhenhua Han, Chengruidong Zhang, Yuqing Yang, Fan Yang, Chen Chen, Lili Qiu
Submitted: 2024-05-30
Current version read: arXiv v1, submitted Thu, 30 May 2024 09:46:36 UTC
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
Comments: To appear on USENIX OSDI 2024

作者与关系

Chaofan Lin: Shanghai Jiao Tong University.
Zhenhua Han: Microsoft Research.
Chengruidong Zhang: Microsoft Research。
Yuqing Yang: Microsoft Research.
Fan Yang: Microsoft Research。
Chen Chen: Shanghai Jiao Tong University.
Lili Qiu: Microsoft Research。

阅读目标与判断边界

本笔记关注：

Semantic Variable 这个抽象解决了哪些 request-centric serving 看不到的信息。
Parrot 如何把 workflow 信息转成可执行的 scheduling、communication 和 shared-prefix optimization。
实验中每类 workload 的收益来自哪一层机制。
它和已存档 LLM systems、agent tool-use、RLHF/RLVR infrastructure 论文的关系。

判断边界：

论文是 OSDI 2024 systems paper，关注 serving throughput / latency / memory，不讨论模型能力、alignment 或 reward learning。
Parrot 的收益依赖应用愿意暴露 prompt structure、semantic variables 和 performance criteria；传统黑盒 API 场景无法直接获得全部收益。
GitHub 仓库说明当前是 research prototype 且不活跃维护，生产落地仍需重新评估安全、隔离、兼容性和运维复杂度。
实验基于 LLaMA 7B/13B、A100/A6000、FastChat/vLLM/HuggingFace baseline，结论需要结合 2026 年 serving engine 演进重新校准。

论文脉络

1. 问题背景

LLM 应用经常由多次模型调用组成：长文档总结会分块 map-reduce 或 chain；搜索/办公 Copilot 会先理解意图、检索、校验，再生成回答；多 agent 编程会让 architect、coder、reviewer 多轮协作。现有 public LLM service 的抽象通常是单个 completion API：

\mathrm{Completion}(\mathrm{prompt}:\mathrm{str}) \rightarrow \mathrm{generated\_text}:\mathrm{str}.

这个 API 把复杂应用压平成孤立请求。服务端看不到哪些请求属于同一个应用、谁依赖谁、哪段 prompt 是 system prompt、哪段是中间变量、哪个输出是用户真正等待的最终结果。于是服务端只能优化单请求延迟，难以优化端到端应用 latency 或 cluster throughput。

论文指出三个系统问题：

Consecutive requests 的输出经客户端回传再发给服务端，引入网络和重新排队开销。生产测量中，LLM API latency 有 $30\%\sim50\%$ 平均来自 LLM engine 外部，最坏超过 $70\%$ 。
请求级调度目标和应用级目标错位。map-reduce summary 中，map 阶段更适合大 batch 提高吞吐，reduce 阶段更适合低 latency；统一按单请求 latency 调度会降低端到端性能。
prompt 存在大量共享前缀。生产 chat search 中超过 $94\%$ tokens 在不同用户请求中重复；MetaGPT 和 AutoGen 中重复段落分别约 $72\%$ 和 $99\%$ 。服务端缺少 prompt structure 时，很难在 cluster 层快速检测并共置这些共享前缀请求。

2. 核心假设或切入点

Parrot 的判断是：很多 LLM serving 低效来自应用级结构在 API 边界处丢失。只要把 prompt 中的变量结构、请求依赖和性能目标以轻量方式暴露给服务端，传统系统里的数据流分析、DAG scheduling、prefix sharing 和 locality-aware placement 就可以进入 LLM application serving。

因此，论文提出 Semantic Variable。它是 prompt 里的输入/输出变量区域，例如 task、code、test。当一个请求的输出变量被另一个请求用作输入变量时，服务端可以恢复请求之间的数据流。

3. 方法 / 系统 / 理论框架

Parrot 把 LLM request 视为 semantic function：自然语言实现的函数，由 LLM 执行。开发者在 prompt template 中标注 Semantic Variables：

@P.SemanticFunction
def WritePythonCode(task: P.SemanticVariable):
    """Write python code of {{input:task}}.
    Code: {{output:code}}"""

@P.SemanticFunction
def WriteTestCode(task: P.SemanticVariable, code: P.SemanticVariable):
    """Write test code for {{input:task}}.
    Code: {{input:code}}.
    Your test code: {{output:test}}"""

前端把 semantic function 降到 OpenAI-like API 扩展：

{
  "prompt": "str",
  "placeholders": [
    {
      "name": "str",
      "in_out": "bool",
      "semantic_var_id": "str",
      "transforms": "str"
    }
  ],
  "session_id": "str"
}

Parrot Manager 维护每个 session 的 request / semantic variable DAG。它使用两类分析原语：

DAG-based analysis：通过 GetProducer、GetConsumers、GetPerfObj 找到变量生产者、消费者和最终输出的性能目标。
Prompt structure-based analysis：通过 PrefixHash 在 Semantic Variable 切分点生成 hash，用于快速发现共享 prefix。

基于这些信息，Parrot 做四类优化：

Serving dependent requests：服务端在 DAG ready 时连续执行依赖请求，中间变量通过服务端 message queue 传递，减少客户端往返和重新排队。
Performance objective deduction：从最终 output variable 的 latency / throughput 目标反推请求级 scheduling preference。并行 map task group 可以被标成 throughput-oriented，即便最终用户目标是低端到端 latency。
Sharing prompt prefix：在 Semantic Variable 边界计算 prefix hash，快速找到相同 system prompt、few-shot examples 或动态生成上下文；通过 context fork 共享 KV cache。
Application-centric scheduling：按 topological order、task group、shared prefix 和性能目标调度请求，尽量把相似目标或共享 prefix 的请求放到同一 engine。

实现上，Parrot 包括 Python front-end、central manager 和基于 vLLM/xFormers/自研 kernel 的 LLM engine，总计约 14K 行代码。engine 抽象出三类上下文 API：

def Fill(token_ids: List[int], context_id: int, parent_context_id: int)
def Generate(sampling_configs: Dict, context_id: int, parent_context_id: int)
def FreeContext(context_id)

Fill 负责 prefill / KV cache 写入，Generate 负责自回归 decoding，parent_context_id 支持 context fork。论文还实现了结合 PagedAttention 和 FlashAttention 思路的 shared-prefix decoding kernel，避免每个分叉请求重复从 HBM / L2 / shared memory 加载同一 prefix KV。

4. 结论链条

论文的因果链条是：

LLM 应用天然有 multi-request workflow、变量传递、性能目标和 prompt commonality。
单请求 completion API 丢失这些结构，让 serving backend 只能做局部调度。
Semantic Variable 用较小 API 扩展恢复应用级结构。
服务端用 DAG 和 prompt structure 分析，可以把中间变量传递、任务组调度和 prefix sharing 放到 backend 执行。
端到端应用 latency、cluster throughput 和 KV memory 使用都得到改善；在多 agent 编程和 GPTs-style shared prompt workload 中收益尤其大。

关键实验/定理

结果 1：长文档 chain summary 减少客户端往返和重新排队

设置：Arxiv-March 长文档，单文档超过 20K tokens；chain summary；一张 A100 80GB 运行 LLaMA 13B；baseline 为 LangChain + FastChat + vLLM/HuggingFace。
指标：平均端到端 latency。
结果：单文档 chain summary 相比 vLLM baseline 最高 $1.38\times$ 加速，相比 HuggingFace 最高 $1.88\times$ 加速；加入 background requests 后，相比 vLLM 最高 $2.38\times$ 加速；多 chain-summary 应用并发时平均端到端 latency 降低 $1.68\times$ 。
解读：收益主要来自服务端连续执行依赖请求，减少网络往返、客户端中转和后继请求重新排队。输出越短，这类固定开销越占主导，收益越明显。

结果 2：map-reduce summary 通过 performance objective deduction 优化 task group

设置：Arxiv-March 长文档 map-reduce summary；map 阶段包含大量并行请求，reduce 阶段较少。
指标：平均端到端 latency。
结果：论文报告 Parrot 在 map-reduce document summarization 中相对 baseline 取得约 $2.37\times$ 加速；motivation 中的调度分析也显示应用级目标可带来约 $2.4\times$ 端到端 latency 改善。
解读：关键在于 map 阶段的目标是尽快完成整个 task group。请求级 latency 最优会限制 batch capacity；应用级调度允许 map 阶段用更大 batch 提高吞吐，reduce 阶段再偏 latency。

设置：Bing Copilot final request，系统 prompt 约 6000 tokens，合成 64 个用户请求；另有四类 GPTs 应用在 4 张 A6000 GPU 上模拟多租户服务。
指标：request latency、per-output-token latency、可承载 request rate。
结果：Bing Copilot 相比无共享 prompt baseline 在 batch size 8/16 下 $1.8\times\sim2.4\times$ 加速；相比静态 prefix 共享的 vLLM paged attention baseline 仍有 $1.1\times\sim1.7\times$ 加速，batch size 32 时达到 $1.58\times$ 和 $1.84\times$ 。多 GPTs workload 中，Parrot 可承载比无共享 baseline 高 $12\times$ 的 request rate；关闭 affinity scheduling 后只剩约 $3\times$ 。
解读：收益来自两层：scheduler 将同一应用或共享 prefix 请求共置到同一 engine；kernel 对共享 prefix KV 做更高效的 attention 读取，减少重复内存事务。

结果 4：MetaGPT-style multi-agent programming 受益最大

设置：MetaGPT 派生的三角色编程工作流：Architect 设计文件/API，多个 Coders 编写文件，多个 Reviewers 评论并触发多轮 revise；一张 A100 运行 LLaMA 13B。
指标：端到端 latency、KV cache memory。
结果：相比 latency-centric baseline，Parrot 最高 $11.7\times$ 加速；相比 throughput-centric baseline 最高 $2.45\times$ 加速；prompt structure analysis 带来约 $2.35\times$ 加速，shared-prefix kernel 在 16 files 时额外约 $1.2\times$ 。
解读：multi-agent workflow 同时具备并行 task groups、动态生成上下文复用和多轮依赖。静态 prefix sharing 覆盖不足，Semantic Variable 让服务端能识别运行时生成的可共享上下文。

结果 5：混合 chat 与 map-reduce workload 中应用感知调度缓解目标冲突

设置：4 张 A6000 GPU，每张一个 LLaMA 7B engine；混合低 latency chat 请求和高吞吐 map-reduce requests。
指标：chat normalized latency、chat token generation speed、map-reduce speedup。
结果：Parrot 相比 latency-focused baseline 和 throughput-focused baseline，chat normalized latency 分别提升 $5.5\times$ 和 $1.23\times$ ；chat token generation speed 相比 throughput-focused baseline 提升 $1.72\times$ ；map-reduce 相比 latency-focused baseline $3.7\times$ 加速，相比 throughput-focused baseline $1.05\times$ 。
解读：单一全局调度目标会让 latency 和 throughput workload 互相干扰。Parrot 按应用目标分组与隔离，把 low-latency chat 和 throughput-oriented map-reduce 放到更合适的 engine 组合。

证据链强度评估

强证据

论文对四类 workload 给出分层评测，覆盖 dependency、task group scheduling、static/dynamic shared prefix 和 mixed workload interference。
Parrot 与 vLLM/HuggingFace/FastChat 类 baseline 对比，说明收益来自 request abstraction 和 backend scheduling 的组合，单个 kernel 只解释其中一部分。
GitHub 已开源 ParrotServe，包含前端、manager、CUDA kernel、docs 和 benchmark 目录，增强了系统可检查性。

中等强度证据

生产 workload 统计提供了 94% shared prompt、30%-70% engine 外开销等动机证据，但完整生产环境细节受限。
GPT-4 记录输出长度、LLaMA 生成等长文本用于系统评测，适合衡量 serving 性能，但不能衡量真实应用质量。
shared-prefix kernel 对 vLLM paged attention 有额外收益，但 2026 年 serving engines 已内置更成熟 prefix caching / chunked prefill，需要重新跑现代 baseline。

需要谨慎的推论

Parrot 的 API 改造需要应用开发者配合标注 Semantic Variables；对完全黑盒第三方 API 或自由格式 prompt 很难直接部署。
动态 control flow、function calling 和 native tools 在论文中被有意限制在客户端执行，公共服务端执行用户代码会带来安全风险。
多租户服务中暴露 prompt structure 与 session DAG 也会产生隐私、隔离和 side-channel 问题，论文主要从效率角度讨论。

OpenReview / 审稿意见吸收

Venue status: 当前档案未记录公开 peer-review 状态。
Public reviews: 当前档案未记录可可靠匹配的 OpenReview / ARR / 会议 reviewer comments。
Ratings / confidence: 无公开评分可用于校准。
Reviewer consensus: 暂无。
Main criticisms: 暂无公开 reviewer 质疑可引用；可信度主要由论文、技术报告、项目证据和本地一致性检查决定。
Author response: 暂无公开 rebuttal 记录。
对本文可信度的影响: 按未完成公开审稿吸收处理，结论需要依赖实验设置、baseline 强度、复现证据和跨论文一致性校准。

本地讨论补充

1. 讨论收敛点

本文在本地档案中的定位是 “application-aware LLM serving”。它强调 LLM 应用的有效 workload 单位经常是 DAG / session / workflow，单个 request 只是其中的执行片段。
Semantic Variable 是一个很强的系统接口设计：它保留了 prompt template 的变量边界，让 serving backend 能看见依赖和共享结构，同时保持接近 OpenAI-style API 的调用形态。

2. 修正后的理解

Parrot 的核心不只在共享 KV cache。它首先恢复应用级数据流，再由数据流驱动通信、调度和 prefix sharing。KV/prefix kernel 是后端优化的一部分，抽象层面的贡献更基础。
与 agent/RL 论文连接时，应区分 inference serving 和 training rollout。Parrot 能降低 agentic workflow serving 成本，但它没有处理 reward、policy update 或 tool-use RL 的训练问题。

3. 关于 Tensor Parallelism 的判断

论文没有跑真正的 tensor parallelism / TP 实验。evaluation setup 明确写到每个 LLM engine 使用一张 GPU 运行 LLaMA 13B 或 LLaMA 7B；multi-GPU setup 是四张 A6000，每张卡承载一个独立 LLM engine，形成四个 engine 的 cluster。
文中提到 “LLM Engine 可以由 GPU server 或一组 servers 构成”，说明抽象层允许把一个 engine 实现成 TP group；但实验没有设置 tensor_parallel_size > 1、没有报告跨 GPU collective / NCCL 开销，也没有做 TP degree ablation。
文中唯一直接触及 TP 的位置，是说明更长上下文如 32K 或 1M tokens 若要保持满意延迟，可能需要 tensor-parallel、sequence-parallel 或近似 attention；作者随后把这部分明确划到本文范围之外。
因此，Parrot 的 “parallel” 主要指三类并行：应用 DAG 中的 parallel task group、engine 内 continuous batching、多 engine cluster scheduling。它的实验结论主要证明 application-aware scheduling 和 shared-prefix reuse 对单 GPU engine 集群有效，尚未证明在 TP engine 上的收益形态。
若要把 Parrot 放到 TP serving 中复验，需要额外记录：context fork 的 KV cache 如何按 TP shard 共享、shared-prefix kernel 是否能跨 shard 保持收益、TP all-reduce / all-gather 是否吞掉应用级调度收益，以及 scheduler 的最小调度单位是单 GPU engine 还是 TP group。

4. 后续复验指标

对现代 vLLM/SGLang baseline：比较 prefix caching、chunked prefill、continuous batching、PD disaggregation、speculative decoding 下的收益。
对应用集成成本：统计需要标注的 Semantic Variables 数量、prompt 模板改造量、错误解析率、DAG 构建开销。
对多租户安全：记录 session isolation、prefix sharing side-channel、transform function sandbox、native code offload 风险。
对 agent workflows：测试 tool calling、retrieval、function calling 和 conditional branches 下的 DAG 动态变化与 scheduler 稳定性。

主要启发

LLM serving 的抽象层会决定 backend 看得见什么。completion API 只暴露 prompt 字符串，Semantic Variable 暴露应用的数据流边界。
对复杂 LLM 应用，端到端 latency 的最优调度可能要求某些中间阶段牺牲单请求 latency，用更大 batch 提高 task group completion speed。
prefix caching 需要 cluster scheduler 配合。engine 支持 KV 复用还不够，请求被随机分散到不同 engine 时共享机会会丢失。
Agent serving 的系统瓶颈往往来自 workflow structure：多角色、多轮、共享上下文、短输出、动态依赖共同决定实际成本。
未来 agent 平台如果希望稳定扩展，API 层需要表达 DAG、变量、工具输出和性能目标，而不只是转发自然语言 prompt。

局限

Parrot 需要应用开发者采用 Semantic Variable / SemanticFunction 或适配现有 orchestration framework，迁移成本和生态兼容性需要单独评估。
论文限制 public service 端执行 native functions，以降低恶意注入风险；这让 dynamic applications、function calling、branching control flow 的云端优化仍留给后续工作。
ParrotServe 仓库说明当前是 research prototype 且不活跃维护，生产系统中的可靠性、可观测性、权限隔离和 SLA 还需工程化。
实验 baseline 使用 OSDI 2024 时期的 FastChat/vLLM/HuggingFace；现代 vLLM、SGLang、TensorRT-LLM、prefix cache 和 disaggregated serving 可能缩小部分收益。
评测重心是系统性能，输出质量、应用正确性、agent failure recovery 和用户体验没有作为核心指标。
多租户 prefix sharing 可能引入隐私和 side-channel 风险；论文主要讨论 prompt structure 带来的效率收益。

跨论文关系

与 Grape：Grape 接续 Parrot 的 Semantic Variable 与 application DAG，将每次调用进一步拆成 static prefill、dynamic prefill 和 decode 微任务；上游 decode token 可以通过 partial edge 驱动下游增量 prefill。Parrot 提供 workflow 语义入口，Grape 展示了向 engine 内部 lowering 后的跨 task overlap。
与 2409.19256：两者都把上层 dataflow 显式交给系统。HybridFlow 面向 RLHF/RLVR training dataflow 和多模型协同；Parrot 面向 inference-time LLM application DAG 和多请求服务。
与 2606.00135：tool-calling RL 论文强调 harness、tool schema 和多轮历史会改变有效训练信号；Parrot 说明这些 workflow 结构也会改变 serving 成本和调度机会。后续真实 tool-use agent 系统需要同时设计训练 harness 与 serving API。
与 2510.20270：ImpossibleBench 的 coding agent 依赖工具反馈和测试循环；Parrot 的 Semantic Variable / DAG 视角可用于服务这类 multi-step coding workflow，并提供记录依赖、工具输出和最终结果的系统边界。
与 2606.04101：UltraEP 使用 runtime exact load 做 MoE expert balancing；Parrot 使用 runtime exact application structure 做 request scheduling。两者都说明真实系统负载信号比静态假设更适合指导调度。
与 2025-09-10：Parrot 的应用感知 batching、context fork 和 shared-prefix scheduling 可能改变实际推理 batch 形态；若用于评测或 RL rollout，需要额外关注 batch-invariant determinism。
与 2605.14220：TIM/VeXact 关注 rollout engine 与 trainer engine 的 logprob mismatch；Parrot 关注应用级 serving 调度。若 Parrot 式 workflow serving 被用于 agent rollout collection，必须记录 serving backend 与 trainer backend 的一致性。
与 2605.30290：STV 的 verifier-guided refinement / V-R loop 由多个模型调用组成，Parrot 的 Semantic Variable 可以表达 reasoner output、verifier feedback 和 refinement input 的数据流，服务端可据此做共置和共享。
与 2503.11926：CoT monitoring 和 agentic coding RL 都依赖长 trajectory 与多工具/多请求上下文。Parrot 提供系统层结构化 workflow 表达，可能帮助记录 monitor 所需的完整依赖链，但它本身不解决 monitor Goodhart 问题。

Reference Intake Brief

Target

Intended target system: 新增论文笔记；更新索引行和 LLM application serving / systems 关系章节。
Existing related assets: papers-index.md；2409.19256；2606.00135；2606.04101。
Proposed form: 新建独立 Markdown 文档；更新索引行、对应论文的关系章节和站点标签。

Reusable Elements

Semantic Variable 抽象：prompt 中的输入/输出变量边界，可同时表达数据依赖和 prompt structure。
Application-centric scheduling：从最终输出的 performance criteria 推导请求级目标，将 parallel task group 按端到端目标调度。
Shared-prefix serving：通过 prefix hash、context fork 和 shared-prefix attention kernel 组合完成 cluster-level + engine-level 复用。
Agent workflow serving checklist：DAG、变量、工具输出、性能目标、prefix sharing、session isolation。

Risks

Copyright/over-copying: 只记录摘要式分析、公式/接口形态和关键实验数值，未复制长段原文。
Unsourced or unverifiable claims: 版本、作者、OSDI 页码、代码仓库来自 arXiv、USENIX、Microsoft Research 和 GitHub；生产 workload 细节按论文公开内容记录。
Tone/brand mismatch: 中文表达遵循本目录说明，保留系统论文分析语气。
Safety/compliance issues: 本文是系统效率论文。涉及 function calling / native code offload 的安全风险时，只记录边界和防护动机。
Overlap with existing assets: 与 HybridFlow、Tool-calling RL 有主题交叉；本文新增价值是 application-level serving abstraction。

Skipped

Material	Reason
完整 API 文档和安装教程	GitHub 仓库已有文档，本笔记只保留论文分析所需接口。
所有图中曲线逐点读数	论文图表较多，本笔记保留正文报告的关键倍数。
CUDA kernel 逐行实现	当前重点是系统抽象和评测结论，kernel 细节可按需单独展开。
Microsoft 中文博客细节	已使用 arXiv、USENIX、Microsoft Research publication page 和 GitHub 作为主要来源。

Recommendation

Decision: merge

Why: Parrot 补齐本地档案中 LLM application serving 的关键系统节点。它和 HybridFlow、Tool-calling RL、TIM/VeXact 共同说明：LLM 系统效率越来越依赖上层 workflow structure、backend scheduling 和执行引擎之间的接口设计。

Source #

作者与关系 #

阅读目标与判断边界 #

论文脉络 #

1. 问题背景 #

2. 核心假设或切入点 #

3. 方法 / 系统 / 理论框架 #

4. 结论链条 #

关键实验/定理 #

结果 1：长文档 chain summary 减少客户端往返和重新排队 #

结果 2：map-reduce summary 通过 performance objective deduction 优化 task group #

结果 3：Bing Copilot / GPTs-style shared prompt workload 中 prefix sharing 提升吞吐 #

结果 4：MetaGPT-style multi-agent programming 受益最大 #

结果 5：混合 chat 与 map-reduce workload 中应用感知调度缓解目标冲突 #

证据链强度评估 #

强证据 #

中等强度证据 #

需要谨慎的推论 #

OpenReview / 审稿意见吸收 #

本地讨论补充 #

1. 讨论收敛点 #

2. 修正后的理解 #

3. 关于 Tensor Parallelism 的判断 #

4. 后续复验指标 #

主要启发 #

局限 #

跨论文关系 #

Reference Intake Brief #

Target #

Reusable Elements #

Risks #

Skipped #

Recommendation #