跳到正文
研踪PaperTrail

版本更新

查看已发布论文的最新修订,在详情页对照实际观测到的版本。

部分采集异常

全站更新概况

+1085新增论文
+884其中 AI 相关
+130已有论文修订
+94新增 AI 导读

arXiv 最近完成扫描:2026-11-19 06:59 · 全站最近入库:2026-11-19 06:59各信源进度 →

统计口径与数据新鲜度

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

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

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

26,871 已收录论文22,375 AI 相关8,156 有修订112 HF 社区发现

论文修订列表

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

找到 8,156 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-19 06:57(北京时间)
版本更新 · v2arXiv:2609.04273

Scalable Neural Video Representation Compression

Tianhao Peng, Ho Man Kwan, Fan Zhang, Shan Liu, David Bull

原文摘要

Scalable video coding (SVC) encodes a video into a layered bitstream of a base layer and one or more enhancement layers, enabling decoding at different bitrate/quality/resolution operating points for diverse devices and network conditions. SVC has been incorporated into major video coding standards and has recently attracted growing interest for both scene-agnostic and scene-adaptive neural video codecs. Among the latter, implicit neural representation (INR) based codecs overfit a compact neural network to an individual video, offering fast decoding and competitive coding efficiency. However, research on scalable INR-based compression remains in its infancy: existing methods introduce additional network layers, which couple the bitrate with the decoding complexity and cannot match strong scalable/non-scalable codecs. This paper proposes S-NVRC, a scalable INR-based video codec that jointly supports fine-grained bitrate and decoding complexity scalability from a single embedded bitstream. It adopts a coarse-to-fine prefix for feature grids and a nested prefix for network layers, which scale bitrate and decoding complexity, respectively. With a single encoding, S-NVRC spans a wide range of bitrate and decoding complexity and outperforms SHM-12.4 and the multi-layer VTM-20.0 by 43.7% and 5.6% in BD-rate on the UVG dataset.

eess.IV · cs.CV · cs.MM

版本更新 · v3arXiv:2604.05152

Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances

Renan Fernando Franco da Silva, Vinícius Loti de Lima, Rafael C. S. Schouery, Jean-François Côté, Manuel Iori

原文摘要

The Bin Packing Problem (BPP) and Cutting Stock Problem (CSP) are classical combinatorial optimization problems extensively studied since the 1960s. State-of-the-art exact algorithms are based on set-cover and arc-flow models whose linear relaxation, rounded up, matches the integer optimum for most benchmark instances, a condition known as the Integer Round-up Property (IRUP). In 2016, Delorme et al. showed that most existing instances could be solved within ten minutes by approaches exploiting this property. This motivated them to introduce two new classes of instances, Augmented IRUP (AI) and Augmented Non-IRUP (ANI), designed to challenge the exact algorithms available at the time. Although these classes have motivated significant advances over the past decade, 13 out of 500 AI and ANI instances remain unsolved within standard time limits in the literature. In this paper, we show that while AI and ANI are particularly hard for mixed-integer programming methods, the BPP restricted to these classes is not strongly NP-hard. We present polynomial-time algorithms for the AI class and pseudopolynomial-time algorithms for the ANI class, which solve all such instances orders of magnitude faster than previous approaches. They are also straightforward to adapt to the Skiving Stock Problem, the dual counterpart of the CSP. In addition, they can be used as preprocessing routines in exact methods, as their runtime is independent of the instance class, although they are guaranteed to return an optimality status only for instances belonging to the class for which they were designed.

cs.DS

版本更新 · v2arXiv:2611.00290

Quantifying Local and Global Fidelity of Nonlinear Embeddings

Henry Han

原文摘要

Dimension reduction rests on a claim: t-SNE and UMAP preserve local structure, PCA global structure. Our DLP curve is the share of each point's k nearest neighbors a map keeps. Corrected for chance, it gives L at k=10 and G over 30 to 50% of the data, local and global fidelity. At the midpoint the curve is provably a rank correlation of distances. The LG reversal test decides, with a stated error rate, which of two maps is local and which global. On twelve datasets of up to 1.38 million points, G agrees with established global scores at 0.84 and 0.93, and the area under R_NX at 0.22 and 0.30. The entity fidelity E, read at each point's entity size, predicts which entities a map loses beyond L and G where entity sizes differ. In an agent memory of one million passages, t-SNE and PCA cross at 150,000 passages (p=2.6e-5).

cs.AI

版本更新 · v2arXiv:2610.12702

Product Monte Carlo: Expectation Under a Product of Densities

Pietro Carlotti, Sifan Liu, Yuling Yao

原文摘要

Aggregating independently computed sub-sample inferences is a well-known challenge in large-scale Bayesian computation, federated learning, and opinion pooling. The core problem is to approximate a distribution whose density is proportional to a product of individual densities. We propose Product Monte Carlo (PMC), an algorithm for computing arbitrary expectations under a product of densities using only Monte Carlo draws from individual densities. We turn the intractable product expectation into a regression problem by expressing it through a family of computable conditional expectations. Besides the point estimate, our fully Bayesian regression formulation provides coherent uncertainty quantification and principled diagnostics. We establish theoretical guarantees on consistency and characterize convergence rates for the PMC estimator. Across simulated and real-data experiments varying the number, dimensionality, and heterogeneity of the component distributions, PMC achieves higher estimation accuracy, better-calibrated uncertainty coverage, and improved scalability at a lower computational cost than existing methods. In addition, PMC requires no density evaluation, making it applicable to simulation-based inference, as we demonstrate in an application with protein images.

