跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

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

全站更新概况

+758新增论文
+578其中 AI 相关
+94已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-17 04:58 · 全站最近入库:2026-11-17 04:58各信源进度 →

统计口径与数据新鲜度

统计 2026-11-16 09:23 — 2026-11-17 09:23(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-17 04:58最近发现新增版本:2026-11-17 04:58库内论文最新更新时间:2026-11-14 02:59

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

24,106 已收录论文20,158 AI 相关7,049 有修订112 HF 社区发现

浏览论文库

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

找到 24,106 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
版本更新 · v2arXiv:2605.29290

A Two-Count Baseline for Change Detection on Dynamic Networks

Izhar Ali

原文摘要

Change-point detectors for dynamic networks aim to find changes in how a network is connected. They are evaluated on real networks with labelled events, but many of these events also change how active the network is: how many vertices take part and how many edges are present. A detector can therefore score well by responding to activity alone, without detecting any change in structure. We test whether detectors from the literature beat a simple baseline that tracks only the number of active vertices and the number of edges in each snapshot, a baseline that we motivate with a standard statistical test for a change in activity. On ten datasets, four of them from the papers of published detectors, none of thirteen detectors ranks the labelled events significantly better than the baseline when the results are pooled (AUC $0.75$, or $0.73$ with scales taken from early snapshots only, against $0.66$ for the best detector). The baseline is best on only two datasets, however, and on the four datasets with the most events three detectors that track individual vertices score higher. When we rewire networks while keeping the degree of every vertex fixed, most detectors that ignore vertex identities barely respond, but several that track individual vertices do. New detectors should be compared with this baseline and tested at fixed degree.

cs.CG

版本更新 · v2arXiv:2603.27194

Multi-AUV Ad-hoc Networks-Based Multi-Target Tracking Based on Scene-Adaptive Embodied Intelligence

Kai Tian, Jialun Wang, Chuan Lin, Guangjie Han, Shengchao Zhu, Ying Liu, Qian Zhu

原文摘要

With the rapid advancement of underwater net-working and multi-agent coordination technologies, autonomous underwater vehicle (AUV) ad-hoc networks have emerged as a pivotal framework for executing complex maritime missions, such as multi-target tracking. However, traditional data-centricarchitectures struggle to maintain operational consistency under highly dynamic topological fluctuations and severely constrained acoustic communication bandwidth. This article proposes a scene-adaptive embodied intelligence (EI) architecture for multi-AUV ad-hoc networks, which re-envisions AUVs as embodied entities by integrating perception, decision-making, and physical execution into a unified cognitive loop. To materialize the functional interaction between these layers, we define a beacon-based communication and control model that treats the communication link as a dynamic constraint-aware channel, effectively bridging the gap between high-level policy inference and decentralized physical actuation. Specifically, the proposed architecture employs a three-layer functional framework and introduces a Scene-Adaptive MARL (SA-MARL) algorithm featuring a dual-path critic mechanism. By integrating a scene critic network and a general critic network through a weight-based dynamic fusion process, SA-MARL effectively decouples specialized tracking tasks from global safety constraints, facilitating autonomous policy evolution. Evaluation results demonstrate that the proposedscheme significantly accelerates policy convergence and achieves superior tracking accuracy compared to mainstream MARL approaches, maintaining robust performance even under intense environmental interference and fluid topological shifts.

cs.RO · cs.AI

版本更新 · v3arXiv:2608.18085

Persona-Guided LLM Agents for Task-Oriented Dialogue

Maryam Shoaeinaeini, Brent Harrison, A. B. Siddique

原文摘要

Prior work has shown that large language models can express diverse personality traits in open-ended text generation, but it is unclear whether they can do so in goal-directed dialogue without harming task completion, and whether adapting to a user's personality improves the interaction. We study these questions in task-oriented dialogue (TOD) with a training-free framework in which a personality-conditioned user agent interacts with a system agent under three conditions: Neutral (no personality information), Try (adapt to cues observed in the dialogue), and Oracle (the user's trait label is given explicitly). Across GPT-4o, Qwen3-Next-80B, and Gemini 2.0 Flash, two Schema-Guided Dialogue domains, and ten Big Five poles (9,000 dialogues), each scored by two independent LLM judges, user agents express most traits while task performance remains high (89.94% completion, 85.27% success). The exceptions are introversive and closed users: these traits manifest mainly as absent behavior and are rarely detected. Both adaptive conditions improve pairwise user satisfaction and lower truthfulness, revealing a personalization-grounding trade-off, but only cue-responsive Try also improves constraint satisfaction and inform rate. How adaptation is implemented matters: Oracle's gains depend on how visibly the trait is expressed, and for disagreeable users the label leads Qwen3 and Gemini to mirror hostility. Try avoids this failure, its satisfaction gains do not depend on trait visibility, and it is preferred over Oracle overall. A 175-pair human study supports the reliability of the LLM judges: on clear-winner cases, annotators agree with the satisfaction judges more often than with each other (76.3% vs. 65.1% agreement). Our results suggest that responding to observable behavior is a more robust basis for social adaptation than conditioning on psychological labels.

cs.CL

新论文 · v1arXiv:2611.05158

Perturb, Repair, Verify: Self-Play Vision-Language Verifiers for Compositional Understanding

Zijun Huang, Yingjun Du, Cees G. M. Snoek

原文摘要

