Retrieval augmentation enables large language models to take advantage of
external knowledge, for example on tasks like question answering and data
imputation. However, the performance of such retrieval-augmented models is
limited by the data quality of their underlying retrieval corpus. In this
paper, we propose an algorithm based on multilinear extension for evaluating
the data importance of retrieved data points. There are exponentially many
terms in the multilinear extension, and one key contribution of this paper is a
polynomial time algorithm that computes exactly, given a retrieval-augmented
model with an additive utility function and a validation set, the data
importance of data points in the retrieval corpus using the multilinear
extension of the model's utility function. We further proposed an even more
efficient ({\epsilon}, {\delta})-approximation algorithm. Our experimental
results illustrate that we can enhance the performance of large language models
by only pruning or reweighting the retrieval corpus, without requiring further
training. For some tasks, this even allows a small model (e.g., GPT-JT),
augmented with a search engine API, to outperform GPT-3.5 (without retrieval
augmentation). Moreover, we show that weights based on multilinear extension
can be computed efficiently in practice (e.g., in less than ten minutes for a
corpus with 100 million elements).

通过修剪或重新权重检索语料库，可以提高大型语言模型的性能，无需进行进一步训练。在某些任务中，甚至允许较小的模型（例如 GPT-JT）通过搜索引擎 API 进行扩展，胜过未使用检索增强的 GPT-3.5。此外，我们展示了在实践中可以高效地计算基于多线性扩展的权重（例如，对于包含 1 亿个元素的语料库，计算时间少于十分钟）

通过数据重要性学习改进检索增强的大型语言模型

Improving Retrieval-Augmented Large Language Models via Data Importance  Learning

The study of combinatorial optimization problems with a submodular objective
has attracted much attention in recent years. Such problems are important in
both theory and practice because their objective functions are very general.
Obtaining further improvements for many submodular maximization problems boils
down to finding better algorithms for optimizing a relaxation of them known as
the multilinear extension.
In this work we present an algorithm for optimizing the multilinear
relaxation whose guarantee improves over the guarantee of the best previous
algorithm (which was given by Ene and Nguyen (2016)). Moreover, our algorithm
is based on a new technique which is, arguably, simpler and more natural for
the problem at hand. In a nutshell, previous algorithms for this problem rely
on symmetry properties which are natural only in the absence of a constraint.
Our technique avoids the need to resort to such properties, and thus, seems to
be a better fit for constrained problems.

本文研究了带有子模性目标函数的组合优化问题，提出了一种基于新技术的算法来优化多线性松弛问题，该算法避免了对称性等性质的需要，适用于约束问题，相比之前的算法，它具有更好的保证。

通过非对称技术来实现受限子模最大化

Constrained Submodular Maximization via a Non-symmetric Technique

We consider the problem of maximizing a non-negative submodular set function
$f:2^N \rightarrow \mathbb{R}_+$ over a ground set $N$ subject to a variety of
packing type constraints including (multiple) matroid constraints, knapsack
constraints, and their intersections. In this paper we develop a general
framework that allows us to derive a number of new results, in particular when
$f$ may be a non-monotone function. Our algorithms are based on (approximately)
maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that
represents the constraints, and then effectively rounding the fractional
solution. Although this approach has been used quite successfully, it has been
limited in some important ways. We overcome these limitations as follows.
First, we give constant factor approximation algorithms to maximize $F$ over
a down-closed polytope $P$ described by an efficient separation oracle.
Previously this was known only for monotone functions. For non-monotone
functions, a constant factor was known only when the polytope was either the
intersection of a fixed number of knapsack constraints or a matroid polytope.
Second, we show that contention resolution schemes are an effective way to
round a fractional solution, even when $f$ is non-monotone. In particular,
contention resolution schemes for different polytopes can be combined to handle
the intersection of different constraints. Via LP duality we show that a
contention resolution scheme for a constraint is related to the correlation gap
of weighted rank functions of the constraint. This leads to an optimal
contention resolution scheme for the matroid polytope.
Our results provide a broadly applicable framework for maximizing linear and
submodular functions subject to independence constraints. We give several
illustrative examples. Contention resolution schemes may find other
applications.

研究了如何在不同的 packing 类型约束下，最大化定义在给定集合上的非负子模函数，提出了一个基于多线性扩展和分数解取整的算法框架，并且解决了其中的一些重要限制问题，开辟了线性和子模函数最大化的新方法。