stat.ME · cs.LG · stat.CO

版本更新 · v2arXiv:2606.28315

Pairwise Reflection Symmetry in Frequency Rectangles

Enrico Iurlano, Günther R. Raidl

原文摘要

Many combinatorial designs ask for equal distribution of given symbols across the entries of a matrix. The paramount examples are Latin squares, where each symbol from $\{1,\dots,n\}$ appears once per row and column of an $n\times n$ matrix. Frequency rectangles extend this to $λn \times μn$ matrices with repeated symbols under controlled column and row frequencies. In this more general setting, we examine structural properties of pairwise reflection-symmetry, which requires that, on every pair of columns, each ordered symbol pair $(p,q)$ occurs as often as its reversal $(q,p)$. This order-balance is precisely what makes head-to-head comparisons unbiased, i.e., no symbol gains a systematic advantage from the position it occupies relative to another, a fairness demand arising for instance when scheduling tournaments or laying out comparative trials. Existence of such objects for odd $λ$ turns out to be remarkably more subtle than for even $λ$. After showing that existence holds also for sufficiently large odd $λ$, we initiate the search for the smallest possible value of $λ$ in this setting. We obtain the insight that a per-column multiplicity of $λ=1$ can be achieved if and only if $n$ is a power of two. We complement the existence results with a direct product construction and add several further observations on the property. Finally, we propose and evaluate a quadratically constrained integer program to computationally search for these objects. The resulting experiments reveal that many of them possess an underlying group-theoretic structure which, as we conjecture, may even be unavoidable in certain settings.

cs.DM · math.CO

版本更新 · v5arXiv:2605.14381

NodeSyn: Socially Aligned Synthetic Data for AI Evaluation

Qazi Mamunur Rashid, Xuan Yang, Zhengzhe Yang, Yanzhou Pan, Erin van Liemt, Darlene Neal, Kshitij Pancholi

原文摘要

Recent advancements in generative AI facilitate large-scale synthetic data genera- tion for model evaluation. However, without targeted approaches, these datasets often lack the sociotechnical nuance required for sensitive domains. We introduce NodeSyn, an evidence-grounded methodology that generates socially relevant syn- thetic queries by leveraging a fine-tuned taxonomy generator (TaG) anchored in real-world evidence. Evaluated against four mainstream LLMs, NodeSyn elicited failure rates up to five times higher than human-authored benchmarks. Ablation studies confirm that our granular taxonomic expansion significantly drives these failure rates, while independent validation reveals critical deficiencies in prominent guard models.

cs.LG · cs.CL

版本更新 · v2arXiv:2606.09788

POTATR: A Lightweight Image-to-Graph Model for Page-Level Table Extraction

Brandon Smock, Libin Liang, Maxim Sokolov, Amrit Ramesh, Valerie Faucon-Morin, Tayyibah Khanam, Maury Courtland

原文摘要

Large-scale document processing requires contextually aware table extraction (TE) that is both accurate and efficient. Yet current approaches require billions of parameters, hundreds of autoregressive steps, or costly API inference. Motivated by this, we introduce the Page-Object Table Transformer (POTATR), a lightweight 29M parameter image-to-graph model that extends the Table Transformer (TATR) for contextualized page-level TE. POTATR outperforms all models tested on the PubTables-v2 Single Pages benchmark -- including frontier MLLMs -- achieving $\textrm{GriTS}_\textrm{Con}$ of 0.964 while running over 130$\times$ faster at 300$\times$ lower cost. Further, POTATR's output is spatially grounded: every recognized element has a bounding box, enabling visual verification and geometric text assignment. As a result, POTATR performs unified page-level TE while composing with other models, enabling extension to scanned documents via external OCR and to full-document TE via techniques like cross-page merging. Code and models are available at https://github.com/kensho-technologies/POTATR.

cs.CV

版本更新 · v2arXiv:2604.14191Apple ML Research

Attention to Mamba: A Recipe for Cross-Architecture Distillation

Abhinav Moudgil, Ningyuan Huang, Eeshan Gunesh Dhekane, Pau Rodríguez, Luca Zappella, Federico Danieli

原文摘要

State Space Models (SSMs) such as Mamba have become a popular alternative to Transformer models, due to their reduced memory consumption and higher throughput at generation compared to their Attention-based counterparts. On the other hand, the community has built up a considerable body of knowledge on how to train Transformers, and many pretrained Transformer models are readily available. To facilitate the adoption of SSMs while leveraging existing pretrained Transformers, we aim to identify an effective recipe to distill an Attention-based model into a Mamba-like architecture. In prior work on cross-architecture distillation, however, it has been shown that a naïve distillation procedure from Transformers to Mamba fails to preserve the original teacher performance, a limitation often overcome with hybrid solutions combining Attention and SSM blocks. The key argument from our work is that, by equipping Mamba with a principled initialization, we can recover an overall better recipe for cross-architectural distillation. To this end, we propose a principled two-stage approach: first, we distill knowledge from a traditional Transformer into a linearized version of Attention, using an adaptation of the kernel trick. Then, we distill the linearized version into an adapted Mamba model that does not use any Attention block. Overall, the distilled Mamba model retains most of the original Pythia-1B Transformer performance, reaching a perplexity of 14.01 close to the teacher's 13.86. This largely carries over to downstream tasks, although some gaps appear on tasks relying more on in-context recall. To show the efficacy of our recipe, we conduct thorough ablations at 1B scale with 10B tokens varying sequence mixer architecture, scaling analysis on model sizes and total distillation tokens, and a sensitivity analysis on tokens allocation between stages.

