Box Embeddings: Query2Box Geometry

📍 Where we are: Part II · Region and Geometric Embeddings — Chapter 5. Balls and Cones gave concepts regions; this chapter gives queries regions, and picks the one shape whose intersections stay in the family.

The previous chapter ended on a sour geometric note: balls are a fine region calculus for single concepts, but the intersection of two balls is a lens, and a lens is not a ball. That failure matters the moment we stop asking about one edge and start asking real questions, like "who authored p1 and is advised by alice?", because the natural semantics of and is intersection. This chapter builds the region family that fixes it. Query2Box represents a query, not just a concept, as an axis-aligned box: anchor entities are points, each relation hop translates and widens the current box, and conjunction intersects boxes, which our from-scratch build does exactly, by a corner-wise max and min (the published system approximates the intersection with a learned operator, as the intersection section explains) [1]. We will derive its two-part distance term by term, work out every subgradient through its kinks, train the model with hand-written gradients on the academic graph, and then watch it answer three multi-hop queries whose ground truth we compute symbolically, by traversal, so the geometry has something honest to be measured against.

The simple version

Imagine searching for an apartment on a map. "Near the university" is not a pin; it is a shaded rectangle of acceptable blocks. "On a metro line" is another rectangle. If you need both, you do not average the two rectangles into a compromise pin; you shade in their overlap, and the overlap of two rectangles is, conveniently, another rectangle. Query2Box treats a database query the same way: each hop of the question paints a box in embedding space, and means "overlap the boxes," and the answers are whatever entities' pins fall inside the final box. It all works because of the rectangle's little superpower: rectangles overlapped with rectangles stay rectangles, which is exactly what circles refused to do in the last chapter.

What this chapter covers

• From one tail to a set of tails: an EPFO (existential positive first-order) query has a set of answers, so the query deserves a region, not a point; answering becomes membership ranking.
• The box and its distance, derived: center $\mathbf{c}$, non-negative offset $\mathbf{o}$, and the distance $\operatorname{dist}_{\text{outside}} + \alpha \cdot \operatorname{dist}_{\text{inside}}$, each term derived from interval geometry and matched to boxes.py.
• Relation projection as translate-and-widen: $\text{box}' = (\mathbf{c} + \mathbf{t}_r,\ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r))$, a monotonicity argument for why a hop may only grow the region, and a doubled relation vocabulary for backward edges.
• Intersection, exact: a two-line proof that boxes are closed under intersection, emptiness detection for free, and the contrast with the learned attention operator and with the balls that failed.
• Training by subgradients: the margin loss over 1-hop queries, every subgradient through the $\max/\min$ kinks worked out, the chain rule through softplus, and the real committed loss trace.
• Three queries answered geometrically: 1p, 2p, and 2i on the academic graph, each checked against traversal-computed symbolic answers, plus the intersection corners and a 20-point closure check from the run.
• An honest small-scale reading: what matched exactly (two of three), what ranked close, and why a 13-entity graph is a demonstration rather than a benchmark.

From "which tail?" to "which set of tails?"

Everything in Part I scored one triple at a time. TransE, DistMult, and ComplEx all answer "how plausible is the single edge $(h, r, t)$?", and link prediction reduced a query like advises(bob, ?) to scoring each candidate tail separately. That framing hides a type error. The query advises(bob, ?) does not have an answer; it has an answer set. In the academic graph that set is $\{$carol, dave$\}$, and no single point in $\mathbb{R}^d$ (real $d$-dimensional space, where $d$ is the embedding dimension) can sit close to carol's point and dave's point and every other member of every answer set at once. A point has no interior; a set needs one.

The queries worth caring about make the mismatch worse. This chapter's target class is the EPFO query, short for existential positive first-order: a query built from relation atoms using conjunction ($\wedge$, "and"), disjunction ($\vee$, "or"), and existential quantification ($\exists$, "there is some"), with no negation and no universal quantifier [1]. Written out, our third demo query is

$$q[v]\;=\;\text{authored}(v,\, p1)\ \wedge\ \text{advises}(\text{alice},\, v),$$

read: "the entities $v$ such that $v$ authored p1 and alice advises $v$." The square brackets in $q[v]$ mark $v$ as the answer variable: it stays free, never bound by a quantifier, because the query denotes the set of entities that can fill it. The $\exists$ of the class name binds only intermediate variables, the ones a chained query passes through without returning; this 2i query has none, while the 2p query $q[v] = \exists\, y:\ \text{advises}(\text{alice}, y) \wedge \text{advises}(y, v)$, "the advisees $v$ of some advisee $y$ of alice", has one. An EPFO query is a small directed graph from anchor entities (the constants p1 and alice) through relation edges to one free variable, and its answer is the set of entities that can fill that variable. The standard shape names count the hops: 1p is a single projection advises(bob, ?), 2p chains two projections, 2i intersects two 1p branches [1].

The symbolic way to answer such a query is graph traversal: start at each anchor, follow the edges, intersect the sets. Traversal is exact but brittle: on an incomplete graph (the premise of Link Prediction) a single missing edge silently truncates the answer set, and on large graphs the intermediate sets explode. The first neural alternative, Graph Query Embedding, embedded the query itself as a point, composing hops with learned operators and answering by nearest-neighbor search [2]. That inherits the type error: a point-valued query still cannot represent "a set with three members." Query2Box upgrades the query's type from point to region: the query becomes a box whose interior is the answer set, so answering becomes membership ranking, sorting all entities by how far their points sit from the box [1]. Entities stay points; only queries become boxes. (A third paradigm composes an ordinary 1-hop predictor fuzzily, with no query embedding at all; we return to it at the end [3].)

