Daily TMLR digest for Dec 02, 2025
TMLR
Accepted papers
===============
Title: Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
Authors: Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal
Abstract: We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of $O(T^{1-\theta/2})$ with communication complexity of $O(T^{\theta})$ and number of linear optimization oracle calls of $O(T^{2\theta})$ for decentralized upper-linearizable function optimization, for any $0\le \theta \le 1$. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.
URL: https://openreview.net/forum?id=bZ5WD2HUQr
---
Title: kNNSampler: Stochastic Imputations for Recovering Missing Value Distributions
Authors: Parastoo PASHMCHI, Jérôme Benoit, Motonobu Kanagawa
Abstract: We study a missing-value imputation method, termed kNNSampler, that imputes a given unit's missing response by randomly sampling from the observed responses of the k most similar units to the given unit in terms of the observed covariates. This method can sample unknown missing values from their distributions, quantify the uncertainties of missing values, and be readily used for multiple imputation. Unlike popular kNNImputer, which estimates the conditional mean of a missing response given an observed covariate, kNNSampler is theoretically shown to estimate the conditional distribution of a missing response given an observed covariate. Experiments illustrate the performance of kNNSampler. The code for kNNSampler is made publicly available (https://github.com/SAP/knn-sampler).
URL: https://openreview.net/forum?id=4CDnIACCQG
---
Title: Learning to Rank Features to Enhance Graph Neural Networks for Graph Classification
Authors: Fouad Alkhoury, Tamas Horvath, Christian Bauckhage, Stefan Wrobel
Abstract: A common strategy to enhance the predictive performance of graph neural networks (GNNs) for graph classification is to extend input graphs with node- and graph-level features. However, identifying the optimal feature set for a specific learning task remains a significant challenge, often requiring domain-specific expertise. To address this, we propose a general two-step method that automatically selects a compact, informative subset from a large pool of candidate features to improve classification accuracy. In the first step, a GNN is trained to estimate the importance of each feature for a given graph. In the second step, the model generates feature rankings for the training graphs, which are then aggregated into a global ranking. A top-ranked subset is selected from this global ranking and used to train a downstream graph classification GNN. Experiments on real-world and synthetic datasets show that our method outperforms various baselines, including models using all candidate features, and achieves state-of-the-art results on several benchmarks.
URL: https://openreview.net/forum?id=WmZGvWRAWb
---
Title: Pushing the Limits of Sparsity: A Bag of Tricks for Extreme Pruning
Authors: Andy Li, Aiden Durrant, Milan Markovic, Tianjin Huang, Souvik Kundu, Tianlong Chen, Lu Yin, Georgios Leontidis
Abstract: Pruning of deep neural networks has been an effective technique for reducing model size while preserving most of the performance of dense networks, crucial for deploying models on memory and power-constrained devices. While recent sparse learning methods have shown promising performance up to moderate sparsity levels such as 95% and 98%, accuracy quickly deteriorates when pushing sparsities to extreme levels due to unique challenges such as fragile gradient flow. In this work, we explore network performance beyond the commonly studied sparsities, and develop techniques that encourage stable training without accuracy collapse even at extreme sparsities, including 99.90%, 99.95\% and 99.99% on ResNet architectures. We propose three complementary techniques that enhance sparse training through different mechanisms: 1) Dynamic ReLU phasing, where DyReLU initially allows for richer parameter exploration before being gradually replaced by standard ReLU, 2) weight sharing which reuses parameters within a residual layer while maintaining the same number of learnable parameters, and 3) cyclic sparsity, where both sparsity levels and sparsity patterns evolve dynamically throughout training to better encourage parameter exploration. We evaluate our method, which we term Extreme Adaptive Sparse Training (EAST) at extreme sparsities using ResNet-34 and ResNet-50 on CIFAR-10, CIFAR-100, and ImageNet,achieving competitive or improved performance compared to existing methods, with notable gains at extreme sparsity levels.
URL: https://openreview.net/forum?id=XX9JdOJD8R
---
Title: Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations
Authors: Dimitris Bertsimas, Caio de Próspero Iglesias, Nicholas A. G. Johnson
Abstract: We study Sparse Multiple Kernel Learning (SMKL), which is the problem of selecting a sparse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing $\ell_1$‐regularized approaches that approximate a sparsifying penalty, we formulate the problem by imposing an explicit cardinality constraint on the kernel weights and add an $\ell_2$ penalty for robustness. We solve the resulting non-convex minimax problem via an alternating best response algorithm with two subproblems: the $\alpha$‐subproblem is a standard kernel SVM dual solved via LIBSVM, while the $\beta$‐subproblem admits an efficient solution via the Greedy Selector and Simplex Projector algorithm. We reformulate SMKL as a mixed integer semidefinite optimization problem and derive a hierarchy of semidefinite convex relaxations which can be used to certify near-optimality of the solutions returned by our best response algorithm and also to warm start it. On ten UCI benchmarks, our method with random initialization outperforms state-of-the-art MKL approaches in out of sample prediction accuracy on average by $3.34$ percentage points (relative to the best performing benchmark) while selecting a small number of candidate kernels in comparable runtime. With warm starting, our method outperforms the best performing benchmark's out of sample prediction accuracy on average by $4.05$ percentage points. Our convex relaxations provide a certificate that in several cases, the solution returned by our best response algorithm is the globally optimal solution.
URL: https://openreview.net/forum?id=Y5icwFwkyh
---
Title: A Shortcut-aware Video-QA Benchmark for Physical Understanding via Minimal Video Pairs
Authors: Benno Krojer, Mojtaba Komeili, Candace Ross, Quentin Garrido, Koustuv Sinha, Nicolas Ballas, Mido Assran
Abstract: Existing benchmarks for assessing the spatio-temporal understanding and reasoning abilities of video language models are susceptible to score inflation due to the presence of shortcut solutions based on superficial visual or textual cues. This paper mitigates the challenges in accurately assessing model performance by introducing the Minimal Video Pairs (MVP) benchmark, a simple shortcut-aware video QA benchmark for assessing the physical understanding of video language models. The benchmark is comprised of 55K high-quality multiple-choice video QA examples focusing on physical world understanding. Examples are curated from nine video data sources, spanning first-person egocentric and exocentric videos, robotic interaction data, and cognitive science intuitive physics benchmarks. To mitigate shortcut solutions that rely on superficial visual or textual cues and biases, each sample in MVP has a minimal-change pair — a visually similar video accompanied by an identical question but an opposing answer. To answer a question correctly, a model must provide correct answers for both examples in the minimal-change pair; as such, models that solely rely on visual or textual biases would achieve below random performance. Human performance on MVP is 92.9%, while the best open-source state-of-the- art video-language model achieves 40.2% compared to random performance at 25%.
URL: https://openreview.net/forum?id=gvFgNJcSw1
---
Title: Outcome-based Reinforcement Learning to Predict the Future
Authors: Benjamin Turtel, Danny Franklin, Kris Skotheim, Luke Hewitt, Philipp Schoenegger
Abstract: Reinforcement Learning with Verifiable Rewards (RLVR) has been an effective approach for improving Large Language Models' reasoning in domains such as coding and mathematics. Here, we apply RLVR methods towards forecasting future real-world events – a challenging task for RL due to the very noisy (and delayed) outcomes involved. Using a novel dataset of recent questions from a prediction market, and accompanying relevant news headlines, we show that a compact (14B) reasoning model can be trained to match or surpass the predictive accuracy of frontier models like o1, while greatly improving probabilistic calibration. The model's performance is also practically meaningful: in a Polymarket trading simulation, we estimate that its bets would have yielded a return on investment of over 10\% across all questions in the test set. We detail and compare approaches used in training our model, including augmenting our training-data with synthetic prediction questions, guardrails for learning stability, and median prediction sampling at inference-time.
URL: https://openreview.net/forum?id=bbhdeL8EUX
---
New submissions
===============
Title: SLIP: Securing LLM’s IP Using Weights Decomposition
Abstract: Large language models (LLMs) have recently seen widespread adoption, in both academia
and industry. As these models grow, they become valuable intellectual property (IP), reflecting
enormous investments by their owners. Moreover, the high cost of cloud-based
deployment has driven interest towards deployment to edge devices, yet this risks exposing
valuable parameters to theft and unauthorized use. Current methods to protect models’
IP on the edge have limitations in terms of practicality, loss in accuracy, or suitability to
requirements. In this paper, we introduce a novel hybrid inference algorithm, named SLIP,
designed to protect edge-deployed models from theft. SLIP is the first hybrid protocol that
is both practical for real-world applications and provably IP-preserving, while having zero
accuracy degradation and minimal impact on latency. It involves partitioning the model
between two computing resources, one secure but expensive, and another cost-effective but
untrusted. This is achieved through matrix decomposition, ensuring that the secure resource
retains a maximally sensitive portion of the model’s IP while performing a minimal amount
of computations, and vice versa for the untrusted resource. Importantly, the protocol includes
guarantees that prevent attackers from exploiting the partition to infer the model
weights. Finally, we present experimental results that show the robustness and effectiveness
of our method, positioning it as a compelling solution for protecting LLMs.
URL: https://openreview.net/forum?id=3MAGV75ndV
---
Title: On the Vulnerability of Discrete Graph Diffusion Models to Backdoor Attacks
Abstract: Diffusion models have demonstrated remarkable generative capabilities in continuous data domains such as images and videos. Recently, discrete graph diffusion models (DGDMs) have extended this success to graph generation, achieving state-of-the-art performance. However, deploying DGDMs in safety-critical applications—such as drug discovery—poses significant risks without a thorough understanding of their security vulnerabilities.
In this work, we conduct the first study of backdoor attacks on DGDMs, a potent threat that manipulates both the training and generation phases of graph diffusion. We begin by formalizing the threat model and then design a backdoor attack that enables the compromised model to: 1) generate high-quality, benign graphs when the backdoor is not activated,
2) produce effective, stealthy, and persistent backdoored graphs when triggered, and
3) preserve fundamental graph properties—permutation invariance and exchangeability—even under attack.
We validate 1) and 2) empirically, both with and without backdoor defenses, and support 3) through theoretical analysis.
URL: https://openreview.net/forum?id=Brn7lUoDtf
---
Title: Incremental3D: Incremental 3D Scene Generation with Scene Graph for Immersive Teleoperation
Abstract: Graph-based 3D scene generation aims to synthesize 3D environments conditioned on scene graphs and has been widely explored in applications such as 3D gaming and interior design. However, its potential for immersive robotic teleoperation has been largely overlooked. In this setting, transmitting lightweight incremental 3D scene graphs from the robot-side to the operator-side is far more bandwidth-efficient and lower-latency than streaming raw RGB or point-cloud data. %from the robot side to the operator side, and
At the same time, recent advances in robot-side 3D scene-graph learning now make such incremental scene-graphs readily obtainable from RGB-D inputs. % for this new teleoperation system. Despite this opportunity, existing scene-graph-based 3D scene generation methods are fundamentally single-shot: inserting even a single new object requires regenerating the entire scene. This global re-computation incurs prohibitive latency and renders existing approaches unsuitable for real-time immersive robotic teleoperation, where the scene graph, and therefore the scene itself, is built and generated incrementally as the robot moves through the environment. To address this limitation, we propose \textit{Incremental3D}, the first framework capable of incremental graph-to-3D scene generation for teleoperation applications. \textit{Incremental3D} augments an existing scene graph with a global classification (CLS) node that maintains a holistic representation of the evolving environment. At each update step, the CLS node aggregates global context and conditions the generation of newly added objects, enabling geometry synthesis and spatial prediction without recomputing unchanged regions. Extensive experiments demonstrate that \textit{Incremental3D} achieves 38 Hz generation speed while maintaining high spatial accuracy, indicating its suitability for real-time teleoperation and other latency-sensitive 3D applications.
URL: https://openreview.net/forum?id=am8Zv3R8GW
---
Title: On the Unreasonable Effectiveness of Last-layer Retraining
Abstract: Last-layer retraining (LLR) methods --- wherein the last layer of a neural network is reinitialized and retrained on a held-out set following ERM training --- have garnered interest as an efficient approach to rectify dependence on spurious correlations and improve performance on minority groups. Surprisingly, LLR has been found to improve worst-group accuracy even when the held-out set is an imbalanced subset of the training set. We initially hypothesize that this ``unreasonable effectiveness'' of LLR is explained by its ability to mitigate neural collapse through the held-out set, resulting in the implicit bias of gradient descent benefiting robustness. Our empirical investigation does not support this hypothesis. Instead, we present strong evidence for an alternative hypothesis: that the success of LLR is primarily due to better group balance in the held-out set. We conclude by showing how the recent algorithms CB-LLR and AFR perform implicit group-balancing to elicit a robustness improvement.
URL: https://openreview.net/forum?id=h81ztbrkFb
---
Title: Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradients
Abstract: We unify two seemingly distinct approaches to policy gradient optimization for the Pass@K objective in reinforcement learning with verifiable rewards (RLVR): direct REINFORCE-style methods and advantage-shaping techniques that modify GRPO. By reverse-engineering existing advantage-shaping algorithms, we reveal that they implicitly optimize surrogate rewards. We specifically interpret practical ``hard-example upweighting'' modifications to GRPO as reward-level regularization. Conversely, starting from surrogate reward objectives, we provide a simple recipe for deriving both existing and new advantage-shaping methods.
This perspective provides a lens for RLVR beyond our original motivation of Pass@K.
URL: https://openreview.net/forum?id=R1RhBFUk8t
---
Title: Investigating Linguistic Steering: An Analysis of Adjectival Effects Across Large Language Model Architectures
Abstract: Achieving reliable control of Large Language Models (LLMs) requires a precise, scalable understanding of how they interpret linguistic cues. We introduce a rigorous framework using Shapley values to quantify the steering effect of individual adjectives on model performance, moving beyond anecdotal heuristics to principled attribution. Applying this method to 100 adjectives across a diverse suite of models (including o3, gpt-4o-mini, phi-3, llama-3-70b, and deepseek-r1) on the MMLU benchmark, we uncover several critical findings for AI alignment. First, we find that a small subset of adjectives act as disproportionately powerful "levers," yet their effects are not universal. Cross-model analysis reveals a "family effect": models of a shared lineage exhibit correlated sensitivity profiles, while architecturally distinct models react in a largely uncorrelated manner, challenging the notion of a one-size-fits-all prompting strategy. Second, focused follow-up studies demonstrate that the steering direction of these powerful adjectives is not intrinsic but is highly contingent on their syntactic role and position within the prompt. For larger models like gpt-4o-mini, we provide the first quantitative evidence of strong, non-additive interaction effects where adjectives can synergistically amplify, antagonistically dampen, or even reverse each other's impact. In contrast, smaller models like phi-3 exhibit a more literal and less compositional response. These results suggest that as models scale, their interpretation of prompts becomes more sophisticated but also less predictable, posing a significant challenge for robustly steering model behavior and highlighting the need for compositional and model-specific alignment techniques.
URL: https://openreview.net/forum?id=xN7NYpQeBm
---
Title: CI-CBM: Class-Incremental Concept Bottleneck Model for Interpretable Continual Learning
Abstract: Catastrophic forgetting remains a fundamental challenge in continual learning, in which models often forget previous knowledge when fine-tuned on a new task. This issue is especially pronounced in class incremental learning (CIL), which is the most challenging setting in continual learning. Existing methods to address catastrophic forgetting often sacrifice either model interpretability or accuracy. To address this challenge, we introduce Class-Incremental Concept Bottleneck Model (CI-CBM), which leverage novel techniques, including concept regularization and pseudo-concept generation to maintain interpretable decision processes throughout incremental learning phases.
Through extensive evaluation on seven benchmark datasets, CI-CBM achieves comparable performance to black-box models and significantly outperforms previous interpretable approaches in CIL, with an average 36\% accuracy gain.
CI-CBM provides both interpretable decisions on individual inputs and understandable global decision rules, as shown in our experiments, thereby demonstrating that human-understandable concepts can be maintained during incremental learning without compromising model performance.
Our approach is effective in both pretrained and non-pretrained scenarios; in the latter, the backbone is trained from scratch during the first learning phase.
URL: https://openreview.net/forum?id=Wf6OpLgj2i
---
Title: Character-Level Perturbations Amplify LLM Jailbreak Attacks
Abstract: Contemporary large language models (LLMs) exhibit remarkable capabilities, yet their subword tokenization mechanisms suffer from a vulnerability, whereby small character-level perturbations can re-partition text into unfamiliar subwords, degrading model performance across various tasks. Building on this, we show that this tokenization vulnerability also compromises safety mechanisms in jailbreak scenarios. We introduce a simple, model- and template-agnostic character-level jailbreak method and demonstrate that minimal character-level perturbations effectively increase the success rates of both simple and complex jailbreak attacks across multiple LLMs. We reveal that these perturbations lead to over-fragmented tokenization and token representation drift, resulting in substantial divergence in the semantic representations of words. Furthermore, our analysis using word-level semantic recovery and sentence-level spelling error detection and correction shows that models struggle to reconstruct the original semantics for perturbed content. In addition, layer-wise probe classifiers also fail to reliably detect the harmful intent of perturbed jailbreak prompts, further exposing the models' vulnerability in comprehending adversarially perturbed input. Finally, we find that in certain cases, perturbations reduce rather than increase attack success, as the corrupted spans fit less naturally into the template. Together, our findings demonstrate that tokenization-induced vulnerabilities compromise safety mechanisms, underscoring the need for investigation into mitigation strategies.
URL: https://openreview.net/forum?id=BXsOIppKEI
---