Technical Summary: Verifier-Guided Code Translation via Meta-Step Decoding

Problem Statement

Large Language Models (LLMs) have become capable code generators, but improving performance on difficult inputs is increasingly pursued through test-time scaling (allocating additional inference compute) rather than solely through larger pretraining. Existing test-time scaling methods are primarily designed for open-ended domains where correctness is difficult to verify exactly. Consequently, they rely on probabilistic signals derived from the model itself (e.g., token likelihoods, learned reward models) or repeated sampling.

However, coding tasks possess deterministic external verifiers (compilers, type checkers, behavioral tests) that provide exact pass/fail feedback. Current approaches typically apply these verifiers only post-hoc (after generation is complete). This is inefficient because:

1. Error Propagation: Once a verifier-detectable error enters the autoregressive prefix, the model conditions on a corrupted context.
2. Late Correction: Models tend to continue the erroneous trajectory rather than recover, as the error is only detected after the full program is generated.
3. Wasted Compute: Post-hoc filtering or reranking discards entire sequences, wasting the tokens spent on the initial (flawed) generation.

The core challenge is how to integrate deterministic verifier signals directly into the autoregressive decoding loop to guide generation before errors compound, without incurring excessive overhead.

Methodology: Decoding Time Verification (DTV)

The authors introduce Decoding Time Verification (DTV), a framework that interleaves token generation with deterministic verifier calls under an explicit state-machine controller. DTV treats structural boundaries (statements, blocks, functions) as meta-steps for verifier-guided decoding.

Core Mechanisms

1. Structural-Boundary Verification:

   • Instead of verifying arbitrary token prefixes, DTV pauses generation at structural boundaries (e.g., the end of a statement or block).
   • At each boundary, the current prefix is rendered into a verifier-consumable artifact (e.g., a compilable snippet).
   • Applicable oracles (compilers, type checkers, linters) are invoked.
   • Invariant: Only prefixes that pass all applicable verifiers are "committed" as valid conditioning context for subsequent decoding.

2. Structure-Aware Rollback with Escalation:

   • If verification fails, the controller does not simply restart the entire generation.
   • It identifies the smallest scope (e.g., statement, block, function) implicated by the verifier's diagnostic.
   • The system rolls back the prefix to the checkpoint immediately preceding that scope.
   • Escalation: If repeated failures occur at a fine-grained scope, the rollback scope is widened (e.g., from statement to block) to allow the model to revise a larger region of code.

3. Feedback via Prompt Augmentation:

   • To prevent "blind resampling," DTV updates the model's context with the verifier's diagnostics.
   • The feedback state (error messages and source anchors) is encoded into a textual block and injected back into the prompt.
   • The model then retries generation under this updated context, either via inline continuation (appending diagnostics as comments) or patch-based repair (requesting a minimal diff).

Control Flow

The process operates as an inner loop within a broader test-time scaling strategy (e.g., self-refinement):

1. GENERATE: Extend the token prefix to the next structural boundary.
2. VERIFY: Render the prefix and run oracles.
3. COMMIT: If all oracles pass, checkpoint the prefix.
4. RECOVERY: If any oracle fails, update the feedback state, roll back to the appropriate scope, and regenerate.
5. TERMINATE: End the loop upon program-level success or budget exhaustion (bailout).

Key Contributions

1. Framework Design: DTV is the first framework to treat structural boundaries as meta-steps for verifier-guided decoding, separating the controller, verification scopes, and verifier suite as configurable components.
2. Mechanism Integration: It combines three distinct mechanisms—structural-boundary verification, scope-aware rollback with escalation, and diagnostic feedback augmentation—to prevent error propagation and reduce wasted tokens.
3. Empirical Validation: The authors evaluate DTV on two translation tasks with complementary verifier structures:
   • C-to-Rust: Combines compiler checks (rustc) with differential testing.
   • JavaScript-to-TypeScript: Relies on static type checking (tsc) and linting (ESLint).

Experimental Results

The evaluation uses Qwen3-4B and Gemma-4-E4B as generators under matched token budgets (16x source tokens).

Performance Gains

• C-to-Rust: DTV with self-refinement improves the compile pass rate from 72.3% (naive self-refine) to 82.0%.
• JavaScript-to-TypeScript: DTV improves the pass rate from 33.3% to 46.0%.
• Token Efficiency: DTV achieves these higher pass rates while using fewer tokens per case on average compared to naive baselines.
• In-Loop Impact: Even without outer-loop retry (one-shot), in-loop verification alone improves pass rates by +30.7 pp (C-to-Rust) and +16.7 pp (JS-to-TS) over direct decoding.

Comparison with Baselines

• Pareto Dominance: DTV/self-refine occupies the upper-left region of the cost-vs-pass-rate frontier, outperforming naive self-refinement, Best-of-N (BoN), and the compile-feedback-based S* baseline.
• Cost Efficiency: S* achieves lower pass rates (75.5% vs 84.5% on C-to-Rust) while consuming roughly 4.7x more tokens per case. DTV's advantage stems from verifying at structural boundaries within a single attempt, converting signals into early localized rollback rather than full restarts.
• Cross-Model Robustness: The gains transfer to Gemma-4-E4B, with DTV outperforming naive baselines on three of four model-task pairs.

Ablation Studies

Removing any of DTV's three key mechanisms reduces performance:

• No Feedback: Pass rate drops by 11.0 pp (inner-loop resampling without diagnostic guidance is inefficient).
• No Escalation: Pass rate drops by 6.0 pp (restricting rollback to statement scope fails to fix non-local errors).
• Detect-and-Abort: Pass rate drops by 15.0 pp (deferring recovery to outer loops wastes budget on failed inner attempts).

Significance and Claims

The paper claims that verifier-guided decoding is an effective use of inference-time compute for code translation. By shifting verification from a post-hoc filter to an integral part of the decoding process, DTV:

1. Prevents Error Accumulation: It stops models from extending corrupted prefixes, addressing the exposure bias inherent in autoregressive generation.
2. Optimizes Compute: It converts the same verifier signals into early, localized repairs rather than discarding entire generations, leading to a more favorable pass-rate-cost tradeoff.
3. Generalizes: The framework is applicable to any task with deterministic process-level verifiers and structural renderers, though the current evaluation is limited to code translation.

The authors note that DTV relies on oracles that provide local, actionable diagnostics and requires non-trivial implementation effort for new tasks (renderers, parsers, oracle drivers). They do not claim DTV solves non-local semantic errors requiring global redesign or that it guarantees behavioral equivalence on all inputs, only that it improves compile-time correctness and reduces token waste for the evaluated tasks.