We study the evolution of the halo-halo correlation function and small-scal
e (approximate to 0.2-7 h(-1) Mpc) bias in four cosmological models (Lambda
CDM, OCDM, tau CDM, and SCDM) using very high resolution n-body simulation
s with a dynamical range of similar to 10,000-32,000 (force resolution of a
pproximate to 2-4 h(-1) kpc and particle mass of approximate to 10(9) h(-1)
M.). The high force and mass resolution allows dark matter halos to surviv
e in the tidal fields of high-density regions and thus prevents the ambigui
ties related with the "overmerging problem." This allows us to estimate for
the first time the evolution of the correlation function and bias at small
(down to similar to 100 h(-1) kpc) scales. We find that at all epochs the
two-point correlation function of galaxy-size halos xi(hh) is well approxim
ated by a power law with slope approximate to 1.6-1.8. The difference betwe
en the shape of xi(hh) and the shape of the correlation function of matter
results in the scale-dependent bias at: scales less than or similar to 7 h(
-1) Mpc, which we find to be a generic prediction of the hierarchical model
s, independent of the epoch and of the model details. The bias evolves rapi
dly from a high value of similar to 2-5 at z similar to 3-7 to the antibias
of b similar to 0.5-1 at small less than or similar to 5 h(-1) Mpc scales
at z = 0. Another generic prediction is that the comoving amplitude of the
correlation function for halos above a certain mass evolves non-monotonical
ly: it decreases from an initially high value at z similar to 3-7, and very
slowly increases at z less than or similar to 1. We find that our results
agree well with existing clustering data at different redshifts, indicating
the general success of the hierarchical models of structure formation in w
hich galaxies form inside the host DM halos. Particularly, we find an excel
lent agreement in both slope and the amplitude between xi(hh)(z = 0) in our
ACDM(60) simulation and the galaxy correlation function measured using the
Automatic Plate Measuring Facility galaxy survey. At high redshifts, the o
bserved clustering of the Lyman-break galaxies is also well reproduced by t
he models. We find good agreement at z greater than or similar to 2 between
our results and predictions of the analytical models of bias evolution. Th
is indicates that we have a solid understanding of the nature of the bias a
nd of the processes that drive its evolution at these epochs. We argue, how
ever, that at lower redshifts the evolution of the bias is driven by dynami
cal processes inside the nonlinear high-density regions such as galaxy clus
ters and groups. These processes do not depend on cosmology and tend to era
se the differences in clustering properties of halos that exist between cos
mological models at high z.