bpe_worst_ratio
def
For a merge budget k, the infimum of greedy length reduction divided by optimal partial-merge length reduction over finite natural-number strings and all greedy tie-breaking runs with positive optimum.
Statement
noncomputable def bpe_worst_ratio (k : ℕ) : ℝ
- Source
- Definitions for OP-1288, following arXiv:2611.08671, Section 2.
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 3
- bpe_stepsExactly k applications of the specified binary relation connect the input and output strings.
- bpe_greedy_stepA greedy full-merge step selects any most frequent adjacent pair and a fresh symbol; a string without adjacent pairs remains unchanged.
- bpe_optimal_utilityThe supremum, over strings reachable in k partial-merge steps, of the reduction in length of the input string.
- Used by 1
- bpe_worst_case_ratio_three_upper_boundThe worst-case ratio of greedy Byte-Pair Encoding to optimal partial-merge utility for three merges is at most 7/12.
Lean source view module on GitHub
noncomputable def bpe_worst_ratio (k : ℕ) : ℝ := sInf {r : ℝ | ∃ s t : List ℕ, bpe_steps bpe_greedy_step k s t ∧ 0 < bpe_optimal_utility s k ∧ r = ((s.length - t.length : ℕ) : ℝ) / bpe_optimal_utility s k}