论文检索

Optimization · Discrete and Combinatorial Optimization

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Danny Mittal

The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most $c$, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost $\mathcal{O}(n^{2-1/c} \log n)$.

Probabilistic Methods · Graphical Models

Leander Kurscheidt, Gabriele Masina, Roberto Sebastiani, Antonio Vergari

In many safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints, e.g., predicting the most likely trajectory that does not cross obstacles. These real-world constraints are rarely convex, nor the densities considered are (log-)concave. This makes computing this constrained maximum a posteriori (MAP) prediction in an efficient and reliable way extremely challenging. In this paper, we first investigate under which conditions we can perform constrained MAP inference over continuous variables exactly and efficiently and devise a scalable message-passing algorithm for this tractable fragment. Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions with numerical constrained optimization. We evaluate both methods on synthetic and real-world benchmarks, showing our structure aware approach outperforms constraint-agnostic baselines.

Probabilistic Methods · Graphical Models

Samo Hromadka, Kai Biegun, Lior Fox, James Heald, Maneesh Sahani

We address the challenge of uncovering systematic, and potentially controllable, dynamical structure underlying complex high-dimensional time series data. Existing generative and autoregressive models have difficulty telling systematic content apart from distractors, while contrastive methods struggle to learn accurate dynamics. To address these shortcomings, we develop the Recognition-Parametrized Gaussian State Space Model (RP-GSSM), a probabilistic framework that infers accurate latent dynamics without relying on a parametrized decoder. By eliminating explicit generative parameters, the model directs its entire representational capacity to encoding dynamically relevant state; and, being fully probabilistic, learns via maximum likelihood without auxiliary objectives or ad-hoc regularization. Combining the expressive power of a neural network encoder with exact inference under a jointly Gaussian prior allows the RP-GSSM to embed a broad class of intrinsically nonlinear dynamical systems. We show that the RP-GSSM recovers physically meaningful latent states from noisy video more faithfully than competing methods, more reliably identifies underlying controllable nonlinear dynamics, and remains substantially more robust to visual distractors.

Theory · Learning Theory

Eric Shen, Tony Wu, Mahbod Majid, Ankur Moitra

We study the task of learning the structure of a $d$-sparse Gaussian graphical model on $n$ variables from a single trajectory of Glauber dynamics. Beyond algorithmic considerations, many applications present temporally correlated observations rather than i.i.d. samples. Moreover, in the classical i.i.d. setting, polynomial-time structure learning from a sublinear in $n$ number of samples is suspected to be computationally hard without additional assumptions on the precision matrix. Motivated in part by this, we design the first polynomial-time algorithm that recovers the conditional-independence graph from a single Glauber trajectory, with a trajectory-length guarantee that does not depend on the mixing time. Technically, our algorithm has three components. First, we estimate the conditional variances and rescale the trajectory to reduce to the unit-diagonal case, without changing the underlying graph. Second, we design a local edge test that extracts adjacency information from short update windows by isolating pairwise influence. Third, we aggregate these local statistics using a robust median-based estimator, and prove accuracy despite contamination and temporal dependence arising from a single trajectory.

Social Aspects · Safety

Haowen Hu, Pengzhou Cheng, Zheng Wu, Lingzhong Dong, Gongshen Liu, Zhuosheng Zhang

Vision-language model (VLM) based graphical user interface (GUI) agents have shown strong interaction capabilities. However, they often behave unfaithfully, relying on memorized shortcuts rather than grounding actions in displayed screen evidence or user instructions. To address this, we propose **Faithful-Agent**, a faithfulness-first framework that reformulates GUI interaction to prioritize evidence groundedness and internal consistency. Faithful-Agent employs a two-stage pipeline: (i) a faithfulness-oriented SFT stage to instill abstainment behaviors under evidence perturbations; (ii) an RFT stage that further amplifies faithfulness by introducing the guided advantage estimator (GuAE), an anchor-based and variance-adaptive advantage tempering mechanism built upon GRPO. GuAE prevents advantage collapse in low-variance rollout groups under sparse GUI rewards, and with a thought-action consistency reward, Faithful-Agent (Stage II) elevates the Trap SR from 13.88\% to 80.21\% relative to the baseline, while preserving robust general instruction-following performance.