The box, formally

Decode the objects before the symbols. A box lives in $\mathbb{R}^d$; throughout this chapter $d = 8$, and the index $i \in \{1, \ldots, d\}$ names one coordinate axis. The box is stored as two vectors: a center $\mathbf{c} \in \mathbb{R}^d$, the box's midpoint, and an offset $\mathbf{o} \in \mathbb{R}^d$ with every component $o_i \ge 0$, the box's half-width along each axis. The box itself is the product of intervals

$$\operatorname{Box}(\mathbf{c}, \mathbf{o}) \;=\; \bigl\{\, \mathbf{v} \in \mathbb{R}^d \;:\; c_i - o_i \,\le\, v_i \,\le\, c_i + o_i \ \text{ for every } i \,\bigr\},$$

with lower corner $\mathbf{c} - \mathbf{o}$ and upper corner $\mathbf{c} + \mathbf{o}$. Membership is a per-dimension interval test, and it compresses nicely. Write $a_i = \lvert v_i - c_i \rvert$ for the axial distance of the point from the center along axis $i$ (the bars $\lvert \cdot \rvert$ denote absolute value). Then $c_i - o_i \le v_i \le c_i + o_i$ holds exactly when $a_i \le o_i$, so

$$\mathbf{v} \in \operatorname{Box}(\mathbf{c}, \mathbf{o}) \quad\Longleftrightarrow\quad a_i \le o_i \ \text{ for every dimension } i.$$

In the companion module boxes.py a box is literally the pair of arrays (boxes.py line 89), and an entity is embedded as the degenerate box whose offset is zero, a point (boxes.py lines 144–146):

def point_box(e: str, V: np.ndarray) -> Box:
    """An entity as a degenerate box: its point with a zero offset."""
    return V[E_ID[e]].copy(), np.zeros(D)

The distance, derived term by term

Ranking needs a graded notion of "how far is this entity from being an answer," and Query2Box uses a two-part distance with a deliberate asymmetry between outside and inside [1]. Here is the committed implementation, whose docstring states both parts (boxes.py lines 105–119):

def box_dist(v: np.ndarray, c: np.ndarray, o: np.ndarray) -> float:
    """Query2Box point-to-box distance, with a = |v - c| per dimension:

        dist_outside(v, box) = || max(0, a - o) ||_1   L1 path from v to the
                                                       box surface (0 inside);
        dist_inside(v, box)  = || min(a, o) ||_1       L1 path from the surface
                                                       toward the center,
                                                       capped at the offset;
        dist = dist_outside + ALPHA * dist_inside      ALPHA = 0.2 makes every
                                                       point inside the box
                                                       near-equally good, yet
                                                       still ordered centerward.
    """
    a = np.abs(v - c)
    return float(np.maximum(a - o, 0.0).sum() + ALPHA * np.minimum(a, o).sum())

The notation $\lVert \cdot \rVert_1$ is the L1 norm: the sum of the absolute values of a vector's components. Let us derive both terms rather than accept them.

The outside term is the L1 distance to the nearest point of the box. Because the box is a product of intervals, the point of the box nearest to $\mathbf{v}$ can be found one axis at a time: it is the clamp $p^{\ast}_i = \min\bigl(\max(v_i,\, c_i - o_i),\ c_i + o_i\bigr)$, which leaves $v_i$ alone when it is already in the interval and otherwise snaps it to the nearer endpoint. Check the three cases of the per-axis gap $\lvert v_i - p^{\ast}_i \rvert$. If $v_i \gt c_i + o_i$ (above the interval), the clamp returns $c_i + o_i$, and since $v_i \gt c_i$ we have $a_i = v_i - c_i$, so the gap is $v_i - (c_i + o_i) = a_i - o_i$. If $v_i \lt c_i - o_i$ (below), the gap is $(c_i - o_i) - v_i = a_i - o_i$ by the mirror computation. If $v_i$ is inside the interval, the clamp is $v_i$ itself and the gap is $0$. All three cases are one formula, $\max(0,\, a_i - o_i)$, and summing over axes gives

$$\operatorname{dist}_{\text{outside}}(\mathbf{v}; \mathbf{c}, \mathbf{o}) \;=\; \bigl\lVert \max(\mathbf{0},\, \mathbf{a} - \mathbf{o}) \bigr\rVert_1 \;=\; \sum_{i=1}^{d} \max(0,\ a_i - o_i),$$

which is zero precisely when $\mathbf{v}$ is inside the box: the outside term is the membership test, made quantitative.

The inside term orders the interior centerward, capped at the surface. Per axis, $\min(a_i, o_i)$ equals $a_i$ when the point is inside the interval (its axial distance from the center) and saturates at $o_i$, the half-width, once the point is outside. Summed, the term has a clean identity: $\operatorname{dist}_{\text{inside}} = \sum_i \min(a_i, o_i) = \lVert \mathbf{c} - \mathbf{p}^{\ast} \rVert_1$, the L1 distance from the center to the clamp $\mathbf{p}^{\ast}$, the point's projection onto the box. For an interior point the clamp is the point itself, so the term is exactly the center-to-point distance; on every axis where the point lies outside, the clamp sits on the face and the contribution saturates at the half-width. The term therefore never exceeds the sum of half-widths $\lVert \mathbf{o} \rVert_1$. The total distance discounts it by $\alpha$:

