论文检索

General Machine Learning · Clustering

Kenneth Clarkson, Lior Horesh, Takuya Ito, Charlotte Park, Parikshit Ram

Although transformers are most commonly optimized as statistical sequence models, it is unclear to what extent they can implement and learn exact algorithmic computations. Here, we specify a transformer implementation from first principles that executes a fundamental and widely used method for $k$-means clustering: Lloyd's algorithm. We theoretically prove and empirically demonstrate that this implementation of a transformer architecture, which we term the _$k$-means transformer_, exactly implements Lloyd's algorithm for $k$-means clustering using the standard circuit mechanisms of modern transformers: attention block, residual connections, and feed-forward block. In learning experiments, we find that training this base architecture on $k$-means clustering yields a generalizable clustering algorithm that surpasses Lloyd's algorithm in terms of clustering quality. Finally, we demonstrate that interpretable alterations (e.g., inclusion of layer normalizations) to this architecture yields diverse and novel variants of clustering algorithms, including soft $k$-means, spherical $k$-means, trimmed $k$-means. Overall, our results show that transformer circuit mechanisms can instantiate exact algorithmic routines for clustering, while simultaneously providing an effective learnable model.

Yujia Chen, Rui Sun, Zhaoyang Li, Wangkai Li, Huayu Mai, Bingzhou Wang, Aibing Li, Wenzhang SUN

Visual Contrastive Decoding (VCD) mitigates hallucinations in Multimodal Large Language Models (MLLMs) by penalizing the output shift from noise-perturbed images, assuming this shift captures the hallucination direction. We prove this assumption flawed: noise-induced drift in Language-Image Pretrained (LIP) encoders is a \emph{coupled vector} entangling (i) structural degradation from corrupted visual information with (ii) hallucination induction from linguistic prior activation. VCD's indiscriminate penalty inevitably suppresses valid visual semantics. Our key insight is that Self-Supervised Learning (SSL) encoders exhibit \emph{only} structural degradation under noise—geometrically orthogonal to hallucination paths—enabling principled disentanglement via LIP--SSL differential response. We propose \textbf{Disentangled Visual Rectification (DVR)}, a training-free dual-stream framework performing visual-layer rectification and decoding-layer contrast on purified representations. DVR achieves approximately $5\times$ theoretical error reduction over VCD and establishes SOTA performance on POPE, MME, LLaVA-Bench and CHAIR benchmarks.

Deep Learning · Attention Mechanisms

Zecheng Tang, Quantong Qiu, Yi Yang, Zhiyi Hong, Haiya Xiang, Kebin Liu, Qingqing Dang, Juntao Li, Min zhang

The quadratic complexity of standard attention mechanisms poses a significant scalability bottleneck for large language models (LLMs) in long-context scenarios. While hybrid attention strategies that combine sparse and full attention within a single model offer a viable solution, they typically employ static computation ratios (i.e., fixed proportions of sparse versus full attention) and fail to adapt to the varying sparsity sensitivities of downstream tasks during inference. To address this issue, we propose $\textit{\textbf{Elastic Attention}}$, which allows the model to dynamically adjust its overall sparsity based on the input. This is achieved by integrating a lightweight $\textit{\textbf{Attention Router}}$ into the existing pretrained model, which dynamically assigns each attention head to different computation modes. Within only 12 hours of training on 8$\times$A800 GPUs, our method enables models to achieve both strong performance and efficient inference. Experiments across three long-context benchmarks on widely-used LLMs demonstrate the superiority of our method.

Deep Learning · Algorithms

Jiaxiao Wang, Dachun Kai, Huyue Zhu, Quanquan Hu, Zhenyang Xu, Xiaoyan Sun

Reflection removal is a highly challenging problem. Though remarkable progress has been made, current methods primarily exploit static image priors from a single frame. Due to the inherent ambiguity between layers, existing methods still suffer from severe residual artifacts. In this paper, we propose leveraging event signals to break this ambiguity. By employing event cameras to capture micro-dynamics, we reveal the differential motion between the reflection and background layers. We thereby present a novel event-driven reflection removal network, EvReflection, that utilizes these dynamic cues for layer separation. Specifically, we design a Micro-Dynamics Decoupler to disentangle layer-specific motions from event streams as priors, which then guide a Parallax-Attention Rectifier to cleanly remove artifacts from the RGB image. Furthermore, to address the data shortage, we develop a physics-based simulation pipeline and construct the EVR$^2$ benchmark, the first real-world dataset for this task. Extensive experiments demonstrate that EvReflection significantly outperforms existing methods, recovering clean images in challenging real-world scenarios.