cs.CL · cs.LG

版本更新 · v2arXiv:2606.26421

Otter Weather: Skillful and Computationally Efficient Medium-Range Weather Forecasting

Cristiana Diaconu, Jonas Scholz, Aliaksandra Shysheya, Stratis Markou, Payel Mukhopadhyay, Miles Cranmer, Richard E. Turner

原文摘要

State-of-the-art medium-range AI weather models can outperform traditional Numerical Weather Prediction (NWP) but require massive training budgets. This restricts usage for under-resourced groups and severely limits fast model iteration. Here we develop Otter Weather, a highly efficient spatiotemporal forecasting model designed to democratise high-performance weather prediction with AI. Evaluated on ERA5 reanalysis data at 1.5° resolution using standard WeatherBench protocols, the Otter family significantly advances the skill-compute Pareto frontier. The deterministic version outperforms the best NWP baseline by 9.6% at a 24-hour lead time while requiring fewer than 3.5 A100-days for training. It provides a 2x efficiency gain over lightweight AI models and a 100-fold reduction in compute compared to resource-intensive frontier architectures. We extend these efficiency gains into probabilistic forecasting by training via the Continuous Ranked Probability Score (CRPS). Scaling to a larger architecture, Otter-XL achieves a 9.7% CRPS improvement over the IFS ENS baseline. This yields an almost two-fold increase in predictive skill over comparable lightweight models at similar compute budgets. Otter-XL also outperforms frontier architectures like GenCast by over 2%, while using an order of magnitude less compute. Finally, Otter is applied out-of-the-box to a complex acoustic scattering PDE task where it outperforms a state-of-the-art foundation modelling approach, suggesting that the advances made here might apply across a range of scientific domains.

cs.LG · cs.CE

版本更新 · v2arXiv:2610.24973

A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions

Yichen Huang

原文摘要

We study simple auctions for one additive bidder whose values for $m$ items are independent. Write $\mathrm{REV}$ for the optimal revenue, $\mathrm{SREV}$ and $\mathrm{BREV}$ for the optimal revenues from separate selling and grand bundling, and $\mathrm{BSPA}_2$ for the grand-bundle second-price revenue with two independent bidders. For independent regular items, we prove $\mathrm{REV} \le \mathrm{BSPA}_2 \le 2\,\mathrm{BREV}$. Thus, one additional bidder lets a reserve-free second-price auction for the grand bundle match the optimal revenue from one bidder, regardless of the number of items. This gives a Bulow-Klemperer theorem for bundling and resolves an open question of Beyhaghi, Cai, Feng, Li, and Weinberg (EC 2025) on whether constant competition suffices for bundling. The factor-$2$ bundling approximation is also tight. For general independent items, we prove $\mathrm{REV} \le \mathrm{SREV} + \frac{π^2}{6}\mathrm{BREV} \le 2.645 \max\{\mathrm{SREV}, \mathrm{BREV}\}$. This improves the previous approximation factors of $6$ from Babaioff, Immorlica, Lucier, and Weinberg (FOCS 2014, JACM 2020) and $5.2$ from Ma and Simchi-Levi (AISTATS 2021). For the lower bound, we construct an instance in which pricing three disjoint bundles earns more than $2.11\max\{\mathrm{SREV},\mathrm{BREV}\}$, improving the previous lower bound of $2$ from Rubinstein (ITCS 2016). Together, these results narrow the tight approximation ratio to the range $[2.11, 2.645]$.

cs.GT · econ.TH

版本更新 · v4arXiv:2606.28079

GTI-mSEMP Framework : A Proposed Framework to Simulate Malware Propagation with Inclusion of Attacker-Defender Strategy

Shadeeb Hossain, Elias Calboreanu, Kristopher Wilson

原文摘要

The rapid proliferation of automated, multi-vector malware threats poses a significant risk to heterogeneous, resource constrained cyber-physical networks. Conventional epidemiological models often treat security defenses as static parameters, failing to capture the strategic, asymmetric maneuvers between an attacker and a defender. To address the gap, this paper proposes a Game-Theory-Integrated Modified Multi- Wireless Sensor Epidemic Malware Propagation (GTI-mSEMP) framework. This paper analyzed and compared the operational trajectories of Susceptible (S) and Recovered (R) node populations across three different operational regimes: Balanced Matchup, Exploit Surge and Hardened Defense. Numerical simulation results capture the real-time transient dynamics of the network state variables, demonstrating how the epidemic curve shifts when either the defensive or offensive scaling vectors hold an efficiency advantage. The proposed mathematical and numerical framework provides a rigorous foundation that can be deployed in highly adversarial network environments to evaluate dynamic malware propagation and predict localized node population states.

cs.CR · cs.GT · cs.NI

版本更新 · v2arXiv:2609.13044

Robust Policy Optimization via Adversarial Importance Sampling

Amine Andam, Jamal Bentahar, Mustapha Hedabou

原文摘要

