- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper formalizes bounded-error sampled CoT for constant-depth, constant-precision Transformers. It extends circuit upper bounds and sensitivity-based lower bounds to this setting, and relates polynomial-resource probabilistic CoT to P/poly in the nonuniform setting and BPP under uniformity.
Critical strengths
The overall framework is conceptually clean.
Critical weaknesses
I find the technical novelty somewhat limited: extensions from deterministic to randomized computation follow naturally from existing simulations and standard probabilistic techniques.
Questions for authors
The paper could more clearly identify the new technical ideas required beyond adapting the existing deterministic proofs.
2 comments
Thanks for the responses. My concern largely remains. I keep my score.
Response to Reviewer 3
The questions of Reviewer 3 coincide with those of Reviewer 2. Please see our response to Reviewer 2, Question 1, for a theorem-by-theorem comparison with previous results. Also, in the revised version we add a sentence before each result to separate our contribution from the techniques of previous work. For the question about fine-grained regimes, please see our response to Reviewer 1, Question 3, where we describe the new applications to primality testing and polynomial identity testing. Finally, regarding the claim of a "more realistic model", please see the end of our response to Reviewer 2: we modified the abstract and the conclusions to state precisely which aspect of LLMs our model incorporates and which assumptions remain.