$$\operatorname{dist}(\mathbf{v}; \mathbf{c}, \mathbf{o}) \;=\; \operatorname{dist}_{\text{outside}} \;+\; \alpha \cdot \operatorname{dist}_{\text{inside}}, \qquad \alpha = 0.2 .$$

The constant $\alpha$ (the module's ALPHA, boxes.py line 51) is the design decision that makes a box behave like a set with a soft boundary: with $\alpha$ small, every point inside the box is nearly equally good (all answers are answers), yet ties still break toward the center, so ranking inside the box remains deterministic and trainable [1]. The per-dimension case analysis compresses into a table:

where $v_i$ sits	test	outside term $\max(0, a_i - o_i)$	inside term $\min(a_i, o_i)$	contribution to dist
at the center	$a_i = 0$	$0$	$0$	$0$
strictly inside	$0 \lt a_i \lt o_i$	$0$	$a_i$	$\alpha\, a_i$
on the face	$a_i = o_i$	$0$	$o_i$	$\alpha\, o_i$
outside	$a_i \gt o_i$	$a_i - o_i$	$o_i$	$(a_i - o_i) + \alpha\, o_i$

Two facts to read off the last column. First, the distance is continuous at the face: approaching $a_i = o_i$ from inside gives $\alpha\, a_i \to \alpha\, o_i$, and from outside gives $(a_i - o_i) + \alpha\, o_i \to \alpha\, o_i$; the two one-sided limits agree, so there is no jump, only a crease. Second, the slope with respect to $a_i$ jumps at the crease, from $\alpha = 0.2$ inside to $1$ outside: an entity outside the box feels a five-times-stronger pull toward the surface than an interior entity feels toward the center. That crease is where the subgradients of the training section will live.

The three moves of Query2Box: a relation hop translates a point into a box (left), conjunction intersects boxes exactly by corner-wise max and min (middle), and ranking uses the two-part distance, an L1 path to the surface plus an α-discounted path to the center (right). Original diagram by the authors, created with AI assistance.

Relation projection: translate and widen

A 1-hop query starts from an anchor point and follows a relation. Query2Box gives each relation $r$ two learned vectors: a translation $\mathbf{t}_r \in \mathbb{R}^d$ that moves the center (the same move TransE made in Translational Models) and a widening that grows the offset. The companion parameterizes the widening through softplus so it can never be negative (boxes.py lines 149–156):

def project(box: Box, r: str, T: np.ndarray, S: np.ndarray) -> Box:
    """Relation projection P_r(box) = (c + t_r, o + softplus(s_r)): translate
    the center (the TransE move) and *widen* the offset by a non-negative
    amount — following one more hop can only make a query region larger, never
    sharper, so the widening must not be allowed to shrink the box."""
    c, o = box
    ri = REL_ID[r]
    return c + T[ri], o + softplus(S[ri])

Here $\operatorname{softplus}(x) = \ln(1 + e^{x})$, where $\ln$ is the natural logarithm and $e^{x}$ the exponential function; since $e^{x} \gt 0$ always, the argument of the logarithm exceeds $1$ and the output is strictly positive (boxes.py lines 92–96). So the projection is

$$P_r\bigl(\operatorname{Box}(\mathbf{c}, \mathbf{o})\bigr) \;=\; \operatorname{Box}\bigl(\mathbf{c} + \mathbf{t}_r,\ \ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r)\bigr),$$

where $\mathbf{s}_r \in \mathbb{R}^d$ is the relation's raw width vector, a free parameter.

Why must a hop widen? If the current region stands for a set of entities $Y$, the next region must stand for $\{\,t : (y, r, t) \text{ for some } y \in Y\,\}$, the union over all of $Y$ of each member's $r$-successors. A single member may have several successors (bob advises both carol and dave), and different members' successor sets land in different places, so the image of a set under a relation is in general more spread out than a single translate of the set. The translation handles where the successors live on average; the widening is the budget for their spread. The parameterization enforces the right monotonicity: because $\operatorname{softplus}(\mathbf{s}_r) \gt \mathbf{0}$ componentwise, we get $o_i \le o_i + \operatorname{softplus}(s_{r,i})$ in every dimension $i$, and therefore the translated copy of the old box is contained in the new one:

$$\mathbf{t}_r + \operatorname{Box}(\mathbf{c}, \mathbf{o}) \;=\; \operatorname{Box}(\mathbf{c} + \mathbf{t}_r,\ \mathbf{o}) \;\subseteq\; \operatorname{Box}\bigl(\mathbf{c} + \mathbf{t}_r,\ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r)\bigr).$$

No gradient step can teach a hop to shrink a region, only to translate it and grow it more or less, which matches the semantics: a longer existential chain can only be satisfied by at least as diffuse a set of witnesses.

One practical wrinkle: EPFO queries need to walk edges backwards. "Who authored p1?" traverses the authored relation tail-to-head. Rather than special-case direction, the module doubles the relation vocabulary, giving each of the 5 base relations a formal inverse (boxes.py lines 70–77):

REL10: list[str] = RELATIONS + [f"{r}_inv" for r in RELATIONS]
REL_ID: dict[str, int] = {r: i for i, r in enumerate(REL10)}
assert len(REL10) == 10 and all(REL_ID[r] == R_ID[r] for r in RELATIONS)


def _with_inverses(triples: list[tuple[str, str, str]]) -> list[tuple[str, str, str]]:
    """The triples plus, for each (h, r, t), the inverse triple (t, r_inv, h)."""
    return list(triples) + [(t, f"{r}_inv", h) for h, r, t in triples]

