In this case, we again examine how the presumption against retroactive legislation, a principle rooted in “[ejlementary considerations of fairness,” Landgraf v. USI Film Prods., 511 U.S. 244, 265, 114 S.Ct. 1483, 128 L.Ed.2d 229 (1994), applies in the context of immigration law. The government appeals from a judgment of the district court (Weinstein, J.) granting an aben’s petition for a writ of habeas corpus upon finding that the Antiterrorism and Effective Death Penalty Act’s elimination of section 212(c) discretionary relief was impermissibly retroactive as applied to him. We hold that the district court’s rationale for this conclusion was erroneous, but that there is an alternative basis for finding impermissible retroactivity that may apply in this case. We therefore *630vacate the judgment and remand to the district court for further proceedings.
BACKGROUND
Petitioner Nevio Restrepo (“Petitioner”), a Colombian national, entered the United States as a lawful permanent resident in 1969. In 1992, after a jury trial in federal court, he was convicted of conspiracy to distribute cocaine in violation of 21 U.S.C. § 846, and he was sentenced to a term of imprisonment.1 On October 28, 1996, the Immigration and Naturalization Service (“INS”)2 served Petitioner with an Order to Show Cause, charging him with deport-ability as an aggravated felon under the then-effective provision of section 241 (a) (2) (A) (iii) of the Immigration and Nationality Act (codified at 8 U.S.C. § 1251 (a)(2)(A)(iii) (1994)). This charging document was filed with the immigration court on November 19,1996.
At his hearing before an Immigration Judge (“IJ”), Petitioner, through counsel, conceded deportability. The IJ held that Petitioner was ineligible for any form of relief and entered a deportation order on September 9, 1997. Petitioner appealed, and the Board of Immigration Appeals (“BIA”) dismissed the appeal, holding that Petitioner’s aggravated felony conviction rendered him ineligible for 212(c) relief3 under section 440(d) of the Antiterrorism and Effective Death Penalty Act (“AED-PA”), Pub.L. No. 104-132, 110 Stat. 1214, 1277 (Apr. 24, 1996),4 and that this was so despite the fact that Petitioner was convicted prior to the enactment of the AED-PA.5
*631Petitioner then filed a habeas petition pursuant to 28 U.S.C. § 2241 in the United District Court for the Eastern District of New York, arguing: 1) that, under Landgraf v. USI Film Prods., 511 U.S. 244, 114 S.Ct. 1483, 128 L.Ed.2d 229 (1994), the AEDPA’s section 440(d) may not be applied retroactively to his criminal act and conviction, and 2) that section 440(d) violates equal protection principles by barring deportable aliens, but not excludable aliens, from applying for 212(c) relief.
In a September 22, 1999 order, the district court (Weinstein, J.) held that section 440(d) “may not be applied retroactively to Petitioner,” a conclusion it reached on the basis of its prior rulings. See Maria v. McElroy, No. 98CY6596, 1999 WL 680370 (E.D.N.Y. August 27, 1999), superseded by 68 F.Supp.2d 206, 228-30 (E.D.N.Y.1999) (Weinstein, J.) (holding that Congress did not intend for section 440(d) to be applied retroactively and that, even if Congress’s intent were ambiguous, application of section 440(d) to an alien’s pre-AEDPA criminal conduct would have an impermissible retroactive effect under the second step of Landgrafs retroactivity analysis); Pottinger v. Reno, 51 F.Supp.2d 349 (E.D.N.Y.1999) (Weinstein, J.) (same).6 Finding it unnecessary to rule on Petitioner’s equal protection claim, the district court granted the writ, thereby vacating the Petitioner’s final order of deportation and directing the INS to adjudicate Petitioner’s application for 212(c) relief. The government appealed.
DISCUSSION
We agree with the government that the specific ground upon which the district court granted habeas has been fatally undermined by our subsequent case-law analyzing the AEDPA’s retroactive reach under Landgraf, 511 U.S. 244, 114 S.Ct. 1483. Under Landgraf, a court determines whether a civil statute applies retroactively by first assessing whether Congress “has expressly prescribed the statute’s proper reach,” id. at 280, 114 5.Ct. 1483; if it has, the inquiry is over and the court must implement Congress’s intent. But if Congress’s intent is ambiguous, a court must proceed to the second question, which is whether, in view of the “familiar considerations of fair notice, reasonable reliance, and settled expectations,” id. at 270, 114 S.Ct. 1483, the application of the statute to the case at hand would have a “retroactive effect,” id. at 280, 114 S.Ct. 1483. If it would, then the court will adhere to the traditional presumption that Congress did not intend the statute to apply. Id. at 280, 114 S.Ct. 1483.
In St. Cyr I, after determining that Congress’s intent on the retroactivity of the AEDPA’s section 440(d) was ambiguous, we held that the elimination of 212(c) eligibility with respect to aliens who pled guilty to criminal charges before the enactment *632of the AEDPA would have an impermissible retroactive effect. St. Cyr v. INS, 229 F.3d 406, 420 (2d Cir.2000) (“St. Cyr I”), aff'd INS v. St. Cyr, 533 U.S. 289, 325, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001) (“St. Cyr II’’).7 In St. Cyr I, we rejected, though only in dicta, the position that the district court appears to have adopted in the instant case — that the application of section 440(d) to such an alien is “retroactive” because it would attach a new consequence to the alien’s criminal conduct. We stated that “[i]t would border on the absurd to argue that these aliens might have decided not to commit drug crimes, or might have resisted conviction more vigorously, had they known that if they were not only imprisoned but also, when their prison term ended, ordered deported, they could not ask for a discretionary waiver of deportation.” Id. at 418 (citing Jurado-Gutierrez v. Greene, 190 F.3d 1135, 1150-51 (10th Cir.1999)).
In Domond v. INS, 244 F.3d 81 (2d Cir.2001), we adopted this dicta as a holding and ruled that section 440(d) could properly be applied to an alien whose criminal conduct preceded, but whose guilty plea came after, the enactment of the AEDPA. Id. at 86 (“[I]t cannot reasonably be argued that aliens committed crimes in reliance on a hearing that might possibly waive their deportation.”).8 And recently, in Khan v. Ashcroft, 352 F.3d 521, 523-25 (2d Cir.2003), we held that Domond’s holding survives the Supreme Court’s reasoning in St. Cyr II, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347.
In the instant case, the district court based its grant of habeas on its prior decision in Maria v. McElroy, 1999 WL 680370, which broadly held that section 440(d) could not be applied to an alien whose criminal conduct preceded the AEDPA’s enactment, since doing so would attach a new liability to a past act. Given Domond, it is clear that this ground is contrary to current precedent, and cannot stand.
Accordingly, the government argues that we should simply reverse the district court’s judgment and hold that Petitioner is not eligible to seek 212(c) relief. We disagree. On appeal, Petitioner contends that section 440(d) may not be applied retroactively to him for another reason, a reason that the district court had no occasion to address given the broad rationale upon which it disposed of the case. Specifically, Petitioner claims that, when he was convicted in 1992, INS regulations permitted him to file an application for 212(c) relief “affirmatively,” that is, before being placed in deportation proceedings. See 8 C.F.R. § 212.3(b) (providing that a 212(c) application may be filed “prior to, at *633the time of, or at any time after the applicant’s departure from or arrival into the United States”).9 Petitioner goes on to say that he decided to forgo this opportunity in reliance on his ability to apply for 212(c) relief at a later time, when, presumably, his 212(c) case would be stronger due to a longer record of rehabilitation- and community ties, and that the AEDPA’s elimination of that relief would disrupt his reasonable reliance and settled expectations.10
The crux of Petitioner’s argument is correct under both the Supreme Court’s and our retroactivity jurisprudence. We believe, however, that, on remand, the district court will have to make further inquiries in order to -determine whether Petitioner may himself claim the benefit of his argument.
In determining whether a statute has a “retroactive effect” under the second step of Landgraf, a court must make a “commonsense, functional judgment,” Martin v. Hadix, 527 U.S. 343, 357, 119 S.Ct. 1998, 144 L.Ed.2d 347 (1999), guided by “familiar considerations of fair notice, reasonable reliance, and settled expectations,” id. at 358, 119 S.Ct. 1998 (internal quotation marks omitted).11 Essentially, Petitioner argues that he gave up something of value (the opportunity to apply for *634212(c) relief immediately after his conviction) in reliance on his ability to apply for 212(c) relief at a later time. When, moreover, one considers the factors that an immigration judge weighs in making a 212(c) determination, it becomes perfectly understandable why some aliens convicted of a deportable crime might choose to wait to apply for 212(c) relief, but would only do so if they believed that 212(c) relief would remain available later.
In evaluating a 212(c) application, an immigration judge “must balance the adverse factors evidencing an alien’s undesirability as a permanent resident with the social and humane considerations presented in his behalf.” Lovell v. INS, 52 F.3d 458, 461 (2d Cir.1995) (internal quotation marks omitted). Favorable considerations include the duration of the alien’s residence in the country, his history of employment, the existence of property or business ties, evidence of service to the community, and “proof of genuine rehabilitation” if the alien has a criminal record. See Matter of Edwards, 20 I. & N. Dec. 191, 195 (BIA 1990) (citing Matter of Marin, 16 I & N Dec. 581, 584-85 (BIA 1978)). Adverse considerations, of course, include the “nature, recency, and seriousness” of an alien’s criminal record. Id. Thus, an alien convicted of a deportable crime would be motivated to wait as long as possible to file a 212(c) application in the hope that he could build a better case for relief — one that shows longer residence in the United States, deeper community ties, and, perhaps most significantly, stronger proof of rehabilitation.
Indeed, the BIA itself recognized this commonsense point in Matter of Gordon, 17 I. & N. Dec. 389 (BIA 1980). In that case, the District Director had sent letters to convicted aliens informing them that they might be deportable and inviting them to make an “advance” application for 212(c) relief (without first being put into deportation proceedings). An alien applied, and the INS rejected her application because of her failure, among other things, to show rehabilitation. On appeal, the BIA set aside this determination, holding that the Director had unfairly induced the application and observing that “[c]onfined aliens and those who have recently committed criminal acts will have a more difficult task in showing that discretionary relief should be exercised in their behalf than aliens who have committed the same offenses in the more distant past. Common sense and prudence suggest that a recently convicted alien should prefer to let a considerable time elapse before offering to demonstrate rehabilitation.” Id. at 391-92.
It cannot therefore be doubted that an alien such as Petitioner might well decide to forgo the immediate filing of a 212(c) application based on the considered and reasonable expectation that he would be permitted to file a stronger application for 212(c) relief at a later time.12 It seems equally clear that the AEDPA’s undermining of this settled expectation represents a prototypical case of retroactivity. Just like the aliens in St. Cyr, who sacrificed something of value — their right to a jury trial, at which they could obtain outright acquittal — in the expectation that then-guilty pleas would leave them eligible for 212(c) relief,13 an alien like Petitioner also *635sacrificed something — the shot at obtaining 212(c) relief by immediately filing an application — in order to increase his chances of obtaining such relief later on. Such an alien “conformed his or her conduct according to the availability of relief,” St. Cyr I, 229 F.3d at 420, and therefore had settled expectations that would be “severely upset,” id., were the AEDPA to be applied retroactively.14
While we do not doubt that Congress has the power, within constitutional limits,15 to create a statute that works such a disruption of settled expectations, Landgraf, St. Cyr II, and longstanding practice require us to presume that Congress did not mean to do so, at least in the absence of a clear indication to the contrary. See, e.g., St. Cyr II, 533 U.S. at 316, 121 S.Ct. 2271. “Requiring clear intent assures that Congress itself has affirmatively considered the potential unfairness of retroactive application and determined that it is an acceptable price to pay for the countervailing benefits.” Id. (internal quotation marks omitted). And vigilant adherence to our presumption against retroactivity would seem particularly important in the context presented here, given both the gravity of the consequences at stake, see, e.g., Delgadillo v. Carmichael, 332 U.S. 388, 391, 68 S.Ct. 10, 92 L.Ed. 17 (1947) (“Deportation can be the equivalent of banishment or exile. The stakes are indeed high and momentous for the alien who has acquired his residence here.”) (citation omitted),16 and the status of the *636group affected, see St. Cyr II, 533 U.S. at 315 & n. 39, 121 S.Ct. 2271 (noting that one of the reasons that retroactive legislation raises special concerns is that a legislature “may be tempted to use retroactive legislation as a means of retribution against unpopular groups or individuals”) (internal quotation marks omitted).
The government argues, however, that our recent decision in Rankine v. Reno, 319 F.3d 93 (2d Cir.2003), controls this case. In Rankine, we held that the IIRI-RA’s elimination of 212(c) relief was applicable to aliens who were convicted by jury trial. While it is true that Petitioner, like the aliens in Rankine, was convicted after a trial, the government is mistaken in asserting that “[t]he Rankine Court considered a retroactivity claim identical to that raised by the Petitioner in the case at bar.” Rankine resolved the narrower question of whether an alien detrimentally relied on the continued availability of 212(c) relief in deciding to go to trial rather than accepting a plea. Petitioner, by contrast, raises a separate and distinct reliance claim that Rankine did not have occasion to address since it arose outside the plea bargaining context.
We have no argument with Rankine’s reasoning or conclusion. Indeed, Rankine ’s underlying rationale suggests that the AEDPA may be impermissibly retroactive as applied to Petitioner. In discussing St. Cyr II, Rankine explained that it is “choosing to forgo fighting the conviction of a qualifying crime and enter a plea that leads to an expectation of relief from removal.” Id. at 100 (internal quotation marks omitted). The Rankine petitioners, by contrast, “assumed no similarly heightened expectation from their decision to go to trial.” Id. Rankine also found that “none of these petitioners detrimentally changed his position in reliance on continued eligibility for § 212(c) relief,” id. at 99, and that “the petitioners have pointed to no conduct on their part that reflects an intention to preserve their eligibility for *637relief under § 212(c) by going to trial,” id. at 100. The court concluded that “the lack of detrimental reliance on § 212(c) by those aliens who chose to go to trial puts them on a different footing than aliens like St. Cyr.” Id. at 102. See also Swaby v. Ashcroft, 357 F.3d 156, 161-62 (2d Cir.2004).
The grounds upon which Rankine distinguished its petitioners from those in St. Cyr serve equally well to distinguish aliens in Petitioner’s situation from those in Rankine. As in St. Cyr, aliens like Petitioner incurred a heightened expectation of prospective relief flowing from their choice to forgo filing an affirmative application in the hope of building a stronger record and filing at a later date. Furthermore, while aliens who elected a jury trial cannot “plausibly claim that they would have acted any differently if they had known about AEDPA,” Rankine, 319 F.3d at 102 (internal quotation marks and brackets omitted), it is certainly plausible that aliens who decided to forgo affirmatively filing a 212(c) application would have acted differently if they had foreseen the AEDPA’s enactment. Many might well have chosen affirmatively to file the “weaker,” but still valid, application. To the extent that aliens like Petitioner detrimentally adapted their positions in reliance of their expectation of continued eligibility for 212(c) relief, the factors considered in Rankine appear to weigh against proscribing such relief retroactively.
The government asserts that such an alien does not show the “quid pro quo type of reliance that was critical to the decision in St. Cyr.” While it is true that in St. Cyr II the Supreme Court discussed the quid pro quo nature of an alien’s guilty plea, see St. Cyr II, 533 U.S. at 322, 121 S.Ct. 2271 (“In exchange for some perceived benefit, defendants waive several of their constitutional rights (including the right to a trial) and grant the government numerous tangible benefits, such as promptly imposed punishment without the expenditure of prosecutorial resources.”) (internal quotation marks omitted), the Court never suggested that all parties who claim that a statute has a retroactive effect must show the disruption of a quid pro quo exchange. And it would be out of keeping with the reasoning of St. Cyr II to read such a quid pro quo requirement into that opinion. For in St. Cyr II, the Court observed that “categorical arguments are not particularly helpful in undertaking Landgraf’s commonsense, functional retroactivity analysis,” St Cyr. II, 533 U.S. at 324, 121 S.Ct. 2271, and cited its decision in Martin, 527 U.S. at 359, 119 S.Ct. 1998, which warned against a reliance on labels in determining the retroactivity of a statute. What is more, the Court has on other occasions, such as in Landgraf itself and in Hughes Aircraft Co. v. United States ex rel. Schumer, 520 U.S. 939, 117 S.Ct. 1871, 138 L.Ed.2d 135 (1997), found impermissible retroactivity in the absence of a disrupted bargain.17
*638St. Cyr II’s discussion of quid pro quo is a powerful explanation of how the “familiar considerations of fair notice, reasonable reliance, and settled expectations” applied in the particular factual setting presented in that case. And while that discussion must serve as one important guidepost in our essentially analogical task of judging, we cannot let it prevent us from applying our “ ‘sound ... instinct[s],’ ” Landgraf, 511 U.S. at 270, 114 S.Ct. 1483 (alteration in original), to litigants in different factual situations who conformed their conduct and expectations to the then-prevailing law.18
Having concluded that Petitioner’s ret-roactivity argument is valid,19 we. remand *639this case to the district court for it to determine whether Petitioner can himself claim the benefit of this argument. We do so because we deem it wise to let the district court decide, in the first instance, whether an alien such as Petitioner must make an individualized showing that he decided to forgo an opportunity to file for 212(c) relief in reliance on his ability to file at a later date (and, if he must, whether Petitioner can do so), or whether, instead, a categorical presumption of reliance by any alien who might have applied for 212(c) relief when it was available, but did not do so, is more appropriate.
Before the Supreme Court decided St. Cyr II, some courts of appeal had asked whether a particular alien who pled guilty showed “actual and reasonable reliance” on the availability of 212(c) relief. See, e.g. Mattis v. Reno, 212 F.3d 31, 40-41 (1st Cir.2000) (suggesting in dicta that, because the court was announcing a new rule, the district court might remand to the BIA for *640a determination of the alien’s actual reliance, but not deciding the issue because there was little reason to think that the alien had a “colorable claim of actual and reasonable reliance”);20 Magano-Pizano v. INS, 200 F.3d 603, 613-614 (9th Cir.1999) (stating that impermissible retroac-tivity may be established by a “specific factual showing” that a plea was entered in reliance on the availability of 212(c) relief and remanding to the district court to determine whether the AEDPA applied to the alien).
In St. Cyr II, instead, the Supreme Court took a categorical approach. It recognized that, “as a general matter, alien defendants considering whether to enter into a plea agreement are acutely aware of the immigration consequences of their convictions.” 533 U.S. at 322, 121 S.Ct. 2271; see id. at 322-23, 121 S.Ct. 2271 (citing evidence that aliens are routinely advised by counsel of the immigration consequences of pleading guilty). And, as a result, it did not require any specific showing that St. Cyr had, himself, based his guilty plea on any particular expectations concerning 212(c) relief.
We have not had briefs or oral arguments on whether the approach taken by the Supreme Court in St. Cyr II or a more individualized one is appropriate in the circumstances before us. Normally' — in the interest of judicial economy — we would remedy that absence by simply asking the parties to submit briefs to us on the question. But given the distinct possibility that the choice between categorical and individualized approaches may turn, at least in part, on facts that the district court is much better placed to evaluate than we are, we deem it prudent to remand the issue to that court for its learned consideration.
CONCLUSION
We have determined that the basis of the district court’s issuance of the writ is invalid, but that the application of the AEDPA to Petitioner may be impermissi-bly retroactive on a different rationale. We therefore VACATE the district court’s judgment and REMAND the case for proceedings consistent with this opinion.
. The record does not indicate the length of this term of imprisonment.
. This agency is now called the U.S. Bureau of Citizenship and Immigration Services, but we will refer to it as the INS in view of the period in which this case arose.
. Section 212(c) of the Immigration and Nationality Act provided in relevant part:
Aliens lawfully admitted for permanent residence who temporarily proceeded abroad voluntarily and not under an order of deportation, and who are returning to a lawful unrelinquished domicile of seven consecutive years, may be admitted in the discretion of the Attorney General without regard to the provisions of subsection (a) of this section!, which enumerates grounds for exclusion]....
8 U.S.C. § 1182(c) (1994). Because, read literally, this section only applies to aliens facing exclusion, not deportation, the BIA used to require that a deportable alien actually depart the country and return to be eligible for 212(c) relief. But in Francis v. INS, 532 F.2d 268 (2d Cir.1976), we held that this requirement violated the equal protection component of the Due Process Clause, because there was no minimally rational reason to treat differently "two classes of aliens identical in every respect except for the fact that members of one class have departed and returned to this country at some point after they became deportable.” Id. at 272; see also Swaby v. Ashcroft, 357 F.3d 156, 157 n. 1 (2d Cir.2004) (noting that this court has "long held” that section 212(c) applies to deportation). The BIA adopted our position in Matter of Silva, 16 I. & N. Dec. 26, 30 (BIA 1976), holding that "no distinction shall be made between permanent resident aliens who temporarily proceed abroad and non-departing permanent resident aliens,” id., with regard to their eligibility to apply for 212(c) relief.
. Section 440(d) of the AEDPA barred certain criminal aliens, including those convicted of aggravated felonies, from seeking 212(c) relief. See 110 Stat. at 1277. Congress later repealed section 212(c) and replaced it with a form of relief called "cancellation of removal.” See Illegal Immigration Reform and Immigrant Responsibility Act of 1996 ("IIRI-RA”), Pub.L. No. 104-208, § 304(a),(b), 110 Stat. 3009, 3009, 594-97 (Sept. 30, 1996). Petitioner's case, however, is not controlled by the IIRIRA, since that law only applies to deportation proceedings instituted after April 1, 1997. See Rankine v. Reno, 319 F.3d 93, 95-96 (2d Cir.2003).
. The BIA based this conclusion on the Attorney General’s decision vacating the BIA’s holding in Matter of Soriano, 21 I. & N. Dec. *631516, 1996 WL 426888 (BIA June 27, 1996). See Authority of the Attorney General to Grant Discretionaiy Relief from Deportation Under Section 212(c) of the Immigration and Nationality Act as Amended by the Antiterrorism and Effective Death Penalty Act of 1996, 1997 WL 33347804, at n. 4 (O.L.C.) (Op. Att’y Gen. Feb. 21, 1997). The BIA noted that, while Henderson v. INS, 157 F.3d 106 (2d Cir.1998), held that the AEDPA's section 440(d) did not apply retroactively to pending deportation proceedings, that decision reserved the question of whether section 440(d) applied to criminal convictions that occurred prior to the AEDPA’s enactment.
. Both of these holdings preceded this court’s decisions in St. Cyr v. INS, 229 F.3d 406 (2d Cir.2000), aff'd 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001), and Domond v. INS, 244 F.3d 81 (2d Cir.2001), as well as the Supreme Court’s decision in INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001).
. St. Cyr I and the other cases discussed here also applied the same retroactivity analysis to the elimination of 212(c) relief effected by the IIRIRA’s section 304. For convenience, we will only discuss these cases as they relate to the AEDPA’s section 440(d), since that is the only provision at issue in the instant case.
. We cannot, see Jones v. Coughlin, 45 F.3d 677, 679 (2d Cir.1995) (per curiam), and do not take issue with this statement. We do, however, note that, in the context of criminal sanctions, similar retroactive increases in penalties have been considered to raise serious concerns under the Ex Post Facto Clause, see, e.g., Warden, Lewisburg Penitentiary v. Marrero, 417 U.S. 653, 663, 94 S.Ct. 2532, 41 L.Ed.2d 383 (1974) (concerning retroactive elimination of parole eligibility), presumably because they violate notice rather than reliance interests. See generally Landgraf, 511 U.S. at 270, 114 S.Ct. 1483, on notice and reliance considerations in retroactivity analysis, and note 16, infra, on the punitive aspects of deportation sanctions. Nevertheless, the Ex Post Facto Clause has been held not to apply directly to deportation. See, e.g., Marcello v. Bonds, 349 U.S. 302, 314, 75 S.Ct. 757, 99 L.Ed. 1107 (1955).
. In full, section 212.3(b) provides as follows:
Filing of application. The application may be filed prior to, at the time of, or at any time after the applicant's departure from or arrival into the United States. All material facts and/or circumstances which the applicant knows or believes apply to the grounds of excludability or deportability must be described. The applicant must also submit all available documentation relating to such grounds.
8 C.F.R. § 212.3(b).
. The government points out that this particular reliance argument is new on appeal, although it does not seem to claim that the contention was forfeited. In fact, Petitioner’s decision not to raise this specific argument in his habeas petition is perfectly understandable. Almost none of this circuit’s AEDPA retroactivity cases had been decided when he applied for habeas relief. And, having readily won in the district court on a broad ground that had been expressly left open in Henderson, see 157 F.3d at 128 n. 28, he had little reason to spell out more specific grounds on which to base his reliance argument. In any event, Petitioner raised the general issue of the AEDPA’s retroactivity under Landgraf in his habeas petition, and we enjoy broad discretion to consider subsidiary legal arguments that were not specifically raised below. See Ford v. Bernard Fineson Dev. Ctr., 81 F.3d 304, 307 (2d Cir.1996).
We also find that Petitioner adequately exhausted his administrative remedies with regard to his retroactivity argument. See Theodoropoulos v. INS, 358 F.3d 162, 173-74 (2d Cir.2004) (holding that district court lacked jurisdiction to consider an alien’s retroactivity argument on habeas review because the alien had failed to exhaust his administrative remedies as required by section 1252(d) of the INA). Petitioner has satisfied this exhaustion requirement, because the BIA’s decision addressed the retroactivity of the AEDPA and considered the relevant authorities— Henderson v. INS and the Attorney General's decision vacating Matter of Soriano (see supra note 5).
. Landgraf cited Justice Story’s influential definition of retroactivity: "[Ejvety statute, which takes away or impairs vested rights acquired under existing laws, or creates a new obligation, imposes a new duty, or attaches a new disability, in respect to transactions or considerations already past, must be deemed retrospective...." Landgraf, 511 U.S. at 269, 114 S.Ct. 1483 (internal quotation marks and citation omitted). The Supreme Court has emphasized that Story’s categories represent only sufficient, rather than necessary, conditions for finding retroactivity, and that the Court’s decisions 'have used "various formulations to describe the functional conception of legislative retroactivity.” Hughes Aircraft Co. v. United States ex rel. Schumer, 520 U.S. 939, 947, 117 S.Ct. 1871, 138 L.Ed.2d 135 (1997) (internal quotation marks and brackets omitted); see also St. Cyr II, 533 U.S. at 321 n. 46, 121 S.Ct. 2271.
. As the Supreme Court noted, in the years preceding the AEDPA, over half of the applications for 212(c) relief were granted. See St. Cyr II, 533 U.S. at 296 n. 5, 121 S.Ct. 2271.
. See St. Cyr II, 533 U.S. at 323, 121 S.Ct 2271 ("Relying upon settled practice, the advice of counsel, and perhaps even assurances in open court that the entry of the plea would not foreclose § 212(c) relief, a great number of defendants in Jideonwo's and St. Cyr’s *635position, agreed to plead guilty. Now that prosecutors have received the benefit of these plea agreements, agreements that were likely facilitated by the aliens’ belief in their continued eligibility for § 212(c) relief, it would surely be contrary to familiar considerations of fair notice, reasonable reliance, and settled expectations to hold that IIRIRA’s subsequent restrictions deprive them of any possibility of such relief.”) (citation, footnote, and internal quotation marks omitted).
. The same regulations that seem quite clearly to permit an alien to file a 212(c) application with a district director before deportation proceedings are instituted, see 8 C.F.R. §§ 212.3(a)(1), (b), also seem to permit the renewal of such an application — even if the previous application had been denied— once the alien is in deportation proceedings, see § 212.3(c), (e)(1). This does not alter the fact that an alien might well delay making a 212(c) application prior to deportation proceedings — on the expectation that 212(c) relief will remain available — in order to make his case stronger by establishing a longer track record of rehabilitation, etc. Such an alien, quite sensibly, would want to wait as long as possible before using his one pre-proceedings bite at the apple.
. We noted in St. Cyr I that a "profound constitutional question” would arise under the Due Process Clause were the IIRIRA interpreted to apply retroactivity to aliens who pled guilty in reliance on the availability of 212(c) relief. St. Cyr I, 229 F.3d at 416 n. 6; see also Landgraf 511 U.S. at 266, 114 S.Ct. 1483 ("The Due Process Clause also protects the interests in fair notice and repose that may be compromised by retroactive legislation; a justification sufficient to validate a statute's prospective application under the Clause may not suffice to warrant its retroactive application.”) (internal quotation marks omitted); id. at 267 n. 21, 93 S.Ct. 1602 (stating that, in some cases, the interest in avoiding the adjudication of constitutional questions will counsel against the retroactive application of a statute). Our application in St. Cyr I of the presumption against retroac-tivity obviated the need to pursue this Due Process inquiry. See St. Cyr I, 299 F.3d at 416 n. 6.
. In this sense, deportation, like some other kinds of civil sanctions, combines an unmistakable punitive aspect with non-punitive aspects. See, e.g., Fong Haw Tan v. Phelan, 333 U.S. 6, 10, 68 S.Ct. 374, 92 L.Ed. 433 (1948) (construing narrowly a statute providing for the deportation of convicted aliens because "deportation is a drastic measure and at times the equivalent of banishment or exile. It is the forfeiture for misconduct of a residence in this country. Such a forfeiture is a penalty.”) (citation omitted); Jordan v. De George, 341 U.S. 223, 231, 71 S.Ct. 703, 95 *636L.Ed. 886 (1951) (applying the void-for-vagueness doctrine to a deportation statute because, though not a criminal statute, the statute imposed a "drastic measure,” which is at times "the equivalent of banishment or exile”) (quoting Fong Haw Tan, 333 U.S. at 10, 68 S.Ct. 374); see id. at 243, 71 S.Ct. 703 (Jackson, dissenting, joined by Black and Frankfurter, J.J.) ("We have said that deportation is equivalent to banishment or exile. Deportation proceedings technically are not criminal; but practically they are for they extend the criminal process of sentencing to include on the same convictions an additional punishment of deportation. If respondent were a citizen, his aggregate sentences of three years and a day would have been served long since and his punishment ended. But because of his alienage, he is about to begin a life sentence of exile from what has become home, of separation from his established means of livelihood for himself and his family of American citizens. This is a savage penalty and we believe due process of law requires standards for imposing it as definite and certain as those for conviction of crime.”) (footnote omitted); Costello v. INS, 376 U.S. 120, 128, 131-32, 84 S.Ct. 580, 11 L.Ed.2d 559 (1964); United States v. Restrepo, 999 F.2d 640, 647 (2d Cir.1993) (acknowledging that deportation, "as a 'forfeiture for misconduct of a residence in this country’, is a civil ‘penalty,’ ”) (quoting Fong Haw Tan, 333 U.S. at 10, 68 S.Ct. 374) (emphasis added). As such, procedures and limits more akin to those of criminal law may be appropriate. Cf. State Farm Mut. Auto. Ins. Co. v. Campbell, 538 U.S. 408, 123 S.Ct. 1513, 1519-21, 155 L.Ed.2d 585 (2003) (emphasizing the punitive aspect of punitive damages and stating that substantive and procedural due process protections apply); Cooper Indus. Inc. v. Leatherman Tool Group, Inc., 532 U.S. 424, 438-39, 121 S.Ct. 1678, 149 L.Ed.2d 674 (2001) (observing that punitive damages may serve punitive purposes as well as non-punitive purposes, such as deterrence) (citing, inter alia, Polinsky & Shavell, Punitive Damages: An Economic Analysis, 111 Harv. L.Rev. 869 (1998), and Ciraolo v. New York, 216 F.3d 236, 244-45 (2d Cir.2000) (Calabresi, J., concurring)).
. Were a quid pro quo necessary, however, it would seem that deciding not to bring an early 212(c) application, at a time when the INS often failed to initiate deportation proceedings, would confer a benefit on the INS in the form of a reduced docket. In other words, a quid pro quo of some sort, though not of the same level as existed in St. Cyr II, is also present in the instant case. We reject the need for a quid pro quo, however, on broader grounds. The Supreme Court, as noted above, has found impermissible retroactivity in cases that did not involve a quid pro quo. The Court has instead focused on whether, as a practical matter, a party has acted on the reasonable expectation that a law would not be changed. (And there are even exceptions to this generalization, since the extent to which a party conformed its conduct to the old law was not a salient factor in either Rivers v. Roadway Exp., Inc., 511 U.S. 298, 114 S.Ct. 1510, 128 L.Ed.2d 274 (1994), or *638Hughes Aircraft, 520 U.S. 939, 117 S.Ct. 1871, 138 L.Ed.2d 135.)
. Petitioner's claim that he did not seek 212(c) relief when he could have, because of his expectation that it would be available later, readily fits within the Court’s concept of reasonable reliance. But just as we today hold that a guilty plea is not the only kind of reliance that would make the abolition of 212(c) have an impermissible retroactive effect under Landgraf, so we wish to make clear that the kind of reliance involved in the instant case is itself not another exclusive category of Landgraf reliance that applies to aliens. It is just another example of reliance. Thus, there may one day be a case in which the government had for years declined to bring deportation proceedings against a de-portable alien because of its estimation that she was a very strong candidate for 212(c) relief. Cf. Matter of Gordon, 17 I. & N. Dec. at 392 (Appleman, B.M., concurring) (observing that a District Director "has every right, in fact, a duty, to exercise his prosecutive judgment whether or not to institute a deportation proceeding against an alien .... If, in screening the file of, and possibly after consultation with, such an alien, it appears to him that a deportation proceeding would surely result in a grant of section 212(c) relief ... it would be pointless to institute an expensive, vexatious, and needless deportation proceeding.”). It is more than plausible that, in such a situation, an alien may have relied on the fact that the government has not initiated deportation proceedings given her chances of receiving 212(c) relief to make important commitments to her residency in the United States (as by marrying, establishing a business, losing ties with her home country) only later to find that, after Congress had eliminated 212(c) relief, the INS seeks to deport her. Under such circumstances, it is arguable that her behavior constitutes the kind of reliance that would make the elimination of 212(c) relief impermissibly retroactive. Such a case is not before us, of course, and we express no view on the merits of such an argument. We only note it because the government in this case has contended that the holdings in St. Cyr II and Rankine represent a kind of expres-sio unius est exclusio alterius and that, as a result, no form of reliance other than that recognized in St. Cyr II can satisfy Landgraf. We wish to be clear that our analysis in this case should not be read in such a manner.
. We note that the government does not contest that Petitioner could have filed an application for 212(c) relief prior to being put into deportation proceedings. (The government, rather, challenges Petitioner's explanation of why he did not file such an application, saying that "[i]t would seem equally likely that the Petitioner did not file an affirmative application following his conviction because he did not want to bring himself to the attention of the immigration authorities.” It thereby implies that reliance on the continued availability of 212(c) relief for this decision would not be justified — a suggestion that is by no means obvious and as to which we express no opinion). An alien’s right to file such an application is furnished by 8 C.F.R. § 212.3(b) (providing that a 212(c) application may be filed "prior to, at the time of, or at any time after the applicant's departure from or arrival into the United States”) when that regulation is read in light of the extension of 212(c) relief to deportable aliens who had not temporarily left the country, see supra note 3 (discussing Francis, 532 F.2d 268, and Matter of Silva, 16 I. & N. Dec. 26). Indeed, the next sentence in section 212.3(b) requires that "[a]ll material facts and/or circumstances which the applicant knows or believes apply to the grounds of excludability or deportability ... be described.” 8’C.F.R. § 212.3(b) (emphasis added).
Though the parties have not raised the matter, our research has shown that, on March *63925, 1994, in response to an attorney's inquiry, Louis D. Crocetti, the INS’s Acting Assistant Commissioner for Adjudication, wrote a letter stating his view that an alien cannot file a 212(c) application before being put into deportation proceedings. See 71 Interpreter Releases No. 27, at 949-950 (Appendix VII) (July 18, 1994). The letter said that Francis and Silva "did not hold that a permanent resident alien may submit a 212(c) waiver application at any time.” Id. at 949. The letter went on to address 8 C.F.R. § 212.3(b), and stated that its use of the term "arrival” was meant to refer to an "alien who is applying for admission to the United States.” Id. at 950. The letter then seemed to conclude from this — despite the fact that, as noted above, section 212.3(b) itself makes reference to deportability — that "[a] permanent resident alien, who is not under deportation or exclusion proceedings, can only submit an application for a 212(c) waiver to a district director prior to his or her departure and subsequent application for readmission to the United States and upon any application for admission to the United States.” Id.
Because Petitioner was convicted of a de-portable offense in 1992, and because there is no indication that the INS would have departed at that time from its previous acceptance of "advance” applications for 212(c) relief from deportable aliens, see Matter of Gordon, 17 I. & N. Dec. at 391, we do not have to decide the effect or validity of Mr. Crocetti's 1994 letter. This is especially so since, even if there were a chance that the INS would have declined to entertain an application by Petitioner in 1992, Petitioner's alleged decision to forgo filing an application at that time would still qualify as detrimental reliance for purposes of retroactivity analysis: Petitioner’s giving up of a "shot” at 212(c) relief is rendered no less of a sacrifice because of the possibility that the INS would have rejected his application on the grounds that it was premature than that the application would have been rejected on its merits.
In any event, it is dubious that the Crocetti letter — even if such a single letter were taken to represent the INS’s settled interpretation— can defeat the reading of 8 C.F.R. § 212.3(b) that we stated above. While Auer v. Robbins, 519 U.S. 452, 461, 117 S.Ct. 905, 137 L.Ed.2d 79 (1997), requires a court to give deference to an agency's interpretation of its own regulations, such deference is "warranted only when the language of the regulation is ambiguous,” Christensen v. Harris County, 529 U.S. 576, 588, 120 S.Ct. 1655, 146 L.Ed.2d 621 (2000); see also Auer, 519 U.S. at 461, 117 S.Ct. 905 (an agency’s interpretation is given controlling weight unless plainly erroneous or inconsistent with the regulation); Taylor v. Vt. Dep’t of Educ., 313 F.3d 768, 780 (2d Cir.2002). In view of the BIA's adoption of our decision in Francis, which held that there is no rational reason to treat differently "aliens identical in every respect except for the fact that members of one class have departed and returned to this country at some point after they became deportable,” 532 F.2d at 272, it would seem that regulation 212.3(b) "plainly,” Christensen, 529 U.S. at 588, 120 S.Ct. 1655, allows a deportable alien to apply for 212(c) relief both before and after the commencement of deportation proceedings. Finally, we note that many resident aliens could have triggered their right to apply for 212(c) relief, even under the Crocetti letter's interpretation, by simply going abroad temporarily and then seeking reentry, or perhaps even by applying for 212(c) relief prior to such a planned temporary trip.
. In rejecting a categorical approach, the First Circuit stated:
The universe of all aliens who entered guilty pleas before April 1996 is too broad, as there are many reasons to plead guilty, reasons much stronger than the hope of discretionary relief from deportation: hopes of sentencing leniency in recognition of acceptance of responsibility, a better bargain from the government in exchange for not going to trial, and the like. Nonetheless, there is reason to believe that there might be some aliens who made such choices in actual and reasonable reliance on the availability of § 212(c) relief. Good defense counsel in criminal cases often advise clients about immigration law consequences. There may well be those who pled despite having a colorable defense because the act of accepting responsibility would bode well for their § 212(c) application. Similarly, there may be aliens who pled to lesser offenses than those charged in order to ensure that they would serve less than five years of prison time. If applied to such aliens, that is, those who pled to or did not contest criminal charges in reasonable reliance on the availability of § 212(c) relief, AEDPA § 440(d) would have a retroactive effect.
212 F.3d at 39-40.