tcb@breakable

# Entropy Law: The Story Behind Data Compression and LLM Performance

Mingjia Yin†, Chuhan Wu${}^{*^{\dagger}}$, Yufei Wang†, Hao
Wang${}^{*^{\dagger}}$,
Wei Guo, Yasheng Wang, Yong Liu, Ruiming Tang∗, Defu Lian, Enhong Chen
State Key Laboratory of Cognitive Intelligence & University of Science and
Technology of China
Noah’s Ark Lab, Huawei
{mingjia-yin, wanghao3<EMAIL_ADDRESS>
{wuchuhan1<EMAIL_ADDRESS>
Corresponding authors. $\dagger$ Equal contribution.

###### Abstract

Data is the cornerstone of large language models (LLMs), but not all data is
useful for model learning. Carefully selected data can better elicit the
capabilities of LLMs with much less computational overhead. Most methods
concentrate on evaluating the quality of individual samples in data selection,
while the combinatorial effects among samples are neglected. Even if each
sample is of perfect quality, their combinations may be suboptimal in teaching
LLMs due to their intrinsic homogeneity or contradiction. In this paper, we
aim to uncover the underlying relationships between LLM performance and data
selection. Inspired by the information compression nature of LLMs, we uncover
an “entropy law” that connects LLM performance with data compression ratio and
first-epoch training loss, which reflect the information redundancy of a
dataset and the mastery of inherent knowledge encoded in this dataset,
respectively. Through both theoretical deduction and empirical evaluation, we
find that model performance is negatively correlated to the compression ratio
of training data, which usually yields a lower training loss. Based on the
findings of the entropy law, we propose a quite efficient and universal data
selection method named ZIP for training LLMs, which aim to prioritize data
subsets exhibiting a low compression ratio. Based on a multi-stage algorithm
that selects diverse data in a greedy manner, we can obtain a good data subset
with satisfactory diversity. Extensive experiments have been conducted to
validate the entropy law and the superiority of ZIP across different LLM
backbones and alignment stages. We also present an interesting application of
entropy law that can detect potential performance risks at the beginning of
model training.111Code can be found in https://github.com/USTC-StarTeam/ZIP.

##  1 Introduction

In recent years, Large Language Models (LLMs) have gained significant
attention from both academia and industry, applied in various domains, such as
chatbots (Ouyang et al., 2022; Achiam et al., 2023), chemistry tools (M. Bran
et al., 2024), and programming assistants (GitHub, 2020). The great success of
LLMs depends on their general intelligence obtained from a vast amount of data
collected from various sources (Albalak et al., 2024; Wang et al., 2023c).
Through pretraining on trillions of tokens to master diverse knowledge and
tuning on smaller instruction data to align models with human preference, LLMs
can effectively utilize their knowledge to follow user instructions, do
commonsense reasoning, and solve real-world problems (Zhao et al., 2023).

However, not all data are useful for teaching LLMs, especially when
computational resources are limited (Albalak et al., 2024). For example, we
can better elicit the capability of LLMs by fine-tuning them on carefully
curated samples rather than a large but noisy data collection (Ouyang et al.,
2022; Chowdhery et al., 2023; Meta, 2020; Zhou et al., 2023). However,
selecting the proper data for LLM training is quite complicated and abstruse,
since the space of data preprocessing and combination is almost unlimited. Due
to the huge computational overhead of LLM training, manual or empirical data
selection based on trial-and-error feedback is rather cumbersome and even
impractical. Therefore, automatic data selection methods are necessary for LLM
development under limited computational budgets.

Intuitively, high-quality samples are expected to have better efficiency in
teaching LLMs. For example, the successful practice of LIMA (Zhou et al.,
2023) shows the powerful effect of data quality on LLM performance that can
surpass the amount of data. Therefore, existing methods usually focus on
quality-oriented data selection, based either on heuristic rules (Raffel et
al., 2020; Rae et al., 2021; Xie et al., 2023; Chowdhery et al., 2023; Li et
al., 2023) or evaluation models (Wettig et al., 2024; Chen et al., 2023; Lu et
al., 2023; Liu et al., 2023; Cui et al., 2023). Heuristic methods typically
involve hand-crafted rules (e.g., sentence number (Raffel et al., 2020), word
count (Rae et al., 2021), length (Shen, 2024)) to evaluate data across
multiple dimensions. Model-based approaches, on the contrary, rely on well-
established LLMs such as GPT-4 (Achiam et al., 2023) to provide quality
assessments of training samples in different views, such as direct scoring
(Chen et al., 2023), task tagging (Lu et al., 2023), and pairwise scoring (Liu
et al., 2023). However, most of these approaches evaluate different data
samples independently, which neglects the intricate combinatorial effects
among samples. As illustrated in Figure 1, even if each sample is in perfect
quality, their combinations may still be suboptimal due to their mutual
information redundancy or inconsistency. Although the quality-based subset is
composed of all three good samples, the knowledge they encode is actually
redundant and conflicting. In contrast, another data subset composed of
several relatively lower-quality but diverse samples may convey more
information than the above subset in the teaching of LLMs. Therefore, quality-
based data selection does not fully align with the goal of maximizing the
knowledge mastery of LLMs.

Figure 1:  An illustrative example describing different data selection
paradigms. Quality-based data selection relies on sample-level data quality
measurements while overlooking combinatorial effects among samples.
Information-amount-based selection aims to select samples maximizing the
overall information amount.

In many recent studies, researchers have shown that the basic mechanism of
auto-regressive language modeling in LLMs is information compression (Delétang
et al., 2023; Huang et al., 2024). Thus, the knowledge condensed by LLMs
actually depends on the effective information encoded by training data. This
intuition opens another direction of data selection, i.e., based on the
effective information amount of data. In this paper, we uncover the underlying
relations between LLM performance and data homogeneity, which can be measured
by various canonical lossless compression algorithms (e.g., DEFLATE in ZIP).
Through both theoretical analysis and empirical experiments, we formulate the
“entropy law”, which shows that the compression ratio of training data is a
decisive factor affecting model performance, if the overall quality and
consistency of selected samples remain unchanged. Motivated by the entropy
law, we propose an effective and efficient data selection algorithm called ZIP
to select heterogeneous data with low compression ratio, which aims to
maximize the effective information amount of information for LLM learning.
Specifically, we devise a multi-stage greedy strategy to find an approximate
solution that guarantees a low compression ratio without exhausting all
possible combinations, and it iterates continuously until we obtain a
predetermined number of samples. In each iteration, ZIP performs preliminary
filtering to choose a smaller pool of candidates, and then selects a few
samples from the reduced pool that minimizes the compression ratio of the
selected dataset through a cascaded manner. By learning LLMs on a collection
of diverse samples that encode heterogeneous and complementary information,
the capabilities of LLMs can be better elicited. Extensive experiments on
different LLM backbones at different stages of LLM alignment demonstrate the
superiority of ZIP over various quality-based baselines. We also present an
interesting application of the entropy law that can detect potential
performance risks at the beginning of model training, which can effectively
reduce the computational overhead in LLM development.

##  2 Related Works

###  2.1 Large Modeling and Information Compression

The relationship between language modeling and data compression has long
intrigued researchers (Shannon, 1948, 1951). Pandey (2024) has identified a
data-dependant scaling law that takes data’s gzip compressibility into
consideration. Besides, recent empirical studies have confirmed that language
models can act as versatile data compressors (Delétang et al., 2023), and the
intelligence of LLMs can be quantified by their capacity for text compression
(Huang et al., 2024). Let a text corpus be generated from an underlying
distribution $\rho$. A lossless compression algorithm $\mathcal{C}$ is then
expected to encode a text sequence $x_{1:n}$ into a bitstream
$\mathcal{C}(x_{1:n})$ of minimal length, ensuring that $x_{1:n}$ can be
perfectly recovered from $\mathcal{C}(x_{1:n})$. The expected number of bits
of an optimal $\mathcal{C}$ is equal to
$\mathbb{E}_{x\sim\rho}[-\log_{2}\rho(x)]=\mathbb{E}_{x\sim\rho}[-\sum_{i=1}^{n}\log_{2}\rho(x_{i}|x_{1:i-1})]$
(Shannon, 1948). The underlying distribution $\rho$ is usually unknown in
reality, but it can be estimated by a language model $\rho_{\text{model}}$.
Then the expected number of bits of an optimal $\mathcal{C}$ can be updated:

$\mathbb{E}_{x\sim\rho}[-\sum_{i=1}^{n}\log_{2}\rho_{\text{model}}(x_{i}|x_{1:i-1})].$
(1)

Equation 1 is the cross-entropy loss employed in training LLMs, thereby
establishing a coherent relationship between LLMs and information compression.
This foundational insight paves the way for this work.

###  2.2 Alignment of Large Language Models

Large Language Models (LLMs) have recently gained significant attention from
academia and industry. LLM alignment, which includes supervised fine-tuning
(SFT) and reinforcement learning with human feedback (RLHF), has emerged as a
crucial technique for adapting LLMs to end tasks using natural language
instructions (Zhao et al., 2023; Wang et al., 2023c). Alignment is performed
using instruction datasets consisting of multiple (Instruction, Output) pairs,
which require LLMs to follow the instructions and generate corresponding
outputs. Early explorations have focused on constructing or expanding
instruction datasets through methods such as crowd-sourcing (Wang et al.,
2022; Köpf et al., 2024), self-instruction (Taori et al., 2023; Peng et al.,
2023; Wang et al., 2023b), or the combination of existing datasets (Wang et
al., 2023a; Ivison et al., 2023). Fine-tuned LLMs on these datasets have
demonstrated promising capabilities to adhere to instructions across various
contexts and align with human expectations.

###  2.3 Data selection for LLM alignment

A growing body of research has emphasized the importance of selecting
appropriate data for LLM alignment, which can prevent potential quality issues
and optimize computational resource allocation. As a prominent example, Lima
(Zhou et al., 2023) has demonstrated superior performance by carefully
crafting only 1,000 high-quality samples for SFT, highlighting the crucial
importance of data quality. The current literature on selecting alignment data
has focused on selecting samples according to individual sample quality, which
can be categorized into heuristic methods (Shen, 2024) and model-based methods
(Chen et al., 2023; Lu et al., 2023; Liu et al., 2023; Li et al., 2023, 2024;
Du et al., 2023). Heuristic methods typically employ specific criteria, such
as response length (Shen, 2024), to guide data selection. On the other hand,
model-based methods adopt various strategies to leverage the capabilities of
established language models for evaluating sample quality. For example, IFD
(Li et al., 2023) measures the change in response loss when instructions are
removed, and selects those with the most significant changes. Building upon
IFD, SuperFiltering (Li et al., 2024) introduces a lightweight proxy model for
a more efficient calculation of the IFD score. In addition, other model-based
methods employ proprietary LLMs to assess data quality. In a pioneering work,
AlpaGasus (Chen et al., 2023) uses ChatGPT directly to assign data quality
scores to samples, while #InsTag (Lu et al., 2023) proposes assigning tags to
each sample using ChatGPT and evaluates sample quality based on the number of
tags. DEITA (Liu et al., 2023) uses ChatGPT-generated data to train two Llama-
based scorers, assigning complexity and quality scores to each sample, and
ultimately selecting samples with the highest hybrid scores. However, existing
methods are mainly designed to pick data based on sample-wise quality
measurements, which are usually weak in reflecting the overall dataset
quality. In this paper, we focus on the relation between performance and
dataset quality, which can be efficiently measured by data compression
metrics.

##  3 Entropy Law: Connecting Model Performance with Data Compression

In this section, we provide some theoretical analysis of the relations between
data compression and LLM performance. Intuitively, the correctness and
diversity of the training data would affect the performance of the final
model. Meanwhile, the performance of LLM may be suboptimal if the data have
severe intrinsic conflicts or the model has poor mastery of the information
encoded by the data, which can be indicated by the training loss. Based on
these assumptions, we denote the performance of an LLM as $Z$, which is
expected to be influenced by the following factors:

  * •

Data compression ratio $R$: This metric can be derived by dividing the pre-
compression data size by the post-compression size, which can be computed by
various off-the-shelf compression algorithms. Intuitively, a dataset with a
lower compression ratio indicates a higher information density.

  * •

Training loss $L$: Indicates whether the data are hard for the model to
memorize. Given the same base model, a high training loss is usually due to
noisy or inconsistent information in the dataset. In practice, the average
loss of a small number of training steps in the first training epoch is
sufficient to produce an indicative $L$ value so that the model does not
overfit the data.

  * •

Data consistency $C$: The consistency of data is reflected by the entropy of
the probability of the next token given the previous contexts. Higher data
consistency usually yields a lower training loss. The performance of LLMs is
usually suboptimal if the dataset has poor consistency.222 Assume we have two
question-answer pairs $(q_{1},a_{1})$ and $(q_{2},a_{2})$. When an LLM updates
on each QA pair, it learns the mutual information (MI) between the question
and answer, i.e., $I(q_{1};a_{1})$ and $I(q_{2};a_{2})$. When it updates on
both, it learns the joint MI $I(q_{1}q_{2};a_{1}a_{2})$. If $q_{1}$ and
$q_{2}$ are not independent, we have
$I(q_{1}q_{2};a_{1}a_{2})<I(q_{1};a_{1})+I(q_{2};a_{2})$, whose detailed
derivation can be found in Appendix A. This implies that the total knowledge
learned by LLMs is narrowed if the answers to similar questions are highly
inconsistent.

  * •

Average data quality $Q$: This reflects the average sample-level quality of
the data, which can be measured through various objective and subjective
aspects.

Given a certain amount of training data, the model performance can be
estimated by the above factors:

$Z\propto f(R,L,C,Q),$ (2)

where $f$ is a hidden function. Given a specific base model, the scale of $L$
usually depends on $R$ and $C$, which can be formulated as:

$L\propto g(R,C).$ (3)

$L$ is expected to be monotonous on $R$ and $C$, since a dataset with higher
homogeneity or better data consistency is easier for a model to learn. Thus,
we can rewrite the above formula as follows:

$C\propto g^{\prime}(R,L),$ (4)

where $g^{\prime}$ is an inverse function. By combining the three above
equations, we have:

$Z\propto f(R,L,g^{\prime}(R,L),Q)\propto h(R,L,Q),$ (5)

where $h$ is another hidden function. If a data selection method does not
substantially change the average data quality $Q$, we can approximately regard
the variable $Q$ as a constant. Therefore, the final performance can be
roughly formulated as follows:

$Z\propto h^{\prime}(R,L),$ (6)

which means that the model performance is correlated with the data compression
ratio and training loss. We name this relationship as “Entropy Law”.

We can raise two deductions based on the entropy law:

  * •

If we further regard the data consistency as a constant, the training loss is
directly influenced by the compression ratio (Eq. 3). Thus, the model
performance is controlled by the compression ratio: $Z$ is usually worse if
the data compression ratio $R$ is higher, which will be validated by our
experiments.

  * •

Given the same compression ratio $R$, a higher training loss means a lower
data consistency. Thus, the effective knowledge learned by the model may be
more limited. This can be used to predict the performance of LLM on different
data with similar compression ratios and sample qualities. We will show later
the application of this deduction in our practice.

Notably, entropy law reveals a coherent connection between downstream model
performance and data compression ratio, setting it apart from the previously
proposed data-dependent scaling law by Pandey (2024). Building upon the
entropy law, we derive a data selection algorithm in Section 4 and demonstrate
its application in practical large-scale LLM development in Section 5.3.

##  4 ZIP: Lightweight Data Selection for LLM Alignment

Guided by the findings of the entropy law, we propose an effective and
efficient method named ZIP to select data samples based on data compression
ratios, which aims to maximize the amount of effective information given a
limited training data budget. Although there exists a subset with the lowest
compression ratio, it is impractical to find it due to the huge combination
space of data samples. Thus, we propose an iterative multi-stage greedy
algorithm to efficiently obtain an approximate solution with a relatively low
compression ratio. In each iteration, we first use a global selection stage to
choose a pool of candidate samples that have low compression ratios, which
aims to find samples with high information density. We then employ a coarse-
grained local selection stage incorporating a smaller set of samples with the
lowest redundancy with already selected samples. Finally, we use a fine-
grained local selection stage that minimizes the similarity between samples to
add. The above process is conducted until we obtain a sufficient size of data.
The workflow of our method is summarized in Algorithm 1, whose details are
introduced as follows.

###  4.1 Global Selection

In general, we maintain an information redundancy state $\pi_{\mathcal{D}}$
that evaluates the “information gain” of each sample. Intuitively, data with
high intra-sample information redundancy are unlikely to have good global
diversity. For example, a sample with repeated patterns or echoed conversation
turns usually has low education value in LLM training. Thus, we initialize
this state by calculating the sample-level compression ratio for the entire
dataset $\mathcal{D}$. In each iteration, We select $K_{1}$ samples with the
lowest scores in $\pi_{\mathcal{D}}$ to form an initial candidate pool
$\mathcal{D}_{K_{1}}$, which provides a good set for subsequent local
selection.

###  4.2 Local Coarse-grained Selection

Since the global selection does not well consider the mutual relations among
samples, we further conduct local selection to pick diverse samples. To ensure
good computational efficiency, we introduce a coarse-grained selection phase
to narrow the candidate pool into a smaller one with $K_{2}$ samples. We first
compute the compression ratio of a merged set that adds each sample in
$\mathcal{D}_{K_{1}}$ to the selected set $\mathcal{D}^{\prime}$. We use this
score to update the information redundancy state $\pi_{\mathcal{D}}$ to better
indicate the current information gain of these samples. Based on the scores of
the samples in $\mathcal{D}_{K_{1}}$, we select $K_{2}$ samples with the
lowest scores. These samples form a small subset for final fine-grained
selection, where each sample has good diversity with the selected dataset
$\mathcal{D}^{\prime}$.

Algorithm 1 Pseudo code of ZIP

1:The original dataset $\mathcal{D}$ of size $N$. A data compressor
$\mathcal{C}$. The number of selected samples $m$. The number of compression
ratios to be updated in the global selection $K_{1}$. The data pool size of
local selection $K_{2}$. The data budget of local selection $K_{3}$.
Compression ratio calculation function
$g(\mathcal{C}(D))=\frac{\text{Bits}(D)}{\text{Bits}(\mathcal{C}(D))}$, which
measures compression ratio by the number of bits.

2:A data subset $\mathcal{D}^{\prime}$ of size $m$ with a relatively low
compression ratio.

3:Init $\mathcal{D}^{\prime}$ as an empty set $\Phi$

4:Init $\pi_{\mathcal{D}}=\\{g(d_{0}),g(d_{1}),\dots,g(d_{N})\\}$ by
calculating the compression ratio of each sample in $\mathcal{D}$

5:while $|\mathcal{D}^{\prime}|<m$ do

6: // Stage 1: Global Selection

7: $\mathcal{D}_{K_{1}}$ =
Bottom-K($\mathcal{D}\setminus\mathcal{D}^{\prime}$,
$\pi_{\mathcal{D}\setminus\mathcal{D}^{\prime}}$, $K_{1}$) // Select $K_{1}$
samples with the lowest scores

8: // Stage 2: Local Coarse-grained Selection

9: $\pi_{K_{1}}=g(\mathcal{D}^{\prime}\cup\\{d\\})$, where
$d\in\mathcal{D}_{K_{1}}$ //Compression ratios of the union of
$\mathcal{D}^{\prime}$ and $d$

10: Update corresponding values in $\pi_{\mathcal{D}}$ with $\pi_{K_{1}}$

11: $\mathcal{D}_{K_{2}}$ = Bottom-K($\mathcal{D}_{K_{1}}$, $\pi_{K_{1}}$,
$K_{2}$) // Select $K_{2}$ samples with the lowest compression ratios

12: // Stage 3: Local Fine-grained Selection

13: Init $\mathcal{D}_{K_{3}}$ as an empty set $\Phi$

14: while $|\mathcal{D}_{K_{3}}|<K_{3}$ do

15:
$\pi_{K_{2}}=\\{g(\mathcal{D}_{K_{3}}\cup\\{d\\})|d\in\mathcal{D}_{K_{2}}\\}$

16: d = $\operatorname*{arg\,min}_{d}{\pi_{K_{2}}}$

17: $\mathcal{D}_{K_{3}}$ = $\mathcal{D}_{K_{3}}\cup\\{d\\}$

18: $\mathcal{D}_{K_{2}}$ = $\mathcal{D}_{K_{2}}\setminus\\{d\\}$

19: end while

20: // Update the selected dataset

21: $\mathcal{D}^{\prime}=\mathcal{D}^{\prime}\cup\mathcal{D}_{K_{3}}$

22:end while

###  4.3 Local Fine-grained Selection

Although the above stage ensures that the candidate pool has distinct
information from the selected set, the information redundancy among the
samples within this pool is not measured. Thus, we aim to pick further samples
from this subset that are diverse from each other. Concretely, we initialize a
local selected set $\mathcal{D}_{K_{3}}$, and compute the compression ratio of
the union of $\mathcal{D}_{K_{3}}$ and each sample in $\mathcal{D}_{K_{2}}$.
We add the sample with the lowest compression ratio into
$\mathcal{D}_{K_{3}}$, and remove it from $\mathcal{D}_{K_{2}}$. By repeating
this process, we obtain a small subset that contains samples not only
different from the selected set $\mathcal{D}^{\prime}$ but also distinct from
each other. We conduct the three stages above until the size of
$\mathcal{D}^{\prime}$ reaches a predefined data budget $m$. In our method,
the entire selection process is quite easy to implement since it is model-
free, and can be accelerated using multiple threads. It can select data
efficiently and effectively from a large candidate pool for high-quality LLM
training.

##  5 Experiments

ZIP is content-agnostic and model-free, making it suitable for various stages
of LLM alignment. We systematically evaluate the effectiveness of ZIP through
experiments conducted in the SFT and RLHF stages, as described in Sections 5.1
and 5.2, respectively. Subsequently, Section 5.3 presents an in-depth analysis
to empirically support the proposed entropy law, including a practical
application guided by this law.

###  5.1 Data Selection for SFT

####  5.1.1 Setup

Data Pool & Data Selection We follow DEITA (Liu et al., 2023) to establish a
large-scale data pool comprising 300K high-quality samples obtained from
WizardLM (Xu et al., 2023), ShareGPT (Chiang et al., 2023), and UltraChat
(Ding et al., 2023). Subsequently, various data selection techniques are
employed to extract a subset of this pool for LLM instruction tuning. Notably,
previous studies controlled the data budget by limiting the number of
instances, whereas we managed the total token count to ensure a fair
allocation of the compute budget among all methods. To achieve this, we
initially select 10,000 samples using ZIP and calculate the corresponding
token count. Then, we apply other methods to continue data selection until the
required token count is reached.

Training & Evaluation We fine-tune Mistral-7B (Jiang et al., 2023) and
LLama-3-8B (Meta, 2020) on the selected dataset. Other training details can be
found in Appendix B. As for evaluation, we adopt MT-bench(Zheng et al., 2023)
as our benchmark. Specifically, MT-bench is a challenging multi-turn question
set with LLM judgements to evaluate model responses, which exhibits a high-
level human preferences alignment.

Baselines We select the baseline from two aspects. The first group includes
heuristic methods: (1) Random, which randomly selects instances from the data
pool to verify the fundamental effectiveness of other methods; (2) Cluster,
which adopts K-means clustering based on the sample representations and select
cluster centroids; (3) Perplexity, which selects the samples with highest
training loss. The second group of baselines includes model-based methods: (1)
DEITA (Liu et al., 2023), which employs ChatGPT-generated data to train a
Llama-based data complexity evaluator and a quality evaluator, and selects
samples with the highest hybrid scores; (2) SuperFiltering (Li et al., 2024),
which assesses each sample by calculating the change in response loss upon
instruction removal and introduce a lightweight proxy model to calculate the
score more efficiently.

####  5.1.2 Results

Table 1: Model performance comparison between different data selection baselines based on Mistral-7B and Llama-3-8B on the SFT stage. We also provide the computational cost, average token length of selected data, and the average data quality produced by Alpagasus Chen et al. (2023). The best results are bolded, and the second-best numbers are underlined. $\dagger$ means CPU-only methods. Model | MT-bench $\uparrow$ | Cost $\downarrow$ | Avg.length | Quality
---|---|---|---|---
Mistral-7B-based models with SFT
Random $\dagger$ | 6.85 | 10s | 976 | 4.08
Cluster |  6.91 | 15h | 970 | 4.05
Perplexity | 6.89 | 8h | 981 | 4.09
SuperFiltering | 6.12 | 14h | 1579 | 4.10
DEITA | 6.82 | 21h | 2048 | 4.03
ZIP $\dagger$ | 7.08 |  4.5h | 543 | 4.00
Llama-3-8B-based models with SFT
Random $\dagger$ | 7.16 | 10s | 892 | 4.08
Cluster |  7.18 | 16h | 886 | 3.95
Perplexity | 7.09 | 9h | 895 | 3.96
SuperFiltering | 6.59 | 14h | 1481 | 3.99
DEITA | 7.11 | 21h | 2048 | 4.09
ZIP $\dagger$ | 7.28 |  4.5h | 470 | 4.00

Main comparison We compare ZIP with various data selection methods based on
Mistral-7B and Llama-3-8B, and the results are presented in Table 1. ZIP
outperforms other data selection approaches on all backbones, which can be
attributed to ZIP’s ability to model the complex combinatorial effects among
samples. Furthermore, our observations indicate that model-based data
selection methods often fail to produce satisfactory outcomes when a fixed
token number is given. This is because the sample-level evaluations are not
updated correspondingly after selecting some samples, leading to biased
evaluations for the remaining samples. Additionally, some of these methods
adopt strategies to enhance data diversity, such as DEITA, which controls the
representation distances of selected samples. However, these strategies only
provide a rough assessment of the combinatorial effects within the
representation space, since semantic distances do not necessarily reflect
information redundancy.

Selection bias in sample length across different strategies We also provide
the average length of tokenized samples in Table 1. The average token length
of Random provides an estimation for the entire data pool, which is used to
analyze other methods. From the tables, we can observe that Cluster and
Perplexity exhibit similar selection preferences as Random. Additionally,
Deita and SuperFiltering predominantly select lengthy data samples. This bias
may stem from the LLMs’ inclination toward generating longer responses (Saito
et al., 2023). However, given the limited budget of selected tokens, choosing
excessively lengthy data will reduce the information density and degrade the
capabilities of models trained on such data. In contrast, ZIP tends to select
shorter samples. Furthermore, we plot the token length distribution of these
methods, as depicted in Figure 2 and Figure 6. Consistent with the previous
results, we can observe similar distributions for Random, Cluster, and
Perplexity. The token length distributions of DEITA and SuperFiltering are
severely skewed, deviating greatly from the original data distribution. In
contrast to these model-based approaches, ZIP exhibits no bias toward
selecting lengthy samples.

Cost comparison of different strategies We provide a detailed cost analysis of
each method in Table 1. Except for the Random method, ZIP required the least
time to complete the data selection process, demonstrating greater efficiency
than other methods. Notably, ZIP’s computations are entirely executed on CPUs,
resulting in significant cost savings. Furthermore, ZIP is independent of
proprietary LLMs used by DEITA or the proxy model employed by Cluster,
Perplexity, and SuperFiltering. This model-free characteristic endows ZIP with
notable efficiency and versatility.

(a) ZIP

(b) Random

(c) Diversity

(d) Perplexity

(e) DEITA

(f) SuperFiltering

Figure 2: The distribution of average token number across datasets selected by
different algorithms for Mistral-7B.

Selected data quality of different strategies We have followed Alpagasus (Chen
et al., 2023) to evaluate the quality of each data sample in the selected
datasets by prompting ChatGPT, with the quality scores ranging from 0 to 5.
The quality scores of multi-turn samples are the average scores of each turn.
The results have been presented in Table 1. Surprisingly, the quality scores
of selected datasets are highly similar, even with significant differences in
selection mechanisms. This may suggest that the average quality distribution
remains relatively uniform in the original data pool. Notably, even the SOTA
model-based methods like DEITA (Liu et al., 2023) and SuperFiltering (Li et
al., 2024) select data with similar quality scores, potentially contradicting
their original conclusions. We posit that this discrepancy stems from the
setting of the data budget, which is controlled by the number of samples in
prior studies. Considering the selection bias discussed above, these methods
tend to select lengthy samples, resulting in a significantly higher token
count compared with baselines. For instance, under this setting, data selected
by DEITA will possess 2.7 times the number of tokens compared to ZIP. However,
we argue it is fairer to control the data budget by the token count since it
guarantees a similar compute budget among all methods333In practical
implementation, the training steps of all methods are almost equal by
employing the packing technique detailed in Axolotl..

###  5.2 Data Selection for RLHF

Table 2: Model performance comparison between different data selection baselines based on Llama-3-8B on the RLHF stage. We also provide the computational cost of each method. Model | MT-bench $\uparrow$ | Cost | Avg.length
---|---|---|---
Base | 7.18 | NA | NA
Random $\dagger$ |  7.33 | 5s | 464
Score | 7.30 | NA | 489
ZIP $\dagger$ | 7.42 | 1.1h | 357

####  5.2.1 Setup

Data Pool & Data Selection The data pool used for preference alignment is a
cleaned version of UltraFeedback (Cui et al., 2023; Bartolome et al., 2023),
which consists of around 60k samples in the form of a "chosen-rejected" pair.
Similarly to the SFT stage, we ensure each data selection method selects data
with an approximately equal token count. Since a "chosen-rejected" data pair
encompasses two data points, we select 5,000 data pairs with ZIP and then
apply other methods to select data with the corresponding token budget.

(a) Entropy law w.r.t. compression ratio

(b) Entropy law w.r.t. training loss

Figure 3: Entropy law demonstration of Mistral-7B. The Entropy law curve is
fitted with the results of different methods.

(a) Entropy law w.r.t. compression ratio

(b) Entropy law w.r.t. training loss

Figure 4: Entropy law curve of Llama-3-8B. The Entropy law curve is fitted
with the results of different methods.

Training & Evaluation Building upon the model previously fine-tuned with SFT,
we further refine it using RLHF. In particular, we employ Kahneman-Tversky
Optimization (KTO) (Ethayarajh et al., 2024) for preference alignment, a novel
method that shows promising potential in aligning preferences. Additional
training details can be found in Appendix B. For evaluation, we continue to
utilize MT-bench (Zheng et al., 2023) as our benchmark to assess the
capabilities of LLMs fine-tuned with data selected using diverse data
selection strategies.

Baselines We compare ZIP with the following baselines: (1) Random, which
randomly samples some "chosen-rejected" pairs from the data pool. (2) Score,
which selects the "chosen-rejected" pairs with the highest "chosen-scores".
These scores are obtained through LLM evaluation of the response quality (Cui
et al., 2023; Bartolome et al., 2023).

####  5.2.2 Main results

Table 2 presents the results of different data selection strategies on the
preference alignment stage of LLMs. Similar to the SFT stage, models aligned
with data selected by ZIP can yield the best downstream performance,
demonstrating the necessity for modeling the combinatorial effects. Besides,
we find Score and Random are on par with each other, even though the selection
process of Score is far more expensive than Random. This is unsurprising, as
Score does not consider the combinatorial effects, which may limit the
knowledge amount of the selected dataset.

###  5.3 Empirical Validation of Entropy Law

Figure 5:  Practical application of Entropy law in incremental training data
update, where $x_{1},x_{2},x_{3},x_{4},x_{5}$ are five data versions.

In this section, we aim to demonstrate the proposed entropy law. Specifically,
we have plotted the model performance of Mistral-7B and Llama-3-8B concerning
data compression ratio and training loss in Figure 3 and 4, respectively.
Besides, we plot entropy-law curves by fitting the results. From the two
figures, we can draw the following analysis:

Relationship between model performance, data compression ratio, and training
loss In Figure 3(a) and Figure 4(a), LLMs trained on data with a lower
compression ratio typically exhibit enhanced performance. Since the learning
process of LLMs is highly relevant to information compression, we can regard
LLMs as data compressors. Then the data with a lower compression ratio means a
higher knowledge amount, which is more beneficial to the compressors. Besides,
a lower compression ratio usually corresponds a higher training loss, as
illustrated in Figures 3(b) and 4(b). This is because data resistant to
compression carries more knowledge, posing a greater challenge for LLMs to
absorb the encapsulated knowledge.

Model performance interpretation with entropy law Considering the three
methods with comparable compression ratios and training loss, namely Random,
Cluster, and Perplexity, the corresponding model performances are close. This
phenomenon may seem counter-intuitive, given the distinct criteria used for
data selection. However, it aligns with the predictions of our proposed
entropy law: when the average data quality, training loss, and data
compression ratio are similar, the model performance is expected to be
comparable as well. Thus, the entropy law has the potential to serve as a
criterion for predicting the model’s performance on data, thereby guiding the
training of LLMs.

Practical application of entropy law Incremental version update of training
data is a common setting in practical LLM development. Usually, the training
data amount remains relatively stable, with only a minor portion undergoing
modification. We have conducted incremental training data update experiments
in real scenarios, with results depicted in Figure 5. Due to confidentiality,
only the relative order of the results is provided. Guided by entropy law,
assuming the data quality $Q$ does not significantly decay after each
incremental update, we can expect a model performance improvement with a
decreased data compression ratio. This expectation is supported by the results
from data versions $x_{1}$ to $x_{4}$ in Figure 5 since their compression
ratios are decreased after each incremental update. However, the data version
$x_{5}$ exhibits an abnormal increase in the loss and data compression ratio,
which serves as an early indicator of potential model performance degradation
due to a decline in training data consistency. This prediction is further
confirmed by subsequent post-training model performance evaluations, as
illustrated in Figure 5. Thus, the entropy Law can be utilized as a guideline
for LLM training to identify potential risks of experimental failure without
training the model on the full dataset until convergence. This is particularly
significant given the substantial costs associated with training an LLM.

##  6 Conclusion

In this paper, we delve deeply into the data selection problem from a data
compression perspective. Inspired by the insight that language modeling is
performing information compression, we propose an entropy law delineating the
coherent relationship between model performance, data compression ratio, and
training loss. Theoretically guided by the entropy law, we propose a new data
selection algorithm, ZIP, to select data with the nearly lowest compression
ratio, which is model-free and content-agnostic. rendering it significantly
lightweight and versatile. Experimental results have demonstrated the
effectiveness and efficiency of ZIP, based on various LLM backbones, during
the SFT and RLHF stages. Further in-depth analysis provided empirical evidence
of Entropy law, which could serve as a criterion for LLM performance
prediction on specific data.

## References

  * (1)
  * Achiam et al. (2023) Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023\.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ (2023).
  * Albalak et al. (2024) Alon Albalak, Yanai Elazar, Sang Michael Xie, Shayne Longpre, Nathan Lambert, Xinyi Wang, Niklas Muennighoff, Bairu Hou, Liangming Pan, Haewon Jeong, Colin Raffel, Shiyu Chang, Tatsunori Hashimoto, and William Yang Wang. 2024.  A Survey on Data Selection for Language Models.  arXiv:2402.16827 [cs.CL]
  * Bartolome et al. (2023) Alvaro Bartolome, Gabriel Martin, and Daniel Vila. 2023.  Notus.  https://github.com/argilla-io/notus.
  * Chen et al. (2023) Lichang Chen, Shiyang Li, Jun Yan, Hai Wang, Kalpa Gunaratna, Vikas Yadav, Zheng Tang, Vijay Srinivasan, Tianyi Zhou, Heng Huang, et al. 2023\.  Alpagasus: Training a better alpaca with fewer data.  _arXiv preprint arXiv:2307.08701_ (2023).
  * Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. 2023\.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.  _See https://vicuna. lmsys. org (accessed 14 April 2023)_ 2, 3 (2023), 6.
  * Chowdhery et al. (2023) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2023\.  Palm: Scaling language modeling with pathways.  _Journal of Machine Learning Research_ 24, 240 (2023), 1–113.
  * Cui et al. (2023) Ganqu Cui, Lifan Yuan, Ning Ding, Guanming Yao, Wei Zhu, Yuan Ni, Guotong Xie, Zhiyuan Liu, and Maosong Sun. 2023.  Ultrafeedback: Boosting language models with high-quality feedback.  _arXiv preprint arXiv:2310.01377_ (2023).
  * Delétang et al. (2023) Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. 2023.  Language Modeling Is Compression.  _CoRR_ abs/2309.10668 (2023).
  * Ding et al. (2023) Ning Ding, Yulin Chen, Bokai Xu, Yujia Qin, Shengding Hu, Zhiyuan Liu, Maosong Sun, and Bowen Zhou. 2023.  Enhancing Chat Language Models by Scaling High-quality Instructional Conversations. In _EMNLP_. Association for Computational Linguistics, 3029–3051.
  * Du et al. (2023) Qianlong Du, Chengqing Zong, and Jiajun Zhang. 2023.  Mods: Model-oriented data selection for instruction tuning.  _arXiv preprint arXiv:2311.15653_ (2023).
  * Ethayarajh et al. (2024) Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. 2024.  Kto: Model alignment as prospect theoretic optimization.  _arXiv preprint arXiv:2402.01306_ (2024).
  * GitHub (2020) GitHub. 2020.  GitHub Copilot.  https://github.com/features/copilot/
  * Huang et al. (2024) Yuzhen Huang, Jinghan Zhang, Zifei Shan, and Junxian He. 2024.  Compression Represents Intelligence Linearly.  _arXiv preprint arXiv:2404.09937_ (2024).
  * Ivison et al. (2023) Hamish Ivison, Yizhong Wang, Valentina Pyatkin, Nathan Lambert, Matthew E. Peters, Pradeep Dasigi, Joel Jang, David Wadden, Noah A. Smith, Iz Beltagy, and Hannaneh Hajishirzi. 2023.  Camels in a Changing Climate: Enhancing LM Adaptation with Tulu 2.  _CoRR_ abs/2311.10702 (2023).
  * Jiang et al. (2023) Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de Las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023.  Mistral 7B.  _CoRR_ abs/2310.06825 (2023).
  * Köpf et al. (2024) Andreas Köpf, Yannic Kilcher, Dimitri von Rütte, Sotiris Anagnostidis, Zhi Rui Tam, Keith Stevens, Abdullah Barhoum, Duc Nguyen, Oliver Stanley, Richárd Nagyfi, et al. 2024\.  Openassistant conversations-democratizing large language model alignment.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Li et al. (2024) Ming Li, Yong Zhang, Shwai He, Zhitao Li, Hongyu Zhao, Jianzong Wang, Ning Cheng, and Tianyi Zhou. 2024.  Superfiltering: Weak-to-Strong Data Filtering for Fast Instruction-Tuning.  _CoRR_ abs/2402.00530 (2024).
  * Li et al. (2023) Ming Li, Yong Zhang, Zhitao Li, Jiuhai Chen, Lichang Chen, Ning Cheng, Jianzong Wang, Tianyi Zhou, and Jing Xiao. 2023.  From Quantity to Quality: Boosting LLM Performance with Self-Guided Data Selection for Instruction Tuning.  _CoRR_ abs/2308.12032 (2023).
  * Liu et al. (2023) Wei Liu, Weihao Zeng, Keqing He, Yong Jiang, and Junxian He. 2023.  What Makes Good Data for Alignment? A Comprehensive Study of Automatic Data Selection in Instruction Tuning.  _CoRR_ abs/2312.15685 (2023).
  * Lu et al. (2023) Keming Lu, Hongyi Yuan, Zheng Yuan, Runji Lin, Junyang Lin, Chuanqi Tan, Chang Zhou, and Jingren Zhou. 2023.  # InsTag: Instruction Tagging for Analyzing Supervised Fine-tuning of Large Language Models. In _The Twelfth International Conference on Learning Representations_.
  * M. Bran et al. (2024) Andres M. Bran, Sam Cox, Oliver Schilter, Carlo Baldassari, Andrew D White, and Philippe Schwaller. 2024.  Augmenting large language models with chemistry tools.  _Nature Machine Intelligence_ (2024), 1–11.
  * Meta (2020) Meta. 2020.  Llama3.  https://ai.meta.com/blog/meta-llama-3/
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022\.  Training language models to follow instructions with human feedback.  _Advances in neural information processing systems_ 35 (2022), 27730–27744.
  * Pandey (2024) Rohan Pandey. 2024.  gzip Predicts Data-dependent Scaling Laws.  _arXiv preprint arXiv:2405.16684_ (2024).
  * Peng et al. (2023) Baolin Peng, Chunyuan Li, Pengcheng He, Michel Galley, and Jianfeng Gao. 2023.  Instruction Tuning with GPT-4.  _CoRR_ abs/2304.03277 (2023).
  * Rae et al. (2021) Jack W Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, et al. 2021\.  Scaling language models: Methods, analysis & insights from training gopher.  _arXiv preprint arXiv:2112.11446_ (2021).
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of machine learning research_ 21, 140 (2020), 1–67.
  * Saito et al. (2023) Keita Saito, Akifumi Wachi, Koki Wataoka, and Youhei Akimoto. 2023.  Verbosity bias in preference labeling by large language models.  _arXiv preprint arXiv:2310.10076_ (2023).
  * Shannon (1948) Claude E. Shannon. 1948.  A mathematical theory of communication.  _Bell Syst. Tech. J._ 27, 3 (1948), 379–423.
  * Shannon (1951) Claude E Shannon. 1951.  Prediction and entropy of printed English.  _Bell system technical journal_ 30, 1 (1951), 50–64.
  * Shen (2024) Ming Shen. 2024.  Rethinking Data Selection for Supervised Fine-Tuning.  _CoRR_ abs/2402.06094 (2024).
  * Taori et al. (2023) Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. 2023.  Stanford alpaca: An instruction-following llama model.
  * Wang et al. (2023a) Yizhong Wang, Hamish Ivison, Pradeep Dasigi, Jack Hessel, Tushar Khot, Khyathi Chandu, David Wadden, Kelsey MacMillan, Noah A. Smith, Iz Beltagy, and Hannaneh Hajishirzi. 2023a.  How Far Can Camels Go? Exploring the State of Instruction Tuning on Open Resources. In _NeurIPS_.
  * Wang et al. (2023b) Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. 2023b.  Self-Instruct: Aligning Language Models with Self-Generated Instructions. In _ACL (1)_. Association for Computational Linguistics, 13484–13508.
  * Wang et al. (2022) Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Anjana Arunkumar, Arjun Ashok, Arut Selvan Dhanasekaran, Atharva Naik, David Stap, et al. 2022\.  Super-naturalinstructions: Generalization via declarative instructions on 1600+ nlp tasks.  _arXiv preprint arXiv:2204.07705_ (2022).
  * Wang et al. (2023c) Zige Wang, Wanjun Zhong, Yufei Wang, Qi Zhu, Fei Mi, Baojun Wang, Lifeng Shang, Xin Jiang, and Qun Liu. 2023c.  Data management for large language models: A survey.  _arXiv preprint arXiv:2312.01700_ (2023).
  * Wettig et al. (2024) Alexander Wettig, Aatmik Gupta, Saumya Malik, and Danqi Chen. 2024.  QuRating: Selecting High-Quality Data for Training Language Models.  _arXiv preprint arXiv:2402.09739_ (2024).
  * Xie et al. (2023) Sang Michael Xie, Shibani Santurkar, Tengyu Ma, and Percy S Liang. 2023.  Data selection for language models via importance resampling.  _Advances in Neural Information Processing Systems_ 36 (2023), 34201–34227.
  * Xu et al. (2023) Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang. 2023.  WizardLM: Empowering Large Language Models to Follow Complex Instructions.  _CoRR_ abs/2304.12244 (2023).
  * Zhao et al. (2023) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, Peiyu Liu, Jian-Yun Nie, and Ji-Rong Wen. 2023.  A Survey of Large Language Models.  _CoRR_ abs/2303.18223 (2023).
  * Zheng et al. (2023) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. 2023.  Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena. In _NeurIPS_.
  * Zhou et al. (2023) Chunting Zhou, Pengfei Liu, Puxin Xu, Srinivasan Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, Lili Yu, Susan Zhang, Gargi Ghosh, Mike Lewis, Luke Zettlemoyer, and Omer Levy. 2023.  LIMA: Less Is More for Alignment. In _NeurIPS_.

##  Appendix A Derivations of joint mutual information of two QA pairs

$\displaystyle I(q_{1}q_{2};a_{1}a_{2})$
$\displaystyle=H(a_{1}a_{2})-H(a_{1}a_{2}|q_{1}q_{2})$ (7)
$\displaystyle=H(a_{1}a_{2})-H(a_{1}a_{2}|q_{1}q_{2})$
$\displaystyle=H(a_{1}a_{2})-H(a_{1}|q_{1}q_{2})-H(a_{2}|a_{1}q_{1}q_{2})$
$\displaystyle=H(a_{1}a_{2})-H(a_{1}|q_{1})-H(a_{2}|q_{2})$ $\displaystyle\leq
H(a_{1})+H(a_{2})-H(a_{1}|q_{1})-H(a_{2}|q_{2})$
$\displaystyle=I(q_{1};a_{1})+I(q_{2};a_{2}).$

The equality is achieved when $a_{1}$ is independent on $a_{2}$ (similarly,
$q_{1}$ needs to be independent on $q_{2}$).

##  Appendix B Training Details

Platform All experiments were finished on a platform with 64 Intel Xeon Gold
6326 CPU cores @ 2.90GHz, two main-stream high-performance GPUs, and 500GB
memories. The training code is based on a popular open-source framework
Axolotl444https://github.com/OpenAccess-AI-Collective/axolotl.

Data preprocessing To format the multi-turn conversation data, we adopt the
Vicuna-style template for Mistral-7B and the Llama-3 template for Llama-3-8B.
Samples longer than the maximum input sequence length will be truncated.
Besides, the data will be packed to speed up training for SFT.

Hyper-parameters For ZIP, the selection numbers $K_{1}$, $K_{2}$, and $K_{3}$
are set to 10000, 200, and 100, respectively. As for SFT, we share these
hyper-parameters for all backbones: training batch size is 128, training
epochs is 4, input sequence length is 2048, and the warm-up ratio is 0.1. We
adopt different learning rates for each backbone: the learning rate of
Mistral-7B is set to 4e-6, and the learning rate of Llama-3-8B is set to 1e-5.
As for RLHF, the learning rate for KTO is set to 1e-6, and the batch size is
set to 128.

##  Appendix C Token length distribution of more backbones

The token length distribution of data selected for Llama-3-8B is depicted in
Figure 6, similar to the ones of Mistral-7B.

(a) ZIP

(b) Random

(c) Diversity

(d) Perplexity

(e) DEITA

(f) SuperFiltering

Figure 6: The distribution of average token number across datasets selected by
different algorithms for Llama-3-8B.

##  Appendix D Hyper-parameter sensitivity

(a) Model performance w.r.t. $K_{1}$

(b) Model performance w.r.t. $K_{2}$

(c) Model performance w.r.t. $K_{3}$

Figure 7: Model performance w.r.t. different hyper-parameters.

ZIP involves three hyper-parameters $K_{1}$, $K_{2}$, and $K_{3}$ for improved
efficiency. We aim to investigate the impact of these hyper-parameters on the
model performance, with results depicted in Figure 7.

Perceived sample number in global selection $K_{1}$ $K_{1}$ decides the number
of samples to be updated in the global selection stage. We set $K_{1}$ among
range [200, 1000, 10000, 20000], and the results are presented in Figure 7(a).
In the figure, the model performance exhibits an increasing trend when $K_{1}$
increases. When a smaller $K_{1}$ is specified, ZIP is only exposed to a
limited set of samples. This can lead ZIP to degenerate into a variant that
consistently selects samples based on individual compression ratios,
neglecting the modeling of combinatorial effects. Furthermore, the compression
ratio associated with the currently selected dataset typically increases with
each update, whereas the compression ratios of other samples remain unchanged.
Consequently, a large $K_{1}$ may result in the compression ratio of the un-
updated samples being underestimated, leading to inferior samples’ selection.
As a result, a model performance degradation can be found when $K_{1}$ is set
to 20,000.

Data pool size of local selection $K_{2}$ $K_{2}$ decides the number of
samples selected from the previous $K_{1}$ samples. We set $K_{2}$ among range
[100, 200, 500, 1000], and the results are presented in Figure 7(b). The model
performance increases with an increased $K_{2}$, which aligns with intuition
since the algorithm can consider the combinatorial effects of more samples.
But when $K_{2}$ exceeds a threshold, the model performance reaches a
saturated phase, which indicates similar local selection results even with
increased local data budget.

Data budget of local selection $K_{3}$ $K_{3}$ decides the number of samples
selected from the previous $K_{2}$ samples. We set $K_{3}$ among range [50,
100, 150, 200], and the results are presented in Figure 7(b). The results
exhibit a similar trend as the results of $K_{1}$, yet the underlying causes
are inverse. A large $K_{3}$ will make ZIP degenerate into a trivial variant
that consistently selects samples based on individual compression ratios. On
the other hand, a small $K_{3}$ will lead to more frequent compression ratio
updates, which can also lead to underestimated compression ratios of some
inferior samples.


2010429-440Nancy, France 429

Xiaoyang Gu

John M. Hitchcock

A. Pavan

# Collapsing and Separating Completeness Notions under Average-Case and Worst-
Case Hypotheses

X. Gu  LinkedIn Corporation  ,  J. M. Hitchcock  Department of Computer
Science, University of Wyoming  and  A. Pavan  Department of Computer Science,
Iowa State University

###### Abstract.

This paper presents the following results on sets that are complete for ${\rm
NP}$.

  1. (i)

If there is a problem in ${\rm NP}$ that requires $2^{n^{\Omega(1)}}$ time at
almost all lengths, then every many-one NP-complete set is complete under
length-increasing reductions that are computed by polynomial-size circuits.

  2. (ii)

If there is a problem in co-NP that cannot be solved by polynomial-size
nondeterministic circuits, then every many-one complete set is complete under
length-increasing reductions that are computed by polynomial-size circuits.

  3. (iii)

If there exist a one-way permutation that is secure against subexponential-
size circuits and there is a hard tally language in ${\rm NP}\cap{\mbox{\rm
co-NP}}$, then there is a Turing complete language for ${\rm NP}$ that is not
many-one complete.

Our first two results use worst-case hardness hypotheses whereas earlier work
that showed similar results relied on average-case or almost-everywhere
hardness assumptions. The use of average-case and worst-case hypotheses in the
last result is unique as previous results obtaining the same consequence
relied on almost-everywhere hardness results.

###### Key words and phrases:

computational complexity, NP-completeness

Gu’s research was supported in part by NSF grants 0652569 and 0728806.

Hitchcock’s research was supported in part by NSF grants 0515313 and 0652601
and by an NWO travel grant. Part of this research was done while this author
was on sabbatical at CWI

Pavan’s research was supported in part by NSF grants 0830479 and 0916797.

##  1\. Introduction

It is widely believed that many important problems in ${\rm NP}$ such as
satisfiability, clique, and discrete logarithm are exponentially hard to
solve. Existence of such intractable problems has a bright side: research has
shown that we can use this kind of intractability to our advantage to gain a
better understanding of computational complexity, for derandomizing
probabilistic computations, and for designing computationally-secure
cryptographic primitives. For example, if there is a problem in ${\rm EXP}$
(such as any of the aforementioned problems) that has $2^{n^{\Omega(1)}}$-size
worst-case circuit complexity (i.e., that for all sufficiently large $n$, no
subexponential size circuit solves the problem correctly on all instances of
size $n$), then it can be used to construct pseudorandom generators. Using
these pseudorandom generators, ${\rm BPP}$ problems can be solved in
deterministic quasipolynomial time [23]. Similar average-case hardness
assumptions on the discrete logarithm and factoring problems have important
ramifications in cryptography. While these hardness assumptions have been
widely used in cryptography and derandomization, more recently Agrawal [1] and
Agrawal and Watanabe [2] showed that they are also useful for improving our
understanding of ${\rm NP}$-completeness. In this paper, we provide further
applications of such hardness assumptions.

###  1.1. Length-Increasing Reductions

A language is ${\rm NP}$-complete if every language in ${\rm NP}$ is reducible
to it. While there are several ways to define the notion of reduction, the
most common definition uses polynomial-time computable many-one functions.
Many natural problems that arise in practice have been shown to be NP-complete
using polynomial-time computable many-one reductions. However, it has been
observed that all known ${\rm NP}$-completeness results hold when we restrict
the notion of reduction. For example, $\mathrm{SAT}$ is complete under
polynomial-time reductions that are one-to-one and length-increasing. In fact,
all known many-one complete problems for ${\rm NP}$ are complete under this
type of reduction [9]. This raises the following question: are there languages
that are complete under polynomial-time many-one reductions but not complete
under polynomial-time, one-to-one, length-increasing reductions? Berman [8]
showed that every many-one complete set for ${\rm E}$ is complete under one-
to-one, length-increasing reductions. Thus for ${\rm E}$, these two
completeness notions coincide. A weaker result is known for ${\rm NE}$.
Ganesan and Homer [17] showed that all ${\rm NE}$-complete sets are complete
via one-to-one reductions that are exponentially honest.

For NP, until recently there had not been any progress on this question.
Agrawal [1] showed that if one-way permutations exist, then all NP-complete
sets are complete via one-to-one, length-increasing reductions that are
computable by polynomial-size circuits. Hitchcock and Pavan [20] showed that
${\rm NP}$-complete sets are complete under length-increasing P/poly
reductions under the measure hypothesis on ${\rm NP}$ [26]. Recently Buhrman
et al. improved the latter result to show that if the measure hypothesis
holds, then all NP-complete sets are complete via length-increasing, ${\rm
P}/$-computable functions with $\log\log n$ bits of advice [10]. More
recently, Agrawal and Watanabe [2] showed that if there exist regular one-way
functions, then all NP-complete sets are complete via one-one, length-
increasing, P/poly-computable reductions. All the hypotheses used in these
works require the existence of an almost-everywhere hard language or an
average-case hard language in ${\rm NP}$.

In the first part of this paper, we consider hypotheses that only concern the
worst-case hardness of languages in ${\rm NP}$. Our first hypothesis concerns
the deterministic time complexity of languages in ${\rm NP}$. We show that if
there is a language in ${\rm NP}$ for which every correct algorithm spends
more than $2^{n^{\epsilon}}$ time at almost all lengths, then NP-complete
languages are complete via P/poly-computable, length-increasing reductions.
The second hypothesis concerns nondeterministic circuit complexity of
languages in co-NP. We show that if there is a language in co-NP that cannot
be solved by nondeterministic polynomial-size circuits, then all NP-complete
sets are complete via length-increasing P/poly-computable reductions. For more
formal statements of the hypotheses, we refer the reader to Section 3. We
stress that these hypotheses require only worst-case hardness. The worst-case
hardness is of course required at every length, a technical condition that is
necessary in order to build a reduction that works at every length rather than
just infinitely often.

###  1.2. Turing Reductions versus Many-One Reductions

In the second part of the paper we study the completeness notion obtained by
allowing a more general notion of reduction—Turing reduction. Informally, with
Turing reductions an instance of a problem can be solved by asking
polynomially many (adaptive) queries about the instances of the other problem.
A language in ${\rm NP}$ is Turing complete if there is a polynomial-time
Turing reduction to it from every other language in ${\rm NP}$. Though many-
one completeness is the most commonly used completeness notion, Turing
completeness also plays an important role in complexity theory. Several
properties of Turing complete sets are closely tied to the separation of
complexity classes. For example, Turing complete sets for EXP are sparse if
and only if EXP contains polynomial-size circuits. Moreover, to capture our
intuition that a complete problem is easy, then the entire class is easy,
Turing reductions seem to be the “correct” reductions to define completeness.
In fact, the seminal paper of Cook [13] used Turing reductions to define
completeness, though Levin [25] used many-one reductions.

This raises the question of whether there is a Turing complete language for
${\rm NP}$ that is not many-one complete. Ladner, Lynch and Selman [24] posed
this question in 1975, thus making it one of the oldest problems in complexity
theory. This question is completely resolved for exponential time classes such
as ${\rm EXP}$ and ${\rm NEXP}$ [33, 12]. We know that for both these classes
many-one completeness differs from Turing-completeness. However progress on
the ${\rm NP}$ side has been very slow. Lutz and Mayordomo [27] were the first
to provide evidence that Turing completeness differs from many-one
completeness. They showed that if the measure hypothesis holds, then the
completeness notions differ. Since then a few other weaker hypotheses have
been used to achieve the separation of Turing completeness from many-one
completeness [3, 30, 31, 21, 29].

All the hypotheses used in the above works are considered “strong” hypotheses
as they require the existence of an almost everywhere hard language in ${\rm
NP}$. That is, there is a language $L$ in ${\rm NP}$ and every algorithm that
decides $L$ takes exponential-time an all but finitely many strings. A
drawback of these hypotheses is that we do not have any candidate languages in
${\rm NP}$ that are believed to be almost everywhere hard.

It has been open whether we can achieve the separation using more believable
hypotheses that involve average-case hardness or worst-case hardness. None of
the proof techniques used earlier seem to achieve this, as the they crucially
depend on the almost everywhere hardness.

In this paper, for the first time, we achieve the separation between Turing
completeness and many-one completeness using average-case and worst-case
hardness hypotheses. We consider two hypotheses. The first hypothesis states
that there exist $2^{n^{\epsilon}}$-secure one-way permutations and the second
hypothesis states that there is a language in
$\mathrm{NEEE}\cap\mathrm{co}\mathrm{NEEE}$ that can not be solved in triple
exponential time with logarithmic advice, i.e,
$\mathrm{NEEE}\cap\mathrm{co}\mathrm{NEEE}\not\subseteq\mathrm{EEE}/\log$. We
show that if both of these hypothesis are true, then there is a Turing
complete language in ${\rm NP}$ that is not many-one complete.

The first hypothesis is an average-case hardness hypothesis and has been
studied extensively in past. The second hypothesis is a worst-case hardness
hypothesis. At first glance, this hypothesis may look a little esoteric,
however, it is only used to obtain hard tally languages in ${\rm
NP}\cap{\mbox{\rm co-NP}}$ that are sufficiently sparse. Similar hypotheses
involving double and triple exponential-time classes have been used earlier in
the literature [7, 15, 19, 14].

We use length-increasing reductions as a tool to achieve the separation of
Turing completeness from many-one completeness. We first show that if one-way
permutations exist then ${\rm NP}$-complete sets are complete via length-
increasing, quasipolynomial-time computable reductions. We then show that if
the second hypothesis holds, then there is a Turing complete language for
${\rm NP}$ that is not complete via quasi polynomial-time, length-increasing
reductions. Combining these two results we obtain our separation result.

##  2\. Preliminaries

In the paper, we use the binary alphabet $\Sigma=\\{0,1\\}$. Given a language
$A$, $A_{n}$ denotes the characteristic sequence of $A$ at length $n$. We also
view $A_{n}$ as a boolean function from $\Sigma^{n}$ to $\Sigma$. For
languages $A$ and $B$, we say that $A=\mbox{\rm\tiny io}{B}$, if $A_{n}=B_{n}$
for infinitely many $n$. For a complexity class $\mathcal{C}$, we say that
$A\in\mbox{\rm\tiny io}{\mathcal{C}}$ if there is a language
$B\in{\mathcal{C}}$ such that $A=\mbox{\rm\tiny io}{B}$.

For a boolean function $f:\Sigma^{n}\rightarrow\Sigma$, $CC(f)$ is the
smallest number $s$ such that there is circuit of size $s$ that computes $f$.
A function $f$ is quasipolynomial time computable (${\rm QP}$-computable) if
can be computed deterministically in time $O(2^{\log^{O(1)}n})$. We will use
the triple exponential time class $\mathrm{EEE}={\rm
DTIME}(2^{2^{2^{O(n)}}})$, and its nondeterministic counterpart
$\mathrm{NEEE}$.

A language $L$ is in ${\rm NP}/\mathrm{poly}$ if there is a polynomial-size
circuit $C$ and a polynomial $p$ such that for every $x$, $x$ is in $L$ if and
only if there is a $y$ of length $p(|x|)$ such that $C(x,y)=1$.

Our proofs make use a variety of results from approximable sets, instance
compression, derandomization and hardness amplification. We mention the
results that we need.

######  Definition 2.1.

A language $A$ is $t(n)$-time 2-approximable [6] if there is a function $f$
computable in time $t(n)$ such that for all strings $x$ and $y$, $f(x,y)\neq
A(x)A(y)$.

A language $A$ is io-lengthwise t(n)-time 2-approximable if there is a
function $f$ computable in time $t(n)$ such that for infinitely many $n$, for
every pair of $n$-bit strings $x$ and $y$, $f(x,y)\neq A(x)A(y)$.

Amir, Beigel, Gasarch [4] proved that every polynomial-time 2-approximable set
is in ${\rm P}/\mathrm{poly}$. Their proof also implies the following
extension for a superpolynomial function $t(n)$.

######  Theorem 2.2 ([4]).

If $A$ is io-lengthwise $t(n)$-time 2-approximable, then for infinitely many
$n$, $CC(A_{n})\leq t^{2}(n)$.

Given a language $H^{\prime}$ in co-NP, let $H$ be $\\{\langle
x_{1},\cdots,x_{n}\rangle~{}|~{}|x_{1}|=\cdots=|x_{n}|=n,x_{i}\in
H^{\prime}\\}$. Observe that a $n$-tuple consisting of strings of length $n$
can be encoded by a string of length $n^{2}$. From now we view a string of
length $n^{2}$ as an $n$-tuple of strings of length $n$.

######  Theorem 2.3 ([16, 11]).

Let $H$ and $H^{\prime}$ be defined as above. Suppose there is a language $L$,
a polynomial-size circuit family $\\{C_{m}\\}$, and a polynomial $p$ such that
for infinitely many $n$, for every $x\in\Sigma^{n^{2}}$, $x$ is in $H$ if and
only if there is a string $y$ of length $p(n)$ such that $C(x,y)$ is in
$L^{\leq n}$. Then $H^{\prime}$ is in $\mbox{\rm\tiny io}{{\rm NP}}/poly$.

The proof of Theorem 2.3 is similar to the proofs in [16, 11]. The difference
is rather than having a polynomial-time many-one reduction, here we have a
${\rm NP}/\mathrm{poly}$ many-one reduction which works infinitely often. The
nondeterminism and advice in the reduction can be absorbed into the final
${\rm NP}/\mathrm{poly}$ decision algorithm. The ${\rm NP}/\mathrm{poly}$
decision algorithm works infinitely often, corresponding to when the ${\rm
NP}/\mathrm{poly}$ reduction works.

######  Definition 2.4.

A function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}$ is $s$-secure if for
every $\delta<1$, every $t\leq\delta s$, and every circuit
$C:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}$ of size $t$, $\Pr[C(x)=f(x)]\leq
2^{-m}+\delta$. A function $f:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{*}$ is
$s(n)$-secure if it is $s(n)$-secure at all but finitely many length $n$.

