OpenRaiser/Intern-Atlas huggingface dataset:
Ex-post Individually Rational Bayesian Persuasion
Venue: arXiv cs.GT 2024
Year: 2024

In the Bayesian persuasion model, a sender can convince a receiver to choose an alternative action to the one originally preferred by the receiver. A crucial assumption in this model is the sender's commitment to a predetermined information disclosure policy (signaling scheme) and the receiver's trust in this commitment. However, in practice, it is difficult to monitor whether the sender adheres to the disclosure policy, and the receiver may refuse to follow the persuasion due to a lack of trust. Trust becomes particularly strained when the receiver knows that the sender will incur obvious losses when truthfully following the protocol. In this work, we propose the notion of ex-post individually rational (ex-post IR) Bayesian persuasion: after observing the state, the sender is never asked to send a signal that is less preferred than no information disclosure. An ex-post IR Bayesian persuasion policy is more likely to be truthfully followed by the sender, thereby providing stronger incentives for the receiver to trust the sender. Our contributions are threefold. First, we demonstrate that the optimal ex-post IR persuasion policy can be efficiently computed through a linear program, while also offering its geometric characterization. Second, we show that surprisingly, for non-trivial classes of games, the requirement of ex-post IR constraints does not incur any cost to the sender's utility. Finally, we compare ex-post IR Bayesian persuasion to other information disclosure models that ensure different notions of credibility.
Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
Venue: arXiv cs.CG 2024
Year: 2024

We say that a (multi)graph $G = (V,E)$ has geometric thickness $t$ if there exists a straight-line drawing $φ: V \rightarrow \mathbb{R}^2$ and a $t$-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The \textsc{Geometric Thickness} problem asks whether a given multigraph has geometric thickness at most $t$. This problem was shown to be NP-hard for $t=2$ [Durocher, Gethner, and Mondal, CG 2016]. In this paper, we settle the computational complexity of \textsc{Geometric Thickness} by showing that it is $\exists \mathbb{R}$-complete already for thickness $30$. Moreover, our reduction shows that the problem is $\exists \mathbb{R}$-complete for $4392$-planar graphs, where a graph is $k$-planar if it admits a topological drawing with at most $k$ crossings per edge. In the course of our paper, we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of $31$ edge-disjoint graphs and pseudo-segment stretchability with chromatic number $30$ are $\exists \mathbb{R}$-complete.
LaCour!: Enabling Research on Argumentation in Hearings of the European Court of Human Rights
Venue: arXiv cs.CL 2024
Year: 2024

Why does an argument end up in the final court decision? Was it deliberated or questioned during the oral hearings? Was there something in the hearings that triggered a particular judge to write a dissenting opinion? Despite the availability of the final judgments of the European Court of Human Rights (ECHR), none of these legal research questions can currently be answered as the ECHR's multilingual oral hearings are not transcribed, structured, or speaker-attributed. We address this fundamental gap by presenting LaCour!, the first corpus of textual oral arguments of the ECHR, consisting of 154 full hearings (2.1 million tokens from over 267 hours of video footage) in English, French, and other court languages, each linked to the corresponding final judgment documents. In addition to the transcribed and partially manually corrected text from the video, we provide sentence-level timestamps and manually annotated role and language labels. We also showcase LaCour! in a set of preliminary experiments that explore the interplay between questions and dissenting opinions. Apart from the use cases in legal NLP, we hope that law students or other interested parties will also use LaCour! as a learning resource, as it is freely available in various formats at https://huggingface.co/datasets/TrustHLT/LaCour.
Neuron Patching: Semantic-based Neuron-level Language Model Repair for Code Generation
Venue: arXiv cs.SE 2024
Year: 2024

Language Models (LMs) have become widely used in software engineering, especially for tasks such as code generation, where they are referred to as code LMs. These models have proven effective in generating code, making it easier for developers to automate coding activities. However, research has highlighted a significant limitation: despite their effectiveness, LMs often produce code that is incorrect, buggy, or not fully functional. Updating these models with limited data can be prohibitively challenging, yet it is essential to maximize their utility. This may require hot-fix techniques (updating models with limited data) to resolve. In this paper, we propose \ul{M}odel \ul{I}mprovement via \ul{N}euron \ul{T}argeting (\textsc{MINT}), a novel approach for repairing code LMs. MINT leverages the semantic property of language models to perform neuron-level repairs in a novel way. Further, by analyzing the relationships between the model's latent representations, the incorrect outputs, and the desired outputs, \textsc{MINT} determines which neurons are worth updating. This approach ensures that only the neurons crucial to the model's failure are targeted, avoiding unnecessary changes and allowing for a more efficient and precise repair process. \textsc{MINT} is effective, efficient, and reliable, capable of correcting a neural model by patching a minimum number of neurons (usually one or two neurons). Our approach is evaluated on three coding tasks: line-level code generation, shellcode generation, and intent-to-bash translation. The experimental results demonstrate that the proposed approach significantly outperforms the state-of-the-art in both effectiveness and efficiency measures. In addition, we analyze and discuss the side effects of model repair techniques, including the balance between generalization and specificity, and the performance after multiple repairs in succession.
Apparate: Rethinking Early Exits to Tame Latency-Throughput Tensions in ML Serving
Venue: arXiv cs.DC 2024
Year: 2024

