论文检索

General Machine Learning · Scalable Algorithms

Peyman Afshani, Rezaul Chowdhury, Mayank Goswami, Jens Kristian R Schou, Francesco Silvestri, Mariafiore Tognon

It is known that RandomShuffle, the without replacement version of Stochastic Gradient Descend (SGD), converges faster than with-replacement SGD. However, RandomShuffle requires to uniformly perform a random permutation of the input sequence, which is known to have an high I/O complexity due to data movements over the memory hierarchy. In this paper, we propose a shuffling algorithm with a linear I/O complexity that generates almost-uniformly random permutations with rigorous mathematical guarantees. Specifically, we show that the shuffling algorithm can generate $2$-wise independent permutations. Furthermore, we can extend to $k$-wise independency with a small error in the probability distribution, if the fast memory has at least $k$ memory blocks. These results allow us to reach the same expected theoretical convergence as RandomShuffle while achieving optimal linear I/O cost.

General Machine Learning · Scalable Algorithms

DaeHun Nyang

Cosine similarity estimation is a core primitive in coarse-to-fine retrieval pipelines, where early-stage candidate selection relies on approximate similarity estimates whose errors are amplified downstream. Widely used sign-based sketches arising from extreme quantization of random projections exhibit a structural variance peak near $\theta$ $\approx$ 90$^\circ$, the near-background region where candidate selection is most difficult. We propose QA-Cos, a query-aware decoder-side estimator that departs from the Hamming-agreement paradigm, treating sign bits as probabilistic observations rather than deterministic votes. Across simulations and BEIR benchmarks, QA-Cos reduces estimation error by up to $\sim$15--20\% in the near-orthogonal region and translates these gains into improved candidate selection in two-stage ANN pipelines, improving Hit@K by up to $\sim$30 percentage points at fixed budgets and reducing candidates by up to $\sim$45--50\% at fixed recall.

General Machine Learning · Scalable Algorithms

Haoran Zhang, Dongjun Kim, Seohyeon Cha, Haris Vikalo

Federated LoRA provides a communication-efficient mechanism for fine-tuning large language models on decentralized data. In practice, however, a discrepancy between the factor-wise averaging used to preserve low rank and the mathematically correct aggregation of local updates can cause significant aggregation error and unstable training. We argue that a major source of this problem is *rotational misalignment*, arising from the rotational invariance of low-rank factorizations -- semantically equivalent updates can be represented in different latent subspaces across clients since $(B_i R_i)(R_i^\top A_i) = B_i A_i$. When such misaligned factors are averaged directly, they interfere destructively and degrade the global update. To address this issue, we propose **FedRot-LoRA**, a federated LoRA framework that aligns client updates via orthogonal transformations prior to aggregation. This alignment preserves the semantic update while reducing cross-client subspace mismatch, without increasing communication cost or restricting model expressivity. We provide a convergence analysis that examines the aggregation error induced by factor-wise averaging and shows how rotational alignment yields a tighter upper bound on this error. Extensive experiments on natural language understanding and generative tasks demonstrate that FedRot-LoRA consistently outperforms existing federated LoRA baselines across a range of heterogeneity levels and LoRA ranks. Code is available at https://anonymous.4open.science/r/FedRot-LoRA

General Machine Learning · Scalable Algorithms

Elias Jääsaari, Ville Hyvönen, Teemu Roos

Multi-vector representations generated by late interaction models, such as ColBERT, enable superior retrieval quality compared to single-vector representations in information retrieval applications. In multi-vector retrieval systems, both queries and documents are encoded using one embedding for each token, and similarity between queries and documents is measured by the MaxSim similarity measure. However, the improved recall of multi-vector retrieval comes at the expense of significantly increased latency. This necessitates designing efficient approximate nearest neighbor search (ANNS) algorithms for multi-vector search. In this work, we introduce LEMUR, a simple-yet-efficient framework for multi-vector similarity search. LEMUR consists of two consecutive problem reductions: We first formulate multi-vector similarity search as a supervised learning problem that can be solved using a one-hidden-layer neural network. Second, we reduce inference under this model to single-vector similarity search in its latent space, which enables the use of existing single-vector ANNS methods for speeding up retrieval. In addition to performance evaluation on ColBERTv2 embeddings, we evaluate LEMUR on embeddings generated by modern multi-vector text models and multi-vector visual document retrieval models. LEMUR is an order of magnitude faster than earlier multi-vector similarity search methods.

