Andrii Bidochko

• Updated: July 12, 2026
• 7 min read

PolyUQuest: Verifiable Structure-Aware Web RAG over Heterogeneous Graphs

Direct Answer

PolyUQuest introduces a verifiable, structure‑aware retrieval‑augmented generation (RAG) framework that treats web pages as heterogeneous graphs, preserving HTML hierarchy, hyperlink topology, and cross‑page entity relations. By routing queries through a two‑tier router and attaching fine‑grained citations to every answer, the system dramatically improves answer correctness, coverage, and faithfulness while cutting LLM token consumption.

Background: Why This Problem Is Hard

Traditional RAG pipelines ingest web content as a flat string of text. This flattening discards two critical sources of signal:

• DOM hierarchy: Headings, lists, tables, and other structural cues that indicate the importance and context of a block.
• Hyperlink and entity semantics: Links between pages and the entities they mention encode a knowledge graph that can be traversed for multi‑hop reasoning.

When these signals are lost, LLMs must infer structure from raw tokens, leading to hallucinations, missed citations, and inefficient token usage. Moreover, existing RAG systems provide limited traceability—users cannot easily verify which part of a page supports a claim, a shortcoming for academic or enterprise settings where trust is non‑negotiable.

Current approaches attempt to mitigate these issues by chunking pages heuristically or by adding a separate knowledge base, but they still suffer from:

1. Rigid retrieval modes: A single retrieval strategy cannot satisfy queries that range from simple fact lookup to complex multi‑entity reasoning.
2. Scalability bottlenecks: Maintaining separate indexes for text, DOM, and graph data inflates storage and query latency.
3. Verification gaps: Answers often lack a clear path back to the original source, undermining confidence.

These challenges are especially acute for university portals, corporate intranets, and other structured web ecosystems where the underlying HTML encodes rich, domain‑specific knowledge.

What the Researchers Propose

PolyUQuest proposes a unified heterogeneous graph that simultaneously captures three layers of web information:

• Hyperlink topology: Nodes represent whole pages; edges encode outgoing and incoming links.
• DOM hierarchy: Within each page node, sub‑nodes correspond to DOM blocks (e.g., headings, paragraphs, tables), preserving parent‑child relationships.
• Entity‑relation knowledge: Named entities extracted from blocks become nodes linked by semantic relations (e.g., “teaches”, “located‑in”).

The framework introduces a two‑tier router that first classifies a query by its structural demand (single‑block, cross‑page, or multi‑hop entity reasoning) and then dispatches it to the appropriate retrieval mode:

1. Direct block retrieval for straightforward fact‑looking queries.
2. Cross‑page graph traversal for questions that require navigating hyperlinks.
3. Multi‑hop entity reasoning for complex queries that need chaining across entities and relations.

Every generated answer is accompanied by a verifiable citation bundle that includes the source page URL, the full heading path to the block, and any linked entities, enabling users to trace each claim back to its structural evidence.

How It Works in Practice

Conceptual Workflow

The end‑to‑end pipeline can be broken down into four stages:

1. Web Crawl & Pre‑processing: The system crawls the target domain (PolyU’s official site in the paper) and parses each HTML document into DOM blocks.
2. Graph Construction: Blocks become nodes; hyperlinks become inter‑page edges; an entity extractor (e.g., spaCy or a fine‑tuned NER model) identifies entities, which are added as separate nodes linked by relation edges derived from surrounding text.
3. Two‑Tier Routing:
   • Tier 1 – Structural Classification: A lightweight classifier (often a small transformer) predicts whether the query needs block‑level, link‑level, or entity‑level reasoning.
   • Tier 2 – Retrieval Mode Selection: Based on the Tier 1 label, the router invokes the corresponding retrieval engine (BM25 over blocks, graph‑walk for hyperlinks, or a neural retriever for entity paths).
4. Answer Generation & Verification: The retrieved evidence is fed to a generative LLM (e.g., GPT‑4) with a prompt that forces citation of each block. The system then formats the answer with a structured citation bundle.

Component Interaction

Figure 1 (placeholder) illustrates the data flow:

Key interactions include:

• Crawler ↔ Graph Builder: The crawler streams raw HTML; the builder extracts DOM nodes and entity triples in real time.
• Router ↔ Retrieval Engines: The router’s decision is a lightweight API call that selects the appropriate index, ensuring sub‑second latency.
• LLM ↔ Citation Formatter: The LLM receives a prompt that includes retrieved blocks and a “cite‑as‑you‑go” instruction; the formatter then attaches the hierarchical path and entity links.

