# jXBW: A Compressed Index Enabling Structure-Aware JSONL Retrieval for Structured RAG

arXiv: https://arxiv.org/abs/2508.12536 · HTML: https://mlsanity.com/paper/2508.12536/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge-graph and structured-knowledge RAG, one of 15 directions in Retrieval-augmented generation.
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 18 Aug 2025.

## Placed in

- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 6 of 6)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [StructRAG: Boosting Knowledge Intensive Reasoning of LLMs via Inference-time Hybrid Information Structurization](https://mlsanity.com/paper/2410.08815/) (2024)
- [GenQA: Generating Millions of Instructions from a Handful of Prompts](https://mlsanity.com/paper/2406.10323/) (2024)
- [From Prompts to Templates: A Systematic Prompt Template Analysis for Real-world LLMapps](https://mlsanity.com/paper/2504.02052/) (2025)
- [RAS: Retrieval-And-Structuring for Knowledge-Intensive LLM Generation](https://mlsanity.com/paper/2502.10996/) (2025)
- [From Theory to Practice: Plug and Play with Succinct Data Structures](https://mlsanity.com/paper/1311.1249/) (2013)

## Abstract (arXiv)

Providing textitstructured information to large language models (LLMs) improves multi-step reasoning and factual grounding, and recent retrieval-augmented generation (RAG) systems therefore reconstruct structure from retrieved text on every query. When the corpus is already structured --- as in JSON Lines (JSONL), a popular format for LLM prompts, chemical compounds, and geospatial records --- this per-query rebuilding can be replaced by direct structural retrieval. The core primitive is textitsubstructure search: finding all JSON objects in a collection that contain a given query pattern. Existing approaches index each document separately, so both index space and query time grow with the total collection size; XML-based engines add conversion overhead and semantic mismatches. We propose jXBW, a compressed index for fast substructure search over JSONL, combining three innovations: (i) a merged tree representation that consolidates repeated structures across objects, (ii) a succinct tree index based on the eXtended Burrows--Wheeler Transform (XBW), and (iii) a newly developed three-phase substructure search algorithm that runs on this index. Together they achieve query-dependent complexity: chgbthe search avoids a full scan of the collection and is candidate- and output-sensitive, in compressed space. Experiments on seven real-world datasets, including PubChem (106 compounds) and OpenStreetMap (6.6 × 106 objects), show that jXBW outperforms the strongest tree-based baseline by 16× on the smallest dataset and by up to mathbf2,800× on the largest, and is more than 2 × 106× faster than the XQuery engine Saxon. jXBW thus brings structural retrieval over million-record JSONL collections into the sub-millisecond range.