PolyUQuest: Verifiable Structure-Aware Web RAG over Heterogeneous Graphs

Source: arXiv:2607.08269 · Published 2026-07-09 · By Ying Liu, Yi Ye, Quanyu Feng, Mingxi Ye, Mingtao Zhang, Haoyang Li et al.

TL;DR

PolyUQuest addresses a core limitation in existing retrieval-augmented generation (RAG) systems that treat web pages as flat text, losing important structural signals encoded in HTML. The paper introduces a verifiable, structure-aware RAG framework that represents a website as a heterogeneous graph unifying three structural layers: the hyperlink topology connecting pages, the DOM hierarchy within pages partitioned into heading-aware text blocks, and the cross-page entity-relation graph linking named entities and topics. A two-tier routing mechanism classifies user queries and dynamically dispatches them to one of three retrieval modes optimized for differing structural needs: single-block retrieval, cross-page navigation, or multi-hop entity reasoning. PolyUQuest fully supports provenance by associating each cited answer block with its source page, heading path, and entity context, enabling users to trace answers back to their exact structural evidence. On a real-world large university website dataset (4,240 pages, 31,086 DOM blocks, 29,119 entities, 37,680 relations), PolyUQuest outperforms existing state-of-the-art RAG models in answer correctness (0.644 vs best baseline 0.610), coverage (0.649 vs 0.612), and faithfulness (0.921 vs 0.559), achieving these gains while consuming an order of magnitude fewer LLM tokens per query than costly global graph RAG approaches. The demonstration highlights interactive answer provenance inspection, retrieval trace comparison, and evidence graph exploration. PolyUQuest shows that fine-grained, structure-aware indexing paired with query routing to targeted retrieval pathways can efficiently deliver more accurate, verifiable answers across complex, multi-page web knowledge sources.

Key findings

• PolyUQuest achieves 0.644 answer correctness, 0.649 coverage, and 0.921 faithfulness on 300 curated PolyU-Web questions, outperforming ChunkRAG (0.532/0.479/0.710), HtmlRAG (0.453/0.448/0.804), FastGraphRAG (0.295/0.469/0.737), and LightRAG (0.610/0.612/0.559) (Table 1).
• PolyUQuest consumes only 2,968 LLM tokens per query, 10× fewer than LightRAG’s 29,825 tokens and 26% fewer than HtmlRAG’s 4,009 tokens, by routing queries to targeted retrieval modes instead of injecting large global contexts.
• Ablation removing DOM block segmentation causes an 8.1-point drop in correctness and 13.9-point drop in coverage, confirming structure-aware blocks are critical (Table 2).
• Removing the cross-page navigation mode reduces correctness by 2.0 points and coverage by 1.6 points, highlighting its moderate but significant contribution to multi-page question answering (Table 2).
• Each cited answer block carries detailed provenance metadata: source page URL, heading path, and linked entities, enabling user verification of claims and graph-based evidence exploration.
• Query routing uses heuristics and an LLM classifier to assign queries to three modes: direct block retrieval (Mode A), cross-page navigation (Mode B), and multi-hop entity reasoning (Mode C), improving efficiency and structural fidelity.
• The unified heterogeneous graph consists of webpage nodes, evidence block nodes, entity nodes, and topic nodes, connected by edges encoding page hyperlinks, block containment, entity mentions, and entity-topic relations.
• The demo interface supports inspection of answer provenance, retrieval trace comparison across modes, and exploration of underlying heterogeneous graph evidence paths.

Threat model

The adversary is a typical end-user querying a complex, structured website to extract accurate factual knowledge. They do not manipulate the source webpages but may ask challenging multi-hop questions requiring reasoning over distributed web content. The system assumes trusted crawled data and does not consider malicious attacks like content poisoning or adversarial inputs compromising retrieval.

Methodology — deep read

1. Threat model & assumptions: PolyUQuest assumes the adversary is a user querying a large, structured website (such as a university) whose information is distributed across linked pages, hierarchical DOM blocks, and recurring named entities. The model assumes that the website's HTML structure and entity data can be crawled and processed offline; no adversarial manipulation of source data is considered.

