Enhancing Table Reasoning with Deterministic Table-State Rewards

Structured table reasoning has evolved from rule-based semantic parsing to deep learning approaches like TAPAS, TaBERT, and RAT-SQL, which leverage pretraining and supervised intermediate signals. Despite progress, these methods rely heavily on annotated data or external executors, limiting scalability and domain transferability. Recent advances incorporate symbolic and multi-step reasoning, but often depend on environment-specific answer verification or learned reward models, which are costly and brittle. The challenge remains to develop a universal, scalable supervision mechanism that can guide models through complex reasoning steps without extensive training or external tools. This paper situates itself within this context, aiming to fill the supervision gap with a simple yet effective deterministic reward based on lexical matching.

Existing reward signals for table reasoning are sparse or task-dependent, making it difficult for models to learn intermediate transformations effectively. Learned reward models require costly annotations and are domain-specific, while answer-based rewards only provide sparse feedback at the end. External executors or answer checkers are often unavailable for complex operations like multi-table joins or schema understanding. Consequently, models struggle to detect when they have lost relevant evidence or over-applied operations, leading to error accumulation. This bottleneck hampers the development of robust, scalable multi-step reasoning systems capable of handling diverse and complex tabular data.

The key innovation is the development of TABROUGE, a deterministic, structure-aware reward based on LCS, which evaluates intermediate table states without training. It serializes tables into a standardized string format, preserving exact numeric and symbolic information, and compares these against queries. This approach addresses the limitations of embedding-based rewards, which often truncate long tables and lose structural fidelity. The RE-TAB framework integrates TABROUGE into a control paradigm, supervising each reasoning step with a relative score, and employs trajectory-level ranking via TTS. This combination enables scalable, domain-agnostic supervision, significantly improving multi-step reasoning accuracy and efficiency without additional training.

• �� Serialize each intermediate table into a deterministic string using the '[header] is [value]' format.
• �� Compute the LCS between the serialized table and the query to measure lexical coverage.
• �� Normalize the LCS length by the total serialized table length to obtain a relative reward.
• �� During reasoning, after each action, evaluate the post-action state with TABROUGE, providing stepwise feedback.
• �� Implement early stopping based on rolling variance of TABROUGE scores to avoid over-processing.
• �� Generate multiple reasoning trajectories, score them cumulatively, and select the highest-scoring trajectory using TTS.
• �� Integrate this process into existing reasoning pipelines, replacing traditional sparse or learned rewards.

The authors evaluate RE-TAB on datasets WTQ, TabFact, and MMQA, across models from small open-weight architectures to GPT-5.4. They compare no-reward, embedding-based, and TABROUGE-based rewards, focusing on accuracy improvements and sample efficiency. Hyperparameters such as discount factors and early stopping thresholds are tuned to optimize performance. Ablation studies analyze the contribution of stepwise feedback and trajectory ranking. Results show consistent accuracy gains, with an average increase of 26.7 points, and a reduction in required samples by up to 33%. Additional tests examine robustness and failure modes, validating the method’s scalability and reliability.

RE-TAB achieves an average accuracy boost of 26.7 percentage points over baseline models without rewards, with the highest gains on TabFact (up to 30.3 points). It reduces the number of TTS samples needed by roughly one-third, demonstrating efficiency. The approach outperforms trained reward models like PRM, matching or exceeding their performance on multiple datasets, with gains up to 8.34 points in post-training scenarios. Ablation results confirm that stepwise, deterministic rewards improve both intermediate reasoning and overall trajectory selection, especially in complex multi-step tasks.

This framework can be directly applied to automated data analysis, complex question answering, and enterprise data management, especially in scenarios involving multi-table joins and schema understanding. Its training-free nature allows easy integration into existing systems, reducing costs and increasing robustness. Long-term, it could enable autonomous AI agents capable of reasoning over diverse structured data sources, supporting decision-making, scientific research, and intelligent data-driven services across industries.

TABROUGE’s lexical matching may undervalue paraphrased or synonym-replaced states, leading to under-rewarding correct reasoning. It is sensitive to column renaming and reordering, which can bias the reward signal. In highly noisy or large-scale tables, serialization might omit subtle structural cues, affecting accuracy. The method’s reliance on string serialization also limits its effectiveness in dynamic or highly heterogeneous data environments. Future work should incorporate semantic understanding and adaptive serialization to address these issues.