op_1604_iid_greedy_bpe_budget_one
Open Problem OP-1604 (budget k = 1 case): For a merge budget of k = 1, every alphabet size q ≥ 2, every strictly positive probability vector p on Fin q summing to 1, and every tolerance ε > 0, the greedy BPE approximation probability iid_greedy_bpe_approx_prob q p 1 N ε tends to 1 as string length N tends to infinity.
Statement
theorem op_1604_iid_greedy_bpe_budget_one (q : ℕ) (hq : 2 ≤ q) (p : Fin q → ℝ) (hp_pos : ∀ i, 0 < p i) (hp_sum : ∑ i, p i = 1) (ε : ℝ) (hε : 0 < ε) : Filter.Tendsto (fun N : ℕ => iid_greedy_bpe_approx_prob q p 1 N ε) Filter.atTop (nhds 1)
- Formalizes
- arXiv:2411.08671 Greedy Byte-Pair Encoding Achieves at Least 0.361 of the Optimal Compression, Section 4.3; open problem OP-1604
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- bpe_min_greedy_utility_one_eq_optimalFor any string s and merge budget k = 1, the minimum reduction in length achieved by a greedy full-merge step equals the optimal reduction…
- iid_greedy_bpe_approx_probGiven alphabet size q, weights p : Fin q → ℝ, merge budget k, length N, and tolerance ε : ℝ, iid_greedy_bpe_approx_prob q p k N ε is the…
- iid_word_measureGiven natural numbers q and N, and real weights p : Fin q → ℝ, iid_word_measure q N p is the product measure on words Fin N → Fin q…
- iid_bpe_sharp_factor_boundsThe i.i.d. BPE sharp approximation constant c = (2 + √2)/4 lies strictly in the open unit interval (0, 1).
- iid_bpe_sharp_factorThe conjectured sharp uniform i.i.d. greedy Byte-Pair Encoding merge factor c = (2 + √2) / 4.
- bpe_optimal_full_utilityThe maximum total reduction in string length achieved by any k-step sequence of full Byte-Pair Encoding merges on s.
- bpe_min_greedy_utilityThe minimum total reduction in string length achieved by any k-step greedy Byte-Pair Encoding merge run on s under arbitrary tie-breaking.
Read back from the Lean
For every natural number $q$ such that $2 \le q$, every strictly positive probability vector $p : \mathrm{Fin}\;q \to \mathbb{R}$ (satisfying $0 < p(i)$ for all $i$ and $\sum_{i} p(i) = 1$), and every real number $\varepsilon > 0$:
As the word length $N \to \infty$ along Filter.atTop, the probability (under the i.i.d. product measure of words of length $N$ drawn according to $p$) that a word $w$ satisfies
$$\mathrm{bpe\_min\_greedy\_utility}(w, 1) \ge \left(\frac{2 + \sqrt{2}}{4} - \varepsilon\right) \cdot \mathrm{bpe\_optimal\_full\_utility}(w, 1)$$
tends to $1$ (in the topology of $\mathbb{R}$, i.e., nhds 1).
Here, the utilities are measured in terms of word length reduction:
- $\mathrm{bpe\_min\_greedy\_utility}(w, 1)$ is the infimum over all reachable strings $t$ via 1 greedy BPE merge step of the length reduction $N - \mathrm{length}(t)$.
- $\mathrm{bpe\_optimal\_full\_utility}(w, 1)$ is the supremum over all reachable strings $t$ via 1 general BPE merge step of the length reduction $N - \mathrm{length}(t)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
For a merge budget of k = 1, greedy BPE selects the most frequent adjacent pair in the string, which achieves the exact optimal utility for a single merge. Because the theoretical BPE sharp factor is strictly less than 1 and the tolerance ε > 0, the target ratio is strictly less than 1; combined with the non-negativity of utility, every string trivially satisfies the approximation condition. Consequently, the approximating event is the entire space of words, so its probability under the i.i.d. product measure is identically 1 for every string length N. Being a constant sequence, this probability converges to 1 as N tends to infinity.
The single-letter marginal distribution is a probability measure.
The marginal distribution on characters Fin q is defined as the discrete measure ∑ j, p j • Dirac j. To show it is a probability measure, it suffices to verify that the measure of the universal set is 1. Evaluating the finite sum of scaled Dirac measures on Set.univ reduces to ∑ j, p j * 1. Pulling the sum into ENNReal.ofReal using the non-negativity of each p j and applying the assumption ∑ j, p j = 1 shows the total measure is 1.
uses
MeasureTheory.Measure.coe_finsetSum,Finset.sum_apply,MeasureTheory.Measure.smul_apply,smul_eq_mul,MeasureTheory.Measure.dirac_apply,Set.indicator_of_mem,Set.mem_univ,Pi.one_apply,mul_one,ENNReal.ofReal_sum_of_nonneg,le_of_lt,ENNReal.ofReal_onehave hmarg : MeasureTheory.IsProbabilityMeasure (∑ j, ENNReal.ofReal (p j) • MeasureTheory.Measure.dirac (j : Fin q)) := by refine ⟨?_⟩ rw [MeasureTheory.Measure.coe_finsetSum] simp only [Finset.sum_apply, MeasureTheory.Measure.smul_apply, smul_eq_mul] simp only [MeasureTheory.Measure.dirac_apply, Set.indicator_of_mem, Set.mem_univ, Pi.one_apply, mul_one] rw [← ENNReal.ofReal_sum_of_nonneg (fun i _ => le_of_lt (hp_pos i)), hp_sum, ENNReal.ofReal_one]
For every string length N, the greedy BPE approximation probability equals 1.
Fixing an arbitrary string length N, the product measure iid_word_measure q N p is a probability measure because each coordinate marginal is one. Unfolding the definition of iid_greedy_bpe_approx_prob, the approximating event consists of all words w whose greedy utility is at least (c - ε) times their optimal utility, where c is the sharp BPE factor. For budget k = 1, greedy utility equals optimal utility (bpe_min_greedy_utility_one_eq_optimal). Since c < 1 (iid_bpe_sharp_factor_bounds.2) and ε > 0, the factor satisfies c - ε < 1. Because utility is non-negative, any value u ≥ 0 satisfies u ≥ (c - ε) * u, so every word satisfies the inequality and the event is the entire space Set.univ. Since the word measure is a probability measure, the measure of Set.univ is 1, so the probability is 1.
uses
MeasureTheory.Measure.pi.instIsProbabilityMeasure,Set.mem_ofPred_eq,Set.mem_univ,iff_true,bpe_min_greedy_utility_one_eq_optimal,iid_bpe_sharp_factor_bounds.2,MeasureTheory.measure_univ,ENNReal.toReal_onehave hprob : ∀ N : ℕ, iid_greedy_bpe_approx_prob q p 1 N ε = 1 := by intro N haveI : MeasureTheory.IsProbabilityMeasure (iid_word_measure q N p) := by rw [iid_word_measure] exact MeasureTheory.Measure.pi.instIsProbabilityMeasure _ unfold iid_greedy_bpe_approx_prob have huniv : {w : Fin N → Fin q | (bpe_min_greedy_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) ≥ (iid_bpe_sharp_factor - ε) * (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ)} = Set.univ := by ext w simp only [Set.mem_ofPred_eq, Set.mem_univ, iff_true] -- Greedy and optimal agree for one merge. rw [bpe_min_greedy_utility_one_eq_optimal] have hc : iid_bpe_sharp_factor - ε < 1 := by have := iid_bpe_sharp_factor_bounds.2 linarith have hu : (0:ℝ) ≤ (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) := by positivity nlinarith rw [huniv, MeasureTheory.measure_univ] exact ENNReal.toReal_one
The greedy BPE approximation probability tends to 1 as string length N tends to infinity.
Since the greedy BPE approximation probability is identically 1 for all N, the sequence is constant. A constant sequence converges to its constant value, so the limit as N → ∞ is 1 (tendsto_const_nhds).
uses
tendsto_const_nhdssimp only [hprob] exact tendsto_const_nhds
MeasureTheory.Measure.coe_finsetSum- Evaluating a finite sum of measures on a set equals the sum of the individual measures evaluated on that set.
Finset.sum_apply- Evaluating a pointwise finite sum of functions at a point equals the sum of each function evaluated at that point.
MeasureTheory.Measure.smul_apply- Evaluating a scalar-multiplied measure on a set equals the scalar times the measure of the set.
smul_eq_mul- Scalar multiplication of elements in a ring or monoid acting on itself is standard multiplication.
MeasureTheory.Measure.dirac_apply- The Dirac measure at a point evaluated on a set is the indicator of that set at the point.
Set.indicator_of_mem- The indicator function of a set evaluated at a point in that set takes the value of the underlying function at that point.
Set.mem_univ- Every element of a type belongs to the universal set of that type.
Pi.one_apply- Evaluating the constant function 1 at any argument gives 1.
mul_one- Multiplying any element by 1 on the right yields the element itself.
ENNReal.ofReal_sum_of_nonneg- The embedding from non-negative reals into extended non-negative reals preserves finite sums.
le_of_lt- A strict inequality implies the corresponding non-strict inequality.
ENNReal.ofReal_one- The extended non-negative real corresponding to the real number 1 is 1.
MeasureTheory.Measure.pi.instIsProbabilityMeasure- A finite product of probability measures is a probability measure.
Set.mem_ofPred_eq- Membership of an element in a set defined by a predicate is equivalent to the predicate holding for that element.
iff_true- A proposition is equivalent to True if and only if the proposition holds.
bpe_min_greedy_utility_one_eq_optimal- For any string, the greedy BPE utility for a single merge equals the optimal utility for a single merge.
iid_bpe_sharp_factor_bounds.2- The theoretical sharp approximation factor for BPE is strictly less than 1.
MeasureTheory.measure_univ- In any probability space, the measure of the entire space is 1.
ENNReal.toReal_one- Converting the extended non-negative real number 1 to a real number yields 1.
tendsto_const_nhds- A constant sequence converges to that constant value along any filter.
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.
/-- The greedy BPE approximation probability tends to 1 for merge budget k = 1. -/theorem op_1604_iid_greedy_bpe_budget_one (q : ℕ) (hq : 2 ≤ q) (p : Fin q → ℝ) (hp_pos : ∀ i, 0 < p i) (hp_sum : ∑ i, p i = 1) (ε : ℝ) (hε : 0 < ε) : Filter.Tendsto (fun N : ℕ => iid_greedy_bpe_approx_prob q p 1 N ε) Filter.atTop (nhds 1) := by -- Each marginal of the i.i.d. product measure is a probability measure. have hmarg : MeasureTheory.IsProbabilityMeasure (∑ j, ENNReal.ofReal (p j) • MeasureTheory.Measure.dirac (j : Fin q)) := by refine ⟨?_⟩ rw [MeasureTheory.Measure.coe_finsetSum] simp only [Finset.sum_apply, MeasureTheory.Measure.smul_apply, smul_eq_mul] simp only [MeasureTheory.Measure.dirac_apply, Set.indicator_of_mem, Set.mem_univ, Pi.one_apply, mul_one] rw [← ENNReal.ofReal_sum_of_nonneg (fun i _ => le_of_lt (hp_pos i)), hp_sum, ENNReal.ofReal_one] -- For budget k = 1 the approximating event is the whole space, so the probability is 1. have hprob : ∀ N : ℕ, iid_greedy_bpe_approx_prob q p 1 N ε = 1 := by intro N haveI : MeasureTheory.IsProbabilityMeasure (iid_word_measure q N p) := by rw [iid_word_measure] exact MeasureTheory.Measure.pi.instIsProbabilityMeasure _ unfold iid_greedy_bpe_approx_prob have huniv : {w : Fin N → Fin q | (bpe_min_greedy_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) ≥ (iid_bpe_sharp_factor - ε) * (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ)} = Set.univ := by ext w simp only [Set.mem_ofPred_eq, Set.mem_univ, iff_true] -- Greedy and optimal agree for one merge. rw [bpe_min_greedy_utility_one_eq_optimal] have hc : iid_bpe_sharp_factor - ε < 1 := by have := iid_bpe_sharp_factor_bounds.2 linarith have hu : (0:ℝ) ≤ (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) := by positivity nlinarith rw [huniv, MeasureTheory.measure_univ] exact ENNReal.toReal_one simp only [hprob] exact tendsto_const_nhds