Every training triple $(h, r, t)$ also trains $(t, r_{\text{inv}}, h)$, so the 15 training triples of kg.py become 30 directed positives, and a query like authored_inv(p1, ?), "who authored p1?", is just one more forward projection.

Intersection is exact for boxes

Now the payoff shape. Take two boxes $A = \operatorname{Box}(\mathbf{c}^A, \mathbf{o}^A)$ and $B = \operatorname{Box}(\mathbf{c}^B, \mathbf{o}^B)$, with corner vectors $\mathbf{l}^A = \mathbf{c}^A - \mathbf{o}^A$, $\mathbf{u}^A = \mathbf{c}^A + \mathbf{o}^A$ and likewise for $B$. A point lies in the set intersection $A \cap B$ exactly when it satisfies both membership tests, and both tests are per-dimension interval constraints, so for each $i$:

$$l^A_i \le v_i \le u^A_i \ \ \text{and}\ \ l^B_i \le v_i \le u^B_i \quad\Longleftrightarrow\quad \max\bigl(l^A_i, l^B_i\bigr) \,\le\, v_i \,\le\, \min\bigl(u^A_i, u^B_i\bigr),$$

because satisfying two lower bounds means satisfying the larger one, and satisfying two upper bounds means satisfying the smaller one. The right-hand side is itself a single interval constraint per dimension. Therefore $A \cap B$ is itself an axis-aligned box, with

$$\mathbf{l}^{\cap} = \max\bigl(\mathbf{l}^A, \mathbf{l}^B\bigr), \qquad \mathbf{u}^{\cap} = \min\bigl(\mathbf{u}^A, \mathbf{u}^B\bigr)$$

taken elementwise, and it is empty exactly when $l^{\cap}_i \gt u^{\cap}_i$ for some dimension $i$ (an interval with its lower end above its upper end contains nothing). That is the entire proof: boxes are closed under intersection, conjunction of queries is intersection of regions, and the operation costs one max and one min per dimension. To convert back to center–offset form, take $\mathbf{c}^{\cap} = (\mathbf{l}^{\cap} + \mathbf{u}^{\cap})/2$ and $\mathbf{o}^{\cap} = (\mathbf{u}^{\cap} - \mathbf{l}^{\cap})/2$, as the demo does before ranking (boxes.py line 350). Contrast the balls of Balls and Cones: the intersection of two overlapping balls is a lens with a sharp rim, no ball equals it, and any enclosing ball admits false positives. Boxes pay for closure with axis-alignment (they cannot tilt), and the family of boxes under intersection carries a full lattice structure that supports probabilistic measures, a thread developed independently of query answering [4].

The companion implements the exact operation, and its docstring records an important honesty about the original system (boxes.py lines 165–174):

def intersect(box_a: Box, box_b: Box) -> tuple[np.ndarray, np.ndarray, bool]:
    """The *exact* geometric intersection, as (lower, upper, empty): elementwise
    max of the lower corners, min of the upper corners; the region is empty iff
    lower > upper in any dimension.  (Query2Box instead *learns* intersection —
    attention over the operand centers plus a DeepSets network that shrinks the
    offsets — which can never return an empty box; the exact operation here is
    the set semantics that learned operator approximates.)"""
    (la, ua), (lb, ub) = corners(box_a), corners(box_b)
    lower, upper = np.maximum(la, lb), np.minimum(ua, ub)
    return lower, upper, bool(np.any(lower > upper))

The published Query2Box does not use the exact corner formula. It learns an intersection operator: the new center is an attention-weighted average of the operand centers, and the new offset is the elementwise minimum of the operand offsets shrunk by a DeepSets network, a permutation-invariant function of the operand set [1]. The learned operator is differentiable everywhere and tolerant of imperfectly placed operand boxes, but it can never return, and therefore never report, an empty box: it trades logical crispness for trainability. Our module takes the exact operation because at this scale we want to verify the set semantics numerically, and the exact intersection is the specification the learned operator approximates.

Training: the margin loss and its subgradients

The model has three parameter blocks, 264 numbers in all:

block	shape	count	role
entity points $V$	$13 \times 8$	$104$	one point per entity
translations $T$	$10 \times 8$	$80$	center shift per relation (5 base + 5 inverse)
raw widths $S$	$10 \times 8$	$80$	offset growth $\operatorname{softplus}(S)$ per relation
total		$\mathbf{264}$

