Joint, Precision-Safe Edit Selection by Low-Rank Semidefinite Relaxation

Systems that fix errors in text, such as grammar correctors, often do more harm by "fixing" correct text than by leaving a real error alone. Human judges punish wrong edits much more than missed ones, so the field scores systems with $F_{0.5}$, which weights precision twice as heavily as recall. Today precision is enforced in two ways. One is a hard gate: a classifier decides which sentences may be touched at all. The other is to train the correcting model to edit less often. Both make each decision more or less in isolation. Edits are not independent, though. Two systems' proposals can overlap on the same words. An agreement fix in one place implies another fix elsewhere. A text that is clean overall makes every proposed edit inside it less likely to be needed. Choosing the best set of edits under these couplings is a combinatorial problem, and at document or corpus scale it is hard to solve exactly.

We propose to pose edit selection as a precision-weighted binary quadratic program over candidate edits pooled from several correction systems. We solve it with the low-rank semidefinite relaxation machinery that made MAP inference in Markov random fields scale to tens of thousands of variables. A semidefinite relaxation replaces yes/no variables with vectors whose inner products form a positive semidefinite matrix, which turns the problem into a convex one. The low-rank solvers keep that matrix in factored form so memory stays small. We then use the relaxation's own confidence to decide what to commit. An edit is applied only if its relaxed value is close to "yes." Everything else is left unchanged. This gives a soft, joint replacement for the hard gatekeeper, and the gap between the relaxed and rounded objectives serves as a per-document certificate of how far the chosen edit set could be from optimal.

Core Claim

At a fixed precision, choosing edits jointly over a coupled graph recovers more true corrections than thresholding each candidate edit independently. The gain should be largest where error base rates shift, as with high-proficiency or native writing. We expect a low-rank semidefinite relaxation with confidence-gated rounding to be the right solver here for two reasons. It stays tractable when the coupling graph is dense and spans whole documents or corpora, which is where exact integer programming becomes too slow. Its rounding step also turns naturally into abstention, which is exactly the behavior a precision-first task needs. The modeling claim (joint beats independent) and the solver claim (SDP beats IP, LP and annealing at scale) are separable. The experiments test each one on its own.

Positioning Against Prior Work

The motivating evidence comes from the error-detection literature. The AIP-Tohoku System at the BEA-2019 Shared Task put a BERT sentence-level detector in front of a correction model. This raised precision by over 3 points and reached precision 70.60 and $F_{0.5}$ 65.57. It also shows the cost of hard gating: any error in a sentence the detector passes is lost for good. Cross-Sectional Evaluation of Grammatical Error Correction Models found that neural models over-correct native-level text, where SMT reaches $F_{0.5}$ 19.7 against 17.8 for a Transformer. A fixed operating point therefore fails when the error base rate moves, which our document-level coupling targets directly. LLMRefine showed that critic precision matters more than recall for refinement. It uses simulated annealing over edits and concedes the latency cost. We replace that stochastic search with a convex relaxation that carries a bound. ErAConD documents the "pedantry trap" in conversational correction and provides a dialog setting where turns are coupled.

The precision-first training methods are the competitors we combine with, not discard. Edit-Wise Preference Optimization weights edit tokens during preference tuning, and Adapting LLMs for Minimal-edit GEC trains on correct examples last to suppress over-correction. Both shape a single model at training time. Our method sits at inference time on top of their outputs, and it can only help if it adds information those models lack, namely cross-system agreement and cross-span coupling.

The closest structural precedent is Consistency-based Abductive Reasoning over Perceptual Errors. That paper selects a subset of predictions from several pre-trained vision models to maximize recall under a cap on logical inconsistency, solved by integer programming or greedy heuristic search. It shares our problem shape. It differs in using exact IP or uncertified heuristics, in working on aerial perception rather than text edits, and in using hard constraints rather than a continuous confidence for abstention.

The method itself comes from Scalable Semidefinite Relaxation for MAP Estimation. That work drops redundant constraints, factors $X = YY^T$, solves by an alternating-direction method (ADMM), and fixes only confident variables during rounding. On its benchmarks it found the lowest-energy assignment every time on ORIENT and PIC-Object, and it scaled to 100,000 variables on grids and 5,000 on dense graphs. It never treats asymmetric false-alarm costs, and it is limited to pairwise interactions, which constrains our model to pairwise couplings. An Efficient QP Relaxation for Large-Scale MIMO Detection supplies a cheaper vector-space relaxation that we use as a solver ablation. In its regime, that relaxation beat non-convex power methods on ill-conditioned instances.

The Formulation

For a document with candidate edits $e = 1, \dots, n$ pooled from $K$ correction systems, let $z_e \in \{0,1\}$ indicate that edit $e$ is applied. Let $p_e$ be its calibrated probability of being correct, fit on development data from features such as the number of systems that propose it, edit type and detector score. Let $c > 1$ be the cost of a false edit relative to a missed one. Let $J_{ef}$ be a pairwise coupling: strongly negative for overlapping, mutually exclusive edits, positive for edits that must co-occur (agreement, tense consistency across sentences), and learned for edits of the same pattern elsewhere in the document. We add one latent variable $z_0$ per document meaning "this text is largely clean," coupled to every edit with weight $J_{0e}$. This lets the whole document become more skeptical, a soft version of the proficiency-prediction module in AIP-Tohoku. We solve

$$\max_{z \in \{0,1\}^{n+1}} \; \sum_{e} \big(p_e - c\,(1-p_e)\big) z_e + \sum_{e<f} J_{ef}\, z_e z_f ,$$

