TraversalBench: Challenging Paths to Follow for Vision Language Models

1. Problem Statement

While Vision-Language Models (VLMs) have achieved strong performance on general multimodal benchmarks, their ability to perform sustained visual grounding—specifically, faithfully tracing a continuous visual path in exact order—remains under-tested and surprisingly brittle.

Existing benchmarks often conflate multiple sources of difficulty, such as Optical Character Recognition (OCR), semantic label interpretation, domain knowledge, and open-ended planning. This makes it difficult to isolate whether a model fails due to a lack of visual reasoning or other factors. The authors argue that current models struggle with tasks requiring serial attention and faithful binding of visual structure, particularly when faced with ambiguity, clutter, and self-intersecting paths.

2. Methodology: TraversalBench

The authors introduce TRAVERSALBENCH, a controlled benchmark designed to isolate and test exact visual path traversal.

• Task Definition: The model is presented with an image containing a single continuous polyline with colored shape markers at each vertex. One marker is designated as the "start." The task is to output the exact ordered sequence of markers encountered when traversing the path from start to finish.
• Controlled Complexity Factors: The dataset is generated to systematically vary four interpretable axes of difficulty:
  1. Self-Intersection Count: The number of times the path crosses itself.
  2. Tortuosity: The degree of winding or meandering of the path.
  3. Vertex Count: The total number of points/markers on the path.
  4. Confounding Lines: Nearby non-target line segments added to create visual distractors without altering the target path's topology.
• Dataset Construction:
  • Polyline "backbones" are generated to target specific bins of tortuosity and self-intersection.
  • Render-Aware Constraints: The generation process ensures geometric constraints (segment length, clearance, vertex separation) are met to prevent accidental rendering artifacts from causing errors.
  • Knowledge-Light Design: The task minimizes reliance on OCR, world knowledge, or complex planning, focusing purely on visual tracing.
• Evaluation Metrics:
  • Exact Match (EM): The predicted sequence must match the ground truth perfectly.
  • Token-Level Accuracy (TokAcc): Position-wise accuracy, allowing for partial credit to identify where errors occur.

3. Key Contributions

1. New Benchmark: Introduction of TRAVERSALBENCH, the first controlled benchmark specifically for exact path traversal that balances structural complexity factors.
2. Diagnosis of Failure Modes: The paper moves beyond aggregate scores to identify how and where models fail, distinguishing between global inability and local breakdowns.
3. Identification of Dominant Factors: The study isolates self-intersections as the primary driver of failure, creating a sharp local bottleneck, whereas confounding lines induce a broader, cumulative degradation.
4. Reasoning Budget Analysis: The paper investigates whether increased inference-time reasoning (e.g., Chain-of-Thought) solves these issues, finding that it offers limited benefits and can sometimes reduce answer rates.

4. Key Results

A. Overall Performance

Even the strongest evaluated models (e.g., Gemini 3.1 Pro, GPT-5.4) show significant gaps between token-level accuracy and exact match accuracy.

• Gemini 3.1 Pro (low) achieved the best performance (0.823 EM), while weaker models like Qwen3-VL 32B dropped to 0.082 EM.
• The gap between EM and TokAcc indicates that models often recover the correct prefix but fail at specific points, rather than generating random noise.

B. Impact of Complexity Factors

• Self-Intersections (Dominant Factor): Performance drops sharply as self-intersections increase.
  • First-Crossing Analysis: Models perform relatively well immediately before the first crossing but suffer a steep drop at the crossing. This suggests a local continuation bottleneck where the model fails to disambiguate the correct path branch.
  • Paths with self-intersections are harder even before the first crossing compared to non-intersecting paths of similar length.
• Confounding Lines: These induce a persistent, cumulative penalty. Unlike the sharp drop at crossings, confounding lines cause a gradual degradation in accuracy that compounds as the model encounters more distractors.
• Tortuosity & Vertex Count: These contribute to difficulty but more gradually compared to self-intersections.

C. Reasoning and Layout Bias

• Reasoning Budget: Increasing reasoning tokens (e.g., GPT-5.4 Pro) improves accuracy on answered examples but significantly lowers the answer rate (the model often abstains). This suggests that simply "thinking longer" does not solve the grounding issue and may lead to inefficiency.
• Reading Order Bias: An auxiliary benchmark revealed a slight preference for left-to-right/top-to-bottom layouts, but this did not explain the main effects of path complexity.

5. Significance and Implications

• Beyond "Tunnel Vision": The results challenge the notion that VLMs simply have "tunnel vision" (inability to see non-local features). Instead, models appear capable of tracing substantial prefixes but fail to re-anchor to the image when local ambiguity (crossings) arises.
• Diagnostic Utility: TRAVERSALBENCH serves as a precise diagnostic tool to distinguish between models that suffer from human-like path-following limitations (crossing ambiguity) versus those with fundamental visual grounding failures.
• Future Directions: The authors suggest that simply increasing inference-time reasoning is insufficient. Remediation likely requires:
  • More training data specifically focused on sustained visual attention.
  • Training procedures that encourage image-grounded computation throughout the generation process, rather than relying on internal reasoning that drifts from the visual input.
• Broader Impact: This work highlights a critical blind spot in current VLMs regarding spatial reasoning under ambiguity, which is crucial for real-world applications like navigation, map reading, and diagram interpretation.

In summary, TRAVERSALBENCH reveals that while VLMs are improving, they still lack the robust, sustained visual attention required to navigate complex, self-intersecting structures, with self-intersections acting as the primary failure point.