acceptodds
Withdrawn from ICLR 2027

Expressive Power of Transformers for Nested Logical Filtering in Table Reasoning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study the expressive power of Transformers in table reasoning. We approach this question through Nested Logical Filtering (NLF), one of the fundamental operations of table reasoning, which evaluates a Boolean query on every row. Longer chains of thought (CoT) expand what Transformers can compute, but expressive power alone does not ensure reliable answers on growing tables. We identify the core challenges of solving NLF with CoT through theoretical and experimental analysis, spanning evaluating nested queries and reliably answering questions. The decision version of NLF is NC1-complete even on a one-cell table, yielding a conditional barrier for constant-depth, log-precision Transformers with O(log N ) CoT emissions, where N is the encoded input length. Polynomial-length CoT can nevertheless compute the full answer exactly. We then compare answer generation with program-of-thought (PoT) execution under a common symmetric token-substitution channel. With a fixed vocabulary and positive noise rate, every direct-readout CoT system has exact-answer success at most exponentially small in the row count, regardless of reasoning length. A system emitting a fixed, constant- length program retains a positive success lower bound when execution on clean input and its output are noiseless. Synthetic experiments illustrate the resulting exposure contrast. WikiTableQuestions and DataBench provide complementary evidence on table size and answer structure. The guarantees depend on the output interface, separating computational capability from reliable delivery.

Primary area:
learning theory
Keywords:
transformers, table reasoning, chain-of-thought, program-of-thought, circuit complexity

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_tWYbOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper examines Transformers for Nested Logical Filtering. Here, boolean queries are evaluated across table rows. The authors compare CoT with Program of Thought, showing that direct textual outputs become susceptible to token errors as answer length grows. They evaluate on WTQ and DataBench.

Critical strengths
  1. Authors give a formal characterization of there approach and the limitations of short CoT LLMs.
  2. There is a good discussion on the distinction on correctness of an answer vs the ability to reliably generate it.
  3. Experiments are well thought out and directly support the claims across synthetic and public benchmarks.
Critical weaknesses
  1. Limited novelty beyond theoretical contribution. NC1 result builds on the problem formulation, and the noise-robustness separation reflects the inference algorithm. The paper needs to be more clear which results are new vs established.
  2. Assumptions limit application: They favor PoT but are not directly characterizing LLM generation errors.
  3. Experiment comparison: PoT gets 8 rounds, CoT does not have an equivalent correction mechanism. Experiments do not cleanly separate the prosed explanation.
  4. Limited size: only 20 synthetic samples, 40 per group on the public. Please note which deep seek checkpoint is used for the backbone.
Questions for authors
  1. Can the authors highlight which results are new beyond existing results?
  2. Fairness: can the authors provide an apple to apple comparison between PoT and CoT?
  3. Reproducibility: Specify model checkpoint and which samples used from public datasets.
Reviewer_jXKUOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors focus on the expressive power of transformers on the task of table reasoning, on Nested Logical Filtering (NLF) that runs Boolean queries on table rows. They studied this problem through theoretical and experimental analyses. On the theoretical side, the authors show the decision version of NLF is NC^1-complete on a single-cell table, a conditional barrier based on the established result that O(log N) chain-of-thought (CoT) tokens stay in TC^0 and polynomial CoT can compute the full row answer exactly. On the empirical side, the authors used synthesised NLF with different sizes, WikiTableQuestions and DataBench to show PoT (program-of-thought) beats textual CoT, with bigger gaps on larger tables. The paper also shows that with token-substitution noise, CoT fails exponentially in table size, whereas a PoT maintains a constant success rate.

Critical strengths
  1. The paper is honest about the scope and states upfront the limitations of the results, e.g., no learned systems, different noise protocols.

  2. The writing is generally clear, and the presentation is good.

  3. The distinction between computing the answer versus delivering the answer reliably through the output interface is thoughtful and clear.