and we sweep $c$ to trace the precision-recall curve. Mapping $z$ to $\pm 1$ variables and lifting to $X \succeq 0$ with unit diagonal gives a semidefinite program of the same form as the MAP relaxation, solved by the factored ADMM solver. Rounding commits $z_e = 1$ only when the relaxed value exceeds $1-\delta$. All other edits default to "no change," so uncertainty becomes abstention rather than a coin flip. The coupling weights are a handful of feature weights fit on development data. The point is a small, inspectable model, not a new learner.

At sentence level, $n$ is small and exact search is trivial, so scale enters only at document level (hundreds of candidates per essay from five to ten systems) and at corpus level. At corpus level we optionally link same-pattern edits across essays in the same proficiency band. This yields $10^4$ to $10^5$ variables with dense blocks, the regime where the MAP paper reports interior-point solvers such as MOSEK failing.

Baselines

The naive reference point is the strongest single input system run alone, with no selection. Next to it is majority voting, which applies an edit if at least $k$ of $K$ systems propose it, with $k$ tuned on development data. The strongest simple competitor is independent calibrated thresholding: apply edit $e$ if $p_e$ exceeds a threshold chosen to maximize $F_{0.5}$ on development data. This uses exactly our unary scores and calibration, so any gain over it is attributable to the pairwise and document-level couplings. It is the key ablation for the modeling claim.

The gatekeeper baseline puts a sentence-level detector, built as in AIP-Tohoku, in front of the same edit pool. For the strongest existing correction systems, we will reproduce an EPO-style model and the two-stage minimal-edit schedule and include them in the candidate pool. On BEA-19 test, Edit-Wise Preference Optimization reports $F_{0.5}$ 75.91 for Mistral-7B with EPO, against 73.37 for supervised fine-tuning. For the minimal-edit schedule of Adapting LLMs for Minimal-edit GEC, no reported result was found on Lacuna for its BEA-19 number. If our reproduction of EPO falls short of 75.91, we report our reproduced figure as the comparison point and say so. Beating the strongest system means our selection over a pool that includes it exceeds its $F_{0.5}$ on BEA-19 test via the official scorer. It also means our method beats independent thresholding by a margin larger than the run-to-run variation across tuning seeds.

For the solver claim, every solver optimizes the identical objective with the identical $p_e$, $J$ and $c$. The competitors are exact binary quadratic programming with a commercial-grade IP solver under a fixed wall-clock budget, an LP relaxation with the same rounding, simulated annealing as in LLMRefine with matched compute, greedy heuristic search as in the abductive-reasoning paper, and the vector-space QP relaxation of the MIMO paper. Beating them means equal or better objective and $F_{0.5}$ on document-level instances, plus completing corpus-level instances within budget where IP does not.

Why not just…?

Why not just threshold each edit's calibrated score? This is the real threat. If couplings carry little information beyond pooled votes, independent thresholding will match us. Overlaps can also be resolved by a trivial "keep the higher-scoring edit" rule. The experiment settles it directly, because the thresholding baseline shares every unary input. We will report the gain separately on documents with many cross-sentence dependencies and on native-level essays, where the latent "clean document" variable should matter most. If no gain appears there, the modeling claim fails and we will say so.

Why not just use an exact integer programming solver? For single essays it may well finish quickly, and then the semidefinite relaxation offers only its bound and its abstention behavior, not speed. We measure IP runtime as instance size grows from sentence to essay to corpus scale and report the crossover honestly. The case for the relaxation rests on dense corpus-scale couplings, where the MAP paper documents interior-point and LP approaches failing. If corpus-level coupling does not improve $F_{0.5}$, that case disappears, and the contribution reduces to the document-level model solved however is fastest.

Why not just fine-tune a more conservative model with EPO or a staged schedule? These methods shape one model's tendencies, but they cannot see what other systems propose or how a document's edits constrain each other. The cross-sectional evaluation also shows that trained operating points drift with writer proficiency. We use these models as inputs, so the question is only whether selection on top of them adds anything. The comparison against the best single system answers it.

Why not just search with simulated annealing? It optimizes the same objective without convexity, but LLMRefine reports high latency, and annealing gives no bound. At matched compute we compare objective value and $F_{0.5}$, and we check how often annealing lands below the relaxation's rounded solution.

Proposed Experiments

Development uses the BEA-2019 W&I+LOCNESS development set, broken down by CEFR level A, B, C and native N, with ERRANT precision, recall and $F_{0.5}$. Final numbers come from the BEA-19 test via the official evaluation and from CoNLL-2014 with the $M^2$ scorer. The CoNLL shared task's best was 37.33 without alternative answers and 45.57 with them, and the cross-sectional study reports a Transformer at 48.62. These numbers place context, not targets, since modern pools will exceed them. ErAConD tests turn-coupled dialog, where the reported fine-tuned XLNet reaches $F_{0.5}$ 0.352 and precision 0.683. There we break results down by severity level, to check that abstention removes mainly the trivial level-1 edits.

The first decisive check concerns the modeling claim. We plot full precision-recall curves by sweeping $c$, and compare recall at matched precision (for example, precision 70) against independent thresholding, overall and per proficiency level. The prediction is a larger gain on level-N text. The second check concerns certification. On essays small enough for exact IP, we measure the gap between relaxed bound, rounded objective and true optimum. We also test whether a document's relaxation gap predicts its precision, which would make the gap usable as a per-document confidence signal. The third check concerns scale. We report runtime and memory against number of variables from $10^2$ to $10^5$, using document-level and corpus-level graphs, for the factored semidefinite solver, IP, LP, annealing and the QP relaxation. We also report whether corpus-level edges change $F_{0.5}$ at all. The fourth check is a stress test: we inject subtle, multi-token errors and test whether joint selection recovers those a sentence gate blocks, which is the recall ceiling AIP-Tohoku leaves open.