Sitemap Crawling vs Link Discovery: Coverage and Cost

Two Crawl Models, One Bill: How Sitemap-First and Link-Following Differ

A sitemap-first crawl reads the site’s own manifest (sitemap.xml) and fetches what it declares; a link-following crawl starts at a seed page, extracts links, and lets the frontier grow organically. Same destination site, same data goal, radically different cost profiles.

The difference that matters for your bill is this: a sitemap-first crawl has a known, finite request count before you start. A link-following crawl does not. And under metered billing, every fetch gets counted — including the ones that return a 404, the ones that land on a redirect you didn’t want, and the ones that fetch a document you already have. If you haven’t thought about how failed requests get billed, this is the article that will make you think about it.

SITEMAP-FIRST                              LINK-FOLLOWING

store.example.com/sitemap.xml              store.example.com/  (seed page)
          |                                          |
          v                                          v
   parse <loc> entries                        extract hrefs from HTML
          |                                          |
          v                                          v
   queued URL list (fixed size)               crawl frontier (grows per fetch)
          |                                          |
          v                                          v
   fetch each URL                             fetch -> extract more hrefs -> fetch
   N requests, known before start             N unknown until the crawl ends

Dimension	Sitemap-first	Link-following
Seed source	sitemap.xml (site-declared)	One or more seed pages (you pick)
Discovery mechanism	XML manifest parsing	href extraction from fetched HTML
Dedup burden	Low — sitemap is usually already deduplicated	High — parameterized URLs, canonical variants, redirect targets all queue up
Coverage ceiling	Every URL the site declares, including orphans	Only URLs reachable from seeds via internal links
Typical billed-request profile	Fixed N fetches; waste = stale entries returning 404	Unbounded-ish; waste = redirects, duplicates, disallowed paths
Freshness signal	lastmod metadata (trust it at your peril)	Live link structure changes

Neither model is strictly cheaper. Which one wins depends on two numbers specific to your target site: its sitemap rot rate and its link duplication factor. The rest of this article is about measuring both before you spend money.

Coverage Math: Why Sitemaps Find Orphan Pages That Links Never Reach

A link-following crawler can only reach pages that something links to. That sounds obvious, but the consequence is not: any page with zero inbound internal links is invisible to link discovery, forever, no matter how many levels deep you crawl. These orphan pages are more common than you’d think — products removed from category listings but still live, landing pages from finished campaigns, pages reachable only through search.

Sitemaps don’t have this problem. The site declares the URL, you fetch it, done. Here’s a sitemap for a store that includes a product page no longer linked from any navigation or category page:

<urlset xmlns="http://www.sitemaps.org/schemas/sitemap/0.9">
  <url>
    <loc>https://store.example.com/products/wool-overcoat</loc>
    <lastmod>{{ product.updated_at.isoformat() }}</lastmod>
  </url>
  <url>
    <loc>https://store.example.com/products/classic-denim-jacket</loc>
    <lastmod>{{ product.updated_at.isoformat() }}</lastmod>
  </url>
  <!-- orphan: delisted from all categories, still live, still in sitemap -->
  <url>
    <loc>https://store.example.com/products/discontinued-linen-shirt</loc>
    <lastmod>{{ product.updated_at.isoformat() }}</lastmod>
  </url>
</urlset>

A link-following crawl starting at the homepage never fetches that linen shirt page. A sitemap-first crawl fetches it on run one.

Run the coverage math on a hypothetical 10,000-URL site:

Page class	Est. share	Sitemap-first finds	Link-following finds
Linked pages (in nav/categories)	8,500	Yes	Yes
Orphan pages (no inbound internal links)	500	Yes	No
Stale sitemap entries (deleted, 404)	1,000	Fetches them, wasted	Never touches them

Read that last row carefully, because it cuts both ways. The sitemap gets you 9,000 valid documents where link-following gets you 8,500. But it also bills you for 1,000 fetches that return nothing. Coverage and waste are the same mechanism — trusting the site’s declaration — viewed from two angles. There is no configuration where you get the extra 500 orphans without also eating the 1,000 dead URLs. That trade is the entire subject of this article.

Freshness Trade-offs: Sitemap lastmod Trust vs Live Link Structure

Sitemaps usually ship a lastmod field per URL. In theory, you skip URLs whose lastmod hasn’t changed since your last crawl and save a fortune on re-fetches. In practice, lastmod is generated by whatever process builds the sitemap, and plenty of those processes stamp every entry with the build time, not the actual content change time. A sitemap regenerated nightly can show 10,000 “modified” URLs where three actually changed.

The fix is sampling-based verification: trust lastmod, but spot-check a random sample against a content hash from your previous crawl.

