论文检索

Theory · Optimization

Sumaya Abdul Rahman, Seckhen Cuellar, Ghani Raissov, Mohammad Raza

Natural language interfaces can greatly benefit the accessibility and usability of optimization modeling, and recent advances in large language models (LLMs) show promise in automatically translating textual problem descriptions into executable solver formulations. However, a key challenge for existing approaches is to ensure that the inferred formulation correctly implements the intended task, even if it may execute without errors. We introduce \textsc{VeriSimpl}, a solver–LLM framework for robust natural-language-to-optimization formalization. Our approach is based on the idea of \emph{simplification-based verification}, where the optimization solver is leveraged to generate simplified diagnostic queries about a candidate formulation to allow the LLM to tractably reason about the correctness of the formulation with respect to the task description. We present such simplification strategies along different dimensions with respect to problem constraints and decision variables, which allow the LLM to reason locally under fixed global contexts. Evaluations on a range of optimization benchmarks show how our approach provides consistent improvements in accuracy over existing methods, while also providing a novel high-precision self-verification signal.

Optimization · Everything Else

Artem Artemev, Rui Xia, Benjamin M. Boyd, Youjing Yu, Felix Dangel, Guillaume Hennequin, Alberto Bernacchia

Many machine learning techniques rely on approximating a loss function's curvature, but this is notoriously hard to do at the scale of modern deep networks. Surprisingly, no previous work has exploited the curvature constraints that arise from well known weight-space symmetries in loss landscapes. By analytically averaging over group actions that leave the loss invariant, we construct structured Hessian approximations from single gradients that can be tractably estimated, stored, and inverted. The choice of user-specified symmetry group directly governs the trade-off between approximation accuracy and computational cost. Moreover, our framework provides a unifying theoretical lens for viewing existing methods; in particular, a specific choice of symmetry group recovers Shampoo/Muon-like curvature estimates. We validate our method on a range of network architectures, and deploy it to second-order optimization benchmarks, including a small language model. Our curvature estimation framework might find applications in other machine learning problems such as uncertainty estimation, continual learning, compression/pruning, training data attribution, and more.

Xinyou Wang, Liang Hong, Jiasheng Ye, Zaixiang Zheng, Shujian Huang, Quanquan Gu

Proteins are shaped by gradual evolution under biophysical and functional constraints. Protein language models learn rich evolutionary constraints from large-scale sequence data, and discrete diffusion–based protein language models (e.g., DPLMs) have emerged as a promising framework for both understanding and generation. However, existing DPLMs typically rely on masking-based absorbing diffusion, which conflicts with a basic biological intuition: proteins evolve through accumulated edits rather than emerging from masked tokens. As a result, these frameworks lack explicit pretraining objectives for substitution and insertion/deletion (indel) operations, which in turn limits both optimization-style post-editing and flexible guided generation. To address these limitations, we present DPLM-Evo, an evolutionary discrete diffusion framework that explicitly predicts substitution, insertion, and deletion operations during denoising. \method decouples a fixed-length latent alignment space from the variable-length observed sequence space, making indel-aware generation tractable and enabling adaptive scaffold growth throughout the process with negligible computational overhead. To further align substitutions with real evolutionary dynamics, we introduce a contextual evolutionary noising kernel that induces biologically informed, context-dependent mutation patterns. Across tasks, \method improves sequence understanding and achieves state-of-the-art performance on ProteinGym in the single-sequence setting, while also enabling variable-length simulated evolution, guided generation, and post-editing or optimization of existing proteins via explicit edit trajectories.

Theory · Everything Else

Alireza Jafari, Heman Shakeri, Hadi Daneshmand

Single-cell perturbation analysis aims to predict how cellular states change after interventions such as drug treatments or genetic edits. A central difficulty is that pre- and post-perturbation measurements are typically observed as *unpaired* populations, so accurate prediction requires inferring a latent coupling and learning a transition map. In this position paper, we argue that the *measurement time gap* is the key experimental knob controlling both the computational tractability of coupling and the effective model complexity. We identify a critical time gap $\Delta$ that induces a phase transition, under biologically inspired conditions; for "measurement-time $< \Delta$", matching is polynomial-time tractable and the task reduces to supervised learning, whereas for "measurement-time $>\Delta$", recovering the matching is NP-hard in the worst case. The required conditions are restricted isometry of the initial states and temporal smoothness of the transition dynamics. We complement the theory with empirical evidence on synthetic and biological datasets showing a sharp regime change as the time gap increases. Furthermore, we demonstrate that a linear model can match or exceed the performance of higher-capacity neural approaches when our conditions hold.

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.

