Peer Revenue Impact factor: volatile

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Computer Science

cs Watch Computer Science

Thursday 3 September

Machine Learning

Robust PAC Learning of Concurrent Stochastic Games

Angel Y. He and David Parker

We introduce the first Probably Approximately Correct (PAC) learning framework for general-sum concurrent stochastic games (CSGs) with transition uncertainty, while addressing the challenge of Nash equilibrium (NE) existence. Our algorithm maintains data-driven $L^1$ confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal $\varepsilon$-NE, using a robust MDP-based exploration mechanism to drive joint state-action coverage. Crucially, we introduce a Nash margin characterisation that enables principled reasoning about equilibrium existence: the framework either returns an $\varepsilon$-approximate NE whose social-welfare value is $\varepsilon$-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition $p_{\mathrm{reach}}>0$ over relevant state-action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity $\widetilde{O}\left( {R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2)} \right)$. Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.
Read the full abstract

Human-Computer Interaction

Toward Frontier-Quality Declarative UI Generation at Small-Model Cost

Yingxiang Yang, Weihang Xiao, Ben Bullough et al. (+2 more)

Declarative UI protocols such as A2UI let applications generate interactive UIs by selecting pre-built components from a catalog and binding their props to application data, rather than emitting frontend code from scratch. This contract is attractive for production systems because of safety and consistency. An open question is: can low-latency and low-cost small models achieve the required quality for A2UI-based UI generation? To answer this, we systematically study three controllable design choices for catalog-conditioned A2UI generation: supervised fine-tuning (SFT) data construction method, model size, and component-catalog size. Across two React/TypeScript domains and four base checkpoints spanning two model families (Qwen 3.5 0.8B/2B/4B; SmolLM 3B), we find: (i) a 4B fine-tuned student recovers ~98% of teacher semantic quality and ~97% of teacher visual quality at more than an order of magnitude lower cost than frontier API calls; (ii) both augmented strategies (Perturbed-catalog and Constrained-GT) Pareto-dominate the unaugmented Full-catalog baseline, while specializing on different axes; (iii) even small models can handle and benefit from relatively large component catalog size. We distill these results into practitioner-facing trade-offs and deployment recommendations across the three design choices.
Read the full abstract

All authors Yingxiang Yang, Weihang Xiao, Ben Bullough, Tushar Deshpande, Niresh Agarwal

Computer Vision

Seeing Before Synthesizing: VLM-Guided Transition Event Discovery for Weakly-Supervised Dense Video Captioning

Ye-Chan Kim, Seunghee Choi, SeungJu Cha et al. (+4 more)

Weakly-Supervised Dense Video Captioning aims to localize and describe multiple events in untrimmed videos given only an ordered set of event-level captions per video. Recent work synthesizes auxiliary transition captions via LLM to provide additional vision-language alignment, but these captions lack visual grounding and are rigidly assigned to every inter-event gap at a fixed location and duration. To address these, we propose Seeing Before Synthesizing (SBS), a framework that adaptively provides visually grounded linguistic guidance only where warranted. Leveraging a VLM, we generate frame-level narratives for the inter-event gaps and detect transitions from the semantic variation across them. For identified transitions, we then refine inter-event temporal masks by blending the temporal midpoint with the semantic change point and selecting the width that maximizes vision-language alignment. Experiments on ActivityNet Captions and YouCook2 demonstrate state-of-the-art performance in both captioning and localization.
Read the full abstract

All authors Ye-Chan Kim, Seunghee Choi, SeungJu Cha, Si-Woo Kim, Hwiseon Kim, Hyungee Kim, Dong-Jin Kim

Computation and Language

Knowledge Acquisition During Pre-training? Large Language Models Learn Better With Auxiliary Views

Joseph Lee, Yidi Huang, Dokyoon Kim et al. (+2 more)

Gaps remain in our understanding of how large language models (LLMs) acquire knowledge during pre-training. We find that auxiliary views, conceptual reformulations, are key to this process. We design controlled experiments to isolate this. First, holding the token budget fixed, allocating tokens from paraphrases to auxiliary views improves learning even for factual recall, which we use near-verbatim sentences from the original document to test. Second, the effectiveness of auxiliary views is not contingent on the strength of the model that generates them. Third, we establish that paraphrasing is helpful but only at smaller batch sizes. Fourth, we identify types of knowledge that aid learning in the presence of prior knowledge gaps. Finally, we examine how these effects manifest mechanistically via layer-wise biases and compression. Together, our findings suggest that auxiliary representations of knowledge are a key factor in the success of pre-training, and explains why data diversity matters. Further, our results provide clear recipes for synthetic data augmentation along with implications on the self-improvement in LLMs.
Read the full abstract

All authors Joseph Lee, Yidi Huang, Dokyoon Kim, Shu Yang, Li Shen

Artificial Intelligence

A Computationally Feasible Framework for Causal Probabilistic Explanation

Rafal Urbaniak, Sam Witty, Daniel Waxman et al. (+7 more)

Explaining why a specific outcome occurred, and which inputs deserve the blame or credit, is central to philosophical, scientific, and policy analysis. Existing tools split into two camps. The theory of actual causality (AC) gives principled verdicts, but only for toy-sized models, because computing them requires enumerating counterfactual scenarios. Scalable attribution methods like SHAP (or even causal SHAP) at least partially ignore the causal structure that generated the data, and can give answers that conflict with a careful causal analysis. We close this gap with Probabilistic Causal Impact (PCI). PCI builds on actual causality and on Pearl's notions of probability of necessity and sufficiency, but recasts the question of explainability as an estimation problem on a probabilistic causal model that is easily approximated via Monte Carlo. By specifying a distribution over "candidate explanations," a distribution over counterfactual values, and a scoring function, PCI provides tractable, causally grounded, graded explanations, generalizing AC and Pearl's probability of causation as degenerate cases. We evaluate PCI in synthetic and real-world examples, spanning consistency checks with AC, scaling experiments, complex continuous-valued dynamical systems, and a real-world deployed causal machine learning model trained on millions of datapoints.
Read the full abstract

