A first answer
Providing a definitive answer wil be difficult without knowing more about your data, understanding the models and chosen hyperparameters, and performing various checks on the results.
One possible cause of such behaviour is, as you hint in the question title, model instability.
Intuitively, a stable algorithm is one for which the prediction does not change much when the training data is modified slightly.
Which is the opposite of what seems to be happening to you (see here for a detailed description of algorithmic stability) Variance of $K$-fold cross-validation estimates as $f(K)$: what is the role of "stability"?
Without going into the details of the above post, the stabilty of a model will depend on:
- The inherent algorithm being used: for example decision trees are notoriously unstable, while $L_2$ ridge regression is inherently more stable (for appropriate regularization parameter)
- The size of the data set
- The number of outliers, their distribution, and their values
This is assuming there are no pre-processing or feature selection steps beforehand as these will add many more possible sources of instability. For example Lasso on correlated features is known to be unstable.
What you could try
Assuming your objective is to reduce the instability of your algorithm, you could try the following
- Add $L_2$ regularization, or a combination of $L_1$ and $L_2$ (elastic net)
- Use different, more stable, algorithms (e.g. bagged regularizers, soft margin SVM with regularization etc..)
- Transform your data (remove outliers, obtain more data, perform PCA, compression etc..)
- Add "robustifying" steps to your algorithm. These will depend on the algorithm and may or may not exist. An example are the robustifying iterations added to the following LOESS algorithm
Note that algorithm stability does not necessarily imply better predictions or performance of your model...
A toy example
The same polynomial linear regression algorithm is unstable in the LHS, and stable in the RHS. More data points reduce the effect of outliers on the model.