Training supervises only 1-hop queries. Each directed positive $(h, r, t)$ is read as the demand: the query box $q = P_r(\operatorname{point}(h))$, whose center is $\mathbf{c} = \mathbf{v}_h + \mathbf{t}_r$ and whose offset is $\mathbf{o} = \operatorname{softplus}(\mathbf{s}_r)$ (a point has zero offset, so the relation's widening is the whole offset), must hold $t$'s point close and hold a sampled non-answer far. With one uniformly sampled negative tail $\tilde{t}$, resampled while it forms a known-true triple so that no genuine answer is ever pushed away (boxes.py lines 222–224), the per-example margin loss is

$$L \;=\; \max\Bigl(0,\ \ \gamma \;+\; \operatorname{dist}\bigl(\mathbf{v}_t;\, \mathbf{c}, \mathbf{o}\bigr) \;-\; \operatorname{dist}\bigl(\mathbf{v}_{\tilde{t}};\, \mathbf{c}, \mathbf{o}\bigr)\Bigr),$$

with margin $\gamma = 1.75$ (boxes.py line 47): the negative must sit at least $\gamma$ farther from the box than the positive, and once it does, the loss is zero and the example is left alone. Abbreviate the two distances as $d_{\text{pos}} = \operatorname{dist}(\mathbf{v}_t;\, \mathbf{c}, \mathbf{o})$, the true tail's distance to the query box, and $d_{\text{neg}} = \operatorname{dist}(\mathbf{v}_{\tilde{t}};\, \mathbf{c}, \mathbf{o})$, the sampled negative's; these are the code's d_pos and d_neg (boxes.py lines 227–228). The gradient needs $\partial \operatorname{dist} / \partial \mathbf{v}$ and $\partial \operatorname{dist} / \partial \mathbf{o}$, the partial derivatives (the symbol $\partial$ asks how fast the distance changes when one coordinate of $\mathbf{v}$, or of $\mathbf{o}$, moves while everything else is held fixed), and the distance is built from $\max$ and $\min$, which have creases. Work dimension by dimension. Write $\operatorname{diff}_i = v_i - c_i$, $a_i = \lvert \operatorname{diff}_i \rvert$, and $s_i = \operatorname{sign}(\operatorname{diff}_i)$, the sign being $+1$, $-1$, or $0$. Away from the creases, the chain rule through the absolute value gives $\partial a_i / \partial v_i = s_i$, and each term of the distance differentiates by cases:

• Outside term $\max(0,\, a_i - o_i)$. When $a_i \gt o_i$ the max takes its second argument, so $\partial/\partial v_i = \partial(a_i - o_i)/\partial v_i = s_i$ and $\partial/\partial o_i = -1$. When $a_i \lt o_i$ the max is the constant $0$ and both derivatives vanish.
• Inside term $\alpha \min(a_i,\, o_i)$. When $a_i \lt o_i$ the min takes the $a$-branch, so $\partial/\partial v_i = \alpha\, s_i$ and $\partial/\partial o_i = 0$. When $a_i \gt o_i$ it takes the $o$-branch, so $\partial/\partial v_i = 0$ and $\partial/\partial o_i = \alpha$.

Stacking the cases with indicator masks (writing $[\,P\,]$ for $1$ if $P$ holds, else $0$):

$$\frac{\partial \operatorname{dist}}{\partial v_i} = s_i\,[\,a_i \gt o_i\,] + \alpha\, s_i\,[\,a_i \lt o_i\,], \qquad \frac{\partial \operatorname{dist}}{\partial o_i} = -\,[\,a_i \gt o_i\,] + \alpha\,[\,a_i \ge o_i\,].$$

This is box_dist_grads, mask for mask (boxes.py lines 122–141):

    diff = v - c
    a, s = np.abs(diff), np.sign(diff)
    m_out = (a > o).astype(float)          # outside-active dimensions
    m_in_v = (a < o).astype(float)         # inside min takes the a-branch
    g_v = s * m_out + ALPHA * s * m_in_v
    g_o = -m_out + ALPHA * (1.0 - m_in_v)  # o-branch mask = (a >= o) = 1 - m_in_v
    return g_v, g_o

What happens exactly at a crease, and why it is safe. At $a_i = o_i$ the one-sided derivatives with respect to $a_i$ disagree: $\alpha$ from inside, $1$ from outside (the outside term wakes up, the inside term freezes). The distance is still continuous there (the one-sided limits agreed at $\alpha\, o_i$), so the function has a crease, not a cliff, and at a crease any value between the two one-sided slopes is a valid subgradient: a slope whose linear extrapolation stays below the function nearby, which is all a descent step needs to make progress on average. The code's strict masks make a mixed pick at the tie ($m_{\text{out}} = 0$ treats the outside term as inactive, while the min takes the $o$-branch, per the docstring at boxes.py lines 132–134), returning the per-axis pair $(g_{v_i}, g_{o_i}) = (0, \alpha)$. Honesty requires noting that this mixed pair is not itself a member of the subgradient set: the valid slopes at the tie run from $\alpha\, s_i$ to $s_i$ in $v_i$ and from $\alpha - 1$ to $0$ in $o_i$, so the returned $0$ falls outside the first interval whenever $s_i \neq 0$, and the returned $\alpha = 0.2$ falls outside the second (its sign is even wrong). The pick is harmless for a blunter reason: the tie $a_i = o_i$ is a measure-zero event, one that occurs with probability zero for real-valued iterates, so in practice the training loop never lands on it, and the branch choice decides reproducibility, not correctness. (No convexity guarantee was ever on offer anyway: each distance is convex in $\mathbf{v}$ and in $\mathbf{o}$ separately, but the joint objective over the points $V$, translations $T$, and raw widths $S$ is non-convex.) The same reasoning covers the crease of the absolute value at $\operatorname{diff}_i = 0$, where NumPy's $\operatorname{sign}(0) = 0$ picks the zero subgradient, the sensible choice at the bottom of the $\lvert \cdot \rvert$ crease, where no first-order move helps.

Three chain-rule hops assemble the parameter gradients when the hinge is active ($L \gt 0$, so $\partial L / \partial d_{\text{pos}} = +1$ and $\partial L / \partial d_{\text{neg}} = -1$):

1. Center. The distance depends on $\mathbf{v}$ and $\mathbf{c}$ only through $\operatorname{diff} = \mathbf{v} - \mathbf{c}$, and $\partial \operatorname{diff}_i / \partial c_i = -1$ while $\partial \operatorname{diff}_i / \partial v_i = +1$, so $\partial \operatorname{dist} / \partial \mathbf{c} = -\,\partial \operatorname{dist} / \partial \mathbf{v}$: the center's gradient is the point's gradient, negated.
2. Head and translation. Since $\mathbf{c} = \mathbf{v}_h + \mathbf{t}_r$ is a plain sum, both $\mathbf{v}_h$ and $\mathbf{t}_r$ receive the center's gradient unchanged (the Jacobian, the matrix of partial derivatives of an output vector with respect to one input vector, is the identity matrix in each argument of a plain sum).
3. Raw width. Since $\mathbf{o} = \operatorname{softplus}(\mathbf{s}_r)$ elementwise, we need $\operatorname{softplus}'$. Differentiate $\ln(1 + e^{x})$: the chain rule gives $\frac{e^{x}}{1 + e^{x}}$, and multiplying numerator and denominator by $e^{-x}$ turns this into $\frac{1}{e^{-x} + 1} = \sigma(x)$, the sigmoid (boxes.py lines 99–102). So $\partial L / \partial s_{r,i} = (\partial L / \partial o_i)\, \sigma(s_{r,i})$.

The inner loop applies exactly these, with learning rate $\eta = 0.05$ in the update $\theta \leftarrow \theta - \eta\, \partial L / \partial \theta$, where $\theta$ stands for whichever parameter block ($V$, $T$, or $S$) is being adjusted (boxes.py lines 233–246):

            # Active hinge: dL/dtheta = d d_pos/dtheta - d d_neg/dtheta.
            gv_p, go_p = box_dist_grads(V[ti], c, o)
            gv_n, go_n = box_dist_grads(V[ni], c, o)
            # dL/dv_t = +(d d_pos/dv);  dL/dv_neg = -(d d_neg/dv).
            # dL/dc   = -(d d_pos/dv) + (d d_neg/dv)   [d dist/dc = -d dist/dv],
            #           and c = v_h + t_r, so v_h and t_r share this gradient.
            # dL/ds_r = (d d_pos/do - d d_neg/do) * sigmoid(s_r)
            #           [chain rule through o = softplus(s_r), softplus' = sigmoid].
            g_c = -gv_p + gv_n
            V[ti] -= LR * gv_p
            V[ni] += LR * gv_n
            V[hi] -= LR * g_c
            T[ri] -= LR * g_c
            S[ri] -= LR * (go_p - go_n) * sigmoid(S[ri])

Note the sign on the negative entity's update: $\partial L / \partial \mathbf{v}_{\tilde{t}} = -\,\partial d_{\text{neg}} / \partial \mathbf{v}$, so descending on $L$ means adding $\eta\, \mathbf{g}_{v}^{\text{neg}}$, pushing the sampled non-answer away from the box. Two initialization choices matter enough to name. Points start small (INIT = 0.3, boxes.py lines 52–58), clustered where the boxes will be, so an entity leaves a box only if a gradient explicitly pushes it out. The known-true negative filter then guarantees that a held-out answer such as dave for advises(bob, ?) is never directly pushed away from a box it truly belongs to; the filter does not forbid side-effect drift (dave's point still moves whenever dave is drawn as a negative for some other query), but in this run the small start and the filter together suffice for dave to stay inside, and that observed mechanism is where the generalization to unseen answers comes from. Raw widths start at $s = -1$, so every offset begins at $\operatorname{softplus}(-1) \approx 0.313$: boxes start tight and must grow to cover their positives, keeping the final regions crisp instead of vacuously large (boxes.py lines 59–61). Running the module (python3 boxes.py) prints the committed trace:

