Training on Checklists as Target Sets: Approachability-Directed Rewards for Partially Verifiable Generation

Reinforcement learning on language models works best when a program can say "right" or "wrong" about each answer. For open-ended writing, the closest thing available is a checklist: a list of yes/no questions about a response ("does it mention the 1929 crash?", "does it stay under 800 words?") answered by a reader model. ProxyReward builds such checklists of about 15 questions and trains on the fraction answered "yes". Averaging the answers treats the checklist as one number. That lets a model collect easy checks and ignore hard ones. It also cannot express requirements that couple items, such as "cover at least 12 of these facts while staying under a length budget."

We propose treating each prompt's checklist as a target region in the space of check outcomes, and choosing each training step's scalar reward by geometry. A classical result from repeated games, Blackwell approachability, shows how to steer an average vector of outcomes into a convex target set. At each step you look at the flat boundary (a "half-space") of the target nearest to where you currently are, and optimize the one-dimensional reward that points across it. Mannor, Perchet and Stoltz further show that a polytope target can be "lifted" into an orthant, a region defined only by lower bounds on each coordinate, where that projection becomes coordinate-wise clipping. Put together, a coupled, set-valued requirement becomes a sequence of ordinary scalar rewards built from boolean checks. Each step is therefore a standard reinforcement learning with verifiable rewards (RLVR) problem, and the machinery developed for math reasoning applies unchanged.

Core Claim

Write $v(y) \in \{0,1\}^K$ for the vector of check outcomes on a response $y$. The prompt's requirement is a polytope $S = \{v : Av \ge b\}$, whose rows encode per-item floors, "at least $m$ of $K$" coverage, length budgets and implication constraints. For each prompt, a group of $G$ rollouts is sampled, as in Group Relative Policy Optimization (GRPO), and $\bar v$ denotes their mean outcome vector. We lift to $z = A\bar v - b \in \mathbb{R}^m$, whose target is the nonnegative orthant, and form the per-rollout scalar reward

$$ r(y) = \langle u, v(y) \rangle, \qquad u = \frac{A^\top [\,b - A\bar v\,]_+}{\lVert [\,b - A\bar v\,]_+ \rVert} + \lambda \mathbf{1}, $$

where $[\cdot]_+$ clips negatives to zero and $\lambda$ is a small uniform term that keeps pushing once the group is inside $S$. The reward is then normalized within the group exactly as in GRPO.

The claim has three parts. First, this reward concentrates learning signal on the facets the policy is currently violating. Second, it does so per prompt, which matters because checklists differ from prompt to prompt. Third, it outperforms both uniform averaging and all-or-nothing rewards on the fraction of prompts whose requirements are fully met, without lowering average check accuracy. The direction $u$ is the normal of the violated half-spaces of the lifted target. Approachability theory guarantees that if every such half-space can be reached, then so can $S$. This is what licenses replacing a set-valued goal with a changing scalar one.

Relation to Prior Work

The method comes from two geometric-lifting papers. Set-valued approachability and online learning with partial monitoring supplies the half-space characterization and the lifting of polytopes into orthants. It studies abstract repeated games, not token policies. It also supplies a constraint: when outcomes are only partially observed, its rate slows from $O(n^{-1/2})$ to $O(n^{-1/5})$. This warns that noisy reader-model verdicts may make the direction $u$ unreliable, and we test for exactly that. Near-Optimal No-Regret Learning Dynamics for General Convex Games lifts strategy sets into $\mathbb{R}^{d+1}$ with a log regularizer to get fast no-regret rates. We borrow only the stability view, as a possible damping of $u$ across steps. We do not claim its $O(\log T)$ guarantee for language models.

The application side builds on ProxyReward, which motivates the problem and supplies our pipeline (code). ProxyReward uses a uniform average and trains with DPO. We keep its checks and replace the scalarization. ProxyQA gives the evaluation. Its reported 88% evaluator self-consistency, against 52% agreement from general judges, is our reason to trust boolean checks over holistic scores.

On the reinforcement learning side, 1-shot RLVR shows that GRPO learns only from prompts whose rewards vary within the group, and that long training can collapse outputs without entropy control. Anchored Policy Optimization documents the related "Recursive Space Contraction," in which positive sharpening and negative squeezing collapse output diversity. Both constrain our design. All-or-nothing checklist rewards over 15 items will rarely vary within a group, and our reward must not accelerate collapse.

JEPO handles unverifiable proofs by treating the reasoning as a latent variable, but it needs an exact answer string. Open-ended synthesis has no such string, so it is a complement rather than a competitor. Sub-goal reward work in GUI agents and geometric reasoning also decomposes outcomes into checks, but it sums them.

Characterization of the split closure via geometric lifting proves that a family of valid cuts can leave an arbitrarily large gap to the true integer hull. We read this as a caution that satisfying every check need not mean the response is good. We measure that "verification gap" directly.

Research Program

We first build per-prompt requirement polytopes on top of ProxyReward's synthesized checks. They are assembled from a small template library, with each template becoming one row of $A$:

  • a per-item floor, requiring each check to pass in at least a fraction $\tau$ of rollouts;
  • an "at least $m$ of $K$" coverage row;
  • a length-budget coordinate, appended as an extra boolean;
  • implication rows $v_B - v_A \ge 0$, emitted by the question generator when one item presupposes another, such as a claim and its required caveat.

Next, we implement the lifted-projection reward inside a standard GRPO loop. The cost of computing $u$ is one matrix-vector product per prompt, which is negligible next to generating the rollouts.