General Machine Learning · Methodology

Rui Ai, Yuqi Pan, David Simchi-Levi, Milind Tambe, Haifeng Xu

With the rapid progress of multi-agent large language model (LLM) reasoning, how to effectively aggregate answers from multiple LLMs has emerged as a fundamental challenge. Standard majority voting treats all answers equally, failing to consider latent heterogeneity and correlation across models. In this work, we design two new aggregation algorithms called Optimal Weight (OW) and Inverse Surprising Popularity (ISP), leveraging both first-order and second-order information. Our theoretical analysis shows these methods provably mitigate the inherent limitations of majority voting under mild assumptions, leading to more reliable collective decisions. We empirically validate our algorithms on synthetic datasets, popular LLM fine-tuning benchmarks such as UltraFeedback and MMLU, and a real-world healthcare setting ARMMAN. Our algorithms consistently outperform standard baselines, establishing a robust, training-free framework for effective multi-agent LLM aggregation.

Deep Learning · Large Language Models

Hongyeon Yu, Young-Bum Kim, Yoon Kim

LLM workflows, which coordinate structured calls to individual LLMs (each augmented with varying instructions and tools) to achieve a particular goal, offer a promising path towards extending the capabilities of LLMs and building powerful systems that can tackle diverse tasks. However, existing approaches for building such workflows generally rely on human-crafted pipelines and prompts, which presents a substantial bottleneck to widening the scope of their applications. How can automatically induce and optimize such workflows in a data-driven way? And can lessons from optimizing deep learning architectures help the design of workflow induction algorithms? This paper describes a simple approach for automatically inducing LLM workflows. We formulate workflow induction as a bilevel optimization problem: an outer loop which optimizes a high-level sketch of the workflow (in particular how the LLM calls should be structured), and an inner loop which optimizes each individual LLM call one-by one. Both loops are optimized with ``textual gradients'', where for the inner loop we optimize each component in a modular way through ``backpropagating'' textual gradients layer-by-layer. We find that LLM workflows discovered through our WIBOT (\textbf{w}orkflow \textbf{i}nduction through \textbf{b}ilevel \textbf{o}ptimization and \textbf{t}extual gradients) approach performs competitively against strong baselines that automate workflow generation and optimization.

Reinforcement Learning · Planning

Yuqi Pan, Davin Choo, Haichuan Wang, Milind Tambe, Alastair van Heerden, Cheryl Johnson

We study a sequential resource allocation problem motivated by adaptive network recruitment, in which a limited budget of identical resources must be allocated over multiple rounds to individuals with stochastic referral capacity. Successful referrals endogenously generate future decision opportunities while allocating additional resources to an individual exhibits diminishing returns. We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities. In the multi-round setting, the resulting Bellman recursion is intractable due to the stochastic, high-dimensional evolution of the frontier. To address this, we introduce a population-level surrogate value function that depends only on the remaining budget and frontier size. This surrogate enables an exact dynamic program via truncated probability generating functions, yielding a planning algorithm with polynomial complexity in the total budget. We further analyze robustness under model misspecification, proving a multi-round error bound that decomposes into a tight single-round frontier error and a population-level transition error. Finally, we evaluate our method on synthetic and real-world recruitment scenarios.

General Machine Learning · Clustering

Fangfang Li, Quanxue Gao, Xingyu Xue

Manifold clustering has demonstrated strong capability in capturing complex data structures and has been widely studied in cluster analysis. However, many existing methods mainly focus on combining K-means with manifold learning, while overlooking the consistency between data structures and clustering labels, and often suffer from high computational cost when handling large scale data. To address these issues, we propose a manifold balanced clustering method based on anchor induced distance(LMBC), grounded in the relationship between K-means clustering and manifold learning. Specifically, the LMBC uses label information to guide the construction of the manifold structure, thereby ensuring consistency between data structures and clustering labels. To enable large scale clustering, we introduce an anchor induced distance representation that models manifold structure in a compact anchor space, significantly reducing computational complexity while preserving essential structural information. Furthermore, to naturally maintain class balance during clustering, we maximize the Schatten-p norm of the label representation and provide theoretical analysis to support its effectiveness. Experimental results on several benchmark datasets demonstrate the effectiveness and scalability of the proposed method.