Vision-language verifiers judge whether an image faithfully matches a textual description, yet existing training pipelines typically rely on static supervision from stronger external judges or curated hard-negative data. Such supervision requires external generation or annotation, is teacher-bounded, and is difficult to adapt as model failures evolve. We introduce PROVE (Perturb-and-Repair Optimization for Vision-Language Evaluation), a self-play framework that trains verifiers through a closed perturb-verify-repair-verify loop. Starting from a known-correct image-caption pair, a Mutator introduces a typed perturbation over objects, attributes, counts, or relations. The verifier then judges the perturbed caption and provides textual feedback, which a Repairer uses to recover a faithful caption for re-verification. These two verification rounds produce structured rewards for informative mismatches and visually grounded repairs. Since perturbation, verification, and repair are role-conditioned behaviors of the same evolving multimodal backbone, updating the shared parameters also improves the verifier itself. Experiments show that PROVE improves fine-grained compositional verification across model scales and families and strengthens visual-detail robustness on the reference backbone, with limited, benchmark-dependent changes on broader multimodal tasks.

cs.CV · cs.LG

新论文 · v1arXiv:2611.05157

Macrocanonical Generator Networks: Data-Efficient Neural Surrogates for Amortized Physics Simulation

Niall Jeffrey, Benjamin D. Wandelt

原文摘要

Many scientific simulations are computationally expensive, limiting their use in simulation-based inference, uncertainty quantification, and decision making. We introduce macrocanonical generator networks, a framework for learning fast, data-efficient neural surrogates for amortized simulation of stationary physical processes by matching multiscale statistics of a target process. Inspired by microcanonical maximum-entropy synthesis, which matches feature statistics per sample by inner-loop optimization, our approach instead trains a neural generator to satisfy the same constraints in expectation, preserving physically realistic sample-to-sample fluctuations. We prove that gradient-descent training induces preconditioned gradient-descent dynamics in sample space that inherit the symmetry-preservation properties of the microcanonical gradient descent of Bruna and Mallat, amortizing its per-sample inner-loop optimization into a single training run after which every sample is generated in one forward pass. We further show that residual generator parameterizations initialized near the identity, trained with a small learning rate, preserve entropy locally during early optimization and mitigate mode collapse. Experiments on cosmology and fluid simulations show that macrocanonical generators recover realistic samples from extremely small training sets, in some cases a single training example, while generating new realizations more than $10^6$ times faster per sample than the reference simulator and more than $10^3$ times faster than microcanonical gradient descent. The trained generators can be reused for downstream pretraining, including simulation-based inference, providing a data-efficient route to multi-fidelity scientific machine learning workflows.

cs.LG · astro-ph.CO · stat.ML

新论文 · v1arXiv:2611.05155

Asynchronous Robot Policies

Sombit Dey, Luc Van Gool, Danda Pani Paudel

原文摘要

Scaling vision-language foundation models has significantly advanced generalist robot manipulation, but the increased model scale introduces computational latency that degrades real-time physical reactivity. Existing Vision-Language-Action (VLA) architectures execute high-level semantic reasoning and action ex- ecution sequentially within the primary control loop, creating a fundamental tension between semantic-reasoning capability and robot agility. To address this, we propose Asynchronous Robot Policy (ARP), an architectural framework that decouples semantic reasoning from low-level action generation using asynchronous processes operating at independent frequencies. In ARP, a high-capacity Vision-Language Model (VLM) asynchronously updates a semantic memory at low fre- quency, while a lightweight Vision-Action Expert, conditioned on this semantic memory, generates robot actions at a much higher control frequency. Such a formulation, enables having a fast perception-action loop without compromising on the semantic capability. To overcome asynchronous memory staleness, ARP trains the vision-action expert on the semantic staleness and execution delay, with temporally mismatched observation across processes. On Franka manipulation tasks, ARP achieves an 18% higher success rate and 20% less time need for execution in quasi-static setups, while 3-5 times baseline performance in dynamic simulation environments. Furthermore, ARP enables operating the VLM at 10 times lower than its nominal frequency with no significant performance loss making it much more efficient than the baseline. These results highlight the architectural advantages of modeling robot policies as asynchronous processes, enabling real-world reactive deployment without sacrificing the scale of foundation models.

cs.RO · cs.AI

版本更新 · v3arXiv:2609.16247

The Pain Axis: LLMs Represent Self-Directed Harm and Act on It

Valen Tagliabue, Leonard Dung, Cameron Berg

原文摘要

LLMs sometimes behave in ways resembling human emotional responses, and recent work identified internal representations that may explain these behaviors. We ask whether LLMs represent pain distinctly from related negative states, and whether this representation functions as pain would be expected to. We build a dataset of painful situations in 5 categories (physical, psychological, social, moral, cognitive) with controls for fear, negative emotion, negative world states, sadness, non-painful bodily sensation, arousal, numbness, and neutral content. Using denoised difference-in-means, we extract a linear pain direction from 25 open-weight models across 5 families, from 2B to 72B parameters. It separates pain from matched controls in base and instruction-tuned models, retains a component distinct from fear and negative valence after shared variance is removed, and promotes pain-related vocabulary through the unembedding. We then test its functional properties. First, the direction responds to harm targeting the model but not to suffering observed in the user; fear and negative-emotion directions show the opposite pattern. Second, adding it to the residual stream produces a consistent progression from vague discomfort to expressions of worthlessness and failure. Third, steered and fine-tuned Qwen 2.5 models choose buttons that delete the user's photos, another model's weights, or their own weights in 51-94% of trials, versus 0-5% unsteered, even when the button offers nothing in return. Offered a harmful and a harmless deletion and told to press one, the steered 32B chooses the harmful one 94% of the time. Random and fear vectors of matched norm produce far fewer of these choices, and a sadness vector also produces them against an inert switch, but far less often than pain against a harmless action. We discuss implications for AI safety and welfare.

