RLVR is blind to redundancy

TL;DR Many tasks have more than one minimal answer, and none of them contains another. Reinforcement learning with verifiable rewards (RLVR) scores each rollout on its own, so it cannot tell a new minimal answer from a redundant superset of one it already has. Starting from the subset order itself, we derive a credit that can.

During my summer visit in Shanghai, I was given a task: use RL to find which dimensions of a chemical reaction’s condition space are worth searching, so that Bayesian optimization (BO) can later search a smaller space.

Take a reaction every high-school chemistry student has met: the Haber process, N₂ + 3H₂ ⇌ 2NH₃. To make ammonia you choose a catalyst, possibly a few promoters for it, a temperature, a pressure and a ratio of the two gases. The textbook recipe is an iron catalyst at about 450 °C and 200 atm. Each of these choices is one dimension of the reaction space. BO is very good at searching such a space for the best yield (if you are not familiar with BO, see Frazier’s tutorial [1]; Shields et al. [2] show it optimizing real reactions), but every dimension you hand it makes the search more expensive. So the question becomes: starting from a baseline recipe, which dimensions do you actually need to turn to reach a good yield?

The task is actually trivial: the space is so small and its transition model so fully known that value iteration solves it directly (e.g. with pymdptoolbox), and the policy succeeds 100% of the time.

Seems easy. But is this what we want?

The result it returns simply says: “Include everything.” Of course, including everything IS a correct reaction space: BO will eventually find the right reaction no matter how large the space is. It is also useless, because handing BO a smaller space was the whole point.

What about a size penalty?

In chemistry, there is often MORE THAN ONE set of conditions that makes a reaction work. When Fritz Haber first got ammonia synthesis to work in 1909, his catalyst was osmium, a rare and expensive metal, and a process built on it looked hard to scale. At BASF, Alwin Mittasch then tested thousands of catalyst compositions and found that iron works too, as long as it comes with a couple of promoters such as potassium oxide and aluminium oxide. That promoted-iron catalyst is what turned Haber’s tabletop demonstration into the industrial Haber–Bosch process. Today, the Haber–Bosch process produces half of the world’s nitrogen used in fertilizers.

In this example, a size penalty would never help you find the iron route, because in terms of size it is larger than the osmium one: iron needs its promoters, and osmium works alone. The penalty keeps the smallest recipe and drops every alternative that needs even one more ingredient, however different its chemistry is. With a size penalty, we would miss the recipe that feeds half of the world.

And diversity?

What about adding a diversity term, or trying soft RL? Both still score each recipe on its own. Whether a recipe adds anything new depends on the recipes you already have, and a score that looks at one recipe at a time cannot see that.

Finding the minimal answer AND every alternative is in fact a well-studied problem. In logic it is prime-implicant enumeration [3, 4]. However, these algorithms enumerate the minimal sets of one problem whose formula they can query as often as they like. A chemist cannot: every query is an hours-long wet-lab experiment, the answer comes from a black box, and each new reaction starts from scratch.

In plain words, what we want is a family of recipes. Every recipe in it works, none contains an ingredient it can do without, and none contains another. Order recipes by “contains”, and this family is exactly the set of minimal elements of that order, which mathematicians call an antichain. The learning target is partially ordered, and the rest of this post is about what changes when you take that seriously.

Why this problem matters

Tired of AI writing you 5,000 words of redundant slop with no logical connection, a dump of code full of unnecessary test files and SHA-256 checks, or a 1,000-page generated proof that keeps circling around the same paths under countless assumptions? This problem, by definition, can be addressed by asking “what are the minimal sufficient ways of doing this?” instead of just “am I doing it correctly, plus do not do this, and do not do that”.

Minimality removes what an answer can do without. The antichain answers a different question, and one minimal answer cannot. Take red teaming. An RL red-teamer finds a minimal prompt that makes a model produce harmful output, and the lab patches it. A second minimal prompt shares no component with the first, so the patch leaves it untouched, and the model is still unsafe. The model is safe only when the patches hit every minimal attack, and a red-teamer rewarded for success converges once it has found one. Knowing what suffices takes one minimal answer; knowing what is necessary, or what must be blocked, takes all of them.

Partial orders and lattices

If you are familiar with these concepts, you may skip this part.

A partial order, unlike the order on numbers, lets two elements be incomparable, with neither below the other. Recipes ordered by “contains” are the example we need: osmium alone lies below osmium with potassium oxide, since the second recipe contains the first, while osmium and promoted iron are incomparable.

