One Global Beam Across Many GPUs: High-Throughput Beam Search at Billion-Record Frontier Scale

One Global Beam Across Many GPUs: High-Throughput Beam Search at Billion-Record Frontier Scale Ivan Litvak Independent Researcher

arXiv:2610.06718v1 [cs.DC] 5 Oct 2026

Abstract

parents P1

Beam search repeatedly makes many children, removes duplicates, and keeps the best B. We show how many GPUs can perform these steps as one search even when the retained set does not fit on one device. States and candidates stay on the GPUs; the CPU receives only small control and ancestry records. We prove that an abstract distributed pipeline returns the monolithic reduced-key top-B for the same complete candidates, integer scores, Hash128 equivalence, and a fully specified physical-layout tie order, provided that its implementation performs one global reduction per key and race-free routing. A static audit of the historical one-T4 pin leaves cross-buffer uniqueness unresolved and identifies a separate multi-rank scatter risk; neither is a reproduced failure, and other revisions inherit neither defects nor correctness without comparison. On eight H200 GPUs, a Cube4 run completed saturated depth 8 at Beff = 2,900,361,216 in 931.266 s: 69,608,669,184 nominal parent–generator pairs, or a derived 74.746 million pairs/s. The puzzle remained unsolved and depth 9 was stopped at user request. A separate two-T4 Megaminx run measured 30.274 million logical children/s at Beff = 82,837,504. Those tasks and hardware differ, so they do not establish strong scaling. Separately, on one eight-RTX-3060 host, fixed-count eight-GPU speedup was 7.487 under a common execution profile and 5.605 under selected stable profiles; weak actual-work throughput gain was 6.113 and 7.295. These profile-sensitive ratios use each series’ own one-GPU baseline.

1

generate and score A

B

B

C

s=1

s=4

s=2

s=3

one record per key A

B

C

best s = 1 best s = 2 best s = 3

next frontier A

B

s=1

s=2

Figure 1: Beam search in one picture. Each parent produces children; records with the same identity key retain their best score; the best B distinct-key records become the next frontier. Smaller scores are better in this paper.

local quotas: a different algorithm GPU 0 candidates A:1, B:2 local top-1: A

Introduction and Problem

GPU 1 candidates C:3, D:4 local top-1: C

one global beam

Beam search is easy to describe. Start with a set of states. Make their children, score them, remove repeated states, and retain the best B: parents → children → one per key → best B

P2

GPU 0 shard A:1, B:2

GPU 1 shard C:3, D:4

(1) global top-2 keeps {A, B}

Figure 1 makes the key-reduction step explicit before the global cut. The retained set is the frontier. If it outgrows one GPU, simply giving each GPU an independent beam changes the algorithm. Our goal is different: split one frontier across GPUs while preserving the result of one monolithic beam. Figure 2 shows why independent local quotas do not implement that objective.

Figure 2: Why sharding is not the same as running independent beams. With local quotas, a GPU can discard a state that belongs to the global top-B. This work applies one global cut across all shards.

1

Formally, states are vertices of an implicit graph G = (V, E). Applying move a ∈ {1, . . . , m} to state x produces Aa (x). A deterministic oracle σ(x, a) scores that choice. It may be learned or hand-engineered; our experiments use neural scorers. The implementation compares only the quantized integer score s(x, a) from Eq. (10). The complete depth transformation is ×m

Reduce

Top

z B Fd−1 −−→ Cd −−−−−→ Ud −−−→ Fd .

hypothetical full-child materialization

69.609 billion nominal pairs × 96-byte full Cube4 child ≈ 6.68 TB

this work: compact candidate path

(2)

hash + score + parent + move + source

Its three stages are defined by Cd = {(x, a, Aa (x)) : x ∈ Fd−1 , a ∈ [m]},

select best B

Ud = Reducez (Cd ; lexmin(s, payload)),

(3)

Fd = TopB (Ud ; s∗d , τL ) ,

(4)

rebuild winners only

Here Cd contains all children, Ud keeps the lowest-score candidate for each Hash128 key z, and Fd contains the best B distinct key records. Specifically, s∗d (z) = min{s(x, a) : z(Aa (x)) = z}, and τL is the deterministic tie order induced by a fully specified physical layout L, including rank, physical buffer, and local slot. Thus de-duplication keeps the best candidate for each key before the global cut. At a saturated depth, the scale follows from one multiplication:

Figure 3: Why the system stores candidate metadata rather than every generated state. The 6.68-TB value is hypothetical full-child materialization before metadata, not measured device allocation. Full children are reconstructed only after the global cut.

2

Nchild = mBeff

The words large search can refer to different quantities:

= 24 × 2,900,361,216 = 69,608,669,184

Related Work and Gap

(5) Blive ̸= Nraw ̸= Ncumulative ̸= Nqueries .

nominal logical pairs.

(7)

The Cube4 representation uses 96 bytes per full child. Here they mean retained frontier, raw candidates in one Hypothetically materializing every child, before metadata, layer, states visited over time, and independent searches. We compare like with like. would require Parallel beam search predates GPUs [2]. DisMhypothetical = 96Nchild tributed/global CPU beams include Wijs–Lisser, a 20= 96 × 69,608,669,184 million shared-memory beam, independent MPI beams, (6) and global or local CPU partitions [21, 8, 13]. = 6,682,432,241,664 bytes Single-GPU systems include a speech beam, GPU ≈ 6.68 decimal TB. A*, Cayley-graph beams, AlphaCube, and DeepCubeA Figure 3 contrasts that hypothetical materialization with [7, 23, 14, 6, 5, 20, 1]. Hash-distributed CPU best-first the compact metadata path used by the system. The search establishes another piece [12]. DA* distributes system therefore never gathers the full candidate layer for A* over multiple GPUs, but does not maintain the layera CPU transfer or a single-GPU sort. synchronous global top-B frontier studied here [9]. During a depth, candidate and frontier arrays remain in QiankunNet-cuSCI is a close adjacent distributed GPU memory. The CPU receives only O(p) control counts pipeline: it performs GPU global de-duplication and reand compact ancestry metadata. Every GPU therefore ports evaluation through 64 GPUs [19]. It is not reported contributes a shard to the same next frontier; the system as beam search. The accessible source used in our audit is not an ensemble of independent searches. did not establish the retained-frontier semantics needed for the conjunction below. Contributions. We distribute one logical beam withOther billion-scale numbers count different objects: out staging its frontier in CPU memory. We state the GPUexplore counts cumulative reachable states [22], Pathimplementation obligations needed to preserve monolithic Weaver serves independent graph queries [11], and multireduced-key top-B semantics for a fixed physical layout and GPU decoders usually distribute utterances, sentences, or identity model, without shard-local semantic caps. We re- model execution rather than one state frontier [10, 3, 4]. port separately an eight-H200 completed Cube4 depth, an Table 2 shows the conjunction examined by the dated older eight-A100 capacity-only record, and two-T4 Megam- audit: one physically sharded beam, GPU-resident candiinx throughput. We also report matched 1/2/4/8-RTX- date/frontier data, global key reduction, no local semantic 3060 scaling under common and selected execution profiles. quota, and fixed-layout global top-B. No earlier system The implementation supports at most 128 ranks; execution with the full conjunction was located in the audited set; beyond eight GPUs remains unmeasured. this is not an exhaustive proof of priority. 2

Table 1: Notation legend. Read this table as the map for the equations below. Symbol

Plain meaning

Symbol

Plain meaning

Symbol

Fd B z(x) Aa (x)

states kept at depth d desired frontier size Hash128 key of state x child after move a

Cd m s(x, a) o(x)

all generated children moves per parent integer score; smaller is better GPU owning state x

Ud p T τL

Plain meaning one best record per key number of GPUs current worst allowed score physical-layout tie order

Table 2: Closest prior systems under a common scale taxonomy. “Other scale” is deliberately not interpreted as retained beam width. System

Platform and search object

Wijs–Lisser 2007

distributed CPU; one global 50,000 beam one 8800 GTX; speech active not reported set tained beam 46 CPU threads; one shared- 20,000,000 memory beam four V100; multi-GPU A* not a beam

Chong et al. 2008 Frohner et al. 2022 DA* 2021 CayleyPy 2025 GPUexplore 3.0 PathWeaver 2025 QiankunNet-cuSCI

