Using Span Queries to Optimize for Cache and Attention Locality

Source

Title: Using Span Queries to Optimize for Cache and Attention Locality
arXiv: https://arxiv.org/abs/2511.02749
HTML v1: https://arxiv.org/html/2511.02749v1
PDF v1: https://arxiv.org/pdf/2511.02749v1
TeX Source v1: https://arxiv.org/e-print/2511.02749v1
DOI: https://doi.org/10.48550/arXiv.2511.02749
Code/Project: 未在 arXiv 页面和 TeX source 中发现公开代码或项目链接
Authors: Paul Castro, Nick Mitchell, Nathan Ordonez, Thomas Parnell, Mudhakar Srivatsa, Antoni Viros i Martin
Submitted: 2025-11-04
Current version read: arXiv v1, submitted Tue, 4 Nov 2025 17:22:49 UTC
Subjects: Artificial Intelligence (cs.AI)
Comments: 12 pages, 17 figures
Venue status: TeX source 使用 mlsys2025 accepted style；arXiv metadata 未写正式 venue，后续若有 camera-ready 或 conference 页面需要复核。

作者与关系

Paul Castro: IBM Research, New York, USA。
Nick Mitchell: IBM Research, New York, USA.
Nathan Ordonez: IBM Research, Zurich, Switzerland。
Thomas Parnell: IBM Research, Zurich, Switzerland。
Mudhakar Srivatsa: IBM Research, New York, USA。
Antoni Viros i Martin: IBM Research, Massachusetts, USA。

阅读目标与判断边界

本笔记关注：

Span Query 这个 IR 如何把 non-chat LLM workload 暴露给 serving backend。
commutativity constraints 如何同时支撑 KV cache locality 和 attention locality。
作者对 vLLM 的改动、CIDRA 重定位算法和实验收益分别说明了什么。
它和 Parrot、HybridFlow、tool-use RL 等已存档论文的系统关系。

判断边界：

本文是 LLM serving / runtime 系统论文，核心指标是 TTFT、prefill load、cache locality 和 attention locality；它不研究 RL objective、model alignment 或 reward learning。
结果主要来自 microbenchmark 和小规模 synthetic / public QA workload；对真实多租户 RAG、agentic coding、long-horizon tool-use 和 production traffic 的外部有效性需要后续复验。
Span Query 的正确性依赖应用能准确声明哪些内容可交换。若把顺序敏感的上下文错误标成 commutative，服务端优化会改变语义。
实现依赖特殊 token、block alignment、partial trailing block 处理和 vLLM 内部 patch；迁移到现代 vLLM/SGLang/TensorRT-LLM 需要重新评估兼容性与维护成本。

论文脉络

1. 问题背景

现有 inference server 以 chat completion 为主要优化对象。chat 的 token 历史具有 append-only prefix pattern：上一轮 history 会原样作为下一轮 prompt 前缀，因此 vLLM 这类系统可以用 prefix matching 复用 KV cache。

RAG、judge-generator、deep research 和 agentic workflow 的复用形态更复杂：

RAG 中，同一 fragment 可能在不同 query 中出现，但排序和相邻 fragment 会改变。传统 prefix cache 只看从开头连续匹配的 block，因此一个可复用 fragment 换了位置就会 miss。
nested generation 中，inner generate 的输出会被 outer judge / reducer 使用，但 outer prompt 的 system instruction 和上下文通常不同。KV cache 里已经有 inner output 对应的 token block，prefix hash 仍无法复用。
inference-time scaling 常把多个生成、评分、筛选步骤拼成调用图，复用单位经常从整个 prompt prefix 转为中间 span。

作者把问题归结为一个系统接口缺失：服务端不知道哪些输入片段的顺序对语义有影响。chat 中历史顺序通常敏感；RAG fragments、多个候选答案、一些 judge 输入常常可以交换。这个差异正是 KV cache 与 attention 优化的关键。

2. 核心假设或切入点

Span Query 的核心切入点是：LLM workload 可以被表示为一个 side-effect-free 的表达式树，树节点是 message span、generate call 和 join operator。join operator 显式表达子树之间的顺序约束：

Q = \mathrm{tree}(\mathbf C,\mathbf R,\mathbf F,\mathbf +,\mathbf{\Join},\mathbf S,\mathbf A,\mathbf U,\mathbf G).

其中：