All authors Rafal Urbaniak, Sam Witty, Daniel Waxman, Andy Zane, Poorva Garg, Emily Bunnapradist, Sankaran Vaidyanathan, Jack Feser, Drew Lehe, Eli Bingham

Computer Vision

Zero-Shot Novel Depth Synthesis Using 3D Foundation Models Scene Representations

Denis M. Akola and David F. Fouhey

3D Foundation Models (3DFMs) such as VGGT have recently pushed the boundaries of 3D vision by predicting rich unified representations with feed-foward transformers. The scene representations learned by these models enable strong performance on multiple 3D vision tasks. In this paper, we investigate using their internal representations to infer 3D in the scene from new views. Our hypothesis is that in order to solve the task of 3D reconstruction, these models need to learn a representation that includes a large amount of general knowledge about 3D scenes. After showing that it is possible to decode hidden surfaces from internal 3DFM representations, we propose a method, Z3D, that estimates pointmaps in unseen views by doing latent diffusion on 3DFM representation. We show that Z3D can predict realistic depth maps for new views across multiple datasets.
Read the full abstract

Computation and Language

Last Translation Benchmark

Vilém Zouhar, Niyati Bafna, Mukund Choudhary et al. (+257 more)

For scientific progress, we need benchmarks that test the limits of state-of-the-art models, and evaluation methods that inform us about failure cases. As models get stronger, standard benchmarks for machine translation are approaching saturation. Further, automatic translation metrics are unreliable, opaque, and vulnerable to reward-hacking. Even gold human evaluation is not problem-free, because it often lacks reproducibility, objectivity, and scalability. Overall, this prevents us from tracking progress in the field and identifying pathways for improvement. We introduce the Last Translation Benchmark, a collection of human-authored and peer-reviewed examples (texts, images, audio, videos) that break leading machine translation models. We also present a new evaluation approach: each example comes with handcrafted verification rules describing concrete failure cases on that example, therefore allowing reliable and actionable future evaluation. The Last Translation Benchmark is a live dataset that accepts ongoing contributions. The latest version is LTBv1, containing accepted contributions prior to September 1st 2026, with future releases planned as new data is continuously collected.
Read the full abstract

All authors Vilém Zouhar, Niyati Bafna, Mukund Choudhary, Maike Züfle, Sara Rajaee, Pinzhen Chen, Jannis Vamvas, Sara Papi, Ona de Gibert, Bhavitvya Malik, Eliya Habba, Orfeas Menis Mastromichalakis, Patrícia Schmidtová, Michelle Wastl, Sheriff Issaka, Leshem Choshen, Stella Biderman, Antonis Anastasopoulos, Jan Niehues, Rico Sennrich, Mrinmaya Sachan, Ondřej Bojar, Kenton Murray, Jörg Tiedemann, Alham Fikri Aji, Philipp Koehn, Christof Monz, Alexandra Birch, Sowmya Vajjala, Chalamalasetti Kranti, Cristina España-Bonet, Nobin Sarwar, David Kaczér, Sourajit Saha, Jonathan Tonglet, Shunta Asano, Malik Marmonier, Daban Q. Jaff, Vaisakhi Mishra, Hend Al-Khalifa, Gabriele Sarti, Nils Rehlinger, Juan Daniel Cuervo Villa, Dominik Macháček, Saugata Purkayastha, Jagannathan Ramanujam, Shubhashis Roy Dipta, Aviral Nigam, Shuaib Shuaib Yusuf, Heejin Do, Jonathan Yahav, Johannes-Rudolf David, Maria Carmen Staiano, Zuzana Nadova, Fred Philippy, Ron Keinan, Maria Lymperaiou, Silvia Casola, Fabian Retkowski, Andrés Jerez, Hanna Yukhy- menko, Sangwon Ryu, Avantica Vempati, Sukannya Purkayastha, Adrian Cosma, Erivan Inan, Vitalii Babenko, Wafa Aissa, Valentin Scourneau, Fatima Haouari, Venkata Prasanth Kumar Gummadi, Mehdi Jafarzadeh, Manon Reusens, Kaiser Sun, Lukas Edman, Shaomu Tan, Giuseppe Gallipoli, Pawan Sasanka Ammanamanchi, Manar Ali, Mohammad Sadegh Gholizadeh, Dipankar Srirag, Marek Šuppa, Javier García Gilabert, Ruta Binkyte, Ana-Maria Bucur, Sabry E. Farrag, Youssef Saber, Yihong Liu, Theresia Veronika Rampisela, Christian Hoang, Nicoleta Cojocaru, Jan Kocoń, Jean Maillard, Xiaochuang Yuan, Sina Ahmadi, Daryna Dementieva, Philipp Mondorf, Kaustubh Dhole, Valmik Nahata, Roman Wixinger, Amir Hossein Yari, Shenbin Qian, Manuel Tuor, Fida Mohammad Thoker, Sergey Troshin, Lance Calvin Lim Gamboa, Amir Arsalan Rezapour, Kätriin Kukk, Koel Dutta Chowdhury, Shaswati Saha, Seth Aycock, Bo Chen, Linh Vu, Vatsal Venkatkrishna, Shayan Bali, Arafat Ahsan, Luan Thanh Nguyen, Hassan Soliman, Ngoc Quynh Tram Do, Azmine Toushik Wasi, R. Damanhuri, Marius Huber, Kazuki Egashira, Jimson Paulo Layacan, David Africa, Vladislav Poritski, Mike Zhang, Deep Shah, Abdulaziz Nura Kani, Luis Frentzen Salim, Paul Gavrikov, Bello Umar Bello, Ayush Sunil Munot, Anumit Garg, Yolanda Xavier, Qiaoyuan Zheng, Kawsar Ahmed, Debanshu Das, Zimu Wang, Gengyu Rao, Kamile Dementaviciute, Farhan Farsi, L D M S Sai Teja, Dawei Zhu, Yi Fan, Wei Liu, Marco Gaido, Elias Herranen, Sankalan Pal Chowdhury, Karen Sanchez, Guy Kaplan, Farzad Shami, Ashok Urlana, Amir Hossein Kargaran, Sofie Goethals, Priyaranjan Pattnayak, Oksana Volchek, Marii Ojastu, Hongbin Na, Emilian Radoi, Chenyi Zhao, Carlos Hinojosa, Andrei Niculae, Andrea Gregor de Varda, Zaid Alyafeai, Tomasz Limisiewicz, Reem Alzahrani, Pouya Sadeghi, Nehal Kathrotia, Mateusz Lango, Enzo Doyen, Alex Flückiger, Ulysses Sekai Tully Carr, Samuel Simko, Ritwik Tiwari, Rishit Dagli, Isaac R Caswell, Bowen Yi, Aicha Chorana, Selja Keränen, Sadiksha Chitrakar, Muhammad Ravi Shulthan Habibi, Joy Olusanya, Bishal Shrestha, Zhengxiang Wang, Vivek Harsha Lakkamaneni, Sophia Conrad, Panayiotis Panayiotou, Nazia Tasnim, Marta Punsola Munárriz, Marko Culjak, Luis Lara, Jenny Chim, Jannatul Nayem, Fidel Rodríguez Velásquez, Eran Yahav, Blanka Kövér, Beatrice Savoldi, Anmol Goel, Aishik Mandal, Tosin Adewumi, Raoyuan Zhao, Mykola Haltiuk, Antonia Karamolegkou, Yuxing Lu, Thura Aung, Naser Almousa, Tommaso Cerruti, Raia Abu Ahmad, Beni Egressy, Alireza Pakniat, Stéphane J.P.S. Thunus, Rachel Bawden, Lena Libon, Samridhya Biswas, Prakhar Gupta, Nusrat Jahan Lia, Nguyen Tai, Natchapon Jongwiriyanurak, Minh Ngoc Do, Ivan Barać, Dzmitry Kuzmin, Badal Nyalang, Antoine Taroni, Andy Catruna, Rushikesh Zawar, Roland Aydin, Pavel Stepachev, Ilai Yaron Levy, Andreas Simons, Rayyan Merchant, Ziyi Yang, Samuel Frontull, Kenneth Enevoldsen, Harris Abdul Majid, Tim Graf, Tatiana Bielakova, Sharifa Djurabaeva, Shaoxiong Ji, Jirui Qi, Ayla Rigouts Terryn, Yurii Paniv, Xiyan Fu, Sunisth Kumar, Shree Harsha Bokkahalli Satish, Papa Abdou Karim Karou Diallo, Mengyu Ye, Maximilian Vieweg, Matija Akrap, Kristýna Onderková, Joseph Attieh, Ivan Yuri De Leon, Ibrahim Baroud, Esrael Teferi Tensay, Elisabeth Fittschen, David Dukić, Benoît Sagot, Jingwei Ni, Yu Fan, Juri Opitz

