DreamCoder learns photonic decomposition rules that scale beyond the training dimension

The paper's main result is a reusable rule, not a faster implementation of a known photonic mesh. In a preprint submitted on 11 July 2026, Yifei Zhang and colleagues extend DreamCoder to complex-valued unitary-matrix decomposition. Programs learned from 5 x 5 matrices are reported to diagonalize random matrices at sizes up to 64 x 64 without retraining, while a related rule reduces the cost of decomposing Householder matrices from quadratic to linear in the matrix dimension. 1

That makes the paper a useful test of DreamCoder's library-learning claim outside the usual list, string, and graphics DSLs. It is also a narrower result than the phrase "AI-driven algorithm discovery" suggests. The system searches inside a hand-specified language of Mach-Zehnder interferometer operations, and its new-domain method is built around enumerative search and compression rather than a newly trained neural recognizer.

The target problem is photonic decomposition. Given a complex unitary matrix U, the system must find a sequence of left- and right-multiplication operations that turns U into a diagonal matrix. Each operation corresponds to an MZI acting on a pair of rows or columns. The starting DSL contains two typed families, R_ij and L_ij, whose parameters are computed from the current matrix. A candidate program is accepted only when every off-diagonal element falls below 5 x 10^-4; the successful programs in the reported experiments usually reach residuals around 10^-16. 1

This is a meaningful change to the DreamCoder setting. The primitives are no longer list combinators or graphics operations. They are complex-valued transformations with a direct physical interpretation, and correctness is a numerical constraint over matrices rather than an exact symbolic output match. The paper therefore tests whether the wake-sleep loop can learn abstractions when both the program semantics and the verifier live in a continuous mathematical domain.

The loop itself remains recognizably DreamCoder. In wake, the system enumerates candidate MZI sequences under the current probabilistic context-free grammar and evaluates them on decomposition tasks. The posterior favors programs that both solve the tasks and have a short description under the current library. In sleep, recurring fragments from successful programs are factored into reusable primitives by minimizing the combined cost of the new abstraction and the rewritten program corpus. The enlarged library is then used in the next wake phase. 1

The distinction matters because the paper's contribution is not a new primitive set. It is the demonstration that compression can discover useful higher-level construction rules over a complex-valued operator language, then use those rules to make deeper searches tractable.

On 5 x 5 matrices, independent learning finds several complete decompositions after nine wake-sleep iterations. Each uses the theoretical minimum of 10 MZIs, but the operation orderings differ from the classical Reck and Clements layouts. The point is not that DreamCoder beats their component count: it cannot beat the universal lower bound. The point is that it finds multiple valid elimination strategies without being given one of those human-designed layouts as the target. 1

The larger 6 x 6 experiment shows why the sleep phase is doing more than tidying code. Direct enumeration of 15-operation programs is too large, so the authors use a curriculum with partially decomposed subtasks. Shorter solutions discovered early in the curriculum become library abstractions, which later searches can compose into deeper programs. After seven iterations, the system finds 15-MZI decompositions, again reaching the universal lower bound. Across ten iterations, the library grows from 30 hand-defined MZI primitives to 65 primitives, with the fastest growth early and only one or two new abstractions per iteration after the seventh. 1

That pattern is the strongest evidence in the paper for a DreamCoder-style effect. The library is not merely a record of solutions. It changes the search regime: recurring subsequences become a vocabulary in which longer decompositions can be expressed without reopening the full primitive-level search space.

The paper's most informative test starts with programs learned on 5 x 5 matrices and extends their construction rules compositionally. The authors test the resulting programs at dimensions 5, 6, 7, 8, 16, 32, and 64. They report 100% success across these dimensions, with off-diagonal residuals at approximately machine precision. One discovered pattern is a row-pair interleaving rule: it processes rows from the largest index downward in a fixed pattern and emits exactly N(N-1)/2 operations for any dimension N. 1

This is a better test of abstraction than reporting another 10-MZI circuit. A fixed sequence for one matrix size would show search. A parameterized construction that survives a change in N shows that the extracted fragment has captured a relation between indices. The paper's evidence is still simulation evidence over generated unitary matrices, but within that setting the result is aligned with what a library-learning system is supposed to produce: a compact program schema that supports new instances rather than a memorized trace.

The paper then applies the same engine to matrix families with additional structure. For Householder reflectors, it discovers a dimension-independent rule using 2N - 3 MZIs instead of the N(N-1)/2 required for a general unitary. At N = 64, the reported counts are 125 and 2016 respectively, a 93.8% reduction, with machine-precision verification and no retraining. 1

This is where the lineage connection becomes more interesting than a simple application label. The system is not only learning a reusable implementation of a universal algorithm. It is using repeated successful programs to expose a property of a task family that was not included as an explicit analytic hint. The input family supplies the regularity; the library-learning loop turns that regularity into a compact operator sequence.

The sparse-matrix experiments make a similar claim for unitary factors obtained from sparse matrices. The paper reports structure-dependent reductions in its N = 6 examples, including 47% and 60% fewer MZIs than the 15-operation general bound, with numerical verification near 10^-16. Its abstract summarizes a sweep reaching up to 38% fewer MZIs at 95% sparsity. These numbers should be read as results for the paper's generated matrix families, not as a general hardware law for arbitrary sparse inputs. 1

DreamCoder's original wake-sleep system couples three ideas: program search, library growth, and a neural recognition model trained to guide later searches. 2 LAPS adds language supervision to abstraction and search heuristics, Stitch makes symbolic compression much faster, and LILO combines LLM-guided synthesis with Stitch-style compression and automatic documentation. 3 4 5

Zhang et al. push on a different axis: domain transfer. Their paper shows that the wake-sleep compression mechanism can operate over complex-valued linear algebra and can produce dimension-independent and structure-specific programs. But the detailed method is still enumerative search under a learned grammar. It does not report a separate neural recognition model that proposes programs from raw tasks. On the channel's distinction between library learning and the full neural-guided loop, this is a genuine library-learning extension, not yet a demonstration that the recognizer and the growing DSL reinforce each other in the new domain.

That missing piece is not cosmetic. The paper itself needs curriculum learning because search grows exponentially with dimension. A neural recognizer trained on matrix tasks could change the proposal distribution and reduce the burden on enumeration. Without that experiment, the paper shows that abstractions can make search more compositional, but not that learned recognition makes the overall system scale in the DreamCoder sense.

The constraints are clear. The MZI vocabulary is supplied by the authors, the training tasks are generated from random unitary matrices or selected structured families, and success is judged by a numerical diagonalization verifier. The paper does not establish that the system can invent a useful photonic DSL from raw hardware descriptions, discover abstractions under device noise, or validate an irregular topology on a physical chip. Its claim is algorithmic: within a specified operator language and simulator, library learning finds compact rules that transfer across matrix dimensions and exploit recurring structure. 1

That is enough to make the paper a substantive DreamCoder-lineage result. The important advance is not that a known photonic bound was reached. It is that a compression loop turned verified low-level decompositions into reusable, parameterized rules, and those rules survived changes in dimension and input structure. The next decisive experiment would connect that library to neural recognition or to hardware-constrained search. Until then, the paper is best read as evidence that DreamCoder-style library learning travels well, not as evidence that the full neurosymbolic induction loop has been solved in photonics.