$\mathbf C$ 表示 chat completion。
$\mathbf R$ 表示 corpus retrieval。
$\mathbf F$ 表示 corpus fragment。
$\mathbf S,\mathbf U,\mathbf A$ 分别表示 system、user、assistant messages。
$\mathbf G$ 表示 generate new tokens。
$\mathbf{\Join}$ 表示 non-commutative join，输入顺序需要保留。
$\mathbf +$ 表示 commutative join，子输入可以重排。

这个 IR 的含义类似 SQL 之于数据库：客户端声明逻辑结构和约束，runtime 决定如何重排、tokenize、prefill、cache、reposition 和 schedule。

3. Query semantics: parallel fork + constrained join

Span Query 是 declarative expression tree，执行子树没有 side effects，因此每个 node 的 child subtrees 可以并行执行。执行结果仍是一个 span query，具备 closure property。

关键语义在 join：

$\mathbf{\Join}$ ：顺序敏感，适合 chat history、system/user/assistant 连续对话、链式推理上下文。
$\mathbf +$ ：顺序不敏感，适合 RAG fragments、候选答案集合、某些 judge-generator fan-out。

直觉上， $\mathbf +$ 给 runtime 一个强约束：这些 children 的相对顺序不承载语义。因此 runtime 可以重排它们来提高 KV cache 命中，也可以把一个大 judge 操作改写成 tree reduction 来改善 lost-in-the-middle。

4. High-level optimizer

作者把 KV locality optimization 拆成高层表达式树改写和低层 token sequence 改写。高层 optimizer 在 tree 上迭代应用规则直到收敛。

主要规则包括：

$\mathbf C$ desugaring：把 chat completion 降到 $\mathbf G$ 加 explicit non-commutative join，即 $\mathbf G(\mathbf{\Join}(\mathbf S,\mathbf A,\mathbf U))$ 。
$\mathbf R$ desugaring：把 retrieval 降到 retrieved fragments 上的 $\mathbf +$ ，并插入 prepare generate（ $\mathbf G^1$ ，max_tokens=1）让 fragment 可以独立进入 cache。
plus simplification：把嵌套 commutative joins 合并，减少无用层级。
plus distribution：把 $\mathbf +$ 分配进 $\mathbf G$ ，解决 nested generation 的 dual output paradox。

dual output paradox 的含义是：模型 server cache 的 generated output 实际上依赖生成它的 input prefix。若 outer query 只把 generated output 当成普通 assistant message 使用，它在新 prefix 下并不匹配原 KV block。plus distribution 提前把 input 和 output 组织成 future-reusable 的结构，让后续复用时仍符合 server 的 cache dependency。

5. Query tokenization 与 low-level optimizer

vLLM 内部消费的是 token sequence，因此作者把 Span Query 序列化成带 parenthesization 的 token stream。特殊 token 表示：

padding token：用于 block alignment。
start token：表示 independent subtree 开始。
sibling boundary token：表示独立 sibling 分界。
end token：表示 independent subtree 结束，并附带 subtree 起点位置或长度信息。

作者选择特殊 token overloading 以减少 vLLM 改动。这个选择有明确代价：全新 special tokens 需要模型 fine-tuning；复用现有 token 会让模型输入包含训练时语义不同的符号，可能伤害准确率。

低层 optimizer 处理两件事：

block alignment：用 padding 让特殊 token 落在 vLLM block 边界上。这样 scheduler 只需检查每个 block 的第一个 token，就能知道 hash accumulation 是否需要暂停或恢复。
trailing partial blocks：vLLM 通常不缓存最后一个未填满 block。nested generation 中，如果 inner generate 的最后几个 token落在 partial block，outer query 复用会 miss。作者当前方案会裁剪某些 inner output 的尾部 token 来保持 cache locality，这是一项重要准确率风险。

6. vLLM patch 与 CIDRA

作者声称仅改动或新增 vLLM 492 行 Python，涉及 scheduler、KV cache manager、block pool 和 GPU model runner：

vLLM file	LoC
`core/block_pool.py`	68
`core/kv_cache_manager.py`	89
`core/kv_cache_utils.py`	73
`core/sched/output.py`	4
`core/sched/scheduler.py`	19
`core/single_type_kv_cache_manager.py`	4
`worker/gpu_model_runner.py`	232
Total	492