General Machine Learning · Methodology

Eric Bridgeford, Hayden Helm

Generative models augmented with external tools and update mechanisms (or \textit{agents}) have demonstrated capabilities beyond intelligent prompting of base models. As agent use proliferates, dynamic multi-agent systems have naturally emerged. Recent work has investigated the theoretical and empirical properties of low-dimensional representations of agents based on query responses at a single time point. This paper introduces the Temporal Data Kernel Perspective Space (TDKPS), which jointly embeds agents across time, and proposes several novel hypothesis tests for detecting behavioral change at the agent- and group-level in black-box multi-agent systems. We characterize the empirical properties of our proposed tests, including their sensitivity to key hyperparameters, in simulations motivated by a multi-agent system of evolving digital personas. Finally, we demonstrate via natural experiment that our proposed tests detect changes that correlate sensitively, specifically, and significantly with a real exogenous event. TDKPS is the first principled framework for monitoring behavioral dynamics in black-box multi-agent systems - a critical capability as generative agent deployment continues to scale.

Applications · Robotics

Pengteng Li, Weiyu Guo, He ZHANG, Tiefu Cai, Xiao He, Yandong Guo, Hui Xiong

We introduce SOMA, the Spatial Memory framework for Out-of-Vision Manipulation in Vision-Language-Action (VLA) models. Most existing VLAs implicitly assume that task-relevant objects are always visible, leading to brittle and reactive behaviors when targets fall outside the camera’s field of view. SOMA addresses this limitation by equipping VLAs with a persistent spatial memory constructed from multi-view observations acquired via a movable head camera, enabling reasoning beyond the current visual frustum. The framework consists of three components: Spatial Memory Construction, which aggregates angular-wise observations into a unified spatial–semantic representation through scanning; Dynamic Memory Refinement, which maintains global consistency over time; and Contextual Memory Retrieval, which activates instruction-relevant spatial cues during manipulation. We evaluate SOMA on five challenging real-world out-of-vision manipulation tasks, including multi-step and dual-arm scenarios where target objects are initially invisible. Experimental results show that SOMA not only improves task success rates, but also induces qualitatively different manipulation behaviors, with faster target localization, reduced viewpoint search, and near one-shot grasping under partial observability. Additional experiments on RoboCasa GR1 and SimplerEnv further validate the effectiveness of SOMA’s memory design under conventional fully observable settings.

Reinforcement Learning · Everything Else

Yuetian Wang, Dianxi Shi, Yuanze Wang, Huanhuan Yang, Shiming Song, Chunping Qiu

Safe reinforcement learning (Safe RL) seeks to optimize long-term performance while ensuring adherence to safety constraints. However, most existing approaches address safety in a simplified manner, typically by linearly combining rewards and costs, which provides limited guidance when safety and performance interact in complex, nonlinear ways. We present USB-RL (Unsupervised Score-Balanced Reinforcement Learning), a model-based framework that learns implicit safety–performance preferences directly from experience. Our approach infers a monotone partial-order score through unsupervised pairwise comparisons of long-horizon outcomes, capturing nuanced trade-offs without relying on manually tuned cost weights. The learned score guides model-based policy optimization by dynamically balancing safety and performance, enabling flexible and adaptive multi-step planning in imagination-based control. Across diverse safety benchmarks, USB-RL achieves strong returns while substantially reducing safety violations, demonstrating stable and interpretable safety–performance trade-offs.

General Machine Learning · Sequential, Network, and Time Series Modeling

Beinan Xu, Andy Song, Jiti Gao, Feng Liu