Machine learning (ML) inference platforms are tasked with balancing two competing goals: ensuring high throughput given many requests, and delivering low-latency responses to support interactive applications. Unfortunately, existing platform knobs (e.g., batch sizes) fail to ease this fundamental tension, and instead only enable users to harshly trade off one property for the other. This paper explores an alternate strategy to taming throughput-latency tradeoffs by changing the granularity at which inference is performed. We present Apparate, a system that automatically applies and manages early exits (EEs) in ML models, whereby certain inputs can exit with results at intermediate layers. To cope with the time-varying overhead and accuracy challenges that EEs bring, Apparate repurposes exits to provide continual feedback that powers several novel runtime monitoring and adaptation strategies. Apparate lowers median response latencies by 40.5--91.5% and 10.0--24.2% for diverse CV and NLP classification workloads, and median time-per-token latencies by 22.6--77.9% for generative scenarios, without affecting throughputs or violating tight accuracy constraints.
PILLOW: Enhancing Efficient Instruction Fine-tuning via Prompt Matching
Venue: arXiv cs.CL 2024
Year: 2024

Instruction fine-tuning has conventionally been employed to adapt Large Language Models (LLMs) to a variety of tasks. Nonetheless, this technique often necessitates substantial computational resources, making it impractical for deployment by individuals or small-scale entities. Recently, Low-Rank Adaptation (LoRA) has become a promising alternative, offering high capabilities on par with full tuning with reduced resource overhead. However, attaining satisfactory performance through the fine-tuning of LoRA is a non-trivial challenge. In this paper, we propose PILLOW, which aims to improve LoRA's performance by a discrimination-based prompting method, leveraging LLMs' In-Context Learning ability. PILLOW incorporates a matching network that selects prompts from a user-defined prompt pool, concatenates the selected prompts with the user instruction as input, and performs inference using the LoRA-fine-tuned LLMs. Trained with Reinforcement Learning, PILLOW exhibits commensurate performance on various evaluation metrics compared with typical instruction fine-tuning methods, utilizing only consumer-grade GPU resources and exhibiting a large reduction in computational costs.
Structured Inverse-Free Natural Gradient: Memory-Efficient & Numerically-Stable KFAC
Venue: arXiv cs.LG 2024
Year: 2024

Second-order methods such as KFAC can be useful for neural net training. However, they are often memory-inefficient since their preconditioning Kronecker factors are dense, and numerically unstable in low precision as they require matrix inversion or decomposition. These limitations render such methods unpopular for modern mixed-precision training. We address them by (i) formulating an inverse-free KFAC update and (ii) imposing structures in the Kronecker factors, resulting in structured inverse-free natural gradient descent (SINGD). On modern neural networks, we show that SINGD is memory-efficient and numerically robust, in contrast to KFAC, and often outperforms AdamW even in half precision. Our work closes a gap between first- and second-order methods in modern low-precision training.
Bit Blasting Probabilistic Programs
Venue: arXiv cs.PL 2024
Year: 2024

Probabilistic programming languages (PPLs) are expressive means for creating and reasoning about probabilistic models. Unfortunately hybrid probabilistic programs, involving both continuous and discrete structures, are not well supported by today's PPLs. In this paper we develop a new approximate inference algorithm for hybrid probabilistic programs that first discretizes the continuous distributions and then performs discrete inference on the resulting program. The key novelty is a form of discretization that we call bit blasting, which uses a binary representation of numbers such that a domain of $2^b$ discretized points can be succinctly represented as a discrete probabilistic program over poly($b$) Boolean random variables. Surprisingly, we prove that many common continuous distributions can be bit blasted in a manner that incurs no loss of accuracy over an explicit discretization and supports efficient probabilistic inference. We have built a probabilistic programming system for hybrid programs called HyBit, which employs bit blasting followed by discrete probabilistic inference. We empirically demonstrate the benefits of our approach over existing sampling-based and symbolic inference approaches.
Beyond Gradient and Priors in Privacy Attacks: Leveraging Pooler Layer Inputs of Language Models in Federated Learning
Venue: arXiv cs.LG 2024
Year: 2024