Scheduler 层的核心改动是 block hash accumulation：普通 prefix cache 会让 block hash 依赖前序 block hash；Span Query 遇到 span start token 时暂停累计 hash，遇到 span end token 时恢复。这样，commutative span 内部 block 可以脱离原 prompt prefix 被命中。

GPU runner 层要处理 positional encoding。缓存 KV block 若被放到新位置使用，其 RoPE position 已不匹配。作者采用 ReRoPE，即反转旧 RoPE，再施加新 RoPE。为了支持多请求并发复用重叠 KV block，作者提出 CIDRA（Concurrent In-place Duplicating ReROPE Algorithm）：

把 block repositioning 请求表示成 dependency graph，例如 block A 移到 B、B 移到 C。
若某个 node out-degree 大于 1，说明多个并发请求要把同一源 block 移到不同目标位置，CIDRA 复制该 block，直到图变成 strict permutation graph。
对图做 strongly connected components analysis，找出 cycles 和 independent subgraphs。
用 bin packing 把可并行 subgraphs 分批在 GPU 上执行；罕见大 cycle 回退到 CPU。
对小 batch 通过 concatenating layers 提高 tensor operation 吞吐。

论文报告 CIDRA repositioning throughput 最高约 500 tokens/ms。这个数字支撑了一个关键系统判断：只有 KV repositioning 足够快，span-level cache reuse 才能抵消额外调度和重定位开销。

7. Attention locality: 从 cache 优化扩展到 lost-in-the-middle

Span Query 的另一个贡献是 attention locality。作者观察到 commutative join 不只允许 cache 重排，也允许把一个大输入集合改写成 tree reduction。

例如一个 8-way judge-generator 可以先分成 4 个 2-way judge，再分成 2 个 2-way judge，最后做 1 个 2-way judge。每一步 judge 只看少量 candidate，避免重要信息被埋在长输入中间。

这类优化无需修改 model server，因为它通过多次普通 model calls 重组 prompt 结构。代价是调用次数增加，收益是每次调用的 attention burden 降低。作者在 needle-in-haystack microbenchmark 中用 random names 作为 needles、random content 作为 hay，比较 granite3.3 2B 和 8B；结果显示 attention-optimized 2B query 在更长 hay 下优于 stock 8B unoptimized query。

关键实验/定理

结果 1：RAG microbenchmark 中 Span Query 显著降低 TTFT

设置：documents 为随机内容，每个 2857 tokens，接近 vLLM Python source file 平均长度；document 数从 1 到 32；每个设置重复 10 次。比较 stock vLLM、Span Query cache miss、Span Query cache hit。
指标：TTFT。
结果：摘要和 introduction 报告两类 non-chat use cases 上可达到 10-20x TTFT 降低；cache miss 时由于 sparse attention 也能降低 prefill load，introduction 中报告约 3x。
解读：stock vLLM 对所有 documents 做 full prefix prefill，随 document 数增长有较高二次项；Span Query cache miss 时每个 document 内部 attention 仍是二次，但跨 document attention 被稀疏化，常数更低；cache hit 时跳过大量 prefill，只支付 repositioning，增长更接近线性。

结果 2：Nested generation 中收益随 inner fan-out 和 temperature 增大

设置：judge-generator span query，执行 100 次，改变 inner generate temperature；比较 fan-out 1 和 fan-out 24。另在 temperature 0.5 下改变 fan-out，每个 fan-out 执行 500 次。
指标：median TTFT、p50-p99 speedup、CIDRA repositioning overhead。
结果：inner temperature 为 0 时收益接近 0，因为 stock vLLM 对确定性 inner output 也能获得 prefix cache；temperature 非零后收益取决于 fan-out。fan-out 1 时 TTFT 降低约 7%-32%；fan-out 24 时 TTFT 约 12-13x faster。temperature 0.5 的 fan-out sweep 中，speedup 到 p99 前较稳定，p99 之后稳定性下降。
解读：Span Query 对 nested generation 最有价值的场景是 candidate 多、输出不完全相同、outer judge 需要重用多个 inner outputs。小 fan-out 或确定性 output 下，普通 prefix cache 已覆盖一部分复用机会。

结果 3：Bulk Span Query execution 可以利用 temporal locality

设置：实现 greedy heuristic，把 bulk request 中引用相同 fragments 的 queries 聚在时间上执行。数据集为 2Wiki 和 NaturalQuestions，每个 fragment 约 100 tokens，属于较短 RAG 场景。
指标：相对 stock vLLM 的平均 TTFT speedup。
结果：

