Pith. sign in

Paper Citation Record · LEDGER

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

As of 10 August 2026, this Paper Citation Record lists 44 of 44 outbound references and 4 inbound Pith citation observations for arXiv:2502.02393.

A citation records a reference. It does not transfer a finding from one paper to another.

pith.paper-citation-record.v1
2502.02393 v3

Coverage vector

measured 44 of 44 reference resolution

Typed states for the displayed outbound observations.

Source: paper_references, paper_reference_links, observed 2026-08-09T12:23:57.989726Z

measured 48 of 48 standing notices

One-hop event checks from named stored sources.

Source: scholarly_work_events, retraction_status_cache, observed 2026-08-09T06:31:02.800959+00:00

measured 4 of 4 inbound itemization

Pith citing papers itemized under the disclosed page cap.

Source: paper_references, paper_reference_links, observed 2026-08-03T20:57:09.438395Z

measured 1 of 1 external citation measurements

A source-named dated measurement, never combined with another source.

Source: arxiv_reference, observed 2026-08-05T02:28:24.338817Z

Reference resolution

44 of 44 outbound references displayed

  • verified exact0
  • verified fuzzy20
  • unresolved17
  • parse uncertain4
  • malformed identifier3
  • metadata mismatch0

External citation measurements

0
arxiv_reference, observed 2026-08-05T02:28:24.338817Z

Outbound references

Observation 2ed6408d-2aa5-4927-a47f-17693ea09256 · outbound

This paper cites The situation is different for parallel computation as performed by transformers: Many problems do have direct parallel solutions.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers The situation is different for parallel computation as performed by transformers: Many problems do have direct parallel solutions

Reference 1

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.667527Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.834409Z digest=sha256:c0d27334e01e01edd509eb818bd7f9294d5a2508d36a8a046effcce1ce82ef48

Observation 7e24c091-8eae-44d9-aa3f-9e05bf61ecb7 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 2

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.652970Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.839052Z digest=sha256:98b464cfad6e2827f4318af313e7031e2a9f2a20880521e0331dc1d226a8c885

Observation 2fff638b-a1a9-4bbf-af5d-92983cb89be9 · outbound

This paper cites Theoretical limitations of multi-layer Transformer.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Theoretical limitations of multi-layer Transformer

Reference 3

Resolution
unresolved
no resolver link, observed 2026-08-09T12:23:57.804636Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

source=pdf_text observed=2026-08-09T12:23:57.804636Z digest=sha256:182ca84a2c663e82a86db659b94d7a005cc1231fa937439d598876eb873099ba

Observation 41e8c9a9-6673-437b-9213-253eef0872b1 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 4

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.623062Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.849779Z digest=sha256:09a9be9980448dcad17fdef3ed4aaded1b096e167c4ee66fea2771e6f8f2a069

Observation a20aa124-19bc-45f0-874c-eda0e7b4521b · outbound

This paper cites How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs

Reference 5

Resolution
malformed identifier
no resolver link, observed 2026-08-09T12:23:57.814261Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

source=pdf_text observed=2026-08-09T12:23:57.814261Z digest=sha256:8bbba27e478a6d11a38402431f84b0366916f082e34d5ba5c0c88b0991560e9b

Observation e0ae232d-ede8-4e86-b337-a761520ba6f4 · outbound

This paper cites Lower bounds on transformers with infinite precision.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Lower bounds on transformers with infinite precision

Reference 6

Resolution
unresolved
no resolver link, observed 2026-08-09T12:23:57.818820Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

source=pdf_text observed=2026-08-09T12:23:57.818820Z digest=sha256:2bec5d6af603f062599f1cc7c59c9be32394482bacec420258d83b5bb322c3a6

Observation f41969af-0b35-486d-b939-d9d04147137e · outbound

This paper cites Ask, and it shall be given: On the Turing completeness of prompting.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Ask, and it shall be given: On the Turing completeness of prompting

Reference 7

Resolution
unresolved
no resolver link, observed 2026-08-09T12:23:57.824032Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

