Limited Perfect Monotonical Surrogates constructed using low-cost recursive linkage discovery with guaranteed output

M. W. Przewozniczek; F. Chicano; R. Tinós; M. M. Komarnicki

cs.AIApr 13, 2026

Limited Perfect Monotonical Surrogates constructed using low-cost recursive linkage discovery with guaranteed output

Authors: M. W. Przewozniczek, F. Chicano, R. Tinós, M. M. Komarnicki

Organizations: Wroclaw Univ. of Science and Techn. Wroclaw, Poland · ITIS Software, University of Málaga Málaga, Spain · University of São Paulo Ribeirão Preto, Brazil

Abstract

Surrogates provide a cheap solution evaluation and offer significant leverage for optimizing computationally expensive problems. Usually, surrogates only approximate the original function. Recently, the perfect linear surrogates were proposed that ideally represent the original function. These surrogates do not mimic the original function. In fact, they are another (correct) representation of it and enable a wide range of possibilities, e.g., discovering the optimized function for problems where the direct transformation of the encoded solution into its evaluation is not available. However, many real-world problems can not be represented by linear models, making the aforementioned surrogates inapplicable. Therefore, we propose the Limited Monotonical Perfect Surrogate (LyMPuS), which overcomes this difficulty and enables the comparison of two solutions that differ by a single variable. Our proposition is suitable for limiting the cost of expensive local search procedures. The proposed surrogate is parameterless and can be trained on the fly without any separate surrogate-building step. It uses only the necessary fitness evaluations, and the already-paid costs are not wasted when the model is updated. Finally, it offers low-cost missing-linkage detection and low-cost linkage discovery, guaranteed to find a missing dependency in no more than $2\lceil\log_2(n)\rceil$ steps.

Figures & tables

Table 1.

G_{NM}

and LyMPuS for

f_{e1}

	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$	$x_{6}$
$x_{1}$	X	1	0	0	0	0
$x_{2}$	1	X	0	0	0	0
$x_{3}$	0	0	X	1	0	0
$x_{4}$	0	0	1	X	0	0
$x_{5}$	0	0	0	0	X	1
$x_{6}$	0	0	0	0	1	X

Table 2.

eG

discovered by eLyMPuS in Example 3.2 (missing dependencies are marked in red )

$x_{g}$	$C_{eG}^{g}$	$Pair.\mathchoice{\mbox{\boldmath$ \displaystyle x $}}{\mbox{\boldmath$ \textstyle x $}}{\mbox{\boldmath$ \scriptstyle x $}}{\mbox{\boldmath$ \scriptscriptstyle x $}}$	$C_{eG}^{g}(Pair.\mathchoice{\mbox{\boldmath$ \displaystyle x $}}{\mbox{\boldmath$ \textstyle x $}}{\mbox{\boldmath$ \scriptstyle x $}}{\mbox{\boldmath$ \scriptscriptstyle x $}})$	$b^{*}_{g}(Pair.\mathchoice{\mbox{\boldmath$ \displaystyle x $}}{\mbox{\boldmath$ \textstyle x $}}{\mbox{\boldmath$ \scriptstyle x $}}{\mbox{\boldmath$ \scriptscriptstyle x $}})$
$x_{1}$	$\{x_{2}\}$	01 10 10 01	1 *	$\{0\}$
		10 10 10 01	0 *	$\{1\}$
$x_{2}$	$\{x_{1}\}$	10 10 10 01	1* **	$\{0\}$
$x_{3}$	$\{x_{4}\}$	11 11 00 11	** 1 * **	$\{1\}$
		00 00 11 00	** 0 * **	$\{0\}$
$x_{4}$	$\{x_{3}\}$	01 10 01 10	** 1*	$\{0\}$

Table 3. eLyMPuS for Example 3.2

			Dep.										Linkage discovery (ratio [%])
	Succ	med. FFE until best	disc.	FIHC-eLyMPuS FFE cost				PXrLL FFE cost				InitPX	eLyMPuS		PXrLL	InitPX
Problem (size)	[%]	Func / Surr / ratio	[%]	Total	$b^{*}_{g}(\mathchoice{\mbox{\boldmath$ \displaystyle x $}}{\mbox{\boldmath$ \textstyle x $}}{\mbox{\boldmath$ \scriptstyle x $}}{\mbox{\boldmath$ \scriptscriptstyle x $}})$	Miss.	Disc.	Total	Regular	Miss.	Disc.	LL	FIHC	Circ	Disc	Disc
nkLand (800)	100	1.1E+7 / 8.0E+7 / 88	100	1.1E+7	7.6E+5	1.0E+7	6.1E+4	1.6E+5	8.1E+4	7.8E+4	1.9E+3	7.9E+2	3984	43	5 (28)	4 (80)
ISG (1936)	60	1.9E+7 / 4.8E+8 / 96	100	1.9E+7	1.9E+5	1.9E+7	7.0E+4	3.9E+5	2.9E+5	9.7E+4	3.2E+2	8.9E+2	3768	0	5 (77)	11 (95)
m3s (75)	90	1.4E+5 / 4.7E+4 / 25	93	2.1E+5	1.3E+5	7.6E+4	5.1E+3	1.6E+1	1.4E+1	2.0E+0	0.0E+0	1.9E+2	740	0	0 (-)	5 (91)
mkDec3 (82)	100	3.6E+4 / 3.4E+4 / 49	85	3.6E+4	1.6E+3	3.3E+4	1.3E+3	1.2E+2	3.8E+1	3.6E+1	2.1E+1	1.4E+2	129	0	1 (100)	4 (78)