Probabilistic Methods · Graphical Models

José Á. Sánchez Gómez, Weibin Mo, Junlong Zhao, Yufeng Liu

The Gaussian graphical model (GGM) is a useful tool to represent relationships of conditional dependence among variables. In many real-world applications, datasets often contain multiple related sub-populations, whose associated GGMs may have common structure, as well as large structural differences. In such cases, it is useful to recover common hub variables, which are the highly connected variables in the GGMs of all sub-populations. In this paper, we propose the Joint Inverse Components for Hub Detection (JIC-HD) method to recover the common hubs across multiple GGMs without the need to estimate all subpopulation GGMs. To this end, we introduce joint minimax eigenspaces, and show that these can be leveraged for the recovery of common hubs. We establish theoretical guarantees for the recovery of common hubs. Additionally, our numerical simulation studies confirm superior performance of our JIC-HD in detecting common hubs compared to the existing methods in the literature. Our method is especially advantageous when the multiple GGMs have both common and individual hubs across sub-populations. Finally, we analyze cancer gene-expression datasets and identify biologically meaningful common hub genes across cancer subtypes.

General Machine Learning · Causality

Alek Fröhlich, Vladimir Kostic, Karim Lounici, Daniel Rodrigues Perazzo, Daniel Tiezzi, Massimiliano Pontil

Conditional independence (CI) is central to causal inference, feature selection, and graphical modeling, yet it is untestable in many settings without additional assumptions. Existing CI tests often rely on restrictive structural conditions, limiting their validity. Kernel methods using partial covariance operators offer a more principled approach but suffer from limited adaptivity, slow convergence, and poor scalability. In this work, we explore whether representation learning can help address these limitations. Specifically, we focus on representations derived from the singular value decomposition of partial covariance operators and use them to construct a simple test statistic. We also introduce a bi-level contrastive algorithm to learn these representations. Our theory links representation learning error to test performance and establishes asymptotic validity and power guarantees. Experiments on real and synthetic data suggest that this approach offers a principled and statistically grounded path toward scalable CI testing, bridging kernel-based theory with modern representation learning.

Applications · Computer Vision

Yijia Guan, Jianhua Sun

Computer-Aided Design (CAD) generation is typically formulated as a sequence modeling task over parametric tokens. Recent studies introduce visual information through additional visual inputs or rendering of the final generated programs. However, these methods provide no intermediate visual feedback, hindering the association of individual tokens with their geometric effects. In this work, we propose an Argument-induced 3D Point Loss (A3PL) that maps argument tokens to corresponding 3D points, enabling dense token-wise geometric supervision. To reduce learning complexity and invalid sequences, we further introduce a Grammar-constrained Operator (GCO) that leverages the structured nature of CAD programs to regulate sequence generation. We evaluate our approach on five CAD generation tasks with diverse input modalities, including text, Scalable Vector Graphics (SVG) sketches, point clouds, and CAD sequences. Our approach improves generation accuracy and program validity across different input modalities. Code and dataset are made publicly available.

Deep Learning · Everything Else

Yeonsang Shin, Insoo Kim, Bongkeun Kim, Keonwoo Bae, Bohyung Han

Transformer-based autoregressive models excel in data generation but are inherently constrained by their reliance on discretized tokens, which limits their ability to represent continuous values with high precision. We analyze the scalability limitations of existing discretization-based approaches for generating hybrid discrete-continuous sequences, particularly in high-precision domains such as logos, layouts, and semiconductor circuit designs, where precision loss potentially leads to visual artifacts, aesthetic degradation, and even functional failure. To address the challenge, we propose a novel unified framework that jointly models discrete and continuous values for variable-length sequences. Our approach employs a hybrid approach that combines categorical prediction for discrete values with diffusion-based modeling for continuous values, incorporating two key technical components: an end-of-sequence (EOS) logit adjustment mechanism that uses an MLP to dynamically adjust EOS token logits based on sequence context, and a length regularization term integrated into the loss function. Additionally, we present ContLayNet, a large-scale benchmark comprising 334K high-precision semiconductor layout samples with specialized evaluation metrics that capture functional correctness, where precision errors significantly impact performance. Experiments on semiconductor layouts (ContLayNet), graphic layouts, and SVGs demonstrate that our approach achieves higher-fidelity hybrid vector representations than discretization-based and fixed-schema baselines, while scaling to high-precision generation across multiple domains.