We introduce Equilibrium State Estimation (ESE), a novel paradigm for simultaneous prediction, where multiple interacting systems require separate yet coordinated forecasts. Such scenarios often arise in real-world such as economics and healthcare modeling. Unlike existing approaches that predict one system at a time, ESE forecasts all systems in a single pass. It first estimates the equilibrium state across systems, then generates holistic forecasts based on the difference between the current state and the estimated equilibrium. Extensive experiments on synthetic and real-world datasets, including currency exchange and COVID-19 spread modeling, demonstrate that ESE is at least as accurate as state-of-the-art (SOTA) methods while being significantly faster. In addition, ESE integrates seamlessly with conventional predictors, combining their accuracy with its exceptional efficiency and delivering a 10–70× speedup. With linear-time complexity, ESE scales far better than SOTA methods as the number of systems increases. Moreover, it remains accurate under diverse perturbations, establishing ESE as a fast, generalizable, robust, and scalable multi-prediction method. Source code and data are available at https://anonymous.4open.science/r/ESE-C339.

Theory · Learning Theory

Leonardo Defilippis, FLORENT KRZAKALA, Bruno Loureiro, Antoine Maillard

Understanding when learning is statistically possible yet computationally hard is a central challenge in high-dimensional statistics. In this work, we investigate this question in the context of single- and multi-index models, classes of functions widely studied as benchmarks to probe the ability of machine learning methods to discover features in high-dimensional data. Our main contribution is to show that a Noise Sensitivity Exponent (NSE)—a simple quantity determined by the activation function—governs the existence and magnitude of statistical-to-computational gaps within a broad regime of these models. We first establish that, in single-index models with large additive noise, the onset of a computational bottleneck is fully characterized by the NSE. We then demonstrate that the same exponent controls a statistical-computational gap in the specialization transition of large separable multi-index models, where individual components become learnable. Taken together, our results identify the NSE as a unifying property linking noise robustness, computational hardness, and feature specialization in high-dimensional learning.

General Machine Learning · Causality

Yuxi Du, Zhiheng Zhang, Haoxuan Li, Cong Fang, Jixing Xu, Zhen Peng, Jiecheng Guo

Causal inference in modern large-scale systems faces growing challenges, including high-dimensional covariates, multi-valued treatments, massive observational (OBS) data, and limited randomized controlled trial (RCT) samples due to cost constraints. We formalize treatment-induced structural non-overlap and show that, under this regime, commonly used weighted fusion methods provably fail to satisfy randomized identifying restrictions.To address this issue,we propose a constrained joint estimation framework that minimizes observational risk while enforcing causal validity through orthogonal experimental moment conditions. We further show that structural non-overlap creates a feasibility obstruction for moment enforcement in the original covariate space.We also derive a penalized primal–dual algorithm that jointly learns representations and predictors, and establish oracle inequalities decomposing error into overlap recovery, moment violation, and statistical terms.Extensive synthetic experiments demonstrate robust performance under varying degrees of non-overlap. A large-scale ride-hailing application shows that our method achieves substantial gains over existing baselines, matching the performance of models trained with significantly more RCT data.

General Machine Learning · Causality

YiXin Ren, Hongquan Liu, Juncai Zhang, Yewei Xia, Zichuan Lin, Deheng Ye, Hao Zhang, Jihong Guan, Shuigeng Zhou

In this paper, we present a novel federated independence testing method that addresses both theoretical and practical challenges arising from client heterogeneity. We begin by revisiting existing federated independence testing methods and showing why they fail to provide valid guarantees or maintain statistical power under data distributional shift across clients. Building on this analysis, we develop a copula-based marginal alignment technique together with a stacking-based aggregation strategy that amplifies intra-client dependence while mitigating inter-client variation, resulting in a theoretically sound and powerful global test. For practicality, we further accelerate the aggregation step and incorporate a privacy-preserving mechanism. On the theoretical side, we prove both the correctness of our method and the validity of the test. Empirically, we conduct extensive experiments on both synthetic and real-world datasets, which demonstrate the superiority of our solution over existing methods.

Xinyi He, Qian Liu, Mingzhe Du, Lin Yan, ZhiJie Fan, Yiming Huang, Yin Zheng, Zejian Yuan, Zejun MA