2. Data: The dataset comprises the entire public English website of Hong Kong Polytechnic University (PolyU) with 4,240 pages containing 31,086 DOM evidence blocks, 29,119 normalized entity nodes, and 37,680 inter-entity relations extracted by a domain-trained LLM. Queries include 300 manually curated questions spanning single-page factual lookup, cross-page navigation, and entity-centric reasoning. Relevance labels map questions to official pages and evidence blocks.

3. Architecture / algorithm: The core data structure is a three-layer heterogeneous graph G = (V, E) where nodes V are webpages, evidence blocks (150-word heading-aware units), entities, and topics. Edges E encode: site graph hyperlinks between pages; page-block containment; block-entity mentions; and semantic entity-topic relations. A bottom-up block-tree construction merges DOM subtrees to capture hierarchy, filtering boilerplate. Entities and their relations are extracted by a small set of website-relevant types and resolved via alias normalization and LLM-based disambiguation.

Query routing is a two-tier classifier. The first tier applies heuristic rules detecting structural signals (keywords like 'professors' or comparison patterns). The second tier uses an LLM classifier to assign queries to one of three retrieval modes:

• Mode A: Direct block retrieval for single-hop facts, combining dense nearest-neighbor search (block embeddings) and BM25 lexical search to generate candidate evidence block sets, then cross-encoder reranking over query, block text, source page, and heading path.
• Mode B: Cross-page navigation for multi-page evidence aggregation. The query is decomposed into subqueries by LLM, which retrieve relevant pages expanded to linked neighbors in the site graph, pulling blocks from multiple pages and reranking holistically.
• Mode C: Multi-hop entity reasoning for entity-centric queries. Extract topic keywords and expand candidate entities via 2-hop entity graph traversal. Candidate blocks linked to these entities are ranked by combined cosine similarity, capped entity coverage, and conciseness, with penalties for blocks from the same page to promote source diversity.

4. Training regime: The entity extraction and resolution uses LLMs fine-tuned on domain-relevant types but details on epochs, batch size, or optimizer are not specified. The reranker is a cross-encoder model jointly scoring queries and candidate blocks; training details are not fully disclosed. For the routing LLM classifier, heuristics handle common cases, limiting LLM calls and latency.

5. Evaluation protocol: Evaluation uses the 300 PolyU-Web questions with manual relevance annotations to compute three primary metrics: Answer Correctness (measuring factual accuracy), Coverage (completeness of retrieved evidence), and Faithfulness (degree to which claims are supported by retrieved evidence). Efficiency metrics include average query tokens consumed by the LLM and offline build tokens during indexing. Baselines include ChunkRAG, HtmlRAG, FastGraphRAG, and LightRAG, all evaluated with the same generator LLM, prompt, and embedding model for fairness. Ablations remove DOM blocks and cross-page navigation to analyze contributions. Statistical tests are not explicitly mentioned.

6. Reproducibility: The code is publicly available (GitHub repository linked in paper). The dataset is a publicly crawlable institutional website but the evaluation queries and annotations are curated by the authors and not noted as public. Frozen LLM weights and prompt details are partly disclosed. The indexing and retrieval pipeline is fully described but some components depend on proprietary or closed LLMs.

Concrete example: For the question “What subjects are in the AIDA secondary major for BEng Mechanical Engineering?”, the system routes the query to Mode A (direct block retrieval). It first constructs query embeddings and uses ANN plus BM25 to find a candidate set of text blocks. The blocks are reranked by a cross-encoder considering the block text, its page, and heading path context. The top-ranked evidence blocks from the blocks store are assembled with source URLs, section headings, and entity annotations, generating an answer with inline citations that users can click to inspect the provenance evidence within the website. This end-to-end process preserves the structural context and limits token consumption by avoiding full-page or global context injection.

Technical innovations

