ICML 2026 Papers

Kleinberg and Mullainathan showed that language generation in the limit is always possible at the level of computability: given enough positive examples, a learner can eventually generate data indistinguishable from a target language. However, such existence results do not address feasibility. We study the sample complexity of language generation in the limit for several canonical classes of formal languages. Our results show that infeasibility already appears for context-free and regular languages, and persists even for strict subclasses such as locally threshold testable languages, as well as for incomparable classes such as non-erasing pattern languages, a well-studied class in the theory of language identification. Overall, our results establish a clear gap between the theoretical possibility of language generation in the limit and its computational feasibility.

Retrieval-augmented generation (RAG) enhances large language models with external knowledge, and tree-based RAG organizes documents into hierarchical indexes to support queries at multiple granularities. However, existing Tree-RAG methods designed for single-document retrieval face critical challenges in scaling to cross-document multi-hop questions: *(1) poor distribution adaptability*, where $k$-means clustering introduces noise due to rigid distribution assumptions; *(2) structural isolation*, as tree indexes lack explicit cross-document connections; and *(3) coarse abstraction*, which obscures fine-grained details. To address these limitations, we propose **$\Psi$-RAG**, a tree-RAG framework with two key components. *First*, a hierarchical abstract tree index built through an iterative "merging and collapse" process that adapts to data distributions without a priori assumption. *Second*, a multi-granular retrieval agent that intelligently interacts with the knowledge base with reorganized queries and an agent-powered hybrid retriever. $\Psi$-RAG supports diverse tasks from token-level question answering to document-level summarization. On cross-document multi-hop QA benchmarks, it outperforms RAPTOR by 25.9\% and HippoRAG 2 by 7.4\% in average F1 score.

Federated Graph Learning (FGL) enables distributed clients to collaboratively train graph neural networks while strictly preserving data privacy. However, existing FGL methods implicitly assume the reliability of local graph structures and lack elastic awareness of parameter importance during model aggregation, leading to representation degradation under topological noise and catastrophic forgetting caused by model drift. To address these challenges, we propose GraphP-FL, a general personalized FGL framework. (1) Specifically, we design a self-supervised dynamic topology reconstruction mechanism on the client side. This mechanism mines implicit dependencies to adaptively rectify noisy topologies, effectively suppressing topological noise propagation and capturing precise structural relationships for high-quality representations. (2) Additionally, we introduce a Fisher-based Elastic Parameter Alignment (FRPA) algorithm. FRPA imposes anisotropic regularization constraints in the parameter space to precisely quantify parameter importance, enabling the model to strictly preserve critical local knowledge while flexibly aligning with the global model, thus effectively overcoming catastrophic forgetting. Extensive experiments on seven benchmarks (including biochemical molecules, social networks, and large-scale encrypted traffic) demonstrate that GraphP-FL significantly outperforms state-of-the-art methods, improving accuracy by up to 8.6% while exhibiting superior generalization and robustness.

With the rapid development of deep learning, the issue of data scarcity has become increasingly prominent, inspiring emerging interests towards research on data augmentation techniques over recent years. However, our literature survey indicates that existing efforts often suffer from two issues of semantic infidelity, including: (i) visual semantics infidelity, such as visual artifacts, manifold intrusion, and unnatural blending boundaries etc, and (ii) label semantic infidelity, where augmented images do not match the original labels, creating extra label noises. To address these issues, we propose a Semantics Calibrated and Diffusion-Enhanced Augmentation (SCalDA) scheme to achieve accurate semantics calibration across image, label and feature domains. Compared with the existing approaches, our proposed features in precise guidance in label domain, semantics driven synthesis across three domains (image, label and feature), and semantics-aware metric learning. Extensive experiments on multiple datasets demonstrate that SCalDA yields consistent and significant performance improvements for both fine-grained and general classification tasks, validating the effectiveness and broad applicability of the proposed.

Multi-adapter serving systems route entire sequences to a single adapter, forcing a choice when requests span multiple domains. This assumption fails in two important settings: (1) multimodal generation, where text and image tokens require different adapters within the same sequence, and (2) mixed-capability requests like ``write code to solve this equation,'' which need expertise from multiple specialized adapters. We introduce \emph{per-token routing}, which routes individual tokens to adapters based on either vocabulary structure (for multimodal models) or learned gating (for semantic specialization). Per-token routing is provably optimal for mixed-adapter requests: $N$ work for $N$ tokens, versus $K \cdot N$ for per-sequence systems that must replay one adapter per pass. Our key contribution is MoLoRA (Mixture of LoRA), which enables \emph{composable specialization}: load multiple domain-specific adapters and let a learned router select the appropriate adapter per-token. We demonstrate that specialization dramatically beats scale: MoLoRA enables Qwen3-1.7B to exceed Qwen3-8B across four reasoning benchmarks while being 4.7$\times$ smaller. This enables modular expertise at inference time: train focused LoRAs independently, combine them without retraining, and add new capabilities by simply loading new adapters.

