Technical Summary: Enhancing Table Reasoning with Deterministic Table-State Rewards

Problem Statement

Large Language Models (LLMs) and Vision-Language Models (VLMs) struggle with multi-step reasoning over structured tables. The core issue is the lack of explicit supervision for intermediate reasoning states. In tool-using agents (e.g., Chain-of-Table, Tree-of-Table), the agent manipulates a table through a sequence of operations (filter, project, sort, aggregate, join). Without a signal to evaluate the quality of these intermediate tables, errors compound silently: the agent may drop query-relevant evidence, retain irrelevant content, or apply operations excessively.

Existing solutions fail to address this cleanly:

• Final-answer rewards are too sparse to guide intermediate transformations.
• Executor-based verifiers require runnable environments (e.g., SQL executors) unavailable for complex tasks like multi-table joins or open-ended analytics.
• Learned reward models require costly preference data and are brittle across domains.
• Semantic-similarity rewards (embedding-based) often truncate long serialized tables, destroying state information, and fail to capture exact numeric or symbolic differences.

Methodology

The paper introduces TABROUGE and the RE-TAB framework to address these gaps using a training-free, deterministic approach.

1. TABROUGE: A Deterministic State Reward

TABROUGE adapts the Longest Common Subsequence (LCS) metric from text summarization (ROUGE-L) to evaluate tabular states.

• Mechanism: After each action, the intermediate table state $T_{l+1}$ is serialized into a deterministic textual sequence using a "[header] is [value]" format.
• Scoring: The reward is calculated as the LCS between the query $Q$ and the serialized table, normalized by the length of the serialized table:
  $$r_{\text{TABROUGE}}(a_l, T_{l+1}, Q) = \frac{\text{LCS}(Q, \text{Enc}(T_{l+1}))}{|\text{Enc}(T_{l+1})|}$$
• Design Rationale:
  • Lexical Precision: Unlike embeddings, it preserves exact numeric and symbolic strings without truncation.
  • Structural Integrity: The order-preserving LCS rewards row-level header-value coupling, which bag-of-words metrics (like BM25) miss.
  • Anti-Hacking: The denominator penalizes "bloat" (e.g., duplicating query tokens), making "echo-column" hacking unprofitable as it inflates both numerator and denominator at the same rate.

2. RE-TAB: A Training-Free Framework

RE-TAB utilizes TABROUGE as a plug-and-play signal for two levels of control:

• Step-Level Feedback: The scalar reward is appended to the prompt after each action, conditioning the next step on cumulative state quality rather than just token confidence. It also serves as a rolling-variance stopping criterion; when the reward signal stabilizes (variance drops below a threshold), the agent stops exploring and commits to an answer.
• Trajectory-Level Selection (Test-Time Scaling): The agent samples multiple independent reasoning trajectories. The aggregated state-supervision signal (sum of step rewards) is used to rank and select the best trajectory ($\tau^*$), replacing standard action-confidence voting or uniform majority voting.

Key Contributions

1. TABROUGE: A deterministic, query-to-state reward that requires no learned models or executors. It provides a scalable signal grounded in the query-table pair, specifically designed for serialized table states.
2. RE-TAB Framework: A two-phase implementation that integrates TABROUGE for both stepwise feedback and trajectory ranking. It operates as a "training-free" wrapper around existing tool-using agents.
3. Empirical Validation: Comprehensive evaluation across six backbones (ranging from small open-weight models to frontier models like GPT-5.4) and three benchmarks (WTQ, MMQA, MMTU).
4. Failure Mode Analysis: A detailed characterization of where lexical supervision is reliable and where it may fail (e.g., paraphrase under-rewarding, renamed columns), providing boundaries for its application.

Results

• Accuracy Gains: Across six backbones and three benchmarks, RE-TAB improves accuracy by an average of 26.7 percentage points (pp) over no-reward baselines.
• Efficiency: The framework reduces the number of Test-Time Scaling (TTS) samples required to reach 95% accuracy by up to 33% compared to action-confidence voting.
• Comparison to Trained Models: Despite having no learned parameters, TABROUGE matches or exceeds the performance of trained Process Reward Models (PRMs) like Qwen2.5-Math-PRM-72B and TaTToo on 4 out of 5 evaluation sets.
• Post-Training Viability: Preliminary experiments using Group Relative Policy Optimization (GRPO) with TABROUGE as a reward signal show an additional 8.34 pp gain over the training-free framework, suggesting its utility for policy-level fine-tuning.
• Robustness: The method remains effective across different model sizes, including frontier models where intermediate-state failures persist.

Significance and Claims

The paper positions TABROUGE not as a universal semantic verifier, but as a deterministic control signal scoped to serialized table-state supervision. Its significance lies in:

• Scalability: It provides a grounded signal for table reasoning without the need for expensive executors or large-scale preference data collection.
• Transparency: It makes the "world model" view of table reasoning explicit by supervising the quality of intermediate states, aligning table agents with the state-based reasoning used in vision and language agents.
• Practicality: It offers a "plug-and-play" solution that improves reasoning quality and reduces token costs for existing tool-using agents without retraining the base model.

The authors acknowledge limitations, noting that TABROUGE relies on fixed serialization and may under-reward semantically correct but lexically mismatched states (e.g., paraphrases or unit conversions). However, they argue that as a relative ranking signal within a trajectory, these issues do not negate the headline gains, and the method remains reliable for the majority of table reasoning tasks.