Critical weaknesses
  1. Motivation for studying the expressive power of Transformers on this specific problem. While the authors established the importance of NLF, it is unclear why studying the expressiveness property specifically is interesting, and what problems this solves.

  2. The injected-noise result is determined by output length. TCoT answers have more characters perturbed and would be more likely to suffer from critical corruption. In practice, the error rates of PoT and TCoT are likely not the same.

  3. Mismatch between the theory and empirical setting. Definition 4.1 assumes that the corrupted tokens are fed back into the model, but the noise perturbation test takes place after generation. The authors could consider corrupting tokens during generation and feeding them back, or use temperature > 0 sampling as a source of model-generated errors.

  4. The connection between theory and experimental findings is currently weak. TCoT has to generate the answer completely, and a longer answer would mean that the model has more room to make errors. In contrast, PoT generates a program that stays the same length regardless of the table size. This is anticipated in the LLM community, but the TCoT collapsing to zero with no noise is not explained.

Questions for authors
  1. What is the error rate of PoT and TCoT at non-zero temperature?

  2. Why does TCoT not get a retry on WikiTableQuestions and DataBench? What would happen if you run PoT with single-shot, no repair?

  3. Why does TCoT collapse even without noise introduced (TCoT drops from 30% to 0% at ε = 0)? The authors should check if this is an artefact of model failure, for example, a repetition loop.

  4. How can TCoT collapse to 0 with no noise be explained in the theoretical framework?

Reviewer_PfbMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the computational expressiveness and output reliability of Transformers for Nested Logical Filtering (NLF), which evaluates a Boolean query on every table row. It establishes NC¹-completeness of the decision problem, derives a conditional impossibility result for logarithmic-length CoT, and gives a polynomial-length CoT construction for exact full-answer computation. Separately, under an independent token-substitution channel, it proves exponentially decreasing exact-answer success for a restricted direct-readout interface, while a fixed correct program retains a positive success lower bound through clean execution. Experiments compare textual CoT and program-of-thought on synthetic filtering tasks, WikiTableQuestions, and DataBench. The empirical protocols differ from the theoretical channel, and public-benchmark PoT additionally receives execution-feedback repair.

Critical strengths
  1. The distinction between computational capability and reliable answer delivery is useful. A system may be expressive enough to compute an answer while remaining unreliable when explicitly generating a long vector of decisions. Formalizing this distinction offers a relevant perspective on when execution-based interfaces can help.

  2. The paper carefully states several important boundaries of its results. It distinguishes input length from row count, worst-case hardness from benchmark accuracy, and existence of a correct program from successful learned program generation. The treatment of random seeds and predictable commitment times makes the assumptions explicit, while Appendix E.5 demonstrates how external aggregation escapes the direct-readout bound. These qualifications improve the interpretability of the theoretical claims.

Critical weaknesses
  1. The additional theoretical contribution appears limited relative to the existing expressiveness results and the imposed interface restrictions. The NLF hardness reduction essentially embeds Boolean formula evaluation into a one-cell table, while the short-CoT barrier and polynomial-CoT sufficiency build directly on existing simulation results. The reliability theorem provides an interface separation for unrestricted generators: the direct-readout side must transmit every answer block without cross-position error correction, whereas the PoT construction sends a fixed evaluator that accesses the clean table and formal query. Appendix E.5 already shows that repetition with external majority decoding can make textual transmission reliable. The manuscript acknowledges these boundaries, but it remains unclear what substantial new conclusion about Transformer-based table reasoning follows beyond this useful synthesis.

  2. The empirical evidence is not sufficiently reproducible or controlled to establish the proposed explanation. Appendix F, lines 1595–1600, explicitly states that the precise model checkpoint, channel-resampling count, and averaging procedure for some benchmark scores are unavailable. Table 2 reports 40 instances per stratum, yet values such as 0.788 and 0.838 require an aggregation procedure beyond a single binary judgment per instance; that procedure is unspecified. Moreover, synthetic exponential fits use only two row counts with nonzero textual-CoT accuracy, and corruption is applied after generation rather than fed back. Public-benchmark PoT receives up to eight execution-feedback rounds without a corresponding textual-CoT repair control. These issues prevent reliable attribution of the observed differences to the output interface and materially weaken the empirical contribution.