This work

3

Retained live beam

as

Other scale

Missing from the claimed conjunction

135.96M cumulative GPU data plane and devicestates resident scorer re- 996,903-state large multi-GPU state frontier model MPI: independent GPU and distributed one-beam beams execution up to 3× versus single- no layer-synchronous global topGPU A* B frontier independent agents multi-GPU global frontier

one GPU; one Cayley-graph 224 beam four V100; exhaustive reach- not a beam > 3.15B states ranked score and top-B able set four A6000; independent not reported exact layered semantics and large 50M-vector dataset ANNS queries retained beam up to 64 GPUs; selected SCI not reported as a beam large distributed selec- retained global-beam semantics configurations tion workload not established in the audited source eight H200; one sharded 2,900,361,216 effective 69.609B nominal raw H200 record: completed depth 8; global beam records pairs/depth full solve, implementation exactness, and H200 fixed-workload scaling unestablished; separate RTX 3060 scaling below

One Search Depth on Five GPU Table 3: Compact candidate fields. Full state bytes are Streams absent. Field

Meaning

Used for

One depth transforms the old frontier into the new frontier. z(y) Hash128 key key reduction, owner s(x, a) integer score ranking, threshold Figure 4 first separates the GPU-resident data path from iparent parent index reconstruction the compact CPU control path: a applied move reconstruction rsrc source GPU fetch and ancestry The input Fd−1 is split over p GPUs. GPU r owns Nr parents and logically generates mNr children. For y = Aa (x), it stores a compact candidate rather than the Streams 1–2: score and identity. Parents are difull child: vided into microbatches and placed in reusable ring slots. c = (z(y), s(x, a), iparent , a, rsrc ), (8) Streams 1 and 2 consume the same slot concurrently. Stream 1 evaluates the chosen scoring oracle and writes where z(y) ∈ {0, 1}128 is the child-state Hash128 key, only s(x, a) is a quantized candidate score, and rsrc identifies s(x, a) = rintRN−even (S clip(σ(x, a), 0, qmax )) ∈ N, (10) the GPU that stores the parent. The child state itself is reconstructed only for goal checking or after the final not the floating-point output. Here RN-even is the GPU selection. We write path’s default round-to-nearest, ties-to-even mode. The x ≡z y ⇐⇒ z(x) = z(y). (9) scalar path evaluates child states, whereas the output-m All reductions and exactness statements below operate on path obtains all m action scores from each parent. Stream 2 these Hash128 key-equivalence classes. They also describe applies every move in registers, checks the goal, and writes full-state equality only if no distinct relevant states collide the 128-bit Zobrist hash. Thus score evaluation and state manipulation overlap without storing the mNr child states. under z. Figure 5 then shows how readiness, rather than a fixed serial phase order, permits overlap among the five streams. Stream 3: early reduction and ownership. When a group of ring slots has both scores and hashes, Stream 3 3

GPU-resident hot-data path frontier shards

S1: score S2: hash

compact candidates

S3: local reduce and owner

S5: NCCL exchange

S4: global reduce and threshold

CPU: counts and compact ancestry metadata only

No full candidate layer or full frontier is staged through CPU memory.

Figure 4: One search depth. Streams overlap in time; arrows show data dependencies, not five serial phases. Table 4: The five streams at a glance. “Resident” means that the large data remain in GPU memory. Stream 1 2 3 5 4

Reads

Main operation

Writes

Why it exists

parent microbatch same parents scores and keys remote owner buckets owned candidates

neural or heuristic scoring apply moves, goal test, hash threshold, compact, local reduce NCCL GPU-to-GPU exchange persistent reduce and histogram

integer scores 128-bit keys owner buckets received candidates survivor shards

rank candidates assign key classes cut work before exchange unite equal-key records maintain the global cut

removes scores above the current threshold T , compacts the survivors, sorts them by z, and reduces equal hashes. For each hash it retains the lexicographically smallest pair (s, payload), where the payload recovers the original parent and move. It then assigns each locally reduced candidate to o(x) = mix(z(x)) mod p. (11)

while Stream 4 cleans the other. A Stream 4 job merges the clean and newly appended regions, applies its snapshot of T , compacts, sorts by z, and retains the best metadata for each hash. There is no per-shard top-k and no semantic shard quota: a shard may retain every candidate below T . Consequently sharding does not approximate the score cut; only the equal-score boundary order is defined by the fixed layout.

Local candidates enter the local collector; the rest are grouped by owner. Performing this first reduction before communication lowers traffic, but does not replace the 3.1 Work, Memory, and Frontier Scaling later global deduplication. Let a denote the branching factor (the earlier move count m), G the number of ranks, Bd = |Fd | ≤ B, and Stream 5: GPU-to-GPU exchange. Stream 5 exNd = aBd−1 ; N = aB at saturation. (14) changes the owner-grouped metadata directly between GPUs using NCCL. The owner rule implies Let ℓ be the logical state length, sstate the bytes per stored z(x) = z(y) =⇒ o(x) = o(y), (12) state, and mmeta the bytes per candidate metadata record. These names avoid conflict with the score-quantization so, under complete and race-free routing, equal-key can- scale S in Eq. (10). Let fchild be the cost of one scalar didates produced by different source GPUs meet at one child score and fparent (a) the cost of one parent inference owner. Stream 5 performs communication only; received returning a action scores. Aggregate generation and idencandidates re-enter the same collector as local candidates. tity work is Θ(Nd ℓ), while scoring work is ( The owner sets form a disjoint partition of the global Θ(Nd fchild ), scalar child scorer, reduced key set: Wscore = Θ(Bd−1 fparent (a) + Nd ), output-a scorer. p−1 ] (15) U (r) = {z ∈ U : o(z) = r}, U= U (r) . (13) The second line includes writing and quantizing the a r=0 outputs; it is not a independent neural-network calls per Figure 6 illustrates the required meeting point for equal- parent. For orientation, a sort-based abstract reference that key records produced on different source GPUs. comparison-sorts all implicit candidates has Stream 4: persistent survivor set. The collector Wref = O(Nd ℓ + Wscore + Nd log Nd ), partitions owned candidates into logical shards. Each Mref = O(Bd−1 sstate + Nd mmeta ). (16) shard has two resident buffers: Stream 3 appends to one 4

S1 score

microbatch A

microbatch B

microbatch C

S2 hash

microbatch A

microbatch B

microbatch C

S3 local reduce

reduce A

S5 exchange S4 shard clean

clean buffer B

reduce B

reduce C

send A

send B

send C

clean buffer A

clean buffer B time

Figure 5: Readiness-driven overlap. Streams 1–2 process the same ring slot in parallel; Streams 3 and 5 handle completed microbatches while Stream 4 cleans the alternate shard buffer. The drawing shows dependencies, not measured durations. source GPU 0

z = 7A

source GPU 1

z = 31

owner GPU 0 key 31

o(z) = mix(z) mod p owner GPU 1 both records with key 7A

source GPU 2

z = 7A equal-key records meet before final selection

Figure 6: Required owner routing in the abstract algorithm. Equal 128-bit keys choose the same destination; a conforming owner reduction then keeps one representative per key. Local reduction cuts traffic. This establishes neither unconditional full-state equality nor compliance of the audited CUDA revision. This is one exact-beam implementation, not an intrinsic lower bound and not a bound claimed for a historical dispatcher. Hash tables, deterministic selection, or fixedscore histograms have different work bounds. Streaming avoids Θ(Nd sstate ) full-child storage, but all Nd metadata records may survive the threshold; therefore it does not imply worst-case O(B) metadata independent of a. Figure 7 is a diagnostic checklist for interpreting these counts. Its boxes are possible limiting resources, not measured shares of runtime or a predicted crossover GPU count. The read-only audit of current dirty HEAD 81ed9f0287c1f9057648119a253f208c31f7a872 finds full-capacity CUB comparison sorts rather than a linear Hash128 radix reduction. With Q the Stream 3 chunk capacity, qr useful chunks on rank r, and U3 ≤ Nd locally reduced survivors across chunks, its accounted work is ! X W3 = O qr Q log Q + Nd + GU3 , (17)

What can stop more GPUs from helping? Scoring work scorer throughput diagnostic: scorer time

