Research map / Large language models / Reasoning and chain of thought
Prefix-Cache-Aware Data Reordering for LLM-Augmented Database Analytics
Yingze Li, Dong Wang, Yiming Guo, Yao Chen, Hongzhi Wang, Bingsheng He
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.
Reorders relational table rows and fields to create shared prompt prefixes so LLM-augmented database queries can reuse prefix KV cache, reducing prefill cost.
Problem
LLM-augmented database analytics is bottlenecked by costly prefill; row-by-row processing produces fragmented prompts that hide shared prefixes, limiting prefix KV cache reuse.
Approach
Reorder table data (rows and attribute order within prompts) to expose repeated attribute values as shared prompt prefixes, instead of heuristic or exhaustive-search reordering used by prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| reorder rows and columns with SOLO | default layout · DMV | prefix-cache hit rate (%): 1.8% -> 35.2% | Improved |
| reorder rows and columns with SOLO | default layout · Food | prefix-cache hit rate (%): 0.0% -> 71.1% | Improved |
| reorder rows and columns with SOLO | default layout · OpenPayments | prefix-cache hit rate (%): 23.7% -> 76.3% | Improved |
| use SOLO instead of GGR | GGR · OpenPayments | avg prefix overlap: 62.72 -> 75.93 | Improved |
| use SOLO instead of NDV column order | NDV · DMV | avg prefix overlap: 11.16 -> 12.72 | Improved |
| reorder with SOLO under strongest injected functional dependency | NDV · OpenPayments (80% constrained) | prefix overlap: 45.26 -> 65.55 | Improved |
| use SOLO for planning instead of GGR | GGR · Planning overhead | planning time: 242.81x lower | Improved |
| use SOLO for prefill under fixed cache budget | baseline layouts · Prefill throughput | prefill throughput: up to 90.3% | Improved |
| give planners a larger time budget (187.5s) instead of SOLO at 1.5s | strongest compared planner · OpenPayments | prefix overlap: 75.93 -> 62.72 | Hurt |
| add matching row ordering to reuse-aware column ordering (ablation) | column-only reordering · Column and row ablation | avg prefix overlap | Improved |
| reorder layout with SOLO (column-only vs full) on output quality | original layout · GoogleAnalytics | accuracy change (points): -0.6 | No clear effect |
| reorder layout with SOLO | original layout · DMV | accuracy change (points): +0.4 | No clear effect |
Experimental setup
Baselines: heuristic reordering exhaustive search reordering row-by-row processing
Closest papers by meaning
- LLM Query Scheduling with Prefix Reuse and Latency Constraints (NeurIPS 2025 · similarity 0.83)
- MiniPIC: Flexible Position-Independent Caching in <100LOC (NeurIPS 2026 · similarity 0.83)
- Compute or Load KV Cache? Why Not Both? (ICML 2025 · similarity 0.81)
- DualMap: Enabling Both Cache Affinity and Load Balancing for Distributed LLM Serving (ICLR 2026 · similarity 0.81)
- Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective (ICLR 2026 · similarity 0.80)
- TableRAG: Million-Token Table Understanding with Language Models (NeurIPS 2024 · similarity 0.80)
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.