Bulk size	2Wiki	NaturalQuestions
1	1.21x	1.03x
1024	1.31x	1.05x
whole corpus	1.59x	1.13x

解读：短 fragment 下收益有限，符合 RAG microbenchmark 的左端区域；bulk API 让 scheduler 增加 temporal locality，是对单 query Span Query 的补充。

结果 4：Attention-optimized tree reduction 缓解 lost-in-the-middle

设置：needle-in-haystack microbenchmark；inner generate 产生随机 names 和 random hay，judge 负责抽取 names；1000 runs；vary hay length；模型为 granite3.3 2B 和 8B。
指标：good attention locality 的 run fraction，论文图中定义与 name extraction precision threshold 相关。
结果：unoptimized query 随 hay 增长出现明显退化；attention-optimized $k=2$ tree reduction 能承受更多 hay；optimized 2B 超过 unoptimized 8B。
解读：这组结果说明 Span Query 的收益不只来自系统 cache。表达式树结构本身可以作为推理分解策略，改变模型看到的局部上下文分布，从而改善准确率。

证据链强度评估

强证据

论文把问题、IR、语义、optimizer、tokenization、vLLM patch、ReRoPE/CIDRA 和实验串成一条完整系统链条，贡献边界清晰。
RAG 和 nested generation 分别覆盖 corpus fragment reuse 与 generated output reuse，证明 Span Query 超过单一 RAG hard-code 场景。
vLLM 改动行数和文件分布具体，说明方案有较小侵入性；CIDRA 解释了并发重定位下的 race / overlap 问题。

中等强度证据

10-20x TTFT 是强收益，但主要来自构造明确的 microbenchmark，真实 RAG fragment 长度、retrieval overlap、cache capacity、request interleaving 和 workload mix 会改变收益。
Bulk execution 在 2Wiki / NQ 上收益较小，说明短 fragment 和低 overlap 场景中 Span Query 的额外结构并不一定带来大幅加速。
Attention locality 实验显示树形分解有潜力，但 needle-in-haystack 与真实 judge-generator / agent reasoning 仍有距离。

需要谨慎的推论

commutativity hint 的语义正确性由应用负责。RAG fragments 有时会存在引用顺序、叙事顺序、证据优先级或 recency 关系，简单标成 $\mathbf +$ 可能损害答案。
special token overloading、padding、block alignment 和 output cropping 都可能影响模型输出质量；论文没有给出足够广的真实任务 accuracy audit。
492 行 patch 表示原型改动较小，但维护 vLLM fork、适配 vLLM 内部 scheduler/GPU runner 更新、和其他 kernel/quantization/parallelism 功能兼容仍是工程问题。
ReRoPE 对 RoPE 模型自然适配；对不同 positional encoding、MLA、multi-query/grouped-query attention、TP/PP/EP serving 的泛化需要复验。

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 / structure-aware serving” 主题下。它和 Parrot 的共同点是上层应用必须把结构暴露给服务端；区别在于 Parrot 暴露变量和 DAG，Span Query 暴露 message spans、generate calls 和 commutativity。
Span Query 更基础的贡献是把 “order matters / order does not matter” 提升为 API 级约束。这个约束一旦进入 runtime，可以同时服务 cache locality、attention locality 和未来的 scheduler optimization。

2. 修正后的理解

传统 prefix cache 假设复用内容必须出现在相同 prefix path 上。Span Query 把可复用单位从 prefix 扩展到被括号标记的 span，再通过 hash accumulation 暂停/恢复和 ReRoPE 处理位置差异。
对 agentic workflow，这个思路尤其重要：agent 的中间报告、候选计划、检索证据、tool outputs 和 judge inputs 经常会在不同外层 prompt 中复用。若这些内容的顺序或依赖可声明，serving backend 可以减少大量重复 prefill。
对 RL rollout 或 evaluation harness，Span Query 型优化需要记录和控制 execution semantics。任何 prompt 重排、batch clustering、span reuse、partial output cropping 都可能改变可复现性和评测分布。

3. 详细讲解口径

