Managing LLM Context Limits with Quadtree Indexes

A hierarchical spatial index answers two questions cheaply that a context budget needs constantly: where are the features concentrated, and which of them are near the thing being asked about. Using it to select is excellent; using it to replace the geometry is where teams go wrong. This guide covers both sides, as a selection technique for context-window optimization for maps.

When to Use This Approach

Use a hierarchical index when the view holds more features than the budget can carry and their distribution is uneven — which is almost always true of real map data.

The counting row is the one worth acting on immediately. A question about how many features are in an area should be answered from the index’s own counts, exactly, and never by sending a sample of features and hoping the model extrapolates.

Implementation

The index is built once per view, queried for density and neighbourhood, and used to produce both a selection and an honest summary of what was left out.

import logging
from dataclasses import dataclass, field
from typing import Iterable, Sequence

log = logging.getLogger("spatial_index_budget")

MAX_DEPTH = 12


@dataclass
class Node:
    bounds: tuple[float, float, float, float]
    depth: int
    features: list = field(default_factory=list)
    children: list = field(default_factory=list)

    def count(self) -> int:
        return len(self.features) + sum(c.count() for c in self.children)


def _quadrants(b):
    w, s, e, n = b
    mx, my = (w + e) / 2, (s + n) / 2
    return ((w, s, mx, my), (mx, s, e, my), (w, my, mx, n), (mx, my, e, n))


def build(features: Sequence[dict], bounds, capacity: int = 16, depth: int = 0) -> Node:
    """Build a hierarchical index over feature representative points."""
    node = Node(bounds, depth)
    if len(features) <= capacity or depth >= MAX_DEPTH:
        node.features = list(features)
        if depth >= MAX_DEPTH and len(features) > capacity:
            log.info("depth limit reached with %d coincident features", len(features))
        return node
    buckets = [[] for _ in range(4)]
    for f in features:
        x, y = f["x"], f["y"]
        for i, (w, s, e, n) in enumerate(_quadrants(bounds)):
            if w <= x <= e and s <= y <= n:
                buckets[i].append(f)
                break
        else:                                        # numerically on a boundary
            node.features.append(f)
    node.children = [build(b, q, capacity, depth + 1)
                     for b, q in zip(buckets, _quadrants(bounds)) if b]
    return node

The fall-through that keeps boundary features at the parent node matters more than it looks. Floating-point comparisons occasionally place a point in no quadrant, and a build that silently drops those features produces an index whose counts disagree with the data — which then propagates into every aggregate answer.

Selection walks the index outward from the focus, taking whole nodes while the budget allows and summarising the rest.

@dataclass(frozen=True)
class Selection:
    features: tuple
    summarised_nodes: tuple
    total_available: int


def select(root: Node, focus, budget_features: int) -> Selection:
    """Take the nearest features up to the budget; summarise the nodes not taken."""
    ordered = sorted(_walk(root), key=lambda n: _distance(n.bounds, focus))
    taken, summarised, used = [], [], 0
    for node in ordered:
        if used + len(node.features) <= budget_features:
            taken.extend(node.features)
            used += len(node.features)
        elif node.features:
            summarised.append(node)
    return Selection(tuple(taken), tuple(summarised), root.count())


def summarise(nodes: Iterable[Node]) -> str:
    """One honest sentence about everything not shown."""
    nodes = list(nodes)
    if not nodes:
        return ""
    total = sum(len(n.features) for n in nodes)
    return (f"{total} further features are present in the view but not shown, "
            f"spread across {len(nodes)} areas.")

Summarising by node rather than by feature is what keeps the summary honest and short. “Four hundred further features” is a number; “four hundred further features across nine areas” tells a reader whether the omission is one dense block or the whole view, which changes how much the shown selection can be trusted to represent it.

Validation & Testing

def test_index_count_matches_the_input():
    root = build(FEATURES, BOUNDS)
    assert root.count() == len(FEATURES)


def test_boundary_features_are_not_dropped():
    on_edge = [{"x": 0.0, "y": 0.0, "id": "edge"}] * 40
    root = build(on_edge, (-1.0, -1.0, 1.0, 1.0), capacity=4)
    assert root.count() == 40


def test_selection_never_exceeds_the_budget():
    sel = select(build(FEATURES, BOUNDS), FOCUS, budget_features=25)
    assert len(sel.features) <= 25


def test_summary_reports_the_true_remainder():
    sel = select(build(FEATURES, BOUNDS), FOCUS, budget_features=25)
    assert sel.total_available == len(FEATURES)
    assert str(len(FEATURES) - len(sel.features)) in summarise(sel.summarised_nodes)


def test_depth_limit_terminates_on_coincident_points():
    coincident = [{"x": 1.0, "y": 1.0, "id": str(i)} for i in range(500)]
    root = build(coincident, (0.0, 0.0, 2.0, 2.0), capacity=4)
    assert root.count() == 500

The last test is the one that prevents a stack overflow in production. Coincident points — several records at the same address, a batch geocoded to a town centroid — subdivide forever without a depth limit, and the failure arrives as a crash on one unusual view rather than as a gradual slowdown.

The count invariant deserves to run on every build rather than only in tests. It is a single comparison against the input length, it costs nothing, and it is the only check that notices when a change to the partition logic starts losing features at quadrant boundaries.

Gotchas & Edge Cases

Cells sent instead of features. The index’s cells are an artefact of the data’s distribution, not a description of the world. Send features; use cells to decide which.

Selection by node when nodes are uneven. Taking whole nodes is efficient and can overshoot badly when one node holds most of the features. Check the node’s size against the remaining budget before taking it, and fall back to per-feature selection inside it.

Rebuilding the index per request. Building over a view’s features is cheap; building over a whole corpus per request is not. Build per view, or maintain a persistent index and query a subtree.

Counts drifting from the data. An index whose count disagrees with the source is worse than no index, because aggregates are answered from it. Assert the invariant on build, as the first test does.

A depth limit reached silently. Hitting the limit means the capacity assumption has failed for this data, which is worth a log line — otherwise the first symptom is an oversized leaf node that defeats selection.

Distance measured to node bounds in degrees. Ordering nodes by an unprojected distance biases selection at high latitude in the same way it biases reranking. Project, or accept that the ordering is approximate and say so.

Frequently Asked Questions

Related

• Up to the parent topic: Context-Window Optimization for Maps
• Budgeting Tokens Across Map Layers
• Related topic: Geometry Tokenization Strategies
• Related technique: Filtering Retrieval by Bounding Box Before Vector Search