Deep Learning · Large Language Models

Weimin Xiong, Hao Tian, Shuhao Gu, Bowen Ye, Zihao Yue, Lei Li, Feifan Song, Sujian Li

Recent advances in multimodal large language models have driven growing interest in graphical user interface (GUI) agents, yet their generalization remains constrained by the scarcity of large-scale training data spanning diverse real-world applications. Existing datasets rely heavily on costly manual annotations and are typically confined to narrow domains. To address this challenge, we propose Video2GUI, a fully automated framework that extracts grounded GUI interaction trajectories directly from unlabeled Internet videos. Video2GUI employs a coarse-to-fine filtering strategy to identify high-quality GUI tutorial videos and convert them into structured agent trajectories. Applying this pipeline to 500 million video metadata entries, we construct WildGUI, a large-scale dataset containing 12 million interaction trajectories spanning over 1,500 applications and websites. Pre-training Qwen2.5-VL and Mimo-VL on WildGUI yields consistent improvements of 5–20\% across multiple GUI grounding and action benchmarks, matching or surpassing state-of-the-art performance. We will release both the WildGUI dataset and the Video2GUI pipeline to support future research of GUI agents.

Deep Learning · Large Language Models

Yiran Wu, Jiale Liu, Jieyu Zhang, Yaolun Zhang, Shilong Liu, Chi Wang, Mengdi Wang, Huazheng Wang, Qingyun Wu

Large language models (LLMs) are increasingly deployed as digital agents that perform multi-step digital work on a computer, but the environments in which they operate remain fragmented and task-specific. Our position is that digital agents need Agent-Native Computer: interfaces that expose system capabilities through compositional observation and action spaces aligned with LLM strengths. To ground this position, we showcase AgentVM, an environment running on top of a modern operating system, which integrates Graphical User Interface (GUI)-based and text-based interactions over a shared system state, and factors interaction into modular environment views. Through quantitative and qualitative analysis, we show that a unified agent-native computer is essential for building general-purpose digital agents.

Probabilistic Methods · Graphical Models

Mustafa Seddiqi, Tiberiu Popa, Marta Kersten-Oertel

Learning effective value heuristics for combinatorial search is difficult, as prior methods rely on surrogate supervision or costly downstream search to assess progress. We introduce a trajectory-aware probabilistic framework that models uncertainty in cost-to-go labels instead of treating them as fixed targets. Heuristic learning is cast as inference over state trajectories using an HMM-style model (Rabiner, 1989), where estimated depth-change dynamics define transitions and forward–backward inference yields soft supervision. To evaluate heuristic quality without search, we propose a large-scale local ranking metric that measures a model’s ability to order neighboring states. On the Rubik’s Cube, our approach consistently improves local ranking accuracy and downstream search performance under matched computational budgets.

Deep Learning · Large Language Models

Krishna Balasubramanian, Aleksandr Podkopaev, Shiva Kasiviswanathan

Large-scale AI evaluation increasingly relies on aggregating binary judgments from $K$ annotators, including LLMs used as judges. Most classical methods, e.g., Dawid-Skene or (weighted) majority voting, assume annotators are conditionally independent given the true label $Y\in\\{0,1\\}$, an assumption often violated by LLM judges due to shared data, architectures, prompts, and failure modes. Ignoring such dependencies can yield miscalibrated posteriors and even confidently incorrect predictions. We study label aggregation through a hierarchy of dependence-aware models based on Ising graphical models and latent factors. For class-dependent Ising models, the Bayes log-odds is generally quadratic in votes; for class-independent couplings, it reduces to a linear weighted vote with correlation-adjusted parameters. We present finite-$K$ examples showing that methods based on conditional independence can flip the Bayes label despite matching per-annotator marginals. We prove separation results demonstrating that these methods remain strictly suboptimal as the number of judges grows, incurring nonvanishing excess risk under latent factors. Finally, we evaluate the proposed method on three real-world datasets, demonstrating improved performance over the classical baselines.

