Instruction Set and Language for Symbolic Regression

Ezequiel Lopez-Rubio; Mario Pascual-Gonzalez

cs.CLMar 23, 2026

Instruction Set and Language for Symbolic Regression

Authors: Ezequiel Lopez-Rubio, Mario Pascual-Gonzalez

Organizations: Department of Computer Languages and Computer Science University of Málaga Bulevar Louis Pasteur, 35 29071 Málaga, Spain · ITIS Software. Universidad de Málaga. C/ Arquitecto Francisco Peñalosa 18, 29010, Málaga, Spain

Abstract

A fundamental but largely unaddressed obstacle in Symbolic regression (SR) is structural redundancy: every expression DAG with admits many distinct node-numbering schemes that all encode the same expression, each occupying a separate point in the search space and consuming fitness evaluations without adding diversity. We present IsalSR (Instruction Set and Language for Symbolic Regression), a representation framework that encodes expression DAGs as strings over a compact two-tier alphabet and computes a pruned canonical string -- a complete labeled-DAG isomorphism invariant -- that collapses all the equivalent representations into a single canonical form.

Figures & tables

Label $\ell$	Type	Arity	Evaluation
+	Add	variadic ( ${\geq}2$ )	$\sum_{u\in N^{-}(v)}\mathrm{eval}(u)$ (commutative)
	Mul	variadic ( ${\geq}2$ )	$\prod_{u\in N^{-}(v)}\mathrm{eval}(u)$ (commutative)
g	Neg	unary (1)	$-\mathrm{eval}(u)$
i	Inv	unary (1)	$1\;/\;\mathrm{eval}(u)$ $\dagger$
s	Sin	unary (1)	$\sin(\mathrm{eval}(u))$
c	Cos	unary (1)	$\cos(\mathrm{eval}(u))$

Table 1: IsalSR operation types, label characters, arities, and evaluation semantics. Operations marked

\dagger

use a numerically protected implementation. Pow is the only binary non-commutative operation: its operand order is given by

\sigma(v)

(edge-insertion order), with

\sigma(v)[0]

as the base and

\sigma(v)[1]

as the exponent. Neg and Inv are the unary decomposition operators that encode subtraction and division commutatively (see § 2.1 ).

Algorithm S2D

(w,\,m)

Input: instruction string

w

; number of variables

m\geq 1

Output: labeled DAG

D=(V,E,\ell,\delta,\sigma)

// Initialization

Create

m

Var nodes

x_{1},\ldots,x_{m}

with IDs

0,\ldots,m{-}1

; set

E\leftarrow\emptyset

;

\sigma(v)\leftarrow[]

for all

v

Insert

x_{1},\ldots,x_{m}

into CDLL

L

in variable-index order

p\leftarrow\mathtt{ptr}(x_{1})

;

q\leftarrow\mathtt{ptr}(x_{1})

Table 2: Pseudocode for the String-to-DAG (S2D) algorithm. Each node

v

maintains an ordered input list

\sigma(v)

; edges are appended to it in insertion order, establishing operand semantics for non-commutative binary nodes.

Figure 1: String-to-DAG execution for the canonical string VcVspv*pv+PpcnnC . The DAG grows incrementally as each instruction inserts labeled nodes ( V / v ) or directed edges ( C / c ), with primary (

\pi

) and secondary (

\sigma

) pointers navigating the circular doubly linked list.

Figure 2: DAG-to-String encoding of

\sin(x_{0})\cdot x_{1}+\cos(x_{0})

via greedy traversal from

x_{0}

. Ghost nodes (dashed) indicate parts not yet encoded; the emitted token sequence converges to the canonical string as all nodes and edges are visited.

Algorithm D2S

(D,\,m)

Input: labeled DAG

D=(V,E,\ell,\delta)

; number of variables

m

Output: IsalSR instruction string

w

w\leftarrow\varepsilon

; Create empty output DAG

D^{\prime}

;

\mathtt{i2o}\leftarrow\{\}

;

\mathtt{o2i}\leftarrow\{\}

Map all

m

Var nodes from

D

D^{\prime}

in variable-index order; insert into CDLL

L

p\leftarrow\mathtt{ptr}(x_{1})

;

q\leftarrow\mathtt{ptr}(x_{1})

N_{\mathrm{left}}\leftarrow|V|-m

;

E_{\mathrm{left}}\leftarrow|E|

