ICML 2026 Papers

Relational Deep Learning aims to learn directly on multi-table databases, yet current methods face a fundamental tension: Transformers' quadratic complexity prohibits the large contexts relational data demands, while GNNs sacrifice global context for efficiency. We introduce Ramba, the first selective state-space model for relational databases. Our approach features two innovations: (1) Topology-Aware Linearization, which processes cells via global columnar serialization in O(L) complexity while recovering relational structure through sparse entity and foreign-key attention masks; and (2) Schema Dynamic Gating, which modulates SSM state transitions based on semantic alignment between the currently scanned attribute and the prediction target, enabling cross-table relevance filtering without relying on value distributions. Together, these enable Ramba to ingest vast relational contexts while selectively retaining semantically relevant information, a combination existing architectures cannot achieve. Experiments demonstrate state-of-the-art performance with linear scalability across diverse relational benchmarks.

Natural Language Querying for Time Series Databases (NLQ4TSDB) aims to assist non-expert users retrieve meaningful events, intervals, and summaries from massive temporal records. However, existing Text-to-SQL methods are not designed for continuous morphological intents such as shapes or anomalies, while time series models struggle to handle ultra-long histories. To address these challenges, we propose Sonar-TS, a neuro-symbolic framework that tackles NLQ4TSDB via a "Search-Then-Verify" pipeline. Analogous to active sonar, it utilizes a feature index to "ping'' candidate windows via SQL, followed by generated Python programs to "lock on'' and verify candidates against raw signals. To enable effective evaluation, we introduce NLQTSBench, the first large-scale benchmark designed for NLQ over TSDB-scale histories. Our experiments highlight the unique challenges within this domain and demonstrate that Sonar-TS effectively navigates complex temporal queries where traditional methods fail. This work presents the first systematic study of NLQ4TSDB, offering a general framework and evaluation standard to facilitate future research.

Identifying training data of large-scale models is critical for copyright litigation, privacy auditing, and ensuring fair evaluation. However, existing works typically treat this task as an instance-wise identification without controlling the error rate of the identified set, which cannot provide statistically reliable evidence. In this work, we formalize training data identification as a set-level inference problem and propose Provable Training Data Identification (PTDI), a distribution-free approach that enables provable and strict false identification rate control. Specifically, our method computes conformal p-values for each data point using a set of known unseen data and then develops a novel Jackknife-corrected Beta boundary (JKBB) estimator to estimate the training-data proportion of the test set, which allows us to scale these p-values. By applying the Benjamini–Hochberg (BH) procedure to the scaled p-values, we select a subset of data points with provable and strict false identification control. Extensive experiments across various models and datasets demonstrate that PTDI achieves higher power than prior methods while strictly controlling the FIR.

Generalized Bayesian Inference (GBI) tempers a loss with a temperature $\beta>0$ to mitigate overconfidence and improve robustness under model misspecification, but existing GBI methods typically rely on costly MCMC or SDE-based samplers and must be re-run for each new dataset and each $\beta$-value. We give the first fully amortized variational approximation for the specific case of the tempered posterior family $p_\beta(\theta\mid x) \propto \pi(\theta)p(x \mid\\theta)^\beta$ by training a single $(x,\beta)$-conditioned neural posterior estimator $q_\phi(\theta \mid x, \beta)$ that enables sampling in a single forward pass, without simulator calls or inference-time MCMC. We introduce two complementary training routes: (i) synthesizes off-manifold samples $(\theta, x) \sim \pi(\theta)p(x \mid \theta)^\beta$ and (ii) reweights a fixed base dataset $\pi(\theta)p(x \mid \theta)$ using self-normalized importance sampling (SNIS), where we show that the SNIS-weighted objective provides a consistent forward-KL fit to the tempered posterior with finite weight variance. Across four standard simulation-based inference (SBI) benchmarks—including the chaotic Lorenz–96 system—our $\beta$-amortized estimator achieves competitive posterior approximations, in standard two-sample metrics, with non-amortized MCMC-based power-posterior samplers over a wide range of temperatures.