General Machine Learning · Evaluation

Jinyeop Song, Jeff Gore, Max Kleiman-Weiner

As language model (LM) agents become increasingly capable and adopted in real-world applications, there is a growing need for scalable evaluation frameworks beyond costly, manually-designed benchmarks. We propose information-theoretic evaluation based on empowerment, an information-theoretic measure of an agent's influence on future states through its actions. To handle the unique challenges of text-based environments, we introduce EELMA (Estimating Empowerment of Language Model Agents), an algorithm for approximating effective empowerment from multi-turn text interactions. We demonstrate EELMA on textual games and web-browsing scenarios, showing that empowerment strongly correlates with average task performance. We further analyze how empowerment varies across models, environment complexity, and agent configurations, and show that high-empowerment states and actions often mark pivotal moments for general capabilities. These results establish empowerment as a general-purpose metric for evaluating LM agents in open-ended settings. Code available: https://anonymous.4open.science/r/EELMA-E227

Probabilistic Methods · Variational Inference

Safa Messaoud, Skander Charni, Elaa Bouazza, Ali Pourghasemi, Halima Bensmail

Computing the differential entropy of distributions known only up to a normalization constant is a long-standing challenge with broad theoretical and practical significance. While variational inference is the most scalable approach for density approximation _from samples_, its potential in settings where _only the unnormalized density_ is available remains largely under-explored. The central difficulty lies in constructing variational distributions that simultaneously ($i$) exploit the structure of the unnormalized density, ($ii$) are expressive enough to capture complex target distributions, ($iii$) remain computationally tractable, and ($iv$) support efficient sampling. Recently, \citet{messaoud2024s} introduced _P-SVGD_, a particle-based variational method that leverages Stein Variational Gradient Descent dynamics, satisfies all of these constraints and demonstrates promising results in low-dimensional setups. We show, however, that _P-SVGD_ does not scale to high dimensions due to _fundamental algorithmic flaws_: ($i$) misdiagnosed sensitivity to \textit{SVGD} hyperparameters, ($ii$) violation of the global invertibility assumption in the entropy derivation, ($iii$) omission of a critical trace-of-Hessian term, ($iv$) along with suboptimal heuristics, including a divergence-based sampling check that induces mode collapse and loose informal bounds with no practical value. These issues severely limit both the correctness and the scalability of the approach. We propose _MET-SVGD_, a principled extension of _P-SVGD_ that addresses these flaws by providing a general framework for \textit{SVGD} hyperparameters selection with global invertibility and convergence guarantees. This enabled more accurate and scalable entropy estimation in high-dimensional settings. Empirically, in entropy estimation benchmarks, _MET-SVGD_ achieves accuracy improvements of up to 12$\times$ and 16$\times$ over _P-SVGD_ and baselines from the _SVGD_ literature, respectively. On CIFAR-10 Energy-Based image generation, it improves FID by $80.4$% compared to _P-SVGD_ and achieves 64$\times$ higher training stability. In Maximum-Entropy reinforcement learning, _MET-SVGD_ yields up to $16$% better returns than _P-SVGD_. We will make our code publicly available at https://tinyurl.com/2esyfx8j.

General Machine Learning · Scalable Algorithms

Celine Lee, Jing Nathan Yan, Chen Liang, Jiaxin Shi, Yin Zhang, Jeremiah Zhe Liu, Pengcheng Yin, Ed Chi, Fernando Pereira, Derek Cheng 等