Table 4. OLyMPuS – detailed results for chosen instances (median values reported). Full results: Tables S-II and S-II (supplementary material).

Panel of Figure 1 — Figure 1. Representative OLyMPuS runs. The increase of the best-found solution, discovered dependency percentage, and the FFE savings brought by eLyMPuS in the experiment run (X axis – FFE of the true function).

	OLyMPuS			P3			P3-FIHCwLL			P3-eLyMPuS			LT-GOMEA-FIHCwLL			LT-GOMEA-eLyMPuS
	Size	Succ	FFE	Size	Succ	FFE	Size	Succ	FFE	Size	Succ	FFE	Size	Succ	FFE	Size	Succ	FFE
nkLand	1000	83	1.8E+7	400	90	8.5E+6	600	93	7.2E+6	1000	83	9.0E+6	400	80	1.0E+7	1000	93	1.3E+7
ISG	1369	100	9.6E+6	1936	100	6.7E+6	1936	97	7.5E+6	1936	100	2.2E+6	1024	97	6.1E+6	1369	93	5.2E+6
m3s	75	90	1.4E+5	100	100	1.6E+5	100	97	2.1E+5	100	97	1.8E+5	75	97	1.3E+5	75	93	9.2E+4
mkBim10	322	100	3.6E+6	N/A	N/A	N/A	162	80	1.2E+7	82	100	2.5E+6	162	97	1.4E+7	162	100	9.4E+6
mkDec3	102	100	4.5E+4	102	100	5.8E+3	102	100	6.3E+3	102	100	5.5E+3	102	100	1.2E+4	102	100	1.0E+4

Table 5. General comparison. The largest problem size solved with success rate above 80% (median FFE until finding the best solution reported). Extended results: Tables S-VI and S-VII (supplementary material).

Panel of Figure 2 — Figure 2. Scalability for chosen problems

Surrogate Modeling

Surrogate modeling builds faster or more interpretable approximations of expensive simulations and black-box models.

See all 226 papers

When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design
Aug 2, 2026Shuangxiu, Ma, Wenhe +1Surrogate Modeling Surrogate-Assisted Optimization
Max · William G. Lowrie Department of Chemical and Biomolecular Engineering, The Ohio State University, Columbus, Ohio 43210, United States · Zachary +1
Parametric Nonconvex Optimization via Convex Surrogates
Apr 7, 2026Renzi Wang, Panagiotis Patrinos, Alberto BemporadNonconvex Optimization Surrogate-Assisted Optimization
IMT School for Advanced Studies, Lucca, Italy. · Department of Electrical Engineering ESAT-STADIUS, KU Leuven, Leuven, Belgium.
Frugal Bayesian Optimization: Scalable Surrogates for Data- and Resource-Limited Discovery
Jul 31, 2026Panagiotis Krokidas, Christoforos Rekatsinas, Vassilis Sioros +3Surrogate Modeling Bayesian Optimization
Institute of Informatics and Telecommunications, National Centre for Scientific Research "Demokritos", Agia Paraskevi, Greece. · Department of Mechanical Engineering and Aeronautics, University of Patras, Patras Greece. · Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece. +4

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

When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design

Shuangxiu, Ma, Wenhe, Zhao

Max · William G. Lowrie Department of Chemical and Biomolecular Engineering, The Ohio State University, Columbus, Ohio 43210, United States · Zachary+1

Surrogate Modeling Surrogate-Assisted Optimization Selection Bias Black-Box Model Auditing

Open paper AskPDF arXiv

Design campaigns in chemistry, materials science, and machine learning share a bottleneck: determining how good a candidate truly is requires an expensive evaluation - an experiment, a first-principles simulation, or a full training run. Machine-learning surrogates that predict these outcomes are increasingly used not only to propose candidates but to grade them, and even to feed their own predictions back into the search as though they were measurements. Through mathematical analysis validated on three exhaustively ground-truthed design tasks, we establish when this practice is safe, what any certificate of safety must cost, and when the substitution provably pays. Predictive accuracy cannot anchor trust: near-perfect R^2 is compatible with worst-possible selections, and screening N candidates inflates the over-prediction at the selected candidate by a quantifiable "selection tax" with matching upper and lower bounds. Safety follows instead from an architectural rule - predictions may propose and train without restriction, but every certified conclusion must rest on true evaluations - which is sufficient with no assumptions on the surrogate, and necessary, since admitting predictions into certification with the standing of measurements opens a deterministic self-confirmation failure mode. We derive the minimal criterion under which a model may act as an oracle (rank preservation, not accuracy), show that trust must be purchased through selection-aware audits that are optimal in query complexity, and prove a dichotomy fixing when audited surrogates cut certified evaluation cost. Across 432 surrogate fits over six task-regime conditions, the audit statistic tracks deployed search performance at Spearman rank correlation 0.80-0.99, while the rank correlation of R^2 with deployed regret falls as low as 0.33; audited screening reduces certified oracle cost by a measured factor of 25.

Abstract

Surrogate Modeling

Explore similar work

When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design

Parametric Nonconvex Optimization via Convex Surrogates

Frugal Bayesian Optimization: Scalable Surrogates for Data- and Resource-Limited Discovery