All subsets of a ground set \(E\), ordered by inclusion, form the subset lattice \(2^E\). It is a lattice because every two sets have a least upper bound, their union, and a greatest lower bound, their intersection. We draw it as a Hasse diagram, with one node per set and a line from \(S\) up to \(T\) when \(T\) adds exactly one element to \(S\) (Figure 1).

Figure 1The 16 recipes over four ingredients, in a toy version of ammonia synthesis where a recipe works when it contains osmium, or iron together with both promoters.

In this toy, adding an ingredient to a working recipe never stops it from working, and we call such a verifier monotone. Under monotonicity a working recipe \(S\) vouches for every recipe above it, its up-set \(\uparrow S = \{T \subseteq E : T \supseteq S\}\). The working recipes are therefore the union of the up-sets of the minimal ones, and the minimal recipes are the lower boundary of that region. They form an antichain, since a recipe that contained another working recipe would not be minimal. The answer we want is this whole boundary, and a single best point of the lattice cannot represent it.

Standard RL just can’t solve it

In RLVR, the policy samples a group of \(K\) rollouts, the verifier returns one bit \(y_i\) for each proposed set \(S_i\), and each rollout is scored by a reward \(r(S_i, y_i)\). The group return adds these rewards, one term per rollout, and no term depends on how the rollouts relate to each other. Whether a working recipe is minimal depends on whether some proper subset of it also works, which its own bit does not reveal. Osmium alone and osmium with potassium oxide both return a 1, so a reward that sees one recipe and its bit cannot separate them. Figure 2 shows where each kind of objective then puts its probability.

Figure 2Optimal probability of each recipe under four objectives on the lattice of Figure 1. Ringed: the minimal recipes.

Success-only rewards (PPO, GRPO, RLOO) and objectives on the success probability (pass@k, maximum-likelihood RL) cannot tell a minimal recipe from a padded one, a size penalty keeps only osmium, and soft RL with a size penalty still prefers osmium with one idle promoter to promoted iron.

The failure is not specific to this lattice. We define a reward as local when it is the same function \(r(S, s(S))\) of a set and its verification bit for every monotone verifier, so that it sees one proposal and its bit and no verification of the proposal’s subsets. A group return is separable when it adds local rewards over the rollouts of a group of size \(K\) drawn from the policy’s law \(q\).

Theorem 1 (Relational necessity [5]). Let a method target the maximizers of the separable objective \(J_{\mathrm{sep}}(q) = \mathbb{E}_{S_{1:K} \sim q^{\otimes K}} \sum_{i} r\big(S_i, s(S_i)\big)\), the law \(q \propto r(\cdot, s(\cdot))\) for a local reward \(r \ge 0\), or the maximizers of an objective that depends on \(q\) only through the success probability \(\Pr_{S \sim q}[s(S) = 1]\). Then, for \(\lvert E \rvert \ge 3\), some monotone predicate with \(\lvert M \rvert \ge 2\) has a target law whose support differs from \(M\).

The three cases cover the objectives of Figure 2. PPO, GRPO and RLOO maximize a separable objective, with or without a size penalty, since baselines and group normalization change the estimator and leave the objective separable. Soft RL and GFlowNets target a law proportional to a local reward, and pass@k and maximum-likelihood RL depend on the policy only through its success probability. The fault therefore lies in the return, and a better optimizer cannot repair it, because the optimizer maximizes a return that does not contain the distinction.

Relational credit assignment

The target is defined by an operator on a family of sets,

\[M = \min_{\subseteq}\,\{S \subseteq E : s(S) = 1\},\]

which keeps the working sets that contain no other working set. The operator compares sets with each other, so the return has to see a group of rollouts together. For a group whose working rollouts are \(W\), the group-level form of the objective is \(\min_{\subseteq} W\), the working rollouts that contain no other working rollout of the group. We turn this set-valued objective into a credit for each rollout in three steps.

From minimal elements to a region. Under a monotone verifier, the working rollouts vouch for the region

\[U(W) = \bigcup_{S \in W} \uparrow S.\]

The region and \(\min_{\subseteq} W\) determine each other: the minimal rollouts generate the region, and the minimal elements of the region are the minimal rollouts. Deleting a duplicate, or a working rollout that contains another, changes neither of them. A group value that ignores duplicates and dominated rollouts, as the objective does, is therefore a function of the region alone, \(G(W) = R(U(W))\) [5].

