论文检索

Theory · Reinforcement Learning and Planning

Wanqiao Xu, Allen Nie, Ruijie Zheng, Aditya Modi, Adith Swaminathan, Ching-An Cheng

Interactively learning from observation and language feedback is an increasingly studied area driven by the emergence of large language model (LLM) agents. While impressive empirical demonstrations have been shown, so far a principled framing of these decision problems remains lacking. In this paper, we formalize the Learning from Language Feedback (LLF) problem, assert sufficient assumptions to enable learning despite latent rewards, and introduce *transfer eluder dimension* as a measure to characterize the hardness of LLF problems. We formalize the intuition that information in the feedback governs the learning complexity of LLF problems. We demonstrate cases where learning from rich language feedback can be exponentially faster than learning from reward. We develop a no-regret algorithm, called `HELiX`, that provably solves LLF problems through sequential interactions, with performance guarantees that scale with the transfer eluder dimension of the problem. Across several empirical domains, we show that `HELiX` performs well even when repeatedly prompting LLMs does not work reliably. Our contributions mark an important step towards designing principled interactive learning algorithms from generic language feedback.

Deep Learning · Large Language Models

Xuanfei Ren, Allen Nie, Tengyang Xie, Ching-An Cheng

Optimizing complex systems, ranging from LLM prompts to multi-turn agents, traditionally requires labor-intensive manual iteration. We formalize this challenge as a stochastic generative optimization problem where a generative language model acts as the optimizer, guided by numerical rewards and text feedback. We introduce Prioritized Optimization with Local Contextual Aggregation (POLCA), a scalable framework designed to handle stochasticity in optimization—such as noisy feedback, sampling minibatches, and stochastic system behaviors—while effectively managing the unconstrained expansion of solution space. POLCA maintains a priority queue to manage the exploration-exploitation tradeoff, systematically tracking candidate solutions and their evaluation histories. To enhance efficiency, we integrate an $\varepsilon$-Net mechanism to maintain parameter diversity and an LLM Summarizer to perform meta-learning across historical trials. We evaluate our framework on diverse benchmarks, including $\tau$-bench (agent optimization), VeriBench (code translation) and KernelBench (CUDA kernel generation). Experimental results demonstrate that POLCA achieves robust, sample and time-efficient performance, consistently outperforming state-of-the-art algorithms in both deterministic and stochastic problems.

Applications · Neuroscience, Cognitive Science

Zhe Jiao, Xiaodong He, Shanglin Zhou

While heavy-tailed synaptic weight distributions are pervasive in biological neural networks, their computational role---particularly in relation to generalization---remains poorly understood. To address this, we develop a novel optimal-transport-based optimization algorithm that incorporates key biological constraints, including Dale’s principle and heavy-tailed synaptic statistics, to train recurrent neural networks (RNNs) on a wide range of cognitive tasks. We show that these biologically constrained, heavy-tailed RNNs exhibit substantially improved generalization, which we further characterize within a PAC-Bayes framework. Our theoretical analysis and numerical experiments reveal two complementary mechanisms underlying this generalization enhancement. Topologically, heavy-tailed connectivity induces an effectively low-rank structure, which in turn yields low-dimensional neural dynamics. Geometrically, heavy-tailed connectivity intrinsically shapes task variable representations to lie near a linear manifold, thereby improving generalization for a linear readout strategy. Together, these results identify heavy-tailed connectivity as a biologically grounded intrinsic mechanism that promotes low-rank structure and favorable representational geometry, leading to improved generalization in flexible cognitive tasks.

Jie Jiang, Ke Cheng, Xin Xu, Mengyang Pang, Xinzhe Xu, Jiaheng Li, Yue Liu, Yuan Wang, Jun Zhang, Huan Yu 等