Significant progress has been made in safeguarding Deep Reinforcement Learning (DRL) policies against input perturbations. Developing robust DRL involves three main stages: algorithm design, implementation, and evaluation. In this work, we identify and address a key limitation at each stage. First, we introduce Adversarial Importance Sampling (Advis), a method that estimates and optimizes worst-case returns directly from trajectories already collected during standard training. Advis satisfies three desirable criteria that prior work does not jointly achieve: it requires no additional environment interactions, no auxiliary networks, and captures long-term robustness. Second, we introduce advrl, a modular PyTorch library that provides clean, single-file implementations of existing robustness methods and adversarial attacks, enabling rapid prototyping and reproducible evaluations. Third, we revisit evaluation under learned adversaries and show that optimal adversarial hyperparameters do not transfer across agents, which can lead to an overestimation of robustness when using a limited set of attacker configurations. Accordingly, we evaluate policies against a large and diverse set of attackers, using 6 to 14 times more configurations than prior work. Finally, experiments on continuous control environments show that Advis achieves stronger worst-case performance and greater training efficiency than existing baselines.

cs.LG

版本更新 · v2arXiv:2610.34651

Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions

Yegor Gorodzha, Steven Hoehner, Gil Kur

原文摘要

We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball $B_d\subset\mathbb R^d$ with relative symmetric-difference volume error at most $\varepsilon\in(0,1)$. We show that the minimum vertex budget $N_\varepsilon(d)$ satisfies $$\log N_\varepsilon(d)\asymp d\log\left(1+\frac1{\varepsilon\sqrt d}\right).$$ In particular, $\exp(O(\sqrt d/\varepsilon))$ vertices suffice for every $\varepsilon\in(0,1)$ and all sufficiently large $d$. We also prove that achieving a fixed error $\varepsilon\in(0,1)$ requires at least $Ω\bigl((\tfrac{1+\varepsilon}{2\sqrt\varepsilon})^{d-1}\bigr)$ facets, an exponential number in $d$. We extend our vertex approximation result to Gaussian symmetric-difference error, and give a positive answer to the question of De, Nadimpalli, and Servedio about subexponential vertex complexity for approximating Euclidean balls. We also disprove a Macbeath-type extremality principle for unrestricted vertex approximation. Whereas the ball uniformly maximizes the inscribed approximation error among all convex bodies (Macbeath, 1951), we show that approximating the hypercube $[-1,1]^d$ to relative error $\varepsilon$, with $δ:=1-\varepsilon$, requires $N\ge\fracδ{2}\exp(Ω(δ^2d/\log^2(2/δ)))$ vertices whenever $d\ge16\log(2/δ)$. Thus, when $d$ is large, the cube is harder to approximate than the ball in this sense. Finally, we determine the sharp dimensional order of the classical Laguerre-Delone triangulation number, showing that $\mathrm{ldel}_{d-1}=Θ(d^{-1/2})$ as $d\to\infty$. This improves both the upper bound of Ludwig, Schütt, and Werner and the lower bound of Böröczky by a factor of order $\sqrt d$. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in $\mathbb R^d$ with $C^2$ boundary and positive Gaussian curvature.

math.MG · cs.CG · cs.LG · math.PR

版本更新 · v2arXiv:2608.07163

Rate-Fidelity Control for Wide-Area Quantum Links

Connor Clayton, Cory Nunn, Quinn Carmack, Wayne McKenzie, Anne Marie Richards, Xiaodi Wu, Bobby Bhattacharjee

原文摘要

Quantum network links must distribute entanglement at high rates while satisfying application-specified fidelity demands. However, wide-area deployed fiber links suffer from polarization drift which destabilizes end-to-end fidelity and forces periodic compensation. Current deployments often use active stabilization with fixed control policies, and improvements generally stem from advances in quantum hardware. Meanwhile, software control remains relatively underexplored. Here, we formulate quantum link operation as a joint control problem over tunable rate-fidelity tradeoffs and uncontrollable link drift. From this framework, we construct a link control protocol that dynamically adapts source pump power and polarization compensation to maximize entanglement distribution rate subject to a minimum fidelity constraint. We evaluate the protocol through trace-driven simulations driven by data from a 64 km deployed optical fiber. Compared with optimized static policies, our adaptive controller improves mean entanglement distribution rate by 14% over a 24 hour trace, without requiring any offline policy optimization. Our results show that software-based physical layer control can provide a practical mechanism for improving near-term quantum link performance without requiring additional quantum hardware.

quant-ph · cs.NI

版本更新 · v4arXiv:2512.10888

PubTables-v2: A new large-scale dataset for full-page and multi-page table extraction

Brandon Smock, Maxim Sokolov, Libin Liang, Valerie Faucon-Morin, Amrit Ramesh, Tayyibah Khanam, Maury Courtland

原文摘要

Table extraction (TE) is a key challenge in document understanding. Traditional approaches detect tables first, then recognize their structure. Recently, interest has surged in developing methods, such as vision-language models (VLMs), to extract tables directly in their full page or document context. However, a lack of annotated data has made progress difficult to demonstrate. To address this, we create a new large-scale dataset, PubTables-v2. PubTables-v2 unifies TE across various levels of surrounding context and, notably, is the first benchmark for multi-page TE. Our evaluations reveal that while current frontier models strongly outperform ($+0.354\ \textrm{GriTS}_\textrm{Con}$) small models on the most complex task (full-document multi-page TE), this gap can be closed or even reversed ($-0.056\ \textrm{GriTS}_\textrm{Con}$) on narrower tasks (cropped table extraction) with targeted training. Data is available at https://huggingface.co/datasets/kensho/PubTables-v2.