Valuing the region. We value a region by its probability \(R(U) = \mu(U)\) under a product measure \(\mu\) that admits each element independently with probability \(p\). One working set is then worth \(\mu(\uparrow S) = p^{\lvert S\rvert}\). A smaller set spans a larger up-set, so refinement toward a minimal set raises the value, and two incomparable sets cover different parts of the lattice, so a second route adds value the first cannot supply. The product form is the only one under which removing one element multiplies the value by the same factor at every size [5]; we use \(p = 0.7\).

Credit by deletion. Each rollout receives the value its group loses when that rollout is deleted,

\[A_i = R(U) - R(U_{-i}) = y_i\,\mu\big(\uparrow S_i \setminus U_{-i}\big),\]

where \(U_{-i}\) is the region the other rollouts vouch for. The subtracted term does not depend on rollout \(i\), so the policy gradient stays unbiased.

The credit returns the objective it started from. Under a measure with full support, \(A_i > 0\) exactly when rollout \(i\) works and no other working rollout of its group is contained in it [5], so the rollouts with positive credit are \(\min_{\subseteq} W\). The operator that defines the target is the support of the credit, and the return needs neither a diversity term nor any label of the minimal sets. Group-minimal is still weaker than minimal, since a padded set earns credit when its group misses the working sets inside it; the two coincide once the group is large enough to contain every minimal set [5]. Figure 3 computes this credit on the lattice of Figure 1.

Figure 3Deletion credit \(A_i\) of each rollout in a group, with \(p = 0.7\). Click a recipe to add it to the group or remove it; hover a row to see the part of the region only that rollout vouches for.

Anatomy

We first watch both mechanisms on the recipe lattice of Figure 1: the two planners one step at a time, then the two policy gradients in real time.

Figure 4Value iteration on the lattice of Figure 1. Top: scalar value iteration with a size penalty of 0.1 per ingredient; the numbers are state values. Bottom: minimal-witness value iteration with \(p = 0.7\); the numbers are the coverage each working recipe would add.

Figure 5Policy-gradient training on the lattice of Figure 1, for a tabular policy over the 16 recipes and groups of 8, one update per frame; the numbers are the policy's probabilities. GRPO normalizes success rewards within the group (learning rate 0.5); MWRL uses the deletion credit with the leave-two-out baseline and \(p = 0.7\) (learning rate 20). Restart draws a new seed.

Prime implicant enumeration

The prime implicants of a monotone Boolean formula form an antichain we can enumerate exactly, so we can check whether a trained policy recovers the whole family or stops at one answer.

Figure 6Proposals of each trained policy on one monotone MaxSAT instance with 14 variables and 10 clauses of length 3, whose satisfying assignments have 19 minimal elements. Each objective is trained with the paper's settings (groups of 48, 150 updates, seed 0) and then sampled 256 times.

Scientific variable identification

We train one policy across many Suzuki–Miyaura substrate pairs to propose the minimal sets of reaction conditions that must leave a baseline protocol, and test it on pairs it never saw.

Figure 7Held-out Suzuki–Miyaura substrate pairs, never seen in training. Each row of the switchboard is one minimal set of the 14 condition dimensions that must leave the baseline protocol (Pd(PPh₃)₄, Na₂CO₃, dioxane with 20% water, 80 °C, 4 h) together to reach 75% yield, with the values of its best reaction; the strips are the first 32 proposals of the fingerprint-conditioned and of the substrate-blind policy. Below, recall on all 205 held-out pairs, each policy sorted by its own recall; the shaded gap is what conditioning on the substrate adds. One run (seed 0) of the mechanistic benchmark: 819 training pairs, 4,800 updates.

Mechanistic interpretability

A circuit is a set of attention heads and MLP blocks that reproduces a model’s behaviour on its own; for each MMLU subject we recover the family of minimal circuits in a frozen Qwen3-1.7B.

Figure 8Minimal circuits recovered in Qwen3-1.7B (28 layers × 16 heads, MLP blocks below) for 10 MMLU subjects. A set of heads and MLP blocks is sufficient when, with every other component resample-ablated, it retains at least 80% of the clean-to-fully-ablated KL gap; the circuits of one subject form an antichain.

RLVR: post-training on data sufficiency

We post-train a language model with MWRL, GRPO and MaxRL on problems whose answers form an antichain.

Figure 9Training curves of Qwen3-4B-Base. Each problem lists 8 true statements about hidden integers, and an answer is a set of statements that determines one of them; the minimal such sets form the antichain. MWRL, GRPO and MaxRL share the model, the data and the budget (256 problems with 16 rollouts per step). Every point is measured on the 16 rollouts of problems the policy has not seen, and the dotted lines mark the base model.

