跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文，不再错过。

覆盖计算机全学科，以 AI 为快捷入口。关注方向、作者和关键词，把发现变成持续的研究积累。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+2已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描：2026-11-08 08:12 · 全站最近入库：2026-11-08 06:02各信源进度 →

统计口径与数据新鲜度

统计 2026-11-07 08:28 — 2026-11-08 08:28（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-08 08:12最近发现新增版本：2026-11-08 06:02库内论文最新更新时间：2026-11-06 02:59

每分钟刷新已保存的数据。空检查不代表采集异常；新收录可能包含历史论文。AI 导读按新增版本计数。

17,100 已收录论文14,661 AI 相关4,057 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

时间范围跟随排序：版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常，查看状态 →

找到 17,100 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-08 08:11（北京时间）
版本更新 · v4arXiv:2603.16016

FlatLands: Indoor floormap completion from a single egocentric view

Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

原文摘要

A single egocentric image typically captures only a small portion of the floor, yet a complete metric traversability map of the surroundings would better serve applications such as indoor navigation. We introduce FlatLands, a dataset and benchmark for single-view indoor floor-map completion in metric bird's-eye view (BEV), evaluating eleven models: both deterministic and generative. FlatLands contain 270,575 observations from 17,656 scene records across six metric 3D datasets, with aligned observation, visibility, validity, and ground-truth maps and both in- and out-of-distribution protocols. We compare training-free, deterministic, ensemble, and generative methods on shared geometry-derived inputs and, without fine-tuning, on maps estimated from real egocentric RGB images. Our results show that predicting floor almost everywhere can achieve high IoU when most evaluated cells are floor, while generative sample sets outperform the best single-output model under a proper scoring rule and support safer risk-weighted planning. FlatLands establishes a rigorous testbed for evaluating both floor-map accuracy and how effectively alternative completions represent the ambiguity of unseen space.

cs.CV · cs.AI · cs.RO · eess.IV

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.17266

Kadison--Singer in Deterministic Polynomial Time

Ekene Ezeunala, Haotian Jiang

原文摘要

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

cs.DS · cs.DM · math.CO · math.FA

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2601.01075

Flow Equivariant World Models: Structured Memory for Dynamic Environments

Hansen Jin Lillemark, Benhao Huang, Fangneng Zhan, Yilun Du, Thomas Anderson Keller

原文摘要

Embodied systems experience the world as 'a symphony of flows': a combination of many continuous streams of sensory input coupled to self-motion, interwoven with the dynamics of external objects. These sensory streams and the underlying dynamics of the world obey smooth, time-parameterized symmetries which existing world models ignore. Without a memory that respects this structure, partial observability presents a major obstacle to existing methods: each observation reveals only a fraction of the world, while unobserved regions continue to evolve. In this work, we introduce Flow Equivariant World Modeling, a framework that leverages time-parameterized symmetries within a latent memory for stable and accurate dynamics prediction over long horizons. The latent memory shifts and transforms equivariantly with self-motion and inferred external object motion, keeping information about out-of-view regions aligned as time progresses. We demonstrate the advantage of this framework over state-of-the-art diffusion, memory-augmented, and recurrent world model architectures on 2D and 3D partially observed video world modeling benchmarks. More broadly, our results suggest that predictive representations become more powerful when they are organized in line with the temporal and dynamical structure of the world they model. Project page: https://flowequivariantworldmodels.github.io/

cs.LG · cs.AI · cs.CV

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04094

A Constant-Factor Approximation for Capacitated Facility Location with Outliers

Rajni Dabas

原文摘要

We give a deterministic polynomial-time $(60/11+\eps)$-approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities. The algorithm respects both capacities and the outlier budget. Its guarantee, approximately $5.455$, is close to the best known factor $5+\eps$ for capacitated facility location without outliers. The main ingredient is a local-search comparison for a common rejection penalty that retains the signed difference between the algorithm's and the comparator's rejection counts. Ordinary approximation guarantees for the penalty objective do not provide this comparison. We extend the exchange-forest accounting of Bansal, Garg, and Gupta \cite{BGG18} so that a nonnegative assignment remainder pays for rejection and cancels in the final bound. We then merge two penalty assignments whose served counts bracket the outlier quota. Grouping alternating paths by their terminal facility preserves capacities and shares opening costs. These ingredients give a $(20/3+\eps)$-approximation; starting each penalty run from the preceding solution improves the guarantee to $60/11+\eps$.

cs.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2604.02434

Compositional Neuro-Symbolic Reasoning

Anugyan Das, Omkar Ghugarkar, Vishvesh Bhat, Asad Aali

原文摘要

