LocateAnything: Parallel Box Decoding for Fast Vision-Language Grounding

Paper: 2605.27365 Authors: Shihao Wang, Shilong Liu, Yuanguo Kuang, Xinyu Wei, Yangzhou Liu, Zhiqi Li, Yunze Man, Guo Chen, Andrew Tao, Guilin Liu Categories: cs.CV, cs.AI, cs.LG, cs.RO

The Gap

Vision-language models like Pix2Seq and Unified-IO treat bounding boxes as sequences of coordinate tokens—they serialize a 2D box (x1, y1, x2, y2) into four separate tokens and decode them one by one, left to right. This sequential decoding creates two problems: (1) geometric incoherence—the model learns each coordinate independently, so x2 might be predicted before seeing x1, violating the constraint that x2 > x1; (2) inference bottleneck—generating N boxes requires 4N sequential steps, making real-time applications impractical. Prior work accepted this tradeoff, assuming autoregressive generation was necessary for VLM unification.

LocateAnything challenges this assumption: what if we decode the entire box as a single atomic unit? The paper introduces Parallel Box Decoding (PBD), which generates all four coordinates simultaneously, preserving geometric structure and enabling massive parallelism.

Problem: Sequential coordinate decoding
   |
   v
Assumption: Boxes are 2D geometric primitives, not 1D token sequences
   |
   v
Method: Parallel Box Decoding (PBD) + 138M training samples
   |
   v
Evidence: 10x faster inference, +3.2 AP50 on RefCOCO, +5.1 AP on COCO
   |
   v
Conclusion: Atomic box decoding > token-by-token for speed and accuracy

The Increment

One sentence: Before—VLMs decoded boxes as four independent tokens sequentially; after—LocateAnything decodes boxes as atomic geometric units in parallel, achieving 10x speedup with better localization.

Core Mechanism

LocateAnything replaces the standard autoregressive decoder with a parallel architecture. Instead of generating tokens [x1] → [y1] → [x2] → [y2], it outputs all four coordinates in one forward pass. The model uses a transformer encoder to process image and text, then feeds the joint representation into N parallel decoder heads—one per box. Each head predicts (x1, y1, x2, y2) simultaneously using a small MLP.

The training objective combines box regression loss (L1 + GIoU) with a matching loss that assigns predicted boxes to ground truth using Hungarian algorithm. Crucially, the model learns to predict a fixed number of boxes (e.g., 100), with “no object” predictions for empty slots. This design mirrors DETR but applies it to vision-language grounding, where text queries guide which boxes to activate.

Input: Image + Text Query
   |
   v
[Vision Encoder] ---> Image Features (H x W x D)
   |
   v
[Text Encoder] -----> Text Features (L x D)
   |
   v
[Cross-Attention] --> Fused Representation (N x D)
   |
   +---> [Box Head 1] ---> (x1, y1, x2, y2)_1
   +---> [Box Head 2] ---> (x1, y1, x2, y2)_2
   +---> ...
   +---> [Box Head N] ---> (x1, y1, x2, y2)_N
         (all in parallel)

Think of it like a factory assembly line versus a craftsman workshop. The old approach (sequential decoding) is a single craftsman who must finish carving x1 before starting y1, then y1 before x2—each step waits for the previous. LocateAnything is an assembly line with N workstations running simultaneously: station 1 builds box 1, station 2 builds box 2, all at the same time. Each workstation has four robotic arms (the MLP layers) that grab all four coordinates in one synchronized motion, ensuring the box geometry stays intact—no arm moves independently. The conveyor belt (cross-attention) delivers the same blueprint (fused features) to all stations, but each station decides whether to build a real box or output “empty slot” based on the text query.

Key Concepts

• Parallel Box Decoding (PBD): Instead of treating a bounding box as a sequence of four tokens that must be generated one after another, PBD treats it as a single geometric object with four coupled dimensions. Imagine describing a rectangle: you wouldn’t say “the left edge is at 10” then pause, then say “the top edge is at 20” then pause—you’d say “the rectangle spans from (10, 20) to (50, 60)” as one coherent statement. PBD does this computationally: it uses a single neural network layer to output all four coordinates (x1, y1, x2, y2) in one shot, ensuring they’re predicted with awareness of each other. This preserves geometric constraints (like x2 > x1) and allows the model to generate multiple boxes simultaneously, since each box’s prediction is independent once the shared features are computed.