Code performance optimization is paramount in real-world software engineering and critical for production-level systems. While Large Language Models (LLMs) have demonstrated impressive capabilities in code generation and bug fixing, their proficiency in enhancing code performance at the repository level remains largely unexplored. To address this gap, we introduce SWE-Perf, the first benchmark specifically designed to systematically evaluate LLMs on code performance optimization tasks within authentic repository contexts. SWE-Perf comprises 140 carefully curated instances, each derived from performance-improving pull requests from popular GitHub repositories. Each benchmark instance includes the relevant codebase, target functions, performance-related tests, expert-authored patches, and executable environments. Through a comprehensive evaluation of representative methods that span file-level and repo-level approaches (e.g., Agentless and OpenHands), we reveal a substantial capability gap between existing LLMs and expert-level optimization performance, highlighting critical research opportunities in this emerging field.

Deep Learning · Generative Models and Autoencoders

Hyoseok Lee, Sohwi Lim, Eunju Cha, Tae-Hyun Oh

While latent diffusion models (LDMs) have emerged as powerful priors for inverse problems, existing LDM-based solvers frequently suffer from instability. In this work, we first identify the instability as a discrepancy between the solver dynamics and stable reverse diffusion dynamics learned by the diffusion model, and show that reducing this gap stabilizes the solver. Building on this, we introduce *Measurement-Consistent Langevin Corrector (MCLC)*, a theoretically grounded plug-and-play stabilization module that remedies the LDM-based inverse problem solvers through measurement-consistent Langevin updates. Compared to prior approaches that rely on linear manifold assumptions, which often fail to hold in latent space, MCLC provides a principled stabilization mechanism, leading to more stable and reliable behavior in latent space.

General Machine Learning · Causality

Yi Wan, Xin Wang, Huanhuan Chen

In domains such as healthcare and marketing, learning optimal individualized dosing policies to maximize utility is crucial, yet high experimental costs impose strict budget constraints, necessitating efficient active policy learning. Existing active learning methods in causal inference primarily focus on binary treatments and effect estimation, leaving continuous dosing and policy optimization underexplored. To address this gap, we propose an active learning framework tailored for optimal policy learning. Exploiting the inherent structure of dose-response curves, we theoretically show that the policy optimization regret is bounded by the expected posterior gradient variance at the estimated optimal doses. Motivated by this result, we introduce Gradient Variance Active Learning for Individualized Dosing (GVALID), a batch acquisition strategy that greedily selects samples to minimize target gradient variance for efficient policy learning. Experiments demonstrate that GVALID achieves superior performance under strict budget constraints.

General Machine Learning · Causality

Robert Ganian, Marlene Gründel, Simon Wietheger

Pearl’s Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formulas is computationally intractable in almost all classical settings. We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability. Our results include fixed-parameter and XP-algorithms for satisfiability in key probabilistic and counterfactual fragments, using parameters such as primal treewidth and the number of variables, together with matching hardness results that map the limits of tractability. Technically, we depart from the dynamic programming paradigm typically employed for treewidth-based algorithms and instead exploit structural characterizations of well-formed causal models, providing a new algorithmic toolkit for causal reasoning.

Applications · Social Sciences

Kunal Pradeep Pimparkhede, Chirayu Chaurasia, Jatin Roy, Mahesh Mohan Mohanachandran Radhamany

Responsible investing aims to generate positive impact across Environment (E), Society (S), and Governance (G), and rating companies along these dimensions is now widespread, making ESG scores highly popular. Allocating retail capital with sustainability in mind could be transformational, yet it remains unclear how individual investors can do so in practice. Current ESG solutions cannot model high-dimensional, multi-modal time series capturing the joint evolution of ESG risks, financial returns, news, and sentiment, even though this domain requires jointly reasoning over distinct numerical signals where both numerical proximity and semantic type must be preserved. To bridge this gap, we introduce a novel domain-aware $\textbf{representation learning framework}$ that learns geometry-preserving representations for heterogeneous time series using value-aware tokens with block-wise $\textbf{orthogonal embeddings}$. To capture trajectory-level structure, we introduce $\textbf{FACET}$ tokens and train the model using a geometry-preserving loss. The resulting model jointly learns to forecast future values and to organize entities in a representation space that reflects their temporal evolution. Trained on ESG, returns, news, and sentiment, the domain-aware LLM learns a representation space that enables accurate ESG forecasting, trajectory-based grouping, and latent-space search for superior asset selection and downstream application like portfolio rebalancing