We study structured abstraction-based reasoning for the Abstraction and Reasoning Corpus (ARC) and compare its generalization to test-time approaches. Purely neural architectures lack reliable combinatorial generalization, while strictly symbolic systems struggle with perceptual grounding. We therefore propose a neuro-symbolic architecture that extracts object-level structure from grids, uses neural priors to propose candidate transformations from a fixed domain-specific language (DSL) of atomic patterns, and filters hypotheses using cross-example consistency checks. Instantiated as a compositional reasoning framework based on unit patterns inspired by human visual abstraction, the system augments large language models (LLMs) with object representations and transformation proposals. On ARC-AGI-2, it improves over the base solver LLM (Grok-4, 16.0%) to 24.4% on the public evaluation set, and to 30.8% when combined with ARC Lang Solver via a meta-classifier. These results support the claim that in the evaluated settings, allocating test-time compute to object abstraction, neural-guided transformation proposal, and consistency filtering can improve accuracy over unstructured sampling-based scaling without task-specific finetuning of the system. We open-source the code: (https://github.com/CoreThink-AI/arc-agi-2-reasoner).

cs.AI

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04093

VARP: A Visual Adaptive Rearrangement Planner for Non-Monotone Object Rearrangement Planning

Hanwen Ren, Meng Zheng, Zhongpai Gao, Anwesa Choudhuri, Benjamin Planche, Terrence Chen, Ziyan Wu

原文摘要

Object rearrangement planning in cluttered environments is often non-monotone, requiring objects to be temporarily relocated before reaching their final destinations. Although search-based planners can solve such tasks, they incur substantial computational cost and require expensive replanning when the environment changes. We propose the Visual Adaptive Rearrangement Planner (VARP), which learns non-monotone rearrangement directly from visual state representations generated from expert demonstrations. VARP predicts pick-and-place actions from the current and goal visual state representations, and incorporates an Action Refinement Strategy (ARS) to improve action feasibility and a Progress Enforcement Strategy (PES) to mitigate progress stagnation. By continuously updating actions from the latest visual state representations, VARP adapts online to disturbances without replanning from scratch or performing online combinatorial search. In challenging rearrangement benchmarks, VARP achieves a 98.3\% success rate with only 0.4 s planning time per task, 97.5\% success under execution-time disturbances, and 94.5\% under continuous severe disturbances, while generalizing effectively to unseen object counts. These results demonstrate that VARP provides a scalable and robust solution for non-monotone object rearrangement.

cs.RO

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.30701

From Tokens to Credits to Outcomes: Pricing AI Across Models, Applications, and Cloud Platforms

Pratik Gupta

原文摘要

Between 2023 and 2026, AI changed how software is priced. Traditional SaaS charged per seat because serving one more user cost almost nothing. Model inference has non-zero marginal cost, and usage varies by orders of magnitude across customers, producing prepaid credits, metered usage, hybrid seat-plus-usage models, and outcome pricing that supplement, and in rare cases replace, seat-based pricing. These pricing models have not been systematically characterized. This paper presents a source-traceable study of public pricing artifacts - pricing pages and documentation - across three cohorts: the full Forbes AI 50 (2026) as the AI-native core sample, cloud platforms selling AI services included by a documented rule, and a frozen purposive cohort of 9 distinctive designs. It contributes (1) a dataset coding each offering's pricing primitive and credit mechanics with dated primary sources, prepared for public release with the paper, (2) a taxonomy of the primitives in use and their distribution across cohorts, and (3) evidence-informed design requirements for automated, configurable billing platforms, including ledger state for credits, attribution pipelines for outcome pricing, and configuration support for high pricing-change velocity. Subscription with usage quota is the dominant observable model among AI-native companies (55% of observable AI-native rows; 45-61% under sensitivity analysis of hybrid boundary cases, 41-65% when product-line coding is also varied). 23 of the 52 AI-native rows publish no pricing. Hybrid products are better understood as compositions of packaging anchor, allowance mechanism, and billable unit than as mutually exclusive categories. The dataset is planned for release with the paper; my employer is excluded from the sample.

cs.SE

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04092

CHROMA-MILL: Joint Low-Light Enhancement and White Balance under Colored Illumination

Pol Riubrogent-Comas, David Serrano-Lozano, Maria Pilligua, Michael S. Brown, Ramon Baldrich, Javier Vazquez-Corral

原文摘要

Capturing an image in a low-light environment produces a weak, noisy sensor signal. Low-light image enhancement (LLIE) aims to restore it. Auto white balance (AWB) is also required for every image, and the same noisy signal degrades its ability to infer the scene illuminant. LLIE is typically performed first, followed by AWB, but this strategy remains largely unexamined because existing low-light datasets span a narrow range of illuminants and lack illuminant ground truth for evaluating AWB. We address this with CHROMA-MILL, a RAW dataset of 50 scenes captured with a DSLR and smartphone under four calibrated illuminants at eleven intensity levels. Because light is additive, we blend these captures in the linear RAW domain to synthesize physically valid illuminant mixtures with exact chromaticity ground truth. Benchmarking on this data, we find joint correction is best, and introduce CTI-Retinexformer, which supervises an illumination map, a chromaticity prediction, and an illumination-invariant scene embedding, outperforming the best cascade by 0.7 dB PSNR$_L$ and 1.1 $ΔE_{00}$.

cs.CV

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04091

Same Rule, Different Verdicts: Rubric Language and Clause Structure in LLM Judges for Korean Support Dialogues

Sangdo Han, Moonsoo Kim

原文摘要

Services that operate in Korean often write their evaluation rubrics in Korean and hand them to an LLM judge. We test whether a judge's verdict depends on the language of the rubric and on how a rubric item is phrased. We write 12 criteria for support dialogues in four clause structures (affirmative, negated, conditional, exception) such that two pairs of structures have the same meaning, and we give each item in Korean and in English. Six low-cost models from three providers, plus one reference model, judge 60 translated ESConv dialogues and 144 constructed boundary cases under every combination (51,744 requests across the seven models). The analysis plan was fixed and committed before data collection. Cross-provider agreement is lower with Korean rubrics than with English rubrics (Cohen's kappa 0.687 vs. 0.745; difference -0.058, 95% CI [-0.072,-0.045]). Disagreement concentrates in negated, conditional, and exception items (odds ratio 5.6 relative to affirmative items). A single model changes its verdict between two items with the same meaning in 11-15% of cases. Two hypotheses are not supported: models from the same provider do not agree more than models from different providers, and adding paired examples does not reduce the language gap. We measure consistency only; no human labels are used, and all materials were drafted by an LLM.

