We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.
Doohyun Kim, Donghwa Kang, Mingyu Jun, Brent ByungHoon Kang
原文摘要
Indirect prompt injection threatens local LLM agents through untrusted tool outputs, motivating defenses that suppress attacks while preserving task evidence under limited inference budgets. We introduce SEAL, which learns a soft prompt and scoring readout offline to sanitize tool outputs using a frozen task model. SEAL constructs scoring queries from trusted initial context and the learned prompt, keeping the reference independent of inspected tool text. It scores tokens without normalization across context tokens and uses preservation regularization to encourage retention of useful evidence during localized deletion. This design requires neither defense-generated tokens nor a separate verifier model. Across AgentDojo and AgentDyn, SEAL suppresses attacks while improving task completion under attack. Specifically, on AgentDojo, SEAL reduces attack success from 34.6\% to 0.1\% and increases Joint---task completion without attack success---from 51.4\% to 77.5\%, while using approximately $127\times$ fewer defense-related tokens than PISanitizer, a state-of-the-art prompt injection defense. Replication on a second backbone with the same training recipe supports applicability across model families.
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, André Nichterlein, Camille Richer
原文摘要
We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem which is known to be NP-hard. While approximation algorithms and polynomial-time algorithms for some graph classes are known, the parameterized complexity of the problem has not been investigated so far. We start a parameterized complexity analysis with the goal of determining the border of algorithmic tractability for the MAD tree problem. To this end, we provide a linear-time algorithm for graphs of constant modular width and a polynomial-time algorithm for graphs of bounded treewidth; the degree of the polynomial depends on the treewidth. That is, the problem is in FPT with respect to modular width and in XP with respect to treewidth. Moreover, we show that it is in FPT when parameterized by vertex integrity, by maximum leaf number, or by an above-guarantee parameter. We complement these algorithms with NP-hardness on split graphs.
Accelerated dynamics methods, such as parallel replica dynamics, require estimates of the decorrelation time, after which a process trapped in one of its metastable states is distributed according to the quasi-stationary distribution (QSD). In a method proposed by Binder, Lelièvre and Simpson, decorrelation times are defined by coupling a particle approximation of the non-linear conditioned probability flow of the process with MCMC-inspired diagnostics. We explore an alternative to MCMC diagnostics, based on coarse-graining of non-linear probability flows and simulation-based inference. We first develop a coarse-graining framework for killed Markov jump processes conditioned on survival, proving uniform-in-time, non-asymptotic estimates approximating the non-linear probability flow of the true process by the non-linear flow of a surrogate process, defined with a collective variable. The framework does not assume reversibility of the true process, and also gives bounds which scale explicitly in an adiabatic regime. Motivated by these results, we then construct a quasi-stationarity diagnostic using simulation-based inference: a recurrent neural network (RNN), trained on particle approximations of non-linear effective flows, estimates posterior probabilities of decorrelation. The learned diagnostic is then transferred to collective-variable traces of high-dimensional particle approximations. We investigate the behavior and robustness of this diagnostic on a set of numerical experiments, comparing it to the MCMC diagnostic of Binder et al.\ on both synthetic examples and a molecular system, in and out of its training prior distribution. When its prior assumptions hold, the RNN diagnostic outperforms the MCMC diagnostic in ROC analysis, is less conservative, fails less often, and has an interpretable decision threshold.
Effective image classification in real-world scenarios requires models capable of capturing both local features and global context, while adapting to the evolving complexity of the input. This paper presents a hybrid deep learning system named AMR-Net (Adaptive Modular Retrieval Network) for adaptable image classification in environmental and industrial contexts. The proposed model integrates ResNet-based local feature extraction and Vision Transformer-based global representation learning with an FAISS-based memory retrieval module for contextual enhancement. Furthermore, AMR-Net has an adaptive modular extension mechanism to dynamically enhance network capacity when validation performance plateaus during training. The proposed framework was evaluated using a ten-class waste classification dataset and the Kolektor Surface Defect Dataset 2 (KolektorSDD2), achieving classification accuracies of 97.15% and 99.80%, respectively. Experimental results demonstrate that AMR-Net consistently outperforms mainstream convolutional and transformer-based approaches while maintaining robust cross-domain generalization. Component-wise ablation studies show that global attention (ViT), retrieval-based contextual learning (FAISS), and adaptive modular growth each provide complementary and partially overlapping contributions to overall performance, with global attention contributing the largest individual gain. The proposed architecture is a scalable and flexible solution for image classification challenges characterized by data unpredictability, class imbalance, and dynamic feature distributions.
Split inference partitions a Vision Transformer between a resource-constrained edge device and a server. However, transmitting intermediate tokens across the communication channel is costly. Deploying fine-tuned backbones to every endpoint becomes expensive as well. We study token reduction for split inference under a frozen backbone, where only a small adapter is shipped. We observe that the CLS token plays a dual role: it acts as the global summary the receiver needs for classification, and it serves as a signal on which patches to keep. We propose Consommé, a method utilizing both characteristics. There, an information bottleneck compresses the CLS token into a compact latent which is transmitted in place of the full CLS token and conditions a learned patch gate merging patches into exactly $k$ tokens via soft assignment. It reaches any budget in a single step, thus escaping the per-layer cap of bipartite matching (BPM). On DeiT-S/T, it leads all methods at aggressive token budgets and remains operable at shallow splits where BPM cannot operate, while matching fine-tuned methods at gentle budgets at a fraction of their deployment cost.
We present a cascade streaming voice privacy system, consisting of ASR, NLP, and TTS modules. By leveraging recent improvements in all three aspects of speech and language processing, we show that such a system is capable of achieving a result comparable to state-of-the-art offline voice privacy systems, while providing controllable capabilities of content protection beyond voice. With an estimated utterance-onset end-to-end latency of 717 ms, the presented system preserves speech content with 11% WER on Librispeech, while detecting PII with a 69% SLU F1 score and achieving up to 47.66% EER against a semi-informed attacker.
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
原文摘要
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.
We study \textsc{Max $k$-Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most $k$ variables to $1$. Each constraint uses at most $d$ distinct variables and a relation from a finite Boolean language $Γ$. This includes \textsc{Partial Vertex Cover}, \textsc{Densest $k$-Subgraph}, bounded-frequency \textsc{Maximum Coverage}, and cardinality-constrained \textsc{Max-SAT}. We completely classify the fixed finite languages admitting an efficient parameterized approximation scheme (EPAS) with parameter $k+d$. Only nonempty relations excluding the all-zero tuple matter. For such a relation, a coordinate is a \emph{unit witness} if the tuple with a single $1$ in that coordinate is accepted, and a \emph{control} otherwise. A relation is \emph{Direct} if setting any selected control to $0$, with all other coordinates unchanged, preserves satisfaction. It is \emph{Rooted} if every satisfying tuple has a selected unit witness such that keeping it, setting all other unit witnesses to $0$, and setting any subset of selected controls to $0$ preserves satisfaction. If all such relations are Direct, or all are Rooted, we give a deterministic $(1-\varepsilon)$-approximation for every rational $\varepsilon\in(0,1)$ in time $2^{O(d+k\log(1+dk/\varepsilon))}\ell_{\mathrm{in}}^{O(1)}$, where $\ell_{\mathrm{in}}$ is the total input length. The algorithms are uniform in $d$ and give an EPAS parameterized by $k+d$ whenever relation membership is polynomial-time decidable. If neither condition holds, no EPAS exists unless $\mathsf{FPT}=\mathsf{W[1]}$, even for unweighted instances where no two constraints involve the same set of variables.
Lei Tian, Chunzheng Zhu, Kai Wu, Yifan Zhang, Haihua Yang
原文摘要
Native multimodal large language models (native MLLMs) jointly encode visual and linguistic sequences within a unified autoregressive Transformer, emerging as a promising paradigm for multimodal understanding. Unlike conventional ViT-based MLLMs relying on external vision encoders, ViT-free native MLLMs tokenize pixel patches directly, potentially suffering severe visual token redundancy. A pilot study confirms this: unlike ViT-based models that degrade under compression, ViT-free MLLMs tolerate aggressive compression with near-lossless or even improved performance. Yet existing compression methods target ViT-based settings, leaving native MLLMs, which stand to gain the most, unexplored. To close this gap, we introduce an analysis pipeline centered on token discriminability and cross-dimensional heterogeneous redundancy, revealing that (i) redundancy is distributed independently and heterogeneously along height and width axes, and (ii) early-layer visual tokens are indiscriminable and uniformly redundant. Guided by these findings, we propose PACE (Pareto-Adaptive Compression for Efficient Native MLLMs), the first visual token compression framework tailored for native MLLMs with Multimodal-RoPE. Leveraging dimensional decoupling of positional encoding, PACE decomposes attention into two orthogonal spatial saliency estimates along height and width, gated by a positional attention signal, yielding direction-aware importance with negligible overhead. It further casts token budget allocation as Pareto optimization over performance preservation, inference efficiency, and spatial coverage, jointly identifying optimal compression depths and retention ratios. Experiments show PACE maintains near-lossless performance at only 25%-50% visual token retention, even improving several benchmarks, while delivering over 2x FLOPs reduction.
Michele Caprio, David Stutz, Shuo Li, Arnaud Doucet
原文摘要
An open question in \emph{Imprecise Probabilistic Machine Learning} is how to empirically derive a credal region (i.e., a closed and convex family of probabilities on the output space) from the available data, without any prior knowledge or assumption. In classification problems, credal regions are a tool that is able to provide provable guarantees under realistic assumptions by characterizing the uncertainty about the distribution of the labels. Building on previous work, we show that credal regions can be directly constructed using conformal methods. This allows us to provide a novel extension of classical conformal prediction to problems with ambiguous ground truth, that is, when the exact labels for given inputs are not exactly known. The resulting construction enjoys desirable practical and theoretical properties: (i) conformal coverage guarantees, (ii) smaller prediction sets (compared to classical conformal prediction regions) and (iii) disentanglement of uncertainty sources (epistemic, aleatoric). We empirically verify our findings on both synthetic and real datasets.
Decision models are language models built to route, classify and triage: they return option probabilities from one forward pass, and an application acts on the top answer. They are offered off the shelf, trained for the decision format rather than for fairness or any one application, and we found no bias measurement in their cards. We test TypeSafe's closed Jev and five open decision models on gender-swapped yes/no decisions about people (Tamkin et al., 2023), BBQ, StereoSet and the gender-bias studies of Fulgu and Capraro (2024). Five of the six give women significantly more favourable answers than men (+0.05 to +0.10 in log-odds), and a gender swap changes 1-3.5% of top answers (Jev's partly through its call-to-call variation). The makers' recommended confidence gate removes many biased commitments but raises the stereotyped share of those it keeps in ambiguous BBQ gender questions (granite-switch 0.76 to 0.85, pplx 0.81 to 1.00). Probes show gender preferences in the same models: all six rate violence for a greater good as more acceptable against a man than against a woman, and two default to "girl" when forced to guess a child's gender without a cue. Decision-level and probability-level measures differ, so audits should read a model as its application does.
We study finite-terminating, address-only step recursion on the nonnegative reals, from zero, unit successor and projections. For reduced positive rational strides $s=a/q$ and $t=b/v$, we prove $\mathcal{C}s\subseteq\mathcal{C}t$ if and only if $q$ divides $v$, for both the bounded and unbounded algebras $\mathcal{C}\in{\mathcal{B},\mathcal{U}}$. The bounded compiler preserves earlier global majorants on every auxiliary input. Mixed rational stride sets are classified by least common denominators and supernatural denominators. Primitive-recursive translated-coordinate grid codes characterize the unbounded algebras and yield $\mathcal{U}{1/q}\cap\mathcal{U}{1/v}=\mathcal{U}{1/\gcd(q,v)}$. For bounded intersections, we prove an exact reduction: all corresponding identities hold if and only if the single identity $\mathcal{B}{1/2}\cap\mathcal{B}_{1/3}=\mathcal{B}_1$ holds, equivalently if the Boolean parts of the integer successor and addition algebras under scalar bounded recursion coincide. A Boolean reconstruction reduces general functions to predicates; a clipped fine-grid simulation with a frozen global resource bound identifies the union of predicate precision classes with the addition level. These reductions do not decide the resulting predicate equality, so literal bounded intersections remain unresolved. We also prove that unbounded-program equality is $Π^0_1$-complete and extensional bounded-algebra membership is $Σ^0_2$-complete. The model has no free real arithmetic or Zeno limits; semantic majorant validity is distinguished from syntax transformation.
Rely/Guarantee is a well-known verification technique for reasoning about concurrent programs. However, for some algorithms, devising suitable rely and guarantee conditions is challenging, due to the strong interference exhibited in these algorithms. The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions. This paper investigates an approach for verifying the Ben-Ari algorithm, which enables reasoning to be performed in a more compositional manner in cases where compositional reasoning would not otherwise be possible. This is accomplished by reasoning that a given property holds for all instances of a particular variable and then instantiating the variable to the local variable required. As well as providing a reasoning approach which is more compositional, the result is the identification of the core property required of a component, thus enabling a deeper understanding about the reasons why the algorithm works correctly. This helps to reveal the reasons why the rely/guarantee approach does not work directly for some problems.
Chen Su, Xingqun Qi, Xurui Hu, Bingkun Yang, Muyi Sun, Man Zhang, Zhenan Sun
原文摘要
Deriving plausible and dynamic Human Object Interaction (HOI) has gained tremendous progress in Embodied AI and Immersive AR/VR. While existing HOI methods have effectively explored human interaction with individual or fixed objects, they still show limitations in complex multi-object interaction scenes. Meanwhile, previous approaches focus more on the contact information held by human-object relation, overlooking the significance of the contact situation of various entities (i.e., object-object). To address these limitations, we propose UniffordInteractor, a Reasoning-then-Interacting framework that leverages unified affordance for realistic and long-horizon human and multi-object interaction modeling. At the reasoning stage, we devise a Unified Affordance Reasoner (UAR) that employs a fine-tuned 3D Multimodal Large Language Model for unified object-centric affordance prediction. At the interacting stage, we propose Hierarchical Interaction Generator (HIG), which formulates the interaction generation as a hierarchical (e.g., root to body to hand to objects) autoregressive prediction, conditioned on the obtained unified affordance. Extensive experiments demonstrate that UniffordInteractor surpasses SOTA counterparts in human and multi-object interaction generation.
Before AI can be trusted to discover new science, it should be able to reproduce what science already knows. Reproduction provides a rigorous checkpoint for an AI scientist: the target claim is known, yet recovering it still requires translating an incomplete scientific description into an executable experiment and producing evidence that can be independently verified. Existing research-reproduction benchmarks largely focus on AI and machine learning, where experiments share relatively homogeneous software stacks. Extending this capability across scientific disciplines introduces a different challenge: agents must operate domain-specific scientific software, make physical and numerical choices, diagnose long-running computations, and distinguish valid evidence from merely plausible outputs. We introduce PAPERBENCHX, a benchmark of 93 expert-constructed paper-reproduction tasks spanning 12 research areas across electromagnetics, photonics, chemistry, materials science, biology, and robotics. Each task provides the source paper, a public task specification, and a domain-native scientific environment involving specialized scientific software. Agents must reconstruct a key experiment, execute and diagnose it, and deliver a runnable workflow that supports the target scientific claim. To evaluate scientific validity rather than surface-level agreement, we replay every submission from scratch and score only regenerated evidence against expert-validated criteria. Across 10 frontier agent configurations, the best configuration fully reproduces only 14% tasks under the 90% threshold. Meanwhile, mean rubric scores range from 27.53% to 59.08%, indicating that substantial partial progress rarely translates into complete scientific reproduction. These results reveal a large gap between paper understanding and reliably producing reproducible scientific evidence.
Deep Neural Networks (DNNs) are increasingly being deployed in security-critical and safety-sensitive applications, which makes rigorous testing essential to identify and mitigate model weaknesses. Existing DNN testing approaches explore either the input space or a learned latent space. While latent-space generation can better maintain plausibility than direct input-space mutation, current methods still face a trade-off among exploration controllability, failure diversity, and seed-relative semantic drift. To overcome these limitations, we propose Latte, a black-box testing framework that generates semantically proximate, diverse, and fault-revealing test cases by leveraging the latent space. Specifically, Latte encodes each input seed with a pre-trained VQ-VAE and performs a seed-centered, one-step latent mutation along directions defined by anchors sampled from alternative classes, followed by quantization and decoding back to the input space. This explores local neighborhoods around each seed within the learned latent manifold, resulting in a larger number and broader diversity of oracle-triggering prediction discrepancies under the same budget. We evaluated Latte on 5 datasets and 10 DNN models in single-model and multi-model testing scenarios. Across the evaluated datasets and models, Latte improves fault exposure and behavioral diversity under matched testing budgets. Under the single-model setting, it also maintains low seed-relative semantic drift with respect to the source seeds.
Rini Sharon, Kadri Hacioglu, Jeena Prakash, Andreas Stolcke
原文摘要
End-of-turn (EoT) detection has been studied mostly through features, models, and modalities, while the speech genre of the training data has drawn far less attention. We isolate this factor. Using one reproducible annotation pipeline, we build a matched pair of corpora, multi-turn human-human conversational and single-turn human-machine, and train the same streaming ConvLSTM EoT detector on each. Across four test sets the conversational model reaches up to +0.45 higher F1, driven by fewer false alarms on the mid-turn pauses and hesitations that are rare in single-turn corpora. This conversational-training effect is not specific to frame-level decoding. Under a matched complete-or-not test it also appears at the utterance level, across two encoders, but only on conversational test data. Testing only on single-turn speech, as most prior work does, therefore hides the benefit of conversational training data. Against open-source baselines, our 1.8M-parameter model attains the highest F1 on every test set.
Reinforcement learning has advanced large language models on tasks with reliable verifiers, where checking an outcome provides a clear basis for reward. Extending this approach to open-ended tasks requires environments that can both evaluate complex, partially successful outputs and turn these judgments into effective learning guidance. We propose a reinforcement learning framework built around a training environment that integrates human domain knowledge with model reasoning. Human domain knowledge, encoded in rubrics, anchors evaluation to task intent, while model reasoning combined with hierarchical rewards distinguishes complex open-ended outputs and links diagnosed failures to likely responsible output regions. Furthermore, these diagnostic attributions guide token-level weights in the GRPO objective, thereby translating the ambiguous notion of success in open-ended tasks into concrete guidance for policy optimization. We instantiate this framework in interactive web application generation, a representative open-ended generation task. The resulting model achieves an average pass rate of 41.25\% on MiniAppBench and 76.19\% on ArtifactsBench. Ablation studies show the contributions of individual components, while additional out-of-distribution evaluations support transferable gains without degrading performance on other evaluated tasks.
We develop a formal semantics for a general class of coordinated systems of parameterized transformations, taking the Transformer as a paradigmatic starting point but abstracting from its particular mathematical instantiation. Representational vectors receive both extensional reference and ordered intensional interpretations, while parameter structures acquire relative, second-level interpretations that determine how argument properties are preserved, replaced, or combined. This yields the notion of a transforming concept: a parameterized transformation whose numerical action is coordinated with a corresponding property-level map. We then distinguish the common algebraic-semantic core of these systems from their architecture-specific functional organization, allowing different mathematical instantiations and mechanical realizations of the same abstract system type. The framework is applied to attention heads and residual connections, providing semantic explanations that depend only on the shared algebraic-semantic core and their local functional organization and therefore generalize beyond the standard Transformer. These analyses also reveal the modularity of the framework: complex architectures can be decomposed into simpler semantically coordinated subsystems whose organization may recur across different abstract system types.
Bin Duan, Ruican Dong, Naipeng Dong, Dan Dongseong Kim, Guowei Yang
原文摘要
Deep learning libraries underpin many safety- and reliability-critical applications, yet existing API-level testing techniques often rely on intra-library properties or CPU--GPU differential oracles and may miss defects that behave consistently across hardware backends. We present Xamt, a cross-framework differential fuzzing approach for deep learning library APIs. Xamt constructs and tests execution-validated groups of APIs intended to implement equivalent operations across seven libraries. It uses explicit API aliases and parameter-role normalization to construct candidate correspondences and validates them through pairwise execution and a group-level behavioral check on canonical ordinary inputs. The resulting groups are explored using variance-guided differential fuzzing with ordinary, boundary, and non-finite inputs. Crash and inconsistency oracles flag executions exhibiting abnormal termination or inconsistent outputs for subsequent reproduction and analysis. Across the seven libraries, Xamt constructs 676 execution-validated groups containing 2,563 matched APIs. Among these, Xamt identifies 72 independently reproduced discrepancy cases, including 4 crash cases and 68 output inconsistencies. Among the 72 developer reports, 25 have been confirmed, including 23 that have been fixed.
Minwoo Park, Junwoo Chang, Jongeun Choi, Roberto Horowitz
原文摘要
Equivariant diffusion policies (EDPs) combine the expressivity of diffusion models with the generalization and sample efficiency afforded by geometric symmetries. While steering these policies with reinforcement learning (RL) offers a promising fine-tuning mechanism beyond demonstration data, directly applying standard (non-equivariant) RL ignores the symmetries that EDPs are designed to exploit, leading to sample inefficiency and instability. We theoretically establish that the diffusion process of an EDP is equivariant, inducing a group-invariant latent-noise MDP which is well-suited for equivariant diffusion steering. Building on this, we introduce a principled symmetry-aware steering framework and compare standard, equivariant, and approximately equivariant RL strategies across tasks with varying degrees of symmetry. While we identify the practical boundaries of strict equivariance under symmetry breaking, exploiting symmetry during the steering yields substantial benefits---enhancing sample efficiency, preventing value divergence, and achieving strong policy improvements even when EDPs are trained from extremely limited demonstrations.
Bank-World is a benchmark of 50 banking tasks across two simulated institutions. Completing banking work requires more than producing the right calculation: agents must reconcile records, obtain permission, execute transactions, and keep instructions and status reports consistent as circumstances change. Bank-World tests these requirements through single-turn assignments and multi-turn interactions with simulated employees who supply information, approve actions, and revise instructions. Grading combines executable checks of recorded actions and state with model judgments of task requirements, including whether valid alternative solutions satisfy them. Across 1,600 attempts by four models, we find that correct decisions often fail to become completed work. Agents charge fees twice, distribute the correct total in incorrect amounts among the recipients, and execute payments while approval is pending. Their strengths also differ: Sol leads single-turn completion, Opus has the highest observed multi-turn completion rate, and Grok succeeds across more multi-turn tasks but less consistently. Bank-World makes these differences inspectable through task-level results and worked examples connecting source evidence, agent decisions, and simulated consequences. We retain the task environments, executable graders, and full trajectories privately to reduce contamination and preserve the benchmark for future evaluations.
While universal approximation theorems theoretically underpin the representation capabilities of machine learning models, they have two shortcomings: They do not focus on efficient representations and they tend to be insensitive to depth and other heuristically important properties. In this work we show that these two shortcomings are intertwined. We prove that machine learning models which are deeper or have higher-order interactions can efficiently represent a larger set of functions, i.e. have larger efficient reach. It follows that deep Boltzmann machines (DBMs) have maximal efficient reach, restricted Boltzmann machines (RBMs) sub-maximal, and k-body generalizations of RBMs form a hierarchy between the two, even though all are universal. More generally, (i) we provide a full characterization of machine learning models with maximal efficient reach; (ii) we derive separations between deep and shallow models for three representation tasks; and (iii) we prove that the efficient reach of shallow models constitutes an infinite hierarchy indexed by the interaction order. The proofs draw on different methodologies, namely on (i) a recent characterization of universal spin models; (ii) computational complexity bounds for spin models; and (iii) communication complexity bounds applied to shallow models. This work shows that universal machine learning models can strongly differ in their efficient representation capabilities, and provides a theoretical foundation for heuristic observations.
Online applications can share data with arbitrary parties, without users noticing. In practice, these data flows could constitute privacy violations to individual users, with the lack of transparency leaving users unaware of the unwanted data flows. To understand the spread and scale of this privacy threat, we investigate what data is collected and where it is sent in popular free-to-play Android games. As part of our investigation, we conduct a measurement study where we collect and analyze over 16 GB of network traffic from 50 puzzle games. Additionally, we explore the effectiveness of user-side countermeasures for a selection of the apps. We find that while most countermeasures, such as ad-blocking DNS services, decrease data flows, withholding consent and opting out of data collection can produce inconsistent behavior including increased outgoing traffic. To encourage further analysis, we release our measurements as an open dataset.
Panagiotis Georgios Pennas, Konstantinos Papaioannou, Marco Guarnieri, Thaleia Dimitra Doudali
原文摘要
Large Language Models (LLMs) rely on optimizations like Automatic Prefix Caching (APC) to accelerate inference. APC works by reusing previously computed states for the beginning part of a request (prefix), when another request starts with the same text. While APC improves throughput, it introduces timing side channels: cache hits are faster than misses, creating observable latency differences. In multi-tenant systems, attackers can exploit these differences to infer sensitive information, e.g., by incrementally reconstructing another user's request by observing hit/miss patterns. Current defenses take a sledgehammer approach: they disable APC and cache sharing, isolating users, and sacrificing efficiency for regular users. This paper presents CacheSolidarity, a system that secures multi-tenant LLM serving systems against APC side channels without sacrificing performance and efficiency. CacheSolidarity monitors cache reuse across users, flags suspicious sharing, and selectively isolates prefixes, restricting their reuse only when necessary. Evaluation shows that CacheSolidarity enables up to 70% higher cache reuse and 30% lower inference latency compared to existing user-isolation defenses. CacheSolidarity's lightweight design demonstrates how LLM serving can be secured without sacrificing performance or incurring unbearable overheads.
Wen Fang, Xianxian Li, Jun Liu, Jie Luo, Yongxin Tong, Ke Xu
原文摘要
We study self-reference and solution independence in Boolean $K$-SAT as a finite analogue of Gödel incompleteness. Independence is defined through factorial moments of the solution count. Constant-width random formulas fail this criterion due to correlations among overlapping assignments. At a covering threshold, logarithmic-width random CNFs have a Poisson solution count, with positive probabilities of unsatisfiability and unique satisfiability. Replacing a redundant clause by one falsified by the unique solution yields an unsatisfiable companion preserving the unsigned incidence graph. For every permitted local view of a good uniquely satisfiable formula, an unsatisfiable companion preserves that view. Irreducibility defeats deterministic and bounded-error evaluators using $N^c$ clause queries, for fixed $0<c<1$. It establishes a local information obstruction, not an unrestricted time lower bound. For fixed $δ>0$, transcripts of $N^{1-δ}$ queries leave $N-o(N)$ bits of witness entropy. On typical support graphs, expansion yields linear Resolution width, linear PC/PCR and SOS degree, and exponential proof size. Bounds hold for semantic Cutting Planes under a partition condition and for Positivstellensatz with bounded product width, uniformly over unsatisfiable support-preserving signings. Structural evidence and the limits of acceleration strategies motivate the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH): no uniform deterministic algorithm deciding the promise family achieves a fixed proportional saving in the exponent. This dual-evidence criterion combines intrinsic hardness mechanisms with algorithmic evidence. We interpret this hypothesis as a quantitative projection of the Gödel-style local--global gap. The information obstruction constrains quantum local observation and statistical learning from bounded local information.
Georgios Floros, Evangelos Sartinas, Orestis Vaggelis, Maria Pateraki
原文摘要
6D pose estimation of novel objects without CAD models remains an open challenge: model-free methods must build the object representation from scratch during onboarding and have long trailed their model-based counterparts. We present NovaSplat, a model-free pipeline that closes this gap. From a short smartphone video captured at onboarding, we train a 3D Gaussian Splatting (3DGS) model that serves both as a template source for detection and coarse pose estimation and as a differentiable backbone for pose refinement. Our refiner optimizes the object-to-camera pose with combined photometric and geometric losses under a continuous rotation parametrization free of gradient singularities. On a household-object benchmark, NovaSplat surpasses all model-based methods. On a challenging industrial benchmark with textureless and specular surfaces, it outperforms all model-free competitors while substantially narrowing the gap to model-based ones. We further introduce NovaSplat-Lite, an inference variant that is $3.1\times$ faster at negligible accuracy cost. Code will be made available at https://github.com/POSE-Lab/novasplat .
An uncertainty estimate is meaningful only if its semantics can be tied to observable predictive behavior. Normal-Inverse-Gamma (NIG) evidential regression provides a structured decomposition of predictive variability into data-scale and predictive-mean components, but marginal likelihood does not identify their allocation. We address this semantic ambiguity in masked representation learning. MORSE (Masked Observability for Reliable Structured Encoding) predicts the same hidden target under controlled changes in visible context and uses normalized cross-context variation to ground predictive-mean uncertainty, while a Gaussian objective learns the conditional mean and data scale. The normalized variation plays the role of the NIG factor $1/ν$, which the marginal leaves unidentified; this yields a policy-relative observability variance that measures dependence on visible evidence, distinct from variation induced by resampling the training set. On a Gaussian-process benchmark with a contextual reference built from analytic Bayes conditional means, MORSE has the lowest log-variance error among compared evidential, ensemble, and dropout estimators in all nine tested settings, while the estimator closest to training-set variation perturbs the model rather than its context in every setting, so the two references separate the estimators empirically. MORSE amortizes observability estimation into one forward pass per observation state. On a heteroscedastic pulse benchmark, its predictor's cross-context variance approaches a large-sample reference as training data increase. MORSE also improves low-label transfer on PTB-XL and in-distribution trajectory prediction on IMPTC.
Kaisong Ji, Ziyang Xu, Chang Bian, Yu Zhou, Wenyu Liu, Xinggang Wang
原文摘要
Zero-shot anomaly detection aims to transfer anomaly discrimination from auxiliary training domains to unseen categories while localizing subtle defects. A key challenge is to construct discriminative references that combine contextual representations with complementary local evidence. We present Cross-Encoder Anchor Refinement (CEAR), which connects two visual encoding paths for the same image at the anchor stage, before normal and anomalous prototypes are constructed. An independent convolutional encoder pretrained for industrial product recognition builds an image-specific memory shared across selected vision transformer (ViT) layers. Spatial anchors read from ViT patch features query this memory through cross-attention and undergo residual refinement. Image-conditioned normal and anomalous queries then gate anchor aggregation to construct prototypes for anomaly scoring. Across 13 industrial and medical datasets, CEAR achieves the best performance in 57 of 68 evaluations spanning image-level detection and pixel-level localization. Notably, CEAR surpasses all other state-of-the-art methods in 41 of 44 pixel-level comparisons. Across 11 localization datasets, mean gains in pixel-level maximum F1 score and average precision are 4.45 and 3.79 percentage points, respectively. This study shows how cross-encoder interaction at the anchor stage can integrate complementary visual representations for fine-grained anomaly localization across domains.