source=pdf_text observed=2026-08-09T12:23:57.824032Z digest=sha256:9a734bee788211f06e06c2b439dfb12ac47a55382e780795617d8ffaa10a59df

Observation 5e8362be-6f0a-4a8c-9a01-03e2a3e326b5 · outbound

This paper cites Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits

Reference 8

Resolution
unresolved
no resolver link, observed 2026-08-09T12:23:57.829205Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

source=pdf_text observed=2026-08-09T12:23:57.829205Z digest=sha256:54953e3d9f249756d2b5791ec70e21954431f6f8f3089e158c3871ab505af721

Observation d68a1469-0d65-4685-b3b6-2b12c737b463 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 9

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.547854Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.873748Z digest=sha256:260409fa5a42a1533e3c28abf9c1164516e65aebcf832d7c5e32cdbaba971af4

Observation 160a6dfd-a02d-4545-95f5-a77718590eb3 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 11

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.638548Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.844116Z digest=sha256:60661a5c02810923bba5aca86eecedba098e423438f96526b5b9402c63f28215

Observation e7bc93ff-3c56-4480-8101-d3fd7ec7f248 · outbound

This paper cites For instance, PARITY is a simple example of state tracking, a family of reasoning problems that have been of substantial interests and that still pose challenges for LLMs (e.g.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers For instance, PARITY is a simple example of state tracking, a family of reasoning problems that have been of substantial interests and that still pose challenges for LLMs (e.g

Reference 13

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.607322Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.854368Z digest=sha256:f00cf6936952c90d145a86b35555e9e1cb370c154be8999de842b93373e21ee6

Observation 3289191e-3553-4a60-8361-1998690b9f9b · outbound

This paper cites Why? The input alphabet needs to be finite for Theorem 3.3 to go through, because the proof of Lemma B.3 by Hahn (2020) involves a union bound over the alphabet.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Why? The input alphabet needs to be finite for Theorem 3.3 to go through, because the proof of Lemma B.3 by Hahn (2020) involves a union bound over the alphabet

Reference 14

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.592084Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.859618Z digest=sha256:9bdeeaf9b625ef6884e71492843887f0d8e1cadcd8f9c820e1562a5e809c6c33

Observation 7c68ef69-46b5-46f5-bab8-be4058460db9 · outbound

This paper cites Isn’t this unrealistic? What about the role of length generalization? It is true that, in practice, one will expect transformers to perform the tasks across input lengths.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Isn’t this unrealistic? What about the role of length generalization? It is true that, in practice, one will expect transformers to perform the tasks across input lengths

Reference 15

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.577022Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.864309Z digest=sha256:0490a1318b6d0a0f2cf3f1bcbede2deba85d4a9de6a91f986c6a9a9073534213

Observation 88fcc03d-6a11-4ca2-81fb-b5e14441d394 · outbound

This paper cites In particular, UHAT is bounded by AC 0, whereas softmax transformers are bounded by T C0.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers In particular, UHAT is bounded by AC 0, whereas softmax transformers are bounded by T C0

Reference 16

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.562746Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.869089Z digest=sha256:5b5d11b15cf97d5563ea21a5f0a93200fb5e71aac02eaa364f7676c680445013

Observation 47cca165-cb83-40e6-a3f9-4ada7330bf89 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 18

Resolution
parse uncertain
raw_fallback, observed 2026-08-09T12:23:58.533204Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.878498Z digest=sha256:4fa73030099ab60bedd4790e42f5953c48848084308fe8997e87439e075a431a

Observation 42643bd6-9925-4fc4-9560-f1cbd1d9b4ec · outbound

This paper cites By applying Lemma B.3 iteratively, L times.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers By applying Lemma B.3 iteratively, L times

Reference 19

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.519420Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.883160Z digest=sha256:a62cc504255d70491b1db43659f9f35897d38fb73033437a060251b00152e9ce

Observation 054c180d-0d4d-4765-8f39-b5cc456cfa41 · outbound

This paper cites Here, “ρ(3)” corresponds to the restriction ρ′ from the statement of the lemma.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Here, “ρ(3)” corresponds to the restriction ρ′ from the statement of the lemma

Reference 20

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.505231Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.887702Z digest=sha256:e14946d8f1ad765ca088c73d886663749c30c0ab568bd959bc67cdd745161a12

Observation 790de37a-4d11-4b3b-944d-1e5f35be3cb4 · outbound

This paper cites First, we obtain a restriction ρ(0), and integers c, k from Lemma 3.4, applying T only on the input x ∈ Σ∗ itself.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers First, we obtain a restriction ρ(0), and integers c, k from Lemma 3.4, applying T only on the input x ∈ Σ∗ itself

Reference 21

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.491288Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.892312Z digest=sha256:d597722f99453e84489cb5fc81af64ad706203004b6aa3bdea0148f8c1c6d3bd

Observation 13642b46-bee7-4ff2-8aa0-272493bd69ef · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 22

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.478548Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.896962Z digest=sha256:e0b7d535d2ee2899e9e99839432094dc73b4befa8b43a25dd0ef7e3b3f34570d

Observation 08664bc3-d590-4078-949c-1d84e1a8de71 · outbound

This paper cites dot-by-dot CoT.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers dot-by-dot CoT

Reference 23

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.464323Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.901255Z digest=sha256:35cf87666e45f8ff604c64922b14c3ef291db947587b05d9311d7a1400a345c4

Observation 157215f7-71d2-406a-af1f-a882e090f143 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 24

Resolution
parse uncertain
raw_fallback, observed 2026-08-09T12:23:58.450359Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.905295Z digest=sha256:94c84a134668ca7a3e90bf8fb0d639fe52996a88fcc02213768f5ec9af5d2688

Observation f1e57c3a-99c7-4b0a-9693-54c9964c5094 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 25

Resolution
parse uncertain
raw_fallback, observed 2026-08-09T12:23:58.436030Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.909350Z digest=sha256:03b9105fe522eb7104e8b6a92c7718531170077615c06882a9c127edee6cc813

Observation 65cecb05-ccae-44f3-83c6-aaebec03afa6 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 26

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.421806Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.913248Z digest=sha256:24f6562fa1798a3f66a4f744877c2aeac4f0bdf29097054720bdedcdd44eaf10

Observation 54acb11d-eeab-4eef-be72-c0bc16b5b5ae · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 27

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.406030Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.917270Z digest=sha256:8c9156f00e5659e5fc0dab45b1351bcd4b4015447b2095a8e8c5351fd69867bf

Observation 4899fcfa-a50e-4ef0-a77b-72c5578f60e1 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 28

Resolution
parse uncertain
raw_fallback, observed 2026-08-09T12:23:58.390936Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.921603Z digest=sha256:fd9766703c3202f87b13e2d38e3e070f7dc248519f1fa46c4d264e71d0e6858e

Observation 1e5201c1-c51b-4ff7-955b-58cb8b844950 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 29

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.376170Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.925755Z digest=sha256:ef1de02a05e068744685f0ed62df7115b5a4988a1dede969c24320f5a08e93aa

Observation 1fbb4e47-c178-4452-b2c6-e2e43406cb73 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 30

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.361906Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.930196Z digest=sha256:6fe9bddf2742f94c7fb42a5b50ae19a215801e2cdfeab40c5306b5e5b5b2ee0f

Observation ba150e93-b063-4aa8-94f4-3767c6da8f63 · outbound

This paper cites All remaining tape positions hold a blank symbol BLANK ∈ Σ.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers All remaining tape positions hold a blank symbol BLANK ∈ Σ

Reference 31

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.347133Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.934369Z digest=sha256:a3fd4c3b2e6f1fe823b90337af3715225d789e1cc11e31682735458efd8f8436

Observation 231408a6-7c7f-469b-8fcb-43f2c04743ea · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 32

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.332312Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.938533Z digest=sha256:7629d30f9fad327f5209749b1fd8e583a95b49937fadcb9e59539a2b0c4ebb89

Observation d93dc880-48ae-4efa-88f2-0c6d7b894b6a · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 33

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.317110Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.942478Z digest=sha256:4371f75ae88bca998496cbde798bceb1e4060c80b4b26686dc172401dd28683d

Observation 66396782-3b8a-482b-8ed3-2229c4503236 · outbound

This paper cites We first encode the input word as a string over the input alphabet Σ, followed by a separator symbol.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers We first encode the input word as a string over the input alphabet Σ, followed by a separator symbol

Reference 34

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.302892Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.946265Z digest=sha256:501067a1ff2f02fd7a33e2065e0a6abf3723eba0b88382c4e9d92fea088ab127

Observation 624657ac-bbaf-4f47-bfac-da67bbce207e · outbound

This paper cites 19 Lower Bounds for CoT Reasoning.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers 19 Lower Bounds for CoT Reasoning

Reference 35

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.288385Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.950263Z digest=sha256:ce05420556c12f61459e8a32b44c5080ca647b5943ebb95e90f467825508e639

Observation 4fdc6f53-e880-4772-ae9d-898d2da33c02 · outbound

This paper cites Turing programs.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Turing programs

Reference 36

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.274603Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.954478Z digest=sha256:dd6fc66e48e0081f04066882f2f558ea9f408bbdb774b0d0adb6784933bed10a

Observation 21395cfc-2124-44c7-b7da-3d1181b7e691 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Unresolved cited work

Reference 37

Resolution
unresolved
raw_fallback, observed 2026-08-09T12:23:58.260035Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.958591Z digest=sha256:3c59c4f433e930b641fb0d1b73fefdb6d34b14c74b13093eee8fdff81dc70a36

Observation ea12ce18-32fd-4b26-b059-4e16490af1a1 · outbound

This paper cites We show this using the characterization of regular languages in AC 0 by Barrington et al.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers We show this using the characterization of regular languages in AC 0 by Barrington et al

Reference 38

Resolution
malformed identifier
raw_fallback, observed 2026-08-09T12:23:58.244879Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.962409Z digest=sha256:e6be50f2c72d297868c51f7e2f7a0a221d67d0b746c73fdf80e05e1ce04024a6

Observation 951fa4a9-3778-4454-a0c6-52528dc742bd · outbound

This paper cites , M2N (and analogously for addition) in parallel.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers , M2N (and analogously for addition) in parallel

Reference 39

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.229227Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.966599Z digest=sha256:08b1f125203caf615ae22e193633b3b91d4472af8fe9be83c5f90c7c7c2a84b4

Observation 59588778-f524-46d8-9af1-93f369e2cef7 · outbound

This paper cites M2N (and analogously for addition).

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers M2N (and analogously for addition)

Reference 40

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.212842Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.970479Z digest=sha256:0f840f13e4f4a82dd08998bc50e56d127a089d9729265fcc89d322e6caff8a10

Observation e59177fa-2132-437b-865d-e0afb470c97e · outbound

This paper cites We expect that this setup will make the task feasible for transformers.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers We expect that this setup will make the task feasible for transformers

Reference 41

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.197213Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.974999Z digest=sha256:3554cb00a76c4aa15a782738a364968dfae616540b6aa524f0ae69cb07476edd

Observation 63b5920b-757d-43c4-8014-479ad69567c4 · outbound

This paper cites increment-by-1.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers increment-by-1

Reference 42

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.181087Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.979667Z digest=sha256:a6370f5221e78841a77fe4c7f5009338e11006896e195e9dc32f128da5f5e98a

Observation a3f84ea5-440e-45b7-85c9-69f409b1830e · outbound

This paper cites Conjecture E.2 thus provides a more optimistic prediction here than our results.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Conjecture E.2 thus provides a more optimistic prediction here than our results

Reference 43

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.164516Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.984971Z digest=sha256:7878871c29272be4e290c8d4601aa2d28023c6aa31f1699de50709121b8c321b

Observation 1083912c-4c02-44b4-8733-ddba00e93559 · outbound

This paper cites (2024) requires a linear-length CoT by Theorem 3.3, and can also be shown to not be representable at sub-linear average sensitivity under a reasonable input encoding.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (2024) requires a linear-length CoT by Theorem 3.3, and can also be shown to not be representable at sub-linear average sensitivity under a reasonable input encoding

Reference 44

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.148411Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.989726Z digest=sha256:44630c1183225fc8a7872ec639712839a0cda5e60ecd829fce4e6ab603ec5f74

Observation ff1f9449-eced-40e6-aaca-1e4c845ba365 · outbound

This paper cites Abb´e, E., Bengio, S., Lotfi, A., Sandon, C., and Saremi, O.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Abb´e, E., Bengio, S., Lotfi, A., Sandon, C., and Saremi, O

Reference 2023

Resolution
verified fuzzy
raw_fallback, observed 2026-08-09T12:23:58.682081Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.794912Z digest=sha256:151f545684413b49b61ee7012829d31fd56466ba7db12536e90df5864e8fe342

Observation 5ef45449-9471-4a80-b362-2a02d7e0eaa6 · outbound

This paper cites Learning High-Degree Parities: The Crucial Role of the Initialization.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Learning High-Degree Parities: The Crucial Role of the Initialization

Reference 2024

Resolution
malformed identifier
local_arxiv, observed 2026-08-09T12:23:58.131874Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-08-09T12:23:57.799757Z digest=sha256:adf34a35ddbc468e2a8b96974d97cddcf10adf6ef498e280236c41d25b77af09

Observation 62b6c806-972d-42b7-bc7e-9af5a335e79c · outbound

This paper cites Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count

Reference 8856

Resolution
unresolved
no resolver link, observed 2026-08-09T12:23:57.809581Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

source=pdf_text observed=2026-08-09T12:23:57.809581Z digest=sha256:841bbe7e486bf2168bc481abb9951af1d9b2abcf622c0069f2855e377510c0ea

Pith citing papers

Observation f0ea446a-36d9-4569-9757-835e1ba637ff · inbound

Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models cites this paper.

Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

Reference 12

Resolution
verified exact
arxiv_id, observed 2026-05-12T08:40:41.311770Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-05-12T08:40:40.910461Z digest=sha256:271feb7c219b572fed38081b151e92b11bb5ea6773f1db07eb20ba68c01f240c

Observation 4030c640-1a10-41e9-9fc0-0e6efc0c3cd3 · inbound

Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently cites this paper.

Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

Reference 1

Resolution
unresolved
no resolver link, observed 2026-08-03T20:57:09.438395Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

source=arxiv_source observed=2026-08-03T20:57:09.438395Z digest=sha256:3561becb68ccf6e2d26caa03161eae4ccaefb662212f00479a41ad5d294cea8b

Observation d57bf956-5b30-4e9a-80dc-8d8181c248be · inbound

On the Spatiotemporal Dynamics of Generalization in Neural Networks cites this paper.

On the Spatiotemporal Dynamics of Generalization in Neural Networks Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

Reference 26

Resolution
verified exact
arxiv_id, observed 2026-05-16T09:00:46.785226Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=pdf_text observed=2026-05-16T08:59:44.016444Z digest=sha256:17e19cbc3394233d4c2f4d12f4a029886a469d51d24a37572846b4844b9a67b0

Observation d415cefe-afb7-4efa-87d2-7840d60e20f9 · inbound

Agentic Transformers Provably Learn to Search via Reinforcement Learning cites this paper.

Agentic Transformers Provably Learn to Search via Reinforcement Learning Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

Reference 23

Resolution
metadata mismatch
arxiv_id, observed 2026-06-28T23:42:49.970053Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-09T06:31:02.800959+00:00.

source=arxiv_source observed=2026-06-28T23:26:28.158991Z digest=sha256:3ed50e2ebae225de3b1546670cd1f3ef8a5a2782007b6b375d888f8f54a16d86