While diffusion models enable new approaches for estimating Local Intrinsic Dimension (LID), existing methods fail in high-dimensional spaces where noise from vast normal directions overwhelms the tangent signal. We propose Local Hessian Spectral Dimension (LHSD), which resolves this by applying spectral filtering to the log-density Hessian, explicitly cutting off large eigenvalues associated with normal directions to count zero-curvature tangent directions. Implemented using Stochastic Lanczos Quadrature (SLQ), LHSD avoids full Hessian construction, achieving linear scalability with dimension $D$. Experiments on synthetic and real data confirm LHSD’s superior robustness and its utility in detecting memorization in large-scale diffusion models.

LLM pre-training efficacy increasingly depends on data composition rather than sheer volume. Yet, optimal mixing is hindered by categorization flaws: human taxonomies suffer from ontological misalignment, and Euclidean clustering fails to address embedding anisotropy. We introduce **GEM** (**G**eometric **E**ntropy **M**ixing), a framework reformulating data curation as a variational problem on the hypersphere augmented with a **mixing-balance regularizer**. By decoupling the generative prior and optimizing the objective via a provable **MM (Minorize-Maximize)** algorithm, GEM effectively counteracts the cluster collapse to discover balanced semantic structures invisible to Euclidean heuristics. We employ teacher-student distillation to scale this geometric fidelity to web-scale corpora and introduce the **Geometric Influence Score (GIS)** for interpretable taxonomy generation. Experiments with 1.1B-parameter models demonstrate that GEM establishes a new state-of-the-art when integrated into mixing strategies like DoReMi and RegMix, improving average downstream accuracy by up to **1.2%** and offering a robust coordinate system for predictable data mixing.

Nonnegative matrix factorization (NMF) seeks a low-rank approximation $X \approx UV^T$ with nonnegative factors and is commonly solved using *interior* methods that enforce feasibility throughout optimization. We show that such constraint-driven approaches can impede progress in the nonconvex landscape, leading to slow convergence or convergence to suboptimal stationary points. We propose an *exterior* framework for NMF (eNMF) that separates low-rank approximation from nonnegativity enforcement. Our method initializes from the optimal unconstrained factorization and introduces a rotation procedure that maps unconstrained factors to an exterior point closest to the nonnegative orthant. This viewpoint yields an algorithmic framework in which simple iterative updates converge to KKT-satisfying stationary points on the boundary of the positive orthant. The exterior formulation also enables a geometric interpretation of NMF solutions, clarifying equivalence classes of factorizations under permutation and orthogonal transformations. An intriguing numerical result, involving 400 NMF experiments across both real and synthetic datasets, show that in 99\% of the cases, different algorithms tend to converge towards equivalent factor matrices. We benchmark eNMF against 9 state-of-the-art NMF algorithms with 9 initialization schemes across 3 real-world and 2 synthetic datasets. eNMF consistently outperforms all 81 competitors, achieving up to 30\% lower reconstruction error under equal-time settings and up to 150\% speedup under equal-error settings. The downstream experiments further demonstrate substantial performance gains in audio processing and recommendation tasks, corroborating the practical benefits of the proposed exterior optimization framework. Code is available at https://github.com/roychowdhuryresearch/eNMF

In personalized federated learning (PFL), collaboration graphs specify model aggregation among clients. However, without constraints on the collaboration geometry, training can drift into two degenerate regimes: global consensus or spontaneous clustering. This paper provides a unified dynamical analysis: under the same budget of representative models, collaborative PFL is more expressive and achieves higher-order approximation accuracy than clustered PFL. An upper bound on disagreement further reveals two degeneration mechanisms—overly strong collaboration drives consensus (reducing to standard federated learning), while similarity-driven weight updates make the graph nearly reducible and induce self-clustering (collapsing to clustered PFL). Motivated by these findings, we propose pFedCCG. pFedCCG preserves the expressivity advantage via controlled collaboration geometry (CCG): it builds a static similarity-based collaboration template decoupled from training, optimizes a Markovian collaboration matrix with a prescribed stationary distribution via reversible parameterization and Euclidean projection, and schedules collaboration strength to avoid self-clustering. Experiments across diverse heterogeneity settings show consistent personalization gains and markedly reduced collapse and self-clustering. Code is available at https://github.com/YinHonb/pFedCCG.

