Computational Complexity · Cross-listed from quant-ph
The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
Itay Shalit and Mark Zhandry
The commuting local-
Hamiltonian (CLH) problem is a restriction of the local-
Hamiltonian problem, in which the terms of the
Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local
Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through
quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-
Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.
Read the full abstract ▾
Artificial Intelligence
Routing Probes Can Improve Without New Information: An Exact-Null Audit of Uncertainty Beyond Model Outputs
Wenhao Liang, Lin Yue, Wei Emma Zhang et al. (+3 more)
Routing signals of modern
vision transformers – expert gates,
attention-residual weights and halting scores – often improve probes that predict whether the model is correct, and the improvement is commonly read as evidence that routing carries information about errors beyond the model's outputs. We test this inference directly: keeping real output-routing pairs, we redraw correctness labels from a frozen output-only generator fitted on disjoint data, so that routing is uninformative by construction. Under this exact label null, a width-matched MLP comparison still reports a routing gain in 51.3% of confidence-only evaluations (308/600), while a linear comparison reports none. Holding each training trajectory fixed on a six-model panel and selecting the checkpoint by validation log loss instead of validation accuracy removes the detections (50/120 to 0/120, and 83/120 to 0/120 in an independently implemented probe), identifying accuracy-based checkpoint selection as the cause; across all output views the raw detection rate falls from 27.5% (528/1,920) to zero observed detections. The repaired comparison is not sensitive, detecting an implanted signal of about 0.005 nats in 0/20 replicates in each of two matched settings, whereas a conditional permutation test built on an estimated routing law detects it in 11/20 and 10/20 and rejects rarely under the null. On real correctness labels, the conditional analysis yields model-relative evidence in five DeiT
attention-residual families; in four it persists under two specified variants of the conditional law, and no family passes an additional noise criterion. Fitting a better probe and testing for incremental information are different problems, and each needs its own validation.
Read the full abstract ▾
All authors Wenhao Liang, Lin Yue, Wei Emma Zhang, Mingyu Guo, Olaf Maennel, Weitong Chen
Machine Learning
Loop-Free Inverse Reinforcement Learning via Sequential Value Recovery with Q-Score Matching
Yang Chen, Yitan Zhang, Michael Witbrock et al. (+1 more)
Inverse Reinforcement Learning (IRL) aims to recover a reward function that explains expert demonstrations. Existing IRL methods typically rely on a bi-level optimization procedure that alternates between reward learning and policy optimization, leading to substantial computational burden and training instability. In this work, we introduce a different route that eliminates policy optimization entirely by leveraging
diffusion policies. Our key insight is that a
diffusion policy encodes the action-gradient structure of the optimal soft Q function, enabling reward learning to be cast as a sequence of value recovery problems, thereby allowing us to bypass reward-policy loops inherent in prior IRL methods. Specifically, our method proceeds in three stages: (I) recovering the optimal soft Q function via action-gradient matching and estimating the corresponding soft value function (LogSumExp of Q values) in a way inspired by Gumbel regression; (II) calibrating these soft values by inferring a state-dependent offset; (III) extracting the reward by enforcing Bellman consistency. This leads to Loop-Free Inverse Reinforcement Learning (LFIRL), a fully offline
algorithm that operates in a simple, loop-free, and sequential manner. LFIRL is simple to implement and significantly improves training efficiency while maintaining strong reward recovery performance. Empirically, across Maze, Franka Kitchen, Adroit Hand Pen, and Push-T
benchmarks, LFIRL achieves 2-3x speedup over the fastest baselines, while matching or surpassing state-of-the-art methods in reward recovery quality.
Read the full abstract ▾
All authors Yang Chen, Yitan Zhang, Michael Witbrock, Shuyue Hu
Cryptography and Security
APTInvestBench: Evaluating Autonomous APT Investigation under Varying Telemetry
Yu Wang, Shuhao Li, Tao Yin et al. (+4 more)
Large
language model (LLM)
agents could help security operations centers (SOCs) investigate advanced persistent threats (APTs) by turning weak leads into evidence for intrusion scoping and response. Yet success under one telemetry setting does not establish robustness to changes in log collection, retention, or sampling. We introduce APTInvestBench, a
benchmark for evaluating cross-telemetry robustness in autonomous APT investigation. It comprises 370 cases across seven SOC-inspired conditions, derived from 56 report-informed attack reconstructions with 16.4 million log records.
Agents investigate unverified leads and submit reports with record-level citations. Fixed action-level support requirements track sufficient evidence across available logs, query returns, and formal citations, separating telemetry limitations from acquisition and reporting gaps. Across eleven LLMs,
agents acquire sufficient evidence for 44.3% of recoverable attack actions on average, while formal citations support only 25.0%. More importantly, aggregate coverage can conceal substantial instability: from Full to endpoint-only telemetry, coverage declines by only 1.6 percentage points, yet 35.5% of previously covered actions lose sufficient citation support despite remaining recoverable. Across four frameworks, such losses persist even when registered supporting records remain unchanged. APTInvestBench provides reusable investigation environments and diagnostic evaluation for identifying these gaps and developing more reliable defensive
agents.
Read the full abstract ▾
All authors Yu Wang, Shuhao Li, Tao Yin, Ziyang Li, Xueying Zhao, Peishuai Sun, Jiang Xie
Human-Computer Interaction
Measuring Student Self-Assessment against Viva-Demonstrated Mastery in a Large First-Year Programming Course
Sakshi Sharma, Pavani Ayinampudi, Aditya B.M.V. et al. (+5 more)
Mastery-based education increasingly places the reporting of learning progress in students' hands, who record task completion on learning dashboards. The usefulness of such self-reports depends on how closely reported mastery corresponds to demonstrated competence. Most evidence on student self-assessment compares an overall self-rating with an overall examination score and therefore provides limited evidence about which tasks or which students account for the mismatch. This study examines first-year students' self-assessment against viva-demonstrated mastery at the level of individual tasks across a ladder of sixty programming tasks. The study draws on a large first-year programming course taught in 2023, involving 203 students and 12 examiners, in which every reported task was verified through an oral viva. Because a task entered the Viva only after it was reported, the design is one-sided and captures over-estimation but not under-estimation. Of 11,093 reported tasks, 10,885 (98.1%) were demonstrated, indicating a high degree of correspondence between self-report and demonstrated mastery. The remaining 208 overestimations were not evenly distributed. A small number of students accounted for most of the errors, and they occurred mainly on difficult tasks near the end of the task ladder rather than on higher-point tasks. This task-level analysis shows that high overall self-assessment accuracy can coexist with specific areas where reported and demonstrated mastery diverge. It also provides a practical basis for directing additional verification and formative feedback toward students and tasks where such divergence is more likely.
Read the full abstract ▾
All authors Sakshi Sharma, Pavani Ayinampudi, Aditya B.M.V., Jinal Gupta, Prakash Hegade, Rohit Sharma, Meenakshi V, S.R.S. Iyengar
Information Retrieval
Text-Video Retrieval via Multi-Dimensional Saliency Assessment and Granularity-Aware Query Decomposition
Shuquan Wei, Xi Chen, Xu Chen et al. (+1 more)
Text-
video retrieval, which aims to bridge visual and textual modalities by learning a joint
embedding space, has become a crucial task in
multimodal intelligence. Despite extensive efforts to mitigate visual redundancy, previous methods typically rely on a single-aspect criterion to assess visual importance, overlooking the multifaceted spatiotemporal nature of
video. In addition, encoding text into a single global
embedding to align with
videos compresses temporal events and spatial entities into a unified representation space, further aggravating cross-modal misalignment. To address these issues, we propose MMTI, a method that jointly mitigates visual redundancy and enables multi-grained text-
video interaction to achieve accurate multi-grained semantic
alignment. Specifically, a key feature selection (KFS) mechanism adaptively identifies and aggregates informative frames and patches by jointly evaluating multi-dimensional saliency and learnable importance scores, effectively compacting dense visual features and mitigating visual redundancy. Furthermore, our proposed multi-grained text-
video interaction module (TVIM) employs a dynamic gating mechanism to decompose the text query into sentence, frame, and patch queries (SFP), enabling multi-grained text-
video alignment. Complementary
alignment at different granularities is thereby achieved. Extensive experiments on four standard
benchmarks demonstrate that our method outperforms state-of-the-art methods.
Read the full abstract ▾
All authors Shuquan Wei, Xi Chen, Xu Chen, Xiangyang Jia
Robotics
DrivingBench: Can Vision-Language Models Drive a Toyota Corolla?
Aditya Ramabadran, Simon Mahns and Tobias Gessler
Frontier models excel at many digital
benchmarks, yet their ability to drive a real car, an everyday human skill, remains largely untested. We present DrivingBench, to our knowledge the first
benchmark where general-purpose
vision-
language models must drive a real car. Through three tools, the models see camera frames from a Toyota Corolla and directly command its steering and velocity around a parking lot cone course at low speeds. The car may continue moving while the model thinks and new commands replace the currently running one, so inference latency is part of the task, testing the models' abilities to observe, act, monitor, recover, and complete a long-horizon objective under such constraints. We
benchmark GPT-6 Astra, Claude Fable 5.1, GPT-5.6 Sol, and Grok 4.6 in vendor-native harnesses (Codex, Claude Code, Cursor) with up to three attempts each in one conversation; Astra is the only model to finish the course, on its second attempt, with no other attempt passing 50% of the course. Two of the four models improved materially across attempts with retained context. We also detail the design principles behind our action interface, and show how the tool output format and the framing of the task combined to determine whether models would drive at all or refuse. We release our harness,
prompts, course map, and traces with
video and telemetry for reproducibility.
Read the full abstract ▾
Computers and Society
Breaking News Out of the Filter Bubble: Generative AI Search Diversifies Collective Attention and Raises Shared Information Consumption
Heeseung Andrew Lee, Dokyun Lee, Gwanhoo Lee et al. (+1 more)
Generative AI search and AI overviews are transforming access to information and news, renewing concerns that readers will encounter a narrower range of topics and have less in common. We examine these concerns via a randomized field experiment with 37,561 readers at The Washington Post. Both groups searched the same archive, but treatment readers also received AI answers with article citations above conventional results. Measuring consumption across displayed answers and opened articles, we find that AI search expands the reach of widely read topics and increases overlap in readers' topic consumption. At the same time, consumption becomes less concentrated and shifts toward less-popular topics, both within readers and across the audience. AI answers account for most of the increase in shared information, delivering it without requiring article clicks and broadening exposure beyond the articles readers open. Cited articles also contribute to the shift toward less-popular topics. Readers shift from conventional-result clicks and browsing toward cited articles and follow-up searches. More frequent searching offsets lower article consumption per search, producing a small increase in article consumption per reader. Total information consumption per minute also rises. Generative AI search can thus diversify collective
attention while strengthening the information readers have in common.
Read the full abstract ▾
All authors Heeseung Andrew Lee, Dokyun Lee, Gwanhoo Lee, Dongwon Lee
Cryptography and Security · Cross-listed from quant-ph
Certified Randomness with Optimal Rate
Siddhartha Jain, Saachi Mutreja and Bhaskar Roberts
The generation of certified random bits is an emerging near-term application of
quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-
entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed. We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the
quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung. We also define and construct a proof of conditional min-
entropy, which certifies optimal min-
entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-
entropy conditioned on all previous messages.
Read the full abstract ▾
Cryptography and Security · Cross-listed from quant-ph
Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
Zvika Brakerski, Andrew Huang, Yael Tauman Kalai et al. (+1 more)
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the post-
quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least $t$ of the executions are accepted (for some threshold $t$). Prior to this work, these results were known only when the cheating prover was assumed to be classical, and it was not known how to achieve tight bounds. As a corollary, we construct the first constant-round succinct argument for $\mathsf{QMA}$ with negligible completeness and soundness errors assuming only the existence of
quantum homomorphic encryption.
Read the full abstract ▾
All authors Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner
Machine Learning
Robust Risk-Sensitive Reinforcement Learning from Corrupted Human Feedback
Xinyi Ni and Lifeng Lai
Reinforcement learning with human feedback (RLHF) learns from human comparisons, which can be corrupted or deliberately manipulated. This paper studies online risk-sensitive RLHF with static conditional value-at-risk (CVaR) under
adversarial preference-label flips. We consider additive linear rewards and a fixed-reference protocol with one comparison per episode and at most $C$ flipped labels over $K$ episodes. We propose weighted streamed-preference CVaR RLHF (WSP-CVaR-RLHF), which combines uncertainty-weighted reward estimation with optimistic augmented-state CVaR planning. For known transitions and normalized rewards, we establish the regret bound $\widetilde{O}\left(\frac{d}{\kappa}\sqrt{\frac{K}{\alpha}}+\frac{dC}{\kappa\alpha}\right)$ up to lower-order terms, where $d$ is the reward-feature dimension, $\alpha$ is the CVaR level, and $\kappa$ characterizes the preference link. The bound separates the clean statistical cost from the penalty caused by corrupted feedback. We further extend the analysis to unknown tabular transitions, where the trajectory distribution entering the CVaR objective must be learned together with the reward. We address the resulting coupled uncertainty using rectangular transition confidence sets, joint optimistic planning, and a history-level CVaR simulation argument. Experiments under four
adversarial attacks demonstrate that WSP-CVaR-RLHF consistently reduces cumulative regret relative to its unweighted robust counterpart while preserving confidence-set coverage.
Read the full abstract ▾
Machine Learning
Signal-Routed Temperature Scaling: Low-Capacity Risk-Conditioned Calibration for Small Validation Budgets
Wenhao Liang, Liangwei Nathan Zheng, Lin Yue et al. (+4 more)
When a classifier is recalibrated from only a few thousand held-out examples, the capacity of the calibration map becomes a statistical design choice rather than a purely architectural one: a scalar map can underfit structured residual miscalibration, while a highly adaptive map can be hard to estimate reliably from so small a split. We disentangle the calibration objective from adaptive capacity and propose signal-routed temperature scaling (SRTS-BCE), a 10-parameter, argmax-preserving calibrator that cross-fits a correctness-risk score over six logit statistics and fits one top-label-BCE temperature per $K=3$ risk groups, recovering TvA-TS as its $K=1$ limit. On fine-tuned CIFAR-100 / ViT-B/16, SRTS-BCE reduces $\mathrm{ECE}_{15}$ from 1.65 (scalar TvA-TS) to 0.96, matching the higher-capacity SMART+BCE head (0.95) at the full calibration budget. The two regimes separate as the budget shrinks: at $n=250$ SRTS-BCE beats SMART+BCE on all three CIFAR-100 backbones (the seed-to-draw hierarchical interval excludes zero), whereas the flagship comparison against the scalar remains directional. A protocol-frozen Tiny-ImageNet follow-up reproduces the small-budget separation and exhibits a budget-dependent ranking reversal on Swin-T; matched routing and map controls show that the effect is tied neither to the learned router nor to discrete grouping. Together the results identify post-hoc calibrator capacity as a finite-sample design choice whose preferred level shifts with the amount of available calibration data.
Read the full abstract ▾
All authors Wenhao Liang, Liangwei Nathan Zheng, Lin Yue, Wei Emma Zhang, Mingyu Guo, Olaf Maennel, Weitong Chen
Cryptography and Security
PrivCert: Certifying Statement Support under Differential Privacy
Tsubasa Takahashi and Takumi Hiraoka
Differentially private (DP) text generation can protect individual records, but
privacy alone does not specify what evidence a released statement carries about the underlying data. We identify this as an evidence gap: a private report may contain plausible claims without indicating whether they are strongly supported by the private
dataset. We introduce PrivCert, a framework for
privacy-preserving reporting that makes statement support explicit through
privacy-preserving certificates and emit-or-abstain decisions. As a canonical instantiation, PrivCert-PF (Proposal-and-Filter) separates data-independent candidate discovery from private support certification, emitting only statements whose support passes a private evidence test. We provide theoretical grounding for this framework by characterizing the limits of implicit evidence under DP, deriving a sharp
privacy–honesty frontier for single-statement certification, and establishing a worst-case cost for fine-grained multi-statement certification. Experiments on synthetic tasks and TAB, WildChat, and Yelp show that explicit certification maintains low unsupported emission, while free-text DP baselines frequently produce low-support claims under the same declared support semantics. We further show that the PrivCert contract can be realized with histogram, sparse-vector, and Gaussian mechanisms, and use DP synthetic data to illustrate an important boundary: support in a private proxy does not automatically certify support in the original data. Together, these results position
privacy-preserving reporting as an evidence-design problem: not only how to generate private text, but what a private report can substantiate about its underlying data.
Read the full abstract ▾
Machine Learning
EFormer: Temporally Aligned Local Correction for Continuous sEMG-Based Hand Pose Tracking
JiaCheng Ge and SiYu Zhang
Surface electromyography (sEMG) provides a wearable, camera-free signal for continuous hand-motion inference. Mapping muscle activity to joint kinematics remains challenging because the recorded waveforms are indirect measurements, their relationship with motion changes over time, and individual anatomy and sensor placement alter the signal distribution. This paper presents EFormer, a residual feature-correction network built on a frozen tracking backbone. EFormer combines a high-rate event branch, temporally aligned local cross-
attention, two causal rotary position
embedding (RoPE) temporal layers, and a bounded, dynamically gated residual. EFormer receives 16-channel sEMG sampled at 2 kHz and fuses a 64-channel tracking representation at 25 Hz with a 128-channel event representation at 200 Hz. Cross-
attention uses a nominal delay of 100 ms, a 300 ms history parameter, and a 50 ms tolerance; its causal mask restricts each query to events occurring 50-400 ms earlier. The correction scale is 0.15. The evaluated continuation-training configuration contains 585,376 trainable parameters and 5,974,508 frozen parameters. On the test set, EFormer achieves an MAE of 0.1546634 rad, an RMSE of 0.24063 rad, and an R^2 of 0.74801, compared with 0.1745326 rad, 0.2715448 rad, and 0.6791103 for the official tracking baseline. EFormer reduces MAE by 11.38% relative to the baseline. The results show that temporally aligned event-feature correction can reduce continuous hand-pose tracking error.
Read the full abstract ▾
Machine Learning
Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback
Jingkai Huang, Yunfan Zhang, Will Ma et al. (+2 more)
Self-consistency samples many
reasoning trajectories and aggregates their final answers, treating the LLM as a black box that returns one answer per trajectory. Yet the final answer of each trajectory is sampled from a softmax vector that is available from the model's log-probabilities. We refer to this as the grey-box setting in which each trajectory reveals this answer distribution rather than a single draw from it. We formulate efficient inference in this setting as sequential mode identification with distribution-valued observations: sample trajectories one at a time and stop as soon as the LLM's modal answer is identified at a prescribed confidence level. We characterize the asymptotic stopping rate of mode identification with distribution-valued observations exactly and show that it is never worse than the black-box rate. We then propose the ASC-D
algorithm, a betting stopping rule that attains this asymptotic stopping rate. On MMLU-Redux, ASC-D uses $46.4$–$95.6\%$ fewer trajectories than answer-only adaptive self-consistency baselines and achieves the highest fixed-budget correct-certification rate across three open-source models.
Read the full abstract ▾
All authors Jingkai Huang, Yunfan Zhang, Will Ma, Weihua Zhou, Zhengyuan Zhou
Computer Vision
On the Relaxation of Conditional Independence Assumption for Image Segmentation
Zixun Wang and Ben Dai
In semantic
segmentation, a recent line of RankSEG methods directly optimizes Dice/IoU scores at inference time, improving
alignment with evaluation metrics without modifying model training. Despite its theoretical and empirical success, RankSEG relies on the restrictive Conditional Independence Assumption (CIA), which ignores crucial label correlations and therefore degrades performance in ambiguous or low-contrast scenarios. However, accounting for full label dependence is computationally prohibitive, requiring $\mathcal{O}(d^3)$ time. To address this, we replace the CIA with a Spatially Localized Dependence (SLD) structure that captures local label correlations while keeping the dependence model tractable. We further overcome the remaining computational bottleneck via a Reciprocal Moment Approximation coupled with a novel fixed-point optimization strategy that eliminates exhaustive search. The proposed
algorithm achieves a highly practical $\mathcal{O}(d \log d)$ complexity and consistently outperforms conventional argmax and CIA-based RankSEG across diverse
segmentation benchmarks. Improvements are significant in low-contrast or small-object scenarios, where label dependence offers valuable signals complementary to image information for accurate
segmentation. The code of experiments is available at https://github.com/ZixunWang/RankSEG-DEP.
Read the full abstract ▾
Artificial Intelligence
Learning What to Forget: Distributional Unlearning for LLM Representation Spaces
Pinaki Mohanty, Haoran Tang, Maggie Makar et al. (+1 more)
Machine learning systems increasingly face the need to remove the influence of entire data domains, such as toxic
language, harmful behavior, or topical content, rather than isolated records. Recent work formalizes this problem as distributional unlearning: selecting a subset of a forget domain whose removal moves the training distribution away from an unwanted population while preserving proximity to the desired one. However, existing analyses often impose parametric assumptions to obtain tractable selection rules. These assumptions may be poorly suited to high-dimensional
language-model representations. We introduce Mamushi, a framework for non-parametric distributional unlearning that ranks forget examples using a probabilistic classifier whose Bayes-optimal logit equals the forget-to-retain log-density ratio (up to an additive class-prior constant). We show that thresholding the population log-density ratio yields the optimal fixed-budget selection rule for our removal–preservation objective and establish a non-asymptotic transfer guarantee relating score-estimation and threshold-calibration errors to degradation from the population-optimal selection rule. Our empirical evaluation spans real-world
datasets on toxic-
language removal and topical-domain removal regimes using different representations, with Mamushi achieving a more favorable removal–preservation trade-off than other baselines. Our work shows that Mamushi can serve as an efficient selection approach for downstream machine unlearning procedures, reducing the number of forget examples required to reach a fixed forgetting target.
Read the full abstract ▾
All authors Pinaki Mohanty, Haoran Tang, Maggie Makar, Rajiv Khanna
Robotics
Local-Minimum Escaper: Programmatic Subgoal Generation for Robust Navigation in Unknown Environments
Yin Gu, Xinming Zhang, Shanze Wang et al. (+2 more)
Mapless
navigation in unknown and partially observable environments remains challenging for mobile
robots, particularly when local minima prevent the
robot from making progress toward its goal. Existing local
navigation methods often lack an explicit mechanism for escaping such situations, while deep reinforcement learning (DRL) approaches typically learn recovery behaviors implicitly through reward design and policy optimization. In this work, we propose LME (Local-Minimum Escaper), a programmatic hierarchical framework that explicitly generates and reasons subgoals to guide
robots out of local-minimum regions. LME operates solely on local observations and selects candidate subgoals using interpretable heuristic criteria that account for both surrounding obstacle geometry and candidate-location safety. A local planner then generates low-level motion commands toward the selected subgoal. This design enables LME to handle environments both with and without local minima within a unified framework, while remaining independent of the underlying local planner and requiring no additional training. Extensive experiments in simulated and real-world environments demonstrate that LME provides robust
navigation performance and generalizes to challenging unseen scenarios. Furthermore, the generated subgoals can be used to guide different local planners, substantially improving their ability to escape local minima. Successful deployments on both differential-drive and quadruped
robots further demonstrate the practical applicability and generality of the proposed framework.
Read the full abstract ▾
All authors Yin Gu, Xinming Zhang, Shanze Wang, Siwei Cheng, Wei Zhang
Machine Learning
World-as-Graph: Relational World Modeling Through Latent Space Graphs
Yaqi Yang, Shuo Huang, Yujin Huang et al. (+3 more)
World models aim to learn representations of real-world environments and predict their future
evolution. Recent object-centric world models have made expressive progress by representing visual scenes as sets of object-level latent states, but object-object relations are often captured only implicitly, which limits explicit relational and temporal structure modeling and object-centric dynamic
memory modeling. To address such challenges, we propose World-As-Graph (WAG), a graph-based object-centric world model that introduces relational inductive bias into JEPA-style predictive representation learning. The proposed WAG contains two main modules: (1) Relation-aware structure induction, which constructs time-varying latent graphs from object-centric slots and designs relation-aware object masking policies to guide relational object representation learning in latent space; (2) Object-centric
memory transition, which maintains and updates object-level dynamic states by combining relational information from neighboring objects with historical
memory, enabling effective autoregressive future prediction. Extensive experiments on both visual
reasoning and robotic manipulation tasks could demonstrate the superior performance of our proposed WAG.
Read the full abstract ▾
All authors Yaqi Yang, Shuo Huang, Yujin Huang, Fucai Ke, Jiatong Han, Xin Zheng
Multimedia
PrecipJEPA: JEPA-Regularized Future-State Prediction with Motion-Source Rendering for Precipitation Nowcasting
Yufeng Zhu, Dan Niu, Qiliang Wu et al. (+4 more)
Long-term precipitation nowcasting requires modeling radar-echo
evolution while preserving localized high-intensity structures. Recent radar-specific studies motivate location-aware prediction and separating echo displacement from intensity change. However existing encoders learn historical representations mainly from final forecast errors. We propose PrecipJEPA, which couples a structured
forecasting path with an auxiliary path that enriches its encoder from observed radar history. In the
forecasting path, an online encoder first converts the observations into spatiotemporal
tokens. The Task-Driven Future-State Predictor (TFP) combines these
tokens with a recent-dynamics summary and spatiotemporal queries to construct future radar states. The Parallel Motion-Source Renderer (PMSR) decodes these states into motion and source-sink fields that transform the latest observation into future frames. During joint training, the History-Masked JEPA (H-JEPA) operates on the auxiliary path to predict masked historical features from visible context, directly supervising the same online encoder from the observed sequence. Experiments on SEVIR and MeteoNet show that PrecipJEPA improves highest-threshold CSI by 118.6% and 35.1%, respectively, over the strongest baselines, while maintaining the highest mean CSI throughout the 3-hour forecast.
Read the full abstract ▾
All authors Yufeng Zhu, Dan Niu, Qiliang Wu, Weiwei Huang, Yixiao Liang, Yongchao Feng, Chunlei Shi
Artificial Intelligence
Tianchi Liao Tianchi_Liao, Lele Fu, Sheng Huang et al. (+3 more)
Multimodal federated learning (MFL) has emerged as a pivotal paradigm for leveraging distributed data to enhance model performance. However, existing methods predominantly rely on idealized assumptions of model homogeneity and balanced modality distributions, rendering them ill-suited for practical scenarios characterized by heterogeneous client architectures and severe modality imbalance. To address these challenges, we propose a
Multimodal Federated learning Prototype-guided Bilateral
Alignment (MFedPBA) framework. MFedPBA facilitates robust knowledge synergy through a dual
alignment mechanism: (i) at the feature level, it aligns heterogeneous feature spaces via a projection encoder optimized by contrastive learning and the Gromov-Wasserstein distance; (ii) at the decision level, it employs an
entropy-weighted aggregation of naturally aligned logit prototypes. This novel design achieves robust MFL by jointly tackling heterogeneous feature spaces and collectively aggregating decisions. Extensive experiments demonstrate that our method significantly outperforms state-of-the-art baselines under conditions of model heterogeneity and modality imbalance.
Read the full abstract ▾
All authors Tianchi Liao Tianchi_Liao, Lele Fu, Sheng Huang, Qing Hu, Hong-Ning Dai, Chuan Chen
Computer Vision
From Image Interpretation to Clinical Reasoning: Upstream Physician-Context-Aware Multimodal Learning with Causal Reinforcement Learning
Jialu Pi, Yanan Ma, Weijie Chen et al. (+8 more)
Major adverse cardiovascular events (MACE) remain the leading cause of mortality worldwide. Opportunistic screening using routinely acquired clinical data offers a scalable approach for identifying high-risk individuals before acute events occur. Although chest X-rays (CXRs) capture latent cardiovascular biomarkers and clinical histories provide complementary patient context, existing medical
vision-
language models are primarily optimized for radiology interpretation rather than prognostic
reasoning. We propose a causal reinforcement learning framework for
multimodal clinical
reasoning that integrates CXRs and physician-authored clinical histories for opportunistic MACE prediction. The framework introduces (1) a role-decoupled dual-LLM architecture that separates
reasoning from risk prediction, (2) a dual-action causal reinforcement learning policy for evidence selection and
reasoning optimization, and (3) causal
token pruning to learn compact
multimodal representations. Evaluated on an internal cohort, an emergency department cohort, and the external MIMIC
dataset, the proposed framework consistently outperformed unimodal baselines and state-of-the-art medical
vision-
language models, achieving AUROCs of 0.720, 0.760, and 0.845, respectively. It also substantially improved
reasoning quality, achieving higher GREEN scores and higher expert preference while maintaining robust predictive performance across diverse patient populations.
Read the full abstract ▾
All authors Jialu Pi, Yanan Ma, Weijie Chen, Owen Crystal, Shubham Trivedi, Stephen Xie, Anna Silverman, Matthew Stib, Chadi Ayoub, Reza Arsanjani, Imon Banerjee
Computation and Language
GraphForge: Training Working Agents with Graph-Anchored Workspace Synthesis
Qisheng Su, Hanchen Wang, Guanru Zhu et al. (+11 more)
Working
agents need to read diverse files, coordinate tools, and produce deliverables. Training such
agents requires tasks built on many real files with verifiable results, but few pipelines exist to synthesize this kind of data. Existing pipelines either generate files with models, which lack realism and diversity, or build tasks on real files without task-specific verifiers, leaving result quality unchecked. We introduce GraphForge, an evidence-graph based framework that grounds both the task and its verification in real files. Starting from occupation-grounded seeds for controlled diversity, GraphForge assembles a workspace of real files for each seed and builds an evidence graph over their relations. Since the task statement and rubrics are both derived from this graph, task requirements are backed by the workspace files and each criterion is anchored to the files needed to verify it. An initial rollout further tests executability, and a revision
agent repairs the task and rubrics against the original files before trajectories are collected. Fine-tuning Qwen3.6-27B on 2,169 GraphForge trajectories brings GDPVal to 1445.7 (+65.7) under OpenHands, and Workspace-Bench-Lite and SpreadsheetBench II to 63.7 (+7.7) and 24.0 (+13.7) under Claude Code. Rejection fine-tuning on the SFT model's own rollouts, with candidates selected by the evidence-anchored rubrics, yields further improvements on all three
benchmarks, suggesting that the rubrics provide a useful selection signal.
Read the full abstract ▾
All authors Qisheng Su, Hanchen Wang, Guanru Zhu, Huicheng Jiang, Qiuyinzhe Zhang, Kou Shi, Zhen Fang, Ziao Zhang, Qingnan Ren, Honglin Guo, Jiazheng Zhang, Zehui Chen, Tao Gui, Feng Zhao
Computational Engineering
Trusting the Inverse: Reliability-Aware Mapping for Simulation-Based Microstructure Estimation in Diffusion MRI
Juan Luis Villarreal Haro, Ileana Jelescu, Jean-Philippe Thiran et al. (+1 more)
Diffusion-weighted MRI can probe tissue microstructure non-invasively, however interpreting microstructural parameter estimates remains challenging due to the intrinsic ambiguity of the inverse problem. While simulation-based approaches can incorporate increasingly realistic tissue models, they still lack voxel-wise characterisation of the reliability and degeneracy of the inferred parameters. Here, we introduce a reliability framework for simulation-based microstructure estimation based on three complementary scores that identify distinct sources of unreliability in the estimation process: out-of-distribution signals, local signal mismatch, and parameter degeneracy. The framework was implemented using a Monte Carlo dictionary of 1,050 synthetic voxels generated from geometrically realistic substrates, with parameter ranges grounded in electron microscopy measurements of rat corpus callosum. The dictionary spans biologically plausible axon radii (0.25-0.85 $\mu$m), microscopic angular spread (0-10$^\circ$), packing densities (60-92%), and intrinsic diffusivities (1.75-3.0 $\mu$m$^2$/ms). On synthetic data, the resulting Reliability Index correlated with actual estimation error (Spearman $\rho = -0.742$) and distinguished between extrapolation, poor local interpolation, and parameter degeneracy. Applied to in vivo corpus callosum DW-MRI in rat (256 voxels, four animals) and human (MGH-USC HCP, 18,765 voxels, nine subjects), 91% and 73% of voxels respectively exceeded $R > 0.5$. These results demonstrate how reliability-aware analysis can support the interpretation and future development of simulation-based
diffusion MRI microstructure models.
Read the full abstract ▾
All authors Juan Luis Villarreal Haro, Ileana Jelescu, Jean-Philippe Thiran, Jonathan Rafael-Patino
Machine Learning
Learning Where to Steer: Noise-Space Geometry for Efficient Offline Multi-Objective Optimization with Generative Models
Yuan Lu, Esha Singh, Yi-An Ma et al. (+1 more)
Offline multi-objective optimization (MOO) seeks solutions with better objective trade-offs using only a fixed
dataset, without querying the objectives.
Diffusion models trained on such data have emerged as a promising approach, but their samples are not inherently better than the data and must be steered toward the Pareto front. Existing methods guide or condition every sampling step. We instead act on the initial noise and leave the sampling process unchanged. Across Off-MOO-Bench, we observe that the objectives, as functions of the noise, are sensitive to only a few directions. We estimate these directions once per task via a Recursive Feature Machine using function values alone, and a small cache serves every trade-off, so each candidate costs one noise displacement and one ODE solve. We prove that this displacement increases the learned scalarized objective in expectation, and that sweeping trade-offs recovers the flow's attainable front up to proxy and steering errors. With additional guidance, for which we introduce novel data-adaptive and Pareto-aware operators, our method attains the best average hypervolume rank among generative methods on 47 tasks, at comparable or lower sampling cost. Steering alone outranks the best prior generative method at a fraction of its sampling cost.
Read the full abstract ▾
All authors Yuan Lu, Esha Singh, Yi-An Ma, Yusu Wang
Information Theory
Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
Fengqi Hou
We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-
embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these
embeddings show that no positive power of information distance can be represented exactly by distances in a real
Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{\delta+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $\delta$, where $C$ is independent of the endpoints. This bound rules out scale-
embeddings of the integer line and every positive-dimensional integer
lattice, resolving Hutter's
lattice embedding problem for both string and sequence
embeddings. Restriction to the integer
lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.
Read the full abstract ▾
Machine Learning
Flow Matching under Noisy Latent Structure: Beyond Exact Low-Dimensional Support
Lifeng Hao and Shaolin Ji
Flow Matching (FM) learns a velocity field whose ODE transports a simple source distribution to a target law. Existing finite-sample theory largely treats ambient-space regularity or data supported exactly on low-dimensional sets. We study linear FM under a noisy latent-generator model, where a low-dimensional Hölder map is perturbed by nondegenerate ambient Gaussian noise, so the target law is full-dimensional despite its latent structure. We construct a spatially regular ReLU velocity class and establish non-asymptotic high-probability approximation and estimation bounds whose leading sample-size exponent is governed by the latent dimension rather than the ambient dimension, with ambient and noise dependence kept explicit. Fixed positive target noise keeps the interpolation nondegenerate over the full time interval. The same spatial regularity propagates the learned velocity error through the transport ODE, yielding a corresponding Wasserstein convergence guarantee. These results show that exact low-dimensional support is not necessary for Flow Matching to retain latent-dimensional statistical behavior.
Read the full abstract ▾
Artificial Intelligence
How Much Can Reliability Drift Under a Fixed Confidence Distribution?
Wenhao Liang, Lin Yue, Wei Emma Zhang et al. (+3 more)
A classifier's conditional accuracy can change while its confidence distribution stays exactly the same. We study the worst-case movement of the reliability relation under
covariate shifts that preserve the distribution of the confidence score, constraining the reweighting within each confidence level by a $\chi^2$ budget; the resulting worst case, as a function of the budget, is a fragility profile. On an interval of budgets that can be computed from the source distribution, the profile equals exactly the square root of the budget times the within-level variance of the correctness propensity – the grouping-loss term of calibration-refinement decompositions. Beyond this interval the profile is governed by the tails of the propensity law, and the entire upward profile determines the centred within-level law; consequently, calibration residual and grouping variance do not determine fragility in general, though they do when labels and predictions are deterministic. Since the propensity is not observed, we restrict reweightings to a learned finite readout within confidence bins, bound the part the restriction misses by the grouping variance remaining inside readout
cells, estimate the restricted profile with role-separated labels, and provide a separate split-sample lower confidence bound. On ImageNet this bound is positive in both splits for four of six primary classifiers and nine of twelve additional ones as released, and for three of eighteen after temperature scaling. Held-out drift under optimised reweightings fitted without evaluation labels tracks the estimated profile; an exploratory label-permutation diagnostic yields near-zero agreement for this statistic while largely reproducing the correlation observed for unsigned random reweightings.
Read the full abstract ▾
All authors Wenhao Liang, Lin Yue, Wei Emma Zhang, Mingyu Guo, Olaf Maennel, Weitong Chen
Machine Learning · Cross-listed from stat.ML
Warm-starting PDE solvers with any-dimensional machine learning
Wilson G. Gregory, George A. Kevrekidis, Ben Blum-Smith et al. (+1 more)
Any-dimensional machine learning models, such as graph neural networks (GNNs), can be naturally trained and evaluated on inputs of different sizes and dimensions. Inspired by the GNN transferability literature, we show mathematical conditions under which a partial differential equation (PDE) learning-based solver can be trained in small dimensions and directly applied to solve a higher dimensional PDE in a zero-shot fashion. These conditions are based on
symmetries in both the partial differential equation and the initial data. When the equations satisfy the
symmetries but the data does not, which is the case for many PDEs arising from physics, we show that our theory gives a principled way of warm-starting low-dimensional PDE solvers for higher dimensional PDEs. We apply this method on the heat equation, Burgers' equation, and the compressible Navier–Stokes equations, improving the performance in both zero-shot and typical training regimes on high dimensional data. For example, we train a surrogate model on 2D Navier–Stokes data and achieve better results on 3D test data than a baseline surrogate model trained on 3D data, while only using 12$\%$ of the flops and 20$\%$ of the total data size.
Read the full abstract ▾
All authors Wilson G. Gregory, George A. Kevrekidis, Ben Blum-Smith, Soledad Villar
Cryptography and Security
Semi-Quantum Cryptography with Certified Deletion
Yael Tauman Kalai and Justin Raizes
Certified deletion allows a client to upload encrypted data to a server as a
quantum state, then later request that the server delete their data and detect whether the server complies. If verification passes, then the data on the server will remain hidden even if the decryption key is later leaked. In publicly verifiable certified deletion, the verification key is published so that anyone may check for deletion compliance. In this work, we give a general compiler to publicly verifiable certified deletion that allows the client to initially upload the *
quantum* ciphertext using purely *classical* communication, assuming the post-
quantum hardness of LWE in the plain model. Our approach can be applied to a wide variety of primitives, including commitments and public-key, attribute-based, identity-based, and fully-homomorphic encryption. Moreover, our constructions allow the client to classically manage the encrypted data beyond just verifying its deletion. The classical client may non-destructively audit the ciphertext via a Proof of No Intrusion to check whether it has been leaked to a third party. The classical client may also retrieve the data while simultaneously verifying its deletion from the server. Thus, they do not have to choose between retrieving the data and protecting it against future key leakage. As our core technical contribution, we give a classical-communication protocol and simulation technique that allows adapting purification-based security arguments for BB84-style states which are prepared through classical interaction. It makes the required purification available in a hybrid experiment, despite the classical transcript uniquely determining the prepared state in a real execution.
Read the full abstract ▾