Questions for authors
  1. Clarification of contribution: Which result constitutes the principal technical advance beyond Li et al. (2024) and prior work on Boolean-formula/compositional reasoning? In particular, what new difficulty is introduced by the full-table setting beyond applying existing simulations to multiple outputs?

  2. Clarification of experimental records: Can you provide the exact model checkpoint, prompts, substitution alphabet, resampling count, per-instance predictions, judge protocol, and score-aggregation procedure? How are the Table 2 values obtained from 40 instances, and which instances contribute to the reported first-error estimate of 37/1053?

  3. Evidence that could change my assessment: What are the public-benchmark results for single-shot PoT, before execution-feedback repair? A comparison with repeated textual answers and deterministic majority decoding would also help establish whether the proposed interface explanation predicts a practically meaningful advantage. These are requests to assess the present interpretation, rather than suggestions to expand the paper to unrelated tasks.

Reviewer_RQgROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper formally analyzes transformer-based table reasoning, focusing on the computational complexity of nested logical filtering, the CoT required to perform it, and the reliability tradeoffs between generating answers directly and executing generated programs. The paper contains interesting and sound theoretical results, but the empirical evaluation does not meaningfully test the central computational theory, and the theoretical conclusions themselves are narrower than the broad framing around transformer table reasoning suggests.

Critical strengths
  1. Theoretical characterization of table computation. The result showing nested logical filtering is NC^1-complete even for a single-row table is nice. Distinguishing query complexity from table size is a useful conceptual contribution. The conditional lower bound for logarithmic CoT and the polynomial-CoT upper bound help to characterize table operations in LLMs.
  2. Separating reasoning difficulty from output reliability. The paper considers two different theoretical issues: (1) whether a transformer can compute NLF under different CoT budgets, and (2) whether a computed multi-bit answer can be reliably communicated through a particular noisy direct-readout interface. The latter, however, is not a transformer-specific limitation.
  3. Comparison with program execution. The paper provides a useful contrast between direct textual reasoning and program-based execution, illustrating how external computation can avoid the need to generate long answers. However, this is primarily an illustration of an established advantage of tool use, rather than a formal characterization of the cost–accuracy tradeoff between internal reasoning and external computation.
Critical weaknesses
  1. The empirical evaluation does not adequately test the theoretical claims. The paper provides two theoretical results: a computational limitation arising from increasing nested-query complexity, and an output-reliability limitation arising from transmitting increasingly long answers through an independent token-noise channel. However, the synthetic experiments primarily vary table size while fixing query depth at two, so they do not directly test the paper’s main computational hardness result, which involves increasing query complexity. Moreover, textual CoT accuracy collapses as table size increases even without injected output noise, a phenomenon not explained by the output-reliability theorem. It therefore remains unclear whether the observed failures arise from computational complexity, long-output generation, or other factors. The comparison with PoT does not resolve this ambiguity because PoT delegates the filtering computation itself to pandas, rather than merely changing the output interface. Finally, the experiments use only 20 examples per table size and a single model backbone, further limiting the connection between theory and observed model behavior. Experiments that independently vary query depth, table size, and CoT budget would much more directly test whether the theoretical predictions characterize practical LLM performance.
  2. Limited transformer-specific insight. The NC^1 hardness follows by encoding Boolean formula evaluation into nested predicates, while the short-CoT lower bound follows by combining this reduction with existing characterizations of CoT transformers. Similarly, the output-reliability result applies to unrestricted generators under an independent noise channel rather than arising from transformer architecture. Thus, while the paper connects existing theory to table reasoning in a technically coherent way, it is less clear what new insight it provides specifically about transformer computation.
  3. Limited connection to the broader theory of query computation. NLF closely resembles nested Boolean predicates in SQL WHERE clauses, but the paper does not situate the task relative to the extensive literature on database query expressiveness and complexity. It is therefore unclear how much of the theoretical characterization is specific to the proposed formulation, or how the results extend to more representative table operations such as projection, aggregation, joins, and nested subqueries.
Questions for authors

See comments above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.