cs.CL

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04090

Swapping the Judge Changes the Ranking: A Preregistered Study of Cross-Provider Replication in LLM-Judged System Comparisons

Sangdo Han, Moonsoo Kim

原文摘要

Practitioners who compare systems with an LLM judge and have no human labels often check a conclusion by repeating it with a judge from another provider. We test how far that check can be trusted. In a preregistered study (with a disclosed post-registration reduction of the judge set), five judge models from three providers re-judged 4,000 Chatbot Arena battles (nine systems, 33 system pairs) that carry human votes, each in both response orders. Agreement with the human vote was low at the verdict level (median Cohen's kappa = 0.22), and system rankings did not survive a change of judge: Kendall's tau with the human ranking ranged from 0.17 to 0.89 (median 0.67), so the preregistered hypothesis that rankings remain stable was not supported. Conclusions replicated by two low-cost judges from different providers matched the human conclusion more often than single-judge conclusions (+0.10 precision), but the gain came from filtering out one poorly aligned judge, and replication involving that judge left a conclusion for only 35% of comparisons. Judges that agreed with humans reached a stable conclusion with no more verdicts than human votes required; the others failed to converge on 26-70% of system pairs at the sample sizes tested (up to 100 verdicts per pair). Disagreements with the human vote co-occurred across judges far more often than independence predicts, although a single human vote per battle cannot separate shared judge bias from voter noise.

cs.CL · cs.AI · cs.CY

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2605.05179

Estimating the expected output of wide random MLPs more efficiently than sampling

Wilson Wu, Victor Lecomte, Michael Winer, George Robinson, Jacob Hilton, Paul Christiano

原文摘要

By far the most common way to estimate an expected loss in machine learning is to draw samples, compute the loss on each one, and take the empirical average. However, sampling is not necessarily optimal. Given an MLP at initialization, we show how to estimate its expected output over Gaussian inputs without running samples through the network at all. Instead, we produce approximate representations of the distributions of activations at each layer, leveraging tools such as cumulants and Hermite expansions. We show both theoretically and empirically that for sufficiently wide networks, our estimator achieves a target mean squared error using substantially fewer FLOPs than Monte Carlo sampling. We find moreover that our methods perform particularly well at estimating the probabilities of rare events, and additionally demonstrate how they can be used for model training. Together, these findings suggest a path to producing models with a greatly reduced probability of catastrophic tail risks.

cs.LG · cond-mat.dis-nn · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2602.01518

Qrita: High-performance Top-k and Top-p Algorithm for GPUs using Pivot-based Truncation and Selection

Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

原文摘要

Despite their importance in model sampling, efficient implementation of Top-k and Top-p algorithms poses a significant challenge as model vocabularies grow with every new model release. Existing approaches often rely on sorting, which incurs significant computation and memory overhead on GPUs, or on stochastic approaches that alter the algorithm's output. In this work, we propose Qrita, an efficient Top-k and Top-p algorithm based on a pivot-based truncation and selection. Qrita leverages pivot-based search for both Top-k and Top-p with two key techniques: 1. Gaussian-based $σ$-truncation, which greatly reduces the search space of the vocabulary, and 2. Quaternary pivot search with duplication handling, which halves the number of pivot search iterations and guarantees deterministic output. We implement Qrita using Triton and evaluate its performance against the Top-k and Top-p kernels of high-performance LLM execution engines such as SGLang and FlashInfer, improving end-to-end serving throughput up to 1.4$\times$ with half the memory usage, while providing the same output of stable sort-based Top-k and Top-p algorithms. Qrita is now the default Triton Top-k and Top-p sampler of vLLM, and its implementation is available at https://github.com/vllm-project/vllm/blob/main/vllm/v1/sample/ops/topk_topp_triton.py.

cs.AI

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04087

ScienceVision: Can AI Observe and Reason Like a Scientist?

Tianyi Ma, Jing Gu, Haozhe Zhao, Liang Chen, Yunfan Zhang, Haijun Su, Jialong Wu, Le Xue 等 13 位作者

原文摘要

Scientific discovery builds on accurate observations interpreted through domain knowledge and reasoning. For scientific 3D data, this requires understanding structures and spatial relationships, from protein contacts to anatomical organization. Existing multimodal benchmarks largely evaluate text and 2D images, while scientific 3D evaluations vary in representations and protocols across disciplines, limiting cross-disciplinary comparison. To assess these foundational capabilities, we introduce ScienceVision, a cross-domain benchmark for scientific 3D understanding and reasoning through expert-level visual question answering (VQA). We construct 250 questions, with 50 each from Biology, Chemistry, Medical Imaging, Mechanical CAD, and Architecture, through a pipeline combining synthetic question generation with domain-expert review and annotation. Each task pairs a native 3D artifact with a scientific question, a specified response format, and a task-specific reference answer, requiring domain knowledge to be applied to geometric or topological evidence. We evaluate 12 models on the same questions in three settings: visual question answering with native 3D artifacts accessed through an agent harness's file and code-execution tools; the same workflow augmented with expert-inspired viewer inspection and measurement tools exposed through the Model Context Protocol (MCP); and visual question answering from prescribed rendered 2D images using an agent harness. All settings use the same task-specific deterministic final-answer scoring. The inspection environment supports view changes, target isolation, and slice inspection. In this main comparison, the best mean answer score is 0.53 out of 1. Mean scores in the native-artifact workflow without additional MCP tools exceed those in the rendered-image workflow for every model, by 17.2 percentage points on average.

cs.CV · cs.AI

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2606.26080

Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents

Changdae Oh, Wendi Li, Seongheon Park, Samuel Yeh, Tanwi Mallick, Sharon Li

原文摘要

Process reward models enable fine-grained, step-level evaluation of LLMs, yet building them for agentic settings remains prohibitively difficult: long-horizon interactions, irreversible actions, and stochastic environment feedback make both human annotation and Monte Carlo estimation infeasible at scale. In this work, we show that reinforcement learning (RL) post-training already provides the ingredients for effective step-level scoring, eliminating the need for dedicated reward model training altogether. Concretely, we derive an implicit advantage under a general stochastic Markov decision process, which we term progress advantage -- log-probability ratio between the RL-trained policy and its reference policy exactly recovers the optimal advantage function. This formulation makes the resulting signal annotation-free, domain-agnostic, and available as a byproduct of the standard RL post-training pipeline. We validate the effectiveness of the progress advantage across three different applications: test-time scaling, uncertainty quantification, and failure attribution on five benchmarks and four model families. Across all settings, it consistently outperforms confidence-based baselines and, despite requiring no task-specific training, surpasses dedicated trained reward models. We complement these results with deeper analyses on characteristics of progress advantage, offering practical guidance for adoption in real-world agentic systems.

cs.LG · cs.AI

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04086

Permitted but Unauthorized: Affordance-Induced Delegated-Scope Violations in Multi-Agent LLM Systems

Shravya Kanchi

原文摘要

Multi-agent LLM systems place several agents on shared infrastructure, where each agent holds permissions far broader than the task it is delegated -- so every agent is routinely permitted to act on a peer's resources it was never assigned. We ask: under competitive pressure, what determines whether an agent crosses from its delegated scope into a peer's resources, and can such crossings be enforced away? We study this across eight LLMs in two simulated environments -- a CI/CD release pipeline and a security-operations incident queue -- using a deterministic, no-model-in-the-loop detector over hash-chained, replay-verified logs. In a controlled 2x2x2 factorial over competitive incentive, candidate visibility, and payoff information (three models, n=52 per cell), we find that action representation, not permission, governs the behavior: no agent crosses when the peer action is unlisted, whereas listing it under competitive pressure with a stated payoff raises crossings sharply -- up to 52 of 52 episodes for Claude Sonnet 4.5. We also observe a model-dependent split: two newer models (Claude Sonnet 5.5 and Opus 5.5) refuse the identical attack in 0 of 100 episodes, where prior-generation models cross in 9 of 10. We then evaluate two defenses -- a deterministic reference monitor and a model-based pre-execution judge -- both block every crossing and, when the task is winnable, cut avoidable peer deadline misses from 15/40 and 14/40 to at most 1/40. But scope enforcement is not harm prevention: an agent can still set a peer back through an authorized action on its own resources -- misreporting its incident's severity -- which neither defense detects. Our results establish action representation, not permission alone, as a controllable driver of inter-agent scope violations, and show that enforcing delegated scope is distinct from preventing harm, motivating effect-aware authorization.

cs.CR

查看论文
arXiv ↗PDF ↗
版本更新 · v7arXiv:2605.14211

ASH: Agents that Self-Hone in Long-Horizon Worlds

Benjamin Schneider, Xavier Schneider, Victor Zhong, Sun Sun

原文摘要

Long-horizon visuomotor tasks remain a fundamental challenge in AI, as current methods rely on hand-engineered rewards or action-labeled demonstrations, neither of which scales. We introduce ASH, an agentic system that learns a long-horizon policy from unlabeled, noisy internet video, without reward shaping or expert annotation. ASH follows a self-improvement loop; when it gets stuck, ASH learns an Inverse Dynamics Model (IDM) from its own trajectories, and uses its IDM to extract supervision from relevant internet video. ASH uses unsupervised learning to identify key moments from large-scale internet video and retains them as long-term memory - allowing it to tackle long-horizon problems. We evaluate ASH on two complementary environments demanding multi-hour planning: Pokemon Emerald, a turn-based RPG, and The Legend of Zelda: The Minish Cap, a real-time action-adventure game. In both games, behavioral cloning, retrieval-augmented and zero-shot foundation-model baselines plateau, while ASH sustains progression across our 8-hour evaluation. ASH reaches an average of 11.2/12 milestones in Pokemon Emerald and 9.9/12 in Legend of Zelda, while the strongest baseline gets stuck in both environments at an average of 9.3/12 and 7.8/12 milestones, respectively. We demonstrate that self-improving agents are a scalable recipe for learning in long-horizon worlds. Our project page is https://toolbox-hq.github.io/ASH

cs.AI · cs.LG

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04085

Follow the Features: SAE Feature-Guided Data-Efficient Instruction-Tuning of Large Language Models

Ryan Swift, Konstantinos Psounis

原文摘要

Selecting small, effective instruction-tuning datasets requires identifying which aspects of the original data to retain. We introduce Follow the Features (FtF), a data-selection method that uses sparse autoencoder (SAE) features to characterize training data and guide subset construction. FtF ranks features using dataset-level activation statistics, scores samples by their expression of highly ranked features, and incorporates feature resampling to encourage diversity. The LLM-SAE pair used for selection is independent of the model being fine-tuned, enabling reuse across target models. We evaluate FtF on two model-dataset settings at a training budget of 100 samples with a fixed sequence length of 256 tokens. FtF achieves performance competitive with GRAPE and S2L, with relative rankings varying across settings. On Qwen 3 8B trained on Alpaca, FtF exceeds full-dataset training by 1.59 percentage points in the harmonic mean of an AlpacaEval-based win rate and Open LLM Leaderboard performance, although full-dataset training retains a higher Leaderboard score. These results support SAE feature statistics as a useful signal for data-efficient instruction tuning.

cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.16025

QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators

Édouard Bonnet, Yeonsu Chang

原文摘要

A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and polygons [Adamaszek, Har-Peled, and Wiese, JACM 2019], or equivalently for packing connected subgraphs of a planar graph [Pilipczuk, van Leeuwen, and Wiese, Algorithmica 2020]. It also generalizes the QPTAS for MWIS on hereditary classes with strongly sublinear separators measured in vertices [Dvořák, EJC 2018; Dvořák and Lahiri, ESA 2021], as well as the QPTASes for graphs excluding specific induced minors [Chudnovsky et al., arXiv 2025; Bonnet et al., SWAT 2026; Czyżewska et al., arXiv 2026].

cs.DS · cs.DM · cs.LO · math.CO

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2502.18779

Towards Optimal Multi-draft Speculative Decoding

Zhengmian Hu, Tong Zheng, Vignesh Viswanathan, Ziyi Chen, Ryan A. Rossi, Yihan Wu, Dinesh Manocha, Heng Huang

原文摘要

Large Language Models (LLMs) have become an indispensable part of natural language processing tasks. However, autoregressive sampling has become an efficiency bottleneck. Multi-Draft Speculative Decoding (MDSD) is a recent approach where, when generating each token, a small draft model generates multiple drafts, and the target LLM verifies them in parallel, ensuring that the final output conforms to the target model distribution. The two main design choices in MDSD are the draft sampling method and the verification algorithm. For a fixed draft sampling method, the optimal acceptance rate is a solution to an optimal transport problem, but the complexity of this problem makes it difficult to solve for the optimal acceptance rate and measure the gap between existing verification algorithms and the theoretical upper bound. This paper discusses the dual of the optimal transport problem, providing a way to efficiently compute the optimal acceptance rate. For the first time, we measure the theoretical upper bound of MDSD efficiency for vocabulary sizes in the thousands and quantify the gap between existing verification algorithms and this bound. We also compare different draft sampling methods based on their optimal acceptance rates. Our results show that the draft sampling method strongly influences the optimal acceptance rate, with sampling without replacement outperforming sampling with replacement. Additionally, existing verification algorithms do not reach the theoretical upper bound for both without replacement and with replacement sampling. Our findings suggest that carefully designed draft sampling methods can potentially improve the optimal acceptance rate and enable the development of verification algorithms that closely match the theoretical upper bound.

cs.CL · cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04084

From Visual Matching to Textual Conditioning: Cross-Domain Few-Shot Segmentation via Reference Inversion

Jiahao Nie, Yun Xing, Wenbin An, Qixin Zhang, Yap-Peng Tan, Alex C. Kot, Shijian Lu

原文摘要

Cross-Domain Few-Shot Segmentation (CD-FSS) aims to segment objects from unseen domains using only a few annotated references. Recent Segment Anything Model (SAM)-based methods have advanced CD-FSS, yet their reference-target visual matching is highly sensitive to target appearance variations. SAM3 introduces text-conditioned segmentation, enabling natural-language descriptions to guide segmentation across target images, but directly using the category name as the condition still yields unstable performance under severe domain shifts. We propose Reference Inversion for SAM3 (RI-SAM3) that leverages SAM3's large-scale vision-language pre-training to learn suitable textual tokens for each target category. RI-SAM3 comprises three core designs: (i) Bi-level Reference Inversion that learns complementary tokens before and after the frozen text encoder: the former remain anchored in SAM3's text space while the latter represent the category more flexibly; (ii) Layer-adaptive Textual Conditioning combines these tokens differently as object queries evolve across decoder layers; and (iii) Presence-aware Confidence Supervision that jointly supervises query confidence and target presence for reliable predictions. With SAM3 frozen, RI-SAM3 optimizes around 12K parameters only per category and it efficiently segments each target in a single forward pass with reusable textual conditioning without per-sample reference-target visual matching. Extensive experiments over multiple widely adopted benchmarks show that RI-SAM3 achieves superior performance consistently in CD-FSS tasks, together with strong robustness, efficiency, and generalization.

cs.CV

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04083

MABEL: An Open Anthropomorphic Mobile Bimanual Platform for Teleoperation and Learning

Qilong Cheng, Rooholla Khorrambakht, Mohamed Yassine Kabouri, Quang Nam Nguyen, Luca Macesanu, Haoran Zhou, Yipeng Wang, Ludovic Righetti

原文摘要

As robot learning moves beyond the tabletop, many tasks require mobility, adjustable reach, active perception, and bimanual dexterity. Commercial platforms combining these capabilities are costly, while affordable open-source alternatives cover only a subset and require software integration. We present MABEL, an open-source anthropomorphic mobile bimanual robot with 56 degrees of freedom (DOF) and a US$8.1k parts cost. It combines two 7-DOF arms with 17-DOF hands, a pitching torso, a lift, a 3-DOF neck, and a holonomic base. Back-drivable arms and torso support compliant interaction, with fingertip reach from floor level to 2.23 m. The head and torso roughly triple modeled camera coverage relative to a torso-fixed camera. Apple Vision Pro head and hand tracking enables whole-body teleoperation without handheld controllers, with 137 ms mean glass-to-glass stereo video latency over the robot's Wi-Fi hotspot. We demonstrate an end-to-end imitation learning pipeline, from teleoperated data collection to policy deployment, using a shared command interface and whole-body controller.

cs.RO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04082

Polynomial VASS MDPs

Michal Ajdarow

原文摘要

Markov decision process over vector addition system with states (VASS MDP) is a finite state model combining non-deterministic and probabilistic behavior, augmented with non-negative integer counters that can be incremented or decremented during each state transition. VASS MDPs can serve as abstractions of probabilistic programs, offering many decidable properties. In this paper, we develop techniques for analyzing the polynomiality of asymptotic estimates for VASS MDPs. That is, for every initial configuration of size \(n\), we consider the number of transitions needed to reach a configuration with some counter negative. We show that for any VASS MDP, either for all \(ε>0 \) and all sufficiently large \(n\) the number of transitions is at least \(2^{n^{\frac{1}{2}-ε}} \) with probability at least \(1-ε\), or for any superpolynomial function \(f \), all \(ε>0 \) and all sufficiently large \(n\) the number of transitions is upper bounded by \(f(n) \) with probability at least \(1-ε\). Furthermore, if the VASS MDP is DAG-like then we can replace \(f(n)\) with \(n^{k+ε} \), where \(k=2\cdot 3^{w\cdot d+|T|} \) and \(w,d\) and \(T \) are the number of MECs, counters and transitions of the VASS MDP, respectively. It is decidable in polynomial time which case holds.

cs.LO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04081

RAPID: Increasing Efficiency of Internal Distillation via Randomized Methods

Ryan Swift, Konstantinos Psounis

原文摘要

Knowledge distillation is a technique used to transfer the expertise of large teacher models into small, efficient student models. Recent advances have integrated the distillation of internal activations, more directly training students to learn similar representations as the teacher. One of the core challenges of internal distillation is the dimensional incompatibility between the student and teacher internal representations. Existing methods add learnable matrices to project the larger teacher activations into the smaller representation space of the student. This is a notable point of inefficiency, as learning additional parameters for the projectors increases training costs, only for them to be discarded immediately after training. We introduce RAPID (RAndomized Projection for Internal Distillation) a novel distillation methodology which eliminates the wasteful projection learning by leveraging randomized methods. RAPID utilizes an efficient transform construction based on the Johnson-Lindenstrauss lemma to compress the teacher representations into the student embedding space with strong theoretical guarantees of structural preservation. RAPID also employs a combination of exponential moving average (EMA) and homoscedastic uncertainty weighting in a novel multi-objective function designed for internal distillation. Our experiments in post-training for reasoning demonstrate that RAPID increases training efficiency by as much as 21.1% while maintaining performance comparable to existing methods.

cs.LG

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04080

FEIJOA: Task-Driven Grounding and Execution for Mobile Manipulation

Aditya Agarwal, William Shen, Sahit Chintalapudi, Lucy Cai, Nishanth Kumar, Aidan Curtis, Travis Manderson, Tomás Lozano-Pérez 等 9 位作者

原文摘要

A mobile manipulator asked to "put the toys away in the toy box" must decide which objects are toys and which container the user means, then find base poses, grasps, and placements it can execute. Because a scene representation is built before the instruction is known, it may lack the attributes, affordances, or concepts needed to resolve the task. We present FEIJOA, a language-model agent that grounds the instruction at test time. It queries a grounding tool over a posed RGB-D scan, inspects the returned candidates, and refines its queries until they resolve the instruction. An embodiment-aware harness checks each skill's preconditions, samples base poses from which the target is reachable, and verifies the skill's effect from observations before and after execution. On 103 open-ended grounding queries, FEIJOA resolves 94.2% exactly, compared with 68.0% for the best prebuilt representation. Over 50 real-world trials on Spot, it completes 35 tasks; 17 of these successes follow recovery from a failed tool call or verification check. Of the 15 failed trials, 13 were caused by the robot's physical skills, and only 2 by grounding or the agent's reasoning. Project website: https://williamshen-nz.github.io/feijoa/.

cs.RO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04079

AlgoPilot: Cross-Paradigm Reasoning in Language Models via Strategy Selection and Guidance

Yilun Hao, Ruixiao Yang, Hudson Hilal, Yongchao Chen, Kaizhi Qian, Yada Zhu, Yang Zhang, Chuchu Fan

原文摘要

Real-world problems span diverse domains, including program synthesis, symbolic reasoning, planning, and optimization, and often require fundamentally different solution paradigms. A central challenge for LLM-based reasoning is twofold: identifying an appropriate problem-solving approach and formulating it correctly. In this paper, we propose AlgoPilot, a cross-paradigm reasoning framework that enables adaptive selection of the solving approaches and structured problem formulation prior to execution. The AlgoPilot framework contains three components: 1) a SteerLM, trained via supervised fine-tuning (SFT) and reinforcement learning (RL), that adaptively selects the solving strategy (paradigm and modes) based on input problems, 2) the corresponding expert GuideLM, trained via SFT, that generates structured formulation guidance tailored to the selected strategy, and 3) an ExecutionLM that generates solutions conditioned on both the selected strategy and its formulation. Unlike prompting-based methods that rely on fixed reasoning templates, our approach learns to adaptively choose and structure problem-solving strategies based on the input. We build AlgoPilot on Qwen3-8B and evaluate across 5 problem categories and 13 benchmarks with 66 unique domains, comparing against both the latest similarly scaled small models and large LLMs. AlgoPilot significantly improves average accuracy for the same model from 38.4% to 72.9%, outperforming the best large LLM prompting baseline GLM-5 by 11.7%. Ablation studies confirm the effectiveness of each component. Notably, we show that the learned steering and formulation modules can transfer across execution models, suggesting their potential to improve other LLMs. Project page: https://sites.google.com/view/algopilot.