Language models trained via federated learning (FL) demonstrate impressive capabilities in handling complex tasks while protecting user privacy. Recent studies indicate that leveraging gradient information and prior knowledge can potentially reveal training samples within FL setting. However, these investigations have overlooked the potential privacy risks tied to the intrinsic architecture of the models. This paper presents a two-stage privacy attack strategy that targets the vulnerabilities in the architecture of contemporary language models, significantly enhancing attack performance by initially recovering certain feature directions as additional supervisory signals. Our comparative experiments demonstrate superior attack performance across various datasets and scenarios, highlighting the privacy leakage risk associated with the increasingly complex architectures of language models. We call for the community to recognize and address these potential privacy risks in designing large language models.
Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings
Venue: arXiv cs.LG 2024
Year: 2024

We present a novel edge-level ego-network encoding for learning on graphs that can boost Message Passing Graph Neural Networks (MP-GNNs) by providing additional node and edge features or extending message-passing formats. The proposed encoding is sufficient to distinguish Strongly Regular Graphs, a family of challenging 3-WL equivalent graphs. We show theoretically that such encoding is more expressive than node-based sub-graph MP-GNNs. In an empirical evaluation on four benchmarks with 10 graph datasets, our results match or improve previous baselines on expressivity, graph classification, graph regression, and proximity tasks -- while reducing memory usage by 18.1x in certain real-world settings.
FM-G-CAM: A Holistic Approach for Explainable AI in Computer Vision
Venue: arXiv cs.CV 2024
Year: 2024

Explainability is an aspect of modern AI that is vital for impact and usability in the real world. The main objective of this paper is to emphasise the need to understand the predictions of Computer Vision models, specifically Convolutional Neural Network (CNN) based models. Existing methods of explaining CNN predictions are mostly based on Gradient-weighted Class Activation Maps (Grad-CAM) and solely focus on a single target class. We show that from the point of the target class selection, we make an assumption on the prediction process, hence neglecting a large portion of the predictor CNN model's thinking process. In this paper, we present an exhaustive methodology called Fused Multi-class Gradient-weighted Class Activation Map (FM-G-CAM) that considers multiple top predicted classes, which provides a holistic explanation of the predictor CNN's thinking rationale. We also provide a detailed and comprehensive mathematical and algorithmic description of our method. Furthermore, along with a concise comparison of existing methods, we compare FM-G-CAM with Grad-CAM, highlighting its benefits through real-world practical use cases. Finally, we present an open-source Python library with FM-G-CAM implementation to conveniently generate saliency maps for CNN-based model predictions.
Learning Unknown Intervention Targets in Structural Causal Models from Heterogeneous Data
Venue: arXiv cs.LG 2024
Year: 2024

We study the problem of identifying the unknown intervention targets in structural causal models where we have access to heterogeneous data collected from multiple environments. The unknown intervention targets are the set of endogenous variables whose corresponding exogenous noises change across the environments. We propose a two-phase approach which in the first phase recovers the exogenous noises corresponding to unknown intervention targets whose distributions have changed across environments. In the second phase, the recovered noises are matched with the corresponding endogenous variables. For the recovery phase, we provide sufficient conditions for learning these exogenous noises up to some component-wise invertible transformation. For the matching phase, under the causal sufficiency assumption, we show that the proposed method uniquely identifies the intervention targets. In the presence of latent confounders, the intervention targets among the observed variables cannot be determined uniquely. We provide a candidate intervention target set which is a superset of the true intervention targets. Our approach improves upon the state of the art as the returned candidate set is always a subset of the target set returned by previous work. Moreover, we do not require restrictive assumptions such as linearity of the causal model or performing invariance tests to learn whether a distribution is changing across environments which could be highly sample inefficient. Our experimental results show the effectiveness of our proposed algorithm in practice.
Stealing Maggie's Secrets -- On the Challenges of IP Theft Through FPGA Reverse Engineering
Venue: arXiv cs.CR 2024
Year: 2024

Intellectual Property (IP) theft is a cause of major financial and reputational damage, reportedly in the range of hundreds of billions of dollars annually in the U.S. alone. Field Programmable Gate Arrays (FPGAs) are particularly exposed to IP theft, because their configuration file contains the IP in a proprietary format that can be mapped to a gate-level netlist with moderate effort. Despite this threat, the scientific understanding of this issue lacks behind reality, thereby preventing an in-depth assessment of IP theft from FPGAs in academia. We address this discrepancy through a real-world case study on a Lattice iCE40 FPGA found inside iPhone 7. Apple refers to this FPGA as Maggie. By reverse engineering the proprietary signal-processing algorithm implemented on Maggie, we generate novel insights into the actual efforts required to commit FPGA IP theft and the challenges an attacker faces on the way. Informed by our case study, we then introduce generalized netlist reverse engineering techniques that drastically reduce the required manual effort and are applicable across a diverse spectrum of FPGA implementations and architectures. We evaluate these techniques on six benchmarks that are representative of different FPGA applications and have been synthesized for Xilinx and Lattice FPGAs, as well as in an end-to-end white-box case study. Finally, we provide a comprehensive open-source tool suite of netlist reverse engineering techniques to foster future research, enable the community to perform realistic threat assessments, and facilitate the evaluation of novel countermeasures.
Activation Gradient based Poisoned Sample Detection Against Backdoor Attacks
Venue: arXiv cs.CR 2024
Year: 2024

