BEACON: Milestone-Guided Long-Horizon Agents

Long-horizon agents — the ones that run for dozens of steps before anything is verifiably finished — fail in a way short-horizon agents don't. Performance doesn't degrade gently as tasks get longer. It falls off a cliff.

A recent paper from Zhejiang University's ZJU-REAL lab, Milestone-Guided Policy Learning for Long-Horizon Language Agents, diagnoses that cliff precisely enough to be useful even if you never train a policy yourself. The method is called BEACON; the code is open source.

We read it closely because the problem it describes is the same one we keep running into on the product side. What follows is the paper's argument, one place where we had to work through the math to reconcile a result, and what we think transfers to agent architecture.

Two failure modes, both measurable

What we appreciate most is that the paper doesn't open with a method. It opens with an autopsy: Qwen2.5-1.5B trained with GRPO on ALFWorld, with the collapse broken into two quantified causes.

Credit misattribution

Trajectory-level RL treats a run as a flat action sequence. Every action shares one terminal score. So the same correct action earns a positive gradient in a successful run and a negative one in a failed run — whether it was "right" depends on what happened afterwards.

The authors quantify this as the Contradictory Action Ratio: the fraction of actions receiving opposite-sign advantages across trajectories despite being executed at identical states. It peaks above 40%. After those gradients cancel, effective learning signal drops below 20%.

Sample inefficiency

Bucket the trajectories three ways — full success, partial success (at least one subgoal completed, task still failed), and total failure:

• Partial successes hold steady at 39–47% of samples throughout training.
• Full successes stay below 27%.

Under GRPO a partial success and a total failure both score zero. Over 73% of samples produce no learning signal at all.

Both problems compound as horizons grow: longer tasks succeed less often (more partial successes) and give downstream randomness more chances to corrupt credit. Concretely, on ALFWorld: 76.7% on short tasks, 53.5% on long ones.

The insight: long tasks already have structure

Long-horizon tasks decompose into phases bounded by milestones — verifiable state transitions that mark subgoal completion. Flat optimization simply discards that structure.

The authors formalize it as the Milestone Markov Property: once you reach a milestone state, the distribution over the rest of the trajectory depends mostly on which subgoals remain, not on the full history of how you got there.

Once you have the key, what happens next depends on what you do with it — not on how you found it.

That approximate Markov property is what makes credit decoupleable across segments.

The method, in three steps

1. Partition at milestones

A detector Φ flags milestone timesteps and cuts the trajectory into segments. The design decision we think is underrated: Φ needs no learned model and no human annotation. It reads observable state changes straight from environment feedback — object state transitions in ALFWorld, page transitions in WebShop, explicit subgoal signals in ScienceWorld.

Zero extra models, zero extra rollouts. That is the entire cost advantage over process reward models and Monte Carlo value estimation.

2. Temporal reward shaping inside each segment

r_t = R_ms * γ^(t_k − t)   if segment k ends in a completed milestone
    = 0                    otherwise

Only segments that terminate in a milestone earn reward, and within such a segment actions closer to the milestone earn more. Every action in a completed segment now carries signal, so partial successes stop being discarded.

3. Dual-scale advantage

The trajectory level is standard GRPO normalization over terminal rewards. The segment level is where the idea lives — in how the comparison group is defined:

G_k = { i : K_i ≥ k }          # only trajectories that ALSO reached milestone k

A_seg(i,t) = r_t − (1/|G_k|) · Σ_{j∈G_k}  R_k(j) / |Seg_k(j)|
                               └── group-average PER-STEP return ──┘

Actions in segment k are compared only against trajectories that also reached milestone k. From this the authors derive a variance isolation property: whether later segments succeed or fail cannot mathematically contaminate credit for the current one.

The final advantage is A_traj + λ · A_seg, optimized with a standard PPO clipped surrogate. Hyperparameters γ=0.95, λ=1.0 are fixed across every benchmark — no per-task tuning.

Results

ALFWorld, Qwen2.5-1.5B:

Success rate on the other two environments:

The 1.5B model outscores GPT-4o on ALFWorld (91.4 vs 48.0) and WebShop (75.6 vs 23.7), and ties it on ScienceWorld (45.3 vs 45.4). Fair caveat: the closed models are prompted with ReAct, not trained. Sample utilization rises from 23.7% to 82.0%, and convergence is faster — 60% success by iteration 50, where GRPO needs iteration 120.

The most convincing result is that the gains scale with horizon. On 7B, relative improvement over GRPO goes from +13% on short tasks to +39% on long ones; GiGPO only goes from +11% to +22%. The reason matters: GiGPO builds step-level comparison groups from repeated states, and as a policy improves and its trajectories diversify, state recurrence gets sparser — its own signal source erodes. Milestone anchors don't decay as the policy gets stronger.

A method whose benefit grows as the problem gets harder is a much stronger claim than a higher average score.

The metric that looks like a contradiction

The paper defines a Credit Concentration Ratio — average advantage magnitude for milestone actions divided by that for non-milestone actions. Above 1 means credit concentrates on milestones.

So the best-performing method is the one that concentrates credit on key steps the least — which reads as a direct contradiction of "actions closer to the milestone get more reward." It isn't. The two statements measure different quantities, with two transformations in between.

Transformation 1 — shaped reward. Within a segment, reward does increase monotonically toward the milestone. With γ=0.95 and a segment of length 5, the five actions get 0.8145, 0.857, 0.9025, 0.95, 1.0. But this is reward, not the credit that reaches the gradient.

Transformation 2 — subtract the group baseline. The baseline is the group-average per-step return (segment return ÷ segment length). For a segment of length L, per-step return is (1−γ^L) / (L(1−γ)):

