CGRiC: Compositional Risk Certification for Structured LLM Outputs

Large language models increasingly generate structured outputs, including citation-grounded summaries, multi-step reasoning chains, and tool-augmented responses, where correctness is inherently compositional: a single flawed claim can invalidate an otherwise accurate response. Existing certification methods treat outputs as atomic units, forcing a binary choice between unsafe acceptance and wasteful rejection. We introduce \textbf{Claim Graph Risk Control (CGRiC)}, a framework that decomposes responses into dependency graphs of verifiable claims and assigns calibrated per-claim risk bounds via information-lift statistics. By composing these bounds, CGRiC provides explicit guarantees on the probability that any incorrect claim passes verification undetected. When this composed risk exceeds a target threshold, the system triggers localized repairs rather than full abstention, preserving correct content while fixing problematic claims. Our approach explicitly models extraction noise and verifier imperfection, and exploits conditional independence structure for tighter certificates when validated. Empirically, CGRiC achieves target risk levels while reducing abstention by 31\% compared to atomic baselines across QA, summarization, and reasoning tasks.

When an AI system answers a question, its response is often built from many small pieces, such as several cited facts in a summary, or the individual steps of a math solution. The problem is that one wrong piece can ruin the whole answer, and a single false claim can mislead a doctor or a lawyer who trusts it. Today's safety tools treat each answer as all or nothing: they either accept the entire response or throw it away, which wastes a lot of useful information that was mostly correct. We built a method called CGRiC that instead breaks an answer into its individual claims and maps out how those claims depend on one another. It estimates how risky each claim is and combines these into a mathematical guarantee, a firm limit on the chance that any wrong claim slips through unnoticed. When the overall risk is too high, the system does not discard the whole answer; it locates the shaky claim and repairs just that part, often changing a single word, while keeping everything already verified. Across question answering, summarization, and math tasks, our method hits its safety targets while refusing to answer 31% less often than comparable approaches. This means people keep far more trustworthy information, which matters most in high stakes settings like medicine and law where both accuracy and helpfulness count.