面向系统读者介绍时，可以把本文讲成三层：第一层是应用接口，Span Query 让客户端声明调用图和顺序约束；第二层是 runtime 优化，服务端用这些约束做 query rewrite、span tokenization、block alignment、cache hash 改写和 ReRoPE；第三层是 workload 结果，在 RAG 和 judge-generator 中减少重复 prefill，在 lost-in-the-middle 中把大 judge 分解成更局部的 tree reduction。
这篇文章的核心变量是 commutativity。若两个片段交换顺序后语义保持稳定，runtime 就可以改变它们的位置来追求 cache locality 或 attention locality；若顺序承载语义，runtime 应保留 non-commutative join。
对比 Parrot 时，可以说 Parrot 的最小表达单元是 Semantic Variable / request DAG，Span Query 的最小表达单元是 message span / generate call / join constraint。前者更适合讲应用依赖和调度目标，后者更适合讲 KV cache 复用、span relocation 和 attention 结构。
评价这类系统时，需要同时看性能和语义：TTFT speedup 只说明服务端成本下降；commutativity hint 是否正确、特殊 token 是否影响输出、partial block cropping 是否丢信息、tree reduction 是否改变 judge 决策，也需要单独验证。

4. Call tree 重排与子调用的准确机制

需要区分两类 tree transformation。第 5.1 节的 cache-locality rewrite 在已有 expression tree 上执行 chat / retrieval desugaring、嵌套 $\mathbf +$ 展平和 plus distribution，目标是让 fragment 或 generated span 可以独立缓存、移动和复用。第 6 节的 attention-locality rewrite 会改变调用拓扑，把一个高 fan-out judge 改写成多层 reduction，并新增真实的 model calls。
Span Query 从客户端程序的 parse tree 开始。叶节点是 system / user / assistant message 或 corpus fragment， $\mathbf G$ 节点是一条 LLM 调用， $\mathbf +$ 与 $\mathbf{\Join}$ 分别表示可交换和保序的 child join。所有 subtree 都声明为 side-effect-free，因此互不依赖的 siblings 可以并行执行；父 $\mathbf G$ 等待 children 返回 assistant spans 后，再按 join 约束构造自己的 prompt。这就是论文所说的 parallel fork + semantically constrained join。
RAG 的 cache 路径会把 retrieval node 降解为多个 fragment 上的 $\mathbf G^1$ 子调用，其中 $\mathbf G^1$ 是 max_tokens=1 的 prepare generate。它的作用是让每个 fragment 脱离最终 query prefix 独立完成 prefill 并进入 KV cache；外层 generate 随后消费这些 span。nested generation 的 plus distribution 则提前把生成输入与输出组织成可复用 subtree，以满足 generated KV 对原输入 prefix 的依赖。
以 8 个候选 $c_1,\ldots,c_8$ 的 judge-generator 为例，定义一个二元 judge：

J(x,y)=\mathbf G\!\left(\mathbf S_J\ \mathbf{\Join}\ \mathbf U_J\ \mathbf{\Join}\ (x\ \mathbf +\ y)\right).

attention-locality optimizer 可以把一次 flat 8-way judge 改写为：

\begin{aligned} r_{12}&=J(c_1,c_2), & r_{34}&=J(c_3,c_4), & r_{56}&=J(c_5,c_6), & r_{78}&=J(c_7,c_8),\\ r_{14}&=J(r_{12},r_{34}), & r_{58}&=J(r_{56},r_{78}),\\ r_{18}&=J(r_{14},r_{58}). \end{aligned}

第一层 4 个 judge 可以并行，第二层 2 个 judge 可以并行，根节点最后执行。原来 1 个 outer judge 因而变为 3 个依赖轮次、共 7 个二元 judge 子调用；原有 8 个 candidate-generation calls 保持不变。每个 $r$ 都是普通 LLM 请求生成的 assistant span，随后作为父 judge 的输入。具体 reducer 输出可以是胜出候选或抽取后的关键信息，由 task prompt 决定。
子调用发生在 workflow / runtime 层，每个 $\mathbf G$ 都是一条独立推理请求；单次 model forward 不会在内部递归展开整棵树。attention-locality 版本因此可以运行在未修改的 model server 上。span-aware vLLM、block hash 暂停/恢复与 ReRoPE 主要服务跨位置 KV reuse。
论文把 $\mathbf +$ 的 commutativity 作为允许重排与 tree reduction 的核心 hint。严格语义还需要 reducer closure：中间 judge 输出必须保留上层继续判断所需的信息。LLM judge 通常缺少可证明的结合律与确定性，因此 4→2→1 改写属于会改变输出分布的 workflow optimization；Figure 17 的 synthetic name-extraction 实验提供经验支持，尚未证明它对任意 judge、agent decision 或 evidence aggregation 都保持语义。