import hashlib
import random
import requests

API = "https://api.finedata.ai"
HEADERS = {"Authorization": "Bearer fd_your_api_key"}

def content_hash(url: str) -> str:
    resp = requests.post(
        f"{API}/api/v1/scrape",
        headers=HEADERS,
        json={
            "url": url,
            "formats": ["text"],
            "only_main_content": True,
        },
        timeout=180,
    )
    resp.raise_for_status()
    text = resp.json()["data"]["text"]
    return hashlib.sha256(text.encode()).hexdigest()

def verify_lastmod(sample_size=50):
    """Compare sitemap lastmod claims against actual content hashes."""
    # entries: list of (url, lastmod, last_crawl_hash) from your state store
    entries = load_previous_crawl_state()
    sample = random.sample(entries, min(sample_size, len(entries)))

    lying = 0
    for url, lastmod, prev_hash in sample:
        if content_hash(url) == prev_hash:
            lying += 1  # lastmod claimed a change; content is identical

    print(f"{lying}/{len(sample)} lastmod entries were false positives "
          f"({lying / len(sample):.0%})")

If more than about 10% of your sample shows false-positive lastmod values, stop trusting the field entirely and switch to a change-detection strategy — the trade-offs there are covered in re-scrape vs change detection.

Link-following has the opposite freshness problem. It never lies to you — the link structure is live, so a new page linked from the homepage is discovered on your next crawl, full stop. But it only notices changes on pages it already visits, and it has no concept of “this page changed, that one didn’t.” You re-fetch the whole reachable graph or nothing.

Scenario	Sitemap-first notices	Link-following notices
New product added today	Next sitemap regeneration (could be instant or weekly)	Next crawl, if the product is linked from a crawled page
Price changed on an old page	Only if lastmod updates — often it doesn’t	Next crawl, but you pay to re-fetch every neighbor too
Page deleted (404)	Never proactively — you learn by wasting a fetch	Only if something still links to it; otherwise silence

My position: for change detection on a known URL set, neither strategy is good alone. Sitemaps give you a cheap manifest of what should exist; links give you ground truth about what currently matters. Hold that thought for the hybrid section.

Dead-URL Waste: Billed 404s in a Sitemap-First Crawl

Here is where metered billing bites. A fetch that returns a 404 from the destination site still consumed a request slot, still burned tokens, and still shows up on your invoice. The destination said “nothing here” — you paid to hear it.

A crawl log from a sitemap-first run against a store with a stale manifest:

batch=a91f  url=store.example.com/products/discontinued-linen-shirt  dest=404  tokens=1
batch=a91f  url=store.example.com/products/old-widget-v2             dest=404  tokens=1
batch=a91f  url=store.example.com/campaign/spring-launch              dest=404  tokens=1
batch=a91f  ... 27 more 404s in this batch ...
summary: 500 fetched, 30 dead URLs, 470 valid documents

At a sample rate of $0.0001 per base fetch, 30 dead URLs cost $0.003 per run. Trivial. Now scale it: a 50,000-URL sitemap with 4% rot is 2,000 dead fetches per run, $0.20 per run, $73 per year if you crawl daily. Still tolerable — until you remember that a base fetch is one token, and real crawls rarely run at one token. Turn on use_js_render (+5 tokens) because the product pages are an SPA, and every one of those 2,000 dead fetches costs 6x. Now you’re at roughly $438 per year for the privilege of confirming that deleted pages are, in fact, deleted.

The obvious counter is pre-validation: check whether a URL is alive before spending a full fetch on it.

import httpx
import random
import xml.etree.ElementTree as ET

NS = {"sm": "http://www.sitemaps.org/schemas/sitemap/0.9"}

def sitemap_urls(path="sitemap.xml"):
    tree = ET.parse(path)
    return [loc.text for loc in tree.findall(".//sm:loc", NS)]

def prevalidate(sample_size=200):
    urls = sitemap_urls()
    sample = random.sample(urls, sample_size)

    dead = 0
    with httpx.Client(follow_redirects=False, timeout=15) as client:
        for url in sample:
            try:
                r = client.head(url)
                if r.status_code == 404:
                    dead += 1
            except httpx.HTTPError:
                pass  # network-level failure: don't count as dead

    rate = dead / len(sample)
    print(f"Estimated sitemap rot: {rate:.1%}")

    # break-even: pre-check wins when dead fetch cost exceeds check cost
    # cost_fetch = full crawl fetch (tokens x rate), cost_check = HEAD cost
    cost_fetch, cost_check = 0.0006, 0.000005  # 6-token JS fetch vs local HEAD
    break_even = cost_check / cost_fetch
    print(f"Pre-validation pays off when rot > {break_even:.1%}")
    print(f"This site: {'pre-check wins' if rate > break_even else 'blind fetch wins'}")