cs.CV

版本更新 · v2arXiv:2610.17154

Neuromorphic Decoding and Dynamical Image Reconstruction from Populations of Spiking Retinal Ganglion Cells

Ning Zhang, Arto Nurmikko

原文摘要

Decoding visual stimuli from the spiking activity of retinal ganglion cells (RGCs) informs both our understanding of the retinal code and the design of visual prostheses. Natural vision is dynamic, yet state-of-the-art decoders mostly reconstruct single frames with artificial neural networks that process dense, continuous-valued signals rather than the retina's sparse, asynchronous spikes. We asked whether dynamic scenes can be reconstructed and tracked entirely within the spike domain, and at what computational cost. We built an end-to-end spiking neural network (SNN) whose neurons integrate the recorded RGC spikes over time. Populations of up to 1836 RGCs were recorded ex vivo from mouse retina on high-density microelectrode arrays while flashed images, moving bars, drifting gratings and randomly moving handwritten digits were presented. For moving digits, one shared spiking encoder fed two readouts, one reconstructing the image and one decoding the digit's position. Compute energy was estimated from counted synaptic operations. The SNN decoded what and where at once. It reconstructed the stimuli with a structural similarity (SSIM) of up to 0.93, refining the reconstruction as spikes accumulated, and tracked a randomly moving target with a mean error of 1.33 pixels on a $32\times32$ grid. Its fidelity nearly matched that of the best of 17 larger spiking and artificial decoders (5.9 million to 1.7 billion parameters, versus 5.4 million), and at a mean firing rate of 14.2% it needed an estimated $\sim$70-fold less compute energy than a dense artificial network of the same architecture. Dynamic visual scenes can thus be decoded from retinal population activity in the spike domain, with a compact network and at a compute cost compatible with implantable and wearable neural interfaces, supporting spike-native decoders for visual prostheses.

cs.ET · cs.LG · eess.SP

版本更新 · v4arXiv:2609.14101

On the Complexity of Finding Fixed Points for Set-Valued Contractions

Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong

原文摘要

We study the computational complexity of finding fixed points of set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem, PROJECTED-NADLER, and prove that it is CLS-complete by showing its equivalence to CONTINUOUS-LOCALOPT. We then establish a stronger converse to Nadler's theorem, which can be applied as a tool to analyze the convergence rate of the set-valued basic iteration procedure. Finally, we reduce the large-margin triplet stationarity problem to PROJECTED-NADLER. Combining the argument for CLS-hardness of exact triplet stationarity problem [Yan et al. 2025] with the CLS-hardness of approximate KKT points of quadratic programs [Fearnley et al. 2025], we obtain CLS-completeness of large-margin triplet stationarity at any prescribed accuracy.

cs.CC · math.GN

版本更新 · v3arXiv:2606.18902

SAGE: Stochastic Prompt Optimization via Agent-Guided Exploration

Ziyi Zhu, Luka Smyth, Saki Shinoda, Jinghong Chen

原文摘要

Context engineering has emerged as a primary lever for improving AI systems without parameter updates. Recent work showing that textual gradients do not function as real gradients motivates treating automatic prompt optimization (APO) as black-box search. We introduce SPO (Stochastic Prompt Optimization), a framework for stochastic search over prompt space, and compare three strategies of increasing sophistication: error-informed random search, a genetic algorithm with evolutionary operators, and SAGE (SPO via Agent-Guided Exploration), a multi-agent pipeline with diagnostic code execution. Across three benchmarks, no single strategy dominates; effectiveness depends on the interaction of landscape structure with error type. We further deploy SAGE on a mental-health chatbot under a continuous optimization paradigm, where it compounds eight cycles of individually-noisy A/B tests into a statistically robust gain in next-day retention. We argue that coupling qualitative diagnosis with quantitative validation is what makes agentic optimization effective for open-ended task-oriented dialogue.

cs.CL

版本更新 · v2arXiv:2607.01546

The General Stability of Ranking

Houming Chen, H. V. Jagadish

原文摘要

Rankings derived from weighted scoring functions are widely used in university rankings and employment candidate evaluations. Since ranking weights are often chosen by organizations or analysts, ranking stability asks whether a reported ranking persists under reasonable weight changes. Prior work defines volume-based stability as the fraction of the weight space that induces the target ranking exactly. This exact-match requirement can be too blunt: once a perturbed weight vector produces a different ranking, exact stability gives it no credit, whether the change replaces the top-ranked item or only swaps two nearly tied lower-ranked items. We propose general stability, a distance-based generalization that aggregates ranking regions according to a user-defined distance from the target ranking. This lets users specify which ranking changes matter in the application, while recovering exact stability as a special case. We extend existing methods and identify distance properties that permit faster general-stability computation with accuracy guarantees. Our sampling algorithm, $GSC_{md}$, can take exponential time in the worst case, but a property we call uniform boundedness gives a sample budget independent of database size and dimension at fixed accuracy and confidence. We develop Prefix-GSC, a sampling optimization that reduces sorting for distances satisfying a further property, tail decay with bounded influence. We also develop Conv-SC to approximate stability through convex volumes for distances satisfying a property we term quasiconvexity. Experiments on seven real-data sources and generated inputs show how distance affects robustness conclusions and when the algorithms save time. On three 500-item university datasets, Prefix-GSC achieves median query speedups of $1.22$--$1.98\times$ over $GSC_{md}$ at 2% relative error and 95% confidence, including method setup.