We then analyze three failure modes. The first is reader noise: we estimate the per-check flip rate of the reader by re-querying it, and test whether $u$ computed from noisy $\bar v$ still points consistently. For partial monitoring we also try the pessimistic surrogate of Mannor et al., counting a check as passed only when the reader passes it on repeated queries. The second is diversity collapse, measured with the diversity metrics used by Anchored Policy Optimization. The third is the verification gap, measured as the disagreement between "all facets satisfied" and a held-out pairwise judgment.

The parabolic-lifting view has a natural extension that we treat as secondary. Quadratic balance requirements, such as coverage spread evenly across sections, become linear facets once squared coordinates are added.

Baselines

The first reference point is the naive one: the base model with no post-training, alongside the model trained by ProxyReward's own recipe of uniform-average reward with DPO. For this recipe, ProxyReward reports that Qwen2.5-7B reaches 35.07% on ProxyQA, against 33.94% for GPT-4-Turbo. We re-run it from the released code rather than quoting it, so that data, checks and reader model are identical.

The strongest direct competitor is uniform-average reward trained with the same GRPO loop, group size, rollout budget and learning-rate sweep as our method. This isolates the scalarization from the choice of optimizer. If uniform GRPO already matches us, the geometry adds nothing.

Two further competitors test alternative scalarizations. The all-or-nothing reward gives 1 only if the response lies in $S$. The soft-minimum reward emphasizes the worst check. Both target the same goal as ours without projection.

A global primal-dual baseline learns one multiplier per template type (floor, coverage, length, implication), updated by dual ascent across prompts. It is the constrained-RL answer to the same problem.

Finally, two ablations isolate the key ingredients. The first removes the lifting, projecting in the original $v$ space onto the cube's all-ones corner, so that coupled rows are ignored. The second computes $u$ from a running average across steps rather than from the current group.

Every method gets the same prompts, the same synthesized checks, the same reader model, the same number of generated tokens, and the same tuning budget of six configurations. We would count our method as beating a baseline if it raises the full-requirement satisfaction rate on held-out prompts beyond seed variance across three seeds, while keeping mean ProxyQA accuracy within one point of that baseline or above it. No reported result was found on Lacuna for GRPO with checklist rewards on ProxyQA, so those rows are produced by this study.

Why not just…?

Why not just average the checks, as ProxyReward does? Averaging is the natural null hypothesis and already gave roughly a 20% relative gain according to ProxyReward. Its weakness is structural. A response that passes 14 easy checks scores the same as one that passes 14 including the hard one, and coupled rows such as length-versus-coverage cannot be expressed at all. The uniform-GRPO baseline settles this. If per-check pass rates under averaging stay flat on the hardest items while ours rise, the geometry is doing work. If not, we should drop it.

Why not just reward only fully satisfied checklists? This goal matches ours exactly, but with 15 checks almost every rollout in a group scores zero. The within-group variance that 1-shot RLVR identifies as the source of learning signal therefore vanishes. We will report the fraction of groups with nonzero reward variance under each scheme, which directly predicts this failure. The soft-minimum variant is the honest middle ground and is included.

Why not just use Lagrangian constrained RL? This is the real threat. On a fixed orthant target, our clipped-deficit direction behaves like dual weights set equal to the current violations. The difference is that ProxyReward's checks are generated per prompt. Global multipliers can only attach to template types, not to "mention the 1929 crash." Our direction is recomputed from each prompt's own rollout group. The primal-dual baseline tests exactly this. If it matches us, the contribution reduces to per-prompt dual weighting, and we would report it that way.

Why not just use a single LLM judge score? ProxyQA found that general judges agree with humans only 52% of the time and are confounded by length. Boolean checks reach 88% self-consistency. We keep a pairwise judge only as a held-out check on hacking, never as the training reward.

Proposed Experiments and Decisive Checks

The main testbed is ProxyQA's 100 human-curated meta-questions and 1,550 proxy questions, with Qwen2.5-7B and a Llama model of similar size. Training uses ProxyReward-synthesized checks, so the test checks are independent of the training checks. Web-based Question Answering (WQA) is a second evaluation. We report four quantities:

  • mean ProxyQA accuracy;
  • the full-requirement satisfaction rate under held-out polytopes;
  • the pass rate on the lowest-scoring decile of checks;
  • length and diversity statistics.

A sanity check tests the reduction to standard RLVR. With a single verifiable check, $K=1$, the method is identical to GRPO. On MATH500 with Qwen2.5-Math-1.5B, it should reproduce the known 1-shot curve, which 1-shot RLVR reports going from 36.0% to 73.6%.

A semi-verifiable test runs on Numina. The final-answer check is exact and the proof-step checks are reader-generated, with a JEPO hybrid as a comparison point. For this setting only a qualitative "outperformed both baselines" is reported in JEPO; no reported number was found on Lacuna.

Three checks decide the question.

  1. Coupled requirements. The gap between our method and the no-lifting ablation should appear on prompts with coupled rows (coverage-plus-length, implications) and vanish on prompts with only per-item floors. If it appears everywhere or nowhere, the lifting is not the cause.
  2. Reader noise. Injecting controlled flips into reader verdicts should degrade our method faster than averaging, as the partial-monitoring rate predicts. The pessimistic surrogate should recover part of that loss.
  3. Verification gap. On responses that satisfy every facet, held-out pairwise preference over uniform-GRPO outputs should exceed 50%. If full satisfaction does not translate into better responses, the checks are being gamed. That would be the split-closure warning realized in text, and a result worth reporting either way.