training (manual gradients: margin 1.75, lr 0.05, 1 negative per positive, seed 0)
  epoch    1  mean margin loss 1.6447
  epoch  100  mean margin loss 0.0103
  epoch  500  mean margin loss 0.0000
  epoch 1000  mean margin loss 0.0000
  epoch 1500  mean margin loss 0.0000
  held-out link prediction (filtered): MRR 0.9167  hits@1 0.8333  ranks [1, 1, 1, 1, 1, 2]

The first epoch's mean loss, $1.6447$, sits just under the margin $\gamma = 1.75$, which is what a random start looks like: positives and negatives begin nearly equidistant from every box, so the hinge is almost fully open on average. By epoch 100 the mean loss is $0.0103$, and from epoch 500 on every one of the 30 directed positives clears the margin exactly. As a sanity bridge to Part I, the trained boxes also serve as a link predictor through the shared filtered harness of kg.py (lines 110–122), scoring a triple by the negated distance of the tail to the 1-hop box: five of the six held-out ranking queries land at rank 1 and one at rank 2, for a filtered Mean Reciprocal Rank of $0.9167$.

Three queries, answered geometrically

Now the payoff. The module answers three EPFO queries by geometry alone (build the box, rank all 13 entities by box_dist), and checks each against symbolic ground truth: the answer set computed by graph traversal over all 18 triples, held-out test edges included, via sym_tails (boxes.py lines 185–192). The truth is computed, never assumed, and the comparison rule is strict: the geometric top-$k$ set, with $k$ the size of the gold set, must equal the gold set exactly.

q1 (1p): advises(bob, ?) is one projection from bob's point. Traversal says the answers are carol and dave, and the second is the interesting one: the edge (bob, advises, dave) is a held-out test triple, never trained on, so retrieving dave is generalization, not memorization. The run:

q1 (1p)  advises(bob, ?)
  symbolic answers (traversal over all 18 triples): ['carol', 'dave']
  geometric top-4 by box distance:
    1. carol  0.1876  <- gold
    2. dave   2.2971  <- gold
    3. bob    2.3359
    4. erin   2.4306
  top-2 set equals the symbolic set: True