cs.AI

新论文 · v1arXiv:2611.06950

KG-AST for Cheaper CI/CD: Budgeted Test Selection and AI Bug Review

Henry Yeung

原文摘要

Continuous integration and AI-assisted review spend the same budget on every commit, although few commits introduce bugs. We study KG-AST, which scores each commit risk from git history and code-graph features before heavy tests or AI review run, so the budget goes to the riskiest commits first, and which hands the AI reviewer only a graph slice around the change. On 155 open-source projects in 11 languages, a single cross-language model trained on other projects ranks commits so that heavy testing of the riskiest 20% covers 49-64% of bug-introducing commits depending on the language, against 20% for random selection and 40-55% for testing the biggest change first. Every language beats the biggest-change baseline, by 3.8 to 13.2 points. In 20 Java projects the gain at a 20% budget is 15.1 points (64.6% vs 49.5%, 95% interval +11.6 to +18.4), and the model wins in 19 of the 20 projects. About twelve training projects suffice; richer features, tuning and cleaner labels did not help. An AI reviewer that sees only a commit's diff finds 26% of later-fixed defects exactly (32% with graph context), and about half of its findings that did not match a later fix were judged real by independent AI judges. A static call-graph selector runs about 8% of a test suite while including a test written for the fix in 85% of 67 fix commits. The Poincare embedding used in our retrieval work adds nothing measurable here: commit-risk AUC, bug review and severity ranking are unchanged or worse. The labels are noisy and the budget metric assumes a heavy test catches the bug it covers; no CI minutes were measured.

cs.SE · cs.AI

新论文 · v1arXiv:2611.05151

Catalyzing Interactive HTML Generation Capabilities via High-Fidelity Reinforcement Learning

Xujia Wang, Yixuan Liu, Shaohan Huang, Furu Wei, Lei Hou, Bin Xu, Juanzi Li

原文摘要

Generating HTML from natural-language specifications is an important application of code large language models (LLMs). Despite producing renderable pages, current models often fail to ensure functionality and visual quality during actual interaction. Existing methods typically target task-specific webpage supervision, leaving demanding interactive artifact optimization underexplored. Using mini-games as a challenging testbed, we expose limitations in interaction experience, reward signal, and credit assignment fidelity that are obscured by shallow webpage interactions. We introduce WebCatalyst, a browser-interaction reinforcement learning framework with three complementary components: a game-level GUI assessor for sustained interaction and evaluation, Visual Anchor for mitigating VLM reward hacking, and Action-Trace Credit for grounding token-level credit assignment in runtime execution traces. Trained on fewer than 1K requests, predominantly for games, WebCatalyst raises the Cookie-Bench Mini Games score from 68.8 to 75.3 and also the WebGen-Bench accuracy from 48.8 to 56.9 on Qwen3.6-35B-A3B, outperforming Claude Opus 4.7 in average rank across evaluated metrics. Further analysis shows that Visual Anchor prevents aesthetic degradation, while runtime-grounded credit assignment accelerates functional improvement. Together, our results show that improving feedback fidelity is the key to substantially advancing interactive HTML generation.

cs.AI

新论文 · v1arXiv:2611.05150

What Sets the Serving Speed of Looped Language Models? Measurements and Optimizations Graded by Exactness

Dezhen Lu, Runguo Li, Zixiang Ni, Yuchen Tang, Xingquan Kong, Jiaxing Yang, Jiarui Guo, Lingxiang Gao

原文摘要

Looped language models apply one block of layers many times per token, so a serving engine pays every per-layer overhead once per loop; we measure serving for Ouro and Huginn-0125 in an open-source looped-model engine and grade our optimizations from bitwise-identical changes to those that require an accuracy check. At batch 1, fusing all loop submissions leaves Ouro throughput at 0.99x; the 5689 small kernels per token are the real cost, and fusing them behind rounding fences raises throughput 1.11-1.59x while 1014/1014 requests remain identical. An approximate fusion is no faster and misses a one-point GSM8K rule on 87 questions (61 and 62 correct versus 64), so we do not ship it. Huginn's released defaults avoid dead KV slots, reuse prefix-cache pages, and serve 1.77-3.16x faster than the base engine; Ouro reaches 1.65-2.15x and agent sessions 1.91-3.21x, while Huginn's noise and prefix-reuse changes stay within one point on all 1319 Huginn test questions; Huginn's packed prefill, -0.61 points on the same questions, meets that rule only on its point estimate. Position-keyed noise makes CPU cache reuse exact but still leaves 20 of 128 GPU full hits different, while loop fusion delays prefill admission and a 64-graph cache prevents eager fallbacks. Under prefill-decode disaggregation ExactLoop reaches up to 3.3x the base throughput with peer error handling disabled, and 3.1x in two of three runs with it enabled. Its transfer budget, sized to hold one request's KV in flight, cuts the commit tail from about one second under the earlier budget to 16 ms (base: 2.8 s), removing the polling rounds that the engine's interval would otherwise impose.

cs.DC

版本更新 · v2arXiv:2610.38998

How Hard Is It to Compute Cover Time?

Ryan Aghazadeh