What Sets PolyUQuest Apart

• Unified Graph: Instead of maintaining parallel indexes, a single heterogeneous graph serves all retrieval modes, reducing storage overhead.
• Structure‑Aware Routing: The two‑tier router dynamically matches query complexity to the most efficient retrieval strategy, cutting token usage by up to 40% in experiments.
• Built‑in Verifiability: Citations are not an afterthought; they are generated alongside the answer, providing a transparent audit trail.

Evaluation & Results

Benchmark Design

The authors constructed a multi‑type benchmark covering three query families:

• Block‑Level Questions: Simple factual lookups (e.g., “What is the deadline for the MSc program?”).
• Link‑Level Questions: Queries that require navigating from one page to another (e.g., “Which department hosts the AI research lab?”).
• Entity‑Reasoning Questions: Multi‑hop inference across entities (e.g., “Name all professors who supervise PhD students in computer vision.”).

The dataset comprised 1,200 annotated queries with ground‑truth answers and citation paths, drawn from real student inquiries and faculty FAQs.

Key Findings

PolyUQuest consistently outperformed baselines across all three query families. The most pronounced gains appeared in entity‑reasoning questions, where the heterogeneous graph enabled concise multi‑hop paths that a flat‑text retriever could not discover.

Human evaluators also reported higher trust levels because every claim was backed by a clear citation bundle, reducing perceived hallucination risk.

Why This Matters for AI Systems and Agents

For AI practitioners building agents that must interact with web knowledge bases, PolyUQuest offers a blueprint for marrying structural web signals with LLM reasoning. The implications include:

• Reduced Hallucination: By grounding generation in verifiable blocks, agents can answer with higher factual fidelity, a critical requirement for compliance‑heavy industries.
• Token Efficiency: The router’s ability to select the minimal evidence set cuts LLM token consumption, lowering inference cost and enabling higher query throughput.
• Modular Extensibility: The heterogeneous graph can be enriched with additional modalities (e.g., PDFs, multimedia metadata), allowing agents to evolve without redesigning the retrieval stack.
• Better Orchestration: In multi‑agent ecosystems, a shared graph serves as a common knowledge store, simplifying coordination and reducing duplication.

Enterprises looking to embed trustworthy Q&A into intranets, support portals, or knowledge‑base assistants can adopt the PolyUQuest pattern to achieve both accuracy and auditability. For example, the Enterprise AI platform by UBOS could integrate a PolyUQuest‑style graph to power its internal help‑desk bots, delivering answers that are instantly traceable to policy documents.

What Comes Next

While PolyUQuest marks a significant step forward, several avenues remain open for exploration:

• Dynamic Graph Updates: Current construction is batch‑oriented; real‑time updates would enable agents to reflect breaking news or rapidly changing curricula.
• Cross‑Domain Generalization: Extending the approach beyond a single university to heterogeneous corporate ecosystems will test scalability and schema alignment.
• Richer Entity Semantics: Incorporating ontologies or knowledge graphs like Wikidata could improve relation extraction and enable deeper reasoning.
• User‑Feedback Loops: Allowing end‑users to flag incorrect citations could create a reinforcement signal that refines both the graph and the router.

Future research may also investigate hybrid retrieval that blends dense vector search with the graph‑based approach, potentially capturing both semantic similarity and structural relevance.

Developers interested in rapid prototyping can experiment with the Chroma DB integration to store vector embeddings alongside the graph, or leverage the Workflow automation studio to orchestrate crawl‑to‑graph pipelines without writing extensive code.

Conclusion

PolyUQuest demonstrates that treating web content as a first‑class heterogeneous graph—preserving DOM hierarchy, hyperlink topology, and entity relations—yields a RAG system that is more accurate, transparent, and cost‑effective. Its two‑tier routing mechanism intelligently matches query complexity to the optimal retrieval mode, while built‑in citation bundles provide the verifiability demanded by academic and enterprise users alike. As AI agents become integral to knowledge‑intensive workflows, frameworks like PolyUQuest will likely become the de‑facto standard for trustworthy, structure‑aware web retrieval.

For readers who want to dive deeper, the full PolyUQuest paper offers detailed methodology, ablation studies, and a public demo that showcases interactive evidence inspection.

Andrii Bidochko

CTO UBOS

Andrii Bidochko is an AI entrepreneur and researcher focused on AI agents, reinforcement learning, and autonomous systems. He writes about the technologies shaping the future of machine intelligence, from frontier models and agent architectures to real-world AI applications.