We present adversarial flow models, a class of generative models that belongs to both the adversarial and flow families. Our method supports native one-step and multi-step generation and is trained with an adversarial objective. Unlike traditional GANs, in which the generator learns an arbitrary transport map between the noise and data distributions, our generator is encouraged to learn a deterministic noise-to-data mapping. This significantly stabilizes adversarial training. Unlike consistency-based methods, our model directly learns one-step or few-step generation without having to learn the intermediate timesteps of the probability flow for propagation. This preserves model capacity and avoids error accumulation. Under the same 1NFE setting on ImageNet-256px, our B/2 model approaches the performance of consistency-based XL/2 models, while our XL/2 model achieves a new best FID of 2.38. We additionally demonstrate end-to-end training of 56-layer and 112-layer models without any intermediate supervision, achieving FIDs of 2.08 and 1.94 with a single forward pass and surpassing the corresponding 28-layer 2NFE and 4NFE counterparts with equal compute and parameters.

We introduce TFRBench, the first benchmark designed to evaluate the reasoning capabilities of forecasting systems. Traditionally, time-series forecasting has been evaluated solely on numerical accuracy, treating foundation models as "black boxes." Unlike existing benchmarks, TFRBench provides a protocol for evaluating the reasoning generated by forecasting systems--specifically their analysis of cross-channel dependencies, trends, and external events. To enable this, we propose a systematic multi-agent framework that utilizes an iterative verification loop to synthesize numerically grounded reasoning traces. Spanning ten datasets across five domains, our evaluation confirms that this reasoning is causally effective; useful for evaluation; and prompting LLMs with our generated traces significantly improves forecasting accuracy compared to direct numerical prediction (e.g., avg. $\sim40.2$% $\rightarrow$ $\sim56.6$%), validating the quality of our reasoning. Conversely, benchmarking experiments reveal that off-the-shelf LLMs consistently struggle with both reasoning (lower LLM-as-a-Judge scores) and numerical forecasting, frequently failing to capture domain-specific dynamics. TFRBench thus establishes a new standard for interpretable, reasoning-based evaluation in time-series forecasting. Our benchmark is available at: https://tfrbench.github.io

Spiking Neural Networks (SNNs), with their event-driven and biologically inspired mechanisms, are well-suited for energy-efficient neuromorphic hardware. Neural coding, which is critical to SNNs, determines how information is represented via spikes. While Time-to-First-Spike (TTFS) coding uses a single spike per neuron to offer extreme sparsity and energy efficiency, it often suffers from unstable training and low accuracy due to its sparse firing. To address these challenges, we propose a training framework that incorporates parameter initialization, training normalization, a temporal output decoder, and a re-evaluation of the pooling layer. The proposed parameter initialization and training normalization mitigate signal diminishing and gradient vanishing, which helps stabilize training. Our output decoder aggregates temporal spikes to encourage earlier firing, thereby reducing latency. The re-evaluation of the pooling layer demonstrates that max-pooling violates single-spike constraints, which should be avoided, whereas average-pooling preserves them. Experiments show that our framework stabilizes and accelerates training, reduces latency, and achieves state-of-the-art accuracy for step-by-step TTFS SNNs on MNIST ($99.48\%$), Fashion-MNIST ($92.90\%$), CIFAR10 ($90.56\%$), CIFAR100 ($70.27\%$) and DVS Gesture ($95.83\%$).

State Space Models (SSMs) provide linear-time alternatives to attention for vision, but require serializing 2D images into 1D sequences using a predefined scan order. We identify scan order as a previously underexplored inductive bias that fundamentally shapes spatial dependency modeling in Vision SSMs. Fixed scan paths distort local adjacency, fragment object structure, and induce anisotropic representations that are brittle under geometric transformations such as rotation. We propose Partial RIng Scan Mamba (PRIS-Mamba), a rotation-robust traversal that decomposes images into concentric rings, performs permutation-invariant aggregation within each ring, and models cross-ring dependencies via short radial SSMs. This design induces a structured factorization of spatial dependencies that preserves isotropy while maintaining linear complexity. To improve efficiency without sacrificing expressivity, we introduce partial channel filtering, selectively applying recurrent modeling to informative channels while routing others through a residual pathway. Empirically, PRIS-Mamba improves accuracy, efficiency, and rotation robustness over prior Vision SSMs on ImageNet-1K. Our results position scan-order design as a core representational choice in Vision SSMs, with implications for robustness and generalization beyond architectural scaling. The code will be released upon paper acceptance.