We propose a unified framework to enhance the power of online multiple hypothesis testing procedures based on $e$-values. While $e$-value-based methods offer robust online False Discovery Rate (FDR) control under minimal assumptions, they often suffer from power loss by discarding evidence that exceeds the rejection threshold. We address this inefficiency via the \textbf{S}equential \textbf{C}ontrol with \textbf{O}vershoot \textbf{R}efund for \textbf{E}-values (SCORE) framework, which leverages the inequality $\mathbb{I}(y \ge 1) \le y - (y-1)_+$, valid for all $y\ge 0$, to reclaim this otherwise ``wasted'' evidence. This simple yet powerful insight yields a unified principle for improving a broad class of online testing algorithms. Building on this framework, we develop SCORE-enhanced versions of several state-of-the-art procedures, including SCORE-LOND, SCORE-LORD, and SCORE-SAFFRON, all of which strictly dominate their original counterparts while preserving valid finite-sample FDR control. Furthermore, under mild assumptions, SCORE permits retroactive updates of alpha‑wealth by using the latest decision twice: first to determine its reward or loss, and then to refresh past wealth. Such a mechanism enables more aggressive testing strategies while maintaining valid FDR control, thereby further improving statistical power. The effectiveness of the proposed methods is validated through extensive simulation and real-data experiments.

Standard classification treats all errors equally, but in applications such as content moderation and medical screening, mistakes on clear-cut cases are more costly than errors on ambiguous ones. From a contextual bandit framework, we propose normalized excess cost (NEC), a metric that weighs classification errors by per-example costs and reduces to standard error rate when costs are uniform. Costs can derive from annotator vote margins, distance from decision thresholds, or confidence ratings. Across text, image, and tabular benchmarks, we find that NEC is often substantially lower than error rate—models with 5% error rate can achieve 1.8% NEC—revealing that most mistakes concentrate on ambiguous, low-cost examples. We also find that incorporating costs into training via loss weighting, sampling strategies, or regression yields inconsistent benefits. Our framework provides a practical methodology for deriving and evaluating instance-level misclassification costs, even if cost-sensitive training offers limited benefit.

Functional ANOVA offers a principled framework for interpretability by decomposing a model’s prediction into main effects and higher-order interactions. For independent features, this decomposition is well-defined, strongly linked with SHAP values, and serves as a cornerstone of additive explainability. However, the lack of an explicit closed-form expression for general dependent distributions has forced practitioners to rely on costly sampling-based approximations. We completely resolve this limitation for categorical inputs. By bridging functional analysis with the extension of discrete Fourier analysis, we derive a closed-form decomposition without any assumption. Our formulation is computationally very efficient. It seamlessly recovers the classical independent case and extends to arbitrary dependence structures, including distributions with non-rectangular support. Furthermore, leveraging the intrinsic link between SHAP and ANOVA under independence, our framework yields a natural generalization of SHAP values for the general categorical setting.

We study program-learning methods that are efficient in both samples and computation. Classical learning theory suggests that when the target admits a short program description, for example a short piece of ``Python code'', it can be learned from few examples by ERM over the program class. However, this approach relies on enumerating candidate programs, which is typically exponential in the description length; gradient-based training avoids this explicit search but, for some families of short programs, can require exponentially many samples to succeed. We propose \textsc{LLM-PV}, a propose-and-verify recipe that enables ERM-style selection over a discrete program class without exhaustive enumeration: a pretrained LLM induces a proposal distribution over candidate programs, each proposal is executed and scored on a held-out validation set, and the best program is selected, with no gradient updates or validation feedback used to adapt the sampling distribution. Across algorithmic tasks including parity variants, pattern matching, and primality testing, \textsc{LLM-PV} often recovers the exact underlying rule from a small labeled set and generalizes far beyond the training sequence lengths, while SGD-trained transformers, fine-tuning, in-context learning, and classical ML baselines can fit the training data yet fail to generalize reliably. Together, these results suggest that pretrained LLM priors can serve as effective search biases for ERM, narrowing the gap between statistical and computational efficiency.