Sort and reduction capacity sorts; repeated jobs diagnostic: |J4 |, Ck

Owner exchange traffic and skew diagnostic: remote bytes; maxr |U (r) |

Live memory phase peak; history/drain diagnostic: peak bytes; tservice , tfinal

Figure 7: Conceptual diagnostic map, not a measured timeline or an established GPU-count crossover. The boxes are independent checks: overlap requires resource independence, per-rank division requires balance, and a boundedpass count for Stream 4 jobs is not established by the present audit.

No bounded-pass or amortized charging argument for the job count is established; hence Eq. (18) is not simplified plus padded and service rounds. The GU3 term is from to O(Nd ) or O(Nd log Nd ). These current-code formulas per-peer owner scans. For Stream 4 jobs k with sorted do not transfer correctness or complexity to historical pin capacity Ck and H score bins, a1db0e6d9bb5458c8a842b37dfa99572d3025667 or to the ! H200, two-T4, or RTX 3060 measured working snapshots X X W4 = O Ck log Ck + (Ck + H) . (18) without per-file comparison. Appendix A records the remaining implementation-specific terms. k∈J4 k∈J4 r

5

snapshot. The safety premise is witness-based: each entry Table 5: Scaling with frontier width. The right column (z, q) ∈ Wj represents a different key and has an observed requires balanced parents, owners, admitted work, and integer score q ≥ s∗ (z). Entries may be omitted, and a adequate capacity; it is not guaranteed. stored score may be stale and higher than its eventual Quantity Aggregate or Balanced condiminimum; either case can only loosen the cut. With Hj worst case tional per rank the histogram of witness scores, define Candidates Frontier states Survivor metadata

Nd = aBd−1 Θ(Bd sstate )

Nd /G Θ(Bd sstate /G)

( ) t X b Tj = min t : Hj (u) ≥ B ,

O(Nd mmeta ); one O(Nd mmeta /G) owner may receive Θ(Nd ) Candidate O(Nd mmeta ) about aggregate/G, exchange bytes plus latency Final ex- O(Bd (mmeta + balanced only after change sstate redistribution P )) bytes O( d Bd h); satu- host/disk service, History through D rated O(DBh) not GPU balance

u=0

Tj = min{Tj−1 , Tbj },

T0 = +∞.

(22)

When |Wj | < B, Tbj = +∞. Streams 3 and 4 may discard only candidates with s(c) > Tj ; the score boundary s(c) = Tj is retained because its final membership depends on τL . Figure 8 visualizes the conservative integer-score cut and the retained equal-score boundary.

Peak GPU memory also includes allocated frontier capacity, rings, both accumulator buffers, comparison-sort temporary storage, model/scorer workspace, and communication/runtime workspace. Mutually exclusive allocator phases are combined by a maximum, by summing every Pnot D phase. Across depths the work is d=1 Wd , not aD once the beam is saturated. Finally, five CUDA streams imply neither a fivefold speedup nor linear strong scaling. Under verified balance, bandwidth, and resource independence one may model a steady pipeline as

Lemma 1 (the published threshold never rises). The update rule publishes a minimum, Tj = min{Tj−1 , Tbj } ≤ Tj−1 .

(23)

This statement does not require a physical snapshot to equal Reducez (Cj ) (Fig. 8).

