Research map / Large language models / Language, safety and interpretability
PARALLELPROMPT: Extracting Parallelism from Large Language Model Queries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces PARALLELPROMPT, a benchmark of ~37k real LLM-log prompts annotated with decomposition schemas, and an execution suite showing serial-vs-parallel latency and quality tradeoffs.
Problem
LLM serving treats user prompts as monolithic, missing latent intra-query semantic parallelism that could reduce latency; existing decomposition methods assume synthetic or predefined structures.
Approach
Extract structured schemas (template, shared context, data list or count, category) from real user prompts in chat logs using LLM-assisted extraction with rule-based validation, then execute serial vs parallel to measure latency and fidelity.
Key results
- Parallel execution yields raw speedups of 1.36x (keyword extraction), 2.94x (reading comprehension), and 2.50x (repeated generation); normalized speedup up to 5.72x.
- About 10.3% of 358,000 inspected prompts (37,070) validated as parallelizable.
- Reading comprehension keeps about 92% quality under parallelization while creative generation drops to about 76%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Execute Keyword Extraction subtasks in parallel rather than serially | PARALLELPROMPT · Keyword Extraction | normalized speedup: 2.54× normalized speedup | Helped |
| Execute Reading Comprehension subtasks in parallel rather than serially | PARALLELPROMPT · Reading Comprehension | normalized speedup: 5.72× normalized speedup | Helped |
| Execute Repeated Generation subtasks in parallel rather than serially | PARALLELPROMPT · Repeated Generation | normalized speedup: 4.39× normalized speedup | Helped |
| Include schema extraction overhead when parallelizing Repeated Generation | PARALLELPROMPT · Repeated Generation (E2E) | normalized speedup: 3.41× normalized speedup | Helped |
| Execute independent questions in parallel | PARALLELPROMPT · Reading Comprehension | quality preservation: 92% quality preservation | Helped |
| Execute extraction subtasks in parallel | PARALLELPROMPT · Keyword Extraction and Named Entity Recognition | quality preservation: 82-85% preservation | Hurt |
| Execute creative generation subtasks in parallel | PARALLELPROMPT · Creative generation tasks | quality preservation: 76% preservation | Hurt |
Surprising findings
- Prior decomposition methods (ToP, SoT) fail on many real-world prompts.
- Dependency blindness affects roughly 25% of structurally valid prompts.
Limitations
- Dependency blindness leads to false positives where parallel execution degrades output.
- Lower validation and extraction success for East Asian languages and creative tasks.
- Data sourced from early adopters, possibly not representative of broader users.
Experimental setup
Datasets: LMSYS-Chat-1M WildChat-1M
Benchmarks: ParallelPrompt
Metrics: latency normalized speedup raw speedup semantic fidelity structural adherence
Baselines: Skeleton-of-Thought Tree-of-Problems serial execution
Builds on: Skeleton-of-Thought Tree-of-Problems LLMCompiler
Closest papers by meaning
- Hogwild! Inference: Parallel LLM Generation via Concurrent Attention (NeurIPS 2025 · similarity 0.89)
- On the Worst Prompt Performance of Large Language Models (NeurIPS 2024 · similarity 0.89)
- Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation (ICLR 2024 · similarity 0.88)
- MixEval: Deriving Wisdom of the Crowd from LLM Benchmark Mixtures (NeurIPS 2024 · similarity 0.88)
- Preble: Efficient Distributed Prompt Scheduling for LLM Serving (ICLR 2025 · similarity 0.87)
- TokenPowerBench: Benchmarking the Power Consumption of LLM Inference (AAAI 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.