if __name__ == "__main__":
    prevalidate()

Two caveats before you ship this. First, some servers return 200 on HEAD for URLs that 404 on GET — lazy frameworks that don’t route HEAD properly. Spot-check a handful of HEAD-200s with real GETs before trusting a low rot estimate. Second, running thousands of HEADs from your own IP is itself a fingerprint. If the target blocks you, route the pre-checks through your scraping provider as minimal GETs — every option off, no rendering — which costs a fraction of a full crawl fetch.

Link-Following Waste: Redirect Chains, Canonical Loops, and Duplicate Fetches

Link-following has its own billing pathologies, they’re just less visible because no manifest makes them countable in advance.

Start with what the site itself tells you. robots.txt is a free map of where link-following crawls bleed:

User-agent: *
Crawl-delay: 2
Disallow: /search
Disallow: /cart
Disallow: /*?ref=
Disallow: /*?sort=

Sitemap: https://example.com/sitemap.xml

Every Disallow pattern there is a class of URL that a naive href extractor will happily queue and fetch. A product grid that links to ?sort=price_desc variants of itself can double your fetch count for the same category. Faceted navigation is worse — combine sort, filter, and pagination parameters and a 200-product catalog can present thousands of distinct URLs holding a few hundred distinct documents.

Then there are redirects. Here’s a trace that costs three billed requests and delivers exactly one document:

1. GET example.com/old-page            -> 301 -> store.example.com/page      [billed]
2. GET store.example.com/page          -> 200, document served               [billed]
3. GET store.example.com/page?ref=nav  -> 200, same document, nav variant    [billed]

Request 1 happens because a legacy page still has inbound links. Request 3 happens because your frontier saw the ?ref=nav href in the site header before your dedup layer canonicalized it. If the site’s canonical tags are missing or inconsistent, step 3 repeats with ?ref=footer, ?ref=email, and friends. I’ve seen crawls where redirect and parameter overhead exceeded the valid-document count on legacy e-commerce properties.

The dedup burden is the structural tax of link-following. A sitemap is usually deduplicated by whatever generates it. A frontier is not — you build dedup yourself, across URL normalization, canonical resolution, and content hashing, and every rule you get wrong is a billed duplicate.

Break-even Analysis: When Billed Failures Flip the Cheaper Strategy

Time to put numbers on it. Define:

• Sitemap-first cost per valid page = c / (1 - f) where f is the sitemap rot rate and c is cost per fetch. If 20% of entries are dead, you pay for 1.25 fetches per valid document.
• Link-following cost per valid page = c × (1 + d + r) where d is the duplication factor (parameter/canonical variants) and r is redirect overhead as a fraction of valid fetches.

Sitemap-first wins when 1/(1-f) < (1 + d + r), which rearranges to f < (d + r)/(1 + d + r). At a typical d + r = 0.25, the crossover sits at f = 20%. Below 20% sitemap rot, the manifest wins. Above it, following links is cheaper per valid page — but remember you also lose orphan coverage on that side of the line.

Three site profiles at $0.0001 per base fetch:

Site profile	Sitemap rot (f)	Link overhead (d + r)	Winner	Fetches per 1,000 valid pages
Clean catalog site	2%	15%	Sitemap-first	1,020 vs 1,150
High-churn news site	3%	45% (tags, authors, syndication)	Sitemap-first, decisively	1,031 vs 1,450
Legacy site with rot	25%	10%	Link-following	1,333 vs 1,100

The news-site row is the one people get wrong. Intuition says “news changes too fast for a sitemap,” so crawl links. But news sites are the worst link-following targets: every article links to tag pages, author pages, and related stories, and the duplication factor explodes. Their sitemaps, meanwhile, tend to be generated continuously and stay accurate. Trust the manifest.

The legacy-site row is equally counterintuitive in the other direction. Old sites accumulate sitemap entries for pages deleted years ago, while their link graphs are small and tidy because dead links get pruned by whoever maintains the site. Follow the links.

Hybrid Crawl: Sitemap Discovery with Link-Based Verification

For most real targets, the answer is both, with an explicit budget split. Sitemaps supply coverage; selective link extraction supplies freshness on the pages where staleness actually costs you money.

import requests
from urllib.parse import urljoin, urlparse
import re
import xml.etree.ElementTree as ET

API = "https://api.finedata.ai"
HEADERS = {"Authorization": "Bearer fd_your_api_key"}
NS = {"sm": "http://www.sitemaps.org/schemas/sitemap/0.9"}

# pages where we extract links to catch new content the sitemap hasn't shipped yet
LINK_EXTRACTION_ALLOWLIST = ("store.example.com/new-arrivals",
                             "store.example.com/sale")
URL_FILTER = re.compile(r"[?&](ref|sort|filter)=")   # never enqueue these

def scrape(url, formats=("rawHtml",)):
    resp = requests.post(
        f"{API}/api/v1/scrape",
        headers=HEADERS,
        json={"url": url, "formats": list(formats)},
        timeout=180,
    )
    resp.raise_for_status()
    return resp.json()["data"]

def hybrid_queue(sitemap_path="sitemap.xml"):
    tree = ET.parse(sitemap_path)
    sitemap_urls = [loc.text for loc in tree.findall(".//sm:loc", NS)]

    queue = [("sitemap", u) for u in sitemap_urls]           # 80% of budget, first
    seen = set(normalize(u) for _, u in queue)

    for _, url in sitemap_urls:                              # 20%: priority pages
        if not any(host in url for host in LINK_EXTRACTION_ALLOWLIST):
            continue
        html = scrape(url, ("rawHtml",))["rawHtml"]
        for href in re.findall(r'href="([^"]+)"', html):
            link = urljoin(url, href)
            if URL_FILTER.search(link):
                continue
            key = normalize(link)
            if key not in seen:
                seen.add(key)
                queue.append(("link", link))
    return queue

def normalize(url: str) -> str:
    p = urlparse(url)
    return f"{p.netloc}{p.path.rstrip('/')}"   # strip params and trailing slash

The corresponding config for a budgeted crawl run:

HYBRID_CONFIG = {
    "budget_split": {"sitemap_sourced": 0.80, "link_sourced": 0.20},
    "max_redirect_hops": 2,          # abandon chains longer than this
    "dedup": {"normalize_params": True, "respect_canonical": True},
    "link_extraction": {"allowlist_only": True},
    "fetch_options": {"use_antibot": True, "use_js_render": False},
}

The two decisions in there that matter most: the allowlist for link extraction, and the redirect-hop cap. Link extraction is expensive per page (you fetch raw HTML and parse it), so restricting it to a handful of high-churn pages keeps the 20% slice honest. The hop cap exists because redirect chains on legacy sites are unbounded — I’ve hit five-hop chains ending in a 404, which is the maximum possible insult on a per-fetch invoice.

If you’re running this at volume, submit the queue as a batch instead of looping sync requests — the trade-offs between those patterns are worth a separate read, and we’ve covered batch vs single calls before.

Measuring Your Own Split: A Local Audit Before You Commit

Everything above is theory until you measure your actual target. Both numbers — rot rate and duplication factor — are cheap to estimate locally before you spend crawl budget.

Step by step:

1. Download https://example.com/sitemap.xml (follow sitemap-index entries to the leaf sitemaps).
2. Sample 200 URLs randomly. Fetch each with a plain local HTTP client. Record status codes: 200, 404, 301/302 targets.
3. Rot rate = 404s plus redirects that terminate in 404s, divided by 200.
4. Crawl the homepage two levels deep with a throwaway script. Normalize URLs (strip parameters, trailing slashes) and count unique documents versus total fetches.
5. Duplication factor = (total fetches − unique documents) / unique documents.
6. Plug both into the crossover formula from the break-even section.

Fill in this worksheet as you go:

Measurement	Value	Source
Sitemap 404 rate (f)	____	Step 3
Redirect ratio (r)	____	Steps 3–4
Duplicate-content ratio (d)	____	Step 5
Sitemap-first cost per 1,000 valid pages	____	c / (1 − f) × 1000
Link-following cost per 1,000 valid pages	____	c × (1 + d + r) × 1000
Orphan pages present? (sample check)	yes / no	Fetch 20 sitemap URLs, grep homepage HTML for them

One hour of local measurement replaces weeks of guessing. If the orphan check comes back “no” and rot is under 5%, you can skip the hybrid machinery entirely and run a plain sitemap-first crawl — simpler code, predictable cost, done.

What I’d Actually Do

Default to sitemap-first. It’s the cheaper strategy for the majority of sites because most sitemaps are machine-generated and reasonably accurate, and the fixed request count makes cost predictable in a way a growing frontier never is. Add link extraction only where freshness demands it, on an allowlist, with a hard budget cap.

Two things will flip that recommendation: measured rot above roughly 20%, or a target whose sitemap is a static file nobody has regenerated since the site launched. Both are detectable in the one-hour audit above. Run the audit, and trust your own numbers over any rule of thumb — including mine.