Research map / Large language models / Retrieval and knowledge

Superposition Prompting: Improving and Accelerating Retrieval-Augmented Generation

ICML 2024 · Large language models › Retrieval and knowledge · approach: Long-context and personalized retrieval · 1 citations (OpenAlex)

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.

Proposes superposition prompting, a training-free RAG prompting scheme that processes documents as parallel prompt paths in a DAG, prunes irrelevant paths via a Bayesian saliency score, and caches/parallelizes computation to cut latency while improving accuracy.

Problem

LLM-based retrieval-augmented generation is expensive because inference cost grows quadratically with long concatenated contexts, and irrelevant retrieved documents ("distraction") degrade answer quality.

Approach

Represent the RAG prompt as a ForkJoin DAG of independent document-query paths (sharing a preamble) instead of a linear sequence; score each path with a Bayes-rule likelihood from the LM head and prune low-scoring paths, with equilibrium position assignment for continuous positions and path-level KV caching and parallel batching.

Key results

• On NaturalQuestions-Open with mpt-7b-instruct, superposition prompting reaches 0.465 accuracy vs 0.026 for naive LLM-RAG and 0.338 for Contriever, with 93.7x theoretical speedup.
• Path caching alone yields 10.2x speedup and parallelism alone 14.8x for mpt-7b-instruct on NaturalQuestions-Open.
• On MuSiQue, superposition prompting gives the highest F1 for each model tested, e.g. 0.120 F1 for mpt-7b-instruct versus 0.064 for naive RAG.

Measured effects reported in the paper

Surprising findings

• Naive LLM-RAG achieves near-zero accuracy on OpenELM-3B-Instruct and bloomz-3b on NaturalQuestions-Open, indicating severe length-extrapolation failure of baselines.
• Measured CUDA speedups are roughly an order of magnitude smaller than theoretical FLOP-based speedups because memory bottlenecks dominate.

Limitations

• Measured CUDA speedups are about an order of magnitude below theoretical speedups, since memory bottlenecks dominate and no fused kernel is implemented.
• Path caching requires auxiliary memory proportional to tokenized sequence length, and iterative superposition on MuSiQue lowers speedups because only the first k documents are cacheable.
• Evaluated only on NaturalQuestions-Open and MuSiQue with small open models; fine-tuning effects are left unexplored.

Experimental setup

Datasets: NaturalQuestions-Open MuSiQue

Benchmarks: NaturalQuestions-Open MuSiQue

Metrics: Best EM Subspan accuracy Answer EM F1 theoretical speedup (compute cycles via fvcore) CUDA speedup

Baselines: Naive LLM-RAG BM-25 TF-IDF Contriever Attention Sort Prompt Cache

Builds on: Prompt Cache Attention Sort SGPT PagedAttention Parallel Context Windows

Closest papers by meaning

• Long-Context LLMs Meet RAG: Overcoming Challenges for Long Inputs in RAG (ICLR 2025 · similarity 0.89)
• Inference Scaling for Long-Context Retrieval Augmented Generation (ICLR 2025 · similarity 0.89)
• Accelerating Inference of Retrieval-Augmented Generation via Sparse Context Selection (ICLR 2025 · similarity 0.88)
• RankRAG: Unifying Context Ranking with Retrieval-Augmented Generation in LLMs (NeurIPS 2024 · similarity 0.88)
• One Token Can Help! Learning Scalable and Pluggable Virtual Tokens for Retrieval-Augmented Large Language Models (AAAI 2025 · similarity 0.88)
• RAPID: Long-Context Inference with Retrieval-Augmented Speculative Decoding (ICML 2025 · similarity 0.88)