Reinforcement learning with verifiable rewards (RLVR) can yield large reasoning gains from very few training instances, yet its strong sensitivity to which instances are used makes data selection a central bottleneck. Most existing selection pipelines rely on training-time optimization signals and/or require access to verifiable rewards or ground-truth answers over large candidate pools, which is costly and often infeasible in specialized domains. We study RLVR data selection in a setting where selection must be performed before any RL training and without labels or reward evaluation on the full pool. We propose SHIFT, a one-shot, training-free selector based solely on inference-time hidden-state dynamics. For each candidate instance, SHIFT runs a single deterministic reasoning rollout and computes a reasoning-induced representation shift (RIRS) as the start-to-end hidden-state delta. SHIFT uses the RIRS magnitude as a lightweight proxy for instance utility and enforces coverage via a quality-weighted farthest-first CoreSet procedure in an RIRS-augmented feature space, producing compact subsets that scale to large unlabeled pools. Across mathematical reasoning and medical QA benchmarks under ultra-low budgets, SHIFT consistently outperforms training-free diversity and difficulty/uncertainty baselines, improving both in-domain accuracy and transfer to harder evaluation settings. Ablations show that RIRS-based coverage and quality-weighting contribute complementary gains, and analyses indicate that RIRS is not explained by simple input/output length statistics. Code is available at github.com/JianghaoWu/SHIFT.

Autoregressive decoding becomes bandwidth-limited at long contexts, as generating each token requires reading all $n_k$ key and value vectors from KV cache. We present Stochastic Additive No-mulT Attention (SANTA), a method that sparsifies value-cache access by sampling $S \ll n_k$ indices from the post-softmax distribution and aggregates only those value rows. This yields an unbiased estimator of the post-softmax value aggregation while replacing value-stage multiply-accumulates with gather-and-add. We introduce stratified and systematic sampling to design variance-reduced, GPU-friendly variants. Evaluated on Llama-3.1-8B-Instruct at 32k-token contexts, S$^2$ANTA matches baseline accuracy while achieving up to $1.5\times$ decode-step attention-kernel speedup over FlashInfer and FlashDecoding on an NVIDIA RTX 6000 Ada. In batched long-context generation, these kernel gains translate to up to $1.25\times$ end-to-end decode-latency speedup. Finally, we propose Bernoulli $qK^\mathsf{T}$ sampling as a complementary technique to sparsify the score stage, reducing key-feature access through stochastic ternary queries. Both methods are complementary to upstream quantization, low-rank projection, KV-cache compression, and KV-cache selection methods. Together, they point toward sparse, multiplier-free, and energy-efficient inference. We open-source our kernels at: https://github.com/OPUSLab/SANTA.git

Recently, vision-language models (e.g., CLIP) have been increasingly adopted for continual learning to mitigate catastrophic forgetting. However, existing CLIP-based methods typically freeze the backbone to preserve pre-trained knowledge, which limits the model's ability to learn discriminative features for downstream tasks. In this paper, we introduce HypCL, a parameter-efficient framework that continually adapts CLIP in hyperbolic space for continual learning. Our key insight is that the exponentially expanding capacity of hyperbolic geometry naturally accommodates the growing class space and promotes stronger inter-class separation. Specifically, HypCL attaches task-specific adapters and composes their updates sequentially in the Poincaré ball. To exploit the enhanced feature separability of hyperbolic geometry, HypCL maintains visual prototypes computed from the adapted features, which serve as stable anchors for calibrating predictions at inference. Extensive experiments on standard class-incremental benchmarks demonstrate that HypCL consistently outperforms existing CLIP-based continual learning methods.