cs.DB

版本更新 · v4arXiv:2603.01865

CyclicJudge: Mitigating Judge Bias Efficiently in LLM-based Evaluation

Ziyi Zhu, Olivier Tieleman, Alexey Bukhtiyarov, Jinghong Chen

原文摘要

LLM-as-judge evaluation has become standard practice for open-ended model assessment; however, judges exhibit systematic biases that cannot be averaged out by increasing the number of scenarios or generations. These biases are often similar in magnitude to the model differences that benchmarks are designed to detect, resulting in unreliable rankings when single-judge evaluations are used. We introduce a variance decomposition that partitions benchmark score variance into scenario, generation, judge, and residual components. Based on this analysis, CyclicJudge, a round-robin assignment of judges to scenarios, is demonstrated to be the optimal strategy for a fixed judge panel and judge-call budget: it cancels the average additive judge offsets while matching the cost of single-judge evaluation. Empirical results on MT-Bench and MindEval validate the effectiveness of CyclicJudge as predicted, across both general-purpose and domain-specific evaluation settings, reducing benchmark score variance and stabilizing the resulting model ranking.

cs.CL

版本更新 · v3arXiv:2610.34474

Unconditional Lower Bounds for the Fredman--Khachiyan Algorithms for Monotone Boolean Duality Testing

Khaled Elbassioni

原文摘要

We prove unconditional lower bounds on the number of recursive calls made by the two algorithms of Fredman and Khachiyan (1996) for monotone Boolean duality testing, as a function of the explicit input size $N$. For Algorithm A we show a lower bound of $N^{Ω(\log N)}$ on the dual pairs $(\HH_k,\LL_k)$ obtained from the read-once family of Gurvich and Khachiyan. The proof lower-bounds the number of leaves of every binary decision tree computing the function by the modulus of its multilinear polynomial evaluated at a complex point of the unit circle. It therefore applies to every choice of branching variables and, more generally, to the class of two-child variable-restriction procedures whose terminal calls have polynomially bounded decision-tree complexity. On this family the number of calls is exactly $N^{Θ(\log N)}$. For Algorithm B, a symmetric specialization of the polynomial padding construction of Kobayashi, Kurita, and Wasa, with full polynomial blocks, yields at least $q^{(t-1)k-t(t-1)/2}$ calls, where $k=4t^2$ and $q=Θ(t^2)$; as a function of $N$ this is $N^{Ω(\sqrt{\log N/\log\log N})}$ along an infinite family. The same padded family forces Berge multiplication, for every edge ordering, to generate an intermediate family of size $N^{Ω(\sqrt{\log N/\log\log N})}$. In an appendix we show that applying the padding construction directly to Algorithm A gives $Ω(2^n)$ calls on a dual pair obtained from an unsatisfiable $n$-variable formula, which is only $N^{Ω(\sqrt{\log N/\log\log N})}$ in terms of the input size. No complexity-theoretic assumption is used. The proofs allow every branching-variable choice permitted by the respective algorithm. They concern the original recursive procedures, counting every invocation separately, without sharing calls or adding positive stopping tests.

cs.CC · cs.DS

版本更新 · v3arXiv:2508.09275

Constrained Black-Box Attacks Against Cooperative Multi-Agent Reinforcement Learning

Amine Andam, Jamal Bentahar, Mustapha Hedabou

原文摘要

Collaborative multi-agent reinforcement learning (MARL) is increasingly deployed in critical domains, yet its vulnerability to adversarial perturbations has not been thoroughly investigated. Most existing adversarial attacks against MARL rely on optimistic assumptions, such as access to policy weights or the ability to train surrogate policies. We investigate whether adversaries with limited capabilities remain effective against MARL agents. In particular, we study two restricted attack settings that are overlooked in the literature: (i) adversaries with access only to agent observations and (ii) adversaries with no access whatsoever. Our approach generates perturbations that intentionally misalign how victim agents perceive their environment, preventing them from collaborating. We conduct extensive experiments across a diverse set of 22 environments. Our results demonstrate both the effectiveness and sample efficiency of our attacks.

cs.LG · cs.MA

版本更新 · v3arXiv:2606.11319

Neural networks become centroid classifiers when trained on heavily corrupted inputs

Justin Tahmassebpur, Asadullah Bhuiyan, Hyejin Kim, Omri Lesser

原文摘要

Learning from imperfect data is a central theme in machine learning, connecting practical questions of robustness to fundamental questions of learnability. Here we examine attribute noise: learning from corrupted inputs while keeping the labels intact, a setting that has received considerably less analytical attention than its label-noise counterpart. We consider two types of corruption models: additive noise and replacement noise. Through experiments with multi-layer perceptrons (MLPs) on corrupted classification datasets, we find that neural networks remain robust, maintaining well-above-chance accuracy even when inputs are >90% corrupted -- far beyond human recognition. To understand this robustness, we analyze infinite-width networks in the heavy-corruption regime using a mean-field-inspired approach and derive a leading-order decision rule for the classification outcome: the network implements a prototype rule, the nearest-class-mean, assigning each test point to the class whose training-set average it most closely resembles. This leading-order decision rule is universal across a broad range of MLP architectures, holding for any depth, as well as a wide class of activation functions and noise distributions. The same centroid mechanism closely matches finite-width network behavior in our experiments and provides an interpretable and analytically tractable account of why learning can succeed even when individual training examples carry almost no signal.

