GraTAG: Production AI Search via Graph-Based Query Decomposition and Triplet Aligned Generation with Rich Multimodal Representations
KDD 2026ACM SIGKDD Conference on Knowledge Discovery and Data Mining* = Co-first authors
In brief
GraTAG is a production AI search engine built on graph-based query decomposition and triplet-aligned generation, deployed as Xinyu at Xinhua News Agency. It tackles three pain points of AI search — imprecise retrieval on complex queries, logic lost to chunking, and flat text-only answers. Complex queries are broken into a dependency graph of atomic sub-queries for precise, stepwise retrieval; answer generation is aligned with relation triplets extracted from the retrieved evidence, restoring the logic that chunking breaks; and answers ship with timelines, built-in citations, and matched images. Across 1,000 real-world queries and over 243,000 expert ratings, GraTAG outperforms eight existing systems, and the industry-grade full-stack implementation is publicly released.
Key takeaways
- AI search answers fail in predictable ways: an expert audit of Perplexity AI, a leading AI search engine, on 300 queries across 8 domains found frequent problems, including answers that stray from their cited sources, key retrieved information missing from the answer, and noise-filled retrieved documents — failure modes GraTAG's production pipeline is designed to attack.
- Graph-based query decomposition (GQD) turns a multi-part query into a directed acyclic graph of single-question sub-queries — independent parts retrieved in parallel, dependent parts in sequence — making retrieval precise instead of noisy.
- GraTAG's query-decomposition model beats prompted GPT-4o at its own job — answer quality 9.312 vs. 9.204 on a 10-point GPT-4o-judged scale — after two-stage training: supervised fine-tuning on expert-curated decompositions, then GRPO (Group Relative Policy Optimization) reinforcement learning that rewards a decomposition by how likely the full pipeline is to answer correctly.
- Triplet-aligned generation (TAG) repairs what chunking — splitting retrieved pages into passages — breaks: entity-and-relation facts (triplets) pulled from the evidence are injected during generation to reconnect information across passages; removing TAG hurts factuality, insightfulness, and numerical precision most, and the automatic triplets come within 0.04 of hand-verified oracle triplets (9.312 vs. 9.351).
- Answers arrive as more than text: timelines cover about twice as many events as CHRONOS, a dedicated timeline-generation method, in half the time on that standalone task (33.3 s vs. 67.4 s), and 80% of answers include images, 90% of them judged relevant — the rival Metaso search engine includes images in just 3% of answers.
- Across 1,000 real-world queries, nine criteria, and 243,000+ expert ratings, GraTAG is rated best of the nine systems compared (9.235 out of 10 vs. 8.810 for the runner-up), leading in comprehensiveness (+10.8% relative) and insightfulness (+7.9%); on the public BrowseComp browsing benchmark it reaches 30.57% accuracy versus 26.07% for the strongest baseline.
- GraTAG runs in production as Xinyu at Xinhua News Agency (21,765 users) and China Telecom (85,439 users), with industry contracts above USD 2 million; a 14-day A/B test more than doubled active users' daily questions (2.73 to 5.56) — the cost is latency: 14.2 s per answer, slowest of the nine systems compared.
Abstract
Generative AI search engines offer a key advantage over traditional search engines through their ability to synthesize fragmented information for queries, yet they still require improvements in relevance, comprehensiveness, and presentation. To these ends, we introduce GraTAG, an AI Search framework that addresses these challenges through three core innovations. First, we introduce graph-based query decomposition (GQD) to dynamically break down complex or ambiguous queries into structured sub-queries with explicit dependencies, enabling more precise, stepwise retrieval. Second, we propose triplet-aligned generation (TAG), which dynamically constructs relation triplets from retrieved documents to explicitly model entity relationships, factual dependencies, and logical connections, enabling the model to generate more coherent and comprehensive answers. Third, GraTAG innovates in rich multimodal presentations that integrates timeline visualization and textual-visual choreography to reduce cognitive load and enhance information verification. Evaluated on recent real-world queries, GraTAG outperforms eight existing systems in human expert assessments, excelling in relevance, comprehensiveness, and insightfulness. Our work publicly releases a comprehensive, industry-grade full-stack AI search engine, providing a solid reference for the community and demonstrating the effectiveness of the proposed system through rigorous evaluations and ablation studies.
BibTeX
@inproceedings{gratag,
title = {{GraTAG}: Production {AI} Search via {Graph-Based} Query Decomposition and Triplet Aligned Generation with Rich Multimodal Representations},
author = {Tang, Bo and Zhu, Junyi and Li, Ang and Wu, Yiquan and Kuang, Kun and Jin, Beihong and Wu, Jiahao and Wang, Hao and Xi, Chenyang and Feng, Yuchen and Wei, Wenqiang and Li, Chunyu and Lin, Zehao and Li, Zhiyu and Xiong, Feiyu and Li, Beibei and Wei, Kaiwen and Chen, Jingrun},
year = {2026},
booktitle = {Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2},
pages = {8041--8052},
doi = {10.1145/3770855.3818426},
url = {https://doi.org/10.1145/3770855.3818426},
}