Correct, minimal, and all

TL;DR There are many problems that is partial ordered, yet we may ignore the requirement for minimality and alternatives as a preference. 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 to accelerate Bayesian optimization (BO).

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, 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 quite trivial: the scale is so small and its transition model fully known so that by importing pymdptoolbox you solve it directly, and it 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 (or better, minimal) space was the whole point.

Minimality is not a preference

People may say, why don’t just add a size penalty? There is a distinction. Minimality, meaning irreducible to sufficiently produce an outcome, is not equal to a preference on minimum sizes, it is the very definition of a valid answer. A well known example is, when Fritz Haber first got ammonia synthesis to work in 1909, his catalyst was Os, a rare and expensive metal, and the process built on it looked hard to scale. Later at BASF, Alwin Mittasch then tested thousands of catalyst compositions and found that Fe works too, as long as it comes with a couple of promoters such as K2O and Al2O3. That promoted-iron catalyst is what turned Haber’s tabletop demonstration into the industrial Haber–Bosch process. Today, the Haber–Bosch process produces nearly all of the world’s nitrogen used in fertilizers. By preferring a minimum size, we will miss the recipe that feeds the world. In this case, both Os and Fe + K2O + Al2O3 are MINIMAL, because they are all the irreducible conditions that convert nitrogen and hydrogen into ammonia. These two routes are also incomparable, so by only giving you the question “will this condition make the haber process work”, the “correct” response should include all of them.

And diversity?

What about adding a diversity term or trying soft RL to spread the probability, if we also want alternatives? Again, alternatives in this problem is not a preference either. If a reaction has one minimal recipe, the best answer is to only recover that recipe. If a reaction contains three, then the best return is just three, no more and no less. A diversity reward is blind to this.

Moreover, diversity method needs a metric: an entropy over recipes, or a distance between them, to tell whether it is diverse. But our nature never impose such metrics. The chemistry structure itself decides which recipes are alternatives: a recipe is an alternative when it works and needs every ingredient it has. Using a diversity metric is injecting a strong prior that does not exist in nature.

Finding the minimal answer AND every alternative is in fact a well-studied problem. If you are familiar with Boolean functions, the same problem is formalized as prime-implicant enumeration [3, 4]. However, algorithms for prime implicant enumeration can query a formula as often as they like. A chemist cannot: every query is an hours-long wet-lab experiment, the verifier is 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, minimal and including all alternatives. Mathematicians call this learning target partially ordered, and the rest of this blog is about what changes when you take that seriously.

Why this problem matters

Because we might just ignore a bunch of such problems, especially in RLVR, where the target is actually partial ordered. Tired of a hours long reasoning that just give you a trivial idea, an AI generated code base 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 (if being formalized correctly), 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 at the same time discover more routes”.

And more than just the RLVR we are familiar with. There are many things we can actually make them into a RLVR.

Partial orders and lattices

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

An order is a relation \(\le\) on a set that is reflexive, antisymmetric and transitive: every element is below itself, two elements below each other are the same element, and an element below a second one is below everything the second is below. The order on numbers is a total order, in which of any two elements one is below the other. A partial order drops that requirement and lets two elements be incomparable. On the left below, \(a \le b \le c \le d\) is a total order; on the right, \(a \le b \le d\) and \(a \le c \le d\) hold, but neither \(b \le c\) nor \(c \le b\), so \(b\) and \(c\) are incomparable.

Left: a total order. Right: a partial order, in which b and c are incomparable. A line runs up from an element to each element directly above it.

In our Haber example, recipes are ordered by “contains”: 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\). We draw it as a Hasse diagram, with one node per set and a line from \(S\) up to \(T\) when \(T\) adds 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. Together 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. Suppose a building has two doors and we ask how a burglar can get in. “Through the front door” is correct, and minimal, yet a guard who locks only that door leaves the building open: knowing what suffices takes one minimal answer, while knowing what must be blocked takes all of them.

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

First let’s formally define the target our problem asks:

\[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 certify 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. To value a region, we need a measure. Common choices for sets including counting measure and coverage measure. Here 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].

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.

The group value \(R(U)\) is a coverage function, so it is submodular, and the credit is its marginal gain. The form resembles the counterfactual credit of COMA [12] and the leave-one-out baseline of RLOO [13, 14], but what is deleted differs: COMA removes an agent’s action and RLOO a rollout’s reward, while here deleting a rollout removes the part of the lattice that only it certifies. The credit therefore measures how much of the answer a rollout supplies, not how much reward.

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 ground truth antichain we can enumerate (just like a maze or grid world example) so we can check whether a trained policy recovers the 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.

AI4S

Previous prime implicant enumeration methods cannot amortize. But for AI4S, amortization matters. 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

Interestingly, we can see the sparse circuit of a dense LLM model as a sufficiency question. We delibrately test this case also because the monotonicity is not strictly preserved, though it still falls-back to 1-minimal, to demonstrate the robustness. 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.

LLM Post-training

We post-train a language model with MWRL and other post training methods on problems whose answers actually form an antichain. The task is GMAT-style data sufficiency: each problem lists 8 true statements about two hidden whole numbers \(x\) and \(y\), and the model must name a set of statements that determines \(x\), with no statement it can drop, and give the value of \(x\).

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 effort 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 RLVR methods that respect the partial order.
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].
	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.
AI4S	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 only 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.
J. Foerster, G. Farquhar, T. Afouras, N. Nardelli and S. Whiteson. Counterfactual multi-agent policy gradients. AAAI, 2018.
W. Kool, H. van Hoof and M. Welling. Buy 4 REINFORCE samples, get a baseline for free! ICLR Workshop on Deep Reinforcement Learning Meets Structured Prediction, 2019.
A. Ahmadian, C. Cremer, M. Gallé, M. Fadaee, J. Kreutzer, O. Pietquin, A. Üstün and S. Hooker. Back to basics: Revisiting REINFORCE-style optimization for learning from human feedback in LLMs. ACL, 2024.