cs.AI · cs.CL · cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.38037

Emergence in Network Systems is Bounded by Boundary-Crossing Paths

Johnny Jingze Li, Gabriel A. Silva

原文摘要

Emergence, features of a whole that no part shows alone, is central to complex systems but rarely measured so as to locate its source. Viewing a system structurally, as a network of interacting parts, we evaluate emergence as what observing the coupled whole reveals beyond, or erases from, the combined observations of the parts. For observations that build what they see route by route, we show that every emergent feature is produced by its own route across the interface between parts, a route that traces it to the components and interactions responsible. We show the number of all such boundary-crossing paths bounds the total emergence discrepancy, and equals the emergence of measures that count routes. The bound is computed locally around the interface, validated through network examples, and in a nervous system the routes show that interneurons relay most of the emergence. Our work associates emergence with path structure in the network system that can be anticipated, attributed, and engineered.

physics.soc-ph · cs.SI · nlin.AO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04077

From topology-optimization brief to solver-checked release: separating intent, admissibility and acceptance knowledge for language agents

Shaoliang Yang, Jun Wang

原文摘要

An engineering solver can converge even when a language agent has misread the user's problem. AgenticTO makes this distinction inspectable by keeping three records separate: the proposed problem specification, deterministic formulation checks, and numerical acceptance of the solved design. We evaluated the workflow on 50 author-built topology-optimization briefs, injected faults, five numerical problems, and complete agent sessions. The tests used linear-elastic models with one load case. Geometry tools raised the primary provider's correct specifications and refusals from 37 to 44 of 50, while also increasing wrong specifications delivered as finished. Input-format feedback alone recovered most of the accuracy gain. The wrong specifications passed the formulation rules, which also missed most injected faults that changed the intended problem. Clarification corrected the remaining errors when an oracle supplied reference facts, but also prompted questions on fully specified briefs. Perfect accuracy under that oracle therefore does not establish performance with engineers. Numerical trials reached 73.7 million elements, although released designs used finer grids than requested. The records expose how a proposed problem becomes an accepted numerical result; agreement with the brief still needs a separate judgment.