Theory · Probabilistic Methods

Tom Yates, Yuzhou Cheng, Ignacio Alzugaray, Danyal Akarca, Pedro Mediano, Andrew Davison

Belief Propagation (BP) is a powerful algorithm for distributed inference in probabilistic graphical models, however it quickly becomes infeasible for practical compute and memory budgets. Many efficient, non-parametric forms of BP have been developed, but the most popular is Gaussian Belief Propagation (GBP), a variant that assumes all distributions are locally Gaussian. GBP is widely used due to its efficiency and empirically strong performance in applications like computer vision or sensor networks – even when modelling non-Gaussian problems. In this paper, we seek to provide a theoretical guarantee for when Gaussian approximations are valid in highly non-Gaussian, sparsely-connected factor graphs performing BP (common in Spatial AI). We leverage the Central Limit Theorem to prove mathematically that variables’ beliefs under BP converge to a Gaussian distribution in complex, loopy factor graphs obeying our 4 key assumptions. We then confirm experimentally that variable beliefs become increasingly Gaussian after just a few BP iterations in a stereo depth estimation task.

Applications · Computer Vision

Bin Lei, Nuo Xu, Ali Payani, Mingyi Hong, Chunhua Liao, Yu Cao, Caiwen Ding

Multimodal large language models (MLLMs) have markedly expanded the competence of graphical user-interface (GUI) systems, propelling them beyond controlled simulations into complex, real-world environments across diverse platforms. However, practical usefulness is still bounded by the reliability of visual grounding, i.e., mapping textual references to exact on-screen elements. This limitation prevents the system from accurately performing pointer-level actions such as clicking or dragging. To address it, we introduce GUI-Spotlight -- a model trained for image-grounded reasoning that dynamically invokes multiple specialized tools to iteratively narrow its focus to the relevant region of the screen, thereby substantially improving visual grounding accuracy. On the ScreenSpot-Pro benchmark, GUI-Spotlight trained with only 18.5K training samples achieves 52.8\% accuracy, surpassing V2P-7B (50.6\% with 9.6M training samples) and GTA-1-7B (50.1\% with 1.56M training samples).

Applications · Computer Vision

Yinuo Zhang, Zian Cheng, Ziya Zhao, Zongyu Li, Bingshuo Liu, Qingbin Liu, Junxian Cai, chen, Zhiying Tu, Dianhui Chu 等

Photoshop is a professional image editing software whose complex multi-level menus, fine-grained operations, and layer-based non-destructive editing pose substantial challenges for automated agents. Existing GUI benchmarks and methods primarily target web interfaces and short-horizon, low-complexity tasks, falling short in modeling the multi-step decision-making and semantic understanding required by professional graphic software. We introduce PSBench, the first benchmark specifically designed for image editing in Adobe Photoshop, consisting of 600 human-annotated tasks across three difficulty levels, with tasks drawn from official tutorials and popular real-world workflows. PSBench covers core functionalities such as canvas adjustment, layer manipulation, and filter application, and provides fine-grained evaluation metrics tailored to each task category. Our experiments show that even the state-of-the-art system, Agent S3, achieves a success rate of only 18.09\% on difficult tasks, indicating that GUI agents still face considerable challenges in operating complex professional software. Furthermore, human-in-the-loop evaluations reveal that MLLMs, when serving as interactive assistants, can significantly improve novice users’ task completion rates and reduce operation time.

Deep Learning · Foundation Models

Wonbong Jang, Shikun Liu, Soubhik Sanyal, Juan Perez, Kam Woh Ng, Sanskar Agrawal, Juan-Manuel Perez-Rua, Yiannis Douratsos, Tao Xiang

Can we bridge the gap between perceiving camera trajectories and rendering novel views within a single generative framework? Recovering camera parameters from images and rendering scenes from novel viewpoints are considered the forward and inverse problems in the field of computer vision and graphics. Previous approaches treat these problems in isolation, often failing when image coverage is sparse or camera poses are ambiguous. In this work, we propose Rays as Pixels, a specialized Video Diffusion Model (VDM) that learns a joint distribution of videos and camera trajectories. We represent cameras as dense ray pixels (raxels) and simultaneously denoise them alongside video frames using a novel Decoupled Self-Cross Attention. This joint formulation enables us to: i) generate a video from multiple input images following a defined camera trajectory, ii) perform novel view synthesis from sparse views (without necessarily requiring camera poses), and iii) predict the camera trajectory from a raw video. We evaluate our model on pose estimation, camera-controlled video generation and validate its self-consistency. Please reference supplementary material for more qualitative results.