Generative sequence modeling faces a fundamental tension between the expressivity of Transformers and the efficiency of linear sequence models. Existing efficient architectures are theoretically bounded by shallow, single-step linear updates, while powerful iterative methods like Test-Time Training (TTT) break hardware parallelism due to state-dependent gradients. We propose PRISM (Parallel Residual Iterative Sequence Model) to resolve this tension. PRISM introduces a solver-inspired inductive bias that captures key structural properties of multi-step refinement in a parallelizable form. We employ a Write-Forget Decoupling strategy that isolates non-linearity within the injection operator. To bypass the serial dependency of explicit solvers, PRISM utilizes a two-stage proxy architecture: a short-convolution anchors the initial residual using local history energy, while a learned predictor estimates the refinement updates directly from the input. This design distills structural patterns associated with iterative correction into a parallelizable feedforward operator. Theoretically, we prove that this formulation achieves Rank-$L$ accumulation, structurally expanding the update manifold beyond the single-step Rank-$1$ bottleneck. Empirically, it achieves comparable performance to explicit optimization methods while achieving \textbf{174x higher throughput}. Codes are available in \href{https://anonymous.4open.science/r/msir-F607/}{anonymous.4open.science}.

Optimization · Discrete and Combinatorial Optimization

Rongsheng Jia, Yifan Zhang, Jun Zhang, Jian Cheng

Recent decomposition-based approaches have achieved significant success in Multi-Objective Combinatorial Optimization (MOCO). However,existing methods typically rely exclusively on node-centric representations, failing to capture the complementary representations provided by edge features for problem instances, resulting in a persistent optimality gap. To address this , we propose a Preference-Modulated Structural Attention mechanism to enhance problem representation by synergizing node and edge features. It includes: (1) Utilizing preference-modulated edge features as explicit structural biases during attention calculation, enabling model to perceive sub-problem structures conditioned on specific preferences,and (2) an edge feature aggregation strategy that dynamically incorporates node-specific context into edge representations to enhance the perception of preference-aware structures. Experiments on classic MOCOP benchmarks demonstrate the superiority of our approach in terms of both performance and generalization capabilities.

Social Aspects · Alignment

Mohammad Anas Jawad, Cornelia Caragea

Existing calibration methods for Large Language Models (LLMs) often overlook a critical dimension of trustworthiness: a model's {\em behavioral robustness} to irrelevant or misleading information. In this paper, we argue that a model's true confidence should reflect its stability under cognitive pressure. We introduce \textsc{CaliDist}, a novel, post-hoc calibration approach that directly measures and penalizes a model's susceptibility to distraction. \textsc{CaliDist} quantifies how an LLM's predictions and uncertainty change when its input prompt is perturbed with semantic \textit{distractors}. This stability (or lack thereof) signal is then used to adaptively scale the model's initial confidence score. Our extensive experiments on seven Natural Language Understanding (NLU) classification benchmarks using six distinct LLMs show that \textsc{CaliDist} consistently achieves lower Expected Calibration Error (ECE) and Brier Score compared with strong baselines. Remarkably, our method reduces the ECE from 19\% to 11\% on average—a relative improvement of 47\%—demonstrating that behavioral stability is a powerful and practical signal for calibration.

Deep Learning · Generative Models and Autoencoders

Jean Pachebat

Standard generative models struggle with heavy-tailed data: Lipschitz architectures cannot produce power-law tails from Gaussian noise, and interpolating between heavy-tailed data and Gaussians is ill-posed. We propose a simple fix: apply the soft-log transform $\phi(x) = \mathrm{sign}(x) \cdot \log(1 + |x|)$ to data before training, then exponentiate samples after generation. This compresses heavy tails into a range where standard flow matching succeeds. The approach requires no tail parameter estimation, no heavy-tailed base distributions, and no architectural modifications. We provide theoretical intuition for why this works: the log-transform maps Pareto tails to exponentials, and the induced dynamics implement a form of tail annealing via power transformations. Experiments on synthetic benchmarks and real financial data show that this simple trick achieves competitive sample quality for heavy-tailed distributions ($\nu \leq 5$), with improved stability over specialized methods in moderate dimensions ($d = 50$).

Deep Learning · Algorithms

Sucheng Ren, Chen Chen, Zhenbang Wang, Liangchen Song, Xiangxin Zhu, Yinfei Yang, Jiasen Lu

Conventional practice assumes that online reinforcement learning for flow-matching models requires sampling full denoising trajectories to compute rewards. This assumption underlies methods such as Group Relative Policy Optimization (GRPO), where the policy must traverse the entire reverse process before receiving a delayed, trajectory-level reward. We observe, however, that while such terminal rewards provide feedback, they are neither necessary nor optimal for effective learning. In this work, we introduce iGRPO (Instant-reward GRPO), which replaces GRPO's full-trajectory rollouts with a single-step mapping that assigns rewards instantly at each denoising step. Because the flow matching model behaves differently across timesteps, our step-local instant rewards which are inherently time-dependent, overcome prior approaches that rely on a single, time-independent terminal reward. By evaluating each action locally rather than relying on a final terminal score, iGRPO eliminates the need for multi-step SDE rollouts and offers more precise credit assignment. Across standard benchmarks, iGRPO converges 10.2× faster than FlowGRPO while achieving higher final alignment quality. We hope this work motivates more efficient and scalable online RL methods for flow-matching generative models.

Theory · Game Theory

Yiting Hu, Lingjie Duan

Continual learning (CL), where a model is trained on a sequence of data tasks, is increasingly being adopted across key fields such as large language models and image recognition, yet it remains highly vulnerable to data poisoning that triggers learning divergence or severe generalization loss. Despite these threats, a principled theoretical foundation in CL for understanding attack and defense remains lacking. In this paper, we develop a theoretical framework to analyze strategic attacks and defenses in regularization-based CL, a cornerstone of recent CL theory. By framing the adversary-defender interaction as an online zero-sum game, we first establish a fundamental performance limit: no defense succeeds when an adversary poisons a linear proportion of tasks via adding unbounded noise or pattern shifts in regularization-based CL. We then analyze two possibly denfensible scenarios: infrequent attacks and bounded noise per attack. For the former regime, we propose a task-to-task verification mechanism to detect data poisoning and reduce cumulative bias for learning convergence. For the latter regime, we derive a robust defense that minimizes the model’s sensitivity to poisoned features, provably accelerating the convergence rate. Extensive experiments on realistic tasks further validate our theoretical results.

Social Aspects · Privacy

Yiting Hu, Lingjie Duan, Qian Zhang

Machine unlearning aims to eliminate the influence of specific data from trained models to safeguard privacy. However, this presents a significant challenge in the context of continual learning (CL), where models update sequentially on dynamic datasets. A major limitation is that current certified unlearning algorithms fail to account for the complex, cumulative model evolution inherent to CL framework. In this work, we establish the first theoretical foundation bridging CL and machine unlearning. We formulate the CL's unlearning objective as the minimization of post-unlearning excess risk, which decomposes into CL excess risk and unlearning loss, characterizing the fundamental trade-off between preserving historical knowledge and targeted forgetting. Under mild assumptions, we first establish an upper bound for the CL excess risk in non-convex models. We then adapt two certified unlearning approaches, gradient-based and Hessian-based, to the CL framework. Our analysis reveals that while the gradient-based approach is less effective than the Hessian-based method in minimizing unlearning loss, it offers the distinct advantage of nearly zero storage overhead for enabling unlearning. This insight inspire us for a combination strategy to minimize storage costs while maintaining post-unlearning performance. Experimental results further validate our theoretical findings.

General Machine Learning · Evaluation

Valerie Chen, Rohit Malhotra, Xingyao Wang, Juan Michelini, Xuhui Zhou, Aditya Bharat Soni, Hoang Tran, Calvin Smith, Ameet Talwalkar, Graham Neubig

While benchmarks measure the accuracy of LLM-powered agents, they mostly assume full automation, failing to represent the collaborative nature of real-world use cases. In this paper, we make two major steps towards the rigorous assessment of human-agent interactions. First, we propose PULSE, a framework for more efficient human-centric evaluation of agent designs, which comprises collecting user feedback, training an ML model to predict user satisfaction, and computing results by combining human satisfaction ratings with model-generated pseudo-labels. Second, we deploy PULSE n software engineering---one of the highest-impact, real-world domains for LLM agents---via a large-scale web platform built around the open-source agent OpenHands. Across 15k users, we evaluate how three agent design decisions impact developer satisfaction rates. We also show how PULSE can lead to more robust conclusions about agent design, reducing confidence intervals by 40% compared to a standard A/B test. Finally, we find substantial discrepancies between in-the-wild results with benchmark performance (e.g., the anti-correlation between claude-sonnet-4 and gpt-5, underscoring the limitations of benchmark-driven evaluation. Our framework PULSE provides guidance for future evaluations, and our findings identify opportunities for better software agent designs.

Deep Learning · Robustness

Jiaqi Tang, Jianmin Chen, Youyang Zhai, Wei Wei, Runtao Liu, Mengjie Zhao, Xiangyu Wu, Qingfa Xiao, Qifeng Chen

Multimodal Large Language Models (MLLMs) have demonstrated remarkable success in visual understanding, yet their performance degrades significantly under real-world visual corruptions. While existing robustness enhancement approaches exist, they are limited: black-box feature alignment lacks interpretability, and white-box text-based reasoning cannot restore lost pixel-level details. This work investigates a fundamental research question: Can MLLMs recover corrupted visual content by themselves? To address this, we propose Robust-U1, a novel framework that equips MLLMs with explicit visual self-recovery capability for robust understanding. The approach comprises three core stages: supervised fine-tuning for initial reconstruction, reinforcement learning with dual rewards (pixel-level SSIM and semantic-level CLIP similarity) for aligning high visual quality, and multimodal reasoning that jointly considers both the corrupted input and the recovered image. Extensive experiments demonstrate that Robust-U1 achieves state-of-the-art robustness on the real-world corruption benchmark (R-Bench) and maintains superior performance under adversarial corruptions on general VQA benchmarks (MMMB, MMStar, RealWorldQA). Analysis confirms that high-quality visual recovery directly enhances reasoning performance, establishing self-recovery as a critical mechanism for robust visual understanding. Code, demo, and models will be open-sourced soon.

Reinforcement Learning · Deep RL

Ibne Farabi Shihab, SANJEDA AKTER, Anuj Sharma

Sparse-reward reinforcement learning typically focuses on exploration, but we ask: can structural assumptions about reward functions themselves accelerate learning? We introduce Policy-Aware Matrix Completion (PAMC), which exploits low-rank structure in reward matrices while correcting for policy-induced sampling bias. PAMC combines three key components: a low-rank plus sparse reward model, inverse propensity weighting to handle Missing-Not-At-Random (MNAR) data, and confidence-gated abstention that falls back to intrinsic exploration when uncertain. We provide finite-sample theory showing that completion error scales as $O(\sigma\sqrt{r(|\mathcal{S}|+|\mathcal{A}|)/\text{ESS}})$ where ESS is the effective sample size under policy overlap $\kappa$. PAMC achieves strong empirical results at 10M steps (a sample-efficiency comparison): 4100$\pm$250 return vs. 200$\pm$50 for DrQ-v2 on Montezuma's Revenge, 78\% vs. 65\% success rate on MetaWorld-50, and 15\% improvement over CQL on D4RL datasets. The method maintains 8\% computational overhead while providing calibrated confidence intervals (95\% empirical coverage). When structural assumptions are violated, PAMC gracefully degrades through increased abstention rather than catastrophic failure. Our approach demonstrates that reward structure exploitation can complement traditional exploration methods in sparse-reward domains.

General Machine Learning · Transfer, Multitask and Meta-learning

HuiYu Yi, Xu Zhiming, Dunwei Tu, Zhicheng Wang, Baile Xu, Furao Shen

The Nearest Class Mean (NCM) classifier is widely favored in Class-Incremental Learning (CIL) for its superior resistance to catastrophic forgetting compared to Fully Connected layers. While Neural Collapse (NC) theory supports NCM's optimality by assuming features collapse into single points, non-linear feature drift and insufficient training in CIL often prevent this ideal state. Consequently, classes manifest as complex manifolds rather than collapsed points, rendering the single-point NCM suboptimal. To address this, we propose Hierarchical-Cluster SOINN (HC-SOINN), a novel classifier that captures the topological structure of these manifolds via a ``local-to-global'' representation. Furthermore, we introduce Structure-Topology Alignment via Residuals (STAR) method, which employs a fine-grained pointwise trajectory tracking mechanism to actively deform the learned topology, allowing it to adapt precisely to complex non-linear feature drift. Theoretical analysis and Procrustes distance experiments validate our framework's resilience to manifold deformations. We integrated HC-SOINN into seven state-of-the-art methods by replacing their original classifiers, achieving consistent improvements that highlight the effectiveness and robustness of our approach. Code is available at \url{https://anonymous.4open.science/r/icml2026-9B60}.

Theory · Everything Else

Franz Nowak, Reda Boumasmoud, Ryan Cotterell

Recent progress in language model reasoning capabilities has revived a classic goal: characterizing which algorithms such systems can implement, or equivalently, which formal languages they can recognize. A growing research program studies RNNs, LSTMs, SSMs, and related architectures via reductions to finite-state automata and regular languages. Yet many results are not well-posed: they rely on implicit or incompatible semantic assumptions, invoking associativity and real-arithmetic techniques while also assuming floating-point arithmetic, which is finite and non-associative. Moreover, many proofs are highly architecture-specific and hard to transfer across closely related models. We address these issues with a unifying algebraic framework for a broad class of RNN language models, formally translating them to wreath products of transformation semigroups. By separating universal algebraic structure from contingent choices such as numerical semantics and wiring, the framework yields a disciplined workflow for rigorous expressivity analysis under realistic assumptions. We illustrate its value by rederiving and correcting representative expressivity claims from the literature under explicit deterministic finite-precision semantics.

Deep Learning · Large Language Models

Yan Wang, Chang Si, Kaiming Yang, Zhipeng Zhang, Weijian Liu, Man Yuan, Mingzhen Li, Yong Li, Weile Jia

Multi-token prediction (MTP) architecture is widely adopted in LLMs. MTP blocks can be appended to the tail of model to predict additional tokens. However, when training with pipeline parallel, MTP leads to more pipeline bubbles and deteriorates the pipeline efficiency. Based on in-depth analysis of MTP architectures and loss functions, we have identified the parallel nature of the MTP blocks, and leverage it for superior pipeline scheduling. We propose AdaHC, an adaptive pipeline scheduling framework for accelerating LLMs training with MTP block(s). AdaHC splits the output heads into chunks and reassembles the chunks to generate balanced pipeline stages, and performs adaptive activation forwarding to preserve the numerical equivalence. Experimental results show that AdaHC improves the training throughput of SOTA LLMs with diverse MTP configurations by 1.35$\times$ on average. This work paves a new direction for practical pipeline training.

Deep Learning · Large Language Models

Pingjie Wang, Hongcheng Liu, Yusheng Liao, Ziqing Fan, Yaxin Du, shuo tang, Yanfeng Wang, Yu Wang

Adapting large language models (LLMs) to low-resource domains remains challenging due to the scarcity of domain-specific data. While in-domain data is limited, there exists a vast amount of general-domain data that shares similar question–answer formats and reasoning patterns with domain tasks. This observation raises an important question: can useful general-domain data be mined to improve low-resource domain adaptation? Our initial findings show that general-domain chain-of-thought data contains useful auxiliary signals for domain adaptation, even without careful selection. This observation motivates a new paradigm for domain adaptation beyond exclusive reliance on domain-specific data. To systematically identify the most beneficial general-domain samples, we propose NTK-Selector, motivated by the Neural Tangent Kernel’s ability to capture alignment in training dynamics. Since directly applying NTK to pretrained LLMs is impractical, we introduce a Jacobian-free NTK approximation and empirically demonstrate stable NTK-like behavior during fine-tuning. Extensive experiments across medical, financial, legal, and psychological domains demonstrate that NTK-Selector consistently outperforms domain-only fine-tuning and existing data selection baselines. In particular, NTK-Selector achieves gains of +8.7 and +5.1 points on Llama3-8B-Instruct and Qwen3-8B, respectively, compared to only +0.8 and +0.9 points from domain-only fine-tuning.

Deep Learning · Large Language Models

Yuhan Liu, Yixiong Zou, Yuhua Li, Ruixuan Li

Referring Expression Segmentation (RES) aims to generate pixel-wise segmentation masks from complex and implicit textual queries. While recent advances in Multimodal Large Language Models (MLLMs) have substantially boosted RES performance, their prohibitive computational overhead remains a critical bottleneck, which, however, is rarely explored. To fill this gap, we first evaluate typical token compression methods on this task and observe a surprising performance degradation. In this paper, we aim to understand this phenomenon for a solution. By extensive experiments, we find that token compression for RES requires preserving the original position embeddings and local neighboring spatial structures, indicating that visual token position information is far more critical than in other tasks. Building on this insight, we ask: Can we design the token compression method purely based on the position information? Therefore, we propose PAYN, a plug-and-play, training-free token compression method that relies solely on position information. PAYN retains tokens that are adequately distributed in every local neighboring region while strictly preserving original positional indices, thereby maintaining spatial relational consistency. Experiments on multiple RES benchmarks demonstrate that our method outperforms existing token compression methods, verifying that position is indeed all you need for token compression in the MLLM-based RES task. Codes will be released.

Social Aspects · Safety

Joonhyuk Baek, Wonjune Seo, Jae-yun Kim, Saerom Park, Hoki Kim

Despite the proliferation of proactive defenses against deepfakes, the lack of a unified evaluation protocol precludes fair comparison and masks critical vulnerabilities. To bridge this gap, we present the first comprehensive benchmark that systematically assesses disruption, robustness, and transferability encompassing pixel, perceptual, and identity metrics. Our extensive analysis reveals that fidelity and identity metrics capture orthogonal performance axes, often leading to conflicting interpretations when relied upon individually. Furthermore, we identify a fundamental trade-off where peak white-box performance signals overfitting, and we introduce a calibrated evaluation to correct generator-induced identity bias. By exposing these blind spots, we establish a rigorous standard to guide the development of genuinely generalizable protections.

Applications · Chemistry, Physics, and Earth Sciences

Martin Jankowiak, Yerdos Ordabayev, Rudraksh Tuwani, Henry Ward, Hunter Nisonoff, James McFarland, Gevorg Grigoryan

Despite its importance to applications in protein design, predicting protein properties like binding affinity and thermostability from sparse experimental data remains a significant challenge. Accordingly, we introduce a class of sequence kernels that exploit evolutionary substitution matrices as well as local linearity and demonstrate that the resulting Gaussian processes provide data-efficient models of protein property landscapes, frequently outperforming alternatives that rely on foundation model embeddings. Furthermore--by learning what are in effect structure-aware substitution matrices--we show that our kernels can readily incorporate structural information from foundation models. We demonstrate that these structure-conditioned kernels are well suited to multi-task learning across multiple protein property landscapes and can decisively outperform local supervised learning methods.