(19) Lemma 2 (a discarded candidate cannot win the reduced-key beam). If s(c) > Tj , some published witness snapshot has at least B distinct keys with observed but skew, peer latency, collectives, HBM contention, hisscores at most Tj . Their eventual minimum scores are no tory I/O, and the final drain are non-scaling floors. Equalarger than those observations, hence are strictly better tion (19) is a conditional performance model, not a theorem than s(c). Thus c cannot represent a key in the final top-B. or a new benchmark result. Omitted witnesses or stale higher scores make Tj weaker, not unsafe. Counting one key twice, however, destroys the Classical top-B versus monotone thresholding. Let distinct-key premise. C be the complete candidate multiset, write s(c) for the quantized integer score in Eq. (10), and let U = Reducez (C; lexmin(s, payload)) be its one-entry-per-key Theorem (conditional abstract reduced-key equivreduction, carrying s∗ (z) = minc:z(c)=z s(c) and the as- alence). For the same complete candidate set, integer sociated best payload. For fixed layout L, the complete quantization, Hash128 mapping z, payload order, and fully specified physical layout L, Lemmas 1–2 give the same ordering key is selected key representatives if every candidate is processed,
κL (z) = s∗ (z), τL (z) , (20) all records for one key are globally reduced before contributing distinct threshold witnesses, rejection is strict above where smaller score is better and τL is the deterministic the committed threshold, no local capacity silently drops prefix order over rank, physical shard/buffer, and local slot an eligible record, and exchange plus final physical-prefix for equal scores. Thus L specifies the realized physical ar- boundary selection complete: rangement, not merely GPU and shard counts. A classical distributed monolithic reference materializes U , sorts it by κL , and returns, for Fd,z (L) = Fd,z (L). (24) b = min(B, |U |), The equality concerns selected membership under the same ( ∅, b = 0, L. It does not assert an identical serialized output order TopB (U ) = (21) after redistribution. Fixed GPU and shard counts alone {z ∈ U : κL (z) ≤ κL,(b) (U )}, b > 0. are insufficient if scheduling changes physical-buffer or Thus the order statistic is used only when b > 0. The local-slot placement. This is a theorem about the abstract streamed abstract algorithm need not materialize U . At algorithm, not by itself a proof that a particular CUDA update j, let Wj be the entries counted by the threshold revision satisfies every obligation. Td ≈ tfill + max ti + tdrain/final , i

6

fixed beam size B = 7 in every row early

1

2

3

4

5

6

7

7

9

T1 = 7

middle

0

1

2

3

4

5

6

6

8

T2 = 6

final

0

1

2

3

4

5

5

5

7

T∗ = 5

keep for now

retain boundary until the physical-layout tie break

never rises

safe to discard

Final row: n< = 5; n= = 2 of three score-5 keys win by τL .

Figure 8: Monotone thresholding for one fixed B = 7 with integer scores. Green entries are retained provisionally, not guaranteed final membership. Values above the current threshold cannot return; every equal-score boundary entry remains until the fully specified physical-layout tie-break. Numbers are illustrative. Pinned-code correspondence. The historical one-T4 measurement is pinned to a1db0e6d9bb5458c8a842b37dfa99572d3025667. Its static audit verifies Hash128 owner calculation, per-buffer lexicographic reduction, inclusive threshold retention, monotone threshold publication, and final score-boundary phases. It does not establish the full theorem correspondence. Stream 4 reduces each physical sibling buffer separately, while threshold.cu:34--61 combines per-physical-shard snapshots and the final-selection paths scan all physical buffers; no global cross-buffer key reduction was found. In addition, the multi-rank Stream 3 owner scatter reads and compacts the same metadata array in one kernel across peer blocks without a grid-wide synchronization point. These are static audit findings, not reproduced GPU failures. The scatter issue is a world size¿1 code-path risk and is not evidence that the one-T4 measurement failed. Cross-buffer duplication would violate the distinct-key witness premise. Final ties use rank/physical-buffer/local-slot prefixes (threshold.cu:147--154,214--229,252--279 and dispatcher.cu:4480--4494). The H200 revision and historical two-T4 v118 run inherit neither these defects nor correctness without their own code comparison.

does not claim a canonical output order. It concerns beam selection, not shortest-path optimality. Historical measurements remain tied to their own revisions and do not inherit correctness or defects from this theorem or from another source tree. Final cut and materialization. After all five streams are drained, the ranks combine the final histograms. If |U | ≥ B, they choose the smallest T ∗ such that ∗

T X

H(u) ≥ B.

(26)

u=0

All states below T ∗ survive, and the same physical-prefix tie rule cuts its boundary to exactly B selected members. Define X n< = H(u), n= = B − n< . (27) u<T ∗

The final cut keeps every key below T ∗ and the first n= boundary keys by τL . This defines membership, not the later output serialization order. If |U | < B, all available keys survive instead. Therefore |Fd | = min(B, |U |).

(28)

Identity and exactness scope. The word exact means The selected metadata are load-balanced across GPUs. beam-selection exactness and has three explicit boundaries: Only then does each source GPU reconstruct the requested children and send them directly to their target GPUs. The quantized integer scores CPU receives O(p) count vectors plus compact selected+ Hash128 key equivalence (25) candidate metadata used to reconstruct ancestry, but no full state or frontier arrays. + fully specified physical-layout ties The five streams are readiness-driven rather than five seCompact candidates represent the equivalence classes of rial phases. Streams 1–2 fill ring slots almost continuously Eq. (9); they do not carry the full state representation. If while Streams 3 and 4 reduce earlier batches and Stream 5 no distinct relevant full states share a Hash128 key, the exchanges remote survivors. The mathematical obligation key-level equality also implies full-state selection equality. is that every published threshold count is a distinct-key Otherwise, a collision merges those states within the stated witness and every final key class is globally reduced before model. Boundary ties use the prefix over rank, physical the cut. Under that premise, a conforming implementabuffer, and local slot. Changing that arrangement may tion realizes the same selected reduced-key membership change selected membership; fixed GPU/shard counts do as its monolithic reference for the same physical tie laynot imply schedule-independent results. The theorem out, without materializing the raw candidate layer. The 7

pinned-code gaps above must be closed before making that does not reconstruct this missing 40GB run. The implestatement unconditionally for a specific measured binary. mentation limit is 128 ranks.

4

8×H200 Cube4 completed depth. On one Vast instance, eight H200 GPUs (143,771 MiB each) ran Cube4 puzzle 1000 with 24 generators. Requested width 2,900,000,000 aligned to Beff = 2,900,361,216 = 8 × 362,545,152. All eight rank logs record completed depth 8; using the conservative maximum gives 931.266 s. Thus the saturated layer represents

Experiments

Protocol. Historical records below retain their stated single-run or summary scope. The new RTX 3060 scaling points are medians of three timed repeats after a full warmup; selected profiles were re-warmed and repeated independently. We measure computational cost, not solution quality, and tag every result by hardware, workload, model, 24Beff = 69,608,669,184 =⇒ Rpair = 74.746×106 s−1 , and timing boundary. End-to-end (E2E) time includes (31) generation, de-duplication, communication, selection, and where the rate is derived, not a native distincthistory; it must not be confused with an isolated scoring- state counter. Observed device-wide peak usage kernel rate. was 141,820 MiB/GPU. The solver revision was Figure 9 separates the three legacy headline evidence 3b756afe9e7636e53520fa6de7e60a167bbaa79a. The records before the detailed platform tables. puzzle was unsolved and depth 9 was stopped at user Tables 6 and 7 separate legacy records, derivations, and request. The 2.94B attempt failed during NCCL count missing measurements. Empty cells mean “not measured.” exchange and the 3.00B attempt failed a static budget The T4 and H200 rates count nominal parent–generator gate; neither establishes a true maximum or CUDA-OOM pairs before de-duplication. No RTX 3070 child rate is boundary. This Cube4/H200 run and the Megaminx/T4 derived because its early depths are not saturated. run are not a strong-scaling comparison. For the saturated T4 depths, the recorded mean and derived child rate are

4.1

t̄7:10 =

1 4

10 X

td = 65.670 s,

Matched 1/2/4/8-GPU RTX 3060 Scaling

(29)

A separate public record measures one search on an exclusive host with eight RTX 3060 12-GiB GPUs. Every mBeff 24 × 82,837,504 Rchild = = 30.274 × 106 s−1 . = point uses the p900 input, the original FP16 MLP with t̄7:10 65.670 (30) FP32 accumulation (not the Cube4 Transformer), seed 0xC0DEC0DE, and 12 complete steps. The synchronized maximum-rank time includes expansion, inference, exLocal RTX 3070. The folded-input half2 kernel raised change, global selection, de-duplication, and history flush; isolated Stream 1 throughput from about 24.7 to 48.142 initialization and model loading are separate. Each point million candidates/s. Over 1,202 Nsight launches, its time had a full warmup and three timed repeats. fell from 9.678 to 3.232 s (2.99×). On the same complete The strong series fixes B = 4,194,304 and W = depth-20 workload, E2E wall time fell from 115.334 to 637,616,736 expanded actions at every GPU count. Its 60.623 s (1.90×). An older run that failed at depth 33 is speedup and efficiency are excluded. d=7

Sp = T1 /Tp , Kaggle 2×T4. Two T4 ranks jointly maintain one beam. The requested 82,615,524 states aligned to Beff = 82,837,504; the run solved in 350.402 s with 128 shards and Bµ = 4096. At B = 226 , moving from 8 to 64 shards reduced the saturated-depth mean from 69.365 to 51.732 s (1.34×). The isolated 40.60 M/s scoring rate is not an E2E rate.

Epstrong = Sp /p,

(32)

using each profile series’ own one-GPU median. The selected profiles are medium/common/common/common for p = 1/2/4/8. Medium changes the one-GPU median from 85.107 to 63.595 s, while both eight-GPU medians remain near 11.35 s. Consequently S8 changes from 7.487 to 5.605 and efficiency from 93.59% to 70.06%. The weak series uses Bp = p 4,194,304 and expanded-action counts Wp = 637,616,736, 1,241,596,512, 2,449,556,064, and 4,501,367,640. Every configuration starts from the same single state, and its early frontier grows naturally, so Wp is not exactly pW1 . We therefore report actual-work throughput gain rather than fixed-work speedup:

8×A100 capacity-only record. The run establishes capacity at requested width Breq = 770,883,178. Its summary records stable depth-8 execution on three Megaminx instances and 39,745 MiB peak memory per GPU. It does not record wall time, exact aligned width, or a complete runtime manifest. The pinned 2d5f978fcfc1f018813fc49e9d9aeec32ea5e22c launcher targets eight 80GB A100s and a requested 1.4B width; it

Gp = 8

Wp /Tp , W1 /T1

Epweak = Gp /p.

(33)

Throughput 2×T4 30.274 M children/s no scaling beyond two

Completed depth 8×H200, Cube4 Beff = 2.900361216B 931.266 s

Solution Megaminx superflip 51 replay-valid moves no optimality proof

Three claims, three evidence records; missing fields are never transferred between them.

Figure 9: The three legacy headline results use independent evidence. The H200 Cube4 depth, T4 Megaminx throughput, and replayed solution answer different questions and are not a scaling series. Table 6: Measured performance by platform. E2E is the production critical path; micro is an isolated kernel pipeline; capacity has no timing claim. n/d: not derived; n/a: not applicable; n/r: not recorded. Platform

Workload

Beam B

Measurement

RTX 3070 8GB puzzle 0, depth 20 222

s/depth

E2E complete; 60.623 s 3.031 avg. total micro complete n/a

Raw rate

child

n/d

48.142 M/s RTX 3070 8GB Stream 1, Bµ = — 4096, c = 3 Kaggle 2×T4 puzzle 20, radius 4, Breq = 82,615,524; Beff = solved; 350.402 s; 65.670 satu- 30.274 M/s limit 72 82,837,504 CSV+summary rated 8×A100 40GB puzzles n/r Breq = 770,883,178; Beff not stable; 39,745 MiB/GPU; n/r 900/950/1000, recorded summary depth 8 8×H200 Cube4 puzzle 1000, Breq = 2.900B; Beff = completed depth; 931.266 74.746 M/s depth 8 2,900,361,216 141,820 MiB/GPU obderived served

from 210 (no solution) to 220 (length 190); its large-cube agents use 224 [5, 6]. The completed H200 depth has Beff = 2,900,361,216 = 172.875×224 effective records. This is only a reported width ratio: it is not a speed, solutionquality, scaling, or verified unique-state comparison. We additionally measured Pilgrim and our search implementation on the same Cube4 state, checkpoint, single GPU, beam, and ten layers. The 3,383,064-parameter scorer maps 96 six-class input positions to 56 piece tokens plus CLS (57 tokens), applies input layer normalization, then four pre-LN Transformer blocks with width 256, eight heads, and a 1024-wide feed-forward layer, followed by a 24-output head. Inference uses FP16 and microbatches of 384. Table 11 reports the tenth layer, where every saturated frontier expands 24B pairs.

Here W8 /W1 = 7.059676. The selected weak profile is large at every p; common/selected G8 is 6.113/7.295, with efficiency 76.42%/91.19%. Thus GPU count alone is not a complete performance label: fixed beam and action counts still permit different batching, concurrency, buffering, physical capacity, memory use, and executed system work. The common strong series is superlinear at two and four GPUs, but the experiment does not isolate a cause; locality and single-versus-distributed path explanations remain hypotheses. Selected means fastest among only three admitted stable profiles, followed by independent final repeats, not a global optimum or an optimization ablation. The first five strong frontier memberships match across p; the first saturated cutoff differences are tied at score 43,768 under rank/physical-buffer/local-slot order, so later trajectories may differ. The experimenter reports all 12 saved frontiers checked for uniqueness, balance, and padding admission, plus fixed-p weak profile agreement. These are bounded recorded checks, not an exhaustive implementation proof or evidence of identical final search results.

5

5.1

Table 13 is an inventory, not a speed ranking. The Megaminx tests form two separate families: scalar output-1 and Q output-24. A ratio is valid only when checkpoint, architecture, head, state, moves, depth, width, dtype, and hardware match. CayleyPy cannot consume the output-24 head. A node rate is reported only when the native solver exposes a valid counter; it is never replaced by B/t. Matched implementations load identical checkpoint bytes: scalar SHA-256 7f5071e6...a539b759 or output24 SHA-256 e7bda332...5d2ca670. These are different models. The Cube4 Transformer is another separate comparison.

Comparison with CayleyPy and Megaminx Result

Comparisons answer different questions and must not be mixed: capacity ̸= speed ̸= solution quality.

Native approach inventory and matched model families on one T4

(34)

CayleyPy shows that wider beams can improve solution quality on one GPU. In its S20 experiment, width grows 9

Table 7: How to read the legacy headline results. A derived value is shown only when all inputs come from the same run. Run

Directly recorded

Exact derivation

Not established

2×T4 throughput

Breq , Beff , depth times, wall time Breq , depth 8, peak MiB/GPU, stable status all eight rank logs complete depth 8; effective width; device telemetry 20 completed depths, 60.623 s total isolated Stream 1 counters and time

24Beff /65.670 = 30.274 M children/s 24Breq ≥ 18.501 B children/depth 24Beff = 69,608,669,184 nominal pairs; 74.746 M/s derived 60.623/20 = 3.031 s/depth average 48.142 M candidates/s

throughput beyond two GPUs

8×A100 capacity 8×H200 Cube4

RTX 3070 E2E RTX 3070 micro

wall time, exact Beff , speed, strong scaling solved puzzle, depth-9 time, true maximum, CUDA-OOM boundary, or cross-platform scaling saturated child rate full-system throughput

Table 8: RTX 3060 scaling medians. Times are rounded to three decimals here; the public CSV contains exact summaries and paths to all three repeats. R denotes Sp for strong rows and actual-work Gp for weak rows. The daggered weak common p = 2 point is retained but its 5.97% min–max range/median exceeds the 5% winner-selection stability gate. Regime

p

Expanded actions Wp

Common Tp (s)

Common R

Selected Tp (s)

Selected R

Strong Strong Strong Strong

1 2 4 8

637,616,736 637,616,736 637,616,736 637,616,736

85.107 33.952 18.727 11.367

1.000 2.507 4.545 7.487

medium common common common

Selected profile

63.595 33.998 18.789 11.347

1.000 1.871 3.385 5.605

Weak Weak Weak Weak

1 2 4 8

637,616,736 1,241,596,512 2,449,556,064 4,501,367,640

100.779 117.355† 120.793 116.380

1.000 1.672 3.205 6.113

large large large large

72.209 69.980 70.951 69.876

1.000 2.009 3.910 7.295

Strong own-baseline speedup 8

80 Sp = T1 /Tp

whole-search median (s)

Strong time: fixed B, W

60 40 20 0

1

2

4

6 4 2 0

8

120 100 80 60 1

2

4

2

4

8

Weak actual-work throughput gain Gp = (Wp /Tp )/(W1 /T1 )

whole-search median (s)

Weak time: growing Bp , Wp

1

8

8 6 4 2 0

1

2

4

8

GPUs p

GPUs p common

selected

Figure 10: Profile-sensitive RTX 3060 scaling. Solid lines are measured three-repeat medians; bars span the observed minimum and maximum, not a confidence interval. Gain bars hold the corresponding T1 median fixed. In the strong-time panel, colored dashed lines are each series’ T1 /p. In the weak-time panel, dotted lines are constant T1 and colored dashed lines are T1 (Wp /W1 )/p, the ideal time for linear throughput on the actual measured work. Black dashed gain references are y = p. No line is a fitted performance law.

10

Table 9: Which comparisons are valid. A speed ratio requires the same model contract and workload; a capacity ratio does not imply a speed ratio. Pair

Matched quantities

Valid statement

Invalid inference

MultiGPU vs CayleyPy scalar MultiGPU vs Pilgrim Cube4 MultiGPU vs AlphaCube MultiGPU vs DeepCubeA Eight H200 completed depth vs CayleyPy

checkpoint, model head, moves, T4, widths state, Q checkpoint, GPU, B, depth 10 native released systems only

E2E wall-time ratio at a shared width depth-10 pair rate

output-24 or node-rate ratio

hardware-side native run effective-record and reported beam-width definitions

execution and failure-mode inventory native A* iteration and node statistics 172.875× width ratio

W

210

212

214

216

220

Length

—

252

202

194

190

mean s/depth

Table 10: Published CayleyPy beam-width trend (Table 8 of [5]).

10−1 210

214

218

220

218

220

beam width B ·104

Peak VRAM

198.153 508,007 2.90 GiB reserved 181.282 555,293 1,949 MiB used 314.487 320,087 2.90 GiB reserved 301.955 333,378 1,949 MiB used

AlphaCube and DeepCubeA. For AlphaCube, s/depth is solver wall divided by the completed search depth reported by the returned solution (20 for the first three rows and 17 for the remaining rows). For both Megaminx implementations it is wall divided by the fixed eight completed depths. These averages include startup and early unsaturated layers; they complement, rather than replace, nodes/s. AlphaCube materializes its 18B Cube3 children in host NumPy arrays, so its first failure is a host-memory kill despite only 4.685 GiB GPU reservation. Its widest completed rates are about 40–44 thousand nodes/s. DeepCubeA is weighted A*, not a persistent beam. The audited run used weight 0.6 and search/NN batch sizes 10,000/10,000; its T4 run completed 55 iterations in 146.474 s, expanded 6,134,352 nodes at 41,880 nodes/s, and found a length-21 solution. These are A* statistics, not beam-depth or frontier-capacity values. Figure 11 places the completed AlphaCube timings beside its native node counter and marks the next tested host-memory failure in the caption.

speed, quality, scaling, or verified unique-state ratio

100

native nodes/s

T4 Pilgrim T4 Ours P100 Pilgrim P100 Ours

retained-beam capacity

101

Table 11: Matched Cube4 depth-10 computation at B = 4,194,304. GPU Implementation s/depth (depth 10) Pairs/s

memory ratio across different counters direct speedup

6

4

2 210

214

beam width B

Figure 11: AlphaCube one-T4 completed sweep. The upper panel shows wall time per completed depth; the lower uses AlphaCube’s valid native node counter. The next tested width, 1,703,936, ended in a host-memory kill.

20,971,520 completed in 197.358 s (24.670 s/depth) at 12,333 MiB, whereas B = 23,068,672 CUDA-OOMed. The measured brackets are therefore 5,898,240–6,291,456 and 20,971,520–23,068,672, respectively. The final collaborator-run MultiGPU pass and scalaronly v27 confirmation now give measured complete/OOM pairs for both heads. Scalar completed at 29,360,128 and CUDA-OOMed at 31,457,280; native output-24 completed through 29,360,128 and CUDA-OOMed at 33,554,432. Figure 13 juxtaposes those measured endpoints while keeping the scalar and output-24 model families separate. The scalar OOM recurred for every row-budget profile CayleyPy sweep. Figure 12 pairs the native CayleyPy from 49,152 through 24. The common primary metric is timing curve with its allocator growth; the failed broad- total wall divided by eight, 352.145 s/depth; the auxiliary grid point is shown only as a memory boundary, not as a final-depth time was 1,644.13 s. completed timing. Pilgrim’s widest scalar completion, B = 5,898,240, took 1,462.557 s (182.820 s/depth) with a 14,433 MiB device MultiGPU output-24 sweep. The largest completion peak; B = 6,291,456 CUDA-OOMed. For output-24, B = is B = 29,360,128: 116.904 s total, 14.613 s/depth, and 11

Table 12: Model contracts used by the reported tests. Parameter counts refer to the trainable source model before batch-normalization folding. Full layer sequences remain in the artifact tables. Model family

Parameters Output

Compatible implementations

Cube3 AlphaCube 118,939,666 18 actions large Cube3 DeepCubeA 14,663,001 scalar cube3 Megaminx scalar MLP 34,766,849 scalar Megaminx QMLP2RB Cube4 Q Transformer

AlphaCube only DeepCubeA only Pilgrim Searcher, CayleyPy, MultiGPUBeamSearch Pilgrim QSearcher, MultiGPUBeamSearch matched Pilgrim/MultiGPU Cube4 and 8×H200 tests

23,978,008 24 actions 3,383,064 24 actions

Table 13: Native search inventory on one visible T4. This table records algorithm type, compatible model family, and measured boundary; it is not a cross-row speed ranking. Approach

Search type

Model family

Max complete

First failure/status

AlphaCube 0.1.6 DeepCubeA

beam weighted A*

Cube3 action-18 Cube3 scalar

1,572,864 n/a

1,703,936 host kill complete, length 21

Pilgrim Searcher Pilgrim QSearcher native CayleyPy

beam beam beam

Megaminx scalar Megaminx output-24 Megaminx scalar

5,898,240 20,971,520 20,971,520

MultiGPUBeamSearch MultiGPUBeamSearch

beam

Megaminx scalar

29,360,128

nodes/s iterations, nodes/s 6,291,456 OOM wall/depth 23,068,672 OOM wall/depth targeted 21,037,056 wall/depth OOM 31,457,280 OOM wall/depth

beam

Megaminx output-24

29,360,128

33,554,432 OOM

mean s/depth

103

wall/depth

scalar model MultiGPU

101

largest complete first measured failure

CayleyPy

10−1

Pilgrim 10

2

14

2

18

2

22

2

25

2

223

beam width B allocator peak (MiB)

Valid metric

allocated reserved first broad-grid OOM

104

224

output-24 model

225

MultiGPU

103 Pilgrim 102 210

214

218

222

225

225

beam width B

beam width B

Figure 12: Native CayleyPy one-T4 sweep. Time and Figure 13: Measured completion/failure brackets on one allocator memory rise with beam width; 224 completes and T4. A line joins the largest completed width to the first 225 is the first broad-grid OOM. The failed point is not a measured failure; it does not claim that the exact capacity lies at either endpoint. Scalar and output-24 models remain timing measurement. separate. 13,717 MiB peak device memory. At B = 33,554,432, every row-budget profile down to 1 failed at 14,909 MiB. Its final therefore separates the completed timing curve from the 1.563-s attempt is not a completed depth time. Figure 14 marked OOM boundary. 12

its output-24 path reached 29,360,128 and OOMed at 33,554,432. Neither scalar path exposed a valid node counter, so only wall time and memory are compared. At B = 16,777,216, wall time was 4,741.581 s for CayleyPy and 1,728.460 s for MultiGPU, a matched 2.74× ratio. Superseded and cancelled runs are excluded. The broad matched curve is cohort C1 and uses the solver-internal MultiGPU timer. The later boundary rows are cohort C2: their executable-wrapper timer includes initialization but excludes build and model export. At B = 25,165,824, C1 records 2,416.150 s whereas C2 records 3,027.673 s. Both are normalized by eight completed steps, but their timing boundaries differ; the cohorts are neither pooled nor substituted for one another. Figure 15 therefore shows only the matched C1 curve and states its timing boundary in the caption.

Table 14: Final MultiGPU 1xT4 scalar boundary points. B

Wall (s)

s/depth

Peak device (MiB)

25,165,824 27,262,976 29,360,128 31,457,280

3,027.673 3,080.206 2,817.158 —

378.459 385.026 352.145 —

12,267 13,241 14,215 14,909

Status complete complete complete CUDA OOM

224

225

mean s/depth

15

10

5

0 ·104 1.5

222

223

beam width B complete CUDA OOM

mean wall time per depth (s)

peak device memory (MiB)

220

1 0.5 0 220

222

223

224

225

beam width B What happens when we double the frontier? B : 222 → 223 → 224 time: 2.842 → 5.136 → 9.683 s/depth (×1.81, ×1.89) memory: 2253 → 4159 → 7983 MiB (×1.85, ×1.92)

103

MultiGPUBeamSearch CayleyPy 102

101

100 216

218

220

222

224

retained beam width B

Figure 14: Native output-24 sweep on one T4. Upper: completed mean time per depth. Lower: device-memory growth and the failed B = 33,554,432 attempt. The doubling rows are descriptive adjacent ratios from three completed points in this same sweep, not a fit or asymptotic claim. The OOM point is not treated as a timing measurement. Reference-count comparison (not a performance fit). For fixed branching a, doubling retained B doubles generated N = aB and frontier-state bytes. In the sortbased abstract reference of Eq. (16), the N log2 N referencework term scales by   (2N ) log2 (2N ) 1 =2 1+ . (35) N log2 N log2 N

Figure 15: Matched one-T4 Megaminx scalar sweep. Both axes are logarithmic. The historical MultiGPU C1 series uses the solver-internal timer; CayleyPy uses its recorded run wall. Values are normalized by eight completed steps. Neither implementation exposes a valid node counter for these runs. Scalar timings are not compared with the faster, architecturally different output-24 model. In the separately matched Cube4 test, our tenth-layer pair rate is 1.093× Pilgrim on T4 and 1.042× on P100. The memory counters differ (allocator reservation versus device-wide usage), so no memory ratio is claimed. The dated public-source audit located the same-metric chronology

55 −→ 54 −→ 53 −→ 51 moves. (36) These are operation and storage counts, not a wall-time bound for the historical sweep or the audited Stream 4 dispatcher. Fixed costs, occupancy, other work, and repeated The immediately preceding located public result is 53 jobs can keep the measured adjacent ratios from equaling moves. The companion record for the 51-move path identifies the same signed 72-degree, 24-generator metric and two. lists 22,600.2 s [18, 17, 16, 15]. Independent CPU replay Matched scalar cohorts. The matched scalar sweep reaches the exact target. The audit located no shorter pubcompleted CayleyPy through 224 and OOMed at 225 . A lic same-metric path through August 25, 2026, but there separate targeted run gives the finer bracket 20,971,520- is no formal registry or optimality proof; we therefore do complete versus 21,037,056-OOM. MultiGPU reached not call it a world record. This result is separate from the 29,360,128 at 14,215 MiB and OOMed at 31,457,280; capacity and throughput runs. 13

threshold witnesses, global one-per-key reduction, raceTable 15: Public artifact map. Short link labels keep the free routing, and complete processing without semantic paper readable; each artifact is tied to the claim it can local caps. The equality is selected membership under support. the same realized physical layout, not a canonical serialResource Contents and supported claim ization order or schedule-independent result from GPU Paper repository sources, evidence index, tables, noteand shard counts alone. Full-state equality additionally rebooks; definitions and provenance quires no relevant Hash128 collision. This is beam-selection Paper release matched checkpoints and PDFs; modelv1.0.0 contract comparisons exactness, not shortest-path optimality. The static audit One-T4 dataset data and notebooks; one-T4 sweeps and leaves cross-buffer de-duplication unresolved and identiboundaries RTX 3060 scaling 16 measured points, profiles, manifests fies a multi-rank in-place owner-scatter risk in a1db0e6; dataset and logs; matched 1/2/4/8-GPU scaling neither finding is evidence that its historical one-T4 meaSolver repository solver, Megaminx release and replay audit; implementation and 51-move path surement failed. The H200 revision and historical two-T4 v118 run inherit neither the risk nor correctness without 6 Code and Artifacts their own code comparison. Eight H200s completed one saturated Cube4 depth at 2,900,361,216 retained records Evidence is revision-scoped. The public index pins one-T4 to and a derived 74.746 million nominal pairs/s; two T4s a1db0e6d9bb5458c8a842b37dfa99572d3025667; Cube4 to measured 30.274 million logical Megaminx children/s; and df534ebb1ef624abd42443211778b5588916d6d2; the older eight-A100 record establishes only requested cluster/capacity to 2d5f978fcfc1f018813fc49e9d9aeec32ea5e22c; and CayleyPy capacity. Those cross-platform records do not establish strong scaling. On the separate RTX 3060 host, fixed-count to 5b2b53f. It gives no measured solver revision for the common/selected eight-GPU speedups were 7.487/5.605 two-T4 throughput record. The H200 depth is pinned separately to 3b756afe9e7636e53520fa6de7e60a167bbaa79a. (efficiencies 93.59%/70.06%), while weak actual-work gains None is relabeled as main@25cc25d. The RTX 3060 record is were 6.113/7.295 (efficiencies 76.42%/91.19%). The onethe public dataset observed at revision GPU medium profile changed 85.107 s to 63.595 s while 4f8e9b67fc00a2ef2e49ae1d2b255f860531d0aa; its exact eight-GPU time stayed near 11.35 s: GPU count alone is source identities are listed in Appendix B. In snapshot therefore an incomplete performance label. These data b113582e15c78d33deceea5922eb6589ae492fe4, the actual establish neither a causal bottleneck attribution nor idenSHA-256 of artifacts/manifest.json is c01dc1c3c74b78fc tical final search trajectories. The artifacts separately 8af4ba363f80edb5f9aca4dbc10fb8004b50ae38b209972c; the contain a replay-valid 51-move Megaminx-superflip path, older checksum list contains a different value and is not the shortest public same-metric solution located by the treated as a verified inventory. The complexity analysis is a separate read-only source audit, dated audit. not a benchmark. Its note has SHA-256 98b8eea288b20b69 9a0bab4e962fc9f6de6fc9ededa6698d574ae3593d4e9528; its source manifest has SHA-256 a0f44e50a6aeb1b2 2fb0f48fa516c5d30b1b1c666c3c4b9695aa43f6c94af70b. The manifest pins current dirty HEAD 81ed9f0287c1f9057648119a253f208c31f7a872 and the exact SHA-256 of each audited source file. That snapshot, historical pin a1db0e6, and the abstract exact-beam contract are three distinct scopes. Current specialized state widths and current final-union code are not substituted into historical H200, T4, or A100 measurements.

Acknowledgements The author thanks OpenAI, its AI tools including Codex, and the CayleyPy project. The author also thanks Vlad Kuznetsov for providing the neural network model used in measurement runs and in the search that found the 51-move Megaminx superflip path.

The A100 record supports capacity only; the T4 record Use of Generative AI and Author supports Megaminx throughput; the H200 record supports one completed Cube4 depth; and the RTX 3060 record Contributions supports only the declared profile-sensitive scaling series. OpenAI AI systems were used extensively in the develMissing fields are never borrowed from a different run. opment of MultiGPUBeamSearch and the preparation of this paper. The author defined the system architecture, directed the development and experimental work, and 7 Conclusion personally checked the correctness of obtained solutions The conditional abstract beam-selection result can be sum- through Kaggle. The author also personally verified the theorem relating threshold-based selection to global top-k marized in one line: selection. Most of the software implementation was gendistributed monolithic Fd,z (L) = Fd,z (L) (37) erated and revised using OpenAI Codex, which was also used for testing, debugging, performance investigation, and for the same complete candidate set, quantized scores, experimental tooling. AI agents prepared instrumentation Hash128 key equivalence, payload order, fully speci- and launch scripts, executed the RTX 3060 scaling experfied rank/physical-buffer/local-slot tie order, distinct-key iments, processed their recorded outputs, and generated 14

tables and plots. OpenAI assistants, including the assistant used in Prism, contributed to mathematical analysis, theorem and proof drafting, complexity analysis, literature and source checks, manuscript drafting and revision, and LaTeX preparation. Numerical consistency checks, code-to-claim audits, and visual checks of the manuscript were likewise AI-assisted. These checks have the specific scope and limitations described in the paper; they do not establish exhaustive implementation correctness or independent human verification of every output. The author remains responsible for the submitted manuscript, its claims, and its limitations.

Peak memory. The audited current planner has the phase structure Mrarena = align(sstate Frcap ) + align(Msolved )   + align max Mx ,

(39)

x∈P

where P contains compatible stream, selection, materialization, and other phases. Stream memory includes score/hash rings, send/receive rings, both physical survivor buffers, comparison-sort keys/values and temporary storage, histograms, and spill capacity. Process peak additionally includes model weights, scorer activations/workspace, CUDA/NCCL contexts, graph metadata, and allocator/runtime overhead. Thus arbitrary survivors A Complexity Details for the Au- require O(Nd mmeta ) aggregate persistent metadata and potentially that order on one owner; O(Nd mmeta /G) redited Code quires balance. The current audit’s specialized allocated state widths are not used to replace the separately sourced This appendix expands only the terms needed to interpret 96-byte hypothetical full-child value in Eq. (6) or any Eqs. (17)–(19). It does not assert that the current dirty historical memory measurement. snapshot produced any reported measurement or satisfies the abstract exactness obligations. History, depth, and wall time. Let nhist,d be final history entries recordedPat depth d and h their stored bytes. volume is Repeated reduction and final selection. Stream 3 HistoryPwork is Θ( d nhist,d ), device-to-host P m n , and stored logical bytes are h meta hist,d d d nhist,d ; comparison-sorts the full Q capacity, including sentinel these counts are not all N expansions. With a saturated d tail, then reduces equal Hash128 keys. Fixed-width radix operations used later for score bins or shard indices do unpruned beam this is O(DBh). Disk bandwidth and not make this Hash128 comparison sort linear. Stream 4 flush/read latency remain service limits, and one reconsimilarly sorts the scheduled physical capacity Ck . Cur- structed path can require O(D) reads and O(Dℓ) replay rent stream3.cu:863--868 can request a small-dirty job, work. For stage times ti , network/history time tservice , and including dirty=0, when enough clean records remain; final drain tfinal , completion gives the scheduling bounds queue and running guards do not prove an amortized job X bound. The current final A/B union additionally has max{ti , tservice , tfinal } ≤ Td ≲ ti + tservice + tfinal . (40) i X Wunion = O(Cjunion log Cjunion ), (38) The maximum form in Eq. (19) requires demonstrated j overlap and independent resources. Balance, bandwidth, followed by histogram and boundary scans accounted as latency, skew, minimum job capacities, HBM contention, O(Vscan + GH + EGJH) for J logical shards and E thresh- history service, and the final drain bound strong scaling; old updates. This union term belongs only to the audited no concrete crossover GPU count follows without measured current code; it is not assigned to historical executions. A parameters. threshold may retain all candidates, so it provides datadependent savings but no worst-case survivor reduction.

B

Communication and skew. If Uremote ≤ U3 ≤ Nd , candidate payload is mmeta Uremote = O(mmeta Nd ). Final selected metadata and reconstructed states add O(Bd mmeta + Bd sstate ) aggregate bytes and O(Bd ℓ) materialization work. Uniform independent ownership would give expected load near U3 /G, but it is an assumption: one owner can receive Θ(U3 ). Per-peer count and payload calls add peer-count and latency terms; over q exchange rounds the count operations are Θ(qG2 ) aggregate. Fabric bisection bandwidth, port bandwidth, collectives, zero-size peer calls, and skew must therefore remain explicit in a wall-time model.

RTX 3060 Scaling Protocol Details

The three tested profiles change physical execution parameters, not the beam semantics. Every profile uses eight logical shards and four active sort slots. Strong history allocation is 8 GiB total; weak allocation is 8 GiB per GPU, with no history pruning. This is capacity allocation, not a semantic shard cap. Capacity amendment and selection. The original weak common p = 2 admission with capacity 655,360 overflowed a physical Stream 3 buffer before completion

15

Table 16: RTX 3060 profile parameters. Weak runs override only the physical shard-buffer capacity to 3,276,800 for every profile and GPU count. “S4” is both batch and trigger capacity; the final materialization chunk has the same size. Profile common medium large

examples/forward

outer/lane

concurrency

ring

S3 accumulator

strong shard cap

weak shard cap

S4/final chunk

8,192 16,384 32,768

196,608 393,216 786,432

1 2 2

2 2 4

393,216 786,432 3,145,728

655,360 1,310,720 3,276,800

3,276,800 3,276,800 3,276,800

65,536 131,072 262,144

and is excluded from timing. All weak candidates were then admitted with capacity 3,276,800; weak p = 1 was remeasured independently rather than reused from strong scaling. The runner, global beams, 12-step workload, and global selection/de-duplication semantics were unchanged. The weak one-GPU common point (100.779 s) and strong one-GPU common point (85.107 s) use different physical buffer capacities, so their difference does not isolate a causal capacity effect. Each candidate received a warmup and three selection repeats; an admitted candidate required range/median at most 5%. The frozen winner then received an independent warmup and three final repeats. The reported weak common p = 2 point has a 5.97% range and therefore does not satisfy that winner-selection gate.

Admission scope. The experimenter reports all 12 saved frontiers checked for logical-state uniqueness, distribution balance, and valid padding. Strong memberships match across p for the first five frontiers; first saturatedcutoff differences are score-43,768 ties under rank/physicalbuffer/local-slot order. At each fixed weak p, all 12 saved frontiers match across tested profiles. These are bounded recorded admission checks. They are not an independent exhaustive implementation proof, a guarantee of identical later strong trajectories, or evidence of identical final solutions.

References

Hardware and telemetry. The exclusive host had eight RTX 3060 12-GiB GPUs, two Xeon E5-2673 v4 CPUs, and no NVLink; links were PIX/PHB within groups and NODE between groups. The record reports driver 595.71.05, CUDA compiler 12.8.93, GCC 13.3.0, NCCL 2.31.2, and Linux 6.8.0-124-generic. GPU clocks were observed rather than locked. Device memory was sampled through nvidia-smi at roughly 0.2-s intervals plus command overhead, so transient peaks may be missed. Min–max intervals are three-repeat ranges, not confidence intervals. The experiment contains no isolated capacityeffect or optimization ablation.

[1] F. Agostinelli, S. McAleer, A. Shmakov, and P. Baldi. Solving the rubik’s cube with deep reinforcement learning and search. Nature Machine Intelligence, 1:356–363, 2019. [2] T. S. Anantharaman and R. Bisiani. A hardware accelerator for speech recognition algorithms. In Proceedings of the 13th Annual International Symposium on Computer Architecture, pages 216–223, 1986. [3] H. Braun, J. Luitjens, R. Leary, T. Kaldewey, and D. Povey. GPU-accelerated viterbi exact lattice decoder for batched online and offline speech recognition. In 2020 IEEE International Conference on Acoustics, Speech and Signal Processing, 2020. [4] W. Chan et al. Efficient beam search for large language models using trie-based decoding. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 14795–14807, 2025. [5] A. Chervov et al. CayleyPy RL: Pathfinding and reinforcement

learning on cayley graphs. arXiv preprint arXiv:2502.18663, Measurement identities. The 2025. public dataset is TryDotAtwo/ multigpu-beam-rtx3060-scaling-20261004, [6] A. Chervov et al. A machine learning approach that beats large rubik’s cubes. arXiv preprint arXiv:2502.13266, 2025. observed revision 4f8e9b67fc00a2ef2e49 ae1d2b255f860531d0aa. The final report SHA- [7] J. Chong, Y. Yi, A. Faria, N. R. Satish, and K. Keutzer. Dataparallel large vocabulary continuous speech recognition on graph256 is f87d0ef6d92115fdbb1b83f05a92afce ics processors. Technical Report UCB/EECS-2008-69, Univerd7d9fbb6976639687867a53bad79b207; the measuresity of California, Berkeley, 2008. ment CSV is 926a3103df656ef427d89f62b51d7779 Frohner, J. Gmys, N. Melab, G. R. Raidl, and E.-G. Talbi. b965f8af1f61b0f23453735e787b3449; and the com- [8] N. Parallel beam search for combinatorial optimization. In Proceedpletion audit is fc9112a534d9bed4a5c6d704a26192de ings of the 51st International Conference on Parallel Processing Workshops, 2022. 8d6edc2f1a84139e47d7ba640ce1d544. The immutable runner binary is 7c10c4e8cade66d78900946052e0a1cc [9] X. He, Y. Yao, Z. Chen, J. Sun, and H. Chen. Efficient parallel f08644fa0df37df6b5286fd3028279a2; the instruA* search on multi-GPU system. Future Generation Computer Systems, 123:35–47, 2021. mented runner is a38556e3fd5a85313d74b5fa1a573be1 bf26baa2586fb61ca081d01327c7366b. The completion [10] M. Junczys-Dowmunt, T. Dwojak, and H. Hoang. Is neural machine translation ready for deployment? a case study on 30 audit reverified 346 per-file source-manifest entries based translation directions. In Proceedings of the 13th International on 81ed9f0287c1f9057648119a253f208c31f7a872. Conference on Spoken Language Translation, 2016. Sharing that base revision does not prove identity with S. Kim, S. Park, S. U. Noh, J. Hong, T. Kwon, H. Lim, and the separately audited dirty snapshot; neither correctness [11] J. Lee. PathWeaver: A high-throughput multi-gpu system for nor audit findings transfer without comparison of the graph-based approximate nearest neighbor search. In 2025 per-file bytes. USENIX Annual Technical Conference, pages 1501–1517, 2025.

16

[12] A. Kishimoto, A. Fukunaga, and A. Botea. Evaluation of a simple, scalable, parallel best-first search strategy. Artificial Intelligence, 195:222–248, 2013. [13] R. Kuroiwa and J. C. Beck. Parallel beam search algorithms for domain-independent dynamic programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20743–20750, 2024. [14] M. Soltani and F. Agostinelli. GPU-accelerated A* search with deep neural network heuristics. In Proceedings of the Nineteenth International Symposium on Combinatorial Search, 2026. [15] SpeedSolving forum contributor. Development of a megaminx solver: 51-move superflip report. SpeedSolving forum post 1705451, 2026. [16] SpeedSolving forum contributor. Development of a megaminx solver: 53-move superflip report. SpeedSolving forum post 1700151, 2026. [17] SpeedSolving forum contributor. Development of a megaminx solver: 54-move superflip report. SpeedSolving forum post 1696217, 2026. [18] SpeedSolving forum contributor. Development of a megaminx solver: 55-move superflip report. SpeedSolving forum post 1696242, 2026. [19] D. Sun, B. Kan, H. Long, H. Zhao, H. Li, Y. Liu, P. Zhou, A. Feng, W. Huang, Y. Gu, Z. Li, H. Shang, Y. Zhang, D. Tao, N. Sun, and G. Tan. A fully GPU-accelerated framework for high-performance configuration interaction selection with neural network quantum states. In Proceedings of the 35th International Symposium on High-Performance Parallel and Distributed Computing, 2026. [20] K. Takano. Self-supervision is all you need for solving rubik’s cube. Transactions on Machine Learning Research, 2023. [21] A. Wijs and B. Lisser. Distributed extended beam search for quantitative model checking. In Model Checking Software: 14th International SPIN Workshop, pages 166–184, 2007. [22] A. Wijs and M. Osama. The fast and the capacious: Memoryefficient multi-GPU accelerated explicit state space exploration with GPUexplore 3.0. Frontiers in High Performance Computing, 2, 2024. [23] Y. Zhou and J. Zeng. Massively parallel A* search on a GPU. In Proceedings of the AAAI Conference on Artificial Intelligence, 2015.

17

Related documents

• One Global Beam Across Many GPUs: High-Throughput Beam Search at Billion-Record Frontier Scale#1217565
• PhaseGate: Phase-Aware CPU Retrieval Scheduling for On-Device LLMs on Unified Memory#1200188
• PhaseGate: Phase-Aware CPU Retrieval Scheduling for On-Device LLMs on Unified Memory#1194405
• BOA: Beamwidth Online Adaptation for Filtered-ANNS on a GPU#1110553
• BOA: Beamwidth Online Adaptation for Filtered-ANNS on a GPU#919339