cs.LG · cond-mat.dis-nn

版本更新 · v2arXiv:2610.21257

Fractional Power-of-Two Quantization for Efficient and Effective Multiplier-Free LLM Inference

Sunghyun Wee, Geunjae Choi, Hyeonjin Kim, Suyoung Kim, Nojun Kwak

原文摘要

Large Language Models (LLMs) demand efficient inference, where the multiply-accumulate (MAC) operations in linear projections dominate compute and energy cost. Post-training quantization (PTQ) reduces this cost by mapping weights and activations to low-bit integers. Power-of-Two (PoT) weight quantization promises efficient multiplier-free LLM inference via shift-add logic, but suffers significant accuracy degradation at low bit-widths due to its coarse base-2 quantization grid. We introduce Fractional PoT (FPoT), a base-$\sqrt{2}$ (half-octave) fractional PoT grid that achieves practical 4-bit weight quantization while preserving a fully integer shift-add datapath. The method combines (i) the base-$\sqrt{2}$ weight grid with uniform integer activations, (ii) a calibration-time grid-alignment refinement absorbed into the static per-channel scale, and (iii) a lightweight 1-adder $\sqrt{2}$ approximation whose error is absorbed during weight calibration via approximate-grid quantization, yielding a processing element (PE) with significantly fewer gates than a 4-bit integer multiplier. On Llama-3-8B with 4-bit weight and activation quantization, FPoT improves zero-shot commonsense reasoning performance by 8.72% relative to the PoT baseline, while maintaining performance close to the uniform integer baseline, with only a negligible 0.4%p degradation. These results hold across various configurations spanning seven models and three bit-widths. Furthermore, FPoT can be integrated with state-of-the-art LLM PTQ methods, demonstrating framework-agnostic applicability.

cs.LG · cs.AI

版本更新 · v2arXiv:2609.09502

Recovery Theory for Projected Power Iterations in Permutation Synchronization

Vahan Huroyan, Gilad Lerman

原文摘要

We study the projected power method for permutation synchronization: recovering $n$ unknown permutations of $m$ objects from pairwise relative permutations, observed independently with probability $p$ and independently corrupted by uniform permutations with probability $1-π_0$. Our main theorem establishes uniform one-step contraction for all estimates with optimally aligned block-error fraction at most $1/2-ε$, for fixed $ε>0$, including measurement-dependent estimates. When $np\ge C_0\log(n)$ and $m=o(npπ_0^2)$, one update contracts the error by a factor $O(m/(npπ_0^2))$, up to a floor of $O(e^{-c\min\{m\,npπ_0^2,\,npπ_0\}} + \log(n) / n)$. Thus, every initialization in this majority basin achieves $o(1)$ error after one update and maintains it uniformly over subsequent iterations. A reference-block spectral initializer enters the basin with probability $1-o(1)$, yielding end-to-end almost-exact recovery. If additionally $\min\{m\,npπ_0^2,\,npπ_0\} \ge C\log(n)$ for sufficiently large $C$, the method achieves exact recovery in finitely many iterations. We also establish prescribed-block recovery under weaker conditions for measurement-independent estimates and extend the guarantees to independent permutation-valued corruptions with uniform mean and to partial permutations with common visible support.

stat.ML · cs.IT · math.OC

版本更新 · v3arXiv:2507.10880

Domain-Adaptive Small Language Models for Structured Tax Code Prediction

Souvik Nath, Sumit Wadhwa, Luis Perez

原文摘要

Every day, multinational firms process thousands of transactions, each of which must adhere to tax regulations that vary by jurisdiction and are often nuanced. The determination of product and service tax codes, such as HSN or SAC is a major use case in Tax compliance. An accurate determination of such codes is imperative to avoid any tax penalties. This paper proposes a domain-adaptive small language model (SLM) with an encoder-decoder architecture for the enhanced prediction of product and service tax codes. In this approach, we address the problem of predicting hierarchical tax code sequences using unstructured product and services data. We employ an SLM based upon encoder-decoder architecture as this enables sequential generation of tax codes to capture the hierarchical dependencies present within the tax codes. Our experiments demonstrate that encoder-decoder SLMs can be successfully applied to the sequential prediction of structured tax codes, a domain that remains comparatively unexplored in current NLP research. In this paper, we demonstrate the superior performance of the domain-adaptive encoder-decoder SLMs over flat classifiers when applied to the Harmonized System of Nomenclature (HSN), and achieve superior results compared to decoder-only and encoder-only architectures for structured sequence generation tasks. This approach can also be scaled to other government-mandated tax commodity codes, such as United Nations Standard Products and Services Codes (UNSPSC), or Brazil's Nomenclatura Comum do Mercosul (NCM).

cs.LG · cs.CL

版本更新 · v5arXiv:2512.20773

DIAL: Direct Iterative Adversarial Learning for Realistic Multi-Turn Dialogue Simulation

Ziyi Zhu, Olivier Tieleman, Caitlin A. Stamatis, Luka Smyth, Thomas D. Hull, Daniel R. Cahn, Jinghong Chen, Matteo Malgaroli

原文摘要

