Trained to depth three. It solves depth nine.

2026-07-20 ~1,108 words

LightSearch is a program synthesizer. You hand it a few input/output pairs, and it returns a program that reproduces them exactly, found by best-first search over partial candidates. What it learns is narrower than what it produces. It never learns programs, and is never asked to score one. It learns how each instruction transforms a state, one step at a time. From those per-transition predictions a compact geometry emerges: a space in which the discrete instructions become local moves, and distance to the target is legible. Search leans on that geometry.

A model trained to guess whole programs is doing pattern recognition, and pattern recognition is uninformed exactly where the program grows deep enough to be interesting. A model that learns local structure knows what is adjacent to where it stands. Composition is left to search. The model is never asked what the answer is, only what a step does, and a step is a much easier thing to be right about.

The domain

The test domain is a scalar one. A state is a single float. The instruction set has ten unary operations on the unit interval.

f_{0} (x) = 1 - x

f_{5} (x) = sin (π x)

f_{1} (x) = x^{2}

f_{6} (x) = tanh (x)

f_{2} (x) = (x + \frac{1}{2}) mod 1

f_{7} (x) = ∣ 2 x - 1 ∣

f_{3} (x) = e^{x - 1}

f_{8} (x) = x^{3}

f_{4} (x) = ln (1 + x)

f_{9} (x) = \frac{1}{1 + x}

A program is a chain of these operations. Chain length grows exponentially with depth, so depth nine is a billion candidate programs. The search is ordinary best-first over partial chains.

Trained shallow, tested deep

The model never learns programs. It learns single transitions: what one instruction does to one state. That is all the gradient ever sees, one step at a time.

For the results below, the training curriculum was capped at depth three. The model was never shown the task distribution at any greater depth, so depths four through nine sit entirely outside what it trained on. It solves them anyway. Because what it learned is per-transition and local, going deeper is just more search, not a distribution it needs to have seen.

Results

Thirty-two tasks at each depth. Brute-force branching factor is ten. The learned heuristic holds the effective branching factor under 3.5 the whole way down, and solves every task at every depth.¹1 Nodes are pops from the priority queue, the states actually expanded, not everything pushed onto it.

depth	solved	avg nodes	avg EBF	nodes/s
2	32/32	2.0	1.41	473
3	32/32	2.9	1.43	420
4	32/32	10.8	1.76	1,118
5	32/32	88.5	2.23	2,774
6	32/32	855	2.76	3,209
7	32/32	4,650	2.99	2,440
8	32/32	59,755	3.32	2,361
9	32/32	383,087	3.44	1,959

Table 1. Thirty-two tasks per depth, exact solutions only.

Depth nine is the one I care about. Every task ran to a real solution, with no budget cutoff: 32 of 32 solved, 383,087 node expansions out of a billion-program space. That is under four hundredths of a percent, at a branching factor of ten.

One solve

Take one concrete solve. Eight input-output pairs, and an absolute tolerance of one thousandth.

0.000 0.125 0.250 0.375 0.500 0.625 0.750 0.875 \mapsto \mapsto \mapsto \mapsto \mapsto \mapsto \mapsto \mapsto 0.273 0.014 0.591 0.991 0.482 0.060 0.000 0.008

The solver returns a depth-nine chain of instructions. Every target lands within tolerance.

(sin (π 2 sin (π (((e^{t a n h (x) - 1})^{2} + \frac{1}{2}) mod 1 + \frac{1}{2}) mod 1) - 1))^{2}

Adding a domain

To point LightSearch at a new problem, you implement a handful of traits: a codec, an instruction set, a particle encoder, a residual, and a curriculum sampler.

/// Three views of a state: native, differentiable, and operational.
trait Codec {
    fn encode(&self, s: &State) -> Symbols;
    fn decode(&self, s: &Symbols) -> ProtoState;
    fn project(&self, p: &ProtoState) -> State;
}
/// The deterministic instructions the solver composes into programs.
trait ISA {
    fn size(&self) -> usize;
    fn transform(&self, op: usize, s: &Symbols) -> Symbols;
}
/// Lift a state into the continuous space where adjacency is measured.
trait ParticleEncoder {
    fn particlize(&self, s: &Symbols) -> Particle;
}
/// Exact goal test. Used only to declare a state solved, never to guide search.
trait ResidualFn {
    fn residual(&self, a: &State, b: &State) -> f64;
    fn is_solved(&self, r: f64) -> bool;
}
/// Sample training tasks of bounded depth.
trait Curriculum {
    fn generate(&self, depth: u32) -> Task;
}

The solver handles the rest. It runs a curriculum that deepens as the heuristic improves, so training always sits just past the edge of what the model can already reach, where the information gained per unit of compute is highest.

Where it goes next

The open problem is the instruction set itself: everything so far assumes the instructions are handed to you. For a domain where they are not, LightSearch has to grow its own, a dynamic instruction set that adapts to the domain it is dropped into. That means relaxing the state into a differentiable form so instructions can be learned by gradient and then projected back to something discrete. That is the piece I am building now, and it is the prerequisite for pointing any of this at ARC-AGI.