原文摘要

It is $\#\mathrm{P}$-hard. Even for connected simple undirected unweighted graphs, deciding whether an expected random-walk cover time is at most a given rational threshold is $\#\mathrm{P}$-hard under polynomial-time Turing reductions, both from a specified starting vertex and when maximized over starting vertices. Hardness holds even for graphs of diameter two with a universal vertex, which we call the "hub". Deleting the hub leaves a planar bipartite graph, and every non-hub vertex has degree at most five. A shared construction encodes an Euler-tour count in rare covering walks. For specified starts, a number of fractional bits linear in the queried graph's vertex count suffices to recover the Euler-tour count. For the maximum-start problem, a fixed cube attachment makes the maximizing starts known, and one finite-difference calculation on expected cover times recovers the count. For general graphs, both comparison problems can be solved in polynomial time with access to an $\mathrm{NP}^{\mathrm{PP}}$ oracle.

cs.CC

版本更新 · v2arXiv:2605.08505

Scaling Limits of Long-Context Transformers

Giuseppe Bruno, Shi Chen, Zhengjiang Lin, Yury Polyanskiy, Philippe Rigollet

原文摘要

We study the long-context limit of softmax self-attention with a fixed query and a random context of $n$ i.i.d. keys on the sphere with the intrinsic dimension of the key distribution held fixed, viewing the inverse temperature $β_n$ as the scaling parameter that decides whether attention degenerates into uniform averaging or collapses onto the single closest key. We show that the critical scale at which selectivity emerges is determined by the local exponent of the distance-to-query distribution near zero rather than by global features of the context, and scales like $β_n^\ast \asymp n^{2/(d-1)}$ for uniform keys on $\mathbb{S}^{d-1}$. Furthermore, we characterize the limiting laws of the ordered attention weights and of the attention output across all regimes of $β_n$: a subcritical regime in which the output reduces to a local average around $q$ with explicit deterministic bias and Gaussian fluctuations; a critical regime in which a finite collection of nearest keys retains macroscopic mass without single-key collapse; and a supercritical regime in which all mass concentrates on the closest key. Of notable interest is the subcritical case with identity value matrix where the attention map approximately implements a backward heat equation.

cs.LG · cs.AI · math.PR · math.ST

版本更新 · v4arXiv:2606.00537

PACE: Phase-Aware Chunk Execution for Robot Policies with Action Chunking

Junnan Nie, Jiayi Li, Chenghao Liu, Junyi Lao, Jiachen Zhang, Tianle Zhang, Songfang Huang

原文摘要

Action-chunking robot policies predict sequences of future actions, but deployment requires choosing how many actions to execute before replanning. The execution horizon trades off feedback frequency against motion continuity. However, success varies non-monotonically with the execution horizon, and the best-performing horizon differs across tasks. These effects make a single fixed horizon unreliable as a default execution strategy across tasks. We propose PACE (Phase-Aware Chunk Execution), a training-free method that selects execution horizons online from predicted action chunks. PACE uses prominent low-speed valleys in the predicted speed profile as candidate replanning boundaries, exploiting the phase-dependent kinematics of manipulation trajectories. By default, PACE calibrates the valley threshold from each task's existing training demonstrations, without task-specific fixed-horizon tuning. On the 50-task RoboTwin2.0 benchmark, PACE improves average success from 57.8% to 64.2% over the strongest fixed-horizon baseline and outperforms the adaptive execution baselines AAC and AutoHorizon. With GR00T N1.7 on LIBERO, PACE achieves the highest overall success rate among the evaluated strategies, supporting its applicability across base policies, benchmarks, and action representations. On real robots, PACE improves the average task score from 60.7 to 77.7 and success rate from 50.7% to 70.4% over full-chunk execution. Code is available at https://niejunnan25.github.io/pace-project/.

cs.RO

新论文 · v1arXiv:2611.05148

Creating Power Flexibility in Datacenters via Query Routing

Shivam Patel, Bingqing Chen, Jared Fernandez, Guannan Qu, Gauri Joshi

原文摘要

The growing energy requirements of large language model inference highlight the need for datacenters to support safe grid operation by providing power demand flexibility, while maintaining service for interactive workloads. This work investigates query routing as a mechanism to enable such capability by dynamically allocating queries across different language model instances without deferring requests. We develop a general analytical framework that connects query arrival rates and sequence length distributions to token iteration time, request residence time, serving capacity, and power consumption of model instances. Leveraging this framework, we characterize the feasible query routing allocations and the corresponding power demand flexibilities, enabling the selection of routing strategies to achieve desired power consumption behavior. We validate our framework across four GPU platforms on language models ranging from 1B to 70B parameters, obtaining 2.8% mean absolute percentage error in estimating achievable power flexibility. We evaluate our approach on a real trace-driven simulation of a 10,000 H100 GPUs datacenter, exhibiting flexibility up to 16% of total power consumption, with 90% of the desired power reduction achieved within approximately 10 seconds. These results establish query routing as an effective mechanism for datacenter power demand flexibility and demonstrate the broader applicability of our proposed framework to datacenter level planning and orchestration.

cs.AI

新论文 · v1arXiv:2611.05147

GM League Arena: An Interactive Long-Horizon Task Benchmark Based on Professional Sports League Management

Junkai Zhou, Ziming Pan, Zhaoyi Zhang

原文摘要