######  Definition 2.5.

An $s(n)$-secure one-way permutation is a polynomial-time computable bijection
$\pi:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{*}$ such that $|\pi(x)|=|x|$ for all
$x$ and $\pi^{-1}$ is $s(n)$-secure.

Under widely believed average-case hardness assumptions about the hardness of
the RSA cryptosystem or the discrete logarithm problem, there is a secure one-
way permutation [18].

######  Definition 2.6.

A pseudorandom generator (PRG) family is a collection of functions
$G=\\{G_{n}:\\{0,1\\}^{m(n)}\rightarrow\\{0,1\\}^{n}\\}$ such that $G_{n}$ is
uniformly computable in time $2^{O(m(n))}$ and for every circuit of $C$ of
size $n$,

$\left|\Pr_{x\in\\{0,1\\}^{n}}[C(x)=1]-\Pr_{y\in\\{0,1\\}^{m(n)}}[C(G_{n}(y))=1\right|\leq\frac{1}{n}.$

There are many results that show that the existence of hard functions in
exponential time implies PRGs exist. We will use the following.

######  Theorem 2.7 ([28, 23]).

If there is a language $A$ in ${\rm E}$ such that $CC(A_{n})\geq
2^{n^{\epsilon}}$ for all sufficiently large $n$, then there exist a constant
$k$ and a PRG family
$G=\\{G_{n}:\\{0,1\\}^{\log^{k}n}\rightarrow\\{0,1\\}^{n}\\}$.

##  3\. Length-Increasing Reductions

In this section we provide evidence that many-one complete sets for NP are
complete via length-increasing reductions. We use the following hypotheses.

Hypothesis 1. There is a language $L$ in ${\rm NP}$ and a constant
$\epsilon>0$ such that $L$ is not in $\mbox{\rm\tiny io}{{\rm
DTIME}}(2^{n^{\epsilon}})$.

Informally, this means that every algorithm that decides $L$ takes more than
$2^{n^{\epsilon}}$-time on at least one string at every length.

Hypothesis 2. There is a language $L$ in co-NP such that $L$ is not in
$\mbox{\rm\tiny io}{{\rm NP}}/\mathrm{poly}$.

This means that every nondeterministic polynomial size circuit family that
attempts to solve $L$ is wrong on on at least one string at each length.

We will first consider the following variant of Hypothesis 1.

Hypothesis 3. There is a language $L$ in ${\rm NP}$ and a constant
$\epsilon>0$ such that for all but finitely many $n$,
$CC(L_{n})>2^{n^{\epsilon}}$.

We will first show that Hypothesis $3$ holds, then ${\rm NP}$-complete sets
are complete via length-increasing reductions. Then we describe how to modify
the proof to derive the same consequence under Hypothesis 1. We do this
because the proof is much cleaner with Hypothesis $3$. To use Hypothesis $1$
we have to fix encodings of boolean formulas with certain properties.

###  3.1. If ${\rm NP}$ has Subexponentially Hard Languages

######  Theorem 3.1.

If there is a language $L$ in ${\rm NP}$ and an $\epsilon>0$ such that for all
but finitely many $n$, $CC(L_{n})>2^{n^{\epsilon}}$, then all ${\rm
NP}$-complete sets are complete via length-increasing, P/poly reductions.

######  Proof 3.2.

Let $A$ be a ${\rm NP}$-complete set that is decidable in time $2^{n^{k}}$.
Let $L$ be a language in ${\rm NP}$ that requires $2^{n^{\epsilon}}$-size
circuits at every length. Since $\mathrm{SAT}$ is complete via polynomial-
time, length-increasing reductions, it suffices to exhibit a length-
increasing, ${\rm P}/\mathrm{poly}$-reduction from $\mathrm{SAT}$ to $A$.

Let $\delta=\frac{\epsilon}{2k}$. Consider the following intermediate language

$S=\left\\{\langle x,y,z\rangle\;\left|\;|x|=|z|,|y|=|x|^{\delta},\mbox{\tt
MAJ}[L(x),\mathrm{SAT}(y),L(z)]=1\right.\right\\}.$

Clearly $S$ is in ${\rm NP}$. Since $A$ is ${\rm NP}$-complete, there is a
many-one reduction $f$ from $S$ to $A$. We will first show that at every
length $n$ there exist strings on which the reduction $f$ must be honest. Let

$T_{n}=\left\\{\langle
x,z\rangle\in\\{0,1\\}^{n}\times\\{0,1\\}^{n}\;\left|\;L(x)\neq
L(z),~{}\forall y\in\\{0,1\\}^{n^{\delta}}~{}|f(\langle
x,y,z\rangle)|>n^{\delta}\right.\right\\}$

######  Lemma 3.3.

For all but finitely many $n$, $T_{n}\neq\varnothing$.

Assuming that the above lemma holds, we complete the proof of the theorem.
Given a length $m$, let $n=m^{1/\delta}$. Let $\langle x_{n},z_{n}\rangle$ be
the first tuple from $T_{n}$. Consider the following reduction from
$\mathrm{SAT}$ to $A$: Given a string $y$ of length $m$, the reduction outputs
$f(\langle x_{n},y,z_{n}\rangle)$. Given $x_{n}$ and $y_{n}$ as advice, this
reduction can be computed in polynomial time. Since $n$ is polynomial in $m$,
this is a P/poly reduction.

By the definition of $T_{n}$, $L(x_{n})\neq L(z_{n})$. Thus $y\in\mathrm{SAT}$
if and only if $\langle x_{n},y,z_{n}\rangle\in S$, and so $y$ is in
$\mathrm{SAT}$ if and only if $f(\langle x_{n},y,z_{n}\rangle)$ is in $A$.
Again, by the definition of $T_{n}$, for every $y$ of length $m$, the length
of $f(\langle x_{n},y,z_{n}\rangle)$ is bigger than $n^{\delta}=m$. Thus there
is a P/poly-computable, length-increasing reduction from $\mathrm{SAT}$ to
$A$. This, together with the proof of Lemma 3.3 we provide next, complete the
proof of Theorem 3.1.

######  Proof 3.4 (Proof of Lemma 3.3).

Suppose $T_{n}=\varnothing$ for infinitely many $n$. We will show that this
yields a length-wise 2-approximable algorithm for $L$ at infinitely many
lengths. This enables us to contradict the hardness of $L$. Consider the
following algorithm:

  1. (1)

Input $x$, $z$ with $|x|=|z|=n$.

  2. (2)

Find a $y$ of length $n^{\delta}$ such that $|f(\langle x,y,x\rangle)|\leq
n^{\delta}$.

  3. (3)

If no such $y$ is found, Output $10$.

  4. (4)

If $y$ is found, then solve the membership of $f(\langle x,y,z\rangle)$ in
$A$. If $f(\langle x,y,z\rangle)\in A$, then output $00$, else output $11$.

We first bound the running time of the algorithm. Step 2 takes
$O(2^{n^{\delta}})$ time. In Step 4, we decide the membership of $f(\langle
x,y,z\rangle)$ in $A$. This step is reached only if the length of $f(\langle
x,y,z\rangle)$ is at most $n^{\delta}$. Thus the time taken to for this step
is $(2^{n^{\delta}})^{k}\leq 2^{n^{\epsilon/2}}$ time. Thus the total time
taken by the algorithm is bounded by $2^{n^{\epsilon}/2}$.

Consider a length $n$ at which $T_{n}=\varnothing$. Let $x$ and $z$ be any
strings at this length. Suppose for every $y$ of length $n^{\delta}$, the
length of $f(\langle x,y,z\rangle)$ is at least $n^{\delta}$. Then it must be
the case that $L(x)=L(z)$, otherwise the tuple $\langle x,z\rangle$ belongs to
$T_{n}$. Thus if the above algorithm fails to find $y$ in Step 2, then
$L(x)L(z)\neq 10$.

Suppose the algorithm succeeds in finding a $y$ in Step 2. If $f(\langle
x,y,z\rangle)\in A$, then at least one of $x$ or $z$ must belong to $L$. Thus
$L(x)L(z)\neq 00$. Similarly, if $f(\langle x,y,z\rangle)\notin A$, then at
least one of $x$ or $z$ does not belong to $L$, and so $L(x)L(z)\neq 11$.

Thus $L$ is 2-approximable at length $n$. If there exist infinitely many
lengths $n$, at which $T_{n}$ is empty, then $L$ is infinitely-often, length-
wise, $2^{n^{\epsilon}/2}$-time approximable. By Theorem 2.2, $L$ has circuits
of size $2^{n^{\epsilon}}$ at infinitely many lengths.

Now we will describe how to modify the proof if we assume that Hypothesis 1
holds. Let $L$ be the hard language guaranteed by the hypothesis. We will work
with 3-$\mathrm{SAT}$. Fix an encoding of 3CNF formulas such that formulas
with same numbers of variables can be encoded as strings of same length.
Moreover, we require that the formulas $\phi(x_{1},\cdots,x_{n})$ and
$\phi(b_{1},\cdots,b_{i},x_{i+1},\cdots,x_{n})$ can be encoded as strings of
same length, where $b_{i}\in\\{0,1\\}$. Fix a reduction $f$ from $L$ to
3-$\mathrm{SAT}$ such that all strings of length $n$ are mapped to formulas
with $n^{r}$ variables, $r\geq 1$. Let
$3\mbox{-}\mathrm{SAT}^{\prime}=3\mbox{-}\mathrm{SAT}\cap\cup_{r}\Sigma^{n^{r}}$.
It follows that that if there is an algorithm that decides
3-$\mathrm{SAT}^{\prime}$ such that for infinitely many $n$ the algorithm runs
in $2^{n^{\epsilon}}$ time on all formulas with $n^{r}$ variables, then $L$ is
in $\mbox{\rm\tiny io}{{\rm DTIME}}(2^{n^{\epsilon}})$.

Now the proof proceeds exactly same as before except that we use
3-$\mathrm{SAT}^{\prime}$ instead of $L$, i.e, our intermediate language will
be

$\\{\langle x,y,z\rangle~{}|~{}\mbox{\tt
MAJ}[3\mbox{-}\mathrm{SAT}^{\prime}(x),\mathrm{SAT}(y),3\mbox{-}\mathrm{SAT}^{\prime}(z)]\\}=1.$

Consider the set $T_{n}$ as before. It follows that if $T_{n}$ is empty at
infinitely many lengths, then for infinitely many $n$,
3-$\mathrm{SAT}^{\prime}$ is 2-approximable on formulas with $n^{r}$
variables. Now we can use the disjunctive self-reducibility of
3-$\mathrm{SAT}^{\prime}$ to show that there is a an algorithm that solves
3-$\mathrm{SAT}^{\prime}$ and for infinitely many $n$, this algorithm runs in
${\rm DTIME}(2^{n^{\epsilon}})$-time on formulas with $n^{r}$ variables. This
contradicts the hardness of $L$. This gives the following theorem.

######  Theorem 3.5.

If there is a language in ${\rm NP}$ that is not in $\mbox{\rm\tiny io}{{\rm
DTIME}}(2^{n^{\epsilon}})$, then all ${\rm NP}$-complete sets are complete via
length-increasing P/poly reductions.

###  3.2. If co-NP is Hard for Nondeterministic Circuits

In this subsection we show that Hypothesis 2 also implies that all NP-complete
sets are complete via length-increasing reductions.

######  Theorem 3.6.

If there is a language $L$ in co-NP that is not in $\mbox{\rm\tiny io}{{\rm
NP}}/poly$, then ${\rm NP}$-complete sets are complete via P/poly-computable,
length-increasing reductions.

######  Proof 3.7.

We find it convenient to work with co-NP rather than ${\rm NP}$. We will show
that all co-NP-complete languages are complete via P/poly, length-increasing
reductions.

Let $H^{\prime}$ be a language in co-NP that is not in $\mbox{\rm\tiny
io}{{\rm NP}}/\mathrm{poly}$. Let $H$ be

$\\{\langle x_{1},\cdots,x_{n}\rangle~{}|~{}\forall 1\leq i\leq n,[x_{i}\in
H^{\prime}\mbox{ and }|x_{i}|=n]\\}.$

Note that every $n$-tuple that may potentially belong to $H$ can be encoded by
a string of length $n^{2}$.

Let $S=0H^{\prime}\cup 1\overline{SAT}$. It is easy to show that $S$ is in co-
NP and $S$ is not in $\mbox{\rm\tiny io}{{\rm NP}}/poly$. Observe that $S$ is
co-NP-complete via length-increasing reductions. Let $A$ be any co-NP-complete
language. It suffices to exhibit a length-increasing reduction from $S$ to
$A$.

Consider the following intermediate language:

$L=\\{\langle x,y,z\rangle~{}|~{}|x|=|z|=|y|^{2},\mbox{\tt MAJ}[x\in H,y\in
S,z\in H]=1\\}.$

Clearly the above language is in co-NP. Let $f$ be a many-one reduction from
$L$ to $\overline{A}$. As before we will first show at every length $n$ that
there exits strings $x$ and $z$ such that for every $y$ in $S$ the length of
$f(\langle x,y,z\rangle)$ is at least $n$.

######  Lemma 3.8.

For all but finitely many $n$, there exist two strings $x_{n}$ and $z_{n}$ of
length $n^{2}$ with $H(x_{n})\neq H(z_{n})$ and for every $y\in S^{n}$,
$|f(\langle x_{n},y,z_{n}\rangle)|>n$.

######  Proof 3.9.

Suppose not. Then there exist infinitely many lengths $n$ at which for every
pair of strings (of length $n^{2}$) $x$ and $z$ with $H(x)\neq H(z)$, there
exist a $y$ of length $n$ such that $|f(x,y,z)|\leq n$.

From this we obtain a ${\rm NP}/\mathrm{poly}$-reduction from $H$ to $A$ such
that for infinitely many $n$, for every $x$ of length $n^{2}$, $|f(x)|\leq n$.
By Theorem 2.3, this implies that $H^{\prime}$ is in $\mbox{\rm\tiny io}{{\rm
NP}}/\mathrm{poly}$. We now describe the reduction. Given $n$ let $z_{n}$ be a
string (of length $n^{2}$) that is not in $H$.

  1. (1)

Input $x,|x|=n^{2}$. Advice: $z_{n}$.

  2. (2)

Guess a string $y$ of length $n$.

  3. (3)

If $|f(\langle x,y,z_{n}\rangle)|>n$, the output $\bot$.

  4. (4)

Output $f(\langle x,y,z_{n})$.

Suppose $x\in H$. Since $z_{n}\notin H$, there exists a string $y$ of length
$n$ such that $y\in S$ and $|f(\langle x,y,z_{n}\rangle)|\leq n$. Consider a
path that correctly guesses such a $y$. Since $z_{n}\notin H$, and $y\in S$,
$\langle x,y,z_{n}\rangle\in L$. Thus $f(\langle x,y,z_{n}\rangle)\in A^{\leq
n}$. Thus there exists at least one path on which the reduction outputs a
string from $L\cap\Sigma^{\leq n}$. Now consider the case $x\notin H$. On any
path, the reduction either outputs $\bot$ or outputs $f(\langle
x,y,z_{n}\rangle)$. Since both $z_{n}$ and $x$ are not in $H$, $\langle
x,y,z\rangle\notin L$. Thus $f(\langle x,y,z_{n}\rangle)\notin A$ for any $y$.

Thus there is a ${\rm NP}/\mathrm{poly}$ many-one reduction from $H$ to $L$
such that for infinitely many $n$, the output of the reduction, on strings of
length $n^{2}$, on any path is at most $n$. By Theorem 2.3, this places
$H^{\prime}$ in $\mbox{\rm\tiny io}{{\rm NP}}/\mathrm{poly}$.

Thus for all but finitely many lengths $n$, there exist strings $x_{n}$ and
$z_{n}$ of length $n^{2}$ with $H(x_{n})\neq H(z_{n})$ and for every $y\in
S^{n}$, the length of $f(\langle x_{n},y,z_{n}\rangle)$ is at least $n$.

This suggests the following reduction $h$ from $S$ to $A$. The reduction will
have $x_{n}$ and $z_{n}$ as advice. Given a string $y$ of length $n$, the
reductions outputs $f(\langle x_{n},y,z_{n}\rangle)$. This reduction is
clearly length-increasing and is length-increasing on every string from $S$.
Thus we have the following lemma.

######  Lemma 3.10.

Consider the above reduction $h$ from $S$ to $A$, for all $y\in S$,
$|h(y)|>|y|$.

Now we show how to obtain a length-increasing reduction on all strings. We
make the following crucial observation.

For all but finitely many $n$, there is a string $y_{n}$ of length $n$ such
that $y_{n}\notin S$ and $|f(\langle x_{n},y_{n},z_{n}\rangle)|>n$.

######  Proof 3.11.

Suppose not. This means that for infinitely many $n$, for every $y$ from
$\overline{S}\cap\Sigma^{n}$, the length of $f(\langle x_{n},y,z_{n}\rangle)$
is less than $n$. Now consider the following algorithm that solves $S$. Given
a string $y$ of length $n$, compute $f(\langle x_{n},y,z_{n}\rangle)$. If the
length of $f(\langle x_{n},y,z_{n}\rangle)>n$, then accept $y$ else reject
$y$.

The above algorithm can be implemented in P/poly given $x_{n}$ and $z_{n}$ as
advice. If $y\in S$, then we know that that the length of $f(\langle
x_{n},y,z_{n}\rangle)$ is bigger than $n$, and so the above algorithm accepts.
If $y\notin S$, then by our assumption, the length of $f(\langle
x_{n},y,z_{n}\rangle)$ is at most $n$. In this case the algorithm rejects $y$.
This shows that $S$ is in ioP/poly which in turn implies that $H^{\prime}$ is
in ioP/poly. This is a contradiction.

Now we are ready to describe our length increasing reduction from $S$ to $A$.
At length $n$, this reduction will have $x_{n}$, $y_{n}$ and $z_{n}$ as
advice. Given a string $y$ of length $n$, the reduction outputs $f(\langle
x_{n},y,z_{n}\rangle)$ if the length of $f(\langle x_{n},y,z_{n}\rangle)$ is
more than $n$. Else, the reduction outputs $f(\langle
x_{n},y_{n},z_{n}\rangle)$.

Since $H(x_{n})\neq H(z_{n})$, $y\in S$ if and only if $f(\langle
x_{n},y,z_{n}\rangle)\in A$. Thus the reduction is correct when it outputs
$f(\langle x_{n},y,z_{n}\rangle)$. The reduction outputs $f(\langle
x_{n},y_{n},z_{n}\rangle)$ only when the length of $f(\langle
x_{n},y,z_{n}\rangle)$ is at most $n$. We know that in this case $y\notin S$.
Since $y_{n}\notin S$, $f(\langle x_{n},y_{n},z_{n})\notin A$.

Thus we have a P/poly-computable, length-increasing from $S$ to $A$. Thus all
co-NP-complete languages are complete via P/poly, length-increasing
reductions. This immediately implies that all ${\rm NP}$-complete languages
are complete via P/poly-computable, length-increasing reductions.

##  4\. Separation of Completeness Notions

In this section we consider the question whether the Turing completeness
differs from many-one completeness for ${\rm NP}$ under two plausible
complexity-theoretic hypotheses:

  1. (1)

There exists a $2^{n^{\epsilon}}$-secure one-way permutation.

  2. (2)

$\mathrm{NEEE}\cap\mathrm{co}\mathrm{NEEE}\not\subseteq\mathrm{EEE}/\log$.

It turns out that the first hypothesis implies that every many-one complete
language for ${\rm NP}$ is complete under a particular kind of length-
increasing reduction, while the second hypothesis provides us with a specific
Turing complete language that is not complete under the same kind of length-
increasing reduction. Therefore, the two hypotheses together separate the
notions of many-one and Turing completeness for ${\rm NP}$ as stated in the
following theorem.

######  Theorem 4.1.

If both of the above hypotheses are true, there is is a language that is
polynomial-time Turing complete for ${\rm NP}$ but not polynomial-time many-
one complete for ${\rm NP}$.

Theorem 4.1 is immediate from Lemma 4.2 and Lemma 4.3 below.

######  Lemma 4.2.

Suppose $2^{n^{\epsilon}}$-secure one-way permutations exist. Then for every
${\rm NP}$-complete language $A$ and every $B\in{\rm NP}$, there is a
quasipolynomial-time computable, polynomial-bounded, length-increasing
reduction reduction $f$ from $B$ to $A$.

A function $f$ is polynomial-bounded if there is a polynomial $p$ such that
the length of $f(x)$ is at most $p(|x|)$ for every $x$.

######  Lemma 4.3.

If $\mathrm{NEEE}\cap\mathrm{co}\mathrm{NEEE}\nsubseteq\mathrm{EEE}/\log$,
then there is a polynomial-time Turing complete set for ${\rm NP}$ that is not
many-one complete via quasipolynomial-time computable, polynomial-bounded,
length-increasing reductions.

The proof of Lemma 4.2 will appear in the full paper. The remainder of this
section is devoted to proving Lemma 4.3. It is well known that any set $A$
over $\Sigma^{*}$ can be encoded as a tally set $T_{A}$ such that $A$ is
worst-case hard if and only if $T_{A}$ is worst-case hard. For our purposes,
we need an average-case version of the this equivalence. Below we describe
particular encoding of languages using tally sets that is helpful for us and
prove the average-case equivalence.

Let $t_{0}=2$, $t_{i+1}=t_{i}^{2}$ for all $i\in\mathbb{N}$. Let
$\mathcal{T}=\left\\{0^{t_{i}}\;\left|\;i\in\mathbb{N}\right.\right\\}$. For
each $l\in\mathbb{N}$, let
$\mathcal{T}_{l}=\left\\{0^{t_{i}}\;\left|\;2^{l}-1\leq i\leq
2^{l+1}-2\right.\right\\}$. Observe that
$\mathcal{T}=\bigcup_{l=0}^{\infty}\mathcal{T}_{l}$. Given a set
$A\subseteq\\{0,1\\}^{*}$, let
$T_{A}=\left\\{\left.0^{2^{2^{r_{x}}}}\right|x\in A\right\\},$ where $r_{x}$
is the rank index of $x$ in the standard enumeration of $\\{0,1\\}^{*}$. It is
easy to verify that for all $l\in\mathbb{N}$ and every $x$,

$\displaystyle x\in A\cap\\{0,1\\}^{l}$ $\displaystyle\iff$ $\displaystyle
0^{t_{r_{x}}}\in T_{A}\cap\mathcal{T}_{l}.$ (1)

######  Lemma 4.4.

Let $A$ and $T_{A}$ be as above. Suppose there is a quasipolynomial time
algorithm $\mathcal{A}$ such that for every $l$, on an $\epsilon$ fraction of
strings from $\mathcal{T}_{l}$, this algorithm correctly decides the
membership in $T_{A}$, and on the rest of the strings the algorithm outputs “I
do not know”. There is a $2^{2^{2^{k(l+1)}}}$-time algorithm
$\mathcal{A}^{\prime}$ for some constant $k$ that takes one bit of advice and
correctly decides the membership in $A$ on $\frac{1}{2}+\frac{\epsilon}{2}$
fraction of the strings at every length $l$.

We know several results that establish worst-case to average-case connections
for classes such as ${\rm EXP}$ and ${\rm PSPACE}$ [34, 5, 22, 23, 32]. The
following lemma establishes a similar connection for triple exponential time
classes, and can be proved using known techniques.

######  Lemma 4.5.

If $\mathrm{NEEE}\cap\mathrm{co}\mathrm{NEEE}\not\subseteq\mathrm{EEE}/\log$,
then there is language $L$ in $\mathrm{NEEE}\cap\mathrm{co}\mathrm{NEEE}$ such
that no $\mathrm{EEE}/\log$ algorithm can decide $L$, at infinitely many
lengths $n$, on more than $\frac{1}{2}+\frac{1}{n}$ fraction of strings from
$\\{0,1\\}^{n}$.

Now we are ready to prove Lemma 4.3.

######  Proof 4.6 (Proof of Lemma 4.3).

By Lemma 4.5, there is a language
$L\in(\mathrm{NEEE}\cap\mathrm{co}\mathrm{NEEE})-\mathrm{EEE}/\log$ such that
no $\mathrm{EEE}/\log$ algorithm can decide $L$ correctly on more than a
$\frac{1}{2}+\frac{1}{n}$ fraction of the inputs for infinitely many lengths
$n$.

Without loss of generality, we can assume that $L\in{\rm
NTIME}(2^{2^{2^{n}}})\cap\mathrm{co}{\rm NTIME}(2^{2^{2^{n}}})$ Let

$T_{L}=\left\\{\left.0^{2^{2^{r_{x}}}}\right|x\in L\right\\}.$

Clearly, $T_{L}\in{\rm NP}\cap\mathrm{co}{\rm NP}$.

Define $\tau:\mathbb{N}\rightarrow\mathbb{N}$ such that
$\tau(n)=\max\left\\{i\;\left|\;t_{i}\leq n\right.\right\\}$. Now we will
define our Turing complete language. Let

$\mathrm{SAT}_{0}=\left\\{0x\;\left|\;0^{t_{\tau(|x|)}}\notin T_{L}\text{ and
}x\in\mathrm{SAT}\right.\right\\},$
$\mathrm{SAT}_{1}=\left\\{1x\;\left|\;0^{t_{\tau(|x|)}}\in T_{L}\text{ and
}x\in\mathrm{SAT}\right.\right\\}.$

Let $A=\mathrm{SAT}_{0}\cup\mathrm{SAT}_{1}$. Since $L$ is in ${\rm
NP}\cap{\mbox{\rm co-NP}}$, $A$ is in ${\rm NP}$. The following is a Turing
reduction from $\mathrm{SAT}$ to $A$: Given a formula $x$, ask queries $0x$
and $1x$, and accept if and only if at least one them is in $A$. Thus $A$ is
polynomial-time $2$-$\mathrm{tt}$ complete for ${\rm NP}$.

Suppose $A$ is complete via length-increasing, polynomial-bounded,
quasipolynomial-time reductions. Then there is such a reduction $f$ from
$\\{0\\}^{*}$ to $A$. There is a constant $d$ such that $f$ is $n^{d}$-bounded
and runs in quasipolynomial time.

The following observation is easy to prove. Let $y\in\\{0,1\\}^{*}$ and
$b\in\\{0,1\\}$ be such that $f(0^{t_{i}})=by$. Then $0^{t_{\tau(|y|)}}\in
T_{L}$ if and only if $b=1$.

Fix a length $l$. We will describe a quasipolynomial-time algorithm that will
decide the membership in $T_{L}$ on at least $\frac{1}{\log d}$ fraction of
strings from $\mathcal{T}_{l}$, and says “I do not know” on other strings. By
the Lemma 4.4, this implies that there is $\mathrm{EEE}/1$ algorithm that
decides $L$ on more than $\frac{1}{2}+\frac{1}{2\log d}$ fraction of strings
from $\\{0,1\\}^{l}$. This contradicts the hardness of $L$ and completes the
proof.

Let $s=2^{l}-1$ and $r=2^{l+1}-2$. Recall that
$\mathcal{T}_{l}=\left\\{0^{t_{i}}\;\left|\;s\leq i\leq r\right.\right\\}$.
Divide $\mathcal{T}_{l}$ in sets $T_{0},T_{2},\cdots T_{r}$ where
$T_{k}=\left\\{0^{t_{i}}\;\left|\;s+k\log d\leq r+(k+1)\log
d\right.\right\\}$. This gives at least $\frac{2^{l}}{\log d}$ sets. Consider
the following algorithm that decides $T_{L}$ on strings from
$\mathcal{T}_{l}$: Let $0^{t_{j}}$ be the input. Say, it lies in the set
$T_{k}$. Compute $f(0^{t_{s+k\log d}})=by$. If $t_{\tau(|y|)}\neq t_{j}$, then
output “I do not know”. Otherwise, accept $0^{t_{j}}$ if and only if $b=1$. By
Observation 4.6 this algorithm never errs. Since $f$ is computable in
quasipolynomial time, this algorithm runs in quasipolynomial time. Finally,
observe that $t_{\tau(|y|)}$ lies between $t_{s+k\log d}$ and $t_{s+(k+1)\log
d}$. Thus for every $k$, $0\leq k\leq r$, there is at least one string from
from $T_{k}$ on which the above algorithm correctly decides $T_{L}$. Thus the
above algorithm correctly decides $T_{L}$ on at least $\frac{1}{\log d}$
fraction of strings from $\mathcal{T}_{l}$, and never errs.

## References

  * [1] M. Agrawal.  Pseudo-random generators and structure of complete degrees.  In Proceedings of the Seventeenth Annual IEEE Conference on Computational Complexity, pages 139–147, 2002.
  * [2] M. Agrawal and O. Watanabe.  One-way functions and the isomorphism conjecture.  Technical Report TR09-019, Electronic Colloquium on Computational Complexity, 2009.
  * [3] K. Ambos-Spies and L. Bentzien.  Separating NP-completeness notions under strong hypotheses.  Journal of Computer and System Sciences, 61(3):335–361, 2000.
  * [4] A. Amir, R. Beigel, and W. Gasarch.  Some connections between bounded query classes and non-uniform complexity.  Information and Computation, 186:104–139, 2003.
  * [5] L. Babai, L. Fortnow, N. Nisan, and A. Wigderson.  BPP has subexponential time simulations unless EXPTIME has publishable proofs.  Computational Complexity, 3:307–318, 1993.
  * [6] R. Beigel.  Query-limited reducibilities.  PhD thesis, Stanford University, 1987.
  * [7] R. Beigel and J. Feigenbaum.  On being incoherent without being very hard.  Computational Complexity, 2(1):1–17, 1992.
  * [8] L. Berman.  Polynomial Reducibilities and Complete Sets.  PhD thesis, Cornell University, 1977.
  * [9] L. Berman and J. Hartmanis.  On isomorphism and density of NP and other complete sets.  SIAM Journal on Computing, 6:305–322, 1977.
  * [10] H. Buhrman, B. Hescott, S. Homer, and L. Torenvliet.  Non-uniform reductions.  Theory of Computing Systems.  To appear.
  * [11] H. Buhrman and J. M. Hitchcock.  NP-hard sets are exponentially dense unless NP $\subseteq$ coNP/poly.  In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, pages 1–7. IEEE Computer Society, 2008.
  * [12] H. Buhrman, S. Homer, and L. Torenvliet.  Completeness for nondeterministic complexity classes.  Mathematical Systems Theory, 24:179–200, 1991.
  * [13] S. A. Cook.  The complexity of theorem proving procedures.  In Proceedings of the Third ACM Symposium on the Theory of Computing, pages 151–158, 1971.
  * [14] J. Feigenbaum, L. Fortnow, S. Laplante, and A. Naik.  On coherence, random-self-reducibility, and self-correction.  Computational Complexity, 7:174–191, 1998.
  * [15] J. Feigenbaum, L. Fortnow, C. Lund, and D. Spielman.  The powwer of adaptiveness and additional queries in random-self-reductions.  Computational Complexity, 4:158–174, 1994.
  * [16] L. Fortnow and R. Santhanam.  Infeasibility of instance compression and succinct PCPs for NP.  In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 133–142, 2008.
  * [17] K. Ganesan and S. Homer.  Complete problems and strong polynomial reducibilities.  SIAM J. Comput., 21(4):733–742, 1992.
  * [18] O. Goldreich, L. Levin, and N. Nisan.  On constructing 1-1 one-way function.  Technical Report TR95-029, ECCC, 1995.
  * [19] E. Hemaspaandra, A. Naik, M. Ogiwara, and A. Selman.  P-selective sets and reducing search to decision vs. self-reducibility.  Journal of Computer and System Sciences, 53(2):194–209, 1996.
  * [20] J. M. Hitchcock and A. Pavan.  Comparing reductions to NP-complete sets.  Information and Computation, 205(5):694–706, 2007.
  * [21] J. M. Hitchcock, A. Pavan, and N. V. Vinodchandran.  Partial Bi-immunity, Scaled Dimension, and NP-Completeness.  Theory of Computing Systems.  To appear.
  * [22] R. Impagliazzo.  Hard-core distributions for somewhat hard problems.  In Proceedings of the 36th Annual Conference on Foundations of Computer Science, pages 538–545, 1995.
  * [23] R. Impagliazzo and A. Wigderson.  P = BPP if E requires exponential circuits: Derandomizing the XOR lemma.  In Proceedings of the 29th Symposium on Theory of Computing, pages 220–229, 1997.
  * [24] R. Ladner, N. Lynch, and A. Selman.  A comparison of polynomial time reducibilities.  Theoretical Computer Science, 1:103–123, 1975.
  * [25] L. Levin.  Universal sorting problems.  Problems of Information Transmission, 9:265–266, 1973.  English translation of original in Problemy Peredaci Informacii.
  * [26] J. H. Lutz and E. Mayordomo.  Measure, stochasticity, and the density of hard languages.  SIAM Journal on Computing, 23(4):762–779, 1994.
  * [27] J. H. Lutz and E. Mayordomo.  Cook versus Karp-Levin: Separating completeness notions if NP is not small.  Theoretical Computer Science, 164(1–2):141–163, 1996.
  * [28] N. Nisan and A. Wigderson.  Hardness vs randomness.  Journal of Computer and System Sciences, 49:149–167, 1994.
  * [29] A. Pavan.  Comparison of reductions and completeness notions.  SIGACT News, 34(2):27–41, June 2003.
  * [30] A. Pavan and A. Selman.  Separation of NP-completeness notions.  SIAM Journal on Computing, 31(3):906–918, 2002.
  * [31] A. Pavan and A. Selman.  Bi-immunity separates strong NP-completeness notions.  Information and Computation, 188:116–126, 2004.
  * [32] M. Sudan, L. Trevisan, and S. Vadhan.  Pseudorandom generators without the XOR lemma.  JCSS: Journal of Computer and System Sciences, 62, 2001.
  * [33] O. Watanabe.  A comparison of polynomial time completeness notions.  Theoretical Computer Science, 54:249–265, 1987.
  * [34] A. Yao.  Theory and applications of trapdoor functions.  In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 80–91, 1982.