Definition. Edit-distance reward [ftip-00AB]
Definition. Edit-distance reward [ftip-00AB]
Let \(y=y_1\cdots y_m\) and a nonempty target \(\tau =\tau _1\cdots \tau _n\) be finite strings. Their Levenshtein distance is determined by \(D(0,j)=j\), \(D(i,0)=i\), and, for \(i,j>0\),
\[ D(i,j)=\min \left \{ \begin {aligned} &D(i-1,j)+1,\\ &D(i,j-1)+1,\\ &D(i-1,j-1)+\mathbf 1\{y_i\neq \tau _j\} \end {aligned} \right \}. \]Set \(L(y,\tau )=\max \{|y|,|\tau |\}\). The edit-distance reward is
\[ r_{\rm edit}(y,\tau ) =\max \left \{0,1-\frac {D(|y|,|\tau |)}{L(y,\tau )}\right \}. \]The recurrence is Equation (1) in the main text and Equation (4) in Appendix C of Demystifying Reinforcement Learning Post-Training of Language Models[clay2026demystifying]; the normalized reward is its Equation (5). The nonempty-target assumption makes the displayed denominator positive. This reward does not establish that edit similarity is the correct utility for a different task.