rvsmart: fix exploration efficiency — 93.9% iteration waste on revisited states

[phtcosta]

Context

Experiment exp-rvsmart-ape (169 APKs × 2 tools × 3 reps × 600s, JCA specs, image 0.8.0) revealed critical inefficiencies in the rvsmart:mvp exploration algorithm. Full analysis: docs/20260311_exp_rvsmart_ape_validation.md.

Problem

93.9% of iterations revisit already-known states. The pipeline of loss:

298 iterations (600s, median)
  ↓ 52.6% are RETRIES on the same widget
144 unique actions
  ↓ 82.6% do NOT change UI state
 53 state transitions
  ↓ 62.8% revisit known states
 ~20 new states (median actual: 16)

Comparison with APE: APE discovers 3.7x more states (median 77 vs 16) while being 2.6x more efficient per step (13.9% vs 5.4% discovery rate) and executing 1.85x more steps (553 vs 298).

Overall: rvsmart method coverage 24.4% vs APE 27.8% (-3.3pp). APE wins on 77/169 APKs (>2pp), rvsmart wins on 21.

Root Causes (from algorithm + data analysis)

1. Excessive retries — 52.6% of actions (highest impact)

max_retries_per_cycle=3 fires constantly. On saturated screens, all 3 retries are wasted. Burns ~157 of 298 median iterations.

2. Backward navigation on saturation (Tier 3 BFS)

When saturation ≥80%, Tier 3 BFS navigates backward to an unsaturated ancestor. This creates cycles: saturate current → BFS to ancestor → re-traverse known path → saturate again. Explains the 93.9% revisitation rate.

3. Slow stuck detection (10+5 = 15 wasted iterations)

Force BACK requires 10 consecutive same-hash iterations. Force RESTART requires 5 more failed BACKs. At 0.5 it/s, that's 30 seconds of doing nothing useful.

4. SKIP screens not blacklisted (19% of actions)

When the parser finds no actionable widgets (SKIP), the algorithm doesn't mark the screen as sterile. It revisits these screens repeatedly. 10 APKs have 100% SKIP.

5. Content-blind structural hash

Hash uses 9 widget properties (class, resource_id, clickable, etc.) but ignores text/content. A scrolled list with different items appears as the "same screen" → algorithm thinks it's stuck when it actually advanced.

6. Throughput gap (0.5 vs 0.9 evt/s)

Despite in-emulator execution (5ms UI capture), throughput is 1.85x lower than APE. Likely cause: wait-for-idle timeout or scorer computation overhead.

Proposed Improvements

#	Change	Mechanism	Expected Impact
1	Reduce retry budget	max_retries_per_cycle: 3→1 (0 on saturated screens)	+80 iters/APK → +5-8pp
2	Forward navigation	On saturation, navigate to nearest frontier state (unseen widgets) instead of BFS to ancestor	+5-10pp (less revisitation)
3	Faster stuck detection	same-hash threshold: 10→5; BACK failure threshold: 5→3	+2-3pp
4	Sterile screen blacklist	Mark SKIP-producing hashes, never return to them	+1-2pp
5	Content-aware hash	Include partial text hash or item count in state hash	+3-5pp (more states)
6	Reduce wait-for-idle	Profile loop phases; lower idle timeout on known screens	+throughput

Estimated total impact: +15-25pp method coverage, which would close and potentially exceed the gap with APE.

Supporting Data

• Plateau at 360s (median): 90% of final states discovered by 360s. 64.4% of APKs plateau between 300-600s. More timeout doesn't help.
• Phase distribution: 62.7% of APKs stay entirely in Phase 1; only 1.2% reach Phase 3 (stochastic). Phase escalation thresholds may be too high.
• Correlation: SKIP+RESTART waste vs coverage: r=-0.353 (moderate negative). APKs with >50% waste have mean coverage 8.6%.
• 10 zero-state APKs: rvsmart cannot parse their UI at all (console apps, custom views).
• Redundant metrics: unique_states == unique_hashes == content_states in 100% of APKs.

Files

• Analysis: docs/20260311_exp_rvsmart_ape_validation.md
• Spec: openspec/specs/rvsmart/spec.md (24 invariants, 10 scorers)
• Tool wrapper: modules/rvsmart-tool/src/rvsmart_tool/tools/rvsmart/tool.py
• Java source: $RVSEC_HOME/rvsec-android/rvsmart/