论文检索

Social Aspects · Accountability, Transparency, and Interpretability

Biagio La Rosa, Leilani Gilpin

Compositional explanations are a family of methods that aim to describe the spatial alignment between neurons' receptive field activations and concepts through logical rules, typically computed via a search over all possible concept combinations. Since computing the spatial alignment over the entire state space is computationally infeasible, the literature commonly adopts beam search to restrict the space. However, beam search cannot provide any theoretical guarantees of optimality, and it remains unclear how close current explanations are to the true optimum. In this theoretical paper, we address this gap by introducing the first framework for computing guaranteed optimal compositional explanations. Specifically, we propose: (i) a decomposition that identifies the factors influencing the spatial alignment, (ii) a heuristic to estimate the alignment at any stage of the search, and (iii) the first algorithm that can compute optimal compositional explanations within a feasible time. Using this framework, we demonstrate that 10-40% of explanations previously obtained with beam search are suboptimal when overlapping concepts are involved. Finally, we evaluate a beam-search variant guided by our proposed decomposition and heuristic, showing that it matches or improves runtime over prior methods while offering greater flexibility in hyperparameters and computational resources.

Social Aspects · Privacy

Ahmed Mehdi Inane, Vincent Quirion, Gintare Karolina Dziugaite, Ioannis Mitliagkas

Noise-based certified machine unlearning currently faces a hard ceiling: the noise magnitude required to certify unlearning typically destroys model utility, particularly for large-scale deletion requests. While leveraging public data is a standard technique in differential privacy to relax this tension, its role in unlearning remains unexplored. We address this gap by introducing **Asymmetric Langevin Unlearning (ALU)**, a framework that uses public data to mitigate privacy costs. We prove that public data injection suppresses the unlearning cost by a factor of $O(1/n_{\mathrm{pub}}^2)$, guaranteeing a strict computational advantage over retraining. This establishes a new control mechanism: practitioners can mitigate the need for high noise—and the associated utility loss—by increasing the volume of public data. Crucially, we analyze the realistic setting of **distribution mismatch**, explicitly characterizing how shifts between public and private sources impact utility. We show that ALU enables "mass unlearning'' of constant dataset fractions -- a regime where standard symmetric methods become impractical -- while maintaining high utility. Empirical evaluations using variational Rényi divergence and membership inference attacks confirm that ALU effectively thwarts privacy attacks while preserving utility under reasonable distribution shifts.

Deep Learning · Large Language Models

Qingyao Li, Weiwen Liu, Weinan Zhang, Yong Yu, Bo An

Recent advancements in Large Language Models (LLMs) have successfully employed search-based strategies to enhance code generation. However, existing methods typically rely on static, sparse public test cases for verification, leading to pseudo-correctness—where solutions overfit the visible public tests but fail to generalize to hidden test cases. We argue that optimizing against a fixed, weak environment inherently limits robustness. To address this, we propose AdverMCTS, a novel adversarial Monte Carlo Tree Search framework that combats pseudo-correctness by coupling code search with active vulnerability discovery. AdverMCTS formulates generation as a minimax-style game between a Solver agent, which synthesizes code candidates, and an Attacker agent, which evolves to generate targeted test cases that exploit logical divergences in the current solution pool. These discovered tests form a dynamic, progressively hostile filter that penalizes fragile reasoning. Extensive experiments demonstrate that AdverMCTS significantly outperforms state-of-the-art baselines, effectively reducing false positive rates and forcing the model to generalize beyond the initial constraints. The resources of this work are available at https://anonymous.4open.science/r/AdverMCTS_open-A255.

Deep Learning · Generative Models and Autoencoders

Dong Hoon Lee, Seunghoon Hong

Latent Diffusion Models (LDMs) have become dominant in visual synthesis, but their quality–compute trade-off is largely constrained by the tokenizer’s fixed compression ratio. Variable-length tokenizers (VLTs) promise adaptive compression by varying token counts, allowing diffusion models to flexibly balance quality and compute. However, conventional VLTs modulate length by truncating ordered token sequences, which changes token semantics across lengths and breaks representational alignment. This leads to significant cross-length variation in the latent distribution that hinders a single variable-length diffusion model from operating effectively. To address this, we propose a novel variable-length tokenizer that modulates length by merging tokens. We show that encouraging similar tokens to merge enables direct cross-length representation alignment when the diffusion transformer operates according to the merging pattern. Since conventional merging methods are data-dependent, making the merging pattern inaccessible during generation, we introduce learnable global merging, which is data-independent, to ensure compatibility with diffusion transformers. On ImageNet 256$\times$256 generation, our merging-based variable-length tokenizer integrated with a diffusion transformer achieves a superior gFID–compute trade-off compared to prior VLT methods.

