Zero-LLM Trajectory Search over Line-Lifted Knowledge Graphs: Internalizing Query Decomposition for Multi-Hop RAG

Retrieval-augmented generation (RAG) has become a cornerstone of LLM applications, underpinning vertical-domain knowledge construction and agent memory. As applications demand complex relational reasoning, retrieval has turned to graphs, yet graph-based RAG still relies almost entirely on LLM calls, one or more per query, making latency and cost a deployment bottleneck, as if precise retrieval required LLM guidance. We propose LiftRAG, which represents every extracted relation as a graph vertex carrying its evidence-sentence embedding, turning the knowledge graph into its line graph. Retrieval is then a multi-round beam search over entity–relation trajectories, where each step decides the next hop from the frontier reached so far and query decomposition emerges from the search itself, LLM-free. On the entity-grounded test sets of three multi-hop benchmarks, LiftRAG leads the published baselines on all four metrics. The accuracy margins are 5.7–10.0 points over LightRAG, which shares our extraction and index, and 0.9–3.9 over the strongest baseline, HippoRAG 2, at 13–25× lower retrieval latency in API deployment (per-call latency measured on our own LLM relay). Moreover, 7–20% of LLM-decomposed sub-question trajectories fall outside the coverage of a single retrieval by LiftRAG. This work establishes Zero-LLM Decomposition, query decomposition performed by the retrieval process itself without any LLM call. The part of LLM decomposition it does not cover defines the open problem of fusing the two.