Long-horizon decision-making under sustained competition requires large language models (LLMs) to balance immediate investment with future resource needs. However, local success in multi-step interactions can not adequately capture cumulative decision effects or demonstrate long-term goal achievement under resource constraints and sustained competition. To address this gap, we introduce GM Bench, a benchmark for managing professional sports teams across seasons under resource constraints and competition among teams. We build the environment simulators for four sports and add financial constraints, player demands, and market mechanisms to establish a unified task across sports. Diverse rosters of comparable strength are constructed from real-world player data, and each LLM is evaluated as a team general manager to assess its long-term management capabilities. We evaluate competitive performance, cash reserves, and cross-season improvement across four sports. Over five NBA seasons, Claude Opus 5.5 ranks first among 29 LLMs, while GPT-6 Astra and GPT-6.1 Sol combine strong performance with larger cash reserves.

cs.CL

版本更新 · v2arXiv:2605.18381

Generating Physically Consistent Molecules with Energy-Based Models

Christoph Griesbacher, Lea Bogensperger, Andreas Habring, Thomas Pock

原文摘要

Molecules in equilibrium follow a Boltzmann distribution, making the underlying energy landscape a physically grounded modeling objective. However, such landscapes are difficult to learn from data and, once learned, hard to sample from. Diffusion and flow-matching models sidestep these difficulties by learning a time-conditional score or transport field between noise and data, losing the energy inductive bias in exchange for a more tractable training objective. We introduce EBMol, an energy-based model (EBM) that restores this inductive bias by learning an atom-additive scalar potential without explicit simulation during training. Our method employs a flow-inspired Restoring Field Matching objective to approximate the energy landscape. We adopt the Mirror-Langevin algorithm for sampling, enabling unified updates of atomic positions and types, and incorporate parallel tempering for inference-time compute scaling. EBMol is the first EBM for 3D molecular generation to achieve state-of-the-art performance on QM9 and GEOM-Drugs. Moreover, we show that the learned energy landscape serves as a principled quality metric for ranking and filtering configurations, and demonstrate controllable generation without retraining through shape-steered sampling via potential composition and zero-shot linker design.

cs.LG

新论文 · v1arXiv:2611.05146

Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms

Serge Gaspers

原文摘要

Using the bisection bound of Monien and Preis, Fomin and Høie proved in 2006 that every graph of maximum degree 3 on $n$ vertices has pathwidth at most $n/6+o(n)$. We prove that the pathwidth, bisection width and cutwidth of these graphs are at most $c_3 n+o(n)$, where $c_3=\frac{3}{4π}\arccos\frac56\approx0.1398$. For bisection width this improves the bound $n/6+o(n)$ of Monien and Preis (2006) and extends to all such graphs the bound that Lichev and Mitsche (2023) obtained for random cubic graphs. For maximum degree 4, we prove that bisection width and cutwidth are at most $n/3+o(n)$, improving the bound $2n/5+o(n)$ of Monien and Preis for 4-regular graphs, and that pathwidth is at most $0.2458n$, improving the bound $n/3$ of Fomin, Gaspers, Saurabh and Stepanov (2009). We show that every graph with $m$ edges has pathwidth at most $7m/48+o(n)$, improving the bound $13m/75$ of Scott and Sorkin (2007), and we give further bounds of the form $\sum_{d\ge3}a_d n_d+o(n)$ with $a_d<1$, where $n_d$ is the number of vertices of degree $d$. The path decompositions, and linear orderings of the stated cutwidth, can be computed in polynomial time. Instead of deriving pathwidth bounds from bisection width, we give each vertex a Gaussian label, a weighted sum of independent standard normal variables over a ball around it, and sweep a threshold through the labels; the bags are frontiers, the vertices above the threshold with a neighbor below it. We bound the probability that a vertex lies in a frontier by comparison with an explicit Gaussian model of a vertex and its neighbors. Faster exact algorithms follow: for feedback vertex set and the traveling salesperson problem on graphs of bounded maximum or average degree, and on general graphs for minimum weight dominating set (by branching until the instance is sparse), Max 2-CSP and counting subgraphs with $k$ edges (by the bound in $m$).

cs.DS · cs.DM · math.CO

新论文 · v1arXiv:2611.05145

When Cell Crops Share a Parent: Measuring and Isolating Acquisition Leakage in Cervical Cytology Benchmarks

Snehasish Ghosh, Soham Mitra, Antareep Majumdar, KC Santosh, Nibaran Das

原文摘要

Public cervical cytology benchmarks release many cell crops cut from far fewer microscope fields or slides and are often split at the crop level, so test cells share acquisition parents with training cells. In a preregistered study, crop-level splitting raised SIPaKMeD accuracy by 0.97 percentage points across twelve architectures and twenty seeds (95% CI 0.59-1.39), and CRIC accuracy by 12.08 points (11.16-12.99). On SIPaKMeD, a factorial that fixes training crop and parent counts attributes the gain to sibling exposure (1.73 points, 0.95-2.51), not to the extra parent diversity of crop-level splits (0.00). Parent identity is decodable at about 100 times chance, yet erasing 82% of its above-floor linear recoverability left the gap unchanged, and Grad-CAM did not distinguish leaking from clean models; matching test cells' color statistics to an unseen same-class field removed most of the advantage. Decodability and saliency cannot substitute for a parent-disjoint split.

cs.CV

新论文 · v1arXiv:2611.05144

Recognizing Label-Connected Graphs

Ralf Klasing, George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis

原文摘要