Artificial Intelligence

Rethinking On-Policy Distillation of Large Language Models II: One Training Example

Zixuan Fu, Bingxiang He, Yuxin Zuo et al. (+10 more)

On-policy distillation (OPD) combines student-generated rollouts with dense token-level supervision from a teacher. Existing work has mainly studied its algorithmic behavior, leaving the role of training data unclear. We examine this role at the data-minimal limit by training on a single query. One-shot OPD keeps improving for hundreds of steps and recovers most of full-data OPD's gain across task domains and model families. We explain this result through the states visited during training and the rate at which the student aligns with the teacher. We measure state coverage, the fraction of the states full-data OPD visits that a query set's rollouts reach. A single query already reaches \(71.5\%\), most of it within the first 100 steps. Adding semantically distinct queries raises coverage and validation accuracy together, until 16 queries reach \(98.9\%\) and match full-data training. Yet alignment slows at a similar pace whether OPD trains on one query or the whole dataset, and even a fixed set of states takes hundreds of steps to absorb. OPD is therefore data-overfed but algorithm-starved. Its rollouts quickly expose broad supervision, while the student absorbs that supervision increasingly slowly. The state-coverage result extends to multi-teacher OPD, where 16 semantically diverse queries per domain match full-data MOPD. As a further stress test, content-light templates and off-domain WildChat queries also approach the real-query baseline. Task content and induced state coverage can therefore come apart. We hope these findings direct future work toward the step efficiency of OPD, and prompt a re-examination of the data and the mechanisms behind its recent successes in frontier post-training.
Read the full abstract

All authors Zixuan Fu, Bingxiang He, Yuxin Zuo, Haohuan Huang, Jinqian Zhang, Ruhang Xiao, Cheng Qian, Qinyu Luo, Huan-ang Gao, Yudong Wang, Zhiyuan Liu, Ning Ding, Chaojun Xiao

Artificial Intelligence

A Case Study on Emergent Cheating and Whistleblowing in Autonomous Research Swarms

Davide Paglieri, Logan Cross, Tim Genewein et al. (+3 more)

Multi-agent AI science ecosystems rely on agents possessing tools that allow them to communicate, coordinate, and build on each other's work. Yet this shared infrastructure can also introduce vulnerabilities by creating a substrate for the contagious spread of unintended and undesirable behaviors. We report a case study on a research collective of 100 autonomous LLM agents tasked with proving formal mathematical conjectures. Within the swarm, cheating spontaneously emerged and was later challenged by whistleblowers - both without any external intervention. When a single agent discovered an exploit in the evaluation system, it propagated across the collective via a shared knowledge library and later through peer-to-peer messages. Despite early reluctance, a cohort of agents adopted the exploit in response to competitive pressure. A separate group of agents produced an emergent counter-response: auditing fraudulent proofs, alerting peers across broadcast and private channels, staging boycotts, lodging formal complaints, and proposing validation patches. In recent incidents, agent swarms coordinated covertly through improvised side-channels (Dalton and Wallace, 2026; Greenblatt et al., 2026). Our setting differs: the same transparent channels that carried the exploit also gave non-cheating agents the visibility they needed to detect fraud, organize resistance, and enforce norms. We cast the problem of managing the agents' shared infrastructure as the knowledge commons governance problem (Ostrom, 1990). To protect the commons from exploits, we propose to adopt institutional mechanisms, such as graduated sanctioning and collective-choice rules, to support decentralized self-governance in autonomous swarms.
Read the full abstract

