AI Paper Atlas

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

ICML 2026 · Large language models › Reasoning and chain of thought · approach: KV cache compression

Read the paper

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 changedWhereMeasuredEffect
reorder rows and columns with SOLOdefault layout · DMVprefix-cache hit rate (%): 1.8% -> 35.2%Improved
reorder rows and columns with SOLOdefault layout · Foodprefix-cache hit rate (%): 0.0% -> 71.1%Improved
reorder rows and columns with SOLOdefault layout · OpenPaymentsprefix-cache hit rate (%): 23.7% -> 76.3%Improved
use SOLO instead of GGRGGR · OpenPaymentsavg prefix overlap: 62.72 -> 75.93Improved
use SOLO instead of NDV column orderNDV · DMVavg prefix overlap: 11.16 -> 12.72Improved
reorder with SOLO under strongest injected functional dependencyNDV · OpenPayments (80% constrained)prefix overlap: 45.26 -> 65.55Improved
use SOLO for planning instead of GGRGGR · Planning overheadplanning time: 242.81x lowerImproved
use SOLO for prefill under fixed cache budgetbaseline layouts · Prefill throughputprefill throughput: up to 90.3%Improved
give planners a larger time budget (187.5s) instead of SOLO at 1.5sstrongest compared planner · OpenPaymentsprefix overlap: 75.93 -> 62.72Hurt
add matching row ordering to reuse-aware column ordering (ablation)column-only reordering · Column and row ablationavg prefix overlapImproved
reorder layout with SOLO (column-only vs full) on output qualityoriginal layout · GoogleAnalyticsaccuracy change (points): -0.6No clear effect
reorder layout with SOLOoriginal layout · DMVaccuracy change (points): +0.4No clear effect

Experimental setup

Baselines: heuristic reordering exhaustive search reordering row-by-row processing

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy