NeurIPS 2026 Papers

We study learning-augmented online portfolio selection (OPS), where an investor uses predictions to improve wealth while remaining protected against unreliable advice. In frictionless markets, we characterize the optimal tradeoff between robustness (wealth under arbitrary predictions) and consistency (wealth under perfect predictions) tied to the geometric mean, and show that the optimal tradeoff admits a tractable online characterization. We further quantify how performance interpolates between these endpoints under imperfect predictions by smoothness guarantees. Under transaction costs, we give exact robust-trading certificates and, to our knowledge, the first learning-augmented OPS impossibility under costs: for any positive cost, no GM-robust policy can be maximally consistent under exact predictions. Lastly, we show that a cost-aware greedy rule remains Pareto-optimal.

Motivated by modern marketplaces, where the platform or the seller routinely gathers detailed user profiles, we study a novel learning theoretic model that simultaneously involves information and mechanism design. Specifically, we consider the economic setting recently introduced by Bergemann et al, where in addition to the menu of quality-price pairs, the seller offers information on the value of the match between product quality and buyer's taste via a signaling scheme. We relax the assumption that the seller knows the buyers' belief about the distribution of tastes and study the sample requirements of designing a revenue maximizing scheme. We consider both the batch setting where we have access to data from a set of i.i.d. buyers and an online demand query model where we observe the buyers behaviors to seller's schemes. Despite the apparent non-convexity of the problem, we also give the first FPTAS to compute a scheme that maximizes the revenue within an arbitrarily small additive loss, which was unknown even in the previous result of Bergemann et al. Overall, this brings a new learning perspective in asymmetric economic settings where buyers and sellers know different types of information.

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.

We study risk control for online policy learning, where an agent adaptively collects data and aims to learn a new policy where the risk is below a tolerance threshold at every round with a high probability. Such policy updates and data collection induce feedback covariate shift (FCS): the observed data depend on the history through the evolving policies and data-collection process. FCS brings two substantive problems for risk control: 1) efficient risk evaluation for each candidate policy and 2) valid policy selection with high probability risk control. To address these, we propose an efficient permutation-based weighted risk evaluator based on the Sinkhorn algorithm and select policies whose estimated risk upper confidence bounds (UCB) fall below the target threshold, with the UCB obtained through a proposed Gaussian bootstrap method. Theoretically, we prove that our risk evaluator's worst-case variance is no greater than that of the standard importance-weighted evaluator. Also, our policy control method yields an asymptotically valid simultaneous risk bound and provides asymptotic high-probability risk control for the selected policy. Empirically, our method maintains the target risk level, achieves lower risk than baseline methods, has lower variance in risk estimation, and enables reliable policy selection with high-probability risk control.

Visual geometry grounded transformers are strong feed-forward backbones for multi-view 3D reconstruction, but their global attention becomes the dominant inference bottleneck as views and tokens increase. Existing acceleration methods mainly focus on designing compression operators, while compression strengths are often assigned by uniform schedules or offline calibration, overlooking the heterogeneous sensitivity of layers and attention heads during inference. We therefore propose HALO-VGGT, a lightweight online compression allocator requiring no training or calibration for efficient VGGT-style reconstruction. HALO uses a sampled query-key margin proxy to estimate compression sensitivity at the layer and head levels, and assigns hierarchical compression ratios accordingly. Instead of introducing a new compression operator, HALO complements pruning, merging, and sparse attention mechanisms by deciding where and how aggressively they should be applied. HALO improves the trade-off between speedup and accuracy across datasets and backbones, achieving up to 4.20$\times$ speedup and further improving existing merging and sparsity methods by up to 1.46$\times$.

The explosive demand for interactive Large Language Model serving has highlighted the management of the Key-Value cache's dynamic memory footprint as a critical area for performance optimization in inference engines. Modern inference systems overwhelmingly rely on time-centric scheduling heuristics, such as Shortest Job First. However, their theoretical optimality is rooted in traditional schedule modeling, failing to capture the highly dynamic, 2D spatio-temporal geometric growth specific to LLM inference mechanisms. To resolve this, we propose the geometry-aware online scheduling by introducing the Smallest Volume First (SVF) algorithm and its highly efficient variant, 1-bit SVF. Theoretically, we provide a rigorous mathematical foundation for our approach. Utilizing a novel proof methodology, we tighten the worst-case competitive ratio ($\text{CR} \le 48 \rightarrow \text{CR} \le 5$) for SVF with known output lengths. Building upon this core breakthrough, we complete a comprehensive theoretical taxonomy analyzing our algorithms across different traffic scenarios and information availability. Practically, we seamlessly integrate our approach as a plug-and-play layer in vLLM. Extensive evaluations on Llama-3.1 models demonstrate comprehensive performance gains: SVF delivers strong reductions in both average and tail latency, while 1-bit SVF, with merely a single bit information, achieves competitive throughput and latency. This work establishes a theoretically sound and empirically proven approach for resolving memory-constrained scheduling in modern LLM deployments. To facilitate future research, our code is available at \url{https://anonymous.4open.science/r/LLM-inference-scheduling-7970}.

Streaming 3D reconstruction from long monocular video sequences requires maintaining a key-value(KV) cache that grows linearly with sequence length, creating a severe memory bottleneck. Existing approaches either truncate the cache to a fixed set of anchor frames, leading to reconstruction quality degradation, or rely on attention-score heuristics that are agnostic to 3D scene structure,failing to preserve geometrically valuable tokens. To address these problems, we present GHOST (Geometry-Hierarchical Online Streaming Token Eviction), a training-free KV cache management framework that exploits the model's own 3D geometry outputs to evict redundant tokens online. GHOST introduces three mutually reinforcing innovations: a hierarchical dual-level importance scoring scheme, a privilege mechanism that protects special tokens from eviction, and a cosine-similarity-guided layer-wise budget allocation. Experiments on various benchmarks show that GHOST preserves excellent reconstruction quality while cutting the KV cache by nearly half and delivering $1.75\times$ faster inference compared to state-of-the-art methods. Our code and model will be available to the public.

Model-based reinforcement learning in partially observable environments requires inferring hidden states, learning latent dynamics, and planning under the resulting belief. Practical algorithms often solve one aspect of the above pipeline while relying on approximations for the others that are often poorly understood, while existing POMDP theory typically analyzes computationally inefficient theoretical algorithms far from modern deep RL practice. To fill this gap, we propose a practical end-to-end algorithm that approximately solves the hidden state filtering problem via sequential Monte Carlo (SMC), updates a latent dynamics model online, and performs approximate online planning for $d$ steps before bootstrapping leaves with a state-value critic (a QMDP approximation). We analyze each approximation and prove an end-to-end regret bound decomposing the error into model estimation error, particle filter error, Monte Carlo rollout error, and a structural bias term induced by the QMDP approximation controllable by the planning depth that we further analyze in various special cases. The resulting guarantee makes explicit how statistical sample size, particle budget, rollout budget, and planning depth affect performance. We instantiate our algorithm in an MPC-based deep RL framework, demonstrating its practicality on a variety of environments. Our results provide a practical and theoretically grounded route for bridging theory and practice within online decision-making in POMDPs.

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.

The framework of Online Convex Optimization with Memory captures sequential decision-making settings where the learner's instantaneous loss is affected by their past choices, in addition to the most recent decision. We first give a new first-order regret bound in this framework for potentially non-smooth loss functions, with regret scaling as the square root of the loss of the best decision in hindsight, which can be much better than known regret bounds that explicitly scale with the horizon. In fact, our result holds in a generalized non-differentiable setting, which also captures other decision making problems of interest. We then give a faster gradient-based algorithm that yields an improved first-order regret bound for smooth loss functions. As an application, we consider the recently introduced problem of online nonstochastic control, which involves controlling a linear dynamical system subject to adversarial disturbances to minimize convex cost functions, where our results can be adapted to produce novel first-order regret bounds. This means whenever there is a benchmark controller with small loss in hindsight, our regret bounds are significantly smaller than those present in the literature.

Probabilistic spiking neural networks (SNNs) model spike trains as temporal point processes and provide a principled framework for learning with latent spikes. Recent differentiable point-process methods enable path-wise variational learning, but their training still relies on full-sequence backpropagation through time (BPTT), leading to memory costs that grow with the temporal horizon. In this paper, we develop an online variational training framework for probabilistic SNNs based on discrete-time spike response model dynamics. By representing synaptic history with finite-dimensional Markovian traces, our method updates both generative and variational parameters without storing the full temporal computation graph. To handle future-dependent credit assignment from recurrent spike histories, we introduce a horizon-$R$ family of online estimators. Theoretically, we show that the truncation-induced bias decays exponentially with $R$ under the SRM kernel-decay condition. Synthetic experiments validate the predicted horizon-dependent behavior and bias decay, while N-MNIST experiments show competitive classification accuracy and avoid the sequence-length-dependent memory growth of BPTT.

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.

Many bandit systems are deployed with offline historical data, such as past logs from earlier policies. By using these data, one can reduce the amount of online exploration needed early in learning. When the offline and online environments differ, such data can be biased for the online problem. For linear (contextual) bandits, this bias is directional: offline data may be informative in some feature directions and misleading in others. However, prior work typically controls this gap through a known Euclidean bound on the model parameters, which we prove is too coarse to separate easy and hard offline-to-online instances from offline data alone. To address this challenge, we introduce a directional bias certificate $(M_{\mathrm{bias}},\rho)$ that measures the offline-to-online gap through an $M_{\mathrm{bias}}$-induced norm and assigns different bias budgets to different directions. Building on this certificate, we propose \emph{Ellipsoidal-MINUCB}, which augments the online learning with an offline-pooled branch that safely exploits historical data. When the certificate is known, we show that the algorithm matches the standard SupLinUCB rate in the worst case and improves when offline coverage aligns with low-bias directions. When the certificate is unknown, we estimate it adaptively from offline and accumulated online data and establish a corresponding regret guarantee. Numerical experiments support the theory and show gains in aligned regimes.

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.

In Euclidean online convex optimization, first-order and full-information feedback share the minimax regret \(\Theta(DL\sqrt{T})\) over \(T\) rounds, as convex losses can be replaced by their linearizations. On Riemannian manifolds this reduction fails, because the corresponding first-order surrogate of a geodesically convex loss is generally not geodesically convex; we show that this failure has provable consequences. For online convex optimization on Hadamard manifolds with sectional curvature bounded below by \(\kappa<0\) and feasible diameter \(D\), we construct hard hyperbolic-space instances yielding first-order regret lower bounds at the scale \( DL\sqrt{\zeta\, T}, \) where \( \zeta=\sqrt{|\kappa|}D/\tanh(\sqrt{|\kappa|}D) \) is the curvature--diameter factor. Our first lower bound applies to all (possibly randomized) first-order algorithms satisfying a natural geometric-span condition, holding almost surely over the algorithm's internal randomness. Our second lower bound removes the geometric-span restriction for deterministic first-order algorithms, provided the feasible diameter satisfies \(D=\Omega(\log T)\); the proof rests on a new construction that confines the hidden comparator to a single horosphere in hyperbolic space. Combined with existing curvature-free full-information upper bounds, these results yield a feedback-model separation on Hadamard manifolds: full-information algorithms attain \(O(DL\sqrt{T})\) regret, yet the additional \(\sqrt{\zeta}\) factor is unavoidable for first-order feedback whenever either the geometric-span condition holds or the algorithm is deterministic.

We study \emph{bilinear matching bandits}, an online sequential decision problem in which at each round a learner assigns $M$ users to $N$ items via an injective matching $\pi:[M]\hookrightarrow[N]$ and observes semi-bandit feedback with bilinear mean reward $\mathbf{x}_i^\top \mathbf{\Theta}^\star \mathbf{y}_{\pi(i)}$, where the parameter $\mathbf{\Theta}^\star \in \mathbb{R}^{d_1 \times d_2}$ is unknown. We propose \textsc{HybridRRD}, a hybrid algorithm that combines high-width elimination with a row-wise regularized design sampler over the fractional matching polytope. Without assuming $\mathbf{\Theta}^\star$ is low-rank, \textsc{HybridRRD} achieves a high-probability regret bound of $\widetilde{O} (d_2 \sqrt{d_1MT} + Md_1 d_2)$, suppressing problem-scale constants. This improves the leading dimension dependence from $d_1d_2$ to $d_2\sqrt{d_1}$ over the standard Kronecker-linearized contextual combinatorial semi-bandit baseline. We further prove a minimax lower bound of $\Omega(d_2 \sqrt{d_1 M T})$ in a large-item regime, matching the leading regret term up to logarithmic factors. Numerical experiments show that \textsc{HybridRRD} performs favorably against Kronecker-linearized 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.