Modern language models typically rely on two design choices: subword tokenization and autoregressive (AR) ordering. To achieve more universal modeling, the field is advancing toward byte-level modeling to bypass domain-specific vocabularies and masked diffusion models (MDM) to enable parallel non-sequential generation. Intuitively, the intersection of these paradigms represents a generative ideal: a modality-agnostic system capable of fine-grained any-order generation. However, the computational interaction between these granular representations and non-sequential objectives remains under-explored. In this work, we investigate the viability of this combination through a compute-matched scaling study. We observe a structural dichotomy: AR models on bytes effectively amortize the cost of tokenization, naturally rediscovering sub-word segmentation at scale. In contrast, byte-level MDMs suffer a non-convergent efficiency collapse. We attribute this disparity to the masking objective, which shatters the local contiguity required to resolve sub-word semantics from bytes, whereas AR's stable causal history preserves these essential local dependencies. Our findings inform the community of a critical efficiency tradeoff, suggesting that future modality-agnostic designs should address this context fragility to maintain efficient scaling.

Jiachen Liu

Spectral clustering, a widely-used technique for graph-based data partitioning, faces a severe computational bottleneck due to its $O(n^{3})$ time complexity. While anchor-based approximations reduce the complexity to $O(nm^{2})$ ($m \ll n$), they often yield degenerate solutions in the absence of explicit cluster-size control. To address this limitation, we propose \textbf{SC-FAGC (Size-Constrained Fast Anchor Graph Clustering)}, a unified formulation that integrates entropy regularization and bilateral cardinality constraints within an anchor-based spectral clustering framework. Our model simultaneously promotes cohesive clusters and enforces soft lower and upper bounds on cluster sizes, thus avoiding trivial or highly unbalanced partitions. To solve the resulting non-convex optimization problem efficiently, we develop an \textbf{Iteratively Re-weighted (IRW)} optimization scheme, which sequentially linearizes the objective and solves each subproblem via a \textbf{Double-Bounded Optimal Transport (DB-OT)} solver based on the \textbf{Sinkhorn--Knopp} algorithm. This approach guarantees convergence while maintaining scalability. Extensive experiments on benchmark datasets demonstrate that SC-FAGC consistently achieves state-of-the-art performance in terms of accuracy, purity, and recall, while strictly satisfying the prescribed cluster-size constraints. Thus the proposed method offers a principled and scalable solution for large-scale graph clustering with controllable partition structure.

Deep Learning · Algorithms

Seungil Lee, Gilha lee, Hyun Kim

Large-scale vision–language models (VLMs) excel at multimodal reasoning, yet efficiency collapses when vision tokens—often orders of magnitude more than text—dominate compute and memory. Prior token-reduction strategies typically trade off salience (which is prone to position bias and incurs extra computation) against diversity (which can under-cover salient regions and is sensitive to hyperparameters). We present SPLIT, a theoretically grounded framework that jointly preserves salience and diversity while aggressively eliminating redundancy. SPLIT (i) estimates token importance via temporal shifts of hidden states across layers—eschewing attention scores and their biases; (ii) assigns adaptive region-level budgets to guarantee localized coverage; and (iii) selects tokens using a diversity score that prioritizes distinctive, non-redundant representations. Our analysis shows that adaptive budgeting yields tighter coverage guarantees than uniform allocation, and our selection rule maintains diversity without costly tuning. Empirically, SPLIT consistently outperforms state-of-the-art on image and video understanding benchmarks. On image understanding with LLaVA-1.5-7B, SPLIT preserves over 99\% accuracy with 192 vision tokens and about 92.8\% with only 64 tokens, demonstrating robust performance under severe token budgets. These results indicate that SPLIT delivers scalable, attention-score-free token reduction that makes multimodal reasoning substantially more efficient without sacrificing accuracy.

Applications · Neuroscience, Cognitive Science

Junfeng Lu, Zijie Yu, SHAOYANG CUI, Gan He, Ruiqin Xiong, Kai Du, Tiejun Huang

