Git rebase with no arguments changing commits IDs and order

Each rebase operation will take whatever commits are not already present on the destination and recreate them there. I say recreate, and not move, because a commit is something immutable, with its fixed set of changes, parents, message and other meta-data. A rebase is creating a new commit with the same message, changes, meta-data but different parents.

Now I will add origin/feature to your original graph, pointing to F2 because that's where your final log says it is.

I will also add F3 to your original graph, and assume feature pointed to it. The logs you show after the rebases are impossible unless that was the case. (Or did you create F3 after the first rebase? In any case, you're showing it in the results of the rebase, so it has to have gotten created either initially or before the second rebase, but origin/feature never pointed to it according to your last log output.)

Updated initial state:

 F3 feature / F1 -- F2 origin/feature / M1 -- M2 -- M3 main, origin/main 

The first rebase created F1', F2' and F3' and set feature to point to F3', but left origin/feature alone, still pointing at F2:

 F1 -- F2 origin/feature / / F1' -- F2' -- F3' feature / / M1 -- M2 -- M3 main, origin/main 

The second rebase says take feature and rebase it on top of origin/feature. That means take M3, F1', F2' and F3' and add them after F2. M2 is in the shared history, so it does not need to be considered. Now, by default that might create M1 - M2 - F1 - F2 - M3' - F1'' - F2'' - F3'' as the new history for feature, except that the rebase notices that F1' has the same change set as F1, so it skips it (as the log message says), and ditto for F2'. The final results you get are as expected once you skip creating F1'' and F2'':

 M3' -- F3'' -- feature / F1 -- F2 origin/feature / / F1' -- F2' -- F3' (nothing points here anymore, but it still exists) / / M1 -- M2 -- M3 main, origin/main 

(The original F3 also still exists, with F2 as its parent but no branch pointing to it. My graph is getting too crowded to display it, though.)

Now, if you had run your second rebase with --keep-empty, which tells the rebase to "Keep the commits that do not change anything from its parents in the result," you would have indeed had F1 - F2 - M3' - F1'' - F2'' - F3'', but F1'' and F2'' would have been empty commits, since they were trying to reproduce F1' and F2' which are bringing in changes that have already been applied earlier in the history leading to M3'.