diff --git a/gcc/cp/config-lang.in b/gcc/cp/config-lang.in
index a6c7883cc24..e34c392d208 100644
--- a/gcc/cp/config-lang.in
+++ b/gcc/cp/config-lang.in
@@ -52,6 +52,7 @@ gtfiles="\
 \$(srcdir)/cp/name-lookup.cc \
 \$(srcdir)/cp/parser.cc \$(srcdir)/cp/pt.cc \
 \$(srcdir)/cp/rtti.cc \
+\$(srcdir)/cp/search.cc \
 \$(srcdir)/cp/semantics.cc \
 \$(srcdir)/cp/tree.cc \$(srcdir)/cp/typeck2.cc \
 \$(srcdir)/cp/vtable-class-hierarchy.cc \
diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
index a4809f034dc..c761b73b771 100644
--- a/gcc/cp/pt.cc
+++ b/gcc/cp/pt.cc
@@ -151,7 +151,7 @@ static tree get_partial_spec_bindings (tree, tree, tree);
 static void tsubst_enum	(tree, tree, tree);
 static bool check_instantiated_args (tree, tree, tsubst_flags_t);
 static int check_non_deducible_conversion (tree, tree, unification_kind_t, int,
-					   struct conversion **, bool);
+					   struct conversion **, bool, bool);
 static int maybe_adjust_types_for_deduction (tree, unification_kind_t,
 					     tree*, tree*, tree);
 static int type_unification_real (tree, tree, tree, const tree *,
@@ -22315,7 +22315,8 @@ pack_deducible_p (tree parm, tree fn)
 static int
 check_non_deducible_conversions (tree parms, const tree *args, unsigned nargs,
 				 tree fn, unification_kind_t strict, int flags,
-				 struct conversion **convs, bool explain_p)
+				 struct conversion **convs, bool explain_p,
+				 bool noninst_only_p)
 {
   /* Non-constructor methods need to leave a conversion for 'this', which
      isn't included in nargs here.  */
@@ -22351,7 +22352,7 @@ check_non_deducible_conversions (tree parms, const tree *args, unsigned nargs,
 	  int lflags = conv_flags (ia, nargs, fn, arg, flags);
 
 	  if (check_non_deducible_conversion (parm, arg, strict, lflags,
-					      conv_p, explain_p))
+					      conv_p, explain_p, noninst_only_p))
 	    return 1;
 	}
 