We propose a system for marking sensitive or copyrighted texts to detect their use in fine-tuning large language models under black-box access with statistical guarantees. Our method builds digital “marks” using invisible Unicode characters organized into (“cue”, “reply”) pairs. During an audit, prompts containing only “cue” fragments are issued to trigger regurgitation of the corresponding “reply”, indicating document usage. To control false positives, we compare against held-out counterfactual marks and apply a ranking test, yielding a verifiable bound on the false positive rate. Empirically, we obtain a true positive rate of 96.7\% at 0\% false positive rate and reply regurgitation rates exceeding 28\% per document with only 40 (4\%) watermarked documents. The approach is minimally invasive, scalable across many sources, robust to standard processing pipelines, and achieves high detection power even when marked data is a small fraction of the fine-tuning corpus.

Relational prediction tasks are fundamental in many real-world applications, where data are naturally stored in relational databases (RDBs). Relational Deep Learning (RDL) addresses this problem by modeling RDBs as graphs and applying graph neural networks (GNNs) for end-to-end learning. However, the full-resolution property is commonly adopted as a design principle in graph construction for RDBs to preserve relational semantics, which leads most existing methods to rely on fixed graph structures. In this paper, we propose **FROG**, a *F*ull-*R*esolution and *O*ptimizable *G*raph Structure Learning framework for RDL that formulates relational structure learning as a learnable table role modeling problem, allowing tables to contribute as nodes and edges in message passing. We further design role-driven message passing mechanisms to capture relational semantics, enabling joint optimization of graph structure and GNN representations. To ensure semantic consistency, we introduce functional dependency constraints that regularize representations across table and entity levels. Extensive experiments demonstrate that our method outperforms existing approaches and reveal how table roles impact downstream tasks, offering new insights into graph construction for RDL.

Research on continual learning for LLMs seeks to acquire new skills without catastrophic forgetting of established prior knowledge. However, domain-specific fine-tuning still triggers severe, long-tailed forgetting issues even under narrow updates, particularly when the pre-training data is inaccessible. To tackle this challenge, we propose **ALER**, a data-free continual learning framework that adversarially searches for a small set of latent prompt embeddings to maximize logit divergence from a frozen reference model, proactively exposing high-risk forgetting modes at each step. It then performs online distillation from the frozen reference using the discovered embeddings to retain prior behaviors while preserving target-domain adaptation. We provide theoretical guarantees on the efficiency of our targeted repair, and extensive experiments demonstrate consistent improvements in the retention–adaptation frontier over representative baselines across $2$ domain-specific fine-tuning datasets and $6$ general-purpose benchmarks, suggesting a more proactive approach for LLM continual learning.

Large language models excel at short-horizon reasoning tasks, but performance drops as reasoning horizon lengths increase. In this work, we introduce a scalable method to bootstrap long-horizon reasoning capabilities using only existing, abundant short-horizon data. Our approach synthetically composes simple problems into complex, multi-step dependency chains of arbitrary length. We train models on this data using outcome-only rewards under a curriculum that automatically increases in complexity, allowing RL training to be scaled much further without saturating. Empirically, our method generalizes remarkably well: curriculum training on composed 6th-grade level math problems improves accuracy on longer, competition-level benchmarks. It also transfers significantly to diverse out-of-distribution ReasoningGym domains and long-context benchmarks, indicating broader generalization. Importantly, our long-horizon improvements are significantly higher than baselines even at high pass@k, showing that models can learn new reasoning paths under RL. Theoretically, we show that curriculum RL with outcome rewards could achieve an exponential improvement in sample complexity over full-horizon training, providing training signal comparable to dense supervision. h1 therefore introduces an efficient path towards scaling RL for long-horizon problems using only existing data.

Controlling the false discovery rate (FDR) under complex sparsity structures remains a fundamental challenge in large language model (LLM) analysis. Motivated by multiple comparison problems in LLMs, we consider a setting in which sparsity arises at the group level after a linear transformation of model parameters. We propose Split Group Knockoffs (SGKs), a general framework for group-wise variable selection under grouped transformational sparsity that extends the Split Knockoff procedure to grouped transformed variables. We establish theoretical guarantees for group-level FDR control and support recovery consistency, addressing challenges induced by group-wise penalties in transformed spaces. Applying SGK to LLM behavior auditing experiment reveals that model disagreement is not uniform across subjects, but instead concentrates in domains with greater semantic and reasoning complexity, where SGK effectively distinguishes genuine behavioral deviations from surface-level performance variation.

