Consistent submodular maximization aims to maintain a high-utility subset of size at most $k$ as new elements arrive one by one, while changing only a limited number of elements per update. Previously, [DFL+25](STOC '25) established an information-theoretic bound of $2/3$ and gave the first polynomial-time randomized algorithm with a $0.51$-approximation guarantee. However, a fundamental question remained open: Is it possible to design an efficient algorithm for consistent submodular maximization that matches the classical offline $(1-1/e)$-approximation? In this paper, we answer this question in the negative by proving that the sharp approximation threshold achievable with polynomially many value queries and worst-case constant recourse is \[β:=2-\sqrt{2}\approx0.5858<1-1/e.\] Specifically, we develop an improved poly-time randomized algorithm, which can attain a $(β-\varepsilon)$-approximation in expectation at each fixed time with $O(\varepsilon^{-2})$ worst-case recourse. The cornerstone of this algorithm is a novel anchored sampling scheme, which uses only value queries on subsets of the elements seen so far to construct a solution that remains competitive under unknown future arrivals. Conversely, we establish a matching lower bound by showing that any fixed improvement over $β$ requires either exponentially many value queries or $Ω(k)$ changes per update. Furthermore, we characterize the impact of curvature by establishing a sharp threshold of $1-(\sqrt{2}-1)\vartheta$ for consistent submodular maximization, where $\vartheta\in[0,1]$ denotes the total curvature. Surprisingly, for weighted coverage objectives, we devise a poly-time randomized algorithm that can match the optimal $(1-1/e-\varepsilon)$-approximation with $O(\varepsilon^{-1})$ worst-case recourse, thereby separating coverage maximization from general submodular maximization in the consistent settings.
Jiahao Nie, Yun Xing, Wenbin An, Qixin Zhang, Yap-Peng Tan, Alex C. Kot, Shijian Lu
Cross-Domain Few-Shot Segmentation (CD-FSS) aims to segment objects from unseen domains using only a few annotated references. Recent Segment Anything Model (SAM)-based methods have advanced CD-FSS, yet their reference-target visual matching is highly sensitive to target appearance variations. SAM3 introduces text-conditioned segmentation, enabling natural-language descriptions to guide segmentation across target images, but directly using the category name as the condition still yields unstable performance under severe domain shifts. We propose Reference Inversion for SAM3 (RI-SAM3) that leverages SAM3's large-scale vision-language pre-training to learn suitable textual tokens for each target category. RI-SAM3 comprises three core designs: (i) Bi-level Reference Inversion that learns complementary tokens before and after the frozen text encoder: the former remain anchored in SAM3's text space while the latter represent the category more flexibly; (ii) Layer-adaptive Textual Conditioning combines these tokens differently as object queries evolve across decoder layers; and (iii) Presence-aware Confidence Supervision that jointly supervises query confidence and target presence for reliable predictions. With SAM3 frozen, RI-SAM3 optimizes around 12K parameters only per category and it efficiently segments each target in a single forward pass with reusable textual conditioning without per-sample reference-target visual matching. Extensive experiments over multiple widely adopted benchmarks show that RI-SAM3 achieves superior performance consistently in CD-FSS tasks, together with strong robustness, efficiency, and generalization.
Can Jin Rutgers University, Rui Wu, Tong Che NVIDIA, Qixin Zhang Nanyang Technological University, Hongwu Peng Adobe Research, Jiahui Zhao University of Connecticut, Zhenting Wang Mohamed bin Zayed University of Artificial Intelligence, Wenqi Wei Fordham University 等 13 位作者
Ensuring that Large Language Models (LLMs) adhere to safety principles without refusing benign requests remains a significant challenge. While OpenAI introduces deliberative alignment (DA) to enhance the safety of its o-series models through reasoning over detailed “code-like” safety rules, the effectiveness of this approach in open-source LLMs, which typically lack advanced reasoning capabilities, is understudied. In this work, we systematically evaluate the impact of explicitly specifying extensive safety codes versus demonstrating them through illustrative cases. We find that referencing explicit codes inconsistently improves harmlessness and systematically degrades helpfulness, whereas training on case-augmented simple codes yields more robust and generalized safety behaviors. By guiding LLMs with case-augmented reasoning instead of extensive code-like safety rules, we avoid rigid adherence to narrowly enumerated rules and enable broader adaptability. Building on these insights, we propose CADA, a case-augmented deliberative alignment method for LLMs utilizing reinforcement learning on self-generated safety reasoning chains. CADA effectively enhances harmlessness, improves robustness against attacks, and reduces over-refusal while preserving utility across diverse benchmarks, offering a practical alternative to rule-only DA for improving safety while maintaining helpfulness.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Jian Mu, Qixin Zhang Nanyang Technological University, Zhiyong Wang Chinese University of Hong Kong, Menglin Yang HKUST(GZ), Shuang Qiu City University of Hong Kong, Chengwei Qin The Hong Kong University of Science and Technology (Guangzhou), Zhongxiang Dai The Chinese University of Hong Kong, Shenzhen, Yao Shu The Hong Kong University of Science and Technology (Guangzhou)
Large language models (LLMs) increasingly solve complex reasoning tasks via long chain-of-thought, but their forward-only autoregressive generation process is fragile; early token errors can cascade, which creates a clear need for self-reflection mechanisms. However, existing self-reflection either performs revisions over full drafts or learns self-correction via expensive training, both fundamentally reactive and inefficient. To address this, we propose Self-Reflective Generation at Test Time (SRGen), a lightweight test-time framework that reflects before generating at uncertain points. During token generation, SRGen utilizes dynamic entropy thresholding to identify high-uncertainty tokens. For each identified token, it trains a specific corrective vector, which fully exploits the already generated context for a self-reflective generation to correct the token probability distribution. By retrospectively analyzing the partial output, this self-reflection enables more trustworthy decisions, thereby significantly reducing the probability of errors at highly uncertain points. Evaluated on challenging mathematical reasoning benchmarks and a diverse set of LLMs, SRGen can significantly strengthen model reasoning. Moreover, our findings position SRGen as a plug-and-play method that integrates reflection into the generation process for reliable LLM reasoning, achieving consistent gains with bounded overhead and can be combined with other training-time (e.g., RLHF) and test-time (e.g., SLOT) techniques.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表