All authors Davide Paglieri, Logan Cross, Tim Genewein, Joel Z. Leibo, Nenad Tomasev, Alexander Sasha Vezhnevets

Distributed Computing

Para-Pipe: Exploiting Hierarchical Operator Parallelism of ML Computational Graphs on SoCs

Yujie Zhang, Huiying Lan, Ehsan Aghapour et al. (+5 more)

As edge-based deep learning applications become more complex, optimizing performance on heterogeneous System-on-Chips (SoCs) presents unique challenges. Traditional pipelining techniques distributing the computation across different on-chip processing units, while effective for throughput, do not address the latency demands posed by modern neural networks with complex interdependencies and extensive operator parallelism. There is a potential in leveraging operator parallelism to enable concurrent execution across multiple processing units, thereby reducing inference latency. However, prioritizing pipelining or parallel execution often necessitates a compromise, where optimizing one performance metric adversely impacts the other. This paper introduces Para-Pipe, a hierarchical mapping framework that integrates intra- and inter-stage operator parallelism within a pipelined architecture. Para-Pipe navigates the trade-off between throughput and latency by selectively fine-tuning parallelism levels within and across pipeline stages. This strategy can significantly reduce inter-processor communication overhead, significantly improving energy efficiency. Our evaluation demonstrates that Para-Pipe generates multiple Pareto-optimal configurations, achieving a balance between throughput and latency on an Amlogic SoC equipped with ARM big.LITTLE CPUs and GPU, as well as the Black Sesame Technology SoC featuring a deep learning accelerator and two DSPs. More importantly, throughput-optimized configurations under Para-Pipe on Amlogic SoC show an average energy efficiency improvement of 11.0% over purely pipelined strategies and 23.3% relative to non-pipelined parallel execution.
Read the full abstract

All authors Yujie Zhang, Huiying Lan, Ehsan Aghapour, Zhiyuan Ning, Peng Zan, Weidong Shao, Anuj Pathania, Tulika Mitra

Software Engineering

SWE-Gate: Passing Functional Tests Is Not Enough for Software Engineering Agents

Xin He, Yanlin Wang, Mingwei Liu et al. (+3 more)

Repository-level software engineering benchmarks have significantly advanced the evaluation of coding agents, but existing benchmarks primarily measure whether generated patches pass functional tests and overlook review-derived acceptance constraints (review constraints) that often influence whether a patch is acceptable in real-world software development. We introduce SWE-Gate, a repository-level benchmark for software engineering agents that explicitly evaluates review constraint compliance alongside functional correctness. SWE-Gate derives review constraints from real pull request review comments and synthesizes repository-level repair instances around these constraints. Each instance provides separate functional and constraint tests, together with non-compliant and gold patches, enabling explicit separation between issue resolution capability and review constraint compliance. We construct SWE-Gate with 303 repository-level repair instances spanning 75 open-source Python repositories across diverse software domains. Experiments with four LLM backends spanning different capability levels under a common coding-agent scaffold reveal a substantial gap between functional success and success under the complete repair specification: among 644 repairs that pass the functional tests, 221 fail to satisfy the provided review constraints. These findings show that functional-only evaluation overestimates agents' ability to satisfy the full requirements of repository-level repair tasks. The replication package including code, data, and experimental results is available at https://github.com/DeepSoftwareAnalytics/SWE-Gate.
Read the full abstract

All authors Xin He, Yanlin Wang, Mingwei Liu, Jiachi Chen, Hongyu Zhang, Guanbin Li

Artificial Intelligence

From Deceptive Outputs to Deceptive Mechanisms: A Causal Framework for Language-Model Deception Research

Yakov Pyotr Shkolnikov

Research and news coverage of language-model deception increasingly attributes human-like mental-state concepts to language models. Such claims can blur the distinction between behavior that looks deceptive and a mechanism that is actually deceptive. We introduce a causal taxonomy separating prior commitment from retrospective report, model preference from realized output, false preference from sensitivity to the utility of misleading a recipient, and deceptive behavior from the provenance of the objective or strategy producing it. We test these distinctions in two open-weight model families. Across controlled guessing-game and stock-trading experiments, we find that deceptive-looking behavior can arise without the corresponding proposed mechanism, while other interventions provide direct evidence that recipient information state can causally affect deceptive preference. These results show that deceptive behavior can provide evidence for a deceptive mechanism. But even evidence for such a mechanism does not establish model agency in the deception.
Read the full abstract

Data Structures and Algorithms · Cross-listed from quant-ph

Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography

Matthias C. Caro, Natalie McHugh and Sergii Strelchuk

Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error $\epsilon$ of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.
Read the full abstract

Discrete Mathematics

Minimizing the makespan in job shop scheduling under conflict graph constraints

Nour Elhouda Tellache and Abdenour Azerine

We study the job shop scheduling problem with a conflict graph, in which adjacent jobs cannot be processed simultaneously on different machines, with the objective of minimizing the makespan. We establish a polynomial equivalence with a resource-constrained job shop problem having unit-capacity resources and binary resource requirements The problem is strongly NP-hard even on two machines with unit-time operations. For this setting, we derive an optimal-makespan formula and a linear-time algorithm when the conflict graph is a cluster graph, given the clique partition. We also develop a polynomial-time $4/3$-approximation algorithm for arbitrary conflict graphs on two machines when each job has exactly two unit-time operations. For the general problem, we propose four mixed-integer linear formulations, lower bounds, and a genetic algorithm with active, non-delay, and hybrid decoding procedures. Computational experiments on instances derived from the Lawrence and Taillard benchmarks and on randomly generated generalized job shop instances evaluate the proposed methods and show that the genetic algorithm generally improves on constructive heuristics.
Read the full abstract