Recent advances have shifted the paradigm of tabular learning toward tabular foundation models, yet their accuracy relies on a heavy inference cost that scales poorly with context size. Deep neural networks remain a highly competitive and more efficient modeling paradigm when equipped with well-designed architectures; however, identifying such architectures in a data-adaptive and budget-aware manner remains challenging. We propose pTNAS, the first progressive neural architecture search (NAS) approach tailored for tabular data, which enables fast identification of a viable architecture and continuously improves its search performance as more budget becomes available. pTNAS adopts a filter-and-refine optimization strategy that combines efficient training-free and effective training-based architecture evaluation. In the filtering phase, we introduce pTProxy, a novel zero-cost proxy specifically designed for tabular networks that jointly captures architectural trainability and expressivity, enabling fast filtering of large architecture search spaces. In the refinement phase, pTNAS employs a fixed-budget scheduling algorithm to accurately identify the best-performing architecture from a small set of promising candidates. We further propose a budget-aware coordinator to optimize budget allocation holistically. Experiments show that pTNAS reduces the time to reach the globally best architecture by up to 82.75 X compared with other NAS approaches, achieves the best average predictive rank, and improves end-to-end efficiency by up to 4.78 X compared with TabPFN.

Selection bias is pervasive in observational studies. For example, large scale biobanks data can exhibit ``healthy volunteer bias'' when respondents are healthier and of higher socio-economic status than the population they are meant to represent. Recovering causal effects from such sub-population is an important problem in causal inference, as estimating average treatment effects (ATE) from selected populations can result in a severely biased estimate of the ATE from the whole population. In this paper, we investigate the identifiability of the ATE under selection bias. We provide *necessary and sufficient conditions* for ATE identifiability, leveraging weak assumptions on probability classes to characterize propensity score and selection probability, which are weaker assumptions than those required by existing general identification frameworks. Compared to previous works, our results extend existing graphical identifiability criteria and offer a more comprehensive understanding of causal effect identification *with strictly weaker conditions* in the presence of selection bias.

Building reliable applications that leverage large language models (LLMs) remains a significant challenge. While LLMs offer impressive capabilities across diverse tasks, their outputs often lack accuracy and provide no clear measure of confidence. This uncertainty compounds in flows of multiple calls to LLMs and other tools, making it difficult for developers and end-users to trust the results. This paper introduces a probabilistic language for programming LLM-based flows. It enables developers to quantify and propagate uncertainty throughout the application's flow, and experiment with different inference scaling techniques without adding a single line of code beyond the flow's logic. We present an experimental study to demonstrate this capability, and a case study building a theorem proving agent for the Rocq theorem prover.

Modern decision-making increasingly relies on contextual features (covariates) to improve optimization under uncertainty. In practice, however, such covariates are often only partially observed due to, e.g., data source heterogeneity or costly data collection. Nonetheless, most existing methods assume fully observed historical data and can become unreliable when this assumption is violated. We address this gap by proposing a distributionally robust optimization approach that exploits incomplete covariates to produce robust decisions without imputing a complete dataset. Our method builds ambiguity sets from the observed partial data and incorporates the general structure of the missingness mechanism, ensuring candidate distributions remain consistent with what is observed. Across settings with discrete or continuous covariates and outcomes, we derive tractable reformulations and establish finite-sample out-of-sample performance guarantees. Empirical results across a range of contextual decision-making tasks demonstrate that the proposed integrated approach consistently outperforms state-of-the-art baselines, including various impute-then-optimize pipelines, in both out-of-sample performance and reliability.

Memory-based test-time adaptation (TTA) assigns streaming test samples into class-specific memory slots based on pseudo-labels predicted by models like CLIP, and retrieves them to facilitate subsequent predictions under distribution shift. However, this process introduces two challenges: (1) Each sample is hard-assigned to a single class based on CLIP's prediction, where inaccurate CLIP prediction leads to memory contamination that biases subsequent prediction. (2) Samples are evicted under biased selection due to fixed memory capacity, which risks discarding informative samples and undermining the efficacy of the memory. To address these challenges, we propose A²Memory (Attributive-Associative Memory for Test-time Adaptation). For challenge (1), we propose Attribute-centric Memory Construction that builds prior textual representations from class-shared representative and diverse visual attributes, and applies soft assignment to generate surrogate visual representations. For challenge (2), we design Class-wise Associative Memory that dynamically compresses streaming samples into fixed-capacity memory through gradient-based optimization and data-dependent retention, then retrieves sample-adaptive class prototypes for reliable inference. Extensive experiments demonstrate consistent improvements over state-of-the-art methods across 15 benchmarks.