diff --git a/lisp/progmodes/xref.el b/lisp/progmodes/xref.el
index 6677b4f004..b2f82f1889 100644
--- a/lisp/progmodes/xref.el
+++ b/lisp/progmodes/xref.el
@@ -1751,15 +1751,7 @@ xref-matches-in-files
        (remote-id (file-remote-p dir))
        ;; The 'auto' default would be fine too, but ripgrep can't handle
        ;; the options we pass in that case.
-       (grep-highlight-matches nil)
-       (command (grep-expand-template (cdr
-                                       (or
-                                        (assoc
-                                         xref-search-program
-                                         xref-search-program-alist)
-                                        (user-error "Unknown search program `%s'"
-                                                    xref-search-program)))
-                                      (xref--regexp-to-extended regexp))))
+       (grep-highlight-matches nil))
     (when remote-id
       (require 'tramp)
       (setq files (mapcar
@@ -1770,25 +1762,56 @@ xref-matches-in-files
     (when (file-name-quoted-p (car files))
       (setq files (mapcar #'file-name-unquote files)))
     (with-current-buffer output
-      (erase-buffer)
       (with-temp-buffer
         (insert (mapconcat #'identity files "\0"))
-        (setq default-directory dir)
-        (setq status
-              (xref--process-file-region (point-min)
-                                         (point-max)
-                                         shell-file-name
-                                         output
-                                         nil
-                                         shell-command-switch
-                                         command)))
-      (goto-char (point-min))
-      (when (and (/= (point-min) (point-max))
-                 (not (looking-at grep-re))
-                 ;; TODO: Show these matches as well somehow?
-                 (not (looking-at "Binary file .* matches")))
-        (user-error "Search failed with status %d: %s" status
-                    (buffer-substring (point-min) (line-end-position))))
+        (let* ((default-directory dir)
+               (xref-search-program-alist xref-search-program-alist)
+               (program (if (version<= "27" emacs-version)
+                            (with-connection-local-variables
+                             xref-search-program)
+                          xref-search-program)))
+          ;; In case `xref-search-program' is not installed on a
+          ;; remote system, we will speculatively try to start a
+          ;; different searcher to see if it is installed and works.
+          (catch 'ok
+            (while xref-search-program-alist
+              (with-current-buffer output
+                (erase-buffer))
+              (setq status
+                    (xref--process-file-region
+                     (point-min) (point-max)
+                     shell-file-name
+                     output nil shell-command-switch
+                     (grep-expand-template
+                      (or (alist-get program xref-search-program-alist)
+                          (user-error "Unknown search program `%s'"
+                                      program))
+                      (xref--regexp-to-extended regexp))))
+              (with-current-buffer output
+                (goto-char (point-min))
+                (unless (and (/= (point-min) (point-max))
+                             (not (looking-at grep-re))
+                             ;; TODO: Show these matches as well somehow?
+                             (not (looking-at "Binary file .* matches")))
+                  (when (and (not (eq program xref-search-program))
+                             (version<= "27" emacs-version))
+                    ;; If possible and necessary, save whatever program
+                    ;; was found as a connection local variable.
+                    (let* ((host (file-remote-p default-directory 'host))
+                           (profile (intern (concat "xref-remote-" host))))
+                      (connection-local-set-profile-variables
+                       profile `((xref-search-program . ,program)))
+                      (connection-local-set-profiles
+                       (list :machine host) profile)))
+                  (throw 'ok t)))
+              (setq xref-search-program-alist
+                    (remq (assq program xref-search-program-alist)
+                          xref-search-program-alist)
+                    program (caar xref-search-program-alist)))
+            (with-current-buffer output
+              (user-error "Search failed with status %d: %s" status
+                          (buffer-string)
+                          (buffer-substring (point-min) (line-end-position)))))))
       (while (re-search-forward grep-re nil t)
         (push (list (string-to-number (match-string line-group))
                     (match-string file-group)