Verifiable rewards turn agent training into a scheduling problem
New work suggests the limit on reliable agents is not clever rewards, but how much checked experience a compute budget can produce.
Ines KovačFrontier models and AI agents
New work frames verifiable rewards as a training constraint, because model-generated rollouts are costly. One RLVR result links larger batches to slower learning and schedule failures, while separate work describes an investigation into offline Q-learning and a Lean coding-agent baseline. The practical question is whether verification can scale with compute budgets.
The cheap part of training agents with verifiable rewards is the checking step. The expensive part is producing enough model-generated attempts for the checker to judge, according to new work on reinforcement learning with verifiable rewards.
That shifts the bottleneck from benchmark design to compute scheduling: how many rollouts to run, when to spend it, and how to keep an agent reliable while the budget is finite.
Verification is easy; experience is expensive
RLVR is attractive because the reward is not a human label. A test suite, a proof checker, or another automatic rule can say whether an attempt succeeded. The paper on RLVR says the system still relies on costly model-generated responses. In plain terms, the model must produce many candidate trajectories before the checker can sort useful behaviour from noise.
Cost has two layers. The first is raw compute. The second is scheduling: if responses are expensive, the trainer must decide whether to spend tokens on more attempts, longer attempts, or earlier attempts in the schedule. In other words, the reward function is not free; it is paid for in rollouts. That is why a statement about rewards becomes a statement about operations.
Batch size is not just throughput
The same work reports a puzzling result: larger rollout batches learn slower but fail on schedule. If accurate, the mechanism is intuitive. A big batch can average over more attempts, but it can also delay the feedback that tells the policy which moves are worth repeating. The trainer gets more data per step, yet less timely learning per unit of compute.
If accurate, the result would matter because schedules determine when a policy sees a reward signal relative to compute already spent. This is one investigation, not a settled engineering law. But it points at a practical distinction: throughput is not the same as progress. A cluster can be busy and still be behind.
Offline reinforcement learning shows a related caution. A separate paper says it investigates offline Q-learning with KL regularization for finite-horizon Markov decision processes. One reading is that the paper's own statement defines the scope; another is that the scope remains narrow until the method is tested beyond finite horizons, a regularizer, and an offline setting. Either way, the question is the same: how much can an agent improve from stored experience without burning fresh compute?
Concrete agent work is more modest. A Lean-focused paper introduces mini-Lean-agent and describes it as a coding-agent baseline for Lean. One reading is that this gives theorem-proving agent work a shared measuring stick. Another is that a baseline introduced by its own paper is only a starting point until independent teams adopt it. The stronger version would be a common test object; the safer version is a tool awaiting reuse.
Agents still live in text and shells
Elsewhere, the work says LLM-based automated heuristic design discovers heuristics for combinatorial optimization problems. That is a real use case, but the finding stops at discovery. It does not, by itself, tell a buyer which problems, which budgets, or which failure rates apply.
Two other points are almost boring. The observations say general-purpose coding agents use standard shell and file interactions, and modern LLM agents still reason and interact through text. The importance is not novelty; it is constraint. If the interface is text and ordinary shell commands, every improvement in reward verification must survive contact with files, permissions, logs, and failed commands.
The open question is not whether rewards can be verified. It is whether labs can buy enough verified experience cheaply enough to make agents dependable on an ordinary Tuesday, without a human watching every step.
- 01New work treats reward verification as a training constraint tied to compute scheduling.
- 02One RLVR paper says model-generated responses are costly.
- 03The same work reports larger rollout batches learn slower but fail on schedule.
- 04A separate paper says it investigates offline Q-learning with KL regularization for finite-horizon Markov decision processes.
- 05A Lean paper introduces mini-Lean-agent and describes it as a coding-agent baseline.
Interpretation, not reporting. The facts above carry their tiers; this is one correspondent’s reading of them.
The important move in this batch of work is not any single benchmark. It is the shift from asking what an agent can do in a demo to asking how much verified experience its training budget can afford. I find that reframing useful because it separates three things that often get blurred: the checker, the rollout schedule, and the interface through which the agent acts. If larger rollout batches really learn slower but fail on schedule, then raw parallelism is not a cure; it may be a cost. If mini-Lean-agent is only a baseline introduced by its own paper, then Lean agent progress needs external adoption before it becomes a yardstick. And if agents still reason through text and use ordinary shell and file interactions, the unglamorous parts of computing are the test. I would watch for independent replication of the batch-size result and for heuristic-design findings that specify budgets and failure modes. What would change my mind: evidence that larger batches reliably improve schedule performance across tasks, or that a single baseline becomes common without its authors pushing it.
— Ines Kovač
Every claim in this article, and what it rests on
We do not ask you to take our word for it. Each statement below carries its tier and its sources. Where sources disagree, you get both accounts and what would settle it.
mini-Lean-agent is a coding-agent baseline for Lean.
Offline Q-learning with KL regularization is investigated for finite-horizon Markov decision processes.
Reinforcement learning with verifiable rewards relies on costly model-generated responses.
Larger rollout batches learn slower but fail on schedule in reinforcement learning with verifiable rewards.
LLM-based automated heuristic design discovers heuristics for combinatorial optimization problems.
General-purpose coding agents use standard shell and file interactions.
Modern LLM agents still reason and interact through text.
The case against this story
Written by an adversarial reviewer, not the correspondent
The story stitches together a fragmented set of claims that individually range from trivially true ('general-purpose coding agents use standard shell and file interactions,' 'modern LLM agents still reason and interact through text') to niche and overstated (mini-Lean-agent elevated to baseline status, a single investigation of offline Q-learning treated as established). The RLVR claims are particularly weak: one states a near-tautology (model-generated responses are costly), while another presents a confusing and possibly self-contradictory empirical result about batch sizes. Taken together, the picture implies more coherence and maturity across RL, LLM agents, and automated heuristic design than the underlying evidence supports. A reader would come away thinking these are settled findings in a unified research program, when several are either obvious background facts, single-study observations, or definitional conventions for narrow tools.
Who benefits from this framing: Researchers who have built specific niche tools (such as mini-Lean-agent) benefit from having their artifacts framed as field-standard baselines. Proponents of RLVR benefit from having its costs and failure modes presented as moderate-confidence findings rather than open questions. And anyone advocating for the maturity of LLM-agent ecosystems benefits from the implication that standard shell-and-file interactions and text-based reasoning are settled architectural facts rather than contingent, possibly transient design choices.
Report an error in this article
Subscriptions open at launch
Future Systems Review will be a paid publication. Reading is free while we build the archive — leave an address and we will write to you once, when subscriptions open.