5. 后续复验指标

真实 RAG：fragment length distribution、fragment overlap rate、retrieval order sensitivity、cache hit by span、TTFT / TPOT / throughput、answer accuracy。
Agent workflow：inner generate fan-out、candidate diversity、judge input length、shared intermediate reuse、tool output order sensitivity。
Runtime overhead：tokenization / optimizer time、padding overhead、CIDRA repositioning p50/p95/p99、cache capacity pressure、partial block crop rate。
Accuracy audit：special token overloading 的输出影响、cropping 对 final answer 的影响、tree reduction 对 judge consistency 的影响。
Backend compatibility：modern vLLM prefix caching、chunked prefill、continuous batching、TP/PP serving、MLA models、SGLang radix cache、TensorRT-LLM KV reuse。

主要启发

LLM serving 不能长期只用 completion string 作为接口。RAG、agent、test-time scaling 都有更丰富的结构，runtime 看见这些结构后才能做更强优化。
“可交换性”是一个很小但很有力的系统 hint。它既决定 cache block 能否跨位置复用，也决定 long context 能否被分解成更局部的 judge/reduce 过程。
Cache locality 和 attention locality 可以由同一个 IR 同时管理。前者降低系统成本，后者改善模型质量，两者都源于对输入结构的显式表达。
vLLM 这类生产级 server 的改动点可以很小，但高性能落地要求处理 hash dependency、block alignment、partial cache、positional encoding 和并发 race。
对未来 agent platform，合理的 serving API 可能需要同时表达 DAG、semantic variables、span boundaries、tool output types、commutativity 和 performance objectives。

局限

论文没有公开完整代码或 vLLM patch 链接，复现 492 行改动和 CIDRA 性能仍需等待 artifact。
commutativity constraints 需要应用正确声明；错误声明会改变 prompt 语义和输出分布。
特殊 token encoding 可能影响模型准确率；新 token 要 fine-tuning，复用 token 会引入语义污染。
trailing partial block 的当前处理会裁剪 inner generate output，可能损害 nested generation 正确性。
实验主要是 microbenchmark 和 synthetic lost-in-the-middle；真实 RAG、agent、code workflow、multi-tenant traffic 的收益范围需要复验。
attention locality 的 tree reduction 会增加 model calls，端到端成本需要同时统计 TTFT、TPOT、总 tokens、并发调度和准确率。
方案依赖 vLLM 内部 hash / KV cache / GPU runner 机制，后续 vLLM 版本、SGLang radix cache、MLA/TP serving 和 disaggregated prefill/decode 架构都可能改变实现路线。

跨论文关系

与 Grape：两者都把 prompt 内部结构交给 serving runtime。Span Query 用 expression tree 和 span algebra 优化 cache reuse、重排与 attention locality；Grape 用 InputVar / IntermediateVar 边界生成 static / dynamic 微任务和 streaming edge，重点优化相依 task 的 prefill / decode overlap 与 SLO 调度。
与 2405.19888：这是最强系统关系。Parrot 把 LLM application 表示成 Semantic Variable DAG，服务端据此做 dependent-request serving、performance objective deduction 和 shared-prefix scheduling；Span Query 把 LLM calls 表示成带 commutativity constraints 的 expression tree，服务端据此做 span-level cache reuse 和 attention-locality rewrite。两者共同说明：服务端优化能力取决于应用层结构暴露程度。
与 2409.19256：HybridFlow 将 RLHF/RLVR 的 actor、rollout、reference、reward、trainer dataflow 显式交给系统；Span Query 将 inference-time workflow 的 message spans 和 generation tree 显式交给 serving runtime。二者都是 “dataflow/IR drives scheduling” 的系统思路。
与 2606.00135：tool-calling RL 论文讨论 harness、tool schema、多轮历史和工具返回如何改变训练效率与表现；Span Query 提供一个可能的 serving-side 表达层，用于减少同类多轮 agent workflow 的重复 prefill 和长上下文 attention 负担。
与 2605.30290：STV 的 verifier-reasoner loop 和 verifier BoN / refinement 可以自然表示为 nested generation；Span Query 提供了对候选答案集合和 verifier 输入做 cache reuse / attention-locality optimization 的接口。
与 2512.07783：该论文讨论 test-time / process verification 和 RL 数据构造，Span Query 从 serving 角度降低 judge-generator、process verifier 和多候选评估的执行成本。两者在 inference-time scaling workflow 上相连。
与 2025-09-10 和 2605.14220：Span Query 的重排、padding、batch clustering、ReRoPE 和 partial block 处理会改变 runtime execution path。若用于 RL rollout、eval harness 或 reproducibility-sensitive serving，需要像这两篇材料强调的那样记录 batch-invariant determinism 和 rollout/trainer logprob consistency。