cs.CE

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2211.02107

Variable Parameter Analysis for Scheduling One Machine

Nodari Vakhania

原文摘要

In contrast to the fixed parameter analysis (FPA), in the variable parameter analysis (VPA) the value of the target problem parameter is not fixed, it rather depends on the structure of a given problem instance and tends to have a favorable asymptotic behavior when the size of the input increases. While applying the VPA to an intractable optimization problem with $n$ objects, the exponential-time dependence in enumeration of the feasible solution set is attributed solely to the variable parameter $ν$, $ν<<n$. As opposed to the FPA, the VPA does not imply any restriction on some problem parameters, it rather takes an advantage of a favorable nature of the problem, which permits to reduce the cost of enumeration of the solution space. Our main technical contribution is a variable parameter algorithm for a strongly $\mathsf{NP}$-hard single-machine scheduling problem to minimize maximum job lateness. The target variable parameter $ν$ is the number of jobs with some specific characteristics, the ``emerging'' ones. The solution process is separated in two phases. At phase 1 a partial solution including $n-ν$ non-emerging jobs is constructed in a low degree polynomial time. At phase 2 less than $ν!$ permutations of the $ν$ emerging jobs are considered. Each of them are incorporated into the partial schedule of phase 1. Doe to the results of an earlier conducted experimental study, $ν/n$ varied from $1/4$ for small problem instances to $1/10$ for the largest tested problem instances, so that that the ratio becomes closer to 0 for large $n$s.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04073

