GAUSS: Graph-Assisted Uncertainty Quantification using Structure and Semantics for Long-Form Generation in LLMs

In critical domains like clinical reporting, legal analysis, and policy drafting, large language models (LLMs) are increasingly expected to produce extended, fact‑rich narratives rather than isolated sentences. Reliable uncertainty quantification in such long‑form outputs is crucial. Existing techniques either assign a single confidence score to an entire paragraph or evaluate factual consistency by comparing extracted atomic facts across multiple generations. Some recent approaches represent fact–paragraph relationships using bipartite entailment graphs and derive uncertainty from fact centrality. However, these methods ignore the explicit dependencies among facts within a paragraph and the structural and semantic variation across multiple LLM outputs for the same prompt, missing a key source of uncertainty specific to long‑form generation. We propose GAUSS (Graph‑Assisted Uncertainty Quantification using Structure and Semantics), a principled framework that models each generated paragraph as a semantic graph of atomic facts and their relations. We posit that uncertainty arises from structural and semantic discrepancies among these graphs across different samples. GAUSS quantifies uncertainty as the expected alignment cost between the semantic graph of an anchor paragraph and those of alternative generations. By capturing both semantic content and structural coherence, GAUSS offers a more interpretable and theoretically grounded measure of uncertainty than coarse, sentence‑level scores.