General Machine Learning · Causality

Kenneth Lee, Zihan Zhou, Murat Kocaoglu

Modern cloud systems rely on architectures with many interconnected microservices, which enable scalability and flexibility but make troubleshooting failures difficult. Identifying the root cause requires navigating complex dependencies, often beyond the capacity of domain experts. Causal models offer a principled approach to root cause analysis (RCA), but prior methods are typically sample inefficient, as they assume access to the full causal graph or require large numbers of post-failure interventions. We introduce Bayesian Root Cause Discovery (BRCD), which leverages a partial causal structure (a CPDAG learned during the pre-failure period) and performs Bayesian inference without enumerating all DAGs from each interventional Markov equivalence class ($\mathcal{I}$-MEC) for each root cause candidate. Using a recent uniform DAG sampling framework (Wienöbst et al., 2023), BRCD provides the first statistical consistency guarantees for nonparametric RCA, with both identifiability and finite-sample posterior bounds under $\varepsilon$-vanishing approximation. Empirically, across synthetic benchmarks and three microservice systems (Online Boutique, Sockshop, Petshop), BRCD achieves state-of-the-art top-$l$ accuracy while remaining effective in low-failure-sample regimes and scaling to large graphs.

Deep Learning · Theory

Yang Yang, Zhengmin Kong, Yuan Liu, Tao Huang, Wei Xiang

Modern neural networks derive much of their effectiveness from rich connectivity patterns. Yet, existing architectures often fix the topology at either the sparse or dense extremes, thereby limiting structural flexibility and analysis. We propose Kronecker Generative Networks (KGNs), an algebraic framework that constructs neural network topologies via recursive generation rules, treating topology as a first-class design object. KGNs generate families of directed acyclic graphs with controllable connectivity complexity, enabling systematic interpolation between sparse and dense aggregation regimes. Under this formulation, architectures such as FractalNet and DenseNet arise as specific instantiations corresponding to different generation rules. We provide theoretical analysis of acyclicity, connectivity scaling, and expressiveness, and demonstrate experimentally that KGN instantiations achieve favorable accuracy-efficiency trade-offs across multiple domains.

General Machine Learning · Clustering

Fan Yang, Haikun Xu

Incomplete multi-view clustering (IMVC) becomes particularly challenging under heavy missingness and view imbalance, where scarce co-observed pairs make cross-view correspondences unreliable: imputation-first pipelines can trigger cascading reconstruction errors, while purely consistency-based alignment often degrades sharply and offers limited control over semantic convergence across views. We propose \textbf{MAGIC} (Masked multi-p\textbf{A}th contrast with conf\textbf{I}dence-\textbf{G}ated semant\textbf{I}c imputation), a unified framework that learns calibrated cluster semantics before performing conservative completion. MAGIC instantiates multiple correlated representation and prediction paths from lightly augmented latent codes and couples them via a masked multi-path contrastive consensus objective with prediction-consistency regularization, yielding stable posteriors even when co-observations are scarce; these posteriors are then aggregated into view-wise soft assignments to reduce overconfidence and alleviate dominance by highly available views. Building on the calibrated semantics, MAGIC conducts similarity-guided semantic transfer in label space with confidence-aware gating and completes missing representations in a geometry-preserving manner, thereby mitigating error propagation under severe missingness. Extensive experiments on four benchmarks across a wide range of missing ratios demonstrate consistent improvements over prior IMVC methods, and ablations validate the complementary roles of masked multi-path consensus learning and confidence-gated semantic imputation.

Social Aspects · Fairness

David Troxell, Noah Roemer, Guido Montufar

Differentiable optimization layers are traditionally integrated in predict-then-optimize frameworks where a neural model estimates parameters that subsequently serve as fixed inputs to downstream decision-making optimization problems. In this work, we introduce the concept of a ``fairness layer'': a differentiable optimization layer appended to a model's output layer that guarantees a chosen notion of output parity is satisfied when integrated into a neural network. Additionally, we introduce an online primal-dual inference algorithm that provides provable aggregate fairness guarantees for streaming predictions with arbitrarily small batch sizes, where traditional per-batch constraints become overly restrictive. Numerical experiments demonstrate the effectiveness of the fairness layer and associated algorithm, and theoretical analysis characterizes the layer's differentiability and stability properties during model training and backpropagation. Our code for these experiments is publicly available on GitHub: https://github.com/anonymouspapersubmission012345/icml_2026_submission and our public Python package documentation can be found online: https://anonymouspapersubmission012345.github.io/fairness_training_anonymous/ .