Table 3: Pseudocode for the DAG-to-String (D2S) algorithm.

\mathtt{moves}(a)

: emits

|a|

copies of N (if

a{>}0

) or P (if

a{<}0

\mathtt{moves}_{s}(b)

: analogously n / p for the secondary pointer.

Algorithm PrunedCanonical

(D,\,m)

Input: labeled DAG

D=(V,E,\ell,\delta,\sigma)

; number of variables

m

Output: pruned canonical string

w^{**}_{D}

D\leftarrow\mathtt{normalize\_const\_creation}(D)

// redirect all Const creation edges to

x_{1}

Precompute

\tau(v)

for all

v\in V

O(|V|(|V|+|E|))

Initialize

D^{\prime}

L

\mathtt{i2o}

\mathtt{o2i}

p

q

as in D2S

return

\textsc{PCSstep}(D,D^{\prime},L,p,q,\mathtt{i2o},\mathtt{o2i},|V|{-}m,|E|,\varepsilon,\tau)

Table 4: Pseudocode for the Pruned Canonical String algorithm. PCSstep is called recursively and uses in-place mutation of

D^{\prime}

L

, and the index maps, with explicit undo on each backtrack step.

\mathtt{eligible}(u,c)

holds iff

c

is not a binary non-commutative node with a pre-existing first operand other than

u

Name	Expression $f(x)$ or $f(x,y)$	$m$	Input range
Nguyen-1	$x^{3}+x^{2}+x$	1	$[-1,1]$
Nguyen-2	$x^{4}+x^{3}+x^{2}+x$	1	$[-1,1]$
Nguyen-3	$x^{5}+x^{4}+x^{3}+x^{2}+x$	1	$[-1,1]$
Nguyen-4	$x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x$	1	$[-1,1]$
Nguyen-5	$\sin(x^{2})\cos(x)-1$	1	$[-1,1]$
Nguyen-6	$\sin(x)+\sin(x+x^{2})$	1	$[-1,1]$

Table 5: Nguyen symbolic regression benchmarks, following the configuration of Liu et al. (2025) . Training:

20

uniform samples; testing:

100

uniform samples; seed

42

ID	Expression	$m$	Variable ranges
I.6.20a	$e^{-\theta^{2}/2}/\!\sqrt{2\pi}$	1	$\theta\in[1,3]$
I.12.1	$\mu\,N_{s}$	2	$[1,5]^{2}$
I.25.13	$q/C$	2	$[1,3]^{2}$
I.34.27	$\hbar\,\omega$	2	$[1,5]^{2}$
I.39.10	$p_{r}V/2$	2	$[1,5]^{2}$
II.3.24	$p\,r/(4\pi)$	2	$[1,5]^{2}$

Table 6: AI Feynman benchmark subset, following the selection and variable ranges of Liu et al. (2025) . Data:

200

samples,

80

20

train/test split, seed

42

	Experiment	$k$	$m$	$N$	Timeout	Total
P1–P4	Property validation	—	$1$ – $3$	5,000/ $m$	2 s	15,000
P5	Search space	$1$ – $12$	$1$ – $2$	${\sim}40$ /config	5 s	961
	Scalability	$1$ – $15$	$1$ – $3$	200/config	120 s	9,000
	Shortest path	—	$1$ – $2$	5 pairs	—	5
	Neighbourhood	—	$1$	357 neighbours	5 s	357

Table 7: Summary of experiment parameters.

k

: internal nodes;

m

: input variables;

N

: samples per configuration. All experiments except the two illustrative ones run on the Picasso supercomputer.

Figure 3: Round-trip property for the Nguyen-1 benchmark (

x_{0}^{3}+x_{0}^{2}+x_{0}

). Each row applies a different DAG-to-String (D2S) algorithm, followed by String-to-DAG (S2D) reconstruction. Columns 0, 6 : original and reconstructed DAGs (isomorphic,

\cong

). Columns 1–2 : D2S progressively encodes the DAG; ghost (dashed) nodes and edges indicate parts not yet encoded, while the instruction string builds up left-to-right. Column 3 : the complete instruction string (

w^{*}

for canonical,

w

for greedy). Columns 4–5 : S2D rebuilds the DAG from the string. The canonical and pruned algorithms produce identical strings (

|w^{*}|{=}19

>

99.97% agreement), while the greedy algorithm yields a longer encoding (

|w|{=}23

+

21%), yet all three round-trip to isomorphic DAGs.

Figure 4: Property P3 (canonical invariance and idempotence) for

\sin(x_{0})+\cos(x_{0})

. The original DAG

D

is canonicalized to produce

w^{**}=\texttt{VcVspv+Ppc}

, then decoded via S2D to reconstruct

D^{\prime\prime}

, which is structurally isomorphic to

D

( invariance :

D\cong D^{\prime\prime}

). Applying canonicalization a second time yields

w^{**^{\prime}}=w^{**}

( idempotence ), confirming that the canonical string is a fixed point of the compose-and-recanonicalize map. Colour-coded token blocks show the instruction string at each transformation step.

Figure 5: Shortest Levenshtein path between

\cos(x_{0})+x_{0}

( V+VcPnc ) and

\cos(x_{0})+1

( VcVkpv+Ppc ) in the canonical string space (

d_{\mathrm{Lev}}=6

). Each step applies one character-level edit (substitution or insertion) to the current string. All intermediate strings produce valid expression DAGs, progressing through simplified

\cos(x_{0})

forms—including a

\cos(\cos(x_{0}))

detour at Step 4—before reaching the target. Below each DAG: the corresponding IsalSR instruction string (colour-coded by token type) and the mathematical expression.

Figure 6: Neighbourhood structure in the canonical string space around

G_{0}:\sin(x_{0})+\cos(x_{0})

(canonical string VcVspv+Ppc ). Each neighbour is obtained by a single Levenshtein edit (substitution, insertion, or deletion) on the canonical string, followed by re-canonicalization. The

d

labels indicate the Levenshtein distance between the neighbour’s canonical string and the base. Substitution neighbours (

d{=}1

) change only the combinator operation (

+{\to}\times

+{\to}-

+{\to}\div

), preserving the operand structure. Insertion and deletion neighbours produce structurally different DAGs with varying distances. Of the 132 valid Lev-1 perturbations, only 38 yield distinct canonical forms (71.2% redundancy), illustrating the

\Theta(k!)

search-space reduction.

Expression	$m$	$\|V\|$	$\|E\|$	Depth	P1	P2	P3	P4	$\|w^{**}\|$
Nguyen-1	1	6	9	3	✓	✓	✓	✓	19
Nguyen-5	1	8	10	5	✓	✓	✓	✓	26
Nguyen-7	1	9	12	5	✓	✓	✓	✓	32
Nguyen-8	1	3	3	2	✓	✓	✓	✓	7
Nguyen-9	2	7	7	4	✓	✓	✓	✓	19
Nguyen-10	2	6	6	2	✓	✓	✓	✓	16

Table 8: Deterministic validation of P1–P4 on benchmark expressions.

|V|

: node count;

|E|

: edge count;

|w^{**}|

: pruned canonical string length.

$m$	Evaluated	Pass	Rate	$95\%$ CI
1	3,004	3,004	100%	$[99.88\%,\;100\%]$
2	3,062	3,061	99.97%	$[99.82\%,\;100\%]$
3	3,062	3,060	99.93%	$[99.74\%,\;100\%]$
All	9,128	9,125	99.97%	$[99.89\%,\;100\%]$

Table 9: P3 pass rates by number of input variables

m

. Clopper–Pearson exact

95\%

confidence intervals.

Figure 7: Empirical validation of the

\Theta(k!)

search-space reduction. For each of

961

random expression DAGs with

k

internal nodes (

m\in\{1,2\}

variables), all

k!

permutations of internal node IDs were applied (exhaustively for

k\leq 8

;

50{,}000

sampled for

k>8

), producing structurally distinct labeled DAGs that encode the same mathematical expression. (a) Number of distinct representations (node numberings modulo automorphisms) per expression, compared with the theoretical

k!

curve (dashed). For

k\leq 8

, the exhaustive box plots sit on the

k!

line across five orders of magnitude, confirming that the equivalence class size equals

k!/\lvert\mathrm{Aut}(D)\rvert

. For

k>8

, sampled counts are lower bounds. The red horizontal line at

y=1

marks the result after canonicalization: all equivalent representations collapse to a single canonical string (shaded region = eliminated redundancy). (b) Normalized ratio of measured distinct representations to

k!

for the exhaustive range (

k\leq 8

). The majority of DAGs achieve the full

k!

bound (ratio

=1.0

); outliers below

1.0

correspond to DAGs with non-trivial automorphism groups, where

n_{\text{distinct}}=k!/\lvert\mathrm{Aut}(D)\rvert

as predicted by the Orbit-Stabilizer theorem. Canonical invariance was verified at

100\%

across all

961

DAGs.

Pair	Expression 1	Expression 2	Relationship	$d_{\mathrm{Lev}}$
A	$\sin(x)$	$x^{2}+x$	Different structure	10
B	$\sin(x)+\cos(x)$	$\sin(x)\cdot\cos(x)$	Same operands, different combinator	1
C	$x^{2}$	$x^{3}+x^{2}+x$	Containment	12
D	$\exp(x)$	$\log(x)$	Same topology, different unary op	1
E	$\sin(x)+y^{2}$	$\cos(x)\cdot y$	Mixed two-variable	12

Table 10: Levenshtein distances between pruned canonical strings for five expression pairs. Each pair is designed to isolate a specific structural relationship.

Operation	$N_{\mathrm{total}}$	$N_{\mathrm{valid}}$	$N_{\mathrm{unique}}$	Redundancy
Deletion	10	5	3	40.0%
Substitution	160	60	35	41.7%
Insertion	187	67	18	73.1%
All	357	132	38	71.2%

Table 11: Distance-1 neighbourhood of

\sin(x_{0})+\cos(x_{0})

(

w^{**}=\texttt{VcVspv+Ppc}

), disaggregated by edit operation.

N_{\mathrm{total}}

: number of Lev-1 strings;

N_{\mathrm{valid}}

: strings that produce a valid non-trivial DAG;

N_{\mathrm{unique}}

: distinct canonical forms among valid strings.

Explore similar work

InsightSR: Refining Symbolic Regression Search Spaces via Parallel Semantic and Structural LLM Guidance
Aug 26, 2026Yating Ling, Wenjing Cun, Zhitang ChenSymbolic Regression Large Language Model-Guided Scientific Discovery
Symbolic Regression via Latent Iterative Refinement
May 26, 2026Xieting Chu, Sriram Vishwanath, Vijay GaneshLatent Variable Models Amortized Inference
Georgia Institute of Technology
Deep Divide-and-Reduce in Symbolic Regression
Jul 26, 2026Yusong Deng, Yanjie Li, Xin Ning +6Symbolic Regression
School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences, Beijing, China · AnnLab, Institute of Semiconductors, Chinese Academy of Sciences, Beijing, China · Zhongguancun Academy, Beijing, China

Aug 26, 2026J/K move · Enter open · S save

InsightSR: Refining Symbolic Regression Search Spaces via Parallel Semantic and Structural LLM Guidance

Yating Ling, Wenjing Cun, Zhitang Chen

Symbolic Regression Large Language Model-Guided Scientific Discovery Genetic Programming

Open paper AskPDF arXiv

Symbolic regression (SR) seeks to discover parsimonious mathematical laws from observational data, yet conventional approaches often struggle with the vast combinatorial search space of physically meaningful expressions. We present InsightSR, a framework that embeds Large Language Models (LLMs) as a guiding layer around the PySR genetic programming engine. Rather than relying on LLMs to generate expressions directly, InsightSR uses LLMs to progressively transform the search space itself through two complementary pathways: a Semantic Seed Pathway that proposes dimensionally consistent functional skeletons, and a Structural Feature Pathway that recommends nonlinear feature transformations. These transformations accumulate over iterations, broadening the input space and shifting the symbolic search from constructing deep expression trees over raw variables to assembling shallow trees over a rich, semantically informed feature set. A post-generation feedback loop evaluates candidates, categorizes features by their empirical utility, and refines the guidance for the next iteration, transforming the discovery process from open-ended generation into iterative, self-correcting refinement. Across three benchmarks, InsightSR achieves a 95% exact recovery rate on the Feynman benchmark and 80.18% accuracy on the LLM-SRBench LSR-Transform task, substantially outperforming state-of-the-art genetic programming and neural-symbolic methods while maintaining strong out-of-distribution generalization on real-world datasets.

Abstract

Explore similar work

InsightSR: Refining Symbolic Regression Search Spaces via Parallel Semantic and Structural LLM Guidance

Symbolic Regression via Latent Iterative Refinement

Deep Divide-and-Reduce in Symbolic Regression