q2 (2p): advises(alice, Y) ∧ advises(Y, ?), alice's advisees' advisees, is two chained projections: $P_{\text{advises}}(P_{\text{advises}}(\operatorname{point}(\text{alice})))$. Traversal gives the intermediate set $Y = \{$bob$\}$ and the answer set $\{$carol, dave$\}$:

q2 (2p)  advises(alice, Y) . advises(Y, ?)
  symbolic answers (traversal over all 18 triples): ['carol', 'dave']
  geometric top-4 by box distance:
    1. carol  0.2436  <- gold
    2. erin   1.2500
    3. dave   1.5862  <- gold
    4. bob    1.6437
  top-2 set equals the symbolic set: False

This is the honest miss: both gold answers rank in the top 3 of 13, but erin intrudes at rank 2 and pushes dave to rank 3. Erin is not a random intruder; the closing section reads the mechanism in full.

q3 (2i): authored_inv(p1, ?) ∧ advises(alice, ?), "who authored p1 and is advised by alice?", is the intersection query. Each conjunct is a 1p box; the exact corner-wise intersection combines them:

q3 (2i)  authored_inv(p1, ?) AND advises(alice, ?)
  operand traversal: authored_inv(p1,?) = ['alice', 'bob'], advises(alice,?) = ['bob'], intersection = ['bob']
  box A lower [0.507 -0.017 -1.452 -1.158 1.010 -0.229 -0.204 -0.184]
        upper [1.020 0.587 -0.820 -0.585 1.587 0.289 0.354 0.478]
  box B lower [0.241 -0.131 -0.863 -0.836 0.542 -0.550 -0.503 -0.154]
        upper [0.767 0.334 -0.358 -0.309 1.129 0.145 0.141 0.450]
  exact intersection (nonempty):
        lower [0.507 -0.017 -0.863 -0.836 1.010 -0.229 -0.204 -0.154]
        upper [0.767 0.334 -0.820 -0.585 1.129 0.145 0.141 0.450]
  closure on 20 sampled points: inA=10 inB=10 inA&B=4 inI=4 mismatches=0

Check the corner arithmetic against the theorem in dimension 1: box A's lower corner is $0.507$, box B's is $0.241$, and the intersection's lower corner is $\max(0.507, 0.241) = 0.507$; the uppers are $1.020$ and $0.767$, and the intersection's is $\min(1.020, 0.767) = 0.767$. Every printed coordinate obeys the max/min rule, and no dimension has lower above upper, so the region is nonempty. The closure check then samples 20 seeded points across the interesting cases (6 inside A, 6 inside B, 4 inside the intersection, 4 from a padded hull around everything; boxes.py lines 359–377) and verifies, point by point, that membership in the intersection box equals membership in A and membership in B: 10 points landed in A, 10 in B, exactly 4 in both, exactly those 4 in the intersection box, zero mismatches. That is the set semantics of conjunction, holding numerically. The ranking against the intersection box:

q3 (2i)  ranked by distance to the intersection box
  symbolic answers (traversal over all 18 triples): ['bob']
  geometric top-4 by box distance:
    1. bob    0.5525  <- gold
    2. alice  2.5787
    3. carol  3.6868
    4. p1     3.7172

Bob is retrieved at rank 1 with a wide gap to the runner-up ($0.5525$ against $2.5787$), and the runner-up is alice, the other author of p1, the entity satisfying one conjunct but not both. The module's competency asserts pin all of this in code: the intersection's gold set must differ from both of the earlier projection queries' gold sets, q1's and q2's, so the conjunction demo is not a re-run of a query already answered (it may coincide with one operand's set, and here it does: advises(alice, ?) already returns exactly bob); at least 2 of the 3 queries must retrieve their gold set exactly; and the closure check must show zero mismatches (boxes.py lines 390–398).

query	shape	symbolic answers (traversal)	geometric top-$k$, $k = \lvert\text{gold}\rvert$	exact match
advises(bob, ?)	1p	carol, dave	carol ($0.1876$), dave ($2.2971$)	yes
advises(alice, Y) ∧ advises(Y, ?)	2p	carol, dave	carol ($0.2436$), erin ($1.2500$)	no: dave at rank 3
authored_inv(p1, ?) ∧ advises(alice, ?)	2i	bob	bob ($0.5525$)	yes

Reading the result honestly

Two of three queries retrieved their symbolic answer sets exactly, and the exact intersection behaved as the theorem says it must: projection, chaining, and conjunction all executed as geometry, with generalization to a held-out answer in q1. The q2 miss deserves the promised close look, because erin is not an arbitrary entity. The graph contains (carol, advises, erin), so erin is exactly the kind of point that lives where advises boxes land, an advisee-shaped entity; after two widenings the 2p box is broad enough that erin's point sits slightly nearer than dave's. The box did what two hops of widening must do, grew, and a near neighbor slipped inside the ranking. None of this is a benchmark result. Thirteen entities give a ranking task with twelve distractors; the model has 264 parameters and saw every entity during training. Query2Box's actual habitat is knowledge graphs at the scale of FB15k, FB15k-237, and NELL995, roughly fourteen to sixty-three thousand entities, where queries are generated across nine dependency-graph shapes and the model ranks against fourteen to sixty-three thousand candidates [1]. At that scale the learned attention intersection earns its keep over the exact one (operand boxes are imperfect, so a forgiving overlap generalizes better), and disjunction is handled by a rewriting theorem: any EPFO query can be transformed into disjunctive normal form, a union of purely conjunctive branches, so unions are answered by embedding each branch as its own box and taking the minimum distance over branches [1]. Regions are not the only paradigm, either: the same queries can be answered by keeping an ordinary 1-hop predictor such as ComplEx and composing its scores through fuzzy conjunctions (t-norms) with beam search over intermediate variables, no query operators trained at all, and on standard benchmarks that composition is a strong rival [3]. The box calculus wins on a different axis: one geometric object and one nearest-neighbor sweep per query, instead of a search over intermediate assignments.

