Skip to main content
Back to timeline
arXivSource publication:

One long document, hundreds of questions: Parallel Prompting decodes them as parallel streams for a 3.7x speedup on SGLang

Synopsis

When tens to hundreds of questions are asked about the same long document, prefix caching removes only the repeated prefill; every decode step still re-reads the document's key-value cache once per question, so decoding is bound by memory bandwidth. Parallel Prompting packs those questions into a single request and decodes them as independent streams, reading the shared document once per step, with a stream-id mask evaluated inside the attention kernel so each answer sees only the document and its own question. On CodeLlama-7B with 8k–16k-token documents and 64–256 questions per document, it is 3.7x faster than stock SGLang with the FlashInfer backend on an A100 and 5.9–6.0x faster on an RTX A6000, winning all 144 paired runs.

AI-generated editorial illustration: Read Once, Answer Many: Parallel Prompting for Shared-Context LLM Inference

Interpretation

Many independent questions about one long document can now be decoded in parallel at once, instead of each question running its own decode loop. Prefix caching had already made the document prefill happen once, but every decode step of every question still re-read the whole document's key-value cache, a cost that grows linearly with the number of questions. With CodeLlama-7B, 8k and 16k documents and 64, 128 or 256 questions per document, it is 3.7x faster than stock SGLang's FlashInfer backend on an A100 and 5.9–6.0x faster on an RTX A6000, faster in all 144 paired runs.

The method places all questions in one request and generates them simultaneously as independent streams, appending one token per stream at each step. Each stream carries a stream id, and the attention kernel lets a token attend only to the document and to earlier tokens of its own stream, so each answer is conditioned exactly as if its question were decoded alone, unlike batch prompting where answers interfere. The implementation adds about 80 lines to three existing SGLang files plus a small engine package; the mask comes from two fixed-size index tensors with no dense tensor, so every decode step is captured as a CUDA graph; on the QuALITY and LooGLE long-document benchmarks, accuracy and recall stay within 0.33 and 0.36 points of the other configurations.

Perspective

The demonstrated scope is batch and offline workloads where the requests sharing a document are known in advance; the implementation covers one attention backend, a single GPU and greedy decoding. On CodeLlama-7B with 8k–16k documents and 64–256 questions per document, it is 3.7x faster than the FlashInfer backend on an A100 and 5.9–6.0x faster on an A6000.

The gain varies with workload: it falls from 3.6 to 1.9 as answers lengthen, it is 5–7% slower than stock FlashInfer for Qwen2.5-1.5B with 64 questions where the per-token key-value cache is small, and on LooGLE, whose answers average 234 tokens, it is 1.26x slower than FlashInfer. Online serving of requests as they arrive needs scheduler integration, which the authors leave to future work; the changed floating-point order means outputs are not bitwise identical to standard decoding.