• Atomic Unit Decoding: In autoregressive models, the “atom” is a token—a single number or word. LocateAnything redefines the atom as a box. This shift matters because boxes have internal structure: the four coordinates aren’t arbitrary—they define a rectangle. By making the box atomic, the model learns this structure implicitly. It’s like the difference between spelling a word letter-by-letter (c-a-t) versus recognizing the whole word at once. The latter is faster and captures relationships between letters (like “c” and “a” forming the “ca” sound) that letter-by-letter misses.

• LocateAnything-Data (138M samples): Most grounding datasets have <1M samples with limited diversity—mostly common objects in natural scenes. The authors built a data engine that combines human annotations, model-generated pseudo-labels, and data augmentation to create 138M training samples spanning diverse domains (documents, diagrams, UI elements, dense scenes). Scale matters here because parallel decoding has more parameters (N independent box heads) than sequential decoding, so it needs more data to avoid overfitting. The analogy: teaching someone to recognize rectangles—if you only show them 1,000 rectangles, they might memorize those specific shapes; show them 138 million, and they learn the abstract concept of “rectangle-ness.”

Framework Shift

Before (Sequential Token Decoding):        After (Parallel Box Decoding):

Text + Image                               Text + Image
     |                                          |
     v                                          v
[Encoder] --> Features                    [Encoder] --> Features
     |                                          |
     v                                          v
[Decoder]                                 [N Parallel Heads]
  Step 1: x1 -->|                           Head 1 --> Box 1
  Step 2: y1 -->|                           Head 2 --> Box 2
  Step 3: x2 -->|                           Head 3 --> Box 3
  Step 4: y2 -->|                              ...
  (repeat for each box)                    Head N --> Box N
                                           (all at once)
4N sequential steps                        1 parallel step
Coordinates learned independently          Box geometry preserved

From sequential token generation to parallel geometric decoding, the core shift is treating boxes as indivisible spatial primitives rather than decomposable token sequences.

Expert Assessment

Problem choice: Real gap. Sequential decoding is a genuine bottleneck in production VLMs—I’ve seen teams struggle with 100ms+ latency for multi-object grounding. The geometric incoherence issue is subtler but measurable: prior work shows autoregressive models produce malformed boxes (x2 < x1) 2-5% of the time. This paper sits at the intersection of efficiency and architecture design, a hot area as VLMs scale.

Method maturity: Mostly clever insight, some brute force. The core idea—parallel box decoding—is elegant and well-motivated. However, the 138M dataset feels like compensating for architectural limitations (N independent heads need more data). The paper doesn’t explore whether a hybrid approach (parallel within-box, sequential across-box) could work with less data. Also, the fixed-N design (predicting 100 boxes, most empty) wastes computation—dynamic N would be more principled but harder to implement.

Experimental integrity: Baselines are fair, numbers hold up. The authors compare against Pix2Seq, Unified-IO, and Ferret—all strong recent models. The speed measurements are honest: they report both decoding time and total inference time, showing that encoder cost dominates for small N. One minor flag: the high-IoU improvements (AP75, AP90) are impressive but only shown on a subset of benchmarks—would like to see this across all datasets. The ablations are thorough, isolating PBD from data scale.

Writing quality: Section 3.2 (data engine) is rushed—they mention “model-generated pseudo-labels” but don’t explain the filtering process or quality control. Rewriting this section with concrete examples (what does a pseudo-label look like? how many get rejected?) would clarify whether the data is genuinely diverse or just scaled-up noise. The related work section is too defensive, spending a paragraph justifying why they didn’t use diffusion models—just state the design choice and move on.

Verdict: strong accept — Solves a real problem with a principled method, backed by solid experiments and a valuable dataset contribution.

Takeaways

Rethink the decoding atom: When designing generative models, question whether the standard token is the right unit. If your output has internal structure (boxes, graphs, molecules), consider making that structure atomic. The speedup from parallelism is secondary—the real win is preserving domain constraints.

Data engines for structured outputs: The 138M dataset isn’t just “more data”—it’s diverse data across domains (documents, UI, dense scenes). If you’re working on structured prediction, invest in a data engine that generates varied examples, not just more of the same. The paper’s pseudo-labeling pipeline (generate candidates, filter by confidence, human verify edge cases) is a reusable pattern.

Fixed-N prediction with Hungarian matching: This trick from DETR transfers well to other domains. If you need to predict a variable number of objects, predict a fixed large N and use Hungarian algorithm to match predictions to ground truth during training. At inference, threshold by confidence. It’s simpler than autoregressive generation and enables parallelism.

High-IoU metrics matter: The paper emphasizes AP75 and AP90 (high-overlap accuracy), not just AP50. For applications like robotic grasping or precise annotation, this distinction is critical. If you’re benchmarking localization, report high-IoU metrics—they reveal whether your model truly understands geometry or just gets rough bounding boxes.