Realistic user simulation is crucial for training and evaluating multi-turn dialogue systems, yet creating simulators that accurately replicate human behavior remains a significant challenge. An effective simulator must expose the failure modes of the systems under evaluation. This work introduces Direct Iterative Adversarial Learning (DIAL), an adversarial framework that iteratively enhances user simulator realism through a competitive dynamic between a generator (user simulator) and a discriminator. When applied to mental health support, a domain characterized by diverse failure types and a critical dependence on realistic user behavior for failure detection, DIAL restores lexical diversity diminished by supervised fine-tuning and drastically reduces discriminator accuracy. The resulting simulator exhibits a strong correlation between simulated and real failure occurrence rates while maintaining low distributional divergence of failure modes. These findings indicate that DIAL is a promising method for developing realistic user simulators in multi-turn dialogue, facilitating reliable and cost-effective system evaluation prior to deployment.

cs.CL

版本更新 · v2arXiv:2610.36418

When the Application Layer Is Disposable: Putting Integrity Constraints Back in the Database

Hasara Kalumin, Amol Deshpande

原文摘要

Integrity constraints have been central to the relational model since its inception. However, beyond keys, single-row CHECKs, and referential integrity, most constraints are enforced by application layers today. SQL ASSERTIONs, standardized in SQL-92, remain poorly supported by major RDBMSs. This has become increasingly unacceptable due to two developments. First, LLM-driven applications and agents increasingly issue queries and updates directly against databases, bypassing application layers where invariants reside. Such code may be generated on demand and discarded afterwards, making the database the only durable component that can encode and enforce these invariants. Second, natural constraints in higher-level conceptual models, such as E/R and property graphs, become fragmented across relations under mappings chosen for performance. The resulting multi-relation constraints lack direct database support, and only some can be efficiently enforced using existing mechanisms such as triggers. These developments motivate an overhaul of how constraints are defined, mined, managed, and enforced in data management systems. As a first concrete step, we introduce constraint indexes, which represent constraints spanning multiple relations as transactional access paths, and implement a proof of concept as a PostgreSQL extension. Constraint indexes enforce constraints arising from distributed inheritance hierarchies, folded relationships, and folded weak entities, as well as cardinality bounds and functional dependencies, at low overhead relative to no enforcement. Across these workloads, they outperform the better of the correctness-preserving baselines by up to 2.41 times. We also show that LLM-driven writers frequently violate unenforced constraints and behave erratically when provided with a list of constraints to enforce. We close by discussing a few research challenges raised by this agenda.

cs.DB

版本更新 · v2arXiv:2610.38970

Communication-Efficient Clustered Federated Learning in Non-IID Wireless Networks

Martin Isaksson, Rickard Cöster, Šarūnas Girdzijauskas, Seif Haridi

原文摘要

Current and emerging mobile networks face increasing privacy, scalability, and performance challenges as distributed learning becomes essential for advanced 6G services. These challenges are amplified by the presence of non-IID data, naturally arising in heterogeneous wireless environments, that degrade the performance of standard Federated Learning (FL) approaches. To address non-IID data across clients, we propose a Clustered Federated Learning (CFL) framework that assigns clients to specialized models during training. Data-domain clustering initializes model-based clustering, enabling identification and exploitation of client similarities without sharing raw data while reducing communication cost. Motivated by mmWave beam selection, we evaluate our methods on a wireless simulation dataset (DeepMIMO) and complement it with two non-IID benchmarks (FEMNIST, Rotated CIFAR-10) to isolate different non-IID characteristics. Our best configurations improve accuracy over IFCA by 4.8 pp on DeepMIMO and 10.6 pp on FEMNIST while reducing downlink data volume by 83.1 % on FEMNIST compared to IFCA. We demonstrate that different clustering strategies suit different non-IID characteristics. These results show that our CFL methods enable resource-efficient, and high-performance distributed learning in future 6G networks.

cs.LG

版本更新 · v3arXiv:2607.17082

OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories

Babak Barazandeh, Subhabrata Majumdar, George Michailidis

原文摘要

Large language model agents solve tasks by generating trajectories that interleave planning, tool calls, and intermediate results. Current evaluation metrics reduce such a trajectory to a binary success flag, compare it against a reference by exact matching, or delegate judgment to another language model. A success flag cannot distinguish sound solutions from lucky ones, nor explain why runs fail. Exact matching penalizes valid plans reordered or decomposed differently. We reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiate it via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs. The resulting score, termed OTAP (Optimal Transport for Agentic Planning), is a normalized discrepancy score. Its idealized, globally minimized entropy-free objective is invariant to dependency-preserving relabelings of a fixed graph and has a redundant-insertion sensitivity analysis under stated assumptions. Its unbalanced marginals handle missing or hallucinated steps without forcing a match; granularity invariance remains an open problem that soft coupling mitigates only in part. On controlled perturbations and three public benchmarks, OTAP separates valid from invalid trajectories in a regime where semantics-only metrics score below chance. Its performance is encouraging across these settings, while controlled edge-noise experiments reveal sensitivity to dependency extraction. Where a formal verifier exists, strict surface metrics predict validity better than OTAP does, which places OTAP in open-ended domains where no verifier is available. A blinded study of 236 trajectories finds the strongest agreement with OTAP among the six compared metrics. Structure-aware baselines achieve higher clean-graph AUROC, while OTAP has the smallest absolute AUROC decline under the tested edge noise.

cs.AI · cs.CL · cs.LG