bpe_greedy_run
def
The relation defining a k-step greedy Byte-Pair Encoding run on string s yielding string t: for k = 0 we have s = t, and for k + 1 there exists an intermediate string u such that bpe_greedy_run k s u and bpe_greedy_step_with (k + 2) u t.
Statement
def bpe_greedy_run : ℕ → List ℕ → List ℕ → Prop
- Defined in
- Sennrich, Haddow, Birch, arXiv:1508.07909; Gage, C Users Journal 1994
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 1
- bpe_greedy_step_withA greedy full Byte-Pair Encoding merge step with fresh symbol z: either no adjacent pair occurs with positive count in string s and t = s,…
- Used by 4
- bpe_deviation_probGiven parameters (p : ℝ), hypothesis (hp : 0 < p ∧ p < 1), (k N : ℕ), and (c ε : ℝ), bpe_deviation_prob p hp k N c ε is the real number…
- bpe_greedy_run_length_lower_boundApplying k greedy full BPE merges reduces the string length by at most a factor of 2^k: if bpe_greedy_run k s t, then s.length ≤ 2^k *…
- bpe_deviation_prob_nonnegFor any source bias p ∈ (0, 1), step count k, input length N, target constant c, and tolerance ε, the deviation probability…
- bpe_zero_step_run_uniqueA zero-step greedy Byte-Pair Encoding run from string s to string t holds if and only if s = t.
Read back from the Lean
bpe_greedy_run n s t is a recursively defined relation asserting that the list of natural numbers t can be obtained from s after n steps of greedy byte-pair encoding (BPE).
- Base case (n = 0): s = t.
- Inductive step (n = k + 1): there exists an intermediate list u : List ℕ such that bpe_greedy_run k s u holds, and u transitions to t via bpe_greedy_step_with (k + 2) u t.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A k-step greedy BPE run with fresh symbol IDs 2, 3, ..., k + 1. -/ def bpe_greedy_run : ℕ → List ℕ → List ℕ → Prop | 0, s, t => s = t | k + 1, s, t => ∃ u, bpe_greedy_run k s u ∧ bpe_greedy_step_with (k + 2) u t