bpe_optimal_utility
def
The supremum, over strings reachable in k partial-merge steps, of the reduction in length of the input string.
Statement
noncomputable def bpe_optimal_utility (s : List ℕ) (k : ℕ) : ℕ
- Source
- Definitions for OP-1288, following arXiv:2611.08671, Section 2.
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 2
- bpe_stepsExactly k applications of the specified binary relation connect the input and output strings.
- bpe_partial_stepA partial merge replaces an arbitrary nonoverlapping subset of one pair by a fresh symbol, with an unchanged step allowed.
- Used by 2
- bpe_worst_ratioFor a merge budget k, the infimum of greedy length reduction divided by optimal partial-merge length reduction over finite natural-number…
- 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_optimal_utility (s : List ℕ) (k : ℕ) : ℕ := sSup {u : ℕ | ∃ t, bpe_steps bpe_partial_step k s t ∧ u = s.length - t.length}