Probabilistic Methods · Gaussian Processes

Donghyun Lee, Young Myoung Ko

Modeling the learning curve is critical for cost-effective data collection in deep learning systems. Most prior approaches assume a specific parametric learning curve, but these can be inappropriate when no reliable parametric form can be assumed for the learning curve. While Gaussian processes offer flexible nonparametric modeling, existing GP approaches that enforce monotonicity typically introduce intractable factors or require derivative observations. To address this, we propose a Monotonic Variational Gaussian Process for Efficient Data Collection (MOVE), which (i) introduces a novel monotonic variational GP formulation with virtual-derivative factors to enable tractable posterior inference, and (ii) develops an expected shortfall based objective for target-driven data collection. Furthermore, our theoretical analysis shows that expected shortfall provides non-vanishing gradient signals that enable reliable gradient-based optimization. Extensive experiments on classification, segmentation, and detection benchmarks demonstrate consistent improvements over the prior method.

Deep Learning · Generative Models and Autoencoders

Jiawei Zhang, Ziyuan Liu, Leon Yan, Zhenyu Xiao, Yuantao Gu

The distortion–perception (D–P) tradeoff is a fundamental phenomenon of Bayesian inverse problems, which characterizes the inherent tension between distortion performance and perceptual quality. Enabling flexible traversal of the D-P tradeoff at inference time is crucial for practical applications. Despite the recent success of diffusion models in zero-shot inverse problem solving, efficient and principled strategies for D-P traversal in diffusion-based inverse algorithms remain inadequately characterized. In this paper, we propose a stage-wise framework for realizing D-P traversal using a single diffusion model in zero-shot inverse problems. Our proposed method, termed MAP-RPS, starts with an MAP estimation stage that approximates the MMSE solution and provides a low-distortion initialization, followed by a re-noised posterior sampling stage that progressively improves perceptual quality. We provide theoretical analyses for both stages, establishing the validity and effectiveness of the proposed design. Furthermore, we extend MAP-RPS to the latent space, yielding LMAP-RPS, which enjoys broader applicability by leveraging large-scale pre-trained latent diffusion backbones. Extensive experiments demonstrate that MAP-RPS and LMAP-RPS enable more effective D-P traversal on various tasks, while also exhibiting strong performance as efficient solvers for real-world inverse problems.

Applications · Everything Else

Aurelien Ghiglino, Daniel Elenius, Anirban Roy, Ramneet Kaur, Manoj Acharya, Colin Samplawski, Brian Matejek, Susmit Jha, Juan Alonso, Adam Cobb

In this paper, we generate conceptual engineering designs of electric vertical take-off and landing (eVTOL) aircraft. We follow the paradigm of simulation-based inference (SBI), whereby we look to learn a posterior distribution over the full eVTOL design space. To learn this distribution, we must sample over discrete aircraft configurations (topologies) and their corresponding set of continuous parameters. Therefore, we introduce a hierarchical probabilistic model consisting of two diffusion models. The first model leverages recent work on Riemannian Diffusion Language Modeling (RDLM) and Unified World Models (UWMs) to enable us to sample topologies from a discrete and continuous space. For the second model we introduce a masked diffusion approach to sample the corresponding parameters conditioned on the topology. We show our approach successfully rediscovers known trends and captures governing physical laws in aircraft design.

Reinforcement Learning · Deep RL

Giorgi Butbaia, Paul Orland, Coco Huang, Davide Passaro, Lucas Fagan, Michele Tarquini, Hailong Dao, David Eisenbud, Ali Shehper, Sergei Gukov

Applying machine learning techniques to solving long-standing mathematical conjectures can be particularly challenging due to their extreme reward sparsity. As an illustrative example, we consider Kalai's algebraic Hirsch conjecture and recast the construction of its counterexamples as a sparse-reward reinforcement learning problem on graphs. We propose a constrained options-based HRL framework with an equivariant graph neural network policy, which allows us to learn useful temporal abstractions for this task. We evaluate our approach over a wide range of degrees and demonstrate that it consistently outperforms classical RL algorithms as well as greedy search. By exploiting the hierarchical structure of the problem, we effectively provide a first-of-its-kind application of HRL to a problem in commutative algebra.

Optimization · Large Scale, Parallel and Distributed

