Early stage of GaAs nucleation on Si substrate was theoretically studied by computer simulation. Compared to the constant ledge interaction energy in conventional nucleation theory, functional behavior of ledge-ledge interaction resulted in small size clusters depending on the cluster size and shape. Among various kinds of clusters, the multilayer pyramidal shape GaAs cluster requires smallest excess free energy due to the formation of Ga(111) facet planes. There this result suggests that the defects involved in GaAs/Si are originated from the early stage nucleation.