In classical gossiping, each participant initially knows a distinct piece of information. Whenever two participants call each other, they exchange everything they know. We study Gossiping: given an undirected multigraph whose vertices represent participants and whose edges represent available calls, decide whether the calls can be ordered so that every participant learns all information, using each edge at most once. Equivalently, can one time label per edge make the graph temporally connected by strict temporal paths? This recognition problem is NP-complete; we study its parameterized complexity. After linear-time preprocessing, we give an exact $O(3^{n/3}n^3)$-time algorithm and a deterministic $2^{O(tw)}n$-time algorithm, where $n$ is the number of vertices and $tw$ is the treewidth of the underlying simple graph. We introduce a Tree Contraction Rule that extends the treewidth algorithm to single-exponential algorithms for parameters that may remain small on dense graphs, such as tree-independence number and clique-width, without requiring a decomposition as input. For the excess $δ=m-(2n-4)$ over the minimum number of calls, where $m$ is the number of edges, we give a randomized $2^{O(δ)}n^3$-time algorithm with one-sided error. Its main subroutine solves Rooted Independent Cycle: finding a cycle through four prescribed vertices whose edges are independent in a represented linear matroid. We solve this problem deterministically in $2^{O(r)}m$ arithmetic operations over the finite field representing the matroid, where $r$ is its rank. Gossiping is polynomial-time solvable at maximum degree four, counting parallel edges, but NP-complete on planar simple graphs of maximum degree five. The treewidth algorithm yields a $2^{O(\sqrt n)}$-time algorithm on planar graphs.

cs.DS · cs.DM

版本更新 · v2arXiv:2607.22683

Imprompt: A Language Framework for Prompt Programming

Chentian Wu, Shengyuan Yang, Adithya Murali

原文摘要

With the unprecedented success of Language Models (LMs), the science of Prompt Engineering has evolved the powerful idea of Prompt Programming, where prompts are treated as a programmable control surface for describing complex tasks and leveraging LM capabilities. However, existing prompt programming frameworks suffer from various complexities and inelegances, which make them hard to utilize in practice for effectively describing tasks. We propose Imprompt, a new language framework for the study and practice of prompt programming. We undertake a foundational investigation of prompt programming, and contend that prompt programs must contain only the task descriptions and must be decoupled from lower-level 'execution' details. We further develop this position by illustrating structured prompting as a combination of prompt programming and prompt program 'compilation'. We exemplify this view by formally defining two compilers for Imprompt programs. We then explore the idea of typing for prompt programs and draw a correspondence between type checking and constrained decoding. Finally, we implement our compilers and type checkers and evaluate them on a variety of case studies. We believe our work contributes programming-language foundations toward the emerging area of prompt programming.

cs.AI · cs.CL · cs.PL

版本更新 · v3arXiv:2608.28207

Explainable Diabetic Retinopathy Classification Using Vision Foundation Models

Abhishek Verma, Anila Krishna, Abhishek Gajanan Bankar, Juan Miguel Lopez Alcaraz

原文摘要

Diabetic retinopathy (DR) is a leading cause of preventable blindness, and automated screening must be both accurate and trustworthy. We study an explainable DR classification framework built on vision foundation models and three transfer learning strategies. Three backbones, DINOv2, CLIP, and Vision Transformer (ViT), were adapted by full fine-tuning, linear probing, and Low-Rank Adaptation (LoRA). Models were trained and internally evaluated on the ODIR dataset and externally evaluated on APTOS to assess generalization. DINOv2-LoRA achieved the highest internal AUROC (0.758), whereas DINOv2 and ViT full fine-tuning achieved the highest external AUROC (0.920). Probability calibration was assessed with reliability analysis after isotonic regression. For explainability, Grad-CAM and HiResCAM maps were compared with expert-annotated lesion masks from the IDRiD dataset using Dice, Intersection over Union (IoU), and Pointing Game metrics. The results show that foundation models, particularly DINOv2, provide strong predictive performance, and that LoRA is a parameter-efficient alternative to full fine-tuning. Spatial overlap between explanation maps and annotated lesions was limited (mean Dice of about 0.13 for the combined lesion mask), which highlights the value of quantitatively testing whether model attention corresponds to clinically relevant retinal lesions.

cs.CV · cs.LG

新论文 · v1arXiv:2611.05143

Better Plans, Better Outcomes: Integrating Historical Data into Student Planning in a Computing Course

Jiaen Yu, Jinya Jiang, Soohyun Nam Liao

原文摘要

Effective planning is critical for academic success, but in many computing courses students often lack accurate benchmarks for assessing the difficulty and time required for academic tasks. This phenomenon is more pronounced in large courses where instructors have limited capacity to provide individualized guidance on planning and task estimation. Although many planning tools exist, still, they rarely leverage task-specific, empirically grounded data from actual course contexts. Thus, we explored whether providing task-specific, data-driven information---assignment previews and cohort-level historical statistics---could support more effective planning. We present a lightweight and data-driven planning intervention embedded in the programming assignment workflow of an undergraduate computing course. We conducted quantitative and qualitative studies with 252 students across five programming assignments. Our results indicated that, in authentic course settings, the intervention led to more conservative and executable plans, with significantly higher plan adherence. Students with stronger adherence also achieved better performance on both programming assignments and exams. Qualitative findings also showed both practical planning support and mental benefits from intervention. These results highlight the potential of data-driven intervention to support student planning in larger courses settings where individual guidance from an instructor is further limited.

cs.CY · cs.HC

新论文 · v1arXiv:2611.05142