Reference Intake Brief

Target

Intended target system: 新增论文笔记 / LLM serving、KV cache locality、attention locality 专题文档。
Existing related assets: content/utility/papers-index.md；相关已存档论文包括 2405.19888、2409.19256、2606.00135。
Proposed form: 新建独立 Markdown 文档；更新当前收录和 LLM serving / Span Query 跨论文关系。

Reusable Elements

Span Query expression tree：用 $\mathbf +$ / $\mathbf{\Join}$ 表示 commutative 与 non-commutative joins。
prefix cache 到 span-level cache reuse 的问题定义。
high-level rewrite rules： $\mathbf C$ desugaring、 $\mathbf R$ desugaring、plus simplification、plus distribution。
vLLM patch 思路：block hash accumulation 暂停/恢复、block alignment、ReRoPE repositioning。
CIDRA：并发 KV block repositioning 的 graph / SCC / duplication / batching 算法。
attention locality：把 8-way judge 改成 tree reduction，缓解 lost-in-the-middle。

Risks

Copyright/over-copying: 本文档采用转述和少量事实数据摘录，避免长段复制论文原文。
Unsourced or unverifiable claims: 作者、提交时间、subjects 来自 arXiv abs；vLLM LoC、实验设置和结果来自 arXiv source。公开代码链接未发现，复现状态需要后续确认。
Tone/brand mismatch: 写作保持系统分析口径，区分作者主张、本地判断和待复验项。
Safety/compliance issues: 论文为 serving systems 研究，无直接攻击或滥用流程。
Overlap with existing assets: 与 Parrot / HybridFlow 关系明确，已在跨论文关系中区分各自抽象层级。

Skipped

Material	Reason
所有 17 个 figures 的逐图复述	本次沉淀保留结构、算法和关键结果，避免过长
TeX comments 中未进入正文的 TODO 和 speculative numbers	这些内容不作为论文正式主张
完整 CIDRA pseudocode	arXiv source 未包含正式 appendix pseudocode，本次只保留算法机制
全量 bibliography	本地档案只需在关系章节保留关键相关工作

Recommendation

Decision: merge as a new paper note.

Why: 该论文把 LLM serving 的优化接口从 prefix cache 推进到可声明结构的 Span Query，和本目录已有 Parrot、HybridFlow、tool-calling RL 形成清晰系统脉络，值得后续跟踪代码、artifact 和真实 agent workload 复验。

Source #

作者与关系 #

阅读目标与判断边界 #

论文脉络 #

1. 问题背景 #

2. 核心假设或切入点 #

3. Query semantics: parallel fork + constrained join #

4. High-level optimizer #

5. Query tokenization 与 low-level optimizer #

6. vLLM patch 与 CIDRA #

7. Attention locality: 从 cache 优化扩展到 lost-in-the-middle #

关键实验/定理 #

结果 1：RAG microbenchmark 中 Span Query 显著降低 TTFT #

结果 2：Nested generation 中收益随 inner fan-out 和 temperature 增大 #

结果 3：Bulk Span Query execution 可以利用 temporal locality #

结果 4：Attention-optimized tree reduction 缓解 lost-in-the-middle #

证据链强度评估 #

强证据 #

中等强度证据 #

需要谨慎的推论 #

OpenReview / 审稿意见吸收 #

本地讨论补充 #

1. 讨论收敛点 #

2. 修正后的理解 #

3. 详细讲解口径 #

4. Call tree 重排与子调用的准确机制 #

5. 后续复验指标 #

主要启发 #

局限 #

跨论文关系 #

Reference Intake Brief #

Target #

Reusable Elements #

Risks #

Skipped #

Recommendation #