Biophysically detailed neural networks represent a promising frontier for brain-inspired AI, offering intrinsic spatio-temporal dynamics to enhance the expressivity and computational density of deep learning systems. However, general-purpose deep learning frameworks suffer from a fundamental mismatch between their dense parallel optimizations and the irregular, tree-structured complexity of biological mechanisms. In this work, we propose **HelioX**, a **GPU-native** framework designed to unify high-performance simulation with scalable training. Unlike approaches that adapt biology to existing deep learning tools, HelioX adopts a "GPU-to-Biophysics" paradigm. We tailor the underlying GPU parallelism to biological structures by implementing custom-fused CUDA kernels for both the Dendritic Hierarchical Scheduling (DHS) algorithm and its gradient propagation. This design eliminates the runtime overhead of generic automatic differentiation and enables multi-stream concurrency for spike generation and equation assembly. Experimental results demonstrate that HelioX outperforms standard simulators (NEURON) by orders of magnitude and surpasses prior GPU-based solvers in both speed and scalability. We successfully train deep biophysical MLPs and organism-scale biophysical neural networks (e.g., the BAAIWorm C. elegans model) on a single consumer-grade GPU. HelioX establishes a new standard for computational efficiency, enabling the training of biophysically detailed models at scales previously unattainable.

Deep Learning · Algorithms

Keigo Nishida, Eren Mehmet KIRAL, Kenichi Bannai, Mohammad Emtiyaz Khan, Thomas Moellenhoff

We propose a new algorithm enabling stable training under low-precision computations. We call this algorithm Log-normal Multiplicative Dynamics (LMD), and derive it by taking inspiration from the robustness of biological neural networks. Such networks use synapses whose size follow log-normal distribution and whose fluctuations follow noisy multiplicative dynamics. There has been no scalable algorithm to train modern deep networks that incorporates all such synaptic properties. We are able to include them in LMD by using a variational formulation where a log-normal posterior distribution is used. We show several results that involve low-precision matrix multiplications in the forward passes. This includes results for training Vision Transformer and GPT-2 from scratch. Our findings suggest that biologically inspired multiplicative dynamics offer a promising direction for future energy-efficient hardware.

Applications · Social Sciences

Yan Zhuang, Junhao Yu, Bohou Zhang, Zachary Pardos, Jinze Wu, Daoqiang Zhang

Adaptive testing is widely adopted in AI-driven educational assessment systems (e.g., GRE), where the goal is to select an optimal subset of questions from a large question pool to accurately estimate an examinee's ability. A fundamental challenge is that: optimal question subsets are inherently personalized, and solving for them is NP-hard. Recently, it has been framed as a gradient matching problem: aligning gradients between selected subsets and the full question set across the entire ability parameter space. However, such global alignment on entire space is computationally expensive and difficult to scale. In this work, we propose GPM (Gradient Path Matching), a novel framework that instead aligns gradients along possible optimization paths toward the final estimate. By leveraging intermediate gradients as supervision, GPM learns an explicit and generalizable selection algorithm from large-scale data. We provide theoretical analysis on its convergence and scalability. Experiments on both real-world and synthetic datasets demonstrate that it achieves the same estimation accuracy using, on average, 20% fewer questions.

Probabilistic Methods · Variational Inference

Yuhang Xi, Yu-Feng Yu, Chuan-Xian Ren, Zhao-Rong Lai

Parameter-Efficient Fine-Tuning (PEFT) is essential for adapting Large Language Models, yet existing methods typically struggle to balance model capacity with computational efficiency. Standard approaches often enforce rigid low-rank constraints, while dynamic alternatives incur significant memory overheads. To resolve this dilemma, we propose Spectral Bridge Variational Inference (SBVI), a geometric framework that reformulates LoRA not as static parameter optimization, but as a continuous Wasserstein gradient flow on the manifold of Gaussian measures. Rather than fixing the rank at initialization, SBVI governs the singular value evolution via a stochastic differential equation driven by a thermodynamic competition between task gradients and adaptive entropic friction. This mechanism induces a spectral bifurcation that automatically prunes redundant noise modes while amplifying signal-rich components, naturally discovering a layer-wise optimal rank distribution. We derive a scalable algorithm with linear complexity using factorized Riemannian retractions and an Empirical Bayes friction update. Experiments on reasoning and coding benchmarks demonstrate that SBVI achieves state-of-the-art performance, offering superior accuracy and memory efficiency compared to existing static and dynamic adaptation methods.

Probabilistic Methods · Graphical Models

Leander Kurscheidt, Gabriele Masina, Roberto Sebastiani, Antonio Vergari