• Unified three-layer heterogeneous web graph integrating hyperlink structure, DOM block hierarchy, and entity-relation knowledge across pages, enabling richer context representation compared to prior single-layer or flattened approaches.
• Two-tier query routing combining lightweight heuristics and an LLM classifier to dynamically dispatch queries to one of three structurally matched retrieval modes (block retrieval, cross-page navigation, multi-hop entity reasoning), improving efficiency and accuracy.
• Structure-aware block segmentation using heading-aware DOM subtree merging removing non-content boilerplate, preserving semantic hierarchy and locality for more coherent and precise evidence retrieval.
• Verifiable answer provenance with each cited block linked to its originating page, heading path, and entity links, supporting transparent user inspection and trust in generated answers.

Datasets

• PolyU-Web — 4,240 pages, 31,086 DOM blocks, 29,119 entities, 37,680 relations — Crawled official Hong Kong Polytechnic University website for institutional QA

Baselines vs proposed

• ChunkRAG: Correctness=0.532, Coverage=0.479, Faithfulness=0.710, Query Tokens=2947 vs PolyUQuest: Correctness=0.644, Coverage=0.649, Faithfulness=0.921, Query Tokens=2968
• HtmlRAG: Correctness=0.453, Coverage=0.448, Faithfulness=0.804, Query Tokens=4009 vs PolyUQuest same metrics
• FastGraphRAG: Correctness=0.295, Coverage=0.469, Faithfulness=0.737, Query Tokens=4484 vs PolyUQuest same metrics
• LightRAG: Correctness=0.610, Coverage=0.612, Faithfulness=0.559, Query Tokens=29825 vs PolyUQuest same metrics

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.08269.

Fig 2: Interactive demo interface of PolyUQuest.

Fig 2 (page 4).

Fig 3 (page 4).

Fig 4 (page 4).

Fig 5 (page 4).

Fig 6 (page 4).

Limitations

• Evaluation limited to a single institutional website domain (PolyU) thus generalizability to other heterogeneous web domains not fully validated.
• No explicit adversarial or robustness testing against deliberately misleading or manipulated HTML/webpage content.
• Relies on accurate entity extraction and resolution by LLMs; errors in entity linking can impact retrieval quality but impact not deeply analyzed.
• Cross-encoder reranker and routing LLM details including training regimes are not fully disclosed, limiting reproducibility of exact performance.
• Handling of dynamic web content or frequent updates is unclear; system evaluated on a static crawl snapshot.
• No end-to-end latency or server load benchmarks reported, only LLM token efficiency.

Open questions / follow-ons

• How well does PolyUQuest generalize to other sectors such as government or corporate websites with differing HTML structures and ontologies?
• What is the impact of entity extraction and resolution errors on downstream answer quality and faithfulness?
• Can the routing classifier be improved by joint training or learning from user interaction logs to better handle long-tail queries?
• How does the system perform under evolving website content or partial web property crawls with missing pages?

Why it matters for bot defense

PolyUQuest illustrates that leveraging rich website structural signals beyond plain text—such as hyperlink graphs, DOM hierarchies, and entity relations—can significantly improve retrieval accuracy, faithfulness, and user verifiability in QA systems. For bot-defense and CAPTCHA engineers, this work underscores the value of incorporating fine-grained structural features and provenance signals to verify evidence origin and reduce hallucination risks in content fetched for automated reasoning. The two-tier query routing scheme offers an efficient way to balance retrieval cost versus complexity based on query type, which could inspire adaptive backend pipelines for interactive captcha solving where some queries need deeper multi-hop reasoning over site structure. The explicit provenance and graph-based evidence exploration interfaces inform transparency standards essential for trusted automated retrieval in security-sensitive applications.

Cite

@article{arxiv2607_08269,
  title={ PolyUQuest: Verifiable Structure-Aware Web RAG over Heterogeneous Graphs },
  author={ Ying Liu and Yi Ye and Quanyu Feng and Mingxi Ye and Mingtao Zhang and Haoyang Li and Chen Jason Zhang and Qing Li },
  journal={arXiv preprint arXiv:2607.08269},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.08269}
}

Read the full paper

• arXiv:2607.08269 (abstract)
• arXiv:2607.08269 (PDF)