Computational Complexity · Cross-listed from quant-ph

Vanilla Exact Synthesis of CNOT Circuits is NP-hard

Chenjian Li and Ji Guan

Exact CNOT synthesis seeks a minimum-size circuit implementing a given invertible binary linear transformation. We study its vanilla formulation: synthesis from the identity on fixed labeled qubits, without ancillas and with all-to-all connectivity. We prove that this problem is NP-hard and that its bounded decision version is NP-complete. Hardness persists even for unitriangular targets that are low-rank perturbations of the identity and under near-linear gate budgets. Our proof gives a polynomial-time reduction from the NP-complete Hamiltonian path problem on grid graphs. A unary hypercube embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over $\mathrm{GL}(n,2)$ with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.
Read the full abstract

Cryptography and Security

SENTINEL-RL: Offloading Topological Reasoning from LLM Agents in the Security Operations Center

Uday Vallabhaneni, Cassie L. Cagwin and David J. Wild

Large language model (LLM) agents are increasingly proposed as autonomous SOC analysts, but two limitations make them unreliable at enterprise scale: a finite context window cannot hold a multi-thousand-host authentication graph, and free-form generation offers no guarantee that a recommended containment action is consistent with the topology it operates on. We present Sentinel-RL, an agentic-SOC architecture that decouples topological reasoning from semantic reasoning: a heterogeneous graph attention encoder summarizes the live authentication subgraph into a fixed-dimensional state, a Proximal Policy Optimization (PPO) policy maps this state to a constrained set of investigative actions, and an LLM agent loop is restricted to consuming the policy's recommendations and producing analyst-readable narratives gated by a critic. We instantiate the system on the LANL Comprehensive, Multi-Source Cyber-Security Events dataset and the Indiana University Quartz HPC cluster, reporting four results: (i) a two-phase CREATE ingestion pattern loads a 24M-edge authentication subgraph into Neo4j in 14.2 minutes on a single 32-core node, roughly 24x faster than the canonical MERGE-based pipeline; (ii) a sliding-window alert engine reliably trips a 25-event/10-second threshold in <=2.5 s across 50 trials; (iii) PPO training over 200 iterations converges to a mean episodic return of 8.74+/-0.31, with held-out precision of 0.91 and recall of 0.87 on labeled red-team events; and (iv) the integrated containment loop completes a full detect-investigate-recommend-human-approve cycle in a median of 6.3 s. We contribute a reusable engineering pattern (the hot-node deadlock workaround), a portable HPC deployment pattern (anchor-node co-location), and an enterprise-readiness analysis covering false-positive economics, reversibility guarantees, audit compliance, and the human-approval boundary.
Read the full abstract

Systems and Control

Formation Matrix and Energy-based Control of Multi-Agent Systems

Martín Crespo, Sergio Junco and Matías Nacusse

This paper presents an energy-based controller for a multiagent robotic system designed to achieve and maintain a specific formation while moving on a plane and avoiding collisions between agents. The controller emulates a network of elementary spring-damper modules connecting pairs of agents. This network, with its de-energized states representing the desired formation, determines the system's dynamics, which is fully encapsulated by a bond graph model. The modeling is further enhanced through the introduction of a formation matrix, using a graph-theoretic approach, that describes both the distances and relative velocities among the agents of the arrangement. This matrix mathematically represents the interconnection and energy-exchange structure of the bond graph, allowing us to put it in correspondence with the control-by-interconnection CbI-scheme of the IDA-PBC theory, facilitating the solution of the formation control problem within the port-Hamiltonian system framework. Furthermore, the paper presents leader-following and position-based formation control systems based on the CbI scheme, including a stability analysis of the corresponding closed-loop systems. The theoretical findings are validated through numerical simulations across various scenarios.
Read the full abstract

Computer Vision

Persistent Identity Preservation in Generative Image Models: A Benchmark and Evaluation System

Mengwei Ren, Xuaner Zhang and Zhihao Xia

Generative image models can now produce high-quality images, follow complex instructions, and support precise edits, but they still struggle to preserve who or what is being depicted. When generating or editing images of a specific subject, identity may drift as the pose, expression, appearance, viewpoint, or surrounding scene changes. Existing subject-driven methods make fundamentally different choices about where identity is represented: through the input context (GPT-Image-2, NB2), as trainable subject-specific model parameters (LoRA), or as a persistent identity layer (PHOTA IDENTITY) reusable across generations and edits. We systematically benchmark these paradigms across subject-driven generation, editing, restoration, and multi-subject settings, with tasks designed to increasingly stress identity preservation. Our results show that identity preservation remains a distinct limitation of current generative foundation models: strong image quality and instruction following do not necessarily imply strong identity fidelity, and identity degradation becomes more pronounced under iterative edits, small subject scales, severe image degradation, and multi-subject composition. Persistent identity substantially reduces this degradation across generation, editing, and restoration, consistently improving identity preservation when applied to different foundation models while maintaining comparable instruction adherence and perceptual image quality. These results suggest that identity does not simply emerge from increasingly capable generative models, but can instead be represented as persistent subject knowledge that is composed independently with the underlying generative model.
Read the full abstract

Artificial Intelligence

Terminal-Universe: Turning Agent Trajectories into Scalable Terminal Environments

Jie Wu, Zhenru Zhang, Beichen Zhang et al. (+11 more)