@@ -22651,6 +22652,16 @@ fn_type_unification (tree fn,
 
  deduced:
 
+  /* As a refinement of CWG2369, check first and foremost non-dependent
+     conversions that we know are not going to induce template instantiation
+     (PR99599).  */
+  if (strict == DEDUCE_CALL
+      && incomplete
+      && check_non_deducible_conversions (parms, args, nargs, fn, strict, flags,
+					  convs, explain_p,
+					  /*noninst_only_p=*/true))
+    goto fail;
+
   /* CWG2369: Check satisfaction before non-deducible conversions.  */
   if (!constraints_satisfied_p (fn, targs))
     {
@@ -22664,7 +22675,8 @@ fn_type_unification (tree fn,
      as the standard says that we substitute explicit args immediately.  */
   if (incomplete
       && check_non_deducible_conversions (parms, args, nargs, fn, strict, flags,
-					  convs, explain_p))
+					  convs, explain_p,
+					  /*noninst_only_p=*/false))
     goto fail;
 
   /* All is well so far.  Now, check:
@@ -22899,7 +22911,7 @@ maybe_adjust_types_for_deduction (tree tparms,
 static int
 check_non_deducible_conversion (tree parm, tree arg, unification_kind_t strict,
 				int flags, struct conversion **conv_p,
-				bool explain_p)
+				bool explain_p, bool noninst_only_p)
 {
   tree type;
 
@@ -22921,6 +22933,50 @@ check_non_deducible_conversion (tree parm, tree arg, unification_kind_t strict,
     {
       bool ok = false;
       tree conv_arg = TYPE_P (arg) ? NULL_TREE : arg;
+      if (conv_p && *conv_p)
+	{
+	  /* This conversion was already computed earlier (when
+	     computing only non-instantiating conversions).  */
+	  gcc_checking_assert (!noninst_only_p);
+	  return unify_success (explain_p);
+	}
+      if (noninst_only_p)
+	{
+	  /* We're checking only non-instantiating conversions.
+	     A conversion may instantiate only if it's to/from a
+	     class type that has a constructor template/conversion
+	     function template.  */
+	  tree parm_nonref = non_reference (parm);
+	  tree type_nonref = non_reference (type);
+
+	  if (CLASS_TYPE_P (parm_nonref))
+	    {
+	      if (!COMPLETE_TYPE_P (parm_nonref)
+		  && CLASSTYPE_TEMPLATE_INSTANTIATION (parm_nonref))
+		return unify_success (explain_p);
+
+	      tree ctors = get_class_binding (parm_nonref,
+					      complete_ctor_identifier);
+	      for (tree ctor : lkp_range (ctors))
+		if (TREE_CODE (ctor) == TEMPLATE_DECL)
+		  return unify_success (explain_p);
+	    }
+
+	  if (CLASS_TYPE_P (type_nonref))
+	    {
+	      if (!COMPLETE_TYPE_P (type_nonref)
+		  && CLASSTYPE_TEMPLATE_INSTANTIATION (type_nonref))
+		return unify_success (explain_p);
+
+	      tree convs = lookup_conversions (type_nonref);
+	      for (; convs; convs = TREE_CHAIN (convs))
+		if (TREE_CODE (TREE_VALUE (convs)) == TEMPLATE_DECL)
+		  return unify_success (explain_p);
+	    }
+
+	  /* Checking this conversion definitely won't induce a template
+	     instantiation.  */
+	}
       if (conv_p)
 	/* Avoid recalculating this in add_function_candidate.  */
 	ok = (*conv_p
diff --git a/gcc/cp/search.cc b/gcc/cp/search.cc
index cd80f285ac9..9986eec4856 100644
--- a/gcc/cp/search.cc
+++ b/gcc/cp/search.cc
@@ -2582,6 +2582,10 @@ lookup_conversions_r (tree binfo, int virtual_depth, int virtualness,
   return my_virtualness;
 }
 
+/* A cache of the result of lookup_conversions.  */
+
+static GTY((cache)) type_tree_cache_map *conversions_cache;
+
 /* Return a TREE_LIST containing all the non-hidden user-defined
    conversion functions for TYPE (and its base-classes).  The
    TREE_VALUE of each node is the FUNCTION_DECL of the conversion
@@ -2594,12 +2598,15 @@ lookup_conversions_r (tree binfo, int virtual_depth, int virtualness,
 tree
 lookup_conversions (tree type)
 {
-  tree convs;
-
+  type = TYPE_MAIN_VARIANT (type);
   complete_type (type);
   if (!CLASS_TYPE_P (type) || !TYPE_BINFO (type))
     return NULL_TREE;
 
+  if (tree *c = hash_map_safe_get (conversions_cache, type))
+    return *c;
+
+  tree convs;
   lookup_conversions_r (TYPE_BINFO (type), 0, 0, NULL_TREE, NULL_TREE, &convs);
 
   tree list = NULL_TREE;
@@ -2618,6 +2625,7 @@ lookup_conversions (tree type)
 	}
     }
 
+  hash_map_safe_put<hm_ggc> (conversions_cache, type, list);
   return list;
 }
 
@@ -2798,3 +2806,5 @@ any_dependent_bases_p (tree type)
 
   return false;
 }
+
+#include "gt-cp-search.h"
diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-nondep4.C b/gcc/testsuite/g++.dg/cpp2a/concepts-nondep4.C
new file mode 100644
index 00000000000..d26783524f7
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp2a/concepts-nondep4.C
@@ -0,0 +1,21 @@
+// PR c++/99599
+// { dg-do compile { target c++20 } }
+
+struct foo_tag { };
+struct bar_tag { };
+
+template <class T>
+concept fooable = requires(T it) {
+  invoke_tag(foo_tag{}, it);
+};
+
+template<class T>
+void invoke_tag(foo_tag, T in);
+
+template<fooable T>
+void invoke_tag(bar_tag, T it);
+
+int main() {
+  invoke_tag(foo_tag{}, 2);
+  invoke_tag(bar_tag{}, 2);
+}
diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-nondep4a.C b/gcc/testsuite/g++.dg/cpp2a/concepts-nondep4a.C
new file mode 100644
index 00000000000..5ee214aa495
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp2a/concepts-nondep4a.C
@@ -0,0 +1,30 @@
+// PR c++/99599
+// { dg-do compile { target c++20 } }
+
+struct foo_tag {
+  foo_tag() = default;
+  foo_tag(int);
+  operator int();
+};
+
+struct bar_tag {
+  bar_tag() = default;
+  bar_tag(int);
+  operator int();
+};
+
+template <class T>
+concept fooable = requires(T it) {
+  invoke_tag(foo_tag{}, it);
+};
+
+template<class T>
+void invoke_tag(foo_tag, T in);
+
+template<fooable T>
+void invoke_tag(bar_tag, T it);
+
+int main() {
+  invoke_tag(foo_tag{}, 2);
+  invoke_tag(bar_tag{}, 2);
+}