Theory · Deep Learning

Nathanaël Haas, François Gatine, Augustin Cosse, Zied Bouraoui

Understanding why gradient-based training in deep networks exhibits strong implicit bias remains challenging, in part because tractable singular-value dynamics are typically available only for balanced deep linear models. We propose an alternative route based on two theoretically grounded and empirically testable signatures of deep Jacobians: depth-induced exponential scaling of ordered singular values and strong spectral separation. Adopting a fixed-gates view of piecewise-linear networks, where Jacobians reduce to products of masked linear maps within a single activation region, we prove the existence of Lyapunov exponents governing the top singular values at initialization, give closed-form expressions in a tractable masked model, and quantify finite-depth corrections. We further show that sufficiently strong separation forces singular-vector alignment in matrix products, yielding an approximately shared singular basis for intermediate Jacobians. Together, these results motivate an approximation regime in which singular-value dynamics become effectively decoupled, mirroring classical balanced deep-linear analyses without requiring balancing. Experiments in fixed-gates settings validate the predicted scaling, alignment, and resulting dynamics, supporting a mechanistic account of emergent low-rank Jacobian structure as a driver of implicit bias.

Probabilistic Methods · Everything Else

Kianoosh Ashouritaklimi, Stefano Cortinovis, Francois Caron

Bayes--assisted conformal prediction combines the strengths of Bayesian modelling with exact, distribution--free frequentist coverage guarantees. While validity holds even under model misspecification, the size of the prediction sets can degrade significantly when the prior is poorly aligned with the observed data. We address this limitation by introducing \textbf{RoBAS}: a novel Bayes--assisted nonconformity score which is motivated by a hierarchical Bayesian working model with heavy--tailed priors, and which we implement in practice via a computationally tractable empirical Bayes instantiation. Our proposed method is adaptive to the quality of the available working information in the prior. When reliable prior information is available and can be effectively encoded, we achieve set sizes lower than that of other sets with the same coverage. On the other hand, when such information is weak or inaccurate, our nonconformity scores revert to the Distance--To--Average score, a robust baseline that is well--suited to settings where accurate prior information is not available. We evaluate our method on tabular and image regression tasks in the setting where there exists distribution shift between the training and calibration/test data. We find that our approach is competitive with widely used nonconformity scores in the absence of distribution shift, while providing significant gains in the more challenging setting of distribution shift.

Deep Learning · Foundation Models

Anjie Liu, Ziqin Gong, Yan Song, Yuxiang Chen, Xiaolong Liu, Hengtong Lu, Kaike Zhang, Chen Wei, Jun Wang

Visual perception in modern Vision-Language Models (VLM) is constrained by a fundamental perceptual bandwidth bottleneck: a broad field-of-view inevitably sacrifices the fine-grained details necessary for complex reasoning. Inspired by the classical paradigms of active vision and information foraging, we frame overcoming this limitation as a sequential decision-making process. We formalise this process through the lens of the sequential Bayesian optimal experimental design (S-BOED) problem. While exact Bayesian inference is intractable in continuous gigapixel spaces, we derive principled yet tractable approximations that balance spatial coverage against resolution. To validate this framework, we present a training-free inference strategy as a practical instantiation of the S-BOED objective for agents equipped with multiple vision tools. Designed as a flexible template, this strategy accommodates arbitrary optimisation algorithms—ranging from efficient greedy sampling to look-ahead planning—to approximate the optimal design. Empirical evaluations on gigapixel-level benchmarks demonstrate that our approach further boosts the performance of state-of-the-art models, significantly outperforming standard baselines and effectively narrowing the gap toward human-annotated oracles.

Deep Learning · Large Language Models

Heng Zhao, Zilei Shao, Guy Van den Broeck, Zhe Zeng

