Directed Information $γ$-covering: An Information-Theoretic Framework for Context Engineering

• URL: http://arxiv.org/abs/2510.00079v1
• Date: Tue, 30 Sep 2025 02:41:11 GMT
• Title: Directed Information $γ$-covering: An Information-Theoretic Framework for Context Engineering
• Abstract summary: We introduceDirected Information $gamma$-covering, a framework for redundancy-aware context engineering.<n>Building the $gamma$-cover is emphquery-agnostic: it incurs no online cost and can be computed once offline and amortized across all queries.<n>These results establish DI $gamma$-covering as a principled, self-organizing backbone for modern LLM pipelines.
• Score: 2.541246776283285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce \textbf{Directed Information $\gamma$-covering}, a simple but general framework for redundancy-aware context engineering. Directed information (DI), a causal analogue of mutual information, measures asymmetric predictiveness between chunks. If $\operatorname{DI}_{i \to j} \ge H(C_j) - \gamma$, then $C_i$ suffices to represent $C_j$ up to $\gamma$ bits. Building on this criterion, we formulate context selection as a $\gamma$-cover problem and propose a greedy algorithm with provable guarantees: it preserves query information within bounded slack, inherits $(1+\ln n)$ and $(1-1/e)$ approximations from submodular set cover, and enforces a diversity margin. Importantly, building the $\gamma$-cover is \emph{query-agnostic}: it incurs no online cost and can be computed once offline and amortized across all queries. Experiments on HotpotQA show that $\gamma$-covering consistently improves over BM25, a competitive baseline, and provides clear advantages in hard-decision regimes such as context compression and single-slot prompt selection. These results establish DI $\gamma$-covering as a principled, self-organizing backbone for modern LLM pipelines.

Related papers

• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  We show that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be nearly achieved in dimension $d = O(mathsfmmathsfrd(+infty, A)-2log n)$.<n>Our main theorem establishes that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be
  arXiv  Detail & Related papers  (2026-05-22T12:22:20Z)
• Covering a Few Submodular Constraints and Applications [2.243805796685295]
  We consider the problem of covering multiple submodular constraints.<n>For covering multiple submodular constraints we obtain a randomized bi-criteria approximation that for any given integer $alpha ge 1$ outputs a set $S$ such that $f_i(S) ge$ $(1-1/ealpha -epsilon)b_i$ for each $i in [r]$ and $mathbbE[c(S)] le (1+epsilon)alpha cdot sfOPT$.
  arXiv  Detail & Related papers  (2025-07-14T03:32:42Z)
• Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples [24.45016514352055]
  We study the sample-complexity of learning $T+1$ functions $f_star(t) circ g_star$ from a function class $mathcal F times mathcal G$. We show that as the number of tasks $T$ increases, both the sample requirement and risk bound converge to that of $r$-dimensional regression.
  arXiv  Detail & Related papers  (2024-10-15T03:20:19Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  We show that when $rho$ is concentrated near an $mtext-d$ set we may interpret this as a manifold learning problem with noisy data.<n>We quantify $nu$'s performance in approximating $rho$ via the Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$, and constrain the complexity by requiring $mathrmsupp nu$ to be coverable by an $f : mathbbRm
  arXiv  Detail & Related papers  (2024-09-25T01:30:16Z)
• GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility [16.843606527688326]
  We study a novel subset selection problem called max-min diversification with monotone submodular utility ($textsfMDMS$)<n>Given a set of points in a metric space, the goal of $textsfMDMS$ is to maximize $f(S) = g(S) + lambda cdot textttdiv(S)$ subject to a cardinality constraint.<n>We show that $texttGIST$ outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet
  arXiv  Detail & Related papers  (2024-05-29T04:39:24Z)
• On Understanding Attention-Based In-Context Learning for Categorical Data [49.40350941996942]
  We develop a network composed of attention blocks, with each block employing a self-attention layer followed by a cross-attention layer, with associated skip connections.<n>This model can exactly perform multi-step functional GD inference for in-context inference with categorical observations.
  arXiv  Detail & Related papers  (2024-05-27T15:03:21Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  We provide the first differentially private algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean data points over a stream with length at most $T$.<n>Our main technical contribution is a differentially private clustering framework for data streams which only requires an offline DP coreset or clustering algorithm as a blackbox.
  arXiv  Detail & Related papers  (2023-07-14T16:11:22Z)
• Active Learning of Classifiers with Label and Seed Queries [18.34182076906661]
  In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin $gamma$ requires in the worst case $Omegabig(k m log frac1gammabig)$ seed queries. We show that, by carefully combining the two types of queries, a binary classifier can be learned in time $operatornamepoly(n+m)$ using only $O(m2 log n)$ label queries and $Obig(m log fracmgamma
  arXiv  Detail & Related papers  (2022-09-08T18:46:23Z)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  We propose a simple and practical tool $mathsfFriendlyCore$ that takes a set of points $cal D$ from an unrestricted (pseudo) metric space as input. When $cal D$ has effective diameter $r$, $mathsfFriendlyCore$ returns a "stable" subset $cal D_Gsubseteq cal D$ that includes all points. $mathsfFriendlyCore$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy
  arXiv  Detail & Related papers  (2021-10-19T17:43:50Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states.
  arXiv  Detail & Related papers  (2021-06-18T07:54:23Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes with $S$ states, $A$ actions and planning horizon $H$. We obtain the first set of nearly $H$-free sample complexity bounds for evaluation and planning using the empirical MDPs.
  arXiv  Detail & Related papers  (2021-03-25T18:52:17Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.