The unsolved part

Boxes buy closure under conjunction, and the price shows up one logical operator later: there is no negation. The complement of a box is not a box. In one dimension this is already visible: the complement of the interval $[l, u]$ is the union of two rays, everything below $l$ and everything above $u$, which no single interval represents; in $d$ dimensions the complement wraps around the box on all $2d$ sides, unbounded, about as un-box-like as a set can be. So a query such as "affiliated with cmu and not advised by bob" has no home in this calculus: boxes are closed under intersection but not under complement, and EPFO, the class Query2Box handles, is defined precisely by excluding negation [1]. There is a second, quieter limit: the exact intersection can report emptiness, but the attention operator that replaces it at scale never produces an empty box, so the trained model can never say "this query has no answers." A geometry that represents negation, and expresses "no answer" natively, needs objects richer than solid regions; the next chapter replaces regions with probability distributions, where the complement becomes an exact parameter map.

Why it matters

This chapter crossed a line that matters for the whole neuro-symbolic program: for the first time in this volume, a compound logical expression, not just a single atom, was executed entirely inside the embedding space. Conjunction ran as max/min arithmetic, existential quantification ran as translate-and-widen, and the result was checked against traversal ground truth rather than eyeballed. That is the embryonic form of what Volume 4 will treat as complex query answering by differentiable reasoning: logical structure compiled into geometric operators, trained by gradients, evaluated by ranking. The chapter also sharpened Part II's design lesson: choose the representation family for the operations you must support, not just the objects you must store. Balls store concepts beautifully and fail conjunction; boxes handle conjunction exactly and fail negation; every operator added to the query language is a closure demand on the geometry.

Key terms

• EPFO query (existential positive first-order): a query built from relation atoms with conjunction, disjunction, and existential quantification, no negation; its answer is a set of entities.
• Box embedding: the axis-aligned region $\operatorname{Box}(\mathbf{c}, \mathbf{o})$ with center $\mathbf{c}$, non-negative per-dimension offsets $\mathbf{o}$, and corners $\mathbf{c} \pm \mathbf{o}$.
• Query2Box distance: $\operatorname{dist}_{\text{outside}} + \alpha \cdot \operatorname{dist}_{\text{inside}}$, the L1 distance to the box surface plus an $\alpha$-discounted pull toward the center; zero outside-term means membership.
• Relation projection: $P_r(\mathbf{c}, \mathbf{o}) = (\mathbf{c} + \mathbf{t}_r,\ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r))$; translation moves the region, softplus-positive widening guarantees a hop can only grow it.
• Inverse relation: a formal relation $r_{\text{inv}}$ trained on the reversed edges, doubling the relation vocabulary so queries can traverse edges backwards.
• Exact box intersection: lower corner $\max(\mathbf{l}^A, \mathbf{l}^B)$, upper corner $\min(\mathbf{u}^A, \mathbf{u}^B)$, elementwise; empty exactly when some lower exceeds its upper.
• Subgradient: at a convex crease of a continuous piecewise-linear function (left slope below right slope), any slope between the two one-sided derivatives; taking a full one-sided derivative is a valid pick, and even the code's mixed per-term pick is harmless because the tie is never hit in practice.
• Margin (hinge) loss: $\max(0, \gamma + d_{\text{pos}} - d_{\text{neg}})$; zero, with zero gradient, once the negative sits at least $\gamma$ farther from the box than the positive.
• Closure check: an empirical verification, on sampled points, that membership in the intersection box equals joint membership in both operands.
• DNF rewriting (disjunctive normal form): rewriting any EPFO query as a union of conjunctive branches, letting a conjunction-only geometry answer disjunctions branch by branch.

Where this leads

Boxes gave us and exactly and or by rewriting, and then stopped cold at not: the complement of a box is not a box, so no purely region-based calculus of this shape can answer "affiliated with cmu and not advised by bob." The next chapter, Beta and Probabilistic Embeddings, makes the representational jump that buys negation. Every entity and every query becomes a vector of Beta distributions; fit is measured by a closed-form Kullback–Leibler divergence, conjunction multiplies densities so their exponents combine additively, and negation, the operator no ball or box could express, becomes the exact parameter map $(\alpha, \beta) \mapsto (1/\alpha,\, 1/\beta)$, where $\alpha$ and $\beta$ are the Beta distribution's two shape parameters (a different $\alpha$ from this chapter's distance discount) and $\mapsto$ reads "maps to". The price and the payoff of trading regions for distributions is the story there.

---

Companion code: examples/neural/boxes.py implements everything in this chapter, the box geometry (box_dist, project, intersect), the hand-derived subgradients (box_dist_grads), the margin-loss training loop, and the three-query demo with its traversal ground truth and closure check, over the shared graph and evaluation harness of examples/neural/kg.py. Run python3 examples/neural/boxes.py to reproduce every number quoted above; the module's competency asserts fail the run if the intersection query merely repeats an earlier query's answer set, fewer than two of the three queries retrieve their gold sets exactly, or any closure mismatch appears.