· 20 min read
Correct, minimal, and all
TL;DR Many problems ask for all the minimal correct answers, yet we often misinterpret this requirement as a preference for smaller size or diversity. Existing methods for reinforcement learning with verifiable rewards (RLVR) score each rollout on its own, so they cannot tell whether an answer is minimal or a new alternative, and in principle they are destined to fail. This post is about what happens when you actually respect that requirement. In LLM post-training, a model trained this way finds about twice as many of each problem’s minimal answers within 64 samples as any baseline, even GRPO with a minimality oracle.
During my summer visit to 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) [1, 2].
Take a reaction every high-school chemistry student has met: the Haber process, N2 + 3H2 ⇌ 2NH3. 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. Take each of these choices as one dimension of the reaction space. BO is very good at searching such a space for the best yield, but every dimension you give 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 looked trivial: the space is small and its transition model is fully known, so you can use pymdptoolbox, solve it directly, and succeed 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 giving BO a smaller (or better, minimal) space was the whole point.
Minimality is not a preference
Why not just add a size penalty? Minimality, meaning that nothing can be removed without losing the outcome, is not a preference for small size; it is the very definition of a valid answer. 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 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. This 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 would miss the recipe that feeds the world. In this case, both Os and Fe + K2O + Al2O3 are MINIMAL, because each is an irreducible set of conditions that converts nitrogen and hydrogen into ammonia. If you simply ask “what are the irreducible conditions that make the Haber process work?”, the answer should include both.
And diversity?
What about adding a diversity term or trying soft RL to spread the probability, if we also want alternatives? Alternatives are not a preference here either. If a reaction has one minimal recipe, the best answer is to only recover that recipe. If it has three, the best answer is exactly those three, no more and no less. A diversity reward is blind to this structure.
Moreover, a diversity method needs a metric, such as entropy, to judge whether answers are diverse. Nature imposes no such metric, so using one injects a strong prior that the problem itself does not contain.
In plain words, what we want is a family of recipes in which each recipe is correct and minimal, and we want to find all of them. Finding the minimal answer AND every alternative is in fact a well-studied problem. If you know Boolean functions, you will recognize this as prime-implicant enumeration [3, 4]. Algorithms for prime-implicant enumeration, however, can query a white-box formula as often as they like. Yet our chemists cannot: every query is an hours-long wet-lab experiment, the verifier is a black box, and each new reaction starts from scratch. Amortizing and scaling prime-implicant enumeration are also hard, because the search space has \(2^N\) elements for \(N\) conditions. The question then becomes: given only one bit from a black-box verifier, can RL recover this family, in a way that scales and amortizes? Our paper, Minimal Witness Reinforcement Learning (MWRL) [5], discusses this problem formulation, the rigorous mathematical framing, and our method in detail, but you don’t need to read the paper for the rest of the blog.
Why this problem matters
Because we might be ignoring a bunch of such problems, not just in AI4S but also in RLVR, where the target is often partially ordered. Tired of hours-long reasoning that just hands back an idea you already gave in the prompt, an AI-generated codebase full of unnecessary test files and SHA-256 checks, or a 1,000-page generated proof that keeps circling the same paths under countless assumptions? Each calls for minimal answers, and for all of them: two solutions that share no step confirm each other in a way that a hundred paraphrases of one cannot; the leanest codebase may rest on a library you are not allowed to use; and only the whole family of minimal assumption sets tells you which assumptions a theorem truly needs. Another important question that might be worth a look is red teaming, one of the biggest concerns in AI today. We want minimal jailbreaks because we want to know exactly why the model fails: the reasons that explain the failure, rather than just spotting a jailbreak. And we want all of them: a red-teamer rewarded for making a model misbehave can stop at the first jailbreak, but the model is only safe when every jailbreak is patched; a second jailbreak that doesn’t share anything with the first one will survive the patch. If we only ask for one answer, we are left to find the rest by hand. These problems (if formalized correctly) can be addressed by asking “what are the minimal sufficient ways of doing this?” instead of just “\(\text{success reward} - \alpha\,\text{size} + \beta\,\text{diversity} + \gamma\,\text{preference}\)” (which is still incorrect for these problems anyway).
Partial orders, Lattices and Monotonicity
If you are familiar with these concepts, you may skip this part.
An order is a relation \(\le\) on a set that is reflexive (\(3 \le 3\)), antisymmetric (\(x \le 3\) and \(3 \le x\) only when \(x = 3\)) and transitive (\(3 \le 5\) and \(5 \le 7\) give \(3 \le 7\)) [6]. The order that we are most familiar with 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.
In our Haber example, recipes are ordered by “contains”: Os alone lies below Os with K2O, since the second recipe contains the first, while Os and Fe + K2O + Al2O3 are incomparable because neither contains the other.
All subsets of a set \(E\) (here, the four ingredients), 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).
In this toy, we assume adding an ingredient to a correct recipe never makes it incorrect. We call such a verifier monotone. Under monotonicity a correct recipe \(S\) certifies every recipe above it, its up-set \(\uparrow S = \{T \subseteq E : T \supseteq S\}\). The correct 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 (a family in which no set contains another). The answer we want is this whole boundary, which no single best point can represent. 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
Existing RL methods, from PPO [7], GRPO [8] and RLOO [9, 10] to pass@k [11], soft RL [12] and RL-style samplers such as GFlowNets [13], assign credit locally: each rollout ends with a proposal, a set \(S_i\), the verifier returns one bit \(y_i\), and its reward depends only on \(S_i\) and \(y_i\): other rollouts enter at most through their own bits, never through how their sets relate to \(S_i\).
However, you can’t tell minimality, or whether a proposal is a new alternative, without knowing how it relates to the other proposals in the group. Os, Os + K2O and Fe + K2O + Al2O3 all count as a success. You can’t tell the difference between these three, and the RL optimizer will eventually end up at one of them. Thus no matter how you change the optimizer, as long as your credit assignment is local, you can’t address this problem [5]. Figure 2 shows where each kind of objective ends up putting its probability.
Relational credit assignment
So what should the credit assignment look like? Let’s start from what the problem actually asks for:
\[M = \min_{\subseteq}\,\{S \subseteq E : s(S) = 1\},\]where \(s(S) = 1\) means the verifier accepts \(S\), and \(\min_{\subseteq}\) (minimal under inclusion) keeps the sets that contain no other set of the family, so \(M\) is the set of minimal correct answers. Notice that \(\min_{\subseteq}\) compares sets with each other, so the credit has to look at a group of proposals together. Inside a group whose correct proposals are \(W\), the same objective becomes \(\min_{\subseteq} W\): the correct proposals that contain no other correct proposal of the group. We turn this objective, whose answer is a set, into a credit for each proposal in three steps:
From minimal elements to a region. With a monotone verifier, a correct proposal also certifies every superset of it. Together the correct proposals certify the region
\[U(W) = \bigcup_{S \in W} \uparrow S.\]The region and \(\min_{\subseteq} W\) carry the same information: the region is everything that contains a minimal proposal, and the lowest points of the region are exactly the minimal proposals. A duplicate, or a correct proposal that contains another one, does not change anything. So any group value that ignores duplicates and redundant proposals, as our objective does, can be written as a value of the region alone, \(G(W) = R(U(W))\) [5].
Valuing the region. We value a region by its coverage measure: its probability \(R(U) = \mu(U)\) under a base measure \(\mu\)—a product measure that includes each element independently with probability \(p\). Think of \(\mu\) as drawing a random recipe, with a coin flip for each ingredient that puts it in with probability \(p\); the value of a region is the chance that this random recipe falls inside it, that is, contains one of our correct proposals. A single correct set is then worth \(\mu(\uparrow S) = p^{\lvert S\rvert}\), and this gives us both things we asked for. A smaller set has a larger up-set, so removing a useless ingredient increases the value. And because incomparable sets cover different parts of the lattice, a new alternative will also increase the value by covering what the others did not. The product form is also the only one under which removing an ingredient multiplies the value by the same factor at every size [5]. This matters because a redundant answer can be long. If a set were worth \(1/(\lvert S\rvert + 1)\) instead, removing an ingredient would increase the value of a two-ingredient set by half but that of a twenty-ingredient set by only 5%, and the credit would hardly push a long answer to shrink. Under the product measure, every ingredient removed multiplies the value by \(1/p\), however long the answer is.
Credit by deletion. Each proposal gets the value its group loses without it,
\[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 proposals certify. Since the subtracted term does not depend on proposal \(i\), the policy gradient stays unbiased.
This credit gives back exactly the objective we started from. Because the product measure gives every recipe a positive chance (as long as \(0 < p < 1\)), \(A_i > 0\) exactly when proposal \(i\) is correct and no other correct proposal of its group is contained in it [5]. The reason is obvious. Take a correct proposal \(i\). Its set \(S_i\) is itself a point of \(\uparrow S_i\), and another correct proposal \(T\) certifies that point only when \(T \subseteq S_i\). If there is no such \(T\), proposal \(i\) alone certifies \(S_i\), which has positive probability, so \(A_i > 0\). If there is one, its up-set already covers all of \(\uparrow S_i\), and deleting proposal \(i\) does not lose anything. In other words, the proposals with positive credit are the members of \(\min_{\subseteq} W\) that appear only once in the group. One caveat: group-minimal is weaker than minimal. A redundant set still earns credit when its group happens to miss the correct sets inside it. A larger group helps any group method find rare correct answers; here it also sharpens the credit itself, because a larger group is more likely to hold both a minimal answer and a redundant superset of it, so group-minimal approaches minimal as the group grows. We further demonstrate this in our paper [5]. Figure 3 computes this credit on the lattice of Figure 1.
You may notice that \(R(U)\) is a coverage function, which is submodular, and the credit is just its marginal gain, as in submodular RL [14]. The form also looks like the counterfactual credit of COMA [15] and the leave-one-out baseline of RLOO [9, 10]. The difference is in what gets deleted, and why. COMA removes an agent’s action to ask how much that agent added to the team’s shared reward, a counterfactual that splits credit among agents. RLOO removes a rollout’s reward from the group average only to get a baseline that reduces variance; each rollout is still judged by its own reward. Here, deleting a proposal removes the part of the lattice that only it certifies. Like COMA’s, this is a counterfactual, but over the answer instead of a reward. So the credit measures how much of the answer a proposal supplies instead of how much reward it gets. In the paper, we also introduce a leave-two-out variant of this credit (l2o) that reduces its variance [5].
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.
Scalar value iteration starts from what stopping pays, \(s(S) - \lambda\lvert S\rvert\), and repeats
\[V_{k+1}(S) = \max\Big(s(S) - \lambda\lvert S\rvert,\ \max_{e \notin S} V_k\big(S \cup \{e\}\big)\Big)\]until nothing changes; the greedy policy then walks up from the empty recipe. Minimal-witness value iteration plans over regions instead. Its state is the region \(F\) certified by the recipes committed so far, and committing a correct recipe \(S\) adds the coverage
\[\Delta(S \mid F) = R(F \cup \uparrow S) - R(F) = \mu\big(\uparrow S \setminus F\big).\]Starting from \(F_0 = \varnothing\), it repeats
\[F_{k+1} = F_k \cup \uparrow S_k, \qquad S_k \in \arg\max_{S:\, s(S) = 1} \Delta(S \mid F_k),\]stopping when the largest \(\Delta\) is zero. Each step then commits a new minimal recipe, and the planner is guaranteed to stop when it has recovered the entire antichain [5].
Prime-implicant enumeration
The prime implicants of a monotone Boolean formula form a ground-truth antichain that we can enumerate (much like a maze or grid world you see in other RL papers), so we can demonstrate the different return structure from many RL methods. As the figure shows, our method recovers most of the antichain.
AI4S
Previous prime-implicant enumeration methods cannot amortize. But for AI4S, amortization matters. We train one policy conditioned on substrate 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. The substrate pairs are real reactions from the literature, but no existing dataset gives the yields of whole condition panels across many substrate pairs: papers report only a few conditions per reaction, mostly the ones that worked. So we fill in the panels with a mechanistic simulator calibrated on measured screens, and the yields here are simulated, not measured [5].
Mechanistic interpretability
Interestingly, we can see the discovery of sparse circuits in a dense LLM as a sufficiency question (“What are the minimal sparse circuits that do not affect the performance?”). We also chose this case on purpose because monotonicity does not strictly hold here, to test robustness; the guarantee then falls back to 1-minimality [16], where no single component can be removed. For each of 10 MMLU subjects we recover the family of 1-minimal circuits in a frozen Qwen3-1.7B.
LLM Post-training
We post-train a Qwen3-4B model with MWRL and other RL 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 minimal set of statements that determines \(x\) and give the value of \(x\).
On 512 held-out problems, MWRL finds about 70% of a problem’s minimal answers within 64 samples, about twice as many as any other method, including GRPO with a minimality oracle (Table 1). The size penalty and the oracle still score each proposal alone, so a repeated answer earns as much as a new one and their policies settle on a few small answers; the diversity reward compares proposals by their raw sets, so a superset of a found answer counts as new and its policy spreads over supersets.
| Method | Found by 16 samples | Found by 64 samples | Minimal | Statements | Distinct sets | Correct |
|---|---|---|---|---|---|---|
| Qwen3-4B-Base | 4.9% | 16.2% | 18.9% | 4.39 | 5.4 | 9.4% |
| GRPO | 0.0% | 0.0% | 0.0% | 8.00 | 1.1 | 99.6% |
| MaxRL | 0.1% | 0.3% | 0.0% | 7.98 | 1.4 | 99.0% |
| GRPO + size penalty | 28.0% | 33.2% | 84.6% | 2.36 | 2.5 | 95.5% |
| GRPO + minimality oracle | 30.4% | 36.5% | 96.9% | 2.21 | 2.2 | 90.5% |
| Diversity reward | 1.0% | 3.4% | 0.4% | 5.72 | 32.5 | 91.0% |
| Diversity reward + size penalty | 8.8% | 22.5% | 4.2% | 4.51 | 30.6 | 87.0% |
| MWRL | 41.4% | 72.0% | 37.3% | 2.90 | 14.0 | 63.0% |
MWRL does not seem to perform well on two columns, Correct and Minimal, which may look odd given the title. This is because both columns score single samples, while the actual question asks about the whole family, so a policy that collapses onto one correct answer naturally scores high on both. GRPO is the plainest case: it answers with all eight statements, the “include everything” answer from the opening, so it is correct 99.6% of the time and finds 0% of the minimal answers. The size penalty and the oracle do not fall back on including everything, but they also concentrate on a few small answers, only 2.2 to 2.5 distinct correct sets per problem, while MWRL spreads over about 14, some of them likely harder to get right. Meanwhile, the non-minimal samples that come with exploration are cheap to clean up: in a batch, any correct answer that contains a smaller correct one can be dropped without another call to the verifier. A minimal answer that was never sampled, however, cannot be recovered by any post-processing, so Found by \(k\) samples is the column that nothing else can make up for. This column also already pays for MWRL’s mistakes: it counts all \(k\) samples, incorrect ones included, so MWRL finds about twice as many minimal answers within 64 samples even though 37% of its samples are incorrect. MWRL’s 37.3% comes partly from exploration itself and partly from the caveat in the credit section: group-minimal is weaker than minimal, but given enough compute for a larger group (I ran each method with only 4 L40 GPUs, where 100 steps with 16 answers per problem already take 2 to 3 days), we are likely to see a steady improvement.
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 [18] and LeanDojo [19] supply the data. |
| Overthinking as redundant supersets | Read a solution as a set of reasoning steps. Test whether rewarding correctness alone makes redundant steps grow over training, and whether relational credit removes them without losing accuracy, compared with a length penalty. This is the one I’m most fascinated by. | |
| Agents, software and safety | Delta debugging with LLM agents | The minimal failure-inducing inputs, one per cause of a bug [16]. |
| Minimal sufficient evidence for RAG | Independent lines of support. The verifier, an NLI judgement, is not monotone in this case. This is where [5] restores monotonicity by counting a set as correct when any subset of it is, which keeps the same minimal sets. | |
| AI4S | Minimal cut sets of metabolic networks | Flux balance analysis is the verifier [20]; 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 [21]. | |
| 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. |
| A multi-answer RLVR benchmark | Tasks whose answers form an antichain by nature (prime implicants, minimal hitting sets, minimal unsatisfiable cores, minimal test cases, even math reasoning), each with exact ground truth, to measure RLVR methods that respect the partial order. | |
| 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 correct answer found so far into the covered region lets the partial order define novelty over the whole of training, beyond a single group. | |
| Circuits of SAE features | On public sparse autoencoders such as Gemma Scope [22], 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. arXiv:2610.07226, 2026.
- B. A. Davey and H. A. Priestley. Introduction to Lattices and Order, 2nd edition. Cambridge University Press, 2002.
- J. Schulman, F. Wolski, P. Dhariwal, A. Radford and O. Klimov. Proximal policy optimization algorithms. arXiv:1707.06347, 2017.
- Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. K. Li, Y. Wu and D. Guo. DeepSeekMath: Pushing the limits of mathematical reasoning in open language models. arXiv:2402.03300, 2024.
- 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.
- C. Walder and D. Karkhanis. Pass@K policy optimization: Solving harder reinforcement learning problems. arXiv:2505.15201, 2025.
- T. Haarnoja, A. Zhou, P. Abbeel and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. ICML, 2018.
- E. Bengio, M. Jain, M. Korablyov, D. Precup and Y. Bengio. Flow network based generative models for non-iterative diverse candidate generation. NeurIPS, 2021.
- M. Prajapat, M. Mutný, M. N. Zeilinger and A. Krause. Submodular reinforcement learning. ICLR, 2024.
- J. Foerster, G. Farquhar, T. Afouras, N. Nardelli and S. Whiteson. Counterfactual multi-agent policy gradients. AAAI, 2018.
- A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Transactions on Software Engineering 28(2), 183–200, 2002.
- F. Tajwar, G. Zeng, Y. Zhou, Y. Song, D. Arora, Y. Jiang, J. Schneider, R. Salakhutdinov, H. Feng and A. Zanette. Maximum likelihood reinforcement learning. ICML, 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.
- 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.