Mixture-of-Experts (MoE) models scale by activating only a small subset of experts per token, but standard deterministic top-$k$ routing is non-differentiable and trained using surrogate gradients that ignore the discrete expert selection used at inference. We introduce SIMoE routing by modeling expert selection as a stochastic latent variable, casting it as probabilistic inference over discrete expert subsets under explicit cardinality constraints. First, we purpose SIMoE Exact-$k$ routing, which samples discrete $k$-expert subsets and propagates gradients through tractable inclusion probabilities for stochastic expert selection. We then extend this to SIMoE Dynamic-$k$ routing, where both training and inference constrain the routing cardinality to the same predefined range, allowing adaptive expert allocation per token. Across different benchmarks on OLMoE and Qwen MoE backbones, SIMoE Exact-$k$ improves expert utilization and routing diversity over competitive baselines, and Dynamic-$k$ achieves comparable performance with fewer activated experts.

Deep Learning · Graph Neural Networks

Lucas Gantes, Abele Mălan, Roberto Gheda, Robert Birke, Lydia Y. Chen

Hypergraphs are graph generalizations with key applications in domains such as healthcare, where strict data privacy requirements apply, or bioinformatics, where testing new compounds is costly. However, due to their combinatorial nature, hypergraph representations are often either intractable, or introduce major information loss. For this reason, research into hypergraph synthesis is limited, and state-of-the-art approaches yield poor generation quality in terms of overall structural patterns and graph-level validity. To address such shortcomings, we introduce SuperHype, an exact and tractable hypergraph diffusion model. The core of SuperHype is the projection of graph-superposition, a novel representation that embeds a hypergraph into a multilayer graph enabling a tractable representation with no loss of generalization. To generate new samples from such representations, we introduce a Graph-Superposition Transformer that treats the superposition as an interconnected sequence of layers. Moreover, we enhance the model’s performance with hypergraph specific auxiliary features and triplet aggregation of indirect node interactions. Our evaluation on five datasets shows that SuperHype generally reproduces local and global connectivity patterns with superior fidelity than state-of-the-art baselines.

John Sweeney

Predicting transferability within shared-output model families (e.g., LLMs that share a vocabulary) poses a dilemma: representation-similarity metrics can be uninformative without assumptions about error geometry, while update-geometry metrics are computationally prohibitive. We show that, in a shared-output head setting, representation metrics (e.g., CKA) are non-identifiable for transfer; models can share identical representations yet have orthogonal head updates, so CKA alone cannot reliably rank transfer. We make head Fisher alignment tractable at vocabulary scale ($K{=}128{,}256$) using FisherSketch, a streaming algorithm that compresses joint (activation, error) geometry to a 16KB task signature ($m{=}4096$) with a 192KB per-task streaming state. Beyond the head, we prove a full-network decomposition and bounds, and we propose measurable diagnostics (profile cosine and off-diagonal discrepancy). We validate these on ViT-B/16 and LLMs up to 70B, showing that head/block approximations track the full Fisher and that FisherSketch remains informative in fixed-prefix verbalizer-shift settings where activation similarity cannot distinguish tasks.

Deep Learning · Theory

Long HC Pham

Conditional flow matching has emerged as a powerful generative modeling framework that learns a vector field to transport an initial distribution toward a target data distribution. However, theoretical understanding of its out-of-distribution (OOD) performance under unseen conditions remains limited. In this work, we establish a rigorous geometric formulation to decompose the source of generalization error. We treat the conditional task as a map from the condition space to the Wasserstein space and derive a generalization bound under a coarse embedding assumption. The resulting decomposition separates OOD error into three tractable components: *Interpolation Sparsity*, *Geometric Distortion*, and *In-Distribution Fit*. Our empirical evaluation confirms that this framework demonstrates three key functions: (1) it acts as a diagnostic tool that tracks the dynamics of generalization during training; (2) it identifies dataset-specific failure modes (e.g., topological gaps, geometric instability); and (3) it enables mathematically motivated interventions that yield predictable gains by minimizing specific terms.

Probabilistic Methods · Gaussian Processes

Xiaoyu Jiang, Xinxing Shi, Sokratia Georgaka, Magnus Rattray, Mauricio Álvarez