In many safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints, e.g., predicting the most likely trajectory that does not cross obstacles. These real-world constraints are rarely convex, nor the densities considered are (log-)concave. This makes computing this constrained maximum a posteriori (MAP) prediction in an efficient and reliable way extremely challenging. In this paper, we first investigate under which conditions we can perform constrained MAP inference over continuous variables exactly and efficiently and devise a scalable message-passing algorithm for this tractable fragment. Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions with numerical constrained optimization. We evaluate both methods on synthetic and real-world benchmarks, showing our structure aware approach outperforms constraint-agnostic baselines.

Applications · Robotics

Yibin Wang, Muhan Li, Zihan Guo, Sam Kriegman

In this paper, we introduce a model of evolution and learning in robots that co-optimizes a distribution of latent design vectors (genotypes) and a mixture of control experts (neural modules), which are gated by the latent coordinates of each decoded design (phenotype). This provides a scalable alternative to co-design algorithms that either train an individual policy for every robot, which is inefficient, or a monolithic universal controller for all robots, which results in overly conservative structures and behaviors. Our approach lies somewhere between these two extremes, preserving ancestral knowledge in a unified yet modular framework in which different body plans activate and deactivate different combinations of learned sensorimotor circuits for goal-directed behavior. This allows one part of the controller to be overhauled to better suit new species of designs as they emerge without disrupting the hard-earned knowledge contained within other expert modules. Pretrained expert policies can also be directly plugged into the mixture, providing a simple mechanism to indirectly steer evolution into areas of latent space containing desired morphological traits. We refer to this process as "evolution by demo" and use it to direct evolution toward the canonical form defined by the pretrained policy.

General Machine Learning · Scalable Algorithms

Nasib Ullah, Jinbin Zhang, Jean Lucien Randrianantenaina, Erik Schultheis, Rohit Babbar

Extreme multi-label classification (XMC) involves learning deep learning models over large output spaces with millions of labels, making the output layer of the network a major bottleneck in memory and compute. While sparsity-based methods reduce arithmetic complexity, they often fail to yield proportional wall-clock gains due to irregular memory access, poor hardware utilization, or reliance on auxiliary architectural components in extreme long-tailed regimes. We introduce group-shared fixed fan-in sparsity, a semi-structured output-layer design in which groups of semantically related labels share a common sparse input pattern while retaining independent weights. This grouping introduces a task-aligned inductive bias---encouraging related labels to attend to similar feature subsets---while simultaneously reducing index memory overhead, increasing feature reuse across labels, and enabling efficient GPU execution via custom CUDA kernels that leverage modern accelerator primitives. As an alternative to auxiliary objectives, we exploit the long-tailed structure of XMC datasets by decomposing the output layer into a small dense head over frequent labels and a group-shared sparse tail over the remainder, providing an informative gradient pathway while preserving the memory benefits of sparsity. Through kernel-level microbenchmarking, we show that group-shared fixed fan-in converts reductions in arithmetic complexity into proportional wall-clock gains, achieving up to $4.4\times$ speedup in the forward pass and up to $25\times$ speedup in backward passes compared to standard fixed fan-in sparsity, while operating within a few percent of a FLOPs-matched dense bottleneck. Across large-scale XMC benchmarks, our approach matches or improves precision@k compared to prior sparse baselines, while substantially narrowing the performance gap to dense.

Applications · Chemistry, Physics, and Earth Sciences

Jannis Becktepe, Aleksandra Franz, Nils Thuerey, Sebastian Peitz

Reinforcement learning (RL) has shown promising results in active flow control (AFC), yet progress in the field remains difficult to assess as existing studies rely on heterogeneous observation and actuation schemes, numerical setups, and evaluation protocols. Current AFC benchmarks attempt to address these issues but heavily rely on external computational fluid dynamics (CFD) solvers, are not fully differentiable, and provide limited 3D and multi-agent support. To overcome these limitations, we introduce FluidGym, the first standalone, fully differentiable benchmark suite for RL in AFC. Built entirely in PyTorch on top of the GPU-accelerated PICT solver, FluidGym runs in a single Python stack, requires no external CFD software, and provides standardized evaluation protocols. We present baseline results with PPO and SAC and release all environments, datasets, and trained models as public resources. FluidGym enables systematic comparison of control methods, establishes a scalable foundation for future research in learning-based flow control, and is available at https://anonymous.4open.science/r/fluidgym (anonymized mirror of our public repository).