Nozomi Hata, Kenta Niwa

For communication-efficient decentralized learning, advanced network (NW) topologies, such as exponential and 1-peer exponential graphs, have been studied under homogeneous communication delays. However, real-world NWs exhibit heterogeneous communication delays, making node assignment optimization crucial for minimizing the Bottleneck Communication Delay (BCD). We propose BTSP-MSR, an approximate method for minimizing BCD on circulant digraphs, including exponential and 1-peer exponential graphs. Leveraging the fact that circulant digraphs can be viewed as a union of (directed) ring graphs, we derive an upper bound on the BCD by combining the ring-graph BCD (BTSP) with a deviation term (MSR). We then construct a solver that sequentially minimizes these two terms. Numerical experiments show that BTSP-MSR consistently reduces BCD across several circulant digraphs with large numbers of nodes. Notably, incorporating the exponential or 1-peer exponential graph enables communication-efficient decentralized learning under heterogeneous delay settings.

Applications · Language, Speech and Dialog

William Chen, Prem Seetharaman, Rithesh Kumar, Oriol Nieto, Shinji Watanabe, Justin Salamon, Zeyu Jin

Despite recent breakthroughs, audio foundation models struggle in processing complex multi-source acoustic scenes. We refer to this challenging domain as audio stories, which can have multiple speakers and background/foreground sound effects. Compared to traditional audio processing tasks, audio stories introduce new layers of semantic, temporal, and physical complexity. To address this challenge, we propose AudioChat, a framework for developing audio foundation models that can generate, edit, and understand audio stories. AudioChat introduces a new paradigm in which LLM-based toolcalling agents simulate interactions between users and the system, and these simulated dialogues are used as training data. We also introduce a novel Audio Transfusion Forcing objective to train the AudioChat model, allowing it to simultaneously decompose high-level instructions via structured chain-of-thought reasoning and perform interactive multi-turn audio understanding/generation. To evaluate generation and editing performance, we develop three new metrics that directly measure task performance instead of relying upon distribution-based scoring. We highly encourage readers to visit our demo to better understand the capabilities of AudioChat: https://audiochat-icml-2026.github.io/.

Deep Learning · Generative Models and Autoencoders

Zhan Tong, Tinne Tuytelaars

Latent diffusion models have become the dominant paradigm for video generation, making the video tokenizer a critical role. While most existing tokenizers are trained primarily for reconstruction, diffusion models are optimized to denoise heavily corrupted latents, which creates a mismatch between tokenizer training objectives and downstream generative learning. As a result, reconstruction metrics (e.g., rFVD) can be a poor proxy for generation quality (gFVD), and overly prioritizing reconstruction may even hinder diffusion training. We propose VideoMAETok, a simple family of ViT-based video tokenizers trained explicitly as corruption-inversion models for latent video diffusion. VideoMAETok builds on masked autoencoders: we (i) apply high-ratio token masking and encode only visible spatiotemporal tokens for efficiency, and (ii) corrupt latent tokens with interpolative Gaussian noise to better match the denoising nature of diffusion generators. Training under such corruption encourages latents that remain informative and well-conditioned for downstream denoising. Extensive experiments show that VideoMAETok consistently improves generation quality when paired with off-the-shelf diffusion models (SiT and LightningDiT), achieving state-of-the-art gFVD on Kinetics-600 and UCF-101 while remaining compute-efficient.

Reinforcement Learning · Deep RL

Lucas Fagan, Michele Tarquini, Ali Shehper, Maksymilian Manko, Angus Gruen, Coco Huang, Giorgi Butbaia, Davide Passaro, Sergei Gukov

Mathematical search problems present a unique challenge for Reinforcement Learning (RL) due to vast search spaces and sparse rewards. In previous works, the Andrews-Curtis (AC) conjecture was established as an illustrative example of such problems. In this work, we identify a critical structural barrier in the AC landscape: a "Two Hump" distribution, where problem instances are either trivially solvable or effectively impossible, with a scarcity of intermediate "hard-but-solvable" instances required for effective learning. We tackle this challenge through two primary avenues: novel data generation techniques to populate the difficulty gap, and significant algorithmic enhancements including the introduction of supermoves and Transformer-based architectures. We demonstrate substantial performance improvements over previous baselines, and release new comprehensive benchmark datasets including **AC-19** (125,192 AC-trivial presentations of varying difficulty with length at most 19) and **AC-1M** (1,136,154 hard AC-trivial presentations of length at most 30), the first large-scale, publicly available datasets of this kind.