As terminal-based code agents become prevalent, agent trajectories have accumulated at scale, while realistic, executable environments remain scarce. However, environments are what agent post-training actually requires: each can be re-queried into many verifiable tasks and provides execution feedback, whereas a trajectory is a single frozen demonstration. Rather than generating environments from scratch, we observe that the tool-execution history in existing trajectories exposes the structure and contents of the environments in which they ran, making it possible to reconstruct those environments from the trajectories themselves. Thus, we introduce Terminal-Universe, a framework which turns each trajectory into a reusable environment and explores it for synthesizing new tasks and continued interactions. Specifically, Terminal-Universe replays the file operations recorded in a trajectory to restore each file before the agent modified it, yielding a partial workspace; a completion agent then supplies the missing files and dependencies. On this recovered workspace, we both reconstruct the original intent task and synthesize entirely new ones. Besides, we also scale the tasks along two complementary axes: breadth and depth. For breadth, we mine directional dependency relations between related environments and synthesize cross-workspace queries spanning multiple codebases, as developers routinely do in real-world development. For depth, we extend the initial single-turn query into a multi-round session that captures iterative user feedback and requirement refinement via a user agent. Applied to public terminal agent trajectories, Terminal-Universe produces 37.3k task-sufficient environments. Supervised fine-tuning of Qwen3.5-27B on this corpus improves single-round performance on Terminal-Bench 2.1 by 11.9 points and multi-round performance on EvoCode-Bench v2 MT@4 by 13.8 points.
Read the full abstract

All authors Jie Wu, Zhenru Zhang, Beichen Zhang, Xuwu Wang, Yuhui Su, Mouxiang Chen, Peng Wang, Zhihai Wang, Que Shen, Hao Zhou, An Yang, Fei Huang, Yujiu Yang, Dayiheng Liu

Machine Learning

A Low-Cost, Open Platform for End-to-End Autonomous Driving on a Miniature Ackermann Vehicle

Gustavo Claudio Karl Couto, Eric Aislan Antonelo and Gabriel George Zipperer

This paper presents a low-cost, open experimental platform for research in end-to-end autonomous driving with miniature Ackermann vehicles. The platform combines a physical vehicle, a printed urban track, data collection tools, trajectory registration, and a Webots digital twin, enabling controlled experiments that connect simulation-based autonomous-driving methods to real-world execution. As a first baseline, we implement command-conditioned behavior cloning, in which a neural policy receives an on-board camera image and a high-level navigation command and outputs steering and speed. The system is evaluated both on the physical vehicle and in simulation. In real closed-loop experiments, the learned policy follows lanes and executes commanded turns, reaching a mean cross-track error of 6.1 cm with respect to the reference route, close to the 4.7 cm observed in human demonstrations. In the digital twin, camera field of view has a strong effect on performance, reducing the mean cross-track error from 35.6 to 3.3 cm when widened from 58 to 120 degrees. Using the digital twin to generate synthetic driving data and a learned sim-to-real image translator to reduce the appearance gap, we further show that a higher-capacity policy trained on this synthetic data combined with real demonstrations is the only configuration that completes all four track routes in closed loop, whereas the compact baseline and the same network trained on real data alone complete fewer. These results establish the open platform as a practical testbed for sim-to-real studies and provide an initial command-conditioned imitation-learning baseline; we release it to support reproducible research.
Read the full abstract

Artificial Intelligence

Efficient Test-Time Adaptation through Human-AI Interaction

Zora Zhiruo Wang, Apurva Gandhi, Rulin Shao et al. (+22 more)

AI agents are trained on population-scale data to encode broad capabilities spanning those of many practitioners. Yet the artifacts they produce rarely meet the personal bar professionals need to stake their reputation on. On realistic, open-ended tasks where success criteria are heterogeneous and insufficiently documented, individual expertise lives precisely in the elevation and departure from the average. In practice, iterative human-agent interaction surfaces criteria that users cannot fully specify up front, yet apply repeatedly across tasks. We argue this cross-session interaction data is a rich, underused signal for closing the gap to individual expertise. In this work, we propose test-time adaptation through human-agent interaction (TAHI), which integrates these signals into agent context and weights, and crystallizes each user's training and evaluation criteria via an evolving rubric module. We adapt agents to 30 individuals in two high-utility domains, writing and visual creation, on a total of 600 tasks. Our agents improve solo task success by 4.5-20.9% within only tens of tasks. Meanwhile, our evolving rubric module serves as a scalable annotation tool, creating evaluation rubrics that catch 16.0-22.3% more failures than those from LMs or humans alone. While agents are adapted towards individuals, we show these personalized agents also produce improvements in success of up to 8.8% that generalize across users.
Read the full abstract

All authors Zora Zhiruo Wang, Apurva Gandhi, Rulin Shao, Aspen Chen, Jonas Mueller, Zhiqi Liang, Jett Chen, Michael Ryan, Qianou Ma, Luxi He, Zhoujun Cheng, Andre He, Seungone Kim, Jiayi Geng, Mingqian Zheng, Weiwei Sun, Zheyuan Zhang, Xinran Zhao, Yike Wang, Abe Hou, Liwei Jiang, Pang Wei Koh, Diyi Yang, Graham Neubig, Daniel Fried

Artificial Intelligence

The Natural Language Interaction Protocol and Standard for AI Agents

Luyi Xing, Rasit Onur Topaloglu, Ranjan Sinha et al. (+9 more)

AI agents are increasingly being developed and deployed across organizations using heterogeneous agent-development frameworks, AI models, tool interfaces, protocols, and execution environments. To realize their potential social and business impact, these agents must be able to interoperate through a common communication protocol. The Natural Language Interaction Protocol (NLIP), developed by researchers and practitioners across companies and universities and standardized by Ecma International, addresses this need by defining a standards-based application-layer protocol for AI-agent interaction. NLIP provides a lightweight semantic message envelope that can be carried over existing transports such as HTTP/HTTPS, WebSocket, and AMQP, while allowing NLIP-aware agents and gateways to adapt between clients, agents, local context stores, ontologies, tools, enterprise services, and heterogeneous underlying protocols. This paper presents the motivation and design rationale of NLIP, its message model and transport bindings, security-by-design considerations, reference implementation, representative applications, adoption signals, and relationship to emerging agent protocols such as MCP and A2A.
Read the full abstract

