Although applications involving long-context inputs are crucial for the effective utilization of large language models (LLMs), they also result in increased computational costs and reduced performance. To address this challenge, we propose an efficient, training-free prompt compression method that retains key information within compressed prompts. We identify specific attention heads in transformer-based LLMs, which we designate as evaluator heads, that are capable of selecting tokens in long inputs that are most significant for inference. Building on this discovery, we develop EHPC, an Evaluator Head-based Prompt Compression method, which enables LLMs to rapidly "skim through'' input prompts by leveraging only the first few layers with evaluator heads during the pre-filling stage, subsequently passing only the important tokens to the model for inference. EHPC achieves state-of-the-art results across two mainstream benchmarks: prompt compression and long-context inference acceleration. Consequently, it effectively improves performance with the reduced costs associated with commercial API calls compared to prompt compressing methods. We further demonstrate that EHPC attains competitive results compared to key-value cache-based acceleration methods, thereby highlighting its potential to enhance the efficiency of LLMs for long-context tasks.

In this paper, we consider the problem of zero-error network function computation. In a directed acyclic network, a single sink node requires to compute with zero error a function of source messages generated by multiple source nodes. We are interested in the information-theoretic computing capacity, which is defined as the average number of times that the function can be computed with zero error for one use of the network. The explicit characterization of the computing capacity in general is extremely challenging. The best known upper bound, applicable to arbitrary network topologies and arbitrary target functions, is the one proved by Guang et al. using the cut-set strong partition approach. This bound is tight for all previously considered network function computation problems whose computing capacities are known. In this paper, we focus on the model of computing the binary arithmetic sum over an asymmetric diamond network, which is of great importance to illustrate the combinatorial nature of network function computation problem. We first prove an upper bound of 1 on the computing capacity by using a linear programming approach, which rectifies an invalid upper bound previously proposed in the literature. However, this upper bound does not surpass the best known upper bound for this model, which is also equal to 1. Further, by developing a different graph coloring approach, we obtain an improved upper bound 3–1 0.822). We thus show that the best known upper bound by Guang et al. is not tight for this model. On the other hand, we present an explicit code construction, which implies a lower bound 6 0.815) on the computing capacity. Comparing the improved upper and lower bounds thus obtained, there exists a rough 0.007 gap between them.

We consider a model of broadcast channel where a pair of base-user operates in the full-duplex mode. A partial decode-forward strategy together with Marton's coding are adopted to obtain an inner bound. An outer bound is also presented. Numerical evaluations are performed on a particular set of discrete memoryless channels to compare the sum-rates of these two bounds and the one of time division duplex.

Conditional graph entropy is known to be the minimal rate for a natural functional compression problem with side information at the receiver. In this paper we show that it can be formulated as an alternating minimization problem, which gives rise to a simple iterative algorithm for numerically computing (conditional) graph entropy. This also leads to a new formula which shows that conditional graph entropy is part of a more general framework: the solution of an optimization problem over a convex corner. In the special case of graph entropy (i.e., unconditioned version) this was known due to Csiszár, Körner, Lovász, Marton, and Simonyi. In that case the role of the convex corner was played by the so-called vertex packing polytope. In the conditional version it is a more intricate convex body but the function to minimize is the same. Furthermore, we describe a dual problem that leads to an optimality check and an error bound for the iterative algorithm.

The nascent field of Rate-Distortion-Perception (RDP) theory is seeing a surge of research interest due to the application of machine learning techniques in the area of lossy compression. The information RDP function characterizes the three-way trade-off between description rate, average distortion, and perceptual quality measured by discrepancy between probability distributions. However, computing RDP functions has been a challenge due to the introduction of the perceptual constraint, and existing research often resorts to data-driven methods. In this paper, we show that the information RDP function can be transformed into a Wasserstein Barycenter problem. The non-strictly convexity brought by the perceptual constraint can be regularized by an entropy regularization term. We prove that the entropy regularized model converges to the original problem. Furthermore, we propose an alternating iteration method based on the Sinkhorn algorithm to numerically solve the regularized optimization problem. Experimental results demonstrate the efficiency and accuracy of the proposed algorithm.

Recent advances in machine learning-aided lossy compression are incorporating perceptual fidelity into the rate-distortion theory. In this paper, we study the rate-distortion-perception trade-off when the perceptual quality is measured by the total variation distance between the empirical and product distributions of the discrete memoryless source and its reconstruction. We consider the general setting, where two types of resources are available at both the encoder and decoder: a common side information sequence, correlated with the source sequence, and common randomness. We consider both the strong perceptual constraint and the weaker empirical perceptual constraint. The required communication rate for achieving the distortion and empirical perceptual constraint is the minimum conditional mutual information, and similar result holds for strong perceptual constraint when sufficient common randomness is provided and the output along with the side information is constraint to an independent and identically distributed sequence.

Many real-world phenomena arise from causal relationships among a set of variables. As a powerful tool, Bayesian Network (BN) has been successful in describing high-dimensional distributions. However, the faithfulness condition, enforced in most BN learning algorithms, is violated in the settings where multiple variables synergistically affect the outcome (i.e., with polyadic dependencies). Building upon recent development in cluster causal diagrams (C-DAGs), we initiate the formal study of learning C-DAGs from observational data to relax the faithfulness condition. We propose a new scoring function, the Clustering Information Criterion (CIC), based on information-theoretic measures that represent various complex interactions among variables. The CIC score also contains a penalization of the model complexity under the minimum description length principle. We further provide a searching strategy to learn structures of high scores. Experiments on both synthetic and real data support the effectiveness of the proposed method.

It is well known that joint interactions between agents can be described qualitatively as having synergistic, unique, and redundant components. In recent years, there have been renewed efforts to decompose mutual information, a general, non-parametric measure of joint interactions, into constituent parts. We propose a novel, non-negative decomposition of mutual information between two sources and a target variable. The decomposition is for the exponential family, and thus can be applied to a broad range of distributions. We also show that values from our decomposition arise naturally from testing hypotheses of conditional dependence. We demonstrate the method numerically using standard binary logic gates and Gaussian channels, as well as apply the method to investigate redundancy between brain regions using an fMRI-based image classification data-set.