Choosing beam directions is one of the slowest steps in radiotherapy planning. A planner, human or algorithm, decides from which angles around the patient radiation should enter, and in "4π" non-coplanar planning there are 500 to 800 collision-free candidate directions. The fastest published method treats beam selection as one convex optimization. A penalty pushes whole beams to zero, and the solver periodically throws away beams whose intensity has become negligible. That deletion rule gives a 4–5× speedup and an average of 4.1 minutes per case (4pi Non-Coplanar IMRT Beam Angle Selection by Convex Optimization with Group Sparsity Penalty). That is still above the roughly 3-minute budget that online adaptive radiotherapy needs while the patient lies on the couch (Auto-Segmentation and Auto-Planning in Automated Radiotherapy for Prostate Cancer). The deletion rule also has two weaknesses. It is reactive: a beam is only dropped after dozens of full-size gradient steps. It is also unguaranteed: a dropped beam might have been part of the optimum.
We propose to replace threshold deletion with certified beam elimination. This is a cheap test, run inside the solver, that proves a beam must have zero intensity at the optimum of the convex problem. The test is paired with an explicit model of what each test costs, so it runs only when it pays for itself. The idea is borrowed from the combinatorial-search literature on dominance pruning, which has found repeatedly that the decisive question is how much the pruning check costs relative to what it removes, not whether pruning is possible. We carry that lesson into dose optimization, where the "states" are candidate beams and the expensive objects are gigabyte-scale matrices that map beam intensities to dose.
Core Claim
For the beam-selection problem that uses a group-sparsity penalty (a penalty on the length of each beam's intensity vector, which drives whole beams to zero), each candidate beam can be eliminated with a guarantee once a bound shows it cannot be active at the optimum. The bound needs only quantities the solver already computes, plus one cached number per beam. Write the problem as
$$\min_x \; f(x) + \lambda \sum_b w_b \lVert x_b \rVert_2,$$
where $x_b$ is the vector of beamlet intensities of candidate beam $b$, $f(x) = \tfrac12\lVert W(Ax - d)\rVert^2$ is a weighted quadratic dose-fidelity term with dose-influence matrix $A$ (blocks $A_b$), prescription $d$ and voxel weights $W$, $\lambda$ is the sparsity strength, and $w_b$ are per-beam weights. Standard duality arguments for this objective give a test of the form
$$\lVert A_b^\top W^\top r \rVert_2 + \lVert W A_b \rVert \, \rho(G) < \lambda w_b \;\Rightarrow\; x_b^\star = 0.$$
Here $r$ is the current weighted residual, which the solver already holds. $G$ is the current duality gap, the gap between the solver's objective and a lower bound on the optimum. $\rho(G)$ is a radius that shrinks as $G$ shrinks, so certification gets easier as the solver converges. $\lVert W A_b \rVert$ is a per-beam matrix norm computed once and cached. The first term is the per-beam gradient the solver computes anyway.
The guarantee holds for the convex surrogate, not for the original combinatorial choice of exactly $k$ beams. We claim exactly what the surrogate method of 4pi Non-Coplanar IMRT Beam Angle Selection by Convex Optimization with Group Sparsity Penalty can support: the same answer, reached faster. Clinical objectives with hard maximum-dose terms are not quadratic. For those we either keep the guarantee for the quadratic stage only, or derive the radius from a smooth surrogate and report that the guarantee is then approximate.
The claim to test is twofold. First, certified elimination combined with a cost-aware schedule brings 4π beam selection under 3 minutes on large head-and-neck and lung cases. Second, it reaches the same solution as the unpruned solver, while threshold deletion sometimes does not.
How the Pruning Literature Shapes the Design
The combinatorial work does three different jobs here. Chu and Stuckey's Dominance breaking constraints post constraints that exclude assignments provably dominated by a better one, and they show orders-of-magnitude gains: Knapsack-100 goes from a 900-second timeout to 0.40 seconds. They also warn that propagating intricate dominance conditions can cost more than the search they save. Fukunaga and Korf's Bin-Completion Algorithms show the same trap in another form, where the per-node cost of checking against an expanding history grows with depth. On the Complexity of BDDs for State Space Search shows that naive pruning can even increase memory. These papers constrain the design. Our check must cost a small, fixed amount per beam and must never compare against a growing history.
Transition Dominance in Domain-Independent Dynamic Programming supplies the method. It discards a move by checking a local condition rather than storing and comparing whole states, and it makes that affordable by caching shared intermediate expressions in "state functions." That combination yields 5–10× speedups across seven domains. The same paper notes that caching simple expressions can cost more than recomputing them. Our per-beam cached norms play the role of state functions, and we test that caching-versus-recomputation tradeoff directly. For example, a cheap but loose Frobenius-norm bound can be compared against a tighter spectral norm that needs a few power-iteration steps per beam.
Our test differs from transition dominance in one important way. It certifies a beam against the optimum itself, not against a competing beam. Pairwise geometric dominance, such as "beam $i$ sees the target with less organ in its path than beam $j$", is not admissible for fluence optimization, because beams act in combination.
The radiotherapy papers mainly motivate the work. Pattern mining-based evolutionary multi-objective algorithm for beam angle optimization prunes beam sets by mining frequent angles from Pareto-optimal solutions. It is a heuristic with no protection against removing the optimum, it is limited to coplanar geometry, and it names full dose re-evaluation as the unresolved cost. The 4π method's other weakness is uniform downsampling of large structures to fit in 8–9.5 GB. This motivates the second part of our design: eliminate beams before full-resolution matrices are ever stored.
Research Program
We will build the elimination test into an accelerated proximal-gradient solver (FISTA, the same solver class as the 4π paper). The test runs on a schedule chosen online by a simple cost model. Each test costs the time to compute the gap and the cached-norm products. It saves the expected number of eliminated beams times their per-iteration matrix cost, estimated from how many beams the last test removed and how fast the gap is falling. A test runs only when the predicted saving exceeds its cost. This is the pruning-overhead tradeoff made explicit and measurable.
The second component is a coarse-to-fine pass. Each beam's full-resolution matrix block is streamed once, in a single pass that never holds all blocks in memory at the same time. During that pass we record the beam's norm and a measured bound on its downsampling error. Screening then runs on the coarse problem, with the radius inflated by that error bound so the certificate stays valid. Full-resolution blocks are stored only for beams that survive, which should remove the need for uniform downsampling in the final optimization.
The third component applies the method to adaptive replanning. Warm-starting from a previous fraction's solution should make $G$ small immediately, so most beams are certified out in the first few iterations. We will test this on synthetically deformed anatomy and label it as simulation.
Baselines
The naive reference is the same FISTA solver run to convergence with no pruning on the same cases and hardware. It defines the target solution, the unpruned optimum, and the runtime to beat. It also shows how much of any speedup comes from pruning rather than from implementation.
The strongest existing method is threshold deletion as in 4pi Non-Coplanar IMRT Beam Angle Selection by Convex Optimization with Group Sparsity Penalty. That paper drops beams below $10^{-6}$ intensity every 40 iterations and reports a 4.1-minute average (range 2.8–6.2 minutes) for selecting 20 beams from 500–800 candidates, with a 4–5× speedup over no pruning. We will reimplement it in our solver with the same objective, candidate sets, $\lambda$, GPU and stopping tolerance. We will also tune its threshold and interval over the same grid budget we give our scheduler, so it is not handicapped by the defaults. Our method beats it if two things hold together. Median wall-clock time to a fixed duality gap must be lower, with head-and-neck cases under 3 minutes. And our final beam set and objective must match the unpruned optimum, while measuring how often threshold deletion fails to match it.
A heuristic prefilter baseline keeps the top-$k$ beams by line-of-sight score between target and organs, in the spirit of the initialization in PM-EMA, and then optimizes over that subset. Two ablations isolate our ingredients. In the first, certified tests run on a fixed schedule rather than the cost-aware one, which separates "certification" from "knowing when to certify." In the second, norms are recomputed rather than cached, and Frobenius bounds are compared with spectral bounds, which isolates the state-function caching tradeoff.
Why not just…?
Why not just predict the plan with a neural network in under a second? Physics-Guided Radiotherapy Treatment Planning with Deep Learning predicts machine parameters in under one second. It does so for a fixed two-arc protocol on 133 prostate patients and does not select beam directions at all, so there is no reported result on Lacuna for neural 4π beam selection to compare against. OpenKBP-Opt also found that raw predictions met 66.2% of clinical criteria against 77.0% after an optimization stage. The two approaches are complementary: a network's suggested beams can serve as a warm start, and our certificates then say which remaining candidates are safe to discard. We will test that combination rather than argue against it.
Why not just prune more aggressively with a larger threshold, or prefilter by geometry? This is the real threat. If a tuned threshold or a top-$k$ geometric prefilter matches our runtime and almost always reproduces the unpruned beam set, the guarantee has little practical value. The tuned-threshold and prefilter baselines above settle this directly. We report runtime alongside the rate of beam-set mismatch and the dose-quality loss when mismatches occur. If mismatches are negligible, we will say so and fall back to the narrower contribution of coarse-to-fine memory reduction.
Doesn't the certification overhead eat the savings? It might, exactly as the dominance-breaking and bin-completion papers warn. That is why the test reuses the gradient the solver already computes and only adds cached scalars and one gap evaluation. We report the fraction of total time spent in checks, and the fixed-schedule ablation shows whether the cost model is necessary.
Proposed Experiments
The four 4π cases from the threshold-pruning paper are not public. We will therefore regenerate candidate sets of comparable size, about 500–800 beams after collision filtering, on public anatomy. We use head-and-neck patients from OpenKBP (340 patients) and head-and-neck and lung patients from the HMM-RT dataset released with Automating High Quality RT Planning at Scale (3,730 plans, 1,622 patients). Dose-influence matrices come from a pencil-beam engine.
Per case we measure wall-clock time to a fixed gap, peak memory, the fraction of beams eliminated over time, the fraction of time spent on checks, the objective gap to the unpruned optimum, and agreement of the final beam set with it. We also evaluate clinical criteria satisfaction after fluence optimization, using OpenKBP-Opt-style criteria so results are comparable to its 77.0% best pipeline.
The decisive checks are three. The first is whether we beat tuned threshold deletion on time while it, and not we, shows beam-set mismatches. The second is whether the coarse-to-fine pass lets large structures stay at full resolution within the memory envelope the 4π paper needed downsampling to reach, and whether that measurably changes organ-boundary dose. The third is whether warm-started replanning on deformed anatomy finishes well inside 3 minutes. A negative result on the first check, with our method no faster than a well-tuned threshold, would itself be informative: it would mean the convex surrogate is already easy enough that guarantees, not speed, are the only thing certification buys.
References
- TH‐EF‐BRB‐05: 4pi Non‐Coplanar IMRT Beam Angle Selection by Convex Optimization with Group Sparsity Penalty
- Auto-Segmentation and Auto-Planning in Automated Radiotherapy for Prostate Cancer
- Dominance breaking constraints
- Bin-Completion Algorithms for Multicontainer Packing and Covering Problems
- On the Complexity of BDDs for State Space Search: A Case Study in Connect Four
- Transition Dominance in Domain-Independent Dynamic Programming
- Pattern mining-based evolutionary multi-objective algorithm for beam angle optimization in intensity-modulated radiotherapy
- Physics-Guided Radiotherapy Treatment Planning with Deep Learning
- OpenKBP-Opt: an international and reproducible evaluation of 76 knowledge-based planning pipelines
- OpenKBP: The open-access knowledge-based planning grand challenge
- Automating High Quality RT Planning at Scale