bpe_partial_merge_can_skip_overlap
A partial merge of equal adjacent symbols may skip the first occurrence and merge the overlapping middle occurrence.
Statement
theorem bpe_partial_merge_can_skip_overlap : bpe_partial_merge 1 1 9 [1,1,1,1] [1,9,1]- Source
- Sanity check for the partial merge relation in OP-1288.
- Verified
- 10 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- bpe_partial_mergeThe relation between input and output strings obtained by replacing an arbitrary subset of pairwise nonoverlapping occurrences of the…
The proof, explained
The theorem shows that byte-pair encoding (BPE) partial merge can skip an initial match to merge an overlapping pair: replacing (1, 1) with 9 can turn [1, 1, 1, 1] into [1, 9, 1]. The proof unfolds the recursive definition of `bpe_partial_merge` using `simp`, which evaluates the choices on concrete lists and confirms the valid merge path.
The list [1, 9, 1] is a valid partial merge of the pair (1, 1) into 9 on the input [1, 1, 1, 1]. automation
By unfolding the recursive definition of bpe_partial_merge on concrete lists, the simplifier confirms that [1, 1, 1, 1] can step to [1, 9, 1]: the first symbol 1 is skipped, the next pair (1, 1) is merged into 9, and the remaining singleton [1] is kept by the base case.
uses
bpe_partial_mergetheorem bpe_partial_merge_can_skip_overlap : bpe_partial_merge 1 1 9 [1,1,1,1] [1,9,1] := by simp [bpe_partial_merge]
bpe_partial_merge- A relation specifying that the second list is obtained from the first by nondeterministically merging occurrences of adjacent pairs (a, b) into z, or leaving symbols unmerged.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem bpe_partial_merge_can_skip_overlap : bpe_partial_merge 1 1 9 [1,1,1,1] [1,9,1] := by simp [bpe_partial_merge]