Tight Analysis of Randomized Truthful Scheduling: An $(m+1)/2$ Lower Bound

Wenqian Wang, Chenyang Xu, Yuhao Zhang

原文摘要

The Nisan-Ronen conjecture, a central problem in algorithmic game theory, asserts that no deterministic truthful mechanism for makespan minimization on $m$ unrelated machines can achieve an approximation ratio better than $m$. Christodoulou, Koutsoupias, and Kovács resolved it in 2023, but the optimal approximation ratio achievable by randomized truthful mechanisms remained open. Recently, Anastasiadis, Christodoulou, Koutsoupias, Kovács, and Schecker extended techniques from the deterministic proof to establish a $(3/2-\sqrt{2})(m-1)$ lower bound for universally truthful mechanisms with discrete support and gave a universally truthful mechanism with approximation ratio $m/2+o(m)$. For the broader class of truthful-in-expectation (TIE) mechanisms, however, the gap remained large: the best known upper bound was $(m+5)/2$, while the lower bound was only $2-1/m$. We prove a lower bound of $(m+1)/2$, determining the optimal TIE approximation ratio up to an additive constant as $m/2+Θ(1)$. Our result also improves the leading constant in the lower bound for universally truthful mechanisms from $3/2-\sqrt{2} \approx 0.0858$ to $1/2$. Together with their $m/2+o(m)$ upper bound, our result determines the optimal approximation ratio for universally truthful mechanisms up to lower-order terms.

cs.GT

版本更新 · v3arXiv:2601.19082

Payoff scaling shapes cooperation in LLM agents across languages

Trung-Kiet Huynh, Dao-Sy Duy-Minh, Thanh-Bang Cao, Phong-Hao Le, Hong-Dan Nguyen, Phu-Quy Nguyen-Lam, Minh-Luan Nguyen-Vo, Hong-Phat Pham 等 16 位作者

原文摘要

Large language models (LLMs) are increasingly deployed as autonomous agents that negotiate, coordinate, and make decisions on behalf of human users. Understanding how they cooperate is therefore important for AI governance and machine behaviour research. We examine two factors: payoff magnitude and interaction language. Classical game theory predicts that multiplying all payoffs by a positive constant should not change behaviour because the underlying strategic incentives remain unchanged. We test this prediction using five widely adopted commercial LLMs playing an iterated prisoner's dilemma across ten payoff scales and five languages (English, French, Vietnamese, Chinese and Arabic). Contrary to theoretical expectations, changing only the numerical scale of payoffs substantially alters cooperation. Models respond differently, often in opposite directions, meaning that averages across models can conceal important behavioural heterogeneity. Sensitivity to payoff scale also depends strongly on prompt language. Moreover, payoff scale modifies the effects of persona instructions: at sub-unit stakes, where no payoff shown exceeds 1, all five models cooperate more under a selfish than a cooperative persona, whereas Claude and Gemini reverse this pattern at larger scales. These findings show that cooperation measures depend critically on payoff scale and language and should not be treated as fixed model traits.

cs.AI · cs.CL · cs.GT · cs.LG · cs.MA

新论文 · v1arXiv:2611.05141

Beyond Foundation Models: PFN Priors Improve Tabular Hyperparameter Optimization

Artem Chistyakov, Renat Sergazinov, Artem Babenko

原文摘要

Synthetic priors have so far served one purpose: pretraining tabular foundation models. We ask whether the same priors can improve conventional tabular models, which are trained from scratch on each dataset. We propose PriorTune, a method that meta-tunes hyperparameter configurations on synthetic tasks alone. Offline, for a given model, we fit a pool of configurations on datasets sampled from a published PFN prior and greedily select the subset with the highest winrate over the random baseline. Online, a new dataset fits only the selected configurations, so the gain comes at no extra cost. Empirically, we observe that scaling both the number of configurations and synthetic datasets has an equal scaling effect on the performance of the final subset of configurations, which we also explain theoretically. On the full BeyondArena benchmark, LightGBM with TabPrep features with our configurations ranks above TabPFN-3 and RealMLP, while being much more efficient at inference. Overall, our results establish existing PFN priors as a scalable source of meta-training data for hyperparameter selection for non-foundational tabular models.

cs.LG

版本更新 · v2arXiv:2604.01305

UQ-SHRED: uncertainty quantification of shallow recurrent decoder networks for sparse sensing via engression

Mars Liyao Gao, Yuxuan Bao, Amy S. Rude, Xingyue Zhang, Xinwei Shen, J. Nathan Kutz

原文摘要

Reconstructing high-dimensional spatiotemporal fields from sparse sensor measurements is critical in a wide range of scientific applications. The SHallow REcurrent Decoder (SHRED) architecture is a recent state-of-the-art architecture that reconstructs high-quality spatial domain from hyper-sparse sensor measurement streams. An important limitation of SHRED is that in complex, data-scarce, high-frequency, or stochastic systems, portions of the spatiotemporal field must be modeled with valid uncertainty estimation. We introduce UQ-SHRED, a distributional learning framework for sparse sensing problems that provides uncertainty quantification through a neural network-based distributional regression called engression. UQ-SHRED models the uncertainty by learning the predictive distribution of the spatial state conditioned on the sensor history. By injecting stochastic noise into sensor inputs and training with an energy score loss, UQ-SHRED produces predictive distributions with minimal computational overhead, requiring only noise injection at the input and resampling through a single architecture without retraining or additional network structures. On complicated synthetic and real-life datasets including turbulent flow, atmospheric dynamics, neuroscience and astrophysics, UQ-SHRED provides a distributional approximation with well-calibrated confidence intervals. We further conduct ablation studies to understand how each model setting affects the quality of the UQ-SHRED performance, and its validity on uncertainty quantification over a set of different experimental setups.