Existing machine learning models for network simulation excel at predicting average performance but, due to their reliance on mean squared error, systematically fail to capture the critical tail-latency and jitter that define modern network stability. This 'tail-blindness' renders them unreliable for latency-sensitive systems. We bridge this gap by introducing Accurate Neural Architecture Search (ANAS), a paradigm that automates the discovery of architectures for high-precision, distribution-aware network simulation. ANAS corrects the evaluation inaccuracies of weight-sharing NAS via a similarity-constrained search, employs a hybrid search space to model complex traffic, and uses a Wasserstein loss to optimize for the entire delay distribution, not just its mean. Empirically, the ANAS-discovered architecture is holistically superior: it reduces overall validation loss by 25.8\% compared to DeepQueueNet, demonstrating strong average-case performance, while simultaneously excelling at tail-sensitive metrics by lowering the normalized Wasserstein distance ($W_n$) by up to 69.8\%. This confirms its ability to faithfully model a comprehensive performance spectrum, encompassing both average and critical tail behaviors. The ANAS framework provides a practical methodology for automatically creating high-fidelity model of network devices, enabling more reliable validation of next-generation network protocols and algorithms.

Diffusion-based language models (dLLMs) enable parallel token generation through iterative denoising, but existing decoding strategies collapse to single-token generation under low confidence, severely limiting throughput. Unlike autoregressive models where speculative decoding operates on token sequences in a fixed left-to-right order, dLLMs require speculating over \emph{denoising trajectories}—sequences of multi-token updates with explicit positions and unmasking orders. We develop a trajectory-level speculative framework that constructs draft denoising trajectories via confidence-stratified tree exploration and verifies them through blockwise parallel evaluation with bidirectional attention masking. Our method further introduces inter-block speculation, exploiting diffusion models' bidirectional structure to perform cross-block lookahead. We formally characterize when this approach is exact and identify trajectory drift as the fundamental cost of increased parallelism. Building on Fast-dLLM's dual-cache infrastructure, our framework reduces denoising iterations by 30-40\% and increases tokens-per-step from 2.6 to 4.3, achieving 7-14$\times$ speedup over vanilla dLLMs and 1.3$\times$ over Fast-dLLM with less than 1\% accuracy change across reasoning and code benchmarks.

Real-world datasets often follow a long-tailed distribution, making generalization to tail classes difficult. We revisit this problem through the lens of shortcut learning, where models prefer the easiest predictive cues (e.g., background or textures) over object-centric semantics, especially under scarce and biased supervision. We find that this tendency is amplified for tail classes: limited examples often share similar contexts, making non-semantic signals highly correlated and thus tempting shortcuts, whereas head classes with diverse appearances and environments encourage more stable object-focused representations. Motivated by this observation, we propose Shortcut-Resistant CAM Distillation (SRCD), a plug-and-play framework that transfers object-focused explanations from head to tail classes. SRCD operates in the Class Activation Map (CAM) space, where a CAM provides a class-specific spatial evidence map for a prediction. SRCD aggregates CAMs from a small set of head-class candidates into a shortcut-resistant teacher using an energy-model weighting based on coherence and concentration, and distills it to the tail-class CAM. We provide a theoretical analysis that quantifies shortcut reliance as shortcut-region evidence mass in CAM space and shows that SRCD suppresses tail shortcuts. Extensive experiments on long-tailed benchmarks consistently improve strong baselines. The code is available at \url{https://github.com/Haifeng3/SRCD}.

Static program analysis is a foundational technique in software engineering for reasoning about program behavior. Traditional static analysis algorithms model programs as logical systems with well-defined semantics, but rely on uniform, hard-coded heap abstractions. This limits their precision and flexibility, especially in dynamic languages like JavaScript, where heap structures are heterogeneous and difficult to analyze statically. In this work, we introduce ABSINT-AI, a language-model-guided static analysis framework that augments abstract interpretation with adaptive, per-object heap abstractions for Javascript. This enables the analysis to leverage high-level cues, such as naming conventions and access patterns, without requiring brittle, hand-engineered heuristics. Importantly, the LM agent operates within a bounded interface and never directly manipulates program state, preserving the soundness guarantees of abstract interpretation. To evaluate our approach, we focus on a soundness-critical task: determining whether object property accesses may result in undefined or null dereferences. This task directly models a common requirement in compiler optimizations, where proving that an access is safe enables the removal of dynamic checks or simplifies code motion. On this task, ABSINT-AI reduces false positives by up to 34% compared to traditional static analyses with fixed heap abstractions, while preserving formal guarantees. Our ablations show that the LM’s ability to interact agentically with the analysis environment is crucial, outperforming non-agentic LM predictions by 25%.