Prefix-Cache-Aware Data Reordering for LLM-Augmented Database Analytics

Yingze Li, Dong Wang, Yiming Guo, Yao Chen, Hongzhi Wang, Bingsheng He
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:70693-70723, 2026.

Abstract

LLM-augmented database analytics face a major bottleneck in the costly prefill phase. Although relational tables inherently contain repeated attribute values, standard row-by-row processing produces fragmented prompt layouts that obscure shared prefixes, thereby minimizing opportunities for prefix KV cache reuse and constraining system efficiency. Existing solutions typically employ heuristic or exhaustive search methods to reorder prompt layouts, but these approaches can be inefficient and may not leverage the structural properties of relational tables. We address this challenge by formulating prefix-cache-aware prompt layout optimization as a problem rooted in the isomorphism between prefix-cache reuse and the radix tree topology induced by the relational data distribution. Building on this perspective, we introduce a practical greedy tree-shaping algorithm that efficiently selects row and column orderings to maximize prefix overlap. Our approach, SOLO, improves prefill throughput by up to 90.3% under fixed prefix-cache budget. Moreover, it reduces planning overhead by up to 242$\times$ compared to state-of-the-art baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-li26gn, title = {Prefix-Cache-Aware Data Reordering for {LLM}-Augmented Database Analytics}, author = {Li, Yingze and Wang, Dong and Guo, Yiming and Chen, Yao and Wang, Hongzhi and He, Bingsheng}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {70693--70723}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/li26gn/li26gn.pdf}, url = {https://proceedings.mlr.press/v306/li26gn.html}, abstract = {LLM-augmented database analytics face a major bottleneck in the costly prefill phase. Although relational tables inherently contain repeated attribute values, standard row-by-row processing produces fragmented prompt layouts that obscure shared prefixes, thereby minimizing opportunities for prefix KV cache reuse and constraining system efficiency. Existing solutions typically employ heuristic or exhaustive search methods to reorder prompt layouts, but these approaches can be inefficient and may not leverage the structural properties of relational tables. We address this challenge by formulating prefix-cache-aware prompt layout optimization as a problem rooted in the isomorphism between prefix-cache reuse and the radix tree topology induced by the relational data distribution. Building on this perspective, we introduce a practical greedy tree-shaping algorithm that efficiently selects row and column orderings to maximize prefix overlap. Our approach, SOLO, improves prefill throughput by up to 90.3% under fixed prefix-cache budget. Moreover, it reduces planning overhead by up to 242$\times$ compared to state-of-the-art baselines.} }
Endnote
%0 Conference Paper %T Prefix-Cache-Aware Data Reordering for LLM-Augmented Database Analytics %A Yingze Li %A Dong Wang %A Yiming Guo %A Yao Chen %A Hongzhi Wang %A Bingsheng He %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-li26gn %I PMLR %P 70693--70723 %U https://proceedings.mlr.press/v306/li26gn.html %V 306 %X LLM-augmented database analytics face a major bottleneck in the costly prefill phase. Although relational tables inherently contain repeated attribute values, standard row-by-row processing produces fragmented prompt layouts that obscure shared prefixes, thereby minimizing opportunities for prefix KV cache reuse and constraining system efficiency. Existing solutions typically employ heuristic or exhaustive search methods to reorder prompt layouts, but these approaches can be inefficient and may not leverage the structural properties of relational tables. We address this challenge by formulating prefix-cache-aware prompt layout optimization as a problem rooted in the isomorphism between prefix-cache reuse and the radix tree topology induced by the relational data distribution. Building on this perspective, we introduce a practical greedy tree-shaping algorithm that efficiently selects row and column orderings to maximize prefix overlap. Our approach, SOLO, improves prefill throughput by up to 90.3% under fixed prefix-cache budget. Moreover, it reduces planning overhead by up to 242$\times$ compared to state-of-the-art baselines.
APA
Li, Y., Wang, D., Guo, Y., Chen, Y., Wang, H. & He, B.. (2026). Prefix-Cache-Aware Data Reordering for LLM-Augmented Database Analytics. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:70693-70723 Available from https://proceedings.mlr.press/v306/li26gn.html.

Related Material