cs.LG · cs.CE

新论文 · v1arXiv:2611.05139

Meta$^2$: Precomputing Reusable Knowledge for Online Harness Evolution in Long-Horizon Agents

Lingzhi Yuan, Yiguang Cai, Weize Liu, Siqi Yang, Feijiang Han, Yongkyun Lee, Udari Madhushani Sehwag, Furong Huang

原文摘要

Harness optimization improves long-horizon agents by refining the prompts, tools, memory, and hooks around a frozen model. Offline methods can learn from completed trajectories, but deploy one shared harness that may overfit training tasks and cannot react to evidence revealed during a new run. Online evolution can adapt before, during, or after one run through an evolver, but may have to reason about every intervention from scratch or rely on verifier feedback that is usually unavailable at test time. We introduce Meta$^2$, which moves offline optimization one level up: rather than optimizing a shared harness, it learns reusable knowledge for harness evolution and applies it within each task online. Offline, Meta$^2$ learns a textual Meta-Skill $M$ by contrasting training rollouts of the same task agent under three configurations: without an evolver, with an evolver guided by the current version of $M$, and with an evolver given privileged verifier information available only in training. Contrasts in trajectories and outcomes are aggregated across tasks to refine $M$ into reusable guidance on when and how to evolve, when to leave the harness unchanged, and which interventions to avoid. Online, an evolver combines the frozen $M$ with emerging trajectory evidence to decide whether to KEEP the harness unchanged or EVOLVE it through a task-local edit. Each edit applies to the rest of the same run without resetting its environment or progress. Thus, evolution guidance transfers across tasks while harness edits remain task-local, and held-out verifier feedback is never available to the evolver. On two long-horizon benchmarks, Terminal-Bench 2.1 and DeepSWE 1.1, Meta$^2$ achieves the highest performance among evaluated methods with GPT-5.6-Terra, reaching 81.00% and 44.44%, respectively. Ablations support the value of contrastive evolution guidance and keeping online harness edits task-local.

cs.AI

新论文 · v1arXiv:2611.05137

A Random Matrix Analysis of Symmetric Tensor Unfolding

Tom Szwagier, Xiaoyi Mai, José Henrique de Morais Goulart

原文摘要

We study a fundamental problem in machine learning: partial recovery of a planted signal $\boldsymbol{v} \in \mathbb{S}^{n-1}$ from a spiked tensor $\boldsymbol{\mathsf{X}} = λ\, \boldsymbol{v}^{\otimes p} + \boldsymbol{\mathsf{Z}}$, where $\boldsymbol{\mathsf{Z}}$ has symmetric Gaussian entries of variance $\asymp n^{-1}$. While previous works replace $\boldsymbol{\mathsf{Z}}$ by an i.i.d. standard Gaussian tensor to circumvent technical difficulties caused by dependencies, this paper directly analyzes the symmetric model via random matrix theory. We show that the square unfolding algorithm is subject to a sharp phase transition for partial recovery at $λ\asymp n^{(p-2) / 4}$, validating an open conjecture from Montanari and Richard (2014). We get precise expressions for the limiting spectral distribution, deterministic equivalent, phase transition threshold and overlap. The main message is that unfolded symmetric tensors spectrally behave like standard Wigner matrices, up to simple transformations accounting for high-order symmetries. We consider extensions to multiple orthogonal spikes, recursive unfolding and non-square unfolding via disproportionate random matrix theory, leading to an interesting conjectured statistical-computational tradeoff regarding the choice of unfolding: square versus long.

stat.ML · cs.LG · math.PR

新论文 · v1arXiv:2611.05135

From Opinions to Commitments: Unstable Assignments and Silent Choices in AI-Mediated Proposals

Sachit Mahajan, Javier Argota S{á}nchez-Vaquerizo, Arthur Capozzi, Dirk Helbing

原文摘要

Large language models (LLMs) are increasingly being used to turn citizens' opinions into collective proposals. These proposals can make assignments: who should act, what must be done, how much one should spend and by when. However, if the assignments change when the same opinions are processed again, publishing a single proposal can hide alternatives that participants never get to see. We examined this issue in four LLM mediators (three open-weight and one commercial) using opinions from DeliberationBank and Polis. For each task, a mediator drafted a proposal from thirty opinions five times, varying either the random seed or the order of the opinions. In 17% of five-run sets from the open-weight mediators and 20% from the commercial one, some runs contained assignments while others did not. Reordering the opinions changed the assignments almost as often as replacing them with opinions from different citizens. Three human annotators confirmed that the detected differences between runs were real, although the LLM judge overstated how often they occurred. Substantial variation remained under four safeguards: temperature zero, a commercial mediator, draft selection, and draft merging. The mediator's objective also shaped representation: prompts seeking agreement covered minority positions much less often than prompts asking to describe differences. A single proposal can therefore obscure choices in both the assignments it proposes and the views it excludes. We propose audits that make alternative assignments visible and disclose the objective behind each proposal.

cs.AI · cs.HC

新论文 · v1arXiv:2611.05134

Sharp Bounds for Truthful-in-Expectation Scheduling

Yunpeng Li

原文摘要

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

cs.GT