Expressive Power of Transformers for Nested Logical Filtering in Table Reasoning

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.