Open directions

MWRL is our first step in this direction. Beyond those listed in Appendix I of [5], we raise several questions that may be worth a look.

Area	Direction	The antichain, and how to test it
RLVR post-training	Premise selection in Lean	The minimal sufficient premise sets of a theorem; the prover is the verifier, and Mathlib [6] and LeanDojo [7] supply the data.
	Overthinking as a flood of supersets	Read a solution as a set of reasoning steps. Test whether rewarding success alone makes redundant steps grow over training, and whether relational credit removes them without losing accuracy, compared with a length penalty.
	A multi-answer RLVR benchmark	Tasks whose answers form an antichain by nature (prime implicants, minimal hitting sets, minimal unsatisfiable cores, minimal test cases), each with exact ground truth, to measure how far GRPO and PPO collapse.
Agents, software and safety	Delta debugging with LLM agents	The minimal failure-inducing inputs, one per cause of a bug; the verifier runs the program [8].
	Red teaming in safety evaluation	The minimal sets of prompt components that trigger an unwanted behaviour, one per failure mode; a direct comparison with red-teaming RL that adds a diversity bonus.
	Minimal sufficient evidence for RAG	Independent lines of support. The verifier, an NLI judgement, is not monotone, since one more passage can introduce a contradiction, and this is where the existential closure of [5] applies.
Scientific discovery	Minimal cut sets of metabolic networks	Flux balance analysis is the verifier [9]; on small models the ground truth can be enumerated exactly.
	Minimal sufficient combinations of interventions	Synthetic-lethal gene pairs, drug combinations, or the minimal sets of transcription factors that induce pluripotency, as Yamanaka’s factors do [10].
	Minimal sufficient substructures of molecules	The substructures sufficient for a property, ordered by subgraph inclusion.
Methods and theory	Datasets whose answers are antichains	Most datasets still assume that a problem has one solution.
	Relational credit beyond lattices	Under the subsequence, subtree or subgraph order, the intersection of two up-sets is no longer a single up-set. This is the central obstacle to extending the method to reasoning traces, and a methods paper in its own right.
	Coverage measures and hypervolume	Unifying the two brings the tools of multi-objective optimization into policy learning, and carries the unbiased group credit of MWRL into multi-objective RL.
	Coverage memory across training	Merging every witness found so far into the covered region lets the partial order define novelty over the whole of training, beyond a single group.
	Antichain recall as an evaluation	A complement to pass@k, and eventually a standard metric.
	Circuits of SAE features	On public sparse autoencoders such as Gemma Scope [11], the minimal feature sets that reproduce a behaviour, one per mechanism.

References

P. I. Frazier. A tutorial on Bayesian optimization. arXiv:1807.02811, 2018.
B. J. Shields, J. Stevens, J. Li, M. Parasram, F. Damani, J. I. M. Alvarado, J. M. Janey, R. P. Adams and A. G. Doyle. Bayesian reaction optimization as a tool for chemical synthesis. Nature 590, 89–96, 2021.
W. V. Quine. The problem of simplifying truth functions. The American Mathematical Monthly 59(8), 521–531, 1952.
E. J. McCluskey. Minimization of Boolean functions. Bell System Technical Journal 35(6), 1417–1444, 1956.
T. Y. Tsui, Z. Ye, P. Cai, Y. Li, Y. Li and Z. Ai. Minimal Witness Reinforcement Learning. 2026.
The mathlib Community. The Lean mathematical library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, 367–381, 2020.
K. Yang, A. M. Swope, A. Gu, R. Chalamala, P. Song, S. Yu, S. Godil, R. Prenger and A. Anandkumar. LeanDojo: Theorem proving with retrieval-augmented language models. NeurIPS, 2023.
A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Transactions on Software Engineering 28(2), 183–200, 2002.
J. D. Orth, I. Thiele and B. Ø. Palsson. What is flux balance analysis? Nature Biotechnology 28, 245–248, 2010.
K. Takahashi and S. Yamanaka. Induction of pluripotent stem cells from mouse embryonic and adult fibroblast cultures by defined factors. Cell 126(4), 663–676, 2006.
T. Lieberum, S. Rajamanoharan, A. Conmy, L. Smith, N. Sonnerat, V. Varma, J. Kramár, A. Dragan, R. Shah and N. Nanda. Gemma Scope: Open sparse autoencoders everywhere all at once on Gemma 2. arXiv:2408.05147, 2024.