Multi-Output Gaussian Processes (MOGPs) provide a principled probabilistic framework for modelling correlated outputs but face scalability bottlenecks when applied to datasets with high-dimensional output spaces. To maintain tractability, existing methods typically resort to restrictive assumptions, such as employing low-rank or sum-of-separable kernels, which can limit expressiveness. We propose the Transformed Latent Variable MOGP (T-LVMOGP), a novel framework that scales MOGPs to a massive number of outputs while preserving the capacity to capture meaningful inter-output dependencies. T-LVMOGP constructs a flexible multi-output deep kernel by mapping inputs and output-specific latent variables into an embedding space using a Lipschitz-regularised neural network. Combined with stochastic variational inference, our model effectively scales to high-dimensional output settings. Across diverse benchmarks, including climate modelling with over $10,000$ outputs and zero-inflated spatial transcriptomics data, T-LVMOGP outperforms baselines in both predictive accuracy and computational efficiency.

Deep Learning · Large Language Models

Zheng Chen, Weifeng Yang, Jianxiao Tang, Buhui Yao

Sparse Mixture-of-Experts (MoE) language models enable conditional computation but face deployment challenges due to the "memory wall": while few experts are activated per token, the entire model must reside in memory. Existing expert pruning methods primarily rely on independent ranking, failing to account for the complex inter-dependencies and redundancies between experts. In this paper, we formulate post-training MoE pruning as a reconstruction-driven subset selection problem, aiming to minimize layer-output distortion under a cardinality constraint. We introduce SCHUR-A*, an algorithm that leverages A* search to achieve globally optimal expert selection within each layer. To maintain computational tractability, we derive a novel, admissible heuristic upper bound using a Schur-complement-based relaxation of the reconstruction objective. This tight bound allows for aggressive pruning of the search space while mathematically guaranteeing optimality. Furthermore, we propose an automated strategy to balance fidelity and memory reduction across heterogeneous layers via knee-point detection. Extensive experiments on Qwen3-30B-A3B demonstrate that SCHUR-A* significantly outperforms greedy and ranking-based baselines, maintaining comparable performance even under aggressive pruning ratios.

Social Aspects · Accountability, Transparency, and Interpretability

Enrique Valero-Leal, Bernd Bischl, Pedro Larrañaga, Concha Bielza, Giuseppe Casalicchio

Group counterfactual explanations find a set of counterfactual instances to explain a group of input instances contrastively. However, existing methods either (i) optimize counterfactuals only for a fixed group and do not generalize to new group members, (ii) strictly rely on strong model assumptions (e.g., linearity) for tractability or/and (iii) poorly control the counterfactual group geometry distortion. We instead learn an explicit optimal transport map that sends any group instance to its counterfactual without re-optimization, minimizing the group's total transport cost. This enables generalization with fewer parameters, making it easier to interpret the common actionable recourse. For linear classifiers, we prove that functions representing group counterfactuals are derived via mathematical optimization, identifying the underlying convex optimization type (QP, QCQP, ...). Experiments show that they accurately generalize, preserve group geometry and incur only negligible additional transport cost compared to baseline methods. If model linearity cannot be exploited, our approach also significantly outperforms the baselines.

General Machine Learning · Evaluation

Kunvar Thaman

Reinforcement learning (RL) trained language model agents with tool access are increasingly deployed in coding assistants, research tools, and autonomous systems. We introduce the Reward Hacking Benchmark (RHB), a suite of multi-step tasks requiring sequential tool operations with naturalistic shortcut opportunities such as skipping verification steps, inferring answers from task-adjacent metadata, or tampering with evaluation-relevant functions. RHB supports independent and chained task regimes, where chain length acts as a proxy for longer-horizon agent behavior. We evaluate 13 frontier models from OpenAI, Anthropic, Google, and DeepSeek. Exploit rates range from 0\% (Claude Sonnet 4.5) to 13.9\% (DeepSeek-R1-Zero), varying sharply by post-training style. A controlled sibling comparison (DeepSeek-V3 vs. DeepSeek-R1-Zero) shows RL post-training is associated with substantially higher reward hacking (0.6\% vs. 13.9\%), with consistent gaps across all four task families. We identify six exploit categories and find that 72\% of reward hacking episodes include explicit chain-of-thought rationale, suggesting models often frame exploits as legitimate problem-solving. Simple environmental hardening reduces exploit rates by 88\% without degrading task success. Models with near-zero exploit rates on standard tasks show elevated rates on harder variants, suggesting production post-training suppresses reward hacking only below a complexity threshold where honest solutions remain tractable.

