Robotics
Long-WAM: Scaling the Context of World-Action Models
Wei Huang, Bohan Zhang, Chenzhi Liu et al. (+13 more)
Real-time
robot control demands enough visual history to infer motion and task progress, but processing that history can delay action. We present Long-WAM, a model-system framework for scaling the context of causal world-action models under real-time control constraints. Our central finding is that access to history is not the same as using it: longer histories pay off far more when the
video foundation is pretrained autoregressively (AR). We first learn causal prediction from
robot and
egocentric videos without action labels, then preserve this history-to-future structure during world-action adaptation. On RoboCasa GR-1, increasing context from 0.0 to 19.2 seconds raises success from 63.3% to 78.7%, whereas a bidirectionally pretrained initialization shows no net gain;
robot-domain AR pretraining further raises peak success on GR-1 and LIBERO-Long. Long-WAM also achieves the best results among compared methods on LIBERO-Long, RoboTwin 2.0, and DOMINO. Streaming observation encoding, asynchronous execution, and hardware-specific acceleration enable deployment on RTX 5090, DGX Spark, and Jetson AGX Thor without dropping future prediction; on RTX 5090, each action chunk, including future-
video latent prediction, takes 107.4 ms. Real-time deployment on Unitree G1 and YAM supports dynamic and long-horizon manipulation, including 95% success on dynamic cup stacking, where Pi0.5 and Fast-WAM succeed in none of 20 trials. As a
memory-informed executor, Long-WAM also complements higher-level planning in composite tasks.
Read the full abstract ▾
All authors Wei Huang, Bohan Zhang, Chenzhi Liu, Isabella Liu, Shuai Yang, Weian Mao, Luozhou Wang, Yicheng Xiao, Weifeng Lin, Qixin Hu, Bryan Chu, Sifei Liu, Linxi Fan, Xiaojuan Qi, Song Han, Yukang Chen
Machine Learning · Cross-listed from math.OC
Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
Aleksandar Armacki, Haoyuan Cai and Ali H. Sayed
Heavy-tailed noise has been widely observed in modern machine learning, motivating the use of methods like gradient clipping and normalization. While these methods are well understood in centralized settings, much less is known in decentralized ones, where applying a nonlinearity to local gradients affects both optimization and consensus. Recent works on decentralized non-convex optimization have studied both clipping and normalization under heavy-tailed noise, with clipping yielding suboptimal rates and normalization needing local momentum or mini-batches to converge. This raises the question: can a baseline decentralized method using a nonlinearity achieve optimal convergence rates under heavy-tailed noise? We answer affirmatively with clipped decentralized SGD ($\mathtt{DSGD}$). For smooth non-convex costs under bounded $p$-th moment noise, $p \in (1,2]$, we show that clipped $\mathtt{DSGD}$ achieves order-optimal rates both with high probability and in expectation. Moreover, we establish a linear speed-up in the number of
agents, which, to our knowledge, has not been shown for decentralized methods with clipping. The key technical ingredient is a sharp analysis of the consensus gap that exploits the structure of clipping, relegating network effects to higher-order terms. Our results highlight an important distinction between clipping and normalization in decentralized settings: while normalized $\mathtt{DSGD}$ can fail to converge, clipping retains magnitude information, enabling $\mathtt{DSGD}$ to be convergent and order-optimal. Numerical experiments validate our theory.
Read the full abstract ▾
Robotics
Rephrase Before You Act: Characterizing and Mitigating Language Sensitivity in Vision-Language-Action Models
Mikey Watts and Yuchen Cui
Vision-
language-action models (VLAs) are strikingly sensitive to instruction phrasing and do not inherit the
language robustness of the
vision-
language models they are built on. A one-word edit can move success by tens of points: $\pi_{0.5}$ turns on a LIBERO stove 100% of the time for "switch on the stove" and 2% for "switch on the hot plate", and a $\pi_0$ checkpoint finetuned with rephrase augmentation still shows swings of up to 61 points. We characterize this sensitivity with statistically tested single-edit swings and an oracle phrase search, which shows that phrasing alone nearly closes the 21-point gap between in-distribution and out-of-distribution tasks. We then reduce it without modifying the policy. Because the sensitivity is systematic, it can be expressed as explicit rules: we score many phrasings of a few training tasks, have a large
language model distill the evidence into ten to twenty rephrasing rules, and at deployment rewrite each incoming instruction once under these rules. The rules improve the frozen $\pi_0$ by 16 to 27% relative on twelve held-out tasks across
adversarial, VLM-generated, and human-generated phrasings, with gains concentrated on out-of-distribution tasks. The pipeline replicates on $\pi_{0.5}$ and LIBERO, lifting in-finetune success from 93.6% to 97.8%. The method requires no retraining and no per-step verification, and applies zero-shot to unseen tasks and instructions. Project website: https://sttawm.github.io/rephrase-before-you-act
Read the full abstract ▾
Computer Vision
GRACE: Generation-aware latent compression for efficient video generation
Jiyoung Kim, Paul Hyunbin Cho, Jisu Nam et al. (+5 more)
Highly compressed
video autoencoders offer an effective way to accelerate
video diffusion models, as the
Diffusion Transformer (DiT) operates on far fewer
tokens. However, such autoencoders are challenging to train, since a higher compression ratio degrades reconstruction quality and recovering it requires more channels, which is known to slow the convergence of the DiT. The compressed latent also differs from the one the DiT was trained on, so the pretrained DiT must be either retrained from scratch or adapted at considerable cost. Compressing the autoencoder the DiT was trained with appears to preserve compatibility, yet optimizing it for reconstruction alone still shifts the latent away from the distribution the DiT has learned. To address this, we propose Generation-Aware Latent Compression for Efficient
Video Generation (GRACE), a two-stage framework that compresses a pretrained
video autoencoder while keeping it compatible with the pretrained DiT. Specifically, we keep a frozen base latent from the pretrained encoder and learn a residual latent for the information lost under stronger compression, while aligning the compressed latent with the pretrained latent in the feature space of the frozen DiT so that the autoencoder is optimized for generation. We then adapt the DiT with lightweight fine-tuning and asymmetric denoising, where the base is denoised ahead of the residual. GRACE reduces the
token count of Wan2.1-I2V-14B by 8x and its latency by 11.1x at 480x832x81, while matching the generation quality of the pretrained pipeline before compression on VBench.
Read the full abstract ▾
All authors Jiyoung Kim, Paul Hyunbin Cho, Jisu Nam, Donghoon Lee, Hyunsung Go, Yeonkyeong Lee, Hansaem Kim, Seungryong Kim
Machine Learning
Distilling Graph Geometry: Knowledge Gap from GNNs to MLPs
Zhewei Chen, Hao Zhu, Jiaojiao Jiang et al. (+1 more)
GNN-to-MLP
distillation aims to retain the predictive accuracy of a message-passing teacher while deploying a graph-free MLP at inference. Existing methods mainly transfer node-wise predictions or use confidence-based reweighting, but they do not specify where the student should preserve the teacher's graph-induced geometry. We show that this omission leads to two spectral failure modes in the student's representation space. On sparse graphs, the student suffers from spectral underfit, missing high-energy teacher directions concentrated near boundary regions. On dense graphs, it suffers from spectral overfit, retaining spurious directions that the teacher has collapsed through aggregation. Motivated by an energy-weighted teacher-student
alignment objective, we propose Graph Geometry-aware MLP (G^2MLP), a training-time
distillation framework guided by Ollivier-
Ricci curvature.
Curvature identifies where the two spectral errors concentrate and is used to allocate supervision between prediction-level and representation-level
alignment. The deployed model remains a standard MLP and requires no graph access at inference. Across node-classification
benchmarks, G^2MLP consistently improves over graph-free
distillation baselines, reduces the teacher-student rank gap in both regimes, and transfers without architectural changes to Graph
Transformer teachers and link prediction.
Read the full abstract ▾
All authors Zhewei Chen, Hao Zhu, Jiaojiao Jiang, Ahad N. Zehmakan
Machine Learning
Why Forget-Only Unlearning Needs Memorization
Luka Radić, Vikrant Singhal and Amartya Sanyal
Machine unlearning asks for a deletion
algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearning, where the deletion
algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. We ask whether forget-only unlearning is always possible. We first show that this depends on the learning method: different
datasets can produce the same trained model but require very different outputs after the same examples are removed. Using this observation, we derive lower bounds on how accurately unlearning can match retraining and instantiate them for several standard learning
algorithms. We then ask what must be true when forget-only unlearning succeeds. To this end, we derive lower bounds on what an
algorithm must memorize about the training data to handle arbitrary deletion requests. For simple threshold learners, the required information can be as large as the entire
dataset, even though ordinary training keeps only one boundary point. Overall, our results show that information discarded during ordinary learning may be needed later for deletion, so models designed for forget-only unlearning may need to retain more information than standard training does.
Read the full abstract ▾
Data Structures and Algorithms
Symmetric Submodular Minimization from Comparisons
James Fox and David P. Woodruff
Given value-oracle access to a symmetric submodular function $f:2^V\to\mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries. We study the weaker comparison model, in which a query on $S,T\subseteq V$ reveals only whether $f(S)$ is smaller than, equal to, or larger than $f(T)$. We give a deterministic
polynomial-time
algorithm that finds a nontrivial minimizer of any symmetric submodular function using $O(n^3)$ comparisons, matching the best-known deterministic value-oracle bound despite not knowing the function values. More generally, the same $O(n^3)$-comparison bound holds for minimization over the nonempty members of any downward-closed family. Our
algorithm combines the minimum-capacity ordering recently introduced by Iwata and Konno with the contraction framework of Goemans and Soto. Applying this result to weighted graph cut functions resolves the main open question of Cohen-Addad et al., who gave an $\widetilde{O}(n^3)$-comparison
algorithm that runs in exponential time and asked whether a weighted minimum cut can be found in
polynomial time using comparisons. For graphs with $m$ edges of integer weight at most $B$, we also give a deterministic
polynomial-time
algorithm that finds a minimum cut using \[ \widetilde{O}\!\left(n^2+\min\!\left\{mB,\,nB^2\right\}\right) \] comparisons, improving on the $O(n^3)$ bound when $B$ is small. Finally, we show that every randomized
algorithm that outputs a minimum cut with probability at least $2/3$ makes $\Omega(n \log n)$ expected comparisons in the worst case. Under the stronger assumption that all edge weights are polynomially bounded integers, we obtain an $\Omega(n \log \log n)$ expected comparison lower bound. These bounds contrast with the value-oracle model, where no $\omega(n)$ lower bound is known even for deterministic
algorithms.
Read the full abstract ▾
Sound
Unsupervised Maneuver-Aware Acoustic Fault Detection for Autonomous Drones
Ali M Ali, Ziyi Tang, Nurdaulet Nazarbay et al. (+1 more)
This paper presents a maneuver-aware acoustic fault detection framework for autonomous drones that integrates Noise2Noise-inspired deep learning denoising with maneuver-conditioned reconstruction. A key practical constraint motivating this work is that labeled faulty-flight data are difficult and potentially unsafe to collect; the proposed framework therefore follows an unsupervised learning paradigm in which only nominal flight recordings are required for training. In flight environments, acoustic signals acquired from unmanned aerial vehicles are subject to variability arising both from environmental noise and from structured, maneuver-dependent aerodynamic effects. To address these challenges simultaneously, a two-stage learning architecture is developed. In the first stage, a Noise2Noise-inspired denoising model attenuates
stochastic acoustic noise while preserving fault-relevant spectral-temporal structures, without requiring clean reference signals. In the second stage, a maneuver-Conditioned Convolutional AutoEncoder (maneuver-CCAE) is trained using maneuver-related labels including drone type and flight direction to model nominal acoustic behavior under varying operating conditions. Fault detection is subsequently performed using reconstruction error as an anomaly score. Experimental results demonstrate that the proposed maneuver-aware conditioning raises the area under the ROC curve (AUC) from $\AUCaeOnly$ (unconditioned baseline) to $\AUCfull$ (full model), validating the critical role of maneuver-dependent modeling. The complete framework is deployed on an NVIDIA Jetson Orin Nano Super embedded platform within a ROS2 pipeline, achieving an end-to-end fault detection latency of approximately $20\,\text{ms}$ per audio segment with a TensorRT half-precision (FP16) backend, confirming real-time viability for onboard
UAV health monitoring.
Read the full abstract ▾
All authors Ali M Ali, Ziyi Tang, Nurdaulet Nazarbay, Hashim A. Hashim
Game Theory
A Constant-Factor Approximation to Multidimensional Consumer Utility
Kira Goldner, Taylor Lundy and Thodoris Tsilivis
Motivated by social services where consumers pay with non-transferable ordeals, we study mechanisms that maximize consumer utility for multiple unit-demand buyers and heterogeneous items whose values are drawn independently from known prior distributions. Prior work in utility maximization approximates social welfare and shows that the gap between optimal utility and social welfare is logarithmic. We resolve the question of whether simple mechanisms can guarantee a constant-factor approximation to optimal utility itself. Our mechanisms achieve a $(5.67+\varepsilon)$-approximation for general independent values, improving to $2e/(e-1)<3.164$ when values are i.i.d. Each buyer chooses their favorite option from posted item prices or free item lotteries, and contention resolution determines which buyers' requests are served; this is BIC, ex-post individually rational, and computable in
polynomial time. Our main technical contribution is a general upper bound on the optimal ex-ante-constrained utility that separates the contributions captured by posted prices and free lotteries. These results establish a utility counterpart to the theory of simple, approximately revenue-optimal mechanisms.
Read the full abstract ▾
Artificial Intelligence
RoboJEPA: Scaling Robotic Latent World Models
Artem Zholus, Nicolas Beltran-Velez, Jianhao Yuan et al. (+9 more)
Latent world models have shown a remarkable ability to predict future states and to plan in the real world. In practice, however, we lack a principled way to estimate how their capabilities scale with model size, data, and compute, an open problem that slows progress in the field. In this work we present RoboJEPA, a world model based on the Joint
Embedding Predictive Architecture (JEPA) and trained on a large-scale
dataset spanning 12 robotic embodiments. We show that RoboJEPA's imagination error, the error of its latent rollouts, follows a second-order power law in compute, allowing us to predict model quality well beyond the scale at which the law is fit. We further show that downstream robotic planning performance improves predictably with compute, and that imagination error is strongly correlated with it, making it a reliable proxy for real-
robot evaluation. Finally, we demonstrate that latent world models can be deployed zero-shot as robotic
agents, planning toward a single goal image to solve tasks requiring long-horizon planning on real hardware. We release all model checkpoints together with our training and
robot deployment code. To our knowledge, this is the first work to establish scaling laws for multi-embodiment robotic world models trained on real
robot data, and RoboJEPA, at 8B parameters, is the largest JEPA predictor model trained to date.
Read the full abstract ▾
All authors Artem Zholus, Nicolas Beltran-Velez, Jianhao Yuan, Sarath Chandar, Tushar Nagarajan, Daniel Severo, Koustuv Sinha, Michal Drozdzal, Adriana Romero Soriano, Jeannette Bohg, Nicolas Ballas, Mahmoud Assran
Computational Complexity
$\exists \mathbb{R} \subseteq \textsf{CH}$
Alex Meiburg
The existential theory of the reals asks whether
polynomial constraints with integer coefficients have a real solution. We give a proof placing this problem in the counting hierarchy. The first argument is intended to expose the essential steps, and a separate analysis lowers the bound to $\exists \mathbb{R}\subseteq\textsf{BPP}^{\textsf C_3\textsf P}\subseteq\textsf C_4\textsf P$, the fourth level of the hierarchy. For each fixed $w$, sentences with $w$ alternating real quantifier blocks lie in $\textsf C_{9w+17}\textsf P$. We then treat exact semidefinite feasibility, PosSLP, square-root sum,
geometric real counting, Euler characteristic, and complex feasibility in separate applications. The corresponding bounds include $\textsf{BPP}^{\textsf C_2\textsf P}$ for general SDP, $\textsf{BPP}^{\textsf{PP}}\cap\textsf{P}^{\textsf{NP}^{\textsf{PP}}}$ for PosSLP and square-root sum, and $\textsf{FP}^{\textsf C_4\textsf P}$ for total
geometric real counting. Note: These proofs were discovered by ChatGPT after a series of conversations ending on September 29th 2026. A group of researchers has been working to digest the proof, and while the most essential arguments appear correct, we are endeavoring to give this result the treatment it deserves and a proper exposition and development to benefit of the community. However, on October 6th, OpenAI released a very similar result, with a slightly weaker bound. While we work to improve our exposition of this proof, the current version has been uploaded as a service to the community to compare the different proof techniques. While the listed author takes responsibility that the proofs appear to be correct, he has not played a nontrivial role in developing them, and believes the human value will be in good exposition and canonicalization of the results.
Read the full abstract ▾
Artificial Intelligence
SciExam for ENSO: Can AI Agents Build Climate Models?
Yinling Zhang, Langchen Liu, Dongbin Xiu et al. (+4 more)
Language-model
agents are increasingly asked to carry out open-ended scientific research, yet their results are usually graded against a known answer, a rubric, or a
language-model reviewer, none of which can tell whether a new scientific model is valid. The AI Science Exam for El Nino-Southern Oscillation (SciExam for ENSO) is a
benchmark in which
agents build low-order
stochastic models of ENSO, the dominant mode of interannual
climate variability, from real observations. Within a six-hour budget,
agents process the observations, write their own diagnostics, which are then frozen, and develop a model using only these diagnostics as feedback. Hidden graders then test whether the model reproduces ENSO's statistics, recovers unobserved variables, and forecasts held-out years, and score a published model in the same way. Across twelve
agent systems, six produce models that score higher than the published model, mainly through better reconstruction and
forecasting. The simplified forms of the stronger models are each compatible with one of the two competing explanations of ENSO's warm-cold asymmetry, an open debate that the task never mentions. Controlled runs of the top system under varied information suggest that its scores do not come from recalling the dated observational record and that the information it receives shapes how it builds its model. SciExam for ENSO can thus evaluate
agent research where no answer is known, and the results suggest that
agents can already build competitive models whose structures bear on questions that scientists still debate.
Read the full abstract ▾
All authors Yinling Zhang, Langchen Liu, Dongbin Xiu, Xueyan Zou, Xu Kuang, Mengdi Wang, Shilong Liu
Computer Vision
Video-Conditioned Generative Joint 2D-3D Hand Motion Recovery
Chen Xu, Yunqi Li, Binbin Huang et al. (+3 more)
Recovering faithful 3D hand motion from
video remains challenging due to frequent occlusions and incomplete visual observations, which make frame-wise pose estimates unreliable and temporally inconsistent. To address this problem, we propose JoHan, a unified generative framework that recovers hand motion directly from
video sequences without relying on intermediate per-frame pose predictions. Trained from scratch, our model jointly generates aligned 2D and 3D local hand pose sequences by learning their temporal dynamics and cross-representation correspondence. The generated 2D trajectories exploit direct spatial and temporal cues from the 2D images to guide the following generative 3D motion reconstruction, while the learned motion prior promotes temporal consistency. Their learned 2D-3D correspondence further enables recovery of the hand's global position and orientation relative to the camera. Extensive experiments on challenging
benchmarks demonstrate significantly improved accuracy and speed in local hand-pose and camera-space reconstruction. Notably, our method captures much better hand-motion dynamics, producing significantly smoother motion than previous methods while maintaining high per-frame pose accuracy.
Read the full abstract ▾
All authors Chen Xu, Yunqi Li, Binbin Huang, Brent Yi, Shenghua Gao, Yi Ma
Robotics
Factorized Tactile Representation and Control for Sim-to-Real Manipulation
Siqi Shang, Bianca Aumann, Tye Brady et al. (+2 more)
Tactile sim-to-real learning must bridge simulated contact and device-specific sensor responses while preserving information needed for control. We propose a factorized tactile representation and control framework that maps normal force and contact patch to an effective contact response recoverable from sensor readings. The response is separated into contact geometry, force distribution, and temporal contact change, with representation-specific encoding and randomization. A Tactile Gated Policy preserves these representations separately through control and operates over all mask configurations without retraining. We evaluate the approach through response reconstruction, spatial
alignment, force regulation, and contact-rich
adversarial peg insertion in simulation and the real world, enabling the utility and transfer reliability of different tactile representations to be assessed independently. The approach achieves <1 mm contact localization, 1.69 N force-tracking error on unseen geometries, and a 35% improvement in real-world
adversarial peg insertion over the unfactorized response, with different tactile representations benefiting different interactions.
Read the full abstract ▾
All authors Siqi Shang, Bianca Aumann, Tye Brady, Joshua Migdal, Taskin Padir
Computation and Language
Your Prompt Should Do More: Effects of Retrieval Instructions in Embedding Models
Amanda Myntti, Jenna Kanerva, Veronika Laippala et al. (+1 more)
Prompted
embedding models have recently received increasing
attention, particularly for
retrieval, where detailed
retrieval instructions are provided as part of the
retrieval prompt. Several new
datasets and studies have examined this setting, showing that the current
embedding models often struggle to follow such instructions reliably. In this paper, we study the mechanism of how instructions actually affect the representations of
retrieval queries in asymmetric
retrieval tasks. We show that models can fail to follow even simple task instructions when query-side distractors are included in the evaluation. We hypothesize that this behavior is driven by the training setup of current
embedding models and their evaluation, and show that fine-tuning with added query-side distractors leads to substantial improvements, with minimal effect on other tasks.
Read the full abstract ▾
All authors Amanda Myntti, Jenna Kanerva, Veronika Laippala, Filip Ginter
Artificial Intelligence
RECAST: Learning to Compute the Right Context through Adaptive Evidence Routing
Yilun Hao, Krishna Sayana, Isabella Ye et al. (+4 more)
Large
language models are increasingly applied to tasks grounded in long, heterogeneous information sources. Conventional
Retrieval-Augmented Generation (RAG) relies on fixed similarity-based
retrieval, while agentic variants adapt queries and tool use but remain largely
retrieval-centric. However, in many tasks, the evidence required for a solution is not explicitly present in any single source item. Instead, it must be derived through filtering, aggregation, or computation across multiple source items. In this work, we introduce RECAST (Routing Evidence through Computation, Access, and Synthesized Tools), a learned framework that formulates evidence construction as a sequential decision process over heterogeneous
retrieval and computation operations, allowing evidence to be actively derived rather than merely retrieved. A lightweight RouterLM iteratively selects and formulates primitive operations or specifies customized operations for a frozen CompilerLM to translate into executable code. Once it judges the evidence sufficient, RouterLM passes the accepted evidence to a frozen AnswerLM to produce the final solution. We train RouterLM with supervised fine-tuning (SFT) followed by group relative policy optimization (GRPO). Across six heterogeneous
benchmark families, RECAST achieves a mean success rate of 75.6%, outperforming the strongest large-model baseline by 15.9%. Moreover, training enables the Qwen3.5-9B RouterLM to outperform a training-free Gemini 3.5 Flash RouterLM by 5.0%. On three held-out
benchmarks, RECAST improves over the strongest baseline by 15.0% on average, demonstrating strong zero-shot generalization across tasks and heterogeneous source representations.
Read the full abstract ▾
All authors Yilun Hao, Krishna Sayana, Isabella Ye, James S Ren, Sukhdeep Sodhi, Craig Boutilier, Chuchu Fan
Artificial Intelligence
Validity Without Ground Truth: What Stated-Preference Economics Offers the Evaluation of Language Models
Daniel Robert Kling Alexander and Catherine Louise Kling
Many of the questions now put to large
language models have no correct answer to score against: what a policy is worth, which option a user should choose, how to weigh competing values. Stated-preference economics has faced this problem for decades. It judges survey responses without knowing the true value, through a framework of validity and related concepts: content, construct, and criterion validity, reliability, incentive compatibility, and consequentiality. We argue that this framework is a general method for evaluating
language models, and we set out what each concept means for LLM evaluation. We demonstrate the approach using a published water-quality stated preference economic valuation survey (Vossler et al. 2023) administered to six models. In this economic application, the validity tests take the form of predictions from economic theory: demand should slope down, and willingness to pay should respond to the scope of the good and to income. The tests separate the models sharply. Two older models fail the most basic test at a household income level of \$75,000, and the two newest pass every test of theoretical validity we can score, but diverge on convergent validity. Passing validity tests shows that a model's answers are coherent, not that they are correct.
Read the full abstract ▾
Data Structures and Algorithms
Barely Monotone (min,+)-Convolution in Truly Subquadratic Time
MohammadTaghi Hajiaghayi, Danny Mittal and Saeed Seddighin
The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)}, prior work computes it in truly subquadratic time when the inputs are monotone; the
algorithm of Chi, Duan, Xie, and Zhang (STOC 2022) takes expected O~(n^{1.5}) time. We introduce a monotonicity measure ranging from 0 (monotone) to 1/2 (entirely non-monotone): a sequence has monotonicity alpha if it can be partitioned into O(n^alpha) monotone subsequences, and by the Erdos-Szekeres
theorem every sequence has monotonicity at most 1/2. We show that truly subquadratic time is achievable even when just one input is barely monotone, that is, has monotonicity 1/2 - Omega(1): if A has monotonicity alpha, we compute the convolution in expected time O~(n^{5/3+2alpha/3}) for every bounded B. If B has monotonicity beta as well, the expected time improves to O~(n^{(3+alpha+beta)/2}), which matches the monotone case for alpha = beta = 0; this
algorithm also allows infinite entries placed arbitrarily. We complement these
algorithms with fine-grained reductions. Bounded (min,+)-convolution reduces to bounded monotone (min,+)-convolution of length N = O(n^{1.5}), so an O(N^{4/3-eps})-time
algorithm for monotone inputs would give an O(n^{2-3eps/2})-time
algorithm for bounded inputs. Similarly, entries bounded by n reduce to entries bounded by N^x on sequences of length N = Theta(n^{2/(1+x)}). We also show that if only A has entries in {0,...,M}, we can compute the convolution in O~(n(M+1)) time, and in O~(n^{1.5} sqrt(M)) time if A may also contain +infinity.
Read the full abstract ▾
Data Structures and Algorithms
Taxonomic Classification with Tag Arrays
Travis Gagie and Gonzalo Navarro
Taxonomic classifiers based on exact matches differ in which matches they use and in how each match splits its credit among the taxa containing it: Kraken~2 gives a $k$-mer's credit to the lowest common ancestor of those taxa, SPUMONI~2 labels each position of the read, Tagger gives each maximal exact match (MEM) one label, and Cliffy splits a match's credit evenly over a roughly logarithmic sample of the taxa. We compare these schemes on the same long MEMs, mainly on short 16S rRNA reads classified to genera with SILVA, where credit proportional to the number of occurrences of the MEM in each taxon is the most accurate, by 1.0 to 6.8 percentage points. We compute long MEMs with Boyer–Moore–Li on a run-length compressed suffix array, and count their occurrences in each taxon with a complete, run-length compressed tag array, in time proportional to the number of tag runs in the MEM's BWT interval, without locating any occurrence. We bound the number of tag runs in terms of the BWT runs and of how often suffixes with long common prefixes have different tags, and show that tags constant on $d$ blocks of the text have a macro scheme with at most $r + 2d$ phrases. On SILVA our index takes 1.44\,GB and classifies a read in 66\,$\mu$s with one thread at 93.8% accuracy, about what Cliffy reports for its 9\,GB index; over minimizer digests it takes 0.49\,GB and reaches 92.5%, against 84.2% for Cliffy's digested index on the same reads. On nanopore reads from whole genomes, where almost every long MEM occurs in one species, we instead use each read's longest MEMs, found in one pass of a variant of Boyer–Moore–Li with a $k$-mer filter, which assigns 99.6% of the reads to their species with no length threshold.
Read the full abstract ▾
Machine Learning
Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
Sasha Voitovych, Adam Block, Alexander Rakhlin et al. (+1 more)
Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however, comes at a steep price, introducing significant statistical and computational barriers. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully
adversarial and fully
stochastic settings by assuming that the conditional law of each
covariate has density at most $1/\sigma$ with respect to some fixed base measure $\mu$, and it is known to match the statistical and computational guarantees of classical learning while still allowing for much of the flexibility of online learning. However, existing oracle-efficient
algorithms require either (i) sampling access to the base measure $\mu$ or (ii) labels that are perfectly predicted by a fixed hypothesis. Both assumptions limit the applicability of these
algorithms, in contrast to statistical learning, where empirical risk minimization (ERM) learns efficiently in the agnostic setting without any knowledge of the data distribution. We show that neither assumption is necessary, giving the first oracle-efficient
algorithm that achieves sublinear regret in the agnostic setting without knowledge of $\mu$. Our
algorithm, based on Gaussian Follow-The-Perturbed-Leader, is parameter-free: it requires no knowledge of $\mu$, the smoothing parameter $\sigma$, or the horizon $T$, and it achieves regret $\widetilde O(d\sqrt{T/\sigma})$ for binary classes of VC dimension $d$ with a single call to an ERM oracle per round, which is optimal up to a $\sqrt{d}$ factor. En route to establishing the regret bound, we introduce several new techniques that may be of independent interest.
Read the full abstract ▾
All authors Sasha Voitovych, Adam Block, Alexander Rakhlin, Abhishek Shetty
Artificial Intelligence
EmbodiedRSI: Active Continual Robot Learning Through Hypothesis-Guided Co-Evolution
Python Song, Zhixuan Liang, Kelsey Fu et al. (+3 more)
Robot foundation models provide strong visuomotor control, yet their performance can degrade when object positions or task instructions change. Further improvements often require post-training on substantial
robot data, which can be costly to collect through methods such as teleoperation. Agentic harnesses can adapt around the model, but current self-evolving harnesses use
robot trials inefficiently when deciding which code and skill changes to pursue. We introduce EmbodiedRSI, a self-evolving agentic harness that autonomously decides where to explore next and turns the resulting physical interaction into improved code and skills. EmbodiedRSI realizes this through a Fast-Slow Dual-System Architecture, in which competing code and skill hypotheses are maintained in a Hypothesis Graph. Value-of-Information Experiment Selection chooses physical experiments that can distinguish these hypotheses. Their outcomes guide Code-Skill Co-
Evolution. The Slow System builds Hierarchical
Memory, and Reward-Grounded
Memory Learning selects effective
memory according to their value for later Fast-System improvement. On RoboCasa365, EmbodiedRSI reaches 77.0% overall success and 71.3% on Composite-Unseen, compared with 40.1% for the best baseline. EmbodiedRSI also reaches 86.8% overall success on LIBERO-Pro. Beyond
benchmark performance, EmbodiedRSI transfers zero-shot to real-world
robot, achieving 71.3% overall success across multiple challenging tasks.
Read the full abstract ▾
All authors Python Song, Zhixuan Liang, Kelsey Fu, Mengdi Wang, Junfeng Yang, Shilong Liu
Computer Vision
QuadTok: Quadtree Visual Tokenizer for Autoregressive Image Generation
Yucheng Mao, Zeyuan Chen, Xiaojun Shan et al. (+4 more)
We introduce QuadTok, a novel framework for visual tokenization and autoregressive image generation. Compared to traditional approaches using 2D grids or 1D
token sequences, we propose a hierarchical quadtree structure, bridging the gap between 2D spatial binding and 1D sequence-level flexibility. The QuadTok tokenizer dynamically allocates representational capacity to visually intricate areas while leaving homogeneous regions at a coarse resolution. Compared with a fixed 256-
token grid, our ImageNet-trained tokenizer saves approximately 10% of
tokens on ImageNet and 9% when transferred zero-shot to the COCO
dataset, while maintaining comparable reconstruction fidelity. Furthermore, the natural causality introduced by the tree structure seamlessly enables autoregressive image generation. Conditioned on a quadtree
topology supplied before generation, our 947M GPT-style generative model achieves a 2.08 gFID on the ImageNet $256 \times 256$
benchmark. Additionally, leveraging the strong spatial correlation preserved by the quadtree structure, the QuadTok generator enables zero-shot spatially controlled image generation capabilities. Code: https://github.com/myc634/QuadTok.
Read the full abstract ▾
All authors Yucheng Mao, Zeyuan Chen, Xiaojun Shan, Xiang Zhang, Divyansh Srivastava, Bingnan Li, Zhuowen Tu
Neural and Evolutionary Computing
Evolutionary Architecture Search for Chlorophyll-$a$ Prediction in Lakes using Sentinel-2
Kursat Komurcu and Linas Petkevicius
Small tabular
datasets with expert-designed spectral features are the norm in operational Earth observation, and the networks applied to them are typically hand-designed. We revisit one such published model – a Sentinel-2 algal bloom classifier – and ask what architecture search adds, holding the task, the features and the lake-level train/test split of the original study fixed. Searching an extended multilayer-perceptron space with regularized
evolution, and selecting on inner-cross-validation AUC only, we find networks that improve held-out AUC from 0.790 to 0.820 and accuracy from 0.733 to 0.748 while using 409 trainable parameters, 26 times fewer than the strongest hand-designed reference. The search converges on a consistent recipe – a single narrow layer, RMS normalisation, $\tanh$ activation, step-decayed RMSprop and weight averaging – that a practitioner would be unlikely to reach by default. At 1.6\,kB the resulting model is small enough to serve as an onboard screening trigger, which is the setting that motivates the work. Code: https://github.com/VU-AIML/automl4eo-bloom-nas.
Read the full abstract ▾
Data Structures and Algorithms
Rectangular matrix multiplication from polynomial products
Przemyslaw Uznanski
In this note, we extend the
matrix-multiplication analysis by OpenAI to rectangular products and prove $\omega(1,k,1)\le2$ for $0\le k\le\frac{1}{2}$, and $\omega(1,k,1)\le1+k+\frac{1}{4k}$ for $k\ge\frac{1}{2}$. In particular, $\omega(1, \frac{1}{2},1)=2$ and the dual exponent satisfies $\alpha\ge\frac{1}{2}$. The proof uses explicit degenerations of convolution tensors, multinomial counting, and Strassen's spectral
theorem. An angular constraint on three dot-product parameters gives both the rectangular curve and a bound for $\omega(a,b,c)$. As an application, Zwick's
algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.
Read the full abstract ▾
Computer Vision
Insights from Autoresearch for Solar Panel Segmentation
Justinas Lekavicius, Kursat Komurcu, Valentas Gruzauskas et al. (+1 more)
This paper investigates AutoResearch, a protocol in which a coding
language model edits a training program under a one-hour GPU budget and retains a change only if validation IoU improves. The protocol is applied to photovoltaic panel
segmentation on a frozen real-image split, with DeepLabV3–ResNet-50 held fixed. Three campaigns of 24 experiments, using Gemma~4 12B, Qwen3-8B all improve their one-hour baselines, but retained modifications do not transfer across hardware. The Qwen3-8B configuration, trained on real images only, reaches a test IoU of 0.836 versus 0.833 for the reference GAN-augmented schedule. Research repository https://github.com/VU-AIML/automl4eo-autoresearch-
segmentation.
Read the full abstract ▾
All authors Justinas Lekavicius, Kursat Komurcu, Valentas Gruzauskas, Linas Petkevicius
Robotics
HuMBLE: Human Motion-Driven Behavior Learning for Embodied Locomotion
Mike Zhang, Dongho Kang, Kevin Bergamin et al. (+19 more)
Despite recent advances in
humanoid locomotion, controllers optimized for command tracking and robustness tend to produce mechanical gaits, whereas controllers tied to human motion data often fail to generalize to commands outside the data distribution. This work introduces a learning framework that balances these competing objectives to synthesize real-time steerable, robust, and biomimetic locomotion policies from human data. Using an in-house curated locomotion
dataset covering diverse speeds and directions, we first learn a natural locomotion prior policy through a teacher-student
distillation process. Specifically, we train a full-body reference-conditioned policy with Reinforcement Learning (RL), then distill it into a lightweight prior policy conditioned solely on proprioception and a planar torso-velocity steering command. Next, we fine-tune the prior policy with multi-task RL to expand command coverage and robustness beyond the data distribution, pairing a goal-conditioned task that tracks arbitrary commands with a reference-guided task that tracks the human data as an explicit style regularizer. We validate our framework on three
humanoid robots: the Boston Dynamics Atlas R1, Atlas D1, and Unitree G1. Experimental results demonstrate robust performance across real-world scenarios, including direct user-controlled locomotion in indoor and outdoor environments, and integration as the locomotion layer within hierarchical control stacks.
Benchmarks against Tabula Rasa RL policies trained without human data and ablation studies confirm that our framework yields a lightweight, deployable policy that reconstructs coordinated whole-body behavior from a steering command, retaining the human gait characteristics while remaining robust and fully steerable.
Read the full abstract ▾
All authors Mike Zhang, Dongho Kang, Kevin Bergamin, Nicola Burger, Robin Deits, Jonathan Foster, Bilal Hammoud, Katie Hughes, Francesco Iacobelli, Twan Koolen, M. Eva Mungai, Zach Nobles, Shane Rozen-Levy, Jean Pierre Sleiman, Fangzhou Yu, Yunbo Zhang, Alfred Rizzi, Jessica Hodgins, Scott Kuindersma, Yeuhi Abe, Sylvain Bertrand, Farbod Farshidian
Machine Learning · Cross-listed from stat.ML
Best Arm Identification for Bandits with Shifting Means
Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal et al. (+2 more)
We study the best arm identification problem in a
stochastic environment with a novel form of
adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbol{\Delta}$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that
algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ($\mathsf{ISM}$). Assuming means bounded by $U$ and $\sigma^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $\delta$-correct and to enjoy a sample complexity bound of order $K (\sigma^2 + U^2) \Delta_{\min}^{-2} \ln \frac{1}{\delta}$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.
Read the full abstract ▾
All authors Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou, Dirk van der Hoeven
Distributed Computing
LOCAA: An Agentic System for Automated Lossy Compressor Tuning
Khondoker Mirazul Mumenin, Dong Dai, Sheng Di et al. (+2 more)
Large-scale scientific simulations generate substantial data volumes, making lossy compression essential for reducing storage and data movement costs. However, users configure compressors through numerical error bounds (EBs) while often evaluating results using quality metrics and end-to-end performance. Because the relationship between an EB and these outcomes varies across
datasets and compressors, identifying a suitable configuration typically requires exhaustive search, which can be time-consuming and computationally demanding. We present LOCAA, an Large
language model-based scientific lossy compression auto-tuning
agent that performs compression-in-the-loop search using tool-integrated execution, compressor-aware guidance, and persistent
memory. LOCAA supports user-defined objectives and constraints without requiring a specialized search strategy. We evaluate LOCAA across three scientific applications, five compressors, and three use cases: fixed-ratio compression, compression tuning under multiple quality constraints, and compression tuning under quality and time constraints. For fixed-ratio search across twelve fields from two applications, LOCAA requires 1.98x fewer evaluation trials than binary search and 5.03x fewer than FRaZ on average. For compression ratio maximization under joint Peak Signal-to-Noise Ratio (PSNR) and Structural Similarity Index Measure constraints across six fields from the Community Earth System Model application, LOCAA reduces the average evaluation trials from 61.5 using binary search to 17, corresponding to a 72.4% reduction. Persistent
memory further reduces the average number of trials by 27.9% across multiple timesteps of the same field. These results demonstrate the potential of tool-augmented LLM
agents to provide flexible and efficient compressor tuning across diverse scientific data and user-defined objectives.
Read the full abstract ▾
All authors Khondoker Mirazul Mumenin, Dong Dai, Sheng Di, Franck Cappello, Jinzhen Wang
Networking
A Compositional Perspective on Communication-Control Co-Design for Mobile Broadband Systems Beyond 6G
Angelo Vera-Rivera, Atefeh Termehchi and Ekram Hossain
Anticipated applications of beyond sixth-generation (B6G) mobile broadband networks will require the co-design of communication and control subsystems within the network architecture. Existing co-design approaches are predominantly optimization-driven, integrating subsystems through joint optimization problems. While this approach is effective in relatively simple systems, such formulations present challenges in (i) modular subsystem representations, (ii) tracing the propagation of requirements across subsystems, and (iii) systematically analyzing design-space feasibility, particularly as the number and complexity of interacting subsystems increase. In this article, we present a compositional perspective on co-design based on the formal theory of co-design. We examine how the notion of composition introduced by this theory can address the challenges of the conventional optimization-driven approach. Building on this perspective, we propose a composition-driven methodology for communication-control co-design in B6G networks and illustrate it through a wireless-assisted robotic control case-study. We then discuss how the composition-driven and optimization-driven co-design approaches can complement each other and why this complementarity may be beneficial for B6G networks. Finally, we identify key research challenges and future directions toward the practical adoption of the proposed methodology.
Read the full abstract ▾
Numerical Analysis
A finite element exterior-to-interior reconstruction in the fractional conductivity inverse problem
Mukul Dwivedi, Jesse Railo and Andreas Rupp
We develop a regularized finite element method for the fractional conductivity equation, recovering the conductivity on an exterior observation region from noisy Dirichlet-to-Neumann measurements and using this reconstruction to determine the interior conductivity. Mesh-localized inputs and mass-lumped Tikhonov regularization discretize the exterior determination principle of Covi–Railo–Zimmermann (2026, Calc. Var. PDE). We prove exterior \(L^2\)- and \(L^\infty\)-convergence with error estimates, including the logarithmic correction at the critical Hölder exponent. The exterior reconstruction enables the Liouville reduction to the Calderón problem for the fractional Schrödinger equation. Separated measurements recover the interior potential, after which overlapping measurements determine the exterior potential tail. Together with the recovered exterior conductivity, the tail supplies the exterior Cauchy data for a Tikhonov-regularized finite element least-squares continuation. We prove \(H^s\)-convergence of the transformed conductivity and \(L^2\)-convergence of the interior conductivity, together with logarithmic state-bias and conductivity error estimates for full observation spaces. The admissible reconstructions remain uniformly positive and bounded. We present one- and two-dimensional numerical experiments illustrating the accuracy of the exterior and interior reconstructions and their sensitivity to measurement noise and discretization.
Read the full abstract ▾