General Machine Learning · Everything Else

Yaqian Zhang, Bernhard Pfahringer, Eibe Frank, Albert Bifet

Memory is a critical component in replay-based continual learning (CL). Prior research has largely treated CL memory as a monolithic store of past data, focusing on how to select and store representative past examples. However, this perspective overlooks the higher-level memory architecture that governs the interaction between old and new data. In this work, we identify and characterize a dual-memory system that is inherently present in both online and offline CL settings. This system comprises: a short-term memory, which temporarily buffers recent data for immediate model updates, and a long-term memory, which maintains a carefully curated subset of past experiences for future replay and consolidation. We propose \textit{memory capacity ratio} (MCR), the ratio between short-term memory and long-term memory capacities, to characterize online and offline CL. Based on this framework, we systematically investigate how MCR influences generalization, stability, and plasticity. Across diverse CL settings—class-incremental, task-incremental, and domain-incremental—and multiple data modalities (e.g., image and text classification), we observe that a smaller MCR, characteristic of \textit{online CL}, can yield comparable or even superior performance relative to a larger one, characteristic of \textit{offline CL}, when both are evaluated under equivalent computational and data storage budgets. This advantage holds consistently across several state-of-the-art replay strategies, such as ER, DER, and SCR. Theoretical analysis further reveals that a reduced MCR yields a better trade-off between stability and plasticity by lowering a bound on generalization error when learning from non-stationary data streams with limited memory. These findings offer new insights into the role of memory allocation in continual learning and underscore the underexplored potential of online CL approaches.

Deep Learning · Generative Models and Autoencoders

Yirong Shen, Lu GAN, Cong Ling

The choice of training objective is central to diffusion-based generative modeling in terms of both sample quality and distribution coverage. While standard maximum likelihood training provides a principled objective with strong theoretical grounding, empirical studies indicate that previous training objectives in diffusion models often face an inverse correlation between likelihood optimization and perceptual evaluations. We propose the Rényi diffusion model, a unified generative framework that formulates training objectives using Rényi divergence. This yields a generalized score matching objective providing explicit control over the trade-off between sample quality and distribution coverage. Experiments demonstrate improved balance between density estimation and sample generation performances across multiple datasets without modifying model architectures or sampling procedures.

Deep Learning · Graph Neural Networks

Danial Saber, Amirali Salehi-Abari

Graph Neural Networks (GNNs) suffer from overfitting and over-squashing of long-range information. Stochastic graph augmentations (e.g., edge deletion) regularize training against overfitting but can introduce train-inference misalignment and do not improve over-squashing. In contrast, rewiring methods improve connectivity to mitigate over-squashing, but are not designed to regularize training. We propose Random Add-Drop Edge (RADE), a stochastic graph augmentation method that jointly drops and adds edges to address both overfitting and over-squashing simultaneously. RADE is provably designed to align training and inference so that random augmentations regularize training without distribution shift, while supporting long-range communication at inference. We further propose and study a mini-batch gradient-norm balancing algorithm that adapts deletion and addition rates during training, rendering RADE hyperparameter-free in practice. Experiments on node- and graph-classification benchmarks show that RADE is a strong regularizer and mitigates over-squashing. Ablations support the roles of train-inference alignment, adaptive rate selection, and the complementary effects of random edge deletion and edge addition.

Theory · Online Learning and Bandits

Lixing Lyu, Jiashuo Jiang, Wang Chi Cheung

We study infinite-horizon discounted Markov decision processes (DMDPs) under a generative model. Motivated by the Algorithms with Advice framework (Mitzenmacher and Vassilvitskii, 2022), we propose a novel framework to investigate how black-box predictions of the transition matrix can enhance sample efficiency in solving DMDPs and improve sample complexity bounds. We focus on DMDPs with $N$ state–action pairs and discount factor $\gamma$. We first provide an impossibility result showing that, in the presence of predictions with unknown accuracy, no sampling policy can compute an $\epsilon$-optimal policy with a sample complexity better than $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, which matches the state-of-the-art minimax sample complexity bound without prediction. In complement, we design an algorithm based on minimax optimization techniques that leverages predictions of the transition matrix without requiring knowledge of the prediction error. Our algorithm achieves a sample complexity bound that depends on the prediction error and is uniformly better than $\tilde{O}((1-\gamma)^{-4} N \epsilon^{-2})$, the previous best result derived from convex optimization methods. In some cases, our bound even improves upon the state-of-the-art $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, despite not having access to the prediction quality.