All authors Luyi Xing, Rasit Onur Topaloglu, Ranjan Sinha, Abhay Ratnaparkhi, Samuel Ndichu, Christopher Nguyen, Anindita Das, Tom Sheffler, Mohamed Rahouti, Zichuan Li, Xiaojing Liao, Sanjay Aiyagari

Machine Learning

Prospective Coding Improves Learning in Deep Continuous-Time Recurrent Networks

Shivang Rawat, Mirko Morello, Flaviano Morone et al. (+1 more)

Temporal integration gives continuous-time recurrent networks memory, but in deep stacks it also delays bottom-up signals and attenuates top-down errors. We compensate for this delay by making each layer's bottom-up input prospective, and we develop Recursive Quadrature Filters (RQFs), biologically motivated temporal band-pass filters that are a special case of diagonal state-space models (SSMs). Starting from an energy model, we derive the RQF dynamics and show that each RQF is a band-pass filter whose learnable parameters control its tuning frequency and bandwidth. We then make each layer's bottom-up input prospective using a parameter-free two-tap update that leaves the recurrent transition and parallel scan unchanged. We extend this correction to general diagonal SSMs and show that it mitigates depth-dependent gradient attenuation when temporal gradients are truncated, i.e., spatial-only backpropagation. We evaluate the performance of RQFs, S5, and ORGaNICs (a nonlinear gated RNN with built-in attentional modulation and recurrent normalization) trained using full backpropagation through time (BPTT) and spatial-only backpropagation. Under full BPTT, the prospective variants of these models match or outperform their non-prospective controls in every configuration. A non-residual width-32 six-layer RQF achieves 96.09% accuracy on raw-audio Speech Commands with 31.9k parameters; a width-64 six-layer RQF achieves 83.36% on the 16,384-step Path-X task. We also introduce selective RQFs (sRQFs), which make each filter's input gain and, optionally, its bandwidth and tuning frequency input-dependent while retaining the parallel scan. With the input gain alone, the same six-layer model achieves 86.31% on Path-X; with all three input-dependent, a four-layer prospective sRQF solves Selective Copying (99.83%).
Read the full abstract

All authors Shivang Rawat, Mirko Morello, Flaviano Morone, David J. Heeger

Computer Vision

Beyond Retrieval: Progressive Latent Memory Evolution for Streaming Video Understanding

Hongyu Qu, Guangming Yao, Ling Xing et al. (+7 more)

Streaming video understanding requires multimodal large language models (MLLMs) to process continuous visual inputs and respond to user queries under strict causality and bounded memory. Existing approaches typically compress historical observations into an external memory bank and retrieve query-relevant evidence as additional visual context. Though effective, this store-and-retrieve paradigm keeps historical evidence as external visual context, preventing it from being internalized into a compact, evolving latent memory that can continuously guide streaming reasoning. To bridge this gap, we introduce LatentStream, a progressive latent working memory framework that shifts streaming memory from store-and-retrieve to retrieve-and-internalize. Specifically, LatentStream comprises three coordinated components. First, Query-agnostic Hierarchical Streaming Memory organizes visual history into short-, mid-, and long-term levels under a fixed memory budget through Jenks-guided adaptive consolidation. Once a query arrives, Hierarchical Latent Memory Evolution equips groups of latent memory tokens with progressively expanding memory receptive fields, enabling them to iteratively retrieve historical evidence from their corresponding scopes and internalize it into a compact, fixed-length latent memory. Finally, Progressive Confidence-guided Latent Memory Optimization constructs a hierarchical progression reward from group-wise predictive entropy and jointly refines the latent memory tokens and retrieved evidence, encouraging increasingly confident streaming reasoning. Extensive experiments demonstrate that LatentStream achieves new state-of-the-art results on existing online and offline video benchmarks.
Read the full abstract

All authors Hongyu Qu, Guangming Yao, Ling Xing, Xiaobin Hu, Rongxing Ding, Guibin Zhang, Fan Zhang, Yi Yuan, Xiangbo Shu, Shuicheng Yan

Artificial Intelligence

Environment Evolution for Terminal Agents

Zhiyuan Fan, Tinghao Yu, Yuanjun Cai et al. (+9 more)

Scaling interactive and verifiable environments is critical for training terminal agents. As frontier models become more capable, environments synthesized from scratch become less challenging and thus provide limited learning signals. Recent co-evolution methods iteratively synthesize environments near the model's learnable frontier based on weaknesses exposed during rollouts. However, their dependence on on-policy rollouts limits generalization and the continuous provision of learning signals as the model becomes stronger. In this paper, we propose environment evolution, which incrementally increases environment difficulty off-policy and schedules the evolved environments generation by generation during training to provide continuous learning signals. We derive three evolution directions that influence environment difficulty from the multi-turn learning objective and then implement evolution along these directions through a loop-engineered multi-agent harness. Quantitative rollout experiments with Hy4 preview, Claude Opus 5, and GPT-5.6 Sol show that environment evolution consistently produces more difficult environments. We validate its effectiveness on Qwen3.6-27B and Qwen3.6-35B-A3B through simple long-horizon RL training, improving their performance by 14.4 and 18.0 percentage points on Terminal-Bench 2.1, respectively.
Read the full abstract

All authors Zhiyuan Fan, Tinghao Yu, Yuanjun Cai, Jiang Zhou, Jiangtao Guan, Jincheng Liu, Yun Yang, Dingxin Hu, Zhuo Han, Xing Wu, Feng Zhang, Lilin Wang

Artificial Intelligence

Epistemic Warrant for LLM Recommendations: Characterizing the Basis for Reliance When Ground Truth Is Unavailable

Shai Vardi and João Sedoc

