Machine Learning
Higher-Order Molecular Grammars for Generative and Foundation Models in Chemistry
Yiming Huang, Yujie Zeng, Vijay Prakash Dwivedi et al. (+4 more)
Molecular learning models are strongly shaped by their underlying representations. Yet standard sequential and graph formalisms struggle to explicitly encode higher-order
topology, such as ring systems and recurring motifs. Existing higher-order representations can capture these structures directly, but they are often computationally demanding and difficult to decode into valid molecules. Here, we introduce Higher-order Grammar Representation (HGR), a principled,
topology-aware framework that lifts molecules to combinatorial complexes and parses each complex into a compact sequence of production rules under a context-free higher-order grammar. By serialising higher-order
topology into rule sequences, HGR makes these structures directly compatible with standard sequence models, avoiding the computational overhead of explicit higher-order encodings while preserving topological expressiveness. To reduce
benchmark bias towards simple ring systems, we construct RingDiv, a ring-enriched
benchmark containing 1.18 million molecules, including the curated RingDiv300k subset, and introduce the ring diversity index (RDI) to quantify ring-system coverage. In molecular generation, HGR-based models uniquely combine 100% validity by construction with leading distributional
alignment, ranking first in FCD on all five generation
benchmarks. In representation learning, HGR-FM achieves the highest mean AUC across seven MoleculeNet
benchmarks under both transfer protocols, improving on the strongest baseline by 8.3 and 3.3 AUC points under probing and full fine-tuning, respectively. Collectively, these results establish HGR as an efficient higher-order representation for molecular generation and transferable representation learning.
Read the full abstract ▾
All authors Yiming Huang, Yujie Zeng, Vijay Prakash Dwivedi, Simone Foti, Jianmin Wang, Jure Leskovec, Tolga Birdal
Machine Learning
Decoding Looped Transformers Better for (Almost) Free
Weihao Liu, Huangjie Zheng, Tianrong Chen et al. (+5 more)
Looped
Transformers achieve parameter efficiency by repeatedly executing a shared block across recurrent loops. Each loop yields an intermediate representation decodable for the same next
token, yet standard decoding discards earlier states. Because earlier loops embody less computation, recurrence inherently supplies aligned weak-and-strong prediction pairs without auxiliary models or external training. We introduce LoopCD, a training-free contrastive decoding framework that guides
token selection by contrasting the final prediction with an earlier recurrent pass, operating either in logit space with one extra output pass (LoopCD-Logits) or in hidden-state space with zero output overhead (LoopCD-Hidden). Across four looped
Transformer families, LoopCD delivers substantial, consistent gains at full recurrent depth: LoopCD-Logits raises Ouro-2.6B-Thinking's AIME 2024 pass@1 from 61.88% to 73.33%, while LoopCD-Hidden lifts Huginn's HumanEval pass@1 from 22.56% to 31.71%. Crucially, these performance gains enable halving the number of recurrent loops while still matching or exceeding full-depth unguided baselines, reducing forward FLOPs by 22.5% to 48.2%. By transforming intermediate recurrent states into effective guidance signals, LoopCD achieves superior decoding quality while substantially reducing inference compute.
Read the full abstract ▾
All authors Weihao Liu, Huangjie Zheng, Tianrong Chen, Rohit Dilip, Richard He Bai, Yizhu Jiao, Yuyang Wang, Ruixiang Zhang
Formal Languages and Automata
Sufficient Reasons and Explanations for Reactive Systems
Hadar Frenkel and Nadav Rutman Moshe
We address the problem of temporal causality and explainability for reactive systems, and, in this setting, study sufficient reasons and contrastive explanations. These two notions are well-known explainability measures in the context of neural networks. In this work, we unify these notions for reactive systems and formal specifications given in temporal logic, providing dedicated definitions for sufficient reasons and contrastive explanations. We then lift these definitions to temporal sufficient reasons and contrastive explanations, providing more general and symbolic representations of explainability. We analyze the complexity of both verifying and finding explanations of the different types, and we demonstrate our approach using a prototype implementation.
Read the full abstract ▾
Machine Learning
SoftServe: A Scalable Quasi-Newton Method for Deep Learning
Joohwan Ko, Tetiana Parshakova, Diana Cai et al. (+1 more)
Quasi-Newton (QN) methods have long been among the most effective methods for large-scale unconstrained convex optimization. Two obstacles have limited their use in deep learning: non-convexity and enormous parameter sizes. We introduce SoftServe, a family of QN methods designed to overcome these obstacles without line searches or ad hoc
curvature corrections. SoftServe derives positivedefinite
curvature estimates from the variational objective of Berglund et al. (2025), even in the presence of negative
curvature. We develop diagonal and Kroneckerfactored variants that preserve positive definiteness by construction and scale to massive neural networks. Finally, SoftServe relies on the stable coupled Newton-Schulz iteration for the required
matrix operations, replacing costly
matrix decompositions with GPU-friendly
matrix multiplications. SoftServe excels on problems that are severely ill-conditioned, including tasks such as recurrent networks, deep autoencoders, physics-informed neural networks, and a 136M-parameter physics-informed
diffusion model, often achieving lower losses than established baselines including Adam,
Muon, and SOAP.
Read the full abstract ▾
All authors Joohwan Ko, Tetiana Parshakova, Diana Cai, Robert M. Gower
Computer Vision
OmniSeek: Native Tool Integration for Multi-turn Audio-Visual Reasoning
Haibo Wang, Jiteng Mu, Jialu Li et al. (+5 more)
We present OmniSeek, an agentic framework that transforms an Omni Large
Language Model (Omni-LLM) into an active, multi-turn
reasoning agent with native tool use. Rather than passively processing an entire audio-visual sequence in a single forward pass, OmniSeek makes evidence acquisition part of the
reasoning process: it dynamically decides whether to look or listen, and over which temporal window, to retrieve sparse but critical evidence across different modalities within long contexts. Through an iterative multi-turn protocol, the retrieved raw audio or visual segments are appended back into the context to support subsequent
reasoning. To cold-start this capability, we build a data engine that synthesizes OmniTraj-170K, a corpus of multi-hop Chain-of-Thought trajectories with interleaved audio and visual evidence. We first supervise the model on these trajectories to instill multi-turn tool-use behavior, and then further optimize the policy via a two-stage reinforcement learning with verifiable rewards. Moreover, we introduce an Audio-Visual Necessity objective that explicitly rewards successful trajectories whose
reasoning depends on both modalities, discouraging single-modality shortcuts. Extensive experiments across a wide range of
benchmarks demonstrate that OmniSeek learns adaptive cross-modal evidence seeking and consistently improves audio-visual
reasoning performance.
Read the full abstract ▾
All authors Haibo Wang, Jiteng Mu, Jialu Li, Jingru Yi, Yuanjun Xiong, Jianming Zhang, Lifu Huang, Mingze Xu
Computer Vision
Generative Cinematographer: Composing Camera and Object Motion in 3D
Jiahan Zhang, Chaohao Yang, Namitha Guruprasad et al. (+4 more)
Current controllable
video generation systems often rely on 2D motion trajectories or sparse drag signals for object motion. These controls are ambiguous because the same 2D trajectory can correspond to different 3D motions, especially when the camera and objects move simultaneously. We present Generative Cinematographer (GenCine), a system that lifts a single image into an editable 3D scene scaffold where artists jointly author camera and foreground motion. Artists specify a camera path and move selected foreground regions using local 3D motion handles. Several handles can move different parts of a subject independently, providing a piecewise-rigid approximation to non-rigid motion without a physics simulator or category-specific prior. To communicate these controls to a pretrained
video model, we project them into guidance maps. These maps record where the controlled regions appear in each frame, assign each handle a fixed color across frames and encode the current 3D positions of its controlled points in the same world coordinate system as the background. This lets us describe object motion relative to the scene even as the camera moves. For training, we recover controls from the motion observed in real
videos and use ground-truth geometry and trajectories from synthetic
videos. We train a lightweight guidance branch and LoRA adapters on a pretrained Wan model to follow these controls. Our experiments show consistent camera-relative motion, improved
geometric consistency under viewpoint changes, and strong controllability across diverse real-world scenes.
Read the full abstract ▾
All authors Jiahan Zhang, Chaohao Yang, Namitha Guruprasad, Vivekjyoti Banerjee, Trong-Tung Nguyen, Alan Yuille, Anand Bhattad
Machine Learning
From Gradients to Capabilities: Understanding Multi-Teacher On-Policy Distillation
Siqi Zhu, Suozhi Huang, Kaixuan Zhang et al. (+4 more)
Multi-teacher on-policy
distillation (MOPD) aims to combine the strengths of RL-trained teachers in a single student, but how teacher signals affect parameter changes remains underexplored. We study Qwen3-1.7B with four domain teachers trained with RL from the same initialization as the student, comparing gradients, optimizer updates, and task learning curves, with additional SmolLM3-3B diagnostics. We find that several factors influence teacher signals. First, loss averaging implicitly weights responses:
token averaging favors longer responses, and equalizing domain contributions retains this weighting within domains. Second, Adam's first moment reduces differences in parameter updates: the cosine similarity is 0.83 between teachers and 0.96 between averaging rules, despite differences in raw gradients. Third, BF16 rounding hides small changes: about 97% of FP32 master weights differ from initialization, but only 7–11% of BF16 weights do. Finally, the top-64 intersection KL gradient closely matches Qwen's full-vocabulary gradient, but the effect on task performance depends on averaging: mathematics accuracy is 2.6 points higher than with sampled-
token policy-gradient (PG) under response averaging and 2.1 points lower under global
token averaging.
Read the full abstract ▾
All authors Siqi Zhu, Suozhi Huang, Kaixuan Zhang, Yuheng Yang, Zhanyang Jin, Yihang Sun, Jiaxuan You
Machine Learning
Effective Resistance and Graph Neural Network Reliability in Tissue-Specific Interactomes
Jianru Shen
Protein function annotation needs to know which predictions to distrust, not only what a model predicts. We ask whether tissue-specific interaction structure carries that information. Our candidate signal is effective resistance, used previously to relieve over-squashing by rewiring. Across 24 tissue-specific interactomes it is dominated by inverse degree, and the degeneration deepens as the co-expression filtered network grows, with a Spearman correlation of -0.955. The residual departure from that limit exceeds degree-preserving null graphs in all 24 networks. Controlling for predictive
entropy, degree, annotation cardinality, local structure and feature-only difficulty, the residual explains additional per-node loss in 19 of 24 held-out networks once a permutation floor is subtracted, at every depth, and the effect strengthens monotonically with depth. The increment reaches 0.37% of the variance the controls leave unexplained, 5.6 times a permutation floor, against 1.5 times when the model is retrained in a degree-preserving null world. Selective prediction improves negligibly. The signal is reproducible; degree degeneration bounds it.
Read the full abstract ▾
Machine Learning
Every Ablation Is a Dose: Counterweights and the Semblance of Self-Repair
Areeb Ahmad, Pratinav Seth and Vinay Kumar Sankarapu
Ablate a component of a
language model, and other components often appear to adjust and compensate. This phenomenon, termed self-repair, has been observed repeatedly, but its mechanism remains unclear. The most systematic study to date concluded that self-repair is noisy and unlikely to have a single explanation. We argue that it has one: a gain already present before any ablation. Any intervention on a causally important component can be viewed as a point on a coordinate axis $\lambda$, the signed strength of a counterfactual contrast. Hence, conventional ablation methods are uncalibrated points on this axis. We show that the causal repair response for a fine-grained unit $r$ is governed by an affine law, $E_r(\lambda)=\mathrm{own}_r+\gamma_r\lambda$. The slope $\gamma_r$ is a fixed coefficient that consistently influences the model, with or without ablation, and its sign determines whether the unit counteracts or reinforces the removed signal. On a factual-verdict task across four models from distinct families (Gemma, Qwen, LLaMA, and Mistral), we identify components including MLP
neurons, OV
neurons, and singular directions that follow this affine law, 68 of 81 downstream directions in all. Moreover, we can anticipate the magnitude of $\gamma_r$ from the fixed weights. On the IOI
circuit of GPT-2 Small, seven of the ten heads the intervention can reach follow the law, and all seven are counterweights. From this perspective, what may appear as self-repair is a counterweight performing its usual operation when the contrastive signal emerges at the core.
Read the full abstract ▾
Robotics
Watch, Infer, Coordinate: Inferring Robot Partner Constraints for Zero-Shot Coordination
Suyu Ye, Zheyuan Zhang, Vaishnav Tadiparthi et al. (+5 more)
Robots operating in the physical world will increasingly need to coordinate with other
robots, particularly in manipulation tasks where an object may be too large or heavy for a single
robot to carry alone. Physical limitations caused by hardware degradation or actuator faults can restrict the actions a
robot can reliably execute, yet these limitations may be unknown to its partner. We study whether a helper can infer a
robot partner's physical constraints from observing it coordinate with another
robot, then use the inferred capability to coordinate with the same partner on a new task. This is difficult because a demonstration shows what the constrained
robot did, but not what it could have done. In physically coupled tasks, the other
robot may also compensate for its limitations, making those limitations difficult to identify from the constrained
robot's behavior alone. Our key insight is that these constraints shape the joint behavior of the team, making the actions of both
robots informative about the constrained partner's capability. We introduce Watch, Infer, Coordinate, a
benchmark spanning three physically coupled manipulation settings, together with an inference approach that scores candidate constraints using observed joint behavior. Across all three settings, our method substantially improves constraint inference and zero-shot coordination, approaching an oracle with access to the true constraints.
Read the full abstract ▾
All authors Suyu Ye, Zheyuan Zhang, Vaishnav Tadiparthi, Hossein Nourkhiz Mahjoub, Ehsan Moradi Pari, Tianmin Shu, Homanga Bharadhwaj, Nakul Agarwal
Computational Complexity · Cross-listed from quant-ph
Jiaqing Jiang, Nathan Ju, Ojas Parekh et al. (+2 more)
Quantum impurity models are paradigmatic models of interacting
quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting
fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating
impurity models, delineating the boundary between classical and
quantum tractability for this class of problems. Our main finding is that static properties of
quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical
algorithms that (1) estimate the ground-state energy to additive precision $\delta$ in time $\mathrm{poly}(n,\delta^{-1})$, and (2) estimate the partition function at inverse temperature $\beta$ to relative precision $\delta$ in time $\mathrm{poly}(n,\beta,\delta^{-1})$, where $n$ is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to
polynomial time, while establishing for the first time rigorous
polynomial-time guarantees for simulating
impurity models in thermal
equilibrium. On the other hand, we find that simulating dynamical properties of
impurity models is hard for classical computers but easy on a
quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of
quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial
quantum speedups for computing static properties, but provide an avenue for
quantum advantage in simulating
impurity physics out of
equilibrium.
Read the full abstract ▾
All authors Jiaqing Jiang, Nathan Ju, Ojas Parekh, Chaithanya Rayudu, Andrew Zhao
Computational Complexity · Cross-listed from quant-ph
Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses
Omar Al-Ghattas, David Gamarnik and Bobak T Kiani
We introduce a method for studying state preparation complexity in dense
quantum $p$-
spin Hamiltonians on $n$
qubits, going beyond bounds based only on
circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric
entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly $p$
qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of $\sqrt n$ for sufficiently large fixed $p$. At subquadratic effective profile complexity, the class cannot outperform a suitable
benchmark class at leading order, with product states providing a universal
benchmark. The proof combines an adaptation of a nonsymmetric
quantum de Finetti
theorem of Berta et al. (arXiv:1810.12197) with Gaussian process
entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires $\Omega(n^2/\log n)$ one- and two-
qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs,
entanglement-depth and
matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total
circuit width $O(n)$. In first-level reverse magic, a shallow
circuit is followed by an unrestricted Clifford
circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-
circuit depth. A sharper
benchmark shows that Clifford+$T$
circuits with $o(n)$ $T$-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.
Read the full abstract ▾
Computation and Language
AutoCompact: Learning When to Compact Context in Long-Horizon Coding Agents
Xuan Zhang, Longtao Zheng, Cunxiao Du et al. (+2 more)
Coding
agents solve repository-level software engineering tasks through long trajectories of code inspection, search, editing, and testing. As a task progresses, earlier exploration becomes stale, so managing context is more than avoiding overflow: an
agent must decide when to compact, what working state to preserve, and how to continue from it. We introduce AutoCompact, which trains a coding
agent to make these decisions as part of its policy. To collect training data, we run the base
agent on coding tasks and use a judge to review its compaction decisions, summaries, and actions after compaction. Flawed outputs are replaced with corrected ones before being executed in the environment, so each trajectory continues from the corrected decisions. We use these trajectories for supervised fine-tuning, then jointly optimize coding and compaction through reinforcement learning with task-success rewards. Experiments on SWE-bench Verified and SWE-PolyBench Verified show that AutoCompact improves pass rates over the base model by an absolute 9.2% and 5.0%, respectively. The improvements hold across all evaluated inference budgets, with a 256K context window that never overflows and with a 16K window whose overflow triggers fallback compaction.
Read the full abstract ▾
All authors Xuan Zhang, Longtao Zheng, Cunxiao Du, Bo An, Xin Dong
Computer Vision
World Observer: Joint Actor-Observer Generation for Persistent World Modeling
Hyunwook Choi, Dahyun Chung, Hyunsung Kim et al. (+4 more)
How can a world model continuously observe regions beyond the actor's current view?
Video world models simulate how an environment evolves from an
agent's actions, yet remain actor-centric. Once an object leaves the actor's view, they lose direct evidence of its
evolution, often failing to preserve its state and dynamics upon re-entry. To address this, we introduce World Observer, which decouples observing from acting by jointly generating a perspective actor for the
agent-centric view with one or more panoramic observers that watch selected world regions. This allows objects that leave the actor's view to remain visually evolving in an observer, so their updated states are reflected when they re-enter. We ground the actor and observers by warping from a shared panoramic source for explicit
geometric correspondence, and introduce an Observer Sink of high-resolution perspective references to restore fine appearance upon re-entry. Since the observers are decoupled from the actor, they can be placed freely across the scene, extended to multiple locations for broader coverage, and driven by control signals to steer out-of-view
evolution. To evaluate out-of-view
evolution, we further introduce world-space metrics and a
benchmark spanning real and synthetic scenes. World Observer substantially improves out-of-view dynamics while remaining competitive in visual fidelity, camera control, and 3D adherence.
Read the full abstract ▾
All authors Hyunwook Choi, Dahyun Chung, Hyunsung Kim, Siyoon Jin, Jinhyeok Choi, Junyoung Seo, Seungryong Kim
Robotics
DuoMind: Enabling Distributed Multi-Robot Coordination with Semantic Communication
Hanchu Zhou, Dechen Gao, Hang Wang et al. (+5 more)
Vision-
language models (VLMs) and
vision-
language-action models (VLAs) have recently driven rapid progress in general-purpose
robots, yet most progress has focused on single-
robot settings. Extending these capabilities to multi-
robot systems remains challenging because
robots must coordinate long-horizon behaviors while maintaining reliable, fine-grained execution. We introduce DuoMind, a distributed hierarchical framework for multi-
robot coordination through semantic communication. Each
robot uses a VLA-based action model for low-level execution and a VLM-based orchestrator for high-level
reasoning and inter-
agent coordination. At each planning step, the orchestrator at each
robot reasons over the task instruction, local observations, and messages received from other
robots. It then generates low-level instructions for the action model and semantic messages for peer
robots. This architecture exploits the complementary strengths of pretrained models by combining the semantic
reasoning capabilities of VLMs with the precise action-generation capabilities of VLAs. To address the scarcity of
benchmarks for multi-
robot coordination, we further develop RoboPoly, a
benchmark comprising long-horizon manipulation tasks that require coordinated, closed-loop execution under distributed control. Experiments on RoboPoly and RoboTwin demonstrate that DuoMind improves multi-
robot task performance, while ablation studies confirm the contributions of hierarchical orchestration and semantic communication. More details are available on our project page.
Read the full abstract ▾
All authors Hanchu Zhou, Dechen Gao, Hang Wang, Brendan Lynch, Boqi Zhao, Qiyao Ma, Raman Goyal, Junshan Zhang
Computer Vision
4Director: Controlling Video World Models with Rigid 3D Geometry
Wei Cao, Hao Zhang, Vikram Voleti et al. (+5 more)
Precise control over camera and object motion is essential for professional
video production. Existing methods control objects only coarsely, through image-plane cues that are ambiguous in depth and rotation or through 3D tracks and blobs that lack complete geometry and lose consistency across viewpoint changes. We introduce 4Director, a
video world model conditioned on an explicit 4D scene representation: each object is reconstructed once from the input image as a canonical mesh and moved by one prescribed rigid transformation per frame. This representation provides an intuitive 3D control interface and prevents unobserved geometry from being regenerated independently in every frame. We render the controlled scene as a depth
video and introduce a Motion Adapter that transforms this
geometric scaffold into
video while synthesizing view-consistent appearance, illumination, and non-rigid dynamics. For training, we construct RealCOD-Rigid, a new
dataset of 20,774 clips annotated with rigid 3D scenes by our automatic pipeline. We further introduce Identity-Gated IoU (IG-IoU), which jointly evaluates adherence to prescribed object motion and preservation of object identity. Experiments demonstrate that 4Director consistently outperforms prior methods in visual quality and in camera and object control.
Read the full abstract ▾
All authors Wei Cao, Hao Zhang, Vikram Voleti, Yuqun Wu, Mallikarjun B R, Shimon Vainer, Mark Boss, Yaoyao Liu
Machine Learning
When Do Intrinsic Rewards Lead to Exploration?
Scott W. Viteri, Laura Gomezjurado Gonzalez and Clark Barrett
Intrinsic rewards are designed to guide exploration in reinforcement learning by assigning value to an
agent's experience, for example through prediction error or learning progress. However, maximizing these rewards need not produce the most informative experience available. We propose a formal criterion for exploration that compares policies by the counterfactual information they acquire: how well their histories can substitute for experience under alternative policies. We construct a single, simple environment in which specified count-based, prediction-error, empowerment, and information-gain objectives have maximizing policies that are Pareto-suboptimal at acquiring counterfactual information. We explain these failures and establish conditions under which existing intrinsic rewards successfully encourage optimal exploration. We also construct an objective that assigns a higher value whenever exploration strictly improves under our criterion.
Read the full abstract ▾
Machine Learning
Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials
Nikolaos Makras and Sotirios Sabanis
We consider the problem of sampling from Gibbs distributions on
matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to
equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling
algorithm.
Read the full abstract ▾
Computational Complexity · Cross-listed from quant-ph
The Robustness of QAC0
Daniel Grier, Jackson Morris and Kewen Wu
In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{QAC}^0$
circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel $W$-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that $\mathsf{QAC}^0$ can exactly simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed
prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-
qubit gates may be used at any point in the
circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-
qubit gates are permitted: every $\mathsf{QAC}^0$
circuit can be approximately implemented by a $\mathsf{QAC}^0$
circuit consisting of just generalized Toffoli, $S$, and Hadamard gates. Moreover, this approximating
circuit can be constructed efficiently from a classical description of the original
circuit.
Read the full abstract ▾
Computer Vision
MosaiChunk: Compositing Spatio-Temporal Memory for Autoregressive Video Generation
Yiwen Zhang, Haocheng Xi, Michael Tian-Yue Liu et al. (+4 more)
Long-horizon autoregressive
video generation is limited by a finite context window. When an object or scene falls out of context, its fine-grained visual details may be lost and difficult to recover upon reappearance. To retain access to such visual details, we introduce MosaiChunk, a spatio-temporal
memory mechanism that composes a mosaic of selected historical key-value (KV) entries across space and time. Our approach is motivated by the observation that a frozen
video generator can directly consume such non-contiguous historical KV and recover the corresponding visual content. We therefore keep the generator fixed and learn only a lightweight router that determines which historical sections to include in the mosaic under a fixed active-
memory budget. We further introduce RememBench, a
benchmark of long-horizon revisits with
prompt-driven text-to-
video (T2V) and camera-driven image-to-
video (I2V) splits. Our experiments show that MosaiChunk consistently improves revisit consistency over both sliding-window inference and whole-chunk
retrieval under matched
memory budgets, across both T2V and I2V settings.
Read the full abstract ▾
All authors Yiwen Zhang, Haocheng Xi, Michael Tian-Yue Liu, Alexei A. Efros, Hadar Averbuch-Elor, Qianqian Wang, Haiwen Feng
Systems and Control
Feasibility of Simultaneous Input-Output Constraints for Tracking in a Class of LTI Systems: Part I
Junhyeok Yoon, Heather Hussain and Anuradha M. Annaswamy
This paper addresses simultaneous input and output constraint satisfaction for a class of multi-input linear time-invariant systems with state feedback and integral action. A control barrier function (CBF)-based governor modifies the reference command while preserving the nominal feedback controller. Necessary and sufficient conditions are derived under which the governor is feasible at every state of a prescribed operating set and ensures simultaneous input and output constraint satisfaction, forward invariance, and bounded closed-loop solutions. The paper also shows that these conditions need not be met for certain choices of the CBF governor parameters due to conflicts between input and output constraints. A systematic design procedure is proposed that first searches for feasible free parameters and, if necessary, proposes a relaxation in the input constraint that restores feasibility. A companion paper provides numerical examples and counterexamples illustrating these results.
Read the full abstract ▾
Computation and Language
From Knowledge Access to Source Learning: Developing Source-Specific Competence
Lucheng Fu, Kejing Xia, Yiyang Wang et al. (+10 more)
Large
language model (LLM)
agents increasingly rely on persistent external sources to solve sequences of knowledge-intensive tasks. Existing methods improve how source content is accessed and organized, while
agent-
memory systems preserve reusable knowledge from prior interactions, but repeated use of the same source is still largely treated as repeated access rather than an opportunity to progressively improve understanding of that source. We study source learning: developing reusable source-specific competence over a persistent authoritative source. We represent this competence with a persistent source model that captures reusable understanding of the source, including how its knowledge is structured, interpreted, and applied. To construct and progressively refine such models, we propose SourceLearn, which combines two complementary learning mechanisms. Self-Directed Source Learning identifies what remains incompletely understood and adaptively revisits the source, while Task-Guided Source Learning uses downstream experience to reveal local representational gaps and recurring needs in how source knowledge should be organized. In both cases, learning signals determine what should be reconsidered, while persistent updates are reconstructed from the authoritative source. Across five
benchmarks and three LLM backends, SourceLearn achieves the best performance in 13 of 15 settings, with gains of up to 22.6 points over Hybrid RAG and substantial overall improvements over static source representations and experience-based
memory baselines.
Read the full abstract ▾
All authors Lucheng Fu, Kejing Xia, Yiyang Wang, Yiqiao Jin, Jinjin He, Xiyuan Yang, Haoxin Liu, Ye Yu, Haibo Jin, Yijia Xiao, Wenke Lee, B. Aditya Prakash, Haohan Wang
Computer Vision
Omni-Embed-Mini: Binding Modalities Without Forgetting via Dense Distillation
Mohammed Irfan Kurpath, Jaseel Muhammad Kaithakkodan, Sahal Shaji Mullappilly et al. (+2 more)
Extending a text
embedding model to new modalities typically degrades text
retrieval quality, and existing omni-modal embedders compensate with multi-billion parameters. We present Omni-Embed-Mini, a 0.9B-parameter model that maps text,
speech, audio, images,
video, and visually-rich documents into a single shared cosine space without updating any text-side parameter. Our key insight is that the teacher signal requires no separate
embedding model: each media sample is paired with a dense cascaded caption, and the teacher target is simply the frozen backbone's own
embedding of that caption. Because teacher and student share the same backbone weights, they inhabit byte-identical geometry, and lightweight projectors plus phased LoRA adapters on the modality encoders suffice for
alignment. Training combines a Matryoshka SigLIP contrastive loss with an online hybrid hard-negative miner whose negatives sharpen as the encoder improves. The recipe carries over to a 2.3B variant by swapping in a native
vision-
language backbone. Omni-Embed-Mini-0.9B keeps its text weights bit-identical to the backbone, so training cannot regress text
retrieval (49.57 nDCG@10 on MTEB-v2 BEIR-8), while extending it to five additional modalities, and is ~2.7x to 9.5x smaller than every open omni embedder we compare against. The 2.3B variant is competitive with the closed gemini-
embedding-2, edging ahead of it on the overall-modality average. Models, code, data and evaluation harness are on our project page: https://omniembed.cvmbzuai.com
Read the full abstract ▾
All authors Mohammed Irfan Kurpath, Jaseel Muhammad Kaithakkodan, Sahal Shaji Mullappilly, Ivan Laptev, Hisham Cholakkal
Computational Complexity · Cross-listed from quant-ph
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
Matthew Coudron, Michael J. Gullans, Jon Nelson et al. (+2 more)
We give a deterministic classical
algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth
quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$-bit output string. This improves over prior state-of-the-art
algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local
circuits.
Read the full abstract ▾
All authors Matthew Coudron, Michael J. Gullans, Jon Nelson, Joel Rajakumar, Shi Jie Samuel Tan
Computational Complexity · Cross-listed from quant-ph
A provable quantum advantage for approximate optimization via decoded quantum interferometry
Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones et al. (+2 more)
Decoded
quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on
quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all
polynomial-time classical
algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal
polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any
polynomial-time classical
algorithm and the approximation ratio achieved by the DQI
algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI
algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.
Read the full abstract ▾
All authors Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber
Machine Learning
Faynt: Scaling and Optimizing Policies for Competitive Melee
Ali Janati, Nikita Kuzmin, Rohit Swamy et al. (+1 more)
We introduce Faynt, a family of 10M- and 75M-parameter
Transformer policies for Super Smash Bros. Melee, each controlling all 26 characters with a single checkpoint. After reinforcement learning (RL), the 10M wins 240 of 244 same-character games (98.4%) against fourteen specialist and multi-character releases on their supported rosters, with a winning record against every release. These opponents retain 21- or 24-frame action delays; Faynt uses no added delay, and we have not isolated the effect of this difference. In a separate evaluation against a privately supplied zero-delay Slippi-AI model, the 10M wins all 68 games across two conditioning settings. We study architecture, optimization, scaling, and hyperparameter transfer to guide pretraining on approximately 840,000 human replays. Post-training combines rank- and outcome-based curricula, 75M-to-10M
distillation, and RL restricted to Fox mirror matches. On the initial 152-game
benchmark, the supervised 10M wins 69.7% of games, compared with 45.4% for the pretrained 75M, despite higher overall held-out controller-prediction loss. The weighted validation loss used for supervised checkpoint selection agrees with the win-rate ordering of all four pretrained and supervised policies. After supervised post-training, both models take less damage per minute, build larger early leads, and win more often after losing the first life. Optimized inference on recorded game states averages 5.2 ms per decision for the 10M and 8.7 ms for the 75M on an NVIDIA T4, excluding emulator execution and communication. We open-source the weights, both
benchmark suites, and a platform for automated model tournaments.
Read the full abstract ▾
All authors Ali Janati, Nikita Kuzmin, Rohit Swamy, Charles Niu
Game Theory
RANDAO Manipulation in the Presence of MEV
Kaya Alpturer, Nicholas Hope and S. Matthew Weinberg
Ethereum's randomness beacon (RANDAO) is well-known to be manipulable, and prior work [AW24] computes the precise fraction of blocks a strategic proposer can propose. The fraction of blocks proposed, however, is only a proxy for participants' rewards. We propose a generalized reward model capturing many canonical forms of rewards: consensus reward rollover, multi-block MEV, CEX-DEX arbitrage, oracle manipulation, and others. We provide a methodology that computes an {\epsilon}-optimal strategy for any reward scheme in our model (and in particular, any combination of the above rewards). Finally, we apply our methodology to several canonical examples, and establish the sensitivity of RANDAO manipulation to the underlying rewards. We find that if rewards partially roll over, or scale super-linearly with consecutive blocks, the incentive to manipulate RANDAO is amplified. Lastly, we investigate tail-slot slashing, which can be modeled as a reward function, and show that honest
equilibria can be recovered.
Read the full abstract ▾
Computation and Language
Keyword Harnesses Fail Open: A Cheap Diagnostic Ladder for Tool-Use Claims in Small Language Models
Juan S. Santillana
Keyword-matching
benchmarks can credit small models for tool use they never perform. We document such a false positive in a matched-architecture pair of Spanish security
language models and propose a ladder of strict, cheap diagnostics. A 661.6M parameter model (approx. 65% code/technical text; no dedicated SFT) and a 1,109M model (web-heavy multi-phase curriculum; 6B-
token tool-SFT) share decoder, tokenizer, and special
tokens, scoring almost identically on lenient tool-use metrics (B4: 0.660 vs. 0.650). Verbatim-reproduction checks on training examples separate them completely: the 600M emits valid tool calls with generalized arguments on 6/6 examples; the 1B does so on 0/6 across checkpoints. A first-
token probe localizes the 1B's failure to a missing prior (prob. $10^{-4}$–$10^{-5}$ on <|tool_call|>), which was erased by its web-heavy training phase. A targeted SFT recipe (diverse corpus, 5x higher learning rate, 2,202 steps, ~3.3 GPU-hours) repairs the 1B using three orders of magnitude fewer
tokens than the failed phase. On all 269 corpus rows, valid emission rises from 0.100 to 0.959 (600M: 0.926). On 238 unseen
prompts, the repaired 1B passes 0.536 vs. the 600M's 0.428 ($p = 0.004$).
Embedding-drift checks show the repair did not move the trigger
token's tied
embedding (97.7% of the bf16 table remains bit-identical), meaning changes live in the surrounding network. Both models over-trigger, rarely answering negative
prompts without a call (0.09 for 600M, 0.17 for repaired 1B). Factorial analyses confirm all repair configurations install the format, though suppression benefits from a diverse corpus remain a hypothesis due to seed sensitivity. This cheap diagnostic ladder costs minutes of CPU time and should gate tool-use claims on small models.
Read the full abstract ▾
Machine Learning
Finetuning with Sampling: SFT Learns Better Than You Think
Aayush Karan, Sitan Chen and Yilun Du
Introducing new capabilities to frontier models has long been the goal of posttraining, which predominantly employs supervised finetuning (SFT) and reinforcement learning (RL) to this end. Conventional wisdom dictates that RL enables strong generalization on new tasks without losing existing capabilities, while SFT is prone to weak generalization and catastrophic forgetting. At the same time, SFT can learn from off-policy expert data, whereas RL must rely on a model's ability to find successful trajectories with repeated sampling. In our work, we seek to leverage the strength of on-policy learning while utilizing the privileged information contained in off-policy data. However, rather than modifying the learning objective to accommodate this data, we instead tailor the data distribution to better suit the learner. We introduce a Markov chain Monte Carlo (MCMC) sampling
algorithm that progressively transforms off-policy traces to be more on-policy given a reference model for finetuning. Across tasks like scientific skill acquisition, mathematical
reasoning, and open-ended expertise, our sampling
algorithm enables SFT to rival prevailing posttraining techniques, often generalizing better and forgetting less than strong on-policy baselines. In addition, the resulting finetuned models exhibit strong distributional performance and are capable of learning beyond sharpening the base model distribution. At a higher level, our approach presents sampling as a model-native operator that shapes data for learnability, offering broader utility as a general-purpose primitive throughout the posttraining stack.
Read the full abstract ▾
Computer Vision
MIRTO: a registration-gated, multiverse-tested evaluation protocol for unsupervised anomaly segmentation in brain MRI
Negin Kafee Hernashki and Soumick Chatterjee
Unsupervised anomaly detection (UAD) methods for
brain MRI are ranked by a single score, yet that score rests on choices that are rarely reported: how each anomaly map is aligned with the reference, how and on which data the threshold is set, and which false-positive budget, metric, aggregation and lesion definition are used. We present MIRTO, an evaluation protocol that makes these choices explicit and measures their effect. It gates the geometry of every comparison with a registration check and label-free diagnostics of known power, sets thresholds on validation data alone and reports the false-positive volume actually realised on test, repeats each comparison over 15,552 defensible evaluation pipelines, and attaches paired subject-bootstrap intervals with multiplicity control. Applied to four UAD methods trained on the same healthy data and tested on 312 BraTS 2020 subjects, MIRTO showed that an axis-order mismatch between stored maps and the reference lowered a
diffusion model's voxel AUROC from 0.873 to 0.583 whilst barely moving its slice-level AUROC. Within each metric, the method explained at least 0.95 of the variance in voxel AUROC and AUPRC and 0.77 in Dice, but only 0.14 in lesion sensitivity, where the lesion definition and hit criterion dominated. A Dice advantage that was significant at validation thresholds vanished at equal realised false-positive burden, and an exact identity attributes it to threshold transfer. A training-free change to REFLECT's latent aggregation raised Dice at equal burden by 0.052. Nine hypotheses were tested against explicit criteria; because the same cohort served to develop the protocol, all inference is exploratory.
Read the full abstract ▾