If your segment took 8 steps while the group averaged 5, your per-step return sits below the baseline and the entire segment's advantage skews negative. Note what this means: the penalty for wandering doesn't come from the decay itself — it comes from the decay acting through the per-step baseline. Decay alone only orders actions within a segment. At this point CCR inside a completed segment is still greater than 1.

Transformation 3 — add the trajectory-level term. This is where CCR drops below 1, through two asymmetric effects. First, the tail segment of a failed trajectory enters no comparison group at all: since G_k = {i : K_i ≥ k} and the incomplete tail has index K_i + 1 > K_i, that trajectory is excluded. The tail receives no segment-level advantage, only the trajectory-level term at full magnitude — and every one of those is a non-milestone action, inflating the denominator. Second, in failed trajectories the negative trajectory-level term cancels against the positive segment-level credit on milestone actions, squeezing their magnitude toward zero.

The paper's own Figure 8 confirms it. On a failed trajectory that completed milestones S3 and S4:

The last two values are identical — the fingerprint of "tail segment gets only the trajectory-level term," which lets you read off A_traj ≈ −2.20. The two milestone actions are positive but only ~0.5 in magnitude, because the negative trajectory term ate most of the segment-level credit. CCR for this trajectory is 0.23; for a successful trajectory it is 2.95. The global 0.84 is the mixture.

So CCR measures the concentration of gradient magnitude, not who got rewarded. Low CCR isn't a design goal — it's a byproduct of dense in-segment allocation plus dual-scale stacking. The authors' conclusion still holds, and it's a good one: don't dump all your gradient energy on the key steps. GiGPO's 2.36 means the preparatory actions in between get almost no signal, and those are exactly what makes reaching a milestone possible.

Something the paper doesn't spell out

There's an odd cell in the ablation table. Setting γ=1 — uniform credit inside each segment — scores 71.8, worse than no shaping at all (γ=0, 81.2) and even below GRPO's 72.8. The paper attributes this to "misleading gradients."

Work through the math and the answer is sharper. With γ=1 every action in a completed segment gets the same reward, so every completed segment — regardless of length — has a per-step return of exactly R_ms. The baseline equals it, and:

A_seg(i,t) ≡ R_ms − R_ms = 0    for every action

The segment-level channel doesn't mislead. It vanishes identically, and the method reduces exactly to GRPO. Check it against the table: 71.8 versus GRPO's 72.8 — one point apart, which is run-to-run noise.

Which reframes what the decay is for. It isn't only about differentiating actions within a segment; it is a necessary condition for the segment-level signal to exist at all. Without it, the per-step baseline cancels the signal on the spot.

Three experiments that close the obvious objections

Credit where due — the authors pre-empt the three questions a skeptical reader asks:

• Is this just behavior cloning? SFT on oracle trajectories reaches 43%; BEACON reaches 91.4%. The policy finds execution strategies better than the oracle, so it isn't imitating.
• Do the gains come merely from chunking? Random partitioning scores 74.2%, just 1.4 points above GRPO. Real milestones score 91.4% — a 17.2-point gap. The benefit comes from task-intrinsic structure.
• What if the detector is unreliable? Dropping 50% of milestones at random still yields 82.8%, ten points above GRPO. Degradation is graceful.

What transfers to agent design

BEACON is a training method, and most products — ours included — orchestrate models rather than train them. The formulas don't transfer. The diagnosis does, and it maps onto architecture surprisingly directly.

Partial progress has to be a first-class, persisted state. The paper's sharpest number is that 39–47% of runs complete real subgoals and are then scored identically to runs that did nothing. A long-running agent session that completes three subgoals and then stalls has the same problem: if the system records only "running" and "done," that progress is thrown away and the retry starts from zero. Milestones give you the vocabulary to record it.

Milestones should come from observable side effects, not self-report. The reason Φ is cheap is that it reads verifiable state transitions rather than asking the policy whether it made progress. Agent runtimes have the same asset available and often ignore it: a file written, a test that exited zero, a connector call that returned success, a document committed to the knowledge base. Those are ground truth. A model asserting "step one complete" is not.

Milestone boundaries are principled compaction and resume points. The Milestone Markov Property says that once a milestone is reached, what came before matters much less. That is a far better justification for compacting context than "we hit a token threshold," and the same boundary is the natural checkpoint to resume from after a failure.

Verify at two scales, not one. This is the ablation we'd underline for anyone building agent workflows: removing the trajectory-level signal drops ALFWorld from 91.4% to 23.4%. With only segment-level feedback, the policy reinforces behavior that hits intermediate milestones while drifting off the actual goal — every subtask executed beautifully, the deliverable wrong. Sub-task acceptance and final-deliverable acceptance are not substitutes. Notably, the necessary weight differs by task: WebShop still manages 67.9% without the trajectory level because its milestones align closely with final success; ALFWorld collapses.

Limitations, stated honestly

The biggest constraint is whether Φ is obtainable at all. All three benchmarks derive milestones from rules — pattern matching on environment responses, page transitions, explicit subgoal signals. Open-ended settings such as browser automation, codebase refactoring, and deep research have no such ready-made verifiable transitions, and the authors list automated milestone discovery as an open problem. This reads as a paradigm validated in structured environments, not an engineering recipe to lift as-is.

Milestone granularity is also sensitive: too sparse and the method degenerates toward GRPO, too dense and segment advantages get noisy. The Markov property is only approximate, and variance isolation rests on it. Experiments stop at 7B with discrete text action spaces — continuous control and multi-agent settings are untested.

Still, the core claim is one we find hard to argue with: long tasks have exploitable compositional structure, and treating that structure as a first-class object beats hoping a model tracks it in context. We're applying that thinking to long-horizon task support in Orkas, and we'll share more of the design as it lands.