Definition
Plain language
A data structure that groups nearby items into nested boxes so you can search regions quickly.
As stated in the literature
A height-balanced tree indexing spatial objects via bounding rectangles for range searching; cited as classical geometry machinery that doesn't map cleanly onto attention-sparsification hardware constraints.
Also called: R-trees
Why it matters: It speeds spatial searches, but its structure doesn't fit neatly onto the hardware constraints of attention sparsification.
For example, it groups nearby map locations into nested rectangles so a search for everything in one neighborhood can skip the rest of the map.
Heard on the show
“Because computational geometry has theoretical answers — KD-trees, R-trees — but those are too heavy for the hardware they need to run on.”Episode 036 — Sparse Attention Was the Wrong Frame. Treat It as Geometry Instead.