Deep Learning · Everything Else

Woosung (Reiss) Koh, Sungjun Han, Segyu Lee, Se-Young Yun, Jay Shin

Mobile Graphical User Interface (GUI) World Models (WMs) offer a promising path for improving mobile GUI agent performance at train- and inference-time. However, current approaches face a critical trade-off: text-based WMs sacrifice visual fidelity, while the inability of visual WMs in precise text rendering led to their reliance on slow, complex pipelines dependent on numerous external models. We propose a novel paradigm: visual world modeling via renderable code generation, where a single Vision-Language Model (VLM) predicts the next GUI state as executable web code that renders to pixels, rather than generating pixels directly. This combines the strengths of both approaches: VLMs retain their linguistic priors for precise text rendering while their pre-training on structured web code enables high-fidelity visual generation. We introduce gWorld (8B, 32B), the first open-weight visual mobile GUI WMs built on this paradigm, along with a data generation framework (gWorld) that automatically synthesizes code-based training data. In extensive evaluation across 4 in- and 2 out-of-distribution benchmarks, gWorld sets a new pareto frontier in accuracy versus model size, outperforming 8 frontier open-weight models over 50.25x larger. Further analyses show that (1) scaling training data via gWorld yields meaningful gains, (2) each component of our pipeline improves data quality, and (3) stronger world modeling improves downstream mobile GUI policy performance.

General Machine Learning · Causality

Erik Jahn, Dominik Janzing

For many real-world systems, causal ground truth is difficult to obtain, making claims about causal effects hard to assess. We develop methods for evaluating collections of $\binom{n}{2}$ bivariate causal statements over a set of $n$ variables. In the setting of acyclic linear statements, any such collection can be extended to a unique multivariate causal model, but we argue that this induced model is implausible if it imposes substantial additional confounding to explain observed correlations. We introduce a compatibility score that quantifies this notion of plausibility, notably without relying on the faithfulness assumption. Additionally, we define an incompatibility score for purely graphical bivariate causal statements, based on global consistency constraints that are derived from acyclicity and faithfulness assumptions. We give theoretical and empirical evidence that both scores can successfully distinguish correct from incorrect causal statements in generic settings. Moreover, we demonstrate the practical applicability of our methods by analyzing causal claims made by large language models. Our work aims to provide a foundation for assessing the reliability of causal information derived from human experts or artificial intelligence in settings where alternative forms of validation are unavailable.

Applications · Computer Vision

Jingjing Liu, Ziye Huang, Zihao Cheng, Zeming Liu, Jiahong Wu, Yuhang Guo, Kehai Chen, Yunhong Wang, Haifeng Wang

While Graphical User Interface (GUI) agents have shown promising performance in automated device interaction, they primarily depend on static parametric knowledge from pre-training or instruction tuning. This reliance fundamentally limits their ability to handle long-tailed tasks that require explicit procedural knowledge absent from model parameters, often forcing agents to resort to inefficient and brittle trial-and-error exploration. To mitigate this limitation, we introduce Proactive Document-Guided Action for GUI agents in dynamic, open-web environments, a novel paradigm that mirrors human problem-solving by enabling agents to autonomously search for relevant documentation to resolve long-tailed tasks. To evaluate agents' capability in this paradigm, we propose DocOS, a benchmark designed to assess document-guided problem solving in fully interactive environments. DocOS requires agents to autonomously navigate a web browser, locate relevant online documentation, comprehend procedural instructions, and faithfully ground them into executable GUI actions. Extensive experiments reveal that progress is strictly constrained by dual bottlenecks: agents struggle to reliably locate relevant information during proactive search and frequently fail to faithfully ground retrieved instructions into precise actions, pointing toward document-guided interaction as a crucial pathway for enabling self-evolving GUI agents in dynamic environments.