CircleCI does not support checks for existence of a cache key without restoring the full cache. Save a tiny key in parallel with the cache to allow bailing out faster if the cache already exists. More documentation on the approach and the code I started from (thanks TzookB!) is here: https://tzookb.com/circleci-project-deepdive

circleci_command_for_cache_optimization.yml

commands:
  halt_if_cache_exists:
    description: Halt a build if a cache already exists, without downloading the entire cache.  Match only exact key. Pair with mark_cache_existence.
    parameters:
      category:
        description: friendly name of the sort of cache (e.g. bundle, src)
        type: string
      key:
        description: hash key where underlying data would be stored
        type: string
    steps:
      - restore_cache:
          key: n-cachecheck-v1-<<parameters.category>>-<<parameters.key>>
          name: Check if cache exists already for <<parameters.category>>
      - run:
          name: halt if cache exists for <<parameters.category>>
          command: |
            FILE=~/cachedflags/job.<<parameters.category>>.flag
            if test -f "$FILE"; then
                echo "$FILE exist"
                circleci step halt
            else
                echo "$FILE doesnt exist"
            fi
  mark_cache_existence:
    description: A command that will mark a cache key as existing. Pair with halt_if_cache_exists
    parameters:
      category:
        description: friendly name of the sort of cache (e.g. bundle, src)
        type: string
      key:
        description: exact hash key to check
        type: string
    steps:
      - run:
          name: Create flag file marking cache for <<parameters.category>> as existing
          command: mkdir -p ~/cachedflags/ && touch ~/cachedflags/job.<<parameters.category>>.flag
      - save_cache:
          name: Mark cache as existing for <<parameters.category>>
          key: n-cachecheck-v1-<<parameters.category>>-<<parameters.key>>
          paths:
            - ~/cachedflags/job.<<parameters.category>>.flag