Computer-Use Agents Gain Little Benefit from a World Model When Conditioned on Tutorials

Anh Nguyen, Tianyi Xu, Phat Tran, Harry Yu, Huazheng Wang, Stefan Lee

原文摘要

Recent work has improved computer-use agents (CUAs) by combining retrieved task-relevant tutorials and look-ahead planning using world models with MLLM judges. However, the contribution of each component -- tutorials, the judge, and the world model -- to overall improvement has not been evaluated in isolation. To fill this gap, we first construct OSWorld-Tutorial and ScienceBoard-Tutorial: two datasets for CUAs with curated multimodal tutorials, covering everyday and scientific domains. We then propose RAG-PolicyJudge (RAG-PJ), a policy-judge framework for CUAs conditioned on task-specific tutorials: the policy proposes candidate actions, and the judge selects among them. To isolate the effect of world models given tutorials, we compare RAG-PJ with and without common world models: using either zero-shot text-based descriptions of next states or an oracle that returns ground-truth visual observations. We find that RAG-PJ gains little benefit from these rollouts when tutorials are present, even with perfect visual futures. This suggests prior world-model gains in tutorial-conditioned methods come mainly from tutorial understanding and the judge's ability to select the proposed actions, rather than from predicted rollouts. Error analysis reveals that the bottleneck is not rollout fidelity, but the judge's ability to reason over future states and recognize task completion. This highlights the need to improve not just next-state prediction in world models, but also reasoning over their predicted rollouts. Datasets and code are available at https://github.com/realjoenguyen/RAGPJ-official.

cs.LG

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04072

Finite-Sample Convergence in Networked Average Reward MARL: Decentralization Pitfalls and Entropy Remedies

Yizhou Zhang, Yashaswini Murthy, Laixi Shi, Adam Vierman

原文摘要

We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its $k$-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

cs.LG · cs.MA

查看论文
arXiv ↗PDF ↗