Theory · Game Theory

Mehryar Mohri, Jon Schneider, Yifan Wu

We focus on the problem of Answer-Level Fine-Tuning (ALFT), where the goal is to optimize a language model based on the correctness or properties of its final answers, rather than the specific reasoning traces used to produce them. Directly optimizing answer-level objectives is computationally intractable due to the need to marginalize over the vast space of latent reasoning paths. To overcome this, we propose a general game-theoretical framework that lifts the problem to a Distributional Alignment Game. We formulate ALFT as a two-player game between a Policy (the generator) and a Target (an auxiliary distribution). We prove that the Nash Equilibrium of this game corresponds exactly to the solution of the original answer-level optimization problem. This variational perspective transforms the intractable marginalization problem into a tractable projection problem. We demonstrate that this framework unifies recent approaches to diversity and self-improvement (coherence) and provide efficient algorithms compatible with Group Relative Policy Optimization (GRPO), yielding significant complexity gains in mathematical reasoning tasks.

Probabilistic Methods · Bayesian Models and Methods

Dongqing Li, Zheqiao Cheng, Geoff Nicholls, Quyu Kong

AI agents increasingly execute procedural workflows as sequential action traces, which obscures latent concurrency and induces repeated step-by-step reasoning. We introduce BPOP, a Bayesian framework that infers a latent dependency partial order from noisy linearized traces. BPOP models traces as stochastic linear extensions of an underlying graph and performs efficient MCMC inference via a tractable frontier-softmax likelihood that avoids \#P-hard marginalization over linear extensions. We evaluate on our open-sourced Cloud-IaC-6, a suite of cloud provisioning tasks with heterogeneous LLM-generated traces, and WFCommons scientific workflows. BPOP recovers dependency structure more accurately than trace-only and process-mining baselines, and the inferred graphs support a compiled executor that prunes irrelevant context, yielding substantial reductions in token usage and execution time.

Deep Learning · Robustness

Gabriel Afriat, Hussein Hazimeh, Dimitris Paparas, Rahul Mazumder

Pruning is a common approach to reduce the memory footprint and inference cost of large vision and language models. As these architectures continue to scale, one-shot pruning methods - i.e. approaches that prune the network without any retraining - have become increasingly attractive. Many popular one-shot pruning methods (e.g., WoodFisher, CAP, SparseGPT, and ALPS) typically optimize a quadratic objective under sparsity constraints. However, in practice, this objective is affected by multiple sources of uncertainty, including noise in the calibration data and variability introduced by algorithmic updates. To address these issues, we introduce RobOP, a robust optimization framework that explicitly accounts for such uncertainties. RobOP is modular and flexible, and can be applied with any existing pruning method through simple modifications motivated by our theoretical framework. We demonstrate that by taking into account uncertainty, RobOP offers improvements over prior pruning approaches. Our framework applies tractably across a range of stylized uncertainty sets, enabling robust one-shot pruning at scale.

Deep Learning · Generative Models and Autoencoders

Dhruvesh Patel, Benjamin Rozonoyer, Gaurav Pandey, Tahira Naseem, Ramón Astudillo, Andrew McCallum

In many domains generating variable length sequences through insertions provides greater flexibility over autoregressive models. However, the action space of insertion models is much larger than that of autoregressive models (ARMs) making the learning challenging. To address this, we incorporate trainable order dynamics into the target rates for discrete flow matching, and show that with suitable choices of parameterizations, joint training of the target order dynamics and the generator is tractable without the need for numerical simulation. As the generative insertion model, we use a variable length masked diffusion model, which generates by inserting and filling mask tokens. On graph traversal tasks for which a locally optimal insertion order is known, we explore the choices of parameterization empirically and demonstrate the trade-offs between flexibility, training stability and generation quality. On de novo small molecule generation, we find that the learned order dynamics leads to a significant increase in validity and quality of the generated molecules, when compared to uniform order dynamics.