This work studies the task of poisoned sample detection for defending against data poisoning based backdoor attacks. Its core challenge is finding a generalizable and discriminative metric to distinguish between clean and various types of poisoned samples (e.g., various triggers, various poisoning ratios). Inspired by a common phenomenon in backdoor attacks that the backdoored model tend to map significantly different poisoned and clean samples within the target class to similar activation areas, we introduce a novel perspective of the circular distribution of the gradients w.r.t. sample activation, dubbed gradient circular distribution (GCD). And, we find two interesting observations based on GCD. One is that the GCD of samples in the target class is much more dispersed than that in the clean class. The other is that in the GCD of target class, poisoned and clean samples are clearly separated. Inspired by above two observations, we develop an innovative three-stage poisoned sample detection approach, called Activation Gradient based Poisoned sample Detection (AGPD). First, we calculate GCDs of all classes from the model trained on the untrustworthy dataset. Then, we identify the target class(es) based on the difference on GCD dispersion between target and clean classes. Last, we filter out poisoned samples within the identified target class(es) based on the clear separation between poisoned and clean samples. Extensive experiments under various settings of backdoor attacks demonstrate the superior detection performance of the proposed method to existing poisoned detection approaches according to sample activation-based metrics.
DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding
Venue: arXiv cs.RO 2024
Year: 2024

Multi-Agent Combinatorial Path Finding (MCPF) seeks collision-free paths for multiple agents from their initial to goal locations, while visiting a set of intermediate target locations in the middle of the paths. MCPF is challenging as it involves both planning collision-free paths for multiple agents and target sequencing, i.e., solving traveling salesman problems to assign targets to and find the visiting order for the agents. Recent work develops methods to address MCPF while minimizing the sum of individual arrival times at goals. Such a problem formulation may result in paths with different arrival times and lead to a long makespan, the maximum arrival time, among the agents. This paper proposes a min-max variant of MCPF, denoted as MCPF-max, that minimizes the makespan of the agents. While the existing methods (such as MS*) for MCPF can be adapted to solve MCPF-max, we further develop two new techniques based on MS* to defer the expensive target sequencing during planning to expedite the overall computation. We analyze the properties of the resulting algorithm Deferred MS* (DMS*), and test DMS* with up to 20 agents and 80 targets. We demonstrate the use of DMS* on differential-drive robots.
Partial End-to-end Reinforcement Learning for Robustness Against Modelling Error in Autonomous Racing
Venue: arXiv cs.RO 2024
Year: 2024

In this paper, we address the issue of increasing the performance of reinforcement learning (RL) solutions for autonomous racing cars when navigating under conditions where practical vehicle modelling errors (commonly known as \emph{model mismatches}) are present. To address this challenge, we propose a partial end-to-end algorithm that decouples the planning and control tasks. Within this framework, an RL agent generates a trajectory comprising a path and velocity, which is subsequently tracked using a pure pursuit steering controller and a proportional velocity controller, respectively. In contrast, many current learning-based (i.e., reinforcement and imitation learning) algorithms utilise an end-to-end approach whereby a deep neural network directly maps from sensor data to control commands. By leveraging the robustness of a classical controller, our partial end-to-end driving algorithm exhibits better robustness towards model mismatches than standard end-to-end algorithms.
Successive Bayesian Reconstructor for Channel Estimation in Fluid Antenna Systems
Venue: arXiv cs.IT 2024
Year: 2024

Fluid antenna systems (FASs) can reconfigure their antenna locations freely within a spatially continuous space. To keep favorable antenna positions, the channel state information (CSI) acquisition for FASs is essential. While some techniques have been proposed, most existing FAS channel estimators require several channel assumptions, such as slow variation and angular-domain sparsity. When these assumptions are not reasonable, the model mismatch may lead to unpredictable performance losses. In this paper, we propose the successive Bayesian reconstructor (S-BAR) as a general solution to estimate FAS channels. Unlike model-based estimators, the proposed S-BAR is prior-aided, which builds the experiential kernel for CSI acquisition. Inspired by Bayesian regression, the key idea of S-BAR is to model the FAS channels as a stochastic process, whose uncertainty can be successively eliminated by kernel-based sampling and regression. In this way, the predictive mean of the regressed stochastic process can be viewed as a Bayesian channel estimator. Simulation results verify that, in both model-mismatched and model-matched cases, the proposed S-BAR can achieve higher estimation accuracy than the existing schemes.