diff --git a/dvc/stage/cache.py b/dvc/stage/cache.py
--- a/dvc/stage/cache.py
+++ b/dvc/stage/cache.py
@@ -34,18 +34,26 @@ def _get_cache_hash(cache, key=False):
     )
 
 
-def _get_stage_hash(stage):
-    if not (stage.cmd and stage.deps and stage.outs):
-        return None
+def _can_hash(stage):
+    if stage.is_callback or stage.always_changed:
+        return False
+
+    if not all([stage.cmd, stage.deps, stage.outs]):
+        return False
 
     for dep in stage.deps:
         if not (dep.scheme == "local" and dep.def_path and dep.get_hash()):
-            return None
+            return False
 
     for out in stage.outs:
         if out.scheme != "local" or not out.def_path or out.persist:
-            return None
+            return False
 
+    return True
+
+
+def _get_stage_hash(stage):
+    assert _can_hash(stage)
     return _get_cache_hash(to_single_stage_lockfile(stage), key=True)
 
 
@@ -136,13 +144,10 @@ def _uncached_outs(self, stage, cache):
                     yield out
 
     def save(self, stage):
-        if stage.is_callback or stage.always_changed:
+        if not _can_hash(stage):
             return
 
         cache_key = _get_stage_hash(stage)
-        if not cache_key:
-            return
-
         cache = to_single_stage_lockfile(stage)
         cache_value = _get_cache_hash(cache)
 
@@ -167,7 +172,7 @@ def save(self, stage):
         self.tree.move(PathInfo(tmp), path)
 
     def restore(self, stage, run_cache=True, pull=False):
-        if stage.is_callback or stage.always_changed:
+        if not _can_hash(stage):
             raise RunCacheNotFoundError(stage)
 
         if (
diff --git a/dvc/stage/run.py b/dvc/stage/run.py
--- a/dvc/stage/run.py
+++ b/dvc/stage/run.py
@@ -139,7 +139,7 @@ def run_stage(stage, dry=False, force=False, checkpoint_func=None, **kwargs):
             stage.repo.stage_cache.restore(stage, **kwargs)
             return
         except RunCacheNotFoundError:
-            pass
+            stage.save_deps()
 
     run = cmd_run if dry else unlocked_repo(cmd_run)
     run(stage, dry=dry, checkpoint_func=checkpoint_func)

diff --git a/tests/unit/stage/test_cache.py b/tests/unit/stage/test_cache.py
--- a/tests/unit/stage/test_cache.py
+++ b/tests/unit/stage/test_cache.py
@@ -208,14 +208,22 @@ def _mode(path):
     assert _mode(cache_file) == file_mode
 
 
-def test_always_changed(mocker):
-    from dvc.repo import Repo
-    from dvc.stage import Stage
+@pytest.mark.parametrize(
+    "kwargs",
+    [
+        {},
+        {"cmd": "cmd"},
+        {"cmd": "cmd", "deps": ["path"]},
+        {"cmd": "cmd", "outs": ["path"]},
+        {"always_changed": True},
+    ],
+)
+def test_unhashable(tmp_dir, dvc, mocker, kwargs):
+    from dvc.stage import Stage, create_stage
     from dvc.stage.cache import RunCacheNotFoundError, StageCache
 
-    repo = mocker.Mock(spec=Repo)
-    cache = StageCache(repo)
-    stage = Stage(repo, always_changed=True)
+    cache = StageCache(dvc)
+    stage = create_stage(Stage, path="stage.dvc", repo=dvc, **kwargs)
     get_stage_hash = mocker.patch("dvc.stage.cache._get_stage_hash")
     assert cache.save(stage) is None
     assert get_stage_hash.not_called

run-cache: `restore` does not check if stage has outs or not
```bash
#! /bin/bash

set -e
set -x

cd "$(mktemp -d)"
git init && dvc init

echo 'var: foo' > params.yaml

# create a stage without any outputs
dvc run -v -n echo -p var "echo hello world"
 
# change `cmd` so that it's not cached
# and, `-f` to not throw duplicate stage error
dvc run -f -v -n echo -p var "echo hello" 
```

#### Analysis
This happens because it seems we are not skipping if the stage does not have any outputs.

tests/unit/stage/test_cache.py::test_unhashable[kwargs0]
tests/unit/stage/test_cache.py::test_unhashable[kwargs1] tests/unit/stage/test_cache.py::test_unhashable[kwargs4]