QUBO Selection Across a Search Frontier

The playback follows a bounded search through a synthetic tree. At each depth the retained beam is expanded, and one QUBO selects the next beam from the complete candidate frontier. Blue items are retained, grey items are pruned, and a gold outline marks the oracle path known only to the benchmark.

One selection over the expanded frontier

For candidate \(i\), let \(x_i\) indicate retention, \(u_i\) its normalized utility and \(s_{ij}\) its similarity to candidate \(j\). A target batch size \(k\) gives the objective

\[E(x)=-\lambda_u\sum_i u_i x_i +\lambda_s\sum_{i<j}s_{ij}x_ix_j +\lambda_k\left(\sum_i x_i-k\right)^2.\]

The first term rewards utility, the second charges redundancy and the last penalizes deviation from the requested count. The built-in classical heuristic stays in the exact-cardinality feasible set, starts greedily and improves the selection with deterministic one-for-one swaps. It is not an exact optimizer or a quantum solver.

The optimization is constructed once over all children of the current beam. It is not solved separately inside every branch. The displayed utility vector and similarity matrix are the actual selector inputs for this explanatory seed.

Where expensive work occurs

Selection can save expensive rollout or terminal evaluations only when those operations occur after pruning. Computing a full expensive rollout for every candidate to obtain its utility would already incur the cost the selector is supposed to avoid.

A practical integration therefore needs a cheap, available estimate: for example a policy/value estimate, a bound, disagreement score or shallow rollout. The controlled study uses an oracle-derived noisy proxy to isolate pruning behavior; that proxy is benchmark instrumentation, not a production-available predictor.

Paired benchmark and cost

The repository’s 500-tree comparison uses four-way trees of depth six. Each tree has 4,096 terminal paths and 5,460 non-root candidates. Search sees a noisy value proxy with errors correlated within the first branch.

At width eight the paired mean-regret improvement is 0.0130 in QUBO’s favour, with a normal 95% interval from 0.0022 to 0.0239. Exact recovery improves by one percentage point.

QUBO at width eight is close to utility selection at width ten, using two fewer terminal evaluations at about 2.75 ms extra selector time. The recorded terminal-only break-even is therefore about 1.38 ms per avoided evaluation. This comparison depends on the measured selector cost and the synthetic proxy; it does not establish a general speed advantage.

Reproduce the comparison and playback

PYTHONPATH=src python examples/benchmark_qubo_branch_search.py \
  --trials 500 --widths 4,6,8,10,12,16 --seed 20260802 \
  --json-output docs/latex/figures/qubo_frontier_efficiency.json \
  --plot-output docs/latex/figures/qubo_frontier_efficiency.pdf

PYTHONPATH=src python examples/visualize_qubo_frontier.py \
  --json-output docs/latex/figures/qubo_frontier_trace.json \
  --plot-output docs/latex/figures/qubo_frontier_trace.pdf \
  --gif-output docs/markup/qubo-frontier.gif

The animation is one illustrative trace. The paired aggregate result supplies the evidence. A Volt application would still need the same accounting on immutable scenario cohorts with a production-available utility estimate.

Source and related material

• QUBO formulation, branch study and limitations.
• Recorded benchmark aggregates.
• Frontier playback source.
• Jörmungandr architecture.