Probabilistic Methods · Monte Carlo and Sampling Methods

Xiaoyu Wang, Jonathan Huggins

Stochastic gradient Langevin dynamics combined with Gibbs updates (SGLD-Gibbs) provides a highly scalable approach to approximate Bayesian inference in latent variable models. However, it remains unclear how to tune the algorithm's hyperparameters in a principled manner to ensure the uncertainty estimates are statistically meaningful. In this work, we address this gap in tuning guidance by developing a statistical scaling limit theory for SGLD-Gibbs. We derive a joint asymptotic limit for the global parameters and latent variables under appropriate space-time rescaling. We show that global parameters converge to a diffusion-type limit, while individual latent variables converge to a jump process reflecting their intermittent Gibbs updates. This joint jump-diffusion structure reveals how latent-variable randomness contributes to the stationary distribution of the global parameters. We leverage our results to provide explicit guidance on hyperparameter tuning for SGLD-Gibbs that ensures meaningful uncertainty quantification. Our empirical results show that SGLD-Gibbs with our tuning guidance leads to better parameter estimates and uncertainty quantification than stochastic variational inference.

Optimization · Discrete and Combinatorial Optimization

Ilay Yavlovich, Jad Agbaria, Jose Yallouz, Muhamed Mhamed, Nir Weinberger

The Linear Assignment Problem (LAP) is a fundamental combinatorial optimization task with applications ranging from computer vision to logistics. Classical exact solvers such as the Hungarian and Jonker--Volgenant (LAPJV) algorithms guarantee optimality, but their cubic time complexity $\mathcal{O}(N^3)$ becomes a bottleneck for large-scale instances. Recent learning-based approaches aim to replace these solvers with neural models, often sacrificing exactness or failing to scale due to memory constraints. We propose a *learning-augmented* framework that accelerates exact assignment solvers while maintaining optimality and worst-case guarantees. Our method predicts dual variables to warm-start a classical solver, with a fallback that prevents asymptotic runtime degradation when the learned advice is unreliable. We introduce **RowDualNet**, a lightweight row-independent architecture that avoids the $\mathcal{O}(N^2)$ memory bottleneck of graph-based models, enabling neural warm-starting at large scale ($N=16{,}384$). Feasibility is ensured via a constructive mechanism based on LP duality (namely, the *Min-Trick*), eliminating costly iterative projection. Empirically, our approach reduces the search effort of LAPJV and achieves over $2{\times}$ speedups on challenging synthetic distributions, in addition to improving over $1.25{\times}$ and $1.5{\times}$ on real-world tracking (MOT) and transportation (LPT) datasets, respectively, while strictly maintaining full optimality, effectively yielding a robust zero-shot generalization to real-world tasks.

Deep Learning · Large Language Models

xin tong, Baojiang cui

Personalized federated LoRA fine tuning has become a key approach to addressing data heterogeneity in distributed fine tuning of large language models (LLMs). Existing methods typically assume homogeneous personalization needs across clients, relying on dual LoRA or personalized calibration schemes. However, they fail to account for the heterogeneity of local personalization requirements and the conflicting optimization objectives in dual LoRA, limiting scalability and performance. To address this, we propose Het-CPFLoRA, a customizable heterogeneous federated LoRA fine tuning algorithm inspired by the decoupling properties of LoRA parameters. We employ a single adapter fine tuning scheme to mitigate conflicts between personalized and generalized optimization, decouple LoRA into generalized and personalized subspaces for local customization, and use SVD compression to integrate cross client generalized knowledge. During inference, we introduce an OOD oriented dynamic mechanism to adjust the weighting between personalized and generalized decoupling knowledge, improving performance on user data. Extensive experiments on two public benchmark datasets show that Het-CPFLoRA outperforms state of the art methods in both personalization and generalization across heterogeneous scenarios. The code will be released as an open-source project.