CHAIN: Complementary Signed Graph Propagation for Uncertainty Quantification in Large Language Models

This paper studies the problem of uncertainty quantification in large language models (LLMs), which is critical for reliable LLM deployment under the risk of hallucination. Existing approaches typically treat the response sets as unordered collections and rely on local pairwise similarity or clustering, which overlook relational signals among responses as well as their corresponding high-order structural semantics. Towards this end, we propose a novel approach named Complementary Signed Graph Propagation (CHAIN) for uncertainty quantification in LLMs. The core idea of CHAIN is to capture complementary signals among responses using a signed graph and then extract high-order structural information using random propagation. In particular, CHAIN builds a semantic graph where each response is considered as a node and edges represent complementary views, namely enrichment relations and contradiction relations. To acquire high-order structural signals, we update hidden states through graph-based information propagation along edges and channel fusion guided by randomized matrices. After propagation, these node states are summarized into graph-level scores for reliable uncertainty quantification. Extensive experiments on five datasets validate the effectiveness of the proposed CHAIN in comparison with competing baselines.