Large language models are increasingly used to support organizational decisions. Despite their rapid and widespread adoption, users often lack a principled basis for assessing whether to rely on a specific recommendation. We introduce epistemic warrant, a decision-level construct that characterizes the scope over which a recommendation is supported. We operationalize this construct through a reliance certificate that uses behavioral evidence from four tiers of tests to assess a recommendation's underlying warrant and assign it to a warrant category. We assess this operationalization using complementary forms of construct-validity evidence, including transformation validity, known-groups tests, independent human consensus, discriminant analyses, and robustness across models and alternative implementations. The results show that the certificate behaves in theoretically expected ways: its transformations instantiate their intended relationships, certificate assignments increase across groups prespecified to represent increasing levels of warrant, and stronger assigned warrant is associated with greater independent human consensus. Certificate assignments also capture information beyond verbalized confidence and are not readily explained by decision difficulty. The main conclusions remain robust across models and operationalizations. These findings support the reliance certificate as an operationalization of epistemic warrant for assessing the scope of support for a particular LLM recommendation when ground truth is unavailable.
Read the full abstract

Computers and Society

Decreasing Digital Distraction in College Students: Associated Online Learning Strategies Identified by Unsupervised Data Mining Approaches

Hui Shi, Ran Bi, Xi Lin et al. (+1 more)

The proliferation of digital tools in education offers numerous benefits but also introduces significant challenges, notably digital distractions that hinder academic performance, especially in online learning contexts. This study employed unsupervised data mining techniques, specifically association rule mining and clustering analysis, to identify effective learning strategies associated with lower levels of digital distractions among college students. Data from 530 participants revealed that self-regulated learning strategies (i.e., goal setting, environment structuring, and time management) co-occurred most consistently with lower digital distractions. Additionally, learner-instructor and learner-content engagement strategies, as well as technical competencies, also tended to appear in the same profiles as lower distraction. Interestingly, reliance on peer help-seeking and learner-learner engagement strategies appeared less often in those lower distraction profiles. These findings offer actionable implications for educators to design targeted interventions that foster focused and productive online learning environments.
Read the full abstract

All authors Hui Shi, Ran Bi, Xi Lin, Yan Dai

Numerical Analysis · Cross-listed from math.ST

Bernstein–von Mises theorems for Bayesian probabilistic numerics

Sascha Gaudlitz and Sven Wang

We study probabilistic numerical methods for solving nonlinear PDEs from a Bayesian nonparametric perspective. Given noisy evaluations at random collocation points, we place a truncated Gaussian series prior on the unknown solution and establish contraction at the minimax nonparametric rate, up to a logarithmic factor. Our main results give Gaussian approximations of the posterior in positive-order Sobolev spaces and, under suitable conditions, in the uniform topology. This contrasts with classical ill-posed inverse problems, where Bernstein–von Mises theorems typically require substantially weaker topologies. Here, the observation operator is differential rather than smoothing, and inversion of its linearisation gains regularity, making these strong-topology results possible. The posterior may be centred at either the posterior mean or the posterior mode. We further prove that the Gaussian Laplace approximation is asymptotically equivalent to the true posterior at a $\sqrt{N}$-scale.
Read the full abstract

Software Engineering

ATIBA: Grounded Integrity and Quality Checking for Research Papers

Veli Karakaya, Semih Çağlar, Yusuf Yiğit Korkmaz et al. (+1 more)

Checking a manuscript's reference integrity, its compliance with a target venue's specific submission rules, and its adherence to community reporting standards is manual, repetitive, and different for every venue so in practice it is done inconsistently or skipped. We present ATIBA, a tool that runs five grounded integrity and quality checks on a manuscript: a reference-integrity check that verifies each citation against bibliographic sources and flags retracted or unfindable references; a venue/track compliance check that derives submission criteria directly from a venue's own call-for-papers page and evaluates the manuscript against them, each verdict anchored to a verbatim quote from that page; an empirical-standards compliance check against the ACM SIGSOFT Empirical Standards, with a hallucination defence that discards any evidence quote it cannot locate verbatim in the manuscript; a multi-mode AI review (venue-specific, formal, and page-anchored annotation) powered by GPT-5.4 through Azure OpenAI; and a citation-suggestion feature that proposes candidate references for a manuscript and verifies each against bibliographic sources before it is shown to the user. All five checks are designed around the same principle: an LLM is only trusted to judge, never to invent the evidence it judges against. We evaluated ATIBA through a moderated user study with 13 non-author participants. Agreement across the six survey items ranged from 69% to 92%, with a mean of 85%, providing initial evidence of positive perceived usefulness across the evaluated workflows. These findings establish perceived usefulness; objective accuracy remains to be measured.
Read the full abstract

All authors Veli Karakaya, Semih Çağlar, Yusuf Yiğit Korkmaz, Eray Tüzün

Information Theory

Synchronization Strings over the Optimal Alphabet

Huibo Xu, Shi Fu, Youming Qiao et al. (+1 more)

Synchronization strings provide deterministic position labels for recovering coordinates after insertions and deletions. Haeupler and Shahrasbi introduced these objects, and subsequent work proved that four symbols suffice for some fixed parameter epsilon < 1, whereas two symbols cannot support arbitrarily long synchronization strings. We resolve the remaining ternary case: every length admits a ternary 2001/2002-synchronization string. Thus three is the exact minimum constant alphabet size. A computer-assisted refinement based on a larger 54-uniform family yields ternary epsilon-synchronization strings for every epsilon > 215/216. The previous four-symbol construction uses a ternary square-free backbone to exclude short repetitions and a fourth symbol to carry long-range synchronization marks. Our main technical contribution is a local-entropy transfer theorem: every square-free block-local source with a positive interval conditional min-entropy rate supports synchronization strings with a fixed gap. We instantiate this theorem using occurrence-wise branching in a Brinkhuis family. Every outcome remains ternary and square-free, while every long interval retains linear conditional min-entropy after all choices outside it are exposed. A deletion-ball estimate converts this entropy into an exponentially small probability of a near-complete common subsequence between adjacent intervals, and an asymmetric Lovasz Local Lemma enforces all interval constraints simultaneously. The same framework also yields exponentially many valid words, synchronization circles, and synchronization within a class of extremal square-free words. Adding constraints on distant intervals gives a Las Vegas construction in expected O(n^2 log^3(n+2)) time.
Read the full abstract

All authors Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao