NeurIPS 2026 Papers

Streaming decision trees are natural candidates for open-world continual learning, as they perform local updates, enjoy bounded memory, and static decision boundaries. Despite these, they still fail in online class-incremental learning due to two coupled miscalibrations: (i) their split criterion grows unreliable as the class count $K$ expands, and (ii) the absence of knowledge transfer at split time. Both failures share a common root: the range of Information Gain intrinsically scales with $\log_2 K$. Consequently, any Hoeffding-style confidence radius derived from it must inevitably grow with the class count, making a $K$-independent split criterion structurally impossible, taking away the potential benefits of applying streaming decision trees to continual learning. To fix this issue, we present \mist{} (McDiarmid Incremental Streaming Tree), which resolves both failures through three integrated components: (i) a tight, $K$-independent McDiarmid confidence radius for Gini splitting that acts as a structural regulariser; (ii) a Bayesian inheritance protocol that projects parent statistics to child nodes via truncated-Gaussian moments, with variance reduction guarantees strongest precisely when splitting is most conservative; and (iii) per-leaf KLL quantile sketches that support both continuous threshold evaluation and geometry-adaptive leaf prediction from a single data structure. On standard and stress-test tabular streams, \mist{} is competitive with global parametric methods on near-Gaussian benchmarks and uniquely robust on non-Gaussian geometry where SOTA benchmarks collapse.

Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, "blind" preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include $O(1)$-competitive algorithms for single and unrelated parallel machines with only $O(1)$ preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.

We study online multicalibration beyond the worst-case. We give a single, efficient algorithm which dynamically interpolates between stochastic and worst-case sequences by adaptively refining a dyadic grid of prediction values. Its error is controlled by the number of leaves in the refinement tree. Our analysis recovers the known $\widetilde O(T^{2/3})$ worst-case-optimal rate for online multicalibration, while simultaneously automatically adapting to easier instances: in the marginal stochastic setting it obtains a rate of $\widetilde O(\sqrt T)$, and for piecewise-stationary means with $J$ segments its rate is $\widetilde O(\sqrt{JT})$. More generally, the rate depends on a threshold-complexity measure of the predictable mean process relative to the group family. We show that this dependence is tight up to logarithmic factors.

We study online multiclass classification with surrogate losses. We identify and exploit a structural property of margin-based classifiers: on many rounds predictions are stable in the sense that after an update of the parameters the algorithms do not change the predicted label on the current example. By exploiting this stability we improve upon the state of the art in several ways. We provide an improved surrogate regret bound for the perceptron, develop a parameter-free version of $\texttt{GAPTRON}$, develop improved results for the delayed feedback setting, and extend our results to the batch setting. These results are complimented by empirical evaluations.

Online Continual Learning (OCL) requires models to learn from non-stationary data streams under a strict single-pass constraint, making them highly susceptible to catastrophic forgetting. While existing studies have explored various strategies from data, architecture, and optimization perspectives, the optimizer often directly uses generic approaches such as SGD and AdamW. In this work, we reveal a new link between optimization dynamics and OCL needs by recasting Polyak-Ruppert averaging as the engine of "plasticity" and Primal averaging as the anchor of "stability". This inspires our novel optimizer, SPIN (**S**tability-**P**lasticity **IN**terpolation), which explicitly decouples plasticity and stability by interpolating between a fast-moving "plasticity" sequence and an adaptive "stability" sequence. We theoretically demonstrate that SPIN implicitly employs an inverse Hessian approximation, providing crucial Tikhonov regularization to damp noisy, single-sample Hessian estimates and mitigate forgetting. More importantly, SPIN can be seamlessly integrated existing OCL methods by taking resulted gradients as input and replacing standard optimizers. Extensive experiments show that using SPIN instead of standard optimizers yields consistent and significant performance gains across multiple OCL approaches, including the challenging rehearsal-free setting and under strict memory constraints.

Large-scale training of machine learning interatomic potentials (MLIPs) increasingly relies on data parallelism over heterogeneous atomistic data. In this setting, atom count captures an important part of the per-rank workload, but structures with similar atom counts can still induce different graph workloads through variations in graph count, cutoff edges, higher-order geometric features, and graph-collation overhead. This makes conventional atom-count batching and offline load tables both incomplete and inflexible, especially when the model architecture, cutoff radius, or data mixture changes. We present Flux, an online workload-aware scheduler for distributed MLIP training. Flux estimates structure-dependent workload signals from lightweight physical and geometric priors during data loading, calibrates them against runtime and memory costs, and forms balanced, memory-feasible local mini-batches across data-parallel ranks. Without requiring precomputed graph metadata, Flux can be used as a drop-in replacement for the standard distributed sampler, making it flexible and portable across training setups. Across large-scale atomistic datasets and three representative MLIP architectures, eSEN, MatRIS, and AllScAIP, Flux improves training throughput by up to 2.23--4.76$\times$ without degrading convergence.

Vision-large language models (VLLMs) editing aims to efficiently update model responses while retaining generalization and unrelated knowledge. Recent online editors store previous edits as reusable experts, forming a mixture-of-experts editing memory for scalable VLLM correction. By retrieving relevant experts at inference time, this paradigm avoids repeatedly overwriting model parameters and enables continual reuse of accumulated editing experience. However, existing sample-level residual experts usually encode each edit instance as a whole, entangling target-relevant visual evidence with irrelevant context. This coarse expert construction weakens expert reusability, leads to inaccurate routing, and increases unintended side effects during continual editing. To address this limitation, we reformulate online VLLM editing as evidence guided expert construction and routing. A fine mask identifies edit-relevant visual evidence, from which support-suppress experts are constructed to strengthen target consistent cues and weaken edit conflicting cues. Each expert is stored with routing signals and reliability scores, and later retrieved through joint sparse routing over visual evidence, textual context, and expert quality. Experiments demonstrate consistent improvements in editing reliability, generalization, and interpretability over competitive online editing baselines.

Behavioral cloning (BC) is a powerful paradigm for learning robotic policies from demonstrations. However, most existing approaches operate in an offline setting and do not address a critical requirement for real-world deployment: the ability to continually improve policies after deployment. While interactive imitation learning methods such as DAgger enable improvement by collecting additional data, they rely on repeated retraining over an ever-growing dataset, leading to increasing computational cost and limited scalability. In practice, robotic systems must adapt continuously during deployment while remaining operational, making retraining on all accumulated data impractical. In this work, we introduce an online formulation of interactive BC, where the policy is updated in real time with expert corrections to address failure cases, with no access to past data. This setting presents a fundamental challenge due to catastrophic forgetting, which degrades previously acquired behaviors when learning from new data. To address this, we propose a novel method based on online ridge regression and random projections, enabling efficient policy updates without gradient-based retraining. We evaluate our approach on a range of manipulation tasks and show that it enables continuous and stable improvement after deployment, outperforming state-of-the-art BC baselines.

Operating and maintaining (O&M) large-scale online engine systems (search, recommendation, advertising) demands substantial human effort for release monitoring, alert response, and root cause analysis. While LLM-based agents are a natural fit for these tasks, the deployment bottleneck is not reasoning capability but *orchestration*: selecting, for each operational event, the relevant *data* (metrics, logs, change events) and the applicable *operational knowledge* (handbook rules and practitioner experience). Feeding all signals indiscriminately causes dilution and hallucination, while manually curating the event-to-(data, knowledge) mapping is intractable under dozens of daily releases. We present **Bian Que**, an agentic framework with three contributions: (i) a **unified operational paradigm** abstracting day-to-day O&M into three canonical patterns: release interception, proactive inspection, and alert root cause analysis; (ii) **Flexible Skill Arrangement**, where each Skill specifies which data and knowledge to retrieve for a given business-module context and can be automatically generated and updated by LLMs or iteratively refined through natural-language instructions from on-call engineers; (iii) a **unified self-evolving mechanism** in which one correction signal drives two parallel pathways, case-memory-to-knowledge distillation and targeted Skill refinement. Deployed on the e-commerce search engine of a major short-video platform in China, **Bian Que** reduces alert volume by 75%, achieves 80% root-cause analysis accuracy, and cuts mean time to resolution by over 50%. Our framework achieves 99.0% pass rate on offline evaluations.

We study online learning in the adversarial injection model [GHMS23], where each instance is either drawn i.i.d. from an unknown distribution or is an arbitrary adversarial injection. The learner never knows which rounds are adversarial, but may abstain without penalty on adversarial injections. The learner's goal is to make few total misclassifications and few abstentions on i.i.d. instances. This model lies between classical statistical learning, governed by the VC dimension, and adversarial online learning, governed by the Littlestone dimension. Unlike prior work, which has largely focused on the realizable setting, we consider an agnostic formulation that allows arbitrary labels. We present an online algorithm that guarantees sublinear excess misclassification error and sublinear abstention error, against oblivious and adaptive adversaries, for function classes that admit bounded bracketing number witnessed by brackets of bounded VC dimension. Our algorithm is distribution-independent and does *not* require prior knowledge of the distribution. As corollaries, we obtain new learning guarantees for halfspaces (linear classifiers) and richer classes such as feed-forward neural networks with threshold activations.

We study nonstationary online linear programming (OLP), where orders arrive sequentially and follow independent but not-identical reward-resource distributions. The decision- maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to a resource endowment available at the beginning of the planning horizon. Such problems arise in resource-constrained ML and AI systems, including inference admission control, online advertising and recommendation, and data-acquisition pipelines, where the mix and value of requests may change over time. We focus on a minimal-information regime in which the decision-maker observes only one independent sample from each future distribution before the horizon begins. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of order, we prove that our algorithm achieves $O((\log n)^2)$ regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.

Online data selection is typically driven by per-sample scores such as loss, uncertainty, or gradient norm, which measure how strongly the model reacts to a candidate but not what parameter update the candidate would induce. What an online learner should select is therefore not the most striking example, but the one whose update is most worth taking. To make this concrete, we score a candidate by the movement induced by its update, using a Fisher-whitened information gain that evaluates the update in the loss geometry rather than by raw gradient size. Movement, however, is not yet progress, so we pass this score through a \emph{Descent Alignment Gate}, a soft factor that retains it only when the induced update agrees with the descent direction. This yields a sample-level score favoring updates that are both informative and descent-aligned. To make the criterion compatible with training, we extend it from samples to batches, where selected updates should not only score well individually but also complement one another. We capture this with the \emph{Gated Fisher Volume}, a log-determinant batch objective that reduces to the per-sample score on a singleton, grows with the volume spanned by the chosen updates in the Fisher geometry, and admits a greedy algorithm with a constant-factor approximation guarantee. Across supervised fine-tuning benchmarks, our selector consistently outperforms online selection baselines under matched training budgets. More broadly, the framework reframes data selection itself: rather than a spotlight on conspicuous examples, it acts as a compass toward updates worth taking.

Large language models increasingly need to accumulate and reuse historical information in long-term assistants and agent systems. Simply expanding the context window is costly and often fails to ensure effective context utilization. We propose $\delta$-Mem, a lightweight memory mechanism that augments a frozen full-attention backbone with a compact online state of associative memory. $\delta$-Mem compresses past information into a fixed-size state matrix updated by delta-rule learning, and uses its readout to generate low-rank corrections to the backbone's attention computation during generation. With only an $8\times8$ online memory state, $\delta$-Mem improves the average score to $1.10\times$ that of the frozen backbone and $1.15\times$ that of the strongest non-$\delta$-Mem memory baseline. It achieves larger gains on memory-heavy benchmarks, reaching $1.31\times$ on MemoryAgentBench and $1.20\times$ on LoCoMo, while largely preserving general capabilities. These results show that effective memory can be realized through a compact online state directly coupled with attention computation, without full fine-tuning, backbone replacement, or explicit context extension.