Xiaoyu Leng, Hongchao Qin, Rong-Hua Li, Guoren Wang
Hypergraphs capture higher-order interactions involving multiple entities. Existing decomposition models, such as $k$-core and nbr-$k$-core, rely on degree or neighborhood constraints and may overlook fine-grained density variations. We propose a $(k,δ)$-dense subhypergraph model based on capped hyperedge contributions. For each parameter pair, the unique dense set is the inclusionwise smallest maximizer of a penalized capped hyperedge contribution. These dense sets form a nested hierarchy characterized by egalitarian $δ$-orientations and hypergraph reachability. We develop three algorithms for dense subhypergraph search and two for complete density decomposition. Both decomposition algorithms use integral flow balancing: Flow-Decomp extracts density levels through strongly connected component condensation, while Reverse-Decomp uses direct reverse propagation. Once an egalitarian orientation is obtained, both recover all density levels in linear time. We further derive sandwich bounds that restrict computation to equivalent residual subproblems and develop incremental algorithms for maintaining the hierarchy under hyperedge insertions and deletions. Experiments on nine real-world hypergraphs, including datasets with over 15 million vertices, compare our methods with four established decomposition models. The results show that Reverse-Decomp improves decomposition efficiency, incremental maintenance outperforms recomputation in the tested settings, and the proposed model captures density structures overlooked by degree-based decompositions.
Pengqi Li, Lizhong Ding Beijing Institute of Technology, Zhehao Zhou, Chunhui Zhang, Jiarun Fu, Hao Li Beijing Institute of Technology, Ye Yuan Beijing Institute of Technology, Guoren Wang Beijing Institute of Technology
Hallucinations arise when large language models (LLMs) guess rather than acknowledge their underlying uncertainty. Existing static strategies for mitigating hallucinations have been only partially successful, largely because they do not explicitly model the information gain from interacting with the external environment. Researchers need a general method to proactively steer users toward informative clarifications, thereby unlocking the model’s effective capacity under underspecified inputs. We model the uncertainty of LLMs in interactive settings and uncover the mechanism of active calibration between model concepts and human evaluations, improving reliability. We show that calibration error in LLMs density estimation admits a non-vanishing lower bound under non-interactive learning, while interaction empirically reduces it. We further characterize that calibration error identifies informative queries and that calibration can be accelerated by shifting query distributions from imbalanced to balanced regimes. Guided by these insights, we propose a calibration-driven Interactive Learning Strategy (ILS) that selects clarification queries by optimizing calibration error, providing both theoretical guarantees and empirical gains for reliability. Code and data are available at https://github.com/zhouyeah215/Demystifying_Uncertainty.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Guangming Qin, Yuhao Deng, Yukun Zhao, Zhenyang Li Baidu, Junfeng Wang, Dawei Yin Baidu, Ye Yuan Beijing Institute of Technology, Guoren Wang 等 11 位作者
The most recent research uses reinforcement learning (RL) to post-train Multi-modal Large Language Models (MLLMs) such that these models are able to iteratively call search engines to dynamically access external knowledge when handling complex Visual Question Answering (VQA) tasks. However, existing methods face two major limitations in effectiveness and efficiency: i) For effectiveness, the objective of these methods, which only considers the correctness of the generated final response, overlooks the quality of intermediate search results, thus leading to suboptimal search strategies. ii) For efficiency, existing methods often unnecessarily invoke search calls during reasoning, making the inference inefficient. To address these issues, we propose , a customized dual-objective reinforcement learning framework to improve the search strategies of MLLMs, enhancing their search quality yet minimizing search frequency. The key ideas include (1) a reward function that promotes correct reasoning trajectories with fewer search calls; and (2) dual optimization objectives that jointly optimize search quality and answer correctness. Extensive experiments on 3 real-world datasets demonstrate that DORA outperforms state-of-the-art methods, achieving up to 8.4% higher accuracy while reducing the number of search calls by 9.7%.
尚无 AI 解读，展示原文摘要
cs.CL · cs.AI · cs.CV
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表